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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

int N,A,B;
int main(){
    scanf("%d%d%d", &N,&A,&B);
    
    printf("%d %d", A<B?A:B,A+B-N<0?0:A+B-N);

    return 0;
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

// 標準入力取込
var g_input = '';
process.stdin.on('data', function(chunk) {
    g_input += chunk;
});
process.stdin.on('end', function() {
    main(g_input.split(/\r?\n/));
});

// 解答
function main(inputs){

    var input = inputs[0];
    var page  = 0;

    // 枚数計算
    page = Math.floor(input / 2);

    // ページ数が奇数の場合、1枚追加
    if (input % 2 == 1) {

        page++;
    }

    console.log(page);
}

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

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 7;

int n, m, d[N];
int ans;

vector < int > g[N];

void dfs (int v){
      d[v] = 1;
      for (int to : g[v]){
            if (!d[to])
                  dfs(to);
            d[v] = max(d[to] + 1, d[v]);

      }
      ans = max(d[v], ans);
}

main () {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++){
            int x, y;
            scanf("%d%d", &x, &y);
            g[x].pb(y);
	}
	for (int i = 1; i <= n; i++){
            if (!d[i])
                  dfs(i);
	}
	printf("%d", ans - 1);
}


Measured memory_bytes: 8192
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
    int x=0,ans=0,n ;
    scanf("%d",&n);
    char s[n] ;
    scanf ("%s",s);
    for(int i=0; i<n; i++){
        if (s[i]=='I'){
            x++;
        } else {
            x--;
        }
        if (ans<x){
            ans=x;
        }
    }
    printf ("%d\n",ans);
	return 0 ;
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
const int N = 205;
int n, v[N], a;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n; ++i)
        scanf("%d", &v[i]);
    std::sort(v + 1, v + 2 * n + 1);
    for (int i = 1; i <= 2 * n; i += 2)
        a += v[i];
    printf("%d", a);
    return 0;
}

Measured memory_bytes: 1732
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

const MOD = 10^^9 + 7L;

void add(T)(ref T a, T b) { a = (a + b) % MOD; }

long calc(string s, int d) {
    int n = cast(int) s.length;
    auto dp = new int[][][](n + 1, 2, d);
    // dp[i][j][k]
    // i: 上から i 桁目まで
    // j: n 未満か
    // k: mod d

    dp[0][0][0] = 1;
    foreach (i; 0..n) {
        foreach (j; 0..2) {
            foreach (k; 0..d) {
                int lim = j == 1 ? 9 : s[i] - '0';
                foreach (m; 0..lim+1) {
                    add(dp[i + 1][j || m < lim][(k + m) % d], dp[i][j][k]);
                }
            }
        }
    }

    auto ans = (-1L + MOD + dp[n][0][0] + dp[n][1][0]) % MOD;
    return ans;
//    return ans - 1; // -1 は 0 の分
}

void main() {
    string s = read!string;
    int d = readint;
    writeln(calc(s, d) - calc("0", d));
}


Measured memory_bytes: 14332
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <string>
#include <iterator>
#include <vector>
 
using namespace std;

typedef long long ll;
typedef long double ld;
#define L(ID) ((ID*2)+1)
#define R(ID) ((ID*2)+2)
#define M(L,R) ((L+R)/2)
#define forr(start,end) for(int i = start; i < end; i++)
#define gap ' '
 
const int MAXN = 1e6 + 5;
int n = 0, m = 0;
int a[MAXN];
int b[MAXN];


int main() {
	int a,b,c;
	cin >> a >> b >> c;
	if(a == b and a != c){
		cout << "Yes" << endl;
		return 0;
	}
	if(a == c and a != b){
		cout << "Yes" << endl;
		return 0;
	}
	if(b == c and a != b){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;

    return 0;
} 

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<utility>
#include<cstdlib>
#include<typeinfo>


using namespace std;
#define INF 1000000005
int main()
{
int n,m;
std::cin >> n >> m;
std::vector<int> rcheck(n,0);
std::vector<int> bcheck(n,1);
std::vector<pair<int,int>> mov;
rcheck[0] = 1;
for(int i = 0; i < m; i++){
    int tx,ty;
    std::cin >> tx >> ty;
    tx--;
    ty--;
    pair<int, int> temp = make_pair(tx,ty);
    mov.push_back(temp);
}
int sum = 1;
for(int i = 0; i < m; i++){
    int x = mov[i].first;
    int y = mov[i].second;
    if(rcheck[x] == 1 && bcheck[x] > 1){
        sum++;
        bcheck[x]--;
        bcheck[y]++;
        if(rcheck[y] == 1) {
            sum--;
            continue;
        }
        rcheck[y] = 1;
    } else if(rcheck[x] == 1){
        bcheck[x]--;
        bcheck[y]++;
        if(rcheck[y] == 1) {
            sum--;
        }
        rcheck[x] = 0;
        rcheck[y] = 1;
    } else {
        bcheck[x]--;
        bcheck[y]++;
    }
}
//std::cout << sum << std::endl;
int csum = 0;
for(int i = 0; i < n; i++){
    csum += rcheck[i];
    //std::cout << i << " " << rcheck[i] << std::endl;
}
std::cout << csum << std::endl; 
return 0;
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N; cin >> N; 
	long long A[314514] = {}; 
	for(int i = 0; i < N; i++) cin >> A[i]; 
	long long cnt[64] = {}; 
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 60; j++){
			if((A[i] >> j) & 1) cnt[j] ++; 
		}
	}
	long long ans = 0; 
	for(int j = 0; j < 60; j++){
		long long tmp = cnt[j] * ((long long) N - cnt[j]); 
		for(int k = 0; k < j; k++){
			tmp *= 2; tmp %= 1000000007; 
		}
		ans += tmp; 
		ans %= 1000000007; 
	}
	cout << ans << endl;
}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,j,mx,t,x,ans,f[19][19],a[19],b[19];
char s[101];
int main(){
	scanf("%lld",&n);
	scanf("%s",s+1);
	mx=1ll<<n;mx--;
	for(t=0;t<=mx;t++){
		a[0]=b[0]=0;
		for(i=n*2;i>n;i--){
			x=n*2-i;
			if(t&(1ll<<x))a[++a[0]]=s[i]-'a';
			 else b[++b[0]]=s[i]-'a';
		}
		memset(f,0,sizeof(f));
		f[0][0]=1;
		for(i=1;i<=n;i++){
			for(j=0;j<=min(a[0],i-1);j++){
				if(i-1-j>b[0])continue;
				if(j<a[0]&&s[i]-'a'==a[j+1])f[i][j+1]+=f[i-1][j];
				if(i-j<=b[0]&&s[i]-'a'==b[i-j])f[i][j]+=f[i-1][j];
			}
		}
		ans+=f[n][a[0]];
	}
	printf("%lld",ans);
}

