akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define fir first
#define sec second
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define maxd 1000000007
#define eps 1e-6
typedef long long ll;
const int N=100000;
const double pi=acos(-1.0);
int n,m,k,nx,ny,x,y;
char s[200200],t[200200];

int read()
{
	int x=0,f=1;char ch=getchar();
	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
	return x*f;
}

int main()
{
	n=read();m=read();k=read();
	x=read(),y=read();
	scanf("%s%s",s+1,t+1);
	nx=x;ny=y;
	rep(i,1,k)
	{
		if (s[i]=='L') ny--;
		if (ny<=0) {printf("NO");return 0;}
		if ((t[i]=='R') && (ny<m)) ny++;
	}
	nx=x;ny=y;
	rep(i,1,k)
	{
		if (s[i]=='R') ny++;
		if (ny>m) {puts("NO");return 0;}
		if ((t[i]=='L') && (ny>1)) ny--;
	}
	nx=x;ny=y;
	rep(i,1,k)
	{
		if (s[i]=='U') nx--;
		if (nx<=0) {puts("NO");return 0;}
		if ((t[i]=='D') && (nx<n)) nx++;
	}
	nx=x;ny=y;
	rep(i,1,k)
	{
		if (s[i]=='D') nx++;
		if (nx>n) {puts("NO");return 0;}
		if ((t[i]=='U') && (nx>1)) nx--;
	}
	puts("YES");
	return 0;
}


Measured memory_bytes: 640
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long 
#define REP(i, a, b) for (ll i = a; i < b; i++)
#define REPI(i, a, b) for (ll i = b - 1; i >= a; i--)
#define i_os ios::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
#define INF (ll)1e18 + 100
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
/*SOME BITMASK KNOWLEDGE
1)x & (x - 1):sets the last one bit of x to zero
power of two exactly when x & (x − 1) = 0.
2)x & -x:sets all the one bits to zero, except last one bit
3)x | (x - 1):inverts all the bits after the last one bit*/
#define o_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define o_setll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
typedef tree<pair<ll, ll>,null_type,less<pair<ll, ll>>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set1;
typedef tree<string,null_type,less<string>,rb_tree_tag,tree_order_statistics_node_update> indexed_set2;
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

int main()
{   
    ll n,k;
    cin>>n>>k;
    int mod = 998244353;

    pair<ll,ll> arr[k];
    REP(i,0,k){
        cin>>arr[i].first>>arr[i].second;
    }
    ll dp[n+2] = {0};
    dp[n] = 1;
    ll pref[n+2] = {0};
    pref[n] = 1;

    REPI(i,1,n){
        dp[i] = 0;
        REP(j,0,k){
            if(i+arr[j].first <= n) dp[i] += pref[i+arr[j].first];
            dp[i] %= mod;
            if(i+arr[j].second + 1 <= n) dp[i] -= pref[i+arr[j].second + 1];
            dp[i] += mod;
            dp[i] %= mod;
        }
        pref[i] = pref[i+1] + dp[i];
        pref[i] %= mod;
    }
    cout<<dp[1]<<endl;
    return 0;
}   
    

Measured memory_bytes: 6752
#include <iostream>
#include <utility>
#include <vector>
#define P pair<int,int>
using namespace std;

char f[20][10];
bool isCheck[20][10];
void pr(){ for(int i=0;i<12;i++){ for(int j=0;j<6;j++) cout<<f[i][j];cout<<endl;}}

int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
int count(int y,int x){
  if( isCheck[y][x] ) return 0;
  isCheck[y][x] = true;
  char c = f[y][x];

  int nx,ny, rtn=1;
  for( int i=0;i<4;i++ ){
    nx=x+dx[i]; ny=y+dy[i];
    if( nx<0 || nx>=6 ) continue;
    if( ny<0 || ny>=12) continue;
    if( f[ny][nx] == c )
      rtn += count(ny,nx);
  }
  return rtn;
}
void erase( int y,int x ){
  char c = f[y][x];
  f[y][x] = '.';
  int nx,ny;
  for( int i=0;i<4;i++ ){
    nx=x+dx[i]; ny=y+dy[i];
    if( nx<0 || nx>=6 ) continue;
    if( ny<0 || ny>=12) continue;
    if( f[ny][nx]=='O' )     f[ny][nx]='.';
    else if( f[ny][nx]==c )  erase( ny,nx );
  }
}


