akhauriyash/Code-Regression huggingface dataset:
import bisect
N = int(input())
H = list(map(int, input().split()))
H.sort()
negative_count = bisect.bisect_left(H, 0)
positive_count = N - negative_count

def f():
    # answer
    ans = ""

    if N == 2:
        return "{0} {1}\n".format(H[-1], H[0]), H[-1] - H[0]

    if positive_count == 0:
        ans += "{0} {1}\n".format(H[-1], H[0])
        sum_ans = H[-1] - H[0]
        for i in range(1, N - 1):
            v = H[i]
            ans += "{0} {1}\n".format(sum_ans, v)
            sum_ans = sum_ans - v
        return ans, sum_ans

    if negative_count == 0:
        ans += "{1} {0}\n".format(H[-1], H[0])
        sum_ans = - H[-1] + H[0]

        for i in range(1, N - 2):
            v = H[negative_count + i]
            ans += "{0} {1}\n".format(sum_ans, v)
            sum_ans = sum_ans - v

        v = H[-2]
        ans += "{1} {0}\n".format(sum_ans, v)
        sum_ans = v - sum_ans
        return ans, sum_ans


    if positive_count == 1:
        ans += "{0} {1}\n".format(H[-1], H[0])
        sum_ans = H[-1] - H[0]
    else:
        ans += "{1} {0}\n".format(H[-1], H[0])
        sum_ans = - H[-1] + H[0]

        for i in range(positive_count - 2):
            v = H[negative_count + i]
            ans += "{0} {1}\n".format(sum_ans, v)
            sum_ans = sum_ans - v

        v = H[-2]
        ans += "{1} {0}\n".format(sum_ans, v)
        sum_ans = v - sum_ans

    for i in range(1, negative_count):
        v = H[i]
        ans += "{0} {1}\n".format(sum_ans, v)
        sum_ans = sum_ans - v

    return ans, sum_ans


ans, sum_ans = f()
ans = "{}\n".format(sum_ans) + ans
print(ans)



Measured memory_bytes: 14060
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

struct pkt
{
    int x, y;
};

int main()
{
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector< vector<bool> > odw(n, vector<bool>(m, false));
    stack<pkt> S;
    bool ok = true;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (!odw[i][j] && a[i][j] == '#')
            {
                int il = 0;
                odw[i][j] = true;
                S.push({i, j});
                while (!S.empty())
                {
                    pkt akt = S.top();
                    S.pop();
                    ++il;
                    for (int k = 0; k < 4; ++k)
                    {
                        pkt nowy = {akt.x + dx[k], akt.y + dy[k]};
                        if (nowy.x >= 0 && nowy.x < n && nowy.y >= 0 && nowy.y < m)
                        {
                            if (!odw[nowy.x][nowy.y] && a[nowy.x][nowy.y] == '#')
                            {
                                odw[nowy.x][nowy.y] = true;
                                S.push(nowy);
                            }
                        }
                    }
                }
                if (il == 1)
                    ok = false;
            }
        }
    }
    if (ok)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}


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

using namespace std;

#define MAXN 105
#define MAXW 100005
long long memo[MAXN][MAXW];
vector<int> values, weights;
int N,W;

long long knap(int curr, int wRim) {
    if(memo[curr][wRim] != -1)
        return memo[curr][wRim];
    if(curr == N)
        return 0;
    long long tot = knap(curr+1, wRim);
    if(wRim - weights[curr] >= 0)
        tot = max(tot, values[curr] + knap(curr+1, wRim - weights[curr]));
    return memo[curr][wRim] = tot;
}
int main() {
    
	cin>>N>>W;
	int tempv, tempw;
	for(int i = 0; i < N; i++) {
		cin>>tempw>>tempv;
        values.push_back(tempv);
        weights.push_back(tempw);
	}
	memset(memo,-1,sizeof memo);
	cout<<knap(0,W);
}

Measured memory_bytes: 82304
#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
int main(){
	string a;
	char t='A';
	while(getline(cin,a)){
		if(a[0]==t)
			t=a[2];
		else if(a[2]==t)
			t=a[0];
	}
	cout<<t<<endl;
	return 0;
}

Measured memory_bytes: 1168
import java.util.*;

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

        String s1 = sc.next();
        String s2 = sc.next();
        String s3 = sc.next();

        String c1 =  s1.substring(0,1);
        String c2 =  s2.substring(1,2);
        String c3 =  s3.substring(2,3);


        System.out.println(c1+c2+c3);

    }
}

Measured memory_bytes: 21844
N,M,Q=map(int, input().split())
ABCD=[tuple(map(int, input().split()))for _ in range(Q)]
def rec(X):
    ans=0
    if len(X)==N:
        res=0
        for a,b,c,d in ABCD:
            if X[b-1]-X[a-1]==c:
                res+=d
        return res
    s = 1 if len(X)==0 else X[-1]
    for i in range(s,M+1):
        X.append(i)
        ans=max(ans,rec(X))
        X.pop()
    return ans
print(rec([]))


Measured memory_bytes: 9224
from collections import Counter
import math
import sys
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result


