akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        Arrays.fill(arr, 'x');
        System.out.println(arr);
    }
}

Measured memory_bytes: 21204
import java.util.*;
import java.io.*;

class Main {

	void solve () {

		int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
		out.println(Math.min(b/a, c));
		
		
	}
	
	public static Scanner in = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out);
	public static void main(String[] args) {
		new Main().solve();
		out.flush();
	}

}

Measured memory_bytes: 21844
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
using namespace std;
int main(){
    int a,b,c,d; cin>>a>>b>>c>>d;
    cout<<c-d+b<<" ";
    cout<<d+c-a<<" ";
    cout<<a-d+b<<" ";
    cout<<b+c-a;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  std::string s;
  cin >> s;
  int64_t result = 0;

  std::string t;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      t += "A";
    } else if (i + 1 < s.size() && s[i] == 'B' && s[i + 1] == 'C') {
      t += 'D';
      i++;
    } else {
      t += 'X';
    }
  }

  int64_t count = 0;
  for (auto c : t) {
    if (c == 'A') {
      count++;
    } else if (c == 'D') {
      result += count;
    } else {
      count = 0;
    }
  }

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 1020
WHITE = 0
GRAY = 1
BLACK = 2

INF = 1.0e+6

def prim(M):
    n = len(M)
    color = [WHITE] * n
    d = [INF] * n
    p = [-1] * n

    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]

        if u == -1:
            break

        color[u] = BLACK
        for v in range(n):
            if color[v] != BLACK and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY

    sum = 0
    for i in range(n):
        if p[i] != -1:
            sum += M[i][p[i]]

    return sum


if __name__ == "__main__":
    n = int(input())

    M = [] * n

    for i in range(n):
        M.append(list(map(int, input().split())))
        M[i] = [INF if j == -1 else j for j in M[i]]

    print(prim(M))



Measured memory_bytes: 5900
input()

t = ''
c = 0
stock = 0
for s in input():
    if s == ')':
        if c == 0:
            stock += 1
        else:
            t += ')'
            c -= 1
    else:
        if stock:
            t = '(' * stock + t + ')' * stock
            stock = 0
        c += 1
        t += '('
t = '(' * stock + t + ')' * stock + ')' * c
print(t)

Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
long long a,b,k;

int main()
{
    #ifdef __LOCAL__
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    cin>>a>>b>>k;
    if(k<=a)
        cout<<a-k<<" "<<b;
    else if(k<=a+b)
        cout<<0<<" "<<b-(k-a);
    else
        cout<<0<<" "<<0;
    
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100;

int n;
char s[maxn + 1], t[maxn + 1];

int main(void) {
  scanf("%d%s%s", &n, s, t);
  for (int m = n; m <= 2 * n; ++m) {
    bool bad = false;
    for (int i = 0; i < n; ++i) {
      int j = i - (m - n);
      if (j >= 0 && j < n && s[i] != t[j]) {
        bad = true;
        break;
      }
    }
    if (!bad) {
      printf("%d\n", m);
      return 0;
    }
  }
}


Measured memory_bytes: 128
fun main(args: Array<String>) {
    val (N, W) = readIntegerList()
    val dp = Array(N + 1) { LongArray(W + 1) { 0L } }
    for (i in 0 until N) {
        val (w, v) = readIntegerList()
        for (j in 0..W) {
            if (0 <= j - w) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w] + v)
            } else {
                dp[i + 1][j] = dp[i][j]
            }
        }
    }
    println(dp[N].max())
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 156280
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long LL;
typedef unsigned long long ULL;
const LL LINF = 0x3f3f3f3f3f3f3f3f; 
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const ULL P = 131;
const int N = 2e5+7;

int a[N];

int main()
{
	int n,t,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t;
		if(i%2 && t%2) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3508
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, type;
    cin >> N;

    int i = 0;
    while (i < N) {
        string s;
        cin >> s;
        if (s == "Y") {
            cout << "Four" << endl;
            break;
        }
        i++;
    }

    if (i == N) {
        cout << "Three" << endl;
    }
}


Measured memory_bytes: 3544
#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <climits>
#include <iomanip>

#define EPS 1e-7
#define LLMAX 9223372036854775807
#define INTMAX 2147483647
#define ULLMAX 18446744073709551615
#define precision(n) cout << setprecision(n) << fixed
#define forn(i, n) for (int i = 0; i<(int)n; ++i)
#define forr(i, t, n) for (int i = t; i<n; ++i)
#define rforr(i, t, n) (int i = n-1; i>=t; --i)
#define rfor(i, n) for (int i = n-1; i>=0; --i)
#define rmod(x, y) (((x%y)+y)%y)
#define pb push_back
#define emp emplace_back
using namespace std;
typedef vector<int>::iterator vit;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MAXN = 101;
const int MAXW = 1e5+1;

//STRUCTS


//OPERATORS


//GLOBALS
int n, cap;
ll dp[MAXN][MAXW];
int w[MAXN], v[MAXN];