int main(){
  int datasetN;  cin >> datasetN;
  while( datasetN-- ){
    for( int i=0;i<12;i++ ) for( int j=0;j<6;j++ ) cin >> f[i][j];

    int ans=0;
    bool flag;
    do{
      flag=false;
      for( int i=0;i<12;i++)for( int j=0;j<6;isCheck[i][j++]=false );
      vector<P> v;
      for( int i=0;i<12;i++ )
	for( int j=0;j<6;j++ ){
	  if( f[i][j]=='O' || f[i][j]=='.' || isCheck[i][j] ) continue;
	  int cnt = count(i,j);
	  if( cnt>=4 ){ v.push_back( P(i,j) );   flag = true;	  }
	}
      if( flag ){ // 消去処理
	ans++;
	for( int i=0;i<(int)v.size();i++ ){
	  //	  cout << "erase " << v[i].first << " " << v[i].second << endl;
	  erase( v[i].first,v[i].second );
	}
	// 落下処理
	//	cout << ans << endl;	pr();
	for( int j=0;j<6;j++ ){
	  for( int i=11;i>=0;i-- ){
	    if( f[i][j]=='.' ){
	      for( int k=i-1;k>=0;k-- ){
		if( f[k][j]!='.' ){
		  f[i][j] = f[k][j];
		  f[k][j] = '.';
		  break;
		}
	      }
	    }
	  }
	}
	//	pr();
      }
    }while( flag );
    cout << ans << endl;;
  }

  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
vector<int>v[100005];
int get_sg(int u,int pre){
    int ret=0;
    for(int i=0;i<v[u].size();i++){
        if(v[u][i]!=pre)
            ret^=(1+get_sg(v[u][i],u));
    }
    return ret;
}
int main(){
    int t,n;

        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            v[i].clear();
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        if(get_sg(1,-1))
            puts("Alice");
        else
            puts("Bob");
    return 0;
}


Measured memory_bytes: 11904
from string import ascii_lowercase, ascii_uppercase
text = open(0).read()
text = list(text.lower())
abc = list(ascii_lowercase)
answer = [0]*26

for i in text:
    num = ascii_lowercase.find(i)
    if num > -1:
        answer[num] += 1

for i in range(26):
    print(f"{abc[i]} : {answer[i]}")


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

int main()
{
    int n;
    cin>>n;
    long int v=0;
    for(int i=0;i<n;i++) v+=i;

    cout<<v<<endl;

	return 0;
}


Measured memory_bytes: 256
n=int(input())
x=input()
d=int(input())
x=list(x)
y=[1]*n
for i in range(n):
    if d and x[i]=='0':y[i]=0;x[i]='1';d-=1
i=n-1
while d:
    if y[i]:x[i]='0';d-=1
    i-=1
print(*x, sep='')

Measured memory_bytes: 7744
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int N, K;

int main() {
    cin >> N >> K;
    double ans, x = 1;

    for (int i = N; i > 0; i--) {
        while (i * x < K) {
            x *= 2;
        }
        ans += double(1) / x;
    }

    cout << setprecision(20) << ans / double(N) << endl;
    return 0;
}


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

int main(){
  int n; cin >>n;
  map<int, int> mp;
  ll total = 0;
  rep(i,n){
    int a; cin >>a;
    mp[a]++;
    total += a;
  }
  int q; cin >>q;
  rep(i,q){
    int b,c; cin >>b >>c;
    total += (c-b)*mp[b];
    mp[c] += mp[b];
    mp[b] = 0;
    cout << total << endl;
  }
  return 0; 
}

Measured memory_bytes: 7956
from collections import Counter
from math import gcd

class Prime:
    def __init__(self, N):
        smallestPrime = [1] * (N + 1)
        primes = []

        for i in range(2, N + 1):
            if smallestPrime[i] != 1:
                continue
            primes.append(i)
            for p in range(i * 2, N + 1, i):
                if smallestPrime[p] == 1:
                    smallestPrime[p] = i

        self.smallestPrime = smallestPrime
        self.primes = primes

    def isPrime(self, n):
        return n > 1 and self.smallestPrime[n] == 1

    def factorization(self, n):
        ret = Counter()
        while (p := self.smallestPrime[n]) != 1:
            ret[p] += 1
            n //= p
        if n > 1:
            ret[n] += 1
        return ret

N = int(input())
A = list(map(int, input().split()))
prime = Prime(max(A) + 100)

def isSetwise(A):
    ret = A[0]
    for a in A:
        ret = gcd(ret, a)
    return ret == 1

def isPairwise(A):
    cnt = Counter()
    for a in A:
        for p in prime.factorization(a):
            if cnt[p] >= 1:
                return False
            cnt[p] += 1
    return True

if not isSetwise(A):
    print('not coprime')
elif isPairwise(A):
    print('pairwise coprime')
else:
    print('setwise coprime')


Measured memory_bytes: 132940
#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX_STRING 2200000
#define MAXCARDS 200000

double alCards[MAXCARDS];
char sInput[MAX_STRING];

int main() {

	char* psInput;
	long long l=0;
	double  lLoopEnd=0.0;
	double  lTemp=0.0;
	double  lAllSum=0.0;
	double  lLeftSum=0.0;
	double  lRightSum=0.0;
	double  lTempMin=0.0;
	double  lMin=0.0;
	double  lCardsNumber =0.0;

//	printf("hoge\n");

	// read line 1
	gets(sInput);
	lCardsNumber = atol(sInput);
	// read line 2
	gets(sInput);
	psInput = strtok(sInput," ");
	for (l=0;l<lCardsNumber;l++){
		lTemp=atol(psInput);
		alCards[l] = lTemp;
		lAllSum=lAllSum+lTemp;
		psInput = strtok(NULL," ");
	}

	// calc
	lRightSum=lAllSum;
	lMin=99999000000000;
	lLoopEnd = lCardsNumber-1;
	for (l=0;l<lLoopEnd;l++){
		lLeftSum=lLeftSum + alCards[l];
		lRightSum=lRightSum - alCards[l];
		lTempMin =lLeftSum-lRightSum;
		if (lTempMin<0){
			lTempMin = lTempMin * -1;
		}
//		printf("left:%.0f right:%.0f abs:%.0f sum:%.0f\n",lLeftSum,lRightSum,lTempMin,lAllSum);
		if (lTempMin<lMin){
			lMin=lTempMin;
		}
	}

	printf("%.0f",lMin);
    return 0;
}


Measured memory_bytes: 2944
let nk = readLine()!.split(separator: " ").map {
  Int($0)!
}
let n = nk[0]
let k = nk[1]

let mod: Int = 1000000007

func f(_ x: Int) -> Int {
  return x * (n - x + 1) + 1 % mod
}

var c = 0

for i in k...n+1 {
  c += f(i)
  c %= mod
}

print(c)


Measured memory_bytes: 8216
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int H,W,K;
int sx,sy,gx,gy;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
main()
{
	cin>>H>>W>>K;
	cin>>sx>>sy>>gx>>gy;
	sx--,sy--,gx--,gy--;
	vector<string>S(H);
	for(int i=0;i<H;i++)cin>>S[i];
	vector<vector<int> >D(H,vector<int>(W,(int)1e9));
	queue<pair<int,int> >P;
	D[sx][sy]=0;
	P.push(make_pair(sx,sy));
	while(!P.empty())
	{
		int x=P.front().first,y=P.front().second;
		P.pop();
		int nd=D[x][y]+1;
		for(int r=0;r<4;r++)
		{
			int tx=x,ty=y;
			for(int i=1;i<=K;i++)
			{
				tx+=dx[r],ty+=dy[r];
				if(tx<0||ty<0||tx>=H||ty>=W||S[tx][ty]=='@'||D[tx][ty]<nd)break;
				if(D[tx][ty]>nd)
				{
					D[tx][ty]=nd;
					P.push(make_pair(tx,ty));
				}
			}
		}
	}
	int ans=D[gx][gy];
	cout<<(ans<1e9?ans:-1)<<endl;
}

Measured memory_bytes: 12060
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  string s;
  cin >> s;

  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) cout << "Bad" << endl;
  else cout << "Good" << endl;
}


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

