akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<functional>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef priority_queue<PII, VP, greater<PII> > LOWQ;
typedef vector<int> VI;

int n, k;
int c[5001], r[5001];
int a[10000], b[10000];

VI through_f[5001];
VI through_s[5001];
bool checked[5001];

void deep(int start) //??±?????????;
{
  memset(checked, false, sizeof checked);
  queue<PII> search; // {?????¢, ?????????}
  
  search.push(make_pair(0, start));
  checked[start] = true;

  while(!search.empty()){
    PII now = search.front();
    search.pop();

    for(int i = 0; i < through_f[now.second].size(); i++){
      PII next = make_pair(now.first + 1, through_f[now.second][i]);

      if(!checked[next.second]){
	checked[next.second] = true;
	through_s[start].push_back(next.second);
	if(next.first < r[start])
	  search.push(next);

      }
    }
  }
  return;
}

int dijk() //??????????????????
{
  memset(checked, false, sizeof checked);
  LOWQ search; // {?????????, ?????????};

  search.push(make_pair(0, 1));

  while(!search.empty()){
    PII now = search.top();
    search.pop();
    
    if(now.second == n)
      return now.first;

    if(!checked[now.second]){
      checked[now.second] = true;

      for(int i = 0; i < through_s[now.second].size(); i++)
	search.push(make_pair(now.first + c[now.second], through_s[now.second][i]));
      
    }
  }
}  

int main()
{
  cin >> n >> k;
  for(int i = 1; i <= n; i++)
    cin >> c[i] >> r[i];
  for(int i = 0; i < k; i++)
    cin >> a[i] >> b[i];

  for(int i = 0; i < k; i++){
    through_f[a[i]].push_back(b[i]);
    through_f[b[i]].push_back(a[i]);
  }

  for(int i = 1; i <= n; i++)
    deep(i);

  cout << dijk() << endl;

  return 0;
}

Measured memory_bytes: 200760
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
        String S = sc.next();
        if(S.equals("-")) break;
        int m = sc.nextInt();
        for(int i = 0; i<m; i++){
            int h = sc.nextInt();
            String primer = S.substring(0,h);
            String follower = S.substring(h);
            
            S = new String(follower+primer);
        }
        System.out.println(S);
        }
        sc.close();
    }
}


Measured memory_bytes: 26280
from collections import deque

n,q=map(int,input().split())

qs = [deque() for _ in range(n)]

for _ in range(q):
	op = list(map(int,input().split()))
	que = qs[op[1]]
	if op[0] == 0:
		que.append(op[2])
	elif op[0] == 1:
		if len(que)>0:
			x = que.popleft()
			print(x)
			que.appendleft(x)
	else:
		if len(que)>0:
			que.popleft()



Measured memory_bytes: 14540
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;

constexpr size_t    operator""_sz(unsigned long long value) { return value; };
constexpr intmax_t  operator""_im(unsigned long long value) { return value; };
constexpr uintmax_t operator""_um(unsigned long long value) { return value; };
// }}} End

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int r; cin >> r;

    cout << (r * r) << "\n";

    return 0;
}


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

long long int r(long long int x) {
  if (x == 1) {
    return 1;
  }
  else {
    return r(x / 2) * 2 + 1;
  }
}

int main() {
  long long int H;
  cin >> H;
  cout << r(H) <<endl;
}

Measured memory_bytes: 256
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=len([i for i in A if i%2==1])
even=len([i for i in A if i%2==0])

