akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;

int N, M;
int MapData[101][101], DpMoney[2][101];
bool Used[2][101];
const int INF = 100000000;


void solve() {
	int u, v;

	for (int i = 0; i < 2; ++i) {
		fill(DpMoney[i], DpMoney[i] + 101, INF);
		fill(Used[i], Used[i] + 101, false);
	}

	DpMoney[0][1] = 0;
	while (true) {
		u = -1;
		for (int i = 0; i < 2; ++i) {
			for (int j = 1; j <= N; ++j) {
				if (!Used[i][j] && (u == -1 || DpMoney[i][j] < DpMoney[u][v])) {
					u = i;
					v = j;
				}
			}
		}
		if (u == -1) {
			break;
		}
		Used[u][v] = true;
		//cout << "u(ticket):" << u << " v(dest):" << v << endl;

		for (int k = 1; k <= N; ++k) {
			DpMoney[u][k] = min(DpMoney[u][k], DpMoney[u][v] + MapData[v][k]);
			//cout << "u(ticket):" << u << "  k(now):" << k  << " money:" << DpMoney[u][k] << endl;
			if (u == 1) {
				continue;
			}
			for (int next = 1; next <= N; ++next) {
				if (MapData[v][k] == INF || MapData[k][next] == INF) {
					continue;
				}
				DpMoney[1][next] = min(DpMoney[1][next], DpMoney[0][v] + 0);
				//cout << "k(now):" << k << "  next:" << next << " money:" << DpMoney[1][next] << endl;
			}
		}
	}
}

int main() {
	int a, b, c;

	while (cin >> N >> M, N) {
		for (int i = 0; i < 101; ++i) {
			fill(MapData[i], MapData[i] + 101, INF);
		}
		for (int i = 0; i < M; ++i) {
			cin >> a >> b >> c;
			MapData[a][b] = c;
			MapData[b][a] = c;
		}
		solve();
		cout << min(DpMoney[0][N], DpMoney[1][N]) << endl;
	}

	return 0;
}



Measured memory_bytes: 3136
#include<cstdio>
#define MAX 10000
#define NIL -1

struct Node{int parent ,left,right;};

Node T[MAX];
int n,D[MAX],H[MAX];

void setDepth(int u,int d){//u=root;d=0;
    if(u==NIL)return ;
    D[u]=d;
    setDepth(T[u].left,d+1);
    setDepth(T[u].right,d+1);
}

int setHeight(int u){//u=root;
    int h1=0,h2=0;
    if(T[u].left!=NIL)
        h1=setHeight(T[u].left)+1;
    if(T[u].right!=NIL)
        h2=setHeight(T[u].right)+1;
    return H[u]=(h1>h2?h1:h2);
}

int getSibling(int u){
    if(T[u].parent==NIL)return NIL;
    if(T[T[u].parent].left!=u&&T[T[u].parent].left!=NIL)
        return T[T[u].parent].left;
    if(T[T[u].parent].right!=u&&T[T[u].parent].right!=NIL)
        return T[T[u].parent].right;
return NIL;
}

void print(int u){
    printf("node %d: ", u);
    printf("parent = %d, ",T[u].parent);
    printf("sibling = %d, ",getSibling(u));
    int deg=0;
    if(T[u].left!=NIL)deg++;
    if(T[u].right!=NIL)deg++;
    printf("degree = %d, ", deg);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);

    if(T[u].parent==NIL){
        printf("root\n");
    }else if(T[u].left==NIL&&T[u].right==NIL){
        printf("leaf\n");}
    else {
        printf("internal node\n");
    }
}


