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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

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

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<char>> s(h, vector<char>(w));
  int bc = 0;
  rep(i, h) {
    rep(j, w) {
      char x;
      cin >> x;
      s.at(i).at(j) = x;
      if (x == '#') {
        bc++;
      }
    }
  }
  vector<vector<int>> d(h, vector<int>(w, -1));
  d.at(0).at(0) = 0;
  queue<P> q;
  q.push(make_pair(0, 0));
  while (!q.empty()) {
    P c = q.front();
    q.pop();
    int cx = c.first;
    int cy = c.second;
    rep(i, 4) {
      int nx = cx + dx[i];
      int ny = cy + dy[i];
      if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
        continue;
      }
      if (s.at(ny).at(nx) == '#') {
        continue;
      }
      if (d.at(ny).at(nx) != -1) {
        continue;
      }
      d.at(ny).at(nx) = d.at(cy).at(cx) + 1;
      q.push(make_pair(nx, ny));
    }
  }
  int dist = d.at(h - 1).at(w - 1);
  if (dist == -1) {
    cout << -1 << endl;
    return 0;
  }
  int res = h * w - bc - (dist + 1);
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3648
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
}
int main()
{
    vok();
    ll n,k;
    IN n>>k;
    vll a(n);
    bitset<50> b[n];
    loop(i,0,n)
    {
        IN a[i];
        bitset<50> temp(a[i]);
        b[i]=temp;
    }
    bitset<50> ans(0);
    rloop(i,49,0)
    {
        int countt=0;
        loop(j,0,n)
        {
            if(b[j][i])
            {
                countt++;
            }
          	//cout<<"";
        }
        ans[i]=1;
        if((countt*2)<n && ans.to_ullong()<=k)
        {
            //Do Nothing
        }
        else
        {
            ans[i]=0;
        }
    }
    ll fans=0LL;
    ll X=ans.to_ullong();
    loop(i,0,n)
    {
      	//cout<<"";
        fans+=(X^a[i]);
    }
    OUT fans<<endl
    return 0;
}

Measured memory_bytes: 1792
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP          PIC X(399).
01 cur          PIC 9(10) VALUE 1.
01 i            PIC 9(18) VALUE 1.
01 j            PIC 9(18).
01 jix          PIC 9(18) VALUE 1.
01 len          PIC 9(10).
01 N            PIC 9(3).
01 NUM          PIC 9(1) VALUE 3.
01 nm           PIC 9(3).
01 ans          PIC Z(2)9.
01 flg          PIC 9(1) VALUE 0.
01 y1.
    03 y11 OCCURS 100 DEPENDING ON N.
        05 y    PIC S9(3) VALUE -1.
01 x1.
    03 x11 OCCURS 100 DEPENDING ON N.
        05 x    PIC S9(3) VALUE -1.
01 tate1.
    03 tate11 OCCURS 3.
        05 tate PIC 9(3) VALUE 0.
01 yoko1.
    03 yoko11 OCCURS 3.
        05 yoko PIC 9(3) VALUE 0.
01 naname1.
    03 naname11 OCCURS 2.
        05 naname   PIC 9(3) VALUE 0.

PROCEDURE                        DIVISION.
PERFORM NUM TIMES
    ACCEPT INP
    MOVE 1 TO cur
    MOVE 1 TO jix
    PERFORM NUM TIMES
        PERFORM VARYING j FROM cur BY 1 UNTIL INP(j:1) = SPACE
        END-PERFORM
        COMPUTE len = j - cur
        MOVE INP(cur:len) TO nm
        MOVE i TO y(nm)
        MOVE jix TO x(nm)
        COMPUTE cur = j + 1
        ADD 1 TO jix
    END-PERFORM
    ADD 1 TO i
END-PERFORM.
ACCEPT N.
PERFORM N TIMES
    ACCEPT nm
    IF y(nm) NOT = -1
        ADD 1 TO yoko(y(nm))
        IF NUM = yoko(y(nm))
            MOVE 1 TO flg
            EXIT PERFORM
        END-IF
        ADD 1 TO tate(x(nm))
        IF NUM = tate(x(nm))
            MOVE 1 TO flg
            EXIT PERFORM
        END-IF
        IF y(nm) = x(nm)
            ADD 1 TO naname(1)
            IF NUM = naname(1)
                MOVE 1 TO flg
                EXIT PERFORM
            END-IF
        END-IF
        IF y(nm) = NUM - x(nm) + 1
            ADD 1 TO naname(2)
            IF NUM = naname(2)
                MOVE 1 TO flg
                EXIT PERFORM
            END-IF
        END-IF
    END-IF
END-PERFORM.
IF flg = 1
    DISPLAY "Yes"
ELSE
    DISPLAY "No"
END-IF.
STOP RUN.


Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;


