akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int k, s;
    cin >> k >> s;
    int ans = 0;
    for(int x = 0; x <= k; x++) {
        for(int y = 0; y <= k; y++) {
            int z = s - x - y;
            if(z >= 0 && z <= k) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3600
import java.io.*;
import java.util.Arrays;
class Main{
    public static void main(String[] args) throws IOException {
        int i,n,m; 
        String line,chr;
        String str;
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        for(;;){
            str = in.readLine();
            if("-".equals(str)) break;
            n = Integer.parseInt(in.readLine());
            for(i=0;i<n;i++){
                m = Integer.parseInt(in.readLine());
                chr = str.substring(0,m);
                line = str.substring(m,str.length());
                str = line+chr;
            }
            System.out.println(str);
        }
        System.out.flush();
    }
}

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

int ans=1;

int main(void)
{
    //input
    int n;
    cin >> n;
    set<string> st;
    for(int i=0; i<n; i++) {
        string tmp; cin >> tmp;
        st.insert(tmp);
    }
    //output
    cout << st.size() << endl;
    
    return 0;
}

Measured memory_bytes: 19048
#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb push_back
 
template<typename T> bool chkmin(T&a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool chkmax(T&a, T b) { return a < b ? a = b, 1 : 0; }
 
const int maxn = 300000 + 10;

int n, m;
LL a[maxn], b[maxn], c[maxn], ans;
void add(int l, int r) { b[l+2] ++; b[r+1] --; c[r+1] += l-r+1; }

int main() {
    //freopen("out.txt", "r", stdin);
    //freopen("tmp.out", "w", stdout);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++) {
        if(a[i] == a[i-1]) continue;
        ans += a[i] > a[i-1] ? a[i] - a[i-1] : a[i]+m - a[i-1];

        if(a[i] >= a[i-1]) { add(a[i-1], a[i]);  }
        else { add(a[i-1], a[i] + m); }
    }

    static LL del[maxn];
    LL tot = 0, delta = 0, res = LLONG_MAX;
    for(int i = 1; i <= (m*2); i++) {
        tot += b[i];
        delta += tot + c[i];
        del[i] = delta;
    }
    for(int i = 1; i <= m; i++)
        chkmin(res, ans - del[i] - del[i+m]);
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 7552
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
using namespace std;

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

int n,k,q;
ll a[2010];

bool solve(ll y,ll x){
    int s=0,t=0,l=0;
    FOR(i,0,n+1){
        if(a[i]<y){
            l+=max(min(s-k+1,t),0);
            //l+=min(s-k+1,t),0;
            s=t=0;
        }else{
            if(a[i]<=x){
                t++;
            }
            s++;
        }
    }
    return q<=l;
}

int main(){
    cin>>n>>k>>q;
    FOR(i,0,n) cin>>a[i];
    a[n]=0; //番兵
    ll m=2*INF;
    FOR(i,0,n){
        ll y=a[i];
        ll st=0,en=2*INF;//x
        while(st<en-1){
            ll mid=(st+en)/2;
            if(solve(y,mid)) en=mid;
            else st=mid;
        }
        //cout<<y<<" "<<en<<endl;
        m=min(m,en-y);
    }
    co(m);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  ll n;
  cin>>n;
  ll a[n];
  rep(i,0,n) cin>>a[i];
  ll x=a[0];
  rep(i,1,n) x^=a[i];

  ll b[n];
  rep(i,0,n){
    b[i]=x^a[i];
  }
  rep(i,0,n) cout<<b[i]<<" ";
  cout<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 6788
A,B,C,D,E,F = map(int,input().split())

ans = [0,A*100]

for a in range(31):
    for b in range(31):
        if a*A+b*B==0 or a*A+b*B>=F:
            continue
        for c in range((3000//C)+1):
            if c*C>E*(a*A+b*B) or (a*A+b*B)*100+c*C>F:
                continue
            d = min((E*(a*A+b*B)-c*C)//D,(F-((a*A+b*B)*100+c*C))//D)
            if (a*A+b*B)*100+(c*C+d*D)>F or c*C+d*D>(a*A+b*B)*E:
                continue
            ans_tmp = [c*C+d*D,(a*A+b*B)*100]
            if ans_tmp[0]*ans[1] > ans[0]*ans_tmp[1]:
                ans = ans_tmp
print(ans[1]+ans[0],ans[0])


Measured memory_bytes: 45036
import javax.swing.*;
import java.io.*;
import java.sql.Struct;
import java.text.DecimalFormat;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        boolean[] dp = new boolean[k + 1];
        dp[0] = false;
        for ( int i = 1; i < dp.length; i++) {
            boolean res = false;
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == i) {
                    res = true;
                } else if (i > arr[j] && !(dp[i - arr[j]])) {
                    res = true;
                }
            }
            dp[i] = res;
        }

        if (dp[k] == true) {
            System.out.println("First");
        } else {
            System.out.println("Second");
        }
    }
}

Measured memory_bytes: 22736
def main():
    a, b, c = (int(i) for i in input().split())
    for k in range(c):
        ap, bp = 0, 0
        if k % 2 == 0:
            if a % 2:
                a -= 1
            ap = a//2
            a = a//2
            b += ap
        else:
            if b % 2:
                b -= 1
            bp = b//2
            b = b//2
            a += bp
    print(a, b)


if __name__ == '__main__':
    main()


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

using namespace std;
using ll=long long;

ll calcm(string s){
    ll ret=0;
    ll tmp=0;
    int ind=0;
    char op='+';
    while(ind<s.size()){
        ll tn=s[ind]-'0';
        ++ind;
        if(ind>=s.size()||s[ind]=='+'){
            if(op=='*')tmp*=tn;
            else tmp+=tn;
            ret+=tmp;
            tmp=0;
        }
        else{
            if(op=='*')tmp*=tn;
            else tmp+=tn;
        }
        op=s[ind];
        ++ind;
    }
    return ret+tmp;
}

ll calc(string s){
    ll ret=0;
    int ind=0;
    char op='+';
    while(ind<s.size()){
        ll tn=s[ind]-'0';
        ++ind;
        if(op=='+')ret+=tn;
        else ret*=tn;
        op=s[ind];
        ++ind;
    }
    return ret;
}

ll solve(string s,bool mul){
    if(mul)return calcm(s);
    else return calc(s);
}

int main(){
    string s;
    cin>>s;
    ll res;
    cin>>res;
    bool ml=false,l=false;
    ml=(res==solve(s,true));
    l=(res==solve(s,false));

    if(ml&&!l)cout<<"M"<<endl;
    else if(!ml&&l)cout<<"L"<<endl;
    else if(ml&&l)cout<<"U"<<endl;
    else cout<<"I"<<endl;
    return 0;
}


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

int main() {
    int n, a;
    cin >> n;
    map<int, int> mp;
    for(int i = 0; i < n; ++i) {
        cin >> a;
        if(mp[a] == 0) mp[a] = 1;
        else mp[a] = 0;
    }
    int ans = 0;
    auto begin = mp.begin(), end = mp.end();
    for(auto iter = begin; iter != end; iter++) {
        ans += iter->second;
    }

    cout << ans << '\n';

    return 0;
}


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

int W, Q;
int wall[101];

void sleep(int id , map<int,int> cat ){
	bool sleepFlag = false;
	
	for(int i=0 ; i <= W-cat[id] ; i++ ){
		bool flag = true;
		
		if( wall[i] == -1 ){
			for(int j=i ; j < i+cat[id] ; j++ ){
				if( wall[j] != -1 ){
					flag = false;
				}
			}
			if( flag ){
				sleepFlag = true;
				cout << i << endl;
				for(int j=0 ; j < cat[id] ; j++ ){
					wall[i+j] = id;
				}
				break;
			}
		}
	}
	if( sleepFlag == false ){
		cout << "impossible" << endl;
	}
}

void wakeup(int id , map<int,int> cat ){
	for(int i=0 ; i < W ; i++ ){
		if( wall[i] == id ){
			wall[i] = -1;
		}
	}
}

int main(){
	int id, w;
	
	while( cin >> W >> Q , W ){
		map<int,int> cat;
		for(int i=0 ; i < 101 ; i++ )
			wall[i] = -1;
		
		for(int i=0 ; i < Q ; i++ ){
			char c;
			cin >> c;
			if( c == 's' ){
				cin >> id >> w;
				cat[id] = w;
				sleep( id , cat );
			}else if( c == 'w' ){
				cin >> id;
				wakeup( id , cat );
			}
		}
		cout << "END" << endl;
	}
}

Measured memory_bytes: 0
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int a[13];

int main()
{
	for(int i=1;i<=3;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+3+1);
	if(a[1]+a[2]==a[3])
	{
		puts("Yes");
	}
	else
	{
		puts("No");
	}
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    static int MOD = 1000000007;

    

    public static class Mas {
        int x;
        int y;
        int step;

        Mas(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

    private static final int[] vX = { 1, 0, 0, -1 };
    private static final int[] vY = { 0, 1, -1, 0 };


    public static void main(String[] args) {

        FastScanner fs = new FastScanner();
        int n=fs.nextInt();
        int m = fs.nextInt();
        int[] a = new int[m];
        int sum = 0;
        for (int i = 0; i < m; i++) {
            a[i] = fs.nextInt();
            sum += a[i];
        }
        System.out.println(n >= sum ? n - sum : -1);
       
    }

}


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

// define
# define loop(i,a,n) for(int i=a;i<n;++i)
# define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(0);
# define ll long long int 
# define endl "\n"
# define mp make_pair
# define mt make_tuple
# define pb push_back
# define eb emplace_back
# define in insert
# define rev(i,a,n) for(int i=n-1;i>=a;--i)
# define test int T; cin>>T; while(T--)
# define val 32

/* debug */ 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _itRS(_ss); err(_itRS, args); }

void err(istream_iterator<string> itRS) {}
template<typename T, typename... Args>
void err(istream_iterator<string> itRS, T a, Args... args) {
    cerr << *itRS << " = " << a << endl;
    err(++itRS, args...);
}
int dx[8] = {-1,-1,-1, 0, 0, 1, 1, 1}; 
int dy[8] = {-1, 0, 1,-1, 1,-1, 0, 1};


const int MOD=1000000007;



int main()
{   fast
    int x;
    cin>>x;
    if(x>=400 && x<=599)
    {
        cout<<8<<endl;
    }
   
    else if(x>=600 && x<=799)
    {
        cout<<7<<endl;
    }
     else if(x>=800 && x<=999)
    {
        cout<<6<<endl;
    }
     else if(x>=1000 && x<=1199)
    {
        cout<<5<<endl;
    }

    else if(x>=1200 && x<=1399)
    {
        cout<<4<<endl;
    }
    else if(x>=1400 && x<=1599)
    {
        cout<<3<<endl;
    }
    else if(x>=1600 && x<=1799)
    {
        cout<<2<<endl;
    }   
    else cout<<1<<endl; 
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define endl enjoy_codeforces
using lint=long long;
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    int n;std::cin>>n;
    std::multiset<int,std::greater<>>a;
    while(n--){
        int x;std::cin>>x;
        a.insert(x);
    }
    int ans=0;
    while(!a.empty()){
        int x=*a.begin();a.erase(a.begin());
        int y=1;while(y<=x)y*=2;
        y-=x;
        auto it=a.lower_bound(y);
        if(it==a.end()||*it!=y)continue;
        ans++;
        a.erase(it);
    }
    std::cout<<ans<<'\n';
}


Measured memory_bytes: 9600
fun main(args: Array<String>) {

    val n = readLine()!!.toInt()
    val s = readLine()!!.split("").toTypedArray().drop(1).dropLast(1)
    val k = readLine()!!.toInt()
    val c = s[k-1]

    s.forEach { i ->
        if(i != c){
            print("*")
        }else{
            print(i)
        }
    }
}


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

int n;
void solve(string now, char mx){
    if(now.length()==n)cout << now << endl;
    else{
        for(char c='a';c<=mx;c++){
            if(c<mx) solve(now+c,mx);
            else solve(now+c,mx+1);
        }
    }
}
int main(){
    cin >> n;
    solve("",'a');
}

Measured memory_bytes: 3620
a = list(input())
if "R" in a:
    if a.count("R") == 1:
        print(1)
    elif a.count("R") == 3:
        print(3)
    elif a[0] == a[1] or a[1] == a[2]:
        print(2)
    else:
        print(1)
        
else:
    print(0)

Measured memory_bytes: 61768
def buttons(n, paths):
    cont = 0
    button = 0
    for _ in range(n):
        if button == 1:
            return cont
        cont += 1
        button = paths[button]
    return -1


if __name__ == '__main__':
    n = int(input())
    print(buttons(n, [int(input()) - 1 for _ in range(n)]))

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

using namespace std;

#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define f first
#define s second

#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << endl;}

typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const ll inf = 1e12;
const ll mod = 1e9 + 7;

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

  int n;
  cin >> n;

  string s;
  cin >> s;

  f0r (i, s.length()) {
    cout << (char) (((n + (int) (s[i] - 'A')) % 26) + 'A');

  }

  cout << endl;
}

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

using namespace std;

int main(){
  int K,S;
  cin >> K >> S;
  int z;
  int cnt=0;
  for(int i=0;i<=K;i++){
    for(int j=0;j<=K;j++){
      z = S - i - j;
      if(z <= K && z >= 0 ){
        cnt++;
      }
    }
  }
  
  cout << cnt << endl;
}
        


Measured memory_bytes: 256
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

int A,B,X;
inline void solve(){
  IN3(A,B,X);
  OUT(A<=X&&X<=A+B?"YES":"NO");
}

int main(int argc,char**argv){
  BEGIN
  solve();
  END
}


Measured memory_bytes: 256
import math
n = int(input())
print(math.ceil(n/2)/n)


# 入力
'''
## スペース区切りの数字の受け取り
a = int(input())
a,b,c.. = map(int,input().split())
## 改行で区切られたn個の数字の受け取り
n = int(input())
a = [int(input()) for _ in range(n)]

n,k,x,y = [int(input()) for _ in [0]*4];print(x*k+y*(n-k) if n > k else x*n)

## 切り上げ


'''


Measured memory_bytes: 3188
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    pi = 0
    for n in range(1, N + 1):
        if n % K == 0:
            pi += 1

    hf = 0
    for n in range(1, N + 1):
        if n % K == K // 2:
            hf += 1

    ret = pi ** 3
    if K % 2 == 0:
        ret += hf ** 3
    print(ret)


if __name__ == '__main__':
    main()


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

void solve(ll n){
  ll m=sqrt(n);
  
  ll ans=0;
  for(ll x=1; x<=m; x++){
    for(ll y=1; y<=m; y++){
      for(ll z=1; z<=m; z++){
        if(x*x+y*y+z*z+x*y+y*z+z*x>n) break;
        if(x*x+y*y+z*z+x*y+y*z+z*x==n) ans++;
      }
    }
  }
  cout<<ans<<endl;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n; cin>>n;
  
  for(ll i=1; i<=n; i++){
    solve(i);
  }
  
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

void output_array(vector<int> &v)
{
  for (int i = 0; i < v.size(); i++)
    cout << (i ? " " : "") << v[i];
  cout << "\n";
}

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

  int n;
  cin >> n;

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

  int minv = r[0];
  int maxv = r[1] - r[0];
  for (int i = 1; i < n; i++)
  {
    maxv = max(maxv, r[i] - minv);
    minv = min(minv, r[i]);
  }

  cout << maxv << "\n";

  return 0;
}



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

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P2;
const int inf=1000000000;
int n,m;
ll d[200001]={};
ll s[200001]={};
ll add(int k,int s){
	while(k<2*m){
		d[k]+=s;
		k+=(k&-k);
	}
	return 0;
}
ll sum(int k){
	ll res=0;
	while(k>0){
		res+=d[k];
		k-=(k&-k);
	}
	return res;
}
int main() {
	cin>>n>>m;

	ll a1;
	cin>>a1;
	ll t=0;
	for(int i=1;i<n;++i){
		ll a2;
		cin>>a2;
		if(a2-a1>1){
			add(a1+2,1);
			add(a2+1,-a2+a1);
			add(a2+2,a2-a1-1);
		}
		if(a1-a2>0&&a2+m-a1>1){
			add(a1+2,1);
			add(a2+m+1,-a2-m+a1);
			add(a2+m+2,a2+m-a1-1);
		}
		if(a2>a1)t+=(a2-a1);
		if(a1>a2)t+=(a2+m-a1);
		a1=a2;
	}
	for(int i=1;i<2*m;++i){
		s[i]=s[i-1]+sum(i);
	}
	ll r=0;
	for(int i=1;i<m+1;++i){
		r=max(r,s[i]+s[m+i]);
	}
//	cout<<t;
	cout<<t-r<<endl;


	return 0;
}


Measured memory_bytes: 3328
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

k,t=map(int,input().split())
a=list(map(int,input().split()))

lst=[]
for i in range(t):
    lst.append([-a[i],i])
heapq.heapify(lst)

mae=[0,-1]
while lst:
    now,id=heapq.heappop(lst)
    now+=1
    if mae[0]!=0:
        heapq.heappush(lst,mae)
    mae=[now,id]
print(-mae[0])

Measured memory_bytes: 75300
/**
*	  Name: Ajay Subhash Jadhav
*	  Institute: International Institute of Technology Hyderabad 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define LL long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vii vector<ppi>
#define vll vector<LL>
#define mp make_pair
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void inputread()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main(){
      
  fastio();
  int n,m,i,j,t;
  cin>>n>>t;
  int c[n],ti[n];
  for(i=0;i<n;i++)
  	cin>>c[i]>>ti[i];

  int cur_c=1000000;
  for(i=0;i<n;i++)
  {
  	if(ti[i]<=t && c[i]<cur_c)
  	{
  		cur_c=c[i];
  	}
  }
  if(cur_c==1000000)
  	cout<<"TLE";
  else
  	cout<<cur_c;
  return 0;
}

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

using namespace std;

const int mod = 998244353;

long long mod_pow(long long x, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * x % mod;
    }
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

long long mod_inverse(long long x, long long mod) { return mod_pow(x, mod - 2, mod); }

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

  vector<long long> A(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
  }

  vector<vector<long long>> dp(N + 10, vector<long long>(S + 10, 0));
  dp[0][0] = 1;

  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= S; j++) {
      dp[i][j] += dp[i - 1][j];
      dp[i][j] %= mod;
      if (j - A[i] >= 0) {
        dp[i][j] += dp[i - 1][j - A[i]] * mod_inverse(2, mod);
        dp[i][j] %= mod;
      }
    }
  }

  cout << (dp[N][S] * mod_pow(2, N, mod)) % mod << "\n";

  return 0;
}

Measured memory_bytes: 74192
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
class Program
{       
    public void Slove()
    {
        var input = Console.ReadLine();
        int redCount = input.Count(x => x == '0');
        int blueCount = input.Length - redCount;
        int result = Math.Min(redCount, blueCount) * 2;
        System.Console.WriteLine(result);
    }
    
    static void Main(string[] args)
    {
        new Program().Slove();
    }
}


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

int N;
int K;
VI x;

void solve() {
  int ans = 1e15;
  REP (i, N - K + 1) {
    int l = x[i];
    int r = x[i + K - 1];
    if (r <= 0) {
      ans = min(ans, -l);
    } else if (l >= 0) {
      ans = min(ans, r);
    } else {
      ans = min(ans, min(r - l - l, r + r - l));
    }
  }
  cout << ans << endl;
}

signed main() {
  cin >> N >> K;
  x.resize(N);
  REP (i, N) {
    cin >> x[i];
  }
  solve();
}


Measured memory_bytes: 1024
using System;

class IDONTKNOWCSHARP
{
    public static void Main()
    {
        int[] values = Convert(GetLines());

        int HealthA = values[0];
        int AttackA = values[1];
        int HealthB = values[2];
        int AttackB = values[3];

        bool turn = true;
        while (true)
        {
            if (turn)
            {
                HealthB -= AttackA;
                if (HealthB <= 0)
                {
                    Console.WriteLine("Yes");
                    return;
                }

                turn = false;
            }
            else
            {
                HealthA -= AttackB;
                if (HealthA <= 0)
                {
                    Console.WriteLine("No");
                    return;
                }


                turn = true;
            }
        }

    }


    static int[] Convert(string[] v)
    {
        var temp = new int[v.Length];

        for (int i = 0; i < temp.Length; i++)
        {
            temp[i] = int.Parse(v[i]);
        }

        return temp;
    }




    static string[] GetLines()
    {
        return Console.ReadLine().Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
    }


}

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

#define pb 		push_back
#define mp 		make_pair
#define prior   priority_queue
#define MOD 	1000000007
#define INF64 	(long long)1e18
#define INF 	(int)1e9
#define PI 		3.1415926535897932384626433832795 
#define ll      long long
#define ld		long double
#define ret     return
#define NUM 	1000001
const int SIZE = 2e5+4;
void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

void input(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
}

void solveTest(){
	
}

int main(){
	fastio();
	//input();

	/*int t;
	cin>>t;
	while(t--){
		solveTest();
	}*/

	int n;
	cin>>n;
	vector<int> v;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		v.push_back(x);
	}
	sort(v.rbegin(),v.rend());
	int a=0;
	int b=0;
	for(int i=0;i<n;i++){
		if(i%2==0) a+=v[i];
		else b += v[i];
	}
	cout<<abs(a-b)<<endl;


	return 0;
}


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

const int maxn=1e5+7;
int a[maxn],n,m,p,v;

bool cmp(int a,int b)
{
	return a>b;
}

bool check(int x)
{
	if(x<=p) return 1;
	if(a[x]+m<a[p]) return 0;
	long long t=0;
	t+=1ll*(p-1)*m+1ll*(n-x+1)*m;
	for(int i=p;i<x;++i) {
		t+=max(a[x]+m-a[i],0);
	}
	if(t>=1ll*m*v) return 1;
	else return 0;
}

int main()
{
	scanf("%d %d %d %d",&n,&m,&v,&p);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	sort(a+1,a+n+1,cmp);
	int l=1,r=n;
	while(l<r) {
		int mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d",l);
}

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

using namespace std;

int main()
{
    int N;
    int *a;
    int p = 0;

    cin >> N;

    a = new int[N];

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

    int count = 0;

    while(p!=1){
        p = a[p] - 1;
        count++;

        if(count > N){
            cout << "-1" << endl;
            return 0;
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
#define mod 1000000007
#define int long long int
int power(int a,int b)
{
	if(b==0)
	  return 1;
	int r=power(a,b/2);
	if(b%2==0)
	{
		return (r*r)%mod;
	}
	else
	{
		int x=(r*r)%mod;
		return (a*x)%mod;
	}
}
int32_t main()
{
	int n,k;
	cin>>n>>k;
	int arr[k+1];
	int j;
	for(j=k;j>=1;j--)
	{
		int total=k/j;
		int sub=power(total,n);
		int i;
		for(i=2;i*j<=k;i++)
		{
			sub-=arr[i*j];
			sub=sub%mod;
		}
		arr[j]=sub;
	}
	int answer=0;
	for(j=1;j<=k;j++)
	{
		answer=answer+j*arr[j];
		answer=answer%mod;
	}
	if(answer<=0)
	  answer+=mod;
	cout<<answer<<endl;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl
#define DOUBLE(d) cout << fixed << setprecision(15) << (d) << endl

int A, B, C, D;

bool solve() {
    while (1) {
        C -= B;
        if (C <= 0) return true;
        A -= D;
        if (A <= 0) return false;
    }
}

int main() {
    cin >> A >> B >> C >> D;
    Yes(solve());
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int long long
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define DEBUG(x) cerr << #x << " " << x << endl
using namespace std;
 
const int BASE = 100003;
const int MOD = 30743651146573LL;
 
int depth[100000];
 
vector<vector<int>> child;
int parent[100000];
 
void dfs(int v) {
  for(int u : child[v]) {
    depth[u] = depth[v] + 1;
    dfs(u);
  }
}
 
int hash_value[100000];
 
signed main() {
  memset(depth, -1, sizeof(depth));
  int N; cin >> N;
  child.resize(N);
  parent[0] = -1;
  REP(i,N-1) {
    int a, b; cin >> a >> b;
    --a, --b;
    parent[b] = a;
    child[a].push_back(b);
  }
  depth[0] = 0;
  dfs(0);
  vector<pair<int, int>> ord;
  REP(i,N) {
    ord.emplace_back(-depth[i], i);
  }
  sort(ord.begin(), ord.end());
  REP(i,N) {
    int v = ord[i].second;
    int h = 1;
    for(int u : child[v]) {
      h += hash_value[u] * BASE;
      h %= MOD;
    }
    hash_value[v] = h;
  }
  map<int, int> hash_count;
  REP(i,N) {
    hash_count[hash_value[i]]++;
  }
  int ans = 0;
  for(auto kv : hash_count) {
    ans += kv.second * (kv.second - 1) / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 21720
import java.util.*;
import java.util.Map.Entry;

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

        Map<Integer, Integer> oddMap = new HashMap<>();
        Map<Integer, Integer> evenMap = new HashMap<>();
        int currentVal = 0;
        for (int i = 0; i < n; i++) {
            currentVal = sc.nextInt();
            if (i % 2 == 0) {
                oddMap.put(currentVal, oddMap.getOrDefault(currentVal, 0) + 1);
            } else {
                evenMap.put(currentVal, evenMap.getOrDefault(currentVal, 0) + 1);
            }
        }

        List<Entry<Integer, Integer>> oddEntries = new ArrayList<Entry<Integer, Integer>>(oddMap.entrySet());
        List<Entry<Integer, Integer>> evenEntries = new ArrayList<Entry<Integer, Integer>>(evenMap.entrySet());

        Collections.sort(oddEntries, new Comparator<Entry<Integer,Integer>>() {
            public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2){
                return obj2.getValue().compareTo(obj1.getValue());
            }
        });

        Collections.sort(evenEntries, new Comparator<Entry<Integer,Integer>>() {
            public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2){
                return obj2.getValue().compareTo(obj1.getValue());
            }
        });
        int oddMode = oddEntries.get(0).getKey();
        int oddModeCnt = oddEntries.get(0).getValue();
        int evenMode = evenEntries.get(0).getKey();
        int evenModeCnt = evenEntries.get(0).getValue();
        int ans = 0;
        if (oddMode != evenMode){
            ans = n - (oddModeCnt + evenModeCnt);
            System.out.println(ans);
        } else {
            if (oddEntries.size() == 1){
                ans = n - (oddModeCnt);
            } else {
                int ans1 =0;
                int ans2 =0;
                ans1 = n - (oddModeCnt + evenEntries.get(1).getValue());
                ans2 = n - (oddEntries.get(1).getValue() + evenModeCnt);
                ans = Math.min(ans1, ans2);
            }
            System.out.println(ans);
        }


    }
}

Measured memory_bytes: 61252
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n =  sc.nextInt();
		String s = sc.next();

		int index=0;
		int count=0;

		while(true) {
			if(s.indexOf("ABC",index)!= -1) {
				index = s.indexOf("ABC",index)+3;
			}else {
				break;
			}
			count++;
		}

		System.out.println(count++);


	}
}



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

int main() {
  string s;
  cin >> s;
  
  stack<char> x;
  x.push(s.at(0));
  char k;
  int i;
  for(i = 1; i < s.size(); i++){
    k = s.at(i);
    if(x.size() == 0) x.push(k);
    else if(k == x.top()) x.push(k);
    else x.pop();
  }
  
  cout << s.size() - x.size() << endl;
}

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

int main(void) 
{
    vector<string> ws;
    int n; cin >> n;
    string w; cin >> w;
    ws.push_back(w);

    bool flag = true;

    for (int i = 1; i < n; i++) {
        string p = ws[i - 1];
        cin >> w;
        if (p[p.length() - 1] != w[0]) {
            flag = false;
        }
        
        for (int j = 0; j < ws.size(); j++) {
            if (ws[j] == w)
            {
                flag = false;
            }
        }

        ws.push_back(w);
    }
    if (flag)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a, b = map(int, input().split())
f = [0, 0, 0]
for x in map(int, input().split()):
    if x <= a:
        f[0] += 1
    elif x <= b:
        f[1] += 1
    else:
        f[2] += 1
print(min(f))


Measured memory_bytes: 38384
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a=0,b,f,r,v,n,x=0,y=0;
    int A[30]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    int B[30]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    int C[30]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    int D[30]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    cin>>n;
    while(n!=x){
        cin>>b>>f>>r>>v;
        r+=-1;
        if(b==1){
            if(f==1){
                A[r]+=v;
            }else if(f==2){
                A[r+10]+=v;
            }else{
                A[r+20]+=v;
            }
        }
        if(b==2){
            if(f==1){
                B[r]+=v;
            }else if(f==2){
                B[r+10]+=v;
            }else{
                B[r+20]+=v;
            }
        }
        if(b==3){
            if(f==1){
                C[r]+=v;
            }else if(f==2){
                C[r+10]+=v;
            }else{
                C[r+20]+=v;
            }
        }
        if(b==4){
            if(f==1){
                D[r]+=v;
            }else if(f==2){
                D[r+10]+=v;
            }else{
                D[r+20]+=v;
            }
        }
        x++;
    }
    x=0;
    while(x!=10){
        cout<<" "<<A[x];
        x++;
    }
    cout<<endl;
    while(x!=20){
        cout<<" "<<A[x];
        x++;
    }
    cout<<endl;
    while(x!=30){
        cout<<" "<<A[x];
        x++;
    }
    cout<<endl;
    cout<<"####################"<<endl;
    
    
    x=0;
    while(x!=10){
        cout<<" "<<B[x];
        x++;
    }
    cout<<endl;
    while(x!=20){
        cout<<" "<<B[x];
        x++;
    }
    cout<<endl;
    while(x!=30){
        cout<<" "<<B[x];
        x++;
    }
    cout<<endl;
    cout<<"####################"<<endl;
    
    
    x=0;
    while(x!=10){
        cout<<" "<<C[x];
        x++;
    }
    cout<<endl;
    while(x!=20){
        cout<<" "<<C[x];
        x++;
    }
    cout<<endl;
    while(x!=30){
        cout<<" "<<C[x];
        x++;
    }
    cout<<endl;
    cout<<"####################"<<endl;
    
    
    x=0;
    while(x!=10){
        cout<<" "<<D[x];
        x++;
    }
    cout<<endl;
    while(x!=20){
        cout<<" "<<D[x];
        x++;
    }
    cout<<endl;
    while(x!=30){
        cout<<" "<<D[x];
        x++;
    }
    cout<<endl;
}



Measured memory_bytes: 3076
from collections import Counter
n, *d = map(int, open(0).read().split())
MOD = 998244353
c = Counter(d)
if d[0] != 0 or c[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, max(d)+1):
        ans *= (c[i-1] ** c[i]) % MOD
print(ans % MOD)

Measured memory_bytes: 24496
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define NOT_ZERO 1
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
typedef long long ll;

int main()
{
    int N, W;
    int w[100], v[100];
    int i, j;

    scanf("%d %d",&N,&W);

    ll *dp = (ll*)calloc(W+1, sizeof(ll));  //容量が最大iの時の価値の最大値

    for(i=0; i<N; i++) {
        scanf("%d %d",w+i, v+i);
        for(j=W; j>=w[i]; j--) {
            dp[j] = MAX(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    printf("%lld",dp[W]);

    return 0;
}


Measured memory_bytes: 896
n,m,l=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
b=[list(map(int,input().split())) for _ in range(m)]
[print(*x) for x in [[sum(j*k for j,k in zip(x,y)) for y in zip(*b)] for x in a]]


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

using namespace std;

bool even(string ss, int l)
{
    if(l%2)
        return false;
    else
    {
        string s1,s2;
        s1=ss.substr(0,l/2);
        s2=ss.substr(l/2,l/2);

        if(s1==s2)
            return true;
        else
            return false;

    }
}

int main()
{
    string ss;

    cin>>ss;

    int l=ss.length();

    l--;

    while(!even(ss,l))
    {
        l--;
    }

    printf("%d\n", l);


    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class A7{
  struct Tree{
    public int id;
    public int parent;
    public int depth;
    public int height;
    public int left, right;
    public int sibling;
    public int degree;
    public string type;
  }

  public static void Main(){
    int n = int.Parse(Console.ReadLine());
    var tree = new Tree[n];

    for(int i = 0;i < n;i++){
      tree[i].parent = -1;
    }
    for(int i = 0;i < n;i++){
      var input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
      var id = input[0];
      var l = input[1];
      var r = input[2];
      tree[id].id = id;
      tree[id].left = l;
      tree[id].right = r;
      tree[id].type = "leaf";
      if(l != -1){
        tree[id].type = "internal node";
        tree[id].degree++;
        tree[l].parent = id;
        tree[l].sibling = r;
      }
      if(r != -1){
        tree[id].type = "internal node";
        tree[id].degree++;
        tree[r].parent = id;
        tree[r].sibling = l;
      }
    }
    for(int i = 0;i < n;i++)
      if(tree[i].parent == -1){
        tree[i].type = "root";
        tree[i].sibling = -1;
        Depth(tree,i,0);
        break;
      }
    for(int j = 0;j < n;j++){
        Console.Write("node ");
        Console.Write(tree[j].id);
        Console.Write(": parent = ");
        Console.Write(tree[j].parent);
        Console.Write(", sibling = ");
        Console.Write(tree[j].sibling);
        Console.Write(", degree = ");
        Console.Write(tree[j].degree);
        Console.Write(", depth = ");
        Console.Write(tree[j].depth);
        Console.Write(", height = ");
        Console.Write(tree[j].height);
        Console.Write(", ");
        Console.WriteLine(tree[j].type);
      }
  }

  static int Depth(Tree[] tree,int id,int depth){
    if(id == -1) return depth - 1;
    tree[id].depth = depth;
    var lh = Depth(tree,tree[id].left,depth + 1);
    var rh = Depth(tree,tree[id].right,depth + 1);
    var h = Math.Max(lh,rh);
    tree[id].height = h - depth;
    return h;
  }
}



Measured memory_bytes: 9176
N, M = map(int,input().split())
H = []
L = [[] for k in range(M+1)]

for k in range(N):
    P = list(map(int,input().split()))[1:]
    H.append(P)
    for e in P:
        L[e].append(k+1)

G = [0 for k in range(N+1)]
G[1] = 1
Q = [H[0]]
while len(Q) > 0:
    ima = Q.pop()
    for tsugi in ima:
        for e in L[tsugi]:
            if G[e] == 0:
                G[e] = 1
                if len(H[e-1]) > 1:
                    Q.append(H[e-1])

for k in range(1,N+1):
    if G[k] == 0:
        print("NO")
        exit(0)
print("YES")


Measured memory_bytes: 28820
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
#define fcout cout << fixed << setprecision(10)
int main(){
    int n;
    cin>>n;
    int a[n];
    ll cnt=0,cnt2=0;
    rep(i,0,n){
        cin>>a[i];
        a[i]-=i;
        cnt+=a[i];
    }
    sort(a,a+n);
    int ave=a[(n-1)/2],ave2=a[(n-1)/2+1];
    cnt=0;
    rep(i,0,n)cnt+=abs(a[i]-ave);
    rep(i,0,n)cnt2+=abs(a[i]-ave2);
    cout<<min(cnt,cnt2);
}

Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

def pow_r_mod(x, n, mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= mod
        n //= 2

    return (K * x) % mod

m, a, b = mi()

P = 10**9+7
N = 2*(10**5)+1
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

mca = mcb = 1

for i in range(1, a+1):
    mca *= (m-i+1) * inv_t[i]
    mca %= P

for i in range(1, b+1):
    mcb *= (m-i+1) * inv_t[i]
    mcb %= P

print((pow_r_mod(2, m)-1-mca-mcb) % P)

Measured memory_bytes: 52720
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,n = LI()
dp = [inf]*(h+1)
dp[0] = 0
ab = [LI() for _ in range(n)]
for i in range(h+1):
    for a,b in ab:
        if i + a <= h:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
print(dp[-1])


Measured memory_bytes: 44140