Measured memory_bytes: 256
/*input
async layered coding
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}
int main()
{
	IOS;
	string s;
	cin>>s;
	int ans=0;
	REP(i,SZ(s)) if(s[i]=='1') ans++;
	cout<<ans;
	return 0;
}


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

using namespace std;

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

	vector <int> a(n);

	cin >> a[0];

	long long ans = 0;

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

		if(a[i] < a[i-1]) {
			ans += a[i-1] - a[i];
			a[i] += a[i-1] - a[i];
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 4032
// Last Change: 08/04/2019 21:10:45.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

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

  int ans = 0;
  for (int i = 1; i <= N; ++i) {
    string str = to_string(i);
    if (str.size() % 2 == 1) {
      ++ans;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 888
from sys import stdin
N = int(stdin.readline().rstrip())

count = 0
if N < 105:
    pass
else:
    for i in range(105, N+1):
        if i % 2 == 0:
            pass
        else:
            divisor = 0
            for j in range(1, i+1):
                if i % j == 0:
                    divisor += 1
            if divisor == 8:
                count += 1
print(count)


Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

const int N = 123456 * 2;
ll acc[N], aux[N];

void add(int idx, ll v) {
  acc[0] += v;
  acc[idx + 1] -= v;
}

void add_spo(int idx, ll v) {
  aux[idx] += v;
}

int main(void){
  int n, m;
  cin >> n >> m;
  VI a(n);
  REP(i, 0, n) {
    cin >> a[i];
  }
  ll tot = 0;
  REP(i, 0, n - 1) {
    // a[i] (1 2 ... ??) a[i + 1]
    int diff = a[i + 1] - a[i];
    int dst = a[i + 1];
    if (diff < 0) {
      diff += m;
      dst += m;
    }
    tot += diff;
    // 1st-order diff table
    add(dst, 1);
    add(a[i] + 1, -1);
    add_spo(dst + 1, - diff + 1);
  }
  // acc
  REP(i, 1, N) {
    acc[i] += acc[i - 1];
  }
  REP(i, 0, N) {
    acc[i] += aux[i];
  }
  REP(i, 1, N) {
    acc[i] += acc[i - 1];
  }
  REP(i, 1, m + 1) {
    acc[i] += acc[i + m];
  }
  if (0) {
    REP(i, 0, m + 1) {
      cerr << " " << acc[i];
    }
    cerr << endl;
  }
  ll ma = 0;
  REP(i, 0, m + 1) {
    ma = max(ma, acc[i]);
  }
  cout << tot - ma << endl;
}


Measured memory_bytes: 3328
#include <stdio.h>

int main(void) {
  int a, b, n, i, j, k, flag;
  int x[40], y[40];
  int dp[17][17];

  while (1) {
    scanf("%d%d", &a, &b);
    if (a == 0 && b == 0) return 0;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
      scanf("%d%d", &x[i], &y[i]);

    for (i = 0; i < 17; i++)
      for (j = 0; j < 17; j++)
	dp[i][j] = 0;
    dp[1][1] = 1;

    for (j = 1; j <= b; j++) {
      for (i = 1; i <= a; i++) {
	if (i == 1 && j == 1) continue;
	flag = 0;
	for (k = 0; k < n; k++) {
	  if (x[k] == i && y[k] == j) {
	    flag = 1;
	    break;
	  }
	}
	if (flag) dp[i][j] = 0;
	else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }

    printf("%d\n", dp[a][b]);
  }
}

Measured memory_bytes: 600
/* attention to overflow */
#include <bits/stdc++.h>

#define dump(x) cerr<< #x << " = " << x <<endl
#define ALL(container) (container).begin(),(container).end()

using namespace std;
const int INF = 1 << 25;
void io() { cin.tie(0); ios::sync_with_stdio(false);}
template <class S,class T> ostream& operator<<(ostream& os, const pair <S,T> &s){return os<<'('<<s.first<<','<<s.second<<')';}
/*printf("%.9Lf\n",cf);*/
const int MOD = 1000000007;
const double EPS=1e-8;

