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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

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

    vector<int> a(n);
    vector<vector<ll> > dp(n+1, vector<ll>(2));
    dp[0][0] = 0, dp[0][1] = -INF;

    rep(i, n) {
        cin >> a[i];
        dp[i + 1][0] = max(dp[i][0] + a[i], dp[i][1] - a[i]);
        dp[i + 1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i]);
    }

    cout << dp[n][0] << endl;
    return 0;
}

Measured memory_bytes: 6144
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rg register
#define _ 510
int w, h, m[_][_], r[_][_], b[_][_];
int main(){
	scanf("%d%d", &w, &h);
	for(int i=1; i<=w; ++i)
		for(int j=1; j<=h; ++j){
			char ch=getchar();
			while(ch!='.'&&ch!='#') ch=getchar();
			if(ch=='#') m[i][j]=r[i][j]=b[i][j]=1;
		}

	for(int i=2; i<h; ++i) r[1][i]=b[w][i]=1;
	
	for(int j=2; j<h; j+=2)
		for(int i=2; i<w; ++i)
			r[i][j]=b[i][j|1]=1;
	
	for(int i=1; i<=w; ++i){
		for(int j=1; j<=h; ++j)
			if(r[i][j]) putchar('#');
			else putchar('.');
		putchar('\n');
	}
	puts("");
	for(int i=1; i<=w; ++i){
		for(int j=1; j<=h; ++j)
			if(b[i][j]) putchar('#');
			else putchar('.');
		putchar('\n');
	}

/*	for(int i=1; i<=w; ++i){
		for(int j=1; j<=h; ++j)
			if(r[i][j]&b[i][j]) putchar('#');
			else putchar('.');
		putchar('\n');
	}
*/
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#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++)

int main() {
    int N;
    cin >> N;
    if (N % 2){
        cout << N / 2 + 1 << endl;
    } else {
        cout << N / 2 << endl;
    }
    return 0;
}


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

int main(){
  string S;
  cin>>S;
  
  if(S[1]=='R'){
    if(S[0]=='R' and S[2]=='R'){
      cout<<3<<endl;
    }else if(S[0]=='S' and S[2]=='S'){
      cout<<1<<endl;
    }else{
      cout<<2<<endl;
    }
  }else if(S[0]=='S' and S[2]=='S'){
    cout<<0<<endl;
  }else{
    cout<<1<<endl;
  }
}      

Measured memory_bytes: 3596
import heapq
import sys
def main():
    input = sys.stdin.readline

    def dijkstra(s,edge):
        #始点sから各頂点への最短距離
        d = [10**20] * n
        used = [True] * n #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for a,b in edge[s]:
            heapq.heappush(edgelist,a*(10**6)+b)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge%(10**6)]:
                continue
            v = minedge%(10**6)
            d[v] = minedge//(10**6)
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
        return d

    n,x,y = map(int,input().split())

    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(n-1):
        edge[i].append((1,i+1))
        edge[i+1].append((1,i))
    edge[x-1].append((1,y-1))
    edge[y-1].append((1,x-1))

    for i in range(n):
        edge[i] = tuple(edge[i])
    edge = tuple(edge)

    ans = [0 for _ in range(n)]
    for i in range(n):
        #dijkstra(始点,edge)
        res = dijkstra(i,edge)
        for j in range(i+1,n):
            ans[res[j]] += 1

    for i in range(1,n):
        print(ans[i])

if __name__ == '__main__':
    main()


Measured memory_bytes: 79452
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define ll long long
#define LL ll
#define mem(arry,x) memset(arry,x,sizeof(arry))
const int maxn=3e2+10;
const int INF=0x3f3f3f3f;

