akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

class Main{
	public void run(){
		int n = ni();
		int[] a = new int[n];
		for(int i=0;i<n;i++){
			a[i] = ni();
		}
		int ans = 0;
		for(int i=0;i<n;i++){
			if(i == a[a[i]-1]-1)ans++;
		}
		out.println(ans / 2);
	}

	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().run();
		out.flush();
	}

	public Main(){
	}

	int ni(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;	}

	long nl(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}

	double nd(){
		return Double.parseDouble(next());
	}

	String next(){
		int c;
		while(!isAlNum(c = read()));
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	String nextLine(){
		int c;
		while(!isAlNumOrSpace(c = read()));
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNumOrSpace(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
	private static boolean isAlNumOrSpace(int c){
		return isAlNum(c) || c == ' ' || c == '\t';
	}
	void debug(Object... os){
		out.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 21904
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 1000000000
//#define NCONS 100001
//#define NCONS 1001
//#define NCONS 101
#define MCONS 2001
#define LIMIT 1000000000
#define TRUE 1
#define FALSE 0
#define toRadian(degree) ((degree) * (M_PI / 180.))
#define toDegree(radian) ((radian) * (180. / M_PI))
using namespace std;
struct Point{int x; int y;};

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int a, b; cin >> a >> b;
    
    for(int c = 1; c <= 3; c++)
    {
        if(a * b * c % 2 == 1)
        {
            cout << "Yes"; return 0;
        }
    }
    
    cout << "No";
    return 0;
}


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

int main(){
    int N, K, i;
    int ans = 0;
    int l[120];
    cin >> N >> K;

    for (i=0; i<N; i++){
        cin >> l[i];
    }

    sort(l, l + N, greater<int>());

    for (i=0; i<K; i++){
            ans = ans + l[i];
    }

    cout << ans << endl;
   }




Measured memory_bytes: 256
#ABC079C
I=input()
A,B,C,D=map(int,I)
K=['-','+','=']
for s in range(8):
	ans=A
	F=format(s,'b').zfill(3)
	for n,f in zip([B,C,D],F):
		if f=='1':
			ans+=n
		else:
			ans-=n
	if ans==7:
		F+='2'
		a=''
		for i,f in zip(I,F):
			a+=i+K[int(f)]
		a+='7'
		print(a)
		exit()

Measured memory_bytes: 3064
from collections import deque

n, m = map(int,input().split())
graph =[[] for _ in range(n+1)]
for _ in range(m):
    a,b =map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
queue = deque([1])
visited = [False] * (n+1)
visited[0] = True
ans = [0] * (n+1)
while queue:
    node = queue.popleft()
    for xnode in graph[node]:
        if visited[xnode]:
            continue
        ans[xnode]=node
        visited[xnode]=True
        queue.append(xnode)
print("Yes")
for a in ans[2:]:
    print(a)



Measured memory_bytes: 35744
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define INF 1e9L
#define EPS 1e-9
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<int>())S
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define pb push_back
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
    int n;
    cin >> n;
    int red = 0;
    REP(i, n){
        char s;
        cin >> s;
        if(s == 'R') red++;
    }
    Yes(red > (n - red));
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <set>
#include <queue>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb(x) push_back(x)
typedef long long LL;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const LL INF=0x3f3f3f3f;
const int N=200+5;
LL n,m,R;
LL d[N][N],r[N];
void floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
    while(cin>>n>>m>>R)
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
                if(i!=j) d[i][j]=INF;
                else d[i][j]=0;
        }
        LL u,v,w;
        for(int i=1; i<=R; i++)
            cin>>r[i];
        for(int i=1; i<=m; i++)
        {
            cin>>u>>v>>w;
            if(w<d[u][v]||w<d[v][u])
                d[u][v]=d[v][u]=w;
        }
        floyd();
        sort(r+1,r+R+1);
        LL ans=INF;
        do
        {
            LL tmp=0;
            for(int i=1;i<R;i++)
                tmp+=d[r[i]][r[i+1]];
            ans=min(ans,tmp);
        }while(next_permutation(r+1,r+R+1));
        cout<<ans<<endl;
    }
    return 0;
}

/*
3 3 2
1 3
2 3 2
1 3 6
1 2 2
4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4
*/


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

#define endl '\n'
#define ll long long
#define re register
#define pb(x) push_back(x)
#define ce(x) cout << x << '\n';

using db = long double;
using pll = pair < ll, ll >;

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 1000000007
const db pi = acos(-1);
const long long infl = LLONG_MAX;

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision

#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (ll _tt = 0; _tt < tt; _tt++) // testcase 

int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll t,i,x,j,y,z,k=0,n;

cin>>n;
ll a[n];
rep(i,0,n,1)	cin>>a[i];
j=1;
vector<ll>v;
rep(i,0,n,1){
	if(a[i]==j){
		v.pb(j);
		j++;
	}
}
k=n-v.size();
if(k==n)	k=-1;
ce(k)
}