int main(){
    int  v,l,r,root=0;
    scanf("%d",&n);

    for(int i=0;i<n;i++)T[i].parent=NIL;

    for(int i=0;i<n;i++){
        scanf("%d %d %d",&v,&l,&r);
        T[v].left=l;
        T[v].right =r;
        if(l!=NIL)T[l].parent =v;
        if(r!=NIL)T[r].parent =v;
    }

    for(int i=0;i<n;i++)if(T[i].parent==NIL)root=i;

    setDepth(root,0);
    setHeight(root);

for(int i=0;i<n;i++)print(i);

return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main() {
    int n,a(0),b(0);
    cin >> n;
    vector<int> v(n);
    rep(i, n){
        cin >> v[i];
    }
    sort(v.rbegin(),v.rend());
    rep(i,n){
        if(i % 2 == 0) a+=v[i];
        else b+=v[i];
    } 
    cout << a-b << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
S = [0]
ans = 0
for i in range(len(A)):
  S.append(S[i] + A[i])
S.sort()
count = 1
for i in range(1, len(S)):
  if S[i-1] == S[i]:
    count += 1
  else:
    ans += count * (count-1) / 2
    count = 1
ans += count * (count-1) / 2
print(int(ans))

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

const string YES = "YES";
const string NO = "NO";

void solve(std::string S) {
    string keyence = "keyence";
    if (S == keyence) {
        cout << "YES" << endl;
        return;
    }
    for (ll i = 0; i < S.length(); i++) {
        for (ll j = i + 1; j < S.length(); j++) {
            string tmpS = S;
            tmpS.erase(i, j - i);
            if (tmpS == keyence) {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
    return;
}

int main() {
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

const int MAX_N=200002;
const int mod=1000000007;
ll fact[MAX_N+1];
ll inv[MAX_N+1],finv[MAX_N+1];

int inv_init(ll n,ll p){
    inv[1]=1;
    FOR(i,2,n+1) inv[i]=p-(p/i)*inv[p%i]%p;
    fact[0]=finv[0]=1;
    FOR(i,1,n+1){
        fact[i]=fact[i-1]*i%p;
        finv[i]=finv[i-1]*inv[i]%p;
    }
    return 0;
}
ll comb_mod(ll n,ll k,ll p){
    if(k<0||n<k) return 0;
    return finv[k]*finv[n-k]%p*fact[n]%p;
}
int n,m,k;
ll sum=0;
int main(){
    cin>>n>>m>>k;
    inv_init(n*m,mod);
    rep(i,n){
        sum+=(ll)i*(n-i)*m*m;
        sum%=mod;
    }
    rep(i,m){
        sum+=(ll)i*(m-i)*n*n;
        sum%=mod;
    }
    sum*=comb_mod(n*m-2,k-2,mod);
    cout<<sum%mod<<endl;
    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

signed main(){
    string s,t;
    cin>>s>>t;
    cout<<t+s<<endl;
    return 0;
}

Measured memory_bytes: 256
# def makelist(n, m):
#     return [[0 for i in range(m)] for j in range(n)]

yes = "Yes"
no = "No"

H, W = map(int, input().split())
alph = [0]*26

for i in range(H):
    for c in input():
        alph[ord(c) - 97] += 1

four = 0
two = 0
one = 0
ans = no
for e in alph:
    four += e // 4
    e %= 4
    two += e // 2
    one += e % 2

#print(four, two, one)
    
if (H, W) == (1, 1):
    ans = yes
else:
    if H % 2 == 0 and W % 2 == 0:
        if one > 0 or two > 0:
            ans = no
        else:
            ans = yes
    elif H % 2 == 0 and W % 2 == 1:
        if one == 0 and two <= H // 2:
            ans = yes
    elif H % 2 == 1 and W % 2 == 0:
        if one == 0 and two <= W // 2:
            ans = yes
    elif H % 2 == 1 and W % 2 == 1:
        if one == 1 and two <= H // 2 + W // 2:
            ans = yes

print(ans)


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int n, k, x, y; cin >> n >> k >> x >> y;
    if(n <= k){
        cout << n*x << endl;
    }else{
        cout << k*x + (n-k)*y << endl;
    }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 7632
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using llong = long long;
using P = pair<int, int>;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int main() {
   int n;
   cin >> n;
   vector<int> x(n), y(n);
   rep(i, n) { cin >> x[i] >> y[i]; }
   auto dist = [&](int i, int j) {
      double dx = x[i] - x[j];
      double dy = y[i] - y[j];
      return sqrt(dx * dx + dy * dy);
   };
   vector<int> p(n);
   rep(i, n) p[i] = i;
   double len = 0.0;
   int cnt = 0;
   do {
      rep(i, n - 1) { len += dist(p[i], p[i + 1]); }
      cnt++;
   } while (next_permutation(p.begin(), p.end()));
   double ans = len / cnt;
   printf("%0.6f\n", ans);
   return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

static const int maxn = 100000 + 10;

int n, par[maxn], dis[maxn], color[maxn];
vector<int> e[maxn], c[2];
bool v[maxn];

void dfs(int x, int p)
{
	par[x] = p;
	for (int i = 0; i < e[x].size(); i++)
		if (e[x][i] != p)
		{
			dis[e[x][i]] = dis[x] + 1;
			dfs(e[x][i], x);
		}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		e[a].push_back(b);
		e[b].push_back(a);
	}

	memset(par, 0, sizeof par);
	memset(dis, 0, sizeof dis);
	memset(color, 0, sizeof color);
	dfs(1, 0);
	memset(v, false, sizeof v);

	for (int i = n; i; i = par[i])
	{
		v[i] = true;
		if (dis[i] > dis[n] / 2)
			c[1].push_back(i);
		else
			c[0].push_back(i);
	}

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < c[i].size(); j++)
			for (int k = 0; k < e[c[i][j]].size(); k++)
				if (!v[e[c[i][j]][k]])
				{
					v[e[c[i][j]][k]] = true;
					c[i].push_back(e[c[i][j]][k]);
				}

	if (c[1].size() >= c[0].size())
		printf("Snuke\n");
	else
		printf("Fennec\n");

	return 0;
}

Measured memory_bytes: 13820
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int N, K, S;
  cin >> N >> K;
  S = 1;
  for (int i = 0; i < N; i++) { 
      if (S * 2 <= S + K) {
          S *= 2;
      } else {
          S += K;
      }
  } 
  cout << S << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

int main() { 
   int n; cin >> n;
   int cnt = 0;
   for(int i=7; i<=55555; i+=10){
      if(is_prime(i)){cnt++; cout << i << " ";}
      if(cnt >= n) break;
   }
   cout << ln;
}








Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c) { return b / c - (a - 1) / c; }

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}

int main() {
    long long x, m, ans;
    cin >> x;
    cout << "Christmas";
    for (int i = 0; i < 25 - x; i++) {
        cout << " " << "Eve";
    }
}

Measured memory_bytes: 256
/*
 * AIZU ONLINE JUDGE
 * PCK 2004 Cup Game
 * Time Limit : 1 sec, Memory Limit : 65536 KB
 * Cup Game
 *
 * 3 つのカップがふせて置かれています。カップの置かれている場所を、順にA,B,C と
 * 呼ぶことにします。最初はA に置かれているカップの中にボールが隠されているとし
 * ます。入れ替える２つのカップの位置を保存したデータがあります。このデータを読
 * み込んで、最終的にどの場所のカップにボールが隠されているかを出力して終了する
 * プログラムを作成してください。ただし、カップの位置を入れ替える際には、中に
 * 入っているボールも一緒に移動するものとします。
 * Input
 *
 * 入れ替える２つのカップの位置（1 回目:文字列）
 * 入れ替える２つのカップの位置（2 回目:文字列）
 * 入れ替える２つのカップの位置（3 回目:文字列）
 *
 * Output
 *
 * ボールが入っているカップの場所（文字列）
 *
 * Sample Input
 *
 * B,C
 * A,C
 * C,B
 * A,B
 * C,B
 *
 * Output for the Sample Input
 *
 * A
 *
 * Source: PC Koshien 2004 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2004
 * http://www.pref.fukushima.jp/pc-concours/
 */

#include <stdio.h>

int main(int argc, char* argv[])
{
	char cupl, cupr;
	int cups[256] = {};
	char printcnt = 'A';

	cups[(int)printcnt] = 1;
	while (scanf("%c,%c\n", &cupl, &cupr) == 2) {
		/* printf("debug: %c, %c, %d, %d\n", cupl, cupr, cups[(int)cupl], cups[(int)cupr]); */
		if (cups[(int)cupl] != cups[(int)cupr]) {
			cups[(int)cupl] = 1 - cups[(int)cupl];
			cups[(int)cupr] = 1 - cups[(int)cupr];
		}
	}
	while (cups[(int)printcnt]==0) printcnt++;
	printf("%c\n", printcnt);
	return 0;
}

Measured memory_bytes: 548
#include <stdio.h>

void era_name_translation(int x, int y, int z)
{
    int n;
    n = x * 10000 + y * 100 + z; 
    if (n <= 18680907) {
        printf("pre-meiji\n");
    }
    else if ((18680907 <= n) && (n <= 19120729)) {
        printf("meiji %d %d %d\n", x - 1867, y, z);
    } 
    else if (19120729 < n && n <= 19261224) {
        printf("taisho %d %d %d\n", x - 1911, y, z);
    }  
    else if (19261224 < n && n <= 19890107) {
        printf("showa %d %d %d\n", x -1925, y, z);
    }  
    else if (19890107 < n ) {
        printf("heisei %d %d %d\n", x - 1988, y, z);
    }  
}

int main(void)
{
    int a, b, c;
    while (scanf("%d %d %d", &a, &b, &c) != EOF) {
    era_name_translation(a, b, c);
    }
    return 0;
}

Measured memory_bytes: 1036
a, b, c = map(int, input().split())
ans = 0
if a==b==c and a%2==0 and b%2==0 and c%2==0:
    print(-1)
else:
    while a%2==0 and b%2==0 and c%2==0:
        aa = b//2+c//2
        bb = c//2+a//2
        cc = a//2+b//2
        a = aa
        b = bb
        c = cc
        ans += 1
    print(ans)

Measured memory_bytes: 3064
//#define LOCAL
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(ar) memset(ar,0,sizeof(ar))
#define go(i,a,b) for(int i=a;i<=b;++i)
#define f(i,n) for(int i=0;i<n;++i)


int main(){
#ifdef LOCAL
	freopen("data.in","r",stdin);
#endif
	int sum = 1110;
	int a;
	scanf("%d",&a);
	printf("%d\n",sum-a);
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a[4][3][10]={0};
    int i,j,k,n,b,f,r,v;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d %d %d", &b, &f, &r, &v);
        a[b-1][f-1][r-1] += v;
    }
    for(i = 0; i < 4;i++){
        for(j = 0; j < 3; j++){
            for(k = 0; k < 10; k++){
                printf(" %d", a[i][j][k]);
                if(k == 9){
                    printf("\n");
                }
            }
        }
    if(i < 3){
        printf("####################\n");
    }
    }
    return 0;
}


Measured memory_bytes: 2100
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
	// your code goes here
	long int t=1;
// 	cin>>t;
	while(t--)
	{
	    int x;
	    cin>>x;
	    if(x==0)
	    cout<<"1";
	    else
	    cout<<"0";
	  }
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  
  if(a==0){
    if(b>=k){
      cout << 0 << " " << b - k << endl;
      return 0;
    }
    else{
      cout << 0 << " " << 0 << endl;
      return 0;
    }
  }
  if(a>0){
    if(a<=k){
      if(b>=k-a){
        cout << 0 << " " << b - k + a << endl;
        return 0;
      }
      else{
        cout << 0 << " " << 0 << endl;
        return 0;
      }
    }
    else{
      cout << a - k << " " << b << endl;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <map>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cstdlib>
using namespace std;

int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	if (abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d))
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_members(self, x):  # x が属する集合の要素を返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

    def __str__(self):  # print 表示用
        return '\n'.join('{}: {}'.format(r, self.group_members(r)) for r in self.roots())


N, M = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x-1, y-1)

ans = 0
for i in range(N):
    ans += uf.is_same(i, p[i]-1)

print(ans)


Measured memory_bytes: 13940
n,x = map(int, input().split( ))
a = list(map(int, input().split( )))

a.sort()
tmp = a[0]
cnt = 0
for i in range(1,n):
    #print(cnt,tmp)
    if tmp<=x:
        cnt += 1
        tmp += a[i]
    else:
        break
if tmp==x:
    cnt +=1
print(cnt)

Measured memory_bytes: 38384
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <cmath>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
#define LEN 100005

struct Case{
    char name[100];
    int time;
};

Case Q[LEN];
int head, tail;

void enqueue(const Case& x){
    Q[tail] = x;
    tail = (tail + 1) % LEN;
}

Case dequeue(){
    Case x = Q[head];
    head = (head + 1) % LEN;
    return x;
}

int main(){
    int n, q;
    cin >> n >> q;
    rep(i,n) cin >> Q[i+1].name >> Q[i+1].time;
    
    head = 1;
    tail = n + 1;
    int lap = 0, c;
    while(head != tail){
        Case u = dequeue();
        c = min(u.time, q);
        u.time -= c;
        lap += c;
        if (u.time > 0) enqueue(u);
        else cout << u.name << " " << lap << endl;
    }
}



Measured memory_bytes: 13260
#include <bits/stdc++.h>

using namespace std;

int n, l, q;
long long x[111111];
int f[111111][22];

int main(){
//	freopen("input.inp", "r", stdin);
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i) scanf("%lld",&x[i]);
	scanf("%d%d",&l,&q);
	for(int i = 1; i <= n; ++i){
		int ll = i + 1, rr = n;
		while (ll <= rr){
			int md = (ll + rr) >> 1;
			if (x[md] - x[i] <= l) ll = md + 1;
			else rr = md - 1;
		}
		f[i][0] = rr;
	}
	for(int j = 1; j < 17; ++j){
		for(int i = 1; i <= n; ++i){
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	while (q--){
		int a, b;
		scanf("%d%d",&a,&b);
		if (a > b) swap(a, b);
		int an = 0;
		for(int i = 16; i >= 0; --i){
			if (f[a][i] < b) a = f[a][i], an += (1 << i);
		}
		printf("%d\n",an + 1);
	}
	return 0;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
#define uniq(x)  x.erase(unique(x.begin(),x.end()), x.end()) //Unique value find from vector
#define upper(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Upper value search;
#define lower(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Lower value search;
#define max3(a,b,c) max(max(a,b),c)//maximum value find three value;
#define min3(a,b,c) min(min(a,b),c)//minimum value find three value;
#define rep(i,intial,n) for(int i=intial; i<(n) ; i++)
#define REP(i,intial,n) for(int i=intial; i<=(n) ; i++)
#define PI acos(-1.0)//PI Calculation
#define LL long long
#define MP make_pair
#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define MX 1000005
#define MOD 1000000007
template<typename T> T POW(T b,T p)          //Pow calculation
{
    T r=1;
    while(p)
    {
        if(p&1)r=(r*b);
        b=(b*b);
        p>>=1;
    }
    return r;
}

LL big_mod(LL n, LL p)
{
    if(p==0) return 1;
    if(!(p&1))
    {
        LL r = big_mod(n,p/2) % MOD;
        return ( (r%MOD) * (r%MOD) ) % MOD;
    }
    else return ( ( n%MOD) * (big_mod(n,p-1) %MOD)) % MOD;
}
long long gcd(long long a, long long b) {
  while (b != 0) {
    long long t = a % b;
    a = b;
    b = t;
  }
  return a;
}

//||--------------------------->||Main_Code_Start_From_Here||<---------------------------------||
int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
  string s,ss;
  while(cin>>s)
  {
      ss="ABC";
      cout<<ss+s<<endl;
  }

}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <bitset>
#define ri register
#define inf 0x7fffffff
#define E (1)
#define mk make_pair
#define int long long
//#define double long double
using namespace std;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch-'0'), ch=getchar();
    return s*w;
}
void print(int x) { if(x<0) x=-x, putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); }
signed main()
{
    int x=read();
    printf("%lld\n",x+x*x+x*x*x);
    return 0;
}

Measured memory_bytes: 3768
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {
	final int _intMax = Integer.MAX_VALUE; // =2147483647>10^9
	final int _intMin = Integer.MIN_VALUE;
	final long _longMax = Long.MAX_VALUE; // =9223372036854775807L>10^18
	final long _longMin = Long.MIN_VALUE;
	static boolean bElapsed = false;

	void solve() {
		Counter c1 = new Counter();
		Counter c2 = new Counter();
		int n = readNum();
		for (int i=0; i<n; i++) {
			String line = readLine();
			c1.add(line);
		}
		int m = readNum();
		for (int i=0; i<m; i++) {
			String line = readLine();
			c2.add(line);
		}
		int ans = 0;
		for (Object k : c1.map.keySet()) {
			int v1 = c1.get(k);
			int v2 = c2.get(k);
			ans = max(ans, v1 - v2);
		}
		pln(ans);
	}

	class Counter {
		Map<Object, Integer> map = new HashMap<>();

		void add(Object o) {
			Integer v = map.get(o);
			if (v == null) {
				map.put(o, 1);
			} else {
				map.put(o, v + 1);
			}
		}

		int get(Object o) {
			Integer v = map.get(o);
			if (v == null) {
				return 0;
			} else {
				return v;
			}
		}
	}
	
	int max(int a, int b) {
		return (a > b) ? a : b;
	}

	int pint(String s) {
		return Integer.parseInt(s);
	}

	long plong(String s) {
		return Long.parseLong(s);
	}

	String readLine() {
		try {
			return _in.readLine();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	int readNum() {
		String line = readLine();
		return pint(line);
	}

	String[] readFlds() {
		String line = readLine();
		return line.split(" ");
	}

	int[] readNums() {
		String[] flds = readFlds();
		int[] nums = new int[flds.length];
		for (int i = 0; i < flds.length; i++) {
			nums[i] = pint(flds[i]);
		}
		return nums;
	}

	void p(char c) {
		_out.print(c);
	}

	void pln(char c) {
		_out.println(c);
	}

	void p(double d) {
		_out.print(d);
	}

	void pln(double d) {
		_out.println(d);
	}

	void p(long l) {
		_out.print(l);
	}

	void pln(long l) {
		_out.println(l);
	}

	void p(String s) {
		_out.print(s);
	}

	void pln(String s) {
		_out.println(s);
	}

	static BufferedReader _in;
	static PrintWriter _out;

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		_in = new BufferedReader(new InputStreamReader(System.in));
		_out = new PrintWriter(System.out);
		new Main().solve();
		_out.flush();
		long end = System.currentTimeMillis();
		if (bElapsed) {
			System.err.println((end - start) + "ms");
		}
	}
}


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

int main() {

  bool flg = true;
  
  while (flg) {

    int a, b;
    string op;
    cin >> a >> op >> b;

    if (op == "?"){
      flg = false;
      break;
    } else {
      if (op == "+") {
        cout << a + b << endl;
      } else if (op == "-") {
        cout << a - b << endl;
      } else if (op == "*") {
        cout << a * b << endl;
      } else {
        cout << a / b << endl;
      }
    }

  }

  return 0;

}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    if(a==b)cout<<'='<<endl;
    else cout<<(a<b?'<':'>')<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1000000007;
int main(){
  int N;
  long long K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  long long ans = 0;
  for (int i = 0; i < N; i++){
    for (int j = i + 1; j < N; j++){
      if (A[i] < A[j]){
        ans += K * (K - 1) / 2 % MOD;
        ans %= MOD;
      }
      if (A[i] > A[j]){
        ans += K * (K + 1) / 2 % MOD;
        ans %= MOD;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<bitset>
    #include<vector>
    #include<deque>
    #include<list>
    #include<queue>
    #include<map>
    #include<set>
    #include<stack>
    #include<cmath>
    #include<iomanip>
    #include <functional>
    using namespace std;
    typedef long long ll;
    const int mod = 1000000007;
    const int INF = 1 << 28;
    const double EPS = 1e-10;
    //cout << fixed << std::setprecision(9)
    //memset(a, 0, sizeof(a));
    //--------------------------
     
    int main()
    {
    	int a[3];
    	cin >> a[0] >> a[1] >> a[2];
    	sort(a, a + 3);
    	cout << a[0] * a[1] / 2 << endl;
     
    	return 0;
    }

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define N 20

int main()
{
  char str[N];
  scanf("%s",str);
  int n=strlen(str);
  int i;
  for(i=0;i<n/2;i++){
    if(i!=n-1-i){
      char ch=str[i];
      str[i]=str[n-1-i];
      str[n-1-i]=ch;
    }
  }
  printf("%s\n",str);
  
  return 0;
}

Measured memory_bytes: 524
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;
typedef tuple<int, int, int> T;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void 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;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
ll digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
ll countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}
int to_num(char c) {
	if (c >= '0' && c <= '9')return (c - '0');
	else return -1;
}

int main() {
	string o, e;
	cin >> o >> e;
	string ans = "";
	REP(i, e.size()) {
		ans = ans + o[i] + e[i];
	}
	if (o.size() > e.size())ans = ans + o[o.size() - 1];

	cout << ans << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;
/**
 *2018-04-08
 * https://beta.atcoder.jp/contests/abc081/tasks/abc081_a
**/
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int count = 0;

        for( int i=0; i<s.length();i++){
            if(s.charAt(i)=='1'){
                count ++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 21844
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

#define PB push_back
#define MP make_pair

#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
#define R1(a) do{scanf("%d", &(a));}while(0)
#define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0)
#define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0)
#define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0)
#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
#define INF 1000000007

int m, n, tot;
vector<int> a;
double min;

int main ()
{
  R2(n, m);
  FOR(i, 0, n) SV(a);
  tot = 0;
  FOR(i, 0, n) tot += a[i];
  sort(a.rbegin(), a.rend());
  FOR(i, 0, m)
  {
    double ratio = 1.0 * a[i] / tot;
    if (ratio < 1.0 / (4 * m))
    {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=(1e5)+50;
int N,num=0,pos[maxn],ans[maxn];
char S[maxn];
int main(){
	scanf("%s",S+1);
	N=strlen(S+1);
	for(int i=1;i<=N;i++){
		if(S[i]=='R'&&S[i+1]=='L')pos[++num]=i;
	}
	for(int i=1;i<=num;i++){
		int a=pos[i],b=a+1,c=1,d=1;
		while(S[a-1]=='R')a--,c++;
		while(S[b+1]=='L')b++,d++;
		ans[pos[i]]+=(c+1)/2; c-=(c+1)/2;
		ans[pos[i]+1]+=c;
		ans[pos[i]+1]+=(d+1)/2; d-=(d+1)/2;
		ans[pos[i]]+=d;
	}
	for(int i=1;i<=N;i++)printf("%d ",ans[i]);
	return 0;
}

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

ll min(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    else return b;
}

bool seen[100010]={false};

void g(ll j,vector<vector<ll>> &a){
    seen[j]=true;
    for(ll k=0;k<a[j].size();k++){
        if(seen[a[j][k]]==false){
            g(a[j][k],a);
        }
    }
}

int main() {
    ll l,r;cin>>l>>r;
    if(r-l>=2019){
        cout<<0<<endl;
    }else{
        ll c=2020;
        ll k;
        for(ll i=l;i<=r-1;i++){
            for(ll j=i+1;j<=r;j++){
                k=((i%2019)*(j%2019))%2019;
                if(k<c)c=k;
            }
        }
        cout<<c<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define trep(i, n) for(int i = 0; i <= n; i++)

int main() {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    trep(i, a) {
        trep(j, b) {
            trep(k, c) {
                if(i * 500 + j * 100 + k * 50 == x) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    abc086c()
}

private data class Txy(val time: Int, val x: Int, val y: Int)

fun abc086c() {
    val n = readLine()!!.toInt()
    val txy = listOf(Txy(0, 0, 0)) + (1..n).map { readLine()!!.split(" ").map { it.toInt() } }
        .map { Txy(it[0], it[1], it[2]) }

    val answer = (0 until n).all { i ->
        val curr = txy[i]
        val next = txy[i + 1]

        val move = Math.abs(next.x - curr.x) + Math.abs(next.y - curr.y)
        val moveCap = Math.abs(next.time - curr.time)
        val remainMove = moveCap - move
        remainMove >= 0 && remainMove % 2 == 0
    }.let { if (it) "Yes" else "No" }

    println(answer)
}


Measured memory_bytes: 60172
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int a, b, c;
	while(cin >> a >> b >> c) {
		a -= c;
		cout << a / (b + c) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
const ll MOD = 1e9 + 7;

struct Info{ll v; ll c; ll t;};
struct DP{
	ll v; ll c; ll t;
	bool operator<(const DP& o) const{
		return t > o.t;
	}
};

int mainsolve(){

	ll n,m,s;
	cin >> n >> m >> s;
	vector<ll> a(m), b(m);
	vector<vector<Info>> to(n);
	rep(i,m){
		ll u,v;
		cin >> u >> v >> a[i] >> b[i];
		--u; --v;
		to[u].push_back(Info{v,a[i],b[i]});
		to[v].push_back(Info{u,a[i],b[i]});
	}
	vector<ll> c(n), d(n);
	rep(i,n) cin >> c[i] >> d[i];

	ll INF = 1e18;
	ll maxc = n*50; // 銀貨の枚数はこれだけあれば十分
	vector<vector<ll>> dp(n,vector<ll>(maxc,INF)); // dp[v][c]: 銀貨c枚持ってvにいる状態にするためにかかる時間 

	priority_queue<DP> q;
	q.push(DP{0,min(maxc-1,s),0});

	while(!q.empty()){
		DP now = q.top(); q.pop();
		if(now.c >= 0 && now.t >= 0 && now.t < dp[now.v][min(maxc-1,now.c)] ){
			dp[now.v][min(maxc-1,now.c)] = now.t;

			for(Info next : to[now.v]){
				q.emplace(DP{next.v,now.c - next.c, now.t + next.t}); // 移動
			}
			q.emplace(DP{now.v,now.c + c[now.v], now.t + d[now.v]}); // 換金
		}
	}
	
	rep(i,n){
		if(i==0) continue;
		ll res = INF;
		rep(j,maxc) res = min(res, dp[i][j]);
		cout << res << endl;
	}
	
	return 0;
}

int main(){

	return mainsolve();
}


Measured memory_bytes: 16416
package main

import (
	"fmt"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	fmt.Println(CombCount(n,2) +CombCount(m,2))
}

func CombCount(left int, right int) int {
	rightFac := Factorial(right, right)
	if rightFac <= 0 {
		return 0
	}
	return Factorial(left, right) / rightFac
}

func Factorial(n int, times int) (res int) {
	facts := make([]int, n+1)
	if facts[n] != 0 {
		res = facts[n]
		return res
	}

	if n > 0 && times > 0 {
		res = n * Factorial(n-1, times-1)
		return res
	}

	return 1
}


Measured memory_bytes: 512
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << endl;
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << "";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, m) revi(i, m, 0)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define allr(n) (n.rbegin(), n.rend())
#define sp(n) cout << fixed << setprecision(n)
#define INF pow(10, 9)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

int main() {
  int H, W;
  ci(H, W);
  ve<ve<char>> s(H, ve<char>(W));
  int c = 0;
  rep(i, H){
    rep(j, W){
      ci(s.at(i).at(j));
      if(s.at(i).at(j) == '#'){
        c++;
      }
    }
  }
  ve<ve<int>> n(H, ve<int>(W, INF));
  queue<pair<int, int>> Q;
  ve<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
  n.at(0).at(0) = 1;
  Q.push(mp(0, 0));
  wh(sz(Q)){
    int x = Q.front().ft, y = Q.front().sc;
    Q.pop();
    rep(i, 4){
      int ax = x + dx.at(i), ay = y + dy.at(i);
      if(ax < 0 || H <= ax || ay < 0 || W <= ay){
        con;
      } 
      if(s.at(ax).at(ay) != '#' && n.at(ax).at(ay) == INF){
        Q.push(mp(ax, ay));
        n.at(ax).at(ay) = n.at(x).at(y) + 1;
      }
    }
  }
  if(n.at(H - 1).at(W - 1) == INF){
    cout << -1 << endl;
  }
  else{
    cout << H * W - n.at(H - 1).at(W - 1) - c << endl;
  }
}


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

#define int long long
#define MAX 200

int l, k, temp[MAX];

int hoge(int c, int h){
  int ans = 0;
  if(h >= l) return 0;
  if(temp[h] >= 0) return temp[h];
  //if(l == h - 1) return 1;
  ans += hoge(c+1,h+k+1);
  ans += hoge(c+1,h+2);

  if(h+k <= l) ans++;
  if(h+1 <= l) ans++;

  temp[h] = ans;
  return ans;
}

signed main(){

  cin>>l>>k;

  for(int i = 0; i < MAX; i++){
    temp[i] = -1;
  }

  cout<<hoge(0,0)<<endl;
  return 0;
}



Measured memory_bytes: 3116
#include<bits/stdc++.h>

using namespace std;

int main(){
	string O, E; cin >> O >> E;
	for(int i = 0; i < min(O.size(), E.size());++i){
		cout << O[i] << E[i];
	}
	if(O.size() < E.size()){
		cout << E[E.size()-1];
	}else if(O.size() > E.size()){
		cout << O[O.size()-1];
	}
	cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int now = 0;
    vector<int >v;
    for(int i = 1; now < N; i++) {
        now += i;
        v.push_back(i);
    }
    for(int i = 0; i < v.size(); i++) {
        if(now - v[i] == N) {
            now -= v[i];
            v.erase(v.begin() + i);
        }
    }
    for(int i = 0; i < v.size(); i++) cout << v[i] << endl;
    return 0;
}


Measured memory_bytes: 384
//085 B - Kagami Mochi
#include <bits/stdc++.h>
#define rep(i ,n) for(int i=0;i<(int)(n);++i)
using namespace std;
typedef long long int int64;
typedef unsigned long long uint64;

int main(){
    int n; cin >> n;
    vector<int> d(n,0);
    rep(i ,n) cin >>d[i];
    sort(d.begin(),d.end());
    int ans=0;d[n]=-1;
    rep(i ,n){
        if(d[i]!=d[i+1] && d[i+1]!=-1) {++ans;}
        else { ++ans;
            while(1){
                if(d[i]!=d[i+1]) break;
                else ++i;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
        
int main()
{
	string s;

	cin >> s;

	int n = s.size();

	if (n == 1)
	{
		cout << 1;
	
		return 0;
	}

	if (n % 2 == 0)
	{
		int a = n / 2 - 1;
		int b = n / 2;
                
		while (-1 < a && b < n && s[a] == s[b])
			a--, b++;

		cout << b;
	}	
	else
	{
		int a = n / 2;
		int b = n / 2 + 1;

		if (s[a] != s[b])
		{
			cout << a + 1;
			return 0;
		}
		
		a--;
		
		while (-1 < a && b < n && s[a] == s[b])
			a--, b++;

		cout << b;
	}
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;


int main() {
  int a,b,c;
  cin >> a>> b>> c;
  if((a-b)>c){
    cout << 0 << endl;
    return 0;
  }
  cout << c-(a-b) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Date {
public:
    int y, m, d;
    Date(int y, int m, int d) : y(y), m(m), d(d) {};
    bool operator<(const Date& date) const {
        return y < date.y
                || (y == date.y && m < date.m)
                || (y == date.y && m == date.m && d < date.d);
    }
};

int main() {
    Date meiji(1868,9,8), taisho(1912,7,30), showa(1926,12,25), heisei(1989,1,8);
    int y, m, d;
    while (cin >> y >> m >> d) {
        Date date(y, m, d);
        if (date < meiji) {
            cout << "pre-meiji" << endl;
        } else if (date < taisho) {
            cout << "meiji " << y - meiji.y + 1 << " " << m << " " << d << endl;
        } else if (date < showa) {
            cout << "taisho " << y - taisho.y + 1 << " " << m << " " << d <<endl;
        } else if (date < heisei) {
            cout << "showa " << y - showa.y + 1 << " " << m << " " << d <<endl;
        } else {
            cout << "heisei " << y - heisei.y + 1 << " " << m << " " << d <<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1164
#include <iostream>
using namespace std;

#define rep(i,n) for(int i=0;i < (int)n;i++)


int main(){
  int N,A,B,C,X;
  int Y[110];

  while(1){
    cin >> N >> A >> B >> C >> X;
    if(N == 0)break;
    rep(i,N){
      cin >> Y[i];
    }
    int i=0,ans=0;
    while(ans != 10001){
      if(Y[i] == X){
	i++;
      }
      if(i == N) break;
      X = (A*X+B) % C;
      ans++;
    }
    if(i == N) cout << ans <<endl;
    else cout << "-1\n";
  }
  return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <bitset>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(void){
    string s;
    cin >> s;
    ll a = 0, b = 0, c = 0;
    for(ll i = 0; i < s.length(); i++){
        if(s[i]=='a') a++;
        if(s[i]=='b') b++;
        if(s[i]=='c') c++;
    }
    //cout << a << " " << b << " " << c << endl;
    ll MAX = max(a, b); MAX = max(MAX, c);
    ll MIN = min(a, b); MIN = min(MIN, c);
    if(MAX-MIN<=1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 512
//Zory-2019
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define Debug printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define debug(x) cerr<<#x<<'='<<x<<endl
#define mem(x) memset(x,0,sizeof x)
namespace mine
{
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=80+10;

    bool f[N][N][N*N*4];int M=N*N*2;int a[N][N],b[N][N];
    void main()
    {
        int n=qread(),m=qread();fo(i,1,n) fo(j,1,m) a[i][j]=qread();fo(i,1,n) fo(j,1,m) b[i][j]=qread();
        f[1][1][M+a[1][1]-b[1][1]]=f[1][1][M+b[1][1]-a[1][1]]=1;
        fo(i,1,n) fo(j,1,m) fo(sum,-(i+j)*N,(i+j)*N) if(f[i][j][M+sum])
        {
            int aa,bb;
            aa=a[i+1][j],bb=b[i+1][j];f[i+1][j][M+sum+aa-bb]|=f[i][j][M+sum];f[i+1][j][M+sum+bb-aa]|=f[i][j][M+sum];
            aa=a[i][j+1],bb=b[i][j+1];f[i][j+1][M+sum+aa-bb]|=f[i][j][M+sum];f[i][j+1][M+sum+bb-aa]|=f[i][j][M+sum];
            // if(i==1 and j==2) write2(sum);
        }
        int ans=INF;fo(sum,-n*2*N,n*2*N) if(f[n][m][M+sum]) chmin(ans, abs(sum) );write(ans);
    }
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 231680