akhauriyash/Code-Regression huggingface dataset:
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	llint i,n,ans=0;cin>>n;
	array<llint,6>dp={0,-inf,-inf,-inf,-inf,-inf};
	
	//前に選ない -0 -1 -2
	//前に選んだ -0 -1 -2
	
	for(i=0;i<n;i++){
		llint a;cin>>a;
		array<llint,6>ep;
		ep[0]=dp[3];
		ep[1]=max(dp[0],dp[4]);
		ep[2]=max(dp[1],dp[5]);
		ep[3]=dp[0]+a;
		ep[4]=dp[1]+a;
		ep[5]=dp[2]+a;
		dp=ep;
	}
	if(n%2==1){cout<<max(dp[1],dp[5])<<endl;}
	else{cout<<max(dp[0],dp[4])<<endl;}
	return 0;
}


Measured memory_bytes: 3664
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	int ls=s.size(),lt=t.size();
	int sum=0,ans=100000,x;
	for(int i=0;i<=ls-lt;i++)
	{
		sum=0,x=i;
		for(int j=0;j<lt;j++)
		{
			if(s[x]!=t[j]) sum++;
			x++;
		}
		ans=min(ans,sum);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3632
import math
X,Y=map(int,input().split())
#B,W=map(int,input().split())
#N=int(input())

flag=False

for i in range(X+1):
    if i*2+((X-i)*4)==Y:
        flag=True

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9112
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & (-x))


using namespace std;

string a, b;
string sol;

