akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main()
{
    int h,w,i,j;


    for(;;)
    {
        scanf("%d %d",&h,&w);
        if(h==0 && w==0)
            break;
        for(i=0; i<h; i++)
        {
            if(i%2==0)
            {
                for(j=1; j<=w; j++)
                {
                    if(j%2==0)
                        printf(".");
                    else
                        printf("#");
                }
            }
            else
            {
                for(j=0; j<w; j++)
                {
                    if(j%2==0)
                        printf(".");
                    else
                        printf("#");
                }
            }
  printf("\n");
        }
  printf("\n");

    }
}





Measured memory_bytes: 2140
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] coin = { 500, 100, 50, 10, 5, 1 };
    while (true) {
      int price = sc.nextInt();
      if (price == 0) {
        return;
      }
      int change = 1000 - price;
      int ans = 0;
      for (int i = 0; i < 6; i++) {
        if (change <= 0) {
          break;
        }
        int num = change / coin[i];
        ans += num;
        change = change - num * coin[i];
      }
      System.out.println(ans);
    }
  }
}


Measured memory_bytes: 25836
#include <stdio.h>
#include <string.h>

int main(void)
{
	char O[60] = {0}, E[60] = {0};
	int i;

	scanf("%s", O);
	scanf("%s", E);

	if (strlen(O) == strlen(E))
	{
		for (i = 0; i < strlen(O); i++)
			printf("%c%c", O[i], E[i]);
	}
	else
	{
		for (i = 0; i < strlen(O) - 1;i++)
			printf("%c%c", O[i], E[i]);
		printf("%c", O[i]);
	}

	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[105];
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	cout<<a[n]-a[1];
	return 0;
}


Measured memory_bytes: 256
import java.math.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Main {
  static BigInteger MOD = new BigInteger("1000000007");

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int s = sc.nextInt();
    System.out.println(culc(s));
  }

  static Map<Integer, BigInteger> MAP = new HashMap<>();
  static BigInteger culc(int n) {
    return MAP.computeIfAbsent(n, key -> {
      if (n <= 2) {
        return BigInteger.ZERO;
      }
      BigInteger result = BigInteger.ONE;
      for (int i = 3, len = n - 3; i <= len; i++) {
        result = result.add(culc(n - i)).remainder(MOD);
      }
      return result;
    });
  }
}


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

int main(){
	long L,R;
	cin>>L>>R;
	int ans=2018;
	if(R-L+1 > 2019)ans = 0;
	else{
		for(long i=L;i<R;++i){
			for(long j=i+1;j<=R;++j){
				if(ans>(i*j)%2019)ans = (i*j)%2019;
			}
		}
	}
	cout<<ans<<endl;
}


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

using namespace std;

using ll = long long;

const int N = (int)2e5 + 5, mod = (int)1e9 + 7, offset = (int)2e3 + 5;
int n, a[N], b[N], dp[offset << 1][offset << 1], fact[offset << 2], invFact[offset << 2];

int add(int _a, int _b) {
    _a += _b;
    if (_a >= mod) _a -= mod;
    return _a;
}
int sub(int _a, int _b) { return add(_a, mod - _b); }
int mul(int _a, int _b) { return (int)( (ll)_a * _b % mod); }

int binPow(int _a, int _m) {
    int ret = 1;
    for (; _m; _m >>= 1, _a = mul(_a, _a) ) if (_m & 1) ret = mul(ret, _a);
    return ret;
}

int C(int _k, int _n) { return mul(fact[_n], mul(invFact[_k], invFact[_n - _k]) ); }

int main() {

    fact[0] = 1; for (int i = 1; i < (offset << 2); ++i) fact[i] = mul(fact[i - 1], i);
    invFact[(offset << 2) - 1] = binPow(fact[(offset << 2) - 1], mod - 2);
    for (int i = (offset << 2) - 2; i >= 0; --i) invFact[i] = mul(invFact[i + 1], i + 1);

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", a + i, b + i);
        dp[ offset - a[i] ][ offset - b[i] ] = add(dp[ offset - a[i] ][ offset - b[i] ], 1);
    }

    for (int i = 0; i < (offset << 1); ++i) {
        for (int j = 0; j < (offset << 1); ++j) {
            if (j) dp[i][j] = add(dp[i][j], dp[i][j - 1]);
            if (i) dp[i][j] = add(dp[i][j], dp[i - 1][j]);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = add(ans, dp[ offset + a[i] ][ offset + b[i] ]);
        ans = sub(ans, C(a[i] << 1, (a[i] + b[i]) << 1) );
    }
    ans = mul(ans, binPow(2, mod - 2) );

    printf("%d\n", ans);

    return 0;
}


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

using namespace std;

const int N = 1e2+5;

int n , k;
bool yes[N];