int main()
{
    int n,m,t;
    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
    {
        if(n+m>=t) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int ll
#define ld double
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define len length()
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect

void solve() {
    int n; string s;
    cin >> n >> s;
    set <int> num[10];
    loop(i, n)
        num[s[i] - '0'].insert(i);
    int ans = 0;
    loop(i, 10) {
        if (num[i].size() == 0) continue;
        int x = *num[i].begin();
        loop(j, 10) {
            if (num[j].upper_bound(x) == num[j].end()) continue;
            int y = *num[j].upper_bound(x);
            loop(k, 10)
                if (num[k].upper_bound(y) != num[k].end()) ++ans;
        }
    }
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

const ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

int X1,Y1,X2,Y2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X1>>Y1>>X2>>Y2;
	ll ret=0;
	ll pat=0;
	FOR(i,Y1+1) pat+=comb(X1+Y1,i);
	ret=pat;
	for(y=Y1+1;y<=Y2;y++) {
		pat=(pat*2+comb(X1+y-1,y))%mo;
		(ret+=pat)%=mo;
	}
	for(x=X1+1;x<=X2;x++) {
		pat=(pat*2+mo-comb(x+Y2-1,x-1))%mo;
		(ret+=pat)%=mo;
	}
	pat=0;
	FOR(i,Y1) pat+=comb(X1+Y1,i);
	ret-=pat;
	for(x=X1+2;x<=X2+1;x++) {
		pat=(pat*2+mo-comb(x+Y1-2,x-1))%mo;
		ret-=pat;
	}
	for(y=Y1;y<Y2;y++) {
		pat=(pat*2+comb(X2+1+y-1,X2))%mo;
		ret-=pat;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int n,list[6];
double h;

int main(){
	for(scanf("%d",&n);n>0;n--){
		scanf("%lf",&h);
		if(h<165.0)list[0]++;
		else if(h<170.0)list[1]++;
		else if(h<175.0)list[2]++;
		else if(h<180.0)list[3]++;
		else if(h<185.0)list[4]++;
		else list[5]++;
	}
	for(n=0;n<6;n++){
		printf("%d:",n+1);
		for(;list[n]>0;list[n]--)printf("*");
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,i;scanf("%lld",&n);
  ll a[n],b[n],c;
  for(i=0;i<n;i++) scanf("%lld%lld",&a[i],&b[i]);
  sort(a,a+n);sort(b,b+n);
  if(n%2) c = b[n/2]-a[n/2];
  else c = b[n/2]+b[n/2-1]-a[n/2]-a[n/2-1];
  printf("%lld\n",c+1);
}

Measured memory_bytes: 6968
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int a, b, c;
    cin >> a >> b >> c;
    int w = a;
    bool db = false;
    while (w < 10000000)
    {
        if (w % b == c)
            db = true;
        w += a;
    }
    if (db)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    char c1[3], c2[3];
    cin>>c1;
    cin>>c2;

    if((c1[2] == c2[0]) && (c1[1] == c2[1]) && (c1[0] == c2[2]))
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}


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

int main(){
  int N,K;
  cin >> N >> K;
  bool finished=false;
  if(N%2==1){
    if(K<=(N+1)/2) finished=true;
  }
  else {
    if(K<=N/2) finished=true;
  }
  if(finished) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String[] input = sc.next().split("");
		long res = 0;
		long numB = 0;
		for (String element : input) {
			if (element.equals("W")) {
				res += numB;
			} else {
				numB++;
			}
		}
		System.out.println(res);

	}
}


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

typedef struct _circle {
        double x;
        double y;
} circle_t;

circle_t crossp[10000];
int crs = 0;

// 21_$N8rE@$r5a$a$k
void crosspoint( circle_t c1, circle_t c2 )
{
        double dist, dist2, distx, disty, centx, centy, height;
        double m1, m2, theta, convx, convy, tmpx, tmpy;

        // 21_$NCf?44V$Ndx, dy$r5a$a$k
        distx = ( c1.x - c2.x );
        disty = ( c1.y - c2.y );
        if ( distx * distx + disty * disty > 4.0000001 ) { return; }
        // c1, c2$N@.$9D>@~$N3QEY$r5a$a$k
        theta = atan( disty / distx );
        // 2E@4V$N5wN%
        dist = sqrt( distx*distx + disty*disty );

        // 2E@4V$NCfE@$r5a$a$k
        centx = ( c1.x + c2.x ) / 2;
        centy = ( c1.y + c2.y ) / 2;
        // 1_$NCf?4, >e5-CfE@$NCM, 1_$N8rE@$H$r7k$V;03Q7A$N$&$A,
        // >e5-CfE@$H8rE@$r7k$VD>@~$ND9$5$r5a$a$k
        height = sqrt( 1 - dist*dist/4 );

        crossp[crs].x = centx - height * sin( theta );
        crossp[crs].y = centy + height * cos( theta );
        crs++;
        crossp[crs].x = centx + height * sin( theta );
        crossp[crs].y = centy - height * cos( theta );
        crs++;
}

int main()
{
        int n, i, j, top = 0, tmpans = 0;
        circle_t c[100];
        char str[20], *p;
        double dist, distx, disty;

        while ( scanf( "%d", &n ) != 0 ) {
                // n$,0$N>l9gbreak
                if ( n == 0 ) { break; }
                for ( i = 0 ; i < n ; i++ ) {
                        // str$rF~NO$5$l$?8e, strtok$K$h$j,6h@Z$j$K$9$k
                        // scanf( "%lf,%lf", &c[i].x, &c[i].y );$N$[$&$,4JC1
                        scanf( "%lf,%lf", &c[i].x, &c[i].y );
                }

                crs = 0;
                // 3F1_$N8rE@$r5a$a$k
                for ( i = 0 ; i < n ; i++ ) {
                        for ( j = i+1 ; j < n ; j++ ) {
                                crosspoint( c[i], c[j] );
                        }
                }

                top = 1;
                for ( i = 0 ; i < crs ; i++ ) {
                        tmpans = 0;
                        for ( j = 0 ; j < n ; j++ ) {
                                distx = crossp[i].x - c[j].x;
                                disty = crossp[i].y - c[j].y;
                                dist = distx*distx + disty*disty;
                                // 3F1_$N8rE@$H, G$0U$N1_$NCf?4$N5wN%$,1$h$j>.$5$$>l9g, $=$l$i$O=E$J$C$F$$$k
                                if ( dist <= 1.0000001 ) {
                                        tmpans++;
                                }

                                if ( top < tmpans ) {
                                        top = tmpans;
                                }
                        }
                }
                printf( "%d\n", top );
        }

        return 0;
}



Measured memory_bytes: 2248
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str=br.readLine();
		String[] strAry=str.split(" ");
		int a=Integer.parseInt(strAry[0]);
		int b=Integer.parseInt(strAry[1]);
		String ans;
		if(a>b)ans="a > b";
		else if(a < b)ans="a < b";
		else ans="a == b";
		System.out.println(ans);
	}
}

Measured memory_bytes: 24340
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 110;
int n, a[N], ans = 0;
int f[N / 2][N][N];

int main() {
	scanf("%d", &n);
	for(int i = 1; i < n + n; i++) scanf("%d", &a[i]);
	sort(a + 1, a + n + n);
	f[n][1][0] = 1;
	for(int i = n - 1; i; i--) {
		int l = (a[i] != a[i + 1]), r = (a[n + n - i] != a[n + n - i - 1]);
		for(int j = 0; j <= n + n - 1; j++)
			for(int k = 0; k <= n + n - 1; k++) if(f[i + 1][j][k]) {
				for(int h = 1; h <= l + j; ++h)
					f[i][j + l - h + 1][k + r + (h > 1)] = (f[i][j + l - h + 1][k + r + (h > 1)] + f[i + 1][j][k]) % mod;
				for(int h = 1; h <= r + k; ++h)
					f[i][j + l + 1][k + r - h] = (f[i][j + l + 1][k + r - h] + f[i + 1][j][k]) % mod;
			}
	}
	for(int i = 0; i <= n + n - 1; i++)
		for(int j = 0; j <= n + n - 1; j++) ans = (ans + f[1][i][j]) % mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1536
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;

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

  if (h == 1 || w == 1) {
        cout << 1;
  } else {
    cout << ((h * w) + 1) / 2;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int n, m, c;
  scanf("%d%d%d", &n, &m, &c);
  int b[30];
  for (int i = 0; i < m; i++) {
    scanf("%d", b + i);
  }
  int sum;
  int tmp;
  int count = 0;
  for (int i = 0; i < n; i++) {
    sum = 0;
    for (int j = 0; j < m; j++) {
      scanf("%d", &tmp);
      sum += tmp * b[j];
    }
    sum += c;
    count += sum > 0;
  }
  printf("%d", count);
}


Measured memory_bytes: 128
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main() {

    ll N, K;
    cin >> N >> K;

    ll mn = N / K;
    ll mx = N / K;
    if(N % K > 0){
        mx += N % K;
    }

    cout << mx - mn << endl;

}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


using i64 = ::std::int_fast64_t;
using u64 = ::std::uint_fast64_t;
using i32 = ::std::int_fast32_t;
using u32 = ::std::uint_fast32_t;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// main.cpp

int main() {
  i64 N;
  std::cin >> N;
  std::vector<i64> A;
  tools::read(A, N);

  std::unordered_map<i64, i64> tally;
  for (const i64& A_i : A) {
    ++tally[A_i];
  }
  i64 sum = std::accumulate(A.begin(), A.end(), static_cast<i64>(0));

  i64 Q;
  std::cin >> Q;
  for (i64 i = 0; i < Q; ++i) {
    i64 B_i, C_i;
    std::cin >> B_i >> C_i;

    sum += tally[B_i] * (C_i - B_i);
    std::cout << sum << std::endl;
    tally[C_i] += tally[B_i];
    tally.erase(B_i);
  }

  return 0;
}

Measured memory_bytes: 7300
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int diff_xa = (x -a > 0) ? x - a : -1 * (x -a);
        int diff_xb = (x -b > 0) ? x - b : -1 * (x -b);
        
        System.out.println((diff_xa < diff_xb) ? "A" : "B");
    }
}


