akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 1005
#define MAX 16

struct Edge{
	Edge(int arg_word_id,int arg_loc,int arg_dist){
		word_id = arg_word_id;
		loc = arg_loc;
		dist = arg_dist;
	}
	int word_id,loc,dist;
};

struct Info{
	Info(int arg_word_id,int arg_loc,int arg_sum_dist){
		word_id = arg_word_id;
		loc = arg_loc;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct Info &arg) const{

		return sum_dist > arg.sum_dist; //総距離の昇順(PQ)
	}
	int word_id,loc,sum_dist;
};
int N,AMBIGUOUS;
int min_dist[SIZE][MAX+1];
int LENGTH[SIZE];
char words[SIZE][MAX+1];
vector<Edge> G[SIZE][MAX+1];


int main(){

	scanf("%d",&N);
	AMBIGUOUS = N;

	int length;
	for(int i = 0; i < N; i++){

		scanf("%s",words[i]);
		for(length = 0; words[i][length] != '\0'; length++);
		LENGTH[i] = length;
	}

	int from_length,match_length;
	bool FLG;

	for(int from = 0; from < N; from++){
		for(int loc = 0; loc < LENGTH[from]; loc++){
			for(int to = 0; to < N; to++){
				if(from == to && loc == 0)continue;

				from_length = LENGTH[from]-loc;
				match_length = min(from_length,LENGTH[to]);

				FLG = true;
				for(int i = 0; i < match_length; i++){
					if(words[from][loc+i] != words[to][i]){
						FLG = false;
						break;
					}
				}
				if(!FLG)continue;

				if(match_length == LENGTH[to] && loc+match_length == LENGTH[from]){ //両方ぴったり終わる
					G[from][loc].push_back(Edge(AMBIGUOUS,0,LENGTH[to]));
				}else{

					if(from_length > match_length){
						G[from][loc].push_back(Edge(from,loc+match_length,match_length));

					}else{
						G[from][loc].push_back(Edge(to,match_length,match_length));
					}
				}
			}
		}
	}

	for(int i = 0; i <= N; i++){
		for(int k = 0; k < MAX; k++){
			min_dist[i][k] = BIG_NUM;
		}
	}

	priority_queue<Info> Q;

	for(int i = 0; i < N; i++){
		min_dist[i][0] = 0;
		Q.push(Info(i,0,0));
	}

	int next_word_id,next_loc,next_dist;

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().word_id][Q.top().loc]){

			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().word_id][Q.top().loc].size(); i++){

				next_word_id = G[Q.top().word_id][Q.top().loc][i].word_id;
				next_loc = G[Q.top().word_id][Q.top().loc][i].loc;
				next_dist = Q.top().sum_dist+G[Q.top().word_id][Q.top().loc][i].dist;

				if(min_dist[next_word_id][next_loc] > next_dist){
					min_dist[next_word_id][next_loc] = next_dist;
					Q.push(Info(next_word_id,next_loc,next_dist));
				}
			}
			Q.pop();
		}
	}

	if(min_dist[AMBIGUOUS][0] == BIG_NUM){

		printf("0\n");
	}else{

		printf("%d\n",min_dist[AMBIGUOUS][0]);
	}

	return 0;
}



Measured memory_bytes: 20072
#include<iostream>
#include<cmath>
#include<algorithm>
#define Fast ios_base :: sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define loop(i, n) for(i=1; i<=n; i++)
#define ll long long
using namespace std;
int main() {
    Fast;
    ll n;
    cin >> n;
    ll mint = 1000000000002;
    ll i, tmp = 0;
    for(i=1; i<=sqrt(n); i++){
        if(n%i == 0){
            ll x = n/i;
            tmp = i + x - 2;
            mint = min(tmp, mint);
        }
    }
    cout << mint << endl;
    return 0;
}

Measured memory_bytes: 3680
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

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

    int N, Y;
    cin >> N >> Y;
    Y /= 1000;

    int x, y, z;
    bool found = false;
    for (x = 0; x <= N; ++x)
    {
        y = (Y - N - 9 * x) / 4;
        z = (5 * N + 5 * x - Y) / 4;
        if (y < 0 || z < 0) continue;
        if (10 * x + 5 * y + z == Y)
        {
            found = true;
            break;
        }
    }

    if (!found) x = y = z = -1;
    cout << x << " " << y << " " << z << "\n";
    return 0;
}



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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sfl(i,a,n) for (int i=a;i<n;i++)
#define ufl(i,a,n) for (int i=n-1;i>=a;i--)
#define SZ(x) ((int)(x).size())
#define endl '\n'
typedef long long ll;

ll power(ll a, ll b){
    ll res = 1;
    for(int i = 0; i<b; i++)
        res *= a;

    return res;
}

void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}


int main()
{
    init();
    int x,y;
    cin >>x>>y;
    cout <<(x-1)*(y-1);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
    while(1){
        int a,b,i;
        string str;
        cin>>a>>str>>b;
        if(str=="+"){
            cout<<a+b<<endl;
        }
        else if(str=="-"){
            cout<<a-b<<endl;
        }
        else if(str=="*"){
            cout<<a*b<<endl;
        }
        else if(str=="/"){
            cout<<a/b<<endl;
        }
        else{break;
        }
        i++;
    }
}

