akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cmath>
#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
#include<set>
//#include<map>
//#include<list>

using namespace std;
using LLI = long long int;

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//int gcd(int x, int y) {
//	int tmp, r;
//	if (x < y) {
//		tmp = x;
//		x = y;
//		y = tmp;
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//long nCr(int n,int r) {
//	long ans = 1;
//	for (int i = n; i > n - r;i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1;i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

int main(void) {
	int K;
	string S;
	cin >> S >> K;
	vector<string>vec;
	for (int i = 0; i < min(5, (int)S.size());i++) {
		for (int j = 0; j < S.size() - i;j++) {
			vec.push_back(S.substr(j,i + 1));
		}
	}
	sort(vec.begin(),vec.end());
	unique(vec.begin(),vec.end());
	cout << vec[K - 1] << endl;
}

Measured memory_bytes: 1660
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll mod=1e9+7;
ll n,h,d;
ll fac[maxn],sum[maxn];
ll fpow(ll a,ll k){
    ll res=1;
    while(k){
        if(k&1)
            res=res*a%mod;
        a=a*a%mod;
        k/=2;
    }
    return res;
}
ll inv(ll a){
    return fpow(a,mod-2);
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>h>>d;
    ll t=1;//n的阶乘
    ll s=1;//n的阶乘前缀和
    for(ll i=2;i<=n;++i){
        t=t*i%mod;
        s=(s+t)%mod;
    }
    fac[0]=inv(s);//(1/(1+2!+...+n!))
    sum[0]=fac[0];
    for(ll i=1;i<=h;++i){
        ll u=(sum[i-1]-(i>d?sum[i-d-1]:0)+mod)%mod;
        fac[i]=u*s%mod;//fac[1]=sum[0]*s=1
        sum[i]=(sum[i-1]+fac[i])%mod;//sum[1]=sum[0]+fac[1]
    }
    for(ll i=n;i>=1;--i)fac[h]=fac[h]*i%mod;
    cout<<fac[h];
}


Measured memory_bytes: 16000
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner scanner = new Scanner(System.in);
        String S = scanner.next();
        String Sn = "";
        String x = "x";
        
        for(int i=0; i<S.length(); i++){
            
            Sn += x;
            
        }


        System.out.println(Sn);
    }
}


Measured memory_bytes: 23892
import math
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)

    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'setwise coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())

Measured memory_bytes: 150536
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, K: int, p: "List[int]"):
    p.sort()
    print(sum(p[:K]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, p)


if __name__ == '__main__':
    main()


Measured memory_bytes: 67172
#include <iostream>

using namespace std;

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

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

    int a = 0;
    int ma = -1000000000;
    for(int j=n-1;j>=0;j--){
        if(r[j] > a){
            a = r[j];
            for(int i=j-1;i>=0;i--){
                if(a - r[i] > ma){
                    ma = -1000000000;
                    //cout << a << " - "  << r[i] << endl;
                    ma = a-r[i];
                }
            }
        }
    }
    cout << ma << endl;
}

Measured memory_bytes: 1940
#include <iostream>
#include<string>

using namespace std;
int main()
{
	int k = 0;
	string S;
	string T;
	cin >> S;
	cin >> T;
	for (int i = 0;i < S.size();i++) {
		if (S[i] != T[i]) {
			T[i] = S[i];
			k++;
		}

	}

	cout << k;

}

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

#define ALL(v) (v).begin(),(v).end()

using namespace std ;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;




int main()
{
  int a, b ;
  cin >> a >> b ;
  
  cout <<max({a+b, a-b,a*b})<<endl ;
    return 0 ;
}

/*　吾輩はやれば出来る子である。 
　　　　∩∩ 
　　　（´･ω･） 
　　 ＿|　⊃／(＿＿_ 
　／　└-(＿＿＿_／ 
　￣￣￣￣￣￣￣ 
　やる気はまだない 

　　 ⊂⌒／ヽ-、＿_ 
　／⊂_/＿＿＿＿ ／ 
　￣￣￣￣￣￣￣　　*/

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

int xl,yl,xr,yr,n,m,q,sx,sy;
char s1[200010],s2[200010];

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	scanf("%d%d",&sx,&sy);
	scanf("%s%s",s1+1,s2+1);
	xl=1,xr=n,yl=1,yr=m;
	for (int i=q; i; i--)
	{
		if (s1[i]=='L') yl++; else
		if (s1[i]=='R') yr--; else
		if (s1[i]=='D') xr--; else xl++;
		if (xl>xr||yl>yr) return puts("NO"),0;
		if (i>1)
		{
			if (s2[i-1]=='L') yr=min(yr+1,m); else
			if (s2[i-1]=='R') yl=max(yl-1,1); else
			if (s2[i-1]=='U') xr=min(xr+1,n); else xl=max(xl-1,1);
		}
	}
	if (sx>=xl&&sx<=xr&&sy>=yl&&sy<=yr) puts("YES"); else puts("NO");
	return 0;
}

Measured memory_bytes: 640
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
#define rep(i,n) for (int i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

