akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
D = K.bit_length()
to = [[0] * D for _ in range(N)]

for i, a in enumerate(map(int, input().split())):
    to[i][0] = a - 1

for j in range(D - 1):
    for i in range(N):
        h = to[i][j]
        to[i][j+1] = to[h][j]

v = 0
for i in reversed(range(D)):
    x = 1 << i
    if x <= K:
        v = to[v][i]
        K -= x

print(v + 1)

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

int main()
{
    ll N;
    string S;
    cin >> N >> S;
    char prev=' ';
    string res="";
    for(int i=0;i<N;i++){
        if(S[i]!=prev)res+=S[i];
        prev=S[i];
    }
    cout<<res.size()<<endl;
    return 0;
}

Measured memory_bytes: 3732
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

K = I()
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(math.gcd(i,j),k)

print(ans)

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

int main(){
  long long int n,a,b,c,d,e;
  cin>>n>>a>>b>>c>>d>>e;
  long long int x[5]={a,b,c,d,e};
  sort(x,x+5);
  if(n%x[0]==0){
  cout<<n/x[0]+4;
  }
  else{
    cout<<n/x[0]+5;
  }
}


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

int main() {
  int n;
  cin >> n;
  string p[2];
  rep(i, 2) {
    p[i].resize(n);
    rep(j, n) cin >> p[i][j];
  }
  sort(p, p + 2);
  int ans = 0;
  for (; p[0] != p[1]; ans++) next_permutation(p[0].begin(), p[0].end());
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
 
fast();

{
  int a,b;
  cin>>a>>b;
  if(a+b<10)
  {
    cout<<a+b<<endl;
  }
  else
  {
    cout<<"error"<<endl;
  }

}
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int suma,sumb,a_max,b_max,t_max;
int a[MAXN],b[MAXN],n,x,ta,tb,ans;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
      scanf("%d",&x);
      if (i&1){
      a[x]++;
      }
       else {
      	b[x]++; 
	  }
	}
	suma=n/2; sumb=n/2; if (n&1) suma++;
	for (int i=1;i<=100000;i++)
	 if (a_max<a[i]) {
	 	a_max=a[i]; ta=i;
	 }
	 for (int i=1;i<=100000;i++)
	 if (b_max<b[i]) 
	 {
	 	b_max=b[i]; tb=i;
	 }
	 if (ta!=tb)
	printf("%d\n",suma-a_max+sumb-b_max);
	else
	{
		t_max=0;
		for (int i=1;i<=100000;i++)
		if (t_max<a[i]&&i!=ta) {
			t_max=a[i]; 
		}
		ans=suma-t_max+sumb-b_max;
		t_max=0;
		for (int i=1;i<=100000;i++)
		 if (t_max<b[i]&&i!=tb){
		 	t_max=b[i];
		 }
		ans=min(ans,suma-a_max+sumb-t_max);
		printf("%d\n",ans); 
	}
}

Measured memory_bytes: 1024
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

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

void solve(int n, int m){
    vector<int> h(n), w(m);
    rep(i, n) cin >> h[i];
    rep(i, m) cin >> w[i];

    vector<int> hh, ww;
    rep(i, n){
        int len = 0;
        for(int j = i; j < n; j++){
            len += h[j];
            hh.push_back(len);
        }
    }
    rep(i, m){
        int len = 0;
        for(int j = i; j < m; j++){
            len += w[j];
            ww.push_back(len);
        }
    }

    map<int, int> mh, mw;
    rep(i, (int)hh.size()){
        if(mh.find(hh[i]) == mh.end()){
            mh.emplace(hh[i], 0);
        }
        mh[hh[i]]++;
    }
    rep(i, (int)ww.size()){
        if(mw.find(ww[i]) == mw.end()){
            mw.emplace(ww[i], 0);
        }
        mw[ww[i]]++;
    }

    int ans = 0;
    vector<P> H, W;
    for(auto it = mh.begin(); it != mh.end(); it++){
        int x = (*it).first;
        int c = (*it).second;

        if(mw.find(x) != mw.end()){
            ans += c * mw[x];
        }
    }
    cout << ans << endl;
}

signed main(){
    while(true){
        int n, m;
        cin >> n >> m;

        if(n == 0 && m == 0){
            break;
        }
        solve(n, m);
    }

    return 0;
}



Measured memory_bytes: 46280
N, M = map(int, input().split())
A = [input() for i in range(N)]
B = [input() for i in range(M)]

isFind = False
for i in range(N-M+1):
    for j in range(N-M+1):

        isFind2 = True
        for k in range(M):
            for l in range(M):
                if A[i+k][j+l] != B[k][l]:
                    isFind2 = False
                    break
                if(not isFind2):
                    break
        
        if(isFind2):
            isFind = True
            break
    if(isFind):
        break

print("Yes" if isFind else "No")

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  if(a<b){
    for(int i=0;i<b;i++){
      cout << a;
    }
  }
  else{
    for(int i=0;i<a;i++){
      cout << b;
    }
  }
  cout << endl;
  return 0;
}


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

