akhauriyash/Code-Regression huggingface dataset:
//templates
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <queue>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define sort_key(struct_name,key_name) [](const struct_name &x, const struct_name &y){return x.key_name < y.key_name;}
#define pb(x) push_back(x)
typedef long long ll;
const long long MOD = 1e9 + 7;
using namespace std;

//main
int main(){
    double S; cin >> S;
    double ans;
    int N = S;
    if(N==1) ans = 1;
    else if(N%2==0) ans = 0.5;
    else ans = (S+1)/2/S;
    cout << ans << endl;
}



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

typedef long long   ll;
const ll mod = 1e9 + 7;

#define speedup_IO      ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn(i,a,n)     for(ll i = a; i < n; i++)
#define ford(i,n,a)     for(ll i = n-1; i >= a; i--)
#define pb              push_back
#define lb              lower_bound
#define ub              upper_bound
#define pll             pair<ll,ll>
#define all(a)          (a).begin(),(a).end()
#define reset(a,x)      memset(a,x,sizeof(a))

ll mypow(ll base, ll exp) {ll res = 1; while (exp) {if (exp & 1) res = (res * base) % mod; exp >>= 1, base = (base * base) % mod;} return res;}
ll gcd(ll a, ll b)  { return b ? gcd(b, a % b) : a;            }
ll mult(ll a, ll b) { if (a < 0) {a += mod;} if (b < 0) {b += mod;} return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b)  { if (a < 0) {a += mod;} if (b < 0) {b += mod;} return (a % mod + b % mod) % mod;        }
ll sub(ll a, ll b)  { if (a < 0) {a += mod;} if (b < 0) {b += mod;} return (a % mod + mod - b % mod) % mod;  }

const ll inf = 1e18;
const int nax = 1e5 + 5;

// ll fact[nax], invfact[nax];

// void pre()
// {
// 	fact[0] = 1;
// 	forn(i, 1, nax)
// 	{
// 		fact[i] = mult(fact[i - 1], i);
// 	}

// 	invfact[nax - 1] = mypow(fact[nax - 1], mod - 2);

// 	ford(i, nax, 1)
// 	{
// 		invfact[i - 1] = mult(invfact[i], i);
// 	}
// }

// ll ncr(ll n, ll r)
// {
// 	if (r > n)
// 		return 0;

// 	ll ans = mult(fact[n], mult(invfact[n - r], invfact[r]));

// 	return ans;
// }

int main()
{
	speedup_IO;

	int t = 1;
	//cin >> t;
	while (t--)
	{
		ll n;
		cin>>n;
		
		ll ans = (n+1)/2;
		cout<<ans;
	}

	return 0;
}

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        // [1-1]:top
        // [2-1]:south
        // [3-1]:east
        // [4-1]:west
        // [5-1]:north
        // [6-1]:down
        int[] n = new int[6];
        for (int i = 0; i < 6; i++) {
            n[i] = Integer.parseInt(sc.next());
        }
        Dice dice = new Dice(n[0], n[1], n[2], n[3], n[4], n[5]);

        String S = sc.next();
        for (int i = 0; i < S.length(); i++) {
            int[] temp = new int[6];
            char order = S.charAt(i);
            if (order == 'N') {
                dice.toNorth();
            } else if (order == 'S') {
                dice.toSouth();
            } else if (order == 'E') {
                dice.toEast();
            } else {
                dice.toWest();
            }
        }
        out.printf("%d\n", dice.getTop());
        out.flush();
    }
}

class Dice {
    private static int top;
    private static int south;
    private static int east;
    private static int west;
    private static int north;
    private static int down;
    Dice(int in_top, int in_south, int in_east, int in_west, int in_north, int in_down) {
        top = in_top;
        south = in_south;
        east = in_east;
        west = in_west;
        north = in_north;
        down = in_down;
    }
    public static void toNorth() {
        int temp = top;
        top = south;
        south = down;
        down = north;
        north = temp;
    }
    public static void toSouth() {
        int temp = top;
        top = north;
        north = down;
        down = south;
        south = temp;
    }
    public static void toEast() {
        int temp = top;
        top = west;
        west = down;
        down = east;
        east = temp;
    }
    public static void toWest() {
        int temp = top;
        top = east;
        east = down;
        down = west;
        west = temp;
    }
    public static int getTop() {
        return top;
    }
}


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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

const int MAXN = 100100;

ll arr[MAXN], sum[MAXN], pos[MAXN];

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        sum[i] = arr[i];
        pos[i] = max(0LL, arr[i]);
    }
    for (int i = 1; i < n; i++) {
        sum[i] += sum[i-1];
        pos[i] += pos[i-1];
    }
    ll res = max(0LL, sum[n-1]);
    ll fpos = pos[n-1];
    for (int i = 0; i + k <= n; i++){
        ll tot = sum[i + k - 1];
        if (i) tot -= sum[i-1];
        ll ptot = pos[i + k - 1];
        if (i) ptot -= pos[i-1];

        // color black
        res = max(res, fpos - ptot + tot);
        // color white
        res = max(res, fpos - ptot);
    }


    cout << res << endl;
}


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

int main() {
    vector<int> p(123456 * 2 + 1, 1);
    p[0] = p[1] = 0;
    for (int i = 2; i < p.size(); i++) {
        if (p[i] == 0) continue;
        for (int j = 2; i * j < p.size(); j++) {
            p[i * j] = 0;
        }
    }

    for (int i = 1; i < p.size(); i++) {
        p[i] += p[i-1];
    }

    
    int n;
    while (cin >> n, n) {
        cout << p[n * 2] - p[n] << endl;
    }

    return 0;
}



Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	int N;
	cin >> N;
	int A[N + 2];
	A[0] = 0;
	A[N + 1] = 0;
	for(int i = 0; i < N; i++) cin >> A[i + 1];

	int sum = 0;
	for(int i = 1; i < N + 2; i++) sum += abs(A[i - 1] - A[i]);

	for(int i = 1; i < N + 1; i++) {
		cout << sum - abs(A[i - 1] - A[i]) - abs(A[i] - A[i + 1]) + abs(A[i - 1] - A[i + 1]) << "\n";
	}
	return 0;
}

