akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n, k = map(int, input().split())
hp_list = list(map(int, input().split()))

if n < k:
    print(0)
    exit()

# ソートする
hp_list.sort()

# 必殺技の回数ぶん除去
for i in range(k):
    hp_list.pop()

sum_hp = 0
for hp in hp_list:
    sum_hp += hp

print(sum_hp)




Measured memory_bytes: 87372
#ifndef CLion
//#pragma GCC optimize ("O3")
#endif

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

#define F first
#define S second
#define pb push_back
#define ll long long
#define all(x) x.begin() , x.end()
#define rep(i,s,e) for (int i = s; i < e; ++i)
#define rev(i,s,e) for (int i = s; i > e; --i)
#define mem(a,v) memset(a , v , sizeof a)
//#define mod(x,m) ((x%m + m)%m)
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;

const int N = 2e5 + 99 , mod = 1e9 + 7;

int s;
ll add( ll x , ll y ){
    ll ret = x + y;
    while ( ret >= mod ) ret -= mod;
    while ( ret <  0   ) ret -= mod;
    return ret;
}

ll dp[N];
ll go( int rem ){
    if ( rem <  0 ) return 0;
    if ( rem == 0 ) return 1;
    ll &ret = dp[rem];
    if ( ~ret ) return ret;
    ret = 0;
    for ( int i = 3; rem - i >= 0; ++i )
        ret = add(ret , go(rem - i));
    return ret;
}

void Main(int cse , bool last){
    int s;
    cin >> s;
    mem(dp , - 1);
    cout << go(s);
}

int main(){

#ifndef CLion
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
#ifdef CLion
    freopen( "in.txt" , "r" , stdin  );
//    freopen( "out.txt", "w" , stdout );
    clock_t st = clock();
#endif

    int t = 1;
//    cin >> t;
    for ( int cse = 1; cse <= t; ++cse ) Main(cse, cse == t);

#ifdef CLion
    clock_t en = clock();
    cout << "\n\nTime: " << fixed << (en - st - 0.0) / CLOCKS_PER_SEC;
#endif
    return 0;
}

Measured memory_bytes: 5212
#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>;

// https://atcoder.jp/contests/abc122/tasks/abc122_b

int f(string s) {
  int cnt = 0;
  int length = s.size();
  for(int i = 0; i < length; i++) {
    int rest = length - i;
    for(int j = 1; j <= rest; j++) {
      string str = s.substr(i, j);

      bool is_acgt = true;
      for(auto c : str) {
        if(c == 'A' || c == 'C' || c == 'G' || c == 'T') continue;
        is_acgt = false;
      }
      if(is_acgt) {
        cnt = max(cnt, j);
      }
    }
  }
  return cnt;
}

int main() {
  string s;
  cin >> s;

  cout << f(s) << endl;

  return 0;
}

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


ans = 1

if n > 1:

    count = 0
    least = pn[0]

    for i in range(1,n):
    
        if least > pn[i] :
            least = pn[i]
            count +=1

    ans += count

print(ans)

Measured memory_bytes: 26516
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;

int n,q;
int sc[2000001];
int data[2000001];
int data2[2000001],data2_cnt[2000001],cnt2;

struct leader{
	int s;
	int n;
};

bool comp(const leader& l1,const leader& l2){
	return l1.s<l2.s;
};

int l_flag[2000001],l_num;

leader l[2000001];

bool check(int range,int x){
	int cnt=0;
	int r=0;
	for(int i=0;i<l_num;i++){
		if(l_flag[l[i].n]==1){
			int nl=lower_bound(data2,data2+cnt2,l[i].s-range)-data2;
			int nr=lower_bound(data2,data2+cnt2,l[i].s)-data2;
			if(nl>r)cnt+=data2_cnt[nl-1]-data2_cnt[r];
			r=nr;
		}
	}
	cnt+=n-data2_cnt[r];
	if(cnt>x)return false;
	return true;
}

int query(int x){
	int l=-1,r=1200000001;
	for(int i=0;i<150;i++){
		int mid=(l+r)/2;
		if(check(mid,x))r=mid;
		else l=mid;
	}
	return r;
}

int main(void){
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++){
		scanf("%d",&sc[i]);
		data[i]=sc[i];
	}
	sort(data,data+n);
	data2[0]=-1;
	for(int i=0;i<n;i++){
		if(data2[cnt2]==data[i])data2_cnt[cnt2]++;
		else{
			cnt2++;
			data2_cnt[cnt2]=data2_cnt[cnt2-1]+1;
			data2[cnt2]=data[i];
		}
	}
	//for(int i=0;i<=n;i++)printf("%d%c",data2[i],i==n?'\n':' ');
	//for(int i=0;i<=n;i++)printf("%d%c",data2_cnt[i],i==n?'\n':' ');
	for(int i=0;i<q;i++){
		string s;
		int x;
		cin >> s >> x;
		if(s[0]=='A'){
			x--;
			l_flag[x]=1;
			l[l_num].n=x;
			l[l_num].s=sc[x];
			l_num++;
			sort(l,l+l_num,comp);
		}
		if(s[0]=='R'){
			x--;
			l_flag[x]=0;
		}
		if(s[0]=='C'){
			int ans=query(x);
			if(ans==1200000001)printf("NA\n");
			else printf("%d\n",ans);
		}
	}
	return 0;
}

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