Measured memory_bytes: 21716
#include<stdio.h>
#define N 500

int main(){
  int i, j, k, l, n, A[N][N], c;
  scanf("%d", &n);
  for(i = 0 ; i < n ; i++){
    scanf("%d%d",&k,&l);
    for(j = 0 ; j < l ; j++){
      scanf("%d",&c);
      A[k-1][c-1]=1;
    }
  }
  for(i = 0 ; i < n ; i++){
    for(j = 0 ; j < n ; j++){
      if(A[i][j] != 1) A[i][j] = 0;
      printf("%d", A[i][j]);
      if(j != n-1) printf(" ");
    }
    printf("\n");
  }
}



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

int main()
{
    int a,b;
    cin >> a >> b;
    if(a < 10 && b < 10){
        cout << a * b << endl;
    }
    else{
        cout << -1 << endl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, n, r = 0, a, b, now, t;
  scanf("%lld", &n);
  vector<ll> vec[n];
  ll p[n], m[n][2];
  for(i = 0; i < n; ++i) m[i][0] = m[i][1] = 0;
  for(i = 1; i < n; ++i) {
    scanf("%lld%lld", &a, &b);
    vec[--a].push_back(--b);
    vec[b].push_back(a);
  }
  queue<ll> q;
  stack<ll> s;
  q.push(0);
  p[0] = 0;
  while(q.size()) {
    now = q.front(), q.pop();
    s.push(now);
    for(i = 0; i < vec[now].size(); ++i) if(p[now] != vec[now][i]) {
      p[vec[now][i]] = now;
      q.push(vec[now][i]);
    }
  }
  while(s.size()) {
    now = s.top(), s.pop();
    for(i = 0; i < vec[now].size(); ++i) if(p[now] != vec[now][i]) {
      t = vec[now][i];
      if(m[now][0] < m[t][0] + 1) m[now][1] = m[now][0], m[now][0] = m[t][0] + 1;
      else if(m[now][1] < m[t][0] + 1) m[now][1] = m[t][0] + 1;
    }
    if(m[now][0] + m[now][1] + 1 > r) r = m[now][0] + m[now][1] + 1;
  }
  printf("%s", r % 3 == 2 ? "Second" : "First");
  return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;

  int ans = a - (b * 2);

  if(ans < 0){
      cout << 0 << endl;
  }else{
      cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
point = []
y_list = []

for _ in range(N):
    x,y = map(int, input().split())
    point.append((x,y))
    y_list.append(y)
point = sorted(point,key=lambda tup: tup[0])
y_list.sort()
min_area = (y_list[N-1] - y_list[0]) * (point[N-1][0] - point[0][0])

for by in range(N):
    for ty in range(by+1,N):
        size=0
        idx = [0 for _ in range(N)]
        for i in range(N):
            if (y_list[by] <= point[i][1] and y_list[ty] >= point[i][1]):
                idx[size] = i
                size +=1
        lb = 0
        while(lb + K -1 < size):
            min_area = min(min_area, (y_list[ty] - y_list[by]) * (point[idx[lb + K - 1]][0] - point[idx[lb]][0]))
            lb+=1
print(min_area)

Measured memory_bytes: 3064
//扫雷
import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        BigInteger a=sc.nextBigInteger();
        BigInteger n=new BigInteger("9");
        if((a.mod(n)).compareTo(BigInteger.ZERO)==0)
            System.out.println("Yes");
        else System.out.println("No");
    }
}



Measured memory_bytes: 42476
#include<stdio.h>
int main(){
	int i;
	int n;
	int h;
	int a,s=0;
	scanf("%d %d",&h,&n);
	for(i=0;i<n;i++){
	scanf("%d",&a);
	s+=a;}
	if(s>=h)
	printf("Yes");
	else
	printf("No");
	
}

Measured memory_bytes: 128
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;
//const long long int MOD = 998244353;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	cin >> N;
	int ga, gb, sa, sb, ba, bb;
	cin >> ga >> sa >> ba;
	cin >> gb >> sb >> bb;
	vector<long long int>dp(N + 5050);
	dp[0] = 0;
	for (int i = 0; i < N; i++) {
		dp[i + ga] = max(dp[i + ga], dp[i] + gb);
		dp[i + sa] = max(dp[i + sa], dp[i] + sb);
		dp[i + ba] = max(dp[i + ba], dp[i] + bb);
	}
	for (int i = 0; i <= N; i++) {
		M = max(M, N + dp[i] - i);
	}
	long long int ans = 0;
	if (M == N) {
		for (auto &i : dp)i = 0;
		for (int i = 0; i < N; i++) {
			dp[i + gb] = max(dp[i + gb], dp[i] + ga);
			dp[i + sb] = max(dp[i + sb], dp[i] + sa);
			dp[i + bb] = max(dp[i + bb], dp[i] + ba);
		}
		for (int i = 0; i <= M; i++) {
			ans = max(ans, M + dp[i] - i);
		}
	}
	else {
		vector<int>a;
		vector<int>b;
		if (gb < ga) {
			a.push_back(ga);
			b.push_back(gb);
		}
		if (sb < sa) {
			a.push_back(sa);
			b.push_back(sb);
		}
		if (bb < ba) {
			a.push_back(ba);
			b.push_back(bb);
		}
		if (a.empty()) {
			ans = M;
		}
		else if (a.size() == 1) {
			ans = M / b.front()*a.front() + (M%b.front());
		}
		else {
			for (int i = 0; i <= M; i++) {
				if (i*b.front() > M)break;
				long long int box;
				box = (M - i * b.front()) / b.back()*a.back() + ((M - i * b.front()) % b.back());
				box += (long long int)a.front()*i;
				ans = max(ans, box);
			}
		}
	}
	cout << ans << endl;
}

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

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int inf = 1e9 + 7;
const int mod = 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