int main()
{
    ll N;
    cin >> N;
    vector<vector<ll>> masu(3,vector<ll>(N+1));

    for(ll i = 1; i <= 2; i++)
    {
        for(ll j = 1; j < N+1; j++)
        {
            cin >> masu.at(i).at(j);
        }
    }

    
    ll sumMax = 0;
    
    for(ll i = 1; i < N+1; i++)
    {
        ll sum = 0;
        for(ll j = 1; j < N+1; j++)
        {
            if(j < i)
            {
                sum += masu.at(1).at(j);
            }
            else if(j == i)
            {
                sum += masu.at(1).at(j);
                sum += masu.at(2).at(j);
            }
            else
            {
                sum += masu.at(2).at(j);
            }
            
             
        }
        sumMax = max(sum,sumMax);
    }
    cout << sumMax << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;
}
using ll = long long;
const ll MOD = 1e9 + 7;
const long long INF = 1LL << 60;

int main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i, n) cin >> s.at(i);

    map<string, int> mp;
    rep(i, n)
    {
        mp[s.at(i)]++;
    }

    int max_value = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++)
    {
        max_value = max(max_value, itr->second);
    }

    map<string, int> mp2;
    for (auto itr = mp.begin(); itr != mp.end(); itr++)
    {
        if (max_value == itr->second)
        {
            mp2[itr->first]++;
        }
    }

    for (auto itr = mp2.begin(); itr != mp2.end(); itr++)
    {
        cout << itr->first << endl;
    }
}

Measured memory_bytes: 39296
n = gets.chomp.to_i
alist = gets.chomp.split.collect{ |item| item.to_i}

result = []
n.times do |ni|
  result[ni] = 0
end
num = 1
alist.each do |ai|
  result[ai-1] = num
  num +=1
end

puts result.join(" ")


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

int main() {
	int N, A, B;
	cin >> N >> A >> B;

	int Min;
	int Max;

	if (A == B && A == N) {
		Max = N;
		Min = N;
	}

	if ((A + B >= N) && (A + B != 2 * N)) {
		if (A >= B) {
			Max = B;
			Min = B-(N-A);
		} else {
			Max = A;
			Min = A-(N-B);
		}
	}
	if (A + B < N) {
		if (A >= B) {
			Max = B;
			Min = 0;
		} else {
			Max = A;
			Min = 0;
		}
	}
	cout << Max << " " << Min << endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
//		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//		String W	 = in.readLine();
//		int num = Integer.parseInt(W.split(" ")[0]);

		Scanner sc = new Scanner(System.in);
		String N = sc.next();

		char n = N.charAt(N.length()-1);
		
		if(n=='3') {
			System.out.println("bon");
		}else if(n=='0'||n=='1'||n=='6'||n=='8') {
			System.out.println("pon");
		}else {
			System.out.println("hon");
		}


	}

	//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
        return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
        return b == 0 ? a: gcd(b, a % b);
	}



}


Measured memory_bytes: 35660
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>




int main()
{
    
    std::vector<int> data(3);
    for (auto& val : data)
        std::cin >> val;
    
    std::sort(data.begin(), data.end());


    std::cout << data[1] - data[0] + data[2] - data[1];

    return 0;
}

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

int tax(int r, int n){ // rが税率、nは税抜き価格
    int price = n * (100 + r) / 100;
    return price;
}