arr_data = getinputdata()

n = int(arr_data[0][0])

maxdata = 0

arr01 = list(map(int, arr_data[1]))
arr02 = list(map(int, arr_data[2]))
    
for i in range(0, n):
    
    if maxdata <= sum(arr01[:i+1]) + sum(arr02[i:]):
        
        maxdata = sum(arr01[:i+1]) + sum(arr02[i:])
    
    
print(maxdata)
    

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  vi cnt(3,0);
  char c;
  while(cin >> c){
    cnt[c-'a']++;
  }
  sort(rng(cnt));
  if(cnt[0]==cnt[2] or cnt[0] + 1 == cnt[2]){
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 256
n = gets.chomp.to_i - 1
@dice = gets.split(' ').map(&:to_i)

def throw(a, b)
    temp = @dice[0]
    @dice[0] = @dice[a]
    @dice[a] = @dice[5]
    @dice[5] = @dice[b]
    @dice[b] = temp
end

def check(dice)
    3.times do
        throw(4, 1)
        break if dice[1] == @dice[0]
        throw(2, 3)
        break if dice[1] == @dice[0]
    end
    return false if dice[1] != @dice[0]
    throw(4, 1)
    4.times do
        throw(2, 3)
        return true if dice == @dice
    end
    false
end

count = 0;

n.times do
    diceN = gets.split(' ').map(&:to_i)
    count += 1 if  !check(diceN)
end

puts count == n ? 'Yes' : 'No'

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

int main() {
  long double a, b, x;
  cin >> a >> b >> x;
  
  long double ans;
  if (a * a * b / 2.0 > x) {
    ans = atan(a * b * b / (2 * x));
  } else {
    ans = atan(2 * (a * a * b - x) / (a * a * a));
  }
  
  cout << fixed << setprecision(10) << ans * 180 / M_PI << endl;
  
  return 0;
}

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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<Int> s, t;
    for (Int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            s.push_back(a[i]);
        } else {
            t.push_back(a[i]);
        }
    }
    map<Int, Int> mp_s, mp_t;
    for (Int i = 0; i < (Int)s.size(); i++) {
        mp_s[s[i]]++;
    }
    for (Int i = 0; i < (Int)t.size(); i++) {
        mp_t[t[i]]++;
    }
    vector<pair<Int, Int>> cnt_s, cnt_t;
    for (auto i : mp_s) {
        cnt_s.emplace_back(i.se, i.fi);
    }
    for (auto i : mp_t) {
        cnt_t.emplace_back(i.se, i.fi);
    }
    sort(all(cnt_s), greater<pair<Int, Int>>());
    sort(all(cnt_t), greater<pair<Int, Int>>());    
    if (cnt_s.front().se != cnt_t.front().se) {
        dump(n / 2 - cnt_s.front().fi + n / 2 - cnt_t.front().fi);
    } else {
        if (cnt_s.size() == 1 and cnt_t.size() == 1) {
            dump(n / 2);
        } else if (cnt_s.size() == 1) {
            dump(n / 2 - cnt_t[1].fi);
        } else if (cnt_t.size() == 1) {
            dump(n / 2 - cnt_s[1].fi);
        } else {
            dump(min(n / 2 - cnt_s[1].fi + n / 2 - cnt_t.front().fi, n / 2 - cnt_t[1].fi + n / 2 - cnt_s.front().fi));
        }
    }
    return 0;
}


Measured memory_bytes: 10352
def main():
  N, M = map(int, input().split())
  inf =  10**9
  p = 1<<N
  dp = [inf]*p 
  dp[0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([1<<(c-1) for c in C])
    for j in range(p):
      #print(min(dp[i][j|c_bit], dp[i][j] + a))
      dp[j|c_bit] = min(dp[j|c_bit], dp[j] + a)
  if dp[p-1] == inf:
    print(-1)
  else: 
    print(int(dp[p-1]))
  
if __name__ == "__main__":
  main() 

Measured memory_bytes: 3188
/*
	************	************    ************	***      ***	************	***               ***
	************	************    ************	****     ***	************	 ***             ***
	***      ***	***      ***    ***      ***	*****    ***	***      ***	  ***           ***
	***      ***	***      ***    ***      ***	******   ***	***      ***	   ***         ***
	************	************    ************	*** ***  ***	************	    ***       ***
	************	************    ************	***  *** ***	************	     ***     ***
	***				***   ***       ***      ***	***   ******	***      ***	      ***   ***
	***				***    ***      ***      ***	***    *****	***      ***	       *** ***
	***				***     ***     ***      ***	***     ****	***      ***	        *****
	***				***      ***    ***      ***	***      ***	***      ***	         ***
*/

#define named(blockname) goto blockname; \
                         blockname##_skip: if (0) \
                         blockname:

#define break(blockname) goto blockname##_skip
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define readarr(a,n) for (int i=0; i<n; i++) {cin>>a[i];}
#define printarr(a,n) for (int i=0; i<n; i++) {cout<<a[i]<<' ';}
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define vint vector <int>
#define pb push_back
#define pf push_front
#define endl "\n"

ll maxSubArraySum(ll a[], ll size) 
{ 
	// ll max = 0 ;
	ll m = 0 ;
    ll max_so_far = INT_MIN, max_ending_here = 0; 
  
    for (ll i = 0; i < size; i++) 
    { 
    	m = max(a[i],m) ;
        max_ending_here = max_ending_here + a[i]  ; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) {
            max_ending_here = 0; 
            max_so_far -= m ;
            m = 0 ;
        }
    } 
    // cout << max_so_far ;
    return max_so_far; 
}