int main() {
	string s;
	cin >> s;
	int cnt[3];
	cnt[0] = cnt[1] = cnt[2] = 0;
	for(int i=0; i<s.size(); i++)
		cnt[s[i] - 'a'] ++;
	int maxim = max(cnt[0], max(cnt[1], cnt[2]));
	int minim = min(cnt[0], min(cnt[1], cnt[2]));
	//cout << minim << " " << maxim << endl;
	if(maxim - minim <= 1)
		cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

Measured memory_bytes: 512
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define INF 100000000
typedef long long ll;

int main(void) {
    int a, b;
    cin >> a >> b;
    while (1) {
//        if (a == 0 && b == 0) break;
        int flag = 0;
        for (int i = a; i <= b; i++) {
            if (i % 400 == 0) {
                cout << i << endl;
                flag = 1;
            } else if (i % 100 == 0) {
                /* do nothing */
            } else if (i % 4 == 0) {
                cout << i << endl;
                flag = 1;
            }
        }
        if (flag == 0) cout << "NA" << endl;
        cin >> a >> b;
        if (a == 0 && b == 0) break;
        cout << endl;
    }
    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> v(100, 0);
    for (int i = 0; i < K; i++)
    {
        int d;
        cin >> d;
        rep(i, d)
        {
            int a;
            cin >> a;
            a--;
            v[a]++;
        }
    }
    int ans = 0;
    rep(i, N)
    {
        if (!v[i])
            ans++;
    }

    cout << ans << endl;

    return 0;
}

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

int main() {
  string s; cin >> s;
  vector<int> runs;
  for (int i = 0; i < int(s.size()); ) {
    int j = i;
    while (j < int(s.size()) && s[j] == s[i]) j++;
    runs.push_back(j-i);
    i = j;
  }
  for (int i = 0; i < int(runs.size()); i += 2) {
    for (int z = 0; z < runs[i]-1; z++) cout << 0 << ' ';
    cout << (runs[i]+1)/2+(runs[i+1])/2 << ' ';
    cout << (runs[i])/2 + (runs[i+1]+1)/2 << ' ';
    for (int z = 0; z < runs[i+1]-1; z++) cout << 0 << ' ';
  }
  cout << '\n';
}

Measured memory_bytes: 1144
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string str;
	cin>>str;
	if(str=="ABC")puts("ARC");
	else puts("ABC"); 
	return 0;
}

Measured memory_bytes: 3572
from collections import Counter
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, k = LI()
a = LI()
c = Counter(a)
l = sorted(c.items(), key=lambda x: x[1])
types = len(l)
if types <= k:
    print(0)
    sys.exit()
ans = 0
i = 0
while types > k:
    ans += l[i][1]
    i += 1
    types -= 1
print(ans)


Measured memory_bytes: 44236
W,H,N = map(int,input().split())

a1,a2,a3,a4 = -1,101,-1,101
for i in range(N):
  x,y,a = map(int,input().split())
  if a == 1:
    a1 = max(a1,x)
  elif a == 2:
    a2 = min(a2,x-1)
  elif a == 3:
    a3 = max(a3,y)
  else:
    a4 = min(a4,y-1)
    
mass = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if i < a3 or a4 < i:
      mass[i][j] += 1
    if j < a1 or a2 < j:
      mass[i][j] += 1
      
cnt = 0
for k in mass:
  cnt += k.count(0)
  
print(cnt)

Measured memory_bytes: 9240
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int x[4], y[4];
	for(int i=0; i<2; i++){
		cin >> x[i] >> y[i];
	}
	for(int i=2; i<4; i++){
		x[i]=x[i-1]+y[i-2]-y[i-1];
		y[i]=y[i-1]-x[i-2]+x[i-1];
	}
	cout << x[2] << " " << y[2] << " " << x[3] << " " << y[3] <<endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int q = Integer.parseInt(sa[1]);
		sa = br.readLine().split(" ");
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sa[i]);
		}

		long[] b = new long[n + 1];
		long[] c = new long[n + 1];
		System.arraycopy(a, 0, b, 1, n);
		System.arraycopy(a, 0, c, 1, n);
		b[1] += b[0];
		for (int i = 2; i <= n; i++) {
			b[i] += b[i - 1];
			c[i] += c[i - 2];
		}

		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			int x = Integer.parseInt(br.readLine());
			int ok = n - 1;
			int ng = 0;

			while (Math.abs(ok - ng) > 1) {
				int mid = (ok + ng) / 2;
				if (judge(a, x, mid)) {
					ok = mid;
				} else {
					ng = mid;
				}
			}

			long ans = b[n] - b[ok];
			int cnt = n - ok;
			if (cnt <= n / 2) {
				ans += c[n - cnt * 2];
			}
			pw.println(ans);
		}
		br.close();
		pw.flush();
	}

	static boolean judge(long[] a, int x, int mid) {
		int cnt = a.length - mid;
		int left = mid - cnt + 1;
		if (left < 0 || x - a[left] > a[mid] - x) {
			return false;
		}
		return true;
	}
}


Measured memory_bytes: 54916
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final int K = sc.nextInt();
		
			long[] hs = new long[N];
			for(int i = 0; i < N; i++) {
				hs[i] = sc.nextLong();
			}
			Arrays.sort(hs);
			
			for(int i = 0; i < Math.min(N, K); i++) {
				hs[(N - 1) - i] = 0;
			}
			
			final long sum = Arrays.stream(hs).sum();
			System.out.println(sum);
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 53240
#include <stdio.h>
int main(void){
	int i,n,k,ans=0;
	scanf("%d%d",&n,&k);
	int h[n+1];
	for(i=0;i<n;i++){
		scanf("%d",&h[i]);
		if(h[i]>=k) ans++;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

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

		String a_str = scanner.next();
		String b_str = scanner.next();

		int a = Integer.parseInt(a_str);
		int b = Integer.parseInt(b_str);

		if(a >= -1000 && b <= 1000) {
			System.out.print("a");
			if(a > b) {
				System.out.print(" > ");
			}
			if(a < b) {
				System.out.print(" < ");
			}
			if(a == b) {
				System.out.print(" == ");
			}
			System.out.println("b");
		}

    	scanner.close();
    }
}