Measured memory_bytes: 1204
s = input()
l = len(s)
ans = [0]*l
count = 0
for i in range(l):
    if s[i]=="R" and s[i+1]=="R":
        count += 1
    elif s[i]=="R" and s[i+1]=="L":
        count += 1
        ans[i] += (count+1)//2
        ans[i+1] += count//2
        count = 0
for i in reversed(range(l)):
    # print(i)
    # print(s[i])
    if s[i]=="L" and s[i-1]=="L":
        count += 1
    elif s[i]=="L" and s[i-1]=="R":
        count += 1
        ans[i] += (count+1)//2
        ans[i-1] += count//2
        count = 0
print(" ".join(map(str, ans)))

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

int main(void) {
    
    int r,g,b,a;
    cin >> r >> g >> b;
    a = (r*100) + (g*10) + (b);
    if(a % 4 == 0){cout << "YES" << "\n";}
    if(a % 4 != 0){cout << "NO" << "\n";}
    
    return 0;
}


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

int main(){
  int N, K;
  cin >> N >> K;
  int num0=0, num1=0;
  for(int i=1; i<=N; i++){
    if(i%K==0) num0++;
    else if(i%K==K/2) num1++;
  }
  if(K%2==1){
    cout << (long)pow(num0,3) << endl;
    return 0;
  }
  cout << (long)pow(num0,3)+(long)pow(num1,3) << endl;
  return 0;
}


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

int main(void)
{
    char h[100];
    int j;
    int x,i;
    int sum;
    int len;
    while (scanf("%s", h) != EOF)
    {
        i = 0;
        x = 0;
        sum = 0;
        len = strlen(h);
        

        for (j = len - 1; j >= 0; j--){
            switch(h[j])
            {
                case 'I':
                //printf("%d", i);
                
                if(h[j + 1] != 'I' && j != len - 1){
                    sum -= 1;
                    //printf("%d>", sum);
                    break;
                }
                
                sum += 1;
                break;

                case 'V':
                
                if ((h[j + 1] != 'I' && h[j + 1] != 'V') && j != len - 1){
                    sum -= 5;
                    break;
                }

                sum += 5;
                break;

                case 'X':
                if (h[j + 1] != 'I' && h[j + 1] != 'V' && h[j + 1] != 'X' && j != len - 1){
                    sum -= 10;
                    break;
                }
                sum += 10;
                break;

                case 'L':
                if ((h[j + 1] == 'C' || h[j + 1] == 'D' || h[j + 1] == 'M') && j != len - 1){
                    sum -= 50;
                    break;
                }
                sum += 50;
                break;

                case 'C':
                if ((h[j + 1] == 'D' || h[j + 1] == 'M') && j != len - 1){
                    sum -= 100;
                    break;
                }
                sum += 100;
                break;

                case 'D':
                if(h[j + 1] == 'M' && j != len - 1){
                    sum -= 500;
                }
                sum += 500;
                break;

                case 'M':
                sum += 1000;
                break;
            }
            //printf("<%d> ", sum);
        }
    printf("%d\n", sum);

    }
    return (0);
}


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

using ll = long long;

