akhauriyash/Code-Regression huggingface dataset:
// Gaurav Nuti
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii > vii;
typedef vector<pll > vll;
#define pb push_back
#define mp make_pair 
#define ar array
#define mod 1000000007
#define F first
#define S second
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define For(i, a, b) for(__typeof (a) i=a; i<=b; i++)
#define inp_arr(a,n) for(__typeof (n) i=0; i<n; ++i) {cin>>a[i];}
#define debug_arr(a,n) {{for(__typeof (n) i=0; i<n; ++i) {cout<<a[i]<<" ";}cout<<"\n";}}
#define INF 1e9 

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

ll power_without_mod(ll x, ll y) 
{ 
    ll res = 1;   
    while (y > 0) { 
        if (y & 1) 
            res = (res*x); 
        y = y>>1;
        x = (x*x); 
    } 
    return res; 
}

bool comparep(pair<ll, ll> i1, pair<ll, ll> i2){
	return (i1.S < i2.S);
} 

ll modInverse(ll a)
{
    return power(a , mod - 2);
}

vector<vector<ll>> graph;
vector<bool> visited;
vector<ll> dist;
map<ll,ll> mymap;
ll max_dist = 1;

void bfs(int u1){
    visited[u1] = 1;
    dist[u1] = 1;
    mymap[1] = u1;
    queue<ll> q;
    q.push({u1});
    while(!q.empty()){
        ll u = q.front();
        q.pop();
        for(auto i=graph[u].begin();i!=graph[u].end();i++){
            if(!visited[*i]){
                dist[*i] = dist[u] + 1;
                visited[*i] = 1;
                max_dist = max(dist[*i],max_dist);
                mymap[dist[*i]] = *i;
                q.push({*i});
            }
        }
    }
}

// int next_lunlun(ll n){
//     vector<int> digits;
//     while(n){
//         digits.pb(n%10);
//         n /= 10;
//     }
//     // reverse(digits.begin(),digits.end());
//     ll num_digits = digits.size(); 
//     int count_9 = 0;
//     for(int i: digits)
//         if(i == 9)
//             count_9++;
//     if(count_9 == num_digits)
//         return ;
//     for(int i=0;i<(num_digits-1);i++){
//         if(digits)
//     }
// }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
    #endif  
	
    ll t;
    // cin>>t;
    t = 1;
    for(ll z=0;z<t;z++){
        ll n, w;
        cin>>n>>w;
        ar<ll,2> wv[n];
        for(ll i = 0;i<n;i++){
            cin>>wv[i][0]>>wv[i][1];
        }
        ll dp[w + 1] = {0};
        for(ll i=0;i<n;i++){
            for(ll j = w;j >= 0; j--){
                if(j >= wv[i][0])
                dp[j] = max(dp[j - wv[i][0]] + wv[i][1], dp[j]);
            }
        }
        cout<<dp[w];
    }
}

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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

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

pair<ll,ll> ans[1 << 20];
ll ret[1 << 20];

pair<ll,ll> seica(pair<ll,ll> A,pair<ll,ll> B){
	ll fir = max(A.FI,B.FI);
	ll sec = max(min(A.FI,B.FI),max(A.SE,B.SE));
	return MP(fir,sec);
}	