int main() {
    int n, m, a, b;
    ll c;
    cin >> n >> m;
    vector<bool> vrow(n+1,0);
    vector<vector<bool>> visited(n+1,vrow);
    vector<vector<pair<int,ll>>> paths(n+1);
    for (int i=0; i<m; i++) {
        cin >> a >> b >> c;
        paths[a].push_back(make_pair(b,c));
        paths[b].push_back(make_pair(a,c));
    }
    priority_queue<pair<ll,int>> moves;
    for (int i=1; i<=n; i++) {
        vector<ll> dists(n+1,1000000000);
        vector<vector<ll>> links(n+1);
        dists[i] = 0;
        moves.push(make_pair(0,i));
        while (moves.size()>0) {
            pair<ll,int> curr = moves.top();
            moves.pop();
            for (auto j : paths[curr.second]) {
                if (-curr.first+j.second > dists[j.first]) continue;
                if (-curr.first+j.second == dists[j.first]) {
                    links[j.first].push_back(curr.second);
                    continue;
                }
                links[j.first].clear();
                links[j.first].push_back(curr.second);
                dists[j.first] = -curr.first+j.second;
                moves.push(make_pair(curr.first-j.second,j.first));
            }
        }
        for (int j=1; j<=n; j++) for (auto k : links[j]) {
            visited[k][j] = true;
            visited[j][k] = true;
        }
    }
    ll res = m*2;
    for (auto i : visited) for (auto j : i) if (j) res--;
    cout << res/2;
    return 0;
}

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

int main(){
  for(;;){
    int N,M;
    cin >> N >> M;
    // cout << "input!"<<endl;
    vector<int> height(N,0);
    vector<int> width(M,0);
    if (N==0 && M==0) break;
    for(size_t h=0; h<height.size(); h++) cin >> height[h];
    for(size_t w=0; w<width.size(); w++) cin >> width[w];
    // width??????????????¶
    vector<int> comb_width(1501*750,0);
    vector<int> comb_height(1501*750,0);
    for(int i=0; i<M; i++){
      int len = 0;
      for(int j=i; j<M; j++){
        len += width[j];
        comb_width[len]++;
      }
    }
    for(int i=0; i<N; i++){
      int len = 0;
      for(int j=i; j<N; j++){
        len += height[j];
        comb_height[len]++;
      }
    }
    int count = 0;
    for(int i=0; i<1501*750; i++){
      count += comb_height[i]*comb_width[i];
    }
    cout << count << endl;
  }
}

Measured memory_bytes: 11524
import java.io.IOException;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) throws IOException {
//			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//			String W = in.readLine();
//
//			int N= Integer.parseInt(W.split(" ")[0]);
//			int M= Integer.parseInt(W.split(" ")[1]);
		Scanner sc = new Scanner(System.in);
			int N  = sc.nextInt();
			int M= sc.nextInt();
//			int[] A = new int[M];
			int homework =0;

			for(int i=0;i<M;i++) {
				homework+= sc.nextInt();
			}

			int ans = N - homework;

			if(ans >=0) {
				System.out.println(ans);
			}else {
				System.out.println(-1);
			}

	}

}


Measured memory_bytes: 46372
#include<set>
#include<cstdio>
int i,n,v[9999];main(){for(;scanf("%d",&n),n;){std::set<int>t;for(i=1;i<n;i++)v[i]=0,t.insert(i*i%n);for(std::set<int>::iterator s=t.begin(),S=s,T=t.end();s!=T;S=++s)for(;++S!=T;v[i>n/2?n-i:i]+=2)i=*S-*s;for(i=0;i<n/2;)printf("%d\n",v[++i]);}}

Measured memory_bytes: 1300
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define ALL(A)		(A).begin(),(A).end()
#define DUMP(A)    cout<<#A<<"="<<(A)<< endl
#define SIZE(A)    (int)((A).size())
using namespace std;
typedef long long ll;

int main(){
    int n,m;
    int a,b,c,d;
    const int INF=10000000;
    scanf("%d\n%d\n",&n,&m);
    int dist[20][20];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=INF;
        }
    }
    for(int i=0;i<m;i++){
        scanf("%d,%d,%d,%d\n",&a,&b,&c,&d);
        a--;b--;
        dist[a][b]=c;
        dist[b][a]=d;
    }
    int fr,to,y1,y2;
    scanf("%d,%d,%d,%d\n",&fr,&to,&y1,&y2);
    fr--;to--;
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    printf("%d\n",y1-y2-dist[fr][to]-dist[to][fr]);

}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pa;
const int maxn=1e5+10,P=1e9+7;

inline ll rd(){
    ll x=0;char c=getchar();int neg=1;
    while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*neg;
}

struct Mat{
	int n,m,a[3][3];
	Mat(int _n=1,int _m=3){
		n=_n,m=_m;
		CLR(a,0);
	}
}ans,t1,t2;

inline int up(int &a,ll b){a=(a+b)%P;}

inline Mat operator *(Mat a,Mat b){
	Mat r=Mat(a.n,b.m);
	for(int i=0;i<a.n;i++){
		for(int j=0;j<b.m;j++){
			for(int k=0;k<a.m;k++){
				up(r.a[i][j],1ll*a.a[i][k]*b.a[k][j]);
			}
		}
	}return r;
}

int N,M,a[maxn],sum;

inline Mat fpow(Mat a,int b){
	if(!b){
		Mat r=Mat(3,3);
		r.a[0][0]=r.a[1][1]=r.a[2][2]=1;
		return r;
	}
	Mat r=a;b--;
	while(b){
		if(b&1) r=r*a;
		a=a*a,b>>=1;
	}return r;
}