int main() {
    int N, K, x, y;
    cin >> N >> K;
    int L = 2 * K;
    vector<vector<int>> B(L, vector<int>(L, 0));
    vector<vector<int>> W(L, vector<int>(L, 0));
    char c;
    rep(i, N) {
        cin >> x >> y >> c;
        if (c == 'B') B[x % L][y % L]++;
        else W[x % L][y % L]++;
    }
    vector<vector<int>> s(L + 1, vector<int>(L + 1, 0));
    vector<vector<int>> t(L + 1, vector<int>(L + 1, 0));
    rep(i, L) rep(j, L) {
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + B[i][j];
        t[i + 1][j + 1] = t[i][j + 1] + t[i + 1][j] - t[i][j] + W[i][j];
    }
    int ans = 0;
    rep(i, K) {
        rep(j, K) {
            int x = s[L][L] - s[K + i][L] + s[i][L];
            x = x - s[L][K + j] + 2 * (s[K + i][K + j] - s[i][K + j]);
            x = x + s[L][j] - 2 * (s[K + i][j] - s[i][j]);
            int y = t[L][L] - t[K + i][L] + t[i][L];
            y = y - t[L][K + j] + 2 * (t[K + i][K + j] - t[i][K + j]);
            y = y + t[L][j] - 2 * (t[K + i][j] - t[i][j]);
            int z = x + t[L][L] - y;
            if (z > ans) {
                ans = z;
            }
            z = y + s[L][L] - x;
            if (z > ans) {
                ans = z;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 63104
Option Infer On
Imports System.Collections.Generic
Imports System.Console

Module Program
    Sub Main()
        Dim H As Integer = NextInt()
        Dim W As Integer = NextInt()

        Dim a As String() = New String(H - 1) {}
        For i = 0 To H - 1
            a(i) = ReadLine()
        Next

        For i = 0 To H + 1
            Write("#")
            If i = 0 OrElse i = H + 1 Then
                Write(New String("#"c, W))
            Else
                Write(a(i - 1))
            End If
            WriteLine("#")
        Next
    End Sub

    Function NextInt() As Integer
        Return CInt(NextString())
    End Function

    Function NextString() As String
        Dim result As New List(Of Char)
        Do
            Dim tmp = Read()
            If tmp < 0 Then Exit Do
            Dim nextChar = Chr(tmp)

            If Not Char.IsWhiteSpace(nextChar) Then
                result.Add(nextChar)
            ElseIf nextChar <> vbCr Then
                Exit Do
            End If
        Loop
        Return New String(result.ToArray())
    End Function

End Module


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  bool jud = true;
  rep(i,n) {
    if (a[i]%2 != 0) continue;
    if (a[i]%3 != 0 && a[i]%5 != 0) jud = false;
  }
  if (jud == true) cout << "APPROVED" << endl;
  else cout << "DENIED" << endl;
  return 0;
}

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	char a;
	cin >> a;
	if(a>='A'&&a<='Z')cout << "A";
	else cout << "a";
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 3648
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto n = readln.chomp.to!int;
  auto m = n;
  int cnt;
  foreach_reverse(i; 0..10) {
    auto e = 10 ^^ i;
    auto d = n / e;
    n %= e;
    cnt += d;
  }
  writeln(m % cnt ? "No" : "Yes");
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
 
int main()
{
  long long n,x,y;
  double d;
  cin>>n>>d;
  double dis=0,dist=0;
  long long c=0;
  for(long long i=0; i<n; i++)
  {
    cin>>x>>y;
    dis=x*x+y*y;
    dist=sqrt(dis);
 	 if(dist<=d)
    	c++;
  }
  cout<<c<<endl;
  return(0);
}

Measured memory_bytes: 3772
def submit():
    n, m = map(int, input().split())
    wa_count = {i: 0 for i in range(1, n + 1)}
    ac_status = {i: False for i in range(1, n + 1)}
    
    penalty = 0
    for _ in range(m):
        p, s = input().split()
        p = int(p)

        if ac_status[p]:
            continue
        
        if s == "AC":
            ac_status[p] = True
            penalty += wa_count[p]
        else:
            wa_count[p] += 1

    print("{} {}".format(sum(ac_status.values()), penalty))


if __name__ == "__main__":
    submit()

Measured memory_bytes: 27368
#include<iostream>
using namespace std;
#define n 10000

int main(){

int N,a[n],i=0,count=0;

std::cin >> N;
while(i<N){
  std::cin >> a[i];
  i++;
}

i=0;

while(i<N){
  if(a[i]%2==0){
    while(a[i]%2==0){
      a[i]=a[i]/2;
      count++;
    }
  }
  i++;
}

std::cout << count << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
#define MOD 1000000007

int w, h;
vvi c(60, vi(60));
vector<vector<bool>> flag(60, vector<bool>(60));

void dfs(int i, int j){
  flag.at(i).at(j) = false;

  vector<int> dx = {0, 0, 1, -1, 1, -1, -1, 1};
  vector<int> dy = {1, -1, 0, 0, 1, 1, -1, -1};
  for(int k = 0; k < 8; k++){
    int y = i + dy.at(k);
    int x = j + dx.at(k);
    if(x < 0 || x >= w || y < 0 || y >= h) continue;
    if(c.at(y).at(x) && flag.at(y).at(x)) dfs(y, x);
  }
}

int main(){
while(true){
  cin >> w >> h;
  if(w == 0 && h == 0) break;

  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> c.at(i).at(j);
      flag.at(i).at(j) = true;
    }
  }
  int result = 0;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(c.at(i).at(j) && flag.at(i).at(j)){
        dfs(i, j);
        result++;
      }
    }
  }
  cout << result << endl;
}
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int N = 1e5+10;
int a[N];
int main(){
    int k,a,b;
    cin >> k >> a >> b;
    if(a%k == 0 || b%k==0){
        puts("OK");
    }else{
        int d = b/k*k;
        if(d <= b && d>=a){
            puts("OK");
        }else{
            puts("NG");
        }
    }
    return 0;
}

Measured memory_bytes: 3596
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx") 
#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	int ret=0; char c=getchar();
	while(c<48||c>57)c=getchar();
	while(c>=48 && c<=57)ret=ret*10+c-48,c=getchar();
	return ret;
}
#define N 6006
int op[N],LL[N],flag,vis[N],L[N],vi[N],qn,n,m,p,cnt[N],c[N][3],tot,a[N],u,v,w,C[N][2],A[N];
int q[9000009];
long long D[N];

void dfs(int p)
{
	L[p]=1;
	for(int o=A[p]; o; o=C[o][1]){
		if(L[C[o][0]])continue;
		dfs(C[o][0]);
	}
}
void dfss(int p)
{
	LL[p]=1;
	for(int o=a[p]; o; o=c[o][1]){
		if(LL[c[o][0]])continue;
		dfss(c[o][0]);
	}
}

void df(int u){
	op[u]=1;
    if(flag) return ;
    vis[u]=true;
    for(int o=a[u];o;o=c[o][1]){
        if(flag) return ;
        int v=c[o][0];
        if(!L[v])continue;
        if(D[u]+c[o][2]<D[v]){
            D[v]=D[u]+c[o][2];
            if(vis[v]){
                flag=true;
                return;
            }else{
                df(v);
            }
        }
    }
    vis[u]=false;
}
 