if P==0:
    ans=2**even
    ans_odd=1
    if odd!=0:
        ans_odd=0
        for i in range(odd//2+1):
            ans_odd+=cmb(odd,2*i)
else:
    ans=2**even
    ans_odd=0
    if odd!=0:
        for i in range(odd//2):
            ans_odd+=cmb(odd,2*i+1)
print(ans*ans_odd)

Measured memory_bytes: 3700
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace atbc_115
{
    class Program
    {
        static void Main(string[] args)
        {
            int cnt = 25 - int.Parse(Console.ReadLine());

            string ret = "Christmas";
            for (int i = 0; i < cnt; i++)
            {
                ret += " Eve";
            }

            Console.WriteLine(ret);
        }
    }
}


Measured memory_bytes: 13140
# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

  
a, b = map(int,input().split())
aa = prime_factorize(a)
bb = prime_factorize(b)
ab = list(set(aa) & set(bb))
ab.sort()
print(len(ab)+1)

Measured memory_bytes: 9104
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Mod 998244353
using namespace std;
int fac[1000010],inv[1000010];
int n,m;
int C(int x,int y)
{
	if(x<0||y<0||x-y<0)return 0;
	return (long long)fac[x]*inv[y]%Mod*inv[x-y]%Mod;
}
int fpow(int a,int b)
{
	int ans=1,t=a;
	while(b)
	{
		if(b&1)ans=(long long)ans*t%Mod;
		t=(long long)t*t%Mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	scanf("%d %d",&n,&m);
	fac[0]=1;
	for(int i=1;i<=m;i++)
		fac[i]=(long long)fac[i-1]*i%Mod;
	inv[m]=fpow(fac[m],Mod-2);
	for(int i=m;i>=1;i--)
		inv[i-1]=(long long)inv[i]*i%Mod;
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int j=m-i;
		int t=i-n+1;
		if(i<j||t<0)continue;
		if(i>j){
			ans=(ans+C(m,i))%Mod;
			ans=(ans-C(m,i+t)+Mod)%Mod;
		}
		else{
			ans=(ans+C(m-1,i))%Mod;
			ans=(ans-C(m-1,i+t)+Mod)%Mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 6272
#include<stdio.h>
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a<=b&&a<=c&&b<=c)
	printf("%d %d %d\n",a,b,c);
	else if(b<=a&&b<=c&&a<=c)
	printf("%d %d %d\n",b,a,c);
	else if(c<=a&&c<=b&&a<=b)
	printf("%d %d %d\n",c,a,b);
	else if(a<=c&&a<=b&&c<=b)
	printf("%d %d %d\n",a,c,b);
	else if(b<=c&&b<=a&&c<=a)
	printf("%d %d %d\n",b,c,a);
	else if(c<=b&&c<=a&&b<=a)
	printf("%d %d %d\n",c,b,a);
	return 0;
}


Measured memory_bytes: 2132
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;

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

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main()
{
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	vector<P> query(q);
	for (int i = 0; i < q; i++){
		cin>>query[i].first>>query[i].second;
		// query[i].first--;
		// query[i].second--;
	}
	vector<int> sum(n+1,0);
	for (int i = 1; i < n; i++){
		if(s[i]=='C' && s[i-1]=='A') sum[i+1] = 1;
	}
	for (int i = 1; i <= n; i++){
		sum[i] += sum[i-1];
	}
	for(auto qq: query){
		cout<<sum[qq.second] - sum[qq.first]<<endl;
	}
	return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int N = readInt(r);
        String[] numStrings = r.readLine().split(" ");
        int[] A = new int[N];
        for (int i = 0;i < N;i++) {
            A[i] = Integer.parseInt(numStrings[i]);
        }
//        insertionSort(A, N);
//        bubbleSort(A, N);
        selectionSort(A, N);
    }
    
    public static void insertionSort(int[] A, int N) {
        System.out.println(dump(A, N));
        for (int i = 1;i <= (N - 1);i++) {
            int v = A[i];
            int j = i - 1;
            while (j >= 0 && A[j] > v) {
                A[j + 1] = A[j];
                j--;
            }
            A[j + 1] = v;
            System.out.println(dump(A, N));
        }
    }
    
    public static void bubbleSort(int[] A, int N) {
        int swapCount = 0;
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int j = N - 1;j >= 1;j--) {
                if (A[j] < A[j - 1]) {
                    swapInt(A, j, j - 1);
                    swapCount++;
                    flag = true;
                }
            }
        }
        System.out.println(dump(A, N));
        System.out.println(swapCount);
    }
    
    public static void selectionSort(int[] A, int N) {
        int swapCount = 0;
        for (int i = 0;i < N;i++) {
            int minj = i;
            for (int j = i;j < N;j++) {
                if (A[j] < A[minj]) {
                    minj = j;
                }
            }
            if (A[i] != A[minj]) {
                swapInt(A, i, minj);
                swapCount++;
            }
        }
        System.out.println(dump(A, N));
        System.out.println(swapCount);
    }
    
    public static void swapInt(int[] A, int j, int k) {
        int v = A[j];
        A[j] = A[k];
        A[k] = v;
    }
    
    public static String dump(int[] A, int N) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < N;i++) {
            if (i != 0) {
                builder.append(" ");
            }
            builder.append(A[i]);
        }
        return builder.toString();
    }
    
    public static int readInt(BufferedReader r) throws Exception {
        return Integer.parseInt(r.readLine());
    }
}

Measured memory_bytes: 24164
N = int(raw_input())
CSF = [map(int, raw_input().split()) for _ in range(N-1)]

for i in range(N-1):
    ans = CSF[i][0] + CSF[i][1]
    for j in range(i+1, N-1):
        s, t, u = CSF[j][0], CSF[j][1], CSF[j][2]
        if t < ans:
            n = (ans - t) / u if ((ans - t) % u) == 0 else (ans - t) / u + 1
            ans = s + t + u * n
        else:
            ans = s + t

    print ans

print 0

Measured memory_bytes: 2820
#include<bits/stdc++.h>
using namespace std;
bitset<4919810> s;  
int n,sum;
int main(){
	scanf("%d",&n);s[0]=1;
	for(int i=1,x;i<=n;i++)
		scanf("%d",&x),sum+=x,s|=(s<<x);if(sum%2==1) sum++;
	for(int i=sum/2;i<=sum;i++)
		if(s.test(i)) {printf("%d",i);exit(0);}
}

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