Measured memory_bytes: 3956
n = int(input())
a = list(map(int, input().split()))
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
g = gcd(a[0],a[1])
for i in range(n):
    g = gcd(g,a[i])
print(g)


Measured memory_bytes: 14252
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
//#define mod 1000000007
#define MN 100005
using namespace std;
int a[MN],pos[MN],hua[MN];
int n,m,tot;
bool u[MN];
ll sum;

inline int read()
{
	int n=0,f=1; char c=getchar();
	while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
	while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
	return n*f;
}

//inline void rw(int& x,int y) {x+=y; if (x>=mod)x-=mod;}
int getf(int x) {return hua[x]<0?x:hua[x]=getf(hua[x]);}
inline void gather(int x,int y) {if (a[-hua[x]]<a[-hua[y]]) hua[y]=hua[x]; hua[x]=y;}
bool cmp(int x,int y) {return a[x]<a[y];}

int main()
{
	register int i,x,y;
	n=read(); m=read(); tot=(n-1-m)*2;
	if (tot>n) return 0*printf("Impossible");
	if (!tot) return 0*printf("0");
	for (i=1;i<=n;++i) a[i]=read(),pos[i]=i,hua[i]=-i;
	for (i=1;i<=m;++i)
	{
		x=read()+1; y=read()+1;
		gather(getf(x),getf(y));
	}
	for (i=1;i<=n;++i)
		if (hua[i]<0) u[-hua[i]]=true,sum+=a[-hua[i]],--tot;
	sort(pos+1,pos+n+1,cmp);
	for (i=1;i<=n&&tot;++i)
		if (!u[pos[i]]) sum+=a[pos[i]],--tot;
	printf("%lld",sum);
}

Measured memory_bytes: 1408
#!/usr/bin/env python3
import sys
from math import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()
 
def pairwaise(bools):
    for i in range(2,10**6):
        hantei=0
        for j in range(i,10**6+1,i):
            hantei+=bools[j]
        if hantei>1:
            return False
    return True
 
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    gcds=reduce(gcd,A)
    if gcds>1:
        print('not coprime')
    else:
        bools=[0]*(10**6+5)
        for AA in A:
            if bools[AA]==1 and AA!=1:
                print('setwise coprime')
                exit()
            bools[AA]+=1
        if pairwaise(bools):
            print('pairwise coprime')
        else:
            print('setwise coprime')
 
    
    
 
 
if __name__ == '__main__':
    main()

Measured memory_bytes: 127852
/* Graph */
#include <stdio.h>

