akhauriyash/Code-Regression huggingface dataset:
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
bool DEBUG = 0; void log(A ...)(lazy A a){ if(DEBUG) print(a); }
void main(string[] args){ args ~= ["", ""]; string cmd = args[1]; if(cmd == "-debug") DEBUG = 1;
if(cmd == "-gen") gen; else if(cmd == "-jury") jury; else solve; } 
void print(){ writeln(""); } void print(T)(T t){ writeln(t); } void print(T, A ...)(T t, A a){ std.stdio.write(t, " "), print(a); }
string unsplit(T)(T xs){ return xs.array.to!(string[]).join(" "); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; } T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
T lowerTo(T)(ref T x, T y){ if(x > y) x = y; return x; } T raiseTo(T)(ref T x, T y){ if(x < y) x = y; return x; }

// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //
void gen(){
}
void jury(){
}
void solve(){
    int x = scan!int;
    (1 - x).print;
}

Measured memory_bytes: 3228
#include <stdio.h>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
typedef long long int ll;
#define F first
#define S second
#define MP make_pair
const int N=5e5+10;
const ll INF=1LL<<60;
ll dis(pi a,pi b){
    ll x=a.F-b.F,y=a.S-b.S;
    return x*x+y*y;
}
int main(){
    int n,lim;
    ll ans=INF;
    pi a[N];
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",&a[i].F,&a[i].S);
    sort(a,a+n);
    lim=min(500,n);
    for(int i=0;i<lim;i++)for(int j=i+1;j<lim;j++)ans=min(ans,dis(a[i],a[j]));
    for(int i=lim;i<n;i++)for(int j=1;j<lim;j++)ans=min(ans,dis(a[i],a[i-j]));
    printf("%lld\n",ans);
}


Measured memory_bytes: 6656
#include<stdio.h>
#include<string.h>
#define Max(x,y) ((x>y)?x:y)
typedef struct str{
	int n;
	char s;
}STR;
STR d[1000005];
char s[1000005];
int main(){
	int i,j,n,k,l,ans=0;;
	scanf("%s",s);
	l=strlen(s);
	k=0;n=-1;
	for(i=0;i<l;i++){
		if(k!=s[i]){
			n++;
			k=s[i];
			d[n].s=s[i];
			d[n].n=1;
		}else d[n].n++;
	}
	for(i=1;i<n;i++){
		if(d[i].s=='O' && d[i-1].s=='J' && d[i+1].s=='I' 
		   && d[i].n<=d[i-1].n && d[i].n<=d[i+1].n)
		   ans=Max(ans,d[i].n);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#define ll long long
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_set>
#include <iomanip>
using namespace std;
ll dp[400][400] = {0};
vector<ll> elements;


ll sum(int start, int last)
{
    ll ans = 0;
    for(int i = start; i<=last; ++i)
    {
        ans+=elements[i];
    }
    return ans;

}


ll check(int start, int last)
{
    //cout<<start<<"\t"<<last<<endl;
    if(start == last)
    {
        dp[start][start] = 0;
        return 0;
    }

    if(dp[start][last] != -1)
    {
        return dp[start][last];
    }

    ll ans = 1e18+5;
    ll x = sum(start, last);
    for(int i=start; i< last; ++i)
    {
       // cout<<ans<<" "<<" "<<start<<" "<<last<<endl;
        ans = min( (check(start, i) + check(i+1, last) + x),ans);
    }
    dp[start][last] = ans;
    return ans;


}


int main()
{

    ll a,b,c,k;
    cin>>a>>b>>c>>k;

    ll total = 0;
    if(k <= a)
    {
         total += k;
    }
    else
    {
        total += a;
    }
    k -= a;
    if(k <= 0)
    {
        cout<<total;
        exit(0);
    }
    k -= b;
    if(k<=0)
    {
        cout<<total;
        exit(0);
    }
    if(k <= c)
    {
        total -= k;
    }
    else
    {
        total-=c;
    }


    cout<<total;






    return 0;
}


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

int main(){
	long long a,b,c,d;
	cin >> a >> b >> c >> d;
	long long e = b / c - (a-1)/ c;
	long long f = b / d - (a-1)/ d;
	long long g = c * d / __gcd(c,d);
	long long h = b / g - (a-1)/ g;
	cout << b - a + 1 - e - f + h << endl;
}

Measured memory_bytes: 256
#include  <bits/stdc++.h>
using namespace std;
#define pb push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define M 1000000007

/*const ll N=10^5+1;
std::vector<ll> deg(N);
std::vector<vector<ll> >g(N);
vector<bool> visited(N);
vector<ll> comp;

void dfs(ll i){

    //comp.push_back(i);
   // cout<<" visited: "<<i<<" ";
    visited[i]=true;
   for(int j=0;j<g[i].size();j++)
    if(!visited[g[i][j]])
    dfs(g[i][j]);
}
*/

int main() {
    
    string s,t;
    cin>>s>>t;
    int n=s.length(),m=t.length();
    int mn=m;
    for(int i=0;i+m<=n;i++){
        string ss=s.substr(i,i+m);
        int cnt=0;
        for(int j=0;j<m;j++)
            if(ss[j]!=t[j])
            cnt++;
        
        mn=min(mn,cnt);
    }
    cout<<mn;
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x)    // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()


int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    ll cnt = 0;
    for (ll i = 0; i < n; i++)
    {
        ll temp1, temp2;

        cin >> temp1 >> temp2;

        if (temp1 == temp2)
        {
            cnt++;
            if (cnt >= 3)
            {
                cout << "Yes" << endl;
                exit(0);
            }
        }
        else
        {
            cnt = 0;
        }

    }

    cout << "No" << endl;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll mi=N;
	for(ll a=1;a*a<=N;a++) if(N%a==0) {
		mi=min(mi,a-1+N/a-1);
	}
	cout<<mi<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    static PrintWriter out;

    public static void main(String[] args) throws IOException {
        out = new PrintWriter(new OutputStreamWriter(System.out));
        CF_Reader in = new CF_Reader();

        int n = in.intNext();
        long[] nums = new long[n];
        long total = 0;

        for (int i = 0; i < n; i++) {
            nums[i] = in.longNext();
            total += nums[i];
        }
        long average = total / n;
        long result = 0;
        long result2 = 0;
        for (long num: nums) {
            long diff = average - num;
            long diff2 = (average + 1) - num;
            result += diff * diff;
            result2 += (diff2 * diff2);
        }
        out.println(Math.min(result, result2));

        out.close();
    }

    static class CF_Reader {
        BufferedReader br;
        StringTokenizer st;

        public CF_Reader() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine().trim());
            return st.nextToken();
        }

        long longNext() throws IOException {
            return Long.parseLong(next());
        }

        int intNext() throws IOException {
            return Integer.parseInt(next());
        }

        double doubleNext() throws IOException {
            return Double.parseDouble(next());
        }

        char charNext() throws IOException {
            return next().charAt(0);
        }

        public int[] nextIntArray(final int n) throws IOException {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = intNext();
            return a;
        }

        public long[] nextLongArray(final int n) throws IOException {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = longNext();
            return a;
        }

        String line() throws IOException {
            return br.readLine().trim();
        }
    }
}


Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const int MOD = 1000000007;

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

    ll N;
    cin >> N;
    vec A(N);
    Rep (i, N) {
        cin >> A[i];
    }

    vec cnt(100010, 0);
    cnt[0] = 3;
    ll ans = 1;
    Rep (i, N) {
        ans *= cnt[A[i]];
        ans %= MOD;
        cnt[A[i]]--;
        cnt[A[i]+1]++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T &a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T &a, T b) {
	a = std::min(a, b);
}

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)
			return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)
		return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i;
		res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)
		return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod ;
}
int get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int> engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/