signed main() {
	
	fast ;
	
	ll q ;
	q = 1 ;
	// cin >> q ;
	while (q--)
	{
		// ll a,b,c,d,e ;
		// cin >> a>>b>>c>>d>>e ;
		// ll a[n] ;
		// readarr(a,n) ;
		// maxSubArraySum(a, n);
		string s ;
		cin >> s ;
		ll n = s.length() ;
		
		for (ll i = 0; i < n; i++)
		{
			if (s[i]=='?')
				s[i] = 'D' ;
		}
		cout << s ;
	}
	
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll,ll> pii;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rept(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define fi first
#define se second
#define mes(a,b) memset(a,b,sizeof a)
#define mp make_pair
#define dd(x) cout<<#x<<"="<<x<<" "
#define de(x) cout<<#x<<"="<<x<<"\n"
#define debug() cout<<"I love Miyamizu Mitsuha forever.\n"
const int inf=0x3f3f3f3f;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	cout<<360/__gcd(n,360)<<"\n";
	return 0;
}

Measured memory_bytes: 3644
#include<cstdio>
#include<map>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define MAXN 56
using namespace std;
int n;
long long ans;
char a[MAXN];
map<pair<unsigned long long,unsigned long long>,long long> ma;
int main()
{
	scanf("%d",&n);
	scanf("%s",a);
	int Max=1<<n;
	for(int s=0;s<Max;s++)
	{
		unsigned long long p=0,q=0;
		for(int i=0;i<n;i++)
		{
			if(s&(1<<i)) p=p*131+a[i];
			else q=q*131+a[i];
		}
		ma[make_pair(p,q)]++;
	}
	for(int s=0;s<Max;s++)
	{
		unsigned long long p=0,q=0;
		for(int i=n*2-1;i>=n;i--)
		{
			if(s&(1<<(i-n))) p=p*131+a[i];
			else q=q*131+a[i];
		}
		ans+=ma[make_pair(q,p)];
	}
	printf("%lld",ans);
}

Measured memory_bytes: 33024
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
ll modpow(ll a, ll n, ll mod = MOD) {
    ll res = 1;
    while(n > 0) {
        if(n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x); // 再帰的に解く
    y -= a / b * x;
    return d;
}

// 負の数にも対応した mod (a = -11 とかでも OK)
inline long long mod(long long a, long long m) { return (a % m + m) % m; }

// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
    long long x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}
int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = modpow(2, n) - 1;
    ll t1 = 1;
    for(ll i = 1; i <= a; i++) {
        t1 *= modinv(i, MOD);
        t1 %= MOD;
        t1 *= (n + 1 - i);
        t1 %= MOD;
    }
    ll t2 = 1;
    for(ll i = 1; i <= b; i++) {
        t2 *= modinv(i, MOD);
        t2 %= MOD;
        t2 *= (n + 1 - i);
        t2 %= MOD;
    }
    ans -= t1;
    ans = mod(ans, MOD);
    ans -= t2;
    ans = mod(ans, MOD);
    cout << ans << endl;
}

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

int main(){
    int n; cin >> n;
    vector<long long> a(n);
    long long all = 0;
    bitset<4000010> bit = 1;
    for (int i = 0; i < n; i++) {
        long long a; cin >> a;
        bit |= (bit << a);
        all += a;
    }
    for (long long i = (all+1)/2; ; i++) {
        if (bit[i]) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

int N=0, X=0, l=0, acc=0, ans=0;

int main(){
  cin >> N >> X;
  rep(i, N){
    cin >> l;
    acc += l;
    if (acc <= X) ans ++;
    else break;
  }
  cout << ans + 1 << endl;
}

Measured memory_bytes: 3516
#include <iostream>

using namespace std;

int N;
int A[100];

void solve() {
    cout << A[0];
    for (int j = 1; j < N; j++) {
        cout << ' ' << A[j];
    }
    cout << endl;

    for (int i = 1; i < N; i++) {
        int j;
        int v = A[i];
        for (j = i - 1; j >= 0 && A[j] > v; j--) {
            A[j + 1] = A[j];
        }
        A[j + 1] = v;

        cout << A[0];
        for (int j = 1; j < N; j++) {
            cout << ' ' << A[j];
        }
        cout << endl;
    }
}

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

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

int main() {
  int N, M, count = 0;
  cin >> N >> M;

  vector<int> R(M * 2);
  for (int i = 0; i < M * 2; i++) {
    cin >> R[i];
  }

  for (int i = 0; i < N; i++){
    for (int j = 0; j < M * 2; j++){
      if (j % 2 == 1)
        continue;
      if (R[j] == i + 1 || R[j + 1] == i + 1) {
        count++;
      }
    }
  cout << count << endl;
  count = 0;
  }
 
}

Measured memory_bytes: 256
#include<stdio.h>

int a[100001];
int n, sum = 0;

int binarySearch(int x)
{
	int low, high, mid;
	low = 0, high = n;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (x < a[mid])
			high = mid - 1;
		else if (x > a[mid])
			low = mid + 1;
		else return 1;
	}
	return 0;
}

void solve()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	int m;
	scanf("%d", &m);
	while (m--)
	{
		int x;
		scanf("%d", &x);
		if (binarySearch(x))
			sum++;
	}
	printf("%d\n", sum);
}

