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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int N, M; cin >> N >> M;
    vector<int> a(M);
    rep(i, M) cin >> a[i];

    vector<ll> ans(N+1, 0);
    for (int i = 0, j = 0; i < N+1; ++i) {
        if (j < M && i == a[j]) {
            j++;
        } else {
            if (i == 0 || i == 1) ans[i] = 1;
            else ans[i] = (ans[i-1] + ans[i-2]) % MOD;
        }
    }
    cout << ans[N] << endl;
    return 0;
}

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

#define int long long

const int MOD = 1e9 + 7;
string K;
int D;

int dp[10010][2][110] = {0}; // dp[i桁目][K未満?][mod D] = 総数

signed main() {
  cin >> K >> D;
  int n = K.size();

  dp[0][0][0] = 1;
  for (int digit = 0; digit < n; digit++) {
    for (int smaller : {0, 1}) {
      int lim = smaller == 1 ? 9 : K[digit] - '0';
      for (int num = 0; num <= lim; num++) {
        for (int modD = 0; modD < D; modD++) {
          dp[digit+1][smaller || num < lim][(modD + num) % D] += dp[digit][smaller][modD] % MOD;
        }
      }
    }
  }

  // この部分
  cout << (dp[n][0][0] + dp[n][1][0] - 1) % MOD << endl;

  return 0;
}


Measured memory_bytes: 17408
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>
#include<map>
#include<queue>

#define rep(i, n) for (ll i = 0; i < n; i++) 
#define rrep(i, n) for(ll i = n-1; i>=0; i--)
#define range(i, n, m) for (ll i = n; i < m; i++) 
#define rrange(i, n, m) for (ll i = n - 1; i => m; i--) 
#define MOD 1000000007
//#define MOD 998244353

typedef long long int ll;
typedef unsigned long long int ull;

using namespace std;

template<class T> inline bool chmax(T & a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T & a, T b) { if (a > b) { a = b; return true; } return false; }

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

	ll N, K;
	cin >> N >> K;

	double out = 0;
	double kaku = 1.0 / N;
	double coin = 0.5;

	rep(i, N) {
		if (i + 1 >= K) {
			out += kaku;
		}
		else {
			ll count = ((log(K) / log(2))) - (log((i + 1)) / log(2)) + 0.99999;
			out += kaku * pow(coin, count);
		}
	}



	cout << setprecision(16) << out <<  endl;








	return 0;
}


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

#define ll long long
#define print(r) cout << r << endl
#define prints(r) cout << r << " "
#define printline cout << endl

#define lim (ll)(1e6 + 1)

int main()
{
	ll n;
	cin >> n;
	vector<ll> arr(lim, 0);
	int pc = 1, sc = 1;
	ll t;
	for (ll i = 0; i < n; i++)
	{
		cin >> t;
		arr[t]++;
		if (arr[t] > 1 && t != 1)
			pc = 0;
	}

	if (pc == 1)
	{
		for (ll i = 2; i < lim; i++)
		{
			ll d = 0;
			if (arr[i])
				d = 1;
			for (ll j = i + i; j < lim; j += i)
			{
				if (arr[j])
				{
					d++;
				}
			}
			if (d > 1)
				pc = 0;
		}
	}

	ll gcd = t;
	for (ll i = 0; i < lim; i++)
	{
		if (arr[i])
			gcd = __gcd(gcd, i);
	}
	if (gcd != 1)
		sc = 0;
	
	if (pc)
		print("pairwise coprime");
	else if (sc)
		print("setwise coprime");
	else
		print("not coprime");

	return 0;
}

Measured memory_bytes: 11180
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef complex<double> P;
typedef long long ll;

struct edge{
    int to;
    char ch;
};

vector<edge> G[2][4000];
// dp[i][j]->m[gÌm[hði,m[gÌRs[Ìm[hðjÆµ½Æ«A»±ÜÅÉ¤ÊµÄ»êé¶ÍÌ
//int dp[3600][3600];
map<int,map<int,int> > dp;
int n[2],m[2];

const int INF=-1;
const int MOD=1000000007;

int dfs(int idx1,int idx2){
    //if(dp[idx1][idx2]!=-1)
    //    return dp[idx1][idx2];
    if(!(dp.find(idx1)==dp.end()||dp[idx1].find(idx2)==dp[idx1].end()))
        return dp[idx1][idx2];
    if(idx1==0&&idx2==0)
        return 1;
    else if(idx1==0||idx2==0)
        return 0;
    // »ÝÌn_É¢½é[gð·×Ä²×ã°é
    // ßèûÌgÝí¹ðXgAbvµA·×Ä²×é
    int res=0;
    for(int i = 0; i < G[0][idx1].size(); i++){
        edge back=G[0][idx1][i];
        for(int j = 0; j < G[1][idx2].size(); j++){
            edge back2=G[1][idx2][j];
            if(back.ch==back2.ch){
                res+=dfs(back.to,back2.to);
                res%=MOD;
            }
        }
    }
    return dp[idx1][idx2]=res%MOD;
}

