akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <tuple>
#include <cstring>
#include <map>
#include <iomanip>
#include <ctime>
#include <complex>
#include <cassert>
#include <climits>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _ << " " <<
#define all(X) (X).begin(), (X).end()
#define len(X) (X).size()
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define Tiii tuple<int, int, int>
#define Tlll tuple<ll, ll, ll>

ll INF = 1e15;

vector<vector<ll>> WF_init(int v) {
    vector<vector<ll>> ret;
    for (int i = 0; i < v; i++) {
        vector<ll> tmp;
        for (int j = 0; j < v; j++) tmp.push_back(INF * (i != j));
        ret.push_back(tmp);
    }
    return ret;
}

vector<vector<ll>> warshall_floyd(vector<vector<ll>> G) {
    int v = G.size();
    for (int k = 0; k < v; k++) {
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
    return G;
}

int main() {
    ll n, m, l;
    cin >> n >> m >> l;
    
    vector<vector<ll>> G, H;
    G = WF_init(n);
    H = WF_init(n);

    for (int i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;  b--;
        G[a][b] = c;
        G[b][a] = c;
    }
    G = warshall_floyd(G);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (G[i][j] <= l) H[i][j] = 1;
            //else if (G[i][j] != INF) H[i][j] = 1;
        }
    }

    H = warshall_floyd(H);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        cout << (H[s - 1][t - 1] != INF ? H[s - 1][t - 1] - 1: -1) << endl;
    }

    /*
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << G[i][j] << " " ;
        }
        cout << endl;
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << H[i][j] << " " ;
        }
        cout << endl;
    }*/
}


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

namespace Util {
#ifdef LOCAL
#define dbg(a) cerr << __LINE__ << " \"" << #a << "\": " << a << '\n'
#else
#define dbg(a)
#endif
#define all(v) (v).begin(), (v).end()
}
using namespace Util;

int64_t constexpr MOD = int(1e9) + 7;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        g[--v].emplace_back(--u);
        g[u].emplace_back(v);
    }
    vector<vector<int64_t>> dp(n, vector<int64_t>(2, 1));
    function<void(int, int)> dfs = [&](int v, int p) {
        for (auto &u : g[v]) {
            if (u == p) continue;
            dfs(u, v);
            (dp[v][0] *= (dp[u][0] + dp[u][1]) % MOD) %= MOD;
            (dp[v][1] *= dp[u][0]) %= MOD;
        }
    };
    dfs(0, -1);
    cout << (dp[0][0] + dp[0][1]) % MOD;
    return 0;
}



Measured memory_bytes: 22448
#include <algorithm>
#include <cstdio>
#include <utility>
typedef long long lld;
typedef std::pair<lld,lld> pll;
const int MAXN = 1e5+5;
int A[MAXN];
lld P[MAXN];
lld M;
int N;

lld sum;

lld f(int x) {
  lld cnt = 0LL;
  sum = 0LL;
  for (int i = N; i >= 1; --i) {
    int k = (A+N+1) - std::lower_bound(A+1, A+N+1, x - A[i]);
    if (k) {
      sum += 1LL * k * A[i] + (P[N] - P[N-k]);
      cnt += k;
    }
  }
  return cnt;
}

lld solve() {
  int lo = 2 * A[1];
  int hi = 2 * A[N];
  while (lo < hi) {
    int x = (lo + hi + 1) / 2;
    if (f(x) >= M) {
      lo = x;
    } else {
      hi = x-1;
    }
  }
  lld cnt = f(lo);
  lld ret = sum - lo * (cnt - M);
  return ret;
}

void init() {
  A[0] = 0;
  std::sort(A+1, A+N+1);
  P[0] = 0;
  for (int i = 1; i <= N; ++i) {
    P[i] = P[i-1] + A[i];
  }
}

int main() {
  scanf(" %d%lld", &N, &M);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
  }
  init();
  printf("%lld\n", solve());
  return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include<cstring>
#include<tuple>


#define rep(i,p,q) for(int i = p;i < q;i++)
#define ll long long

using namespace std;

//ABC 48 C

