akhauriyash/Code-Regression huggingface dataset:
from collections import deque
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()
b = list(a)
a = deque(a)
b = deque(b)

l=a.popleft() 
r=l
count=0
ans=0
while len(a)>0:
  if count%4==0:
    temp=a.pop()
    ans+=abs(temp-l)
    l=temp
  elif count%4==1:
    temp=a.pop()
    ans+=abs(temp-r)
    r=temp
  elif count%4==2:
    temp=a.popleft()
    ans+=abs(l-temp)
    l=temp
  elif count%4==3:
    temp=a.popleft()
    ans+=abs(r-temp)
    r=temp
  count+=1
  
l=b.pop() 
r=l
count=0
ans2=0
while len(b)>0:
  if count%4==2:
    temp=b.pop()
    ans2+=abs(temp-l)
    l=temp
  elif count%4==3:
    temp=b.pop()
    ans2+=abs(temp-r)
    r=temp
  elif count%4==0:
    temp=b.popleft()
    ans2+=abs(l-temp)
    l=temp
  elif count%4==1:
    temp=b.popleft()
    ans2+=abs(r-temp)
    r=temp
  count+=1
print(max(ans, ans2))

Measured memory_bytes: 85816
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, answer = 0, tmpA, beforeTmpA;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	vector<int> C(N);
	for (int count = 0; count < N; count++)
	{
		cin >> A.at(count);
	}
	for (int count = 0; count < N; count++)
	{
		cin >> B.at(count);
	}
	for (int count = 0; count < N - 1; count++)
	{
		cin >> C.at(count);
	}
	for (int count = 0; count < N; count++)
	{
		tmpA = A.at(count);
		answer += B.at(tmpA - 1);
		if (count != 0 && beforeTmpA + 1 == tmpA)
		{
			answer += C.at(beforeTmpA - 1);
		}
		beforeTmpA = tmpA;
	}
	cout << answer << endl;
}

Measured memory_bytes: 256
N, M, X, Y = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

max_x = max(x)
min_y = min(y)
for i in range(X+1, Y+1):
  if(max_x < i <= min_y):
    print("No War")
    break
else:
  print("War")

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

int par[202020], sz[202020];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int u, int v){ u = find(u); v = find(v); if(u != v) par[u] = v, sz[v] += sz[u]; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    iota(par, par+202020, 0);
    fill(sz, sz+202020, 1);
    
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e;
        merge(s, e);
    }
    int mx = 0;
    for(int i=1; i<=n; i++) mx = max(mx, sz[find(i)]);
    cout << mx;
}

Measured memory_bytes: 11340
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <istream>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
typedef long long ll;
using namespace std;
int main() {

	int n = 0;
	ll count = 0;
	scanf("%d", &n);
	vector<ll>a(n + 1);
	vector<ll>b(n);
	rep0(i, n) scanf("%lld", &a[i]);
	rep0(j, n - 1)scanf("%lld", &b[j]);
	rep0(k, n - 1) {
		if (a[k] >= b[k]) {
			count += b[k];
		}
		else {
			count += a[k];
			b[k] -= a[k];
			if (b[k] >= a[k + 1]) {
				count += a[k + 1];
				a[k + 1] = 0;
			}
			else {
				a[k + 1] -= b[k];
				count += b[k];
			}
		}
	}
	printf("%lld", count);
	return 0;
}


Measured memory_bytes: 1792
#include <cmath>
#include <vector>
#include <map>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>

using namespace std;

#define ll long long int
#define pll pair<double,ll>

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};


int main()
{
    int n,k,l;
    cin >> n >> k >> l;
    UnionFind uk(n);
    UnionFind ul(n);
    for(int i = 0;i < k;i++)
    {
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        uk.unionSet(p, q);
    }
    for(int i = 0;i < l;i++)
    {
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        ul.unionSet(p, q);
    }
    
    map<pll,int> m;
    for(int i = 0;i < n;i++)
    {
        int fi = uk.root(i);
        int si = ul.root(i);
        pll p = make_pair(fi, si);
        m[p]++;
    }
    for(int i = 0;i < n;i++)
    {
        int fi = uk.root(i);
        int si = ul.root(i);
        pll p = make_pair(fi, si);
        cout <<m[p] << " ";
    }
    
    cout << endl;
    return 0;
}


Measured memory_bytes: 13568
import java.io.*;
import java.util.*;