signed main(){
	int n,sum=0,x;
	cin>>n>>x;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int ans=1e16;
	for(int i=0;i<=n-x;i++){
		ans=min(ans,a[i+x-1]-a[i]);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;

// 基本的な演算
namespace BasicMath {
    // 二つの値の最大値を求める関数
    static Int Max(const Int a, const Int b);
    // 三つの値の最大値を求める関数
    static Int Max(const Int a, const Int b, const Int c);
    // 二つの値の最大値を求める関数
    Int Max(const Int a, const Int b) {
        if (a >= b) {
            return a;
        } else {
            return b;
        }
    }
    // 三つの値の最大値を求める関数
    Int Max(const Int a, const Int b, const Int c) {
        return Max(a, Max(b, c));
    }
}
using namespace BasicMath;

int main(void) {
    Int a, b, c;
    cin >> a >> b >> c;
    cout  << a + b + c - Max(a, b, c) << endl;
    return 0;
}



Measured memory_bytes: 3552
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - Good Sequence
            int n = int.Parse(Console.ReadLine());
            var dic = GetNumbers();

            long count = 0;

            foreach(var num in dic.Keys)
            {
                if (num > dic[num])
                {
                    count += dic[num];   
                }
                else if (num < dic[num])
                {
                    int diff = dic[num] - num;
                    count += diff;
                }
            }

            Console.WriteLine(count);
        }

        static Dictionary<int,int> GetNumbers()
        {
            var line = Console.ReadLine();
            var array = line.Split(' ');

            var dic = new Dictionary<int, int>();

            foreach(var s in array)
            {
                int num = int.Parse(s);

                if (dic.ContainsKey(num))
                {
                    dic[num]++;
                }
                else
                {
                    dic.Add(num, 1);
                }
            }

            return dic;
        }
    }
}

Measured memory_bytes: 24796
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))

    n = max(A)
    a = -1
    d = n
    for e in A:
        if e == n:
            continue
        if abs(e - n/2) < d:
            a = e
            d = abs(e - n/2)
    
    print(n, a)


if __name__ == '__main__':
    main()

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

inline int read(){
	re int ans = 0;re bool f = 1;re char ch = getchar();
	while(ch<'0'||ch>'9'){if (ch=='-')f = 0;ch = getchar();}
	while(ch>='0'&&ch<='9'){
		ans = (ans<<3)+(ans<<1)+(ch^48);
		ch = getchar();
	}
	return f?ans:~(ans-1);
}
signed main(void){
	int n=read();
	queue<int>q;
	for(re int i=1;i<=9;++i)q.push(i);
	for(re int i=1;i<n;++i){
		int x = q.front();q.pop();
		int fis = x%10;
		x*=10;
		if(fis!=0)q.push(x+fis-1);
		q.push(x+fis);
		if(fis!=9)q.push(x+fis+1);
	}
	printf("%lld\n",q.front());
	return 0;
}
/*
暴力好像可以,看下最大,34亿,溜了溜了,就算2s时限也绝对T

?构造搞一下?

好像可以,推推性质

1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10
11	12	21	22	23	32	33	34	43	44
11	12	13	14	15	16	17	18	19	20
45	54	55	56	65	66	67	76	77	78
21	22	23	24	25	26	27	28	29	30
87	88	89	98	99	100	101	110	111	112
31	32	33	34	35	36	37	38	39	40
121	122	123	210	211	212	221	222	223	232
41	42	43	44	45	46	47	48	49	50
234	321 322 323 332 333 334 343 344 345
51	52	53	54	55	56	57	58	59	60
…………
789	876	877	878	887	888	889	898	899	987
100 101 102 103 104 105 106 107 108 109
988	989	998	999	1000
110 111	112	113	114

这样推测到114是4位数,36是3位数

……没得规律啊,蒟……

*/

Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    string a,b;cin>>a>>b;
    a +=b;
    int num = atoi(a.c_str());
    REP(i,500){
        int p = num%i, q = num/i;
        if(p == 0&& i == q){cout<<"Yes"<<endl; return 0;}
    }
    cout<<"No"<<endl; return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>
#include <map>
#include <numeric>
#include <functional>
#include <utility>

using namespace std;

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

