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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int q = sc.nextInt();

		long[] s = new long[a + 2];
		long[] t = new long[b + 2];
		long[] x = new long[q];

		for (int i = 1; i < a + 1; i++) {
			s[i] = sc.nextLong();
		}
		s[0] = -10000000000000000L;
		s[a + 1] = 10000000000000000L;

		for (int i = 1; i < b + 1; i++) {
			t[i] = sc.nextLong();
		}
		t[0] = -10000000000000000L;
		t[b + 1] = 10000000000000000L;


		for (int i = 0; i < q; i++) {
			x[i] = sc.nextLong();
		}

		for (int i = 0; i < x.length; i++) {
			int lt = binarySearch(t, x[i]);
			long answer = 1000000000000000000L;


			if (lt != 0) {
				int lls = binarySearch(s, t[lt]);
				long dl = Math.abs(x[i] - t[lt]);
				answer = Math.min(answer, dl + Math.abs(t[lt] - s[lls]));
				answer = Math.min(answer, dl + Math.abs(t[lt] - s[lls + 1]));
			}

			if (lt + 1 != b + 1) {
				int rt = lt + 1;
				long dr = Math.abs(x[i] - t[rt]);
				int rls = binarySearch(s, t[rt]);
				answer = Math.min(answer, dr + Math.abs(t[rt] - s[rls]));
				answer = Math.min(answer, dr + Math.abs(t[rt] - s[rls + 1]));
			}


			lt = binarySearch(s, x[i]);

			if (lt != 0) {
				int lls = binarySearch(t, s[lt]);
				long dl = Math.abs(x[i] - s[lt]);
				answer = Math.min(answer, dl + Math.abs(s[lt] - t[lls]));
				answer = Math.min(answer, dl + Math.abs(s[lt] - t[lls + 1]));
			}

			if (lt + 1 != a + 1) {
				int rt = lt + 1;
				long dr = Math.abs(x[i] - s[rt]);
				int rls = binarySearch(t, s[rt]);

				answer = Math.min(answer, dr + Math.abs(s[rt] - t[rls]));
				answer = Math.min(answer, dr + Math.abs(s[rt] - t[rls + 1]));
			}


			System.out.println(answer);
		}
	}

	private static int binarySearch(long[] a, long x) {
		int l = 0;
		int r = a.length;
		while (r - l > 1) {
			int m = (l + r) / 2;
			if (a[m] <= x) {
				l = m;
			} else {
				r = m;
			}
		}
		return l;
	}
}


Measured memory_bytes: 98168
#include<bits/stdc++.h>
using namespace std;
int main()
{
 unordered_map<int,string> mp;
 for(int i=0;i<=9;i++)
 {
   if(i==2||i==4||i==5||i==7||i==9)
   mp[i]="hon";
   else if(i==3)
   mp[i]="bon";
   else
   mp[i]="pon";
 }
int n;
cin>>n;
cout<<mp[n%10]<<"\n";
}

Measured memory_bytes: 3552
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;



public class Main {


	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<String> l = solve(n);
		for (String s : l) {
			System.out.println(s);
		}


	
	}
	
	
	static List<String> solve(int n) {
		if (n==1) {
			return  Arrays.asList("a");
		} else {
			List<String> tmp = solve(n-1);
			List<String> ans = new ArrayList<>();
			for (String s : tmp) {
				char c = 'a';
				for (int i=0;i<n-1;i++) {
					c = (char)Math.max(c, s.charAt(i));
				}
				
				for (char j='a'; j<=c+1;j++) {
					ans.add(s+String.valueOf(j));
				}
			}
			return ans;
		}
		
	}


}





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

int main()
{
  int N;
  unsigned long X;
  long pnum = 0;
  unsigned long index;
  
  cin >> N >> X;
  vector<unsigned long> p(N+1);
  vector<unsigned long> s(N+1);
  p[0] = 1;
  s[0] = 1;
  for(int i = 1; i <= N; i++){
    p[i] = 1 + 2*p[i-1];
    s[i] = 3 + 2*s[i-1];
  }
  index =  X;
  int i;
  for(i = N; i > 0; i--){
    if(index == 1){
      break;
    }
    else if(index == 2+s[i-1]){
      pnum += p[i-1]+1;
      break;
    }
    else if(index == 3+2*s[i-1]){
      pnum += 2*p[i-1]+1;
      break;
    }
    else if(index < 2+s[i-1]){
      index -= 1;
      if(i == 1){
      	pnum++;
      	break;
      }
      continue;
    }
    else if(index < 3 + 2*s[i-1]){
      if(i == 1){
        pnum += 3;
        break;
      }
      pnum += 1+p[i-1];
      index -= 2+s[i-1];
      continue;
    }
  }
    cout << pnum << endl;
}

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