int dp[200010];
struct ed{int u,v,t,c;};
vector <ed> eds(200010);
struct edge{int no,u,tc;};
vector <edge> Graph[100010];

int N,M,S,G;

int memo(int q){
	if(dp[q]!=-1) return dp[q];

	int uofq=eds[q].u;
	int tofq=eds[q].t;

	if(uofq==S) return dp[q]=tofq;

	int tmp=INF;
	for(int i=0;i<Graph[uofq].size();i++){
		int no=Graph[uofq][i].no;
		int tc=Graph[uofq][i].tc;
		//if(tc>tofq) continue;
		if(tc>tofq) break;
		tmp=min(tmp,(tofq-tc)+memo(no));
	}
	return dp[q]=tmp;
}

int main() {
	io();
	cin>>N>>M>>S>>G;
	S--,G--;
	fill_n(dp,M+10,-1);
	for(int i=0;i<M;i++){
		int u,v,t,c;
		cin>>u>>v>>t>>c;
		u--,v--;
		Graph[v].push_back({i,u,t+c});

		//eds.push_back({u,v,t,c});
		eds[i]={u,v,t,c};
	}

	for(int i=0;i<N;i++){
		sort(Graph[i].begin(),Graph[i].end(),[](const edge &a, const edge &b){return a.tc<b.tc;});
	}

	int ans=INF;
	for(int i=0;i<M;i++){
		if(eds[i].v==G) ans=min(ans,memo(i));
	}
	cout<<ans<<endl;


	return 0;
}

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

typedef long long ll;
typedef unsigned long long int ull;
#define endl "\n"
#define pb push_back
#define sq(a) (a)*(a)
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define MOD 1000000007
#define PI 3.141592653589793238
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

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

ll exp(ll x,ll n,ll mod)
{
    ll result=1;
    while(n>0)
    {
        if(n & 1 ==1)
            result=(result * x)%mod;
        x=(x*x)%mod;
        n=n>>1;
    }
    return result;
}



