akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

int main(){
	int n;
	cin >> n;
	int64_t a[n];
	for(int64_t &i:a) cin >> i;
	int64_t sum = accumulate(a, a + n, 0ll), x = max(int64_t(0), sum - n * (n - 1));
	for(int64_t &i:a) i += x;
	int64_t l = 0, r = sum;
	while(1 < r - l){
		int64_t mid = (l + r) / 2, puni = 0;
		for(int64_t &i:a) puni += max(int64_t(0), (i - mid) / (n + 1));
		(puni <= x ? r : l) = mid;
	}
	int64_t times = 0;
	for(int64_t &i:a) times += max(int64_t(0), (i - r) / (n + 1));
	for(int64_t &i:a) i -= (n + 1) * max(int64_t(0), (i - r) / (n + 1));
	for(; times < x; times++) *max_element(a, a + n) -= (n + 1);
	while(n <= *max_element(a, a + n)){
		for(int64_t &i:a) i++;
		*max_element(a, a + n) -= n + 1;
		times++;
	}
	cout << times << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll a,b;
    cin>>a>>b;
    if(a>b)
        swap(a,b);
    if((b-a)%2==0)
        cout<<a+(b-a)/2<<endl;
    else
        cout<<"IMPOSSIBLE"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define itn int
using ll = long long;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };


signed main() {
	int a, b, c, d, e, k;
	int n[6];
	int i;
	rep(i, 5) cin >> n[i];
	cin >> k;
	int j;
	bool can = true;
	rep(i, 5) {
		rep(j, 5) {
			if (max(n[i], n[j]) - min(n[i], n[j]) > k) {
				can = false;
				break;
			}
		}
	}
	if (can)
		cout << "Yay!" << endl;
	else {
		cout << ":(" << endl;
	}
	return 0;
}



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

int main()
{
  ll n; cin >> n;
  vector<ll> x(n);
  for (int i=0; i<n; i++){
    cin >> x[i];
  }
  sort(x.begin(),x.end());
  ll ans = 1LL<<60;
  for (int k=1; k<=100; k++) {
    ll sum = 0;
    rep(i, n) sum += pow(x[i]-k, 2);
    ans = min(ans, sum);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 8
#define OK -1
#define NOT 1

int row[N],col[N],dpos[2*N-1],X[N][N];
int dneg[2*N-1];

void freedom(){
int i;
  for(i=0;i<N;i++){
    row[i]=OK;
    col[i] = OK;
  }
  for(i=0;i<2*N-1;i++){
    dpos[i] = OK;
    dneg[i]=OK;
  }
}

void output(){
  int i,j;
  for(i = 0;i<N;i++){
    for(j = 0;j<N;j++){
      if(X[i][j]){
	if(row[i]!=j)return;
      }
    }
  }
  for(i= 0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i] == j){
	printf("Q");
      }else{
	printf(".");
      }
    }
    printf("\n");
  }
}

void Queen(int i){
  int j;

  if(i == N){
    output();
    return;
  }
  for(j = 0;j<N;j++){
    if(col[j] == NOT || dpos[i+j]== NOT || dneg[i-j+N-1]==NOT )continue;

    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = 1;

    Queen(i+1);

    col[j] = dpos[i+j] = dneg[i-j+N-1] = -1;
    
  }
}

void recursive(int i){
  int j;
  if(i == N){
    output();
    return;
  }
  for(j = 0;j<N;j++){
    if(NOT == col[j] || NOT == dpos[i+j] || NOT == dneg[i-j+N-1]){
      continue;
    }
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT;
    recursive(i+1);
   row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = OK;
    
  }


}


  int main(){
  freedom();
  int i,j,k,r,c;
 
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      X[i][j]=0;
    }
  }
  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    X[r][c]=1;
  }
 
  recursive(0);
  return 0;
}



Measured memory_bytes: 2112
#include<stdio.h>

int ifok(int a);