int main()
{
	n=read(); m=read(); p=read();
	for(int i=1;i<=m;++i){
		u=read(); v=read(); w=read();
		c[++tot][0]=v; c[tot][1]=a[u]; a[u]=tot; c[tot][2]=p-w; 
		C[tot][0]=u; C[tot][1]=A[v]; A[v]=tot; 
	} 
	
	dfs(n);
	if(!L[1]){
		puts("-1");
		return 0;
	}
	
	dfss(1);
	
	for(int i=1;i<=n;++i)if(!op[i]&&L[i]&&LL[i]){
	memset(D,0,sizeof(D));
	df(i);
	if(flag){
		puts("-1");
		return 0;
	}
	}
	
	for(int i=1;i<=n;++i)D[i]=1e9,vi[i]=0; D[1]=0;
	
	q[qn=1]=1;
	for(int q1=1;q1<=qn;++q1){
		u=q[q1]; vi[u]=0;
		for(int o=a[u]; o; o=c[o][1]){
			v=c[o][0];
			if(!L[v])continue;
			if(D[u]+c[o][2]<D[v]){
				D[v]=D[u]+c[o][2];
				if(!vi[v]){
					q[++qn]=v;
					vi[v]=1;
				}
			}
		}
	}
	printf("%lld\n",max(0ll,-D[n]));
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    string d;
    cin>>d;
    if (d=="SAT"){
        cout<<"1"<<endl;
    }
    if(d=="FRI"){
        cout<<"2"<<endl;
    }
    if(d=="THU"){
        cout<<"3"<<endl;
    }
    if(d=="WED"){
        cout<<"4"<<endl;
    }
    if(d=="TUE"){
        cout<<"5"<<endl;
    }
    if(d=="MON"){
        cout<<"6"<<endl;
    }
    if(d=="SUN"){
        cout<<"7"<<endl;
    }
}


Measured memory_bytes: 256
program change_a_little_bit
    implicit none
    integer(8),parameter:: md=1000000007_8
    integer(8):: n,i,ans=0
    integer(8),allocatable:: c(:)

    read*,n
    allocate(c(n))
    read*,c(:)
    call merge_sort(c,1_8,n)
    
    do i=1, n
        ans = mod(ans + mod(c(i)*mod(pow_fast(2_8,n-1,md)+mod(pow_fast(2_8,n-2,md)*(n-i),md),md),md),md)
    end do

    print*, mod(ans*pow_fast(2_8,n,md),md)
contains

recursive subroutine merge_sort(ar,fst,lst)
    integer(8):: ar(:), fst, lst, mid, tmp

    if (lst-fst < 2) then
        if(ar(lst) < ar(fst)) then
            tmp = ar(lst)
            ar(lst) = ar(fst)
            ar(fst) = tmp
        end if
        return
    end if

    mid = (fst+lst)/2
    call merge_sort(ar,fst,mid)
    call merge_sort(ar,mid+1,lst)
    call merge(ar,fst,mid,lst)
end subroutine

subroutine merge(ar,fst,mid,lst)
    integer(8):: ar(:), fst, mid, lst
    integer(8),pointer:: tmp(:)
    integer(8):: it,il,ir

    allocate(tmp(lst-fst+1))
    it = 1
    il = fst
    ir = mid+1
    do while(il<=mid .and. ir<=lst)
        if (ar(il) <= ar(ir)) then
            tmp(it) = ar(il)
            il=il+1        
        else
            tmp(it) = ar(ir)
            ir=ir+1
        end if
        it=it+1
    end do

    if (ir > lst) then
        tmp(it:) = ar(il:mid)
    else
        tmp(it:) = ar(ir:lst)
    end if

    ar(fst:lst) = tmp(:)
    deallocate(tmp)
end subroutine

function pow_fast(x,pow,md) result(ret)
    integer(8),value:: x, pow
    integer(8)::md,ret

    ret=1_8
    if (x==1 .or. pow==0) return

    do while(pow > 0_8)
        if (mod(pow,2_8) == 1_8) then
            ret = mod(ret*x,md)
        end if
        x = mod(x*x,md)
        pow = pow/2_8
    end do

end function



end program change_a_little_bit

Measured memory_bytes: 4644
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)

N, u, v = map(int, input().split())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(v-1)
dist_v = tr.dist
tr.dfs(u-1)
dist_u = tr.dist
ans = 0
for du, dv in zip(dist_u, dist_v):
    if du < dv:
        ans = max(ans, dv - 1)
print(ans)

Measured memory_bytes: 52564
K, N = map(int, input().split())
lists = list(map(int, input().split()))

lists_slic = lists[1:] + lists[0:1]

# print(lists_slic)
a = 0
for i in range(len(lists)):
    if lists_slic[i] - lists[i] < 0:
        b = lists_slic[i] - lists[i] + K
        if b > a:
            a = b
    else:
        if (lists_slic[i] - lists[i])>a:
            a = lists_slic[i] - lists[i]

c = K - a

print(c)

Measured memory_bytes: 26436
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <string.h>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i > 0; i--)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t int64;

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

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; }