/*
#include <math.h>
int standerd = int(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

ll K;
ll cnt[10][100];
ll maxCnt[10][100];
ll total;
    
int main(){


    
    cin >> K;
    int keta;
    if(K<10){
        cout << K << endl;
    }else{
        maxCnt[0][1]=1;
        for( int ni = 0 ; ni <=9 ; ni++ ){
            cnt[ni][1]=1;
            maxCnt[ni][1]=1;
        }
        total = 9;
        
        keta = 2;
        int val;
        val = 1;
        while(1){
            cnt[0][keta]=cnt[0][keta-1]+cnt[1][keta-1];
            for( val = 1 ; val <=9 ; val++ ){
                if(val<9){
                    cnt[val][keta]=cnt[val-1][keta-1]+cnt[val][keta-1]+cnt[val+1][keta-1];
                }else{
                    cnt[val][keta]=cnt[val-1][keta-1]+cnt[val][keta-1];                
                }
                //cout << keta << " " << val << " = " << cnt[val][keta] << endl;
                maxCnt[val][keta]=total+cnt[val][keta];
                if(maxCnt[val][keta]>= K) break;
                total=maxCnt[val][keta];
                //cout << total << endl;
            }
            if(maxCnt[min(9,val)][keta] >= K) break;
            keta+=1;
        }
        //cout << cnt[val][keta] << endl;
        //cout << minCnt[val][keta] << endl;
        //cout << maxCnt[val][keta] << endl;

        int now;
        int left=0;
        left = K - total;
        cout << val;
        keta = keta -1;
        while(keta>0){
            //cout << "-----" << endl;
            //cout << left << endl;
            //cout << cnt[val-1][keta] << endl;
            //cout << cnt[val][keta] << endl;
            //cout << cnt[val+1][keta] << endl;
            if(val>0){
                if(left <= cnt[val-1][keta]){
                    val = val - 1;
                }else{
                    left -= cnt[val-1][keta];
                    if(left <= cnt[val][keta]){
                        val = val;
                    }else{
                        left -= cnt[val][keta];
                        val = val + 1;
                    }
                }
            }else{
                if(left <= cnt[val][keta]){
                    val = val;
                }else{
                    left -= cnt[val][keta];
                    val = val + 1;
                }
            }
            cout << val;
            keta = keta -1;
        }
    }
}

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

using namespace std;
typedef long long ll;
#define MOD 1000000007

int main()
{

  ll n, m;
  cin >> n >> m;
  vector<set<ll>> routes(n + 1, set<ll>{});

  for (auto i = 0; i < m; i++)
  {
    ll a, b;
    cin >> a >> b;
    routes[a].insert(b);
    routes[b].insert(a);
  }

  vector<ll> marks(n + 1, -1);
  set<ll> visited{};
  queue<ll> q = {};
  // pairは、いまいる, どこから来た とする

  q.push(1);
  visited.insert(1);

  ll cnt = 0;
  while (!q.empty())
  {
    auto size = q.size();
    for (auto i = 0; i < size; i++)
    {
      auto cur = q.front();
      q.pop();

      for (auto next : routes[cur])
      {
        if (visited.count(next) == 0)
        {
          visited.insert(next);
          q.push(next);
          marks[next] = cur;
          cnt++;
        }
      }
    }
  }

  if (cnt < n - 1)
  {
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
  for (auto i = 2; i <= n; i++)
  {
    cout << marks[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 33012
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N; cin >> N;
    vector<pair<int,int>> P(N);
    rep(i,N) {
        int x,y; cin >> x >> y;
        P.at(i) = {x,y};
    }
    map<pair<int,int>, int> M;
    
    for (int i = 0; i < N-1; i++) {
        for (int j = i + 1; j < N; j++) {
            int a1 = P[i].first;
            int a2 = P[j].first;
            int b1 = P[i].second;
            int b2 = P[j].second;
            M[{a1 - a2, b1 - b2}]++;
            M[{a2 - a1, b2 - b1}]++;
        }
    }
    int ma = 0;
    for (auto [k,v] : M) if (ma < v) ma = v;
    cout << N - ma << endl;
}


Measured memory_bytes: 3784
unittest
{
	assert( [ "1" ].parse.expand.solve == "6.28" );
	assert( [ "73" ].parse.expand.solve == "458.67" );
}



import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto r = input.front.to!( long );
	return tuple( r );
}

auto solve( long r )
{
	return format( "%0.2f", 2 * r * PI );
}


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

int main(){
    int a, b, c;
    char comma;
    int hishi, tyou;
    hishi = 0;
    tyou = 0;
    while(cin >> a >> comma >> b >> comma >> c){
        if(a == b){
            hishi++;
        }else if(a*a + b*b == c*c){
            tyou++;
        }
    }
    cout << tyou << endl;
    cout << hishi << endl;
}

Measured memory_bytes: 0
from statistics import mean, median,variance,stdev
import sys
import math

x = input().split()
#y = input().split()
a= []
for i in range(len(x)):
    a.append(int(x[i]))

if a[1]-a[2]>=0: print("delicious")
elif a[2]-a[1] <= a[0] :print("safe")
else: print("dangerous")

Measured memory_bytes: 5148
#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#define ll long long 
#define int long long
using namespace std;
const int maxn=500010, inf=1e9, mod=998244353;
int n, a, b, K, ans;
int fac[maxn], inv[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(!b) return x=1, y=0, a;
    int ans=exgcd(b, a%b, x, y);
    ll t=x; x=y; y=t-a/b*y;
    return ans;
}

inline int power(int a, int b)
{
	int ans=1;
	for(;b;b>>=1, a=1ll*a*a%mod)
	if(b&1) ans=1ll*ans*a%mod;
	return ans;
}

inline int C(int n, int m){return (n<m)?0:1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}

signed main()
{
//	freopen("1.out", "w", stdout);
	read(n); read(a); read(b); read(K);
	fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=power(fac[n], mod-2); for(int i=n;i;i--) inv[i-1]=1ll*inv[i]*i%mod; 
	int x, y; int d=exgcd(a, b, x, y); 
//	printf("%lld %lld %lld\n", d, x, y);
	int tmp=K;	
	if(tmp%d) return puts("0"), 0;
	int tmpx=x*tmp/d, tmpy=y*tmp/d;
//		printf("tmp:%lld %lld %lld\n", tmpx, tmpy, tmp);
	int TMP=tmpx/(b/d);
	tmpx-=TMP*(b/d), tmpy+=TMP*(a/d);
//		printf("l:%lld tmpx:%lld tmpy:%lld\n", l, tmpx, tmpy);
	for(;tmpx<=n && tmpy>=0;)
//		printf("tmpx:%lld tmpy:%lld %lld\n", tmpx, tmpy, ans), 
	{
		if(tmpx>=0 && tmpy<=n)
		ans=(ans+C(n, tmpx)*C(n, tmpy))%mod;
		tmpx+=b/d, tmpy-=a/d;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int a[N];
  for(int i=0;i<N;i++) cin>>a[i];
  int s=0;
  for(int i=0;i<N;i++){
    s+=a[i];
  }
  cout<<s-N<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
	int n; cin >> n;
	vector<int> a(n),b(n);
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> b[i];
	vector<vector<vector<int>>> bisum(29,vector<vector<int>>(2));
	rep(i,n){
		int sum = 0;
		rep(bit,29){
			bisum[bit][b[i]>>bit & 1].push_back((1<<bit)-sum);
			if(b[i]>>bit & 1) sum += 1<<bit;
		}
	}
	rep(i,29) rep(j,2) sort(all(bisum[i][j]));
	vector<int> acc(29,0);
	rep(i,n){
		int sum = 0;
		rep(bit,29){
			int t = a[i]>>bit & 1;
			acc[bit] += bisum[bit][1-t].end() - upper_bound(all(bisum[bit][1-t]),sum);
			acc[bit] += upper_bound(all(bisum[bit][t]),sum) - bisum[bit][t].begin();
			if(t) sum += 1<<bit;
		}
	}
	int ans = 0;
	rep(bit,29){
		if(acc[bit] & 1) ans += 1<<bit;
	}
	cout << ans << endl;
}

Measured memory_bytes: 31208
#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
 
int main(){
	int n;
	cin>>n;
	vector<int> a(n),b(n),c(n);
	for(int i=0;i<n;i++){  
        cin>>a[i]>>b[i]>>c[i];
    } 
	vector<vector<int> > dp(n,vector<int>(3,-INF));
	dp[0][0]=a[0];
	dp[0][1]=b[0];
	dp[0][2]=c[0];
	
	for(int i=1;i<n;++i){
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
	}
	cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<endl;
	return 0;
}

Measured memory_bytes: 6912
#include<iostream>
using namespace std;
int main(){
    int team[100];
    for(int i=0;i<100;i++)team[i]=0;
    int n;
    cin>>n;
    int m=(n*(n-1))/2;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(c==d){
            team[a-1]++;
            team[b-1]++;
        }
        else if(c>d)team[a-1]+=3;
        else team[b-1]+=3;
    }

    int rnk[100],cnt=0;
    int ranking=1;
    while(cnt<n){
        int mxm=-100;
        int cpycnt=cnt;
        for(int j=0;j<n;j++){
            mxm=max(mxm,team[j]);
        }
        if(mxm==-1)break;
        for(int j=0;j<n;j++){
            if(mxm==team[j]){
                cnt++;
                team[j]=-1;
                rnk[j]=ranking;
            }
        }
        ranking+=cnt-cpycnt;
    }
    for(int i=0;i<n;i++)cout<<rnk[i]<<endl;

    return 0;
}

Measured memory_bytes: 1160
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc078/tasks/abc078_b

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    X, Y, Z = map(int, input().split())
    ans = (X - Z) // (Y + Z)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

//a^b % MOD
long long mod_pow(ll a,ll b){
	long long ret = 1;
	long long c = a;
	for(int i = 0;i <= 60;i++){
		if(b & (1LL << i))ret = (ret * c) % MOD;
		c = (c * c) % MOD;
	}
	return ret;
}

//ａをbで割る
long long mod_div(long long a,long long b){
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}

#define MAX_K 333333
vector<long long> fact(MAX_K);
long long combination(long long n, long long r){
    ll bunbo = 1;
    ll bunshi = 1;

    REP(i, r){
        bunbo = bunbo * (n - i) % MOD;
        bunshi = bunshi * (i + 1) % MOD;
    }

    return mod_div(bunbo, bunshi);
}

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

    ll n, a, b;cin >> n >> a >> b;
    ll ans = (mod_pow(2, n) + MOD - 1) % MOD;

    ans = (ans + MOD - combination(n, a)) % MOD;
    ans = (ans + MOD - combination(n, b)) % MOD;

    cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2816
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
	double point[30][2],s = 0;
	int i;
	for(i=0;;i++){
		if(scanf("%lf,%lf",&point[i][0],&point[i][1]) == EOF){break;}
	}
	for(int j=1; j<i-1; j++){
		double z,a,b,c;
		a = sqrt((point[j][0]-point[0][0])*(point[j][0]-point[0][0])+(point[j][1]-point[0][1])*(point[j][1]-point[0][1]));
		b = sqrt((point[j+1][0]-point[0][0])*(point[j+1][0]-point[0][0])+(point[j+1][1]-point[0][1])*(point[j+1][1]-point[0][1]));
		c = sqrt((point[j+1][0]-point[j][0])*(point[j+1][0]-point[j][0])+(point[j+1][1]-point[j][1])*(point[j+1][1]-point[j][1]));
		z = (a+b+c)/2;
		s+=sqrt(z*(z-a)*(z-b)*(z-c));
	}
	printf("%.6lf\n",s);
	return 0;
}

Measured memory_bytes: 0
// Problem : C - Forbidden List
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int X, N;
	cin >> X >> N;
	set<int> st;
	for(int i = 1; i<=N; i++){
		int n;
		cin >> n;
		st.insert(n);
	}
	int ans = 10000;
	for(int x = -1000; x<=1000; x++){
		if(!st.count(x) && abs(ans-X) > abs(X-x)){
			ans = x;
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(){
  int a[30], i, n;

  for(i = 0; i<30; i++){
    a[i] = 1;
  }

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

  for(i=0;i<30;i++){
    if(a[i]) printf("%d\n", i+1);
  }

  return 0;
}

Measured memory_bytes: 592
#ABC061
N,K = (int(i) for i in input().split())
a = {}
for i in range(N):
    tmp = list(int(i) for i in input().split())
    if not tmp[0] in a.keys():
        a[tmp[0]] = tmp[1]
    else:
        a[tmp[0]] += tmp[1]


ans_array = []
for k,v in a.items():
    ans_array.append((k,v))
ans_array = sorted(ans_array)

count = 0
for i in range(N):
    count += ans_array[i][1]
    if count>=K:
        print(ans_array[i][0])
        break

Measured memory_bytes: 15064
def main():    
    n,k,q = map(int,input().split())
    a = [int(input())-1 for i in range(q)]
    current_point = [k]*n
    minus_point = [q]*n
    for i in a:
        minus_point[i] -= 1
    for i in range(n):
        if current_point[i] <= minus_point[i]:
            print("No")
        else:
            print("Yes")
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 11240
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>

using namespace std;


int main() {

  int n,m;
  int result[1100][110];

  string str;
  int answer[110];

  char* tp;
  int temp;
  int max_num,max_id;


  while(1) {

    cin >> n;
    cin >> m;

    if(n==0 && m==0) break;

    getline(cin,str);

    for(int i=0;i<n;i++) {

      getline(cin,str);

      tp=strtok((char*)str.c_str()," ");

      result[i][0]=atoi(tp);

      for(int j=1;j<m;j++) {

	tp=strtok(NULL," ");

	result[i][j]=atoi(tp);

      }

    }

    /*
    for(int i=0;i<n;i++) {

      for(int j=0;j<m;j++) {

	cout << result[i][j] << " ";

      }

      cout << endl;

    }
    */

    for(int i=0;i<m;i++) {

      temp=0;

      for(int j=0;j<n;j++) {

	temp+=result[j][i];

      }

      answer[i]=temp;

      //cout << temp << endl;

    }

    for(int i=0;i<m;i++) {

      max_num=0;

      for(int j=0;j<m;j++) {

	if(max_num<answer[j]) {

	  max_num=answer[j];
	  max_id=j;

	}

      }

      if(i==0) cout << max_id+1;

      else cout << " " << max_id+1;

      answer[max_id]=0;

    }

    cout << endl;
	
  }

  return 0;
  
}
  