int main()
{
	int r,d,i;
	int x2000[11]={0};
	scanf("%d %d %d",&r,&d,x2000);
	for(i=0;i<10;i++)
	{
		x2000[i+1]=r*x2000[i]-d;
		printf("%d\n",x2000[i+1]);
	}
	
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdlib>

using namespace std;

int n, t, x, y, u, v ,w, d;

int main(void) {
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d %d", &t, &x, &y);
        d = abs(v-x)+abs(w-y);
        if (t<d) {
            cout << "No" << endl;
            return 0;
        }
        if ((t%2==0&&d%2!=0)||(t%2!=0&&d%2==0)){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
int main()
{
	fast;
	ll a,b;
	cin>>a>>b;
	if(a<b)
		cout<<0;
	else
		cout<<10;
	return 0;
}


Measured memory_bytes: 3608
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;


class Program
{
    public static long Read()
    {
        return long.Parse(Console.ReadLine());
    }

    public static long[] Reads()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }
    
    public static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        var n = Read();
        var s = Console.ReadLine();
        long count = 0;
        for(int i = 0; i < n - 2; i++)
        {
            if (s[i] == 'A')
            {
                i++;
                if (s[i] == 'B')
                {
                    i++;
                    if (s[i] == 'C')
                        count++;
                    else
                        i--;
                }
                else
                    i--;
            }
            
        }
        Console.WriteLine(count);

        Console.Out.Flush();
    }
}


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

using namespace std;

#define FOR(i, j, k) for(int i = j; i <= k; i++)
#define PB push_back
#define MEM(n, val) memset((n), val, sizeof(n))
#define F first
#define S second
#define MP make_pair
#define LL long long
#define MOD 1000000007

LL func(LL pos, LL lim)  {
    if(lim < 0)    {
        return 0;
    }
    LL quan = (1LL << pos);

    LL ans = ((lim + 1) / (quan * 2)) * quan;
    ans += max(0LL, ((lim + 1) % (quan * 2)) - quan);
    return ans;
}

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

    LL a, b;
    cin >> a >> b;

    LL ans = 0;
    FOR(i, 0, 62)   {
        LL no_of_one = func(i, b) - func(i, a - 1);
        if(no_of_one % 2)    {
            ans = ans | (1LL << i);
        }
    }
    cout << ans;

    return 0;
}
/**
*/


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

ll gcd(ll a,ll b){
    if(b==0){
        return a;
    }else{
        return gcd(b,a%b);
    }
}

ll lcm(ll a,ll b){
    ll d=gcd(a,b);
    return a/d*b;
}

int main(){
    ll X; cin>>X;
    ll ans=lcm(360,X);
    cout<<ans/X<<endl;
}

Measured memory_bytes: 3624
from itertools import combinations

def exclude_combi_idx(combis, scores):
    a = [score[1] for score in combis]
    v = []
    for score in scores:
        if score[1] in a:
            continue
        v.append(score)
    return v

def set_all_solve(combi):
    current = 0
    num = 0
    for item in combi:
        num += item[0]
        current += item[2]
    return num, current

def track_residue(num, score, current, target):
    for i in range(num):
        current += score
        if current >= target:
            return i + 1
    return None

def main():
    D, G = [int(c) for c in input().split()]
    items = []
    for idx in range(1, 1+D):
        num, bonasu = [int(c) for c in input().split()]
        items.append((idx * 100, num, bonasu))
    scores = [(num, idx,idx * num + bonasu) for idx, num, bonasu in items]
    max_prob = sum([num for num,_, _ in scores])
    min_prob = max_prob
    for i in range(0, D+1):
        combis = list(combinations(scores, i))
        # print('i = {}, combinations = {}'.format(i, combis))
        for combi in combis:
            s = 0
            prob = 0
            # print('combi = {}'.format(combi))
            tmp, tmp2 = set_all_solve(combi)
            prob += tmp
            s += tmp2
            # print('all solves num = {} score = {}'.format(prob, s))
            if s >= G:
                if prob < min_prob:
                    min_prob = prob
                    continue
            else:
                v = exclude_combi_idx(combi, scores)[-1] # 値が最大のもののみ必要
                res = track_residue(v[0], v[1], s, G)
                if res is None:
                    continue
                if res + prob < min_prob:
                    # print('track solve: num = {}, score = {}'.format(res + prob, s))
                    min_prob = res + prob
    print(min_prob)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
vector<pair<ll,ll> > v;
ll n;

int main() {
    cin>>n;
    ll a, b;
    for(int i=0;i<n;i++) {
        cin>>a>>b;
        v.pb(mp(b, a));
    }

    sort(v.begin(), v.end());
    ll sum = 0LL;

    for(int i=0;i<n;i++) {
        sum += v[i].second;

        if(sum > v[i].first) {
            cout<<"No\n";
            return 0;
        }
    }

    cout<<"Yes\n";
    return 0;
}

Measured memory_bytes: 6384
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define int long long
#define endl '\n'
#define pll pair<long long,long long>
//#define LONGLONG_MAX 10000000000000000
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a)%mod;}
                a=(a*a)%mod;
                b>>=1;
        }
    return ans;
        
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin>>s;
    for(auto i:s)cout<<'x';
    return 0;
}

Measured memory_bytes: 256
import collections
n = int(input())
a = []
for i in range(n):
    a.append(input())
# [d1, d2, d3, ..., dN]
a = [int(m) for m in a]#int型に直す
c = collections.Counter(a)
count = 0
for i in c:
    if c[i] % 2 != 0:
        count += 1