class C {
	int n, k;
public:
	C()
	{
		cin >> n >> k;
	}
	void solve()
	{
		int64 ans;
		int64 options{ n / k };
		ans = options * options * options;

		if (!(k & 1))
		{
			int half = k / 2;
			if (n >= half)
				options = (int64)1 + (n - half) / k;
			else
				options = 0;

			ans += options * options * options;
		}

		cout << ans << endl;
	}	
};


int main()
{
	C solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define mp make_pair
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}

};

int main() {
	int n, m;
	cin >> n >> m;
	string a, b;
	cin >> a >> b;
	ll g = gcd(n, m);
	ll l = 1ll*n*m / g;
	int ra=n/g, rb=m/g;
	bool ans = true;
	rep(i, g) {
		if (a[ra*i]!=b[rb*i])ans = false;
	}
	cout << (ans ? l : -1);

}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include  "bits/stdc++.h"
using namespace std;
#define I_AM_SPEED  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define printclock  cerr <<"Time : "<<(double)clock()/(double)CLOCKS_PER_SEC<<" sec\n";
#define mp(a , b)   make_pair(a , b)
#define eb(a)       emplace_back(a)
#define SZ(n)       ((int)(n).size())
#define all(n)      (n).begin(), (n).end()
#define anal           '\n'
#define mod         1000000007
#define fst         first
#define sec         second
#define pr(n)       cerr << n  << " ";
#define pfor(a)     for(auto (w) : (a)) pr(w)
//const double PI = acos(-1.0);
typedef long long ll;
typedef unsigned long long ull;

//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-



//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
int main(){
I_AM_SPEED;
#ifndef ONLINE_JUDGE  
        freopen("input.in", "r", stdin);
        freopen("output.in", "w", stdout);
#endif 
//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
    
  string s; cin  >> s;
  int n = s.length();
  if(s[n-1] != 's'){
       s += "s";
       cout << s << anal;
  }
  else if(s[n-1] == 's'){
      s += "es";
      cout << s << anal;
  }
    
  
//_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
//printclock; 
return  0 ;      
}        



      

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

int main()
{
  int a,b;
  scanf("%d%d",&a,&b);
  if(a+b<24)
      printf("%d",a+b);
  
  else
  {
    int ans=24-a;
    b-=ans;
    printf("%d",b);
  }
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define double long double
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=(ll)a-1;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define print(v) cout<<v<<endl
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define printYES cout<<"YES"<<endl
#define printNO cout<<"NO"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<26;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas x,ddatas y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

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

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}
int main(){
  // startupcpp();
  // ll test;cin>>test;while(test--){
  ll i,j=0,N,K;
  string s,ans="";
  cin>>s;
  N=s.size();
  vec term(1,N),ch(26,0);
  brep(i,N){
    j|=1LL<<(s[i]-'a');
    if(j+1==inf){
      j=0;
      term.pb(i);
    }
  }
  K=term.size();
  rep(i,term[K-1]){
    ++ch[s[i]-'a'];
  }
  N=0;
  while(ch[N])++N;
  ans+='a'+N;
  reverse(all(term));
  j=term[0];
  rep1(i,K){
    ch=vec(26,0);
    while(s[j++]-'a'!=N);
    while(j<term[i])++ch[s[j++]-'a'];
    N=0;
    while(ch[N])++N;
    ans+='a'+N;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 640
import java.util.Arrays;
import java.util.Scanner;

public class Main {


  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] h = new int[N+10];
    for (int i = 0; i < N; i++) {
      h[i] = sc.nextInt();
    }
    int[] dp = new int[N+10];

    Arrays.fill(dp,Integer.MAX_VALUE);

    dp[0] = 0;
    dp[1] = Math.abs(h[0]-h[1]);
    for (int i = 2; i <N ; i++) {

      //kubaru dp
      dp[i] = Math.min(
          ( dp[i-2] + Math.abs(h[i-2]-h[i]))  ,
          ( dp[i-1] + Math.abs(h[i-1]-h[i]))
          );
    }
//    dp[0]=0;
//    for (int i = 0; i < N; i++) {
//      dp[i+1] = Math.min(dp[i+1], dp[i] + Math.abs(h[i] - h[i+1]));
//      dp[i+2] = Math.min(dp[i+2], dp[i] + Math.abs(h[i] - h[i+2]));
//    }

    System.out.println(dp[N-1]);


  }


}


Measured memory_bytes: 50092
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		boolean playFlag = true;
		String a = sc.next();
		String b = sc.next();
		String c = sc.next();

		String person = a;
		String personNext = person.substring(0, 1);
		a = person.substring(1);

		while (playFlag) {

			if ("a".equals(personNext)) {
				if (0 == a.length()) {
					System.out.println("A");
					break;
				}
				person = a;
				personNext = a.substring(0, 1);
				a = a.substring(1);
			} else if ("b".equals(personNext)) {
				if (0 == b.length()) {
					System.out.println("B");
					break;
				}
				personNext = b.substring(0, 1);
				b = b.substring(1);
				person = b;
			} else {
				if (0 == c.length()) {
					System.out.println("C");
					break;
				}
				personNext = c.substring(0, 1);
				c = c.substring(1);
				person = c;
			}
		}
		sc.close();
	}
}


Measured memory_bytes: 21844
n = int(input())
vote_ratio = [ list(map(int, input().split())) for _ in range(n)]