int main()
{
	solve();
}


Measured memory_bytes: 2092
#include<iostream>
#include<vector>
using namespace std;
static const int NMAX = 105;
static const int WMAX = 10005;
static const int SELECTED = 1;
static const int UNSELECTED = 0;
struct Item
{
	int value, weight;
};

Item items[NMAX + 1 ];
int N, W;
int C[NMAX +1][WMAX + 1], G[NMAX +1][WMAX + 1];

int compute(vector<int> &selection) {
   for ( int i = 0; i <= W; i++ ) {
      C[0][i] = 0;
    }
   for( int i = 1; i <= N; i++ )   C[i][0] = 0;

   for ( int i = 1; i <= N; i++ ) {
   		for( int j = 1; j <= W; j++ ) {
   			C[i][j] = C[i-1][j];
   			if( items[i].weight > j) continue;
   			C[i][j] = max( C[i-1][j], C[i-1][j-items[i].weight] +
   			 items[i].value );
   		}
   }

   return C[N][W];
}
int main() {

   cin >> N >> W;
   for(int i = 1; i <= N; i++) {
   	  cin >> items[i].value >> items[i].weight;
   }
    
   int maxValue = 0;
   std::vector<int> selection;
   maxValue = compute(selection);

   cout << maxValue << endl;
	return 0;
}


Measured memory_bytes: 7008
#include<stdio.h>  
#include<algorithm>  
#include<string.h>  
#include<queue>  
using namespace std;  
   
int vis[100009];  
typedef pair<int, int> P;  
   
   
int main()  
{  
    int k;  
    scanf("%d", &k);  
    deque<P> q;  
    memset(vis, 0, sizeof(vis));  
    q.push_back(make_pair(1, 1));  
    while(!q.empty())  
    {  
        P x = q.front(); q.pop_front();  
        if(vis[x.first]) continue;  
        vis[x.first] = 1;  
        if(x.first == 0)  
        {  
            printf("%d\n", x.second);  
            break;  
        }  
        q.push_front(make_pair(x.first*10 % k, x.second));  
        q.push_back(make_pair((x.first+1) % k, x.second+1));  
   
    }  
    return 0;  
}  

Measured memory_bytes: 1408
//ABC094B
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	int n, m, x;
	cin >> n >> m >> x;
	int pa = 0, pb = 0;
	for(int i=0;i<m;i++){
		int a;
		cin >> a;
		if(a < x){
			pa++;
		}else{
			pb++;
		}
	}
	cout << min(pa,pb) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i, N, A, sum = 0, num[2001] = {};
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%d", &A);
		sum += A;
		num[A]++;
	}
	
	int j, k, tail, half = sum / 2, q[2000001];
	char flag[2000001] = {1};
	for (i = 1, q[0] = 0, tail = 1; i <= 2000; i++) {
		if (num[i] == 0) continue;
		for (j = tail - 1; j >= 0; j--) {
			for (k = 1; k <= num[i] && q[j] + i * k <= half && flag[q[j]+i*k] == 0; k++) {
				flag[q[j]+i*k] = 1;
				q[tail++] = q[j] + i * k;
			}
		}
		if (flag[half] == 1) break;
	}
	
	for (i = half; i >= 1; i--) if (flag[i] == 1) break;
	printf("%d\n", sum - i);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 7592