print(count)

Measured memory_bytes: 18132
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, DEP = 17;
int n,k,a[N],dp[DEP][N],ans;
void solve(int l,int r,int dep) {
  if (l == r) {
    int tmp = 0;
    for (int i = max(0,k-a[l]) ; i < k ; ++ i)
      tmp |= dp[dep][i];
    ans += 1 - tmp;
    return;
  }
  int mid = (l + r) >> 1;
  for (int i = 0 ; i < k ; ++ i)
    dp[dep+1][i] = dp[dep][i];
  for (int i = l ; i <= mid ; ++ i)
    for (int j = k-1 ; j >= a[i] ; -- j)
      dp[dep+1][j] |= dp[dep+1][j-a[i]];
  solve(mid+1,r,dep+1);
  for (int i = 0 ; i < k ; ++ i)
    dp[dep+1][i] = dp[dep][i];
  for (int i = mid+1 ; i <= r ; ++ i)
    for (int j = k-1 ; j >= a[i] ; -- j)
      dp[dep+1][j] |= dp[dep+1][j-a[i]];
  solve(l,mid,dep+1);
}
int main() {
  scanf("%d%d",&n,&k);
  for (int i = 1 ; i <= n ; ++ i)
    scanf("%d",&a[i]);
  dp[1][0] = 1;
  solve(1,n,1);
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

typedef long long INT;


int main() {
    INT N, ans = 0;
    cin >> N;
    
    for(INT i=1; i<=N; ++i) {
	INT n = N/i;
	ans += n*(n+1)/2*i;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3620
# abc 157
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, M = map(int, readline().split())
cond_list = []
for _ in range(0, M):
    cond_list.append(list(map(int, readline().split())))

MAX_LIM = int("1" + (N * '0'))

answer = -1
for i in range(0, MAX_LIM):
    i_str = str(i)
    if len(i_str) != N:
        continue
    flag = True
    for j, cond in enumerate(cond_list):
        if len(i_str) < cond[0]:
            flag = False
            break
        if i_str[cond[0]-1] != str(cond[1]):
            flag = False
            break
    if flag:
        answer = i
        break
print(answer)

Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
int main(void){
    int A,B,C,D,E,x,y,cou=0,v[3];
    char S[3],s[3],X,Y;
    scanf("%d %d %d",&A,&B,&C);
    if(A==B){
        printf("%d",C);
    }else if(B==C){
        printf("%d",A);
    }else{
        printf("%d",B);
    }
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
using namespace std;
#define ll long long
int main(){
    ll N;
    cin >> N;
    ll A[N],cnt[N+1];
    ll i;
    for(i=0;i<N+1;i++){
        cnt[i]=0;
    }
    for(i=0;i<N;i++){
        cin >> A[i];
        ++cnt[A[i]];
    }
    ll b=0;
    for(i=0;i<N+1;i++){
        b+=cnt[i]*(cnt[i]-1)/2;
    }
    for(i=0;i<N;i++){
        cout << b-cnt[A[i]]+1 << endl;
    }
    return 0;
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

vector<ll> enum_div(ll n){
	vector<ll> ret;
	for(ll i=1;i*i<=n;++i){
		if(n%i==0){
			ret.push_back(i);
			if(i*i!=n){
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

ll gcd(ll a,ll b){
	if(a<b){
		swap(a,b);
	}

	while(ll r=(a%b)){
		a = b;
		b = r;
	}
	return b;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	ll A=in<ll>(),B=in<ll>();
	auto NA=enum_div(A);
	auto NB=enum_div(B);
	sort(ALL(NA));
	sort(ALL(NB));
	vector<ll> C;
	set_intersection(ALL(NA),ALL(NB),back_inserter(C));

	int M=C.size();
	vector<int> F(M,0);
	for(int i=0;i<M;i++){
		for(int j=i+1;j<M;j++){
			if(!F[i] && gcd(C[i],C[j])!=1) F[j]=1;
		}
	}

	out(count(ALL(F),0));

	return 0;
}


Measured memory_bytes: 512
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()

	if N == 1:
		print(0)
		sys.exit()

	ans = 0
	for i in range(1,N):
		ans += i

	print(ans)

if __name__ == "__main__":
	main()


Measured memory_bytes: 40732
f = readline
f = f.split(" ").map(&:to_i)

A = f[0] + f[1]
B = f[0] - f[1]
C = f[0] * f[1]

ary = Array.new(3)
ary[0] = A
ary[1] = B
ary[2] = C

puts ary.max

Measured memory_bytes: 1916
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int a, b; cin>>a>>b;
	for(int i=0; i<100; i++){
		if(i*a-i+1>=b){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
Pajew = [i for i in range(N)]
import sys
sys.setrecursionlimit(1000000)

def find(x, Pajew):
    if Pajew[x] == x:
        return x
    else:
        a = find(Pajew[x], Pajew)
        Pajew[x] =a
        return a

def unite(x, y):
    x = find(x, Pajew)
    y = find(y, Pajew)
    if x != y:
        Pajew[x] = y

for _ in range(M):
    a, b = map(int, input().split())
    unite(a-1, b-1)

grou = 0
for i in range(N):
    if i == Pajew[i]:
        grou +=1


print(grou-1)

Measured memory_bytes: 75272
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int N;
int A[4009], bsum[2009], wsum[2009];
int black[2009][2009], white[2009][2009];
int dp[2009][2009];
char C[4009];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>N;
    rep(i,2*N) cin>>C[i]>>A[i];
    rep(i,2*N) A[i]--;
    
    rep(i,2*N){
        int a=A[i];
        if(C[i]=='B'){
            rep(j,N+1){
                black[a][j]=bsum[a]+wsum[j];
            }
            for(int j=a;j>=0;j--){
                bsum[j]++;
            }
        }else{
            rep(j,N+1){
                white[a][j]=bsum[j]+wsum[a];
            }
            for(int j=a;j>=0;j--){
                wsum[j]++;
            }
        }
    }
    
    rep(i,2009)rep(j,2009) dp[i][j]=INF;
    dp[0][0]=0;
    rep(i,N+1)rep(j,N+1){
        if(i<N) chmin(dp[i+1][j],dp[i][j]+black[i][j]);
        if(j<N) chmin(dp[i][j+1],dp[i][j]+white[j][i]);
    }
    cout1(dp[N][N]);
}

Measured memory_bytes: 47488
import itertools
import math

def kyori(data1, data2):
    result = 0
    for i in range(len(data)):
        result += (data1[i]-data2[i])**2
    return math.sqrt(result)

N,D = map(int, input().split())
X = []
for _ in range(N):
    data = list(map(int, input().split()))
    X.append(data)

comb = itertools.combinations(X, 2)
ans = 0
for c in comb:
   if kyori(c[0],c[1]).is_integer():
       ans += 1

print(ans)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
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; }
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
int main(){
  int n;cin>>n;
  int c=0,a=0;
  while(true){
    a+=n;c++;
    if(a%360==0){
      cout<<c;return 0;
    }
  }
}

Measured memory_bytes: 3592
echo $(($(egrep '^M|^A|^R|^C|^H'|cut -c-1|tr MARCH 1-5|awk '{a[$0]++}END{b=0;for(i=1;i<=5;i++)for(j=i+1;j<=5;j++)for(k=j+1;k<=5;k++)if(a[i]&&a[j]&&a[k])print a[i] "*" a[j] "*" a[k]}'|xargs|tr ' ' '+')))

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

int main() {
    uint64_t N;
    cin >> N;
    vector<uint64_t> v(N+1);
    v[0] = 2;
    v[1] = 1;
    for (int i = 2; i <= N; i++) {
        v[i] = v[i-2] + v[i-1];
    }

    cout << v[N] << endl;
}

Measured memory_bytes: 256
import sys
from collections import deque
input = sys.stdin.readline

def reorder(que, v):
  for i in range(len(que)):
    if que[i] > v:
      que[i] -= 1
  return que

def factorial(n):
  if n > 1:
    return n * factorial(n-1)
  return 1

def get_order(que):
  n = 0
  while(que):
    q = que.popleft()
    n += ((q-1) * factorial(len(que)))
    que = reorder(que, q)
  return n

N = int(input())
P = deque(list(map(int, input().split())))
Q = deque(list(map(int, input().split())))

n = get_order(P)
m = get_order(Q)
print(abs(n-m))

Measured memory_bytes: 3316
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.List;

public class Main {
    public static Scanner sc = new Scanner(System.in);
    public static int cx;
    public static int cy;
    public static int[][] ary;
    public static int count;
    public static void main(String[] args) throws Exception {
        while (sc.hasNext()){
            ary = new int[21][21];
            cx = 10;
            cy = 10;
            count = 0;
            int n = sc.nextInt();
            if (n == 0) break;
            for (int i = 0; i < n; i++) {
                ary[sc.nextInt()][sc.nextInt()] = 1;
            }
            
            int m = sc.nextInt();
            for (int i = 0; i < m; i++) {
                String s = sc.next();
                int dis = sc.nextInt();

                int x = 0;
                int y = 0;
                if (s.equals("N")) {
                    y = 1;
                } else if (s.equals("S")) {
                    y = -1;
                } else if (s.equals("E")) {
                    x = 1;
                } else if (s.equals("W")) {
                    x = -1;
                }
                
                for (int j = 0; j < dis; j++) {
                    move(x, y);
                }
            }
            
            if (count == n) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
    
    public static void move(int x, int y) {
        cx += x;
        cy += y;
        if (ary[cx][cy] == 1) {
            ary[cx][cy] = 0;
            count++;
        }
    }
}

Measured memory_bytes: 43968
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int> nums;
    int now = 1;
    int cnt = 0;
    for (size_t i = 0; i < n; i++)
    {
        if(s[i] == (char)('0' + now)) cnt++;
        else {
            nums.push_back(cnt);
            now = 1 - now;
            cnt = 1;
        }
    }
    if(cnt != 0) {
        nums.push_back(cnt);
    }

    if(nums.size() % 2 == 0) nums.push_back(0);
    int ans = 0;
    int add = 2 * k + 1;
    vector<int> sums(nums.size()+1);
    sums[0] = 0;
    for (size_t i = 0; i < nums.size(); i++)
    {
        sums[i+1] = nums[i] + sums[i];
    }
    
    for (size_t i = 0; i < nums.size(); i+=2)
    {
        int tmp = 0;
        int left = i;
        int right = min(i + add, nums.size());
        ans = max(ans, sums[right] - sums[left]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1272
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    string s; cin >> s;
    int a, b;
    for(int i=0; i<s.size(); ++i){
        if(s[i] == 'A') { a = i; break; }
    }
    for(int i=s.size()-1; i>=0; --i){
        if(s[i] == 'Z') { b = i; break; }
    }

    cout << b+1-a << endl;
}

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

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

int N;
ll X;
ll H[505];
ll P[505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	H[0]=P[0]=1;
	for(i=1;i<=50;i++) {
		H[i]=3+2*H[i-1];
		P[i]=1+2*P[i-1];
	}
	
	cin>>N>>X;
	ll ret=0;
	while(N>0 && X>0) {
		if(X>=2+2*H[N-1]) {
			ret+=1+2*P[N-1];
			X=0;
			break;
		}
		if(X>=2+H[N-1]) {
			ret+=1+P[N-1];
			X-=2+H[N-1];
		}
		else if(X==1+H[N-1]) {
			ret+=P[N-1];
			X-=1+H[N-1];
		}
		else {
			X--;
		}
		N--;
		
	}
	
	if(X) ret++;
	cout<<ret<<endl;
	
}


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


Measured memory_bytes: 256
A,B,C = map(int,input().split())
K = int(input())
array = []
for i in range(3):
    array.append([A,B,C])

for i in range(3):
    array[i][i] *= 2**K

print(max(sum(array[0]),sum(array[1]),sum(array[2])))
    



Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main()
{
	// 入力
	int N, L;
	cin >> N >> L;
	
	int answer = 0;
	// 食べたリンゴの味
	int eatApple = L;
	// 最小の絶対値を求める
	int minAbs = abs(L);

	for (int i = 0; i < N; i++)
	{
		answer += L + i;
		
		if (minAbs > abs(L + i)) {
			minAbs = abs(L + i);
			// 味の値
			eatApple = L + i;
		}
	}
	// 総和の味 - 食べたリンゴの最小の味
	answer -= eatApple;
	
	// 出力
	cout << answer << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
	if(a>b)
		swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
	char str[100];
	sprintf(str,"%s.in",s);
	freopen(str,"r",stdin);
	sprintf(str,"%s.out",s);
	freopen(str,"w",stdout);
#endif
}
int rd()
{
	int s=0,c;
	while((c=getchar())<'0'||c>'9');
	do
	{
		s=s*10+c-'0';
	}
	while((c=getchar())>='0'&&c<='9');
	return s;
}
int upmin(int &a,int b)
{
	if(b<a)
	{
		a=b;
		return 1;
	}
	return 0;
}
int upmax(int &a,int b)
{
	if(b>a)
	{
		a=b;
		return 1;
	}
	return 0;
}
queue<int> q1;
stack<int> q2;
int main()
{
	ll n;
	scanf("%lld",&n);
	int m=0;
	n++;
	while(n>1)
	{
		if(n&1)
		{
			q1.push(++m);
			n--;
		}
		else
		{
			q2.push(++m);
			n>>=1;
		}
	}
	printf("%d\n",2*m);
	while(!q1.empty())
	{
		printf("%d ",m-q1.front()+1);
		q1.pop();
	}
	while(!q2.empty())
	{
		printf("%d ",m-q2.top()+1);
		q2.pop();
	}
	int i;
	for(i=1;i<=m;i++)
		printf("%d ",i);
	return 0;
}

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

int main(){
  int K, A, B;
  cin >> K >> A >> B;
 
  for(int i=A;i<B+1;i++){
  	if(i%K==0){
      cout << "OK" << endl;
      return 0;
    }  
  }
  cout << "NG" << endl;
}


Measured memory_bytes: 3596
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}


int main()
{
  int phi[1000001],t,n;
  ll dp[1000001];
  
  REP(i,1000001)phi[i] = i;
  for(int i=2;i<1000001;i++){
    if(phi[i] == i){
      for(int j=i;j<1000001;j+=i){
        phi[j] = phi[j]/i*(i-1);
      }
    }
  }
  dp[0] = 1;
  dp[1] = 2;
  for(int i=2;i<1000001;i++){
    dp[i] = dp[i-1] + phi[i];
  }

  cin >> t;
  REP(i,t){
    cin >> n;
    cout << dp[n] << endl;
  }
  
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

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

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}




Measured memory_bytes: 14808
double x,y,r,X,Y,R;main(){for(;~scanf("%*d%lf%lf%lf%lf%lf%lf"+!!R*3,&x,&y,&r,&X,&Y,&R);printf("%d\n",x+R<r?2:x+r<R?-2:r+R<x?0:1))x=hypot(x-X,y-Y);}

Measured memory_bytes: 0
#include <stdio.h>

int main(void)
{
  int k, s, x, y, z, num = 0;

  /*入力*/
  scanf("%d %d", &k, &s);

  /*処理*/
  for (x=0;x<=k;x++) {
    for (y=x;y<=k;y++) {
      for (z=y;z<=k;z++) {
        if (x + y + z == s) {
          if(x == y && y == z) {
            num++;
            break;
          } else if (x == y || x == z || y == z) {
            num = num + 3;
            break;
          } else {
            num = num + 6;
            break;
          }
        }
      }
    }
  }

  /*出力*/
  printf("%d\n", num);
  return 0;
}


Measured memory_bytes: 1692
#include <bits/stdc++.h>
 
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define pb push_back
#define MOD 1000000007
#define ull unsigned long long
#define all(x) (x).begin(), (x).end()
#define read(a, n) for(ll i = 0;i<n;i++) cin>>a[i];
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
const int INF = 1e9 + 5;

void solve() {
	ll n, W;
	cin>>n>>W;
	
	ll w[n], v[n];
	
	for(ll i = 0;i<n;i++) {
		cin>>w[i]>>v[i];
	}
	
	ll dp[n][W+1];
	memset(dp, 0, sizeof(dp));
	
	for(ll i = 0;i<n;i++) {
		dp[i][0] = 0;
	}
	
	for(ll i = 1;i<=W;i++) {
		if(i >= w[0]) {
			dp[0][i] = v[0];
		}
	}
	
	for(ll i = 1;i<n;i++) {
		for(ll j = 1;j<=W;j++) {
			if(j-w[i] < 0) {
				dp[i][j] = dp[i-1][j];
			}
			else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
			}
		}
	}
	
	cout<<dp[n-1][W]<<"\n";
}

int main()
{
	fastio;
	
	int T = 1;
	//cin>>T;
	//int tc = 1; 
	while(T--) {
		//cout<<"Case #"<<tc<<": ";
		solve();
		//tc++;
	}	
	return 0;
}


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

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;

typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// ordered_set X;
// *X.find_by_order(i) = ith largest element (counting from zero)
// X.order_of_key(k) = number of items in X < k (strict lt)

constexpr ll BIG = 1000000000000L;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    vll A(N);
    for(int i=0;i<N;i++) cin >> A[i];

    ll total = 0;
    for (int i=0;i<N;i++) total += A[i];

    ll best = total;
    //cout << "total " << total << endl;
    ll cum = 0;
    for (int i=0;i<N;i++) {
        cum += A[i];
        best = min(best, abs(total - 2*cum));
        //cout << cum << " " << abs(total - 2*cum) << endl;
    }

    cout << best << endl;

    return 0;
}

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


ll cnt = 0,n;
bool is_used[3] = {false};

void dfs(ll d,ll memo){
	//cout << memo << endl;
	if(memo > n) return ;
	
	if(d >= 10){
		rep(j,0,3) is_used[j] = false;
		ll temp = memo;
		rep(j,0,d){
			switch(temp % 10){
				case 3:
					is_used[0] = true;
					break;
				case 5:
					is_used[1] = true;
					break;
				case 7:
					is_used[2] = true;
					break;
			}
			temp /= 10;
		}
		
		rep(j,0,3){
			if(!is_used[j]) break;
			else if(j == 2) cnt++;
		}
		return;
	}
	
	rep(i,0,4){
		switch(i){
			case 0:
				dfs(d+1,memo+3*pow(10,d));
				break;
			case 1:
				dfs(d+1,memo+5*pow(10,d));
				break;
			case 2:
				dfs(d+1,memo+7*pow(10,d));
				break;
			case 3:
				rep(j,0,3) is_used[j] = false;
				ll temp = memo;
				rep(j,0,d){
					switch(temp % 10){
						case 3:
							is_used[0] = true;
							break;
						case 5:
							is_used[1] = true;
							break;
						case 7:
							is_used[2] = true;
							break;
					}
					temp /= 10;
				}
				
				rep(j,0,3){
					if(!is_used[j]) break;
					else if(j == 2) cnt++;
				}
				
				//cout << is_used[0] << is_used[1] << is_used[2] << endl;
				break;
		}
	}
	return;
}


int main(){
	cin >> n;
	
	rep(i,0,3){
		switch(i){
			case 0:
				dfs(1,3);
				break;
			case 1:
				dfs(1,5);
				break;
			case 2:
				dfs(1,7);
				break;
		}
	}
	
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
def solve():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(K):

        arr = [0] * (N + 1)

        for ind,j in enumerate(A):
            arr[max(ind-j,0)] += 1
            arr[min(ind+j+1, N)] -= 1

        A[0] = arr[0]
        for k in range(N-1):
            A[k+1] = A[k] + arr[k+1]

        if arr[0] ==N and arr[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    ans = solve()
    print(*ans)



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

const int maxn = 100000 +5;
int n, m, tot, head[maxn], color[maxn], ma;
struct edge {
	int to, nxt;
} G[maxn << 1];

inline void add_edge (int u, int v) {
	tot ++;
	G[tot].to = v;
	G[tot].nxt = head[u];
	head[u] = tot;
}

void dfs(int x, int now = 0, int fa = 0) {
	color[x] = now, now ^= 1;
    for (int j = head[x]; j; j = G[j].nxt) {
        if (color[G[j].to] == -1) dfs(G[j].to, now, x);
        if (color[G[j].to] != now) {
        	printf ("%lld\n", (long long)n * (n - 1) / 2 - m);
        	ma = 1;
        	return ;
		}
		if (ma) return ;
    }
}

int main() {
	scanf ("%d %d", &n, &m);
	int u, v;
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d", &u, &v);
		add_edge (u, v); add_edge(v, u);
	}
	memset (color, 255, sizeof (color));
	dfs(1);
	if (ma) return 0;
	int a = 0, b = 0;
	for (int i = 1; i <= n; i++) {
		if (color[i]) a++;
		else b++;
	}
	printf ("%lld", (long long)a * b - m);
	return 0;
}

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

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;

#define endl '\n'
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define int long long
#define pb push_back
#define f(i,l,r) for(ll i=l;i<=r;i++)
#define rf(i,r,l) for(ll i=r;i>=l;i--)
#define Max 5000001
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

#define d0(a) cout<<a<<' ';
#define d1(a) cout<<a<<endl;
#define d2(a,b) cout<<a<<' '<<b<<endl;
#define d3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define d4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
#define d5(a,b,c,d,e) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;
#define d6(a,b,c,d,e,f) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<endl;

const ll N=2e3+5,mod=1e9+7,bit=61;

ll n,dis[N][N];
vector<ll> adj[N];

void bfs(ll id,ll s)  // Set inf appropriately
{
    queue<int> mq;
    mq.push(s);
    for(int i=0;i<=n;i++)
    {
        dis[id][i]=inf;
    }
    dis[id][s]=0;
    while(!mq.empty())
    {
        auto u=mq.front();
        mq.pop();
        for(auto v:adj[u])
        {
            if(dis[id][v]>1+dis[id][u])
            {
                dis[id][v]=1+dis[id][u];
                mq.push(v);
            }
        }
    }
}

signed main()
{
    fast;

    ll t=1;
    //cin>>t;
    while(t--)
    {
        cin>>n;
        f(i,1,n-1)
        {
            adj[i].pb(i+1);
            adj[i+1].pb(i);
        }
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        f(i,1,n)
        {
            bfs(i,i);
        }
        ll ans[n]={0};
        f(i,1,n)
        {
            f(j,i+1,n)
            {
                ans[dis[i][j]]++;
            }
        }
        f(i,1,n-1)
        {
            cout<<ans[i]<<'\n';
        }
        cout<<endl;
    }
    return 0;
}


















Measured memory_bytes: 31744
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int x = 0;

        try {
            x = Integer.parseInt(in.readLine());

        } catch(Exception e) {
            e.printStackTrace();
        }

        System.out.println((int) Math.pow((double) x, 3d));
    }
}

Measured memory_bytes: 24280
/*-------enazuma11----------------*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(v) v.begin(),v.end()
#define inc(a,n) sort(a,a+n)
#define dec(a,n) sort(a,a+n,greater<int>() )
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define F first
#define S second
#define M 1000000007
 
/* int x[]={-1,-1,0,1,1,1,0,-1};
int y[]={0,1,1,1,0,-1,-1,-1};
*/
/* int x[]={-1,0,1,0};
int y[]={0,1,0,-1};
*/

const int N=105;
const int W=1e5+5;
ll a[N];
ll b[N];
ll n,w;
ll dp[N][W];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		ll i,j;
		cin>>n>>w;
		rep(i,0,n){
			cin>>a[i]>>b[i];
		}
		rep(i,0,n+1)
		{
			rep(j,0,w+1)
			{
				if(i==0||j==0)
				dp[i][j]=0;
				else{
					if(a[i-1]<=j)
					dp[i][j]=max(dp[i-1][j],b[i-1]+dp[i-1][j-a[i-1]]);
					else
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		cout<<dp[n][w]<<'\n';
	
		
	}
	return 0;
}


Measured memory_bytes: 80128
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
int ABS(int a) {if(a<0) a = -a; return a;}
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数の個数*/int divisor_number(int n){auto p = prime_factor(n); int res = 1; for(auto x:p)res*=(x.second+1); return res;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    VI a(3); REP(i,3) cin >> a[i]; SORT(a);
    Yn(a[0]+a[1]==a[2]);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll n;
	cin>>n;
	vector<int>v;
	while(n>0)
	{
		v.push_back(n%26);
		if(n%26==0) n=n/26-1;
		else n=n/26;
	}
	for(auto it=v.rbegin();it!=v.rend();++it)
	if(*it==0) cout<<'z';
	else cout<<(char)(*it+96);
	return 0;
}

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

template<typename T>
struct WarshallFloyd {
    const T INF = numeric_limits<T>::max();
    int n;
    vector<vector<T>> dp;
    WarshallFloyd(int n) : n(n), dp(n, vector<T>(n, INF)) {
        for (int i = 0; i < n; i++) dp[i][i] = 0;
    }
    void relax(int k) {
        for (int i = 0; i < n; i++) if (dp[i][k] != INF)
            for (int j = 0; j < n; j++) if (dp[k][j] != INF)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    }
    bool build() {
        for (int k = 0; k < n; k++) relax(k);
        return !has_negative_cycle();
    }
    void add_edge(int u, int v, T cost) {
        dp[u][v] = min(dp[u][v], cost);
        for (int k : {u, v}) relax(k);
    }
    bool has_negative_cycle() {
        for (int i = 0; i < n; i++) if (dp[i][i] < 0) return true;
        return false;
    }
    friend ostream& operator<<(ostream& os, WarshallFloyd<T> &wf) {
        for (int i = 0; i < wf.n; i++) for (int j = 0; j < wf.n; j++) {
            if (wf.dp[i][j] == wf.INF) os << "INF"; else os << wf.dp[i][j];
            os << " \n"[j == wf.n - 1];
        }
        return os;
    }
};

int main() {
    int n, m; cin >> n >> m;
    WarshallFloyd<long long> wf(n);
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        wf.add_edge(a, b, c);
    }
    if (wf.has_negative_cycle()) return !(cout << "NEGATIVE CYCLE" << endl);
    cout << wf;
    return 0;
}



Measured memory_bytes: 3252
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 M = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();

		int x[] = new int[N];
		int y[] = new int[M];

		int maxX = 0;
		int minY = 100;

		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
		}

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

		Arrays.sort(x);
		Arrays.sort(y);

		maxX = Math.max(X, x[N - 1]);
		minY = Math.min(Y, y[0]);

		if (maxX < minY) {
			System.out.println("No War");
		} else {
			System.out.println("War");
		}
	}
}


Measured memory_bytes: 23124
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let it = stdin.lock().bytes().map(|c| c.unwrap() as char);
    let (fs, ft) = (|c: &char| c.is_whitespace(), |c: &char| !c.is_whitespace());
    let token = it.skip_while(fs).take_while(ft).collect::<String>();
    token.parse().ok().unwrap()
}
#[allow(dead_code)]
fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    f(std::io::BufWriter::new(out.lock()));
}
#[allow(unused_macros)]
macro_rules! debug {
    ($($var:expr),*) => { #[cfg(debug_assertions)] {
        $({ match &$var { v => eprint!("{}={:?} ", stringify!($var), v) } })*
        eprintln!();
    }};
}

fn main() {
    let a: i32 = input();
    let b: i32 = input();

    println!("{}", (b - 1 + a - 2) / (a - 1));
}


Measured memory_bytes: 4352