int main() {
    //fstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin >> a >> b;
    int n = a.size(), m = b.size();
    for(i = 0; i < n; i++)
        sol.push_back('z');
    bool ans = 0;
    for(i = 0; i <= n - m; i++) {
        string cur = a;
        bool flag = 1;
        for(j = i; j < i + m && flag; j++) {
           if(a[j] == '?') {
               cur[j] = b[j - i];
           }
           else if(a[j] != b[j - i])
               flag = 0;
        }
        if(flag == 1) {
           ans = 1;
           for(j = 0; j < n; j++) {
               if(cur[j] == '?')
                   cur[j] = 'a';
           }
           if(sol > cur)
               sol = cur;
        }
    }
    if(ans == 0)
        cout << "UNRESTORABLE";
    else
        cout << sol;
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        scanner.nextLine();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < count; i++){
            list.add(scanner.nextInt());
        }
        if(list.stream().distinct().collect(Collectors.toList()).size() == list.size()){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


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

namespace AtCoder
{
	class Program
	{
		public static void Main()
		{
			var intArray = IO.ReadLongArray();
			var N = intArray[0];
			var A = intArray[1];
			var B = intArray[2];
			var sum = A + B;
			IO.Write((sum > 0) ? (A * (N / sum)) + Math.Min(A , N % sum) : 0L);
		}
	}

	public static class IO
	{
		public static string   Read()								 { return Console.ReadLine(); }
		public static string[] ReadArray(char iSplitter = ' ')		 { return Read().Split(iSplitter); }
		public static int	   ReadInt()							 { return int.Parse(Read()); }
		public static int[]	   ReadIntArray(char iSplitter = ' ')	 { return ReadArray().Select(iText => int.Parse(iText)).ToArray(); }
		public static long	   ReadLong()							 { return int.Parse(Read()); }
		public static long[]   ReadLongArray(char iSplitter = ' ')	 { return ReadArray().Select(iText => long.Parse(iText)).ToArray(); }
		public static double   ReadDouble()							 { return double.Parse(Read()); }
		public static double[] ReadDoubleArray(char iSplitter = ' ') { return ReadArray().Select(iText => double.Parse(iText)).ToArray(); }
		public static char[]   ReadCharArray()						 { return Read().ToCharArray(); }

		public static void Write(string iValue)									   { Console.WriteLine(iValue); }
		public static void Write(int iValue)									   { Console.WriteLine(iValue); }
		public static void Write(IEnumerable<int> iValue , string iJoinWord = " ") { Console.WriteLine(string.Join(iJoinWord , iValue)); }
		public static void Write(long iValue)									   { Console.WriteLine(iValue); }
		public static void Write(double iValue)									   { Console.WriteLine(iValue); }
		public static void Write(decimal iValue)								   { Console.WriteLine(iValue); }
		public static void Write(bool iValue)									   { Console.WriteLine(iValue ? "Yes" : "No"); }
	}

	public static class Util
	{
		public static long Gcd(long i0 , long i1) { return (i0 > i1) ? _Gcd(i0 , i1) : _Gcd(i1 , i0); }
		public static long Lcm(long i0 , long i1) { return (i0 * i1) / Gcd(i0 , i1); }
		public static long ModPow(long iBaseNumber , long iPow , long iModNumber)
		{
			var num = 1L;
			while(iPow != 0)
			{
				if((iPow & 0x1) != 0)
				{
					num = (num * iBaseNumber) % iModNumber;
				}
				iBaseNumber = (iBaseNumber * iBaseNumber) % iModNumber;
				iPow >>= 1;
			}
			return num;
		}
		public static long CombinationNum(int iLeftNumber , int iRightNumber)
		{
			if(iRightNumber == 0) { return 1; }
			if(iLeftNumber == 0)  { return 0; }
			return iLeftNumber * CombinationNum(iLeftNumber - 1 , iRightNumber - 1) / iRightNumber;
		}

		private static long _Gcd(long i0 , long i1)	{ return (i1 == 0) ? i0 : _Gcd(i1 , i0 % i1); }
	}
}


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

vector<int> comp(100001);

int find_comp(int a){
	int compa=comp[a];
	while (compa != comp[compa]) compa=comp[compa];
	comp[a]=compa;
	return compa;
}

int main(){
	int n,m;
	cin >> n >> m;
	int cnt=n;
	for (int i=1; i<=n; ++i) comp[i]=i;
	for (int i=0; i<m; ++i){
		int x,y,z;
		cin >> x >> y >> z;
		int a=find_comp(x),b=find_comp(y);
		if (a != b){
			comp[b]=a;
			--cnt;
		}
	}
	cout << cnt;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

int main()
{

    int s,w;
    cin>>s>>w;
    if(w>=s)
    {
        cout<<"unsafe";
    }
    else
    {
        cout<<"safe";
    }
    
}


Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define sym cout<<"-----------"<<endl;
#define ll long long
#define P pair<int,int>
#define mk make_pair
#define en endl
#define RE return 0
#define int ll

vector<int> G[200005];

signed main(){
  int n,m,q;
  cin>>n>>m>>q;
  
  for(int i=0; i<m; i++){
    int l,r;
    cin>>l>>r;
    G[l].push_back(r);
  }
  for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());
  for(int i=0; i<q; i++){
    int l,r;
    cin>>l>>r;
    int ans=0;
    for(int j=l; j<=r; j++){
      int n=upper_bound(G[j].begin(), G[j].end(), r)-G[j].begin();
      ans+=n;
    }
    cout<<ans<<en;
  }
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
 
ifstream in ("test.in" );
ofstream out("test.out");
 
const int DIM = 2e5 + 5;
 
int dst[2][DIM];
vector<int> edg[DIM];
 
void dfs(int k, int x, int f) {
    dst[k][x] = dst[k][f] + 1;
    
    for (int y : edg[x])
        if (y != f)
            dfs(k, y, x);
    
    return;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    
    int n;
    cin >> n;
    
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    
    dst[0][0] = dst[1][0] = -1;
    dfs(0, 1, 0); dfs(1, n, 0);
    
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += (dst[0][i] <= dst[1][i]);
    
    cout << ((ans > n / 2) ? "Fennec" : "Snuke" );
    return 0;
}

Measured memory_bytes: 14336
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if (a + b == c || b + c == a || c + a == b) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 9808
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
vector<string> st;
vector<string> p = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
int n;

void dfs(int idx,int m,string now){
        if(idx == n) st.push_back(now);
        else{
         rep(j,m+2){
                    if(j==m+1) dfs(idx+1,m+1,now+p[j]);
                        else dfs(idx+1,m,now+p[j]);
                }
        }

}

        

int main(){
        cin >> n;
        
        dfs(1,0,"a");  
        
        rep(i,(int)st.size()){                              
                              cout << st.at(i) << endl;
        }
        
        
        return 0;
}




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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define INF (1<<29)

int main() {
	int n, m, s, g, V, P;
	int mincost[20][20];
	
	cin >> n >> m;
	
	REP(i, n) REP(j, n) {
		if (i == j) mincost[i][j] = 0;
		else mincost[i][j] = INF;
	}
	
	REP(i, m) {
		int a, b, c, d;
		scanf("%d,%d,%d,%d", &a, &b, &c, &d);
		a--; b--;
		mincost[a][b] = c;
		mincost[b][a] = d;
	}
	
	scanf("%d,%d,%d,%d", &s, &g, &V, &P);
	s--; g--;
	
	REP(k, n) REP(i, n) REP(j, n) {
		if (mincost[i][j] > mincost[i][k] + mincost[k][j])
			mincost[i][j] = mincost[i][k] + mincost[k][j];
	}
	
	cout << V - P - mincost[s][g] - mincost[g][s] << endl;
	return 0;
}

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

#define all(x) begin(x), end(x)
#define cina(s, n, a) for(int quer = s; quer < n; quer++) cin >> a[quer]
#define mod(a, b) (abs(b) + (a % abs(b))) % abs(b)
#define setp(x) fixed << setprecision(x)

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll MOD = 1e9 + 7;
const int N = 200500; // are you sure?
void solve(){
    map<ll, ll> m;
    int n;
    cin >> n;
    vll a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        m[a[i]]++;
    }
    ll ans = 0;
    for(auto &i : m){
        ans += i.second * (i.second - 1) / 2;
    }
    for(int i = 0; i < n; i++){
        ll x = m[a[i]];
        ll tmp = ans;
        ans -= x * (x - 1) / 2;
        ans += (x - 1) * (x - 2) / 2;
        cout << ans << endl;
        ans = tmp;
    }
}

int main(){
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int q = 1;
    //cin >> q;
    for (int i = 1; i <= q; i++) {
        solve();
    }
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f;
const ll mod = 998244353LL;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n, k;
ll a[N];

void solve()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    for (int i = k + 1; i <= n; ++i)
    {
        if (a[i] > a[i - k])
            puts("Yes");
        else
            puts("No");
    }
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

Measured memory_bytes: 5276
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793




int main(){
   int n;
   cin >> n;
   VI a(n), b(n-1);
   rep(i,n)cin >> a.at(i);
   rep(i,n-1){
       b.at(i)=a.at(i+1)-a.at(i);
   }
   int ans=0;
   int w=0;
   rep(i,n-1){
       if(b.at(i)>0 && w==0)w=1;
       else if(b.at(i)<0 && w==0)w=-1;
       else if(b.at(i)==0){
           if(w==0)w==0;
           else if(w==1)w==1;
           else if(w==-1)w=-1;
        }
       else if(b.at(i)>0 && w==-1){
           ans++;
           w=0;
       }
       else if(b.at(i)<0 && w==1){
           ans++;
           w=0;
       }
       else if(b.at(i)>0 && w==1)w==1;
       else if(b.at(i)<0 && w==-1)w==-1;
   }
    cout << ans+1 << endl;
}
       

Measured memory_bytes: 3956
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <complex>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef complex<double> Point;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
  int from, to, cost;
  bool operator < (const edge& e) const { return cost < e.cost; }
  bool operator >(const edge& e) const { return cost > e.cost; }
};
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int main()
{
	int n;
	int cnt = 0;
	cin>>n;
	string s;cin>>s;
	int len = s.size();
	REP(x,n)
	{
		string t;cin>>t;
		for(int i = 0;t.size()>=len+(len-1)*i;i++)
		{
			REP(j,t.size())
			{
				string tmp;
				tmp += t[j];
				FOR(k,1,len)
				{
					int p = j+(i+1)*k;
					if(p>=t.size()) break;
					tmp+=t[p];
				}
				if(tmp==s)
				{
					cnt++;
					goto end;
				}
			}
		}
	end:;
	}
	cout<<cnt<<endl;
	return 0;
}

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

int main(void) {
  string s, t;
  cin >> s >> t;
  
  sort(s.begin(), s.end());
  sort(t.begin(), t.end(), greater<char>());
  
  if (s < t)
    cout << "Yes" << endl;
  else
    cout << "No"  << endl;
  
  return 0;
}

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

int main(void)
{
    string str[7]={"SUN","MON","TUE","WED","THU","FRI","SAT"};
    string s; cin>>s;
    int k;
    for(int i=0;i<7;++i){
        if(s==str[i]) k=i;
    }
    if(k==0) printf("7\n");
    else printf("%d\n",7-k);
    return 0;
}

Measured memory_bytes: 256
// #include C {
#include<cstring>
#include<cassert>
#include<cstdio>
#include<cctype>
#include<cmath>
// }

// #include C++ {
#include<functional>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<list>
#include<map>
#include<set>
// }

using namespace std;
// #typedef {
typedef long long int64;
typedef pair <int, int> PII;
typedef pair <int64, int64> PLL;
// }

// #parameter{
#ifdef DEBUG_MODE

#define TYPE decltype
#define RF(filename) {freopen((filename), "r", stdin);}
#define WF(filename) {freopen((filename), "w", stdout);}
#define DF(filename) {freopen((filename), "w", stderr);}
#define eprintf printf

#else

#define TYPE __typeof
#define RF(filename) {;}
#define WF(filename) {;}
#define DF(filename) {;}
#define eprintf(...)
#define fprintf(...)

#endif

// #define {
#define SZ(a) ((int)(a).size())
#define X first
#define Y second
#define MP make_pair
#define L(x) ((x)<<1)
#define R(x) ((x)<<1 | 1)
#define max3(x, y, z) (max(max((x), (y)), (z)))
#define min3(x, y, z) (min(min((x), (y)), (z)))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(it) (it).begin(), (it).end()
#define FILL(__space, __val) memset(__space, __val, sizeof(__space))
#define MOVE(__spaceTo, __spaceFrom) memmove(__spaceTo, __spaceFrom, sizeof(__spaceTo))
#define UNIQUE(__vector) sort(ALL(__vector)), __vector.resize(unique(ALL(__vector)) - __vector.begin())
#define FOR(it, c) for( TYPE((c).begin()) it = (c).begin(); it != (c).end(); it++)
/////////////////////////////////////////////////////////////
const double PI = acos(-1.0);
const double EPS = 1e-6;

#define MAX_N 505
#define MAX_M 100005
#define MOD (int)(1e9+7)
#define INF ((1 << 30) - 1)
#define BINF ((1LL << 62) - 1LL)
#define NONE -1
#define NIL 0
// }

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

/////////////////////////////////////////////////////////////
int main() {
	RF("input.txt");
//  WF("output.txt");
	DF("err.txt");

	int N, K;
	scanf("%d %d", &N, &K);
	vector <PII> p;
	vector <int> ver, hor;
	for (int k = 0; k < N; k++) {
		int x, y;
		scanf("%d %d", &x, &y);
		p.emplace_back(x, y);
		ver.emplace_back(x);
		hor.emplace_back(y);
	}
	sort(ALL(ver));
	sort(ALL(hor));
	int64 res = BINF;
	for(int a=0;a<N;a++) for(int b=a+1;b<N;b++) for(int c=0;c<N;c++) for(int d=c+1;d<N;d++){
		int lbound = ver[a];
		int rbound = ver[b];
		int bbound = hor[c];
		int tbound = hor[d];
		int count = 0;
		for (int i = 0; i < N; i++) if (lbound <= p[i].X && p[i].X <= rbound && bbound <= p[i].Y && p[i].Y <= tbound)
			count++;
		if (count >= K)
			res = min(res, 1LL * (rbound - lbound) * (tbound - bbound));
	}
	printf("%lld\n", res);
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int n, w;
long long greutate[1000005] = {0}, cost[1000005] = {0};
long long matrice[105][1000005]= {0};
#define L 1e5
long long rez;
void solve();
void read()
{
 cin >> n >> w;

}
void solve()
{
    for(int i = 0; i <= n +2; i++)
        for(int j = 0; j <= L+2 ; j++)
            matrice[i][j] = w + 1;
    matrice[1][1] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        for(int j = 1; j <= L + 1; j++)
        {
            if(j >= y)
            {if(matrice[i][j] < matrice[i][j - y] + x)
                matrice[i + 1][j] = matrice[i][j];
            else matrice[i + 1][j] = matrice[i][j - y] +x;}
            else{
                matrice[i + 1][j] = matrice[i][j];
            }
            if(matrice[i + 1][j] <= w)
                if(j > rez)
                    rez = j;
        }
    }
}
int main()
{
    read();
    solve();
    cout << rez - 1;

}

Measured memory_bytes: 293888
#include<stdio.h>
    long long a[200005],b[200005];
    int n;
    int main(){
        scanf("%d",&n);
        for(int i = 1;i <= n;i++){
            scanf("%lld",&a[i]);
        }
        int l = 1, r = n,flag = 0;
        for(int i = n;i >= 1;i--){
            if(flag == 0) b[l++] = a[i],flag = 1;
            else b[r--] = a[i],flag = 0;
        }
        for(int i = 1;i <= n;i++){
            printf("%lld ",b[i]);
        }
    }

Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define erep(i,a,n) for(int i = a;i<=n;i++)
typedef long long ll;
#define int long long
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define P pair<int,int>
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; }