//FUNCTIONS
ll dyn()
{
	forn(i, n+1)
	{
		forn(j, cap+1)
		{
			if (i == 0 or j == 0) dp[i][j] = 0;
			else if (j<w[i-1]) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + ll(v[i-1]));
		}
	}
	return dp[n][cap];
}

//PROBLEM: 
//LINK: 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);


		cin >> n >> cap;
		forn(i, n) cin >> w[i] >> v[i];
		cout << dyn();



	return 0;
}

Measured memory_bytes: 79232
def use_fast_io():
    global input
    import io
    import sys
    f = io.BytesIO(sys.stdin.buffer.read())
    input = f.readline
use_fast_io()


from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = map(int, input().split())
graph = [[10**10] * N for _ in range(N)]
for _ in range(M):
    s, t, w = map(int, input().split())
    if w <= L:
        graph[s-1][t-1] = graph[t-1][s-1] = w
graph = floyd_warshall(graph, directed=False)
graph = floyd_warshall(graph <= L, directed=False)
graph[np.isinf(graph)] = 0

Q = int(input())
ans = []
for _ in range(Q):
    s, t = map(int, input().split())
    ans.append(int(graph[s-1][t-1]) - 1)
print(*ans, sep='\n')


Measured memory_bytes: 19620
#include <cstdio>
#include <set>
#include <cstring>

using std::set;

int u[101000], v[101000], tot = 0;
char c[101000];
set<int> st;

void dfs(int x, int siz)
{
	int rt = x;
	siz--; x++;
	while(1)
	{
		set<int>::iterator it = st.lower_bound(siz); 
		if(st.size() == 0 || (it == st.begin() && (*it) != siz)) break;
		if((*it) != siz) --it;
		u[++tot] = rt; v[tot] = x;
		int new_rt = x;
		x += (*it); siz -= (*it);
		st.erase(it);
		dfs(new_rt, (*it));
	}
	while(siz) u[++tot] = rt, v[tot] = x, x++, siz--;
}
int main()
{
	scanf("%s", c + 1);
	int n = strlen(c + 1);
	for(int i = 1; i <= (n >> 1); i++)
	{
		if(c[i] != c[n - i]) return 0 * puts("-1");
	}
	if(c[1] != '1' || c[n] == '1') return 0 * puts("-1");
	for(int i = 2; i <= (n >> 1); i++) if(c[i] == '1') st.insert(i);
	dfs(1, n);
	if(st.size() != 0) return 0 * puts("-1");
	for(int i = 1; i < n; i++) printf("%d %d\n", u[i], v[i]);
	return 0;
}