Measured memory_bytes: 1176
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
const ll mod=998244353;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> data_struct;

vector<ll> gr[100010];
ll dist[100010],par[100010];
bool vis[100010];

void dfs(ll u,ll p)
{
	queue< pair<ll,ll>> q;
	q.push({u,p});
	vis[1]=true;
	while(!q.empty())
	{
		pair<ll,ll> pr=q.front();
		q.pop();
		par[pr.first] = pr.second;
		for(auto it:gr[pr.first])
		{
			if(!vis[it])
			{
				vis[it]=true;
				q.push({it,pr.first});
			}
		}
	}
}

// void dijkstra( ll n, ll src)
// {
// 	dist[src] = 0;
// 	priority_queue < pair<ll,ll> , vector<pair<ll,ll>> , greater<pair<ll,ll>> > pq;
// 	pq.push({0, src});
// 	while(!pq.empty())
// 	{
// 		pair<ll,ll> p= pq.top();
// 		ll x=p.second;
// 		pq.pop();
// 		for(pair<ll,ll> y: gr[x])
// 		{
// 			ll wt=y.second;
// 			ll v=y.first;
// 			if(dist[v] > dist[x]+wt)
// 			{
// 				dist[v] = dist[x]+wt;
// 				par[v]=x;
// 				pq.push({dist[v],v});
// 			}
// 		}
// 	}
// }