signed main(){
  int n;
  cin >> n;
  vvint A(n,vint(n-1));
  rep(i,0,n){
    rep(j,0,n-1){
      cin >> A[i][j];
      A[i][j]--;
    }
    reverse(A[i].begin(),A[i].end());
  }
  vector<P> match;
  auto judge = [&](int i){
    if(A[i].size() == 0) return;
    int j = A[i].back();
    if(A[j].size() == 0) return;
    if(A[j].back() == i){
      if(i < j) swap(i,j);
      match.push_back(P(i,j));
    }
  };
  rep(i,0,n){
    judge(i);
  }
  int day = 0;
  while(match.size() > 0){
    day++;
    sort(match.begin(),match.end());
    match.erase(unique(match.begin(),match.end()),match.end());
    vector<P> prevQ;
    swap(prevQ,match);
    for(P p:prevQ){
      int i = p.first;
      int j = p.second;
      A[i].pop_back();
      A[j].pop_back();
    }
    for(P p:prevQ){
      int i = p.first;
      int j = p.second;
      judge(i);
      judge(j);
    }
  }
  rep(i,0,n){
    if(A[i].size() != 0){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << day << endl;
}

Measured memory_bytes: 8192
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
#include <queue>
#include <list>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (d >= abs(a - b) && d >= abs(c - b) || abs(a - c) <= d) cout << "Yes";
	else cout << "No";
}
/*
*/

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (;;) {
            int n = sc.nextInt();
            if(n==0) {
                break;
            }
            boolean f=false;
            int c=0;
            for(int i=0;i<n;i++) {
                int m=sc.nextInt();
                if(m>=2) {
                    f=true;
                }
                if(m==0) {
                    c++;
                }
            }
            System.out.println(f&&n>0?n+1-c:"NA");
        }
    }
}