int main()
{
    int n, i, j, u, k, v;
    int G[101][101];

    scanf("%d", &n);
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            G[i][j] = 0;
        }
    }

    for(i=1; i<=n; i++){
        scanf("%d %d", &u, &k);

        for(j=1; j<=k; j++){
            scanf("%d", &v);
            G[i][v] = 1;
        }
    }

    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            if(j == n){
                printf("%d", G[i][j]);
            } else{
                printf("%d ", G[i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2100
#define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <utility>
#include <set>

using namespace std;

int main() {

  int n, k;
  cin >> n >> k;

  vector<int> step(n, 0);
  rep (i, n) cin >> step[i];

  vector<int> cost(n, -1);
  cost[0] = 0;

  int tmp = 0;

  rep (i, n) {
    for (int j = i + 1; j <= i + k; j++) {
      tmp = abs(step[i] - step[j]);
      if (cost[j] == -1 || cost[j] > cost[i] + tmp) {
        cost[j] = cost[i] + tmp;
      }
    }
  }
   
  cout << cost[n - 1] << endl;

  return 0;
}


Measured memory_bytes: 1024
import collections
n = int(input())
a = [int(i) for i in input().split()] 

num_dict = collections.Counter(a)
min_dict = {}
max_num = 0
for k,v in num_dict.items():
  keymax = v*(v-1)/2
  max_num += keymax
  if (v == 1):
    min_dict[k] = 0
  else:
    min_dict[k] = keymax - (v-1)*(v-2)/2

for i in a:
  print(int(max_num-min_dict[i]))

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	int X, Y;
	cin >> X >> Y;
	cout << X + Y / 2 << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long n, dp[200000], a[200000], k, s; 
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	dp[0] = 1000000000000;
	
	for (int i = 2; i <= n; i ++) dp[i] = 1000000000000;
	long long minn = 100000000000000;
	for (int i = 2; i <= n; i ++)
	{
		if (i-k <= 0) s = 1;
			else
				s = i - k;
				
		for (int j = s; j < i;  j++)
		{
			dp[i] = min	(dp[i], dp[j] + abs(a[i] - a[j]));
		}			
	}
	cout << dp[n];
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

int32_t main()
{
	int a,b;
	cin>>a>>b;
	if(a<=5)
		cout<<0<<endl;
	else if(a>5&&a<=12)
		cout<<b/2<<endl;
	else 
		cout<<b<<endl;
}

Measured memory_bytes: 256
# import sys
# sys.setrecursionlimit(100000)
N, W = map(int, input().split())
v = []; w = []

for i in range(N):
    vv, ww = map(int, input().split())
    v.append(vv); w.append(ww)

"""
def rec(pos, rest):
    if pos == N:
        return 0
    ans = 0
    for i in range(0, rest//w[pos]+1):
        ans = max(ans, rec(pos+1, rest-w[pos]*i)+v[pos]*i)
    return ans

print(rec(0, W))
"""

dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(N-1, -1, -1):
    for j in range(W+1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
            else:
                dp[i][j] = dp[i+1][j]
print(dp[0][W])


Measured memory_bytes: 17092
use std::io::Read;
use std::cmp::max;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    
    let mut iter = buf.split_whitespace();
    
    let a: u32 = iter.next().unwrap().parse().unwrap();
    let b: u32 = iter.next().unwrap().parse().unwrap();
    
    println!("{}", max(max(a*2 - 1, b*2 - 1), a + b));
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int h[100001];
vector<vector<int>> adj(100001);
vector<bool> vis(100001,0);
int n,m,x,y;
int ans;
void dfs(int v,int p){
    vis[v]=true;
    int flag=1;
    for(auto i:adj[v]){
        if(h[i]>=h[v]) flag=0;
    }
    if(flag) {ans++;}
    for(auto i:adj[v]){
        if(!vis[i]) dfs(i,v);
    }
}
int main(){   
    ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>h[i];
    for(int i=0;i<m;i++){
        cin>>x>>y;
        adj[x-1].push_back(y-1);
        adj[y-1].push_back(x-1);
    }
    for(int i=0;i<n;i++){
        if(!vis[i]){
            dfs(i,-1);
        }
    }
    cout<<ans<<endl;
}   


Measured memory_bytes: 10124
def yakusu(n):
    results = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            results.append(n // i)
    return results

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in yakusu(sum(A)):
    M = sorted(map(lambda x: [x % i, (i-x % i)%i], A), key=lambda x: x[0])
    s = sum(map(lambda x: x[1], M))
    sm = 0
    for j, (m, m2) in enumerate(M):
        sm += m
        s -= m2
        if sm == s and s <=K:
            ans = max(ans, i)
print(ans)

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

int main(){
  int N,M;
  cin >>N>>M;
  
  vector<int> X(M);
  for(int i=0;i<M;i++) cin >>X[i];
  
  sort(X.begin(),X.end());
  
  vector<int> L(M-1);
  for(int i=0;i<M-1;i++) L[i] = X[i+1]-X[i];
  
  if (N < M){
    sort(L.begin(),L.end());
    reverse(L.begin(),L.end());

    int ans = X[M-1] - X[0];
    for(int i=0;i<N-1;i++) ans -= L[i];

    cout << ans << endl;
  }else{
    cout << 0 << endl;
  }
}


Measured memory_bytes: 1024
import sys

a, b = map(int, input().split())
a_ = int(str(a)*b)
b_ = int(str(b)*a)
la = len(str(a_))
lb = len(str(b_))
if a_ == b_:
    print(a_)
    sys.exit()
for i in range(min(la, lb)):
    ai = str(a_)[i]
    bi = str(b_)[i]
    if ai > bi:
        print(b_)
        sys.exit()
    elif ai < bi:
        print(a_)
        sys.exit()

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

using namespace std;

struct pt{
    int x,y;
    bool t;
};

int main(){
    int n;
    cin >> n;
    vector <pt> pts(2*n);
    for(int i=0;i<n;i++){
        cin >> pts[i].x >> pts[i].y;
        pts[i].t=0;
    }
    for(int i=n;i<2*n;i++){
        cin >> pts[i].x >> pts[i].y;
        pts[i].t=1;
    }
    sort(pts.begin(),pts.end(),[](pt &a, pt&b){
        return a.x < b.x;
    });
    set<int> remb;
    int ans=0;
    for(int i=2*n-1;i>=0;i--){
        if(pts[i].t==1){
            remb.insert(pts[i].y);
        }
        else{
            auto it = remb.upper_bound(pts[i].y);
            if(it!=remb.end()){
                ans++;
                remb.erase(it);
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

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

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

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=2019;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	ll l, r;
	cin>>l>>r;
	if(r-l>=2018){
		cout<<0<<'\n';
		return 0;
	}
	ll ans=1e18;
	for(ll i=l; i<r; ++i){
		for(ll j=i+1; j<r+1; ++j){
			CHMIN(ans, i*j%MOD);
		}
	}
	cout<<ans<<'\n';
	return 0;
}


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

int main() {
	int N,X;
  	cin >> N >> X;
  
  	vector<int> gram(N);
  
  	int least = 0;
  
  	for(int i = 0; i < N; i++) {
    	cin >> gram.at(i);
      	least += gram.at(i);
    }
  
  	int rest = X - least;
  
  	sort(gram.begin(),gram.end());
  	cout << N + (rest / gram.at(0)) << endl; 
  
}

Measured memory_bytes: 256
N = int(input())
d = []
for i in range(N):
    h, p = map(int, input().split())
    d.append((h, p))

d = sorted(d, key=lambda x: x[0] + x[1])
INF = float('inf')
dp1 = [INF] * (N + 1)
dp2 = [INF] * (N + 1)
dp1[0] = 0
for i in range(1, N + 1):
    for j in range(N + 1):
        dp2[j] = dp1[j]
        if j == 0:
            continue
        if dp1[j - 1] > d[i - 1][0]:
            continue
        dp2[j] = min(dp2[j], dp1[j - 1] + d[i - 1][1])
    dp1, dp2 = dp2, dp1

for i in range(N, -1, -1):
    if dp1[i] < INF:
        print(i)
        exit()

Measured memory_bytes: 49880
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  // 変数の宣言
  int n ; //マス目の数
  int a; //塗るマスの数
  
  //値の取得
  cin >> n>> a;
  
  //出力
  cout << n*n-a;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int a[10],i,j,p,q,A,n;
    char b[5],c[5];
    scanf("%d",&A);
    for(n=0;n<4;n++)
    {
        a[4-n-1]=A%10;
        A/=10;
    }
    int sum=a[0],flag=0;
    for(b[1]=0;b[1]<2;b[1]++)
    {
        for(b[2]=0;b[2]<2;b[2]++)
        {
            for(b[3]=0;b[3]<2;b[3]++)
            {
                for(q=1;q<=3;q++)
                {
                    if(b[q]==0)sum=sum+a[q];
                    if(b[q]==1)sum=sum-a[q];
                }
                if(sum==7){c[1]=b[1];c[2]=b[2];c[3]=b[3];flag=1;}
                sum=a[0];
                if(flag==1)break;
            }if(flag==1)break;
        }if(flag==1)break;
    }
   printf("%d",a[0]);
   for(i=1;i<=3;i++)
   {
       if(c[i]==0)printf("+");
       else printf("-");
       printf("%d",a[i]);
   }
   printf("=7");
   return 0;
}


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

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=n; i--)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
#define v2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

char c;
map<char,char> m;
int main() {
	cin>>c;
	m['A'] = 'T';
	m['T'] = 'A';
	m['G'] = 'C';
	m['C'] = 'G';
	p(m[c]);
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
 int i,j,n,a[200000],min,max;
 
 scanf("%d",&n);
 
 for(i = 0;i < n;i++)
   scanf("%d",&a[i]);

 min = a[0];
 max = a[1] - a[0];
 for(i = 1;i < n;i++)
 {
   if(max < a[i] - min) max = a[i] - min;
   if(min > a[i]) min = a[i];
 }


 printf("%d\n",max);
 
 return 0;
}


Measured memory_bytes: 2512
import java.util.Scanner;

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

		String s[] = sc.next().split("");

		for(int i = 1; i <= s.length; i++) {
			if(i % 2 == 1) {
				System.out.print(s[i-1]);
			}
		}


		/*
		String data = "";

		for(int i = 1; i <= s.length(); i++) {
			if(i % 2 == 1) {
				data = data + s.substring(i-1, i);
			}
		}

		System.out.println(data);
		*/

	}

}

Measured memory_bytes: 35320
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define int long long
#define mod 1000000007
#define fi first
#define se second
#define be begin()
#define en end()
#define re reverse
#define Set setprecision 
const int INFi=2147483647;
const long long INFl=9223372036854775807LL;
template<typename T> T abs(T a,T b){
    return max(a,b)-min(a,b);
}
template<typename T> T lcm(T a,T b){//�Ǿ����ܿ�
  return (a*b)/gcd(a,b);
}
int  gcd(int a,int b){//��������
  int c=a%b;
  while(true){
    if(c==0) break;
    a=b;
    b=c;
    c=a%b;
  }
  return b;
}
bool IsPrime(int num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
    double sqrtNum = sqrt(num);
    for(int i=3;i<=sqrtNum;i+=2){
	if(num%i==0){
	    return false;
	}
    }
  return true;
}
int c[10000000];
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,b,sum=0,d=0;
    map<int,int> a;
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>b;
      a[b]++;
      if(a[b]==1) c[d]=b,d++;
    }
    for(int i=0;i<d;i++){
      if(a[c[i]]%2==1) sum++;
    }
    cout<<sum<<"\n";
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_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())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll k;
  cin>>k;

  queue<ll> que;


  ll cnt=0;
  ll ans;
  REP1(i,10){
    que.push(i);
    cnt++;
    if(cnt==k)
      ans=i;
  }

  while(cnt<=k){
    ll now=que.front();
    que.pop();

    ll rem=now%10;
    for(ll i=-1; i<=1; i++){
      if(rem+i<=-1 || 9<rem+i)
        continue;
      ll res=now*10+rem+i;
      que.push(res);
      cnt++;
      if(cnt==k)
        ans=res;
    }
  }

  cout<<ans<<endl;
}



Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
void chmax (long long &a, long long b) {
    if (a < b) a = b;
}

int main() {
    int n, w;
    cin >> n >> w;
    vector<int> wei(n), val(n);
    for (int i=0; i<n; ++i) cin >> wei[i] >> val[i];
    vector<vector<long long>> dp(n+1, vector<long long>(w+10, 0));
    for (int i=0; i<n; ++i) {
        for (int sumw=0; sumw<=w; ++sumw) {
            if (sumw >= wei[i]) {
                chmax(dp[i+1][sumw], dp[i][sumw - wei[i]] + val[i]);
            }
            chmax(dp[i+1][sumw], dp[i][sumw]);
        }
    }
    cout << dp[n][w] << endl;
}

Measured memory_bytes: 80256
import java.util.*;
import java.math.BigInteger;

public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      BigInteger cost = new BigInteger("0");
      int[][] arr = new int[n][2];
      for(int i = 0; i < n; i++) {
        arr[i][0] = sc.nextInt();
        arr[i][1] = sc.nextInt();
      }
      Arrays.sort(arr, (a1, a2) -> a1[0] - a2[0]);
      for(int i = 0; i < n && m > 0; i++) {
        long cnt = Math.min(arr[i][1], m);
        cost = cost.add(BigInteger.valueOf(cnt * arr[i][0]));
        m -= cnt;
      }
      System.out.println(cost.toString());
  }
}