int main()
{
	ll n,m;
	cin>>n>>m;
	ll x,y;
	while(m--)
	{
		cin>>x>>y;
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	ll i;
	for(i=1;i<=n;i++)
		dist[i]=-1;
	dist[1]=0;
	dfs(1,-1);
	// dijkstra(n,1);
	for(i=2;i<=n;i++)
		if(dist[i] == INT_MAX)
		{
			cout<<"No";
			return 0;
		}
	// for(i=1;i<=n;i++)
	// 	cout<<dist[i]<<" ";
	// cout<<endl;
	cout<<"Yes\n";
	for(i=1;i<=n;i++)
	for(i=2;i<=n;i++)
		cout<<par[i]<<"\n";
}

Measured memory_bytes: 14628
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl;
using LL = long long;

const LL M = 998244353, ROOT = 3;
LL powMod(LL x, LL n) {
	LL r(1);
	while (n) {
		if (n & 1) r = r * x % M;
		n >>= 1;
		x = x * x % M;
	}
	return r;
}
void bitreverse(std::vector<LL> &a) {
	for (int i = 0, j = 0; i != a.size(); ++i) {
		if (i > j) std::swap(a[i], a[j]);
		for (int l = a.size() >> 1;
			(j ^= l) < l; l >>= 1);
	}
}
void nft(std::vector<LL> &a, bool isInverse = false) {
	LL g = powMod(ROOT, (M - 1) / a.size());
	if (isInverse) {
		g = powMod(g, M - 2);
		LL invLen = powMod(LL(a.size()), M - 2);
		for (auto & x: a) x = x * invLen % M;
	}
	bitreverse(a);
	std::vector<LL> w(a.size(), 1);
	for (int i = 1; i != w.size(); ++i) w[i] = w[i - 1] * g % M;
	auto addMod = [](LL x, LL y) {
		return (x += y) >= M ? x -= M : x;
	};
	for (int step = 2, half = 1; half != a.size(); step <<= 1, half <<= 1) {
		for (int i = 0, wstep = a.size() / step; i != a.size(); i += step) {
			for (int j = i; j != i + half; ++j) {
				LL t = (a[j + half] * w[wstep * (j - i)]) % M;
				a[j + half] = addMod(a[j], M - t);
				a[j] = addMod(a[j], t);
			}
		}
	}
}
void mul(std::vector<LL>& a, std::vector<LL> b) {
	int sz = 1, tot = a.size() + b.size() - 1;
	while (sz < tot) sz *= 2;
	a.resize(sz);
	b.resize(sz);
	nft(a);
	nft(b);
	for (int i = 0; i != sz; ++i) a[i] = a[i] * b[i] % M;
	nft(a, 1);
	a.resize(tot);
}
const int N = 1e5 + 2;
LL fac[N], ifac[N];
LL inv(LL a){ // 0 < a < p and gcd(a,p) = 1
	return a == 1 ? 1 : (M - M / a) * inv(M % a) % M;
}
void init() {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % M;
	ifac[N - 1] = inv(fac[N - 1]);
	for (int i = N - 1; i; --i) ifac[i - 1] = ifac[i] * i % M;
}
LL binom(int n, int k) {
	if (n < k) return 0;
	return fac[n] * ifac[k] % M * ifac[n - k] % M;
}
int main() {
	//freopen("in","r",stdin);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	init();
	int n;
	std::cin >> n;
	std::vector<int> cnt(1e5 + 2);
	for (int i = 0, x; i < 2 * n; ++i) {
		std::cin >> x;
		++cnt[x];
	}
	std::vector<LL> r(1, 1);
	LL inv2 = (M + 1) / 2;
	std::sort(cnt.begin(), cnt.end());
	auto start = std::lower_bound(cnt.begin(), cnt.end(), 1) - cnt.begin();
	std::vector<std::pair<int, int>> q;
	q.push_back({cnt[start], 1});
	for (int i = start + 1; i < cnt.size(); ++i) {
		if(cnt[i] != q.back().first) q.push_back({cnt[i], 1});
		else ++q.back().second;
	}
	for (auto [x, xn] : q) if (x > 0) {
		std::vector<LL> a(x / 2 + 1);
		LL p2j = 1;
		for (int j = 0; j <= x / 2; ++j) {
			a[j] = fac[x] * ifac[x - 2 * j] % M * ifac[j] % M * p2j % M;
			p2j = p2j * inv2 % M;
		}
		while (xn) {
			if (xn & 1) mul(r, a);
			xn >>= 1; mul(a, a);
		}
	}
	std::vector<LL> G(n + 1);
	G[0] = 1;
	for (int i = 1; i <= n; ++i) G[i] = G[i - 1] * (2 * i - 1) % M;
	LL ret = 0;
	for (int i = 0; i < r.size() && i <= n; ++i) {
		ret += (i % 2 == 1 ? -1 : 1) * G[n - i] * r[i] % M;
	}
	print((ret % M + M) % M);
	return 0;
}

Measured memory_bytes: 9112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    ll a; cin >> a;
    string b; cin >> b;
    ll ans = 0;
    ans += a * (ll)(100 * (b[0] - '0'));
    ans += a * (ll)(10 * (b[2] - '0'));
    ans += a * (ll)(b[3] - '0');
    ans /= 100;
    cout << ans << endl;
}