inline int mul(int a, int b) {
  return (a * (ll) b) % mod;
}

inline int pw(int x, int n) {
  int res = 1;
  while (n > 0) {
    if (n % 2) {
      res = mul(res, x);
      n--; 
    } else {
      x = mul(x, x);
      n /= 2;
    }
  }
  return res;
}

const int N = 1e4 + 7;
const int K = 107;

int dp[N][K][2];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  int d;
  cin >> d;
  vector <int> pw = {1};
  for (int i = 0; i < N; i++) {
    pw.push_back(pw.back() * 10);
    pw.back() %= d;
  }
  int n = (int) s.size();
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int f = 0; f < 2; f++) {
      int lmt = (f ? 9 : (s[i] - '0'));
      for (int dg = 0; dg <= lmt; dg++) {
        for (int x = 0; x < d; x++) {
          int nf = (dg < s[i] - '0' || f ? 1 : 0); 
          add(dp[i + 1][(x + dg) % d][nf], dp[i][x][f]);
        }
      }
    }
  }
  int ans = dp[n][0][0];
  add(ans, dp[n][0][1]);
  add(ans, -1);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 8704
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int> > v;
ll INF = 1e17;
ll n , m;
ll dp[100000 + 10];
ll dfs(ll  i){
    if(v[i].size() == 0)return 0 ;
    if(dp[i] != -1)return dp[i] ;
    ll ans = -INF;
    for(int j=0;j<v[i].size();j++){
        ans = max(ans , 1+dfs(v[i][j]));
    }
    return dp[i] = ans;
}
int main(){
  //  cout<<(sizeof dp)<<endl;
    cin>>n>>m;
    memset(dp,-1,sizeof dp);
    v.resize(n+2);
    for(int i=0;i<m;i++){
        int  l , r;
        cin>>l>>r;
        l--;r--;
        v[l].push_back(r);
    }
    ll ans1 = -INF;
    for(int i=0;i<n;i++){
        ans1 = max(ans1,dfs(i));
    }
    cout<<ans1<<endl;
    return 0;
}


Measured memory_bytes: 8576
object Main {
  def main(args: Array[String]): Unit = {
    Iterator.continually(io.StdIn.readLine().toInt)
      .takeWhile(_ != 0)
      .foreach { n =>
        val sn = io.StdIn.readLine().split(" ").map(_.toInt)
        val m = sn.sum / n.toDouble
        val a2 = sn.map { s =>
          val v = s - m
          v * v
        }.sum / n
        println(f"${Math.sqrt(a2)}%.8f")
      }
  }
}