int main(){
    //freopen("","r",stdin);
	N=rd(),M=rd();
	for(int i=1;i<=M;i++) a[i]=rd();
	a[M+1]=N+1;
	t1=Mat(3,3);
	t1.a[0][0]=2,t1.a[0][1]=1,t1.a[0][2]=1;
	t1.a[1][0]=2,t1.a[1][1]=1,t1.a[1][2]=2;
	t1.a[2][0]=1,t1.a[2][1]=0,t1.a[2][2]=1;
	t2=Mat(3,3);
	t2.a[0][0]=1,t2.a[0][1]=1,t2.a[0][2]=1;
	t2.a[1][0]=0,t2.a[1][1]=1,t2.a[1][2]=2;
	t2.a[2][0]=0,t2.a[2][1]=0,t2.a[2][2]=1;
	ans=Mat(1,3);
	ans.a[0][0]=1;
	for(int i=1,j=0;i<=M+1;i++){
		Mat r=fpow(t1,a[i]-j-1);
		if(i==M+1) ans=ans*r;
		else ans=ans*r*t2;
		j=a[i];
	}
	printf("%d\n",ans.a[0][2]);
    return 0;
}

Measured memory_bytes: 640
from collections import Counter

n = int(input())
s_input=Counter([input() for i in range(n)])
m = int(input())
t_input=Counter([input() for i in range(m)])

ans=0
for k,v in s_input.items():
    if k in t_input:
        tmp=v-t_input[k]
    else:
        tmp=v
    ans=max(tmp,ans)

print(max(ans,0))




Measured memory_bytes: 3316
/////////////////////////   _LeMur_
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 100005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

long long k , a , b;

int main(){
    cin>>k>>a>>b;
    if(b - a <= 1)
        cout<<k + 1<<endl;
    else{
        long long n = 1;
        long long x = min(k , a - 1);
        k -= x;
        n += x;
        n += (k / 2) * (b - a);
        n += k % 2;
        cout<<n<<endl;
    }
    return 0;
}


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

int main(void){
  int N, K;
  string S;
  cin >> N >> S >> K;
  for(int i = 0; i < N; i ++){
    if(S[i] != S[K-1]){ S.replace(i, 1, "*");
    }
  }
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 256
#define N (1<<16)
#include <bits/stdc++.h>
using namespace std;

int dp[N];
int w,n,x,sum[N];

bool solve(int x)
{
	memset(dp,0,sizeof(dp));
	dp[0]=0,dp[1]=1;

	for(int i=1,j=0,k=0;i<n;i++)
	{
		for(;w-(sum[i]-sum[j])<i-j-1;j++);
		for(int u=0,v=0;u=w-(sum[i]-sum[k]),v=i-k-1,v?u/v+!!(u%v)<=x:!u;k++);
		dp[i+1]=dp[i]+(dp[k]-dp[j]>0);
	}

	for(int i=n-1;i>=0;i--)
	{
		if(w-(sum[n]-sum[i])<n-i-1) return 0;
		if(dp[i+1]-dp[i]) return 1;
	}
	return 0;
}

int main()
{
	for(;cin>>w>>n,w;)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&x),sum[i]=sum[i-1]+x;
		int Left=1,Right=w-1;
		for(;Left<Right;)
		{
			int mid=(Left+Right)>>1;
			if(solve(mid))
				Right=mid;
			else
				Left=mid+1;
		}
		cout<<Left<<endl;
	}
	return 0;
}

Measured memory_bytes: 1708
(*
ocamlfind ocamlopt -package batteries -linkpkg main.ml -o a.out
*)
open Batteries

let i, j = ref 0, ref 0
let f b = 
        if b then
                (* side effect *)
                (
                        incr i;
                        Printf.printf "Yes\n"
                )
        else
                Printf.printf "No\n"

let () =
        Scanf.sscanf (read_line ()) "%d %d %d" (
                fun _ a b -> 
                        let str = read_line () in
                                String.iter (function 
                                        'a' -> f (!i < a + b)
                                        | 'b' -> 
                                                (* side effect *)
                                                (
                                                        incr j;
                                                        f (!i < a + b && !j <= b)
                                                ) 
                                        | _ -> 
                                                f false
                                ) str
        )


Measured memory_bytes: 5760
#include<cstdio>
#include<algorithm> 
using namespace std;

typedef long long ll;

const int MAXN = 100010;

ll stk[MAXN]; int top;

struct Sequece{
	ll len, sum;
}seq[MAXN << 1];
int tot;

bool operator < (const ll& a, const Sequece& s){
	return a < s.len;
}

ll ans[MAXN];

int main(){
	int N, Q;
	scanf("%d %d", &N, &Q);
	stk[++top] = N; ll qi;
	for (int i = 1; i <= Q; ++i){
		scanf("%lld", &qi);
		while (top && stk[top] >= qi) --top;
		stk[++top] = qi;
	}
	for (int i = 1; i <= stk[1]; ++i)
		seq[++tot].len = i;
	for (int i = 2; i <= top; ++i)
		seq[++tot].len = stk[i];
	seq[tot].sum = 1;
	for (int i = tot; i > stk[1]; --i){
		ll nowlen = seq[i].len, pos = i - 1;
		while (1){
			seq[pos].sum += seq[i].sum * (nowlen / seq[pos].len);
			nowlen %= seq[pos].len;
			if (!nowlen) break;
			pos = upper_bound(seq + 1, seq + 1 + tot, nowlen) - seq - 1;
		}
	}
	for (int i = stk[1]; i >= 1; --i)
		ans[i] = ans[i + 1] + seq[i].sum;
	for (int i = 1; i <= N; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}


Measured memory_bytes: 6272
#include<bits/stdc++.h> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#define mod 1000000007
#define mod2 998244353
#define int long long
#define endl "\n"
#define p_b push_back
#define fastIO ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
template <class T> 
using _ost = tree<
		T, 
		null_type, 
		less<T>, 
		rb_tree_tag, 
        tree_order_statistics_node_update>;
// char alphabet[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
void swap(int* a,int* b){
    int temp = *a;
    *a=*b;
    *b=temp;
}	
int32_t main(){
 	fastIO;
 	int p,n;cin>>p>>n;
 	int a[n];for(int i=0;i<n;i++)cin>>a[i];
 	int ans[n],mini=mod;
 	for(int i=0;i<n;i++){
 		if(i==0){
 			ans[i]=p-max((a[i]-a[n-1]+p)%p,(a[i+1]-a[i]+p)%p);
 		}else if(i==n-1){
 			ans[i]=p-max((a[i]-a[i-1]+p)%p,(a[0]-a[n-1]+p)%p);
 		}else{
 			ans[i]=p-max((a[i]-a[i-1]+p)%p,(a[i+1]-a[i]+p)%p);
 		}
 		mini=min(mini,ans[i]);
 	}
 	cout<<mini<<endl;
} 	

Measured memory_bytes: 3328
import java.util.Scanner;

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

        sc.close();

        if ((a <= 8) && (b <= 8)) {
            System.out.println("Yay!");
        } else {
            System.out.println(":(");
        }
    }
}

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