int main(){
    while(true){
        int ans = 0; //答えを格納、毎回初期化
        int x, y, s; cin >> x >> y >> s;
        if(x == 0 && y == 0 && s == 0) break;
        // 2種類の品i, jについて1円からs円まで全探索
        for(int i = 1; i < s; i++){
            for(int j = 1; j < s; j++){
                if(tax(x, i) + tax(x, j) == s){
                    ans = max(ans, tax(y, i) + tax(y, j));
                }
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
LL a[N],ans,n,b[N];
int main()
{
	scanf("%lld",&n);
	for(LL i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	for(LL i=1;i<=n;i++){
		LL x=upper_bound(b+1,b+1+n,a[i])-b-1;
		if((x&1)!=(i&1))ans++;
	}
	cout<<ans/2<<endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

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

int main() {

    int h, w; cin >> h >> w;

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

    queue<pair<int, int>> q;

    vector<vector<int>> d(h, vector<int>(w, -1));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (a[i][j] == '#') {
                d[i][j] = 0;
                q.push(make_pair(i, j));
            }
        }
    }

    while (!q.empty()) {
        auto p = q.front();
        q.pop();

        int x = p.first;
        int y = p.second;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue;
            if (d[nx][ny] != -1) continue;

            d[nx][ny] = d[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }

    int ans = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ans = max(ans, d[i][j]);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 17040
#include<iostream>
#include<stdio.h>
#include<cctype>
#include<string>
using namespace std;

int main(){
	string W, T;
	int a = 0;
	cin >> W;
	while (1){
		cin >> T;
		if (T == "END_OF_TEXT")break;
		for (int i = 0; i < T.size(); i++){
			T[i] = tolower(T[i]);
		}
		if (W == T){
			a++;
		}
	}

	cout << a << endl;

	return 0;
}

Measured memory_bytes: 3224
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
for node in range(1, N):
    a = int(input())
    edge[a-1].append(node)

def dfs(n):
    """
    dfs(n) := nを根としたトーナメントの深さ

    nの深さを浅くしたい
    -> 深い場所に浅い頂点vを割り当てる
    -> 対戦数が少ない人から対戦していく
    """

    if not edge[n]:
        return 0
    
    que = []
    for v in edge[n]:
        que.append(dfs(v))

    que.sort(reverse=True)
    
    res = 0
    for cnt, depth in enumerate(que, start=1):
        # 今までの対戦数 + nの何人目の相手か
        res = max(res, depth + cnt)
    
    return res

print(dfs(0))

Measured memory_bytes: 118960
A, B = map(int, input().split())


def f(n):
    if n % 2:
        return (n + 1) // 2 % 2
    else:
        return n // 2 % 2 ^ n


ans = f(A - 1) ^ f(B)
print(ans)

# F(A, B) = F(0, A - 1) ⊕ F(0, B)
# f(n) = F(0, n)
#  任意の偶数nについて n ⊕ (n + 1) = 1
# 0 ⊕ 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6
# = (0 ⊕ 1) ⊕ (2 ⊕ 3) ⊕ (4 ⊕ 5) ⊕ 6
# = 1 ⊕ 1 ⊕ 1 ⊕ 6


Measured memory_bytes: 2940
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long ll;


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

    if(y%2==1)
    {
        printf("No\n");
    }
    else if(2*x<=y&&y<=4*x)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    
    return 0;
}

Measured memory_bytes: 1620
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
#include<set>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

const ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}

ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
int main() {
	int a, b,c,i;
	cin >> a >> b>>c;
	for (i = 0; i < 10; i++) {
		c = a * c - b;
		cout << c << endl;
	}
}


Measured memory_bytes: 4992
#!/usr/bin/python
# -*- coding: utf-8 -*-
n = int(raw_input())
s = []
for _ in xrange(n):
    s.append(raw_input())
 
ss = set()
last = None
ret = 'Yes'
for w in s:
    if w in ss:
        ret = 'No'
        break
    if last is None:
        ss.add(w)
        last = w
        continue
    if last[-1] != w[0]:
        ret = 'No'
        break
    ss.add(w)
    last = w
 
print ret
##17024717 | shenweiqiang's solution for [AtCoder-4252] [Problem B]

Measured memory_bytes: 2568
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include<string>
#include <algorithm>
#include <iostream>
using namespace std;

struct card{
    char w[20];
    int l = 20;
    int c=0;
};


int n, m, idx=0, idxred=0;
char word[20];
card ca[120], red[120];
bool flag;

int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        flag = false;
        scanf("%s", word);
        for(int j=0; j<idx; j++){
            if(strlen(word) == ca[j].l) flag = true;
                for(int k=0; k<ca[j].l; k++){
                    if(ca[j].w[k] != word[k])
                        flag = false;
                }

            if(flag){
                ca[j].c += 1;
                break;
            }
        }
        if(!flag){
            for(int j=0; j<strlen(word); j++)
                ca[idx].w[j] = word[j];
            ca[idx].c = 1;
            ca[idx].l = strlen(word);
            idx +=1;
        }
    }
    //printf("kko");
    scanf("%d", &m);
    for(int i=0; i<m; i++){
        flag = false;
        scanf("%s", word);
        for(int j=0; j<idxred; j++){
            if(strlen(word) == red[j].l) flag = true;
                for(int k=0; k<red[j].l; k++){
                    if(red[j].w[k] != word[k])
                        flag = false;
                }

            if(flag){
                red[j].c += 1;
                break;
            }
        }
        if(!flag){
            for(int j=0; j<strlen(word); j++)
                red[idxred].w[j] = word[j];
            red[idxred].c = 1;
            red[idxred].l = strlen(word);
            idxred +=1;
        }
    }



    /*sort(ca, ca+idx, compare);
    sort(red, red+idxred, compare);*/
    int maxi = 0, aux;
    flag = false;

    for(int i=0; i<idx; i++){
        aux = ca[i].c;
        for(int j=0; j<idxred; j++){ flag = false;
            if(ca[i].l == red[j].l){ flag = true;
                for(int k=0; k<ca[i].l; k++){
                    if(ca[i].w[k] != red[j].w[k]){
                        flag = false;
                        break;
                    }
                }
            }

            if(flag){
                aux -= red[j].c;
                break;
            }
        }
        if(aux > maxi)
            maxi = aux;
    }
    printf("%d\n", maxi);
}


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

int main() {
  int A,B,C,D;
  string res="Yes";
  cin>>A>>B>>C>>D;
  while(true){C-=B;
               if(A*C<=0){break;}
               A-=D;
               if(A*C<=0){res="No";break;}
              }  
  cout<<res<<endl;
}

Measured memory_bytes: 3564
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = read()[:-1]


# 偶数番目に0の個数を格納するようなデータ構造を構築する
num_cnts = []
now = '1'  # 0から考慮する
cnt = 0
for s in S:
    if s == now:
        cnt += 1
    if s != now:  # もしいまカウントしている文字と異なったらカウントを格納して、カウントをリセットする。
        num_cnts.append(cnt)
        now = s
        cnt = 1
num_cnts.append(cnt)
# もしSが0で終わっていたら0個の1を付け足す
if S[-1] == '0':
    num_cnts.append(0)

assert len(num_cnts) % 2 == 1, '奇数個じゃない！'

# 累積和で実装
from itertools import accumulate
num_accums = [0]+list(accumulate(num_cnts))

# 最大長の探索
add = min(2*K+1, len(num_cnts))  # Kで指定するよりも短い場合はそっちに合わせる
ans = 1

# print(num_cnts)
for left in range(0, len(num_cnts) - add+1, 2):
    right = left + add
    ans = max(ans, num_accums[right] - num_accums[left])
    # print(left, right, ans)

print(ans)


Measured memory_bytes: 8716
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int l;
		int count = 0;

		List<Integer> list = new ArrayList<>();

		for(int i = 0; i < n; i++) {
			l = sc.nextInt();
			list.add(l);
		}

		for(int i = 0; i < list.size() - 2; i++) {

			for(int j = i + 1; j < list.size() - 1; j++) {

				for(int k = j + 1; k < list.size(); k++) {
					int a = list.get(i);
					int b = list.get(j);
					int c = list.get(k);

					if(a != b && b != c && c != a) {
						if(a + b > c && b + c > a && c + a > b) {
							count++;
						}
					}


				}

			}

		}

		System.out.println(count);

	}

}