int main(){

    int t;
    cin>>t;
    while(t--){
        dp.clear();
        //memset(dp,0,sizeof(dp));
        //for(int i = 0; i < 3600; i++)
        //    fill(dp[i],dp[i]+3600,INF);
        for(int j = 0; j < 2; j++)
            for(int i = 0; i < 4000; i++)
                G[j][i].clear();
        for(int j = 0; j < 2; j++){
            cin>>n[j]>>m[j];
            int idx=n[j];
            for(int i = 0; i < m[j]; i++){
                int from,to;
                string str;
                cin>>from>>to>>str;
                // ¶ñðª£µÄ»ê¼êÉidðÂ¯ÄGÉi[·é
                int prv=from;
                for(int k = 0; k < str.size(); k++){
                    edge e;
                    e.to=prv;
                    e.ch=str[k];
                    int tmp=idx;
                    if(k==str.size()-1){
                        tmp=to;
                    }
                    G[j][tmp].push_back(e);
                    prv=tmp;
                    if(k==str.size()-1)
                        break;
                    idx++;
                }
            }
        }
        // »ÄAÅ¦ã°
        int res=dfs(n[0]-1,n[1]-1);
        cout<<res%MOD<<endl;
    }

    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans = max({a*c, b*d, b*c, a*d});
    cout<<ans<<"\n";
}

Measured memory_bytes: 3632
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
using namespace std;
using ll=long long;
#define mod  1000000007