Measured memory_bytes: 94756
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

internal class Program {
    static void Main() => CustomMain();

    static void Solve() {
        long n, x;
        ReadMulti(out n, out x);

        // 2辺目までは確定
        long ans = n + Reflection(n - x, x);

        WriteAnswer(ans);
    }

    static long Reflection(long l, long s) {
        var div = l / s;
        var m = l % s;
        if (l % s == 0) {
            return (2 * div - 1) * s;
        } else {
            return 2 * div * s + Reflection(s, m);
        }
    }


    static void CustomMain() {
#if DEBUG
        // ファイルからテストケースを読み込む
        ChangeStdIn();
        // 時間計測
        var stopwatch = new Stopwatch();
        stopwatch.Start();
#endif
        // 出力高速化
        var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(streamWriter);
        // 回答
        Solve();
#if DEBUG
        stopwatch.Stop();
        Console.WriteLine(stopwatch.Elapsed);
#endif
        Console.Out.Flush();
    }

    static string ReadString() => Console.ReadLine().Trim();
    static int ReadInt() => int.Parse(ReadString());
    static long ReadLong() => long.Parse(ReadString());
    static float ReadFloat() => float.Parse(ReadString());
    static double ReadDouble => double.Parse(ReadString());

    static string[] ReadStringArray() => ReadString().Split(' ');
    static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
    static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
    static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
    static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