int main(void) {
  string s;
  cin >> s;
  int m = stoi(s.substr(5, 2));
  int d = stoi(s.substr(8, 2));
  cout << (m <= 4 && d <= 30 ? "Heisei" : "TBD") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define repi(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
using namespace std;
typedef long long ll;

int main() {
  int S; cin >> S;
  int f,s;
  f = S / 100; s = S % 100;
  if (f >= 1 && f <= 12) {
    if(s >= 1 && s <= 12) puts("AMBIGUOUS");
    else puts("MMYY");
  } else {
    if(s >= 1 && s <= 12) puts("YYMM");
    else puts("NA");
  }
  return 0;
}


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

const int INF=1e9;
int main(){
    int c,n,m;
    cin>>c>>n>>m;
    vector<int> s(n),p(n);
    for(int i=0;i<n;i++) cin>>s[i]>>p[i];
    vector<vector<int>> dp(2,vector<int>(c+1,-INF));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        fill(dp[(i+1)&1].begin(),dp[(i+1)&1].end(),-INF);
        int to=(i+1)&1,fr=i&1;
        for(int j=0;j<=c;j++){
            dp[to][j]=max(dp[to][j],dp[fr][j]);
        }
        int ub=c-s[i];
        for(int j=0;j<=ub;j++){
            dp[to][j+s[i]]=max(dp[to][j+s[i]],dp[fr][j]+p[i]);
        }
    }
    vector<int> tmp=dp[n&1];
    for(int i=1;i<=c;i++){
        tmp[i]=max(tmp[i],tmp[i-1]);        
    }
    vector<int> res(m);
    for(int i=0;i<m;i++){
        res[i]=tmp[c/(i+1)]*(i+1);
    }

    for(int i=0;i<m;i++){
        cout<<res[i]<<endl;
    }

    return 0;
}


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

using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> l(N);
    rep(i, N) cin >> l[i];
    sort(l.begin(), l.end());
    int ans = 0;
    rep(i, K) {
        ans += l[N - 1 - i];
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
#include<utility>
#include<vector>
#include<climits>
#include<queue>
#include<random>

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

using namespace std;

int main(int argc, char const *argv[]) {

    int n,i;
    cin >> n >> i;
    cout << n-i+1 << endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.PrintWriter
import java.util.*

val pw = PrintWriter(System.out)
val DIVIDER: Long = (1e+9 + 7).toLong()
fun main(args: Array<String>) {
    val (n, m) = readListOfInt()
    val floors: MutableList<Long> = (0L..(n+1).toLong()).toMutableList()
    for(i in 0 until(n+1)) {
        floors[i] = 0L
    }
    for(i in 0 until m) {
        val a = readInt() 
        floors[a] = -1L
    }

    floors[1] = if(floors[1] == -1L) 0 else 1

    if(n > 1) {
        floors[2] = if(floors[2] == -1L) 0 else floors[1] + 1L
        for(i in 3 .. n) {
            if(floors[i] == -1L) {
                floors[i] = 0L
                continue
            } 
            val one_step = floors[i-1]
            val two_step = floors[i-2]
            floors[i] = (one_step + two_step) % DIVIDER
        }
    }
    println(floors[n] % DIVIDER)

    pw.flush()
}

fun inputList() = 
    readLine()!!.split(" ").map(String::toInt)

fun sum_digits(num_: Long): Long {
    var num = num_
    var rtn: Long = 0
    while(num != 0.toLong()) {
        val tmp = num % 10
        rtn += tmp
        num /= 10
    }
    return rtn
}

/****** Decrared Functions ******/

// IO
fun read() = readLine()!!
fun readInt() = read().toInt()
fun readLong() = read().toLong()
fun readDouble() = read().toDouble()
fun readListOfString() = read().split(" ")
fun readListOfInt() = readListOfString().map { it.toInt() }
fun readListOfLong() = readListOfString().map { it.toLong() }
fun readListOfDouble() = readListOfString().map { it.toDouble() }


//fun println(value : Any) {
//    pw.println(value)
//}

fun gcd(a: Long, b: Long): Long = 
    if(b != 0L) a else gcd(b, a % b)

fun lcm(a: Long, b: Long) = 
    if(b==0L) a else gcd(b, a % b)


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

using namespace std;
typedef long long ll;
int main(){

    int s;
    cin>>s;

    string ans = "";
    while(s!=0){
        if(s%2!=0){
            s--;
            ans='1'+ans;
        }else
            ans='0'+ans;
        
        s/=-2;
    }
    if(ans=="")
        cout<<"0";
    else
        cout<<ans;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF= 1<<29;

int dp[2][2][5005];
int N;
int t[10005];

int main(){
  scanf("%d", &N);
  for(int i=1;i<N;i++) scanf("%d", &t[i]);

  for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<5005;k++) dp[i][j][k] = INF;
  dp[0][0][0] = 0;
  int cur, tar;
  for(int i=1;i<=N;i++){
    tar = i%2,  cur = !tar;
    for(int j=0;j<2;j++){
      int u = min(i, N>>1);
      for(int k=0;k<=u;k++){
	dp[tar][0][k] = min(dp[cur][0][k], dp[cur][1][k]);
	if(0<k) dp[tar][1][k] = min(dp[cur][0][k-1] + t[i-1] + t[i], dp[cur][1][k-1] - t[i-1] + t[i]);
      }
    }
  }
  printf("%d\n", min(dp[tar][0][N/2], dp[tar][1][N/2]));
  return 0;
}

Measured memory_bytes: 1144
// A.

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
	long long n, k, x, y, ans;
	cin >> n >> k >> x >> y;
	ans = x * min(n, k) + y * max(0LL, n - k);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<queue>
#include<list>
#include<stdio.h>
#include<stdlib.h>
#include<map>
#include<cstdio>
#include <iomanip>

#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

typedef long long ll;

using namespace std;



int main() {
	
	string s;
	ll k;
	cin >> s>>k;

	for (int i = 0; i < k; i++) {
		if (s[i] != '1') {
			cout << s[i] << endl;
			return 0;
		}
	}

	cout << '1' << endl;

	return 0;

}


Measured memory_bytes: 256
import numpy as np
n,m= (int(i) for i in input().split())
ans =np.zeros(n,dtype=int)
for i in range(m):
 a,b= (int(i) for i in input().split())
 ans[a-1] += 1
 ans[b-1] += 1
for j in ans:
 print(j)

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

int main() {
  int a[] = {0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
  int x, y;
  scanf("%d%d", &x, &y);
  cout << (a[x]==a[y]? "Yes" : "No") << endl;
  return 0;  
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)
#define mp(a, b) make_pair(a, b)

template<typename T, typename Compare = greater<T> >
inline void chmax(T& t, T f, Compare comp){if(!comp(t, f))t = f;}

int h, w;

inline int add(int a, int b, int mod){
    int t = a + b;
    return t < mod? t < 0? mod + t: t: t - mod;
}

string solve(vector<string>& patterns){
    string res = "0";
    set<string> spells;
    rep(x, h)rep(y, w){
        for(int dx=-1; dx<=1; ++dx){
            for(int dy=-1; dy<=1; ++dy){
                string spell = "";  spell += patterns[x][y];
                for(int nx=add(x, dx, h), ny=add(y, dy, w); nx!=x || ny!=y; nx=add(nx, dx, h), ny=add(ny, dy, w)){
                    spell += patterns[nx][ny];
                    if(!spells.insert(spell).second){
                        chmax(res, spell, [](string& s, string& t){return mp(t.size(), s) < mp(s.size(), t);});
                    }
                }
            }
        }
    }
    return res;
}

int main(){
    while(cin >> h >> w, h|w){
        vector<string> patterns(h);
        rep(i, h)cin >> patterns[i];
        cout << solve(patterns) << '\n';
    }
    return 0;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int memo[1000][1000];

void solve(long long H, long long W, std::vector<std::string> A){
    vector<PII> now, next;
    REP(i, H) REP(j, W) {
        if(A[i][j] == '#') now.PB(MP(i, j));
    }

    int cnt = -1;
    while(!now.empty()){
        cnt++;

        REP(i, now.size()){
            REP(j, 4) {
                int mx = now[i].second + DX[j];
                int my = now[i].first + DY[j];
                if(RANGE(mx, my, W, H) && A[my][mx] == '.') {
                    next.PB(MP(my, mx));
                    A[my][mx] = '#';
                }
            }
        }
        now = next;
        next.clear();
    }

    cout << cnt << endl;
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    std::vector<std::string> A(H);
    for(int i = 0 ; i < H ; i++){
        std::cin >> A[i];
    }
    solve(H, W, std::move(A));
    return 0;
}


Measured memory_bytes: 13544
#include<stdio.h>
#include<string.h>
int main(){
char str[10000];
scanf("%s",str);
int len=strlen(str);
char str1[len+1];
int j=0;
for(;j<=len-1;j++){
  str1[j]=str[len-1-j];
  }
  str1[len]='\0';
  printf("%s\n",str1);
  return 0;
  }

Measured memory_bytes: 524
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
f=lambda:map(int,input().split())
N,K,L=f()
uf_road=UnionFind(N+1)
uf_rail=UnionFind(N+1)
for _ in [0]*K:
    uf_road.unite(*f())
for _ in [0]*L:
    uf_rail.unite(*f())

from bisect import bisect_left as bl
from bisect import bisect_right as br
    
roots=[(uf_road.find_root(i),uf_rail.find_root(i)) for i in range(1,N+1)]
sorted_roots=sorted(roots)

res=[]
for n in range(N):
    res.append(br(sorted_roots,roots[n])-bl(sorted_roots,roots[n]))
print(*res)

Measured memory_bytes: 114860
#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() {
    int h, n;
    cin >> h >> n;
    ll tot = 0;
    rep(i,n) {
        int a;
        cin >> a;
        tot += a;
    }
    if (h <= tot) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 256
n=int(input())
lst=[]
for i in range(n):
    lst.append(int(input())-1)
ans=1
if lst[0]==1:
    print(ans)
    exit()
else:
    button=lst[0]
    lst[0]=None

while True:
    p=button
    button=lst[button]
    ans+=1
    if button==1:
        print(ans)
        break
    elif button==None:
        print(-1)
        break
    lst[p]=None

Measured memory_bytes: 81296
N = int(input())
A = list(map(int, input().split()))
left = 0
right = sum(A)
diff = abs(left - right)
for i in range(N):
    left += A[i]
    right -= A[i]
    if abs(left - right) < diff:
        diff = abs(left - right)
print(diff)


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

int main() {
	int n;
	while (1) {
		int sum = 0;
		cin >> n;
		if (n == 0) break;

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

		sort(a.begin(),a.end());
		for (int i = 1; i < n-1; i++) sum += a[i];
		cout << sum / (n-2) << endl;

	}
}


Measured memory_bytes: 3100
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main () {
    int n, m;
    while (cin >> n >> m, n | m) {
        vector<pair<int, int> > dp;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            int d, p;
            cin >> d >> p;
            dp.push_back(make_pair(d, p));
            sum += d * p;
        }

        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) {
                if (dp[j].second > dp[j-1].second
                    || (dp[j].second == dp[j-1].second && dp[j].first < dp[j-1].first)) {
                    swap(dp[j], dp[j-1]);
                }
            }
        }

        int i = 0;
        while (m > 0 && i < n) {
            if (m >= dp[i].first) {
                m -= dp[i].first;
                i++;
            } else {
                dp[i].first -= m;
                break;
            }
        }

        int result = 0;
        for ( ; i < n; i++) {
            result += dp[i].first * dp[i].second;
        }
        cout << result << endl;
    }
}

Measured memory_bytes: 1324
use std::io::*;
use std::str::*;

// const MOD: i32 = 1000000007;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let a: usize = read().unwrap();
    let b: usize = read().unwrap();
    let c: usize = read().unwrap();
    if a + b >= c {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll N;
ll A[20], B[20];
ll dp[(1<<20)+10][20][2];

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

  rep( i, N )
    std::cin >> A[i];

  rep( i, N )
    std::cin >> B[i];

  rep( i, 1<<N ) rep( j, N ) rep( k, 2 )
    dp[i][j][k] = INF;

  rep( i, N )
    dp[1<<i][i][!(i&1)] = i;

  repi( i, 1, 1<<N ) rep( j, N ) rep( k, 2 )
  {
    ll pos = __builtin_popcount(i)-1;
    ll cnt = 0;

    rep( l, N ) if( !(i>>l&1) )
    {
      ll diff = cnt;
      ll moved = __builtin_popcount(i>>l)+diff;

      if( (k?A[j]:B[j]) <= (moved&1?B:A)[l] )
        chmin( dp[i|1<<l][l][!(moved&1)], dp[i][j][k]+diff );

      ++cnt;
    }
  }

  ll ans = INF;

  rep( j, N ) rep( k, 2 )
  {
    chmin( ans, dp[(1<<N)-1][j][k] );

    //printf( "dp[%lld][%lld] = %lld\n", j, k, dp[(1<<N)-1][j][k] );
  }

  std::cout << (ans==INF?-1:ans) << std::endl;

  return 0;
}

Measured memory_bytes: 84224
#include<bits/stdc++.h>
#include<math.h>
#include<queue>
#include<cstdio>
#include<set>
#include<map>
using namespace std;
using ll = long long;

int main(){
    int N;
  	cin >> N;
    vector<string> S(N);
    int ac=0;
  	int wa=0;
  	int tle=0;
  	int re=0;
  	
    for(int i=0; i<N; i++){
        cin >> S.at(i);
        if(S.at(i)=="AC") ac=ac+1;
        if(S.at(i)=="WA") wa++;
        if(S.at(i)=="TLE") tle++;
        if(S.at(i)=="RE") re++;
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl; 
    cout << "TLE x " << tle << endl; 
    cout << "RE x " << re << endl; 
    return 0;
}

Measured memory_bytes: 6360
Infinity = 1000000

def floydwarshall graph
  n = graph.size
  dist = Array.new(n).map{Array.new(n, Infinity)}
  n.times do |i|
    dist[i][i] = 0
  end
  n.times do |i|
    graph[i].each do |edge|
      dist[i][edge] = 1
    end
  end

  n.times do |k|
    n.times do |u|
      n.times do |v|
        newPop = dist[u][k] + dist[k][v]
        if newPop < dist[u][v]
          dist[u][v] = newPop
        end
      end
    end
  end
  dist
end

#ネットワーク取得
n = $stdin.gets.to_i
graph = Array.new(n).map{Array.new}
n.times do
  input = $stdin.gets.split(" ").map(&:to_i)
  input[1].times do |t|
    graph[input[0] - 1] << input[t + 2] - 1
  end
end

dist = floydwarshall graph

#パケット処理
$stdin.gets.to_i.times do
  s, d, v = $stdin.gets.split(" ").map(&:to_i)
  if dist[s - 1][d - 1] + 1 <= v
    puts dist[s - 1][d - 1] + 1
  else
    puts "NA"
  end
end

Measured memory_bytes: 6148
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()
    val = 2**31-1

    A, S, i = [], [],  N
    while i > 1:
        i += i & 1
        A.append([val] * i)
        i >>= 1
    A.append([val])
    la = len(A)

    def update(i, x):
        i0 = i
        x0 = A[0][i]
        diff = x0 - x
        if diff == 0:
            return
        A[0][i] = x
        if diff > 0:
            for j in range(1, la):
                i, i0 = i >> 1, i
                y = A[j][i]
                if x >= y:
                    break
                A[j][i] = x
            return

        for j in range(0, la-1):
            y = A[j][i^1]
            if x >= y:
                x = y
            i >>= 1
            if A[j+1][i] == x:
                break
            A[j+1][i] = x


    def find(s, t):
        i, ans = 0, val
        while t - s > 1:
            if s & 1:
                ans = min(ans, A[i][s])
                s += 1
            if t & 1 == 0:
                ans = min(ans, A[i][t])
                t -= 1
            s, t , i= s // 2, t // 2, i + 1
            #print(s, t)

        return min(A[i][s], A[i][t], ans)


    for com, *arg in (map(int, line.split()) for line in sys.stdin):
        if com == 0:
            update(*arg)
        else:
            #for i,a in enumerate(A):
            #    print("*", " "*i*2,  *a)
            #print(*arg)
            res = find(*arg)
            print(res)

if __name__ == "__main__":
    resolve()



Measured memory_bytes: 9064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[1000001];
int gcd(int a,int b)
{ return __gcd(a,b);}
int main()
{
	ll n;
	cin >> n;
	ll x=0;
	for(int i=1;i<=n;i++)
	{for(int j=1;j<=n;j++)
		{for(int k=1;k<=n;k++)
			{ x=x+gcd(i,gcd(j,k));}}}
	cout << x << endl;
}


Measured memory_bytes: 3596
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll read() {
	ll X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

int main() {
	ll a=read(),b=read()*100+read();
  	printf("%lld\n",a*b/100);
}

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



int main() {
  string S;
  cin >> S;

  if((S.find("A") != string::npos) && (S.find("B") != string::npos)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
}


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

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var S = Console.ReadLine();

        if (N % 2 == 1)
        {
            Console.WriteLine("No");
            return;
        }

        if (S.Substring(0, N / 2) == S.Substring(N / 2, N / 2))
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11092
def main():
    n, m = map(int, input().split())
    info = []
    for _ in range(n):
        info.append(list(map(int, input().split())))
    info.sort(key=lambda x: x[0])
    answer = 0
    for a, b in info:
        if m <= 0:
            break
        answer += a * min(m, b)
        m -= min(m, b)
    print(answer)


if __name__ == '__main__':
    main()



Measured memory_bytes: 29028
fun main(args: Array<String>) {
    val (n, m) = readInputLine().split(" ").map { it.toInt() }
    val ships = mutableMapOf<Int, MutableSet<Int>>()

    for (i in 1..m) {
        val (a, b) = readInputLine().split(" ").map { it.toInt() }
        val set = ships.get(a) ?: mutableSetOf<Int>()
        set.add(b)
        ships.put(a, set)
    }

    val firstSteps = ships.get(1)

    if (firstSteps == null) {
        println("IMPOSSIBLE")
        return
    }

    for (i in firstSteps) {
        val secondSteps = ships.get(i)
        if (secondSteps == null) {
            continue
        }
        if (secondSteps.contains(n)) {
            println("POSSIBLE")
            return
        }
    }
    println("IMPOSSIBLE")
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 127112
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b) for(ll i=a;i>=b;i--)
#define endl '\n'
#define spc " "
#define pb push_back
#define mp make_pair
#define mod 1000000007b
#define pi 3.14159265358979323
#define sz(a) (int)((a).size())
#define len(a) (int)(a.length())
#define FOR(i,j,k,l) for(ll i=j;i<k;i+=l)

void Fast_IO() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   #ifndef ONLINE_JUDGE
   freopen("input.in","r",stdin);
   freopen("out.txt","w",stdout); 
   #endif
} 
vector<vector<ll> >vii;

int main(){
   //Fast_IO();
   ll n;
   cin>>n;
   cout<<n+pow(n,2)+pow(n,3)<<endl;

      
}

Measured memory_bytes: 4288
import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		n= sc.nextInt();
		int max = 1;
		Map<String,Integer> map = new TreeMap<String,Integer>();
		for (int i=0;i<n;i++) {
			String s = sc.next();
			if (map.containsKey(s)==false) {
				map.put(s, 1);
			} else {
				Integer in = map.get(s);
				in = in+1;
				if (in>max) {
					max = in;
				}
				map.put(s, in);
			}
		}
		Object[] array = map.keySet().toArray();
		Arrays.sort(array);
		for (int i=0;i<array.length;i++) {
			if (map.get(array[i])== max) {
				System.out.println(array[i]);
			}
		}
	}


}

Measured memory_bytes: 85780
#include <bits/stdc++.h>
  
#define int long long
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

const int MAX_N = 1e5+10;
vi es[MAX_N];

int d[MAX_N*3];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        es[a].pb(b);
    }
    int s, t;
    cin >> s >> t;
    --s;
    --t;
    int root = s *3;
    auto dijkstra = [&] () {
        typedef pair<int, int> P; //dist, from
        priority_queue<P, vector<P>, greater<P> > q;
        rep(i, MAX_N*3) d[i] = 1e18;
        d[root] = 0LL;
        q.push({0LL, root});
        while (!q.empty()) {
            auto p = q.top(); q.pop();
            int prv = p.se/3;
            int r = p.se%3;
            auto cost = p.fi;
            if (d[p.se] < p.fi) continue;
            for (auto& t : es[prv]) {
                auto dist = 1 + cost;
                ll to = t*3 + (r+1)%3;
                if (dist < d[to]) {
                    d[to] = dist;
                    q.push({dist, to});
                }
            }
        }
    };
    dijkstra();
    if(d[t*3] == 1e18) cout << -1 << '\n';
    else cout << d[t*3]/3 << '\n';
    // rep(i, n) {
    //     cout << d[i*3] << " " << d[i*3+1] << " " << d[i*3+2] << endl;
    // }
    return 0;
}