int n, u, v;
int dis[100005];
vector<int> G[100005];
bool used[100005];
int par[100005];
int ko[100005];
void dfs(int x) {
	used[x] = true;
	ko[x] = 1;
	for (int i : G[x]) {
		if (!used[i]) {
			dis[i] = dis[x] + 1;
			par[i] = x;
			dfs(i);
			ko[x] += ko[i];
		}
	}
}
int farmax;
void dfs2(int x) {
	chmax(farmax, dis[x]);
	for (int i : G[x]) {
		if (i == par[x])
			continue;
		dfs2(i);
	}
}
signed main() {
	cin >> n >> u >> v;
	u--;
	v--;
	rep(i,n-1)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(v);
	int p = dis[u];
	int now = u;
	int start;
	int ans;
	if (p % 2)
		ans = p / 2;
	else
		ans = p / 2 - 1;
	while (now != v) {
		if (p % 2) {
			if (dis[now] == p / 2 + 1) {
				start = now;
				break;
			}
		} else {
			if (dis[now] == p / 2 + 1) {
				start = now;
				break;
			}
		}
		now = par[now];
	}
	dfs2(start);
	farmax -= dis[start];
	if (p % 2)
		ans += farmax;
	else
		ans += farmax + 1;
	cout << ans << endl;
}


Measured memory_bytes: 12160
#include<iostream>
#include<cmath>

int main(void)
{
	int a, b, c, i, cout = 0;
	std::cin >> a >> b >> c;
	for (i = a; i <= b; i++){
		if(c%i == 0)
			cout++;
	}
	std::cout << cout << std::endl;
	return 0;
}


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

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        int[] factors = new int[1000001];
        long temp = n;
        for(int prime=2;prime<=1000000;prime++){
            while(temp%prime==0){
                factors[prime]++;
                temp/=prime;
            }
        }
        int count=0;
        for(int i=2;i<=1000000;i++){
            int fac = factors[i];
            for(int j=1;j<=fac;j++){
                fac-=j;
                count++;
            }
        }
        if(temp>1)
            count++;
        System.out.println(count);
    }

   
}

Measured memory_bytes: 29832
def dfs(k, as, cnt)
  res = 0
  n = as.size
  if k == 10
    if cnt == 0
      res = -Float::INFINITY
    else
      n.times { |i| res += $ps[i][as[i]] }
    end
  else
    as = as.dup
    x = dfs(k + 1, as, cnt)
    n.times { |i| as[i] += 1 if $fs[i][k] == 1 }
    y = dfs(k + 1, as, cnt + 1)
    res = x > y ? x : y
  end
  res
end

n = gets.to_i
$fs = Array.new(n, Array.new(10))
$ps = Array.new(n, Array.new(11))
n.times { |i| $fs[i] = gets.split.map(&:to_i) }
n.times { |i| $ps[i] = gets.split.map(&:to_i) }
p dfs(0, Array.new(n, 0), 0)