int main(){
	
	int n;cin >> n;
	vector<ll> v(1>>n);
	
	REP(i,1<<n){
		ll tmp;cin >> tmp;
		ans[i].FI = tmp;
	}
	
	REP(i,n){
		for(int j = 0;j < (1<<n);j++){
			if(j & (1 << i)){
				ans[j] = seica(ans[j],ans[j^(1<<i)]);
			}
		}
	}
	
	REP(i,1<<n){
		ret[i] = ans[i].FI + ans[i].SE;
	}
	
	REP(i,1<<n){
		ret[i+1] = max(ret[i+1],ret[i]);
	}
	
	for(int i = 1;i < (1<<n);i++){
		cout << ret[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 13312
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

int R, C, N;

i64 get_ord(i64 x, i64 y) {
    if (y == 0) {
        return x;
    } else if (y == C) {
        return R + C + R - x;
    } else if (x == 0) {
        return R + C + R + C - y;
    }
    return R + y;
}

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

    vector<pair<int, i64> > ls;

    cin >> R >> C >> N;
    for (int j = 0; j < N; ++j) {
        i64 x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if ((x1 == 0 || x1 == R || y1 == 0 || y1 == C) &&
            (x2 == 0 || x2 == R || y2 == 0 || y2 == C)) {

            i64 o1 = get_ord(x1, y1), o2 = get_ord(x2, y2);

            ls.emplace_back(min(o1, o2), j);
            ls.emplace_back(max(o1, o2), j);
        }
    }

    sort(begin(ls), end(ls));

    stack<int> stk;
    for (int j = 0; j < (int)ls.size(); ++j) {
        if (!stk.empty() && stk.top() == ls[j].second) {
            stk.pop();
        } else {
            stk.push(ls[j].second);
        }
    }
    cout << (stk.empty() ? "YES" : "NO") << endl;


    return 0;
}


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

using namespace std;

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

#define sz(x) ((long long)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define oo 1e15;
const ld eps = 1e-9;
const ld pi = acosl(-1);
const int mod = 998244353;
const int mod1 = 1e9 + 7;


mt19937_64 rnd(time(0));

void faster()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
}

signed main() {
    faster();
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    //______________________________________
    ///*__*/double start = clock();/*__*/
    //_____________________________________
    int n;
    cin >> n;
    vector <vector <ld> > dp(n, vector <ld> (n + 1));
    vector <ld> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    dp[0][0] = (1 - v[0]);
    dp[0][1] = (v[0]);
    for (int i = 1; i < n; i++)
    {
        dp[i][0] = (1 - v[i]) * dp[i - 1][0];
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] * v[i] + dp[i - 1][j] * (1 - v[i]);
          //  cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    ld ans = 0;
    for (int i = n / 2 + 1; i <= n; i++)
    {
        ans += dp[n - 1][i];
       // cout << dp[n - 1][i] << " " << i << endl;
    }
    cout << fixed << setprecision(10);
    cout << ans;
    //______________________________________
    //  cerr << "Time " << (clock() - start)  * 1.0 / CLOCKS_PER_SEC << "s\n";
    return 0;
}

Measured memory_bytes: 141056
v[50],p,n,c;f(X){for(n=0;n<X;n+=v[p++]);c+=n;}main(s){for(;n=atoi(gets(v));printf("%d\n",s)){for(p=s=0;p<n;v[++p]=strlen(gets(v+n)));for(c=0;c-31;)c=0,p=++s,f(5),f(7),f(5),f(7),f(7);}}

Measured memory_bytes: 532
import java.util.*;
import java.math.*;
public class Main {
	static int r; 
	static int c;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n + 1];
		int[] ball = new int[n];
		for(int i = 0; i < n; i++) {
			ball[i] = in.nextInt();
			a[ball[i]] += 1;
		}
		long ans = 0L;
		for(int i = 0; i <= n; i++) {
			ans += ((long) a[i] * (long) (a[i] - 1)) / 2;
		}
		for(int i = 0; i < n; i++) {
			if(a[ball[i]] == 1) System.out.println(ans);
			else {
				long newans = ans;
				newans -= ((long) a[ball[i]] * (long) (a[ball[i]] - 1)) / 2;
				newans += ((long) (a[ball[i]] - 1) * (long) (a[ball[i]] - 2)) / 2;
				System.out.println(newans);
			}
		}
	}
} 


Measured memory_bytes: 110248
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <complex>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
#include <fstream>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define ALL(s) (s).begin(), (s).end()
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;

bool isStable(vector<string>in,vector<string>out){
  REP(i,in.size()){
    FOR(j,i+1,in.size()){
      REP(a,out.size()){
	FOR(b,a+1,out.size()){
	  if(in[i][1] == in[j][1] && in[i] == out[b]&& in[j] == out[a])
	    return false;
	}
      }
    }
  }
  return true;
}

int main (){
  int N;
  while (cin >> N){
    vector<string> a;
    REP(i,N){
      string  ia;
      cin >> ia;
      a.push_back(ia);
    }
    vector<string> ab(a);
    vector<string> ac(a);
    //バブルソート
    bool flag = true;
    while(flag){
      flag = false;
      for(int i = N-1; i  > 0; i--){
	if(ab[i][1] < ab[i-1][1]){
	  swap(ab[i],ab[i-1]);
	  flag = true;
	}
      }
    }
    
    REP(i,N-1){
      cout << ab[i] << " ";
    }
    cout << ab[N-1] << endl;

    if(isStable(a,ab)){
      cout << "Stable" << endl;
    }else{
      cout << "Not stable" << endl;
    }
    
    
    //選択ソート
    int cnt = 0;
    REP(i,N){
      int minj = i;
      FOR(j,i,N){
	int jnam = ac[j][1]-48;
	int minjnam = ac[minj][1]-48;
	if(jnam < minjnam) minj = j;
      }
      if(i!=minj){
	swap(ac[i],ac[minj]);
	cnt++;
      }
    }

    REP(i,N-1){
      cout << ac[i] << " ";
    }
    cout << ac[N-1] << endl;
    if(isStable(a,ac)){
      cout << "Stable" << endl;
    }else{
      cout << "Not stable" << endl;
    }

  }
  return 0;
}



Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
int main()
{
	char a,b;
	cin>>a>>b;
	if(a>b)
	{
		cout<<">";
	}
	else if(a<b)
	{
		cout<<"<";
	}
	else
	{
		cout<<"=";
	}
}