Measured memory_bytes: 138820
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());
    double z8 = (double) 108 / 100;
    double z10 = (double) 110 / 100;
    for (int i = 0; i <= 1500; i++) {
      if ((int) (i * z8) - i == a && (int) (i * z10) - i == b) {
        pw.println(i);
        return;
      }
    }
    pw.println(-1);
  }
}


Measured memory_bytes: 23636
#include <iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, W; cin >> N >> W;
    int value[N];
    int weight[N];
    REP(n, N) {
        cin >> value[n];
        cin >> weight[n];
    } 

    int dp[110][11000] = {{}};

    REP(n, N) {
        REP(w, W + 1) {
            weight[n] > w ? dp[n + 1][w] = dp[n][w] : dp[n+1][w] = max(dp[n][w], dp[n][w - weight[n]] + value[n]); 
        } 
    }

    cout << dp[N][W] << endl;

    return 0;
}


Measured memory_bytes: 7868
N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
gap = []
for i in range(N):
    tmp = V[i]-C[i]
    if tmp > 0:
        gap.append(tmp)

ans = 0
for i in gap:
    ans += i

print(ans)

Measured memory_bytes: 3064
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())

C = ["s", "r", "p"]
Win = {"s": "r", "r": "p", "p": "s"}
Point = {"r": R, "p": P, "s": S}