Measured memory_bytes: 45120
#include <iostream>

using namespace std;

int main()
{
  int S;
  cin >> S;
  int first = S/100;
  int second = S%100;
 
  if(first > 0 && first <= 12){
    if(second > 0 && second <= 12){
      cout << "AMBIGUOUS" << "\n";
    }
    else cout << "MMYY" << "\n";
  }
  else if(second > 0 && second <= 12){
    cout << "YYMM" << "\n";
  }
  else cout << "NA" << "\n";

  return 0;
}


Measured memory_bytes: 256
//ll n_kai[pow(10.0, 5.0)]; なんでだめなの？


#include<iostream>
#include<queue>
#include<vector>

using namespace std;
using ll = long long;

const int INF = 1001001001;
const int MOD = 1000000007;



int main(){
	ll k;cin >> k;
	queue<ll> q;
	for (int i = 0;i < 9; ++i) q.push(i+1);

	ll cnt = 0;
	while(1){
		++cnt;
		ll node = q.front();q.pop();
		if(cnt == k){
			cout << node << endl;
			return 0;
		}

		ll last = node % 10;

		if (last != 0){
			q.push(node * 10 + last - 1);
		}
		q.push(node * 10 + last);
		if ( last != 9){
			q.push(node * 10 + last + 1);
		}
	}

	return 0;
}


Measured memory_bytes: 1792
counter = 0

N = int(input())
counter += (N-2)*2+1
limit = 0
for i in range(1000):
    if (i+1)**2 >=1000000:
        limit = i