int main(){
    
    int K,N,a;
    cin >> K >> N >> a;
    int b,c;
    b = a;
    
    int maxdist = 0;
    
    for(int i = 0; i < N-1;i++){
        cin >> c;
        if(c-b>maxdist){
            maxdist = c-b;
        }
        b = c;
    }
    
    if(K+a-b > maxdist){
        maxdist = K+a-b;
    }
    
    cout << K-maxdist << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
 
int main(){
	int a, b;
	cin >> a >> b;
 
	rep(i, max(a,b)) cout << min(a, b);
	cout << endl;
 
	return 0;
}

Measured memory_bytes: 256
num = gets.chomp.split(" ").map(&:to_i)

if num[0] == num[1]
  if num[1] != num[2] && num[0] != num[2]
    puts "Yes"
    exit
  end
  else
  if num[1] == num[2] && num[0] != num[2] || num[0] == num[2] && num[1] != num[2]
    puts "Yes"
    exit
  end
end

puts "No"



Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
//#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const long long linf = 4523372036854775807;
const int iinf = 1500000000;
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	int from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	int x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
int ari(int a, int b, int c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
int fact(int i) {
	ll sum = 1;
	for (int j = 2; j <= i; j++)
		sum = (sum* j) % Mod;
	return sum;
}//階乗(正）
 //---------------------------------------------------
 //+++++++++++++++++++++++++++++++++++++++++++++++++++
int n;
bool f[100][10];
int p[100][11];
bool b[10];
int solve(int x) {
	int ans = -iinf;
	if (x == 10) {
		for (int i = 0; i < 10; i++)
			if (b[i]) goto stop;
		return -iinf;
	stop:;
		ans = 0;
		for (int i = 0; i < n; i++) {
			int sum = 0;
			for (int j = 0; j < 10; j++) {
				if (b[j] && f[i][j])
					sum++;
			}
			ans += p[i][sum];
		}
		return ans;
	}
	b[x] = 0;
	ans = solve(x + 1);
	b[x] = 1;
	ans = max(ans, solve(x + 1));
	return ans;
}
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> f[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 11; j++) {
			cin >> p[i][j];
		}
	}
	cout << solve(0) << endl;
	getchar(); getchar();
}

Measured memory_bytes: 256
def kaibun(x):
    x_str = str(x)
    x_str_reverse = x_str[::-1]
    if(x_str == x_str_reverse):
        return True
    else:
        return False

def main():
    ans  = 0
    A,B = list(map(int,input().split()))
    for i in range(A,B+1):
        if kaibun(i):
            ans = ans + 1
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

    ll n ;
    cin >> n;
    vl h(n);
    rep(i,n){
        cin >> h[i];
    }
    ll pre=-999;
    rep(i,n){
        if(pre<=h[i]-1){
            pre = h[i]-1;
        }
        else if(pre <= h[i]){
            pre = h[i];
        }
        else{
            No
        }
    }
    Yes
    return 0;
}