Measured memory_bytes: 6784
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int main() {
  int a;
  cin>>a;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(i*j==a){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    if (v.size() == 0) return os << "]";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    lint N;
    cin >> N;
    vec<lint> B_list(N - 1);
    range(i, 0, N - 1) cin >> B_list.at(i);
    vec<lint> A_list(N);
    A_list.at(0) = B_list.at(0);
    A_list.at(N - 1) = B_list.at(N - 2);
    range(i, 1, N - 1) {
        A_list.at(i) = min(B_list.at(i - 1), B_list.at(i));
    }
    lint res = 0;
    for (const lint& A : A_list) res += A;
    cout << res << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  
  int total = 0;
  int min = 1001001;
  
  for(int i = 0; i < N; i++){
    cin >> A.at(i);
    total += A.at(i);
  }
  
  int X = 0;
  int Y = 0;
  
  for(int i = 0; i < N; i++){  
    X += A.at(i);
    Y = total - X;
    if(min > abs(X-Y)) min = abs(X-Y);
    }
  cout << min << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
#define YMAX 250001
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,M,K;
	scan(N);scan(M);scan(K);
	int flag=0;
	rep(i,N+1){
		rep(j,M+1){
			if(i*M+(N-2*i)*j==K) flag=1;
		}
	}
	if(flag) prin("Yes");
	else prin("No");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
int main(){
    std::string s;
    cin >> s;
    ll bit=0;
    ll count = 0;
    ll tmp;
    for(int bit=0; bit < (1<<s.length()-1);bit++){
        tmp=0;
        for(int i=0;i < s.length();i++){
            tmp = tmp*10 + s[i]-'0';
            if(bit & (1<<i)){
                count += tmp;
                tmp=0;
            }
        }
        count+=tmp;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define ce(i,r) i==r?'\n':' '
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;
typedef long long ll;
const int MAX_N=1e2+5;
inline int qi(){
    int f=0,fu=1; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
    while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
    return f*fu;
}
inline ll ql(){
	ll f=0;int fu=1; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
    while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
    return f*fu;
}
int main()
{
	ll x=abs(ql()),k=ql(),d=ql();
	ll mov=x/d,ans;
	if(k<=mov) ans=x-k*d;
	else{
		k-=mov;
		ans=x-mov*d; 
		if(k&1) ans=abs(ans-d);
	}  
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3748
#include <stdio.h>
#define N 36

typedef struct{
  char c;
  int num;
}Data;

void bubbleSort(Data*, int);
void selectionSort(Data*, int);
char* isStable(Data*, Data*, int);
  
int main(){

  Data card[N], data[N];
  int n, i;
  char a;

  scanf("%d", &n);
  
  for(i=0; i<n; i++){
    scanf(" %c%d",&card[i].c, &card[i].num);
   }

  for(i=0; i<n; i++){
    data[i]=card[i];
  }

  bubbleSort(card, n);
  
  for(i=0; i<n-1; i++){
    printf("%c%d ", card[i].c, card[i].num);
  } printf("%c%d\n", card[n-1].c, card[i].num);

  
  printf("%s\n", isStable(card, card, n));
  

  
  selectionSort(data, n);

  for(i=0; i<n-1; i++){
    printf("%c%d ", data[i].c, data[i].num);
  } printf("%c%d\n", data[n-1].c, data[i].num);

  printf("%s\n", isStable(card, data, n));
  

 
  return 0;
}

void bubbleSort(Data* card, int n){

  int i, j;
  Data temp;
  
  for(i=0; i<n-1; i++){

    for(j=n-1; j>i; j--){
      
      if(card[j].num<card[j-1].num){
	temp =card[j];
	card[j]=card[j-1];
	card[j-1]=temp;
      }
    }
  }  
}

void selectionSort(Data* data, int n){

  int i, j, min;
  Data temp;

  for(i=0; i<n-1; i++){

    min= i;
    for(j=i+1; j<n; j++){
      if(data[j].num<data[min].num){
	min=j;
      }
    }
    temp=data[i];
    data[i]=data[min];
    data[min]=temp;

  }
}

char* isStable(Data* bubble, Data* comp, int n){

  int i;
  char *result;

  for(i=0; i<n; i++){
    if(bubble[i].c!= comp[i].c || bubble[i].num!= comp[i].num){
      result = "Not stable";
      return result;
    }
  }
  result = "Stable";
  return result;  
}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

	bool R[500][500] = {};
	bool B[500][500] = {};

	void Solve() {
		UL H, W; cin >> H >> W;
		rep(y, H) {
			R[0][y] = true;
			B[W - 1][y] = true;
			for (UL x = 1; x < W - 1; x++) {
				B[x][y] = (y % 2 == 0);
				R[x][y] = (y % 2 == 1);
			}
		}
		rep(y, H) {
			rep(x, W) {
				char c; cin >> c;
				if (c == '#') R[x][y] = B[x][y] = true;
			}
		}
		rep(y, H) {
			rep(x, W) {
				cout << (R[x][y] ? '#' : '.');
			}cout << endl;
		}cout << endl;
		rep(y, H) {
			rep(x, W) {
				cout << (B[x][y] ? '#' : '.');
			}cout << endl;
		}cout << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll l=0;
	string L;
	cout << 0<<endl;
	cin >>L;
	if(L=="Vacant"){
		return 0;
	}
	ll next=(n-l)/2;
	string ne;
	while(true){
		cout << next<<endl;
		cin>>ne;
		if(ne=="Vacant"){
			return 0;
		}
		if(ne==L){
			if((l-next)%2==0){
				l=next;
				L=ne;
			}
			else{
				n=next;
			}
		}
		else{
			if((l-next)%2==0){
				n=next;
			}
			else{
				l=next;
				L=ne;
			}
		}
		next=(n-l)/2+l;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 852
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<algorithm>
using namespace std;

int main()
{
  int n, d;
  cin >> n >> d;
  vector<vector<int>> dots;
  for (int i=0;i<n;i++) {
    dots.push_back(vector<int>());
    for (int j=0;j<d;j++) {
      int t;
      cin >> t;
      dots[i].push_back(t);
    }
  }
  int ans = 0;
  for (int i=0;i<n;i++) {
    for (int j=i+1;j<n;j++) {
      int t = 0;
      for (int k=0;k<d;k++) {
        t += (dots[i][k] - dots[j][k])*(dots[i][k] - dots[j][k]);
      }
      int t2 = (int)sqrt(t);
      if (t2*t2 == t) ans++;
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for (int i=0; i<n/2; i++) {
        if (s[i] != s[n-i-1]) {
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d,sum=0;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(a<b) sum=a*c;
	else
	{
		sum=b*c+(a-b)*d;
	} 
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 888
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#define ll long long int
using namespace std;
struct node
{
    ll x,y,cost=0;
};
char dp[1005][1005];
ll check[1005][1005];
queue<node*> q;
int main()
{
    ll n,m,i,j,sum=0,ans=0;
    cin>>n>>m;
    node *p,*t;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {
                cin>>dp[i][j];
                if(dp[i][j]=='#')
                {
                    p=new node;
                    p->x=i;
                    p->y=j;
                    p->cost=0;
                    q.push(p);
                    check[i][j]=-1;
                }
            }
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(t->x-1>=1&&check[t->x-1][t->y]==0)
        {
            p=new node;
            p->x=t->x-1;
            p->y=t->y;
            p->cost=t->cost+1;
            q.push(p);
            check[p->x][p->y]=p->cost;
        }
        if(t->x+1<=n&&check[t->x+1][t->y]==0)
        {
            p=new node;
            p->x=t->x+1;
            p->y=t->y;
            p->cost=t->cost+1;
            q.push(p);
            check[p->x][p->y]=p->cost;
        }
        if(t->y-1>=1&&check[t->x][t->y-1]==0)
        {
            p=new node;
            p->x=t->x;
            p->y=t->y-1;
            p->cost=t->cost+1;
            q.push(p);
           check[p->x][p->y]=p->cost;
        }
        if(t->y+1<=m&&check[t->x][t->y+1]==0)
        {
            p=new node;
            p->x=t->x;
            p->y=t->y+1;
            p->cost=t->cost+1;
            q.push(p);
           check[p->x][p->y]=p->cost;
        }
        delete t;
    }
    ll maxn=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(check[i][j]>0&&check[i][j]>maxn)
            maxn=check[i][j];
        cout<<maxn;
}


Measured memory_bytes: 48528
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF=2147483647;
struct Edge
{
	int to;
	int nxt;
	int flow;
}e[400005];
int n,m,s,t,edgenum,head[1005],dep[1005],cur[1005];
int a[105][105],num[105][105],b[105][105],now[105];
vector<int>val[105][105];
queue<int>q;
void add(int u,int v,int f)
{
	e[++edgenum].flow=f;
	e[edgenum].to=v;
	e[edgenum].nxt=head[u];
	head[u]=edgenum;
}
int dfs(int node,int nowf)
{
	if(node==t)return nowf;
	for(int&hd=cur[node];hd;hd=e[hd].nxt)
	{
		int to=e[hd].to;
		if(e[hd].flow==0)continue;
		if(dep[to]==dep[node]+1)
		{
			int d=dfs(to,min(nowf,e[hd].flow));
			if(d)
			{
				e[hd].flow-=d;
				e[hd^1].flow+=d;
				return d;
			}
		}
	}
	return 0;
}
bool bfs()
{
	while(!q.empty()) q.pop();
	for(int i=1;i<=t;i++)dep[i]=0;
	q.push(s);
	dep[s]=1;
	while(!q.empty())
	{
		int node=q.front();
		q.pop();
		for(int hd=head[node];hd;hd=e[hd].nxt)
		{
			int to=e[hd].to;
			if(e[hd].flow==0)continue;
			if(!dep[to])
			{
				dep[to]=dep[node]+1;
				q.push(to);
			}
		}
		if(dep[t])return 1;
	}
	return dep[t];
}
int Dinic()
{
	int ans=0,d=0;
	while(bfs())
	{
		for(int i=1;i<=t;i++)cur[i]=head[i];
		while((d=dfs(s,INF)))
		  ans+=d;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			num[i][(a[i][j]-1)/m+1]++;
			val[i][(a[i][j]-1)/m+1].push_back(a[i][j]);
		}
	}
	for(int o=1;o<=m;o++)
	{
		edgenum=1;
		memset(head,0,sizeof(head));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(num[i][j])
				{
					add(i,j+n,1);
					add(j+n,i,0);
				}
			}
		}
		s=2*n+1;
		t=2*n+2;
		for(int i=1;i<=n;i++)
		{
			add(s,i,1);
			add(i,s,0);
			add(i+n,t,1);
			add(t,i+n,0);
		}
		Dinic();
		for(int i=1;i<=n;i++)
		{
			for(int hd=head[i];hd;hd=e[hd].nxt)
			{
				int to=e[hd].to;
				if(to>n&&e[hd].flow==0)
				{
					b[i][o]=to-n;
					num[i][to-n]--;
					break;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)now[j]=0;
		for(int j=1;j<=m;j++)
		{
			b[i][j]=val[i][b[i][j]][now[b[i][j]]++];
			printf("%d ",b[i][j]);
		}
		printf("\n");
	}
	for(int j=1;j<=m;j++)
	{
		for(int i=1;i<=n;i++)now[i]=b[i][j];
		sort(now+1,now+n+1);
		for(int i=1;i<=n;i++)b[i][j]=now[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		  printf("%d ",b[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
pair<int, int> solve(string s)
{
    pair<int, int> res = {-2, -2};
    for(int i = 0; i < s.size() - 1; i++) if(s[i] == s[i + 1]) res = make_pair(i, i + 1);
    if(res.first != -2) return res;
    for(int i = 0; i < s.size() - 2; i++)
    {
        string t = s.substr(i, 3);
        sort(t.begin(), t.end());
        if(t[0] == t[1] || t[1] == t[2]) res = make_pair(i, i + 2);
    }
    return res;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    while(cin >> s)
    {
        pair<int, int> ans = solve(s);
        cout << ans.first + 1 << " " << ans.second + 1 << endl;
    }
    return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>

using namespace std;

const int INF = (1<<30) - 1;

string table = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    while(cin >> n, n){
        vector<int> key(n);
        for(int i=0; i<n; i++)
            cin >> key[i];
        string s;
        cin >> s;
        for(int i=0; i<s.size(); i++){
            char &c = s[i];
            c = table[(table.find_first_of(c)-key[i%n]+52)%52];
        }
        cout << s << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1212
n = int(input())
arr = [0] + list(map(int, input().split())) + [0]
sum_arr = sum(abs(arr[i] - arr[i+1]) for i in range(n+1))

for i in range(1, n+1):
    diff = abs(arr[i-1] - arr[i]) + abs(arr[i] - arr[i+1])\
               - abs(arr[i-1] - arr[i+1])
    print(sum_arr - diff)

Measured memory_bytes: 20504
// Problem : A - The Number of Even Pairs
// Contest : AtCoder Beginner Contest 159
// URL : https://atcoder.jp/contests/abc159/tasks/abc159_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms

#include<bits/stdc++.h>
using namespace std ;

#define int         long long int
#define all(a)      (a).begin(),(a).end()
#define f           first
#define s           second
#define endl        '\n'
#define MOD         1000000007

void solve()
{
		int n, m ;
		cin >> n >> m ;
		int ans = n*(n - 1)/2 + m * (m-1)/2 ;
		cout << ans ;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1 ;
    //cin >> t ;
    while(t--)
    {
        solve() ;
    }
    return 0 ;
}

Measured memory_bytes: 256
def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()

Measured memory_bytes: 3652
#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  
  vector<int> vd(k);
  for (auto &d : vd) {
  	cin >> d;
  }
  
  sort(vd.begin(), vd.end());
  
  auto check = [&] (int num) {
    string num_s = to_string(num);
    return all_of(num_s.begin(), num_s.end(), [&] (char ch) {
      return !binary_search(vd.begin(), vd.end(), ch - '0');
    });
  };
  
  int ans;
  for (int i = n; i <= 1e5; i++) {
    if (check(i)) {
      ans = i;
      break;
    }
  }
  
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i,j,x[10000];
    for(i=1;i<=10000;i++)
    {
        scanf("%d",&x[i]);
        if(x[i]==0)
            break;
    }
    for(i=1;i<=10000;i++)
    {
        if(x[i]==0)
            break;
        printf("Case %d: %d\n",i,x[i]);
    }
return 0;
}



Measured memory_bytes: 2060
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 1; i*j < n; ++j) {
            ans++;
        }
    }
    cout << ans;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

double f(int x1, int y1, int x2, int y2) {
  return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main() {
  int n;
  cin >> n;
  vector<P> vec(n);
  rep(i, n) cin >> vec.at(i).first >> vec.at(i).second;
  double sum = 0;
  rep(i,n)for(int j = i+1; j < n; j++) sum += f(vec.at(i).first, vec.at(i).second, vec.at(j).first, vec.at(j).second);
  cout << fixed << setprecision(10) << sum * 2 / n << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
	int a,i;
	double b,sum=0;
	char c[3];
	char *d="JPY";
	scanf("%d",&a);
	for(i=0;i<a;i++){
		scanf("%lf %s",&b,c);
		if(strcmp(c,d)==0) sum+=b;
		else sum+=b*380000;
		//printf("%s",c);
	}
	printf("%lf\n",sum);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define f(i, a, b) for(ll i=a; i<b; i++)
#define fr(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define endl "\n"
using namespace std;

bool sortbysec(const pair<ll,ll> &a, 
              const pair<ll,ll> &b) 
{ 
    return (a.second < b.second); 
} 

ll maxSubArraySum(ll a[], ll size) 
{ 
    ll max_so_far = INT_MIN, max_ending_here = 0; 
  
    for (ll i = 0; i < size; i++) 
    { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 
    } 
    return max_so_far; 
} 

ll findSubarraySum(ll arr[], ll n, ll sum = 0) 
{
    unordered_map<ll, ll> prevSum;
    ll res = 0;
    ll currsum = 0;
    for (ll i = 0; i < n; i++)
    {
        currsum += arr[i];
        if (currsum == sum) res++;
        if (prevSum.find(currsum - sum) != prevSum.end()) res += (prevSum[currsum - sum]);
        prevSum[currsum]++;
    }
    return res; 
} 
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
ll powmp(ll x, ll y, ll p) 
{ 
    ll res = 1;     x = x % p;   
    while (y > 0) 
    {  
        if (y & 1)  res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll k;string s;
    cin>>k>>s;
    if(k>=s.length()) cout<<s;
    else cout<<s.substr(0,k)+"...";
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;

constexpr int64_t MAX_N = 100;
constexpr int64_t MAX_V = MAX_N * 1000;
int64_t dp[MAX_N + 1][MAX_V + 1];

int64_t solve(const int64_t N, const int64_t W, const vector<int64_t>& w, const vector<int64_t>& v) {
  // Initialize dp table
  dp[0][0] = 0;
  for (auto i = 1; i <= MAX_V; ++i) {
    dp[0][i] = W + 1;
  }

  // dp
  for (auto i = 1; i <= N; ++i) {
    for (auto j = 0; j <= MAX_V; ++j) {
      if (j - v[i - 1] >= 0) {
        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  // Find max_value
  int64_t max_value = 0;
  for (auto i = 1; i <= MAX_V; ++i) {
    if (dp[N][i] <= W) {
      max_value = i;
    }
  }

  return max_value;
}

int main() {
  // Input
  int64_t N, W;

  cin >> N >> W;

  vector<int64_t> w(N), v(N);
  for (auto i = 0; i < N; ++i) {
    cin >> w[i] >> v[i];
  }

  // Solve
  auto ans = solve(N, W, w, v);

  // Answer
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 79104
H, W = map(int, input().split())
S = [input() for i in range(H)]

offset_h = (-1,-1,-1,0,0,1,1,1)
offset_w = (-1,0,1,-1,1,-1,0,1)
for h in range(H):
  for w in range(W):
    if S[h][w] == "#":
      print("#", end="")
    else:
      bomb = 0
      for i,j in zip(offset_h, offset_w):
        if h+i >= 0 and h+i < H and w+j >=0 and w+j < W and S[h+i][w+j]=="#":
          bomb += 1
            
      print(bomb, end="")
     
  print("")
    

Measured memory_bytes: 3444
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int x, y;
string s;

int dx[] = { 0, 1, 0, -1};
int dy[] = { 1, 0, -1, 0 };

int main(){
	while (cin >> x >> y&&x + y){
		int posx = 1, posy = 1, muki = 0;
		while (cin >> s){
			int num;
			if (s == "STOP")break;
			if (s == "FORWARD"){
				cin >> num;
				REP(i, num){
					int ny = posy + dy[muki], nx = posx + dx[muki];
					if (ny >= 1 && ny <= y&&nx >= 1 && nx <= x){
						posy = ny, posx = nx;
					}
				}
			}
			else if (s == "BACKWARD"){
				cin >> num;
				REP(i, num){
					int ny = posy - dy[muki], nx = posx - dx[muki];
					if (ny >= 1 && ny <= y&&nx >= 1 && nx <= x){
						posy = ny, posx = nx;
					}
				}
			}
			else if (s == "RIGHT"){
				muki++;
				if (muki > 3)muki = 0;
			}
			else if (s == "LEFT"){
				muki--;
				if (muki < 0)muki = 3;
			}
		}
		cout << posx << " " << posy << endl;
	}
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
    int N;cin>>N;
    int A[N];
    REP(i,N)cin>>A[i];
    int ans=0;
    bool ok=true;
    REP(i,N){
        if(i==0){
          	if(A[i]!=0){
            	ok=false;
            	break;
            }
        }
        else{
            if(A[i]-A[i-1]>1){
                ok=false;
                break;
            }
            if(A[i]-A[i-1]==1)ans++;
            if(A[i]-A[i-1]<=0)ans+=A[i];
        }
    }
    cout<<(ok?ans:-1)<<endl;
}

Measured memory_bytes: 1792
import java.util.*;

class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int l = sc.nextInt();
    int r = sc.nextInt();
    int d = sc.nextInt();
    int a;
    int count = 0;
    for (int i = 0; i < r + 1; i++) {
      a = d * i;
      if (a >= l && a <= r) {
        count = count + 1;
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 35676
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        x: usize,
    }

    if x == 1 {
        println!("0");
    } else {
        println!("1");
    }
}


Measured memory_bytes: 2092
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;

int GetMaximum(int X, vector<int> m){
    int sum = accumulate(m.begin(), m.end(), 0);
    if(X<sum) return -1;
    X -= sum;
    auto minM = *(min_element(m.begin(), m.end()));
    return m.size() +  X/ minM;
}

int main()
{
    int N;
    int X;
    int mi;
    vector<int> m;
    cin >> N >> X;
    for(int i=0;i<N;i++){
        cin >> mi;
        m.push_back(mi);
    }
    auto n = GetMaximum(X,m);
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;
    string S; cin >> S;
    vector<ll> B(N+1), W(N+1);
    if(S[0] == '#')B[1]=1;
    if(S[N-1] == '.') W[N-1] = 1;
    for(int i = 2; i <= N; i++){
        B[i] = B[i-1];
        if(S[i-1] == '#') B[i]++;
    }
    for(int i = N-2; i >= 0; i--){
        W[i] = W[i+1];
        if(S[i] == '.') W[i]++;
    }
    ll ans = 1000000000;
    for(int i = N-1; i >=0; i--){
        ll tmp = 1000000000;
        tmp = B[i] + W[i+1];
        ans = min(ans, tmp);

    }

    cout << ans << endl;
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int g[N][N],b[N],n;
bool appear[N][N];
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i = 0;i < 3; ++i)
        for(int j = 0;j < 3; ++j)
            cin >> g[i][j];
    cin >> n;
    for(int i = 0;i < n; ++i) {
        cin >> b[i];
    }
    for(int i = 0;i < 3; ++i) {
        for(int j = 0;j < 3; ++j) {
            for(int k = 0;k < n; ++k) {
                if(b[k] == g[i][j]) appear[i][j] = 1;
            }
        }
    }
    bool f = 0;
    for(int i = 0;i < 3; ++i) {
        if(appear[i][0] and appear[i][1] and appear[i][2]) f = 1;
        if(appear[0][i] and appear[1][i] and appear[2][i]) f = 1;
    }
    if(appear[0][0] and appear[1][1] and appear[2][2]) f = 1;
    if(appear[0][2] and appear[1][1] and appear[2][0]) f = 1;
    if(f) cout << "Yes";
    else cout << "No";

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)3e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);
 
#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        

int n, b[maxn], a[maxn];
ll s1, s2;
main () {
	scanf("%d", &n);;
	forn(i, 1, n) scanf("%d", &a[i]), s1 += a[i];
	forn(i, 1, n) scanf("%d", &b[i]), s2 += b[i];
	ll dif = s2 - s1, step = 0;
	forn(i, 1, n){
		if(a[i] < b[i]) step += (b[i] - a[i] + 1) / 2;	
	}
	if(step <= dif) puts("Yes");
	else puts("No");
}

Measured memory_bytes: 384
n,m = map(int,input().split())
ls = [[x for x in input() + '#'] for i in range(n)] + [['#']*(m+1)]
yokodp = [[0 for x in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    yoko = 0
    for j in range(m+1):
        if ls[i][j] == '#':
            yokodp[i][j] = yoko
            yoko = 0
        else:
            yoko += 1
for i in range(n,-1,-1):
    check = 0
    for j in range(m,-1,-1):
        if yokodp[i][j] != 0:
            check = yokodp[i][j]
        if ls[i][j] == '.':
            yokodp[i][j] = check
tatedp = [[0 for x in range(m+1)] for i in range(n+1)]            
for j in range(m+1):
    tate = 0
    for i in range(n+1):
        if ls[i][j] == '#':
            tatedp[i][j] = tate
            tate = 0
        else:
            tate += 1
for j in range(m,-1,-1):
    for i in range(n,-1,-1):
        if tatedp[i][j] != 0:
            check = tatedp[i][j]
        if ls[i][j] == '.':
            tatedp[i][j] = check
ans = 0
for i in range(n):
    for j in range(m):
        if ls[i][j] == '.':
            ans = max(ans,tatedp[i][j] + yokodp[i][j] - 1)
print(ans)


Measured memory_bytes: 248072
n = int(input())
a = [[] for _ in range(0, 2)]
for i in range(0, 2):
    a[i] = [int(_) for _ in input().split()]

ans = 0
for  i in range(0, n):
    total = 0
    for j in range(0, i+1):
        total += a[0][j]
    for k in range(i, n):
        total += a[1][k]
    if ans < total:
        ans = total
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> ab(n, pair<int, int>());
    for (int i = 0; i < n; i++)
    {
        cin >> ab.at(i).first >> ab.at(i).second;
    }
    sort(ab.begin(), ab.end());

    vector<vector<int>> dp(n + 1, vector<int>(t, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < t; j++)
        {
            int ai = ab.at(i).first, bi = ab.at(i).second;
            if (j - ai >= 0)
            {
                dp.at(i + 1).at(j) = max(dp.at(i).at(j - ai) + bi, dp.at(i).at(j));
            }
            else
            {
                dp.at(i + 1).at(j) = dp.at(i).at(j);
            }
        }
    }

    vector<int> max_bi(n + 1, 0);
    int tmp_max = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        tmp_max = max(tmp_max, ab.at(i).second);
        max_bi.at(i) = tmp_max;
    }

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        res = max(res, dp.at(i).at(t - 1) + max_bi.at(i));
    }
    cout << res << endl;
}

Measured memory_bytes: 37632
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main(){
    int N; cin >> N;
    vector<pint> A(N);
    for(int i=0; i<N;i++){
        cin >> A[i].first;
        A[i].second = i;
    }
    sort(A.begin(), A.end());

    for(int i=0; i<N;i++) cout << A[i].second +1 << ' ';

}

Measured memory_bytes: 1536
// #includes {{{
#ifdef MY_DEBUG
#include "header/header.hpp"
#else
#include <bits/stdc++.h>
#endif

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

//debug

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

template<class T>
T inf(){
	return numeric_limits<T>::has_infinity?numeric_limits<T>::infinity():(numeric_limits<T>::max()/2);
}

typedef pair<int,int> pii;

#ifdef MY_DEBUG
#include"print.hpp"
#include"debug.hpp"
#endif
// }}}

//{{{ Union-Find
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		int r;
		compress(x,r);
		return r;
	}
	int size(int x) {
		return -data[root(x)];
	}
	void compress(int x,int &r){
		if(data[x]<0){
			r=x;
			return;
		}
		compress(data[x],r);
		data[x]=r;
	}
};
//}}}

Int N;
vector<Int> x;
vector<Int> y;

void solve(){
	set<pair<Int,Int> > s,v;
	REP(i,N)s.insert({x[i],y[i]});
	REP(i,N){
		REP(j,N){
			if(i==j)continue;
			pair<Int,Int> p = {x[i]-x[j], y[i]-y[j]};
//			if(p.first>0 or (p.first==0 and p.second>0))v.insert(p);
			v.insert(p);
		}
	}
	Int ans0 = N;
	for(auto &&d:v){
		Int ans = N;
		auto s2(s);
		while(!s2.empty()){
			auto p0 = *s2.begin();
			vector<pair<Int,Int> > w = {p0};
			auto p = p0;
			while(1){
				p.first += d.first;
				p.second += d.second;
				if(s2.find(p)==s2.end()){
					break;
				}
				w.push_back(p);
			}
			p = p0;
			while(1){
				p.first -= d.first;
				p.second -= d.second;
				if(s2.find(p)==s2.end()){
					break;
				}
				w.push_back(p);
			}
			ans -= w.size() - 1;
			for(auto &&p:w){
				s2.erase(p);
			}
		}
		ans0 = min(ans,ans0);
	}
	cout<<ans0<<endl;
}

//{{{ main fucnction
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	x.assign(N,Int());
	y.assign(N,Int());
	for(int i = 0 ; i < N ; i++){
		cin >> x[i];
		cin >> y[i];
	}
	solve();
	return 0;
}

//}}}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
#define rep(i, n) for (int i=0; i<int(n); i++)

lint f(pair<lint,lint> a, pair<lint,lint> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main() {
    lint n; cin >> n;
    vector<pair<lint, lint>> xy(n);
    rep(i,n) {
        cin >> xy[i].first >> xy[i].second;
    }
    vector<pair<lint,lint>> cc(8);
    vector<lint> ccv(8); rep(i,8) ccv[i] = 1e18;
    vector<pair<lint,lint>> ca(8);
    ca[0] = make_pair(-10000000000,-10000000000);
    ca[1] = make_pair(0, -10000000000);
    ca[2] = make_pair(10000000000,-10000000000);
    ca[3] = make_pair(-10000000000,0);
    ca[4] = make_pair(10000000000,0);
    ca[5] = make_pair(-10000000000,-10000000000);
    ca[6] = make_pair(0, -10000000000);
    ca[7] = make_pair(10000000000, -10000000000);

    
    rep(i,n) {
        rep(j,8) {
            lint t = f(xy[i], ca[j]);
            if (t < ccv[j]) {
                ccv[j] = t;
                cc[j] = xy[i];
            }
        }
    }
    lint ans = 0;
    rep(i,n) {
        rep(j,8) {
            ans = max(ans, f(xy[i], cc[j]));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 6416
#include <bits/stdc++.h>
using namespace std;
typedef long long kaage;
#define int kaage
signed main() {
  int N;
  cin >> N;
  vector<int>A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<vector<int>>ki(N);
  for(int i = 0; i < N-1; i++) {
    int a,b;
    cin >> a >> b;
    a--;b--;
    ki[a].push_back(b);
    ki[b].push_back(a);
  }
  queue<int>que;
  que.push(0);
  vector<int>cnt(N,-1);
  cnt[0] = 0;
  while(!que.empty()) {
    int x = que.front();
    que.pop();
    for(int i = 0; i < ki[x].size(); i++) {
      if(cnt[ki[x][i]] == -1) {
        cnt[ki[x][i]] = cnt[x]+1;
        que.push(ki[x][i]);
      }
    }
  }
  vector<vector<int>>cnt2(N);
  vector<int>res(N);
  int mx = 0;
  for(int i = 0; i < N; i++) {
    if(ki[i].size() == 1){
      res[i] = A[i];
    }
    mx = max(mx,cnt[i]);
    cnt2[cnt[i]].push_back(i);
  }
  for(int i = mx-1; i >= 1; i--) {
    for(int j = 0; j < cnt2[i].size(); j++){
      if(ki[cnt2[i][j]].size() == 1){
        continue;
      }
      int sum = 0,MX = 0;
      for(int k = 0; k < ki[cnt2[i][j]].size(); k++) {
        if(cnt[ki[cnt2[i][j]][k]]-1 == cnt[cnt2[i][j]]) {
          sum += res[ki[cnt2[i][j]][k]];
          MX = max(MX,res[ki[cnt2[i][j]][k]]);
        }
      }
      if(A[cnt2[i][j]] >= MX && A[cnt2[i][j]]*2 >= sum && A[cnt2[i][j]] <= sum){
        res[cnt2[i][j]] = A[cnt2[i][j]]*2-sum;
      }
      else {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  int sum = 0;
  for(int i = 0; i < ki[0].size(); i++) {
    sum += res[ki[0][i]];
  }
  if(ki[0].size() == 1) {
    if(sum != A[0]) {
      cout << "NO" << endl;
      return 0;
    }
  }
  else if(sum != A[0]*2) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 15984