Measured memory_bytes: 8192
<?php


$n = trim(fgets(STDIN));

$n = str_split($n);

$changeCnt = 0;
for ($i = 0; $i < (count($n) / 2); $i++) {
    if ($n[$i] !== $n[count($n) - 1 - $i]) {
//        echo $n[$i] . PHP_EOL;
        $changeCnt++;
    }
}
echo $changeCnt . PHP_EOL;


Measured memory_bytes: 4856
#include<cstdio>

int main(void){
char s;
int i;

int m[26]={0};
char a[26],A[26];

for(i=0;i<26;i++){
	a[i]='a'+i;
	A[i]='A'+i;
};
int c;
while(scanf("%c",&s)!=EOF){
	if ((s>=a[0])&&(s<=a[0]+25)){
		c=s-a[0];
		m[c]++;
	}else if((s>=A[0])&&(s<=A[0]+25)){
		c=s-A[0];
		m[c]++;
	};
};

for(i=0;i<26;i++){
	printf("%c : %d\n",a[i],m[i]);
};

return 0;
}

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

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define ull unsigned long long
#define ld long double

#define mod 1000000007
#define EULER 2.7182818284
#define INF 1000000000

#define pb push_back
#define ins insert
#define IT iterator
#define PQ priority_queue
#define    nl           "\n"
#define fi first
#define se second
#define maxe max_element
#define mine min_element
#define er erase
#define lb lower_bound
#define ub upper_bound