Measured memory_bytes: 37028
h,w=map(int,input().split())
ans=-1
s=[]
for i in range(h):
	ss=input()
	s.append(ss)
from collections import deque as dq
for i in range(h):
	for j in range(w):
		if s[i][j]=="#":
			continue
		dis=[[10**3 for _ in range(w)]for _ in range(h)]
		dis[i][j]=0
		queue=dq([[i,j]])
		while queue:
			r=queue.popleft()
			if r[0]+1<h:
				if s[r[0]+1][r[1]]=="." and dis[r[0]+1][r[1]]==10**3:
					queue.append([r[0]+1,r[1]])
					dis[r[0]+1][r[1]]=dis[r[0]][r[1]]+1
			if r[0]-1>=0:
				if s[r[0]-1][r[1]]=="." and dis[r[0]-1][r[1]]==10**3:
					queue.append([r[0]-1,r[1]])
					dis[r[0]-1][r[1]]=dis[r[0]][r[1]]+1
			if r[1]+1<w:
				if s[r[0]][r[1]+1]=="." and dis[r[0]][r[1]+1]==10**3:
					queue.append([r[0],r[1]+1])
					dis[r[0]][r[1]+1]=dis[r[0]][r[1]]+1
			if r[1]-1>=0:
				if s[r[0]][r[1]-1]=="." and dis[r[0]][r[1]-1]==10**3:
					queue.append([r[0],r[1]-1])
					dis[r[0]][r[1]-1]=dis[r[0]][r[1]]+1
		for k in range(h):
			for l in range(w):
				if dis[k][l]!=10**3:
					ans=max(ans,dis[k][l])
print(ans)
			



			


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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

typedef long long ll;


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

  return gcd(b, a % b);
}

int main(){
  int N;
  cin >> N;
  vector<ll> A(N);
  ll mini = 1e9;
  REP(i, N){
    cin >> A[i];
  }
  
  ll g = A[0];
  REP(i, N){
    if(g > A[i])
      g = gcd(g, A[i]);
    else
      g = gcd(A[i], g);
  }

  cout << g << endl;
  
  return 0;
}

Measured memory_bytes: 1024
n = int(input())
A = []
for _ in range(n):
    a = []
    for _ in range(int(input())):
        a.append([int(i) for i in input().split()])
    A.append(a)

ans = 0
for i in range(2**n):
    
    bit = bin(i)[2:].zfill(n)[::-1]
    cnt = bit.count('1')
    b = False
    
    for i,t in zip(bit,A):
        if i == '0': continue
        for p in t:
            k,v = p 
            if bit[k-1] != str(v):
                b = True
                cnt = 0
                break
        
        if b == True: break
    
    ans = max(ans,cnt)

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <map>
#include<queue>

const int INF = 1 << 28;
const long long MOD = 1000000007;
using namespace std;
using Graph = vector<vector<int>>;