int main(){
    scanf("%d%d" , &n , &k);
    for(int i = 1; i <= k; i++){
        int d;
        scanf("%d" , &d);
        for(int j = 1; j <= d; j++){
            int x;
            scanf("%d" , &x);
            yes[x] = 1;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        cnt += !yes[i];
    }
    printf("%d\n" , cnt);
}


Measured memory_bytes: 3824
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#ifdef _debug
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#define dout(i) //
#endif
#define sp(i) (i>n ? i-n : i == 0 ? n : i)
using ll = long long;
using ull = unsigned long long;
using ul = unsigned;
const int maxn = 200001;
const int maxm = maxn * 100;
int a[maxn], b[maxn], n;
int togo[maxm], tlen;
bool ok(int p){
	p = sp(p);
	return b[p] > max(b[p-1] + b[p+1], a[p]);
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;++i)cin >> a[i];
	for(int i = 1;i <= n;++i)cin >> b[i];
	b[n+1] = b[1];b[0] = b[n];
	ll res = 0;
	for(int i = 1;i <= n;++i)if(ok(i))togo[tlen++] = i;
	for(int j = 0;j < tlen;++j){
		int &i = togo[j];
		int st = (b[i] - a[i]) / (b[i-1]+b[i+1]);
		res += st;
		b[i] -= st * (b[i-1] + b[i+1]);
		b[1] = b[n+1] = min(b[1], b[n+1]);
		b[0] = b[n] = min(b[0], b[n]);
		if(ok(i+1))togo[tlen++] = sp(i+1);
		if(ok(i-1))togo[tlen++] = sp(i-1);
	}
	for(int i = 1;i <= n;++i){
		if(a[i] != b[i])res = -1;
	}
	cout << res << '\n';
}

Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int dp[(1<<15)+5],n,m,s[20],d[120];
int main(){
	while(1){
		cin >> n >> m; if(!n) return 0;
		int all = 0,ret = 0;
		for(int i=0;i<n;i++){
			cin >> s[i]; all += s[i];
		}
		for(int i=0;i<m;i++){
			cin >> d[i]; if(d[i] > all) ret += d[i]-all;
		}
		sort(d,d+m);
		for(int i=0;i<(1<<n);i++) dp[i] = INF;
		dp[0] = 0;
		for(int i=0;i<(1<<n);i++){
			int sum = 0;
			for(int j=0;j<n;j++){
				if(((i>>j)&1)) sum += s[j];
			}
			for(int j=0;j<n;j++){
				if(((i>>j)&1)) continue;
				int x = upper_bound(d,d+m,sum)-d;
				int y = upper_bound(d,d+m,sum+s[j])-d;
				int z = dp[i];
				for(int k=x;k<y;k++){
					z += min(d[k]-sum,sum+s[j]-d[k]);
				}
				dp[i+(1<<j)] = min(dp[i+(1<<j)],z);
			}
		}
		cout << dp[(1<<n)-1] + ret << endl;
	}
}