Measured memory_bytes: 3996
import java.util.*


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextLong()
    val b = sc.nextLong()
    if (a > b) {
        println(computeLeastCommonMultiple(b, a))

    } else {
        println(computeLeastCommonMultiple(a,b))

    }
}

fun computeGreatestCommonDivisor(big: Long, small: Long): Long {
    val rest = big % small
    return if (rest == 0L) small else computeGreatestCommonDivisor(small, rest)
}

fun computeLeastCommonMultiple(small: Long, big: Long): Long {
    return small * big / computeGreatestCommonDivisor(big, small)
}

Measured memory_bytes: 29608
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
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; }
int ctoi(char c){return c-'0';}

// TODO: write
int main() {
  int a,b,c;cin>>a>>b>>c;
  if((a%2||b%2||c%2)){
    print(0);
    return 0;
  }
  if(a == b && b == c){
    print(-1);
    return 0;
  }
  int ans = 0;
  while (!(a%2||b%2||c%2)){
    ans++;
    int d=b/2+c/2 ,e = a/2+c/2,f = a/2+b/2;
    a = d;b = e;c = f;
  }
  print(ans);
  return 0;
}



Measured memory_bytes: 256
#include <iostream>

#define MAX_NUM 500000
using namespace std;

int merge(int A[], int left, int right, int mid)
{
    int n1 = mid - left;
    int n2 = right - mid;
    int L[MAX_NUM], R[MAX_NUM];

    for (int i = 0; i < n1; ++i)
        L[i] = A[left + i];
    for (int i = 0; i < n2; ++i)
        R[i] = A[mid + i];
    L[n1] = 1000000000;
    R[n2] = 1000000000;

    int i = 0, j = 0;
    for (int k = left; k < right; ++k) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
    }
    return i + j;
}

int mergeSort(int A[], int left, int right)
{
    int count = 0;
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        count += mergeSort(A, left, mid);
        count += mergeSort(A, mid, right);
        count += merge(A, left, right, mid);
    }
    return count;
}