Measured memory_bytes: 256
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

INF = sys.maxsize

N = int(input().strip())
h = [int(x) for x in input().split()]

@lru_cache()
def solve(i):
  if i >= N - 1:
    return 0
  return min(    
    solve(i + 1) + abs(h[i] - h[i + 1]) if i + 1 < N else INF,
    solve(i + 2) + abs(h[i] - h[i + 2]) if i + 2 < N else INF
  )
  
print(solve(0))

Measured memory_bytes: 287328
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 27 00:28:31 2019

@author: yuta
"""

def palace(n,ta,h):
    ta2 = list(map(int,ta))
    h2 = list(map(int,h))
    temp = list(map(lambda i:ta2[0]-i*0.006, h2))
    near = list(map(lambda i:abs(i-ta2[1]), temp))
    nearest = min(near)
    print(near.index(nearest)+1)

x = input()
y = input().split()
z = input().split()

palace(x,y,z)

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

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

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

    vector<string> s(N);
    rep(i, 0, N) cin >> s[i];

    map<string, int> mp;
    rep(i, 0, N)
    {
        sort(s[i].begin(), s[i].end());
        mp[s[i]]++;
    }

    ll ans = 0;
    for(auto& p : mp)
    {
        int x = p.second;
        ans += (ll)x * (x - 1) / 2;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 18176
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

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

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    int n;
    cin >> n;
    vector<P> a(n);
    rep(i, n) cin >> a[i].first >> a[i].second;

    sort(ALL(a), [&](P s, P t){return atan2(s.second, s.first) < atan2(t.second, t.first);});

    double ans = 0;
    rep(i, n){
        int x = 0;
        int y = 0;
        rep(j, n){
            x += a[(i+j)%n].first;
            y += a[(i+j)%n].second;
            ans = max(ans, sqrt(x * x + y * y));
        }
    }
    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}


Measured memory_bytes: 256
def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x

n = int(input())
a = list(map(int, input().split()))
fromLeft = [0] * n
fromLeft[0] = a[0]
fromRight = [0] * n
fromRight[0] = a[n - 1]
for i in range(1, n):
    fromLeft[i] = gcd(fromLeft[i - 1], a[i])
    fromRight[i] = gcd(fromRight[i - 1], a[n - i - 1])
ret = fromLeft[n - 1]
for i in range(n):
    if i == 0:
        curGcd = fromRight[n - 2]
    elif i == n - 1:
        curGcd = fromLeft[n - 2]
    else:
        curGcd = gcd(fromLeft[i - 1], fromRight[n - i - 2])
    ret = max(ret, curGcd)
print(ret)

Measured memory_bytes: 63856
#include<iostream>
using namespace std;
int main(){
 int x[10000];
 int i =0;
 do{
 cin >> x[i];
 i++;
 }while(x[i-1] != 0);
 
 for(int j=1; j<i; j++){
  cout <<"Case "<<j<<": "<< x[j-1]<<endl;
 }
}


Measured memory_bytes: 3148
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
    ll K; cin >> K;
    int N = 50;
    cout << N << endl;
    vector<ll> ans(N);
    rep(i,N) ans[i] = i;
    ll d = K/N;
    ll r = K%N;
    rep(i,N) ans[i] += d;
    rep(i,r){
        sort(ans.begin(),ans.end());
        ans[0] += N;
        repr(j,1,N) ans[j]--;
    }
    rep(i,N) cout << ans[i] << " ";
    cout << endl;

}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<sstream>
#include<iomanip>
#define forn(i,n) for(int (i)=0;i<(n);i++)
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int MAXN=100005;
const int INF=2147483647;
const ll LINF=9223372036854775807;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int a,b,c,d,x,y;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b>>c>>d;
	x=(c+b-1)/b;
	y=(a+d-1)/d;
	if(x>y)cout<<"No";
	else cout<<"Yes";
	return 0;
}


Measured memory_bytes: 3656
import java.util.*;
import java.math.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int sum = 0;
    for (int i = 0; i < 3; i++) sum += sc.nextInt();
    if (sum >= 22) System.out.println("bust");
    else System.out.println("win");
  }
}


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

int N,A,B;
int MIN,MAX;
int main(){
     cin >> N >> A >> B;
     MAX = min(A,B);
     if (A+B <= N) MIN = 0;
     else MIN = A+B-N; 
     cout << MAX << " " << MIN << endl;

     return 0;
}


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

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MOD = 1000000007;
static const ll MAX = 10000;
static const ll INFTY = 1e18;

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;
// 入力
// int H, W;
vector<vector<char>> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 深さ優先探索
vector<bool> seen;
vector<int> colors;


int main() {

  ll N, x; cin >> N >> x;
  ll sum = 0; 
  ll ans = 0;
  ll diff = 0;
  vector<ll> a(N);
  REP(i, N){cin >> a[i];}

  if(a[0]>x){
      ans += a[0]-x;
      a[0] = x;
  }

  REP(i, N-1){
      sum = a[i] + a[i+1];
      while(sum>x){
    //   if(sum > x){
          if(a[i+1] == 0){
              diff = sum - x;
              if(a[i] < diff)diff = a[i];
              a[i] -= diff;
              ans += diff;
          }else{
              diff = sum - x;
              if(a[i+1] < diff)diff = a[i+1];
              a[i+1] -= diff;
              ans += diff;
          }
          sum = a[i] + a[i+1];
    //   }
      }
  }
//   REP(i, N){
//       cout << " " << a[i];
//   }cout << endl;

  cout << ans << endl;

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    vector<int> l(N);
    for (auto& i : l) cin >> i;
    sort(l.rbegin(), l.rend());
    cout << accumulate(l.begin(), l.begin() + K, 0) << endl;
}


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

int main(){
  long long a,b,c;
  cin >> a >> b >> c;
  c -= (a+b);
  if(c > 2*sqrtl(a*b)) cout <<"Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}
  


Measured memory_bytes: 256
#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 uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const long long LINF = 1e18 + 3141;
int n, a[N], b[N], c[N], w;
ll dp[N];
pair <int,int> p[N];
void solve(){
    cin >> n >> w;
    for(int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y};
    }
    for(int i = 1; i <= n; ++i)
        a[i] = p[i].X,
        b[i] = p[i].Y;
    
    for(int i = 1; i < N; ++i) 
        dp[i] = LINF;
    for(int i = 1; i <= n; ++i) 
        for(int j = N - 1; j >= b[i]; --j) 
            dp[j] = min(dp[j], dp[j - b[i]] + a[i]);
        
    
    for(int i = N - 1; i >= 0; --i)
        if(dp[i] <= w){
            cout << i;
            return;
        }    
}   
 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, r;
  cin >> n >> r;
  if (n >= 10) cout << r << '\n';
  else cout << (r + 100 * (10-n)) << '\n';
  return 0;
} 

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



int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string a,b;
	cin >> a >> b;
	int n = 0;
	for (int i = 0 ; i < a.size() ; i++)
	{
		if (a[i] != b[i]) n++;
	}
	cout<<n<<endl;
}

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


int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a==b&&b==c)cout<<"No";
  else if(a==b||b==c||a==c)cout<<"Yes";
  else cout<<"No";
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    ll ans = INF;
    for(ll i=-100;i<=100;i++){
        ll num = 0;
        for(int j=0;j<n;j++){
            num += (a[j] - i) * (a[j] - i); 
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
    return 0;
}


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

Measured memory_bytes: 1408
import math


def deg2rad(x):
    result = x / 360 * math.pi * 2
    return result


def rad2place(a, x):
    return a * math.cos(x), a * math.sin(x)


a, b, h, m = map(int, input().split())

deg_m = 90 + (60 - m) / 60 * 360
rad_m = deg2rad(deg_m)
mx, my = rad2place(b, rad_m)

deg_h = 90 + ((12 - h) - m / 60) / 12 * 360
rad_h = deg2rad(deg_h)
hx, hy = rad2place(a, rad_h)

dx = hx - mx
dy = hy - my

ans = math.sqrt(dx**2 + dy**2)
print(ans)


Measured memory_bytes: 9604
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

int main() {
    string n1, n2;
    cin >> n1 >> n2;

    int cnt=0;

    for(int i=0; i<n1.size(); i++) {
        if(n1.at(i) != n2.at(i)) cnt++;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3908
n,a,b = map(int, input().split())

nums = range(1,n + 1)

ans = 0

for num in nums:
    sum = 0
    sum += num % 10
    wari = num // 10
    
    while wari > 0:
        sum += wari % 10
        wari = wari // 10
    
    if sum >= a and sum <= b:
        ans += num

print(ans)

Measured memory_bytes: 3060
n,x=map(int,input().split())
def b(n,x):
  if n==0 and x==1:
    return 1
  while n>0:
    z=(2**(n+2)-3)//2+1
    if x==1:
      return 0
    elif 1<x<z:
      return b(n-1,x-1)
    elif x==z:
      return 2**n
    elif z<x<(2**(n+2)-3):
      return 2**n + b(n-1,x-z)
    else:
      return 2**(n+1)-1
print(b(n,x))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,sum=0,i;
    cin>>n;
    if(n<=1)
        cout<<"1"<<endl;
    else
    {
        sum=1;
        i=0;
        while(n!=1)
        {
            n=n/2;
            i++;
//            cout<<i<<endl;
//            cout<<n<<endl;
            sum=sum+pow(2,i);
        }

    cout<<sum<<endl;
    }

}


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

#define int long long

auto main() -> signed {
    int x, y;
    cin >> x >> y;
    if(abs(x-y)<=1) cout << "Brown" << endl;
    else cout << "Alice" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(const void *a, const void *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(const void* left, const void* right) {return strcmp((char *)left,(char *)right);}
int downchar(const void* left, const void* right) {return strcmp((char *)right,(char *)left);}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1){
            res *= a; if(mod>=1) res %= mod;
        }
        a *= a; if(mod>=1) a %= mod;
        n >>= 1;
    }
    return res;
}
void initialize(){
    
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int a[LIMIT2]={0};
  char s[LIMIT1];
  
  scanf("%lld",&n);
  i = n % 10;
  if(i==3) printf("bon");
  else if(i==0||i==1||i==6||i==8) printf("pon");
  else printf("hon");
  
  return 0;
}



Measured memory_bytes: 1700
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
#include<ctype.h>
using namespace std;


int main() {
	int n, l[1010], r[1010],ans=0;
	cin >> n;
	for (int i = 1; i <= n;i++) {
		cin >> l[i] >> r[i];
		ans += r[i] - l[i] + 1;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	void solve() throws IOException {
		int a = ni();
		int b = ni();
		out.println(a*b-a-b+1);
	}

	String ns() throws IOException {
		while (!tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine(), " ");
		}
		return tok.nextToken();
	}

	int ni() throws IOException {
		return Integer.parseInt(ns());
	}

	long nl() throws IOException {
		return Long.parseLong(ns());
	}

	double nd() throws IOException {
		return Double.parseDouble(ns());
	}

	String[] nsa(int n) throws IOException {
		String[] res = new String[n];
		for (int i = 0; i < n; i++) {
			res[i] = ns();
		}
		return res;
	}

	int[] nia(int n) throws IOException {
		int[] res = new int[n];
		for (int i = 0; i < n; i++) {
			res[i] = ni();
		}
		return res;
	}

	long[] nla(int n) throws IOException {
		long[] res = new long[n];
		for (int i = 0; i < n; i++) {
			res[i] = nl();
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		tok = new StringTokenizer("");
		Main main = new Main();
		main.solve();
		out.close();
	}
}

Measured memory_bytes: 21204
n = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
  if a<b:
    a, b = b, a
  if b==0:
    return a
  return gcd(b, a%b)

def lcm(a, b):
  g = gcd(a, b)
  return a*b//g

l = 1
for ele in a:
  l = lcm(l, ele)

ans = 0
for ele in a:
  ans += (l-1)%ele
print(ans)

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

using ll = long long;

int main() {
    int K;
    cin >> K;
    vector<ll> A(K + 1, 1), B(K + 1), C(K + 1);
    rep(i, K) cin >> A[i + 1];
    B[K] = A[K];
    C[K] = A[K];
    if (A[K] != 2) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = K - 1; i >= 0; i--) {
        B[i] = (B[i + 1] + A[i] - 1) / A[i] * A[i];
        C[i] = (C[i + 1] + A[i + 1] - 1) / A[i] * A[i];
        //cout << i << " " << B[i] << " " << C[i] << endl;
        if (B[i] > C[i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << B[0] << " " << C[0] << endl;
}

Measured memory_bytes: 2560
#include<iostream>
using namespace std;
int main(void)
{
  char a[9];
  while(cin>>a)
    {
      int j=0,x=0;
      for(int i=0;i<3;i++)
	{
	  
	  
	  if((a[i+j]=='o' && a[i+j+1]=='o' && a[i+j+2]=='o') || (a[i]=='o' && a[i+3]=='o' && a[i+6]=='o'))
	    {
	      cout<<'o'<<endl;
	      x++;
	      break;
	    }
	  else if((a[i+j]=='x' && a[i+j+1]=='x' && a[i+j+2]=='x') || (a[i]=='x' && a[i+3]=='x' && a[i+6]=='x'))
	    {
	      cout<<'x'<<endl;
	      x++;
	      break;
	    }
	  j+=2;
	}
      if(a[0]=='o' && a[4]=='o' && a[8]=='o' || (a[2]=='o' && a[4]=='o' && a[6]=='o'))
	{
	  cout<<'o'<<endl;
	  x++;
	}
      if((a[0]=='x' && a[4]=='x' && a[8]=='x') || (a[2]=='x' && a[4]=='x' && a[6]=='x'))
	{
	  cout<<'x'<<endl;
	  x++;
	}
 if(x==0)cout<<'d'<<endl;
    }
  return 0;
}

Measured memory_bytes: 1132
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = input()
    if N[-1] in {'2', '4', '5', '7', '9'}:
        print('hon')
    elif N[-1] in {'0', '1', '6', '8'}:
        print('pon')
    else:
        print('bon')

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 9108
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i <= (int)(n); i++) 
#define dunk(n) cout << n << endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
typedef long long ll;

int main() {
    string s;
    cin >> s;
    rep(i,s.size()) cout << "x";
    cout << endl;
    return 0;
}

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

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define INF (1 << 29)

using namespace std;

int main(){
	int n; 
	cin >> n;
	set<string> Set;

	for(int i = 0; i < n; i++){
		string s;
		cin >> s;

		Set.insert(s);
	}

	cout << Set.size() << endl;

	return 0;
}


Measured memory_bytes: 19064
#include<iostream>
#include<string>
#include<string.h>
using namespace std;

int getChar(char ch);
long long getKey(char str[]);
int h1(int key);
int h2(int key);
int h(int key,int i);
void insert(int key);
int serch(int key);

const int m = 1000003;
int *T;

int main(){
	T = new int[m]; for(int i=0;i<m;i++) T[i] = -1;
	int n; cin>>n;
	string command;
	char str[12];

	for(int i=0;i<n;i++){
		cin>>command;
		if(command=="insert"){
			cin>>str; insert(getKey(str));
		}else if(command=="find"){
			cin>>str;
			if(serch(getKey(str))!=-1)
				cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
	}

	delete [] T;
}

int getChar(char ch){
	if(ch=='A') return 1;
	else if(ch=='C') return 2;
	else if(ch=='G') return 3;
	else if(ch=='T') return 4;
	else return 0;
}

long long getKey(char str[]){
	long long sum = 0, p = 1;
	for(int i=0;i<strlen(str);i++){
		sum += p*(getChar(str[i]));
		p *= 5;
	}
	return sum;
}

int h1(int key){
	return key%m;
}

int h2(int key){
	return 1+key%(m-1);
}

int h(int key,int i){
	return (h1(key)+i*h2(key))%m;
}

void insert(int key){
	int i=0;
	while(true){
		int j = h(key,i);
		if(T[j]==-1){
			T[j] = key;
			return ;
		}else
			i++;
	}
}

int serch(int key){
	int i=0;
	while(true){
		int j = h(key,i);
		if(T[j]==key)
			return j;
		else if(T[j]==-1 || i>=m)
			return -1;
		else
			i++;
	}
}

Measured memory_bytes: 6616
N, M = map(int, input().split())

Ls = []
Rs = []
for i in range(0, M):
    l, r = input().split()
    Ls.append(int(l))
    Rs.append(int(r))

maxL = max(Ls)
minR = min(Rs)
result = max(0, minR-maxL+1)

print(result)

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

int32_t main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s; cin >> s;
    int num = 0;
    for (int i = 0; i < s.size(); i++) {
        num += s[i] - '0';
    }
    cout << (num%9 == 0 ? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 3772
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
 
int cmp(const void *a,const void *b)
{
  return *(long int*)a - *(long int*)b;
}
 
//差の最大公約数を求める
int main()
{
  long int N,i,j,count;
  long int X,x[100001],dif[100000],difmin=1000000000,gcd;
  scanf("%ld %ld",&N,&X);
  for(i=0;i<N;i++){
    scanf("%ld",&x[i]);
  }
  x[N] = X;
  qsort(x,N+1,sizeof(long int),cmp);
  for(i=0;i<N;i++){
    dif[i] = x[i+1] - x[i];
    if(difmin>dif[i])difmin=dif[i];
  }
  for(j=difmin;j>0;j--){
    if(difmin%j==0){
      count = 0;
      for(i=0;i<N;i++){
        if(dif[i]%j==0)count++;
      }
      if(count==N){
        gcd = j;
        break;
      }
    }
  }
  printf("%ld",gcd);
  return 0;
}

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

using namespace std;

long long mod = 1000000007;

long long power(long long n, long long k) {
    long long powered = 1;
    while(k) {
        if(k & 1) {
            powered *= n;
            powered %= mod;
        }
        k >>= 1;
        n = n * n;
        n%=mod;
    }

    return powered;
}
int main()
{
    long long n;
    cin>>n;

    long long a = power(10ll,n);
    long long b = power(9ll,n);
    long long c = power(8ll,n);
    long long answer = (a - ((2 * b)%mod));
    if(answer < 0)answer += mod;
    answer += c;
    answer = answer % mod;
    cout<<answer;
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <vector>

#define MAX_N (100)

struct edge { int from, to, cost; };

bool comp ( const edge& e1, const edge& e2 )
{
	return e1.cost < e2.cost;
}

int par[MAX_N];		/// 親
int rank[MAX_N];	/// 木の深さ

/// n要素で初期化
void init ( int n )
{
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		rank[i] = 0;
	}
}

/// 木の根を求める
int find ( int x ) 
{
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

/// xとyの属する集合を合併
void unite ( int x, int y )
{
	x = find(x);
	y = find(y);

	if (x == y) { return; }

	if (rank[x] < rank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rank[x] == rank[y]) { ++rank[x]; }
	}
}

/// xとyが同じ集合に属するか否か
bool same ( int x, int y )
{
	return find(x) == find(y);
}

using namespace std;

int main ( void )
{
	int n, m;

	while (cin >> n >> m, n | m) {
		vector<edge> es;
		for (int i = 0; i < m; ++i) {
			edge e;
			cin >> e.from >> e.to >> e.cost;
			es.push_back(e);
		}

		sort(es.begin(), es.end(), comp);
		init(n);
		int ans = 0;
		for (int i = 0; i < m; ++i) {
			edge e = es[i];
			if (!same(e.from, e.to)) {
				unite(e.from, e.to);
				ans += e.cost;
			}
		}

		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    int R;
    cin >> R;
    cout << 2 * 3.1415 * R << endl;
}

Measured memory_bytes: 3780
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
    /*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
int main() {
    int n;
    cin >> n;
    if(n>=30)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
    



Measured memory_bytes: 3604
/******************************************************************************

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

*******************************************************************************/

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long int n,w;
    cin>>n>>w;
    vector<vector<long long int>>v(n,vector<long long int>(2,0));
    vector<vector<long long int>>dp(n+1,vector<long long int>(w+1,0));

    for(long long int i=0;i<n;i++)
      for(long long int j=0;j<2;j++)
         cin>>v[i][j];
    
    for(long long int i=0;i<n+1;i++)
    {
         for(long long int j=0;j<w+1;j++)
         {
             if(i==0||j==0)
             dp[i][j]=0;
             else if(v[i-1][0]<=j)
             {
                 dp[i][j]=max(dp[i-1][j],v[i-1][1]+dp[i-1][j-v[i-1][0]]);
             }
             else 
             dp[i][j]=dp[i-1][j];
         }
    }
  cout<<dp[n][w];
    
    return 0;
}


Measured memory_bytes: 80256
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 200;
const int MAXK = 100;

int main() {
	string s;
	int k;
	cin >> s >> k;
	vector<vector<vector<int>>> dp(s.size() + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));
	// empty string without non-zero digit equal is 1
	dp[0][0][1] = 1;

	for (int i = 1; i <= s.size(); ++i) {
		// current digit
		int cur = s[i - 1] - '0';

		for (int j = 0; j <= k; ++j) {
			// fill 0 to smaller and equal
			dp[i][j][0] = dp[i - 1][j][0] + (cur ? dp[i - 1][j][1] : 0);

			// fill 1-9 to smaller
			if (j) {
				dp[i][j][0] += dp[i - 1][j - 1][0] * 9;
			}

			// fill 1- (cur-1) to equal
			if (cur > 1 && j) {
				dp[i][j][0] += dp[i - 1][j - 1][1] * (cur - 1);
			}

			// fill cur to equal
			dp[i][j][1] += cur ? (j ? dp[i - 1][j - 1][1] : 0) : dp[i - 1][j][1];
		}
	}
	cout << dp[s.size()][k][0] + dp[s.size()][k][1] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
static const int MOD = 1000000007;
static const int MAXN = 100000 + 10;

LL factors[MAXN];

LL power(LL base, int n) {
    LL cur = base;
    LL ret = 1;
    while (n) {
        if (n & 1) {
            ret *= cur;
            ret %= MOD;
        }
        cur *= cur;
        cur %= MOD;
        n = n >> 1;
    }
    return ret;
}

LL combine(int n, int k) {
    LL ret = 1;
    ret *= factors[n];
    ret *= power(factors[k], MOD-2);
    ret %= MOD;
    ret *= power(factors[n-k], MOD-2);
    ret %= MOD;
    return ret;

}

LL compute(int n, int k, int d) {
    if (k == 1) return n;
    if (k == n+1) return 1;
    LL ret = combine(n+1, k);
    if (n-d >= k) ret -= combine(n-1-d, k-1);
    if (ret < 0) ret += MOD;
    return ret;

}



int main() {
//    freopen("test.txt", "r", stdin);


    int n;
    scanf("%d", &n);

    factors[0] = 1;
    for (int i = 1; i <= n+1; i++) {
        factors[i] = factors[i-1]*i;
        factors[i] %= MOD;
    }

    vector<LL> nums(n+1, 0);
    LL cnt = 0;
    for (int i = 0; i <= n; i++) {
        scanf("%lld", &nums[i]);
        cnt += nums[i];
    }
    LL tmp = n;
    tmp = (tmp + 1) * tmp;
    LL dupitem = cnt - (tmp >> 1);
    vector<int> dupos;
    for (int i = 0; i <= n; i++) {
        if (nums[i] == dupitem) dupos.push_back(i);
        if (dupos.size() == 2) break;
    }
    int d = dupos[1] - dupos[0] - 1;
    for (int k = 1; k <= n+1; k++) {
        cout << compute(n, k, d) << endl;
    }


}


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

using namespace std;

#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
#define mem(a,i) memset(a,i,sizeof(a))
#define ll long long
const int maxn=1e6+10;
const int mod=1e9+7;
const double pi=acos(-1);

int a[maxn];
int main()
{
    int n;
    sint(n);
    for(int i=0;i<n;i++)
        sint(a[i]);
    int ans=1e9;
    for(int i=0;i<=100;i++)
    {
        int sum=0;
        for(int j=0;j<n;j++)
        {
            sum+=(a[j]-i)*(a[j]-i);
        }
        ans=min(ans,sum);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[allow(unused_macros)]
macro_rules ! vec_md { ( $ init : expr ; $ ( $ dim : expr ) ;* ) => { vec_md ! ( $ ( $ dim ) ;* => $ init ) } ; ( $ head : expr ; $ ( $ tail : expr ) ;* => $ init : expr ) => { vec ! [ vec_md ! ( $ ( $ tail ) ;* => $ init ) ; $ head ] } ; ( $ head : expr => $ init : expr ) => { vec ! [ $ init ; $ head ] } ; }

#[allow(unused_macros)]
macro_rules! chmax {
    ( $ x : expr , $ y : expr ) => {
        if $x < $y {
            $x = $y;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        n: usize,
        a: [[i64;n];n]
    }

    let mut cost = vec![0i64;1<<n];
    for mask in 0..1<<n {
        for i in 0..n {
            for j in i+1..n {
                if mask >> i & 1 == 1 && mask >> j & 1 == 1 {
                    cost[mask] += a[i][j];
                }
            }
        }
    }

    let mut dp: Vec<Option<i64>> = vec![None;1<<n];
    dp[0] = Some(0);
    for mask in 0..1<<n {
        for sub_mask in bit_subsets_of_subset(mask) {
            if let Some(src) = dp[mask-sub_mask] {
                chmax!(dp[mask], Some(src + cost[sub_mask]));             
            }
        }
    }
    println!("{}", dp[(1<<n)-1].unwrap());
}

#[doc = " reverse order"]
#[allow(dead_code)]
fn bit_subsets_of_subset(sup: usize) -> Vec<usize> {
    let mut ret = vec![];
    let mut sub = sup;
    loop {
        ret.push(sub);
        if sub == 0 {
            break;
        }
        sub = (sub - 1) & sup;
    }
    ret
}

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

int a[] = {100, 101, 102, 103, 104, 105};
int memo[7][100010];

bool dp(int i, int x){
    if(i == 6){
        return x == 0;
    }

    if(memo[i][x] != -1) return memo[i][x];

    bool ans = dp(i+1, x);
    if(x >= a[i]){
        ans |= dp(i, x-a[i]);
    }

    return memo[i][x] = ans;
}

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

    memset(memo, -1, sizeof(memo));

    cout << (dp(0, x) ? 1 : 0) << endl;
    return 0;
}

Measured memory_bytes: 3072
n = int(input())
F = [tuple(map(int, input().split())) for _ in range(n)]
P = [tuple(map(int, input().split())) for _ in range(n)]
ans = -10 ** 18

for i in range(1,2**10):
  tmp = 0
  lst = [0]*n
  for j in range(10): #時間帯
        if (i >> j) & 1: #開けるとした時
            for k in range(n):
                lst[k] += F[k][j]
  for k in range(n):
      tmp += P[k][lst[k]]
  ans = max(ans, tmp)
 
 
print (ans)

Measured memory_bytes: 3064
N=int(input())
D=list(map(int,input().split()))
from collections import defaultdict
dic=defaultdict(int)
for d in D:
    dic[d]+=1
a=[0,24]
f=0
T=[]
for k in dic.keys():
    for i in range(dic[k]):
        T.append(k)
T.sort()
for t in T:
    if f:
        t=24-t
    a.append(t)
    f^=1
a.sort()
r=12
for i in range(len(a)-1):
    r=min(r,a[i+1]-a[i])
print(r)

Measured memory_bytes: 3316
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int A,B,C;
    cin>>A>>B>>C;
    int s{};
    while(C>0){
        C=C-A;
        s++;
        if(s%7==0)C=C-B;
    }
    cout<<s<<endl;
}



Measured memory_bytes: 3116