Measured memory_bytes: 3240
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=600+10;
struct point{int x,y;}li[maxn*maxn];
int tmp;
int co[2][maxn][maxn],n,d1,d2;
void dfs(int x,int y,int l){
	REP(i,1,tmp){
		int u=x+li[i].x,v=y+li[i].y;
		if(u>=2*n || v>=2*n || u<0 || v<0) continue;
		if(co[l][u][v]==-1) co[l][u][v]=co[l][x][y]^1,dfs(u,v,l);
	}
}
int main(){
	n=read(),d1=read(),d2=read();
	for(int i=0;i*i<=d1;++i){
		int j=sqrt(d1-i*i);
		while(j*j+i*i>d1) --j;
		while(j*j+i*i<d1) ++j;
		if(i*i+j*j!=d1) continue;
		li[++tmp]=(point){i,j};
		li[++tmp]=(point){-i,j};
		li[++tmp]=(point){i,-j};
		li[++tmp]=(point){-i,-j};
	}
	REP(l,0,1) REP(i,0,2*n-1) REP(j,0,2*n-1) co[l][i][j]=-1;
	REP(i,1,2*n-1) REP(j,0,2*n-1) if(co[0][i][j]==-1) co[0][i][j]=0,dfs(i,j,0);
	tmp=0;
	for(int i=0;i*i<=d2;++i){
		int j=sqrt(d2-i*i);
		while(j*j+i*i>d2) --j;
		while(j*j+i*i<d2) ++j;
		if(i*i+j*j!=d2) continue;
		li[++tmp]=(point){i,j};
		li[++tmp]=(point){-i,j};
		li[++tmp]=(point){i,-j};
		li[++tmp]=(point){-i,-j};
	}
	REP(i,0,2*n-1) REP(j,0,2*n-1) if(co[1][i][j]==-1) co[1][i][j]=0,dfs(i,j,1);
	REP(u,0,1) REP(v,0,1){
		int sum=0;
		REP(i,0,2*n-1) REP(j,0,2*n-1) if(co[0][i][j]==u && co[1][i][j]==v) ++sum;
		if(sum>=n*n){
			sum=n*n;
			REP(i,0,2*n-1) REP(j,0,2*n-1) if(co[0][i][j]==u && co[1][i][j]==v){
				printf("%d %d\n",i,j);
				--sum;
				if(!sum) return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 33024
from collections import deque

n, q = list(map(int, input().split(' ')))
queues = [deque([]) for i in range(n)]

for i in range(q):
    op = list(map(int, input().split(' ')))
    if op[0] == 0:
        queues[op[1]].append(op[2])
    elif op[0] == 1:
        if len(queues[op[1]]) != 0:
            print(queues[op[1]][0])
    elif op[0] == 2:
        if len(queues[op[1]]) != 0:
            queues[op[1]].popleft()


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

string s;
vector<string> vs; 
bool f[26];

void dfs(string t, int now){
    if(now == s.size()){
        string r = t;
        memset(f, false, sizeof(f));
        rep(i, 0, r.size()){
            if(f[r[i] - 'a'] == false && r[i] != 'a'){
                r[i] = r[i] - 1;
            }
            f[t[i] - 'a'] |= true;
        }
        if(r == s) vs.push_back(t);
        return;
    }
    int d[26] = {};
    rep(i, 0, now) d[t[i] - 'a']++;
    if(t[now] != 'z'){
        string tmp = t;
        tmp[now] = tmp[now] + 1;
        dfs(tmp, now + 1);
    }
    if(t[now] == 'a' || d[t[now] - 'a'] != 0) dfs(t, now + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (1) {
        cin >> s;
        if(s == "#") break;
        vs.clear();
        dfs(s, 0);
        int ans = vs.size();
        sort(vs.begin(), vs.end());
        cout << ans << endl;
        if(ans <= 10){
            rep(i, 0, ans){
                cout << vs[i] << endl;
            }
        }else{
            rep(i, 0, 5){
                cout << vs[i] << endl;
            }
            rep(i, ans - 5, ans){
                cout << vs[i] << endl;
            }
        }
    }
}


Measured memory_bytes: 4292
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    sort(l.begin(), l.end());
    int ans = 0;
    rep(a, n) {
        for (int b = a + 1; b < n; ++b) {
            for (int c = b + 1; c < n; ++c) {
                if (l[b] - l[a] < l[c] && l[c] < l[a] + l[b]) ++ans;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3556
import heapq
N = int(input())
A = [int(x) for x in input().split()]
B = [[0, 0] for i in range(N + 1)]
A1 = A[:N]
B[0][0] = sum(A1)
heapq.heapify(A1)
for i in range(N):
  B[i + 1][0] = B[i][0]
  B[i + 1][0] += A[N + i]
  heapq.heappush(A1, A[N + i])
  B[i + 1][0] -= heapq.heappop(A1)
A2 = [-a for a in A[2 * N:]]
B[N][1] = -sum(A2)
heapq.heapify(A2)
for i in range(N):
  B[N - i - 1][1] = B[N - i][1]
  B[N - i - 1][1] += A[2 * N - i - 1]
  heapq.heappush(A2, -A[2 * N - i - 1])
  B[N - i - 1][1] += heapq.heappop(A2)
ans = - 10 ** 18
for b0, b1 in B:
  ans = max(b0 - b1, ans)
print(ans)

Measured memory_bytes: 126112
from collections import Counter

N = int(input())
W = []
for n in range(N):
    W.append(input())

for n in range(N-1):
    if W[n][-1] != W[n+1][0]:
        print('No')
        exit(0)

if len(set(W)) != len(W):
    print('No')
    exit(0)

print("Yes")


Measured memory_bytes: 3572
n, t = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(n)]

ab.sort()

dp = [[0] * t for i in range(n+1)]
ans = 0
for i in range(n):
    for j in range(t):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j - ab[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j - ab[i][0]] + ab[i][1])
    now = dp[i][t-1] + ab[i][1]
    ans = max(ans, now)

print(ans)

Measured memory_bytes: 117080
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <complex>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define EPS 1e-8
#define DEB 1

int memo[128][128];  //[time][node]
int edge[128][128];
int reitou[128];
int n,m,l,k,a,h;
int karikari;

class state{
  public:
	int now,life,cost;
	state(int _n, int _l, int _c){
		now = _n;
		life = _l;
		cost = _c;
	}
	bool operator<(const state& a)const{
		if( cost==a.cost ) return life<a.life;
		return cost > a.cost;
	}
};

int main(){

	while(scanf("%d%d%d%d%d%d",&n,&m,&l,&k,&a,&h),n|m|l|k|a|h){
		karikari = INT_MAX;
		memset(reitou,0,sizeof(reitou));
		rep(i,128)rep(j,128)edge[i][j]=memo[i][j]=INT_MAX;
		
		rep(i,l){
			int g; scanf("%d",&g);
			reitou[g] = 1;
		}
		rep(i,k){
			int x,y,t; scanf("%d%d%d",&x,&y,&t);
			edge[x][y] = edge[y][x] = t;
		}

		priority_queue<state> q;
		q.push(state(a,m,0));
		memo[m][a] = 0;

		while( !q.empty() ){
			int nw = q.top().now;
			int lf = q.top().life;
			int co = q.top().cost;
			q.pop();

			if( karikari<=co ) break;
			//Ú®·ép^[
			rep(i,n)if( edge[nw][i]!=INT_MAX && lf-edge[nw][i]>=0 ){
				int next_life = lf - edge[nw][i];
				if( memo[next_life][i] > co+edge[nw][i] ){
					memo[next_life][i] = co+edge[nw][i];
					q.push(state(i,next_life,co+edge[nw][i]));

					if( i==h ){
						karikari = min(karikari, co+edge[nw][i]);
					}
				}
			}

			//â·ép^[
			if( reitou[nw]==1 ){
				for(int i=1; i+lf<=m; i++){
					if( memo[i+lf][nw] > co+i ){
						memo[i+lf][nw] = co+i;
						q.push(state(nw,i+lf,co+i));
					}
				}
			}
		}

		int ans = INT_MAX;
		rep(i,m+1){
			ans = min(ans, memo[i][h]);
		}
		if( ans==INT_MAX ){
			puts("Help!");
		}else{
			printf("%d\n",ans);
		}
	}
	return 0;
}

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

const int N = (1 << 18);
const int W = 100001;

const int MAGIC = 1 << 9;

int n;
int v[N], w[N];

int dp[MAGIC][W];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &v[i], &w[i]);
  }

  for (int i = 1; i < min(n+1, MAGIC); ++i) {
    vector<pair<int, int>> items;
    int u = i;
    while (u >= 1) {
      items.emplace_back(v[u], w[u]);
      u >>= 1;
    }

    for (int mask = 1; mask < 1 << items.size(); ++mask) {
      int sumV = 0, sumW = 0;
      for (int j = 0; j < items.size(); ++j) {
        if (mask >> j & 1) {
          sumV += items[j].first;
          sumW += items[j].second;
        }
      }

      if (sumW < W) {
        // cerr << i << " " << sumW << " " << sumV << endl;
        dp[i][sumW] = max(dp[i][sumW], sumV);
      }
    }

    for (int j = 1; j < W; ++j) dp[i][j] = max(dp[i][j], dp[i][j-1]);
  }

  int q;
  scanf("%d", &q);
  while (q--) {
    int vi, l;
    scanf("%d %d", &vi, &l);
    if (vi < MAGIC) {
      printf("%d\n", dp[vi][l]);
    } else {
      vector<pair<int, int>> items;
      int u = vi;
      while (u >= MAGIC) {
        items.emplace_back(v[u], w[u]);
        u >>= 1;
      }

      int ans = dp[u][l];
      for (int mask = 1; mask < 1 << items.size(); ++mask) {
        int sumV = 0, sumW = 0;
        for (int j = 0; j < items.size(); ++j) {
          if (mask >> j & 1) {
            sumV += items[j].first;
            sumW += items[j].second;
          }
        }

        if (l >= sumW) {
          ans = max(ans, sumV + dp[u][l - sumW]);
        }
      }

      printf("%d\n", ans);
    }
  }
  return 0;
}


Measured memory_bytes: 205452
list = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1]

A, B = map(int, input().split())

# print(A)
# print(B)

# print(list.index(A))
# print(list.index(B))

# Aliceが勝つならAliceを、Bobが勝つならBobを、引き分けならDrawを出力せよ。

if list.index(A) > list.index(B):
    print('Alice')
elif list.index(A) < list.index(B):
    print('Bob')
else:
    print('Draw')

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

vector<ll> divisor(ll n){
  vector<ll> res;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      res.push_back(i);
      if(i!=n/i) res.push_back(n/i);
    }
  }
  return res;
}