int main()
{
    int n;
    int S[MAX_NUM];
    
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> S[i];

    int count = mergeSort(S, 0, n);
    
    for (int i = 0; i < n - 1; ++i)
        cout << S[i] << " ";
    cout << S[n-1] << endl;
    
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 6888
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

H=list(map(int,input().split()))

dp=[10**9]*(N)
dp[0]=0

for i in range(N):
    for j in range(i+1,min(i+1+K,N)):
        dp[j]=min(dp[i]+abs(H[j]-H[i]),dp[j])

print(dp[-1])


Measured memory_bytes: 84836
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int m, d; cin >> m >> d;
    int ans = 0;
    REP(i,m+1) {
        REP(j,d+1) {
            if (j < 20) continue;
            int a = j % 10;
            if (a < 2) continue;
            int b = (j-a) / 10;
            if (a*b == i) ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3596
N, M = list(map(int, input().rstrip().split()))

st = []
dic = {}

for i in range(M):
    s, t = list(map(int, input().rstrip().split()))
    if s == 1:
        st.append(t)
    
    if t == N:
        dic[s] = 0

result = 'IMPOSSIBLE'
for s in st:
    if s in dic:
        result = 'POSSIBLE'
        break


print(result)
        


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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;

constexpr int MOD = 1000000007;

int main() {
    int h, w;
    scanf("%d %d", &h, &w);

    vvi grid(h, vi(w, 0));
    rep(i, 0, h) {
        rep(j, 0, w) { scanf("%d", &grid[i][j]); }
    }

    vvi dp(h + 1, vi(w + 1, 0));
    int ans = 0;

    rep(i, 1, h + 1) {
        rep(j, 1, w + 1) {
            if (grid[i - 1][j - 1] == 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
            ans = max(ans, dp[i][j]);
        }
    }

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


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int N;
    cin >> N;
    vector<ll> a(N*3);
    rep(i,N*3) cin >> a[i];

    priority_queue<ll, vector<ll>, greater<ll>> f;
    ll fsum = 0;
    rep(i, N) {
        f.push(a[i]);
        fsum += a[i];
    }
    vector<ll> ff; ff.push_back(fsum);
    for (int i=N; i<2*N; ++i) {
        fsum += a[i];
        f.push(a[i]);
        fsum -= f.top(); f.pop();
        ff.push_back(fsum);
    }
    reverse(ff.begin(), ff.end());

    reverse(a.begin(), a.end());
    priority_queue<ll> b;
    ll bsum = 0;
    rep(i, N) {
        b.push(a[i]);
        bsum += a[i];
    }
    ll ans = ff[0] - bsum;
    int cur = 1;
    for (int i=N; i<2*N; ++i) {
        bsum += a[i];
        b.push(a[i]);
        bsum -= b.top(); b.pop();
        ans = max(ans, ff[cur++] - bsum);
        //cout << cur << ", " << ff[cur++] << ", " << bsum << endl;
    }
    cout << ans << endl;
}


Measured memory_bytes: 5748
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
  int i, n, s, t, x, w;
  long long *a, *b, z;
  char *p, buf[64];
  buf[63] = 0;
  buf[62] = '\n';
  fgets(buf, 64, stdin);
  for (n=0,p=buf; *p>' '; n=n*10+*(p++)-'0');
  w = pow(2,ceil(log2(n)))+1;
  b = (a = (long long*)calloc(w*2, sizeof(long long)))+w;
  while (fgets(buf, 64, stdin)) {
    for (s=0,p=buf+2; *p>' '; s=s*10+*(p++)-'0');
    for (t=0,p++; *p>' '; t=t*10+*(p++)-'0');
    if (*buf=='0') {
      for (x=0,p++; *p>' '; x=x*10+*(p++)-'0');
      for (i=s; i<w; i+=i&-i) {
	a[i] += -x*(s-1);
	b[i] += x;
      }
      for (i=t+1; i<w; i+=i&-i) {
	a[i] += x*t;
	b[i] += -x;
      }
    } else {
      for (z=0,i=t; i>0; i&=i-1) z += a[i]+b[i]*t;
      for (i=s-1; i>0; i&=i-1)	 z -= a[i]+b[i]*(s-1);
      if (z<10) {
      	putc_unlocked('0'+z, stdout);
	putc_unlocked('\n', stdout);
      } else {
	for (i=62; z>0; buf[--i]='0'+z%10,z/=10);
	fputs(buf+i, stdout);
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3792
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+100;
struct Node{
	ll x,y;
	ll num1,num2;
}p[N];
 
ll n;
bool cmp1 (const Node &a, const Node &b)
{
	return a.num1 < b.num1;
}
bool cmp2 (const Node &a, const Node &b)
{
	return a.num2 < b.num2;
}
int main()
{	
	cin >>n;
	for(ll i=1;i<=n;i++)
	{
		cin >> p[i].x >> p[i].y;
		p[i].num1 = p[i].x - p[i].y;
		p[i].num2 = p[i].x + p[i].y;
	}
	ll ans = 0;
	sort(p+1,p+n+1,cmp1);
	ans = max(ans , p[n].num1-p[1].num1);
	sort(p+1,p+n+1,cmp2);
	ans = max(ans , p[n].num2-p[1].num2);
	cout << ans << endl; 
	return 0;
}

Measured memory_bytes: 9848
#include <stdio.h>
#define max 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n , m[max][max];

void dijkstra()
{
	int minv;
	int d[max];
	int color[max];
	
	for(int i = 0; i < n; i++)
	{
		d[i] = INFTY;
		color[i] = WHITE;
	}
	d[0] = 0;
	color[0] = GRAY;
	
	while(1)
	{
		minv = INFTY;
		int u = -1;
		for(int i = 0; i < n; i++)
		{
			if(minv > d[i] && color[i] != BLACK)
			{
				u = i;
				minv = d[i];
			}
		}
		if(u == -1){		break;}
		color[u] = BLACK;
		for(int v = 0; v < n; v++)
		{
				if(color[v] != BLACK && m[u][v] != INFTY)
				{
					if(d[v] > d[u] + m[u][v])
					{
						d[v] = d[u] + m[u][v];
						color[v] = GRAY;
					}
				}
		}
	}
	for(int i = 0; i < n; i++)
	{
		printf("%d ",i);
		if(d[i] == INFTY)
		{
			printf("-1\n");
		}
		else{
			printf("%d\n",d[i]);
		}
	}
}

int main(void)
{
	scanf("%d",&n);
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			m[i][j] = INFTY;
		}
	}
	int k , c , u , v;
	for( int i = 0; i < n; i++)
	{
		scanf("%d",&u);
		scanf("%d",&k);
		for(int j = 0; j < k; j++)
		{
			scanf("%d",&v);
			scanf("%d",&c);
			m[u][v] = c;
		}
	}
	dijkstra();
	return 0;
}


Measured memory_bytes: 2048
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(min(K,50)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 168980
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;
 
const int INFT = 1000000000;
 
int N;
vector<int> graph[101010];
int X[101010];
 
int low[101010], hi[101010];
int dep[101010];

void dfs(int p, int rt, int d)
{
	dep[p] = d;
	for (int q : graph[p]) if (q != rt) {
		dfs(q, p, d + 1);
		low[p] = max(low[p], low[q] - 1);
		hi[p] = min(hi[p], hi[q] + 1);
	}
}
void dfs2(int p, int rt)
{
	for (int q : graph[p]) if (q != rt) {
		low[q] = max(low[q], low[p] - 1);
		hi[q] = min(hi[q], hi[p] + 1);
		dfs2(q, p);
	}
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N - 1; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	for (int i = 0; i < N; ++i) {
		X[i] = -INFT;
		low[i] = -INFT;
		hi[i] = INFT;
	}
 
	int K;
	scanf("%d", &K);
	for (; K--;) {
		int v, p;
		scanf("%d%d", &v, &p);
		--v;
 
		X[v] = low[v] = hi[v] = p;
	}
	dfs(0, -1, 0);
	dfs2(0, -1);
 
	int par = -1;
	for (int i = 0; i < N; ++i) {
		if (X[i] != -INFT) {
			int myp = (X[i] ^ dep[i]) & 1;
			if (par == -1) par = myp;
			if (par != myp) {
				puts("No");
				return 0;
			}
		}
		if (low[i] > hi[i]) {
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	for (int i = 0; i < N; ++i) printf("%d\n", low[i]);
 
	return 0;
}

Measured memory_bytes: 15744
def main4():
    lis = []
    n,k=map(int, input().split())
    for i in range(n):
        a,b = map(int, input().split())
        lis.append([a,b])
    lis.sort(key = lambda x:x[0])
    res = 0
    i=-1
    while(res < k):
        i+=1
        res += lis[i][1]
        if(res>=k):
            print(lis[i][0])
            break


if __name__ == '__main__':
    main4()


Measured memory_bytes: 25544
#include<stdio.h>
#include<algorithm>
using namespace std;
short dp[5010][60][60];
int g[60][60];
int n;
int solve(int a,int b,int c){
	if(dp[a][b][c]>=0)return dp[a][b][c];
	if(b==c)return dp[a][b][c]=a;
	if(a==2*n){
		return dp[a][b][c]=a;
	}
	if(a%2==0){
		int ret=0;
		for(int i=0;i<n;i++){
			if(g[b][i]){
				ret=max(ret,solve(a+1,i,c));
			}
		}
	//	printf("%d %d %d: %d\n",a,b,c,ret);
		return dp[a][b][c]=ret;
	}else{
		int ret=2*n;
		for(int i=0;i<n;i++){
			if(g[c][i])ret=min(ret,solve(a+1,b,i));
		}
	//	printf("%d %d %d: %d\n",a,b,c,ret);
		return dp[a][b][c]=ret;
	}
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int a;scanf("%d",&a);
		n=a;
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)scanf("%d",&g[i][j]);
		for(int i=0;i<=2*a;i++)for(int j=0;j<a;j++)for(int k=0;k<a;k++)dp[i][j][k]=-1;
		for(int i=0;i<a;i++)g[i][i]=1;
		int s,t;scanf("%d%d",&s,&t);
		solve(0,s,t);
		int ret=solve(0,s,t)/2;
		if(ret==a)printf("infinity\n");
		else printf("%d\n",ret);
	}
}

Measured memory_bytes: 1764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod=1000000007;

int main(){
    int n,m;cin>>n>>m;
    int a[m];rep(i,m)cin>>a[i];
    int cur=0;
    int isOK=1;
    ll ans=1;
    rep(i,m-1){
        if(a[i+1]-a[i]==1){
            isOK=0;
            break;
        }
    }
    int fib[100001];
    fib[0]=1;
    fib[1]=1;fib[2]=2;
    rep(i,99999)fib[i+3]=(fib[i+2]+fib[i+1])%mod;
    if(isOK){
        rep(i,m){
            ans*=fib[a[i]-1-cur]%mod;

            ans%=mod;
            cur=a[i]+1;

        }
        ans*=fib[n-cur]%mod;
        ans%=mod;
        cout<<ans<<endl;
    }
    else cout<<0<<endl;
}




Measured memory_bytes: 1024
a,b,c=map(int,input().split())
k=int(input())
cnt=0
for i in range(k):
    if b>a:
        break
    else:
        b*=2
        cnt+=1
for i in range(k):
    if c>b:
        break
    else:
        c*=2
        cnt+=1

#print(a,b,c)

if cnt>k or c<=b or a>=b:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 9136
s = input()
k = int(input())
lst = []
start = 0
end = 1
while start < len(s):
    while end - start <= 5:
        lst.append(s[start:end])
        end += 1
    start += 1
    end = start +1
lst.append(s[-1])

print(sorted(list(set(lst)))[k-1])

Measured memory_bytes: 40304
unittest
{
	assert( [ "4 3", "4 3 -4 -2" ].parse.expand.solve == -8 );		// 追加ケース
	assert( [ "10 40", "-5 -4 -3 -2 1 0 0 0 0 0" ].parse.expand.solve == 6 );		// 追加ケース
	
	assert( [ "4 3", "3 3 -4 -2" ].parse.expand.solve == -6 );
	assert( [ "10 40", "5 4 3 2 -1 0 0 0 0 0" ].parse.expand.solve == 6 );
	assert( [ "30 413", "-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0" ].parse.expand.solve == 448283280358331064 );
	
	assert( ( [ "200000 19999900000" ] ~ iota( 1, 200001 ).map!( ( a ) => a.to!( string ) ).join( " " ) ).parse.expand.solve == 39999800000 );		// 追加ケース
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nk = input.front.split.to!( long[] );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( nk[ 1 ], as );
}

auto solve( long k, long[] as )
{
	// マイナス、ゼロ、プラスに分類
	auto as_s = as.sort();
	auto ts = as_s.trisect( 0 );
	auto ms = ts[ 0 ].retro.array;
	auto zs = ts[ 1 ];
	auto ps = ts[ 2 ].array;
	
	// 積がマイナス、ゼロ、プラスになるペアの数を計算
	auto mc = ms.length.signed * ps.length.signed;
	auto pc = ms.length.signed * ( ms.length.signed - 1 ) / 2 + ps.length.signed * ( ps.length.signed - 1 ) / 2;
	auto zc = as.length.signed * ( as.length.signed - 1 ) / 2 - mc - pc;
	
	// 積がマイナスになるペア (m,p) の場合
	if( k <= mc )
	{
		auto minusK( long x )
		{
			auto t = 0L;
			auto i = 0L;
			foreach_reverse( j, m; ms )
			{
				while( i < ps.length && x < m * ps[ i ] ) i++;
				t += ps.length.signed - i;
			}
			return ( k <= t );
		}
		return bisect!minusK( -10L ^^ 18, 0L );
	}
	k -= mc;
	
	// 積がゼロになるペア (z,m)or(z,z)or(z,p) の場合
	if( k <= zc ) return 0;
	k -= zc;
	
	// 積がプラスになるペア (m,m)or(p,p) の場合
	auto plusK( long x )
	{
		auto t = 0L;
		auto i = 0L;
		foreach_reverse( j, m; ms )
		{
			while( i < ms.length && m * ms[ i ] <= x ) i++;
			t += i - ( j < i );		// (自分,自分)のペアは除外
		}
		i = 0L;
		foreach_reverse( j, p; ps )
		{
			while( i < ps.length && p * ps[ i ] <= x ) i++;
			t += i - ( j < i );		// (自分,自分)のペアは除外

		}
		t /= 2;		// (x,y)と(y,x)で二重カウントしているので半分除外
		return ( k <= t );
	}
	return bisect!plusK( 0L, 10L ^^ 18 );
}

// 二分法
auto bisect( alias pred, Element )( Element ng, Element ok, Element e = 10 ^^ 0 )
if( is( typeof( pred( ng ) ) : bool ) )
{
	import std.math : abs;
	
	while( e < abs( ok - ng ) )
	{
		auto x = ( ok + ng ) / 2;
		if( pred( x ) ) ok = x;
		else            ng = x;
	}
	return ok;
}


Measured memory_bytes: 11592
gets
seq = gets.split.map(&:to_i)

count = 0

(seq.size - 1).times do |i|
	(seq.size - 1).downto(i + 1) do |j|
		if seq[j] < seq[j - 1]
			seq[j - 1], seq[j] = seq[j], seq[j - 1]
			count += 1
		end
	end
end

puts seq.join(' ')
p count

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


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
#define all(v) v.begin(),v.end()
#define endl "\n"
#define clr(n, r) memset(n,r,sizeof(n));

void fast() {
    cin.tie(0);
    cin.sync_with_stdio(0);
}
    ll ans[10];
map<pair<ll,ll>,bool>blacked;
ll h,w,n;
map<pair<ll,ll>,ll>checked;


int main() {
    fast();
    cin>>h>>w>>n;
    for (ll i = 0; i <n ; ++i) {
        ll a,b;cin>>a>>b;
        blacked[{a,b}]=true;
    }
    for(auto it : blacked){
        ll i=it.first.first;
        ll j=it.first.second;
        for (ll k = -2; k <=0 ; ++k) {
            for (ll l = -2; l <=0 ; ++l) {
                ll a=i+k;
                ll b=j+l;
                if(a>=1&&a<=h&&a+2<=h&&b>=1&&b<=w&&b+2<=w)checked[{a,b}]++;
            }
        }
    }
    ans[0]=(h-2)*(w-2);
    for(auto it:checked){
        ans[it.second]++;
    }
    for (ll i1 = 1; i1 <10 ; ++i1) {
        ans[0]-=ans[i1];
    }
    for (ll m = 0; m <10 ; ++m) {
        cout<<ans[m]<<endl;
    }
}

Measured memory_bytes: 62848
#include<iostream>
#define ck(a,b) 0<=a&&a<b
#define enws(a) (a=='E'||a=='N'||a=='W'||a=='S')
#define dir(a) (a!='E'?a!='N'?a!='W'?3:2:1:0)
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int main(){
	int w,h,t,rest;char m[31][31],nm[31][31];
	while(cin>>w>>h,w){
		rest=0;
		rep(i,h){
			cin>>m[i];
			rep(j,w)if(enws(m[i][j]))rest++;
		}
		for(t=0;rest&&t<181;t++){
			rep(i,h)rep(j,w){
				if(enws(m[i][j])){
					int cd=dir(m[i][j]),nd,ny,nx;
					rep(d,4){
						nd=cd+d+3&3;
						ny=i+dy[nd],nx=j+dx[nd];
						if(ck(ny,h)&&ck(nx,w)&&(m[ny][nx]=='.'||m[ny][nx]=='X')){
							m[i][j]="ENWS"[nd]; break;
						}
					}
				}
				nm[i][j]=m[i][j];
			}
			rep(i,h)rep(j,w)if(m[i][j]=='.'||m[i][j]=='X'){
				rep(d,4){
					int ny=i+dy[d],nx=j+dx[d];
					if(ck(ny,h)&&ck(nx,w)&&m[ny][nx]=="WSEN"[d]){
						if(m[i][j]=='.')nm[i][j]=m[ny][nx];
						else rest--;
						nm[ny][nx]='.';
						break;
					}
				}
			}
			rep(i,h)rep(j,w)m[i][j]=nm[i][j];
		}
		if(t<=180)cout<<t<<endl;
		else cout<<"NA"<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map> 
#include<vector>
#include<queue>
#include<set>
#include<bits/stdc++.h>
#include<deque> 
#include<bitset>
#include<string>
#define N 40
#define K 300005
#define MOD 1e9+7
#define int long long 
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int max(int a, int b){
    if(a>b)
        return a;
    return b;
}

int32_t main(){
	int n, k;
	cin>>n>>k;
	int a[n+1];
    a[0] = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    //exit(0);
	int dp[n+2];
    dp[0] = 0;
	dp[1] = 0;
	for(int i=2;i<=n;i++){
		int ans = INT_MAX;
		for(int j = i-1; j>= max(1, i-k); j--){
			ans = min(ans, dp[j] + abs(a[i] - a[j]));
		}
		dp[i] = ans;
        //cout<<i<<" "<<dp[i]<<endl;
	}
	cout<<dp[n]<<endl;
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n, m) for (int (i) = (n); (i) < (m); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

struct edge {
   ll to, cost;
};

const ll INF = 1e18;
ll N, M, dist[1010];
vec<edge> G[3000];

bool bellman() {
   for (int i = 0; i < N; i++) {
      dist[i] = INF;
   }
   dist[0] = 0;
   for (int k = 0; k < N*2; k++) {
      for (int i = 0; i < N; i++) {
         for (edge e : G[i]) {
            if (dist[i] != INF && dist[e.to] > dist[i] + e.cost) {
               dist[e.to] = dist[i] + e.cost;
               if (e.to==N-1 && k>N) return true;
            }
         }
      }
   }
   return false;
}

int main() {
   cin >> N >> M;
   for (int i = 0; i < M; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      a--, b--;
      G[a].push_back(edge{b, -c});
   }

   if (bellman()) {
      puts("inf");
   } else {
      cout << -dist[N-1] << endl;
   }

   return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <algorithm>
#include <array>
#include <string>
#include <utility>
#include <vector>

int main() {
  size_t n;
  scanf("%zu", &n);

  std::array<int, 3> a;
  for (auto& ai: a) scanf("%d", &ai);

  std::vector<std::pair<size_t, size_t>> s;
  s.reserve(n);
  for (size_t i = 0; i < n; ++i) {
    char buf[4];
    scanf("%s", buf);
    std::string q = buf;
    if (q == "AB") s.emplace_back(0, 1);
    if (q == "AC") s.emplace_back(0, 2);
    if (q == "BC") s.emplace_back(1, 2);
  }

  std::vector<int> res;
  res.reserve(n);

  auto push = [&](size_t u, size_t v) {
    res.push_back(u);
    ++a[u], --a[v];
  };

  for (size_t i = 0; i < n; ++i) {
    auto [u, v] = s[i];
    if (a[u] == 0 && a[v] == 0) return puts("No"), 0;

    if (a[u] < a[v]) {
      push(u, v);
    } else if (a[u] > a[v]) {
      push(v, u);
    } else if (i+1 < n) {
      if (s[i] == s[i+1]) {
        push(u, v);
      } else {
        size_t w = u ^ v ^ s[i+1].first ^ s[i+1].second;
        if ((w ^ u) == 3) {
          push(u, v);
        } else {
          push(v, u);
        }
      }
    } else {
      push(u, v);
    }
  }

  puts("Yes");
  for (auto c: res) printf("%c\n", 'A'+c);
}


Measured memory_bytes: 4720
#include<iostream>
using namespace std;
int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if(a == b && b == c) cout << "No" << endl;
	else if(a == b || b == c || a == c) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;
    int min = A*X + B*Y; 
    for(int k=0; k<=2*max(X,Y); k+=2){
        if(A*(X-k/2) < 0) A = 0;
        if(B*(Y-k/2) < 0) B = 0;
        if(min > C*k + A*(X-k/2) + B*(Y-k/2)){
            min =  C*k + A*(X-k/2) + B*(Y-k/2);
        }
    }
    cout << min << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adjs[a - 1].append((b - 1, c))
        adjs[b - 1].append((a - 1, c))
    q, k = map(int, input().split())

    # DFS
    dist = [None] * n
    dist[k - 1] = 0
    hq = [(0, k - 1)]
    queued = [False] * n
    queued[k - 1] = True
    while hq:
        d, j = hq.pop()
        dist[j] = d
        for j2, d2 in adjs[j]:
            if queued[j2]:
                continue
            hq.append((d + d2, j2))
            queued[j2] = True

    # For each query
    for i in range(q):
        x, y = map(int, input().split())
        print(dist[x - 1] + dist[y - 1])

if __name__ == "__main__":
    main()


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

class Main {
    public static void main(String... args) {
        int H = IN.nextInt();
		int W = IN.nextInt();
		boolean[][] G = new boolean[H + 1][W + 1];
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				G[i][j] = IN.nextInt() % 2 == 1;
			}
		}

		List<String> log = new ArrayList<>();
        for (int i = 1; i < H; i++) {
			for (int j = 0; j <= W; j++) {
                if (G[i][j]) {
					G[i + 1][j] = !G[i + 1][j];
					log.add(i + " " + j + " " + (i + 1) + " " + j);
				}
			}
		}

		for (int j = 1; j < W; j++) {
			if (G[H][j]) {
				G[H][j + 1] = !G[H][j + 1];
				log.add(H + " " + j + " " + H + " " + (j + 1));
			}
		}
        puts(log.size());
		for (String line: log) {
			puts(line);
		}
		flush();
	}
    static final Scanner IN = new Scanner(System.in);
	static final PrintWriter OUT = new PrintWriter(System.out);
	static <T> void puts(T arg) { OUT.println(arg); }
	static void flush() { OUT.flush(); }
}


Measured memory_bytes: 97820
#include<stdio.h>
main()
{
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
 if (a-c>=0 && a-c<=d || c-a>=0 && c-a<=d)
printf("Yes");
else  if (a-b>=0 && a-b<=d || b-a>=0 && b-a<=d)
{
	 if (b-c>=0 && b-c<=d || c-b>=0 && c-b<=d)
printf("Yes");
else
printf("No");
}
else
printf("No");
 return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define FAST_IO   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define Relocate freopen("./in.txt","r",stdin);freopen("./out.txt","w",stdout)
#define up(mi,a,b) for(mi=a;mi<=b;++mi)
#define down(mi,b,a) for(mi=b;mi>=a;--mi)
#define mfill(a,v) memset(a,v,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 5005
#define v_n 5005
#define LL long long
#define e_n 5000005
#define MOD 1000000007
#define eps 0.000000001
#define Blen 32
using namespace std;
int main(void)
{
	int i, j, k;
	FAST_IO;
	//Relocate;
	int val;
	cin >> val;
	int a = val % 100;
	int b = val / 100;
	int cnt = 0;
	bool gg = 0;
	if (a >= 1 && a <= 12)
	{
		cnt++;
		gg = 1;
	}
	if (b >= 1 && b <= 12)
	{
		cnt++;
	}
	if (cnt == 2)
	{
		cout << "AMBIGUOUS\n";
	}
	else if (cnt == 1)
	{
		if (gg)
			cout << "YYMM\n";
		else
			cout << "MMYY\n";
	}
	else
	{
		cout << "NA\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void)
{
  int L,R,d;
  int val=0;
  cin>>L>>R>>d;
  for(int i=L;i<=R;i++)
  {
    if(i%d==0)
    {
      val++;
    }
  }
  cout<<val;
}

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

struct Union_Find
{
	int n;
	vector<int> tree;

	Union_Find(int n) : n(n), tree(n, -1)
	{
	}

	int size(int x)
	{
		assert(0 <= x && x < n);
		return -tree[root(x)];
	}

	int root(int x)
	{
		assert(0 <= x && x < n);
		if (tree[x] < 0)
		{
			return x;
		}
		return tree[x] = root(tree[x]);
	}

	bool same(int x, int y)
	{
		assert(0 <= x && x < n && 0 <= y && y < n);
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		assert(0 <= x && x < n && 0 <= y && y < n);
		x = root(x);
		y = root(y);
		if (x == y)
		{
			return false;
		}
		if (tree[x] > tree[y])
		{
			swap(x, y);
		}
		tree[x] += tree[y];
		tree[y] = x;
		return true;
	}
};

int main()
{
	int64_t n, m;
	cin >> n >> m;
	vector<int64_t> as(m), bs(m);
	for (int64_t i = 0; i < m; i++)
	{
		cin >> as[i] >> bs[i];
		as[i]--;
		bs[i]--;
	}

	Union_Find uf(n);
	for (int64_t i = 0; i < m; i++)
	{
		uf.merge(as[i], bs[i]);
	}

	int ans = 0;
	for (int sz : uf.tree)
	{
		ans = max(ans, -sz);
	}

	cout << ans << endl;

	return 0;
}

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

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

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

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

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

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

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

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

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

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

use std::cmp::{min, max};

fn main() {
    input!{
        a: usize,
        b: usize,
        c: usize,
        d: usize
    }
    println!("{}", count2(b, c, d) - count2(a - 1, c, d));
}

fn count2(n: usize, a: usize, b: usize) -> usize {
    n + n / lcm(a, b) - n / a - n / b
}

fn gcd(n: usize, m: usize) -> usize {
    let mut l = min(n, m);
    let mut r = max(n, m);
    while l > 0 {
        let t = l;
        l = r % l;
        r = t;
    }
    r
}

fn lcm(n: usize, m: usize) -> usize {
    n / gcd(n, m) * m
}


Measured memory_bytes: 4352
// https://atcoder.jp/contests/abc175/tasks/abc175_c
#include <iostream>
#include <vector>
#include <deque>
#include <tuple>
#include <algorithm>
#include <iterator> // std::back_inserter
#include <climits>
#include <sstream>

using namespace std;
#define swap(x,y) do {auto tmp = x; x = y; y = tmp;} while(0)

typedef long ll;

int main()
{
    ll x;
    cin >> x;
    if (x == 0) {
        cout << 1 << endl;
    }
    else {
        cout << 0 << endl;
    }
}


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

int main(){
	char a,b;
  	cin >> a >> b;
  	if (a=='H' && b=='H')cout << "H" <<endl;
  	else if (a=='H' && b=='D')cout << "D" <<endl;
	else if (a=='D' && b=='H')cout << "D" <<endl;
	else cout << "H" <<endl;
}

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

n = int(n)

sort_a = sorted(a)


buka = []
boss_num = 1
buka_count = 0

i = 0
while boss_num < n:
    if i > n-2 and boss_num < n:
        buka.append(buka_count)
        buka_count = 0
        boss_num = boss_num + 1
    elif boss_num == sort_a[i]:
        buka_count = buka_count + 1
        i = i + 1
    elif boss_num != sort_a[i] and i <= n-2:
        buka.append(buka_count)
        boss_num = boss_num + 1
        buka_count = 0

buka.append(0)

for j in range(n):
    print(buka[j])

Measured memory_bytes: 32300
#include <iostream>
#include <vector>
#include <string>

using namespace std;

long long valid(const string& S, const string& r, const string& b){
    vector<vector<long long>> dp(r.size()+1, vector<long long>(b.size()+1, 0LL));
    dp[0][0] = 1;
    for(int i=0;i<=r.size();i++){
        for(int j=0;j<=b.size();j++){
            if(i < r.size() && r[i] == S[i+j]) dp[i+1][j] += dp[i][j];
            if(j < b.size() && b[j] == S[i+j]) dp[i][j+1] += dp[i][j];
        }
    }
    return dp[r.size()][b.size()];
}

int main(){
    int N; cin >> N;
    string S; cin >> S;
    string T;
    for(int i=2*N-1;i>=N;i--) T += S[i];
    long long res = 0;
    for(int i=0;i<(1<<N);i++){
        string r, b;
        for(int j=0;j<N;j++){
            if(i&(1<<j)) r += S[j];
            else b += S[j];
        }
        res += valid(T, r, b);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
($N,$C)=split$",<>;
@D=map[split$",<>],1..$C;
for(<>){
	$j=0;
	for$x(split){
		$k=($i+$j)%3;
		for(0..$C-1){
			$_[$k][$_]+=$D[$x-1][$_]
		}
		++$j
	}
	++$i
}
$y=1e18;
for$i(0..$C-1){
	for$j(0..$C-1){next if$i==$j;
		for$k(0..$C-1){next if$i==$k||$j==$k;
			$x=$_[0][$i]+$_[1][$j]+$_[2][$k];
			$y=$x if$x<$y
		}
	}
}
print$y


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

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N;
  cin >> N;

  map<char, ll> mp;
  for (int i = 0; i < N; i++) {
    string S;
    cin >> S;
    mp[S[0]]++;
  }

  ll ans = 0;
  for (int i = 0; i < 1 << 5; i++) {
    if (__builtin_popcount(i) != 3) continue;
    ll sub = 1;
    for (int j = 0; j < 5; j++) {
      if (i >> j & 1) sub *= mp["MARCH"[j]];
    }
    ans += sub;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i,j,k,a,b,s=0,s2=0;
    scanf("%d %d",&a,&b);
    int col[102][102];
    int c=0,sum[102][102];
    int sum2[102][102];

    for(i=1;i<=a;i++)
    {
        for(j=1;j<=b;j++)
        {
            scanf("%d",&col[i][j]);
            c=c+col[i][j];

        }
        sum[i][j]= c;
        c=0;

    }
    for(i=1;i<=a;i++)
    {
        for(j=1;j<=b;j++)
        {
           printf("%d ",col[i][j]);
        }
        printf("%d\n",sum[i][j]);
        s2=s2+sum[i][j];
    }


  for(i=1;i<=b;i++)
    {
        for(j=1;j<=a;j++)
        {
          s=s+col[j][i];

        }
        sum2[j][i]=s;
        s=0;
        printf("%d ",sum2[j][i]);
    }
    printf("%d\n",s2);
return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[3][3];
    rep(i, 3)rep(j, 3) cin >> a[i][j];
    int n;
    cin >> n;
    int ana[101] = {0};
    rep(i, n){
        int b;
        cin >> b;
        ana[b] = 1;
    }
    rep(i, 3){
        bool flag = true;
        rep(j, 3){
            if (ana[a[i][j]]!=1){
                flag = false;
                break;
            }
        }
        if (flag){
            cout << "Yes" << endl;
            return 0;
        }

        flag = true;
        rep(j, 3){
            if (ana[a[j][i]]!=1){
                flag = false;
                break;
            }
        }
        if (flag){
            cout << "Yes" << endl;
            return 0;
        }
    }
    if (ana[a[0][0]] and ana[a[1][1]] and ana[a[2][2]]){
        cout << "Yes" << endl;
        return 0;
    }
    if (ana[a[0][2]] and ana[a[1][1]] and ana[a[2][0]]){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x) x.begin(), x.end()
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
#define endl '\n'
#ifndef YDK
#define eprintf(...)
#endif
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr const int INF  = 0x3f3f3f3f;
constexpr const i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr const int MOD  = int(1e9) + 7;
// }}}

// Library {{{
template<class Container, class InputIt>
Container countTable(InputIt first, InputIt last)
{
    Container cnt;
    for (; first != last; ++first) { ++cnt[*first]; }
    return cnt;
}
// }}}


signed main()
{
    string w;
    cin >> w;

    auto cnt = countTable<map<int,int>>(ALL(w));

    bool ok = true;
    for (auto e : cnt) {
        if (e.second & 1) ok = false;
    }

    cout << ((ok) ? "Yes" : "No") << endl;

    return 0;
}


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

// ABC095A - Something on It
int main(){
  string s;
  cin >> s;
  int top = 0;
  if (s[0] == 'o') { top++; }
  if (s[1] == 'o') { top++; }
  if (s[2] == 'o') { top++; }

  cout << (700 + top * 100) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n, num, sum, mass[11][11];
	int i, j;
	
	while (scanf("%d", &n), n != 0){
		for (i = 0; i < 11; i++){
			for (j = 0; j < 11; j++){
				mass[i][j] = 0;
			}
		}
		
		for (i = 0; i < n; i++){
			for (j = 0; j < n; j++){
				scanf("%d", &mass[i][j]);
				mass[i][n] += mass[i][j];
				mass[n][j] += mass[i][j];
			}
			mass[n][n] += mass[i][n];
		}
		
		for (i = 0; i <= n; i++){
			for (j = 0; j <= n; j++){
				printf("%5d", mass[i][j]);
			}
			printf("\n");
		}
	}
	return (0);
}

Measured memory_bytes: 612
const main = input => {
  const [A, B, C, D] = input.trim().split(' ').map(x => parseInt(x))
  if (A + B > C + D) {
    console.log('Left')
  } else if (A + B < C + D) {
    console.log('Right')
  } else {
    console.log('Balanced')
  }
}
// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


Measured memory_bytes: 30560
#include <stdio.h>
int main(void)
{
    int i,sum;
    char num[1000];
    while(1){
        scanf("%s",num);
        sum=0;
        i=0;
        while(num[i] != '\0'){
            sum+=num[i]-'0';
            i++;
        }
        if(sum==0) break;
        printf("%d\n",sum);
    }
    return 0;
}

Measured memory_bytes: 536
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,-1,sizeof(i));
#define pb push_back
vector<int>g[10005];
int v[10005];
multiset<int>st;
void dfs(int now,int pre){
	v[now] = *(--st.end());
	st.erase(--st.end());
	for(auto i:g[now]){
		if(i!=pre){
			dfs(i,now);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	while(cin >> n){
		f(n-1){
			int add1,add2;
			cin >> add1 >> add2;
			g[add1].pb(add2);
			g[add2].pb(add1);
		}
		ll sum = 0;
		int mx = 0;
		f(n){
			int add;
			cin >> add;
			sum += add;
			mx = max(mx,add);
			st.insert(add);
		}
		sum -= mx;
		dfs(1,0);
		cout << sum <<endl;
		f1(n){
			cout << v[i] << ' ';
		}
		cout << endl;
	}
	
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin >> s;
    
    int ans = s.size();
    
    for (int i = 0; i < 2; i++){
        int cnt = 0;
        for (int j = 0; j < s.size(); j++){
            if (j % 2 == 0 && s[j] != (char)(i + '0')) cnt++;
            if (j % 2 != 0 && s[j] == (char)(i + '0')) cnt++;
        }
        ans = min(ans, cnt);
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 512
// Problem : A - Multiplication 1
// Contest : AtCoder - AtCoder Beginner Contest 169
// URL : https://atcoder.jp/contests/abc169/tasks/abc169_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define w cout
#define e '\n'
#define int long long
#define sz(x) (int)x.size()
#define re return 
#define vi vector<int>
#define vii vector<pair<int ,int > >
#define F first
#define S second
#define pussy push_back
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

const int N = 1e6 , mod = 1e9 + 7;

void solve() {
	int a, b; cin >> a >> b;w << a*b ;
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}	
}


Measured memory_bytes: 3652