    static T TypeConversion<T>(string s) {
        if (typeof(T) == typeof(int)) {
            return (T) Convert.ChangeType(int.Parse(s), typeof(T));
        } else if (typeof(T) == typeof(long)) {
            return (T) Convert.ChangeType(long.Parse(s), typeof(T));
        } else if (typeof(T) == typeof(double)) {
            return (T) Convert.ChangeType(double.Parse(s), typeof(T));
        } else {
            return (T) Convert.ChangeType(s, typeof(T));
        }
    }

    static void ReadMulti<T, U>(out T a, out U b) {
        var str = ReadStringArray();
        a = TypeConversion<T>(str[0]);
        b = TypeConversion<U>(str[1]);
    }

    static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
        var str = ReadStringArray();
        a = TypeConversion<T>(str[0]);
        b = TypeConversion<U>(str[1]);
        c = TypeConversion<V>(str[2]);
    }

    static void WriteAnswer(object ans) => Console.WriteLine(ans);

    static bool IsOdd(long num) {
        return (num & 1) == 1;
    }

    static bool IsEven(long num) {
        return (num & 1) == 0;
    }

    static long GCD(long a, long b) {
        return b != 0 ? GCD(b, a % b) : a;
    }


    static void ChangeStdIn() {
        var path = "./../../TestCase.txt";
        var exStdIn = new System.IO.StreamReader(path);
        Console.SetIn(exStdIn);
    }
}

Measured memory_bytes: 11732
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long mod2 = 998244353;
const long long INF = 1LL << 60;
const int inf = pow(10, 9) + 7;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