Measured memory_bytes: 3628
#include <iostream>
#define rep2(i, n) for(int i = 1; i < n; i+=2)
using namespace std;

int main(){
  int n;
  cin >> n;
  int ans = 0;
  rep2(i, n+1){
    int num = 0;
    rep2(j, n+1){
      if (i % j == 0)
        num++;
    }    
    if (num == 8)
      ans++;
  }
  cout << ans << endl;
  
  return 0;
}

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

/*int main()
{
    int n;
    cin >> n;
    uint32_t max = 0;
    uint32_t min = 1000000000;

    vector<uint32_t> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a.at(i);
        if (max < a.at(i))
        {
            max = a.at(i);
        }
        if (min > a.at(i))
        {
            min = a.at(i);
        }
    }

    cout << (max - min) << endl;
}*/

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

    vector<uint32_t> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a.at(i);
    }

    sort(a.begin(), a.end() );

    cout << (a.at(n-1) - a.at(0)) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, P> Q;

ll n;
double x[100], y[100], z[100], r[100];

double square(double x) { return x * x; }

class UF {
  ll par[100];
public:
  UF() {
    for (ll i = 0; i < n; i++) par[i] = i;
  }
  ll find(ll x) {
    if (x != par[x]) par[x] = find(par[x]);
    return par[x];
  }
  void merge(ll x, ll y) {
    x = find(x), y = find(y);
    par[x] = y;
  }
  bool same(ll x, ll y) { return find(x) == find(y); }
};