Measured memory_bytes: 1024
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    s = input()

    cnt = 0
    score = 0
    for i in range(1, n):
        if s[i - 1] != s[i]:
            cnt += 1
        else:
            score += 1

    res = min(n - 1, score + min(k, cnt) * 2)
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9188
/* 
chirag11032000
Chirag Thakur
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;

template < typename T > using OrderedSet = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " : " << arg1 << std::endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | ";
	__f(comma + 1, args...);
}
#else
#define trace(...)
#endif

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

const db PI = acos(-1);
const ll LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

void test_case();

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	test_case();
	cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
	return 0;
}

void test_case() {
	char ch;
	cin >> ch;
	if (ch == 'A') {
		cout << "T\n";
	} else if (ch == 'T') {
		cout << "A\n";
	} else if (ch == 'G') {
		cout << "C\n";
	} else {
		cout << "G\n";
	}
}

Measured memory_bytes: 256
n,m=map(int,input().split())
mod=10**9+7

a=set([int(input()) for i in range(m)])

dp=[0]*(n+1)
dp[0]=1

for i in range(1,n+1):
  dp[i]=(dp[i-1]+dp[i-2])%mod
  if i in a:dp[i]=0
print(dp[n])

Measured memory_bytes: 13216
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
//#include <unordered_map> //C++11
using namespace std;

typedef long long ll;

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


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a, b, ans = 0;
	scanf("%d%d", &a, &b);
	if (a + b < 24) {
		ans = a + b;
	}
	else {
		ans = (a + b) - 24;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
import java.io.*
import java.util.*

fun solve(N: Long, T: LongArray){
    println(T.reduce{ a, b -> a/gcd(a, b)*b })
    return
}

tailrec fun gcd(x: Long, y: Long): Long = if (y == 0L) x else gcd(y, x % y)


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toLong()
    val T = LongArray(N.toInt())
    for (i in 0 until N.toInt()) {
        T[i] = sc.next().toLong()
    }
    solve(N, T)
}



Measured memory_bytes: 31528
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	int N,A,B;
	cin >> N >> A >> B;
	if(A%2 == B%2) cout << "Alice" << endl;
	else cout << "Borys" << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(0)
#define pb push_back
#define digit(x) floor(log10(x))+1
#define mod 1000000007
#define endl "\n"
#define int long long
typedef long double ld;
typedef vector<vector<int> > matrix;
typedef vector<int> arr;
typedef vector<string> vs;
typedef vector<pair<int,int> > pv;
#define test() int t;cin>>t;while(t--)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr << #x << " is " << x << endl;
int bx[]={0,0,1,-1,1,-1,-1,1};
int by[]={1,-1,0,0,1,-1,1,-1};
//=================================================================//


#undef int
int main(){
#define int long long 
    fast;
    int n,k;
    cin>>n>>k;
    int arr[n];
    FOR(i,0,n-1) cin>>arr[i];
    bool dp[k+1]={0};
    dp[0] = 0;
    for(int i=1;i<=k;i++) {
        for(int x : arr) {
            if(i-x>=0) {
                if(dp[i-x]==0) {
                    dp[i] = 1;
                    break;
                } 
            }
        }
    }
    if(dp[k]) cout<<"First";
    else cout<<"Second";
    return 0;
}

Measured memory_bytes: 3752
from collections import deque
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy):
  dmap=[[h*w]*w for _ in range(h)]
  dmap[sx][sy]=0
  cand=deque()
  cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.popleft()
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.' and dmap[next_x][next_y]==h*w:
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
        cand.append([next_x,next_y])
  return max([dmap[i][j] for i in range(h) for j in range(w) if dmap[i][j]<h*w])
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      d=maze(l,ix,iy)
      if c<d:
        c=d
print(c)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int X, N;
  cin >> X >> N;
  vector<int> a(102);
  for (int i = 0; i < N; i++) {
    int p;
    cin >> p;
    a[p] = 1;
  }
  pair<int, int> ans(99999,-1);
  for (int i = 0; i <= 101; ++i) {
    if (a[i] == 1) continue;
    int dis = abs(X-i);
    ans = min(ans, pair<int, int>(dis,i));
  }
  cout << ans.second << endl;
}

Measured memory_bytes: 3536
import numpy as np

N,M   = list(map(int,input().split()))
Hlist = list(map(int,input().split()))
Hdict = {i:Hlist[i] for i in range(len(Hlist))}
# adj = [[0 for _ in range(N)] for _ in range(N)]

# for line in Mlist:
bad_set = set()
for _ in range(M):
    line = list(map(int,input().split()))
    if Hdict[line[0]-1] <= Hdict[line[1]-1]:
        bad_set.add(line[0])
    if Hdict[line[1]-1] <= Hdict[line[0]-1]:
        bad_set.add(line[1])
print(N-len(bad_set))

Measured memory_bytes: 44380
#include <stdio.h>
int a[200010];
int main()
{
    int n;scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%d",&a[i]);
    int a1=0,i1,a2=0,i2,a3=0,i3;
    for (int i=0;i<n;i++)
    if (a[i]>a1)
        a1=a[i],i1=i;
    for (int i=0;i<n;i++)
    if (i!=i1 && a[i]>a2)
        a2=a[i],i2=i;
    for (int i=0;i<n;i++)
    {
        if (i==i1) printf("%d\n",a2);
        else printf("%d\n",a1);
    }
}


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

int main(){
    string str;
    int c=0;
    while(cin>>str){
        int s=1;
        for(int i=0;i<str.length();i++)
            if(str[i]!=str[str.length()-1-i])
                s=0;
        if(s)c++;
    }
    cout<<c<<endl;
}

Measured memory_bytes: 1184
N,Y = [int(i) for i in input().split()]

a = 4000
b = 9000

p = Y-N*1000
for i in range(N+1):
    for j in range(N+1):
        if i+j <= N:
            if a*i+b*j == p:
                k = N-i-j
                print(str(j)+' '+str(i)+' '+str(k))
                exit()
print('-1 -1 -1')


Measured memory_bytes: 40812
#include <bits/stdc++.h>
using namespace std;  
typedef long long ll;
typedef vector<ll> vint;
int main() {
  string s,ans="";
  cin >> s;
  for (ll i=0;i<s.size();i+=2) {
    ans += s.at(i);
  }
  cout << ans;
}

Measured memory_bytes: 512
a1,b1 = map(int, input().split())
a2,b2 = map(int, input().split())
a3,b3 = map(int, input().split())

A = [0 for _ in [0]*4]

A[a1-1] += 1
A[a2-1] += 1
A[a3-1] += 1
A[b1-1] += 1
A[b2-1] += 1
A[b3-1] += 1

P = max(A)

if P > 2:
    print('NO')
else:
    print('YES')

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

int main() {
  ll A, B, K;
  cin >> A >> B >> K;

  if (A >= 1) {
    // 自分のクッキーを食べる
    if (A >= K) {
      A -= K;
      K = 0;
    } else {
      K -= A;
      A = 0;
    }
  }

  if (B >= 1) {
    if (B >= K) {
      B -= K;
      K = 0;
    } else {
      K -= B;
      B = 0;
    }
  }

  cout << A << " " << B << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
    
struct Node{
    ll cost;
    int parent;  // index of parent node
    int index;   // index in node list
    vector<pair <int,ll> > connect;
};
    
int reach[100001];
    
void dfs(vector<Node> &node, int index){
    
    //cout << "ind:" << index << endl;
    
    for(int i = 0; i < node[index].connect.size(); i++){
        int next_index = node[index].connect[i].first;
        ll  next_cost = (node[index].connect[i].second) % 2;
        if(reach[next_index] == 0){
            reach[next_index] = 1;
            node[next_index].cost = (node[index].cost + next_cost) % 2;
            node[next_index].parent = index;
            dfs(node, next_index);
        }
    }
    
    
}
    
int main(){
    
    int N;
    cin >> N;
    
    vector<Node> node(N+1);
    for(int i = 0; i <= N; i++){
        node[i].cost = 0;
        node[i].parent = -1;
        node[i].index = i;
    }
    for(int i = 0; i < N-1; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        c = c % 2;
        node[a].connect.push_back( make_pair(b, c));
        node[b].connect.push_back( make_pair(a, c));
    }
    
    reach[1] = 1;
    dfs(node, 1);
    for(int i = 1; i <= N; i++){
        if(node[i].cost % 2) cout << 0 << endl;
        else cout << 1 << endl;
    }   
    
}

Measured memory_bytes: 11136
#include<iostream>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> vc(n);
  for(int i = 0 ; i < n ; i++ ) cin >> vc[i];
  int ans = 0,q,a;
  cin >> q;
  sort(vc.begin(),vc.end());
  while(q--){
    cin >> a;
    if(binary_search(vc.begin(),vc.end(),a)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;

int main(){
    int a, b;
    cin >> a >> b;
    cout << max({a+b, a-b, a*b}) << endl;
}


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

int main() {
	int n, k, mid, color, x, y, tile[1000], y2, x2;
	cin >> n >> k;
	mid = n / 2;
	mid += n % 2;
	color = mid % 3;
	if (color == 0)
		color = 3;
	if (n % 2 == 0)
		mid++;
	if (n % 2 == 1){
		for (int i = 0; i < k; i++){
			x = 0;
			y = 0;
			x2 = 0;
			y2 = 0;
			cin >> x >> y;
			if (x > mid)
				x = x - mid;
			else if (x<mid){
				x = mid - x;
				if (x == 1){
					x2 = 1;
				}
			}
			if (y > mid){
				y = y - mid;
			}
			else if (y < mid){
				y = mid - y;
				if (y == 1){
					y2 = 1;
				}
			}
			if (x == mid)
				x = 0;
			if (y == mid)
				y = 0;
			tile[i] = max(x, y);
			if (tile[i] == 1 && x2 == 1 || tile[i] == 1 && y2 == 1)
				tile[i] = color;
			else{
				if (color == 2){
					tile[i] = (tile[i] + 3) % 3;
					if (tile[i] == 2)
						tile[i] = 3;
					else if (tile[i] == 0)
						tile[i] = 2;
				}
				else if (color == 3){
					tile[i] = (tile[i] + 4) % 3;
					if (tile[i] == 0)
						tile[i] = 1;
					else if (tile[i] == 1)
						tile[i] = 3;
				}
				else if (color == 1)
					tile[i] = (tile[i] + 2) % 3;
				if (tile[i] == 0)
					tile[i] = 3;
				else if (tile[i] == 1)
					tile[i] = 2;
			}
			cout << tile[i] << endl;
		}
	}
	if (n % 2 == 0){
		for (int i = 0; i < k; i++){
			x = 0;
			y = 0;
			x2 = 0;
			y2 = 0;
			cin >> x >> y;
			if (x > mid)
				x = x - mid;
			else if (x<mid){
				x = mid - x;
				if (x == 1){
					x2 = 1;
				}
				x--;
			}
			if (y > mid){
				y = y - mid;
			}
			else if (y < mid){
				y = mid - y;
				if (y == 1){
					y2 = 1;
				}
				y--;
			}
			if (x == mid)
				x = 0;
			if (y == mid)
				y = 0;
			tile[i] = max(x, y);
			if (tile[i] == 1 && x2 == 1 || tile[i] == 1 && y2 == 1)
				tile[i] = color;
			else{
				if (color == 2){
					tile[i] = (tile[i] + 3) % 3;
					if (tile[i] == 2)
						tile[i] = 3;
					else if (tile[i] == 0)
						tile[i] = 2;
				}
				else if (color == 3){
					tile[i] = (tile[i] + 1) % 3;
					if (tile[i] == 0)
						tile[i] = 1;
					else if (tile[i] == 1)
						tile[i] = 3;
				}
				else if (color == 1){
					tile[i] = (tile[i] + 2) % 3;
					if (tile[i] == 0)
						tile[i] = 3;
					else if (tile[i] == 1)
						tile[i] = 2;
					else if (tile[i] == 2)
						tile[i] = 1;
				}
			}
			cout << tile[i] << endl;
		}
	}
	return 0;
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s,t,ch="";
    cin>>s>>t;
    for (int i=0;i<n;i++)
        {
        ch=ch+s[i];
        ch=ch+t[i];
        }
    cout<<ch;


    return 0;
}


Measured memory_bytes: 256
#include <cstdio>

int main() {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);

	int ans = 0;
	for (int i = a; i <= b; ++i) {
		if (c % i == 0) ++ans;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 1028
import numpy as np
n, d = map(int, input().split())
x = []
for _ in range(n):
    a = list(map(int, input().split()))
    x.append(a)
#print(x)
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        s = 0
        for k in range(d):
            s += (x[i][k]-x[j][k])*(x[i][k]-x[j][k])
            #print((x[i][k]-x[j][k])*(x[i][k]-x[j][k]))
            #print(s)
        s = np.sqrt(s)
        #print(s)
        if s//1 == s:
            
            cnt += 1
print(cnt)


Measured memory_bytes: 12428
#include <bits/stdc++.h>
#define int long long int
#define endl "\n"
using namespace std;
void solve()
{
	//Enter your code here Tanmay:)
	int n;
	string s;
	cin>>n>>s;
	if(n==0)
	{

		cout<<s;
		exit(0);
	}
//cout<<(int)'Z';
	for(int i=0;i<s.size();i++)
	{
		int x=s.at(i)+n;
		if(x>=91)
			while(x>=91)
				x=x-26;
		cout<<(char)x;
	}

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

struct Treasure {
	long long int price, rarity;
	Treasure operator+(const Treasure& that) const { return Treasure{ price + that.price, rarity + that.rarity }; }
	Treasure operator-(const Treasure& that) const { return Treasure{ price - that.price, rarity - that.rarity }; }
};
int power(const int base, const int exp) {
	switch (exp) {
	case 0: return 1;
	case 1: return base;
	default: return power(base * base, exp / 2) * power(base, exp % 2);
	}
}
int main() {
	std::cin.tie(0); std::cin.sync_with_stdio(false);
	int n; long long int d; std::cin >> n >> d;
	std::vector<Treasure> treasures(n); for (auto& t : treasures) std::cin >> t.price >> t.rarity;
	std::vector<Treasure> half, rest; half.reserve(power(3, n / 2)); rest.reserve(power(3, n - n / 2));
	half.push_back(Treasure{ 0, 0 }); rest.push_back(Treasure{ 0, 0 });
	for (auto i = 0; i < n / 2; ++i) {
		const auto current_size = half.size();
		for (auto j = 0; j < current_size; ++j) {
			half.push_back(half[j] + treasures[i]);
			half.push_back(half[j] - treasures[i]);
		}
	}
	for (auto i = n / 2; i < n; ++i) {
		const auto current_size = rest.size();
		for (auto j = 0; j < current_size; ++j){
			rest.push_back(rest[j] + treasures[i]);
			rest.push_back(rest[j] - treasures[i]);
		}
	}
	std::sort(half.begin(), half.end(), [](const Treasure& a, const Treasure& b) {return a.price > b.price; });
	std::sort(rest.begin(), rest.end(), [](const Treasure& a, const Treasure& b) {return a.price < b.price; });
	std::deque<Treasure> deque;
	long long int result = 0;
	int ri = 0;
	for (auto hi = 0; hi < half.size(); ++hi) {
		while (ri < rest.size() && d >= rest[ri].price + half[hi].price) {
			auto add_treasure = rest[ri++];
			while (!deque.empty() && deque.back().rarity<= add_treasure.rarity)
				deque.pop_back();
			deque.push_back(add_treasure);
		}
		while (!deque.empty() && deque.front().price + half[hi].price < -d)
			deque.pop_front();
		if (!deque.empty()) {
			result = std::max(result, deque.front().rarity + half[hi].rarity);
		}
	}
	std::cout << result << '\n';
}


Measured memory_bytes: 451368
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
ans = []
while N > 0:
    N -= 1
    x = N % 26
    N = N // 26
    ans.append(alf[x])
ans.reverse()
print("".join(ans))

Measured memory_bytes: 10572
/**
*    created: 16.07.2020 01:41:58
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
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 (b < a) {a = b; return 1;} return 0;}
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    string s; cin >> s;
    vector<char> v;
    rep(i,s.size()) {
        char t = s[i];
        if (t == '0') v.push_back(t);
        if (t == '1') v.push_back(t);
        if (t == 'B') {
            if (v.size() == 0) continue;
            else v.pop_back();
        }
    }
    for (auto p : v) cout << p;
    cout << endl;
    return 0;
}

Measured memory_bytes: 3624
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=1<<30;

ll modinv(ll a,ll m){
  ll b=m,u=1,v=0;
  while(b){
    ll t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  u%=m;
  if(u<0) u+=m;
  return u;
}

ll com(ll n,ll k){
  ll com1=1; ll com2=1;
  for(int i=1;i<=k;i++){
    com1*=(n-i+1); com1%=mod;
    com2*=i; com2%=mod;
  }
  return com1*modinv(com2,mod)%mod;
}

ll rui(ll a,ll n){
  ll ans=1;
  while(n>0){
    if(n&1) ans=ans*a%mod;
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

int main(){
  ll n,a,b; cin >> n >> a >> b;
  ll ans=rui(2,n)-1-com(n,a)-com(n,b);
  while(ans<0){
    ans+=mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
while True:
    n = int(input())
    if n == 0:
        break
    Num = list(map(int,input().split()))
    noko = 32
    jun = 0
    iti = 0
    while noko > 0:
        if jun == 0:
            noko -= (noko - 1) % 5
        else:
            noko -= Num[iti % len(Num)]
            iti += 1
        if noko < 0:
            noko = 0
        print(noko)
        jun = (jun + 1) % 2

Measured memory_bytes: 7604
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.00000000000000001
#define prid(x) printf("%.10lf\n", x)

pair<ll, ll> dp[51][51];
ll v[50];

signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    int3(n, a, b);
    rep(i, n)scanf("%lld", v+i);

    rep(i, n + 1)rep(j, n + 1)dp[i][j] = mp(0, 0);

    dp[0][0] = mp(0, 1);
    rep(i, n){
      rep(j, i + 1){
        if(dp[i + 1][j].X < dp[i][j].X){
          dp[i + 1][j].X = dp[i][j].X;
          dp[i + 1][j].Y = dp[i][j].Y;
        }else if(dp[i + 1][j].X == dp[i][j].X){
          dp[i + 1][j].Y += dp[i][j].Y;
        }
        if(dp[i + 1][j + 1].X < dp[i][j].X + v[i]){
          dp[i + 1][j + 1].X = dp[i][j].X + v[i];
          dp[i + 1][j + 1].Y = dp[i][j].Y;
        }else if(dp[i + 1][j + 1].X == dp[i][j].X + v[i]){
          dp[i + 1][j + 1].Y += dp[i][j].Y;
        }
      }
    }

    /*rep(i, n + 1)rep(j, n + 1)if(dp[i][j].Y > 0){
      //pri3(i, j, dp[i][j].X);
      printf("%d %d %lld %lld \n", i, j, dp[i][j].X, dp[i][j].Y);
    }*/

    ll resx = -1, resy = 1;
    for(i = a;i <= b;++i){
      if(resx * (ll)i < dp[n][i].X * resy){
        resx = dp[n][i].X;
        resy = i;
      }
    }
    ll cnt = 0;
    for(i = a;i <= b;++i){
      if(resx * (ll)i == dp[n][i].X * resy)cnt += dp[n][i].Y;
    }

    double resv = (double)resx / (double)resy;
    prid(resv);
    pri(cnt);