int main(){
  ll n;
  cin>>n;
  auto v=divisor(n);
  int cnt=0;
  for(ll x:v){
    if(x==1) continue;
    ll n2=n;
    while(n2%x==0) n2/=x;
    if((n2-1)%x==0){
      cnt++;
    }
  }
  auto v2=divisor(n-1);
  for(ll x:v2){
    if(x==1) continue;
    cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <algorithm>
#include <unordered_map>
#define int                long long
#define pb                 push_back
#define pi                 pair<int,int>
#define vi                 vector<int>
#define all(v)             v.begin(),v.end()
#define MOD                1000000007
#define F                  first
#define S                  second
#define FOR(i,r)           for(int i=0;i<r;i++)
#define REP(i,l,r)         for(int i=l;i<r;i++)
#define RER(i,l,r)         for(int i=l;i>=r;i--)
#define print(v)           for(auto i : v)cout << i << ' ';
#define FASTIO             ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mem(arr,k)         memset(arr,k,sizeof(arr));
#define pii                acos(-1.0)
#define PI                 3.1415926535897932385
#define Sin(a)             sin((pi*a)/180)
#define test()             int x;cin >> x;while(x--)
using namespace std;
const int N = 1003;
int dp[N][N],n,m;
char mat[N][N];
int rec(int i,int j){
	if(i==n-1 && j==m-1){
		dp[i][j] = 1;
		return 1;
	}
	if(dp[i][j]!=-1)
		return dp[i][j];
	if(mat[i][j] == '#')
		return 0;
	int ways = 0;
	if(i+1 < n){
		ways += rec(i+1,j);
		ways %= MOD;
	}
	if(j+1 < m){
		ways += rec(i,j+1);
		ways %= MOD;
	}
	dp[i][j] = ways;
	return ways;
}
int32_t main(){

	FASTIO;
	cin >> n >> m;
	REP(i,0,n){
		REP(j,0,m){
			cin >> mat[i][j];
		}
	}
	mem(dp,-1);
	cout << rec(0,0) << endl;
    return 0;

}

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

using namespace std;

int N, ans[505 * 505];

struct XX {
  int pos, id, L, R;
  bool operator<(const XX& o) const { return pos < o.pos; }
} X[505];

int main() {
//  freopen("a.in", "r", stdin);
//  freopen("a.out", "w", stdout);
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &X[i].pos);
    ans[X[i].pos] = i;
    X[i].id = i;
    X[i].L = i - 1;
    X[i].R = N - i;
  }
  sort(X + 1, X + N + 1);
  int tot = N * N;
  for (int i = 1; i <= tot; i++) {
    if (ans[i]) continue;
    for (int j = 1; j <= N; j++) {
      if (X[j].L > 0 && X[j].pos >= i) {
        ans[i] = X[j].id;
        X[j].L--;
        break;
      }
    }
  }
  for (int i = tot; i >= 1; i--) {
    if (ans[i]) continue;
    for (int j = N; j >= 1; j--) {
      if (X[j].R > 0 && X[j].pos <= i) {
        ans[i] = X[j].id;
        X[j].R--;
        break;
      }
    }
  }
  bool flag = true;
  for (int i = 1; i <= tot; i++)
    if (!ans[i]) flag = false;
  if (!flag) return puts("No"), 0;
  puts("Yes");
  for (int i = 1; i <= tot; i++) printf("%d%c", ans[i], " \n"[i == tot]);
  return 0;
}


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

#define count_ones __builtin_popcountl
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lca(a, b) a / __gcd(a, b) * b
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    if (s[0] == 'S') {
        cout << "Cloudy";
    } else if (s[0] == 'C') {
        cout << "Rainy";
    } else {
        cout << "Sunny";
    }

    return 0;
}

Measured memory_bytes: 256
main :: IO ()
main = do
  l1 <- getLine
  let [x, y] = map read $ words l1 :: [Integer]
      (x', y') = (max x y, min x y)
      n = x' - y' -- (y'-n, y'-n)から(x, y)への移動回数
      m = (y' - n)`div`3 -- (y'-n, y'-n)への移動回数/2
      k = m + n
  if y'*2 < x' || (x + y) `mod` 3 /= 0 then
    print 0
  else
    print $ binomialCoefficients (10^9 + 7) (m + k) k

-- gcdExt a b = (x, y, g)
-- ax + by = g = gcd a b
gcdExt :: Integral a => a -> a -> (a, a, a)
gcdExt a 0 = (1, 0, a)
gcdExt a b = (x, y, g)
  where (q, r) = a`divMod` b
        (s, t, g) = gcdExt b r
        x = t
        y = s - q*t

-- ax + kp = 1
modInv :: Integral a => a -> a -> a
modInv p a = x
  where (x, _, _) = gcdExt a p

binomialCoefficients p n k = (npk*modInv p (fact p $ n - k))`mod`p
  where npk = product' p $ drop (fromIntegral k) [1..n]

product' p [] = 1
product' p (x:xs) = (x*product' p xs)`mod`p

fact p 0 = 1
fact p n = (n*fact p (n-1))`mod`p

Measured memory_bytes: 18832
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scanf("%s", &s)
	fmt.Printf("%d\n", ABC081A(s))
}

// ABC081A ...
func ABC081A(s string) int {
	res := 0
	for _, c := range s {
		if c == '1' {
			res++
		}
	}

	return res
}