#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define mpi map<int,int>
#define mpl map<ll,ll>
#define umpi unordered_map<int,int>
#define umpl unordered_map<ll,ll>
#define si set<int>
#define sl set<ll>
#define msi multi_set<int>
#define msl multi_set<ll>

#define mem(v,i) memset(v,i,sizeof(v)) // v is array. To set all elements to 0 or -1 only. mem(arr,0);


#define repab(i,a,b) for(int i=(a);i<=(b);i++)
#define reprab(i,a,b) for(int i=(a);i>=(b);i--)
#define repll(i,a,b) for(ll i=(a);i<=(b);i++)
#define rep(i,n) for(int i=(0);i<(n);i++)
#define repr(i,n) for(int i=(n);i>=0;i--)
#define bs bitset
#define bpc(a) __builtin_popcount(a)
#define tc int t;cin>>t;while(t--)




int main()
{   
    
    fast
    ll n;
    cin>>n;
    vll a(n),pre(n);
    rep(i,n)cin>>a[i];
    pre[n-1]=a[n-1];
    for(int i=n-2;i>=0;i--){
        pre[i]=pre[i+1]+a[i];
    }
    ll ans=0;
    rep(i,n){
        ll p=((a[i]%mod)*((pre[i]-a[i])%mod))%mod;
        ans=(ans+p)%mod;
    }
    cout<<ans<<nl;
    return 0;
}

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