if N >= 100:
    if N%2 == 0:
        counter += (N//2-3)*2+1
    else:
        counter += (N//2-2)*2+1

    for i in range(limit):
        for j in range(N//3):
            if (i+3) * (i+3+j) < N:
                if j == 0:
                    counter += 1
                else:
                    counter += 2
            else:
                break
else:
    for i in range(limit):
        for j in range(N // 2):
            if (i + 2) * (i + 2 + j) < N:
                if j == 0:
                    counter += 1
                else:
                    counter += 2
            else:
                break
print(counter)

Measured memory_bytes: 9220
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define debug int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<int, Pi> V;
typedef vector<int> VE;
const ll mod = 1000000007; //10^9+7


int main(){
    ll n, m, d;
    cin >> n >> m >> d;
    double ans = 1.0;
    if(d != 0){
        ans *= 2.0 * (n - d) * (m - 1) / pow(n, 2);
    }else{
        ans *= n * (m - 1) / pow(n, 2);
    }
    printf("%10.10lf\n", ans);
}

Measured memory_bytes: 256
/*
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
*/
#include <bits/stdc++.h>
using namespace std;
void print() { cout << '\n'; } template<class T, class ...U> void print(T x, U ...y) { cout << x << ' '; print(y...); }
typedef long long ll; const int N = 2e5 + 5, M = 1e9 + 7; typedef vector<int> vi; typedef vector<vi> vii; void Main();
int main(int argc, char **argv) {
  ios::sync_with_stdio(0), cin.tie(0); cout << setprecision(10) << fixed;
  #ifdef Zmm
  freopen((string(*(argv)).substr(2, string(*(argv)).size() - 6) + string(".cpp")).c_str(), "r", stdin); string x; cin >> x;
  #endif
  Main();
}
struct node {
  int b, c;
  bool operator<(const node& n) { return c > n.c; }
} b[N];
void Main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> b[i + m].c, b[i + m].b = 1;
  for (int i = 0; i < m; i++) cin >> b[i].b >> b[i].c;
  sort(b, b + m + n);
  ll sum = 0;
  for (int i = 0, j = 0, k; i < n + m && j < n; i++) {
    k = 0;
    while (k < b[i].b && j < n) sum += b[i].c, k++, j++;
  }
  cout << sum << '\n';
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
 
int main() {
    for (;;) {
        int n, x;
        cin >> n >> x;
 
        if (n == 0 && x == 0) break;
 
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                for (int k = j + 1; k <= n; ++k) {
                    if (i + j + k == x) ++ans;
                }
            }
        }
 
        cout << ans << endl;
    }
 
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------------------------------- "<<endl
#define uint unsigned int 
#define ULL unsigned long long
#define LDB long double
#define DB double
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
inline LL read(){
	LL nm=0; bool fh=true; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return fh?nm:-nm;
}

#define mod 1004535809
namespace  CALC{
	inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
	inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
	inline int mul(int x,int y){return (LL)x*(LL)y%mod;}
	inline void upd(int &x,int y){x+=y;(x>=mod)?(x-=mod):0;}
	inline void dec(int &x,int y){x-=y;(x<0)?(x+=mod):0;}
	inline int qpow(int x,int sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
}using namespace CALC;

#define M 1020
int n,m,sum;
int len[M],LEN,w[M];
char ch[M][M],t[M];
int main(){
	n=read();
	for(int i=1;i<=n;i++) scanf("%s",ch[i]),w[i]=read(),len[i]=strlen(ch[i]);
	scanf("%s",t),LEN=strlen(t);
	for(int i=1;i<=n;i++){
		bool mc=(len[i]==LEN);
		for(int j=0;j<len[i]&&mc;j++) mc&=(ch[i][j]==t[j]);
		if(!mc) continue;
		for(int j=i+1;j<=n;++j) sum+=w[j];
		break;
	}
	printf("%d\n",sum);

	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>

using namespace std;

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)
const int inf = 1e+9;


int main() {
	int n, k;
	cin >> n >> k;
	vector<int> h(n);

	rep(i, n) {
		cin >> h[i];
	}

	sort(h.begin(), h.end());

	int diff = inf;

	for(int i = 0; i < n - k + 1; i++) {
		int cur_diff = h[i + k - 1] - h[i];
		if (cur_diff < diff) {
			diff = cur_diff;
		}
	}
	cout << diff << endl;
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	static int first = -1;
	static int second = -1;
	static int third = -1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long result = 1;
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			long mul = countNum(a);
			addNum(a);
			result = result * mul % 1000000007;
		}
		System.out.println(result);
	}

	public static int countNum(int num) {
		int count = 0;
		if (first == num - 1) {
			count++;
		}
		if (second == num - 1) {
			count++;
		}
		if (third == num - 1) {
			count++;
		}
		return count;
	}

	public static void addNum(int num) {
		if (first == num - 1) {
			first++;
			return;
		}
		if (second == num - 1) {
			second++;
			return;
		}
		if (third == num - 1) {
			third++;
		}
	}
}

Measured memory_bytes: 49328
N = int(input())
H = list(map(int, input().split()))
if N == 1:
  print(0)
  exit()
elif H[0] >= H[1]:
  flg = True
  cnt = 1
  max_c = 1
else:
  flg = False
  cnt = 0
  max_c = 0
  
for n in range(1, N - 1):
  if H[n] >= H[n + 1]:
    ch = True
  else:
    ch = False
    
  if ch == flg:
    flg = ch
    if ch:
      cnt += 1
      max_c = max(max_c, cnt)
    else:
      pass
  else:
    flg = ch
    if ch:
      cnt = 1
    else:
      cnt = 0
      pass
print(max_c)

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

public class Main{
	static int max = 60000;
	static boolean[] isPrime = new boolean[max];
	public static void main(String[] args) {
		aryPrime();
		List<Integer> list = new ArrayList<Integer>();
		for(int i = 2; i < max; i++) {
			if(isPrime[i]) {
				list.add(i);
			}
		}
		Integer[] p = list.toArray(new Integer[list.size()]);
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			int low = bs_lower(p, n);
			int up = bs_upper(p, n);
			System.out.printf("%d %d\n", p[low], p[up]);
		}
		sc.close();
	}
	static int bs_upper(Integer[] p, int k) {
		int l = -1;
		int r = p.length;
		int mid = 0;
		while(r - l > 1) {
			mid = l + (r - l) / 2;
			if(p[mid] > k) {
				r = mid;
			}else {
				l = mid;
			}
		}
		return r;
	}
	static int bs_lower(Integer[] p, int k) {
		int l = -1;
		int r = p.length;
		int mid = 0;
		while(r - l > 1) {
			mid = l + (r - l) / 2;
			if(p[mid] < k) {
				l = mid;
			}else {
				r = mid;
			}
		}
		return l;
	}
	static void aryPrime(){
        int l = isPrime.length;
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2; i <= (int)Math.sqrt(l); i++) {
            if(isPrime[i]) {
                for(int j = i * 2; j < l; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}


Measured memory_bytes: 26700
#include <iostream>
#include <vector>
#include <numeric>//accumulate(v.begin(), v.end(), 0);
#include <algorithm>//sort(v.begin(),v.end());
#include <string>//
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
        int n;
        cin >> n;
        int as[100005];
        rep(i,100005){
                as[i]=0;
        }
        int a;
        rep(i,n){
                cin  >> a;
                as[a]++;
        }
        int ans=0;
        rep(i,100002){
                ans=max(ans,as[i]+as[i+1]+as[i+2]);
        }
        cout << ans << endl;



        return 0;
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
N, A, B = map(int, input().split())
if A > B: A, B = B, A
x = max(abs(1 - A), abs(1 - B))
y = max(abs(N - A), abs(N - B))
z = abs(A - (A + B) // 2)
res = 0
if (A + B) % 2:
  if abs(1 - A) < abs(N - B):
    res += abs(1 - A) + 1
    B -= abs(1 - A)
    A = 1
  else:
    res += abs(N - B) + 1
    A += abs(N - B)
    B = N

  x = max(abs(1 - A), abs(1 - B))
  y = max(abs(N - A), abs(N - B))
  z = abs(A - (A + B) // 2)
print(min(x, y, z) + res)

Measured memory_bytes: 38748
#include<bits/stdc++.h>
using namespace std;
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
#define  pi  pair<int,int>
#define  pb  push_back
#define  F   first
#define  S   second
#define  P   2*acos(0.0)
const int N=2e5+3;
//string s,p;
//vector<int>v;
//map<int,int>mp;
//set<ll>st;
int main()
{
    ft
    double t,i,j,n,m,l,r;
    cin>>l;
    cout<<fixed<<setprecision(20)<<(2.0*P*l)<<"\n";
    return 0;
}

Measured memory_bytes: 3804
#include <iostream>
using ll = long long;

ll f(int N, int K, int k)
{
  if (N < k) return 0;
  ll nk = (N - k) / K;
  if (k > 0) ++nk;
  return nk * nk * nk;
}

int main()
{
  int N, K;
  std::cin >> N >> K;
  
  ll ans = f(N, K, K);
  if (K % 2 == 0)
    ans += f(N, K, K/2);
  
  std::cout << ans << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    int n,m;
    cin >> n >> m;
    cout << n-m+1 << endl;

    return 0;
}

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

string convertToBase(int value, int base) {
	string output = "";
	do {
		char digit = value % base;
		if (digit < 10) digit += '0';
		else digit = digit + 'A' - 10;
		output += digit;
		value /= base;
	} while (value > 0);
	reverse(output.begin(), output.end());
	return output;
}


main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	string s = convertToBase(n, k);
	cout << s.size() << '\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  map<int,int64_t> ba;
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    ba[b]+=a;
  }
  int64_t s=0;
  bool f=1;
  for(auto x:ba){
    s+=x.second;
    if(s>x.first)
      f=0;
  }
  cout<<(f?"Yes":"No");
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
int ans,n,a[105],b[105];
int main(){
	cin>>n; 
	for(int i=0;i<n-1;i++)
		cin>>b[i];
	a[0]=b[0];
	for(int i=0;i<n-1;i++)
		a[i+1]=min(b[i],b[i+1]);
	a[n-1]=b[n-2];
	for(int i=0;i<n;i++)
	    ans+=a[i];
	cout<<ans;
	return 0;         
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define ull unsigned long long
using namespace std;

const int nmax = 100100;
int N;
ull A,B;
void solve(ull A, ull B);
void read(){
    cin >> N;
    for(int i=0;i < N; ++i){
        cin >> A >> B;
        solve(A, B);
    }
}
ull bs(ull n)
{
    ull L = 1, R =(unsigned long long)2000000000, mid;
    while( (R-L) > 1)
    {
        mid = (R+L) >> 1;
        if(((mid+1)*(mid+1))/4 > n)
            R = mid;
        else
            L = mid;
    }
    return L;
}
void solve(ull A, ull B){
    if(A > B) swap(A,B);
    if(B == 1)
    {
        cout << 0 << endl;
        return;
    }
    ull x = A * B - 1;
    cout << bs(x) - (A==B ? 0:1) << endl;
}

int main(){
    read();
}

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl

class unionfind {
	vector<int> par, rank;

public:
	void init(int n) {
		par.resize(n);
		rank.resize(n);

		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return ;

		if (rank[x] < rank[y]) par[x] = y;
		else {
			par[y] = x;
			if (rank[x] == rank[y]) ++rank[x];
		}
	}

	bool same(int x, int y) { return (find(x) == find(y)); }
} uf;

const int MN = 200010;

using P = pair<ll, int>;

vector<pii> g[MN];
int col[MN];
ll X[MN];
vector<P> dp[MN];

void mergevec(vector<P>& a, vector<P> b) {
	vector<P> res(a.size() + b.size());
	merge(ALL(a), ALL(b), res.begin());
	a.clear();

	if (res.size()) {
		a.pb(res[0]);

		int c = res[0].se;
		for (int i = 1; i < res.size(); ++i) {
			if (res[i].se != c) {
				a.pb(res[i]);
				break;
			}
		}
	}
}

void dfs_up(int v, int p) {
	dp[v].eb(X[v], col[v]);

	for (pii e : g[v]) {
		if (e.fi != p) {
			dfs_up(e.fi, v);

			vector<P> nx;

			for (auto t : dp[e.fi]) {
				nx.eb(t.fi + e.se, t.se);
			}

			mergevec(dp[v], nx);
		}
	}
}

void dfs_down(int v, int p, int pw) {
	if (p != -1) {
		vector<P> nx;
		for (auto t : dp[p]) {
			nx.eb(t.fi + pw, t.se);
		}
		mergevec(dp[v], nx);
	}

	for (pii e : g[v]) {
		if (e.fi != p) {
			dfs_down(e.fi, v, e.se);
		}
	}
}

int main() {
	int N; cin >> N;

	rep(i, N) cin >> X[i];

	rep(i, N-1) {
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		g[a].eb(b, c);
		g[b].eb(a, c);
	}

	uf.init(N);
	rep(i, N) {
		col[i] = i;
	}

	ll ans = 0;

	while (true) {
		bool one = true;
		for (int i = 1; i < N; ++i) {
			if (col[i] != col[0]) {
				one = false;
			}
		}
		if (one) {
			break;
		}

		rep(i, N) {
			dp[i].clear();
		}

		vector<P> mt(N, mp(LLONG_MAX, -1));

		dfs_up(0, -1);
		dfs_down(0, -1, -1);

		rep(i, N) {
			for (auto p : dp[i]) {
				if (p.se != col[i]) {
					mt[col[i]] = min(mt[col[i]], mp(p.fi + X[i], p.se));
					break;
				}
			}
		}

		rep(i, N) if (mt[i] != mp(LLONG_MAX, -1)) {
			int u = i, v = mt[i].se;
			ll cost = mt[i].fi;
			if (!uf.same(u, v)) {
				uf.unite(u, v);
				ans += cost;
			}
		}

		rep(i, N) {
			col[i] = uf.find(col[i]);
		}
	}

	cout << ans << endl;

	return 0;
}

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

int n,k;
string s,t;

int main() {
  cin >> n;
  int a,y=0,e=0;
  rep(i,n){
     cin >> a;
     if(a%4==0) y++;
     else if(a%2==0) e++;
  }
  cout << (y+e/2>=n/2 ? "Yes" : "No") << endl;
}

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

using namespace std;

const int INF = 1e9 + 3;
const int N = 2e5 + 3;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;

const double PI = acos(-1);

vector<int> gr[N];
char used[N];
vector<int> comp;

void dfs(int cur) {
    used[cur] = 1;
    for (int v : gr[cur]) {
        if (!used[v])
            dfs(v);
    }
    comp.push_back(cur);
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    int ans = 0;
    for (int v = 1; v <= n; v++) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            ans = max(ans, int(comp.size()));
        }
    }
    cout << ans;
}

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

Measured memory_bytes: 24688
// Problem : D - Friend Suggestions
// Contest : AtCoder Beginner Contest 157
// URL : https://atcoder.jp/contests/abc157/tasks/abc157_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
using namespace std;
struct dsu
{
 int fa[100005],siz[100005];
 void init(int n)
 {
  for(int i=1;i<=n;i++)
   fa[i]=i,siz[i]=1;
 }
 int getsiz(int x)
 {
  x=find(x);
  return siz[x];
 }
 int find(int x)
 {
  return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
 }
 void merge(int x,int y)
 {
  x=find(x),y=find(y);
  if(x==y)return;
  fa[y]=x,siz[x]+=siz[y];
  siz[y]=0;
 }
}d;
int res[100005];
int main()
{
 int n,m,k;
 cin>>n>>m>>k;
 d.init(n);
 for(int i=1;i<=m;i++)
 {
  int x,y;
  cin>>x>>y;
  d.merge(x,y);
  res[x]--,res[y]--;
 }
 for(int i=1;i<=n;i++)
  res[i]+=d.getsiz(i)-1;
 for(int i=1;i<=k;i++)
 {
  int x,y;
  cin>>x>>y;
  if(d.find(x)==d.find(y))
   res[x]--,res[y]--;
 }
 for(int i=1;i<=n;i++)
  cout<<res[i]<<' ';
 return 0;
}

Measured memory_bytes: 2432
///Bismillahir Rahmanir Rahim
///ALLAH HU AKBAR
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int A,B;
    int count=1;
    cin>>A>>B;
    int y=A-1;
    int x=A;
    while(x<B)
    {
        x--;
        x=x+A;
        count++;
    }
    if(B<=1)
        count=0;

    cout<<count<<endl;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

namespace atcorder1
{
    class MainClass
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {
            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }
        public static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            var n = Read();
            var r = Console.ReadLine();
            bool b = false;
            
            if (r.Length % 2 == 0)
            {
                for(int i = 0; i < r.Length/2; i++)
                {
                    if (r[i] != r[i + r.Length/2])
                    {
                        b = true;
                    }
                }
            }
            else
            {
                b = true;
            }
            if (!b)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 13140
package main
import (
       "fmt"
       "os"
       "bufio"
       "strconv"
)

func main() {
     sc := bufio.NewScanner(os.Stdin)

     var n int
     for i := 1; sc.Scan(); i++ {
     	 n, _ = strconv.Atoi(sc.Text())
	 if n == 0 { break; }
	 fmt.Printf("Case %d: %d\n", i, n)
     }
}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

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

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

  ll N,X;
  cin>>N>>X;
  vector<ll> A(N);
  rep(i,N)cin>>A[i];
  sort(all(A));
  reverse(all(A));
  vector<vector<ll>> dp(N+1,vector<ll>(X+1,0));
  dp[0][X]=1;
  vector<ll> inv(N+1,0);
  rep(i,N+1)inv[i]=mod_pow(i,mod-2);
  rep(i,N)rep(j,X+1){
    (dp[i+1][j%A[i]]+=dp[i][j]*inv[N-i]%mod)%=mod;
    (dp[i+1][j]+=dp[i][j]*(1-inv[N-i]+mod)%mod)%=mod;
  }
  ll f=1;
  rep(i,N)f=f*(i+1)%mod;
  ll res=0;
  rep(j,X+1)(res+=dp[N][j]*j%mod)%=mod;
  cout<<res*f%mod<<endl;

  return 0;
}


Measured memory_bytes: 158592
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

typedef struct Node {
  int p, q;
  int r,b;
  Node() {}
  Node(int p, int q, int r, int b)
    : p(p), q(q), r(r), b(b) {}
} node;

node nd[101];

typedef long long Int;
Int gcd(Int a, Int b) {
  return (b != 0) ? gcd(b, a%b) : a;
}
Int lcm(Int a, Int b) {
  return a / gcd(a,b) * b;
}

Int solve(Int id, Int nest) {
  // cout << string(nest, ' ');
  // cout << id << endl;
  if (id == 0) return 1;
  Int r = solve(nd[id].r, nest+1);
  Int b = solve(nd[id].b, nest+1);

  Int p = nd[id].p;
  Int q = nd[id].q;

  Int l = lcm(r*p, b*q);
  return l/p + l/q;
}

int main() {
  int n;
  while(cin >> n, n) {
    vector<bool> hoge(n+1);
    REP(i,n) {
      int p, q, r, b;
      cin >> p >> q >> r >> b;
      nd[i+1] = Node(p,q,r,b);
      hoge[r] = 1;
      hoge[b] = 1;
    }
    int a;
    for (int i=1; i<=n; ++i)
      if (!hoge[i])
        a = i;
    cout << solve(a,0) << endl; 
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main(){
  int n,m;
  cin >> n >> m;
  vector<ll> x(n),y(n),z(n);
  rep(i,n){ cin>>x[i]>>y[i]>>z[i]; }
  
  int bit2 = 8;//0a 1b 2c group
  ll ans=-longinf;
  rep(i,bit2){
    int now=i;
    int px=(now%2); now/=2; if(px==0){px=-1;}
    int py=(now%2); now/=2; if(py==0){py=-1;}
    int pz=(now%2); if(pz==0){pz=-1;}
    vector<ll> tmp;
    ll cur=0;
    rep(j,n){ tmp.emplace_back(x[j]*px+y[j]*py+z[j]*pz); }
    sort(tmp.rbegin(),tmp.rend());
    rep(j,m){ cur += tmp[j]; }
    ans = max(ans,cur);
  }    
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256