template<class T> bool chmin(T &a, T &b) { if (a > b) { a = b; return 1; }return 0; }
template<class T> bool chmax(T &a, T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T, class U> using P = pair<T, U>;

vector<int> seen(50,-1);
int counter_for_dfs = 0;
void dfs(Graph &G, int v) {
	seen[v] = counter_for_dfs;
	counter_for_dfs++;
	for (auto v_next : G[v]) {
		if (seen[v_next]>=0)continue;

		dfs(G, v_next);
	}
}

void bfs(Graph &G) {
	vector<int> dist(G.size(), -1);
	queue<int> que;
	
	dist[0] = 0;
	que.push(0);
	while (!que.empty()) {
		int v = que.front();
		que.pop();

		for (int g : G[v]) {
			if (dist[g] != -1)continue;
			dist[g] = dist[v] + 1;
			que.push(g);
		}
	}
	for (auto i : dist) {
		cout << i << " ";
	}
}

int counter[200005] = {};
void bfs2(Graph &G,int p,int x) {
	vector<int> dist(G.size() , -1);
	queue<int> que;
	
	dist[p] = 0;
	que.push(p);
	while (!que.empty()) {
		int v = que.front();
		que.pop();

		for (int g : G[v]) {
			if (dist[g] != -1)continue;
			dist[g] = dist[v] + 1;
			que.push(g);
			counter[g] += x;
		}
	}
}
int main()
{
	int n;
	std::cin >> n;
	float rslt;
	rslt = n % 2 == 0 ? n: n + 1;
	rslt /= 2;
	rslt /= n;
	std::cout << rslt;

	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }


        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var NK = Sarray();
            var N = NK[0];
            var K = NK[1];
            var ans = 0d;
            for (var i = 1; i <= N; ++i)
            {
                if (K <= i)
                {
                    ans += (double)1 / N;
                    continue;
                }
                var sq = Ceiling(Log((double)K / i, 2));
                ans += (double)1 / Pow(2, sq) / N;
            }
            WriteLine($"{ ans:F10}");
            //Out.Flush();
        }
    }
}

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

#define forl(V, N) for(int V = 0; V < N; V++)
#define forll(V, S, E) for(int V = S; V < E; V++)
#define forlc(V, S, E, I) for(int V = S; V < E; V += I)
#define fore(E, X) for(auto &E:X)
#define print(X) cout << X
#define printsp(X) cout << X << " "
#define println(X) cout << X << endl
#define rem(X) X.top(); X.pop()
#define mid(A, B) ((A+B) / 2)
#define setmin(A, B) A = min(A, B)
#define setmax(A, B) A = max(A, B)
#define graph unordered_map<int, unordered_set<int>>
#define vi vector<int>
#define pb push_back
#define ll long long

int N, W;
int items[100][2];
ll DP[100][100001];

ll recur(int I, ll CW) {
    if(I == N) return 0;
    if(DP[I][CW] != -1) return DP[I][CW];
    DP[I][CW] = recur(I+1, CW);
    if(CW + items[I][0] <= W) setmax(DP[I][CW], items[I][1] + recur(I+1, CW+items[I][0]));
    return DP[I][CW];
}

int main() {
    cin >> N >> W;
    forl(i, N) cin >> items[i][0] >> items[i][1];
    forl(i, 100) fill_n(DP[i], 100001, -1);
    println(recur(0, 0));
}

Measured memory_bytes: 78336
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    s = input().strip()
    p = 0
    if "N" in s:
        p += 1
    if "S" in s:
        p += 1
    if p == 1:
        print("No")
        return
    p = 0
    if "E" in s:
        p += 1
    if "W" in s:
        p += 1
    if p == 1:
        print("No")
        return
    
    print("Yes")
if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

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

int main(){
    string s;cin >> s;
    bool result = true;
    for (int i=0;i<s.size();i++){
        if (i % 2 == 0){
            if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D'){
                result = false;
                break;
            }
        } else {
            if (s[i] != 'L' && s[i] != 'U' && s[i]!='D'){
                result = false;
                break;
            }
        }
    }

    if (result) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define ll long long
int main(){
  int A,B;
  cin>>A>>B;
  cout<<(A-1)*(B-1)<<endl;
}

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

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

ll pow(ll a, ll n, ll m) {
	ll ret = 1LL;
	for (; n > 0LL; n >>= 1LL, a = a * a % m) {
		if (n % 2LL == 1LL) {
			ret = ret * a % m;
		}
	}
	return ret;
}

int main() {
    ll K;
    string S;
    cin>>K>>S;
    ll N = S.size();
    ll A = 1LL;
    ll cmb = N;
    ll t = 25LL;
    for(ll i = 1; i <= K; i++){
        A = (cmb * t  + 26*A)%mod;
        cmb = (((cmb * (N+i))%mod)* pow(i+1,mod-2,mod))%mod;
        t= (t*25LL)%mod;
    }
    cout<<A<<endl;
}

Measured memory_bytes: 5300
MOD = 10 ** 9 + 7
def pow(n, k)
  k %= (MOD - 1)
  return 1 if k.zero?
  return pow(n, k - 1) * n % MOD if k.odd?
  return (pow(n, k / 2) ** 2) % MOD
end
def max(a,b); a > b ? a : b; end
  
N = gets.to_i
ab0 = 0
a0 = 0
b0 = 0
dp = Hash.new(0)

N.times.each do
  a,b = gets.split.map(&:to_i)
  if a.zero? && b.zero?
    # どの魚とも仲が悪い
    ab0 += 1
  elsif a.zero?
    # b == 0の魚と仲が悪い
    a0 += 1
  elsif b.zero?
    # a == 0 の魚と仲が悪い
    b0 += 1
  else
    # a/bでグループ分け
    # -b/aのグループと仲が悪い
    dp[a.to_r / b] += 1
  end
end

# 一旦 どの魚とも仲が悪いのは無視して、
# 仲が悪いグループのどちらかを選ぶ組み合わせを計算 2^a + 2^b - 1
# 仲が悪いグループがいない場合 2^a
ans = 1
used = {}

if a0.zero? || b0.zero?
  ans = ans * pow(2, max(a0, b0)) % MOD
else
  ans = ans * (pow(2, a0) + pow(2,b0) - 1) % MOD
