akhauriyash/Code-Regression huggingface dataset:
S = input()


def is_ss(t):
    if len(t) % 2 or t[:len(t)//2] != t[len(t)//2:]:
        return False
    else:
        return True


for i in range(len(S)-2, 0, -2):
    if is_ss(S[:i]):
        print(i)
        exit()


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

signed main(){
    
    vector<int> acc(5000000, 0);
    acc[1] = 1;
    for(int i = 1; i <= 1000100; i++){
        if(acc[i] == 0) continue;
        acc[i * 2] = 1;
        acc[i * 3] = 1;
        acc[i * 5] = 1;
    }

    for(int i = 2; i <= 1000100; i++) acc[i] += acc[i - 1];
    
    while(1){
        int n, m; cin >> n >> m;
        if(n == 0) break;
        cout << acc[m] - acc[n - 1] << endl;
    }
    return 0;
}



Measured memory_bytes: 41688
def main():
    H, W = map(int, input().split())
    if H == 1 or W == 1:
        print(1)
        return
    ans = ((H + 1)//2) * ((W + 1) //2)
    ans += (H//2) * (W//2)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
 
using namespace std;
using ll = long long;
 
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


int main()
{
	string s1, s2, s3;

	cin >> s1 >> s2 >> s3;

	printf("%c%c%c\n", s1[0] - 32, s2[0] - 32, s3[0] - 32);
}

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

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

  int ans = 1;
  for(int i=1; i<n; i++){
    if(s[i] != s[i-1]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 

def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 77196
// Undone
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
#define MOD 1000000007
using namespace std;
signed main() {
  int X, A, B, N;
  cin >> X >> A >> B >> N;
  string s;
  for (int i = 0; i < N; i++) {
    cin >> s;
    if (s == "nobiro") {
      X += A; 
    } else if (s == "tidime") {
      X += B;
    } else {
      X = 0;
    }
    X = max(0LL, X);
  }
  cout << X << endl;
}




Measured memory_bytes: 3172
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

int main(){
	int n;
	cin >> n;
	map<long , int > mp = {};
	rep(i,0,n){
		long tmp;
		cin >> tmp;
		mp[tmp]++;
	}
	
	long ans = 0;
	for(auto it = mp.begin() ; it != mp.end() ; it++ ){
		long num = it->first;
		int cnt = it->second;

		if(num < cnt){
			ans += cnt - num;
		}
		if(num > cnt)
			ans += cnt;
	} 
	P(ans);
	ret 0;
}

Measured memory_bytes: 6272
import sys
import math

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
A,B,H,M=LI()

ta = -(float(H+(M/60))*math.pi/6.0) + (math.pi*0.5)
tb = -(float(M)*math.pi/30.0) + (math.pi*0.5)
Ax = A*math.cos(ta)
Ay = A*math.sin(ta)

Bx = B*math.cos(tb)
By = B*math.sin(tb)

print(math.sqrt((Ax-Bx)*(Ax-Bx) + (Ay-By)*(Ay-By)))


Measured memory_bytes: 9556
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string n;
	cin>>n;
	n='0'+n;
	int ans=0;
	for(int i=n.size()-1;i>=0;i--)
		if(n[i]>'5'||n[i]=='5'&&n[i-1]>='5') {
			ans+='9'+1-n[i];
			n[i-1]++;
		}
		else ans+=n[i]-'0';
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2332
#include<stdio.h>
#include<stdlib.h>
int main(){
  int flag,a,N,i,j,*A,cnt=0;
  scanf("%d",&N);
  A=malloc(N*sizeof(int *));
  flag=1;
  for(i=0;i<=N-1;i++)scanf("%d",&A[i]);
  
  while(flag){
    flag=0;
  for(j=N-1;j>=1;j--){
    if(A[j]<A[j-1]){
      a=A[j];
       A[j]=A[j-1];
      A[j-1]=a;
      flag=1;
      cnt++;
    }
   
    
  }
  }
 
  
    for(j=0;j<N-1;j++)printf("%d ",A[j]);
  
  printf("%d\n",A[N-1]);
  printf("%d\n",cnt);
  free(A);
  return 0;
}



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

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

  int N;
  long long ans = 0;
  cin >> N;
  for(int i = 1; i <= N; i++){
    if(i % 3 == 0 || i % 5 == 0){
      continue;
    } else{
      ans += i;
    }
  }
  cout << ans <<endl;
}


Measured memory_bytes: 3648
import java.util.Scanner;
 
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if(0 < (a-b*2)){
      System.out.println(a-b*2);
    }else{
      System.out.println(0);
    }
  }
  
}

Measured memory_bytes: 21844
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

N = ni()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

ans = 0
for i in range(1, N+1, 2):
    if len(make_divisors(i)) == 8:
        ans += 1

print(ans)

Measured memory_bytes: 3696
N, M = map(int, input().split())
A = ['' for _ in range(N)]
B = ['' for _ in range(N)]
for i in range(N):
    A[i] = input()
for i in range(M):
    B[i] = input()

H = N - M + 1
flag = 'No'

for i in range(H):
    for j in range(H):
        cnt = 0
        for d in range(M):
            if B[d] != A[i+d][j:j+M]:
                break
            cnt += 1
        if cnt == M:
            flag = 'Yes'
            break
    else:
        continue
    break

print(flag)

Measured memory_bytes: 9120
import java.util.Scanner;

class NumTh{
	static long mod=1000000007; // 10e9 + 7
	static long GCD(long x, long y) {
		if(Math.max(x, y) % Math.min(x, y) == 0) return Math.min(x, y);
		return GCD(Math.min(x, y), Math.max(x, y) % Math.min(x, y));
	}
	static int GCD(int x, int y) {
		return (int)GCD((long)x, (long)y);
	}
}
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int N = sc.nextInt();
			int[] A = new int[N];
			int[] Left = new int[N];
			int[] Right = new int[N];
			for(int i = 0; i < N; i++) A[i] = sc.nextInt();
			// Left
			Left[0] = A[0];
			for(int i = 1; i < N; i++) Left[i] = NumTh.GCD(A[i], Left[i - 1]);
			// Right
			Right[N - 1] = A[N - 1];
			for(int i = N - 2; i >= 0; i--) Right[i] = NumTh.GCD(A[i], Right[i + 1]);
			int ans = 0;
			for(int i = 0; i < N; i++) {
				int tmp = 0;
				if(i == 0) tmp = Right[i + 1];
				else if(i == N - 1) tmp = Left[i - 1];
				else tmp = NumTh.GCD(Right[i + 1], Left[i - 1]);
				ans = Math.max(ans, tmp);
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 50208
$n=<>;$h[$|--]{$_}--for glob<>;
($a,$b)=map[sort{$$_{$a}-$$_{$b}}keys%$_],@h;
$u=$h[0]{$$a[0]};
$v=$h[1]{$$b[0]};
$x=$h[0]{$$a[1]};
$y=$h[1]{$$b[1]};
print$n+($$a[0]-$$b[0]?$u+$v:$u+$y<$v+$x?$u+$y:$v+$x)

Measured memory_bytes: 30208
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <unordered_map>
#include <tuple>
#include <complex>


#define FOR(i, a, b)		for(int i = (int)(a); i < (int)(b); ++i)
#define FORE(i, a, b)		for(int i = (int)(a); i <= (int)(b); ++i)
#define REP(i, n)			FOR(i, 0, n)
#define REPE(i, n)			FORE(i, 0, n)
#define ALL(x)				(x).begin(),(x).end()
#define DEBUG_DC(x)			cout << #x << ": " << x << endl
#define ANS_DC(x)			cout <<  x << endl
#define VEC_TYPE			int
#define INF					1e4+1

using namespace std;
typedef long long ll;
typedef vector<VEC_TYPE> vdef;
typedef vector<vdef> vvdef;
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<typename T>inline T mygcd(T a, T b) { return b ? mygcd(b, a%b) : a; }
template<typename T>inline T mylcm(T a, T b) { return a * b / mygcd(a, b); }


int main()
{
	int r, d, x;
	cin >> r >> d >> x;
	int ans[11] = { 0 };
	ans[0] = x;

	for (int i = 1; i < 11; ++i)
	{
		ans[i] = r * ans[i - 1] - d;
	}
	
	FOR(i, 1, 11)
	{
		ANS_DC(ans[i]);
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
const int mod = 998244353;
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
vector<int> f = {1},fi = {1};
int fact(int x){
    while((int)f.size() <=x)f.push_back((f.back()*f.size())%mod);
    return f[x];
}
int ifact(int x){
    return modpow(fact(x),mod-2,mod);
}
int C(int x,int y){
    if(x < y)return 0;
    return fact(x)*ifact(y)%mod*ifact(x-y)%mod;
}
signed main(){
    int n,a,b,k;cin>> n >> a >> b >> k;
    //ax + by = k
    vector<P> kouho;
    bool found = false;
    for(int x = 0;x <= n;x++){
        int tmp = k - a*x;
        if(tmp%b == 0){
            int y = tmp/b;
            if(y >= 0 && y <= n){
                //trace(x,y);
                kouho.emplace_back(x,y);
                found = true;
            }
        }
    }
    //for(auto p:kouho)trace(p);
    if(kouho.size() == 0){
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    rep(i,(int)kouho.size()){
        int x = kouho[i].first,y = kouho[i].second;
        int ret = 1;
        ret = (ret*C(n,x))%mod;
        ret = (ret*C(n,y))%mod;
        ans = (ans + ret)%mod;
    }
    cout << ans%mod << endl;


    return 0;
}

Measured memory_bytes: 12828
import java.util.Scanner;
public class Main {
	public static void main(String args[]){
	@SuppressWarnings("resource")
	Scanner sc = new Scanner(System.in);

	int a = sc.nextInt();				
	int b = sc.nextInt();
	int c = sc.nextInt();

	if(a==b && b!=c){
		System.out.println("Yes");
	}else if(b==c && c!=a){
		System.out.println("Yes");
	}else if(c==a && a!=b){
		System.out.println("Yes");
	}else {
		System.out.println("No");
	}
  }
}

Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{
    
    class Program
    {
        static bool Is_ATCG(char s)
        {
            if(s == 'A' || s == 'T' || s == 'C' || s == 'G')
            {
                return true;
            }
            else
            {
                return false;
            }
            
        }
        
       
        static void Main(string[] args)
        {
            string S = Console.ReadLine();

            int max = 0;

            bool is_atgc = false;
            int cnt = 0;

            for(int i = 0; i < S.Length; i++)
            {
                if(Is_ATCG(S[i]))
                {
                    
                    if (is_atgc)
                    {
                        cnt++;
                    }
                    else
                    {
                        cnt = 1;
                    }
                    is_atgc = true;
                }
                else
                {
                    is_atgc = false;
                    if (cnt > max)
                    {
                        max = cnt;
                    }
                }               
            }

            if (cnt > max)
            {
                max = cnt;
            }


            Console.WriteLine(max);


        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define yes(n) cout << ((n) ? "yes" : "no") << endl

using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

void chmin(int &a, int b) { if (a > b) a = b; }

ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) {
    ll g = GCD(a, b);
    return a / g * b;
}


int main() {
    int n; cin >> n;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];
    reverse(all(h));

    bool ok = true;
    for (int i=1;i<n;++i) {
        if (h[i - 1] < h[i]) {
            if (h[i - 1] < h[i] - 1) {
                ok = false;
                break;
            } else {
                h[i]--;
            }
        }
    }
    Yes(ok);
}

Measured memory_bytes: 1024
#include<stdio.h>
void merge(int *,int,int,int,int);
void mergeSort(int *, int,int,int);
#define MAX 500000
#define INFTY 2000000000

int L[MAX/2+2],R[MAX/2+2];
int count;
int main( ){
  int A[MAX],i,j,k,n;

  scanf("%d",&n);
  count = 0;
  for(i = 0; i < n; i++){
    scanf("%d",&A[i]);
    if(A[i] >= INFTY){
      return 1;
    }
  }

  mergeSort(A,n,0,n);

  for(i = 0; i < n; i++){
    if(i) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
  printf("%d\n",count);
 
  return 0;
}

void merge(int A[], int n ,int left, int mid, int right){
  int i,j,k;
  int  n1 = mid - left;
  int  n2 = right - mid;
  // L[0...n1], R[0...n2] を生成
  for (i = 0 ;i < n1; i++){
    L[i] = A[left + i];
  }
  for( i = 0 ;i < n2;i++){
    R[i] = A[mid + i];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = 0;
  j = 0;
  for(k = left;k < right;k++){
    count++;
    if (L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
    }
    else {
      A[k] = R[j];
      j = j + 1;
    }
  }
}

void mergeSort(int A[], int n ,int left, int right){
  if (left+1 < right){
    int mid = (left + right)/2;
    mergeSort(A,n, left, mid);
    mergeSort(A,n, mid, right);
    merge(A, n,left, mid, right);
  }
}





Measured memory_bytes: 5636
#include <stdio.h>

int main()
{
	int i,k;
	int a,b;
	while(1){
		scanf("%d %d", &a, &b);
		if(a==0&&b==0){
			break;
		}
		else if(a>=3&&a<=300&&b<=300){
			for(i=0; i<a; i++){
				for(k=0; k<b; k++){
					if(i==0||i==a-1){
						printf("#");
					}
					else if(k==0||k==b-1){
						printf("#");
					}
					else{
						printf(".");
					}
				}
				printf("\n");
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define MOD 1000000007ULL;
#define rep(i,n) for(int i=0;i<n;i++)


int main() {
	int A,B,C,D;
  	cin>>A>>B>>C>>D;
  	while(1){
     	C-=B;
      	if(C<=0){
			cout<<"Yes"<<endl;
          	return 0;
        }
      	A-=D;
      	if(A<=0){
        	cout<<"No"<<endl;
          	return 0;
        }
    }
  
  
}

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

int v[101];
int w[101];
int dp[101][10001];
int N,W;
void print(){
  for(int i=0;i<=N;i++){
    for(int j=0;j<=W;j++){
      cout<<dp[i][j]<<" ";;
    }
    cout<<"\n";
  }
  cout<<"\n";
}
void solve(){
  for(int i=0;i<N;i++){
    for(int j=0;j<=W;j++){
      if(w[i]>j){
        dp[i+1][j]=dp[i][j];
      }else{
        dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      }
    }
  }
}
int main(){
  cin>>N>>W;
  for(int i=0;i<N;i++){
    cin>>v[i]>>w[i];
  }
  solve();
  //print();
  cout<<dp[N][W]<<"\n";
}



Measured memory_bytes: 7004
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
const int inf=1e9+7;
const ll mod=1e9+7;

int main() {
    int N;
    cin>>N;
    int p[N];
    for(int i=0;i<N;++i){
        cin>>p[i];
        p[i]--;
    }
    int ans = 0;
    int index = 0;
    while(index < N){
        if(p[index]==index){
            ans++;
            index += 2;
        }
        else index++;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

vector<vector<ll>> g;
P ans[1000];
ll x[1000]; 

void dfs(ll at){
    if(g[at].size() == 0){ans[at] = P(x[at], 0); return;}

    vector<ll> dp(x[at]+1, INF);
    dp[0] = 0;
    zep(i, 0, g[at].size()){
        vector<ll> nxdp(x[at]+1, INF);

        ll nx = g[at][i];
        dfs(nx);

        rep(j, 0, x[at]){
            if(j-ans[nx].first >= 0)
                nxdp[j] = min(nxdp[j], dp[j-ans[nx].first] + ans[nx].second);
            if(j-ans[nx].second >= 0)
                nxdp[j] = min(nxdp[j], dp[j-ans[nx].second] + ans[nx].first);
        }
        dp.swap(nxdp);
    }

    ll res = INF;
    rep(j, 0, x[at]){
        res = min(res, dp[j]);
    }
    ans[at] = P(x[at], res);
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    
    ll n; cin >> n;
    g.resize(n);
    zep(i, 1, n){
        ll p; cin >> p; p--;
        g[p].push_back(i);
    }
    zep(i, 0, n)cin >> x[i];
    
    dfs(0);
    
    print((ans[0].second == INF)? "IMPOSSIBLE" : "POSSIBLE")
    return 0;
}

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

int main(){
    ll n,k,q;
    cin>>n>>k>>q;
    ll quiz;
    ll point[n];
    ll pro[n];
    for(int i=0;i<n;i++) {
        point[i]=0;
    }
    for(int i=0;i<q;i++) {
        cin >> quiz;
        point[quiz-1]++;
    }

    for(int i=0;i<n;i++){
        pro[i]=k-q+point[i];
        if(pro[i]>0) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

Measured memory_bytes: 2176
import math
def C(n, r):
    if n < r or r < 0:
        return 0
    else:
        return (math.factorial(n) // (math.factorial(r) * math.factorial(n - r)))

N, K = map(int,input().split())
ans = []
R = N - K
for i in range(1, K + 1):
    b = C(K - 1, i - 1)
    r = C(R - 1, i - 2) + 2 * C(R - 1, i - 1) + C(R - 1, i)
    ans.append((b * r) % (10**9 + 7))
if R == 0:
    ans = [1] + [0 for i in range(K - 1)]
print('\n'.join(list(map(str,ans))))

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

int main(){
  long N;
  long long count=0;
  cin >> N;
  for(long i=0; i<N; i++){
    long l, r;
    cin >> l >> r;
    count+= r-l+1;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1e9 + 7;
using namespace std;
typedef long long ll;

map<ll, int> mp;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed;
	cout << setprecision(20);
	int n, m;
	cin >> n;
	vector<int> d(n);
	map<int, int> mpa, mpb;
	for (int i = 0; i < n; i++) {
		cin >> d[i];
		mpa[d[i]]++;
	}
	cin >> m;
	vector<int> t(m);
	for (int i = 0; i < m; i++) {
		cin >> t[i];
		mpb[t[i]]++;
	}
	for (int i = 0; i < m; i++) {
		int x = t[i];
		if (mpb[x] > mpa[x]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 20608
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

x = pow(10, 100, mod)
ans = 0
n, k = LI()
for i in range(k, n + 2):
    ans += (n - (i - 1)) * i + 1
    ans %= mod

print(ans)

Measured memory_bytes: 76932
n = int(input())
CSF = [tuple(map(int, input().split())) for _ in range(n - 1)]

for i in range(n):
    t = 0
    for c, s, f in CSF[i:]:
        if t < s:
            t = s
        elif t % f != 0:
            t += f - t % f
        t += c
    print(t)


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, a[100000];

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	
	int flag = 0;
	int pre = a[0];
	int ans = 1;
	inc(i, n) {
		if(pre == a[i]) {
			
		} else if(pre < a[i]) {
			if(flag == -1) { ans++; flag = 0; } else { flag = +1; }
		} else {
			if(flag == +1) { ans++; flag = 0; } else { flag = -1; }
		}
		
		pre = a[i];
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        if (a > 9 || b > 9) System.out.println(-1);
        else System.out.println(a * b);
    }
}


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

int n,m,q;
int ans;
vector<int> a,b,c,d;

void dfs(vector<int> A){
    if(A.size() == n+1){
        int now=0;
        rep(i,q){
            if(A[b[i]]-A[a[i]]==c[i]) now+=d[i]; 
        }
        ans = max(ans, now);
        return;
    }
    A.push_back(A.back());
    while(A.back()<=m){
        dfs(A);
        A.back()++;
    }
}


int main() {
    cin >> n >> m >> q;
    a=b=c=d= vector<int>(q);
    rep(i,q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    dfs(vector<int>(1,1));
    cout << ans << endl;
}

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
namespace aizu
{
    class OnlineJudge
    {
        static void Main()
        {
            int[] input;
            while(((input = Console.ReadLine().Split().Select(q => int.Parse(q)).ToArray())[0] | input[1]) != 0) {
                int index = 0;
                List<int> number = Enumerable.Range(1, input[0]).ToList();
                foreach(string item in Enumerable.Range(1, input[1]).Select(q => q % 15 == 0 ? "FizzBuzz" : q % 5 == 0 ? "Buzz" : q % 3 == 0 ? "Fizz" : q.ToString())){
                    string value = Console.ReadLine();
                    if(number.Count != 1) {
                        if(item.CompareTo(value) != 0) {
                            number.RemoveAt(index--);
                        }
                        index = index >= number.Count - 1 ? 0 : index + 1;
                    }
                }
                Console.WriteLine(string.Join(" ", number.Select(q => q.ToString()).ToArray()));
            }
        }
    }
}

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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



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

	int n;
	cin >>n;
	vector<VI> ba(2, VI(n));
	rep(i,n) cin >>ba[0][i];
	rep(i,n) cin >>ba[1][i];
	
	ll ans =0;
	rep(i,n){
		ll w=0;
		rep(j, i+1) w += ba[0][j];
		rep2(j,i,n) w += ba[1][j];
		ans = max(ans, w);
	}
	cout << ans <<"\n";
	return 0;
	
}


Measured memory_bytes: 256
let solve n = 
  (n / 11) * 2 + ((n mod 11)/6) + (if (n mod 11) mod 6 > 0 then 1 else 0)

let () =
  let rec read () =
    try let ans = (Scanf.scanf "%d\n" solve) in
        Printf.printf "%d\n" ans
    with End_of_file -> ()
  in
  read ()
;;


Measured memory_bytes: 4480
#include <cstdio>

using namespace std;

int main() {
  double xA, yA, xB, yB, xC, yC, xD, yD;
  while (scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &xA, &yA, &xB, &yB, &xC, &yC, &xD, &yD) == 8) {
    double a = xB-xA, b = yB-yA, c = xD-xC, d = yD-yC;
    puts(a * c + b * d == 0 ? "YES" : "NO");
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int N,M;
    cin >> N >> M;
    int ans1 = 0;
    int ans2 = 0;
    vector<bool>ok(N,false);
    vector<int>cnt(N);
    for(int i = 0; i < M; i++) {
        int a;
        string b;
        cin >> a >> b;
        if(b == "AC") {
            if(ok[a-1] == true) {
                continue;
            }
            ok[a-1] = true;
            ans1++;
            ans2+=cnt[a-1];
        }
        else {
            if(ok[a-1] == true) {
                continue;
            }
            cnt[a-1]++;
        }
    }
    cout << ans1 << " " << ans2 << endl;
}

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

// priceをキーに降順でソート
//sort(fruits.begin(), fruits.end(),
//     [](const fruit& x, const fruit& y) { return x.price > y.price;});

int main() {
    vector<char> s;
    string S;
    std::cin >> S;
    for(int i=0; i<4; i++){
        s.push_back(S[i]);
    }
    std::sort(s.begin(), s.end());
    if(s[0]==s[1] && s[2]==s[3] && s[1]!=s[3]){
        std::cout << "Yes" << std::endl;
        return 0;
    }
    else{
        std::cout << "No" << std::endl;
        return 0;
    }
}


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

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

// template starts
typedef long long int ll;

// template ends here

void solve(){
	// code starts from here
	ll N, X, T;
	cin >> N >> X>> T;
	cout << T*(N/X + (N%X != 0)) << endl;
}

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

	int T;
	T = 1;
	while(T--){
		solve();
	}

	return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N; cin >> N;
  map<ll, bool> mp;
  rep(i, N) {
    ll A; cin >> A;
    auto it = mp.find(A);
    if(it == mp.end()) {
      mp.emplace(A, true);
    } else {
      it->second ? it->second=false : it->second=true;
    }
  }
  ll ans = 0;
  for(auto a:mp) {
    if(a.second) ++ans;
  }
  cout << ans << endl;
}

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

int main(){
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  int time = 0;
  for (int i = A; i < B; i++){
    if(C <= i && i < D) time++;
  }
  cout << time;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		int max = 0, mn = 1;
		int prev = sc.nextInt();
		for(int i = 1; i < N; i++) {
			int a = sc.nextInt();
			if(a > prev) {
				if(max == a - prev)
					mn++;
				else if(max < a - prev) {
					max = a - prev;
					mn = 1;
				}
			}
			else
				prev = a;
		}
		System.out.println(mn);
	}

}

Measured memory_bytes: 58680
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int n = 0;
  for(int i = 0; i < 3; i++){
    if(s.at(i) == '1')
      n += 1;
  }
  cout << n << endl;    
}

Measured memory_bytes: 256
import sys
import numpy as np

n = int(input())
xyh = [list(map(int, input().split())) for _ in range(n)]
xyh.sort(key=lambda x: x[2], reverse=True)

for cx in range(101):
    for cy in range(101):
        x, y, h = xyh[0]
        tmp_h = abs(cy - y) + abs(cx - x) + h
        H = np.zeros(n, dtype=np.bool)
        for i, a in enumerate(xyh):
            H[i] = a[2] == max(tmp_h - abs(cx - a[0]) - abs(cy - a[1]), 0)
        if np.all(H):
            print(cx, cy, tmp_h)
            sys.exit()

Measured memory_bytes: 27228
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

#ここから書き始める
n = int(input())
x = list(map(int, input().split()))
x_sorted = sorted(x)
left = x_sorted[n // 2 - 1]
right = x_sorted[n // 2]
for i in x:
    if i <= left:
        print(right)
    else:
        print(left)

Measured memory_bytes: 27248
#include <bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<double,double> pd;
typedef priority_queue<int, vector<int>, greater<int>> min_heap;

// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const double PI = 4*atan(1);
const ll INF = 1e18;
const int MX = 100001;

priority_queue<pair<ll, int>> pq;

const int maxn = 1e5 + 5;
int x, y, a, b, c;

ll p[maxn], q[maxn], r[maxn];
int rem[4], total[4];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> x >> y >> a >> b >> c;
    rem[1] = x;
    rem[2] = y;
    for (int i = 1; i <= a; i++) {
        cin >> p[i];
        pq.push(mp(p[i], 1));
    }
    for (int i = 1; i <= b; i++) {
        cin >> q[i];
        pq.push(mp(q[i], 2));
    }
    for (int i = 1; i <= c; i++) {
        cin >> r[i];
        pq.push(mp(r[i], 3));
    }

    ll ans = 0;

    while (!pq.empty()) {
        pair<ll, int> p = pq.top(); pq.pop();
        int tot = total[1] + total[2] + total[3];
        if (tot == x + y) break;
        int color = p.s;
        if (color != 3) {
            if (rem[color] == 0) continue;
            rem[color]--;
        }
        ans += p.f;
        total[color]++;
    }
    cout << ans << "\n";

}

Measured memory_bytes: 12268
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <codecvt>
#include <locale>
using namespace std;
using ll = long long;

int main() {
    int X;
    cin >> X;
    int res = 0;
    while((res+1)*res/2 < X) {
        res++;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
    int n;
    cin >> n;
  	vector<string> s(n);

    bool s_flg[4];
    rep(i, n) {
        cin >>  s[i];
    }
    rep(i,4){
        s_flg[i] = false;
    }
/*
    cout << n << endl;
    rep(i,n){
        cout << s[i] << " ";
    }
    cout << endl;
*/
    rep(i,n){
        if(s[i] == "P"){
            s_flg[0] = true;
        }
        if(s[i] == "W"){
            s_flg[1] = true;
        }
        if(s[i] == "G"){
            s_flg[2] = true;
        }
        if(s[i] == "Y"){
            s_flg[3] = true;
        }
    }
/*
    rep(i,4){
        cout << s_flg[i] ;
    }
    cout << endl;
*/
    if(s_flg[3] == true && (s_flg[0] == true && s_flg[1] == true && s_flg[2] == true)){
        cout << "Four" << endl;
    }else{
        cout << "Three" << endl;
    }
}


Measured memory_bytes: 256
/* Finding Missing Cards */
#include <stdio.h>

int main()
{
    int card[4][14], c, n, i, j;
    char s;

    scanf("%d", &n);
    for(i=0; i<n; i++){
        for(j=0;j<2;j++){
        scanf("%c %d", &s, &c);
        }
        if(s == 'S'){
            card[0][c] = c;
        }
        else if(s == 'H'){
            card[1][c] = c;
        }
        else if(s == 'C'){
            card[2][c] = c;
        }
        else if(s == 'D'){
            card[3][c] = c;
        }
    }
    for(i=0;i<4;i++){
        for(j=1; j<14; j++){
            if(card[i][j] != j){
                if(i == 0){   printf("S %d\n", j);  }
                else if(i == 1){   printf("H %d\n", j);  }
                else if(i == 2){   printf("C %d\n", j);  }
                else if(i == 3){   printf("D %d\n", j);  }
             }
        }
    }
    return 0;
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(a<b){
        int tmp = a;
        a = b;
        b = tmp;
    }
    int r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
      
}
int main(){
    int N,X;
    cin >> N >> X;
    vector<int> x(N);
    for(int i = 0;i < N;i ++){
        int sx;
        cin >> sx;
        x[i] = abs(sx-X);
    }
    sort(x.begin(),x.end());
  	int ans = 0;
    if(N > 1) ans = gcd(x[0],x[1]);
    else ans = x[0];
    for(int i = 2;i < N;i ++){
        ans = gcd(ans,x[i]);
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

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

int main(){
	ll a,b,c,d;
	cin >> a >> b >> c >> d;
	ll ans = 0;
	ll g = __gcd(c,d);
	ll l = c/g*d;
	ans += b/c - (a-1)/c;
	ans += b/d - (a-1)/d;
	ans -= b/l - (a-1)/l;
	ans = (b-a+1) - ans;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

ll w[102],v[102];
ll dp[102][100005];

int main(){
    ll N,W; cin >> N >> W;
    rep(i,N) cin >> w[i] >> v[i];

    rep(i,102) rep(j,100005) dp[i][j] = LINF;

    // dp[i][j] := i個目までの荷物,価値jとなるようなときの重さの最小値
    dp[0][0] = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<=100000;j++){
            dp[i+1][j] = dp[i][j];
            if(j-v[i] >= 0) dp[i+1][j] = min(dp[i+1][j],dp[i][j-v[i]]+w[i]);
        }
    }

    ll ans = 0;
    for(int i=0;i<=100005;i++){
        if(dp[N][i] <= W) ans = i;
    }
    cout << ans << endl;
}


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

const int N = 1e4+5;

int a[N],b[N];

string s[N];

set<int> ff;
vector<int> bb;

int matching[N];
void solve() {
    int n;
    memset(matching,-1,sizeof(matching));
    scanf("%d",&n);
    int ret = 0;
    int u = 0;
    for(int i=0;i<n;++i) {
        cin>>s[i];
        for(int j = 0;j<s[i].size();++j) {
            if(s[i][j]=='A') {
                ++a[i];
                if(j+1<s[i].size() && s[i][j+1]=='B') {
                    ++ret;
                }
            } else if(s[i][j]=='B') {
                ++b[i];
            }
        }
        if(s[i][0]=='B' && s[i].back()=='A') {
            ++u;
            continue;
        }
        if(s[i][0]=='B'){
            ff.insert(i);
        }
        if(s[i].back()=='A') {
            bb.push_back(i);
        }
    }
    if(u>1) {
        ret += u-1;    
    }
    
    int aa  = bb.size();
    int bb = ff.size();

    if(u>0 && aa>0) {
        ++ret;
    }
    if(u>0 && bb>0) {
        ++ret;
    }
    if(u>0) {
        aa = max(aa-1,0);
        bb = max(bb-1,0);
    }
    //cout<<min(aa,bb)<<endl;
    //cout<<ret<<endl;
    ret += min(aa,bb);
    cout<<ret<<endl;

}

int main(){
    //freopen("input.txt","r",stdin);
    solve();
}

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

void dicemove(int);

typedef struct {
  int up;
  int back;
  int right;
  int left;
  int front;
  int down;
}dicetype;

dicetype dice;

#define FRONT 0
#define BACK  1
#define RIGHT 2
#define LEFT  3
#define CLOCK 4
#define COUNTERCLOCK 5

int main(void){

  int qnum;
  int up_num;
  int back_num;

  cin >> dice.up >> dice.back >> dice.right >> dice.left >> dice.front >> dice.down;
  cin >> qnum;

  for ( int i = 0 ; i < qnum ; i++){
    cin >> up_num >> back_num;

    //?????¢??????
    if(up_num == dice.left){
      dicemove(RIGHT);
    }else if(up_num == dice.right){
      dicemove(LEFT);
    }else if(up_num == dice.back){
      dicemove(FRONT);
    }else if(up_num == dice.front){
      dicemove(BACK);
    }else if(up_num == dice.down){
      dicemove(LEFT);
      dicemove(LEFT);
    }else{
      //Do Nothing
    }

    if(back_num == dice.left){
      dicemove(COUNTERCLOCK);
    }else if(back_num == dice.right){
      dicemove(CLOCK);
    }else if(back_num == dice.front){
      dicemove(CLOCK);
      dicemove(CLOCK);
    }else{
      //Do Nothing
    }

    cout << dice.right << endl;

  }

  return 0;

}

void dicemove(int dir){

  switch(dir){

    int temp;

    case FRONT:
    temp = dice.up;
    dice.up = dice.back;
    dice.back = dice.down;
    dice.down = dice.front;
    dice.front = temp;
    break;

    case BACK:
    temp = dice.up;
    dice.up = dice.front;
    dice.front = dice.down;
    dice.down = dice.back;
    dice.back = temp;
    break;

    case RIGHT:
    temp = dice.up;
    dice.up = dice.left;
    dice.left = dice.down;
    dice.down = dice.right;
    dice.right = temp;
    break;

    case LEFT:
    temp = dice.up;
    dice.up = dice.right;
    dice.right = dice.down;
    dice.down = dice.left;
    dice.left = temp;
    break;

    case CLOCK:
    temp = dice.back;
    dice.back = dice.right;
    dice.right = dice.front;
    dice.front = dice.left;
    dice.left = temp;
    break;

    case COUNTERCLOCK:
    temp = dice.back;
    dice.back = dice.left;
    dice.left = dice.front;
    dice.front = dice.right;
    dice.right = temp;
    break;

    default:
    break;
  }
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    int n;
    cin >> n;
    vector< LL > v(n);
    LL bsum = 0;
    for( int i = 0; i < n; ++i ) {
        LL a, b;
        cin >> a >> b;
        v[i] = a + b;
        bsum += b;

    }
    sort(all(v), greater< LL >());
    LL asum = 0;
    for( int i = 0; i < n; i += 2 ) {
        asum += v[i];

    }
    cout << asum - bsum << endl;
    return 0;
}



Measured memory_bytes: 1024