Measured memory_bytes: 2684
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
int heap[5100];
using namespace std;
string in;
int v[26];
int cap;
int m;
int parser(int);
int alc = -1;
int free(int pos) {
	int adr = parser(pos+5);
	if (adr == -2)throw new exception;
	if (adr == -1)return 0;
	if (heap[adr] == -1)throw new exception;
	cap -= heap[adr];
	heap[adr] = -1;
	return 0;
}
int malloc(int pos) {
	int size = parser(pos + 7);
	if (cap +size> m) {
		return -1;
	}
	alc++;
	heap[alc] = size;
	cap += size;
	return alc;
}
int clone(int pos) {
	int adr = parser(pos + 6);
	if (adr == -2)throw new exception;
	if (adr == -1)return -1;
	if (cap +heap[adr]> m) {
		return -1;
	}
	if (heap[adr] == -1)throw new exception;
	alc++;
	heap[alc] = heap[adr];
	cap += heap[adr];
	return alc;
}
int assign(int pos) {
	return v[in[pos] - 'A'] = parser(pos + 2);
}
int literal(int pos) {
	if (in[pos + 1] == '=')return assign(pos);
	if (in[pos + 1] == 'U')return -1;
	if (in[pos] >= 'A') {
		return v[in[pos] - 'A'];
	}
	int num=0;
	for (; in[pos] != ')'; pos++) {
		num *= 10;
		num += in[pos] - '0';
	}
	return num;
}
int parser(int pos) {
	for (;;) {
		switch (in[pos]) {
		case 'c':
			return clone(pos);
		case 'f':
			return free(pos);
		case 'm':
			return malloc(pos);
		case '(':
			pos++;
			continue;
		default:
			return literal(pos);
		}
	}
}
int main(){
	cin >> m;
	fill(v, v + 26, -2);
	try {
		while (cin >> in) {
			parser(0);
		}
	}
	catch(...){
		cout << "Error" << endl;
		return 0;
	}
	for (int a : v) {
		if (a >= 0) {
			heap[a] = 0;
		}
	}
	int sum = 0;
	for (int a : heap)sum += a > 0 ? a : 0;
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3224
'''
3^9 = 19683
3^10 = 59049
これくらいの数なら全探索して十分間に合う
'''

import itertools
from functools import reduce

n = int(input())
ans = 0

for length in range(3, len(str(n)) +1):
	base = itertools.product('357', repeat=length)
	# baseはタプルからなるリスト
	for i in base:
		if len(set(i))== 3: # 3種類の数字が1回以上使われている
			i_int = int(reduce(lambda x, y: x + y, i))
			if i_int <= n:
				ans += 1

print(ans)


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> b(N-1);
  for(int i=0;i<N-1;i++)
    cin>>b.at(i);
  vector<int> ans(N);
  ans.at(0)=b.at(0);
  for(int i=1;i<N-1;i++)
    ans.at(i)=min(b.at(i-1),b.at(i));
  ans.at(N-1)=b.at(N-2);
  int sum=0;
  for(int i=0;i<N;i++){
    sum+=ans.at(i);
  }
  cout<<sum<<endl;
}


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

int main(void){
    int a,b;
    cin >> a;
    cin >> b;
    int d = a / b;
    int r = a % b;
    double f = double(a) / double(b);
    cout << d;
    cout << " ";
    cout << r;
    cout << " ";
    cout << fixed << setprecision(5) << f;
    cout << endl;
}


Measured memory_bytes: 3272
#include <iostream>

using namespace std;