int main(void) {
	ll n, x;
	cin >> n >> x;
	vector<ll> a = vector<ll>(n);
	rep(i, 0, n)cin >> a[i];
	ll ans = 0;
	rep(i, 1, n) {
		ll sum = a[i] + a[i - 1];
		if (sum > x) {
			if (a[i] > sum - x) {
				a[i] -= sum - x;
				ans += sum - x;
			}
			else {
				ans += sum - x;
				a[i - 1] -= sum - x - a[i];
				a[i] = 0;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <set>
#include <cstdio>
#include <string>
#include<cmath>
using namespace std;
 int a[100][100];
int main(){
int n,d;
cin>>n>>d;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=d;j++)
	{
		cin>>a[i][j];
	}
}
int sum=0,x=0;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<i;j++)
	{
		x=0;
		for(int k=1;k<=d;k++)
		{
		x=x+(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);	
		}
		if((int)sqrt(x)*(int)sqrt(x)==x)
		sum++;
	 } 
}
cout<<sum<<"\n"; 



    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int H, W, i, j;
	while(1){
		scanf("%d %d", &H, &W);
		if (H == 0&&W == 0) {
			break;
		}
		for (i = 0; i < H; i++) {
			for (j = 0; j < W; j++) {
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2696
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    pl,ql=p.popleft,q.popleft
    pa,qa=p.append,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            pl()
            b-=ql()
        h-=b
        t=-(-h//a)
        if t>0:
            s+=t
            t*=a
            b+=t
            pa(x+d+d)
            qa(t)
    print(s)
main()

Measured memory_bytes: 56264
#include <bits/stdc++.h>
using Weight = int;
using Capacity = int;
struct Edge {
    int src, dst;
    Weight weight;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

Edge double_sweep(const Graph &g, int s = 0) {
    static const Weight INF = std::numeric_limits<Weight>::max() / 8;
    static const auto bfs = [](const Graph &g, int s, std::queue<int> &q, std::vector<int> &dist) {
        while(q.size()) q.pop();
        q.push(s);
        int n = g.size();
        dist.assign(n, INF);
        dist[s] = 0;
        while(q.size()){
            int u = q.front();
            q.pop();
            for(auto &e : g[u]){
                int v = e.dst;
                if(dist[v] == INF){
                    dist[v] = dist[u] + e.weight;
                    q.push(v);
                }
            }
        }
        return dist;
    };
    std::vector<Weight> dist;
    std::queue<int> q;
    bfs(g, s, q, dist);
    int n = g.size(), u = -1, v = -1;
    for (int i = 0; i < n; i++)
        if (dist[i] != INF && (u == -1 || dist[i] > dist[u])) u = i;
    bfs(g, u, q, dist);
    for (int i = 0; i < n; i++)
        if (dist[i] != INF && (v == -1 || dist[i] > dist[v])) v = i;
    Weight d = dist[v];
    if (u > v) std::swap(u, v);
    return Edge(u, v, d);
}

int main(){
    int n;
    std::cin >> n;
    Graph g(n);
    for(int i = 0; i < n - 1; ++i){
        int a, b, c;
        std::cin >> a >> b >> c;
        add_edge(g, a, b, c);
    }
    std::cout << double_sweep(g).weight << std::endl;
}

Measured memory_bytes: 10848
import java.util.*

fun main(args: Array<String>) {
    val argList = Scanner(System.`in`)

    val n = argList.nextLine().toInt()
    val a = argList.nextLine().split(" ").map { it.toFloat() }

    val e = Alchemist()
    e.execute(n, a)

}

class Alchemist {
    fun execute(n: Int, a: List<Float>) {
        val result = mutableListOf<Float>()
        val sorted = a.sorted()

        composite(sorted, result)
        println(result[0])
    }

    private fun composite(sorted: List<Float>, result: MutableList<Float>) {
        if (sorted.size <= 2) {
            result.add((sorted[0] + sorted[1]) / 2)
            return
        }
        val calculated = (sorted[0] + sorted[1]) / 2
        val p = sorted.drop(1).drop(1)

        val sortedWithout = (p + calculated).sorted()

        composite(sortedWithout, result)
    }
}

Measured memory_bytes: 34036
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

ll combi[50][50];
char str[1000];

int main() {
  combi[0][0] = 1;
  REP(i, 49) REP(j, 49) {
    combi[i + 1][j] += combi[i][j];
    combi[i + 1][j + 1] += combi[i][j];
  }
  while (scanf("%s", str) > 0) {
    int len = strlen(str);
    int rest = len;
    ll ans = 1;
    for (char c = 'a'; c <= 'z'; c++) {
      int cnt = count(str, str + len, c);
      if (cnt % 2 == 1) {
        if (rest % 2 == 0) { ans = 0; break; }
        cnt--; rest--;
      }
      ans *= combi[rest / 2][cnt / 2];
      rest -= cnt;
    }
    printf("%lld\n", ans);
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,H;
  cin >> N >> H;
  vector<int> a(N),b(N);
  int Ma=0;
  for(int i=0;i<N;i++){cin >> a[i] >> b[i]; Ma=max(Ma,a[i]);}
  sort(b.begin(),b.end());
  reverse(b.begin(),b.end());
  int count=0;
  for(int i=0;i<N;i++){
    if(b[i]<Ma){break;}
    count++;
    H-=b[i];
    if(H<=0){cout << i+1 << endl; return 0;}
  }
  cout << count+(Ma+H-1)/Ma << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200001;
int n,c2[N],c5[N],sum[101][101];
int lowbit(int x){return x&(-x);}
void insert(int x,int y){for(;x<=100;x+=lowbit(x))for(int t=y;t<=100;t+=lowbit(t))sum[x][t]++;}
int query(int x,int y){
	if(x<=0||y<=0)return 0;
	int ans=0;
	for(;x;x-=lowbit(x))for(int t=y;t;t-=lowbit(t))ans+=sum[x][t];
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		double x;
		scanf("%lf",&x);
		ll t=x*1e9+0.5;
		while(t%2==0){c2[i]++;t/=2;}
		while(t%5==0){c5[i]++;t/=5;}
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans+=i-1-query(100,18-c5[i])-query(18-c2[i],100)+query(18-c2[i],18-c5[i]);
		insert(c2[i]+1,c5[i]+1);
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 5276
N=int(input())
def make_divisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n//i)
	return divisors
ans=len(make_divisors(N-1))-1
d=make_divisors(N)
for i in d:
	if i==1:
		continue
	p=0
	n=N
	while p==0:
		n=n//i
		p=n%i
	if p==1:
		ans+=1
print(ans)

Measured memory_bytes: 3188
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
	long int i, j;
	long int n, d;
	long int flg;
	long int count = 1;
	long int max = 0;
	long int tugi = 0;
	long int index_max;
	long int index_tugi;
	long int a[200000];
	
	scanf("%ld%ld", &n, &d);
	
	if(n % (2 * d + 1) == 0) {
		printf("%ld\n", n / (2 * d + 1) );
		return 0;
	}
	
	printf("%ld\n", (n / (2 * d + 1) ) + 1 );
	
	return 0;
}


Measured memory_bytes: 128
using Atcoder;
using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var T = Console.ReadLine();
            int ret = 0;
            for (int i = 0; i < 3; i++)
            {
                if (S[i] == T[i])
                {
                    ret++;
                }
            }
            Console.Write(ret);
        }
        //static void Main(string[] args)
        //{
        //    var temp = new Atcoder.ABC130.D();
        //    temp.Run();
        //}

    }
}

Measured memory_bytes: 11092
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

/*aのb進数時の桁数*/
ll digits(ll a, ll b){return a/b?1+digits(a/b,b):1;}
/*nをa進数にしたときの、i桁目の数*/
ll a_base2(ll n, ll a, ll i){return i==1?n%a:a_base2(n/a,a,i-1);}

int main(void){
    // char ;
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll d[k];
    rep(i,0,k){
        scanf("%lld",&d[i]);
    }
    while(1){
        ll f2=0;
        rep(i,0,digits(n,10)){
            ll f1=0;
            rep(j,0,k){
                if(a_base2(n,10,i+1)==d[j]) break;
                f1++;
            }
            if(f1!=k) break;
            f2++;
        }
        if(f2==digits(n,10)) break;
        n++;
    }
    
    printf("%lld\n",n);
    return 0;
}


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

const int mxn = 3e3 + 3;
int n, trgt;
double P[mxn];

double dp[mxn][mxn];

double dfs( int i, int j ) {
	if( i < 1 ) {
		if( j == 0 ) return 1.0;
		return 0.0;
	}
	double& ret = dp[i][j];
	if( ret >= 0.0 ) return ret;

	ret = 0.0;
	ret += (P[i] * dfs( i - 1, j - 1 ) + (1.0 - P[i]) * dfs( i - 1, j ));
	return ret;
}

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	trgt = n / 2 + 1;
	for(int i = 1; i <= n; i++) {
		cin >> P[i];
	}
	memset(dp, -1, sizeof dp);
	double res = 0.0;
	for(int i = n; i >= trgt; i--) {
		res += dfs( n, i );
	}
	cout << fixed << setprecision(10) << res << "\n";
}

Measured memory_bytes: 70912
#define _DEBUG
#include "bits/stdc++.h"
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
int main(){
	ll A,V,B,W,T;
	scan(A>>V>>B>>W>>T);
	if(T*(V-W)>=abs(A-B)) prin("YES");
	else prin("NO");
	return 0;
}


Measured memory_bytes: 3620
/*
Look at the star
Look at the shine for U
*/
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define sl(x) scanf("%lld",&x)
using namespace std;
const int N = 1e6+5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
ll inv(ll b){if(b==1)return 1; return (mod-mod/b)*inv(mod%b)%mod;}
ll fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}
ll s[N],pre[N];
vector <ll> vec;
int main()
{
	ll i,j,k,n;
	for(i = 1;i < 201;i += 2)
	{
		k = 0;
		for(j = 1;j *j <= i;j++)
		{
			if(j*j == i) k++;
			else if(i%j == 0) k += 2;
		}
		if(k == 8) vec.push_back(i);
	}
	sl(n);
	ll ans = 0;
	for(i = 0;i < vec.size();i++)
	{
		if(n >= vec[i]) ans++;
		else break;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, K = read_ints()

A = read_ints()
B = []
for a in A:
    B.append(a - 1)

# ループするまで回してみる?
# 閉路が知りたい
# 閉路の起点をメモ
# K←（K-起点までの回数）
# K%閉路の長さ
# のこりは愚直に起点から再スタート

nums_to_arrive = [-1] * N
nums_to_arrive[0] = 0
now = 0
while True:
    to = B[now]
    if nums_to_arrive[to] == -1:
        nums_to_arrive[to] = nums_to_arrive[now] + 1
        if nums_to_arrive[to] == K:
            print(to + 1)
            exit()
    else:
        break
    now = to
n1 = nums_to_arrive[to]
n2 = nums_to_arrive[now] + 1 - n1
base = to  # 起点
# print(base)


K = (K - n1) % n2  # 残り移動回数
# print(n1, n2, K)
now = base  # 起点をもとに開始する
while K:
    to = B[now]
    K -= 1
    now = to
print(now + 1)


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

int main(){
  int N,M;
  cin>>N>>M;
  std::vector<int> v(N,1000000);
  int a,b;
  for(int i=0;i<M;i++){
    cin>>a>>b;
    a--;
    b--;
    v[a]=min(v[a],b);
  }
  int m=0;
  int ans=0;
  int i=0;
  while(i<N){
    m=1000000;
    for(i;i<min(m+1,N);i++)m=min(m,v[i]);
    ans++;
    i=m;
  }
  cout<<ans-1<<endl;
}


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

const int MAX = 100005;
int A[MAX];

int main() {
    int N, a;
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &a);
        A[a]++;
    }

    long long x, ans;
    ans = 0;
    for (int i = 1; i < MAX-1; i++) {
        x = (long long)A[i-1] + A[i] + A[i+1];
        ans = max(ans, x);
    }

    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 640
a, b, c, d = map(int, input().split())

i = 0
while True:
    if a <= 0:
        print("No")
        exit()
    elif c <= 0:
        print("Yes")
        exit()
    if i % 2 == 0:
        c -= b
    else:
        a -= d
    i += 1


Measured memory_bytes: 9176
#include<iostream>
#include <math.h>
#include <string>
#define int long long int
using namespace std;
signed main()
{
    int N;
    cin >> N;
    int i;
    int C[500],S[500],F[500];
    for(i=0;i<N-1;i++)
        cin >> C[i] >> S[i] >> F[i];
    for(i=0;i<N;i++)
    {
        int t=0;
        for(int j=i;j<N-1;j++)
        {
            if(t<S[j])
                t=S[j];
            else if (t%F[j]==0);
            else
                t=t+F[j]-t%F[j];
            t+=C[j];
        }
        cout << t << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
b=0
for x in A:
  if x%2==0:
    if x%3==0 or x%5==0:
      pass
    else:
      b=1
      break
if b==0:
  print("APPROVED")
else:
  print("DENIED")

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

int main(){
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    for(int i=0; i<n; i++){
        int c;
        cin>>c;
        a[i]=c;
        b[i]=c;
    }
    sort(b.rbegin(),b.rend());
    for(int i=0; i<n; i++){
        if(a[i]==b[0])cout<<b[1]<<endl;
        else cout<<b[0]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
 
ifstream fin("input.in");
long long n;
vector<int> ans;


int main() {
  cin >> n;
  while(n != 0){
    if(n%26 == 0){
      ans.push_back(26);
      n -= 26;
      n /= 26;
    }else{
      ans.push_back(n % 26);
      n -= n%26;
      n /= 26;
    }
  }
  for(int i = ans.size()-1; i >= 0; i--){
    cout << char(ans[i]+96);
  }
}

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

int main(){
  int w,h,p[h][w],i=1;
  cin>>w>>h;
  char c;
  cin>>c;
  for(int j=1;i<=h && j<=w;j++){
    if((i==1 && j==1) || (i==h && j==1)|| (i==h && j==w)){
      printf("+");
    }else if((i==1 && j==w) || (i==h && j==w)){
      printf("+\n");
    }else if(i==1 || i==h){
      printf("-");
    }else if(j==1){
      printf("|");
    }else if(j==w){
      printf("|\n");
    }else if(i==(h+1)/2 && j==(w+1)/2){
      printf("%c",c);
    }else{
      printf(".");
    }
    if(j==w){
      j-=w;
      i++;
    }
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 3108
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        int c = 0;
        REP(i,10){
            REP(j,10){
                REP(k,10){
                    REP(l,10){
                        if(i + j + k + l == n)
                            c++;
                    }
                }
            }
        }
        printf("%d\n",c);
    }
}

Measured memory_bytes: 3220
#include<iostream>
#include <iomanip>
#include <ios>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include<limits>
#include<cstdlib>
#include<functional>
#include<cassert>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#define fi(p) for(int i=0;i<(p);i++)
#define ce(d) cout<<d<<endl;

using namespace std;

const int MAX_N = 100000;
const int MAX_W = 100000;


int A[MAX_N+1];
int B[MAX_N+1];

void solve() {
	int n;
	float input;
	float sum = 0;
	cin >> n;

	vector<float> a(n);
	vector<float> b(n);
	fi(n) {
		cin >> input;
		sum += 1 / input;
	}
	cout << fixed;
	cout<< setprecision(10) << 1/sum;

	




}

int main()
{

	solve();

	int a;//止める用
	cin >> a;
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int n, k;
	cin>>n>>k;
	string s;
	cin>>s;
	int cnt = 1;
	for(int i = 1; i < n; i++){
		if(s[i] != s[i - 1])cnt++;
	}
	if(cnt)cnt = max(1, cnt - 2*k);
	cout<<n - cnt<<endl;

	return 0;
}

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

using namespace std;

//int N,M,K,L,R,H,W;
long long int N,M,K,L,R,H,W;

//constexpr long long int MOD=1000000007;
//constexpr  int MOD=1000000007;
constexpr int MOD=998244353;
//constexpr long long int MOD=998244353;

long long int gcd(long long int a,long long int b){
	while(b){
		a%=b;
		swap(a,b);
	}
	return a;
}

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

	cin>>K;
	while(K--){
		cin>>H>>W;
		int g=gcd(H,W);
		H/=g;
		W/=g;
		if(H%2==0||W%2==0){
			cout<<"1 1"<<endl;
		}
		else{
			cout<<(H*W+1)/2<<" "<<(H*W-1)/2<<endl;
		}
	}
	return 0;
}


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

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define debug(i) cout << i << endl;
#define debugarr(a) for(auto i : a) cout << i << " ";

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll, ll>
#define vpi vector<pi>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);

    int  n;
    cin >> n;

    int ans = 0;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            ans += arr[i] * arr[j];
        }
    }
    cout << ans << endl;
}


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, k;
  cin >> n >> k;

  vector<int> cnt(n, 0);
  for (int i = 0; i < k; ++i) {
    int d;
    cin >> d;
    for (int i = 0; i < d; ++i) {
      int idx;
      cin >> idx;
      idx--;

      cnt[idx]++;
    }
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (cnt[i] == 0) {
      ans++;
    }
  }

  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>

int max=100;

int main(){
  int x[max][max];
  int n, i, j, u, v, num;
  scanf("%d",&n);
  for(i=0 ; i<n ; i++){
    for(j=0 ; j<n ; j++){
      x[i][j]=0;
    }
  }
  for(i=0 ; i<n ; i++){
    scanf("%d%d",&u, &num);
    u=u-1;
    for(j=0 ; j<num ; j++){
      scanf("%d", &v);
      v=v-1;
      x[u][v]=1;
    }
  }
  for(i=0 ; i<n ; i++){
    for(j=0 ; j<n ; j++){
      if(j!=0)printf(" ");
      printf("%d", x[i][j]);
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2112
#include <iostream>
#include <vector>
// #include <algorithm>
// #include <set>
// #include <cmath>
// #include <string>
 
using namespace std;
typedef unsigned long long ull;
 
 
int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
 
    ull ans = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 3 != 0 && i % 5 != 0) {
            ans += i;
        }
    }
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>

using namespace std;

int main()
{
	int h, w;
	while (1) {
		cin >> h >> w;
		if (h == 0 && w == 0)break;
		for (int q = 0; q < h; q++) {
			for (int e = 0; e < w; e++) {
				cout << '#';
			}
			cout << endl;
		}
		cout << endl;
	}
}


Measured memory_bytes: 3108
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  string g;
  while (cin >> g, g != "#") {
    int y, m, d;
    cin >> y >> m >> d;
    if (y < 31 || (y == 31 && m < 5)) {
      cout << g;
    } else {
      cout << "?";
      y -= 30;
    }
    cout << " " << y << " " << m << " " << d << endl;
  }
  return 0;
}



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

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

	char ch;
	int len = s.length();
	for(int i = 0; i < len - 1; ++i){
		ch = s[i];
		for(int j = i + 1; j < len; ++j){
			if(s[j] == ch) {
				cout << "no" << endl;
				return 0;
			}
		}
	}
	cout << "yes" << endl;
	return 0;
}

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

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;

int main() {
    int n, a, b;
    cin >> n;
    if (n == 1) {
        cout << "Hello World" << endl;
    } else {
        cin >> a >> b;
        cout << a + b << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
/*
Arthor : Ender_zzm
E-mail zzm_ender_wiggin@outlook.com
Blog ender-zzm.enbar.cn
*/
#include <bits/stdc++.h>
using namespace std;

inline int read(){
    register int x = 0, flag = 1;
    register char ch;
    while (!isdigit(ch = getchar())) if (ch == '-') flag = -1;
    while (x = x * 10 + (ch & 15), isdigit(ch = getchar()));
	return x * flag;
}

template <class T>
inline void write(T x){
    if (x < 0)
        putchar('-'), x = -x;
    if(x >= 10) write(x / 10); 
    putchar(x % 10 + '0');
}

template<class T> inline bool Chkmax(T& x, const T& y) { return x < y ? x = y, true : false; }
template<class T> inline bool Chkmin(T& x, const T& y) { return x > y ? x = y, true : false; }

#define For(i, x, y) for (int i = (x); i <= (y); i++) 
#define Rep(i, x, y) for (int i = (x); i >= (y); i--) 

const int maxn = 202020;
int n, m;
int a[maxn];
vector<int> ans;
int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i++) a[i] = read();
	if (m == 1) {
		if (a[1] - 1 != 0) printf("%d\n%d\n%d %d\n", a[1], 2, a[1] - 1, 1);
		else printf("%d\n%d\n%d\n", a[1], 1, 1);
		return 0;
	}
	int tmp = 0;
	for (int i = 1; i <= m; i++) {
		tmp += a[i] % 2;
	}
	if (tmp > 2) {
		printf("Impossible\n");
		return 0;
	}
	for (int i = 1; i <= m; i++) {
		if (a[i] % 2 == 1) {
			if (a[1] % 2 == 0) swap(a[1], a[i]);
			else swap(a[i], a[m]);
		}
	}
	for (int i = 1; i <= m; i++) {
		printf("%d ", a[i]);
	}
	cout << endl;
	ans.push_back(a[1] - 1);
	for (int i = 2; i <= m - 1; i++) {
		ans.push_back(a[i]);
	}
	ans.push_back(a[m] + 1);
	tmp = 0;
	if (a[1] - 1 == 0)  tmp = 1;
	printf("%d\n", ans.size() - tmp);
	for (int i = 0; i <= ans.size() - 1; i++) {
		if (ans[i] == 0) continue;
		printf("%d ", ans[i]);
	}
}


Measured memory_bytes: 3744
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int main() {
  string in;
  getline(cin, in);
  
  if (in.size() == 0) {
    cout << 0 << endl; return 0;
  }

  int ll = 0, rl = in.size() - 1, ans = 0;
  const char lc[4] = { '(', ')', 'i', 'w' };
  const char rc[4] = { ')', '(', 'i', 'w' };
  while (ll <= rl) {
    if (ll == rl) {
      if (in[ll] == '(' || in[rl] == ')') ans++;
      break;
    }
    bool ok = false;
    rep (i,4) if (in[ll] == lc[i] && in[rl] == rc[i]) ok = true;
    if (!ok) ans++;
    ll++;
    rl--;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
    using namespace std;
    int main() {
      int n;
      cin >> n;
      map<string, priority_queue<pair<int, int>>> mp;
      for(int i = 0; i < n; ++i) {
        string s;
        int j;
        cin >> s >> j;
        mp[s].push(make_pair(j, i));
      }
      for(auto& p : mp) {
        auto& q = p.second;
        while(!q.empty()) {
          auto x = q.top();
          q.pop();
          cout << x.second+1 << endl;
        }
      }
    }

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	string s, a;
	cin >> s;
	
	rep(i, s.size()){
		switch(s[i]){
		case '0':
		case '1':
			a += s[i];
			break;
		case 'B':
			if(a.size() != 0) a.pop_back();
			break;
		}
	}
	
	cout << a << endl;
	return 0;
}

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

#define REP(i, n, m) for(int i = n; i < m; i++)
#define REPR(i, n, m) for(int i = n; i >= m; i--)
#define LREP(i, n, m) for(ll i = n; i < m; i++)
#define LREPR(i, n, m) for(ll i = n; i >= m; i--)


const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;

//#define int long long
typedef long long ll;


//functions 
int gcd(int a, int b){
    if(a < b) swap(a, b);
    return b?gcd(b, a%b):a;
}

int s2i(string num){stringstream ss; ss << num << flush; int n; ss >> n; return n;}
string i2s(int n){stringstream ss; ss << n << flush; return ss.str();}

ll D, G;
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> D >> G;
    ll p[D], c[D];
    ll ans = INF;
    ll tmp_ans;
    ll score;
    REP(i, 0, D) cin >> p[i] >> c[i];

    REP(i, 0, 1 << D){
        //cout << bitset<10>(i) << endl;
        score = 0;
        tmp_ans = 0;
        //cout << "完答問題:";
        REP(j, 0, D){
            if(i & 1<<j) {
                score += p[j] * (j + 1) * 100 + c[j];
                tmp_ans += p[j];
                //cout << j;
            }
        }
        //cout << endl;
        //cout << "score = " << score << endl;
        if(score >= G){
            //cout << "問題数" << tmp_ans << endl;
            ans = min(ans, tmp_ans);
        }else{
            ll num_added;
            REPR(j, D-1, 0){
                if(!(i & 1<<j)){
                    num_added = ((G-score)%2==0 ? (G-score)/((j +1)*100):(G-score)/((j + 1)*100) + 1);
                    if(p[j] > num_added && score + num_added * (j + 1) * 100 >= G){
                        tmp_ans += num_added;
                        ans = min(ans, tmp_ans);
                        break;
                    }
                }
            }
        }
    }

    cout << ans << endl;
}


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

using namespace std;

int main(){
	int h,a,temp;
	cin >> h >> a;
	
	temp = h % a;
	if(temp == 0) cout << h/a <<endl;
	else cout << h/a + 1 << endl;	

	return 0;
}

Measured memory_bytes: 256
/*Author : Kartik Bansal
 *Date : 02/08/19
 *Time : 17:46 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define tc int t ;cin>>t ;while(t--)
#define pb push_back
#define FOR(i,n) for(int i =0;i<n;i++)
#define loop(a,b) for(int i=a;i<b;i++)
#define Sort(v) sort(v.begin() ,v.end())
#define vi  vector<int>
int32_t main()
{
  ios::sync_with_stdio(0) ;
  cin.tie(0) ; cout.tie(0) ;
  int n, k  ;
  cin>>n>>k  ;
  vi v(n+1) ;
  v[0] = 0 ;
  // FOR(i,n)
  loop(1, n+1)
  cin>>v[i] ;
  int z = INT_MAX ;
  vi dp(n+1, z ) ;
  dp[1] = 0 ;
  for(int i =1 ;i<n;i++)
  {
    for(int j =i+1 ;j<=i+k;j++)
    {
      // if(i-j >= 0 )
      dp[j] = min(dp[j] , dp[i]+abs(v[j] - v[i])) ;
    }
  }
  cout<<dp[n] ;


}


Measured memory_bytes: 1024
n=gets.to_i
a=[0]+gets.split.map(&:to_i)

if a.all?{|i|i==0}
  p 0
elsif a.max.abs > a.min.abs
  buf=(1..n).select{|i|a[i]<0}.map{|i|[a.index(a.max),i]*" "}
  a=a.map{|i|i<0 ?i+a.max: i}
  (1..n-1).each{|i|
    if a[i]>a[i+1]
      buf << [i,i+1]*" "
      a[i+1]+=a[i]
    end
  }
  puts buf.size,buf
else
  buf=(1..n).select{|i|a[i]>0}.map{|i|[a.index(a.min),i]*" "}
  a=a.map{|i|i>0?i+a.min: i}
  (n-1).downto(1){|i|
    if a[i]>a[i+1]
      buf << [i+1,i]*" "
      a[i]+=a[i+1]
    end
  }
  puts buf.size,buf
end


#p a

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <iomanip>
#include <cmath>
#include <set>
#include <numeric>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;

int main()
{
    // 整数の入力
    ll N;
    cin >> N;
    vector<vector<string>> candidates(N+1);
    candidates[0].push_back("");
    for(int i = 1;i <= N;i++){
        for(auto c: candidates[i-1]){
            set<char> unique_chars;
            for(auto cc:c){
                unique_chars.insert(cc);
            }
            for(int j = 0;j < unique_chars.size() + 1 ;j++){
                candidates[i].push_back(c + (char)('a' + j));
            }
        }
    }
    for(auto c: candidates[N]){
        cout << c << endl;
    }
    return 0;
}

Measured memory_bytes: 11380
/********************************
*** ******** ********** *********
*** * ****** ********* * ********
*** ** ***** ******** *** *******
*** *** **** ******* ***** ******
*** **** *** ****** ******* *****
*** ***** ** ***** +++++++++ ****
*** ****** * **** *********** ***
*** *******  *** ************* **
*** ******** ** *************** *
**********_**********************
* |   /  / \  \     /    /\     *
* |  /  |   |  \   /    /  \    *
* | /   |   |   \ /    /    \   *
* |+\   |   |    |    /______\  *
* |  \  |   |    |   |        | *
* |   \  \_/     |   |        | *
********************************/
#include<bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define KING 1000000002
#define queen 1000002
#define fi first
#define se second
#define se second
#define lsb(i) (i & -i)
#define Pi 3.141592653589793238
#define nl cout<<'\n'
#define TEST cout<<"TEST",nl
#define all(a) a.begin(), a.end()
#define remax(a, b) (a = ((a<b) ? b : a))
#define remin(a, b) (a = ((a<b) ? a : b))
#define pr pair<lli,lli>
#define pb push_back
#define eb emplace_back
#define precise(a) cout<<fixed<<setprecision(a)
#define mp make_pair
#define vi vector<lli>
#define vpi vector<pr> 
#define P pair<lli,pr>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define NA(i,s,n) for(lli i=s;i<n;i++)
using namespace std;

lli power(lli x,lli y,lli p) { 
	lli res = 1;	 
	x = x % p; 
	while (y > 0) 
	{ 
		if (y & 1) 
			res = (res*x) % p; 
		y = y>>1; 
		x = (x*x) % p; 
	} 
	return res; 
} 

const lli N = 101, W = 1e5 + 1;
lli dp[N][W], wg[N], val[N], n, w;

lli fun(lli pos, lli rem){
    if(pos==n || rem==0) return 0;
    if(dp[pos][rem]!=-1) return dp[pos][rem];
    lli res = 0;
    if(wg[pos] <= rem) remax(res, val[pos] + fun(pos+1, rem-wg[pos]));
    remax(res, fun(pos+1, rem));
    return dp[pos][rem] = res;
}
void solve(){
    memset(dp, -1, sizeof dp);
    cin >> n >> w;
    NA(i,0,n) cin >> wg[i] >> val[i];
    cout << fun(0, w);
    return;
}
int main(){
    fastIO;
    lli t = 1;
    // cin>>t;
    NA(i,0,t){
        solve();
    }
    return 0;

}


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

int main()
{
    long long int a,b,n,ans=0,sum;
    cin>>n>>a>>b;
    sum=a+b;
    ans=ans+(n/sum)*a;
    ans=ans+min(a,n%sum);
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long mypow(long long x, int n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
int main(){
	int n;
	cin >> n;

	vector<vector<int>> c(10,vector<int>(10,0));
	for(int i=1; i<=9; ++i){
		for(int j=1; j<=9; ++j){
			if(i==j && i<=n) ++c[i][j];
			for(int k=1; k<=6; ++k){
				int sup=mypow(10,k)*(i+1)-10+j;
				for(int l=mypow(10,k)*i+j; l<=sup; l+=10){
					if(l<=n) ++c[i][j];
					else break;
				}
			}
		}
	}

	int ans=0;
	for(int i=1; i<=9; ++i){
		for(int j=1; j<=9; ++j){
			ans += c[i][j]*c[j][i];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline().rstrip('\n')
    

def calc(N, A):
    A.sort()
    M = A[N - 1] + 1
    b = [False for _ in range(M)]
    tmp = -1
    d = set()
    for a in A:
        if a == tmp:
            d.add(a)
            continue
        for i in range(a * 2, M, a):
            b[i] = True
        tmp = a
    n = 0
    for a in A:
        if not a in d:
            n += (0 if b[a] else 1)
    return n

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))


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

ll n,m,a=0;

int main() {
    cin>>n;
    rep(i,n){
        cin>>m;
        m%2==0?:a++;
    }
    cout<<((a%2==0)?"YES":"NO")<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;


ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222


ll a[MAX];


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


  cin >> n;
  rep(i, n) cin >> a[i];
  rep(i, n) {
    if (a[i] < 0) tmp++;
  }
  if (tmp % 2) {
    rep(i, n) {
      ans += llabs(a[i]);
      mi = min(mi, llabs(a[i]));
    }
    ans -= 2*mi;
  }
  else rep(i, n) ans += llabs(a[i]);

  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> t(n);
    int sum = 0;
    rep(i, 0, n) {
        cin >> t[i];
        sum += t[i];
    }
    int m; cin >> m;
    vector<int> p(m), x(m);
    rep(i, 0, m) {
        cin >> p[i] >> x[i];
    }
    rep(i, 0, m) {
        cout << sum - t[p[i] - 1] + x[i] << endl;
    }
}

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

int n,m;
string s,c,c1;

int main(){
  cin >> s >> c;
  cin >> n >> m;
  
  cin >> c1;
  
  if (c1==s)
    n--;
  else
    m--;
  
  cout << n << " " << m << endl; 
}

Measured memory_bytes: 256
import java.util.*

val sc = Scanner(System.`in`)
val N = sc.nextInt()

fun main(args: Array<String>) {
    (1..N).map { if (calc(it)) 1 else 0 }.sum().let(::println)
}

fun calc(n: Int): Boolean {
    var cnt = 0
    for (i in 1..n) {
        if (n % i == 0) {
            cnt++
        }
    }
    return cnt == 8 && n % 2 != 0
}


Measured memory_bytes: 31520
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

MAP = {
    "a" : 0,
    "b" : 1,
    "c" : 2,
}

MAPREV = {
    0 : "A",
    1 : "B",
    2 : "C",
}

def main():
    SS = [input() for _ in range(3)]

    t = 0
    while SS[t]:
        c = SS[t][0]
        SS[t] = SS[t][1:]
        t = MAP[c]

    print(MAPREV[t])

if __name__ == "__main__": main()


Measured memory_bytes: 3064
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int ans = 0;
    for (int i=0; i<3; i++) {
      if (s.charAt(i) == '1') ans++;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0,lcm;
    lcm=c/__gcd(c,d)*d;
    ans+=b-b/c-b/d+b/lcm;
    ans-=a-1-(a-1)/c-(a-1)/d+(a-1)/lcm;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
function main(_stdin) {
    const stdin = _stdin.split('\n').filter(e => e.length).map(Number);
    const len = stdin.shift();

    let min =  stdin[0];
    let diff =  stdin[1] - stdin[0];
    stdin.shift();

    stdin.forEach(e => {
        diff = Math.max(diff, e - min);
        min = Math.min(min, e);
    });

    console.log(diff);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));



Measured memory_bytes: 56960
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
	int x,y,c,w,next,other;
}a[21000];int len,last[2100];
inline void ins(int x,int y,int c,int w)
{
	len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].w=w;
	a[len].next=last[x];last[x]=len;a[len].other=len+1;
	len++;a[len].x=y;a[len].y=x;a[len].c=0;a[len].w=-w;
	a[len].next=last[y];last[y]=len;a[len].other=len-1;
}
int n;
long long d[2100];
int pre[2100];
bool v[2100];
int list[2100];
void BellmanFord(int st)
{
	memset(d,-64,sizeof(d));d[st]=0;
	memset(v,false,sizeof(v));v[st]=true;
	int head=1,tail=2;list[1]=st;
	while(head!=tail)
	{
		int x=list[head];
		for(int k=last[x];k>0;k=a[k].next)
		{
			int y=a[k].y;
			if(a[k].c>0&&d[y]<d[x]+a[k].w)
			{
				d[y]=d[x]+a[k].w;
				pre[y]=k;
				if(v[y]==false)
				{
					v[y]=true;
					list[tail++]=y;
					if(tail==n*2+7)tail=1;
				}
			}
		}
		v[x]=false;
		head++;if(head==n*2+7)head=1;
	}
}
int main()
{
	scanf("%d",&n);
	int st=n*2+1,ed=n*2+6;
	len=0;memset(last,0,sizeof(last));
	for(int i=1;i<=n;i++)
	{
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		ins(st,i,c,0);
		ins(i,n*2+2,0x3f3f3f3f,x+y);
		ins(i,n*2+3,0x3f3f3f3f,-x+y);
		ins(i,n*2+4,0x3f3f3f3f,-x-y);
		ins(i,n*2+5,0x3f3f3f3f,x-y);
	}
	for(int i=1;i<=n;i++)
	{
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		ins(n+i,ed,c,0);
		ins(n*2+2,n+i,0x3f3f3f3f,-x-y);
		ins(n*2+3,n+i,0x3f3f3f3f,x-y);
		ins(n*2+4,n+i,0x3f3f3f3f,x+y);
		ins(n*2+5,n+i,0x3f3f3f3f,-x+y);
	}
	pre[st]=0;BellmanFord(st);
	long long ss=0;
	while(d[ed]!=0xc0c0c0c0c0c0c0c0ll)
	{
		int f=0x3f3f3f3f;
		for(int k=pre[ed];k>0;k=pre[a[k].x])if(a[k].c<f)f=a[k].c;
		for(int k=pre[ed];k>0;k=pre[a[k].x])a[k].c-=f,a[a[k].other].c+=f;
		ss+=d[ed]*f;
		BellmanFord(st);
	}
	printf("%lld\n",ss);
	return 0;
}

Measured memory_bytes: 2248