#include <stdio.h>
int main(void){
    while(1){
    int n;
    scanf("%d",&n);
    if(n==0) break;
    int a[10]={0};
    for(int i=0;i<n;i++){
    int c;
    scanf("%d",&c);
    a[c]++;
    }
    for(int i=0;i<=9;i++){
        if(a[i]==0) printf("-");
        else{
        for(int j=0;j<a[i];j++) printf("*");
        }
    printf("\n");
    }
    }
   return 0;
}



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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int n, x; cin >> n >> x;
    int l[n];
    int d[n+1];
    int cnt = 0;
    REP(i,0,n) cin >> l[i];
    d[0] = 0;
    REP(i,1,n+1) d[i] = d[i-1]+l[i-1];
    REP(i,0,n+1){
        if(d[i]<=x) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
n,m,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort(key=int)
down=0
up=0
for i in range(m):
  if n>=a[i]>x:
    up+=1
  elif a[i]<x:
    down+=1
print(min(up,down))

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

struct Edge {
  ll cost;
  int from, to;
  Edge(){}
  Edge(int from, int to, ll cost) : from(from), to(to), cost(cost){}
};

static const int MAX = 1000;
static const ll INF = 1000000000000000LL;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
int N, M;
Edge e[2 * MAX];
ll d[MAX];

bool bellman_ford() {
  for (int i = 0; i < MAX; i++) {
    d[i] = INF;
  }
  // 頂点 0 からスタート
  d[0] = 0;
  for (int i = 0; i < 2 * N; i++) {
    for (int j = 0; j < M; j++) {
      if(d[e[j].from] != INF && d[e[j].to] > d[e[j].from] + e[j].cost) {
        d[e[j].to] = d[e[j].from] + e[j].cost;
        if(i >= N - 1 && e[j].to == N - 1) return true;
      }
    }
  }
  return false;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    e[i] = Edge(a - 1, b - 1, -c);
  }
  if (bellman_ford()) {
    cout << "inf\n";
  } else {
    cout << -d[N - 1] << "\n";
  }
  return 0;
}

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

using namespace std;
map<pair<pair<long long , long long > , long long > , bool > mp;
int main()
{
    long long a , b , c ;
    cin >> a >> b >> c ;
    int ans = 0 ;
    mp[{{a,b},c}]=1;
    while(!(a&1) && !(b&1) &&!(c&1)){
        ans++ ;
        int bb = b>>1 , aa = a>>1 , cc = c>>1;
        a = bb + cc , b = aa + cc , c = aa+bb;
        if(mp[{{a,b},c}]){
            cout << -1 ;
            return 0;
        }
        mp[{{a,b},c}]=1;
    }
    cout << ans ;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
constexpr int MOD = 1000000007;
using ll = long long;
using namespace std;

ll inv(ll x) {
    ll res = 1;
    ll k = MOD - 2;
    ll y = x;
    while (k) {
        if (k & 1) res = (res * y) % MOD;
        y = (y * y) % MOD;
        k /= 2;
    }
    return res;
}

ll powmod(ll a, ll n, ll m) {
    ll ret = 1;
    for (; n > 0; n >>= 1, a = a * a % m) {
        if (n % 2 == 1) {
          ret = ret * a % m;
        }
    }
    return ret;
}

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

    ll total = powmod(2, n, MOD);
    total = (total - 1 + MOD) % MOD;
    //cout << "2^n:" << total << endl;
    
    ll fa, fb, fn_a, fn_b;
    ll pre = 1, next;
    for (int i = n - a + 1; i <= n; i++) {
        next = (pre * i) % MOD;
        pre = next;
    }
    fn_a = next;
    pre = 1;
    for (int i = n - b + 1; i <= n; i++) {
        next = (pre * i) % MOD;
        pre = next;
    }
    fn_b = next;
    pre = 1;
    for (int i = 1; i <= max(a, b); i++) {
        next = (pre * i) % MOD;
        if (i == a)
            fa = next;
        if (i == b)
            fb = next;
        pre = next;
    }
    
    ll Cna, Cnb;
    Cna = fn_a * inv(fa) % MOD;
    Cnb = fn_b * inv(fb) % MOD;
    //cout << "C(n,a):" << Cna << " C(n,b):" << Cnb << endl;;
    
    total = total - Cna;
    total = (total + MOD) % MOD;
    total = total - Cnb;
    total = (total + MOD) % MOD;
    cout << total << endl;
    
    return 0;
}


Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
    static final Scanner     sc = new Scanner(System.in);
    static final PrintStream so = System.out;
    
    public static void main(String[] args) {
        int n = ni();
        int m = ni();

        int left = 0;
        int right = n+1;
        for (int i = 0; i < m; i++) {
            left = Math.max(left, ni());
            right = Math.min(right, ni());
        }
        
        int diff = right - left + 1;
        so.println(Math.max(diff, 0));
    }
    
    private static int ni() {
        return sc.nextInt();
    }

    private static long nl() {
        return sc.nextLong();
    }

    private static String ns() {
        return sc.next();
    }

    private static char[] nsToChars() {
        return sc.next().toCharArray();
    }

    private static int[] nints(int n) {
        return nints(n, 0);
    }

    private static int[] nints(int n, int padding) {
        int[] a = new int[padding + n];
        for (int i = 0; i < n; i++)
            a[padding + i] = ni();
        return a;
    }
}


Measured memory_bytes: 64800
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long N; cin>>N;
    vector<long long>A(N);
    for(int i=0;i<N;i++)cin>>A[i];
    long long mm=0;
    long long m=0;
    for(int i=0;i<N;i++){
        if(A[i]>m){
            m=A[i];
            if(m>mm){
                m=mm;
                mm=A[i];
            }
        }
    }
    for(int i=0;i<N;i++){
        if(A[i]==mm){
            cout<<m<<endl;
        }
        else{
            cout<<mm<<endl;
        }
    }
}

Measured memory_bytes: 3200
# -*- coding: utf-8 -*-
import copy