# ans = vote_ratio[0] は同じオブジェクトを参照してしまうので避ける
ans = [vote_ratio[0][0], vote_ratio[0][1]]

for i in range(1,n):
	# bairitsu = max( math.ceil(ans[0] / vote_ratio[i][0]), math.ceil(ans[1] / vote_ratio[i][1]))
	# と書きたいところだが、浮動小数点数を経由したときに不正確になるので代わりにこうする。
	bairitsu = max( 
		(ans[0] + vote_ratio[i][0] - 1)// vote_ratio[i][0],
		(ans[1] + vote_ratio[i][1] - 1)// vote_ratio[i][1])
	ans = [vote_ratio[i][0] * bairitsu, vote_ratio[i][1] * bairitsu]

print(sum(ans))


Measured memory_bytes: 3188
// ※※※ 解答不能 ※※※
// pes氏.
// https://atcoder.jp/contests/abc150/submissions/9406315
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

vector<int> Zalgorithm(auto S){
    vector<int> res(S.size());
    res[0] = S.size();
    int i = 1, j = 0;
    while(i < S.size()){
        while(i + j < S.size() && S[j] == S[i + j]) ++j;
        res[i] = j;
        if(j == 0) { ++i; continue;}
        int k = 1;
        while(i + k < S.size() && k + res[k] < j) res[i + k] = res[k], ++k;
        i += k; j -= k;
    }
    return res;
}

int main(){
    int N;
    scanf("%d", &N);
    vector<int> a(N), b(N);
    for(auto& t : a) scanf("%d", &t);
    for(auto& t : b) scanf("%d", &t);
    vector<int> xa(N), xb(N);
    rep(i, N){
        xa[i] = a[i] ^ a[(i + 1) % N];
        xb[i] = b[i] ^ b[(i + 1) % N];
    }
    vector<int> z = xb;
    z.insert(z.end(), xa.begin(), xa.end());
    z.insert(z.end(), xa.begin(), xa.end());
    auto len = Zalgorithm(z);
    rep(i, N) if(len[N + i] >= N) printf("%d %d\n", i, (a[i] ^ b[0]));
    return 0;
}

Measured memory_bytes: 11436
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const int mod = 1e9+7;

const ll MOD = 1e9+696969;
const long long INF = 1e18+3;
#define maxn 2010

int dp[2 * maxn + 100][2 * maxn + 100], jest[2 * maxn + 100][2 * maxn + 100];
ll fac[8010], invfac[8010];

ll potmod(ll a, ll b)
{
	ll res = 1;
	while (b > 0)
	{
		if (b & 1) res = (res * a ) % mod;
		a = (a * a)%mod;
		b /= 2;
	}
	return res;
}

inline ll binom(int n, int k)
{
	return fac[n] * invfac[k] % mod * invfac[n - k] % mod;
}

int x[200100], y[200100], n;

int main()
{
	fac[0] = invfac[0] = 1;
	FOR(i, 1, 8000) 
	{
		fac[i] = fac[i-1] * i % mod;
		invfac[i] = potmod(fac[i], mod - 2);
	}
	boost;
	cin >> n;
	FOR(i, 1, n) 
	{
		cin >> x[i] >> y[i];
		jest[x[i] + maxn][y[i] + maxn]++;
		jest[-x[i] + maxn][-y[i] + maxn]++;
	}
	
	ll res = 0;
	for (int i=-2000; i<=2000; ++i)
		for (int j=-2000; j<=2000; ++j)
		{
			if (i < 0 && j < 0) dp[i + maxn][j + maxn] += jest[i + maxn][j + maxn];
			dp[i + maxn][j + maxn] += dp[i + maxn - 1][j + maxn];
			dp[i + maxn][j + maxn] += dp[i + maxn][j + maxn - 1];
			while (dp[i + maxn][j + maxn] >= mod) dp[i + maxn][j + maxn] -= mod;
			if (i > 0 && j > 0) res += (ll)jest[i + maxn][j + maxn] * dp[i + maxn][j + maxn];
			res %= mod;
		}
	
	//here the part of doing the dp
	
	
	FOR(i, 1, n)
		FOR(j, i, i) res += mod - binom(x[i] + y[i] + x[j] + y[j], x[i] + x[j]);
	res %= mod;
	res *= potmod(2, mod - 2);
	res %= mod;
	
	cout << res;
}


Measured memory_bytes: 133120
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <math.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define repP(i, a, b) for(int i = a; i < b; i++)
#define repM(i, a, b) for(int i = a - 1; i >= b; i--)

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0, i = 0, j = 0;
  int sum = 0, num = 0, count = 0, ans = 0, min = 0, max = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int a1[999999], a2[999999], a3[999999];
  //char s1[200000], s2[200000], s3[200000];
  //string s1, s2, s3;
  
  cin >> a >> b >> c;
  if(a + b +c <= 21){
    cout << "win"<< endl;
  }else{
    cout <<"bust"<<endl;
  }

}
  


Measured memory_bytes: 256
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
ans = 1
for i in range(K, N + 1):
    ans += i * (2 * N - i + 1) // 2 % MOD - i * (i - 1) // 2 % MOD + 1
    ans %= MOD