vector<int> parent(100100, -1);

void init(int n)
{
  for (int i = 0; i < n; i++)
  {
    parent.at(i) = -1;
  }
}

int root(int X)
{
  if (parent.at(X) < 0) return X;
  return parent.at(X) = root(parent.at(X));
}

int size(int X)
{
  return -parent.at(root(X));
}

void unite(int X, int Y)
{
  int x = root(X);
  int y = root(Y);
  if (x == y) return;
  
  if (size(x) < size(y)) swap(x, y);
  parent.at(x) += parent.at(y);
  parent.at(y) = x;
}

int main()
{
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < M; i++)
  {
    int X, Y, Z;
    cin >> X >> Y >> Z;
    unite(X, Y);
  }
  
  int ans = 0;
  for (int i = 1; i <= N; i++)
  {
    if (parent.at(i) < 0) ans++;
  }

  cout << ans << endl;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

string s;

int main() {
	cin >> s;
	
	bool ans = true;
	
	ans &= (s[0] == 'A');
	s[0] = 'a';
	int c = 0;
	incID(i, 2, s.size() - 1) { if(s[i] == 'C') { c++; s[i] = 'c'; } }
	ans &= (c == 1);
	inc(i, s.size()) { ans &= (inII(s[i], 'a', 'z')); }
	
	cout << (ans ? "AC" : "WA") << endl;
	
	return 0;
}


Measured memory_bytes: 256
n = int(input())
ans = 0
if n < 3:
  print(0)
  quit()
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return (over // under )% (10** 9 + 7)

for i in range(1,n//3+1):
  k = n - 3 * i
  ans +=  cmb((k + i - 1),(i -1))
print(ans% (10** 9 + 7))

Measured memory_bytes: 9472
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [1]*n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unit(self,x,y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        self.rank[x] += self.rank[y]
        self.par[y] = x
        
n,m,*pxy = map(int,open(0).read().split())
p = pxy[:n]
xy = pxy[n:]

uf = UnionFind(n)

for x,y in zip(xy[::2],xy[1::2]):
    uf.unit(x-1,y-1)

ans = 0
for i,pi in enumerate(p):
    if uf.find(i) == uf.find(pi-1): ans += 1

print(ans)

Measured memory_bytes: 35316
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int main(void){
    double a,b,C,S,L,h;
    double P=acos(-1);
    scanf("%lf%lf%lf",&a,&b,&C);
    C=C*P/180;
    S=sin(C)*a*b/2;
    L=a+b+sqrt(a*a+b*b+-2*a*b*cos(C));
    h=b*sin(C);
    
  printf("%.6lf\n%.6lf\n%.6lf\n",S,L,h);  
}



Measured memory_bytes: 3460
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<vector>
#include<list>
#include<map>
#include<unordered_map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>
#include<cstdlib>
#include<ctime>

#define ld  long double
#define ll  long long int
#define ull unsigned long long int
#define pb  push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLr(obj) (obj).rbegin(), (obj).rend()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,s,n) for(int i=s;i<n;i++)
#define endl "\n"

const ll INF = 1LL << 60;
const ld EPS = 1e-11;

//切り上げ整数除算
int divRoundUp(const int& a, const int& b) { return (a + b - 1) / b; }
//四捨五入
int roundOff(const double& a) { return (int)(a + 0.5); }
// r の(誤差付きの)符号に従って, -1, 0, 1 を返す.
int sgn(const ld& r) { return (r > EPS) - (r < -EPS); }
// a, b の(誤差付きの)大小比較の結果に従って, -1, 0, 1 を返す.
int sgn(const ld& a, const ld& b) { return sgn(a - b); }
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; }

using namespace std;

inline void Main() {
	int n; cin >> n;
	vector<int> a(n); REP(i,n)cin >> a[i];
	vector<int> b(n + 1); b[0] = 0;
	FOR(i, 1, n + 1) {
		b[i] = a[i - 1] + b[i - 1];
	}

	auto ans = INF;

	FOR(i, 1, n) {
		int s1 = b[i];
		int s2 = b[n] - s1;
		
		if (ans > abs(s1 - s2))
			ans = abs(s1 - s2);
	}
	cout << ans;
	cout << endl;
}

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

	Main();

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <sstream>
using namespace std;

#define REP(i,a,n) for(i=a; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define foreach(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); it++)


int main(){
    int p,q,i;

    while( cin >> p >> q ){
        map<int,int> cycle;
        string res;
        int idx = 1;

        cycle.insert(make_pair(p,0));
        while( p > 0 ){
            res += (char)(10 * p / q + '0');
            p = 10 * p % q;
            if( cycle.count(p) ) break;
            cycle.insert(make_pair(p,idx));
            idx++;
        }
        cout << res << endl;
        if( p > 0 ){
            idx = cycle[p];
            rep(i,idx) putchar(' ');
            for(i=idx; i<res.length(); i++) putchar('^');
            puts("");
        }
    }
    return 0;
}

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

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt();
		int[] h = new int[n];
		
		for(int i = 0; i < n; i++) {
			h[i] = stdIn.nextInt();
		}
		
		int cnt = 1;
		int max = h[0];
		
		
		for(int i = 1; i < n; i++) {
			if(max <= h[i]) {
				cnt++;
				max = Math.max(max, h[i]);
			}
			
			
		}
		
		System.out.println(cnt);
		
	}

}


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