Measured memory_bytes: 1832
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var S = ReadLine();
        if (S[0] != 'A')
        {
            WriteLine("WA");
            return;
        }
        if (S.Skip(2).Take(S.Length-3).Count(x=>x=='C')!=1)
        {
            WriteLine("WA");
            return;
        }
        if(S.Count(x=>x>0x60)!=S.Length-2)
        {
            WriteLine("WA");
            return;
        }
        WriteLine("AC");
    }
}


Measured memory_bytes: 13140
using System;
using System.Collections.Generic;
using static System.Math;
using System.Linq;
using System.Text;
 
class DandA {
    static void Main(string[] args) {
        long[] nab = ReadLineLongArray();
        long rtn = nab[2];
        if ((nab[2] - nab[1]) % 2 == 0) {
            rtn = Math.Min(rtn, (nab[2] - nab[1]) / 2);
        } else {
            if (nab[2] + nab[1] < nab[0] + 1) {
                rtn = Math.Min(rtn, (nab[2] - nab[1] - 1) / 2 + nab[1]);
            } else {
                rtn = Math.Min(rtn, (nab[2] - nab[1] - 1) / 2 + nab[0] - nab[2] + 1);
            }  
        }
        Console.WriteLine(rtn);
    }
 
    static string Alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static string[] strAry = new string[] {"L", "R", "U", "D"}; 
  