print(ans)

Measured memory_bytes: 9016
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<numeric>
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define ll long long

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	int x = 0;
	while (n!=0) {
		n--;
		x += n;
	}
	int y = 0;
	while (m != 0) {
		m--;
		y += m;
	}

	cout << x + y << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
#define TE 2e5
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int N, K; cin >> N >> K;
	vector<pair<ll, int>> su(N);
	for (int i = 0; i < N; i++) {
		cin >> su[i].second >> su[i].first;
	}

	sort(su.begin(), su.end(),greater<pair<ll,int>>());
	vector<pair<ll,int>> ans;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	map<int, int> cnt;
	ll tot = 0, ki = 0;
	for (int i = 0; i < K; i++) {
		ll sc = su[i].first;
		int id = su[i].second;
		if (cnt[id] == 0) {
			ans.push_back(make_pair(sc, id));
			ki++;
		}
		else pq.emplace(sc, id);
		cnt[id]++;
		tot += sc;
	}

	tot += ki * ki;
	ll temp = tot;
	for (int i = K; i < N; i++) {
		ll sc = su[i].first;
		int id = su[i].second;
		if (cnt[id] == 0) {
			cnt[id]++;
			ans.push_back(make_pair(sc, id));
			if (pq.empty())break;
			ll sc2 = pq.top().first;
			int id2 = pq.top().second;
			cnt[id2]--;
			temp -= sc2 + ki * ki;
			ki++;
			temp += sc + ki * ki;
			pq.pop();
			tot = max(tot, temp);
			/*
			cout << "tot=" << tot << " ki=" << ki << " sc=" << sc << endl;
			for (int j = 0; j < ans.size(); j++) {
				cout << ans[j].second << " ";
			}
			cout << endl;
			*/
		}	
	}

	cout << tot << endl;
}

Measured memory_bytes: 9604
from sys import stdin

if __name__ == '__main__':
    N, M = [ int(x) for x in stdin.readline().rstrip().split() ]
    probs = {}
    for i in range(M):
        a, b = [x for x in stdin.readline().rstrip().split()]
        s = (a, b)
        if not s in probs:
            probs[s] = 0
        if b == 'AC':
            probs[s] = 1
        else:
            if (a, 'AC') in probs:
                pass
            else:
                probs[s] += 1

    AC = 0
    WA = 0

    for key, value in probs.items():
        if key[1] == 'WA':
            if (key[0], 'AC') in probs:
                WA += value
        else:
            AC += 1
    print(AC, WA)


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

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <numeric>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

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

const int Maxn = 200010;

int a[Maxn], b[Maxn];

int n;

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

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }

    int cnt = 0;
    ll sum = 0;
    vector<ll> v;
    for (int i = 0; i < n; ++i) {
        if (a[i] < b[i]){
            ++cnt;
            sum += b[i] - a[i];
        }else if (a[i] > b[i]){
            v.emplace_back(a[i] - b[i]);
        }
    }
    sort(v.begin(), v.end(), greater<ll>());
    for(auto &i : v){
        if (sum == 0) break;
        sum = max(sum - i, 0LL);
        ++cnt;
    }
    if (sum > 0) cout << -1 << endl;
    else cout << cnt << endl;
}

Measured memory_bytes: 1660
#include<bits/stdc++.h>
using namespace std;
int d[1000000];
int main(){
	int n,nn,count=0,x=0,z,p=0;
	cin >> n;
	nn=n+1;
	for(int i=1;i<nn;i++){
		cin >> d[i];
	}
	sort(d,d+nn);
	x=n/2;
	cout << d[x+1]-d[x] << '\n';
return 0;
}


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