using namespace std;

#define vi vector<int>
#define pb push_back
#define lli long long int
#define INF 99999999
#define endl "\n"

void solve() {
	string s, k;
	cin >> s >> k;
	int cnt = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != k[i])cnt++;
	}
	cout << cnt << endl;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);

	freopen("output.txt", "w", stdout);
#endif
	// int t; cin >> t;
	// while (t--) {
	solve();

	// }



	return 0;

}

Measured memory_bytes: 3836
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
  int s1, s2, d;
  int rec_num = 0;
  int loz_num = 0;
  while (scanf("%d,%d,%d\n", &s1, &s2, &d) != EOF) {
    if (s1*s1+s2*s2==d*d) {
      rec_num++;
      continue;
    } else if (s1==s2) {
      loz_num++;
    }
  }
  cout << rec_num << endl;
  cout << loz_num << endl;
      
  return 0;
}

Measured memory_bytes: 0
n=int(input())
t,a = map(int,input().split())
h = list(map(int,input().split()))
r = []
for i in range(n):
  r.append(abs(a-(t-(h[i]*0.006))))
MIN=min(r)
for i in range(n):
  if MIN == r[i]:
    print(i+1)
    break

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define GO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
const int N = 3e4 + 5;
const int M = 1e6 + 5;
const int Mod = 1e9 + 7;


int main()
{
	GO;
	int n;
	cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans += (i % 5 && i % 3 ? i : 0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
 
int main(){
  vector<int> array;
 
  long long int N, K;
  cin>>N>>K;
  
  int number, pcs; 
  map<int, unsigned long int> mp;
  for(int i = 0; i < N; i++){
    cin>>number>>pcs;
 
    auto itr = mp.find(number);
    if(itr != mp.end()){
      if(mp[number] < K) mp[number] += pcs; 
    }else{
      array.push_back(number);
      mp[number] = pcs;
    }
 
  }
 
  sort(array.begin(), array.end());
 
  unsigned long int index = 0;
  for (int i = 0; i < array.size(); i++){
    index += mp[array[i]] ;
    if(index >= K){
      cout<<array[i]<<endl;
      break;
    }
  }
 
  return 0;
}


Measured memory_bytes: 4476
import java.util.Scanner;

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

		if (Math.abs(x-a) > Math.abs(x-b)) {
			System.out.println("B");
		} else {
			System.out.println("A");
		}
		
		sc.close();
	}
}


Measured memory_bytes: 23764
#include<stdio.h>
int main(){
  int n,m,a,s,b,i,d[100003]={0,0};
  scanf("%d %d",&n,&m);
  for(i=1;i<n;i++){
    scanf("%d",&a);
    d[i+1]=a+d[i];
  }//printf("a\n");
  b=1;
  while(m--){
    scanf("%d",&a);
    if(a>0)s+=d[a+b]-d[b];
    else   s+=d[b]-d[b+a];
    b+=a;
    s%=100000;
  }
  printf("%d\n",s);
  return 0;
}

Measured memory_bytes: 996
import sys
from collections import deque
import copy
def main():
    X = int(input())
    now = 1
    for A in range(-118, 120):
        for B in range(-119, 118):
            if A ** 5 - B ** 5 == X:
                print(A, B)
                sys.exit()


if __name__ == '__main__':
    main()


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

const int MAX_N = 50000;

// p[i] := i 番目の素数
vector<int> p;
// is_p[i] := i が素数のとき true
bool is_p[MAX_N+1] = {false,false};
// cnt_p[i] := i 以下の素数の数
int cnt_p[MAX_N+1];

// エラトステネスのふるい
void sieve(){
	for(int i = 2 ; i <= MAX_N ; i++ )
		is_p[i] = true;
	for(int i = 2 ; i*i <= MAX_N ; i++ ){
		if( is_p[i] ){
			p.push_back( i );
			for(int j = i+i ; j <= MAX_N ; j += i ){
				is_p[j] = false;
			}
		}
	}
	// 任意の i 以下の素数の個数を求める(i <= MAX_N)
	int cnt = 0;
	for(int i = 0 ; i <= MAX_N ; i++ ){
		if( is_p[i] ){
			cnt++;
		}
		cnt_p[i] = cnt;
	}
}