    static private string ReadLineStr() {return Console.ReadLine();}
    static private int ReadLineInt() {return int.Parse(Console.ReadLine());}
    static private long ReadLineLong() {return long.Parse(Console.ReadLine());}
    static private double ReadLineDouble() {return double.Parse(Console.ReadLine());}
    static private string[] ReadLineStrArray() {return Console.ReadLine().Trim().Split();}
    static private int[] ReadLineIntArray() {return Console.ReadLine().Trim().Split().Select(a => int.Parse(a)).ToArray();}
    static private long[] ReadLineLongArray() {return Console.ReadLine().Trim().Split().Select(a => long.Parse(a)).ToArray();}
    static private double[] ReadLineDoubleArray() {return Console.ReadLine().Trim().Split().Select(a => double.Parse(a)).ToArray();}
    static private decimal[] ReadLineDecimalArray() {return Console.ReadLine().Trim().Split().Select(a => decimal.Parse(a)).ToArray();}
    static private string[][] ReadMLineStrArray(int arg) { return new int[arg].Select(_ => Console.ReadLine().Split()).ToArray();}
    static private int[][] ReadMLineIntArray(int arg) { return new int[arg].Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()).ToArray();}
 
    static private bool IsPrime(int num) {
        if (num < 2) return false;
        if (num == 2) return true;
        else if (num % 2 == 0) return false;
        double sqrtNum = Math.Sqrt(num);
        for (int i = 3; i <= sqrtNum; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
  
    static private string IntToNString(int x, int n) {
        var nstring = "";
        var numbers = new string[] { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f" };
        int r = 1;
        int q = x;
        while (q > 0) {
            r = q % n;
            nstring += numbers[r];
            q = q / n;
        }
        return string.Join("",nstring.Reverse());
     }
}

Measured memory_bytes: 13396
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;

using namespace std;
int main(){

    string s;
    
    while(getline(cin,s)){
        
        for(int i=0;i<27;i++){
            for(int j=0;j<s.size();j++){
                if(s[j]=='z'){s[j]='a';}
                else if(!isalpha(s[j])){}
                else s[j]=char(s[j]+1);
            }
            if(s.find("this")!=string::npos||s.find("that")!=string::npos||s.find("the")!=string::npos){
                cout<<s<<endl;
                break;
            }
            
            
        }
        
        
    }
    
    return 0;
}



Measured memory_bytes: 3132
#include <iostream>
#include <iomanip>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int N ;
int F[100005],h[100005];
int main()
{
    cin >> N ;
    F[1] = F[0] = 0 ;
    for(int i = 1 ; i<= N ; i++)
        cin >> h[i];
    F[2] = F[1] + abs(h[2]-h[1]);
    for(int i = 3 ; i<= N; i++)
        F[i] = min(F[i-1]+abs(h[i]-h[i-1]),F[i-2]+abs(h[i]-h[i-2]));
    cout << F[N] ;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long int ll;
using namespace std;

int main()
{
    string s;
    cin >> s;
    int ans = 0;
    int size = s.size();
    for(int i=0;i<size;i++){
        if(s[i]-'0' == (i&1)) ans++;
        
    }
    ans = min(ans,size-ans);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
  #include <iomanip>
  #include <algorithm>
  #include <cmath>
  #include <queue>
  #include <list>
  #include <limits>
  #include <string>
  #include <vector>
  #include <stack>
  using namespace std;
  typedef long long ll;

  typedef pair<ll, ll> curr;
  const int MOD = 998244353;


  int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
  }

  ll calc(int a, int b, int p){
    if(b == 0) return 1;
    if(b % 2 == 0){
      ll d = calc(a, b/2, p);
      return (d*d)%p;
    }else{
      return (a*calc(a, b-1, p))%p;
    }

  }
  int main()
  {
    int N,K,curr = 0,index = 0;
    cin >> N >> K;
    int x[100000];
    ll _min;
    for(int i=0;i<N;i++){
      cin >> x[i];
    }
    _min = x[K-1] - x[0] + min(abs(x[0]),abs(x[K-1]));
    for(int i=1;i<N-K+1;i++){
      ll range = x[K+i-1] - x[i] + min(abs(x[i]),abs(x[K+i-1]));
      if(range < _min) _min = range;
    }
    cout << _min;
  }


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = int_fast64_t;
using ull = uint_fast64_t;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep1(i, n) for (ll i = 1; i < n; ++i)
ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }
template <typename T> void vecout(const T &v) {
  for (auto it = v.begin(); it != v.end();
       ++it, cout << (it != v.end() ? " " : "\n")) {
    cout << *it;
  }
}

void solve() {
  // main coding
  string s,t; cin>>s>>t;
  int m=s.size(), n=t.size();
  s="$"+s; t="$"+t; // 1-indexed
  vector<vector<int>> dp(m+1,vector<int>(n+1));
  rep1(i,m+1) rep1(j,n+1) {
    if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1;
    else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
  }
  // 文字を復元する
  string ans="";
  int i=m,j=n;
  while(i>0&&j>0) {
    if(dp[i][j]==dp[i-1][j]) i--;
    else if(dp[i][j]==dp[i][j-1]) j--;
    else {
      ans.push_back(s[i]);
      i--; j--;
    }
  }
  reverse(ans.begin(),ans.end());
  cout<<ans<<endl;
}

int main() {
  cout << fixed << setprecision(10);
  solve();
  return 0;
}


Measured memory_bytes: 35584
X, N = map(int, input().split())
if N == 0:
  print(X)
  exit()
P = list(map(int, input().split()))

i = 0
while 1:
  if not X-i in P:
    print(X-i)
    break
  if not X+i in P:
    print(X+i)
    break
  i += 1

Measured memory_bytes: 9164
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto A = RD;
	auto B = RD;
	auto C = RD;
	auto K = RD;

	long ans;
	if (K % 2 == 0)
	{
		ans = A - B;
	}
	else
	{
		ans = B - A;
	}

	writeln(abs(ans) > 10LU^^18 ? "Unfair" : ans.to!string);
	stdout.flush();
	debug readln();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <complex>

int main()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    printf("%d\n", std::min(a, b) + std::min(c, d));

    return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
    int A, B, C, D;
    if (scanf("%d%d%d%d", &A, &B, &C, &D) < 4) return 0;

    int x = min(A,B);
    int y = min(C,D);
    printf("%d\n", x + y);

    return 0;
}


Measured memory_bytes: 128
//abc160_d.cpp
//Sat Mar 28 21:13:21 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,x,y;
	cin >> n >> x >> y;
	x--;y--;
	int dist[n];
	fill(dist,dist+n,0);
	for (int i=0;i<n-1;i++){
		for (int j=i+1;j<n;j++){
			int tmp1 = j-i;
			int tmp2 = abs(y-j)+abs(x-i)+1;
			dist[min(tmp1,tmp2)]++;
		}
	}

	for (int i=1;i<n;i++){
		cout << dist[i] << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <map>

using namespace std;

using PII = pair<int, int>;

const long long maxi = 1e15;

long long pow5(long long x) {
	return x * x * x * x * x;
}

int main() {
	long long x;
	cin >> x;

	map<int, long long> nums_val;
	vector<int> nums;
	for (int i = -4000; i <= 4000; i++) {
		long long x = pow5(i);
		if (abs(x) <= maxi) {
			nums.emplace_back(i);
			nums_val[i] = x;
		}
	}
	// cout << nums.size() << endl;

	for (auto a: nums) {
		for (auto b: nums) {
			long long tmp = nums_val[a] - nums_val[b];
			if (tmp == x) {
				cout << a << " " << b << endl;
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3292
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>a>>b>>c;
	if(c==0)cout<<a<<endl;
	else if(abs(a/c)>b){
		if(a>0)cout<<a-b*c<<endl;else cout<<abs(a+b*c)<<endl;
	}else{
		b-=abs(a/c);
		long long t1=abs(a%c),t2=abs(a>0?a%c-c:a%c+c);
		if(t1==0){
			if(b%2)cout<<c<<endl;
            else cout<<0<<endl;
		}else{
			if(b%2)cout<<t2<<endl;
			else cout<<t1<<endl;
		}
	}
}


Measured memory_bytes: 3648
#include <stdio.h>
#include <string.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
 
class dice {
  private:
    int f[6];
  public:
    dice(int *a){
      int i;
      rep(i, 6) f[i] = a[i];
    }
    dice(){}
    void set(int *a) {
      int i; 
      rep(i, 6) f[i] = a[i];
    }
    void n(){
      int t;
      t = f[0];
      f[0] = f[1];
      f[1] = f[5];
      f[5] = f[4];
      f[4] = t;
    }
    void s() {
      int t;
      t = f[0];
      f[0] = f[4];
      f[4] = f[5];
      f[5] = f[1];
      f[1] = t;
    }
    void w() {
      int t;
      t = f[0];
      f[0] = f[2];
      f[2] = f[5];
      f[5] = f[3];
      f[3] = t;
    }
    void e() {
      int t;
      t = f[0];
      f[0] = f[3];
      f[3] = f[5];
      f[5] = f[2];
      f[2] = t;
    }
    void r() {
      int t;
      t = f[1];
      f[1] = f[2];
      f[2] = f[4];
      f[4] = f[3];
      f[3] = t;
    }
    void l() {
      int t;
      t = f[1];
      f[1] = f[3];
      f[3] = f[4];
      f[4] = f[2];
      f[2] = t;
    }
    int print(int num) {
      return f[num];
    }
};
 
int main(void) {
  int a[6], n, i, j, k, l;
  scanf("%d", &n);
  dice d[n];
  rep(i, n) {
    rep(j, 6) scanf("%d", &a[j]);
    d[i].set(a);
  }
  /*rep(i, n) {
   rep(k, 6) printf("%d ", d[i].print(k));
   printf("\n");
  }*/
  int s = 0;
  rep(i, n) for(j = i + 1; j < n; ++j) {
    rep(l, 30) {
    if(d[i].print(1) == d[j].print(0)) d[j].s();
    else if(d[i].print(2) == d[j].print(0)) d[j].e();
    else if(d[i].print(3) == d[j].print(0)) d[j].e();
    else if(d[i].print(4) == d[j].print(0)) d[j].n();
    else if(d[i].print(5) == d[j].print(0)) d[j].n(), d[j].n();
    if(d[i].print(3) == d[j].print(1)) d[j].r();
    else if(d[i].print(2) == d[j].print(1)) d[j].l();
    else if(d[i].print(4) == d[j].print(1)) d[j].r(), d[j].r();
    /*printf("%d %d:\n", i, j);
    rep(k, 6) printf("%d %d\n", d[i].print(k), d[j].print(k));*/
    int s = 0;
    rep(k, 6) if(d[i].print(k) != d[j].print(k)) s = 1;
    if(!s) {
     /* printf("%d %d:\n", i, j);
      rep(k, 6) printf("%d %d\n", d[i].print(k), d[j].print(k));*/
      printf("No\n");
      return 0;
    }
    }
  }
  printf("Yes\n");
  return 0;
}


Measured memory_bytes: 2612
e, y = map(int,input().split())

if e == 0:
    if y < 1912:
        a = y - 1867
        print("M", a, sep = '')
    elif y < 1926:
        a = y - 1911
        print("T", a, sep = '')
    elif y < 1989:
        a = y - 1925
        print("S", a, sep = '')
    elif y < 2017:
        a = y - 1988
        print("H", a, sep = '')
elif e == 1:
    a = 1867 + y
    print(a)
elif e == 2:
    a = 1911 + y
    print(a)
elif e == 3:
    a = 1925 + y
    print(a)
elif e == 4:
    a = 1988 + y
    print(a)


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
typedef long long ll;
const int N=4000;
int n,k;
string x,y;
vector<int>v;
int dp[N][N];
string ans;
int solve(int i,int j){
	if(i==x.length()||j==y.length()){
		return 0;
	}
	int &res=dp[i][j];
	if(res!=-1){
		return res;
	}
	if(x[i]==y[j]){
		res=solve(i+1,j+1)+1;
	}else{
		res=max(res,solve(i+1,j));
		res=max(res,solve(i,j+1));
	}
	return res;
}
void build(int i,int j){
	if(i==x.length()||j==y.length()){
		return;
	}
	if(x[i]==y[j]){
		ans+=x[i];
		build(i+1,j+1);
	}else if(dp[i+1][j]>dp[i][j+1]){
		build(i+1,j);
	}else{
		build(i,j+1);
	}
}
int main(){

	cin >>x >> y ;
	memset(dp,-1,sizeof dp);
	solve(0,0);
	ans="";
	build(0,0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 63104
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF (1e9)
#define PI (acos(-1))

bool ReverseCheck(string str) {
	bool flg = false;
	string rev = str;
	reverse(rev.begin(), rev.end());
	if (rev == str) flg = true;
	return flg;
}

int main() {
	string s, front, back, ans = "No";
	cin >> s;

	if (ReverseCheck(s)) {
		front = s.substr(0, s.size()/2);
		back = s.substr((s.size()+1)/2, s.size()/2);
		if (ReverseCheck(front) && ReverseCheck(back)) ans = "Yes";
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 3612
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 998244353;
int n,r,g,b;

signed main(){
    cin >> r >> g >> b >> n;
    int cnt = 0;
    rep(i,3001){
        rep(j,3001){
            int k = n-r*i-g*j;
            if(k<0)break;
            else if(k%b == 0)cnt++;
        }
    }
    cout << cnt << endl;
    
    
    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://diverta2019.contest.atcoder.jp/tasks/diverta2019_a

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "]"; return os; }


// import here

int main(){
    LL n, a, b;
    cin >> n >> a >> b;
    cout << min(a, b) << " " << max<LL>(0, a + b - n) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define int long long
#define double long double
#define all(a) a.begin(), a.end()
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; }
using namespace std;

signed main(void){

    int N, M; cin >> N >> M;
    vector<int> a(N);
    rep(i, N)cin >> a[i];

    vector<vector<int>> graph(N);
    rep(i, M){
        int x, y; cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    if(N > 2 * M + 2){
        cout << "Impossible" << endl;
        return 0;
    } else if(N == M + 1){
        cout << 0 << endl;
        return 0;
    }

    const int inf = 1000000000000000;
    int ans = 0, pos, cur;
    vector<bool> visited(N, false), used(N, false);

    function<void(int)> dfs = [&](int v){
        if(visited[v])return;
        visited[v] = true;
        if(chmin(cur, a[v]))pos = v;
        for(int i : graph[v])dfs(i);
    };

    rep(i, N){
        if(visited[i])continue;
        cur = inf;
        pos = -1; 
        dfs(i);
        ans += cur;
        used[pos] = true;
    }

    vector<int> remaining;
    rep(i, N)if(!used[i])remaining.push_back(a[i]);
    sort(all(remaining));
    rep(i, N - M - 2)ans += remaining[i];

    cout << ans << endl;
    return 0;

}

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

int n, m;
vector<int> c;

int CoinProblem() {//dpを金額で動かす
	vector<int> dp(50001);
	fill(dp.begin(), dp.end(), 1e8);
	dp[0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			if(i >= c[j]) dp[i] = min(dp[i], dp[i - c[j]] + 1);
		}
	}
	return dp[n];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	c.resize(m);
	rep(i, m) cin >> c[i];
	cout << CoinProblem() << endl;
	return 0;
}


Measured memory_bytes: 3112
#include <stdio.h>
#include <limits.h>
 
int main(void){
	int m,N,i = 0,f = 0;
	int a[100000] = {'0'};
	
	scanf("%d",&N);
	while(i < N){
		scanf("%d",&a[i]);
		++i;
	}
	for(i = 0;i < N; ++i){
		f += a[i] - 1;
	}
	printf("%d\n",f);
	return 0;
}


Measured memory_bytes: 512
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Data.Maybe
import Data.List

type S = VU.Vector Int

-- 下限境界 (Vector 付き)
lowerBoundV :: VU.Vector Int -> (Int, Int) -> Int -> Int
lowerBoundV vec (from, to) target
    | from == to = from
    | mValue >= target = lowerBoundV vec (from, mid) target
    | mValue < target = lowerBoundV vec (mid + 1, to) target
        where
            mid = (from + to) `div` 2
            mValue = vec VU.! mid

-- 上限境界 (Vector 付き)
upperBoundV :: VU.Vector Int -> (Int, Int) -> Int -> Int
upperBoundV vec (from, to) target
    | from == to = from
    | mValue > target = upperBoundV vec (from, mid) target
    | mValue <= target = upperBoundV vec (mid + 1, to) target
        where
            mid = (from + to) `div` 2
            mValue = vec VU.! mid

solve :: S -> S -> S -> Int -> Int
solve xs ys zs n
  | VU.null ys = 0
  | otherwise = res + solve xs ys' zs n
    where
      res = lb * (n - ub)
      y = VU.head ys
      ys' = VU.tail ys
      lb = lowerBoundV xs (0,n) y
      ub = upperBoundV zs (0,n) y

main = do
  n <- readLn :: IO Int
  xs <- VU.fromList . sort . map (fst . fromJust . B.readInt) . B.words <$> B.getLine
  ys <- VU.fromList . sort . map (fst . fromJust . B.readInt) . B.words <$> B.getLine
  zs <- VU.fromList . sort . map (fst . fromJust . B.readInt) . B.words <$> B.getLine
  print $ solve xs ys zs n

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

using namespace std;

const int MAXN=128;
const int MAXK=100000+100;
int a[MAXN];
bool dp[MAXK][2];
int n,k;

void output(){
	for(int j=0;j<=1;j++){
		for(int i=1;i<=k;i++){
			cout<<dp[i][j]<<' ';
		}
		cout<<endl;
	}
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			if(a[j]<=i){
				if(!dp[i-a[j]][0]) dp[i][0]=1;
		//		if(!dp[i-a[j]][1]) dp[i][0]=1;
			}
		}
	}
//	output();
	if(dp[k][0]) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
	return 0;
}
/*
2 4
2 3
*/ 

Measured memory_bytes: 384
import java.util.Scanner;
public class Main{
    public static int compare(int A[], int B[]){
        int i = 0;
        while(i < A.length && i < B.length){
            if(A[i] == B[i]);
            else if(A[i] > B[i])
                return 0;
            else return 1;
            i++;
        }
        if(A.length == B.length || i == B.length)
            return 0;
        else
            return 1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int A[] = new int[n];
        for(int i = 0 ; i < n ; i++)
            A[i] = sc.nextInt();
        int m = sc.nextInt();
        int B[] = new int[m];
        for(int i = 0 ; i < m ; i++)
            B[i] = sc.nextInt();
        System.out.println(compare(A,B));
    }
}


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

int main(){
  int p[8];
  int c[8],ans[8];
  int tmp,min;

  while(cin >> p[0]){
    for(int i=1;i<8;i++)cin >> p[i];
    c[0] = 1;
    c[1] = 2;
    c[2] = 1;
    c[3] = 2;
    c[4] = 1;
    c[5] = 4;
    c[6] = 1;
    c[7] = 4;

    min = -1;

    for(int i=0;i<8;i++){
      tmp = 0;
      for(int j=0;j<8;j++){
	if(p[j] > c[j])tmp += p[j] - c[j];
      }
      if(tmp < min || min < 0){
	min = tmp;
	for(int j=0;j<8;j++)ans[j] = c[j];
      }else if(tmp == min){
	bool f = false;
	for(int j=0;j<8;j++){
	  if(ans[j] > c[j]){
	    f = true;
	    break;
	  }else if(ans[j] < c[j])break;
	}
	if(f){
	  for(int j=0;j<8;j++)ans[j] = c[j];
	}
      }

      tmp = c[0];
      for(int i=1;i<8;i++)c[i-1] = c[i];
      c[7] = tmp;
    }
    for(int i=0;i<7;i++)cout << ans[i] << " ";
    cout << ans[7] << endl;
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr_inv(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define rep(i,n) repr(i,0,n)
#define INF INT_MAX
#define INFLL _I64_MAX
#define MOD 1000000007
#define PI 3.1415926535
using namespace std;
int main(void)
{
	int n, ans=0;

	cin>>n;

	vector<int> l(n), r(n);

	rep(i, n) cin>>l[i]>>r[i];

	rep(i, n){
		ans+=r[i]-l[i]+1;
	}
	cout<<ans<<endl;
}



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

#define ll long long int
#define pb push_back
#define RONALDO            \
  ios::sync_with_stdio(0); \
  cin.tie(0);              \
  cout.tie(0);
#define endl "\n"
#define pii pair<ll, ll>
#define ff first
#define ss second
#define mod 1000000007
#define vi vector<char>
#define mi map<char, ll>
#define Max(x, y, z) max(x, max(y, z))
#define Min(x, y, z) min(x, min(y, z))
//LOVE U MESSI && CRistiano !!

//INSPIRATIONAL MICHAEL PHELPS && USAIN BOLT !!

int main()
{
  RONALDO;
  string s, t, k ;
  cin >> s >> t;
  ll ans = 0, mmax = INT_MAX;
  ll n = s.length();
  ll p = t.length();
  for (ll i = 0; i < n-p+1;i++)
  {
    k = s.substr(i, p);
    for (ll j = 0; j < p;j++)
    {
      if(k[j]!=t[j])
        ans++;
    }
    mmax = min(ans, mmax);
    ans = 0;
  }
  cout << mmax;
}

Measured memory_bytes: 3660
import sys
from collections import deque

H, W = map(int, input().split())
N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

B = deque()
for i, a in enumerate(A):
    for j in range(a):
        B.append(i + 1)

res = [[-1] * W for _ in range(H)]
for i in range(H):
    if i % 2 == 0:
        for j in range(W):
            b = B.popleft()
            res[i][j] = b
    else:
        for j in reversed(range(W)):
            b = B.popleft()
            res[i][j] = b

for row in res:
    print(*row)


Measured memory_bytes: 9708
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        sc.close();

        int cnt = 0;
        int j;
        for (int i=1; i<N; i++) {
            j = N -i;
            if (j>0 && i<j) {
                cnt++;
            } else {
                break;
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 23380