public class Main
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public void go() throws IOException
    {
        StringTokenizer tok = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tok.nextToken());
        int q = Integer.parseInt(tok.nextToken());
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++)
        {
            nodes[i] = new Node();
        }
        for (int i = 0; i < n-1; i++)
        {
            tok = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(tok.nextToken())-1;
            int b = Integer.parseInt(tok.nextToken())-1;
            nodes[a].children.add(nodes[b]);
            nodes[b].children.add(nodes[a]);
        }

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(nodes[0]);
        while (!queue.isEmpty())
        {
            Node curr = queue.remove();
            if (curr.visited)
            {
                continue;
            }
            curr.visited = true;
            Iterator<Node> it = curr.children.iterator();
            while (it.hasNext())
            {
                Node next = it.next();
                if (next.visited)
                {
                    it.remove();
                }
                else
                {
                    queue.add(next);
                }
            }
        }

        for (int i = 0; i < q; i++)
        {
            tok = new StringTokenizer(in.readLine());
            int p = Integer.parseInt(tok.nextToken())-1;
            int x = Integer.parseInt(tok.nextToken());
            nodes[p].value += x;
        }
        update(nodes[0], 0);
        for (int i = 0; i < n; i++)
        {
            if (i != 0)
            {
                out.print(" ");
            }
            out.print(nodes[i].value);
        }
        // out.println();

        out.flush();
        in.close();
    }

    public void update(Node curr, long add)
    {
        curr.value += add;
        for (Node next : curr.children)
        {
            update(next, curr.value);
        }
    }

    public static void main(String[] args) throws IOException
    {
        new Main().go();
    }

    private class Node
    {
        ArrayList<Node> children;
        long value;
        boolean visited;

        public Node()
        {
            children = new ArrayList<>();
        }
    }
}


Measured memory_bytes: 126080
#include<stdio.h>//khata

int isPrime(int n)
{
    int i;

    if(n <= 1)
        return 0;
    for(i=2; i*i <= n; i++)
    {
        if(n%i == 0)
            return 0;
    }
    return 1;
}

int finding_prime(int n)
{
    while(isPrime(n) != 1)
    {
        n++;
    }

    return n;
}

int main()
{
    int x, returned;

    scanf("%d", &x);

    returned = isPrime(x);

    if(returned == 1)
        printf("%d\n", x);

    else if(returned == 0)
    {
        x=finding_prime(x);
    }

    if(returned == 0)
        printf("%d\n", x);

    return 0;
}







Measured memory_bytes: 1728
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const double EPS = 1e-9;

int main(){
	int l[10], v[2];
	while(scanf("%d,", &l[0])!=EOF){
		for(int i=1; i<10; i++){
			scanf("%d,", &l[i]);
		}
		scanf("%d,%d", &v[0], &v[1]);
		
		int total=0;
		for(int i=0; i<10; i++){
			total += l[i];
		}
		
		double t = (double)total/(v[0]+v[1]);
		double d = v[0]*t -EPS;
		int sum=0;
		for(int i=0; i<10; i++){
			sum += l[i];
			if(sum > d){
				cout << i+1 << endl;
				break;
			}
		}
	}
    return 0;
}

Measured memory_bytes: 3136
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashSet<Integer> set = new HashSet<>();
        for(int i=0; i<3; i++){
            int t = sc.nextInt();
            set.add(t);
        }
        System.out.println(set.size());
        
    }
}

Measured memory_bytes: 9680
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
using namespace std;


typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)