int main(){
	sieve();
	int T;
	vector<int> v(3);
	
	while( cin >> T , T ){
		int ans = 0;
		map<vector<int>,bool> m;
		
		for(int a=2 ; a < T ; a++ ){
			if( !is_p[a] ) continue;
			for(int b=a ; a+b < T && (T-a-b) < a+b ; b++ ){
				if( !is_p[b] ) continue;
				int c = T - a - b;
				if( !is_p[c] || a >= b+c || b >= a+c || c >= a+b ) continue;
				
				v[0] = a; v[1] = b; v[2] = c;
				sort(v.begin(),v.end());
				if( !m.count(v) ){
					ans++;
					m[v] = true;
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 7760
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

typedef long long ll;

using namespace std;

int main(int argc, const char * argv[]) {
  ll N;
  cin >> N;
  ll i=10;
  ll j;
  ll ans = 0;
  ll keta = 1;
  while(i<=N){
    keta++;
    i *= 10;
  }
  i = 1;
  ll t;
  while(keta > i){
    if(i%2==1){
      t = 1;
      for(j=1; j<i;j++){
        t *= 10;
      }
      ans += t * 9;
    }
    i++;
  }
  if(keta%2==1){
    t = 1;
    for(j=1;j<keta;j++){
      t *= 10;
    }
    ans += N - t + 1;
  }
  cout << ans;
  return 0;
}


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

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    long long ans = 1;
    long double check=1;
    for(int i=0;i<n;i++){
        long long a;
        cin >> a;

        check*=a;
        ans*=a;
    }

    if(check>1e18) cout << -1 << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <list>
#include <cmath>

int main(int argc, char const* argv[])
{
    std::string str;

    getline(std::cin, str);
    long n = std::stol(str);

    auto residents = std::list<long>();
    auto sum = static_cast<long>(0);
    while (std::getline(std::cin, str, ' ')) {
        sum += std::stol(str);
        residents.push_back(std::stol(str));
    }

    auto ave = static_cast<long>(std::round((float)sum / n));

    auto consumption = static_cast<long>(0);
    for (auto x : residents)
        consumption += pow(x - ave, 2);

    std::cout << consumption << std::endl;

    return 0;
}


Measured memory_bytes: 384
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	m := map[int64]int{}
	var s int64
	for i := 0; i < n; i++ {
		a := getNextInt64(scanner)
		s += a
		m[a]++
	}
	q := getNextInt(scanner)
	for i := 0; i < q; i++ {
		b := getNextInt64(scanner)
		c := getNextInt64(scanner)
		s -= b * int64(m[b])
		s += c * int64(m[b])
		m[c] += m[b]
		delete(m, b)
		fmt.Fprintln(writer, s)
	}
}


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

int main() {
    int A , B , C ; 
    int X , Y , Z ;
    cin >> A >> B >> C ; // 1 ≤ B ≤ A ≤ 20 , 1 ≤ C ≤ 20
    X= A - B;
    Y = min (C, X);
    Z = C - Y;
    cout << Z << endl;
	return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <unordered_map> 
using namespace std; 
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI1 3.14159265358979311599796346854418516159057617187500

typedef long long int ll;  
ll MOD = 1e9 + 7;

ll power(ll a , ll n)
{
    unsigned long long int result=1,x=a;
    while(n>0)
    {
        if(n % 2 ==1)
            result = (result * x)%MOD;
        x = (x * x)%MOD;
        n=n/2;
    }
    return result;
}

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

int main()
{
    FIO;
    int t;
    t=1;
    //cin >> t;
    while(t--)
    {
        int n;
        cin >> n;

        int a[n];

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

        ll dp[n] = {0};
        dp[0] = 1000;
        ll mx = 1000;
        for(int i=0;i<n;i++)
        {
            ll stock_size = mx/a[i];
            for(int j=i+1;j<n;j++)
                dp[j] = max(dp[j],(stock_size*a[j]) + mx%a[i]);
            mx = max(mx, dp[i]);
            //cout << mx << endl;
        }

        cout << mx << endl;

    }   
    return 0;
}


Measured memory_bytes: 3556
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n, x; cin >> n >> x;
    vint a(n);
    rep(i,n) cin >> a[i];
    sort(all(a));
    ll sum = 0;
    int ans = 0;
    rep(i,n) {
        sum += a[i];
        if (i == n-1 && sum != x) break;
        if (sum <= x) ans++;
        else break;
    }
    cout << ans << endl;
}

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

int main() {
	
	int a, b;
	cin >> a >> b;
	
	if(b % a == 0) cout << a + b << endl;
	else cout << b - a << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,A;
  cin>>N;
  vector<int> B(N);
  for(int i=0;i<N-1;i++){
    cin>>A;
    B.at(A-1)++; 
  }
  
  for(int i=0;i<N;i++){
    cout<<B.at(i)<<endl; 
  }
  
  
  return 0;
}


Measured memory_bytes: 4052