/*/

//*/ break;
  }
  return 0;
}


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

from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

    def find(self,x):
        if self.par[x]<0:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            
            return self.par[x]

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        ##木の高さを比較し、低い方から高い方へ辺をはる
        if x==y:
          return

        if self.par[x]>self.par[y]:
          x,y=y,x
          
        self.par[x]+=self.par[y]
        self.par[y]=x

    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def size(self,x):
      return -self.par[self.find(x)]
      
    def members(self,x):
      root=self.find(x)
      return [i for i in range(self.n) if self.find(i)==root]
    
    def roots(self):
      return [i for i, x in enumerate(self.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
    
uf=union_find(n)
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  
ans=0

for i in range(n):
  c=uf.size(i)
  ans=max(ans,c)
  
print(ans)

Measured memory_bytes: 83760
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
#define X first
#define Y second
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int h,w,k,dist[805][805],d[805][805];
string b[805];
pair<int,int> s;
queue<pair<int,int> > q,q2;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>h>>w>>k;
	for(int i=0;i<h;i++){
		cin>>b[i];
		for(int j=0;j<w;j++){
			if(b[i][j]=='S'){
				s.X=i;
				s.Y=j;
				break;
			}
		}
	}
	setINF(dist);
	setINF(d);
	dist[s.X][s.Y]=d[s.X][s.Y]=0;
	q.push(s);
	q2.push(s);
	while(!q.empty()){
		pair<int,int> u=q.front();
		q.pop();
		if(dist[u.X][u.Y]>=k)continue;
		for(int o=0;o<4;o++){
			pair<int,int> v;
			v.X=u.X+dx[o];
			v.Y=u.Y+dy[o];
			if(v.X<0 || v.X>=h || v.Y<0 || v.Y>=w || b[v.X][v.Y]=='#' || dist[v.X][v.Y]<INF)continue;
			dist[v.X][v.Y]=dist[u.X][u.Y]+1;
			d[v.X][v.Y]=0;
			q.push(v);
			q2.push(v);
		}
	}
	while(!q2.empty()){
		pair<int,int> u=q2.front();
		q2.pop();
		for(int o=0;o<4;o++){
			pair<int,int> v;
			v.X=u.X+dx[o];
			v.Y=u.Y+dy[o];
			if(v.X<0 || v.X>=h || v.Y<0 || v.Y>=w || d[v.X][v.Y]<INF)continue;
			d[v.X][v.Y]=d[u.X][u.Y]+1;
			q2.push(v);
		}
	}
	int ans=INF;
	for(int i=0;i<max(h,w);i++){
		if(i<h)ans=min(ans,min(d[i][0],d[i][w-1]));
		if(i<w)ans=min(ans,min(d[0][i],d[h-1][i]));
	}
	if(!ans)cout<<"1\n";
	else cout<<(ans-1)/k+2<<endl;
	return 0;
}

Measured memory_bytes: 11520
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Mmax = 500000;
int N, M, A[Mmax], B[Mmax];

pair<int, int> dfs(int n, vector<int> &vec, vector<vector<int> > &g){
	pair<int, int> p = make_pair(1, 0);
	for(int m=0; m<g.size(); m++){
		if(g[n][m]==0) continue;
		if(vec[m]==vec[n]){
			return make_pair(-1, -1);
		}
		if(vec[m]==0){
			vec[m] = -vec[n];
			pair<int, int> q=dfs(m, vec, g);
			if(q.first < 0) return q;
			p.first += q.second;
			p.second += q.first;
		}
	}

	return p;
}


int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
	}

	vector<vector<int> > g(N, vector<int>(N, 1));

	for(int i=0; i<M; i++){
		g[A[i]][B[i]] = 0;
		g[B[i]][A[i]] = 0;
	}
	for(int i=0; i<N; i++){
		g[i][i] = 0;
	}

	vector<int> vec(N);
	vector<pair<int, int> > ps;
	for(int i=0; i<N; i++){
		if(vec[i]) continue;
		vec[i] = 1;
		pair<int, int> p = dfs(i, vec, g);
		if(p.first < 0) {
			cout << -1 << endl;
			return 0;
		}
		ps.push_back(p);
	}

	/*
	for(int i=0; i<ps.size(); i++){
		cout << ps[i].first << " " << ps[i].second << endl;
	}
	*/

	vector<vector<bool> > dp(ps.size()+1, vector<bool>(N+1));
	dp[0][0] = true;
	for(int i=0; i<ps.size(); i++){
		for(int j=0; j<=N; j++){
			dp[i+1][j+ps[i].first] = dp[i][j] || dp[i+1][j+ps[i].first];
			dp[i+1][j+ps[i].second] = dp[i][j] || dp[i+1][j+ps[i].second];
		}
	}

	/*
	for(int i=0; i<N+1; i++){
		if(dp[ps.size()][i]){
			cout << i << endl;
		}
	}
	*/

	int ans = 1e8;
	for(int i=0; i<N+1; i++){
		if(dp[ps.size()][i]){
			ans = min(ans, i*(i-1)/2 + (N-i)*(N-i-1)/2);
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long N,A,B;
	cin>>N>>A>>B;
	long long quo=N/(A+B),rem=N%(A+B);
	long long ans=quo*A;
	if(rem>0){
		if(rem<A){
			ans+=rem;
		}
		else{
			ans+=A;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  int W, a, b;
  cin >> W >> a >> b;
  if(a <= b && b <= a+W){
    cout << 0;
  }else{
    cout << min(abs(a+W - b), abs(b+W - a));
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int pattern1[] = { 0,-1,0,1 };
int pattern2[] = { 1,0,-1,0 };

int main() {
	int H, W;

	cin >> H >> W;

	vector<vector<char>> map(H + 2, vector<char>(W + 2, '#'));
	vector<vector<bool>> flag(H + 2, vector<bool>(W + 2, true));

	int whites = 0;
	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= W; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '.') whites++;
		}
	}



	int steps = 0;
	queue<pair<int, int>> p;
	p.push(make_pair(1, 1));
	flag[1][1] = false;

	pair<int, int> now;
	while (!p.empty()) {
		int num = p.size();
		for (int i = 0; i < num; i++)
		{
			now = p.front(); p.pop();
			if (now.first == H && now.second == W) goto end;

			for (int j = 0; j < 4; j++) {
				if (map[now.first + pattern1[j]][now.second + pattern2[j]] == '.' && flag[now.first + pattern1[j]][now.second + pattern2[j]]) {
					p.push(make_pair(now.first + pattern1[j], now.second + pattern2[j]));
					flag[now.first + pattern1[j]][now.second + pattern2[j]] = false;
				}
			}
		}
		steps++;
	}
end:
	if (now.first == H && now.second == W) {
		cout << whites - steps - 1 << endl;
	}
	else {
		cout << -1 << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
typedef pair<ll,pll> tll;
ll a[3], b[3];
set<tll> s;

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  FOR(i, 0, 3)cin >> a[i];
  tll t;
  int ans = 0;
  while(true){
    if(a[0]%2 || a[1]%2 || a[2] % 2) break;
    sort(a, a+3);
    t = mp(a[0], mp(a[1], a[2]));
    if(s.find(t) != s.end()){
      cout << -1 << endl;
      return 0;
    }
    s.insert(t);
    ans++;
    FOR(i, 0, 3) b[i] = a[(i+1)%3]/2 + a[(i+2)%3]/2;
    swap(a, b);
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

void dfs(vector<set<int>>& g, int u, int cur_comp, vector<int>& components) {
    if (components[u] != -1) {
        return;
    }
    components[u] = cur_comp;
    for(auto v : g[u]) {
        dfs(g, v, cur_comp, components);
    }
}


int32_t main() {
    int n,m;
    cin >> n >> m;
    vector<set<int>> v(n);
    for (int i = 0; i < m; ++i) {
        int a,b;
        cin >> a >> b;
        a--,b--;
        v[a].insert(b);
        v[b].insert(a);
    }
    vector<int> components(n, -1);
    int cur_comp = 0;
    for(int i = 0; i < n; ++i) {
        if (components[i] == -1) {
            dfs(v,i,cur_comp, components);
            cur_comp++;
        }
    }
    vector<int> sizes(cur_comp, 0);
    for (int i = 0; i < components.size(); ++i) {
        sizes[components[i]]++;
    }
    cout << *max_element(sizes.begin(), sizes.end());
}

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

int     main() {
        vector <int> a(3);
        for (int i=0; i<3; i++) {
                cin >> a.at(i);
        }
        sort(a.begin(), a.end());
        cout << a.at(0) + a.at(1) << endl;
        return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
s = {tuple(map(int, input().split())) for _ in range(m)}

for i in range(2, n):
    route = [1, i, n]
    if all(edge in s for edge in zip(route, route[1:])):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')



Measured memory_bytes: 37532
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, m, n) for(ll i = (ll)m; i < (ll)n; i++)
#define PER(i, m, n) for(ll i = (ll)m; i > (ll)n; i--)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

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

int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> v(n);
    vector<ll> cnt(n+1);
    REP(i, 0, n){
        cin >> v[i];
        cnt[v[i]]++;
    }
    ll ans = 0;
    sort(cnt.begin(), cnt.end());
    REP(i, 0, n-k+1){
        ans += cnt[i];
    }
    cout << ans << endl;
}


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

int main() {
    int a, b;
    string ope;
    cin >> a >> ope >> b;
    
    while (ope != "?") {
        int ans;
        if (ope == "+") ans = a + b;
        else if (ope == "-") ans = a - b;
        else if (ope == "*") ans = a * b;
        else if (ope == "/") ans = a / b;
        
        cout << ans << endl;
        
        cin >> a >> ope >> b;
    }
    return 0;
}


Measured memory_bytes: 3156