int32_t main()
{
    IOS

    int n;
    cin>>n;
    int h[n];
  	for(int i=0;i<n;i++) 
  		cin>>h[i];
  	
  	int dp[n];
  	dp[n-1]=0;
  	dp[n-2]=dp[n-1]+abs(h[n-2]-h[n-1]);

  	for(int i=n-3;i>=0;i--)
  		dp[i]=min(dp[i+1]+abs(h[i]-h[i+1]),dp[i+2]+abs(h[i]-h[i+2]));

  	cout<<dp[0]<<endl;

    
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int p(int A,int B){
  if(!B)return 1;
  if(B&1)return p(A,B-1)*A%mod;
  int C=p(A,B/2);
  return C*C%mod;
}
int k[10100];
int c(int A,int B){
  return k[A]*p(k[A-B]*k[B]%mod,mod-2)%mod;
}
signed main(){
  k[0]=1;
  for(int i=1;i<=10000;i++)k[i]=k[i-1]*i%mod;
  int S,ans=0;
  cin>>S;
  for(int i=1;i*3<=S;i++)ans=(ans+c(S-3*i+i-1,S-3*i))%mod;
  cout<<ans<<endl;
}

Measured memory_bytes: 3696
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;

int main() {
	int a, b;
	int ans = 0;
	std::cin >> a >> b;

	ans += std::max(a, b);
	if (std::max(a, b) == a) {
		a -= 1;
	}
	else {
		b -= 1;
	}

	ans += std::max(a, b);

	std::cout << ans << std::endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int main() {

    char b;
    cin >> b;

    if (b == 'A')cout << "T\n";
    if (b == 'C')cout << "G\n";
    if (b == 'G')cout << "C\n";
    if (b == 'T')cout << "A\n";


    return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
for x in range(len(B)):
  ans=ans+B[x]
for i in range(len(A)-1):
  if (A[i+1]-A[i])==1:
    ans=ans+C[A[i]-1]
print(ans)

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

int main() {
  int N;
  cin >> N;
  vector<int> H(N);
  int res = 1;
  for (int i = 0; i < N; i++) cin >> H[i];
  for (int i = 1; i < N; i++) {
    bool can = true;
    for (int  j = 0; j < i; j++) {
      if (H[i] < H[j]) can = false;
    }
    if (can) res++;
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
int main(){
	int N;
	cin>>N;
	cout<<0<<endl;
	string S[SIZE];
	cin>>S[0];
	if(S[0]=="Vacant"){
		return 0;
	}
	int low=0,high=N;
	for(int i=0;i<19;i++){
		int mid=(low+high)/2;
		cout<<mid<<endl;
		cin>>S[mid];
		if(S[mid]=="Vacant")
			return 0;
		if((S[mid]==S[low])!=((mid-low)%2)){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	return 0;
}

Measured memory_bytes: 1744
import java.util.Arrays;
import java.util.Scanner;
public class Main {

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

		Arrays.sort(a);

		int k=0;
		int i=0;
		
//		for(int j=0; j<N; j++){
//			x-=a[i];
//			k++;
//			if(x<0){
//				k--;
//				break;
//			}
//		}
		while(i<N){
			x-=a[i];
			i++;
			k++;
			if(x<0 || (i==N && x>0)){
				k--;
				break;
			}
		}
//		if(i==N && x>0) k--;

		System.out.println(k);
	}
}


Measured memory_bytes: 23636
#include<stdio.h>

int qq(int x, int y){
  return x * y;
}

int main(){
  int i,j;
  for(i=1; i<=9; i++){
    for(j=1; j<=9; j++){
      printf("%dx%d=%d\n", i, j, qq(i,j));
    }
  }

  return 0;
}

Measured memory_bytes: 524
n = int(input())

def pFact(n):
    l=[]
    if(n==1):
        return [1]
    while(n%2==0):
        l.append(2)
        n//=2
    
    f=3
    while(f*f <= n):
        if(n%f==0):
            l.append(f)
            n//=f
        else:
            f += 2
    
    if(n!=1):
        l.append(n)
    return l

l = pFact(n)
dic = {}
div_l = []

for x in l:
    if(dic.get(x) is None):
        dic[x] = 1
    else:
        dic[x] += 1
cnt = 0
for x,y in dic.items():
    if(x==1):
        continue
    e = 1
    while((y-e)>=0):
        y -= e
        e += 1
        cnt += 1
print(cnt)

Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
#define int  long long 
#define speedrap ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int be(int a,int b,int mod) {if(b == 0) return 1; if(b%2 == 1) return (a*be(a,b-1,mod))%mod; else return (be(a,b/2,mod)*be(a,b/2,mod))%mod;}
const int mod = 1e9 + 7;
#define PI 3.14159265359
#define pf push_front
#define pb push_back
#define bitcount __builtin_popcountll
#define setbitcnt __builtin_ctz
#define sc(a) scanf("%d", &a);
#define sz(s) (int)s.size()
#define eb emplace_back
#define pf push_front
#define mkp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define roundup(a,b)  std::cout << std::fixed;std::cout << std::setprecision(b); std::cout << a
const int siz = (1e6 + 10);
const int logi = 21;
const double epsilon = 1e-6;
bool cmp(const int &a,const int &b)
{
  return (abs(a-b)>1);
}



signed main()
{
	#ifndef ONLINE_JUDGE
 	freopen("in.txt", "r", stdin);
 	freopen("out.txt", "w", stdout);
 	#else
// // online submission
 	#endif 
	speedrap
	int t;
	t = 1;
	//cin>>t;
	int val = 0;
	while(t--)
	{
		map<string,int> mp;

		int n;
		cin>>n;

		int cnt1 = 0;
		int cnt2 = 0;
		int cnt3 = 0;
		int cnt4 = 0;
		int cnt5 = 0;

		for(int i = 0 ; i  < n ; i++)
		{
			string s;
			cin>>s;

			if(s == "AC")
			{
				cnt1++;
			}

			if(s == "WA")
			{
				cnt2++;
			}

			if(s == "TLE")
			{
				cnt3++;
			}

			if(s == "RE")
			{
				cnt4++;
			}
		}

		cout<<"AC"<<" x "<<cnt1<<"\n";
		cout<<"WA x "<<cnt2<<"\n";
		cout<<"TLE x "<<cnt3<<"\n";
		cout<<"RE x "<<cnt4<<"\n";
	}
}

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

int main() {
  int N;
  cin>>N;
  
  vector<int> vec(N);
  for(int i=0;i<N;++i){
    cin>>vec[i];
  }
  
  sort(vec.begin(),vec.end());
  
  cout<<vec[N-1]-vec[0]<<endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long i64;


template<i64 N> struct prime_numbers{
  set<i64> primes;
  bool p[N+1];
  
  constexpr prime_numbers<N>() : primes(), p() {
    p[0] = p[1] = true;
    for(i64 i=2; i<=N; i++) {
      if(p[i]) continue;
      if(i*i<=N) {
        for(i64 j=i; i*j<=N; j++) {
          p[i*j] = true;
        }
      }
      primes.insert(i);
    }
  }
  
  bool is_prime(i64 n) {
    return primes.find(n) != primes.end();
  }
};


int main(){
  i64 n;
  prime_numbers<1000000LL> ps;
  while(cin >> n) {
    int res = 0;
    for(int i=1; i<=n; i++) if(ps.is_prime(i)) res++;
    cout << res << endl;
  }
  
}



Measured memory_bytes: 7664
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    sort(rall(v));
    
    int x = v[0];


    int y = 0, diff = 2 * 1e9;
    for(int i=1; i<n; i++){
        if(abs(2*v[i] - x) < diff){
            diff = abs(2*v[i] - x);
            y = v[i];
        }
    }

    cout << x << " " << y << endl;
}


Measured memory_bytes: 640
#include<stdio.h>

int main(){
  char a[200000];
  scanf("%s",a);
  int zerokara=0,ichikara=0,i,len;
  len=strlen(a);
  for(i=0;i<len;i++){
    if(i%2==1){
      if(a[i]=='1'){
        ichikara++;
      }else{
        zerokara++;
      }
    }
    if(i%2==0){
      if(a[i]=='0'){
        ichikara++;
      }else{
        zerokara++;
      }
    } 
  }
  if(zerokara>ichikara){
    printf("%d",ichikara);
  }else{
    printf("%d",zerokara);
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define Cout(s) cout << s << endl
string Yes(bool b) {if(b){return "Yes";} else {return "No";}}
string YES(bool b) {if(b){return "YES";} else {return "NO";}}


int main(){
	int N, A, B;
	cin >> N >> A >> B;
	vector<int> P(N);
	rep(i, N) cin >> P[i];
	int a = 0, b = 0, c = 0;
	for(auto& p : P){
		if(p <= A) a++;
		else if(p <= B) b++;
		else c++;
	}

	Cout(min({a, b, c}));
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <random>
#include <tuple>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)
#define pb push_back
#define f first
#define s second
const ll INFL = 1LL << 60;//10^18 = 2^60
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD  = 998244353;
vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

ll kai_mod(ll x){
  if(x == 0) return 1;
  return x * kai_mod(x-1) % MOD;
}

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

ll N;
vector<ll> A;
int main(){
  cin >> N;
  A.resize(N);
  rep(i, N) cin >> A[i];
  ll ans = 0;
  ll plus = 1;

  while(plus){
    plus = 0;
    rep(i, N){
      plus += A[i] / N;
    }
    rep(i, N){
      A[i] = A[i] % N + plus - A[i] / N;
    }
    ans += plus;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100000

int main() {
        char S[MAX];
        int rcnt, bcnt, minCnt;
        int i;

        scanf("%s", S);

        rcnt = 0;
        for (i = 0; S[i]; i++) {
                if (S[i] == '0') rcnt++;
                bcnt++;
        }

        bcnt -= rcnt;

        if (rcnt < bcnt) minCnt = rcnt;
        else minCnt = bcnt;

        printf("%d\n", minCnt*2);

        return 0;
}


Measured memory_bytes: 256
N,M = map(int, input().split())
H = list(map(int, input().split()))

A = [[] for i in range(N+1)]
for i in range(N+1):
    A[i].append(H[i-1])
for i in range(M):
    a,b = map(int, input().split())
    A[a].append(H[b-1])
    A[b].append(H[a-1])

ans = 0
for i in range(1,N+1):
    if max(A[i]) == A[i][0] and A[i].count(A[i][0]) < 2:
        ans += 1

print(ans)


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

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    int result = 0;
    for(int i = 0; i < n; i++){
        cin >> p.at(i);
    }

    int flag = 0;
    int i = 0;
    int j = 0;
    int min = p.at(0);


    for(i = 0; i < n; i++){
        if(min >= p.at(i)){
            result++;
            min = p.at(i);
        }
    }

    cout << result << endl;

}

Measured memory_bytes: 1024
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut map: Vec<Vec<char>> = vec![];
    for _ in 0..n {
        let s: Vec<char> = read::<String>().chars().collect();
        map.push(s);
    }
    let mut ans: String = "".to_string();

    let abs: Vec<char> = "abcdefghijklmnopqrstuvwxyz".chars().collect();
    for c in abs {
        let min_cnt = map
            .iter()
            .map(|x| x.iter().filter(|&x| x == &c).count())
            .min()
            .unwrap();
        for _ in 0..min_cnt {
            ans += &c.to_string();
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef map<char,int> mci;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vii;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define in insert
#define sz(v) v.size()
#define mina(a,b) (a)=min((a),(b));
#define maxa(a,b) (a)=max((a),(b));
const ll INF = 1e18 + 5;

void solve(){
    string s; cin>>s;
    vi nearL(s.size()),nearR(s.size());
    int cur=0;
    for(int i = 0; i < s.size() ; i++){
        if(s[i]=='R') cur=i;
        nearR[i]=cur;
    }
    for(int i = s.size()-1; i >= 0 ; i--){
        if(s[i]=='L') cur=i;
        nearL[i]=cur;
    }
    vi ans(s.size());
    for(int i = 0; i < s.size(); i++){
        if(s[i]=='R'){
            int b=nearL[i]-i;
            if(b%2==0) ans[nearL[i]]++;
            else ans[nearL[i]-1]++;
        }
        else{
            int b=i-nearR[i];
            if(b%2==0) ans[nearR[i]]++;
            else ans[nearR[i]+1]++;
        }
    }
    for(int it:ans) cout<<it<<" ";
}
int main(){
    int T=1;        //! COMMENT IF THERE IS NO TEST CASES
    //cin>>T;
    for(int i = 0; i < T; i++) solve(); 
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
vector<ll> b;
vector<ll> xo(ll x){
  vector<ll> ret;
  int cnt=61;
  while(cnt>0){
    ret.push_back(x%2);
    x/=2;
    cnt--;
  }
  return ret;
}
int main(){
  ll n,k;cin>>n>>k;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  rep(i,n){
    ll c=0LL;
    reps(j,i,n){
      c+=a[j];
      b.push_back(c);
    }
  }
  n=n*(n+1)/2;
  vector<vector<ll>> v(n);
  rep(i,n){
    v[i]=xo(b[i]);
  }
  vector<bool> m(n,false);
  ll p=1LL<<60,ans=0LL;
  for(int i=60;i>=0;i--){
    ll t=k;
    rep(j,n){
      if(!m[j]&&v[j][i]==1)t--;
    }
    if(t<=0){
      rep(j,n)if(v[j][i]==0)m[j]=true;
      ans+=p;
    }
    p/=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 274032
#include <stdio.h>
#include <stdlib.h>
 
#define WHITE 0
#define BRACK 1
 
int **matrix;
int *d;
int *parent;
int *color;
 
void prim(int);
 
int main()
{
  int n,i,j;
  int cost=0;
  scanf("%d",&n);
  
  color =  malloc(n * sizeof(int ));
  d =  malloc(n * sizeof(int ));
  parent = malloc(n * sizeof(int));
  
  matrix = malloc(n * sizeof(int *));
  for(i=0;i<n;i++)
    matrix[i] = malloc(n * sizeof(int));
  
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      matrix[i][j] = -1;
   
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      scanf("%d",&matrix[i][j]);
  
  prim(n);
  
  for(i=0;i<n;i++)
    cost += d[i];
  
  printf("%d\n",cost);
  
  free(d);
  free(color);
  free(parent);
  for(i=0;i<n;i++) free(matrix[i]);
  free(matrix);
 
  return 0;
   
}
 
 
void prim(int n)
{
  int mincost;
  int i,j,u;
  
  for(i=0;i<n;i++)
    {
      d[i] = 2001;
      parent[i] = -1;
      color[i] = WHITE;
    }
  
  d[0] = 0;
  
  while(1)
    {
      mincost = 2001;
      
      for(i=0;i<n;i++)
	{
	  if(color[i] != BRACK && d[i] < mincost)
	    {
	      mincost = d[i];
	      u = i;
	    }
	}
      
      if(mincost == 2001) break;
      
      color[u] = BRACK;
      
      for(i=0;i<n;i++)
	{
	  if(color[i] != BRACK && matrix[u][i] != -1 && matrix[u][i] < d[i])
	    {
	      d[i] = matrix[u][i];
	      parent[i] = u;
	    }
	}
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <queue>
#include <list>
#include <vector>

using namespace std;

#define MIN(x, y) x<y?x:y
#define ABS(x, y) x<y?(y-x):(x-y)

typedef long long Long;

int main()
{
	Long n, k;
	Long prev=0;
	Long gap=0;

	cin>>n>>k;

	if(n>k) {
		gap = ABS(n, k);
		gap /= k;
	}

	n -= gap * k;

	do {
		prev = n;
		n = ABS(n,k);
	} while(prev>n);

	cout<<prev<<endl;

	return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> ans(n, -1);
    vector<int> dist(n, -1);
    queue<int> que;
    dist[0] = 0;
    que.push(0);
    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front();  // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : graph[v]) {
            if (dist[nv] != -1) continue;  // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);

            if (ans[nv] == -1) ans[nv] = v;
        }
    }

    for (int i = 1; i < n; i++) {
        if (ans[i] == -1) {
            puts("No");
            return 0;
        }
    }

    puts("Yes");
    for (int i = 1; i < n; i++) {
        cout << ans[i] + 1 << endl;
    }
}

Measured memory_bytes: 10568
#include <stdio.h>
#include <math.h>
int main(void){
    double x1,x2,y1,y2,sum;
    scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
    sum=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    printf("%f\n",sqrt(sum));
    return 0;
}

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

int main(){
    ll L,R; cin >> L >> R;
    int l=L%2019, r=R%2019;
    if(R-L>=2019 || l>=r){
        cout << 0 << endl;
        return 0;
    }
    int ans=2018;
    for(int i=l;i<r;i++){
        for(int j=i+1;j<=r;j++){
            ans=min(ans,(i*j)%2019);
            if(ans==0){
                cout << ans << endl;
                return 0;
            } //1や0になりうることを忘れていた。
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int w, h, x, y , r;
    cin >> w >> h >> x >> y >> r;
    if ( x-r >= 0 && y-r >= 0 && x+r <=w && y+r <= h)
       cout << "Yes" << endl;
    else 
        cout << "No" << endl;
    
       
       
}



Measured memory_bytes: 3116
# AOJ 1575: Product Sale Lines
# Python3 2018.7.13 bal4u

W, H = map(int, input().split())
N = int(input())
P = list(map(int, input().split()))
ans = x = y = 0
for p in P:
	if p == 0: x += 1
	else: y += 1
	if x < W-1:
		if x == y: ans += 1
	elif x == W-1: pass
	elif x < W+H-2:
		if x == y+2: ans += 1
	elif x == W+H-2: pass
	else:
		if x == y+4: ans += 1
print(ans)


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    ll x,y;
    cin >> x >> y;
    if(x % y == 0){
        cout << -1 << endl;
    }else{
        cout << x << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int a[11],n,i=0,s=0;cin>>n;
  for(;i<n;i++)cin>>a[i];
  sort(a,a+n);
  s=-a[i-1]/2;
  for(i=0;i<n;i++)s+=a[i];
  cout<<s<<endl;
}

Measured memory_bytes: 256
def payable?(n, a)
  # 1円硬貨の枚数が、支払う金額より多い場合
  if(n <= a)
    return 'Yes'
  end

  # 500円で払える分を除外
  remainder = n % 500
  if(remainder <= a)
    return 'Yes'
  else
    return 'No'
  end
end

N = gets.to_i # 支払う金額
A = gets.to_i # 1円硬貨の数

puts payable?(N, A)

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int R, G, B, N;

    cin >> R >> G >> B >> N;

    int ball[3] = {R, G, B};
    sort(ball, ball + 3);

    int answer = 0;

    for (int i = 0; N >= ball[2] * i; i++)
    {
        for (int j = 0; N >= ball[2] * i + ball[1] * j; j++)
        {
            if ((N - ball[2] * i - ball[1] * j) % ball[0] == 0)
            {
                answer++;
            }
        }
    }

    cout << answer << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

#define MAX 1400

struct Rectangle
{
  int height;
  int pos;
};

int getLargestRectangle(int size, int buffer[])
{
  stack<Rectangle> S;
  int maxv = 0;
  buffer[size] = 0;

  for (int i = 0; i <= size; i++)
  {
    Rectangle rect;
    rect.height = buffer[i];
    rect.pos = i;
    if (S.empty())
    {
      S.push(rect);
    }
    else
    {
      if (S.top().height < rect.height)
      {
        S.push(rect);
      }
      else if (S.top().height > rect.height)
      {
        int target = i;
        while (!S.empty() && S.top().height >= rect.height)
        {
          Rectangle pre = S.top();
          S.pop();
          int area = pre.height * (i - pre.pos);
          maxv = max(maxv, area);
          target = pre.pos;
        }
        rect.pos = target;
        S.push(rect);
      }
    }
  }
  return maxv;
}

int H, W;
int buffer[MAX][MAX];
int T[MAX][MAX];

int getLargestRectangle()
{
  for (int j = 0; j < W; j++)
  {
    for (int i = 0; i < H; i++)
    {
      if (buffer[i][j])
      {
        // 汚れタイル
        T[i][j] = 0;
      }
      else
      {
        // 上から1,2,3と増える
        T[i][j] = (i > 0) ? T[i - 1][j] + 1 : 1;
      }
    }
  }

  int maxv = 0;
  for (int i = 0; i < H; i++)
  {
    maxv = max(maxv, getLargestRectangle(W, T[i]));
  }

  return maxv;
}

int main()
{
  scanf("%d %d", &H, &W);
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      scanf("%d", &buffer[i][j]);
    }
  }

  cout << getLargestRectangle() << endl;

  return 0;
}


Measured memory_bytes: 18480
let () =
  let n = Scanf.scanf "%d\n" (fun n -> n) in
  let as_ = Array.to_list @@ Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
  let evens = List.length @@ List.filter (fun n -> n mod 2 = 0) as_ in
  let odds = List.length @@ List.filter (fun n -> n mod 2 = 1) as_ in
  print_endline (if odds = 1 && evens = 0 || odds mod 2 = 0 then "YES" else "NO")

Measured memory_bytes: 7936
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vso(x) sort( x.begin() , x.end() )
#define vre(x) reverse( x.begin() , x.end() ) ;
#define aso(x) sort( x , x + x.size() )
#define are(x) reverse( x , x + x.size() )
#define print(x) cout << x << endl 
#define no cout << "NO\n" 
#define yes cout << "YES\n"
typedef long long ll ; 
typedef unsigned long long ull ;
typedef long double ld ;
typedef pair<ll, ll> pairs ;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("problem_name.out", "w", stdout) ;
    //freopen("problem_name.in", "r", stdin) ;
    //ull h = 798568968205 ; srand(h) ;
    //int t ; cin >> t ; while(t--){}
    ll ans = 0 ;
    for ( int i = 1 ; i <= 5 ; i++ )
    {
        int x ; cin >> x ;
        if ( x == 0 ) ans = i ;
    }
    print(ans) ;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using mat = vector<vector<ll>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  int N; cin >>N;
  vector<int> s(N); rep(i, N) cin >>s[i];
  vector<vector<int>> dp(N+1, vector<int>(10001, 0));
  dp[0][0] = 1;
  for (int i=0; i<N; i++){
    for (int j=0; j<=10000; j++){
      if (dp[i][j] == 0) continue;
      dp[i+1][j] = 1;
      dp[i+1][j+s[i]] = 1;
    }
  }
  int res = 0;
  for (int j=0; j<=10000; j++){
    if (j%10==0) continue;
    if (dp[N][j]) res = j;
  }
  cout <<res <<endl;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,fa[N],cnt[N];
void find(int x)
{
    if (fa[x]==x) return;
    find(fa[x]);
    cnt[x]+=cnt[fa[x]],fa[x]=fa[fa[x]];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
        fa[i]=i;
    for(int i=1,x,y,z; i<=m; ++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        find(x),find(y);
        if(fa[x]==fa[y])
        {
            if(cnt[x]+z!=cnt[y])
            {
                puts("No");
                return 0;
            }
        }
        else
        {
            cnt[fa[y]]=cnt[x]+z-cnt[y];
            fa[fa[y]]=fa[x];
        }
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<complex>
#include<cmath>
using namespace std;

#define F(I,J,N) for(int I=J;I<N;I++)
typedef complex<double> P;
#define EPS (1.0e-6)

//内包問題
class Inclusion{
private:
	P *p;
	int n;//n個の点
	double l;//半径l内に存在
public:
	Inclusion(){}
	Inclusion(int n){
		this->n=n;
		p =new P[n];
	}
	~Inclusion(){
		delete []p;
	}
	void set(int n,P a){
		p[n]=a;
	}
	void set(double l){
		this->l=l;
	}
	int pnum(){
		int cnt;
		int ans=1;
		P c,ce,h;
		F(i,0,n-1){
			F(j,i+1,n){
				double len=abs(p[i]-p[j]);
				if(len<l*2+EPS){
					c=(p[i]+p[j])/2.0;
					h=(p[i]-p[j])*P(0,1);
					h=h*(sqrt(l*l-len*len/4)/abs(h));
					len=l*l;
					ce=c+h;
					cnt=0;
					F(k,0,n){
						if(k==i||k==j) cnt++;
						else if(abs2(p[k]-ce)<len+EPS) cnt++;
					}
					ans=max(ans,cnt);
					ce=c-h;
					cnt=0;
					F(k,0,n){
						if(k==i||k==j) cnt++;
						else if(abs2(p[k]-ce)<len+EPS) cnt++;
					}
					ans=max(ans,cnt);
				}
			}
		}
		return ans;
	}
	double abs2(P p){
		return this->dot(p,p);
	}
	//内積
	double dot(P a,P b){
		return (real(a)*real(b)+imag(a)*imag(b));
	}
};

int main(){
	int i,n;
	double x,y;
	double l;
	Inclusion *inc;
	while(cin>>n){
		if(n==0) break;
		inc=new Inclusion(n);
		for(i=0;i<n;i++){
			cin>>x>>y;
			inc->set(i,P(x,y));
		}
		inc->set(1);
		cout<<inc->pnum()<<endl;
		delete inc;
	}
	return 0;
}

Measured memory_bytes: 984
#include<stdio.h>
int main()
{
    int m,f,r,n;
    while(1)
    {
        scanf("%d %d %d",&m,&f,&r);
        if(m==-1 && f==-1 && r==-1)
        {
            return 0;
        }
        n = m+f;
        if(m==-1 || f==-1 || n<30)
        {
            printf("F\n");
        }
        else if(n>=80)
        {
            printf("A\n");
        }
        else if(n>=65 && n<80)
        {
            printf("B\n");
        }
        else if((n>=50 && n<65) || (r>=50))
        {
            printf("C\n");
        }
        else if(n>=30 && n<50)
        {
            printf("D\n");
        }
    }
    return 0;
}



Measured memory_bytes: 2060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
typedef long long ll;
const int INF = 1000000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 1000000007ll;

int main(){
	int n;
	std::cin >> n;
	vector<int> a(n);
	rep(i,n)std::cin >> a[i];
	int ans=0;
	rep(j,n){
		for (int i = j+1; i < n; i++) {
			/* code */
			ans+=a[i]*a[j];
		}
	}
	std::cout << ans << std::endl;
}



Measured memory_bytes: 256
import heapq

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


def calc(p):
    cnt = 0
    for a in A:
        for b in B:
            for c in C:
                if a + b + c < p:
                    break
                cnt += 1
                if cnt >= K:
                    return True
    return False


end = A[0] + B[0] + C[0] + 1
start = 0
while end - start > 1:
    mid = (end + start)//2
    if calc(mid):
        start = mid
    else:
        end = mid

D = []

for a in A:
    for b in B:
        for c in C:
            if a + b + c < start:
                break
            D.append(a + b + c)
D.sort(reverse=True)
for d in D[:K]:
    print(d)


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

const int INF = 1000000000;

int main()
{
	while(true){
		int n;
		cin >> n;

		if(n==0)
			break;

		int T[10][10];
		for(int i=0; i<10; i++){
			for(int j=0; j<10; j++){
				if(i==j){
					T[i][j] = 0;
				}
				else{
					T[i][j] = INF;
				}
			}
		}

		int m = 0;

		for(int i=0; i<n; i++){
			int a, b, c;
			cin >> a >> b >> c;

			T[a][b] = T[b][a] = c;

			if(a+1>m){
				m = a+1;
			}
			if(b+1>m){
				m = b+1;
			}
		}
    for(int i =0;i<m;i++){
      for(int j =0;j<m;j++){
        for(int k = 0;k<m;k++){
          if(T[j][k]>T[j][i]+T[i][k]){
            T[j][k]=T[j][i]+T[i][k];
          }
        }
      }
    }
    int anstown,anstime=INF;
    for(int i =0;i<m;i++){
      int sumtime=0;
      for(int j = 0;j<m;j++){
        sumtime+=T[i][j];
      }
      if(anstime>sumtime){
        anstown = i;
        anstime = sumtime;
      }
    }
    cout << anstown <<" "<<anstime<<endl;
  }
  return 0;
}



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

int main() {
  int K,X;
  cin >> K >> X;
  int m = X-K+1;
  cout << m;
  for(int i=0;i<2*K-2;i++){
    cout << ' ' << m+i+1;
  }
  cout << endl;
}



Measured memory_bytes: 256
from functools import reduce
from fractions import gcd

def gcd_list(numbers):
    return reduce(gcd, numbers)

n, x = map(int, input().split())
city = list(map(int, input().split()))
city.append(x)
city = sorted(city)
diff = [city[i+1] - city[i] for i in range(len(city)-1)]

if len(diff)==1:
    print(diff[0])
else:
    print(gcd_list(diff))

Measured memory_bytes: 16308
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
struct Edge {
  ll to;
  ll cost;
};
long long longpow(long long n, long long a, long long mod) {
  if (a == 0) return 1;
  if (a == 1) return n % mod;
  if (a % 2 == 1) return (n * longpow(n, a - 1, mod)) % mod;
  ll t = longpow(n, a / 2, mod) % mod;
  return (t * t) % mod;
}
int main() {
  ll N;
  cin >> N;
  vector<int> A(N + 1);
  for (int i = 1; i <= N / i; i++) {
    for (int j = i; j <= N / i; j++) {
      A[i * j]+=2;
      if (i == j) A[i * j]--;
    }
  }
  ll ans = 0;
  for (ll i = 1; i <= N; i++) {
    ans += i * A[i];
  }
  cout << ans << endl;
}

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

int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> A(N), B(N), C(N);
  for(int64_t i=0; i<N; i++){
    cin >> A.at(i);
    B.at(i)=A.at(i)+i;
    C.at(i)=i-A.at(i);
  }
  map<int64_t, int64_t> mB, mC;
  for(int64_t i=0; i<N; i++){
    mB[B.at(i)]=mB[B.at(i)]+1;
    mC[C.at(i)]=mC[C.at(i)]+1;
  }
  int64_t Ans=0;
  for(int64_t i=0; i<N; i++){
    Ans+=mC[B.at(i)];
  }
  cout << Ans << endl;
}

Measured memory_bytes: 42280