int alpha(char c){
  string u = "abcdefghijklmnopqrstuvwxyz";
  for(int i = 0;i < u.size();i++){
    if(c == u.at(i)){
      return i;
    }
  }
}
int main() {
  string s,t;
  cin >> s >> t;
  vector<int>datas(s.size());
  vector<int>datat(t.size());
  for(int i = 0;i < s.size();i++){
    int c = s.at(i);
    datas.at(i) = alpha(c);
  }
  for(int i = 0;i < t.size();i++){
    int c = t.at(i);
    datat.at(i) = alpha(c);
  }
  sort(datas.begin(),datas.end());sort(datat.begin(),datat.end());
  reverse(datat.begin(),datat.end());
  if(s.size() < t.size()){
    for(int i = 0;i < s.size();i++){
      if(datas.at(i) > datat.at(i)){
        cout << "No" << endl;
        return 0;
      }
      else if(datas.at(i) < datat.at(i)){
        cout << "Yes" << endl;
        return 0;
      }
      else if(i == s.size()-1 && datas.at(i) == datat.at(i)){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  else{
    for(int i = 0;i < t.size();i++){
      if(datas.at(i) > datat.at(i)){
        cout << "No" << endl;
        return 0;
      }
      else if(datas.at(i) < datat.at(i)){
        cout << "Yes" << endl;
        return 0;
      }
      else if(i == t.size()-1 && datas.at(i) == datat.at(i)){
        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 < (int)(n); i++)
#define all(v) v.begin(), v.end()
int main() {
  int N;
  cin >>N;
  vector<int>A(N);
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>A.at(i);
    sum+=A.at(i);
  }
  int sum2=0;
  int kotae=INT_MAX;
  int b=0;
  
  for(int i=0;i<N;i++){
    sum2+=A.at(i);
    kotae=min(kotae,abs(2*sum2-sum));
  } 
  cout<<kotae<<endl;
  return 0;
}

Measured memory_bytes: 256
def examB():
    St = S(); T = S()
    s_asc = ''.join(sorted(St))
    t_desc = ''.join(sorted(T, reverse=True))
    if s_asc < t_desc:
        print('Yes')
    else:
        print('No')


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()


Measured memory_bytes: 3444
n = int(input())
a = list(map(int, input().split()))
c = 10 ** 9 + 7

ans = 0
tmp_val = 0
for i in range(n):
  tmp_val = (tmp_val + a[i]) % c

for i in range(n-1):
  tmp_val = (tmp_val - a[i]) % c
  ans += (tmp_val * a[i]) % c

print(ans % c)


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

const int MAXN = 1 << 19;

int N;
int A[ MAXN * 3 ];
vector< int > dsctz;
map< int, int > dmp;

struct segt {
  long long sum[ MAXN << 2 ];
  int cnt[ MAXN << 2 ];
  void pull( int t ) {
    sum[ t ] = sum[ t << 1 ] + sum[ t << 1 | 1 ];
    cnt[ t ] = cnt[ t << 1 ] + cnt[ t << 1 | 1 ];
  }
  void modify( int t, int lb, int rb, int k, int v ) {
    if( lb + 1 == rb ) {
      sum[ t ] += v * dsctz[ lb ];
      cnt[ t ] += v;
      return;
    }
    int mid = lb + rb >> 1;
    if( k < mid ) modify( t << 1, lb, mid, k, v );
    else modify( t << 1 | 1, mid, rb, k, v );
    pull( t );
  }
  long long dfs_max( int t, int lb, int rb, int k ) {
    if( lb + 1 == rb ) {
      return 1LL * dsctz[ lb ] * k;
    }
    int mid = lb + rb >> 1;
    if( cnt[ t << 1 | 1 ] >= k ) return dfs_max( t << 1 | 1, mid, rb, k );
    return dfs_max( t << 1, lb, mid, k - cnt[ t << 1 | 1 ] ) + sum[ t << 1 | 1 ];
  }
  long long dfs_min( int t, int lb, int rb, int k ) {
    if( lb + 1 == rb ) {
      return 1LL * dsctz[ lb ] * k;
    }
    int mid = lb + rb >> 1;
    if( cnt[ t << 1 ] >= k ) return dfs_min( t << 1, lb, mid, k );
    return sum[ t << 1 ] + dfs_min( t << 1 | 1, mid, rb, k - cnt[ t << 1 ] );
  }
} root[ 2 ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < 3 * N; ++i ) {
    cin >> A[ i ];
    dsctz.emplace_back( A[ i ] );
  }
  sort( dsctz.begin(), dsctz.end() );
  dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() );
  for( int i = 0; i < dsctz.size(); ++i ) {
    dmp[ dsctz[ i ] ] = i;
  }
  for( int i = 0; i < N; ++i ) {
    root[ 0 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], 1 );
  }
  for( int i = 3 * N - 1; i >= N; --i ) {
    root[ 1 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], 1 );
  }
  long long ans = root[ 0 ].dfs_max( 1, 0, dsctz.size(), N ) - root[ 1 ].dfs_min( 1, 0, dsctz.size(), N );
  for( int i = N; i < 2 * N; ++i ) {
    root[ 0 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], 1 );
    root[ 1 ].modify( 1, 0, dsctz.size(), dmp[ A[ i ] ], -1 );
    ans = max( ans, root[ 0 ].dfs_max( 1, 0, dsctz.size(), N ) - root[ 1 ].dfs_min( 1, 0, dsctz.size(), N ) );
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 50288
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<(S)<<endl
#define ck(n,a,b) (a<=(n)&&(n)<b)
using namespace std;

int main(){
	int H,W;
	int dx[2]={1,0};
	int dy[2]={0,1};
	cin>>H>>W;
	char A[9][9];
	int ansc=0;
	REP(i,0,H) REP(j,0,W) {
		cin>>A[i][j];
		if(A[i][j]=='#') ansc++;
	}
	stack<pair<int,int>> st;
	stack<int> cnt;
	st.push({0,0});
	cnt.push(1);
	bool flag=false;
	while(!st.empty()){
		int x=st.top().first,y=st.top().second;
		int c=cnt.top();
		cnt.pop();
		st.pop();
		if(x==W-1&&y==H-1) {
			if(ansc==c){
				flag=true;
				break;
			}
		}
		REP(i,0,2){
			int nx=x+dx[i],ny=y+dy[i];
			if(!ck(nx,0,W)||!ck(ny,0,H)) continue;
			if(A[ny][nx]=='#'){
				st.push({nx,ny});
				cnt.push(c+1);
			}
		}
	}
	p(flag?"Possible":"Impossible");
	return 0;
}


Measured memory_bytes: 384
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
l, r = 0, n
while r - l > 1:
    mid = (l + r) // 2
    cnt = 0
    for i in range(n):
        if i < p - 1 or i >= mid + 1:
            cnt += m
        else:
            cnt += a[mid] + m - a[i]
    if mid <= p - 1 or (a[mid] + m >= a[p - 1] and cnt >= m * v):
        l = mid
    else:
        r = mid
print(r)

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    ll n,p;
    ll tmp;
    ll ans = 1;
    Scll2(n,p);
    tmp = p;

    for( ll k = 2; k * k <= tmp; k++ ){
        p = tmp;
        for( int i = 1; p % k == 0; i++ ){
            if( i == n ){
                ans = k;
            }
            p /= k;
        }
    }

    if( n == 1 ) ans = p;
    printf("%llu\n", ans);

    return 0;
}



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

int a, b, c;

int main()
{
	cin >> a >> b >> c;
	if(a == b and b != c)
		cout << "Yes\n";
	else if(a == c and b != c)
		cout << "Yes\n";
	else if(c == b and b != a)
		cout << "Yes\n";
	else
		cout << "No\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vi adj[2222];
int a[2222];
int sub[2222];

void prep(int u, int p=-1)
{
	sub[u]=a[u];
	for(int v:adj[u])
	{
		if(v==p) continue;
		prep(v,u);
		sub[u]+=sub[v];
	}
}

int mx[2222];
int mn[2222];
int h[2222];
void dfs(int u, int p=-1)
{
	mx[u]=mn[u]=0;
	vector<ii> vec;
	for(int v:adj[u])
	{
		if(v==p) continue;
		h[v]=h[u]+1;
		dfs(v,u);
		mx[u]+=mx[v]+sub[v];
		vec.pb({mn[v]+sub[v],mx[v]+sub[v]});
	}
	if(vec.empty())
	{
		mn[u]=mx[u];
	}
	else
	{
		sort(vec.begin(),vec.end());
		int sum=0;
		for(int i=0;i<vec.size();i++) sum+=vec[i].fi;
		int ans=0;
		if(sum%2==1) ans=1;
		int diff=vec.back().fi;
		for(int i=0;i+1<vec.size();i++)
		{
			diff-=vec[i].se;
		}
		if(diff>0) ans=max(ans,diff);
		mn[u]=ans;
	}
	//cerr<<u<<' '<<mn[u]<<' '<<mx[u]<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); 
	int n; cin>>n;
	string s; cin>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='1') a[i]=1;
	}
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	int ans=int(1e9);
	for(int i=0;i<n;i++)
	{
		h[i]=0;
		prep(i,-1);
		dfs(i,-1);
		if(mn[i]==0)
		{
			int sum=0;
			for(int j=0;j<n;j++)
			{
				if(a[j]) sum+=h[j];
			}
			ans=min(ans,sum/2);
		}
	}
	if(ans>=int(1e9)) ans=-1;
	cout<<ans<<'\n';
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, A[112345];
LL ans;

int main()
{
	in >> N;
	rep(i, N) { in >> A[i]; }

	std::sort(A, A + N);
	LL cou = 1;
	rep(i, N)
	{
		if (A[i] == A[i + 1]) { ++cou; }
		else
		{
			if (cou % 2LL == 1LL) { ++ans; }
			cou = 1;
		}
	}

	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long int ll;
#define MAX_N 100001
int dp[MAX_N];

void init(){
	rep(i,MAX_N){
		dp[i] = -1;
	}
	dp[0] = 0;
	dp[1] = 1;
}

int recMin(int n){
	if( n == 0) return 0;
	if( n == 1) return 1;
	if( dp[n] != -1){
		return  dp[n];
	}
	int ans = MAX_N;
	int power6 = 6;
	int temp;
	while(power6 <= n){
		temp = recMin(n-power6) + 1;
		ans = min(ans,temp);
		power6 *= 6;
	}
	int power9 = 9;
	while(power9 <= n){
		temp = recMin(n-power9) + 1;
		ans = min(ans,temp);
		power9 *= 9;
	}
	temp = recMin(n-1) + 1;
	ans = min(ans,temp);
	dp[n] = ans;
	return ans;
}

int main()
{
	init();
	int n;
	cin>>n;
	rep(i,n){
		int temp = recMin(i);
		//cout<<i<<" : "<<recMin(i)<<endl;
	}
	cout<<recMin(n)<<endl;
	return 0;
}



Measured memory_bytes: 640
<?PHP
$ans = fgets(STDIN);
$aaa = fgets(STDIN);
$heights = explode(" ", $aaa);
$array = explode(" ", $ans);
$amount=$array[0];
$kick_power=$array[1];
$dps=[];

foreach (range(0, $ans-1) as $index) {
	$dps[$index] = INF;
	if($index===0){
		$dps[0]=0;
		continue;
	}
	$dps[$index]=$dps[$index-1]+abs($heights[$index]-$heights[$index-1]);

	foreach (range(1, $kick_power) as $i) {
		if($index>=$i){
			if ($dps[$index]> abs($dps[$index - $i] + abs($heights[$index] - $heights[$index - $i]))){$dps[$index]=abs($dps[$index - $i] + abs($heights[$index] - $heights[$index - $i]));}
		}

	}
}

echo end($dps);





Measured memory_bytes: 23028
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

const ll MOD=1e9+7;

ll ad(ll x,ll y=0){
  return (x+y)%MOD;
}

ll mlt(ll x,ll y=1){
  return (x*y)%MOD;
}

ll pwr(ll x,ll y){
  ll pw[32]={},w=1;
  pw[0]=x;
  fr(i,31) pw[i+1]=mlt(pw[i],pw[i]);
  fr(i,32){
    w=mlt(w,1+(y%2)*(pw[i]-1));
    y/=2;
  }
  return w;
}

ll inv(ll x){
  return pwr(x,MOD-2);
}

ll fc[1010]={1};
ll fct(ll x){
  if(fc[x]==0) fc[x]=mlt(x,fct(x-1));
  return fc[x];
}

ll ifc[1010]={1};
ll ifct(ll x){
  if(ifc[x]==0) ifc[x]=inv(fct(x));
  return ifc[x];
}

ll Bn[1010]={0};
ll bn(ll x){
  if(x>0&&Bn[x]==0) Bn[x]=ad(1,mlt(x,bn(x-1)));
  return Bn[x];
}

int main(){
  ll n,num=1,dp[1010][2][1010]={},dpc[1010]={},kari;
  bool f[1010];
  string s;
  cin>>n>>s;
  if(n==1&&s=="-"){
    cout<<(MOD+1)/2<<" "<<0<<" "<<(MOD+1)/2<<endl;
    return 0;
  }
  int q=0,r=n;
  n=-1;
  if(s[q]=='-') q++;
  if(s[q]=='-'){q++;n++;num++;}
  if(s[q]=='-'){cout<<"0 0 0"<<endl;return 0;}
  for(int i=q;i<r;i++){
    if(s[i]=='X'){
      if(num==0){cout<<"0 0 0"<<endl;return 0;}
      if(n>=0) f[n]=num-1;
      n++;num=0;
    }
    else{
      if(num>1){cout<<"0 0 0"<<endl;return 0;}
      num++;
    }
  }
  if(num==2) f[n++]=1;
  dpc[0]=1;
  fr(i,n){
    if(f[i]){
      fr(j,2){
        fr(k,2*n+2){
          kari=inv(k*k+3*k+2);
          dp[i+1][j][0]=ad(dp[i+1][j][0],mlt(dp[i][j][k],kari));
          dp[i+1][j][1]=ad(dp[i+1][j][1],mlt(dp[i][j][k],MOD-kari));
        }
      }
      dp[i+1][1][0]=ad(dp[i+1][1][0],dpc[i]);
      dp[i+1][1][1]=ad(dp[i+1][1][1],MOD-dpc[i]);
    }
    else{
      fr(j,2){
        fr(k,2*n+2){
          kari=inv(k+1);
          dp[i+1][j][0]=ad(dp[i+1][j][0],mlt(dp[i][j][k],kari));
          dp[i+1][j][1]=ad(dp[i+1][j][1],mlt(dp[i][j][k],MOD-kari));
          dp[i+1][j][k+2]=ad(dp[i+1][j][k+2],mlt(dp[i][j][k],inv(k*k+3*k+2)));
        }
      }
      dp[i+1][1][1]=ad(dp[i+1][1][1],dpc[i]);
      dp[i+1][1][0]=ad(dp[i+1][1][0],MOD-dpc[i]);
      dpc[i+1]=ad(dpc[i+1],dpc[i]);
    }
  }
  ll ans[3]={};
  fr(j,2){
    fr(k,2*n+2){
      ans[j]=ad(ans[j],mlt(dp[n][j][k],fct(k)));
      ans[j+1]=ad(ans[j+1],mlt(dp[n][j][k],MOD-ad(fct(k),bn(k))));
    }
  }
  kari=(MOD+1)/2;
  ans[0]=ad(ans[0],mlt(dpc[n],kari));
  ans[2]=ad(ans[2],mlt(dpc[n],MOD-kari));
  cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<endl;
}

Measured memory_bytes: 16256
#include<bits/stdc++.h>
using namespace std;
int k;
set<string> s;
vector<string> v;
void dfs(string x){
	if(s.find(x)!=s.end())return ;
	s.insert(x);
	v.push_back(x);
	if(x.size()==10)return ;
	if(x[x.size()-1]=='0')dfs(x+'1');
	else if(x[x.size()-1]=='9')dfs(x+'8');
	else{
		dfs(x+(char)(x[x.size()-1]-1));
		dfs(x+(char)(x[x.size()-1]+1));
	}
	dfs(x+x[x.size()-1]);
}
inline bool cmp(string k1,string k2){
	if(k1.size()<k2.size())return true;
	else if(k1.size()>k2.size())return false;
	else if(k1<=k2)return true;
	else return false;
}
int main(){
	cin>>k;
	for(char c='1';c<='9';c++){
		string t="";
		t+=c;
		dfs(t);
	}
	sort(v.begin(),v.end(),cmp);
	cout<<v[k-1]<<endl;
	return 0;
}

Measured memory_bytes: 25096
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define int ll
const ll mod = 998244353;
const ll nmax=1000003;
#define int ll
int m, d, ans;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>m>>d;
    for(int i=1; i<=m; i++){
		for(int j=1; j<=d; j++){
			int x=j/10, y=j%10;
			if(x>=2 && y>=2 && x*y==i) ans++;
		}
	}
	cout<<ans;
}


Measured memory_bytes: 256
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 61;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

    int n, l;
    cin >> n >> l;

    vector<int> apple(n);
    iota(apple.begin(), apple.end(), l);

    int ab = (1 << 30);
    int ans = 0;
    int sum = accumulate(apple.begin(), apple.end(), 0);
    for (int i = 0; i < n; i++) {
        if (abs(apple[i]) < ab) {
            ab = abs(apple[i]);
            ans = sum - apple[i];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3584
n = int(input())
A = []
for i in range(n):
    i = list(map(str,input()))
    i.sort()
    A.append(i)

A.sort()
tmp = A[0]
cnt = 0
ans = 0
for i in range(1,n):
    if tmp == A[i]:
        cnt += 1
    else:
        tmp = A[i]
        for j in range(cnt):
            ans += cnt
            cnt -= 1
if cnt >= 1:
    for j in range(cnt):
        ans += cnt
        cnt -= 1

print(ans)

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

const int mod = 1e9+7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

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

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

// auto mod int
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint sum(ll l, ll r) {
    return (l + r) * (r - l + 1) / 2;
}

mint sum2(ll l, ll r) {
    --l;
    ll s1 = l * (l + 1) * (2 * l + 1) / 6;
    ll s2 = r * (r + 1) * (2 * r + 1) / 6;
    return s2 - s1;
}

int main(){
    int n, k;
    cin >> n >> k;
    mint ans = -(sum2(k, n+1)) + sum(k, n+1) * (n+1) + (n-k+2);
    cout << ans << endl;
    return 0;
}


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

using namespace std;
int n;
int solve(int n)
{
    if(n == 0)
        return 0;
    if(n < 6)
        return 1 + solve(n-1);
    int cur = 1;
    while(cur*6 <= n)
        cur *= 6;
    int curr = 1;
    while(curr * 9 <= n)
        curr *= 9;
    return min(1 + solve(n-cur),1 + solve(n-curr));
}
int main()
{
    cin >> n;
    cout << solve(n);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#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

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

///////////////////////////////////////////////////////////////////////////



int main(){
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    int i = 0;

    while(i < n){
	int j = s.find("ABC",i);
	if(j == -1)break;
	ans++;
	i  = j+1;
    }
    P(ans);
    return  0;
}


Measured memory_bytes: 256
/*
the top of the losers
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    Lcm(a,b)  ((a*b)/(__gcd(a,b)))
#define    X            real()
#define    Y            imag()
#define    clr(v,d)      memset( v, d ,sizeof(v))
#define   angle(n)      atan2((n.imag()),(n.real()))
#define   vec(a,b)       ((b)-(a))
#define   length(a)      hypot( (a.imag()),(a.real()) )
#define   normalize(a)      (a)/(length(a))
#define    dp(a,b)          (((conj(a))*(b)).real())
#define    cp(a,b)          (((conj(a))*(b)).imag())
#define    lengthsqrt(a)       dp(a,a)
#define    rotate0( a,ang)    ((a)*exp( point(0,ang) ))
#define    rotateA(about,p,ang)   (rotate0(vec(about,p),ang)+about)
#define    lcm(a,b)                ((a*b)/(__gcd(a,b)))
#define    reflection0(m,v)         (conj((v)/(m))*(m))
#define     reflectionA(m,v,p0)     (conj( (vec(p0,v))/(vec(p0,m)) ) * (vec(p0,m)) ) + p0
#define     same(p1,p2)               ( dp(  vec(p1,p2),vec(p1,p2)) < eps )
#define     point                    complex<double>
#define     point        complex<double>
#define    cp(a,b)          (((conj(a))*(b)).imag())
#define    PI  acos(-1)
typedef  long long     ll ;
typedef  unsigned long long     ull ;
const double eps= (1e-9);
using namespace std;
using namespace __gnu_pbds;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
int countNumBit1(int mask) {int ret=0; while (mask) 	{mask &= (mask-1);++ret;	}return ret;}
void GO(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

int main(){
    int a,b;
    cin>>a>>b;
    if(a>=1&&a<=9&&b>=1&&b<=9){
        cout<<a*b<<endl;
    }
    else{
        cout<<"-1\n";
    }
}






Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define drep(i,n) for(int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for (int i = s; i < t; i++)
#define rng(a) a.begin(),a.end()
typedef long long ll;

using namespace std;



int main() {
    int n;
    cin>>n;
    vector<int>p(n);
    rep(i,n)cin>>p[i]; 
    int cnt = 0;
    srep(i,1,n-1){
        if(p[i]>min(p[i-1],p[i+1]) && p[i]<max(p[i-1],p[i+1]))cnt++;
    }
    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 3612
import java.util.Scanner;

public class Main {

    static long dp[][];

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

        int N = sc.nextInt();
        int W = sc.nextInt();

        long[] wt = new long[N];
        long[] val = new long[N];
        dp = new long[W+1][N+1];

        for (int i = 0; i <= W; i++) {
            for (int j = 0; j <= N; j++) {
                dp[i][j] = -1;
            }
        }

        for (int i = 0; i < N;i++) {
            wt[i] = sc.nextInt();
            val[i] = sc.nextInt();
        }
        System.out.println(knapsack(wt, val, W, N));
    }

    public static long knapsack(long[] wt, long[] val, int W, int N) {
        if (N == 0 || W == 0) {
            return 0;
        }

        if (dp[W][N] != -1) {
            return dp[W][N];
        }

        if (wt[N-1] <= W) {
            dp[W][N] = Math.max(val[N-1] + knapsack(wt, val, (int) (W - wt[N-1]), N-1), knapsack(wt, val, W, N-1));
        } else {
            dp[W][N] = knapsack(wt, val, W, N-1);
        }
        return dp[W][N];
    }

}

Measured memory_bytes: 129328
import fractions
from functools import reduce
def main():
    n,x = map(int, input().split())
    X = list(map(int,input().split()))

    array = []
    for i in range(len(X)):
        array.append(abs(X[i]-x))
    reduce(lambda a,b: a-b, [1,2,3])
    gcd1 = reduce(lambda a,b: fractions.gcd(a,b), array)
    print(gcd1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 88852
#include<bits/stdc++.h>
    using namespace std;
    #define rep(i,b) for(i=0;i<b;++i)
    #define repp(i,a,b) for(i=a;i<b;++i)
    #define per(i,n) for(i=n-1;i>=0;i--)
    #define endl "\n"
    #define pb push_back
    typedef long long int lli;
    const lli mod=1000000007;
    typedef vector<lli> vi;
    typedef pair<lli,lli> pi;
    #define mp make_pair
    #define pb push_back
    int main(){
       //ios_base::sync_with_stdio(false);
       //cin.tie(NULL);
        lli n,t,i,k,j,f,g,m,a,b,c;
        string s;
        vi v;
        map<lli,lli> mm;
        map<lli,lli> :: iterator it;
        cin>>n;
        lli x[n];
        lli y[n];
        lli h[n];
        rep(i,n){
            cin>>x[i]>>y[i]>>h[i];
            if(h[i]>0){
                a=x[i];
                b=y[i];
                c=h[i];
            }
        }
        f=0;
            rep(i,101){
                rep(j,101){
                    g=c+abs(i-a)+abs(j-b);
                    f=0;
                    rep(k,n){
                        if(max(g-abs(i-x[k])-abs(j-y[k]),(lli)0)!=h[k]){
                            f=1;
                            break;
                        }
                    }
                    if(f==0){
                        cout<<i<<" "<<j<<" "<<g<<endl;
                        return 0;
                    }
                }
            }



        return 0;
    }



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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c; cin >> a >> b >> c;
    cout << c << " " << a << " " << b << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>


using namespace std;

int main(int argc, char *argv[])
{
	int s, w;
	cin >> s >> w;

	if (w >= s)
		cout << "unsafe" << endl;
	else
		cout << "safe" << endl;


	return 0;
}

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

int main() 
{
    int n, m;
    cin >> n >> m;
    vector<int> vl(m);
    vector<int> vr(m);
    for (int i=0; i<m; i++)
    {
        cin >> vl[i];
        cin >> vr[i];
    }
    int min = *min_element(vr.begin(), vr.end());
    int max = *max_element(vl.begin(), vl.end());
    cout << (min - max +1 >0?min-max+1:0);
    return 0;
}

Measured memory_bytes: 1024
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, k = MI()
    a = LI()
    ans = -(-(n-1) // (k-1))
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 20624
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] str;
        int count = 0;
        str = s.split("");
        if (!str[0].equals("A")) {
            System.out.println("WA");
            System.exit(0);
        }
        for (int i = 2; i <= str.length - 2; i++) {
            if (Character.isLowerCase(s.charAt(i))) {
            } else {
                if (str[i].equals("C")) {
                    count++;
                } else {
                    System.out.println("WA");
                    System.exit(0);
                }
            }
        }
        if (Character.isLowerCase(s.charAt(1))) {
        } else {
            System.out.println("WA");
            System.exit(0);
        }
        if (Character.isLowerCase(s.charAt(str.length - 1)) && count == 1) {
            System.out.println("AC");
        } else {
            System.out.println("WA");
        }
    }
}

Measured memory_bytes: 23892
#include <iostream>

using namespace std;

long long int MAX = 100000000;

bool flags[12];
long long int N, M, X, sum[12];
long long int C[12], A[12][12];


long long int dfs(int n, bool flag){
  long long int ans = 0;
  flags[n] = flag;
  if(n == N-1){
    for(int j=0; j<M; j++) sum[j] = 0;
    for(int i=0; i<N; i++){
      if(flags[i]){
        ans += C[i];
        for(int j=0; j<M; j++){
          sum[j] += A[i][j];
        }
      }
    }
    for(int j=0; j<M; j++){
      if(sum[j] < X) return MAX;
    }
    return ans;
  }
  long long int ans1 = dfs(n+1, true);
  long long int ans2 = dfs(n+1, false);
  if(ans1 < ans2) return ans1;
  return ans2;
}

int main(){
  cin >> N >> M >> X;
  for(int i=0; i<N; i++){
    cin >> C[i];
    for(int j=0; j<M; j++) cin >> A[i][j];
  }
  long long int ans1 = dfs(0, true);
  long long int ans2 = dfs(0, false);
  if(ans1 == MAX && ans2 == MAX) cout << -1 << endl;
  else if(ans1 < ans2) cout << ans1 << endl;
  else cout << ans2 << endl;

  return 0;
}


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

int N, M;
vector<int> G[50];
bool d[50][50];
bool v[50];

void dfs(int s) {
    v[s] = true;
    for (int i = 0; i < G[s].size(); i++) {
        int to = G[s][i];
        if (!d[s][to] && !v[to]) {
            dfs(to);
        }
    }
}

int main() {
    cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        A[i] = a;
        B[i] = b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int ans = 0;
    for (int i = 0; i < M; i++) {
        fill(d[0], d[50], false);
        fill(v, v + 50, false);
        int a = A[i], b = B[i];
        d[a][b] = true;
        d[b][a] = true;
        dfs(0);
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (v[i]) cnt++;
        }
        if (cnt != N) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007 
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	double a,b;
	cin >> a >> b;
	cout.precision(19);
	cout << a/b << endl;
}


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

int main(){
  int a;
  int b;
  cin>>a>>b;
  
  if (a%2 == 0 || b%2 == 0) {
    cout<<"Even"<<endl;
  }
  
  else {
    cout<<"Odd"<<endl;
  }
}

Measured memory_bytes: 256
/*#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>*/
#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
typedef vector<P> vP;
const ll mod = 1e9 + 7;
ll dx[4] = {1,0,-1,0};
ll dy[4] = {0,1,0,-1};

int main(){
    ll n=0;
    vi v(3),w(3);
    vvll v1(3,vll(3,0));
    vi count(4,0);
    rep(i,3) {
        cin >> v[i] >> w[i];
        count[--v[i]]++;
        count[--w[i]]++;
    }
    rep(i,4){
        if(count[i] > 2){
            cout << "NO\n";
            return 0;
        }
        if(count[i] == 0){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    return 0;
}  


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

const int MAX_W = 5e5;
const int INF = 1e9;

int main(){
    int N, W; cin >> N >> W;
    vector<ll> w(N), v(N);
    for (int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];
    }

    ll dp[MAX_W]; // dp[i] := 重さi以下で最大の価値を得る

    for(int i = 0; i <= W; i++) dp[i] = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = W ; j >= 0; j--)
        {
            if(j - w[i] >= 0) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[W] << endl;
    
    
}

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

string s;
int mn, mx, c[3];
int main() {
	cin >> s;
	for(int i=0; s[i]; i++) c[s[i]-'a']++;
	mn = min(c[0], min(c[1], c[2]));
	mx = max(c[0], max(c[1], c[2]));
	cout << (mx-mn<=1 ? "YES" : "NO");
	return 0;
}

Measured memory_bytes: 512