a,b = map(int, raw_input().split())
h_max = 40
w_max = 100
ans = []
buff = [ "." for i in range(w_max)]
buff2 = [ "#" for i in range(w_max)]
for j in range(h_max/2):
    tmp = copy.deepcopy(buff)
    ans.append(tmp)
for j in range(h_max/2):
    tmp = copy.deepcopy(buff2)
    ans.append(tmp)

h = h_max
w = w_max
a = a - 1
b = b - 1

px = 0
py = 0
while b > 0:
    b = b - 1
    ans[py][px] = "#"
    px = px + 2
    if px > w_max - 1:
        py = py + 2
        px = 0
#    print("[{} {}]".format(px, py))

px = 0
py = h_max / 2 + 1
while a > 0:
    a = a - 1
    ans[py][px] = "."
    px = px + 2
    if px > w_max - 1:
        py = py + 2
        px = 0
#    print("[{} {}]".format(px, py))

print("{} {}".format(h, w))
for j in range(h):
    print ''.join(ans[j])



Measured memory_bytes: 3076
#include <cstdio>
#include <algorithm>
using namespace std;
bool arr[110000]={};
int nb[110000]={};
int main(){
	int n,m,t1,t2,a=0;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		nb[i]=1;
	}
	arr[1]=true;
	for(int i=1;i<=m;i++){
		scanf("%d %d",&t1,&t2);
		nb[t1]--;
		nb[t2]++;
		arr[t2]|=arr[t1];
		if(nb[t1]==0)arr[t1]=false;
	}
	for(int i=1;i<=n;i++){
		a+=arr[i];
	}
	printf("%d",a);
}


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

int main(){
  string a, b, c;

  cin >> a >> b >> c;

  if(a.back() != b.front()){
    cout << "NO" << endl;
  } else if (b.back() != c.front()){
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }


  return 0;
}


Measured memory_bytes: 256
/*
Original problem: https://atcoder.jp/contests/abc133/tasks/abc133_b
Author: sammochen
*/

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;

#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)

#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef vector<ll> VLL;
typedef vector<int> VI;

const ll mod = 1e9+7;

namespace SOLVE {
    void main() {
        int n, d;
		cin >> n >> d;
		vector<VLL> A(n, VLL(d));
		REP(i,0,n) {
			REP(j,0,d) {
				cin >> A[i][j];
			}
		}
		ll ans = 0;
		// for every two pairs
		REP(i,0,n) {
			REP(j,0,i) {
				ll t = 0;
				REP(k,0,d) {
					t += (A[i][k] - A[j][k]) * (A[i][k] - A[j][k]);
				}
				ll s = sqrt(t);
				if (s * s == t) {
					ans++;
				}
			}
		}
		cout << ans << endl;
    }
}


signed main() {
	int t;
	t = 1;
	// cin >> t;
	while (t--) {
		SOLVE::main();
	}

	return 0;
}

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

int gcd(int a, int b) {
    if (b > a) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    if (a % b != 0) {
        return gcd(b, a % b);
    } else {
        return b;
    }
}

int main() {
    int a, b, result = 1;
    cin >> a >> b;

    cout << gcd(a, b) << endl;
}



Measured memory_bytes: 3108
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <numeric> // next_parmutation
#define ll long long
#define rep(i, n) for(int i = 0; i < (n); i++)

using namespace std;

int main() {
    int K;
    cin >> K;
    string S;
    cin >> S;
    int len = S.size();
    if(len <= K) cout << S << endl;
    else{
        rep(i, K){
            cout << S.at(i);
        }
        cout << "..." << endl;
    }



}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

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

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double pi = 3.141592653589793;
ll mod = 1000000007;
ll INF = 1000000001;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;