int main() {
  while (scanf("%lld", &n), n) {
    for (ll i = 0; i < n; i++) scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
    priority_queue<Q, vector<Q>, greater<Q>> pq;
    for (ll i = 0; i < n; i++) for (ll j = i+1; j < n; j++) {
      double temp = sqrt(square(x[i]-x[j]) + square(y[i]-y[j]) + square(z[i]-z[j])) - r[i] - r[j];
      pq.push(Q(max(0.0, temp), P(i, j)));
    }
    UF uf;
    double ans = 0.0;
    while (!pq.empty()) {
      Q p = pq.top(); pq.pop();
      ll i = p.second.first, j = p.second.second;
      double c = p.first;
      if (uf.same(i, j)) continue;
      uf.merge(i, j);
      ans += c;
    }
    printf("%.3lf\n", ans);
  }
}



Measured memory_bytes: 2716
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <assert.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int main()
{
	// ARC005-A, 1030, 
	string s; cin >> s;
	int ss = s.size();
	int snum = 0;
	string ans;
	rep(i, ss) {
		if (s[i] == 'S') snum++;
		else {
			if (snum == 0) ans += s.substr(i, 1);
			else snum--;
		}
	}
	int as = ans.size();
	rep(i, as) ans.push_back('S');
	cout << ans.size() << endl;
	return 0;
}

Measured memory_bytes: 3752
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib> 
#include <ctime>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
	if (a > b) swap(a, b);
	ll x;
	while (a) {
		x = b % a;
		b = a;
		a = x;
	}
	return b;
}
int main() {
	ll x, y;
	cin >> x >> y;
	cout << x * y / gcd(x, y) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;

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

	vector<int> v(N);
	int sum = 0;

	for (int i = 0; i < N; i++) {
		cin >> v.at(i);
		sum += v.at(i);
	}

	sort(v.begin(), v.end());

	int ans = N;
	ans += (X - sum) / v.front();

	cout << ans << endl;
}

Measured memory_bytes: 3556
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a,b,c,d;
char s[200020];
int main()
{
	scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
	scanf("%s",s+1);
	int flag=1;
	for(int i=a;i<c;++i)
		if(s[i]=='#'&&s[i+1]=='#')
		{
			flag=0;
			break;
		}
	for(int i=b;i<d;++i)
		if(s[i]=='#'&&s[i+1]=='#')
		{
			flag=0;
			break;
		}
	if(c>d)
	{
		int fl=0;
		for(int i=b;i<=d;++i)
			if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.')
			{
				fl=1;
				break;
			}
		flag&=fl;
	}
	if(flag)printf("Yes");
	else printf("No");
	return 0;
}


Measured memory_bytes: 384
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

a = ii()
b = ii()
c = ii()
x= ii()
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
#            print(i,j,k)
            if x == 500*i+100*j+50*k:
                ans += 1
print(ans)

Measured memory_bytes: 3064
//VS2015エラー回避用
#define _CRT_SECURE_NO_WARNINGS 0 
//include
#include<stdio.h>
#include<stdlib.h>
//関数プロトタイプ宣言
void probremA(void);
void probremB(void);
void probremC(void);
void probremD(void);