int main(){
    int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;

    for(int y=sy; y<ty; ++y) cout << 'U';
    for(int x=sx; x<tx; ++x) cout << 'R';

    for(int y=ty; y>sy; --y) cout << 'D';
    for(int x=tx; x>sx; --x) cout << 'L';

    cout << 'L';
    for(int y=sy; y<ty+1; ++y) cout << 'U';
    for(int x=sx-1; x<tx; ++x) cout << 'R';
    cout << 'D';

    cout << 'R';
    for(int y=ty; y>sy-1; --y) cout << 'D';
    for(int x=tx+1; x>sx; --x) cout << 'L';
    cout << 'U';

    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define pb          push_back
#define mp          make_pair
#define ll          long long
#define pii         pair<int, int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int, int>
#define mii         map<pii, int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rev(i,a,b)  for(int i=a;i>=b;i--)
#define lb          lower_bound
#define ub          upper_bound

#define bg(i)       i.begin()
#define fset(it,s)   for(auto it = s.begin(); it != s.end(); it++)
 
#define track(x)                 cerr<<#x<<": "<<x<<endl
#define track2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define track3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define track4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
 
#define ed(i)       i.end()
#define mem(a)	    memset(a, 0, sizeof(a))

#define MOD         1000000007
int mult(int a,int b, int p=MOD){return ((a%p)*(b%p))%p;}
int add(int a, int b, int p=MOD){return (a + b + p)%p;}
int fpow(int n, int k, int p = MOD) {int r = 1; for (; k; k >>= 1LL) {if (k & 1LL) r = mult(r,n,p); n = mult(n,n,p);} return r;}
int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
void self_max(int &a, int b) {a = max(a, b); }
void self_min(int &a, int b) {a = min(a, b); }
void self_add(int &a, int b, int p = MOD) { a += b; if(a >= p) a -= p;}
void self_sub(int &a, int b, int p = MOD) { a -= b; if(a < 0) a += p;}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
const int INF = 1e9 + 5;
#define N	    	400001

void solve() {
    ll x;
    cin>>x;
    rep(i, -1000, 1000) {
        rep(j, -1000, 1000) {
            if(pow(i, 5) - pow(j, 5) == x) {
                cout<<i<<" "<<j<<endl;
                return;
            }
        }
    }
}
int main() {
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin>>t;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 4012
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int N,M;
int X[100000];

int Y[100001];
vector< P > G[100001];

int main(){
  scanf("%d %d",&N,&M);
  for(int i=0;i<N;i++){
    scanf("%d",&X[i]);
    Y[ X[i] ]++;
  }
  for(int i=1;i<=100000;i++){
    if(Y[i]==0)continue;
    int num=Y[i];
    if(num-num%2>0)
      G[ i%M ].push_back( P( num - num%2 , i ) );
    
    if( num%2 > 0 )
      G[ i%M ].push_back( P( num%2 , i ) );
  }

  for(int i=0;i<M;i++){
    sort(G[i].begin(),G[i].end());
    reverse(G[i].begin(),G[i].end());
  }

  int ans=0;
  for(int i=1;i<M;i++){
    int pos=i;
    int target=M-i;
    if( target < pos )break;
    
    while(1){
      if(G[target].empty() || G[pos].empty())break;

      ans++;
      
      P pa=G[target].back();
      G[target].pop_back();
      pa.first--;
      if(pa.first>0)G[target].push_back(pa);

      if(G[pos].empty()){
        pa.first++;
        G[pos].push_back(pa);
        ans--;
        break;
      }

      P pb=G[pos].back();
      G[pos].pop_back();
      pb.first--;
      if(pb.first>0)G[pos].push_back(pb);      

    }
  }
  
  int zcnt=0;
  for(int i=1;i<M;i++){
    map<int,int> mp;
    for(int j=0;j<(int)G[i].size();j++){
      P p=G[i][j];
      mp[ p.second ] += p.first;
    }

    for( P p : mp ){

      int k=p.second/2;
      ans+=k;

      //      while(k--){ cout<<p.first<<' '<<p.first<<endl; }
      
    }
  }
  
  for(int i=0;i<(int)G[0].size();i++)
    zcnt+=G[0][i].first;
  

  int tmp =zcnt/2;
  ans+=tmp;

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


Measured memory_bytes: 6528
N = int(input())
ls = []
for i in range(N):
    ls.append(list(map(int,input().split())))
sls = sorted(ls,key=lambda x:x[1])
#print(sls)
time = 0
ans = 'Yes'
for v in sls:
    time += v[0]
    if time > v[1]:
        ans = 'No'
print(ans)

Measured memory_bytes: 55188
N, Q = map(int, input().split())
rename = []
for i in range(N) :
    year, name = input().split()
    year = int(year)
    rename.append([year, name])
if Q < rename[0][0] :
    print("kogakubu10gokan")
elif Q >= rename[-1][0] :
    print(rename[-1][1])
else :
    for i in range(N-1) :
        if rename[i][0] <= Q < rename[i+1][0] :
            print(rename[i][1])


Measured memory_bytes: 5600
#include <stdio.h>
int main(void){
    int x,y;
    scanf("%d", &x);
    scanf("%d", &y);
    if(x * 2 > y || x * 4 < y){
        printf("No\n");
    }else if(y % 2 != 0){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
    return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const ll INF = 1e18;
const int N = 19;
int a[N];
unordered_map<ll, ll> dp[N][N];

ll f(int l, int r, ll xl, ll xr) {
    if (l + 1 == r)
        return 0ll;
    if (dp[l][r].count((xl << N) | xr))
        return dp[l][r][(xl << N) | xr];

    ll ans = INF;
    for (int i = l + 1; i < r; i++) {
        ans = min(ans, f(l, i, xl, xl + xr) + f(i, r, xl + xr, xr) + a[i] * (xl + xr));
    }
    dp[l][r][(xl << N) | xr] = ans;
    return ans;
}

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

    int n;
    cin >> n;

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

    cout << f(0, n - 1, 1, 1) + a[0] + a[n - 1];

    return 0;
}

Measured memory_bytes: 11264
#include <iostream>
using namespace std;
int main() {
	int n, count = 0;
	int array[100];
	for(int i = 0; i < 100; i++) {
		array[i] = 0;
	}
	while(cin >> n) {
		array[n - 1]++;
		if(count < array[n - 1]) {
			count = array[n - 1];
		}
	}
	for(int i = 0; i < 100; i++) {
		if(count == array[i]) {
			cout << i + 1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
	//freopen("A.in", "r", stdin);
	//freopen("A.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b && b == c) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
}

Measured memory_bytes: 256
"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc091/tasks/arc092_a

xが小さい方から見ていく
→青があったら、今まで見た赤の点の内、現在選んでいる点よりy軸が小さく、最大の点を選んで繋げる
→最適性は簡単にわかる

"""
import bisect
N = int(input())

p = []

for i in range(N):

    a,b = map(int,input().split())
    p.append([a,b,0])

for i in range(N):

    c,d = map(int,input().split())
    p.append([c,d,1])

p.sort()

R = []
ans = 0

for i in range(2*N):

    x,y,cl = p[i]

    if cl == 0:
        R.append(y)
        R.sort()

    else:
        ind = bisect.bisect_left(R,y)
        if ind == 0:
            continue
        else:
            del R[ind-1]
            ans += 1
    #print (R)

print (ans)
    

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    if(2*k-1 <= n){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int,input().split()))
q = int(input())

total = sum(A) # これを基に各queryに対応(加算、減算)する

l = [0 for i in range(10**5+1)] # 配列のインデックスを各valueとみなす
for _ in A: # 各インデックスに各keyを加算
    l[_] += 1

for i in range(q):
    b, c = map(int,input().split())
    total += c * l[b] # totalの調整のみ
    total -= b * l[b] # 同上
    print(total)
    l[c] += l[b] # ここでリストの更新
    l[b] = 0 # 同上


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

typedef unsigned uint;

bool is_exist_bin_search(uint v, std::vector<uint> s){
  uint min = 0, max = s.size();
  while(min < max){
    uint mid = (min + max) / 2;
    uint v_mid = s[mid];
    if(v_mid == v) return true;

    if(v_mid >= v) max = mid;
    else min = mid+1;
  }
  return false;
}

unsigned count(std::vector<uint> s, std::vector<uint> t){
  uint n = 0;
  for(uint i = 0; i < t.size(); i++){
    if(is_exist_bin_search(t[i],s)) n++;
  }
  return n;
}

int main(){
  //std::ios_base::sync_with_stdio(false);
  //std::cin.tie(0);
  std::vector<uint> s,t;

  {
    uint n,buf;
    std::cin >> n;
    for(; n; n--){
      std::cin >> buf;
      s.push_back(buf);
    }
  }

  {
    uint q,buf;
    std::cin >> q;
    for(; q; q--){
      std::cin >> buf;
      t.push_back(buf);
    }
  }

  std::cout << count(s,t) << '\n';
}

Measured memory_bytes: 2648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,x,ans;
  ans = 0;
  cin >> n >> x;
  ll a[n];
  for(int i = 0;i < n;i++)cin >> a[i];
  for(int i = 0;i < n-1;i++){
    if(a[i] > x){
      ans += a[i]-x;
      a[i] = x;
    }
    if(a[i]+a[i+1] > x){
      ans += a[i] + a[i+1] - x;
      a[i+1] = x - a[i];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <vector>

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

using ll = long long;
typedef pair<ll, ll> P_ll;
typedef pair<int, int> P;

const ll INF_ll = 1e17;
const int INF = 1e8;

int main() {
  string S, T;
  cin >> S;
  cin >> T;
  ll ans = 0;
  for (int i = 0; i < S.size(); i++) {
    if (S[i] != T[i]) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3852
r, c = list(map(int, input().split(' ')))
matrix = []
for i in range(r):
    matrix.append(input())

ans = 0
cost = {}  # cost[(i, j), (p, q)]  -> (i,j) -> (p,q) の minコスト (20 * 20 * 20 * 20 = 1.6 * 1e4)
for i in range(r):
    for j in range(c):
        if matrix[i][j] == '#':  # !!!
            continue
        start = (i, j)
        cost[(i,j), (i,j)] = 0
        q = [start]
        while q:
            ti, tj = q.pop(0)
            for ni, nj in [(ti-1, tj), (ti, tj-1), (ti+1, tj), (ti, tj+1)]:
                if ni < 0 or nj < 0 or ni >= r or nj >= c or matrix[ni][nj] == '#':
                    continue
                if cost.get(((i,j), (ni, nj)), 99999999999999999) > cost[(i,j), (ti, tj)] + 1:
                    cost[(i,j), (ni, nj)] = cost[(i,j), (ti, tj)] + 1
                    ans = max(ans, cost[(i,j), (ni, nj)])
                    #print('i,j = ', (i,j), 'ni,nj = ', (ni,nj), 'ans = ', cost[(i,j), (ni, nj)])
                    q.append((ni, nj))
print(ans)

Measured memory_bytes: 109940
//C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

//C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Others
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
const int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
const int dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
const int lr[4] = { 0, 1, 0, -1 };
const int ud[4] = { 1, 0, -1, 0 };



//LOVE Ayane Sakura



using namespace std;



int main() {
	int K, N;
	cin >> K >> N;
	vector<int>A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int m = INT_MIN;
	for (int i = 0; i < N - 1; i++) {
		chmax(m, A[i + 1] - A[i]);
	}
	chmax(m, K + A[0] - A[N - 1]);
	cout << K - m << endl;
}

Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	N, K := nextInt(), nextInt()
	pn := make([]int, N)
	for i := range pn {
		pn[i] = nextInt()
	}
	sort.Ints(pn)
	var ans int
	for i := 0; i < K; i++ {
		ans += pn[i]
	}
	fmt.Println(ans)
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func pow(p, q int) int {
	res := p
	if q == 0 {
		return 1
	}
	for i := 0; i < q-1; i++ {
		res *= p
	}
	return res
}

func MinOf(vars ...int) int {
	min := vars[0]
	for _, i := range vars {
		if min > i {
			min = i
		}
	}
	return min
}

func MaxOf(vars ...int) int {
	max := vars[0]
	for _, i := range vars {
		if max < i {
			max = i
		}
	}
	return max
}

func gcdof2numbers(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcdof2numbers(b, a%b)
}

func lcmof2numbers(a int, b int) int {
	return a / gcdof2numbers(a, b) * b
}

// マイナスの場合は考慮していない
func fuctorial(a int) int {
	if a == 1 || a == 0 {
		return 1
	} else {
		return fuctorial(a-1) * a
	}
}

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// 素因数分解したmapを返す
func primeFuctorize(n int) map[int]int {
	pf := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			pf[i]++
			n /= i
		}
	}
	if n != 1 {
		pf[n]++
	}
	return pf
}


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

#define F first 
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010, M = 2 * N;

int n;
int h[N], e[M], ne[M], idx;
int d1[N], dn[N];
int q[N];
bool st[N];

void bfs(int u, int d[])
{
	memset(st, 0, sizeof st);
	int hh = 0, tt = -1;
	q[ ++ tt] = u;
	d[u] = 0;
	st[u] = true;
	
	while (hh <= tt)
	{
		int t = q[hh ++ ];
		for (int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if (!st[j])
			{
				d[j] = d[t] + 1;
				q[ ++ tt] = j;
				st[j] = true;
			}
		}
	}
}

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
	memset(h, -1, sizeof h);
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	
	bfs(1, d1), bfs(n, dn);
	
	int f = 0, s = 0;
	for (int i = 1; i <= n; i ++ )
		if (d1[i] <= dn[i]) f ++ ;
		else s ++ ;
	
	if (f > s) puts("Fennec");
	else puts("Snuke");
    return 0;
}

Measured memory_bytes: 6016
mod = 10**9+7


def main():
    n, k = map(int, input().split())

    baisuu = [[] for _ in [0]*(k+1)]
    tree = [0]*(k+1)

    for i in range(1, k+1):
        j = 2*i
        while j <= k:
            baisuu[i] += [j]
            j += i
        tree[i] = pow(len(baisuu[i])+1, n, mod)
    for i in range(k, 0, -1):
        for j in baisuu[i]:
            tree[i] -= tree[j]
        tree[i] %= mod
    ans = 0
    for i, j in enumerate(tree):
        ans = (ans+i*j) % mod
    print(ans)


main()


Measured memory_bytes: 61972
A,B,C=map(int, input().split())
#A%Bをたくさん足してそれ%BがCになる
L=[]
for i in range(1,100000):
    X=A*i%B
    if X not in L:
        L.append(X)
    else:
        break
if C in L:
    print("YES")
else:
    print("NO")


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

#if DEBUG && !ONLINE_JUDGE
  #include "header.h"
#else
  #define debug(args...)
#endif

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long lli;
typedef long double ld;

#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define rep(i,a,b) for(auto i=(a);i<b;i++)

#define INF (int)1e9
#define EPS 1e-9
#define MOD 1000000007
void preprocess(void) {
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(20);
  preprocess();
  string st; cin>>st;
  int q; cin>>q;
  int r = 0;
  string s = "", e = "";//start reverse
  while(q--) {
    int t; cin>>t;
    if(t == 1) {
      r = !r;
    }
    else {
      int f; char ch;
      cin>>f>>ch;
      f--;
      if(f^r) {
        e += ch;
      }
      else s += ch;
    }
  }
  if(r) {
    reverse(all(e));
    reverse(all(st));
    cout<<e<<st<<s<<endl;
  }
  else {
    reverse(all(s));
    cout<<s<<st<<e<<endl;
  }
}



Measured memory_bytes: 1040
#include <stdio.h>
int main()
{
  int t[24][60]={0};
  int h,m,count=0;
  int a,b;
  for(int k=0;k<=1;k++){
  scanf("%d",&a);
  for(int i=0;i<=a-1;i++){
    scanf("%d %d",&h,&m);
    t[h][m]=1;
  }
}
  for(h=0;h<=23;h++){
    for(m=0;m<=59;m++){
       if(t[h][m]!=0) {
         if(count) printf(" ");
          count++;
         printf("%d:%02d",h,m);
       }
    }
  }
   printf("\n");
  return 0;
}

Measured memory_bytes: 1048
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define M_PI 3.14159265358979323846

int main(void) {
    
    long A,B,H,M;
    scanf("%ld %ld %ld %ld",&A,&B,&H,&M);

    // jishin
    long double Arad = ((H*30.0) + (M/2.0)) * M_PI/180.0;
    long double Brad = M * 6.0 * M_PI/180.0;

    long double res = sqrtl(((A * sin(Arad) - B * sin(Brad)) *  (A * sin(Arad) - B * sin(Brad))) + ((A * cos(Arad) - B * cos(Brad)) * (A * cos(Arad) - B * cos(Brad))));
    printf("%.70Lf\n",res);

    return 0;
}

Measured memory_bytes: 2604
N,M = map(int,input().split())

lis = []

now = 1
while now ** 2 <= M:

    if M % now == 0 and now ** 2 != M:
        lis.append(now)
        lis.append(M // now)

    elif now ** 2 == M:
        lis.append(now)
        
    now += 1

maxi = 1
lis.sort()

for i in lis:

    if  M // i >= N:

        maxi = i

print (maxi)


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

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


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    ll n, a, b, c, d; cin >> n >> a >> b >> c >> d;
    bool ok = false;

    rep(i, n) {
        if(-1*d*i+c*(n-i-1) <= b-a && b-a <= -1*c*i+d*(n-i-1)) {
            ok = true;
            break;
        }
    }
    
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

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

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn ll
#define int ll
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };


int w[2000010];
int b[2000010];

signed main() {
	ios::sync_with_stdio(false);
	int n, i;
	string s;
	cin >> n >> s;
	for (int i = 0; i < n + 1; i++) {
		if (s[i] == '#') {
			b[i + 1] = b[i] + 1;
			w[i + 1] = w[i];
		}
		else {
			b[i + 1] = b[i];
			w[i + 1] = w[i] + 1;
		}
	}
	int mi = INF;
	for(int i = 0;i < n +1; i++){
		mi = min(b[i] + w[n] - w[i], mi);
	}
	cout << mi << endl;
	return 0;
}

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

int main(void) {
  int i, j, k, l, ans = 0, n;
  char q[30], s[200];
  scanf("%d", &n);
  scanf("%s", q);
  for(i = 0; i < n; ++i) {
    scanf("%s", s);
    int t = 1;
    for(j = 0; j < strlen(s) - strlen(q) + 1; ++j) {
      for(k = 1; k < strlen(s) / (strlen(q) - 1) + 1; ++k) {
        t = 1;
        for(l = 0; l < strlen(q); ++l) {
          if(j + k * l > strlen(s)|| q[l] != s[j + k * l]) {
            t = 0;
            break;
          }
        }
        if(t) break;
      }
      if(t) break;
    }
    if(t) {
     ++ans;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2668
N, Ma, Mb = [int(i) for i in input().split()]
a, b, c = [], [], []
for i in range(N):
    a_, b_, c_ = [int(i) for i in input().split()]
    a.append(a_)
    b.append(b_)
    c.append(c_)
cost = [[float('inf')] * 401 for _ in range(401)]


def solve():
    max_a, max_b = 1, 1
    for num in range(N):
        for ca in range(max_a, -1, -1):
            for cb in range(max_b, -1, -1):
                cost[ca + a[num]][cb + b[num]] = min(cost[ca][cb] + c[num], cost[ca + a[num]][cb + b[num]])
        cost[a[num]][b[num]] = min(cost[a[num]][b[num]], c[num])
        max_a += a[num]
        max_b += b[num]


solve()
ans = float('inf')
most = ans
for i in range(1, 401):
    for n in range(1, 401):
        if i * Mb is n * Ma:
            ans = min(ans, cost[i][n])
if ans is most:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
    ll n,x;
    cin>>n>>x;
    ll c[n],p[n];
    for(ll i=0;i<n;i++)
    cin>>c[i]>>p[i];
    int max_val=n*1000;
    ll dp[n][max_val+1]={0};

    for(ll i=0;i<=max_val;i++)
    {
        dp[0][i]=INT_MAX;
    }
    dp[0][0]=0;
    if(c[0]<=x)
    dp[0][p[0]]=c[0];
    //cout<<dp[0][c[0]]<<endl;
    for(ll i=1;i<n;i++)
    {
        for(ll j=0;j<=max_val;j++)
        {
            dp[i][j]=dp[i-1][j];//not taking item;
            if(p[i]>j)
            continue;
            dp[i][j]=min(dp[i][j],c[i]+dp[i-1][j-p[i]]);
            
            //if(dp[i][j]<dp[i][j-1] && j>=1)
            //dp[i][j]=dp[i][j-1];
        }
    }
    /*for(int i=0;i<n;i++)
 {   for(int j=0;j<=max_val;j++)
    {
        cout<<dp[i][j]<<" ";
    }
    cout<<endl;
}*/
    ll ans=0;
    for(int i=0;i<=max_val;i++)
    {
        if(dp[n-1][i]<=x)
        ans=i;
    }
    cout<<ans<<endl;
	return 0;
}


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

int Bubble(int A[], int N){
    int cnt=0;
    rep(i,N-1){
        for (int j=N-1; i<j; j--){
            if (A[j]<A[j-1]) {
                swap(A[j],A[j-1]);
                cnt++;
            }
        }
    }
    return cnt;
}

int main(){
    int N; cin >> N;
    int A[101];
    rep(i,N) cin >> A[i];
    int ans;
    
    ans=Bubble(A,N);
    rep(i,N-1){
        cout << A[i] << " ";
    }
    cout << A[N-1] << endl;
    cout << ans << endl;
    
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define vec vector
#define ll long long

int main(void)
{
	ll n, m;
	cin >> n >> m;

	if (m < n * 2) cout << m / 2 << endl;
	else cout << n + (m - n * 2) / 4 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int field[13][13], i, j, left, top;

int main(){
  while(1){
    left = top = -1;
    for(i = 1;i <= 8;i++){
      for(j = 1;j <= 8;j++){
	if(scanf("%1d", &field[i][j]) == EOF) return 0;
	if(field[i][j] == 1 && top == -1){
	  top = i;
	  left = j;
	}
      }
    }
    if(field[top][left + 1] == 1 && field[top + 1][left] == 1 && field[top + 1][left + 1] ==1)
      puts("A");

    if(field[top + 1][left] == 1 && field[top + 2][left] == 1 && field[top + 3][left] ==1)
      puts("B");

    if(field[top][left + 1] == 1 && field[top][left + 2] == 1 && field[top][left + 3] ==1)
      puts("C");

    if(field[top + 1][left - 1] == 1 && field[top + 2][left - 1] == 1 && field[top + 1][left] ==1)
      puts("D");

    if(field[top][left + 1] == 1 && field[top + 1][left + 1] == 1 && field[top + 1][left + 2] ==1)
      puts("E");

    if(field[top + 1][left] == 1 && field[top + 1][left + 1] == 1 && field[top + 2][left + 1] ==1)
      puts("F");

    if(field[top][left + 1] == 1 && field[top + 1][left] == 1 && field[top + 1][left - 1] ==1)
      puts("G");    
  }
}

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

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

    if (a > c) swap(a, c), swap(b, d);
    int r = min(b, d) - c;

    cout << max(r, 0) << endl;

    return 0;
}

Measured memory_bytes: 256
S=9;main(w,a,b,c,d,s){scanf("%d%d%d%d%d",&w,&a,&b,&c,&d);for(a--,b--,c--,d--;w;w--)if(s=abs(a%w-b%w)+abs(a/w-b/w)+abs(c%w-d%w)+abs(c/w-d/w),S>s)S=s;printf("%d\n",S);exit(0);}

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

int main() {
  int N;
  cin >> N;
  vector<int> B(N-1);
  for (int i = 0; i < N-1; i++) cin >> B.at(i);
  int ans = B.at(0) + B.at(N-2);
  for (int i = 0; i < N-2; i++) ans += min(B.at(i), B.at(i+1));
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct work{
	int a;
	int b;
};
int cmp1(work a,work b){
	return a.a<b.a;
}
struct cmp2{
	int operator ()(work a,work b){
		return a.b>b.b;
	}
};
priority_queue<work,vector<work>,cmp2> pq;
work a[100005];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d%d",&a[i].a,&a[i].b);
		a[i].a=m-a[i].a;
	}
	sort(a,a+n,cmp1);
	for(int i=0;i<n;i++){
		if(a[i].a<0)continue;
		if(pq.size()<=a[i].a){
			pq.push(a[i]);
		}else{
			work w=pq.top();
			if(w.b<a[i].b){
				pq.pop();
				pq.push(a[i]);
			}
		}
	}
	long long ans=0;
	while(pq.size()){
		work a=pq.top();
		ans+=a.b;
		pq.pop();
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2168
local n, x = io.read("*n", "*n")
local a = {}
for i = 1, n do a[i] = io.read("*n") end
table.sort(a)
local cnt = 0
for i = 1, n do
  if i == n then
    if a[i] == x then
      cnt = cnt + 1
    end
  else
    if a[i] <= x then
      cnt = cnt + 1
      x = x - a[i]
    else
      break
    end
  end
end
print(cnt)


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int k = n;
	int num = 0;
	while(k!=0)
	{
		num+=k%10;
		k/=10;
	}
	if(n%num==0)
		cout<<"Yes "<<endl;
	else
		cout<<"No "<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define lint long long
using namespace std;
int q,m=1000000007;
lint x,y,f[99]={0,1,1};
int main(){
	scanf("%d",&q);
	rep(i,96)f[i+3]=f[i+1]+f[i+2];
	rep(i,q){
		scanf("%lld %lld",&x,&y);
		if(x>y)swap(x,y);
		if(y<=2){
			printf("1 %d ",y==1?1:x==1?2:4);
			continue;
		}
		rep(j,99){
			if(x<f[j]||y<f[j+1]){
				lint a=x==1?2:1;
				rep(k,j-2){
					lint n=f[j-1]+f[j-3-k]*f[k+2],m=f[j]+f[j-2-k]*f[k+2];
					if(n<=x&&m<=y)a+=(y-m)/n+1;
				}
				if(f[j]<=x){
					a++;
					rep(k,j-2)a+=(x-f[j])/(f[j-2-k]*f[k+2]);
				}
				printf("%d %d ",j-2,a%m);
				break;
			}
		}
	}
}

Measured memory_bytes: 4348
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main(){
    ll n,x; cin>>n>>x;
    ll ans = 0;
    vector<ll[2]>dic(n+1);
    dic[0][0] = dic[0][1] = 1;
    for(int i = 1; i <= n; i++){
        dic[i][0] = dic[i-1][0]*2+1;
        dic[i][1] = dic[i-1][1]*2+3;
    }
    ll ptr = n;
    while(1){
        if(ptr == 0){
            ans++;
            break;
        }
        if(x == 1){
            break;
        }
        if(x > 1 && x <= dic[ptr][1]/2){
            ptr--;
            x--;
            continue;
        }
        if(x == dic[ptr][1]/2+1){
            ans+=dic[ptr-1][0]+1;
            break;
        }
        if(x > dic[ptr][1]/2+1 && x < dic[ptr][1]){
            ans+=dic[ptr-1][0]+1;
            x-=dic[ptr][1]/2+1;
            ptr--;
            continue;
        }
        if(x == dic[ptr][1]){
            ans += dic[ptr][0];
            break;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	int n;
	cin>>n;
	int a1,a2,a3,a4;
	vector<int>x(n,0),y(n,0);
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	vector<int>p1;
	for(int i=0;i<n;i++){
		p1.push_back(x[i]+y[i]);
	}
	sort(p1.begin(),p1.end());
	a1=p1[n-1]-p1[0];
	p1.clear();
	for(int i=0;i<n;i++){
		p1.push_back(x[i]-y[i]);
	}
	sort(p1.begin(),p1.end());
	a2=p1[n-1]-p1[0];
	p1.clear();
	
	for(int i=0;i<n;i++){
		p1.push_back(y[i]-x[i]);
	}
	sort(p1.begin(),p1.end());
	a3=p1[n-1]-p1[0];
	p1.clear();
	
	cout<<max(a1,max(a2,a3))<<endl;
	
}

Measured memory_bytes: 8488