int main(){
	int n,ans=0;
    cin>>n;
    vi b(n-1);
    rep(i,n-1){
        cin>>b[i];
        if(i==0){
            ans+=b[i];
            // cout<<ans<<endl;
        }else{
            ans+=min(b[i],b[i-1]);
            // cout<<ans<<endl;
        }
    }
    ans+=b[n-2];
    cout<<ans<<endl;
    // cout<<b[n-1]<<endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long ll;
const int n = 1e6+5;

int N, M, K;


struct node {
	int eos = 0, chi = 0;
	int cc[26];
	int c[26];
};

int root, NC = 0;
node nodes[n];

inline int getIndex(char c) {
	return c - 'a';
}

int createNode() {
	int r = NC++;
	for(int i = 0; i < 26; i++)
		nodes[r].c[i] = -1, nodes[r].cc[i] = 0;
	return r;
}

void insertString(string & s, int i, int n = root) {
	nodes[n].chi++;
	if(i == -1) {
		nodes[n].eos++;
		return;
	}
	if(nodes[n].c[getIndex(s[i])] == -1)
		nodes[n].c[getIndex(s[i])] = createNode();
	//cerr << "insert " << s << " i: " << i << " cc: " << (n->chi) <<endl;
	insertString(s, i - 1, nodes[n].c[getIndex(s[i])]);
	//n->cc[getIndex(s[i])]++;
}

void init() {
	root = createNode();
}

void doDP(int n = root){
	for(int i = 0; i < 26; ++i){
		if(nodes[n].c[i] != -1){
			doDP(nodes[n].c[i]);
			for(int j = 0; j < 26; ++j){
				int cv = nodes[nodes[n].c[i]].cc[j];
				if(j == i) cv = nodes[nodes[n].c[i]].chi;
				//if(cv > 0) cerr << "cv: " << cv << endl;
				nodes[n].cc[j] += cv;
			}
		}
	}
}

int query(string & s, int i, int n = root) {
	if(i == 0){
		return nodes[n].cc[getIndex(s[i])];
	}
	if(nodes[n].c[getIndex(s[i])] == -1)
		return 0;
	else
		return query(s, i -1, nodes[n].c[getIndex(s[i])]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	vector<string> V;
	init();
	for(int i = 0; i < N; ++i){
		string s; cin >> s;	
		V.push_back(s);
		insertString(s, sz(s) - 1);
	}
	doDP();
	ll cc = 0;
	for(string s : V){
		int v = query(s, sz(s) - 1);
		//cerr << s << ": " << v << endl;
		cc += v - 1;
	}
	cout << cc << endl;
	return 0;
}


Measured memory_bytes: 246824
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; 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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

string N;

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

  ll sum = 0;
  for (auto c : N) {
    ll num = c - '0';
    sum += num;
  }

  if (sum % 9 == 0) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}


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

int main() {
  int N;
  cin >> N;
  vector<int> l(N);
  vector<int> r(N);
  for (int i = 0; i < N; i++) {
    cin >> l.at(i) >> r.at(i);
  }
  int num = 0;
  for (int j = 0; j < N; j++) {
    num += (r.at(j) - l.at(j) + 1);
  }
  cout << num << endl;
}

Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
  
N = int(input())
ans = factorization(N)
count = 0
for i in ans:
  if i[0] == 1:
    break
  for j in range(2,40):
    if i[1] < j*(j+1)/2:
      count += j-1
      break
print(count)

Measured memory_bytes: 9492
from datetime import date, timedelta

st = date(2012, 12, 21)
while True:
    s = input()
    if s == '#':
        break
    d = list(map(int, s.split('.')))
    if len(d) == 3:
        r = 0
        while d[0] > 3000:
            d[0] -= 400
            r += 365*400+97

        ed = date(d[0], d[1], d[2])
        r += (ed-st).days
        ki = r%20
        r//=20
        w = r%18
        r//=18
        t = r%20
        r//=20
        ka = r%20
        r//=20
        b = r%13
        print(str(b)+'.'+str(ka)+'.'+str(t)+'.'+str(w)+'.'+str(ki))
    else:
        r = d[0]
        r *= 20
        r += d[1]
        r *= 20
        r += d[2]
        r *= 18
        r += d[3]
        r *= 20
        r += d[4]
        ed = st+timedelta(days=r)
        print(str(ed.year)+'.'+str(ed.month)+'.'+str(ed.day))

Measured memory_bytes: 7096
/* power.cpp
    繰り返し二乗法で pow(x,n) を求める
*/

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main() {
    long long x, n;
    cin >> x >> n;
    cout << pow(x, n) << endl;
    return 0;
}



Measured memory_bytes: 3112
#include<stdio.h>
int main()
{
    double a,b,c;

    scanf("%lf%lf", &a,&b);

    if (a>b)
    {
        printf("GREATER\n");
    }
    else if (a<b)
    {
        printf("LESS\n");
    }
    else if (a==b)
    {
        printf("EQUAL\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
struct t {
	int c,s,f;
} t[503];
int main()
{
	int n,c,s,f,sum; scanf("%d",&n);
	for(int i = 0 ; i < n - 1; ++i) {
		scanf("%d %d %d", &t[i].c, &t[i].s, &t[i].f);
	}
	for(int i = 0; i < n - 1; ++i) {
		sum = t[i].c + t[i].s;
		for(int j = i + 1; j < n - 1; ++j) {
			c = t[j].c , s = t[j].s, f = t[j].f;
			if( sum <= s ) sum = s + c; 
			else if(sum > s) sum = (int)ceil((float)sum/f) * f + c;  
		}
		printf("%d\n",sum);
	}
	printf("0\n");
	return 0;
}

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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;

vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find algo with array
// Find()
int findpar(int curr, int arr[])
{
  while(arr[curr] != curr) curr = arr[curr];
  return curr;
}
// Union()
void Union(int b, int spa, int arr[])
{
  while(arr[b] != b)
  {
    int c = arr[b];
    arr[b] = spa;
    b = c;
  }
  arr[b] = spa;
}

// Main Code

int main()
{
  string o, e;
  cin>>o>>e;
  rep(i, 0, min(o.length(), e.length()))
    cout<<o[i]<<e[i];
  if(o.length() > e.length())
    cout<<o[o.length()-1]<<endl;
  else if(o.length() == e.length())
    cout<<endl;
  else
    cout<<e[e.length()-1]<<endl;
  return 0;
}


Measured memory_bytes: 12160
#include <stdio.h>

int main(void){
    int n;

    scanf("%d", &n);

    if(n == 1) printf("%f\n", (float)n);
    else if((n % 2) == 0) printf("%f\n", 0.5);
    else printf("%f\n", (float)((n/2) + 1)/n);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i, MAT.size()){
    REP(j, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

template <typename CLASS1, typename CLASS2>
class HOGE{
  public:
    CLASS1 key;
    CLASS2 value;
    HOGE(void){
      return;
    };
    HOGE(CLASS1 key, CLASS2 value){
      this->key = key;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "key : " << key << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N, M;
  cin >> N >> M;

  vll count(N, 0);
  REP(i, M){
    ll a, b;
    cin >> a >> b;
    count[a-1]++;
    count[b-1]++;
  }

  REP(i, N){
    if(count[i]%2==1){
      cout << "NO\n";
      return 0;
    }
  }
  cout << "YES\n";
  return 0;

  return 0;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (ll r = a % b)
		a = b, b = r;
	return b;
}

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

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

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

//	for priority queue
//	priority_queue<ipair, vector<ipair>, greater<ipair>>
using ipair = pair<int, pair<int, int>>;
bool operator>(const ipair a, const ipair b) { return a.first > b.first; };
bool operator<(const ipair a, const ipair b) { return a.first < b.first; };

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a.begin(), a.end());
	vector<bool> p(1e6 + 1, false);
	int r = 0;
	for (int i = 0; i < n; i++)
	{
		bool x = i == n - 1 || (i < n - 1 && a[i] != a[i + 1]);
		if (p[a[i]])
			continue;
		if (!p[a[i]] && x)
			r++;
		for (int j = a[i]; j <= 1e6; j += a[i])
			p[j] = true;
	}

	printf("%d", r);

	return 0;
}


Measured memory_bytes: 3668
#include<stdio.h>
int main (void)
{
    int i,p,K,ans;
    char arba[101];
    while(scanf("%s",arba)!=EOF){
        p=0,ans=0,K=0;
        for(i=0;;i++){
            if(arba[i]=='\0'){
                K=i;
                break;
            }
        }
        for(i=K-1;i>=0;i--){
            if(arba[i]=='M'){
                ans+=1000;
                p=1000;
            }
            else if(arba[i]=='D'){
                if(500>=p) ans+=500;
                else ans-=500;
                p=500;
            }
            else if(arba[i]=='C'){
                if(100>=p) ans+=100;
                else ans-=100;
                p=100;
            }
            else if(arba[i]=='L'){
                if(50>=p) ans+=50;
                else ans-=50;
                p=50;
            }
            else if(arba[i]=='X'){
                if(10>=p) ans+=10;
                else ans-=10;
                p=10;
            }
            else if(arba[i]=='V'){
                if(5>=p) ans+=5;
                else ans-=5;
                p=5;
            }
            else if(arba[i]=='I'){
                if(1>=p) ans+=1;
                else ans-=1;
                p=1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

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

int main() {
    char c;
    cin >> c;
    bool ans = false;

    if (c == 'a') ans = true;
    if (c == 'e') ans = true;
    if (c == 'i') ans = true;
    if (c == 'o') ans = true;
    if (c == 'u') ans = true;
    

    if(ans) {
        cout << "vowel" << endl;
    }
    else {
        cout << "consonant" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

int c(int x) {
  if(x == 3) return 100000;
  if(x == 2) return 200000;
  if(x == 1) return 300000;
  return 0;
}

int main(){
  int x, y; cin >> x >> y;
  int s = c(x) + c(y);
  if(x == 1 && y == 1) s += 400000;
  cout << s << endl;

  return 0;
}

// EOF


Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    if (m == 0) {
      System.out.println(1);
      return;
    }
    Map<Integer, UnionFind<Integer>> friendSetMap = new HashMap<>();
    for (int i = 1; i <= n; i++) {
      friendSetMap.put(i, new UnionFind<>(1));
    }
    for (int i = 0; i < m; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      UnionFind.union(friendSetMap.get(a), friendSetMap.get(b), Integer::sum);
    }
    int result = 0;
    for (int i = 1; i <= n; i++) {
      Integer value = friendSetMap.get(i).getRoot().getValue();
      if (value > result) {
        result = value;
      }
    }
    System.out.println(result);
  }
}

class UnionFind<T> {
  UnionFind<T> parent;
  private T value;

  public UnionFind(T value) {
    this.value = value;
  }

  public static <S> void union(UnionFind<S> a, UnionFind<S> b, BiFunction<S, S, S> unionMap) {
    UnionFind<S> aRoot = a.getRoot();
    UnionFind<S> bRoot = b.getRoot();
    if (aRoot != bRoot) {
      bRoot.parent = aRoot;
      aRoot.value = unionMap.apply(aRoot.getValue(), bRoot.getValue());
    }
  }

  public T getValue() {
    return value;
  }

  public UnionFind<T> getRoot() {
    if (parent == null) {
      return this;
    }
    UnionFind<T> root = parent.getRoot();
    parent = root;
    return root;
  }
}


Measured memory_bytes: 69464