end
dp.keys.each do |k|
  next if used[k]
  used[k] = true
  if dp[-1/k] > 0
    ans = ans * (pow(2, dp[k]) + pow(2, dp[-1/k]) - 1) % MOD
    used[-1/k] = true
  else
    ans = ans * pow(2, dp[k]) % MOD
  end
end
# 何も選ばない場合を除く + どの魚とも仲が悪いグループを足す
puts (ans - 1 + ab0 ) % MOD 


Measured memory_bytes: 47448
from sys import stdin
N,Y = [int(x) for x in stdin.readline().rstrip().split()]
flag = False
for x in range(N+1):
    for y in range(N+1):
        z = N - x - y
        if z < 0:
          continue
        if Y == 10000 * x + 5000 * y + 1000 * z:
            flag = True
            break
    else:
        continue
    break
if flag:
    print(x,y,z)
else:
    print(-1,-1,-1)

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

int main() {
  int n;
  cin >> n;
  vector<bool>a(8);
  int p=0;
  for(int i=0;i<n;i++){
    int m;
    cin >>m;
    if(m>=3200){
      p++;
    }
    else if(m>=2800){
      a.at(7)=true;
    }
    else if(m>= 2400){
      a.at(6)=true;
    }
    else if(m>= 2000){
      a.at(5)=true;
    }
    else if(m>= 1600){
      a.at(4)=true;
    }
    else if(m>= 1200){
      a.at(3)=true;
    }
    else if(m>=800){
      a.at(2) =true;
    }
    else if(m>=400){
      a.at(1)=true;
    }
    else{
      a.at(0)=true;
    }
  }
  int ans =0;
  for(int i:a){
    ans+=i;
  }
  cout << max(ans,1) << " " << ans+p;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
A = [int(x) for x in input().split()]
for i in range(1,N+1):
    A[i-1] -= i
A = np.array(A,np.int64)
flagzero = np.count_nonzero(A == 0)
A_m, A_p = A[(A < 0)], A[(A > 0)]
A_p = np.sort(A_p)
A_m = np.sort(A_m)[::-1]
m, p = len(A_m), len(A_p)
if m == p:
    print(abs(A_p.sum()) + abs(A_m.sum()))
    sys.exit()
elif m > p:
    p += flagzero
    diff = m - p
    if diff <= 0:
        print(abs(A_p.sum()) + abs(A_m.sum()))
        sys.exit()
    else:
        diff = (diff//2) + (diff % 2 != 0)
        change = A_m[diff-1]
elif m < p:
    m += flagzero
    diff = p - m
    if diff <= 0:
        print(abs(A_p.sum()) + abs(A_m.sum()))
        sys.exit()
    else:
        diff = (diff//2) + (diff % 2 != 0)
        change = A_p[diff-1]
A_m -= change
A_p -= change
A_m = abs(A_m)
A_p = abs(A_p)
print(abs(A_p.sum()) + abs(A_m.sum()) + abs(flagzero * change))

Measured memory_bytes: 34236
x = int( input() )

import math

def is_prime(n) :
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

i=0
flag = 0
while flag == 0 : 
   if is_prime( i+x ) : 
      print( i+x )
      flag = 1 
   else :
      i += 1

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }

ll dp[110][100100] = {};

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

  ll n, mx_w;
  cin >> n >> mx_w;
  vl w(n), v(n);
  rep(i,n) cin >> w[i] >> v[i];
  rep(i,n) {
    rep(j,mx_w+1) {
      if(j >= w[i]) chmax(dp[i+1][j], dp[i][j-w[i]] + v[i]);
      chmax(dp[i+1][j], dp[i][j]);
    }
  }
  cout << dp[n][mx_w] << endl;
}

Measured memory_bytes: 79360
#include <stdio.h>
#include <string.h>

#define DEF_ELM_MAX 36

typedef	struct	_CARD {
	char	mark;
	int		value;
} CARD;

	CARD R1[DEF_ELM_MAX];
	CARD R2[DEF_ELM_MAX];

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void swap(CARD *x, CARD *y)
{
	CARD tmp;
	tmp = *x;
	*x = *y;
	*y = tmp;
	return;
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void bubbleSort(CARD *A, int N) // N ??????????´?????????? 0-????????????????????? A
{
	int flag = 1; // ????????£??\????´?????????¨??????
	int i;
	int j;

	i = 0;
	while (flag) {
		flag = 0;
		for ( j = N-1 ; j > i ; j-- ) {
			if (A[j].value < A[j-1].value) {
				swap(&A[j], &A[j-1]);
				flag = 1;
			}
		}
		i++;
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void selectionSort(CARD *A, int N) // N??????????´??????????0-?????????????????????A
{
	int i;
	int j;
	int minj;
	int flag;

	for ( i = 0 ; i < N ; i++ ) {
		minj = i;
		flag = 0;
		for ( j = i ; j < N ; j++ ) {
			if ( A[j].value < A[minj].value ) {
				minj = j;
				flag = 1;
			}
		}
		if (flag) {
			swap(&A[i], &A[minj]);
		}
	}
	return;
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void printStable(CARD *A1, CARD *A2, int N)
{
	int i;
	int flag = 0;
	for ( i = 0 ; i < N ; i++ ) {
		if (A1[i].mark != A2[i].mark) {
			flag = 1;
			break;
		}
	}
	printf("%s\n", ((flag == 0) ? "Stable" : "Not stable"));
}
////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void printout(CARD *A, int N)
{
	int i;
	for ( i = 0 ; i < N ; i++ ) {
		printf("%c%d", A[i].mark, A[i].value);
		if (i == N-1) {
			printf("\n");
		} else {
			printf(" ");
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
int main(void)
{
	int N;
	int i;
//
	scanf("%d", &N);
	for ( i = 0 ; i < N ; i++ ) {
		scanf(" %c%d", &R1[i].mark, &R1[i].value);
		R2[i] = R1[i];
	}
//
	bubbleSort(R1, N);

	selectionSort(R2, N);

	printout(R1, N);
	printf("Stable\n");
	
	printout(R2, N);
	printStable(R1, R2, N);

	return 0;
}

Measured memory_bytes: 612
N=int(input())
A=list(map(int,input().split()))
G=1000
K=0
for i in range(N-1):
  if A[i+1]>A[i]:
    K=K+G//A[i]
    G=G % A[i]
  if A[i+1]<A[i]:
    G=G+A[i]*K
    K=0
G=G+A[N-1]*K
print(G)

Measured memory_bytes: 9084
from sys import stdin
import heapq
INF = 1<<21
n = int(stdin.readline())
adj = [[]] * n
for u in range(0, n):
    U = list(map(int, stdin.readline().split()[2:]))
    adj[u] = [e for e in zip(U[0::2], U[1::2])]
def dijkstra():
    d = [0] + [INF] * (n - 1)
    hq = [(0, 0)]
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in adj[u]:
            alt = d[u] + c
            if d[v] > alt:
                d[v] = alt
                heapq.heappush(hq, (alt, v))
    for i, c in enumerate(d):
        print(i, c)
dijkstra()

Measured memory_bytes: 70900
a = input()
b = input()

if a == b:
    print("EQUAL")
if len(a) > len(b):
    print("GREATER")
elif len(a) < len(b):
    print("LESS")
else:
    for i in range(len(a)):
        if int(a[i]) > int(b[i]):
            print("GREATER")
            break
        elif int(a[i]) < int(b[i]):
            print("LESS")
            break


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

int main() {
	int a, b;
	while (scanf("%02d%02d", &a, &b) != EOF) {
		if (a >= 1 && a <= 12 && b >= 1 && b <= 12) {
			puts("AMBIGUOUS");
		} else if (a >= 1 && a <= 12) {
			puts("MMYY");
		} else if (b >= 1 && b <= 12) {
			puts("YYMM");
		} else {
			puts("NA");
		}
	}
	return 0;
}


Measured memory_bytes: 256
S=str(input())
T=str(input())
ls = []
cnt = 0
for i in range(len(S)-len(T)+1):
    cnt = 0
    for j in range(len(T)):
        #print(i,j)
        if T[j] != S[j+i]:
            #print(T[j],S[j+i])
            cnt += 1
    ls.append(cnt)
#print(ls)
print(min(ls))


Measured memory_bytes: 67736
#include "bits/stdc++.h"
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

constexpr auto inf = 1e9;

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

using ll = long long;

int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	if (a + b == c + d)
	{
		cout << "Balanced" << endl;
	}
	else if (a + b < c + d)
	{
		cout << "Right" << endl;
	}
	else
	{
		cout << "Left" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    int n,x,y,z;
    int count = 0;
    char s[256] = {};
    scanf("%d",&n);
    scanf("%s",s);
    for (int i = 0; i < n - 2; i++){
        if (s[i] == 'A'){
            if (s[i + 1] == 'B'){
                if (s[i + 2] == 'C'){
                    count++;
                    i = i + 2;
                }
            }
        }
    }
    printf("%d",count);

 return 0;   
}


Measured memory_bytes: 128
#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<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class Key, class Compare = less<Key>> // find_by_order, order_of_key (for multiset: pair(val, time of insertion))
using Tree = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;






void _SOLVE_() {

  int a, b, c;
  cin >> a >> b >> c;

  if (b >= c) {
    cout << b + c;
  } else {
    // b <= c
    if (a + b >= c) {
      cout << b + c;
    } else {
      // a + b < c
      cout << a + b + b + (c - a - b >= 0);
    }
  }







}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  #ifdef _DEBUG
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  #endif
  _SOLVE_();
}


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

long long mod=1e9+7;
long long INF=1e7;
double EPS = 1e-12;
const long long lim = 1e6+100;
typedef long long int lld;
typedef long long ll;
// typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); i--)
#define mset(a, v) memset(a, v, sizeof(a))
#define Error(x...) { cout << "(" << #x << ")" << " = ( "; printIt(x); }
template <typename T1> void printIt(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void printIt(T1 t1, T2... t2) { cout << t1 << " , "; printIt(t2...); }
 
 
#define popcount __builtin_popcountll
 
ll powP(ll x, ll y) {
    ll ans = 1, po = x % mod;
    while(y > 0) {
        if(y & 1) ans = ans * po % mod;
        y >>= 1; po = po * po % mod;
    }
    return ans;
}

ll findGcd(ll a, ll b){
    while(a != 0) { ll temp = b % a; b = a; a = temp; }
    return b;
}

vector<ll> Adj[lim], Set, Query[lim];
ll Array[lim], BArray[lim], dp[lim];
map<ll,ll> M, InverseMap, Map;

int main(){

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

    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
    
    lld T,i,p,j,l,e,r,b,c,k,m,q,a,d,w,x,y,u,v,z,t,curr,prev,sum=0,val,temp,countA=0,indicator=0,pos,h,minA,maxA,type,n,ans=0,left,right;
    string A,B,C;
    A = "YES", B="NO";
    // cin>>T;
    // rep(tt,1,T) {
    // } 
    cin>>A;
    if(A[A.size()-1]=='s') cout<<A+"es"<<endl;
    else cout<<A+'s'<<endl;
    return 0;
}


Measured memory_bytes: 50508