int main(int argc, char const *argv[]) {
  int A,B,K;
      cin >> A >> B >> K;
      if(B-A+1 <= 2*K) for(int i = 0;i < B-A+1;i ++) cout << A+i << endl;
      else {
          for(int i = 0;i < K;i ++) cout << A+i << endl;
          for(int i = 0;i < K;i ++) cout << B-K+1+i << endl;
        }
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
ll dp[1111][1<<3];
const int mod = 10007;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  string s; cin >> s;
  CLR(dp);
  dp[0][1] = 1;
  FOR(i,0,N) {
    // i+1??\???????????????bit??§??????J001 O010 I100
    int reader = -1;
    if(s[i] == 'J') reader = 0;
    if(s[i] == 'O') reader = 1;
    if(s[i] == 'I') reader = 2;
    FOR(J,1,1<<3) {
      // ???????????£??????????????\????????¨????????????
      // ?????????????????\????????¨????????????
      // ?????????????????????????????£?????°???????????¨????????????
      FOR(K,1,1<<3) {
        if(J & (1<<reader) && (J & K)) {
          dp[i+1][J] += dp[i][K];
          dp[i+1][J] %= mod;
        }
      }
    }
  }
  int ans = 0;
  FOR(i,1,1<<3) {
    ans += dp[N][i];
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3196
n,k=map(int,input().split())
m=10**9+7
l=[0]*(k+1)
a=0
for i in range(k,0,-1):
 l[i]=pow(k//i,n,m)
 for j in range(2,k//i+1):l[i]-=l[i*j]
 a+=i*l[i]
 a%=m
print(a)

Measured memory_bytes: 11292
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc,char** argv){
  int n;
  cin >> n;
  for(int i = 1; i < 10; i++){
    if(n <= 111 * i){
      cout << 111 * i << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s, n) for(int i = s; i < (int)(n); i++)
#define co(x) cout<<x<<endl
#define SQvec(i,j) vector<vector<int>> data(i, vector<int>(j))
#define mod 1000000000+7
typedef long long int lint;

int main(){
  int K,A,B;
  cin >> K >> A >> B;
  string ans = "NG";
  rep(i,A,B+1){
    if(i%K == 0){ans = "OK"; break;}
  }
  co(ans);
}

Measured memory_bytes: 3628
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main() {
    double r;

    cin >> r;

    cout << fixed << setprecision(5) << atan(1) * 4.0 * r * r << " " << 8.0 * atan(1) * r << endl;

    return 0;
}

Measured memory_bytes: 3244
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define INF 1e18
#define pll pair<ll, ll> 
#define vll vector<ll>
ll n,m,a,b,c,k,temp,x,y;
const int MAXN=1e5+11,mod=1e9+7;
inline ll max(ll a,ll b) {return ((a>b)?a:b);}
inline ll min(ll a,ll b) {return ((a>b)?b:a);}
inline vll read(int n) {vll v(n);for (int i = 0; i < v.size(); i++)cin>>v[i];return v;}
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
void sol(void)
{
cin>>n;
vll v(n);
ll sum=0;
for(int i=0;i<n;i++)
{
    cin>>v[i];
    sum+=v[i];
    sum%=mod;
}
ll ans=0;
for(int i=0;i<n;i++)
{
    ans+=((v[i]*(sum-v[i]+mod)%mod)%mod);
    ans%=mod;
}
cout<<(ans*modInverse(2))%mod;
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test=1;
    //cin>>test;
    for(int i=1;i<=test;i++)
    sol();
}


Measured memory_bytes: 4764
/******************************************************************************

                            Online Java Compiler.
                Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.

*******************************************************************************/
import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    Scanner sc=new Scanner(System.in);
	    int a=sc.nextInt();
	    int b=sc.nextInt();
		System.out.println(a*b);
	}
}


Measured memory_bytes: 35788
//
//  main.cpp
//  tarea
//
//  Created by AdÃ¡n LÃ³pez Alatorre on 3/31/17.
//  Copyright Â© 2017 AdÃ¡n LÃ³pez Alatorre. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string.h>
#include <bitset>
#include <set>
#include <cstdio>
#include <cmath>
#include <vector>
#include <iomanip>
#include <stack>
#include <map>
#include <queue>
#include <climits>
#define se second
#define fi first

using namespace std;

typedef  long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

const ll MOD = 1e9 + 7, maxN = 2e2 + 6, maxV = 6561 + 5;

int n;

int getdigsm(int n){
    int ret = 0;
    while(n){
        ret += n % 10;
        n /= 10;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    cin >> n;
    
    int ret = n * 2000;
    for(int i = 1; i < n; i++){
        //cout << getdigsm(i)  << ' ' << getdigsm(n - i) << '\n';
        ret = min(ret, getdigsm(i) + getdigsm(n - i));
    }
    cout << ret << '\n';
    
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>

using namespace  std;

int n;
int main()
{
	cin>>n;
	if(n%2==0) cout<<0.5;
	if(n%2==1) 
	{
		cout<<(n+1)/2.0/n;
	}
	return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef string str;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define pb(x) pop_back(x)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define sum(x) accumulate(all(x),0)
#define pc(x) __builtin_popcount(x)
#define gll greater<ll>()

void solve(){
  str s,t;
  cin >> s >> t;
  
  ll n=s.size();
  ll m=t.size();
  ll ans=m;
  rep(i,0,n-m+1){
    ll tot=0;
    rep(j,0,m) if(s[i+j]!=t[j]) tot++;
    chmin(ans,tot);
  
  }
  
  
 cout << ans << endl;
  
}
int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 3616
#include <stdio.h>
#define N 100005
#define NIL -1

struct Node{
  int p, l, r;
};
struct Node T[N];

int getDepth(int p){
  if(T[p].p == NIL) return 0;
  return getDepth(T[p].p) + 1;
}

int main(){
  int n, i, k, j, c;
  int id, tmp;
  int dep[N];

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    T[i].l = T[i].p = T[i].r = NIL;
  }
  for(i = 0; i < n; i++){
    scanf("%d%d", &id, &k);
    for(j = 0; j < k; j++){
      scanf("%d", &c);
      if(j == 0){
	T[id].l = c;
	T[c].p = id;
	tmp = c;
      }else{
	T[tmp].r = c;
	T[c].p = id;
	tmp = c;
      }
    }    
  }
  for(i = 0; i < n; i++){
    dep[i] = getDepth(i);
  }
  
  for(i = 0; i < n; i++){
    printf("node %d: parent = %d, depth = %d, ", i, T[i].p, dep[i]);
    if(T[i].p == NIL){
      printf("root, [");
    }else if(T[i].l == NIL){
      printf("leaf, [");
    }else{
      printf("internal node, [");
    }
    if(T[i].l != NIL){
      printf("%d", T[i].l);
      tmp = T[i].l;
      while(1){
	if(T[tmp].r == NIL) break;
	printf(", %d", T[tmp].r);
	tmp = T[tmp].r;
      }
    }
      printf("]\n", tmp);
  }
  return 0;
}

Measured memory_bytes: 2164
#include <stdio.h>

typedef struct _node {
    int val;
    struct _node *next;
    struct _node *prev;
} NODE;

class List {
    NODE *nil;
public:
    List() {
        nil = new NODE;
        nil->next = nil;
        nil->prev = nil;
    }
    void insert(int val) {
        NODE *x = new NODE;
        x->val = val;
        x->next = nil->next;
        nil->next->prev = x;
        nil->next = x;
        x->prev = nil;
    }
    NODE* search(int val) {
        NODE *p = nil->next;
        while (p != nil && p->val != val) {
            p=p->next;
        }
        return p;
    }
    void deleteNode(NODE *x) {
        if (x == nil) {
            return;
        }
        x->prev->next = x->next;
        x->next->prev = x->prev;
        delete x;
    }
    void deleteFirst() {
        deleteNode(nil->next);
    }
    void deleteLast() {
        deleteNode(nil->prev);
    }
    void print() {
        NODE *first = nil->next;
        NODE *p = first;
        while (p!=nil) {
            if(p!=first){
                printf(" ");
            }
            printf("%d", p->val);
            p=p->next;
        }
        printf("\n");
    }
};

int main() {
    int n,val;
    scanf("%d", &n);
    char cmd[100];
    List l;
    for (int i=0;i<n;i++) {
        scanf("%s %d", cmd, &val);
        if (cmd[0]=='i') {
            l.insert(val);
        } else if (cmd[6] == 'L') {
            l.deleteLast();
        } else if (cmd[6] == 'F') {
            l.deleteFirst();
        } else {
            NODE *x = l.search(val);
            l.deleteNode(x);
        }
    }
    l.print();
    return 0;
}


Measured memory_bytes: 33812
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define P pair<ll, ll>
#define VI vector<ll>
#define int long long
using namespace std;
int N, M;
vector<vector<bool>> e;

void solve() {
  vector<int> perm(N);
  REP (i, N) { perm[i] = i; }
  int ans = 0;
  do {
    bool hamilton = true;
    REP (i, N-1) {
      if (!e[perm[i]][perm[i+1]]) {
        hamilton = false;
      }
    }
    if (hamilton) {
      ans++;
    }
  } while (next_permutation(perm.begin() + 1, perm.end()));
  cout << ans << endl;
}

signed main() {
  cin >> N >> M;
  e = vector<vector<bool>>(N, vector<bool>(N, false));
  REP (i, M) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    e[a][b] = true;
    e[b][a] = true;
  }

  solve();
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>

using namespace std;

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

const long long inf = (1ll<<31) - 1;

struct SegTree { // ??????min,max
    int n;
    vector<int> Min;
    void init(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        Min.resize(2 * n);
        for (int i = 0; i < 2 * n - 1; ++i) {
            Min[i] = inf;
        }
    }
    void update(int idx, int val) {
        idx += n - 1;
        Min[idx] = val;
        while (idx > 0) {
            idx = (idx - 1) / 2;
            Min[idx] = min(Min[idx * 2 + 1], Min[idx * 2 + 2]);
        }
    }
    int get_min(int a, int b, int k = 0, int l = 0, int r = -1) { // [a, b)???min
        if (r == -1) r = n;
        if (r <= a || b <= l) return inf;
        if (a <= l && r <= b) return Min[k];
        int vl = get_min(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = get_min(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

signed main()
{
    int n, q; scanf("%d%d", &n, &q);

    SegTree seg;

    seg.init(n);

    rep(i, q) {
        int type, x, y;
        scanf("%d%d%d", &type, &x, &y);

        if (type % 2 == 0) {
            seg.update(x, y);
        } else {
            printf("%d\n", seg.get_min(x, y + 1));
        }
    }
}

Measured memory_bytes: 1796
/* Dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005
ll a[2005][2003],b[2003][2003];
int main()
{
	ios
	ll n,m,i,j,ans=0;
	cin>>n>>m;
	string s[n+1];
	for(i=0;i<n;i++){
		cin>>s[i];
		for(j=0;j<m;j++){
			if(s[i][j]=='.')
				a[i][j]=1,b[i][j]=1;
		}
	}
	for(i=0;i<n;i++){
		ll sum=0;
		for(j=0;j<m;j++){
			if(a[i][j]==0)sum=0;else{
				sum++;
				a[i][j]=sum;
			}
		}
	}
	for(j=0;j<m;j++){
		ll sum=0;
		for(i=0;i<n;i++){
			if(b[i][j]==0)sum=0;else{
				sum++;
				b[i][j]=sum;
			}
		}
	}
	for(i=0;i<n;i++){
		ll sum=0;
		for(j=m-1;j>=0;j--){
			if(a[i][j]==0);else{
				a[i][j]=max(a[i][j],a[i][j+1]);
			}
		}
	}
	for(j=0;j<m;j++){
		ll sum=0;
		for(i=n-1;i>=0;i--){
			if(b[i][j]==0);else{
				b[i][j]=max(b[i][j],b[i+1][j]);
			}
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(s[i][j]=='.'){
				ans=max(ans,a[i][j]+b[i][j]-1);
			}
		}
	}
	cout<<ans;
	return 0;
}

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

int main() {
  string N;
  cin >> N;
  int sum = 0;
  for (int i = 0; i < N.size(); i++){
    int a = N.at(i) - '0';
    sum += a;
  }
  if (sum % 9 == 0){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}



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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(2e4 + 5);
const ll MOD = (ll)(1e9 + 7);

/////////////////////////////////////////////////////////////
class CombinationModulo {
 public:
  static const ll MOD = (ll)(1e9 + 7);

  vector<ll> fact;
  vector<ll> inv;
  vector<ll> fact_inv;

  CombinationModulo(int n) {
    this->fact = vector<ll>(n + 1, 0LL);
    this->inv = vector<ll>(n + 1, 0LL);
    this->fact_inv = vector<ll>(n + 1, 0LL);
    init(n);
  }

  void init(int n) {
    inv[1] = fact[0] = fact_inv[0] = 1LL;
    for (int i = 2; i <= n; i++) {
      inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
    }
    for (int i = 1; i <= n; i++) {
      fact[i] = fact[i - 1] * i % MOD;
    }
    for (int i = 1; i <= n; i++) {
      fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
  }

  ll comb(int n, int r) {
    if (r > n) return 0LL;
    return fact[n] * fact_inv[r] % MOD * fact_inv[n - r] % MOD;
  }
};
/////////////////////////////////////////////////////////////

int n, k;

CombinationModulo cm(MAX_N);

ll calc(int cur_k) {
  ll base = cm.comb(n - k + 1, cur_k);

  ll remain = (ll)(k - cur_k);

  ll add = cm.comb(cur_k + remain - 1, remain);

  return (base * add) % MOD;
}

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &k);

  for (int i = 1; i <= k; ++i) {
    printf("%lld\n", calc(i));
  }

  return 0;
}


Measured memory_bytes: 768
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        int n = stdin.nextInt();
        int m = stdin.nextInt();

        Map<Integer, Integer> d = new HashMap<>();
        int t = m;
        for (int x = 2; x * x <= t; x++) {
            while (t % x == 0) {
                d.put(x, d.getOrDefault(x, 0) + 1);
                t /= x;
            }
        }
        if (t > 1) {
            d.put(t, d.getOrDefault(t, 0) + 1);
        }

        BigInteger ans = BigInteger.ONE;
        for (int v : d.values()) {
            ans = ans.multiply(c(n + v - 1, v)).mod(mod);
        }
        System.out.println(ans);
    }

    private static List<BigInteger> fct = new ArrayList<>();
    private static List<BigInteger> inv = new ArrayList<>();
    private static BigInteger mod = BigInteger.valueOf(1000000007);
    private static BigInteger c(int n, int r) {
        if (fct.isEmpty()) {
            fct.add(BigInteger.ONE);
            inv.add(fct.get(0).modInverse(mod));
        }

        for (int i = fct.size(); i <= n; i++) {
            fct.add(fct.get(i - 1).multiply(BigInteger.valueOf(i)).mod(mod));
            inv.add(fct.get(i).modInverse(mod));
        }

        return fct.get(n).multiply(inv.get(n - r).multiply(inv.get(r)).mod(mod)).mod(mod);
    }
}

Measured memory_bytes: 77332
N=int(input())
T,A=map(int,input().split())
H=list(map(int,input().split()))
d=[0]*N

for i in range(N):
  d[i]=abs(T-H[i]*0.006-A)

minimum=min(d)

for i in range(N):
  if d[i]==minimum:
    ans=i+1
    break

print(ans)

Measured memory_bytes: 3064
#include <cstdio>
typedef long long ll;

int main() {
    ll x, y;
    scanf("%lld %lld", &x, &y);

    if (-1 <= x - y && x - y <= 1) {
        printf("Brown\n");
    } else {
        printf("Alice\n");
    }
    return 0;
}

Measured memory_bytes: 128
a = [[[0 for k in range(10)] for j in range(3)] for i in range(4)]
n = int(input())
for i in range(n):
  b, f, r, v = map(int, input().split())
  a[b-1][f-1][r-1] += v
for i in range(4):
  for j in range(3):
    for k in range(10):
      print("", a[i][j][k], end = "")
    print()
  if i != 3:
    print("#"*20)


Measured memory_bytes: 5632
#include <stdio.h>
#define MAX 25
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/

typedef struct Node_struct Node;

Node T[MAX];
int D[MAX];
int H[MAX];
int De[MAX];
int S[MAX];

void print(int u){
  int i, c;
  printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ", u,T[u].p,S[u],De[u],D[u],H[u]);

  if(T[u].p == NIL) printf("root");
  else if(T[u].l == NIL && T[u].r == NIL) printf("leaf");
  else printf("internal node");
  printf("\n");
}

void calcDepth(int u, int p){
  D[u] = p;
  
  if(T[u].l != NIL) calcDepth(T[u].l, p+1);
  if(T[u].r != NIL) calcDepth(T[u].r, p+1);
}

int calcHeight(int u){
  int r,l;
  r = l = 0;
  
  if(T[u].l == NIL && T[u].r == NIL) {
    H[u] = 0;
    return 0;
  }
  
  if(T[u].r != NIL) 
    r = calcHeight(T[u].r) + 1;
  if(T[u].l != NIL)
    l = calcHeight(T[u].l) + 1;
  
  if(l > r) {
    H[u] = l;
    return l;
  }
  else {
    H[u] = r;
    return r;
  } 
}

void calcDegree(int u){
  if(T[u].r != NIL) {
    De[u]++;
    calcDegree(T[u].r);
  }
  if(T[u].l != NIL) {
    De[u]++;
    calcDegree(T[u].l);
  }
}

void calcSibling(int u){ 
    S[T[u].r] = T[u].l;
    S[T[u].l] = T[u].r;
}

int main(){
  int i, j;
  int n;
  int id, sib, child;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) {
    T[i].p = T[i].l = T[i].r = NIL;
    S[i] = NIL; 
  }
  
  for(i=0; i<n; i++){
    scanf("%d",&id);

    for(j = 0; j<2; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else {
	T[id].r = child;
	calcSibling(id);
      }  
     
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == NIL ) root = i;
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
 
  calcDepth(root, 0);
  calcHeight(root);
  calcDegree(root);

  //出力 (output)
  for(i=0; i<n; i++) print(i);
  
  return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <functional>
using namespace std;

int main() {
  string S;
  cin >> S;
  if (S.at(0)==S.at(1)||S.at(1)==S.at(2)||S.at(2)==S.at(3)) cout << "Bad" << endl;
  else cout << "Good" << endl;
}

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

bool uruu(int y){
	bool ch=false;
	if(y%4==0)ch=true;
	if(y%100==0)ch=false;
	if(y%400==0)ch=true;
	return ch;
}

int main(void){
	int f,t;
	bool k=false;
	while(1){
		bool u=false;
		cin >> f >> t;
		if(f==0 && t==0)break;
		if(k)cout << endl;
		for(int i=f;i<=t;i++){
			if(uruu(i)){
				u=true;
				cout << i << endl;
			}
		}
		if(!u)cout << "NA" << endl;
		k=true;
	}
    return 0;
}

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


/* データを互いに重複しない集合に分割して保持するデータ構造を
 * 素集合データ構造 (Disjoint-set Data Structure) という。
 * このデータ構造に対して
 *  ・Find:  特定の要素がどの集合に属しているかを求める
 *  ・Union: 2つの集合を統合する
 * のアルゴリズムを兼ね備えたデータ構造を Union Find データ構造と呼ぶ。
 */

class UnionFind
{
    private:
        std::vector<int> parent;  // parent[x]: x の親の番号
                                  //            ただし、x が親の場合はその連結成分の大きさ
        std::vector<int> rank;    // rank[x]  : x が属する木の高さ 
        std::size_t sz;           // 連結成分の数

    public:
        // parent は全て -1 で初期化し、その連結成分の大きさを -(大きさ) で代入しておく
        UnionFind( std::size_t n ): parent(n, -1), rank(n, 0), sz(n) {}

        // x が属する集合の親を返し、x を親に直接繋ぎ直す
        int find( int x )
        {
            if( parent[x] < 0 ) return x;
            else return parent[x] = find( parent[x] );
        }

        // x が属する集合と y が属する集合を統合する
        bool unite( int x, int y )
        {
            x = find( x );
            y = find( y );
            if( x == y ) return false;

            // 大きい方(x)に小さい方(y)を繋げる
            if( rank[x] < rank[y] ) std::swap( x, y );

            parent[x] += parent[y];  // x に連結している成分の大きさを更新する
            parent[y] = x;           // y を x に繋ぐ
            if( rank[x] == rank[y] ) rank[x]++;
            sz--;

            return true;
        }

        std::size_t size() { return sz; }
        std::size_t size( int x ) { return - parent[find(x)]; }
};



int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for( int i = 0; i < M; ++i ){
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
    } 

    vector<long> ans( M );
    ans[M-1] = (long) N * ( N - 1 ) / 2;

    UnionFind uni( N );

    for( int i = M-1; i >= 1; --i ){
        if( uni.find(A[i]) == uni.find(B[i]) ) ans[i-1] = ans[i]; 
        else{
             ans[i-1] = ans[i] - (long) uni.size( A[i] ) * uni.size( B[i] );
             uni.unite( A[i], B[i] );
        }
    }
    
    for( int i = 0; i < M; ++i ) cout << ans[i] << endl;
    
    return 0;
}

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

//cmdで g++ test.cpp とするとコンパイルできる
typedef long long ll;
typedef pair<int,int> pii;

const int MOD=1000000007;

int main() {
    int N;
    cin>>N;
    if(N%2){
        cout<<N/2+1<<endl;
    }else{
        cout<<N/2<<endl;
    }
    
}


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

int main() {
  int number, a, b, c, d;
  cin >> number;
  
  a = number / 1000;
  b = (number - a * 1000) / 100;
  c = (number - a * 1000 - b * 100) / 10;
  d = number - a * 1000 - b * 100 - c * 10;
  
  if ((a == b && b == c) || (b == c && c == d)) cout << "Yes" << endl;
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)

main = do
  n <- readLn :: IO Int
  input <- getIntListBC
  let mul4 = length . filter (\x -> 0 == mod x 4) $ input
      odds = length . filter (\x -> 0 /= mod x 2) $ input
      mul2 = n - (mul4 + odds)
  if judge mul2 mul4 odds then putStrLn "Yes"
                          else putStrLn "No"

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getIntListBC :: IO [Int]
getIntListBC = map bsToInt . BC.words <$> BC.getLine

judge :: Int -> Int -> Int -> Bool
judge m2 m4 o = m2 == 0 && o <= m4 + 1 || o <= m4


Measured memory_bytes: 9724
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn gcd(a: u64, b: u64) -> u64 {
    fn gcd1(m: u64, n: u64) -> u64 {
        if n == 0 {
            m
        } else {
            gcd1(n, m % n)
        }
    }
    if a > b {
        gcd1(a, b)
    } else {
        gcd1(b, a)
    }
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let a: u64 = read(&mut stdin_lock, &mut buf, b' ');
    let b: u64 = read(&mut stdin_lock, &mut buf, b'\n');

    let ans = a * b / gcd(a, b);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>

using namespace std;

int main()
{
    int n;
    string s;
    string ans;

    cin>>n>>s;
    if (n%2==0)
    {
        int size=s.size();
        size/=2;
        string sub=s.substr(size,size);
        if (s==sub+sub)
        {
            ans="Yes";
        }
        else
        {
            ans="No";
        }
    }
    else
    {
        ans="No";
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
/**
*    created: 07.07.2020 00:11:05
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
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;}
const long double pi = acos(-1.0);
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    string s;
    cin >> s;
    int l = s.size() / 2;

    auto check = [&] (string s) {
        int n = s.size()/2;
        bool ok = true;
        rep(i,n) if (s[i] != s[i+n]) ok = false;
        return ok;
    };

    rep2(i,1,l) {
        string t = s.substr(0,s.size()-i*2);
        if (check(t)) {
            cout << t.size() << endl;
            return 0;
        }
    }
    return 0;
}

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

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a.at(i);
    }
    int left=0;
    int right=pow(10,9);
    while(right > left+1){
        int mid=(left+right)/2;
        int cnt=0;
        for(int i=0; i<n; i++){
            cnt+=(a.at(i)+mid-1)/mid-1;
        }
        if(cnt<=k) right=mid;
        else left=mid;
    }
    cout << right << endl;
}

Measured memory_bytes: 3948
#include<bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx")
#pragma comment(linker,"/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
inline int read()
{
	int ret=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return w*ret;
}
int n;
int f[20][20];
int t[20];
int ans=0;
void check()
{
	for(int i=1;i<=n;i++)
	if(t[i])
	for(int j=1;j<=n;j++)
	if(f[i][j])
	if(f[i][j]-1!=t[j]) return;
	int cnt=0;
	for(int i=1;i<=n;i++) cnt+=t[i];
	ans=max(ans,cnt);
}
void dfs(int step)
{
	if(step==n+1)
	{
		check();
		return;
	}
	t[step]=1;
	dfs(step+1);
	t[step]=0;
	dfs(step+1);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		for(int j=1;j<=x;j++)
		{
			int p,q;
			cin>>p>>q;
			f[i][p]=q+1;
		}
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

        if((a*b)%2==1){
            System.out.println("Odd");
        }else{
            System.out.println("Even");
        }
    }
}

Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
#define push_back pb
#define make_pair mp
using ll =  long long;
const int INF = 0x3f3f3f3f;

string s;

void solve()
{
	int a = stoi(s.substr(0,2)), b = stoi(s.substr(2));
	if(a >=1 && a <=12 && b>=1 && b<= 12) cout << "AMBIGUOUS" << endl;
	else if(b>=1 && b<= 12) cout << "YYMM" << endl;
	else if(a>=1 && a<= 12) cout << "MMYY" << endl;
	else cout << "NA" << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> s;
	solve();
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int N, M;
  int i,s=0;
  
  scanf("%d %d", &N,&M);
  
  int a[M];
  for(i=0;i<M;i++) {
    scanf("%d", &a[i]);
    s=s+a[i];
  }
 if(N>=s)
   printf("%d",N-s);
 else
   printf("-1");
  
 return 0;
}
  

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

using namespace std;
typedef long long ll;

int main(){
  int n, w;
  cin>>n>>w;
  vector<ll> weight(n);
  vector<ll> value(n);
  for(int i=0; i<n; i++){
    cin>>weight[i];
    cin>>value[i];
  }
  vector<vector<ll>> knapsack(n+1, vector<ll>(w+1));
  for(int i=1; i<=n; i++){
    for(int j=1; j<=w; j++){
      knapsack[i][j] = knapsack[i-1][j];
      if(weight[i-1] <= j){
        knapsack[i][j] = max(value[i-1] + knapsack[i-1][j-weight[i-1]], knapsack[i][j]);
      }
    }
  }

  cout<<knapsack[n][w]<<endl;
  return 0;
}


Measured memory_bytes: 80256
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	private static Scanner scan;
	public static void main(String[] args) {
		scan = new Scanner(System.in);
		int a[] = new int[100];
		Arrays.fill(a, 0);
		int m = 0;
		while(scan.hasNext()){
			int n = scan.nextInt();
			a[n-1]++;
			m = Math.max(a[n-1], m);
		}
		for(int i = 0;i < 100;i++){
			if(a[i] == m)System.out.println(i+1);
		}
		System.exit(0);
	}

}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dofloat cout<<fixed<<setprecision(8)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bitcount __builtin_popcount
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vll;
typedef vector<pair<int,int> > vii;
typedef vector<int> vi;
typedef pair<int,int> ii;
const long long MOD=1000000007;
const long long MAX=100005;
const long double PI=3.14159265359;
const long double G=9.807;
const long long INF=1e18;
const long double EPS=1e-6;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
bool isprime(ll a){
  if(a==2)return 1;
  if(!(a&1))return 0;
  for(ll i=3;i*i<=a;i+=2)
    if(a%i==0)return 0;
  return 1;
}
ll mpow(ll base,ll exponent,ll modulus){
  if(modulus==1)return 0;
  long long result = 1;
  base=base%modulus;
  while(exponent){
    if(exponent%2 == 1)
    result=(result*base)%modulus;
    exponent=exponent>>1;
    base=(base*base)%modulus;
  }
  return result;
}
ll minv(ll a,ll mod){
  ll _gcd=gcd(a,mod);
  assert(_gcd==1);
  return mpow(a,mod-2,mod);
}


/*
ll ncr(ll N,ll K){
  if(N<K)return 0;
  if(K==0)return 1;
  if(N==0)return 0;

  ll den=1;
  for(ll i=1;i<=K;i++)den*=i;
  ll num=1;
  while(K--){
    num*=N;
    if(num%den==0){
      num/=den;
      den=1;
    }
    N--;
  }

  return num;
}
*/
ll n;
ll W;
ll w[105],val[105];
ll dp[MAX];

int main(){FAST;
cin>>n>>W;
for(ll i=1;i<=n;++i){
  cin>>w[i]>>val[i];
}
for(ll i=1;i<=100000;++i)dp[i] = INF;
dp[0] = 0;
for(ll i=1;i<=n;++i){
  for(ll j=100000;j>=val[i];--j){
    if(dp[j-val[i]]!=-1){
      dp[j] = min(dp[j-val[i]]+w[i],dp[j]);
    }
  }
}
ll ans;
for(ll i=100000;i>=0;--i){
  if(dp[i]<=W){
    ans = i;
    break;
  }
}
cout<<ans;
return 0;
}

/*
 WA? check edge cases, N=1,M=1 etc. Read code fully once and check all variables.
 Read the question again and see what you might have missed.
 Consider changing your solution or find more cases.
 */


Measured memory_bytes: 4408
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=55;
char s[N][N];ll f[N][N][N];int n;
inline ll calc(R int l,R int r,R int m){
	if(~f[l][r][m])return f[l][r][m];
	if(l==r)return f[l][r][m]=1;
	if(l==m||r==m)return f[l][r][m]=0;
	R ll res=0;
	fp(j,l,m-1)fp(k,m+1,r)if(s[j][k]=='1')
		fp(p,j,m-1)fp(q,m+1,k)
			res+=calc(l,p,j)*calc(p+1,q-1,m)*calc(q,r,k);
	return f[l][r][m]=res;
}
int main(){
	memset(f,-1,sizeof(f));
	scanf("%d",&n);
	fp(i,1,n<<1)scanf("%s",s[i]+1);
	R ll res=0;
	fp(i,2,n<<1)if(s[1][i]=='1')res+=calc(2,n<<1,i);
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 1536
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
cnt = 0
sum = 0
c = []
n.times do |i|
  e = a[i] - b[i]
  if e.negative?
    cnt += 1
    sum += e
    e = 0
  end
  c << e
end
c.sort.reverse.each do |x|
  break if sum >= 0
  sum += x
  cnt += 1
end
puts cnt > n ? "-1" : cnt

Measured memory_bytes: 18856
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<int> vi;
typedef vector<double> vd;
 
double mypow(double b ,int e){
      if(e == 0) return 1;
      if(e%2==0)
            return mypow( b*b, e/2 );
      else
            return mypow( b*b, e/2 ) * b;
}
 
int main(){
 
 
      int N,M,L; cin >> N >> M >> L ;
      if(N==1){
            cout << 1.0 << endl;
            return 0;
      }
      vector<vd> prob(N,vd(M+1,0.0));
      vector<vd> dist(N,vd(M+1,0.0));
 
      vd p(N),t(N),v(N);
      for(int i=0; i<N; i++) cin >> p[i] >> t[i] >> v[i];
 
      // PRE PROCESS
      for(int i=0; i<N; i++){
            dist[i][0] = (double)L / v[i];
            for(int j=1; j<=M; j++){
                  dist[i][j] = dist[i][j-1] + t[i];
            }
      }
      for(int i=0; i<N; i++)
            prob[i][0] = mypow((100-p[i])/100,M);
      for(int i=0; i<N; i++){
            for(int j=1; j<=M; j++){
                  if(p[i] != 100)
                        prob[i][j] = (prob[i][j-1] * (p[i]/100)) / ((100-p[i])/100);
                  else
                        prob[i][j] = 1.0;
            }
      }
      double comb = 1;
      for(int j=1; j<=M; j++){
            comb = comb * (M - j + 1) / j; 
            for(int i=0; i<N; i++){
                  prob[i][j] *= comb;
            }
      }
       
      vector<vd> sum = prob;
      for(int i=0; i<N; i++){
            for(int j=M-1; j>=0; j--){
                  sum[i][j] += sum[i][j+1];
                  if(sum[i][j] > 1) sum[i][j] = 1;
            }
      }
 
      vector<vd> ans = prob;
      for(int i=0; i<N; i++){
            for(int j=0; j<=M; j++){
                  for(int k=0; k<N; k++){
                        if(i==k) continue;
                        int id = upper_bound(dist[k].begin(),dist[k].end(), dist[i][j]) - dist[k].begin();
                        if(id > M) ans[i][j] = 0.0;
                        else       ans[i][j] *= sum[k][id];
 
                  }
            }
      }
 
      for(int i=0; i<N; i++){
            double tmp = 0.0;
            if(p[i] == 100) tmp = ans[i][M];
            else
                  for(int j=0; j<=M; j++)
                        tmp += ans[i][j];
            if(tmp > 1) tmp = 0;
            printf("%.10f\n",tmp);
      }
                         
}

Measured memory_bytes: 3332
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N = in.next().toInt
  val tree = Array.fill[List[(Int, Int)]](N+1)(Nil)
  for (_ <- 1 to N-1) {
    val u, v, w = in.next().toInt
    tree(u) = (v, w) :: tree(u)
    tree(v) = (u, w) :: tree(v)
  }

  //
  val dp = new Array[Boolean](N+1)
  val ans = new Array[Int](N+1)

  val stack = new scala.collection.mutable.Stack[(Int, Int)] // (node, color)
  stack.push((1, 0))

  while (!stack.isEmpty) {
    val (node, color) = stack.pop()
    if (!dp(node)) {
      ans(node) = color

      for ((e, d) <- tree(node) if !dp(e)) {
        val nxColor = (color + (d % 2)) % 2
        stack.push((e, nxColor))
      }

      dp(node) = true
    }
  }


  for(i <- 1 to N)
    pw.println(ans(i))
  pw.flush()
}



class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 61288
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val k = sc.nextInt()
  val s = sc.nextInt()


  var count = 0L
  for (xi in 0..k) {
    for (yi in 0..k) {
      val last = s - xi - yi
      if (last == 0) {
        count++
        break
      }
      if (last > 0 && last <= k) {
        count++
      }
    }
  }

  println(count)

}


Measured memory_bytes: 36284
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[200000];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt() - 1;
		for(int i = 0 ; i < n ; i++) {
			b[a[i]]++;
		}
		Arrays.sort(b);
		int ans = 0;
		for(int i = 199999 - k ; i >= 0 ; i--) {
			ans += b[i];
		}
		System.out.println(ans);

	}
}


Measured memory_bytes: 81540
require 'prime'
n = gets.to_i
if n == 1
  puts 1
  exit(0)
end

elems = Hash.new {1}
(2..n).each do |i|
  Prime.prime_division(i).each do |a|
    elems[a[0]] += a[1]
  end
end
puts elems.values.inject(&:*) % 1000000007


Measured memory_bytes: 2172
#include <stdio.h>
int main(void)
{
   int a, b, k, i;

   scanf("%d%d%d",&a,&b,&k);

   for(i=a;i<=b;i++){
      if((i<a+k)||(b-k<i))
         printf("%d\n",i);
   }   

   return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i = 0; i < (n); ++i)
typedef long long ll;


int main(void) {
  ll h, w;
  cin >> h >> w;
  ll hw = h*w;
  ll ans = 0;
  if(hw % 2 == 0) {
      ans = hw / 2;
  } else {
    ans = (hw+1) / 2;
  }

  if(h == 1 || w == 1) ans = 1;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 888
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define co(x) cout << (x) << "\n"
#define pb push_back
#define Never
#define To

using namespace std;

int main(){

	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;

	cin >> N;

	int d[N];

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

	int ans = 0;

	for(int i = 0; i < N-1; i++){
		for(int j = i+1; j < N; j++){
			ans += d[i] * d[j];
		}
	}

	cout << ans << endl;

	Never To return 0;
}


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

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

  int i{X - K + 1};
  cout << i++;
  for (; i < X + K; ++i) {
    cout << ' ' << i;
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256