Measured memory_bytes: 25940
#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int S[n];
    for(int i=0; i<n; i++)  scanf("%d",&S[i]);
    int q;
    scanf("%d",&q);
    int t;
    int count=0;
    for(int i=0; i<q; i++){
        scanf("%d",&t);
        int left=0;
        int right=n;
        while(right>left){
            int middle=(right+left)/2;
            if(t>S[middle]){
                left=middle+1;
            }
            else if(t<S[middle]){
                right=middle;
            }
            else{
                count++;
                break;
            }
        }
    }
    printf("%d\n",count);
}



Measured memory_bytes: 2972
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include<stack>
#include<tuple>
using namespace std;
#define INF 1100000000000
#define MAX 1100000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<pair<int,int>,int> p;
typedef pair< pair<int,int>, int> p; 
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

ll dp[3100][6100][2];

int main(){
    int N,T,A[3100],B[3100]; cin>>N>>T;
    for(int i=0;i<N;i++) cin>>A[i]>>B[i];
    for(int i=0;i<N;i++){
        for(int j=0;j<=T;j++){
            for(int k=0;k<2;k++){
                if(k==1){
                    dp[i+1][j][k]=max(dp[i][j][k],dp[i+1][j][k]);
                    dp[i+1][j+A[i]][k]=max(dp[i][j][k]+B[i],dp[i+1][j+A[i]][k]);
                }else{
                    dp[i+1][j][k]=max(dp[i][j][k],dp[i+1][j][k]);
                    dp[i+1][j][1]=max(dp[i][j][k]+B[i],dp[i+1][j][1]);
                    dp[i+1][j+A[i]][k]=max(dp[i][j][k]+B[i],dp[i+1][j+A[i]][k]);
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<T;i++){
        for(int j=0;j<2;j++)
            ans=max(ans,dp[N][i][j]);
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 286976
import heapq


n, k = map(int, input().split())
hs = list(zip(sorted([int(input()) for _ in range(n)]),
              range(n)))
minus_hs = []
for i in range(n):
    minus_hs.append((-hs[i][0], hs[i][1]))

q = hs[:k - 1][:]
heapq.heapify(q)
minus_q = minus_hs[:k - 1][:]
heapq.heapify(minus_q)

min_diff = float('inf')
for i in range(k - 1, n):
    heapq.heappush(q, hs[i])
    heapq.heappush(minus_q, minus_hs[i])
    while q[0][1] < i - k + 1:
        heapq.heappop(q)
    while minus_q[0][1] < i - k + 1:
        heapq.heappop(minus_q)
    min_diff = min(min_diff, abs(q[0][0] + minus_q[0][0]))
print(min_diff)


Measured memory_bytes: 30236
a = int(input());b = int(input());c = int(input());x = int(input())
s = 0
counter = 0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      s = 500*i + 100*j + 50*k
      if s == x:
        counter += 1

print(counter)

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

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }



int n;
int a[15][15];

int main() {
    while (cin >> n) {
        if (n == 0) break;
        memset(a, 0, sizeof(a));
        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = 0; j < n; ++j) {cin >> a[i][j]; sum += a[i][j]; }
            a[i][n] = sum;
        }
        for (int i = 0; i < n; ++i) for (int j = 0; j <= n; ++j) a[n][j] += a[i][j];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                cout << setw(5) << a[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1172
#include <bits/stdc++.h>
using namespace std;
int main(){
long long int n,ans=1;
  cin >> n;
  long long int a[n];
  int ant=0;
  cin >> a[0];
  cin >> a[1];
  if (a[1]>a[0])ant=1;
  if (a[1]<a[0])ant=-1; 
  for (int i=2;i<n;i++){
    cin >> a[i];
    if (a[i]>a[i-1]){
      if (ant==0)ant=1;
      if (ant==-1)ans++,ant=0;
    }
    if (a[i]<a[i-1]){
      if (ant==0)ant=-1;
      if (ant==1)ans++,ant=0;
    }
   }
   cout << ans <<endl; 
}


Measured memory_bytes: 1024
data = gets
data = data.split(" ")
W = data[0].to_i
H = data[1].to_i
x = data[2].to_i
y = data[3].to_i
r = data[4].to_i
if x - r < 0 or x + r > W or y - r < 0 or y + r > H
	puts "No"
else
	puts "Yes"
end

Measured memory_bytes: 8688
require 'matrix'
H, W = gets.split.map(&:to_i)
h, w = gets.split.map(&:to_i)
matrix = Matrix.build(H, W) { |i, j| (i <= (h-1) || j <= (w-1)) ? 1 : 0 }
puts matrix.select { |e| e == 0 }.size

Measured memory_bytes: 2556
#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int main(){
  int n;
  while(cin >> n,n){
    int p[50],t[50];
    int i,j,k;
    p[0]=0;t[0]=0;
    for(i=1;i<=n;i++){
      cin >> p[i] >> t[i];
    }
    int dp[50][4];
    int inf = 1<<20;
    fill(dp[0],dp[49],inf);
    dp[0][0]=0;
    for(i=0;i<n;i++){
      for(j=0;j<3;j++){
	if(dp[i][j]==inf) continue;
	//cout << (j+1)*(t[i+1]-t[i]) << ":" << abs(p[i+1]-p[i]) <<endl;
	if((t[i+1]-t[i]) >= abs(p[i+1]-p[i])*(j+1))
	  dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+abs(p[i+1]-p[i]));
      }
      for(j=1;j<4;j++){
	if(dp[i][j]==inf) continue;
	//cout << i << j << endl;
	//cout << p[i]*(j+1)+p[i+1]<<":"<<(t[i+1]-t[i]) << endl;
	if(p[i]*(j+1)+p[i+1]<=(t[i+1]-t[i]))
	  dp[i+1][1]=min(dp[i+1][1],dp[i][j]+p[i]+p[i+1]);
      }
    }
    
    for(j=1;j<4;j++){
      if(dp[n][j]==inf) continue;
      dp[n+1][j]=min(dp[n+1][j],dp[n][j]+p[n]);
    }
    
    int o=inf;
    for(i=0;i<4;i++) {
      //cout << dp[n+1][i] << ":";
      o=min(o,dp[n+1][i]);
    }

    bool f=!true;
    if(f){
      for(i=1;i<=n+1;i++){
	cout << i << ":" ;
	for(j=0;j<4;j++) cout << dp[i][j] << ":";
	cout << endl;
      }
    }
    
    if(o<inf){
      cout << "OK " << o << endl;
    }else{
      k=1;
      for(j=1;j<=n;j++){
	o=inf;
	for(i=0;i<4;i++) {
	  o=min(o,dp[j][i]);
	}
	if(o==inf){
	  k=j;
	  break;
	}
      }
      cout << "NG " << k <<  endl;
    }
  }
  return 0;
}

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

int main()
{
    long long n1, n2;
    char op;
    cin >> n1 >> op >> n2;
    if(op == '+') cout << n1+n2 << endl;
    else cout << n1-n2 << endl;
    return 0;
}

Measured memory_bytes: 3504
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define in2(a,b) scanf("%lld %lld",&(a),&(b))
#define in3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define ind(a) scanf("%lf", &(a))
#define ins(a) scanf("%s", (a))
#define inc(a) scanf("%c", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//      puts(a) printf("%s\n", a) 文字はこっち
//your code here!
int main(void){
    ll N, a[105], ave=0, ans=0;
    double aved=0;
    in(N);
    rep(i, N) {
        in(a[i]);
        ave += a[i];
    }
    aved = (double)ave / (double)N;
    ave /= N;
    if(aved-ave>=0.5)ave++;
    rep(i, N) ans += powll(abs(a[i]-ave), 2);
    put(ans);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
    ll n; cin >> n;
    map<string,ll> mp;
    rep(i,n){
        string s; cin >> s;
        if(mp.count(s)){
            mp.at(s)++;
        }else{
            mp[s] = 1;
        }
    }
    vector<string> ans(0);
    ll mxm = 0;
    for(auto i:mp){
        mxm = max(mxm,i.second);
    }
    for(auto i:mp){
        if(i.second == mxm){
            ans.push_back(i.first);
        }
    }
    sort(ans.begin(),ans.end());
    for(auto i:ans){
        cout << i << endl;
    }
}


Measured memory_bytes: 26868
n = int(input())

dl = [list(map(int,input().split())) for _ in range(n)]

# d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d  # d[i][j]に頂点i, j間の最短距離を格納
from copy import deepcopy
d = warshall_floyd(deepcopy(dl), n)

if d != dl:
    print(-1)
    exit()

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        flag = True
        for k in range(n):
            if i == k or k == j:
                continue
            if d[i][j] == d[i][k] + d[k][j]:
                flag = False
        if flag:
            ans += d[i][j]
print(ans//2)



Measured memory_bytes: 56668
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC075A
{
	class Program
	{
		static void Main(string[] args)
		{
			int a, b, c, s;
			var word = Console.ReadLine(). Split(' ');
			a =int.Parse(word[0]);
			b =int.Parse(word[1]);
			c =int.Parse(word[2]);
			if ((a == b) && ((a < c) || (a > c)))
				Console.WriteLine(c);
			else if((a == c) && ((a < b) || (a > b)))
				Console.WriteLine(b);
			else if((b == c) && ((b < a) || (b > a)))
				Console.WriteLine(a);
			Console.ReadKey();
		}
	}
}


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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<int,pii>    
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

void solve()
{
    int n,s=0;
    cin>>n;
    bitset<4000001> dp;
    dp.set(0);
    rep(i,0,n){
        int x;
        cin>>x;
        dp|=dp<<x;
        s+=x;
    }
    rep(i,(s+1)/2,s+1){
        if(dp[i]) {cout<<i;return;}
    }
}

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

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

Measured memory_bytes: 3608
// @ts-ignore
const main = (input: string) => {
  const loopNum = Number(input);

  let ans = 0;
  for(let i = 1; i <= loopNum; i += 1) {
    if (i % 3 !== 0 && i % 5 !== 0) {
      ans += i;
    }
  }
  console.log(ans);
}

// *この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 35172
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  int h, w;
  cin >> h >> w;
  vector<vector<int> > a(h, vector<int>(w));
  vector<vector<int> > b(h, vector<int>(w));
  for (auto &x: a) {
    for (auto &y: x) cin >> y;
  }
  for (auto &x: b) {
    for (auto &y: x) cin >> y;
  }

  vector<vector<int> > d(h, vector<int>(w));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) d[i][j] = abs(a[i][j] - b[i][j]);
  }

  vector<vector<vector<bool> > > dp(h, vector<vector<bool> >(w, vector<bool>(30000)));
  dp[0][0][15000+d[0][0]] = true;
  dp[0][0][15000-d[0][0]] = true;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i < h-1) {
        for (int k = 100; k < 29900; k++) {
          if (dp[i][j][k]) {
            dp[i+1][j][k+d[i+1][j]] = true;
            dp[i+1][j][k-d[i+1][j]] = true;
          }
        }
      }
      if (j < w-1) {
        for (int k = 100; k < 29900; k++) {
          if (dp[i][j][k]) {
            dp[i][j+1][k+d[i][j+1]] = true;
            dp[i][j+1][k-d[i][j+1]] = true;
          }
        }
      }
    }
  }

  int best = 1000000007;
  for (int k = 0; k < 30000; k++) {
    if (dp[h-1][w-1][k]) {
      if (abs(k - 15000) < best) best = abs(k - 15000);
    }
  }

  cout << best << endl;

  return 0;
}