using Weight = int;
using Capacity = int;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src_, int dst_, int weight_) :
        src(src_), dst(dst_), weight(weight_) { }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

bool operator < (const Edge &e, const Edge &f){ return e.weight > f.weight; }
pair<Weight, Edges> prim(const Graph &g, int r = 0) {
    Edges T; Weight total = 0; vector<int> vis(g.size());
    priority_queue<Edge> q;
    q.emplace(-1, r, 0);
    while (!q.empty()) {
        Edge e = q.top(); q.pop();
        if (vis[e.dst]) continue;
        vis[e.dst] = true;
        total += e.weight; if(e.src != -1) T.push_back(e);
        for(auto& f : g[e.dst]) if (!vis[f.dst]) q.push(f);
    }
    return make_pair(total, T);
}

int main(){
    int n;
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int x;
            cin >> x;
            if(x != -1) g[i].emplace_back(i,j,x);
        }
    }
    cout << prim(g).first << endl;
}

Measured memory_bytes: 3208
import java.util.Scanner;

/**
 * https://atcoder.jp/contests/abc169/submissions/14595332 を参考に作成
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			long n = scanner.nextLong();
			int sqrt = (int) Math.sqrt(n);
			int answer = 0;
			for (int i = 2; i <= sqrt; i++) {
				int count = 0;
				while (0 == (n % i)) {
					n /= i;
					count++;
				}
				for (int j = 1; count - j >= 0; j++) {
					count -= j;
					answer++;
				}
			}
			if (n > 1) {
				answer++;
			}
			System.out.println(answer);
		}
	}
}


Measured memory_bytes: 35676
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

typedef tuple<ll, ll, ll> T;
// get<K>(tuple型の変数)


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

    ll n, a, b; cin >> n >> a >> b;
    vector<ll> x(n);
    rep(i, n) cin >> x[i];
    ll ans=0;
    repr(i, 1, n){
        ll dif=x[i]-x[i-1];
        ans+=min(b, a*dif);
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define gcd(a,b) __gcd(a,b)
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcountll(x)
#define heap_min priority_queue<int,vector<int>,greater<int>>
#define heap_max priority_queue<int>
#define printv(v) for(auto p : v) cout << p << " ";
#define printa(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);

using namespace std;

int32_t main()
{
   fast;
   #ifndef ONLINE_JUDGE
   freopen("goodluckin.txt","r",stdin);
   freopen("goodluckout.txt","w",stdout);
   #endif
   

   int n;
   cin >> n;
   if(n%1000==0){
    cout << "0";
    return 0;
   }

   int k = ((n/1000)+1)*1000;
   cout << (k-n);
}


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

/*
,,,,
　　　　　　　　　　　　　　　　　　　　　　　　　　,.斗*''“i:i:{
　　　　　　　　　　　　　,.　｡. . . * : : : ''' : : : :” :”“ ''ｰ - 弋,,_
　　　　　 　 　 ,.斗*''“ : : : : : : : : : : : : : ' ' ' ' ' ' : : : : : : : : : : :”: '':* ｡ ,
　　　 ,.斗*''“ ” ＼：　　 ”・・． ' ' ' '　　　　　　　　 ' ' ' ' : : : : : : : : : : : : ”ミ*｡,,,,,,　　　　　　 　 　 　 ＿
　　く.　 ◎　 ﾞ:.ﾞ:..　ﾟ:,　:　───────────　　　--　　,,,,,,__ ' ' ' :.:.:.:.:.”≧s｡.　　＿,,,｡s*i:i:i:i:<
　　ﾏ*s｡ :,　 }　ﾟ:,　 :}　　　　　　　　　　　　　　　　　　　　　　　　　　　　”　''　-　”””：：”：：`*｡i:i:i:i:i:i:i;:’
　　　` .｡`　 ,　,ノ ／｡ ,,,_　　　　　　　　　　　　　　　　　　　　　　　　　　　　　＿＿`　　} }　　ﾉi:i:i:i:i:ﾂ
　　　　　 `　*　｡　　`*｡i:i:i::*=-　　　　　　　　　　　＿＿　　　　　　,,,....｡s*'i,:’　　　”`*｡＿,*’i:i:i:i:r’
　　　　　　　　　　　”　─ --　　　　｡｡｡｡｡　　 -　－`''''''''ヽ ─ '''”　　　｀ｰ“　　　　　　　`*｡i:i:i:i:i:i:
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`*｡i:i:::
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`*ﾟ:,
         fozubaoyou    no BUGs alive!
*/