Group = [[] for _ in range(K)]
for i in range(len(T)):
    Group[i % K].append(T[i])

res = 0
for g in Group:
    n = len(g)
    DP = [[0 for _ in range(3)] for _ in range(n + 1)]
    for index, tmp in enumerate(C):
        if Win[g[0]] == tmp:
            DP[0][index] += Point[tmp]
    for i in range(n - 1):
        for j, c in enumerate(C):
            p = 0
            if c == Win[g[i + 1]]:
                p = Point[c]
            if j == 0:
                DP[i + 1][j] = max(DP[i][1], DP[i][2]) + p
            elif j == 1:
                DP[i + 1][j] = max(DP[i][0], DP[i][2]) + p
            else:
                DP[i + 1][j] = max(DP[i][0], DP[i][1]) + p
    res += max(DP[n - 1][0], DP[n - 1][1], DP[n - 1][2])
    # for i in range(n):
    #     print(DP[i])
    # print("------------")

print(res)


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

int main(){
	int sum, buf;
	bool available = false;
	const int cake = 4, donut = 7;
	cin >> sum;
	
	buf = sum;
	if(buf % cake == 0) available = true;
	while(buf > 0){
		if(buf % donut == 0) available = true;
		buf -= cake;
	}
	buf = sum;
	if(buf % donut == 0) available = true;
	while(buf > 0){
		if(buf % cake == 0) available = true;
		buf -= donut;
	}

	if(available)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define INF 1e9+7
#define LLINF 1e18
using namespace std;
const int MOD = 1e9 +7;

int ans[100010];
vector<pii> e[100010];

void dfs(int x,int par=-1){
    for(auto i:e[x]){
        if(i.first != par){
            ans[i.first] = ans[x]^i.second%2;
            dfs(i.first,x);
        }
    }
    return;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    rep(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        e[a].pb(pii(b,c));
        e[b].pb(pii(a,c));
    }
    dfs(1);
    rep2(i,1,n+1){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, x, n) for(int i = x; i < (int)(n); i++)
#define ALL(n) begin(n), end(n)
//struct cww{cww(){ios::sync_with_stdio(false);cin.tie(nullptr);}}star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;

int main() {
  int n;
  REP(i, 5) {
    scanf("%d", &n);
    if (n == 0) {
      printf("%d\n", i + 1);
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 3816
#include <bits/stdc++.h>
#define endl '\n'
#define forn(i, n) for(int i=0;i<n;i++)
#define lli long long int
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back

using namespace std;

const int MAXN = 1000001;

int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        lli a,b,c;
        cin>>a>>b>>c;

        forn(i, 100) {
                if(a & 1 || b & 1 || c & 1) {
                        cout<<i<<endl;
                        return 0;
                }
                lli A = a / 2ll;
                lli B = b / 2ll;
                lli C = c / 2ll;

                a += B + C - A - A;
                b += A + C - B - B;
                c += A + B - C - C;
        }
        cout<<-1<<endl;
        return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

ll N;
VLL parents;
VVLL childs;
VVLL edges;
VLL DP;

ll dp(ll n) {
	if (DP[n] != -1)return DP[n];
	if (childs[n].size() == 0) {
		DP[n] = 1;
		return 1;
	}
	DP[n] = 1;
	for (ll c : childs[n]) {
		DP[n] += dp(c);
	}
	return DP[n];
}

ll modpow(ll base, ll p) {
	if (p == 0)return 1;
	if (p == 1)return base;
	ll ans = modpow(base, p / 2);
	ans = (ans * ans) % MOD;
	if (p & 1)ans = (ans * base) % MOD;
	return ans;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> N;
	edges.resize(N);
	for (ll n = 0; n < N - 1; n++) {
		ll a, b;
		cin >> a >> b;
		edges[--a].push_back(--b);
		edges[b].push_back(a);
	}
	parents.resize(N);
	childs.resize(N);
	queue<pll> q;
	q.push(pll(0, -1));
	while (!q.empty()) {
		ll cur = q.front().first;
		ll p = q.front().second;
		q.pop();
		parents[cur] = p;
		for (ll c : edges[cur]) {
			if (c == p)continue;
			childs[cur].push_back(c);
			q.push(pll(c, cur));
		}
	}
	DP.resize(N, -1);
	dp(0);
	ll ans = (modpow(2,N-1)+MOD-1)%MOD;
	ans = (ans * N) % MOD;
	for (ll n = 0; n < N; n++) {
		for (ll c : childs[n]) {
			ans = (ans+MOD-modpow(2, DP[c])+1)%MOD;
		}
		ans = (ans + MOD - modpow(2, N - DP[n]) + 1) % MOD;
	}
	ll inv = modpow(2, N * (MOD - 2));
	ans = (ans * inv) % MOD;
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 29568
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(v,p,path):
    for c in g[v]:
        if c == p: continue
        if c == n-1:
            path.append(n-1)
            path.append(v)
            return True
        if dfs(c,v,path):
            path.append(v)
            return True
    return False            

path = []
dfs(0,-1,path)

from collections import deque
q = deque()
memo = [-1]*n #0 sente 1: gote
for i in path[:len(path)//2]:
    memo[i] = 1
    q.append(i)
for i in path[len(path)//2:]:
    memo[i] = 0
    q.append(i)

res = len(path)//2 #Sunuke's point

while q: #キューが空になるまで
    v = q.popleft() #キューから情報を取り出す
    for c in g[v]:
        if memo[c] != -1: continue
        #(nx,ny)が未確認のとき、確認済みにしてキューに入れる------------------
        memo[c] = memo[v]
        res += memo[c]
        q.append(c)

if n - res > res: print("Fennec")
else: print("Snuke")







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

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> H(N);
  rep(i, N) {
    cin >> H[i];
  }
  vector<ll> A(M);
  vector<ll> B(M);
  rep(i, M) {
    cin >> A[i];
    cin >> B[i];
  }
  vector<bool> p(N, true);

  rep(j, M){
    if (H[B[j] - 1] > H[A[j] - 1]) {
      p.at(A[j]-1) = false;
    }
    if (H[B[j] - 1] < H[A[j] - 1])
    {
      p.at(B[j] - 1) = false;
    }
      if (H[B[j] - 1] == H[A[j] - 1])
      {
        p.at(A[j] - 1) = false;
        p.at(B[j] - 1) = false;
      }
    }
  int ans = 0;
  rep(i, N) {
    if (p[i] == true) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 5544
n=gets.chomp.to_i
r,b=[],[]
n.times{|i|r[i]=gets.split.map(&:to_i)}
n.times{|i|b[i]=gets.split.map(&:to_i)}
r.sort_by!{|x|x[0]}
b.sort_by!{|x|x[0]}
b.each{|bb|
  c= r.select{|rr|rr[0]<bb[0]}.sort_by{|r|r[1]}.reverse
  c.each{|cc|
    if cc[1]<bb[1] then
      r.delete(cc)
      break
    end
  }
}
puts n-r.size


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


}


Measured memory_bytes: 128
from itertools import permutations
N=int(input())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))
p=0
q=0
i=0
for x in permutations(range(1,N+1)):
    i+=1
    if list(x)==P:
        p=i
    if list(x)==Q:
        q=i
print(abs(p-q))

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  int i;
  for(i = 0;i < n;++i){
    cin >> a.at(i);
  }
  vector<int> b(n-k+1);
  int mi,ma;
  for(i = 0;i <= n-k;++i){
    if(a.at(i+k-1) <= 0){
      b.at(i) = (-1)*a.at(i);
    }else if(a.at(i) < 0 && a.at(i+k-1) > 0){
      mi = min((-1)*a.at(i),a.at(i+k-1));
      ma = max((-1)*a.at(i),a.at(i+k-1));
      b.at(i) = 2*mi + ma;
    }else{
      b.at(i) = a.at(i+k-1);
    }
  }
  int ans = b.at(0);
  for(i = 1; i <= n-k;++i){
    if(ans > b.at(i)){
      ans = b.at(i);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 896
import sys

A, B, C = map(int, input().split())
aLst = [A]
bLst = [B]
cLst = [C]
cnt = 0
if A % 2 == 1 or B % 2 == 1 or C % 2 == 1:
    print(0)
    sys.exit()
    
for i in range(1000000000000):
    atmp = (bLst[i] // 2) + (cLst[i] // 2)
    btmp = (aLst[i] // 2) + (cLst[i] // 2)
    ctmp = (aLst[i] // 2) + (bLst[i] // 2)
    aLst.append(atmp)
    bLst.append(btmp)
    cLst.append(ctmp)
    if atmp % 2 == 1 or btmp % 2 == 1 or ctmp % 2 == 1:
        cnt += 1
        break
    elif atmp == btmp and btmp == ctmp and atmp == ctmp:
        cnt = -1
        break
    else:
        cnt += 1

print(cnt)

Measured memory_bytes: 38256
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1<<30;
const ll  longinf = 1LL<<60;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
	int n,k,l;
	scanf("%d %d",&n,&k);
	l=2*k;
	int x[n],y[n],table[k+1][k+1];
	bool black[n];
	char c[n];
	rep(i,k+1)rep(j,k+1)table[i][j]=0;
	rep(i,n){
		scanf("%d %d %c",&x[i],&y[i],&c[i]);
		x[i]%=l;
		y[i]%=l;
		black[i]=(c[i]=='B');
		if(x[i]>=k){
			x[i]-=k;
			black[i]=!black[i];
		}
		if(y[i]>=k){
					y[i]-=k;
					black[i]=!black[i];
		}
		if(black[i]){
			table[0][0]++;
			table[0][y[i]+1]--;
			table[x[i]+1][0]--;
			table[x[i]+1][y[i]+1]+=2;
		}
		else{
			table[0][y[i]+1]++;
			table[x[i]+1][0]++;
			table[x[i]+1][y[i]+1]-=2;
		}
	}
	rep(i,k)REP(j,1,k)table[i][j]+=table[i][j-1];
	rep(i,k)REP(j,1,k)table[j][i]+=table[j-1][i];
	int ans=0;
	rep(i,k)rep(j,k){
		table[i][j]=max(table[i][j],n-table[i][j]);
		ans=max(ans,table[i][j]);
	}
	cout<<ans<<endl;
  return 0;
  }

Measured memory_bytes: 5120
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int main(){
	int a, b, c;
	while(~scanf("%d %d %d", &a, &b, &c)){
		if(c >= a && c <= b) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

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

int main(){
  int a,b;
  string sa, sb;
  cin>>a>>b;
  for(int i=0;i<a;i++) sa.push_back(b+'0');
  for(int i=0;i<b;i++) sb.push_back(a+'0');
  if(sa<sb) cout<<sa;
  else cout<<sb;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
std::string replaceAll(std::string &replacedStr, std::string from, std::string to) {
    unsigned int pos = replacedStr.find(from);
    int toLen = to.length();
 
    if (from.empty()) {
        return replacedStr;
    }
 
    while ((pos = replacedStr.find(from, pos)) != std::string::npos) {
        replacedStr.replace(pos, from.length(), to);
        pos += toLen;
    }
    return replacedStr;
}
int main() {


//long long a,b;
//int *num=new int[4];
//char *s=new char[3];
string s;
cin >> s;

string s2="CODEFESTIVAL2016";

int res=0;
for(int i=0;i<s.length();i++){
if(s[i]!=s2[i])res++;

}
cout << res;


}


Measured memory_bytes: 256
s=input()
t=input()
f1=[0]*26
f2=[0]*26
for i in s:
    f1[ord(i)-ord('a')]+=1
for i in t:
    f2[ord(i)-ord('a')]+=1
for i in range(26):
    if f1[i]:
        sm=i
        break
for i in range(25,-1,-1):
    if f2[i]:
        lg=i
        break
if sm<lg:
    print('Yes')
else:
    flag=True
    for i in range(26):
        if f1[i]>f2[i]:
            flag=False
            break
    if len(s)<len(t) and flag:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int q,w;
	cin>>q;
	string a;
	cin>>a;
	int s=a.size();
	if(s<=q) cout<<a;
	else 
	{
		for(w=0;w<q;w++)
			cout<<a[w];
		cout<<"...";
	}
}

Measured memory_bytes: 3596
while line = gets
  value = line.chomp
  list = value.split
  n = list[0].to_i
  count = 0

  10.times do |a|
    10.times do |b|
      10.times do |c|
        10.times do |d|
          sum = (a + b + c + d)
          if sum == n
            count += 1
          end
        end
      end
    end
  end
  puts count
end



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

int main(){
    long long n;
    cin >> n;

    vector<long long> a;

    a.push_back(1);

    long long x = 6;
    for(long long i = 0; i < 6; i++){
        a.push_back(x);
        x *= 6;
    }

    long long y = 9;
    for(long long i = 0; i < 9; i++){
        a.push_back(y);
        y *= 9;
    }

    vector<long long> dp(100001, 1e9);
    dp[0] = 0;

    for(long long i = 0; i <= 100000; i++){
        for(long long j = 0; j < a.size(); j++){
            if(i >= a[j]) dp[i] = min(dp[i], dp[i-a[j]]+1);
        }
    }

    cout << dp[n] << endl;
    return 0;
}

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

int mod = 1000000007;
int64_t large = 9223372036854775807;

int main()
{
    int64_t r, D, x;
    cin >> r >> D >> x;
    for (int i = 0; i < 10; i++)
    {
        x = r * x - D;
        cout << x << endl;
    }
}

Measured memory_bytes: 256
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')


def solve(test):
	s = [''] + list(input())
	t = [''] + list(input())
	rec = [[0 for j in range(len(t))] for i in range(len(s))]
	for i in range(1, len(s)):
		for j in range(1, len(t)):
			if s[i] == t[j]:
				rec[i][j] = 1 + rec[i - 1][j - 1]
			else:
				rec[i][j] = max(rec[i - 1][j], rec[i][j - 1])

	ans = []
	i, j = len(s) - 1, len(t) - 1
	while i >= 0 and j >= 0:
		if s[i] == t[j]:
			ans.append(s[i])
			i -= 1
			j -= 1
		elif rec[i - 1][j] > rec[i][j - 1]:
			i -= 1
		else:
			j -= 1

	print(''.join(ans[::-1]))


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)


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

ll c[99][99];

int main(){
  for(int i=0;i<=60;i++){
    c[i][0] = 1;
    for(int j=1;j<=i;j++)c[i][j] = c[i-1][j-1] + c[i-1][j];
  }

  ll n,m;
  while(cin >> n >> m, n){
    m--;
    int k = 0;
    while(c[n][k]<=m)m -= c[n][k++];

    string b;
    for(int i=0;i<n;i++){
      int r = n-i-1;
      if(c[r][k]<=m){
	m -= c[r][k--];
	b += "1";
      }else b += "0";
    }
    cout << b << endl;
  }
}

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

int main() {
  int64_t N,t=1,ans=0; cin>>N;
  vector<int64_t> A(N);
  vector<int64_t> B(N);
  vector<int64_t> C(N);
  vector<pair<int64_t,int64_t>> T(N);
  rep(i,N){
    int64_t a,b; cin>>a>>b;
    A.at(i)=a;
    B.at(i)=b;
    T.at(i)=make_pair(a+b,i);
  }
  sort(T.begin(),T.end());
  reverse(T.begin(),T.end());
  rep(i,N){
    auto k=T.at(i).second;
    if(t>0)ans+=A.at(k);
    else ans-=B.at(k);
    t*=-1;
  }
  cout<<ans;    
}

Measured memory_bytes: 7200
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

int dp1[3050][3050],dp2[3050][3050];
int main(){
    int n,t;
    cin >> n >> t;
    vi a(n), b(n);
    rp(i,n) cin >> a.at(i) >> b.at(i);
    rp(i,n){
        repi(j,0,3001){
            if(i==0){
                if(j-a[i]>=0)
                dp1[0][j]=b[0];
                continue;
            }
            if(j-a[i]<0) dp1[i][j]=dp1[i-1][j];
            else dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-a[i]]+b[i]);
        }
    }
    rp(i,n){
        repi(j,0,3001){
            if(i==0){
                if(j-a[n-1-i]>=0)
                dp2[0][j]=b[n-1];
                continue;
            }
            if(j-a[n-1-i]<0) dp2[i][j]=dp2[i-1][j];
            else dp2[i][j]=max(dp2[i-1][j],dp2[i-1][j-a[n-1-i]]+b[n-1-i]);
        }
    }
    int ans=0;
    rp(i,n){
        int res=0;
        if(i==0){
            res=dp2[n-2][t-1];
        }
        else if(i==n-1){
            res=dp1[n-2][t-1];
        }
        else{
            rp(j,t){
                chmax(res,dp1[i-1][j]+dp2[n-2-i][t-1-j]);
            }
        }
        res += b[i];
        chmax(ans,res);
    }
    print(ans);
    return 0;
}

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define SORTG(v) sort(v.begin(),v.end(),greater<>())
#define SORT(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/3

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<string> Vs;

template<class T> void chmax(T& a, T b) {if(a<b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a>b){a=b;}}
void YesNo(int a) {if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
void YESNO(int a) {if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
void AorB(int a,string b,string c) {if(a){cout<<b<<endl;}else{cout<<c<<endl;}}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void start(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}


signed main(){start();
    int n,a,b,anow=0,bnow=0;
    string s;
    cin>>n>>a>>b>>s;
    
    REP(i,0,n){
        if(s[i]=='a'){
            if(anow+bnow<a+b){
                cout<<"Yes"<<endl;
                anow++;
            }else cout<<"No"<<endl;
        }else if(s[i]=='b'){
            if(anow+bnow<a+b && bnow<b){
                cout<<"Yes"<<endl;
                bnow++;
            }else cout<<"No"<<endl;
        }else cout<<"No"<<endl;
    }
    return 0;
}


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

using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, a, b) for (int64_t i = (a); i < (b); ++i)
const int MOD = 1e9 + 7;
typedef long long ll;
const long long INF = 1LL << 60;
using Graph = vector<vector<int>>;

int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> h(n);
  for (int i = 0; i < n; i++) cin >> h[i];
  if (n <= k)
    cout << 0 << endl;
  else {
    SORT(h);
    ll count = 0;
    for (int i = 0; i < n - k; i++) count += h[i];
    cout << count << endl;
  }
}


Measured memory_bytes: 1792
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))

def binarySearch(key):
  left = 0
  right = n

  while left < right:
    mid = (right + left) // 2
    if S[mid] == key:
      return mid
    elif key < S[mid]:
      right = mid
    else:
      left = mid + 1
  return "Not Found"

cnt = 0
for t in T:
  idx = binarySearch(t)
  if idx != 'Not Found':
    cnt += 1
    
print(cnt)


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

using namespace std;

int main(){
  int x,y,z,k;
  cin>>x>>y>>z>>k;
  while(y<=x&&k) y*=2,k--;
  while(z<=y&&k) z*=2,k--;
  if(x<y&&y<z) cout<<"Yes\n";
  else cout<<"No\n";
  return 0;
}

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

typedef long long ll;
typedef int64_t i6;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 1; i <= n; ++i)
#define ALL(v) (v).begin(), (v).end()
#define Sort(x) sort(ALL(x))
#define Sort_rev(x) Sort(x);reverse(ALL(x))

template<typename V,typename T>
T find_num(V v, T num) {
    if ( find(ALL(v), num) == v.end() ) {
        return false;
    } else {
        return true;
    }
}

// π M_PI
// deg = rad*180/M_PI

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = 0;
    while(1) {
        c -= b;
        if ( c <= 0 ) {
            ans = 1;
            break;
        }
        a -= d;
        if ( a <= 0 ) {
            break;
        }
    }
    cout << ( ans ? "Yes" : "No" ) << endl;
    return 0;
}


Measured memory_bytes: 3668
import sys
input = sys.stdin.readline

def main():
    M, D = map(int, input().split())
    count = 0
    for m in range(1, M+1):
        for d in range(1, D+1):
            d1 = d%10
            d2 = d//10
            if d1 >= 2 and d2 >= 2:
                if d1 * d2 == m:
                    # print(m, d)
                    count += 1
    
    print(count)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060