using namespace std;
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-6
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define mp(a, b) make_pair(a, b)
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define pi acos(-1.0)
const ll maxn = 3e5 + 10;
const ll mod = 1e9 + 7;
signed main()
{
    ll n, r;
    cin >> n >> r;
    if(n < 10){
        cout << r + 100*(10 -n) << endl;
    }else {
        cout << r << endl;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        System.out.println(solve());
    }

    static int solve() {
        int Q = (int) Math.sqrt(M);

        int ans = 1;
        // gを配る
        for (int g = Q; g >= 1; g--) {
            long a = (long)(N-1) * g;
            long b = M - a;

            if( b < 0 ) continue;
            if( b % g != 0 ) continue;
            if( M / g >= N ) ans = Math.max(g, ans);
        }

        // n個配る
        for (int n = N; n <= Q; n++) {
            if( M % n != 0 ) continue;
            int g = M / n;
            ans = Math.max(g, ans);
        }
        return ans;
    }

    static int gcd(int a, int b) {
        while (b > 0) {
            int c = a;
            a = b;
            b = c % b;
        }
        return a;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;


int main(){
    ll N, M;
    cin >> N >> M;
    ll cnt = 0;
    if(N <= M / 2){
        cnt += N;
        M -= (2 * N);
    }else{
        cnt+= (M / 2);
        cout << cnt << endl;
        return 0;
    }
    cnt += (M / 4);
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

void mergesort(long y[], int i, int j);
void merge(long y[], int i, int j);

int main(void)
{
	int k, n;
	long *h, min;
	scanf("%d %d", &n, &k);
	h=(long *)malloc(sizeof(long)*n);
	for (int i = 0; i < n; ++i) scanf("%ld", &h[i]);
	mergesort(h, 0, n-1);
	min=h[k-1]-h[0];
	for (int i = 1; i < n-k+1; ++i) if (h[k+i-1]-h[i]<min) min=h[k+i-1]-h[i];
	printf("%ld\n", min);
	free(h);
	return 0;
}

void mergesort(long y[], int i, int j)
{
	if (i-j == 0)
	{
		return;
	}
	else
	{
		mergesort(y, i, (i+j)/2);
		mergesort(y, (i+j)/2+1, j);
		merge(y, i, j);
		return;
	}
}

void merge(long y[], int i, int j)
{
	int l, r;
	long y2[j];
	l=i;
	r=(i+j)/2+1;
	for (int k = i; k <= j; ++k)
	{
		if (l > (i+j)/2)
		{
			y2[k] = y[r];
			r++;
		} else if (r > j)
		{
			y2[k] = y[l];
			l++;
		} else if (y[l] <= y[r])
		{
			y2[k] = y[l];
			l++;
		} else
		{
			y2[k] = y[r];
			r++;
		}
	}
	for (int k = i; k <= j; ++k) y[k]=y2[k];
	return;
}

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	int r, g, b;
	cin >> r >> g >> b;

	if((100*r + 10*g + b) % 4 == 0) puts("YES");
	else puts("NO");
	
	return 0;
}


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

using namespace std;

int mod(long long a) {
  return a % 2019;
}

int main(void) {
  long long m, n;
  cin >> m >> n;
  long long a, b;
  int ans = 2018;
  for (int i = 0; i < 2019; i++) {
    a = m + i;    
    if (a == n) break;
    for (int j = 0; j < 2019; j++) {
      b = a + j + 1; 
      if (b == n + 1) break;
      if (ans > mod(a * b)) {
      ans = mod(a * b);
     } 
    }
  }
  cout << ans << endl;
  return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> d;
    for (int i = 0; i < n; i++) {
        int d1, d2;
        cin >> d1 >> d2;
        d.emplace_back(d1, d2);
    }
    for (int i = 0; i + 2 < n; i++) {
        if (d[i].first == d[i].second
            && d[i+1].first == d[i+1].second
            && d[i+2].first == d[i+2].second) {
                cout << "Yes" << endl;
                return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
#pragma region Template
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(int i = 0; i < n; i++)
#define RNG(i, a, b) for(int i = a; i < b; i++)
#define RBF(i, v) for(auto& i : v)
#define ALL(x) x.begin(), x.end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;
template<typename T> using VP = vector<pair<T, T>>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = INT64_MAX >> 1;
const int INF = INT_MAX >> 1;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }
#pragma endregion

template<typename T> vector<T> Dijkstra(const T start, const std::vector<std::vector<std::pair<T, T>>>& graph) {
	using namespace std;
	vector<T> mincost(graph.size(), numeric_limits<T>::max()); // i番目のノードまでの最小コスト
	vector<bool> done(graph.size(), false); // i番目のノードまでの最短経路が確定したか
	priority_queue<pair<T, T>, vector<pair<T, T>>, greater<pair<T, T>>> nodes; // 次に最短が確定する候補ノード <コスト，ノード>
	mincost[start] = 0;
	nodes.push(make_pair(0, start));

	// 各ノードまでの最小コストをダイクストラ法で求めていく
	while (!nodes.empty()) {
		pair<T, T> node = nodes.top();
		nodes.pop();

		if (!done[node.second]) {
			done[node.second] = true;
			for (auto& next : graph[node.second]) {
				T cost = node.first + next.first;
				if (mincost[next.second] > cost) {
					mincost[next.second] = cost;
					nodes.push(make_pair(cost, next.second));
				}
			}
		}
	}
	return mincost; // ゴールまでの最小コストを求めるだけならここでreturn
}

signed main()
{
	using LL = long long;
	LL n, m, s, t;
	cin >> n >> m >> s >> t;
	s--; t--;
	vector<vector<pair<LL, LL>>> yen(n), snuuk(n);
	LL i = 0;
	while (i++ < m) {
		LL u, v, a, b;
		cin >> u >> v >> a >> b;
		yen[u - 1].emplace_back(make_pair(a, v - 1));
		yen[v - 1].emplace_back(make_pair(a, u - 1));
		snuuk[u - 1].emplace_back(make_pair(b, v - 1));
		snuuk[v - 1].emplace_back(make_pair(b, u - 1));
	}

	vector<LL> cost_y = Dijkstra(s, yen);
	vector<LL> cost_s = Dijkstra(t, snuuk);

	LL chageCity = n - 1;
	const LL initmoney = static_cast<LL>(1e15);
	vector<pair<LL, LL>> money;
	money.emplace_back(make_pair(initmoney - cost_y[chageCity] - cost_s[chageCity], chageCity));
	chageCity--;
	while (chageCity >= 0) {
		LL mon = initmoney - cost_y[chageCity] - cost_s[chageCity];
		if(mon > money.back().first) money.emplace_back(make_pair(mon, chageCity));
		chageCity--;
	}

	i = 0;
	LL j = money.size() - 1;
	while (i < n) {
		while (money[j].second < i) j--;
		cout << money[j].first << '\n';
		i++;
	}
	return 0;
}


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

struct Graph {
	struct Vertex {
		Vertex() {}
	};
	struct Edge {
		int to;
		Edge(int t) : to(t) {}
		Edge() {}
	};
	int sz;
	vector<Vertex> v;
	vector<vector<Edge>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = Vertex(args...);
	}
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

struct is_Biparite : Graph {
	is_Biparite(int n) : Graph(n) {}
	vector<pair<int, int>> is_biparite() {
		vector<pair<int, int>> res;
		vector<char> color(sz, -1);
		int count[2] = {0, 0};
		auto dfs = [&] (auto f, int v, int c) {
			if (color[v] == c) return true;
			if (color[v] != -1) return false;
			color[v] = c;
			count[c]++;
			for (auto& x: e[v]) {
				if (!f(f, x.to, 1 - c)) return false;
			}
			return true;
		};
		for (int i = 0; i < sz; i++) {
			if (color[i] == -1 && !dfs(dfs, i, 0)) return vector<pair<int, int>>(0);
			if (count[0]) res.emplace_back(count[0], count[1]);
			count[0] = count[1] = 0;
		}
		return res;
	}
};

int main() {
	int V, E;
	cin >> V >> E;
	is_Biparite B(V);
	for (int i = 0; i < E; i++) {
		int a, b; cin >> a >> b; a--; b--;
		B.add_edge(a, b);
		B.add_edge(b, a);
	}
	auto res = B.is_biparite();
	if (res.size() == 0) {
		cout << -1 << endl;
		return 0;
	}
	map<int, int> m;
	int zero = 0;
	vector<pair<int, int>> w;
	for (auto& x: res) {
		int diff = abs(x.first - x.second);
		zero += diff;
		m[diff]++;
	}
	for (auto& x: m) {
		w.emplace_back(x.first*2, x.second);
	}
	vector<int> dp(zero * 2 + 1, -1);
	dp[0] = 0;
	for (auto& x: w) {
		for (int i = 0; i < (int) dp.size(); i++) {
			if (x.first >= 0) {
				if (dp[i] >= 0) {
					dp[i] = x.second;
				} else if (i < x.first || dp[i-x.first] <= 0) {
					dp[i] = -1;
				} else {
					dp[i] = dp[i-x.first] - 1;
				}
			}
		}
	}
	for (int i = 0; i <= zero; i++) {
		if (dp[zero+i] >= 0 || dp[zero-i] >= 0) {
			long long a = V + i;
			long long b = V - i;
			cout << a * b / 4 - E << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 9684
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

typedef struct data
{
	long long int x1;
	long long int y1;
	long long int d1;
	long long int x2;
	long long int y2;
	long long int d2;
} data;

int main()
{
	long long int n, K;
	cin >> n >> K;
	vector<data> v;
	long long int x[101], y[101], d[101];
	for(int i = 0; i < 2 * n; i += 2){
		cin >> x[i] >> y[i] >> d[i];
		cin >> x[i + 1] >> y[i + 1] >> d[i + 1];
		data tmp;
		tmp.x1 = x[i];
		tmp.x2 = x[i + 1];
		tmp.y1 = y[i];
		tmp.y2 = y[i + 1];
		tmp.d1 = d[i];
		tmp.d2 = d[i + 1];
		v.push_back(tmp);
	}
	sort(x, x + 2 * n);
	sort(y, y + 2 * n);
	sort(d, d + 2 * n);
	int result[110][110][110] = {};
	for(int i = 0; i < n; i++){
		data tmp = v[i];
		long long int x1 = lower_bound(x, x + 2 * n, tmp.x1) - x;
		long long int x2 = lower_bound(x, x + 2 * n, tmp.x2) - x;
		long long int y1 = lower_bound(y, y + 2 * n, tmp.y1) - y;
		long long int y2 = lower_bound(y, y + 2 * n, tmp.y2) - y;
		long long int d1 = lower_bound(d, d + 2 * n, tmp.d1) - d;
		long long int d2 = lower_bound(d, d + 2 * n, tmp.d2) - d;
		result[x1][y1][d1]++;
		result[x1][y2][d1]--;
		result[x2][y1][d1]--;
		result[x2][y2][d1]++;
		result[x1][y1][d2]--;
		result[x1][y2][d2]++;
		result[x2][y1][d2]++;
		result[x2][y2][d2]--;
	}
	for(int i = 0; i < 110; i++){
		for(int j = 0; j < 110; j++){
			for(int k = 1; k < 110; k++){
				result[k][i][j] += result[k - 1][i][j];
			}
		}
	}
	for(int i = 0; i < 110; i++){
		for(int j = 0; j < 110; j++){
			for(int k = 1; k < 110; k++){
				result[i][k][j] += result[i][k - 1][j];
			}
		}
	}
	for(int i = 0; i < 110; i++){
		for(int j = 0; j < 110; j++){
			for(int k = 1; k < 110; k++){
				result[i][j][k] += result[i][j][k - 1];
			}
		}
	}
	// for(int i = 0; i < 10; i++){
	// 	for(int j = 0; j < 10; j++){
	// 		for(int k = 0; k < 10; k++){
	// 			cout << x[i] << " " << y[j] << " " << d[k] << " " << result[i][j][k] << endl;
	// 		}
	// 	}
	// }
	long long int ans = 0;
	for(int i = 0; i < 110; i++){
		for(int j = 0; j < 110; j++){
			for(int k = 0; k < 110; k++){
				if(result[i][j][k] >= K){
					ans += (x[i + 1] - x[i]) * (y[j + 1] - y[j]) * (d[k + 1] - d[k]);
					// cout << i << " " << j << " " << k << result[i][j][k] << endl;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8340
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main() {
  int n;
  cin >> n;
  if(n == 1){
    cout << 1 << endl;
    return 0;
  }
  vector<pair<ll, ll>> vec;
  rep(i, n){
    ll a, b;
    cin >> a >> b;
    vec.push_back(make_pair(a, b));
  }
  ll smallest = 100;
  rep(i, n-1){
    for(ll j=i+1; j<n; j++){
      ll p = vec[j].first - vec[i].first;
      ll q = vec[j].second - vec[i].second;
      ll cost = 0;
      vector<ll> flag(n, 0);
      while(find(all(flag), 0) != flag.end()){
        ll index = find(all(flag), 0) - flag.begin();
        queue<vector<ll>> que;
        vector<ll> tmp = {vec[index].first, vec[index].second, index};
        que.push(tmp);
        while(!que.empty()){
          vector<ll> tmpv = que.front();
          que.pop();
          ll x = tmpv[0], y = tmpv[1], ind = tmpv[2];
          flag[ind] = 1;
          for(ll k=0; k<n; k++){
            if(flag[k] == 0){
              if((vec[k].first - x == p && vec[k].second - y == q) || (vec[k].first - x == -p && vec[k].second - y == -q)){
                vector<ll> t = {vec[k].first, vec[k].second, k};
                que.push(t);
              }
            }
          }
        }
        cost++;
      }
      smallest = min(smallest, cost);
    }
  }
  cout << smallest << endl;
  return 0;
}
  
  
  
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/
int digits(ll m){
    int re = 0;
    while(m > 0){
        m /= 10;
        re++;
    }
    return re;
}
int main(){
    rep(i, 3){
        string t; cin >> t;
        cout << t[0];
    }
    cout << endl;
}

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

int main(){
  int n,m,l;
  cin>>n>>m>>l;
  int a[n][m],b[m][l];
  for(int i=0;i<n;i++){
    for(int i1=0;i1<m;i1++){
      cin>>a[i][i1];
    }
  }
  for(int i=0;i<m;i++){
    for(int i1=0;i1<l;i1++){
      cin>>b[i][i1];
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<l;j++){
      long long c=0;
      for(int k=0;k<m;k++){
	c+=a[i][k]*b[k][j];
      }
      if(j) cout<<" ";
      cout <<c;
    }
    cout<<endl;
  }
	
      
      
  return 0;
}



Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

template <ll Mod>
struct modint {
  ll n;

  modint(const ll x = 0) : n(x) { while (n < 0) n += Mod; n %= Mod; }
  modint operator+(const modint r) const { return modint(*this) += r; }
  modint operator-(const modint r) const { return modint(*this) -= r; }
  modint operator*(const modint r) const { return modint(*this) *= r; }
  modint operator/(const modint r) const { return modint(*this) /= r; }
  modint &operator+=(const modint r) {
    n += r.n;
    if (n >= Mod) n -= Mod;
    return *this;
  }
  modint &operator-=(const modint r) {
    if (n < r.n) n += Mod;
    n -= r.n;
    return *this;
  }
  modint &operator*=(const modint r) { n = n * r.n % Mod; return *this; }
  modint &operator/=(const modint r) { return *this *= r.inv(); }
  modint pow(ll x) const {
    modint<Mod> ret(1), tmp(*this);
    while (x) {
      if (x&1) ret *= tmp;
      tmp *= tmp;
      x >>= 1;
    }
    return ret;
  }
  modint inv() const { return pow(Mod-2); }
  friend ostream& operator<<(ostream& os, const modint& obj) { return os << obj.n; }
  friend istream& operator>>(istream& is, modint& obj) { ll t; is >> t; obj = modint(t); return is; }
};
constexpr ll mod = 1000000007;
using mint = modint<mod>;

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

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

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) {
    cin >> a[i];
  }

  map<ll, ll> lcm_p;
  rep(i, n) {
    auto ma = PrimeFactorization(a[i]);

    for (auto&& j : ma) {
      lcm_p[j.first] = max(lcm_p[j.first], j.second);
    }
  }

  mint lcm(1);
  for (auto&& i : lcm_p) {
    lcm *= mint(i.first).pow(i.second);
  }

  mint ans(0);
  rep(i, n) {
    ans += lcm/mint(a[i]);
  }

  cerr << lcm << endl;
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	vector<int> sci(4);
	vector<int> soc(2);
	for (int i = 0; i < 4; i++) {
		cin >> sci[i];
	}
	for (int i = 0; i < 2; i++) {
		cin >> soc[i];
	}
	sort(sci.rbegin(), sci.rend());
	sort(soc.rbegin(), soc.rend());
	cout << sci[0] + sci[1] + sci[2] + soc[0] << endl;
	return 0;
}


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

long long solve(long n, long m){
    if(n==0){
        if(m==0){
            return 1;
        }else{
            return 0;
        }
    }else {
        return (n * solve(m,n-1)) % (long long)(1e9 + 7);
    }
}

int main()
{
    int N,M;
    cin >> N >> M;
    cout << (solve(N,M) + solve(M,N)) % (long long)(1e9 + 7) << endl;
}


Measured memory_bytes: 3328
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n,i;
  cin >> n >> i;
  cout << n - i + 1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s,t,u;
  int a,b;
  cin>>s>>t>>a>>b>>u;
  if (u==s)
    cout<<a-1<<" "<<b<<endl;
  else if (u==t)
    cout<<a<<" "<<b-1<<endl;
return 0;  
}

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

const int MAXN = 102;
const int MAXV = 1e5 + 2;
const ll INF = 1e18;
ll dp[MAXN][MAXV], val[MAXN], wt[MAXN];

int main() {
    for(int i = 0; i < MAXN; i++) {
        for(int j = 0; j < MAXV; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    int n;
    ll w;
    cin >> n >> w;
    for(int i = 1; i <= n; i++)
        cin >> wt[i] >> val[i];
    for(int i = 1; i <= n; i++) {
        for(int v = 0; v < MAXV; v++) {
            dp[i][v] = dp[i - 1][v];
            if(v - val[i] >= 0)
                dp[i][v] = min(dp[i][v], dp[i - 1][v - val[i]] + wt[i]);
        }
    }
    for(int v = MAXV - 1; v >= 0; v--) {
        if(dp[n][v] <= w) {
            cout << v << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 80000
#include <time.h>

#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <bitset>
#include <iterator>
#include <deque>
#include <string>
#include <queue>
#include <omp.h>
#include <fstream>   // ifstream, ofstream
typedef int64_t ll;
using namespace std;
const ll INF=1e10;


int main(){
	ll h,w;
	cin>>h>>w;
	ll **left_ob= new ll*[h];
	ll **right_ob= new ll*[h];
	ll **top_ob= new ll*[h];
	ll **bottom_ob= new ll*[h];
	bool **ob_exist = new bool*[h];
	for(ll i1=0;i1<h;i1++){
		left_ob[i1] = new ll[w];
		right_ob[i1] = new ll[w];
		top_ob[i1] = new ll[w];
		bottom_ob[i1] = new ll[w];
		ob_exist[i1] = new bool[w];

	}

	for(ll i1=0;i1<h;i1++){
		for(ll i2=0;i2<w;i2++){
			char c;
			cin>>c;
			if(c=='.'){
				ob_exist[i1][i2]=false;
			}else{
				ob_exist[i1][i2]=true;
			}
		}
	}
	ll last_ob;
	for(ll i1=0;i1<h;i1++){
		last_ob = 0;

		for(ll i2=0;i2<w;i2++){
			if(ob_exist[i1][i2]){
				last_ob=i2+1;
			}else{
				left_ob[i1][i2]=last_ob;
			}
		}
	}
	for(ll i1=0;i1<h;i1++){
		last_ob=w-1;

		for(ll i2=w-1;i2>=0;i2--){
			if(ob_exist[i1][i2]){
				last_ob=i2-1;
			}else{
				right_ob[i1][i2]=last_ob;
			}
		}
	}


	for(ll i2=0;i2<w;i2++){
		last_ob = 0;

		for(ll i1=0;i1<h;i1++){
			if(ob_exist[i1][i2]){
				last_ob =i1+1;
			}else{
				top_ob[i1][i2]=last_ob;
			}
		}
	}
	for(ll i2=0;i2<w;i2++){
		last_ob=h-1;

		for(ll i1=h-1;i1>=0;i1--){
			if(ob_exist[i1][i2]){
				last_ob=i1-1;
			}else{
				bottom_ob[i1][i2]=last_ob;
			}
		}
	}
	ll ans=0;
	for(ll i1=0;i1<h;i1++){
		for(ll i2=0;i2<w;i2++){
			if(ob_exist[i1][i2]){
				continue;
			}
			ll c_ans = (i1-top_ob[i1][i2])+(bottom_ob[i1][i2]-i1)+(right_ob[i1][i2]-i2)+(i2-left_ob[i1][i2])+1;
			if(c_ans > ans){
				ans=c_ans;
			}
		}
	}
	cout<<ans<<endl;


}


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

int main(int argc, char const* argv[]) {
	int N;
	scanf("%d", &N);
	int A[2][100];
	int lowerSum = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
			if (i == 1) lowerSum += A[1][j];
		}
	}
	int ans = 0;
	int upperSum = 0;
	for (int i = 0; i < N; i++) {
		if (i > 0) lowerSum -= A[1][i - 1];
		upperSum += A[0][i];
		for (int j = 0; j < i + 1; j++) {
			ans = max(ans, upperSum + lowerSum);
		}
	}
	printf("%d", ans);
	return 0;
}


Measured memory_bytes: 3836
#include<iostream>
#include<string.h>
#define loop(i,a,b) for(int i=a;i<b;++i)
#define rep(i,b) loop(i,0,b)
using namespace std;
    int m[7]={};
class DICE{
public :
void set_DISE(){
    rep(i,6){
        cin>>m[i];
    }
}
void Rotate(char(dir)){
    if (dir=='N'){
        m[6]=m[0];
        m[0]=m[1];
        m[1]=m[5];
        m[5]=m[4];
        m[4]=m[6];
    }
    else if(char(dir)=='E'){
        m[6]=m[0];
        m[0]=m[3];
        m[3]=m[5];
        m[5]=m[2];
        m[2]=m[6];
    }
    else if(char(dir)=='W'){
        m[6]=m[0];
        m[0]=m[2];
        m[2]=m[5];
        m[5]=m[3];
        m[3]=m[6];
    }    
    else{
        m[6]=m[0];
        m[0]=m[4];
        m[4]=m[5];
        m[5]=m[1];
        m[1]=m[6];
    }
}
};
int main(){
    DICE d;
    string dir;
    d.set_DISE();
    cin>>dir;
    rep(i,dir.size()){
        d.Rotate(dir[i]);
    }
    cout<<m[0]<<endl;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,A,B;
const ll mo=998244353;

const int NUM_=21000001;
ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
ll comb(ll N_, ll C_) {
	if (fact[0]==0) {
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>A>>B;
	
	if(B==0) return _P("1\n");
	
	ll ret=0;
	if(B+A==N) {
		x=B-1,y=A;
		ret=(comb(x+y,y)+mo-comb(x+y,y-1))%mo;
	}
	for(k=0;N-B-k>0;k++) if(A-k>=0) {
		x=B-1,y=k;
		ll pat=(comb(x+y,y)+mo-comb(x+y,y-1))%mo;
		ret+=pat*hcomb(A-k+1,N-B-k-1)%mo;
		
	}
	
	cout<<ret%mo<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 492416
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll fc[555555]={1ll},nv[555555]={1ll};

ll rwpw(ll a, ll p = MOD-2){
	ll ret = 1ll;
	while(p){
		if(p&1){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p /= 2;
	}
	return ret;
}

ll c(int n, int k){
	ll ret = fc[n];
	mul_mod(ret,nv[k]);
	mul_mod(ret,nv[n-k]);
	return ret;
}

ll p(int n, int k){
	ll ret = fc[n];
	mul_mod(ret,nv[n-k]);
	return ret;
}

int main(void){
	int n,m,i;
	ll ans = 0ll, tmp;
	std::cin >> n >> m;
	for(i=1; i<=m; ++i){
		fc[i] = fc[i-1]*i%MOD;
		nv[i] = rwpw(fc[i]);
	}
	for(i=0; i<=n; ++i){
		tmp = c(n,i);
		mul_mod(tmp,p(m,i));
		mul_mod(tmp,p(m-i,n-i));
		mul_mod(tmp,p(m-i,n-i));
		add_mod(ans,((i&1)?(MOD-tmp):(tmp)));
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 11404
A=[]
for i in range(5):
  A.append(input())
A.sort(key=lambda x:(int(x[-1])-1)%10)
ans=0
A=[int(x) for x in A]
for i in range(1,5):
  ans+=A[i]//10*10
  ans+=0 if A[i]%10==0 else 10
print(ans+A[0])

Measured memory_bytes: 3064
# union by sixe
class DisjointSet:
    def __init__(self, size):
        self.size = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.size[x] = 1

    def same(self, x, y):
        return self.findSet(x) == self.findSet(y)

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.size[x] > self.size[y]:
            self.p[y] = x
            self.size[x] += self.size[y]
        else:
            self.p[x] = y
            self.size[y] += self.size[x]
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

N, M = map(int, input().split())
ds = DisjointSet(N+1) 
stack = []
ans = [N*(N-1)//2]
for m in range(M):
    a, b = map(int, input().split())
    stack += [(a, b)]
for m in range(M):
    a, b = stack.pop()
    if ds.same(a, b):
        ans += [ans[-1]]
    else:
        ans += [ans[-1] - ds.size[ds.findSet(a)] * ds.size[ds.findSet(b)]]
        ds.unite(a, b)
ans = ans[::-1]
for i in range(1, M+1):
    print(ans[i])


Measured memory_bytes: 93432