int main(){
  int a, b, c;
  cin >> a >> b >> c;
  int ma = max(a, max(b, c));
  int diff = 0;
  if(ma == a){
    diff -= b + c;
  } else if( ma == b){
    diff -= a + c;
  } else {
    diff -= a + b;
  }

  diff += 2 * ma;

  int ans = diff / 2;

  if(diff % 2 == 1) ans += 2;

  cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>

#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++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;




int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout<<setprecision(10);
  int k;
  cin>>k;
  while(k%2==0)k/=2;
  while(k%5==0)k/=5;
  int loop=0;
  int m=1;
  vector<int>edge;
  vector<int>f(k,0);
  do {
    //edge.push_back(m);
    if(f[m]==0)f[m]=1;
    else break;
    m*=10;
    m%=k;
    loop++;
  }while(m!=1);
  int l=0;
  rep(i,k)l+=f[i];
  //cout<<l<<endl;
  edge.resize(l);
  l=0;
  rep(i,k){if(f[i]){edge[l]=i;l++;}}
  //cout<<loop<<endl;
  //  cout<<k<<endl;
  if(k==1){cout<<1<<endl;return 0;}
  if(loop==k-1){cout<<2<<endl;return 0;}
  vector<int>dist(k,0);

  queue<int>que;
  que.push(1);
  while(!que.empty())
  {
    int now=que.front();que.pop();
    for(int i:edge)
    {
      int tmp=(i+now);
      if(tmp>=k)tmp-=k;
      if(dist[tmp]>0)continue;
      dist[tmp]=dist[now]+1;
      if(tmp==0)
      {
        cout<<dist[tmp]+1<<endl;
        return 0;
      }
      que.push(tmp);
    }
  }



  return 0;

}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(){
	
	int n;
	cin>>n;
	int b[n];
	int max=-1;
	//cout<<a[0]<<a[1]<<a[2];
	for(int i=0;i<n;i++){
		cin>>b[i];
		if(b[i]>max)
		max=b[i];
		
	}
	int a[max+1];
	for(int i=0;i<=max;i++)
	    a[i]=0;
	for(int i=0;i<n;i++){
		a[b[i]]++;
	}
int 	count=0;
int ans=0;
int p=0;
		for(int i=1;i<=max;i++){
	      count=count+a[i];
	      if(count==(n/2)){
	      p=i;
	      break;
		  }
	      
	}
	
	//cout<<"count"<<count<<endl;
	//for(int i=0;i<=max;i++)
	//  cout<<a[i]<<endl;
	//cout<<"p"<<p<<endl;
	for(int i=p+1;i<=max;i++){
		if(a[i]==0)
		ans++;
		else {
			ans++;
			break;
		}
		
	}
	if(count==n/2)
	cout<<ans<<endl;
	else cout<<"0"<<endl;
	
	
	
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
  int n,m;
  int i,j;
  cin>>n>>m;
  vector<int> ab(m*2),city(n);  
  for(i=0;i<m*2;++i)cin>>ab.at(i);
  for(i=0;i<m*2;++i)
    for(j=1;j<=n;++j)
     if(ab.at(i)==j)city.at(j-1)+=1;
  //for(i=0;i<m;++i)cout<<ab.at(i)<<" "<<ab.at(i+1)<<endl;
  for(j=0;j<n;++j)cout<<city.at(j)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int k;
  cin >> k;
  if(k%2==0) {
      cout<<k/2*k/2<<'\n';
  } else {
      cout<<k/2*(k/2+1)<<'\n';
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		if(n % 500 <= a) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

int main() {
	int n;
	while (cin >> n, n) {
		vector<int> b(n);
		REP(i, n) scanf("%d", &b[i]);
		
		int ans = 0;
		
		while (true) {
			bool flag = true;
			REP(i, b.size()) if (b[i] != i + 1) flag = false;
			if (flag) break;
			
			if (ans > 10000) { ans = -1; break; }

			vector<int> tmp;
			REP(i, b.size()) if (b[i] > 1) tmp.push_back(b[i] - 1);
			tmp.push_back(b.size());

			b = tmp;
			ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3172
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;

const string YES = "Yes";
const string NO = "No";

void solve(long long A, long long B, long long C){
  cout<<((A+B>=C)? "Yes" : "No" )<<endl; 
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


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

int main(void) {
  int K, S;
	cin >> K >> S;
  int count = 0;
  REP(x,K+1) REP(y, K+1) if ((S-x-y) <= K && (S-x-y) >= 0) count++;
  cout << count << '\n';
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	string a, b, c; int al = 0, bl = 0, cl = 0; cin >> a >> b >> c;
	int n = 1;
	for (int i = 0; ; i++){
		if (n == 1) {
			if (al == a.size()) {
				cout << "A\n"; return 0;
			}
			al++;
			if (a[al - 1] == 'a')n = 1;
			else if (a[al - 1] == 'b')n = 2;
			else if (a[al - 1] == 'c')n = 3;
		}
		else if (n == 2) {
			if (bl == b.size()) {
				cout << "B\n"; return 0;
			}
			bl++;
			if (b[bl - 1] == 'a')n = 1;
			else if (b[bl - 1] == 'b')n = 2;
			else if (b[bl - 1] == 'c')n = 3;
		}
		else if (n == 3) {
			if (cl == c.size()) {
				cout << "C\n"; return 0;
			}
			cl++;
			if (c[cl - 1] == 'a')n = 1;
			else if (c[cl - 1] == 'b')n = 2;
			else if (c[cl - 1] == 'c')n = 3;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define ALL(a)  (a).begin(),(a).end()
using namespace std;

string s, t;
vector<int> abc[26];

int main() {
  cin >> s >> t;
  rep(i, s.size()) {
    abc[s[i] - 'a'].push_back(i);
  }
  rep(i, s.size()) {
    abc[s[i] - 'a'].push_back(i+s.size());
  }
  int cnt=0;
  int where=-1;
  int over;
  rep(i, t.size()) {
    if((abc[t[i] - 'a']).size() == 0){
      cout << -1 << endl;
      return 0;
    }
    auto nex = upper_bound(ALL(abc[t[i] - 'a']), where);
    where = *nex % s.size();
    over = *nex / s.size();
    cnt += over;
  }
  cout << (int64_t) s.size() * cnt + where + 1 << endl;
  return 0;
}



Measured memory_bytes: 1724
N = int(input())
A = [int(input()) for _ in range(N)]

# 操作2は0番目からの距離のmodが変化しない
# modが異なる数 / 2が答え

B = sorted(A)
sortedIndex = {b : i for i, b in enumerate(B)}

ans = 0
for i, a in enumerate(A):
    if i % 2 != sortedIndex[a] % 2:
        ans += 1

print(ans // 2)

Measured memory_bytes: 19884
using System;

class Program {
    private static int Main() {
        int[] data = new int[ 26 ];
        while( true ) {
            var input = Console.ReadLine();
            if( string.IsNullOrEmpty( input ) ) { break; }

            foreach( var c in input ) {
                int index = char.ToLower( c ) - 'a';
                if( index >= 0 && index < data.Length ) {
                    ++data[ index ];
                }
            }
        }

        for( int i = 0; i < data.Length; ++i ) {
            var output = string.Format( "{0} : {1}", (char)( 'a' + i ), data[ i ] );
            Console.WriteLine( output );
        }

        return 0;
    }
}

Measured memory_bytes: 5632
#!/usr/bin/env python3
import sys


def solve(D: int):
    print("Christmas" + " Eve" * (25 - D))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    solve(D)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#宿泊数N,金額を表す計算用宿泊日数K,K泊目の金額X,K+1泊目の金額
N=int(input())
K=int(input())
X=int(input())
Y=int(input())

if N<K:
    a=N*X
    b=0
else:
    a=K*X
    b=(N - K) * Y

print(a+b)

Measured memory_bytes: 9112
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<iostream>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

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

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b)
{
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

ll lcm(ll a,ll b)
{
   return a/gcd(a,b)*b;
}

//累乗だってさ
ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}
//逆元だってさ
ll modinv(ll a,ll mod1) {
    return modpow(a, mod1 - 2, mod1);
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,ans=0;
    cin>>n;
    vec<ll> a(n);
    rep(i,n) cin>>a[i];
    rep(i,n) ans=gcd(ans,a[i]);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int p, l, r; };
struct Node T[MAX];
int n;


void preParse(int u) {
  if ( u == NIL ) return;
  printf(" %d", u);
  preParse(T[u].l);
  preParse(T[u].r);
}


void inParse(int u) {
  if ( u == NIL ) return;
  inParse(T[u].l);
  printf(" %d", u);
  inParse(T[u].r);
}


void postParse(int u) {
  if ( u == NIL ) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d", u);
}

int main() {
  int i, v, l, r, root;

  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) {
    T[i].p = NIL;
  }

  for ( i = 0; i < n; i++ ) {
    scanf("%d %d %d", &v, &l, &r);
    T[v].l = l;
    T[v].r = r;
    if ( l != NIL ) T[l].p = v;
    if ( r != NIL ) T[r].p = v;
  }

  for ( i = 0; i < n; i++ ) if ( T[i].p == NIL ) root = i;

  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");

  return 0;
}
    



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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "cycle"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

void solve(){
	ll a, b;
	cin >> a >> b;
	if (a <= 0 && b >= 0){
		cout << "Zero\n";
	} else if (a > 0){
		cout << "Positive\n";
	} else if (a % 2 == b % 2){
		cout << "Negative\n";
	} else {
		cout << "Positive\n";
	}
}	

int main(){

	//freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();	
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    map <int,int> m;
    long long arr[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        m[arr[i]]++;
    }
    for(int i=1;i<=n;i++)
        cout<<m[i]<<endl;
    
}
  

Measured memory_bytes: 14536
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let a: usize = scan(tokens);
    let b: usize = scan(tokens);
    let c: usize = scan(tokens);
    if a + b < c && 4 * a * b < (c - (a + b)).pow(2) {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>
#define ll long long int
int main(void){
	int n,i;
	scanf("%d",&n);
	double x,s=0;
	char u[4];
	char JPY[4] = "JPY";
	ll sum = 0;
	for(i=0;i<n;i++){
		scanf("%lf",&x);
		scanf("%s",u);
		if(strcmp(u, JPY) == 0){
			sum += x;
		}else{
			s += x*380000;
		}
	}
	printf("%lf",s+sum);
	return 0;
}

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

int main() {
  int n,startx,ans=1;
  cin >> n >> startx;
  vector<int> x(n);
  for(int i=0;i<n;i++) {
    cin >> x[i];
    x[i]-=startx;
    x[i]=max(x[i],0-x[i]);
  }
  sort(x.begin(),x.end());
  
  for(int i=1;true;i++) {
    if(x[0]%i==0) {
      int a = x[0]/i;
      for(int j=0;j<x.size();j++) {
        if(x[j]%a!=0) break;
        if(j+1==x.size()) ans=max(ans,a);
      };
    };
    for(int j=0;j<x.size();j++) {
      if(x[j]%i!=0) break;
      if(j+1==x.size()) ans=max(ans,i);
    };
    if(i*i>x[0]) break;
  };

  cout << ans << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);

		int[][][] card  = new int[3][3][2];
		for(int i = 0; i < 3; i++){
			String line = scanner.nextLine();
			String[] ss = line.split(" ");
			for(int j = 0; j < 3; j++){
				card[i][j][0] = Integer.parseInt(ss[j]);
				card[i][j][1] = 0;
			}
		}
		int n = scanner.nextInt();

		int[] b = new int[n];
		for(int i = 0; i < n; i++){
			b[i] = scanner.nextInt();
			for(int k = 0; k < 3; k++){
				for(int j = 0; j < 3; j++){
					if(card[k][j][0] == b[i]){
						card[k][j][1] = 1;
					}
				}
			}
		}
		Boolean isBingo = false;
		// row
		for(int i = 0; i < 3; i++){
			if(isBingo)break;
			isBingo = (card[i][0][1]*card[i][1][1]*card[i][2][1] == 1);
		}
		for(int i = 0; i < 3; i++){
			if(isBingo)break;
			isBingo = (card[0][i][1]*card[1][i][1]*card[2][i][1] == 1);
		}

		if(!isBingo){
			isBingo = (card[0][0][1]*card[1][1][1]*card[2][2][1] == 1);
		}

		if(!isBingo){
			isBingo = (card[2][0][1]*card[1][1][1]*card[0][2][1] == 1);
		}

		String result = isBingo ? "Yes" : "No";
		System.out.println(result);
	}

}


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

int tax(int x, int p)
{
  return p * (100+x) / 100;
}

int solve(int x, int y, int s)
{
  int maximum = 0;
  for(int i=1;i<s;i++)
    for(int j=i;j<s;j++)
      if(tax(x, i) + tax(x, j) == s)
	maximum = max(maximum, tax(y, i) + tax(y, j));
  return maximum;
}


int main()
{
  int X, Y, S;

  while(cin >> X >> Y >> S && X>0)
    {
      cout << solve(X, Y, S) << endl;
    }
}



Measured memory_bytes: 3084
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <queue>
using namespace std;
#define SZ(v) ((int)(v).size())
#define SQR(x) ((x) * (x))
const int maxint = -1u>>1;
typedef long long lint;

struct P {
    int x, y;
    void input() {
        scanf("%d%d", &x, &y);
    }
    lint dist(const P &a) const {
        return SQR(lint(a.x - x)) + SQR(lint(a.y - y));
    }
};

const int maxn = 100000 + 100;
int n1, n2, r;
map<pair<int, int>, vector<P> > mm;
P p1[maxn], p2[maxn];

pair<int, int> calc_pos(const P &pt) {
    int x = pt.x / (r * 4), y = pt.y / (r * 4);
    return make_pair(x, y);
}
int main() {
    while (scanf("%d%d%d", &n1, &n2, &r) && (n1 + n2)) {
        for (int i = 0; i < n1; ++i) {
            p1[i].input();
        }
        mm.clear();
        for (int j = 0; j < n2; ++j) {
            p2[j].input();
            pair<int, int> pos = calc_pos(p2[j]);
            mm[pos].push_back(p2[j]);
        }
        
        lint ans = 0;
        for (int i = 0; i < n1; ++i) {
            pair<int, int> pos = calc_pos(p1[i]);
            for (int dx = -1; dx <= 1; ++dx) {
                for (int dy = -1; dy <= 1; ++dy) {
                    pair<int, int> p = make_pair(pos.first + dx, pos.second + dy);
                    if (mm.find(p) == mm.end()) continue;
                    const vector<P> &v = mm[p];
                    for (int k = 0; k < SZ(v); ++k) {
                        if (p1[i].dist(v[k]) <= SQR(4 * r)) {
                            ++ans;
                        }
                    }
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Measured memory_bytes: 5904
#include<stdio.h>
int main(){
  int i=0,j=0,v,N=15,k=0,l;
  int A[125];

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
     }
  for(i=0;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1] = v;

    for(l=0;l<N;++l){
      if(l!=N-1){
      printf("%d",A[l]);
      printf(" ");}
      if(l==N-1&&i!=N-1){
        printf("%d",A[l]);
      }
      if(l==N-1&&i==N-1){
        printf("%d",A[l]);
      }

    }
    printf("\n");
  }

  return 0;
}








Measured memory_bytes: 2144
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main() {
	int t;
	cin >> t;
	rep(i, 0, t) {
		int n, m, a, b;
		cin >> n >> m >> a >> b;
		printf("%lld\n", floor_sum(n, m, a, b));
	}
	return 0;
}

Measured memory_bytes: 3748
from collections import OrderedDict
number_of_music = int(input())
dict = OrderedDict()

for i in range(number_of_music):
  name,time=input().split()
  dict[name]=int(time)
  
music_name_sleep = input()

x = 0
sleeping_time=0

for key, val in dict.items():  
  if x==1:
    sleeping_time = sleeping_time + val
    
  if key == music_name_sleep:
    x=1

print(sleeping_time)

Measured memory_bytes: 3444
#include "stdio.h"

int main(int argc, char const *argv[])
{
	int i,count;
	int a,b,c,A,B,C;
	scanf("%d",&count);
	for(i=0;i<count;i++){
		scanf("%d %d %d",&a,&b,&c);
		A = a*a;
		B = b*b;
		C = c*c;
		if(A==B+C||B==C+A||C==A+B) printf("YES\n");
		else	printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <stdio.h>

int main(void)
{
	int n,a,b,i=1,rest,sum=0,ans=0;
	scanf("%d%d%d",&n,&a,&b);
	while(i <= n)
		{
		sum = i / 10000;
		rest = i % 10000;
		sum += rest / 1000;
		rest = rest % 1000;
		sum += rest / 100;
		rest = rest % 100;
		sum += rest / 10;
		rest = rest % 10;
		sum += rest;
		if(sum >= a && sum <= b)
			{ans += i;}
		i++;
		}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 128
from collections import defaultdict


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    weights = defaultdict(int)
    for _ in range(N - 1):
        u, v, w = list(map(int, input().split(' ')))
        u -= 1
        v -= 1
        adj_nodes[u].append(v)
        adj_nodes[v].append(u)
        weights[(u, v)] = w
        weights[(v, u)] = w
    # calculate distance from node 0
    frontier = [0]
    dist = [0 for _ in range(N)]
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        node = frontier.pop()
        explored[node] = 1
        for next_node in adj_nodes[node]:
            if explored[next_node] == 1:
                continue
            frontier.append(next_node)
            dist[next_node] = dist[node] + weights[(node, next_node)]
    # color: 0 = dist is even / 1 = dist is odd
    for node in range(N):
        print(dist[node] % 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 65388
#include<iostream>
#include<string>
#define last(X) X[X.length()-1]
using namespace std;

int main(void){
	string a,b,c;
	cin >> a >> b >> c;
	if((last(a) == b[0]) && (last(b) == c[0]))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	
	return 0;
}

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

int main()
{
	int n, a, b, c, t = 0;

	cin >> n;

	cin >> a >> b;

	if (n == 2) {
		if (a == b)
			t = 1;
		else
			t = 0;
	}
	else {
		for (int i = 0; i < n - 2; i++) {
			cin >> c;

			if (a == b) {
				t++;
				a = b + n;
			}
			else if (i == n - 3 && b == c)
				t++;
			else
				a = b;

			b = c;
		}
	}

	cout << t << endl;

	return 0;
}

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

int main() {
  int A , B , C ;
  cin >> A >> B >> C  ;
  if((A==B && A!=C)||(A==C && A!=B) || (B==C && B!=A)){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
/**
 * Author: hotaruijika
 * Created: 2018.09.15 19:11:07
 */
#include <bits/stdc++.h>
using namespace std;

int n, x;
int a[111];

int main() {
	cin >> n >> x;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1);
	int cnt = 0;
	for (int i = 1; i <= n && x > 0; ++i) {
		if (x >= a[i]) cnt++; 
		x -= min(x, a[i]);
	}
	if (x > 0) cnt--;
	cout << cnt << "\n";
	return 0;
}

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

int main() {
  int N, Y;
  cin >> N >> Y;
  
  bool t=false;
  int a, b, c;
  for (int i=0; i<=N;i++){
  	for(int j=0; j<=N-i; j++){
     if (10000*i+5000*j+1000*(N-j-i)==Y) {
       t=true;
       a=i;
       b=j;
       c=N-i-j;
       break;
     }
    }
  }
  if (t==true) cout << a << " " <<b <<" " << c <<endl;
  else cout << -1 <<" " << -1 << " " <<-1 <<endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d,l,r;
	cin >> a >> b >> c >> d;
	l=a+b;
	r=c+d;
	if(l>r){
		cout << "Left";
	}else if(r>l){
		cout << "Right";
	}else{
		cout << "Balanced";
	}
	return 0;
}

Measured memory_bytes: 256
from functools import reduce

def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)


if __name__ == '__main__':
    t = [int(input()) for _ in range(int(input()))]
    print(reduce(lambda x, y: lcm(x, y), t))

Measured memory_bytes: 3572
s = input()
n = len(s)
ans = 1000000000
keep = 0

for i in range(n):
    check = 0
    keep = 0
    for j in range(n):
        if s[i] != s[j]:
            check += 1
        else:
            check = 0
        keep = max(check, keep)
    ans = min(ans, keep)
print(ans)


Measured memory_bytes: 8996
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;

map<ll, int> primeFactor(ll n) {
  map<ll, int> ret;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

int main() {
  //
  ll n, p;
  cin >> n >> p;
  map<ll, int> primes = primeFactor(p);
  ll ans = 1;
  for (auto& p : primes) {
    if (p.second >= n) {
      int f = p.second / n;
      while (f > 0) {
        ans = ans * p.first;
        f--;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
list=input().split(" ")
n=int(list[0])
m=int(list[1])

hidari=0
migi=n+1

for i in range(m):
    list=input().split(" ")
    x=int(list[0])
    y=int(list[1])
    if x>hidari:
        hidari=x
    if y<migi:
        migi=y

#print(hidari, migi)
print(max(migi-hidari+1,0))

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
	int a,b;
	scanf("%d %d",&a,&b);
	if(a == 1)a=14;
	if(b == 1)b=14;

	if(a>b){
		printf("Alice\n");
	}else if(a<b){
		printf("Bob\n");
	}else{
		printf("Draw\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[105];
int main()
{
	int n;
	long long ans=999999999,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int j=a[1];j<=a[n];j++)
	{
		sum=0;
		for(int k=1;k<=n;k++)
		{
			sum+=(a[k]-j)*(a[k]-j);
		}
		if(sum<ans)	ans=sum;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define strall(v) (v).cbegin(),(v).cend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
//const long long INF = 1LL << 60;
 int INF = 500000;
 int MAX = 1e5+10;
 ll mod = 1e9+7;


int main(){
  int n;
  bool flag = true;
  cin >> n;
  vector<pair<ll,ll>> work(n);
  rep(i,n){
    int a,b;
    cin >> a >> b;
    work[i].second = a;
    work[i].first = b;  
  }
  sort(all(work));

  ll now_t = 0;
  for(int i=0;i<n;i++){
    if(now_t+work[i].second > work[i].first) {
      flag = false;
      break;
    }
    now_t+=work[i].second;
  }
  cout << (flag ? "Yes":"No") << endl;
}


Measured memory_bytes: 3328
#include<stdio.h>
int main(){
	int a,b,i,j;
	while(1){
		scanf("%d %d",&a,&b);
		if(a==b && a==0) break;
		for(i=0;i<a;i++){
			for(j=0;j<b;j++){
				if(i==0 || i==a-1){
					printf("#");
				}else{
					if(j==0 || j==b-1){
						printf("#");
					}else{
						printf(".");
					}
				}
			}
			printf("\n");
		}
		printf("\n");
	}
}


Measured memory_bytes: 2040
from collections import Counter
import string
MAX_N = 50

n = int(input())
cc = [Counter(input()) for _ in range(n)]

ans = ''
for c in string.ascii_lowercase:
  min_num = MAX_N
  for counter in cc:
    min_num = min(min_num,counter[c]) 
  ans += c*min_num
  
print(ans)  

Measured memory_bytes: 3768
import sys
input = sys.stdin.readline

from collections import deque
from functools import reduce
f = lambda a: (a+1) % M
g = lambda a, b: a * b % M
init = 1

N, M = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
T = []
while Q:
    i = deque.popleft(Q)
    T.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [0] * N # Bottom Up
TD = [1] * N # Top Down
for i in T[::-1]:
    BU[i] = reduce(g, [f(BU[j]) for j in X[i]]) if len(X[i]) else init

for i in T:
    B = [1] * (len(X[i]) + 1)
    for k, j in enumerate(X[i]):
        B[k+1] = g(B[k], f(BU[j]))
    a = init
    for k in range(len(X[i]))[::-1]:
        j = X[i][k]
        TD[j] = f(g(TD[i], g(a, B[k])))
        a = g(a, f(BU[j]))

for t in [g(a, b) for a, b in zip(BU, TD)]:
    print(t)

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

typedef long long int int64;

int64 length[51];
int64 cnt[51];

int64 calc(int64 level,int64 *x){
  if(*x==0) return 0;
  if(*x>=length[level]){
    *x-=length[level];
    return cnt[level];
  }
  int64 res=0;
  (*x)--;
  res+=calc(level-1,x);
  if(*x<=0) return res;
  (*x)--;
  res++;
  res+=calc(level-1,x);
  if(*x<=0) return res;
  (*x)--;
  return res;
}

void run(void){
  int n;
  int64 x;
  scanf("%d%lld",&n,&x);
  length[0]=cnt[0]=1;
  int i;
  for(i=1;i<=n;i++){
    length[i]=2*length[i-1]+3;
    cnt[i]=2*cnt[i-1]+1;
  }
  int64 ans=calc(n,&x);
  printf("%lld\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
map<int,int>M;

int main(){
	cin>>n;
	rep(i,n){
		int a; cin >> a; M[a]++;
	}
	int ans = 0;
	for(auto a:M){
		int x = a.fi, y = a.sc;//cout<<x<<" "<<y<<endl;
		if(x <= y) ans += y-x;
		else ans += y;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4736
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
static const int MAX_N = 1000;
static const int MAX_M = 100000;

int n, m, h, k;
pair<int, int> p[MAX_M];
int s[MAX_N];
int a[MAX_N];
int b[MAX_N];
set<int> seta[MAX_N];

int main(){
	for(;;){
		scanf("%d %d %d %d", &n, &m, &h, &k);
		if(n == 0 && m == 0 && h == 0 && k == 0) break;
		k--;
		for(int i = 0; i < n; i++) scanf("%d", &s[i]);
		for(int i = 0; i < m; i++){
			scanf("%d %d", &p[i].second, &p[i].first);
			p[i].second--;
		}
		sort(p, p + m);
		for(int i = 0; i < n; i++) a[i] = i;
		for(int i = 0; i < m; i++){
			if(a[p[i].second] <= k && a[p[i].second + 1] > k) seta[a[p[i].second]].insert(a[p[i].second + 1]);
			if(a[p[i].second] > k && a[p[i].second + 1] <= k) seta[a[p[i].second + 1]].insert(a[p[i].second]);
			swap(a[p[i].second], a[p[i].second + 1]);
		}
		int res = 0;
		for(int i = 0; i < n; i++) b[a[i]] = i;
		for(int i = 0; i <= k; i++) res += s[b[i]];
		int max_diff = 0;
		for(int i = 0; i <= k; i++){
			set<int>::iterator itr;
			for(itr = seta[i].begin(); itr != seta[i].end(); itr++){
				max_diff = max(max_diff, s[b[i]] - s[b[*itr]]);
			}
		}
		res -= max_diff;
		printf("%d\n", res);
		for(int i = 0; i < n; i++) seta[i].clear();
	}
	return 0;
}


Measured memory_bytes: 3504
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

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<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:
  using T = ll;
  vector<T> A;
  vector<T> dpF;
  vector<T> dpG;
  int N;
  T K;
  Tmp(int N, T K)
    : A(N)
    , dpF(65, -1)
    , dpG(65, -1)
    , N(N)
    , K(K)
  {}
  T operator() () {
    return recF(64);
  }
  T recF(int n) {
    if (n == 0) {
      return dpF[n] = 0;
    }
    if (dpF[n] != -1) {
      return dpF[n];
    }
    T ret0{}, ret1{};

    T k = 1L << (n-1);
    for (int i = 0; i < N; ++i) {
      ret0 += (A[i] & k);
      ret1 += (A[i] & k) ^ k;
    }

    if ((k & K) != 0) {
      return dpF[n] = std::max(
        (ret0 + std::max(recF(n-1), recG(n-1))),
        (ret1 + recF(n-1))
      );
    } else {
      return dpF[n] = ret0 + recF(n-1);
    }
  }

  T recG(int n) {
    if (n == 0) {
      return dpG[n] = 0;
    }
    if (dpG[n] != -1) {
      return dpG[n];
    }
    T ret0{}, ret1{};

    T k = 1L << (n-1);
    for (int i = 0; i < N; ++i) {
      ret0 += (A[i] & k);
      ret1 += (A[i] & k) ^ k;
    }
    return dpG[n] = std::max(ret0, ret1) + recG(n-1);
  }
};

void solve(void)
{
  int N; cin >> N;
  ull K; cin >> K;
  Tmp t(N, K);
  for (auto& a : t.A) {
    cin >> a;
  }
  auto ans = t();
  cout << ans << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=10100;
char ss[N];
string s;
int k,mark[N];
ll solve(string s) {
	int n=SZ(s);
	rep(i,0,n) mark[i]=0;
	int cnt=0;
	rep(i,0,n) {
		if (i!=0&&!mark[i-1]&&s[i]==s[i-1]) {
			mark[i]=1;
			cnt++;
		}
	}
	return cnt;
}

int main() {
	scanf("%s",ss);
	s=ss;
	scanf("%d",&k);
	if (k<=10) {
		string t;
		rep(i,0,k) t+=s;
		printf("%lld\n",solve(t));
	} else {
		string t1,t2;
		int lv=(k-5)%2+5;
		rep(i,0,lv) t1+=s;
		t2=t1+s+s;
		printf("%lld\n",solve(t1)+(solve(t2)-solve(t1))*(k-lv)/2);
	}
}


Measured memory_bytes: 256
import java.io.*;

class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    String line, str;
    int m, h;
    while(true){
      line = br.readLine();
      if (line.equals("-")) {break;}
      m = Integer.parseInt(br.readLine());
      for (int i = 0; i < m; i++){
        h = Integer.parseInt(br.readLine());
        str = line.substring(0,h);
        line = line.substring(h, line.length()) + str;
      }
    sb.append(line).append("\n");
    }
    System.out.print(sb);
  }
}

Measured memory_bytes: 24392
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;

int main() {
	ll n,k;
	cin >> n >> k;
	vector<pair<ll,ll> > sushi(n);
	for(int i = 0; i < n; i++) {
		cin >> sushi[i].second >> sushi[i].first;
	}
	sort(sushi.begin(),sushi.end());
	reverse(sushi.begin(),sushi.end());

	vector<ll> appeared(n+1);
	priority_queue<ll> new_type;
	stack<ll> old_stack;
	ll temp_sum = 0;
	ll types = 0;
	for(int i = 0; i < n; i++) {
		ll num = sushi[i].first;
		ll type = sushi[i].second;
		if(appeared[type]==0) {
			if(i>=k) {
				new_type.push(num);
			}
			else {
				types++;
			}
		}else {
			if(i<k) {
				old_stack.push(num);
			}
		}
		appeared[type]++;
		if(i<k) {
			temp_sum+=num;
		}
	}

	ll ans = temp_sum+types*types;
	for(int loop = k; loop < n; loop++) {
		//cout << temp_sum << "," << types << endl;
		if(old_stack.size()>0&&new_type.size()>0) {
			ll out = old_stack.top(); old_stack.pop();
			ll in = new_type.top();	new_type.pop();
			temp_sum -= out;
			temp_sum += in;
			types++;
			ans = max(ans,temp_sum+types*types);
		}else break;
	}

	cout << ans << endl;
}


Measured memory_bytes: 3200
require 'set'
s = gets.strip
targets = Set['A', 'C', 'G', 'T']

longest = 0
current = 0
s.split('').each do |s|
  if targets.include?(s)
    current += 1
  else
    longest = [longest, current].max
    current = 0
  end
end
puts [longest, current].max

Measured memory_bytes: 1916