//メイン関数
int main(void) {
	//A問題
	//probremA();

	//B問題
	probremB();

	//C問題
	//probremC();

	//D問題
	//probremD();

//	getchar();
//	getchar();
	//終了
	return 0;
}
//A問題
void probremA(void) {
	
	char s[1001];	//入力文字列
	int pos[4] = {0,0,0,0};		//場所：N,S,E,W
	int count = 0;	//ループ用カウンタ
	//入力処理
	scanf("%s", s);

	//個数の計算
	while(s[count]!='\0') {
		//
		if (s[count] == 'N') {
			pos[0]=1;
		}else if (s[count] == 'S') {
			pos[1]=1;
		}else if (s[count] == 'E') {
			pos[2]=1;
		}else if (s[count] == 'W') {
			pos[3]=1;
		}
		//カウンタを増やす
		count++;
	}
	//出力処理
	if (pos[0] == 1 && pos[1] == 1 && pos[2] == 1 && pos[3] == 1) {
		printf("Yes");
	}else if (pos[0] == 1 && pos[1] == 1 && pos[2] == 0 && pos[3] == 0) {
		printf("Yes");
	}else if (pos[0] == 0 && pos[1] == 0 && pos[2] == 1 && pos[3] == 1) {
		printf("Yes");
	}else {
		printf("No");
	}
	
	return;
}
//B問題
void probremB(void) {
	long n = 0;
	long *a;
	long long pairs=0;
	//入力処理
	scanf("%ld", &n);
	//メモリ確保
	a = (long*)malloc(sizeof(long)*n);
	//入力処理2
	long* lp;
	lp = a;
	for (long i = 0; i < n; i++) {
		scanf("%ld", lp);
		lp++;
	}


	//計算過程
	if (n >= 2) {
		for (long i = 1; i < n - 1; i++) {
			//隣り合う時の計算
			if (a[i-1] % 2 ==1 && a[i] >0) {
				pairs++;
				a[i - 1]--;
				a[i]--;
			}
			if (a[i + 1] % 2 == 1 && a[i] >0) {
				pairs++;
				a[i + 1]--;
				a[i]--;
			}
		}
		//残り
		for (long i = 0; i < n; i++) {
			pairs += a[i] / 2;
		}
	}
	//サイズが1の時
	else {
		pairs = (a[0] / 2);
	}
	//出力処理
	printf("%lld", pairs);
	//メモリ開放
	free(a);
	//終了
	return;
}
//C問題
void probremC(void) {
	long n = 0;
	long *a;
	long ope1 = 0;
	//入力処理
	scanf("%ld", &n);
	//メモリ確保
	a = (long*)malloc(sizeof(long)*n);
	//入力処理2
	long* lp;
	lp = a;
	for (long i = 0; i < n-2; i++) {

		lp++;
	}
	for (long i = 0; i < n;i++)
	//出力処理
	printf("%ld", ope1);
	//メモリ開放
	free(a);
	//終了
	return;
}
//D問題
void probremD(void) {
	return;
}


Measured memory_bytes: 896
#include <stdio.h>