Measured memory_bytes: 26496
<?php
fscanf(STDIN, "%d", $n);

$array = array();
$name_array = array();
$point_array = array();

for ($i=0; $i < $n; $i++) {
    fscanf(STDIN, "%s %d", $s, $p);
    array_push($array, array(
        'no' => $i + 1,
        'name' => $s,
        'point' => $p
    ));
}

foreach ($array as $key => $value) {
    $name_array[$key]  = $value['name'];
    $point_array[$key] = $value['point'];
}

array_multisort($name_array, SORT_ASC, SORT_STRING, $point_array, SORT_DESC, SORT_NUMERIC, $array);

foreach ($array as $key => $value) {
    echo $value['no'];
    echo "\n";
}

?>

Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<ll> vl;
typedef queue<int> qi;
typedef queue<ll> ql;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define pq priority_queue
#define rep(i,n) for (int i=0;i<n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
#define INF 200000009
#define init(x) memset(x,0,sizeof(x))
ll a,b,c,x,y,ans=0; 
int main()
{
	ios::sync_with_stdio(false);
	cin>>a>>b>>c>>x>>y;
	while(x>0&&y>0){
		ans+=min(c*2,a+b);--x;--y;
	}
	while(x>0){
		ans+=min(c*2,a);--x;
	}
	while(y>0){
		ans+=min(c*2,b);--y;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
ifstream in ( "test.in"  );
ofstream out( "test.out" );
 
const int DIM = 1e5 + 5;
const int MOD = 1e9 + 7;
 
int pos[DIM], ans[DIM];
int fct[DIM], inv[DIM];
 
int lgput( int x, int n ) {
    if( n == 0 )
        return 1;
    
    int y = lgput( x, n >> 1 );
    y = ( 1LL * y * y ) % MOD;
    
    if( n & 1 )
        y = ( 1LL * y * x ) % MOD;
    
    return y;
}
 
inline int comb( int n, int k ) {
    if( n < k ) return 0;
    return 1LL * fct[n] * inv[k] % MOD * inv[n - k] % MOD;
}
 
int main() {
    
    int n;
    cin >> n;
    
    int p1 = 0, p2 = 0; n ++;
    for( int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        
        if( pos[x] == 0 )
            pos[x] = i;
        else
            p1 = pos[x], p2 = i;
    }
    
    fct[0] = inv[0] = 1;
    for( int i = 1; i <= n; i ++ ) {
        fct[i] = ( 1LL * fct[i - 1] * i ) % MOD;
        inv[i] = lgput( fct[i], MOD - 2 );
    }
    
    ans[1] = n - 1;
    for( int i = 2; i <= n; i ++ )
        ans[i] = ( comb( n, i ) - comb( n - (p2 - p1 + 1), i - 1 ) + MOD ) % MOD;
    
    for( int i = 1; i <= n; i ++ )
        cout << ans[i] << "\n";
    
    return 0;
}

Measured memory_bytes: 2816
n = int(input())
X = [0]*n
for i in range(n):
    d1, d2 = map(int, input().split())
    if d1 == d2:
        X[i] = 1
c = 0
for i in range(n-2):
    if X[i] == 1 and X[i+1] == 1 and X[i+2] == 1:
        print('Yes')
        exit()
else:
    print('No')


Measured memory_bytes: 62308
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <tuple>
#include <algorithm>
#include <array>
#include <map>
using namespace std;
using ll = long long;
#define rep(i,n) for(decltype(n) i=0; i<n; ++i)
inline constexpr ll Inf = (1ULL << 62) -1;

template <class T>
void updatemax(T& a, T b) { if (b > a) a = b; }

int main() {
    ll N;
    cin >> N;
  	map<string,int> m;
  	rep(i,N) {
     string s;
      cin >> s;
      m[s]++;
    }
  	auto output = [&](string c) {
      cout << c << " x " << m[c] << endl;
    };
  	output("AC");
    output("WA");
  	output("TLE");
  	output("RE");
    return 0;
}


Measured memory_bytes: 3212
#include <stdio.h>
#include <stdlib.h>

#define QQQ 1000000007
#define MAXN 100000

typedef unsigned long long ull;

typedef struct CCC {
  int c;
  struct CCC *next;
} IT;

typedef struct AAA {
  ull b,w;
} DP;

IT *top[MAXN+1];
DP S[MAXN+1];

DP indset ( int no, int p )
{
  if ( S[no].w != -1 ) return S[no];
  DP ans,tmp;
  ans.b = ans.w = 1;

  IT *pos;
  for (  pos = top[no]; pos != NULL; pos = pos->next )
  {
    if ( pos->c == p ) continue;
    tmp = indset( pos->c, no );
    ans.b *= tmp.w;
    ans.b %= QQQ;
    ans.w *= (tmp.w+tmp.b);
    ans.w %= QQQ;
  }

  return S[no] = ans;
}

void init (void )
{
  int i;
  for ( i = 0; i <= MAXN; i++ ) top[i] = NULL;
}

void add( int p, int c )
{
  IT *new;
  new = (IT*)malloc(sizeof(IT));
  new->c = c;
  new->next = NULL;

  if ( top[p] == NULL ) top[p] = new;
  else {
    new->next = top[p];
    top[p] = new;
  }
}



int main(void)
{
  int n,i,j,x,y;
  DP ans;

  scanf("%d", &n);
  for ( i = 0; i < n-1; i++ ) {
    scanf("%d%d", &x, &y);
    add(x,y);
    add(y,x);
  }
  for ( i = 1; i <= n; i++ ) S[i].w = -1;

  ans = indset(1,0);

  printf("%d\n",(ans.w+ans.b)%QQQ);

  return 0;
}


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

int main(){
  int n;
  cin >> n;
  int a[n+1];
  int b[n];
  rep(i,n+1)cin >> a[i];
  rep(i,n)cin >> b[i];
  ll ans = 0;
  rep(i,n){
    ans += min(a[i],b[i]);
    b[i] -= min(a[i],b[i]);
    ans += min(b[i],a[i+1]);
    a[i+1] -= min(b[i],a[i+1]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
def place(board, x, y, num, answer):
    width = len(board[0])
    r_dx = (x + 1) % width
    r_dy = (y + 1) % width
    for i in range(width - 1):
        board[y][(x + i + 1) % width] += num
        board[(y + i + 1) % width][x] += num
    div = [1,1,-1,-1]
    for i in range(4):
        x_i = div[(0 + i) % 4]
        y_i = div[(1 + i) % 4]
        l_dx = x + x_i
        l_dy = y + y_i
        while l_dx >= 0 and l_dy >= 0 and l_dx < width and l_dy < width:
            board[l_dy][l_dx] += num
            l_dx += x_i
            l_dy += y_i
    board[y][x] += num
    if num == 1:
        answer[y][x] = "Q"
    else:
        answer[y][x] = "."

def track(placed_num, board, answer):
    width = len(board)
    if placed_num == width:
        return True
    for x in range(width):
        for y in range(width):
            if not board[y][x]:
                place(board, x, y, 1, answer)
                if track(placed_num + 1, board, answer):
                    return True
                place(board, x, y, -1, answer)
    return False

board = [[0 for n in range(8)] for m in range(8)]
answer = [["." for n in range(8)] for m in range(8)]
placed_num = int(input())
for _ in range(placed_num):
    y, x = (int(n) for n in input().split(" "))
    place(board, x, y, 1, answer)
track(placed_num, board, answer)
for i in range(8):
    print("".join(answer[i]))

Measured memory_bytes: 7912
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,s,n) for(int i = s; i < n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using Graph = vector<vector<int>>;
const int INF = 1000000007;
int main(){
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  rep(i,n){
    if(s[i] == 'a')continue;
    int Abs = abs('z' - s[i]) + 1;
    if(Abs <= k){
      s[i] = 'a';
      k -= Abs;
    }
  }
  k %= 26;
  vector<char>al(26);
  rep(i,26)al[i] = 'a' + i;
  int now = 0;
  rep(i,26)if(al[i] == s[n - 1])now = i;
  rep(i,k){
    now++;
    now %= 26;
  }
  s[n - 1] = al[now];
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb emplace_back
#define x first
#define y second
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(auto i=(a); i<(b); i++)
#define dec(i,n,a) for(auto i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()
#define EPS 3e-11
#define fcin ios_base::sync_with_stdio(false)
#define db(x) cerr << #x << " == " << x << endl
#define _ << " " <<
#define MAXN 202020
#define LOGN 29
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
 
struct trie{
	vi tam, f[2];
	int root, ptr;
	trie(){
		tam.resize(MAXN*(LOGN+1)+10);
		f[0].resize(MAXN*(LOGN+1)+10);
		f[1].resize(MAXN*(LOGN+1)+10);
	}
	void init(){
		tam[0]=tam[1]=f[0][0]=f[0][1]=f[1][0]=f[1][1]=0;
		root = 1, ptr = 2;
	}
	void insert(int node, int v, int k){
		while(1){
			tam[node]+=1;
			if(k<0) return;
			int b = (v>>k)&1;
			if(!f[b][node]){
				f[b][node] = ptr;
				f[0][ptr]=0;
				f[1][ptr]=0;
				tam[ptr]=0;
				ptr++;
			}
			node = f[b][node];
			k--;
		}
	}
	void insert(int v, int k){ insert(root,v,k); }
	int sem_q(int node, int v, int k){
		int ret = 0;
		while(1){
			if(k < 0 || tam[node]==0){
				ret ^= tam[node];
				break;
			}
			int b = (v>>k)&1;
			if(!b){
				ret ^= tam[f[0][node]];
				node = f[1][node];
				k--;
			}
			else{
				node = f[0][node];
				k--;
			}
		}
		return ret;
	}
	int com_q(int node, int v, int k){
		int ret = 0;
		while(1){
			if(k < 0 || tam[node]==0)
				break;
			int b = (v>>k)&1;
			if(b){
				ret ^= tam[f[1][node]];
				node = f[0][node];
				k--;
			}
			else{
				node = f[1][node];
				k--;
			}
		}
		return ret;
	}
	int count(int v, int k){
		int b = (v>>k)&1, ret = 0;
		if(b)
			ret = sem_q(f[0][root], v, k-1) ^ com_q(f[1][root], v, k-1);
		else
			ret = com_q(f[0][root], v, k-1) ^ sem_q(f[1][root], v, k-1);
		return ret;
	}
}tree;
 
int n, veta[MAXN], vetb[MAXN], ans;
 
int main(){
	scanf("%d", &n);
	rep(i,0,n)
		scanf("%d", &veta[i]);
	rep(i,0,n)
		scanf("%d", &vetb[i]);
	rep(k,0,LOGN){
		tree.init();
		rep(i,0,n) tree.insert(veta[i], k);
		rep(i,0,n) if(tree.count(vetb[i],k)&1) ans ^= (1<<k);
	}
	printf("%d\n", ans);
}

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

int main(){
    ll n, d;
    cin >> n >> d;
    int cnt = 0;
    rep(i, n){
        ll x, y;
        cin >> x >> y;
        ll dist = x*x + y*y;
        if(dist <= d*d){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//MOD
//--------------------------------------------
#define MUL(a,b) (((a) % MOD) * ((b) % MOD)) % MOD

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//main code

LL n;
VL ans,visited;
vector<vector<pair<LL,LL>>> tree; // 木のもう片方とコスト

void dfs(LL v, LL cost) {
	visited[v]++;
	if (cost % 2 == 0) {
		ans[v] = 0;
	}
	else {
		ans[v] = 1;
	}
	for (LL i = 0; i < tree[v].size(); i++) {
		if (visited[tree[v][i].first] == 0) {
			dfs(tree[v][i].first, cost + tree[v][i].second);
		}
	}
	return;
}

int main(int argc, char const* argv[])
{
	cin >> n;
	ans = VL(n,0);
	visited = VL(n,0);
	tree = vector<vector<PLL>>(n);
	for (LL i = 0; i < n-1; i++) {
		LL u,v,w;
		cin >> u >> v >> w;
		u--;v--;
		tree[u].push_back(make_pair(v,w));
		tree[v].push_back(make_pair(u,w));
	}
	dfs(0,0);
	for (LL i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;

    vector<ll> d(N);
    rep (i, N) {
        cin >> d[i];
    }

    ll sum = 0;
    rep (i, N) {
        for (ll j = i; j < N; j++) {
            if (i == j) {
                continue;
            }
            sum += d[i]*d[j];
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n, m;
    while(cin >> n >> m, n||m){
        int ans = 0, sum = 0;;
        int inp;
        queue<int> rec;
        rep(i, n){
            if(i < m){
                cin >> inp;
                sum+= inp;
                rec.push(inp);
            }else{
                cin >> inp;
                sum+= inp - rec.front();
                rec.pop();
                rec.push(inp);
            }
            if(ans < sum && i >= m)
                ans = sum;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1348
def solve(A, k):
  if len(A) == 0:
    return 0
  else:
    m = A.index(min(A))
    return A[m] - k + solve(A[:m], A[m]) + solve(A[m+1:], A[m])
  
if __name__ == '__main__':
  N, *h = map(int, open(0).read().split())
  print(solve(h, 0))

Measured memory_bytes: 3060
#include<stdio.h>
#define N 100


 int n,pos,count=0;
 int pre[N],in[N],post[N];
 
 int find(int in[n],int root){
     int i;
     for(i=0;i<n;i++){
            if(in[i]==root)return i;
            }
     return in[n-1];
     }

 void rec(int l,int r){
      int root,m;
      if(l>=r)return;
      root=pre[pos++];
      m=find(in,root);
      rec(l,m);
      rec(m+1,r);
      post[count++]=root;
      }

 void solve(){
      int i;
      pos=0;
      rec(0,n);
      for(i=0;i<n;i++){
              if(i)printf(" ");
              printf("%d",post[i]);
              }
      printf("\n");
      }

 int main(){
      int i,k;
      scanf("%d",&n);

      for(i=0;i<n;i++){
              scanf("%d",&k);
              pre[i]=k;
              }
      for(i=0;i<n;i++){
              scanf("%d",&k);
              in[i]=k;
              }
      solve();
      return 0;
      }



Measured memory_bytes: 2148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }

int main(){
  while(1){
    int ans = 0;
    int n,x;
    cin >> n>>x;
    if(n==0 && x==0){break;}
    for(int c=3;c<=n;++c){
      for(int b=2;b<c;++b){
        for(int a=1;a<b;++a){
          int y = a+b+c;
          if(y==x){ ++ans;break;}
          if(y>x){ break;}
        }
      }
    }
    cout << ans <<"\n";
  }
 
}


Measured memory_bytes: 3084
from sys import stdin
def main():
    readline=stdin.readline
    H,W=map(int,readline().split())
    grid=[0]*H
    for i in range(H):
        s=readline().strip()
        grid[i]=s
    mod=10**9+7

    dp=[[0]*W for _ in range(H)]
    dp[0][0]=1
    for i in range(H):
        for j in range(W):
            if i+1<H:
                if grid[i+1][j]==".":
                    dp[i+1][j]+=dp[i][j]
                    dp[i+1][j]%=mod
            if j+1<W:
                if grid[i][j+1]==".":
                    dp[i][j+1]+=dp[i][j]
                    dp[i][j+1]%=mod
    print(dp[H-1][W-1])

if __name__=="__main__":
    main()

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

int a[10005];
int G[105][105];

int main()
{
    int h,w;
    while(scanf("%d%d",&h,&w)!=EOF)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        int cnt=1;
        for(int i=1;i<=h;++i)
        {
            if(i&1)
            {
                for(int j=1;j<=w;++j)
                {
                   if(a[cnt]>0) {G[i][j]=cnt;--a[cnt];}
                   else if(a[cnt]==0) {++cnt;G[i][j]=cnt;--a[cnt];}
                }
            }else
            {
                for(int j=w;j>=1;--j)
                {
                    if(a[cnt]>0) {G[i][j]=cnt;--a[cnt];}
                    else if(a[cnt]==0) {++cnt;G[i][j]=cnt;--a[cnt];}
                }
            }
        }
        for(int i=1;i<=h;++i)
        {
            for(int j=1;j<=w;++j)
            {
                if(j!=w) printf("%d ",G[i][j]);
                else printf("%d\n",G[i][j]);
            }
        }
    }
    return 0;
}

Measured memory_bytes: 384
N, M = map(int, input().split())
L = []
R = []
for i in range(M):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
x = min(R) - max(L)
if x < 0:
	print(0)
else:
	print(x + 1)

Measured memory_bytes: 10996
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
// lint mod = 998244353;
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
#define ycomb [](auto f){ return [=](auto&&... args){ return f(f, std::forward<decltype(args)>(args)...); }; }

int app() {
  int n,m,q;
  cin>>n>>m>>q;

  vector<vector<vector<int>>> rv(10);
  rep(i,q){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;b--;
    rv[b].push_back({a,b,c,d});
  }

  int A[10];
  int score=0;
  return ycomb([&](auto f, int k, int s){
    for(auto& r:rv[k-1]){
      if(A[r[1]]-A[r[0]]==r[2]) score+=r[3];
    }
    if(k==n) return score;
    int ans=0;
    int _score=score;
    rep_range(i,s,m){
      A[k]=i;
      score=_score;
      chmax(ans,f(f,k+1, i));
    }
    return ans;
  })(0,0);
}

int main(){cout<<app()<<endl;return 0;}


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

int main(){
    int h,w;
    cin>>h>>w;

    vector<vector<int>> map(h,vector<int>(w,0));
    queue<pair<int,int>> q;
    rep(i,0,h){
        rep(j,0,w){
            char tmp;
            cin>>tmp;
            if(tmp=='.') map.at(i).at(j)=-1;
            else q.push(make_pair(i,j));
        }
    }

    vector<pair<int,int>> delta={make_pair(-1,0),make_pair(1,0),make_pair(0,-1),make_pair(0,1)};

    int depth=0;
    while(!q.empty()){
        pair<int,int> pos=q.front();
        q.pop();

        for(auto d:delta){
            pair<int,int> next_p=make_pair(pos.first+d.first, pos.second+d.second);

            if(next_p.first>=0 && next_p.first<h && next_p.second>=0 && next_p.second<w){
                if(map.at(next_p.first).at(next_p.second)==-1){
                    int new_depth=map.at(pos.first).at(pos.second)+1;
                    map.at(next_p.first).at(next_p.second)=new_depth;
                    q.push(next_p);
                    depth=max(depth,new_depth);
                }
            }
        }
    }

    cout<<depth<<endl;
}

Measured memory_bytes: 12432