typedef long long ll;
//{
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define dumo dump
#define sysp system("pause")
//}

#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 0

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cout<<endl;}
template<class...A> inline void debug_rest() {cout<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cout<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cout<<first,debug_rest(rest...);}
inline long long digitsum(long long v){long long d=0;while(v){d+=v%10;v/=10;}return d;};
//}

int n,sum,mv=1000;

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int dis;
		cin>>dis;
		sum+=dis;
		if(dis%10!=0)mv=min(mv,dis);
	}
	if(sum%10!=0)dump(sum);
	else if(sum%10==0&&mv==1000)dump(0);
	else dump(sum-mv);
	system("pause");
}
 

Measured memory_bytes: 504
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
d = {i:0 for i in range(n)}
for a, b in ab:
    d[a-1] += 1
    d[b-1] += 1
for i in range(n):
    print(d[i])


Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#define llint long long
#define inf 1e9

using namespace std;

llint n, m;
vector<llint> G[605], revG[605];
double dp[605], dp2[605];

void dfs(int v, int f)
{
	if(f){
		double sum = 0;
		for(int j = 0; j < G[v].size(); j++){
			sum += dp2[G[v][j]];
		}
		dp2[v] = sum / (int)G[v].size() + 1;
	}
	for(int i = 0; i < revG[v].size(); i++) dfs(revG[v][i], 1);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	llint u, v;
	for(int i = 0; i < m; i++){
		cin >> u >> v;
		G[u].push_back(v);
		revG[v].push_back(u);
	}
	
	dp[n] = 0;
	for(int i = n-1; i >= 1; i--){
		double sum = 0;
		for(int j = 0; j < G[i].size(); j++){
			sum += dp[G[i][j]];
		}
		dp[i] = sum / (int)G[i].size() + 1;
	}
	
	//for(int i = 1; i <= n; i++) cout << dp[i] << " "; cout << endl;
	
	double ans = dp[1];
	for(int i = 1; i <= n; i++){
		
		int N = G[i].size();
		if(N <= 1) continue;
	
		double mx = 0;
		for(int j = 0; j < G[i].size(); j++){
			mx = max(mx, dp[G[i][j]]);
		}
		for(int j = 1; j <= n; j++) dp2[j] = dp[j];
		dp2[i] = ((dp[i] - 1) * N - mx) / (N-1) + 1;
		
		for(int v = i-1; v >= 1; v--){
			double sum = 0;
			for(int j = 0; j < G[v].size(); j++){
				sum += dp2[G[v][j]];
			}
			dp2[v] = sum / (int)G[v].size() + 1;
		}
		
		ans = min(ans, dp2[1]);

		//for(int i = 1; i <= n; i++) cout << dp2[i] << " "; cout << endl;
		
	}
	printf("%.11f\n", ans);
	
	return 0;
}

Measured memory_bytes: 4864
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
int inf = 1000000000;

int main(void) {

  int n;
  while(cin >> n){
    if( n == 0 ) break;
    int cnt = 0;
    for(int i=n; i>= 1; i--){
      int tmp = i;
      while( tmp % 5 == 0 ){
        cnt++;
        tmp /= 5;
      }
    }
    cout << cnt << endl;
  }

  return 0;
}

// EOF

Measured memory_bytes: 3012
#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 <cmath>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

        vector<int> A(N + 1);
        rep(i, N) cin >> A[i];
        bool ok = true;
        int s = 0;

        rep(i, N) s += A[i];

        if (s % 2 == 0)
        {
                cout << "YES" << endl;
        }
        else
        {
                cout << "NO" << endl;
        }

        return 0;
}


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

int main(){
    int a,b;
    cin >> a >> b;
    if (a == b){
        cout << "a" << " == " << "b" << endl;
    }
    else if(a < b){
        cout << "a" << " < " << "b" << endl;
    }
    else if(a > b){
        cout << "a" << " > " << "b" << endl;
    }
}


Measured memory_bytes: 3100