int main() {
	int j;
	cin >> j;
	int a[1000];
	int b[1000] = {0};
	for (int i = 0; i < j*3; i++){
		cin >> a[i];
	}
	for (int w=0; w< j*3; w += 3){
		for (int x = 0; x < j * 3; x += 3){
			if (w != x){
				if (a[w] == a[x]){
					b[w] = 1;
				}
			}
		}
   }			
for (int w = 1; w< j*3; w += 3){
	for (int x = 1; x < j*3; x += 3){
		if (w != x){
			if (a[w] == a[x]){
				b[w] = 1;
			}
		}
	}
}
for (int w = 2; w < j*3; w += 3){
	for (int x = 2; x < j*3; x += 3){
		if (w != x){
			if (a[w] == a[x]){
				b[w] = 1;
			}
		}
	}
}
for (int i = 0; i < j * 3; i++){
	if (b[i] == 1){
		a[i] = 0;
	}
}
	for (int i = 0; i < j*3; i+=3){
         cout << a[i] + a[i + 1] + a[i + 2] << endl;
	}
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long ll;
typedef vector<int >    vecint;
typedef vector<ll >     vecll;
typedef vector<string > vecstr;
typedef vector<bool > vecbool;
////////////////////////////////////////////////
int main()
{
  int n, m; cin >> n >> m;
  vecint a(m);
  REP(i,m) cin >> a[i];
  vecint dp(n + 1,0);
  dp[0] = 1;
  bool ok1 = true;
  ok1 = binary_search(all(a), 1);
  dp[1] = (!ok1);
  bool ok2 = true;
  for(int i = 2; i <= n; i ++ ){
    ok1 = binary_search(all(a), i - 1);
    ok2 = binary_search(all(a), i - 2);
    dp[i] = (!ok1)*dp[i - 1] + (!ok2)*dp[i - 2];
    dp[i] %= MOD;
    if(dp[i] == 0){
      break;
    }
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 1024
BIG_NUM = 2000000000

while True:

    H,W = map(int,input().split())
    if H == 0 and W == 0:
        break
    for i in range(H):
        for k in range(W):
            if i == 0 or i == H-1 or k == 0 or k == W-1:
                print("#",end = "")
            else:
                print(".",end = "")
        print()

    print() #データセットの区切り



Measured memory_bytes: 7000
N = int(input())
F = [list(map(int, input().split())) for _ in range(N)]
P = [list(map(int, input().split())) for _ in range(N)]

ans = -10000000000
for bit in range(1, 1<<10):
  now = 0
  for i in range(N):
    c = 0
    for j in range(10):
      if (1&bit>>j) & F[i][j]:
        c += 1
    now += P[i][c]
  ans = max(ans, now)
print(ans)

Measured memory_bytes: 3064
// O(1) space 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 1e9 + 7;

const ll INF = 1e18;

int main()
{

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

    int N;
    cin >> N;

    vector<vector<int>> A(N, vector<int>(2));

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

    auto comp = [&](vector<int>& a, vector<int>& b) {
        return a[0] + a[1] < b[0] + b[1];
    };

    sort(A.begin(), A.end(), comp);

    // vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, INF));

    vector<ll> dp (N+1 , INF); 


    dp[0] = 0 ; 


    for (int i = 1; i <= N; ++i) {
        for (int j = i; j >= 1; --j) {
            if (A[i - 1][0] >= dp[j - 1]) {
                dp[j] = min(dp[j], dp[j - 1] + A[i - 1][1]);
            }
        }
    }

    for (int j = N; j >= 0; --j) {
        if (dp[j] != INF) {
            cout << j << "\n";
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,x;
    cin >>a>>b>>c>>x;
    int ans=0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(500*i+100*j+50*k==x){
                    ans++;
                }
            }
        }
    }
    cout <<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const long long mod_const = 1e9+7;
using MIte = multimap<long, long, greater<long> >::iterator;

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

	int N, M;
	cin >> N >> M;

	vector<int> vA(N,0);
	rep(i, N) {
		cin >> vA[i];
	}
	sort(vA.begin(), vA.end());

	vector<long> vB(M, 0);
	vector<long> vC(M, 0);
	multimap<long, long> mpB;
	multimap<long, long, greater<long> > mpC;

	rep(i, M) {
		cin >> vB[i] >> vC[i];
		mpB.insert(make_pair(vB[i], i));
		mpC.insert(make_pair(vC[i], i));
	}

	long pivot = 0;
	for (MIte e = mpC.begin(); e != mpC.end(); ++e) {
		long idx = e->second;
		long firstpivot = pivot;
		for (long i = firstpivot; i != firstpivot + vB[idx]; ++i) {
			if (vA[i] >= e->first) {
				break;
			}
			vA[i] = e->first;
			pivot++;
		}
	}

	long long sum = 0;
	for (long i = 0; i != vA.size(); ++i) {
		sum += (long long)vA[i];
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 14720
N, M = map(int, input().split())
l = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)

ans = 0


# pos:現在地 visit:巡回済み頂点のリスト
def dfs(pos, visit):
    global l, ans
    f = True
    visit.append(pos)
    for d in l[pos]:
        if (d in visit):
            continue
        f = False
        dfs(d, visit.copy())

    if (f):
        if (len(visit) == N):
            ans += 1


dfs(0, [])
print(ans)


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

using namespace std;

int n,m; 
int k[100];
int s[100][100];
int p[100];
int a[100];
int ans;

int check()
{
	for(int i=1;i<=m;i++)
	{
		int cnt=0;
		for(int j=1;j<=k[i];j++)
		{
			cnt+=a[s[i][j]];
		}
		if(cnt%2!=p[i])
		{
			return 0;
		}
	}
	return 1;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&k[i]);
		for(int j=1;j<=k[i];j++)
		{
			scanf("%d",&s[i][j]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&p[i]);
	}
	for(int i=0;i<pow(2,n);i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[j]=(i>>j-1)&1;
		}
		ans+=check();
	}
	printf("%d\n",ans);
	return 0;
}

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

using namespace std;

vector<vector<pair<int, int>>> edges;
vector<int> colors;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int N;
  cin >> N;

  edges.resize(N);
  for (int i = 1; i < N; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    edges[--u].emplace_back(--v, w % 2);
    edges[v].emplace_back(u, w % 2);
  }
  colors.resize(N);

  vector<bool> done(N);
  queue<int> q;
  q.emplace(1);
  for (; !q.empty(); q.pop()) {
    auto cur = q.front();
    auto& nexts = edges[cur];
    for (auto next : nexts) {
      if (!done[next.first]) {
        done[next.first] = true;
        colors[next.first] = next.second ^ colors[cur];
        q.emplace(next.first);
      }
    }
  }

  for (auto color : colors) {
    cout << color << endl;
  }
}

Measured memory_bytes: 6912