int main() {
    int A;
    int B;
    int C;
    
    scanf("%d %d %d",&A,&B,&C);
    
    if (A == B == C) {
        printf("No");
    }
    else if (A == B && B != C) {
        printf("Yes");
    }
    else if (A == C && C != B) {
        printf("Yes");
    }
    else if (B == C && C != A) {
        printf("Yes");
    }
    else {
        printf("No");
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
#include <ios>
#include <iomanip>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define print(x) cout<<(x)<<'\n'
#define print_vec(v) rep(i,v.size()){if(i!=0)cout<<" ";cout<<v[i];}cout<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<'\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pi=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;

void solve() {
    int N,W;
    cin >> N >> W; 
    vi v(N),w(N);
    rep(i,N){
        cin >> v[i] >> w[i];
    }
    int dp[N+1][W+1];

    rep(j,W+1){
        dp[0][j]=0;
    }
    

    rep(i,N){
        rep(j,W+1){
            if(j < w[i]){
                dp[i+1][j] = dp[i][j];
            }else{
                dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
            }
        }
    }
    print(dp[N][W]);
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
    //int q; cin >> q;
	//while (q--)
		solve();
    return 0;
}


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

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

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

#define NMax 310000
#define E 'E'
#define W 'W'

char S[NMax];

int main(int argc, const char * argv[]) {
    rep(i, NMax) S[i] = 0;

    int N = inputValue();

    inputArray(S, N);
    int ans = 0;
    repd(i, 1, N) {
        if (S[i] == 'E') ans += 1;
    }

    int count = ans;
    repd(i, 1, N) {
        if (S[i-1] == 'W') count += 1;
        if (S[i] == 'E') count -= 1;
        if (count < ans) ans = count;
    }

    output(ans);
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define F(i,a,n) for(int i=a; i<n; i++)
#define INF 100000000000 // long only


int main(){
  int k,a,b;
  scanf("%d%d%d",&k,&a,&b);
  for(int i=a;i<b+1;i++){
    if(i%k==0){
      printf("OK\n");
      return 0;
    }
  }
  printf("NG\n");
  return 0;
}

Measured memory_bytes: 1664
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int Max(int A[], int p, int q) {
	int max = 0;
	for (int i = p; i < q; i++) {
		max = MAX(max, A[i]);
	}
	return max;
}
int main() {
	int N, T;
	int A[100000];
	int maxA[100000];
	int count = 0;
	int maxGain = 0;
	scanf("%d %d", &N, &T);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	maxA[N - 1] = A[N - 1];
	for (int i = N - 2; i >= 0; i--) {
		maxA[i] = MAX(maxA[i + 1], A[i]);
	}
	for (int i = 0; i < N; i++) {
		int gain = MAX(maxA[i]- A[i], 0);
		if (gain > maxGain) {
			maxGain = gain;
			count = 1;
		}
		else if (gain == maxGain)
			count++;

	}
	printf("%d", count);
	return 0;
}


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

using namespace std;

bool comp(pair<string, int>& left, pair<string, int>& right){
    return left.second > right.second ||
           (left.second == right.second && left.first < right.first);
}

int main() {
    map<string, int> Ss;
    vector<vector<string>> anss;
    int N;
    cin >> N;
    for(auto i = 0; i < N; i++){
        string s;
        cin >> s;
        int t = Ss[s] + 1;
        Ss[s] = t;
        if((int)anss.size() == t-1){
            anss.push_back(vector<string>());
        }
        anss[t-1].push_back(s);
    }
    auto ans = *(anss.rbegin());
    sort(ans.begin(), ans.end());
    for(auto i = ans.begin(); i!=ans.end(); i++){
        cout << *i << endl;
    }
    return 0;
}

Measured memory_bytes: 28400
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion

void Main();

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    string s;
    cin >> s;
    vec<bool> mp(28);
    REP(i, s.length()){
        mp[s[i]-'a'] = true;
    }
    for(char i='a'; i<='z'; i++){
        if(!mp[i-'a']){
            cout << i << el;
            return;
        }
    }
    cout << "None" << el;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
            using namespace std;
            #define ll long long int
            #define ull unsigned long long
            ll power(ll,ll);
            ll ncr(ll,ll);
            ll add(ll a,ll b);
            void fact();
            ll mul(ll a,ll b);
            #define watch(x) cerr<<(#x)<<"is"<<x<<nl;
            #define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
            #define fi(a,b) for(ll i=a; i<b; i++)
            #define fk(a,b) for(ll k=a; k<b; k++)
            #define fri(a,b) for(ll i=a; i>=b; i--)
            #define fj(a,b) for(ll j=a; j<b; j++)
            #define ffi(a,b) for(ll i=a;i*i<=b;i++)
            #define mp make_pair
            #define ff first 
            #define  tc ll t; cin>>t; while(t--)
            #define all(v) (v).begin(),(v).end()
            #define ss second
            #define pb push_back
            #define mem(v,a) memset((v),a,sizeof(v));
            #define pll pair<ll,ll>
            #define mll map<ll,ll>
            #define sll set<ll>
            #define vll vector<ll>
            #define max3(a,b,c) max(a,max(b,c))
            #define min3(a,b,c) min(a,min(b,c))
            #define nl endl
            const long long inf=1e18+1e7;
            const  int mod=1e9+7;
            const ll  N=100032LL;
            ll fac[N+2];
            ll inv[N+2];
          
            signed main(){  
        	fast
        	//~ fact();
        	//~ tc
            { ll n,k; cin>>n>>k;
				vll v(n+1);
				fi(1,n+1)cin>>v[i];
			 mll m;
			 
			 vll pref(n+2,0);
			 ll ans=0;
			 m[0]=1;
			 fi(1,n+1){
				 v[i]--;
				 pref[i]=pref[i-1]+v[i];
			//	 cout<<pref[i]<<" ";
				 pref[i]%=k;
				 if(i>=k) m[pref[i-k]]--;
				 
				 ans+=m[pref[i]]++;
			//	 watch(ans)
			 }
			 cout<<ans<<nl;
				
		    }
                return 0;
            }
             
             
            /******************************************************************************/
             
            ll add(ll a,ll b){
    			a+=b;
    		   if(a>=mod) a-=mod;
    		   if(a<0) a+=mod;
    		   return a;
    		} 
             
            ll mul(ll a,ll b){
                return ((a)*(b))%mod;
            }
             
            ll power(ll a,ll n){
              ll res=1;
              while(n){
                  if(n&1) res= mul(res,a);
                 n>>=1; 
                 a= mul(a,a);
              }
                return res;
            }
            void fact(){
            	inv[0]=fac[0]=1;
            	fi(1,N){
            	 fac[i]=mul(fac[i-1],i);
            	inv[i]=power(fac[i],mod-2);
            }
            }
             
            ll ncr(ll n,ll r){
            	
            	if(r>n) return 0;
            	ll e=fac[n];
            	e=mul(e,inv[r]);
            	e=mul(e,inv[n-r]);
            	return e;
            }


Measured memory_bytes: 15872
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define UNIQUE(v) v.erase(unique(all(v)),v.end());
#define fill(a,x) memset(a,x,sizeof(a))
#define zero(a) fill(a,0)
#define minus(a) fill(a,-1)
#define dbg(x) cout << #x"=" << x << endl

const int INF=INT_MAX/3;
const int LIMIT=100;

int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};

int n;
string s;
int ans;

int main(){
    cin>>n;
    ll l0 = 2;
    ll l1 = 1;
    for(int i = 0; i < n - 1; i++) {
        ll temp = l1;
        l1 += l0;
        l0 = temp;
    }
    cout << l1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
typedef long long ll;
 
#define ALL(obj) (obj).begin(), (obj).end() 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

 int main(){
    int n,m;
    cin >> n >> m;
    vector<int> num(n,1);
    vector<bool> c(n, false);
    int ans = 1;
    c[0] = true;
    rep(i,m){
        int x,y;
        cin >> x >> y;
        num[x-1]--;
        num[y-1]++;
        if(c[x-1]&&!c[y-1]){
            c[y-1] = true; 
            ans++;
        }
        if(c[x-1]&&num[x-1]==0){
            c[x-1] = false; 
            ans--;
        }
    }
    cout << ans << endl;

     return 0;
 }

Measured memory_bytes: 640