akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n;cin>>n;
    vector<int> x(n+1),ans(n*n,0);
    queue<int> que;
    vector<pair<int,int>> v;
    for(int i=1;i<=n;i++){
        cin>>x[i];x[i]--;
        v.push_back(make_pair(x[i],i));
    }

    sort(ALL(v));

    for(int i=0,idx=0;i<n*n;i++){
        if(idx<n and v[idx].first==i){
            if((int)que.size()<v[idx].second-1){
                cout<<"No"<<endl;
                return 0;
            }

            rep(i,v[idx].second-1){
                ans[que.front()]=v[idx].second;
                que.pop();
            }
            ans[i]=v[idx].second;
            idx++;
        }else{
            que.push(i);
        }
    }

    vector<int> w;
    for(auto &p:v){
        rep(_,n-p.second) w.push_back(p.second);
    }

    for(int i=0,idx=0;i<n*n and idx<(int)w.size();i++){
        if(ans[i]==0){
            ans[i]=w[idx];idx++;
        }
    }


    auto check=[&](){
        vector<int> cnt(n+1,0);
        rep(i,n*n){
            cnt[ans[i]]++;
            if(cnt[ans[i]]==ans[i]){
                if(x[ans[i]]!=i){
                    return false;
                }
            }
        }
        return true;
    };

    if(check()){
        cout<<"Yes"<<endl;
        rep(i,n*n){
            cout<<ans[i]<<(i+1==n*n?"\n":" ");
        }
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3452
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>
#include <random>

using namespace std;

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

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define ALL(a)  (a).begin(),(a).end()
#define UNIQUE(a)  (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define PB push_buck
#define EACH(i,c) REP(i,(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
#define RREP(i,n) RFOR(i,n,0)

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";

const int INF = 1e9;
const double EPS = 1e-10;

int n, m, k, s, t;
VI es;
string str;

int main() {
	cin >> str;
	int ans = 0;
	REP(i,6){
		if(str[i]=='1')ans++;
	}
	cout<<ans<<endl;
}


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

int main() {

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

  if(a<=b){
    for(int i=0;i<b;i++){
      cout << a;
    }
  }else{
    for(int i=0;i<a;i++){
      cout << b;
    }
  }

  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
typedef long long ll;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

struct cmp_c {
  bool operator()(int a, int b) {
    return a > b;
  }
} cmp;

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int N = S.length();
//  vector<int> s(N);
//  REP(i,N) {
//    if(S[i] == 'R') s[i] = 1;
//    else s[i] = -1;
//  }
  vector<int> v(N, 0);
  vector<int> RL;
  int init = 0;
  while(true) {
    auto pos = S.find("RL", init);
    if (pos != std::string::npos) {
      RL.pb((int)pos);
      init = (int)pos + 1;
    }
    else break;
  }

  REP(i,N) {
    if(S[i] == 'R') {
      auto itr = lower_bound(ALL(RL),i);
      int d = *itr - i;
      if (d % 2 == 0) ++v[*itr];
      else ++v[*itr+1];
    } else {
      auto itr = lower_bound(RL.rbegin(),RL.rend(),i, [](const int &a, const int &b){ return a > b; });
      int d = abs(*itr - i);
      if (d % 2 == 0) ++v[*itr];
      else ++v[*itr+1];
    }
  }

  for(auto e: v) {
    cout << e << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <ctype.h>

using namespace std;
using ll=long long;

int main()
{
    int a, b, c;
    
    cin >> a >> b >> c;
    
    if ((b - a) == (c - b))
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
    
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <stdio.h>
#include <stdlib.h>
__attribute__((always_inline)) __inline__
long long max(long long x,long long y) {
	return ((y-x>>64-1)&(x^y))^y;
}
typedef struct {int w,s,v;}node;
int cmp(const void *a,const void *b){
	return (((node*)a)->w+((node*)a)->s)-(((node*)b)->w+((node*)b)->s);
}
node b[1005];
long long dp[20005],ans;
int main(n)
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
		scanf("%d%d%d",&b[i].w,&b[i].s,&b[i].v);
	qsort(b,n,sizeof(node),cmp);
	for (int i=0;i<n;i++) for (int j=b[i].s;j>=0;j--)
		dp[j+b[i].w]=max(dp[j+b[i].w],dp[j]+b[i].v);
	for (int i=0;i<=20000;i++) ans=max(ans,dp[i]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 380
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <iterator>
#include <queue>
#include <utility>
#include <stack>

using namespace std;

typedef long long Long;

#define MN 100000
#define MQ 100000
int N, Q;
int parent[MN + 1];
bool marked[MN + 1];
pair<int, int> queries[MQ];

int root(int x) {
    if (marked[x]) return x;
    return parent[x] = root(parent[x]);
}
void merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return;
    parent[x] = y;
}

bool input() {
    scanf("%d %d", &N, &Q);
    if (N == 0 && Q == 0) return false;
    for (int i = 2; i <= N; i++) {
        int p;
        scanf("%d", &p);
        parent[i] = p;
    }
    memset(marked, false, N + 1);
    marked[1] = true;
    for (int i = 0; i < Q; i++) {
        char t; int n;
        scanf("%*[ \t\r\n]%c %d", &t, &n);
        if (t == 'M') {
            if (marked[n]) {
                queries[i] = make_pair('X', 0);
                continue;
            }
            marked[n] = true;
        }
        queries[i] = make_pair(t, n);
    }
    return true;
}

void solve() {
    Long ans = 0;
    for (int q = Q - 1; q >= 0; q--) {
        pair<int, int> query = queries[q];
        if (query.first == 'Q') {
            ans += root(query.second);
        } else if (query.first == 'M') {
            marked[query.second] = false;
        }
    }
    printf("%lld\n", ans);
}

int main() {
    while (input()) {
        solve();
    }
    return 0;
}

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

using namespace std;
#define ll long long
const ll INF = 1e18L + 5;

void mn (ll &a, ll b) {
    a = min (a, b);
}
void mx (ll &a, ll b) {
    a = max (a, b);
}

int main () {

    int N, W;
    scanf("%d %d", &N, &W);

    vector < int > v (N), w (N);

    for (int i = 0; i < N; ++i) scanf("%d %d", &w[i], &v[i]);
    
    ll sum = 0;
    for (int x : v) sum += x;

    vector < ll > dp (sum + 1, INF);

    dp[0] = 0;

    for (int i = 0; i < N; ++i) {

        for (int j = sum - v[i]; j >= 0; --j    ) {
            mn (dp[j + v[i]], dp[j] + w[i]);
        }

    }

    ll ans = 0;

    for (int i = 0; i <= sum; ++i) if (dp[i] <= W) ans = max (ans, (ll) i);

    printf("%lld\n", ans);



    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, a[100008], b[100008];

int main(){
	cin >> n;
	for(ll i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
	}
	
	ll ans = 0;
	for(ll i = n; i >= 1; i--){
		ans += (b[i]-((a[i]+ans)%b[i]))%b[i];
	}
	
	cout << ans << endl;
	return 0;
}

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

int a,b;
int d,r;
double f;

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

  return 0;
  
}

Measured memory_bytes: 3260
import collections
S = input()[::-1]

d = 1
M = []
for s in S:
    M.append(int(s)*d % 2019)
    d *= 10
    d %= 2019

S = [0]
for m in M:
    S.append((S[-1]+m) % 2019)

C = collections.Counter(S)

ans = 0
for v in C.values():
    ans += v*(v-1)//2
print(ans)


Measured memory_bytes: 87660
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

int main() {
    int h,w;
    cin >> h >> w;
    int a[h][w];
    rep(i,h) rep(j,w) cin >> a[i][j];

    vector<int> ans;
    int tmp;
    rep(i,h) {
        rep(j,w) {
            tmp = 0;
            rep(k,h) rep(l,w) tmp += min(abs(i-k),abs(j-l)) * a[k][l];
            ans.push_back(tmp);
        }
    }
    sort(ans.begin(),ans.end());
    cout << ans.at(0) << endl;
}


Measured memory_bytes: 3140
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    int N=sc.nextInt();
    long x=0;
    for(int i=1;i<N+1;i++){
      if(i%3==0){continue;}
      if(i%5==0){continue;}
      x=x+i;}
    System.out.println(x);
  }
}


Measured memory_bytes: 35820
#include <bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)

#define ll long long

int main() {

  ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("input.in", "r", stdin);


    int x;
    cin>>x;
    if (x == 0) cout<<"1\n";
        else cout<<"0\n";

    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
cout<<fixed<<setprecision(10);

 int K, N;
  cin >> K >>N;
  vector<int> A(N);
  for (int i=0;i<N;i++){
  	cin>>A.at(i);
  }
	
  int sukima=0;
  sukima=max(sukima,K+A.at(0)-A.at(N-1));
  for (int i=0;i<N-1; i++){
    sukima=max(sukima, A.at(i+1)-A.at(i));
  }
  
  cout << K-sukima <<endl;
  
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

using namespace std;

#define all(c) c.begin(),c.end()
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

typedef long long ll;
typedef vector<int> vi;


template<typename T>
ostream& operator<<(ostream& os,const vector<T>& val){
    os << "[ ";
    for(typename vector<T>::const_iterator it=val.begin();
        it != val.end();++it){
        os << *it << " ";
    }
    os << "]";
    return os;
}

int s(int a,int b){
    return ceil(1.0*a / b);
}

int main(){
    int l,a,b,c,d;
    cin >> l >> a >> b >> c >> d;
    cout << l-max(s(a,c),s(b,d)) << endl;
    return 0;
}

Measured memory_bytes: 1164
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int n,ch[5252];
vector<int> g[5252];
ll a[5252],dp[2][5252][5252],sp[2][5252][5252];

void solve(int u, int p = -1){
	int i,j,k,v;
	for(i=(g[u].l_ength()-1); i>=0; --i){
		v = g[u][i];
		if(v==p){
			continue;
		}
		solve(v,u);
	}
	for(i=(g[u].l_ength()-1); i>=0; --i){
		v = g[u][i];
		if(v==p){
			g[u].erase(g[u].begin()+i);
			break;
		}
	}
	sp[0][0][1] = a[u];
	sp[1][0][1] = (a[u]>0ll)?a[u]:INFLL;
	ch[u] = 1;
	for(i=0; i<g[u].l_ength(); ++i){
		v = g[u][i];
		for(j=1; j<=ch[u]; ++j){
			for(k=1; k<=ch[v]; ++k){
				sp[0][i+1][j+k-1] = INFLL;
				sp[0][i+1][j+k] = INFLL;
				sp[1][i+1][j+k-1] = INFLL;
				sp[1][i+1][j+k] = INFLL;
			}
		}
		for(j=1; j<=ch[u]; ++j){
			for(k=1; k<=ch[v]; ++k){
				sp[0][i+1][j+k-1] = min(sp[0][i+1][j+k-1],sp[0][i][j]+dp[0][v][k]);
				sp[1][i+1][j+k-1] = min(sp[1][i+1][j+k-1],sp[1][i][j]+dp[1][v][k]);
				if(dp[0][v][k] < 0ll || dp[1][v][k] < INFLL){
					sp[0][i+1][j+k] = min(sp[0][i+1][j+k],sp[0][i][j]);
					sp[1][i+1][j+k] = min(sp[1][i+1][j+k],sp[1][i][j]);
				}
			}
		}
		ch[u] += ch[v];
	}
	for(i=0; i<=ch[u]; ++i){
		dp[0][u][i] = sp[0][g[u].l_ength()][i];
		dp[1][u][i] = sp[1][g[u].l_ength()][i];
	}
}

int main(void){
	int i,u,v;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a[i];
	}
	for(i=1; i<n; ++i){
		cin >> u >> v;
		--u; --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	solve(0);
	for(i=1; i<=ch[0]; ++i){
		if(dp[0][0][i] < 0ll || dp[1][0][i] < INFLL){
			cout << (i-1) << endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 826240
n,y=map(int,input().split())
c=0
for i in range(n+1):
    for j in range(n-i+1):
        if 9*i+4*j+n==y//1000:
            print(i,j,n-i-j)
            c=1
            break
    if c==1:
        break
if c!=1:
    print(-1,-1,-1)

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    string S;
    cin >> S;
    ll N = S.size();

    // dp[i][j]最初i文字を使って，13で割ったあまりがjであるものの数
    ll dp[N + 1][13];
    rep(i, N+1){rep(j, 13){dp[i][j] = 0;}}
    dp[0][0] = 1;
    rep(i, N){
        int c;
        if (S[i] == '?'){c = -1;}else{c = S[i] - '0';}
        rep(j, 10){
            if (c != -1 && c != j){continue;}
            rep(ki, 13){
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki];
            }
        }
        rep(j, 13){dp[i+1][j] %= MOD;}
    }
    cout << dp[N][5] << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 10704
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define mod 1000000007
#define all(x) (x).begin(),(x).end()
 
#define REP(i, n) for(int i = 0; i < (n); i++)
#define NREP(i, n) for(int i = 1; i <= (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.size()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(),v.end());
#define VGSORT(v) sort(v.begin(),v.end(),greater<int>());
#define REV(a) reverse(begin(a),end(a));

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cout << fixed << setprecision(7);
////////////////////////////////////////////
	int a,b,c;
    cin >> a >> b;
    c=a+b;
    if(c%2==0)
    {
      cout << c/2 << endl;
    }else{
      cout << "IMPOSSIBLE" << endl;
    }
///////////////////////////////////////////
}


Measured memory_bytes: 256
package main

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

var stdin = initStdin()
 
func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func scanInt() int {
	stdin.Scan()
	i, _ := strconv.Atoi(stdin.Text())
	return i
}

func scanStr() string {
	stdin.Scan()
	return stdin.Text()
}

type ia []int

func (ia ia)Len() int {
	return len(ia)
}
func (ia ia)Swap(i, j int) {
	ia[i], ia[j] = ia[j], ia[i]
}
func (ia ia)Less(i, j int) bool {
	return ia[i] < ia[j]
}

func main() {
	p := scanInt()
	q := scanInt()
	r := scanInt()
	arr := ia {p, q, r}
	sort.Sort(arr)
	fmt.Println(arr[0] + arr[1])
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    
    vector<int> mizu(3010, 0);
    mizu[0] = 1;
    rep(i, 3010) {
        if (!mizu[i]) continue;
        if (i + 100 * A < 3010) mizu[i + 100 * A] = 1;
        if (i + 100 * B < 3010) mizu[i + 100 * B] = 1;
    }
    vector<int> water;
    REP(i, 3010) {
        if (mizu[i] && i <= F) water.push_back(i);
    }
    vector<int> sato(3010, 0);
    sato[0] = 1;
    rep(i, 3010) {
        if (!sato[i]) continue;
        if (i + C < 3010) sato[i + C] = 1;
        if (i + D < 3010) sato[i + D] = 1;
    }
    vector<int> sugar;
    rep(i, 3010) {
        if (sato[i] && i <= F) sugar.push_back(i);
    }
    
    double max_nodo = 0;
    int max_water = 0, max_sugar = 0;
    for (int w : water) {
        auto iter = upper_bound(sugar.begin(), sugar.end(), min(w / 100 * E, F - w)) - 1;
        int s = *iter;
        if ((double)s / (s + w) >= max_nodo) {
            max_water = w;
            max_sugar = s;
            max_nodo = (double)s / (s + w);
        }
    }
    cout << max_water + max_sugar << " " << max_sugar << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <utility>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF=1<<29;
ll mod=1000000007;

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

	ll N;
	cin>>N;
	ll dp[N+1][4][4][4];
	for(int i=0;i<N+1;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					dp[i][j][k][l]=0;
				}
			}
		}
	}

	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				if(i==0 && j==1 && k==2) continue;
				if(i==0 && j==2 && k==1) continue;
				if(i==1 && j==0 && k==2) continue;
				dp[3][i][j][k]=1;
			}
		}
	}

	for(int i=4;i<=N;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					for(int m=0;m<4;m++){
						if(j==0 && k==1 && l==2) continue;
						if(j==0 && k==2 && l==1) continue;
						if(j==1 && k==0 && l==2) continue;
						if(m==0 && k==1 && l==2) continue;
						if(m==0 && j==1 && l==2) continue;
						dp[i][j][k][l]+=dp[i-1][m][j][k];
						dp[i][j][k][l]%=mod;
					}
				}
			}
		}
	}

	ll Ans=0;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				Ans+=dp[N][i][j][k];
				Ans%=mod;
			}
		}
	}
	cout<<Ans<<endl;
	return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	a := make([]int, n)
	for i := range a {
		sc.Scan()
		a[i], _ = strconv.Atoi(sc.Text())
	}
	c := 0
	for i := 0; i < n; i++ {
		c = a[c] - 1
		if c == 1 {
			fmt.Println(i + 1)
			return
		}
	}
	fmt.Println("-1")
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int x,y,p;
};
int R,C;
int N;
int x[MAXN][2],y[MAXN][2];
vector<node> v[4];
int sta[MAXN * 2],top;
bool on_u(int x,int y) {
    return x == 0;
}
bool on_l(int x,int y) {
    return x != 0 && x != R && y == 0;
}
bool on_r(int x,int y) {
    return x != 0 && x != R && y == C;
}
bool on_d(int x,int y) {
    return x == R;
}
bool check(int x,int y) {
    return on_u(x,y) || on_l(x,y) || on_r(x,y) || on_d(x,y);
}
int id(int x,int y) {
    if(on_u(x,y)) return 0;
    else if(on_r(x,y)) return 1;
    else if(on_d(x,y)) return 2;
    else return 3;
}
void Solve() {
    read(R);read(C);read(N);
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 0 ; j <= 1 ; ++j) {read(x[i][j]);read(y[i][j]);}
	if(check(x[i][0],y[i][0]) && check(x[i][1],y[i][1])) {
	    v[id(x[i][0],y[i][0])].pb((node){x[i][0],y[i][0],i});
	    v[id(x[i][1],y[i][1])].pb((node){x[i][1],y[i][1],i});
	}
    }
    sort(v[0].begin(),v[0].end(),[](node a,node b){return a.y < b.y;});
    sort(v[1].begin(),v[1].end(),[](node a,node b){return a.x < b.x;});
    sort(v[2].begin(),v[2].end(),[](node a,node b){return a.y > b.y;});
    sort(v[3].begin(),v[3].end(),[](node a,node b){return a.x > b.x;});
    for(int i = 0 ; i < 4 ; ++i) {
	for(auto t : v[i]) {
	    if(sta[top] == t.p) --top;
	    else sta[++top] = t.p;
	}
    }
    if(top) puts("NO");
    else puts("YES");
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


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

int main(){
  int n;
  cin >> n;
  vector<int>vec(n);
  for(int i=0;i<n;i++){
    cin >> vec[i];
  }
  
  sort(vec.begin(),vec.end());
  
  cout << vec[n-1]-vec[0];
}
  

Measured memory_bytes: 256
//don't go gentle into
// the goodnight.

#include<bits/stdc++.h>
using namespace std;

#define int       long long
#define ll        long long
#define fr        first
#define sec       second
#define pi        3.141592653589793
#define M         1000000007
#define mod       998244353
#define maxint    2147483647
#define minint    -2147483648
#define maxll     9223372036854775807
#define minll     -9223372036854775808
#define meme0(a)  memset(a,0,sizeof(a));
#define meme1(a)  memset(a,-1,sizeof(a));
#define i_m_speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define open      freopen("input.txt","r",stdin);
#define close     freopen("output.txt","w",stdout);
#define v_int     vector<int >
#define v_ll      vector<long long >
#define pb        push_back
#define mk        make_pair
//upper_bound(begin(),end(),key)
//lower_bound(begin(),.end(),key);

ll expo(ll x , ll n , ll m){
    if(n==0)
        return 1;
    else if(n%2==0)
        return expo((x*x)%m , n/2 , m);
    else
        return (x*expo((x*x)%m,(n-1)/2,m))%m;

}
string toBinary(ll n)
{
    std::string r;
    while(n!=0){
        r=(n%2==0 ?"0":"1")+r;
        n/=2;
    }
    return r;
}
void solve(){
    int a,b;
    cin >>a >> b;
    
    cout << a*b << endl;
    return;
}
int32_t main(){
    i_m_speed
    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }

    return 0;
}


Measured memory_bytes: 3628
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=300;
const int MAXK=300;

int n,k,MOD;

int C[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXK+1]; // dp[i][j] = # ways for i elements with maximum value of j

void inc(int &a,int b) { if((a+=b)>=MOD) a-=MOD; }
void run() {
	scanf("%d%d%d",&n,&k,&MOD);

	REPE(i,n) { C[i][0]=C[i][i]=1; FOR(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; }

	REPE(j,k) dp[0][j]=1;
	FORE(i,1,n) FORE(j,1,k) {
		// first element has value j -> it is the last to be removed
		inc(dp[i][j],dp[i-1][j]);
		// all elements have value < j
		inc(dp[i][j],dp[i][j-1]);
		FORE(sz,1,i-1) { // first sz elements have value < j and then the next element has value j
			int ways=(ll)dp[sz][j-1]*C[i][sz]%MOD*dp[i-sz-1][j]%MOD;
			inc(dp[i][j],ways);
		}
		//printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
	}
	printf("%d\n",dp[n][k]);
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 896
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


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;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b) {
  return b ? GCD(b,a%b) : a;
}


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n,m;
  cin>>n>>m;
  vector<bool> v(n);
  vector<ll> cnt(n);
  rep(i,n){
    v[i]=false;
    cnt[i]=0;
  }
  rep(i,m){
    ll a;
    string b;
    cin>>a>>b;
    a--;
    if(b=="AC") v[a]=true;
    if(!v[a] && b=="WA") cnt[a]++;
  }
  ll ans1=0,ans2=0;
  rep(i,n){
    if(v[i]) ans1++;
    if(v[i]) ans2+=cnt[i];
  }
  cout<<ans1<<' '<<ans2<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
typedef long long LL;

int n;
struct Nod {
	LL a, b, c;
} nod[N << 1];
double ans[N];

int stk[N]; int top;
bool chk(LL X1, LL Y1, LL X2, LL Y2, LL X3, LL Y3) {
	pair<LL, LL> v1 = make_pair(X2-X1, Y2-Y1);
	pair<LL, LL> v2 = make_pair(X3-X2, Y3-Y2);
	return v1.second * v2.first  < v2.second * v1.first;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%lld", &nod[i].a);
	}
	for (int i = 1; i <= n; i ++) {
		scanf("%lld", &nod[i].b);
		nod[i+n] = nod[i];
	}
	LL mx = 0, mxpos = 0;
	for (int i = 1; i <= n; i ++) {
		if (nod[i].a > mx) {
			mx = nod[i].a, mxpos = i;
		}
	}
	for (int i = mxpos; i < mxpos + n; i ++) {
		nod[i - mxpos + 1] = nod[i];
	}
	nod[n+1] = nod[1]; nod[n+2] = nod[2];
	nod[1].c = nod[2].c = 0;
	for (int i = 3; i <= n + 1; i ++) {
		nod[i].c = 2 * nod[i-1].c - nod[i-2].c + 2 * nod[i-1].b;
	}
	for (int i = 1; i <= n + 1; i ++) {
		// printf("%d / (%d, %lld), c = %lld\n", i, i, nod[i].a - nod[i].c, nod[i].c);
		while (top >= 2 && chk(stk[top-1], nod[stk[top-1]].a - nod[stk[top-1]].c, stk[top], nod[stk[top]].a - nod[stk[top]].c, i, nod[i].a - nod[i].c)) 
			-- top;
		stk[++top] = i;
	}
	for (int i = 1; i < top; i ++) {
		int l = stk[i], r = stk[i+1];
		ans[l] = nod[l].a - nod[l].c;
		ans[r] = nod[r].a - nod[r].c;
		// printf("[%d, %d] (%.5f %.5f)\n", l, r, ans[l], ans[r]);
		for (int j = l; j <= r; j ++) {
			ans[j] = ans[l] + (ans[r] - ans[l]) / (r - l) * (j - l);
			// printf("j = %d, ans = %.7f  %lld\n", j, ans[j], nod[j].c);
		}
	}
	double sum = 0;
	for (int i = 1; i <= n; i ++) {
		ans[i] += nod[i].c;
		sum += ans[i];
		// printf("ans[%d] = %.5f\n", i, ans[i]);
	}
	printf("%.8f\n", sum / n);
}
/*
c[x-1] + c[x+1] - 2c[x] = 2b[x]
c[x+1] - c[x] = c[x] - c[x-1] + 2b[x]
c[1] c[2] c[3]  c[4] .......... c[n]  c[1]
    A  A+2b[2] A+2b[3] ...  A+2b[n-1] A+2b[n]

E[x] = 1/2 E[x-1] + 1/2 E[x+1] - b[x] 
2E[x] = E[x-1] + E[x+1] - 2b[x]
2C[x] = C[x-1] + C[x+1] - 2b[x]
F[x] = E[x] + C[x]
2F[x] = F[x-1] + F[x+1]



E[1]=100, C[1]=0
E[2]=0, C[2]=0
E[3]=100, C[3]=200

*/


Measured memory_bytes: 15400
import java.io._
import scala.io.Source

object Main {
  var size = 0
  var size2 = 0
  var count = 0
  val out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(FileDescriptor.out), "ASCII"), 512)

  def swap(a:Array[Int],i:Int,j:Int,ai:Int,aj:Int) =  {
    a(i) = aj
    a(j) = ai
  }

  def up(a:Array[Int], i:Int):Unit = {
    val j = i/2
    if(j>0 && a(j-1) < a(i-1)) { swap(a,j-1,i-1,a(j-1),a(i-1)); up(a,j) }
  }

  def down(a:Array[Int], i:Int, temp:Int):Unit = {
    var largest = i
    val j = (i+1)*2
    if(j>size) a(i) = temp
    else {
       val max = if(j==size) j-1 else if(a(j-1) >= a(j)) j-1 else j
       if(a(max)>temp) { a(i) = a(max); down(a,max,temp) }
       else a(i) = temp
    }
  }

  def extract(a:Array[Int]):Int = {
    val max = a(0)
    if(size>0) {
      a(0) = a(size-1)
      size -= 1
      down(a,0,a(0))
      a(size) = 0
    }
    max
  }

  def insert(a:Array[Int], n:Int) = {
    a(size) = n
    size += 1
    up(a,size)
  }

  def main(args:Array[String]) = {
    val a = new Array[Int](2000000)
    var s = ""
    Source.stdin.getLines.takeWhile(_!="end").foreach { s =>
      val op = s.split(" ")
      if(op(0) == "insert") {
        insert(a, op(1).toInt)
      } else if(op(0) == "extract") {
        val x = extract(a).toString
        out.write(x)
        out.write("\n")
        if(count<100) count += 1
        else {
         out.flush
         count = 0
        }
      }
    }
    out.flush
  }
}

Measured memory_bytes: 461640
#include <bits/stdc++.h>
#define N 105
#define x first
#define y second
using namespace std;
typedef pair<int,int> P;
int n,ans,use[N],where[N];
bool visit[N];
P red[N],blue[N];
vector<int>g[N];
bool dfs(int curr)
{
    visit[curr]=true;
    for(auto &it : g[curr]){
        if(!use[it]||!visit[use[it]]&&dfs(use[it])){
            where[curr]=it;
            use[it]=curr;
            return true;
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>red[i].x>>red[i].y;
    for(int i=1;i<=n;i++)
        cin>>blue[i].x>>blue[i].y;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
        if(red[i].x<blue[j].x&&red[i].y<blue[j].y)
            g[i].push_back(j);
    for(int i=1;i<=n;i++){
        if(!where[i]){
            fill(visit,visit+N,false);
            if(dfs(i))ans++;
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 5;
int main()
{
	int m,d;
	cin >> m >> d;
	int sum = 0;
	for(int i = 2; i <= 9; i++){
		for(int j = 2; j <= 9; j++){
			if(i * j <= m && i * 10 + j <= d){
				sum++;
			}
		}
	}
	cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>

using namespace std;

int main(void) {
	int k;
	char S[101], cp_S[101];
	cin >> k;
	cin >> S;
	int len = strlen(S);

	if (len <= k) {
		cout << S << endl;
	}
	else {
		int i;
		for (i = 0; i < k; i++) {
			cp_S[i] = S[i];
		}
		cp_S[i] = '\0';
		cout << cp_S << "..." << endl;
	}



	return 0;
}

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

struct data{int start,end;};
int main()
{
  int N,Q;
  string name;
  int year;
  string s;
  int a,b;
  data d;
  map<string,data> m;
  map<string,data>::iterator it;
  while(cin>>N>>Q,N|Q){
    m.clear();
    while(N-->0){
      cin>>s>>a>>b;
      d.end=b;
      d.start=b-a+1;
      m[s]=d;
    }
    while(Q-->0){
      name="Unknown";
      year=0;
      cin>>a;
      for(it=m.begin();it!=m.end();it++){
	if(a < it->second.start || it->second.end < a)continue;
	year = a - it->second.start + 1;
	name = it->first;
      }
      cout<<name;
      if(name!="Unknown")cout<<" "<<year;
      cout<<endl;
    }
  }
}

Measured memory_bytes: 996
package main

import "fmt"

func main()  {
	var n, m, c int
	fmt.Scan(&n, &m, &c)
	nums := ScanNums(m)
	ans := 0
	for i := 0; i < n; i++ {
		sourceCodes := ScanNums(m)
		sum := c
		for j, n := range sourceCodes{
			sum += n * nums[j]
		}
		if sum > 0 {
			ans++
		}
	}
	fmt.Println(ans)
}

func ScanNums(len int) (nums []int) {
	var num int
	for i := 0; i < len; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	return
}



Measured memory_bytes: 512
MAXC = 10000

def solve(n,ma,mb,list)
  dp = []

  #init dp
  all_a = 0
  all_b = 0
  list.each do |a,b,c|
    all_a += a
    all_b += b
  end

  dp[0] = []
  (0..all_a).each do |a|
    dp[0][a] = Array.new(all_b+1,MAXC)
  end
  dp[0][0][0] = 0

  (1..n).each do |k|
    dp[k] = []
    ea,eb,ec = list[k-1]

    (0..all_a).each do |a|
      dp[k][a] = []
      (0..all_b).each do |b|
        nosel = dp[k-1][a][b]
        unless (a >= ea && b >= eb)
          dp[k][a][b] = nosel
        else
          sel = (dp[k-1][a - ea][b - eb] + ec)
          if sel < nosel
            dp[k][a][b] = sel
          else
            dp[k][a][b] = nosel
          end
        end
      end
    end

  end

  ansR = Rational(ma,mb)
  ans = MAXC
  f = 0
  loop do
    f += 1
    ta = f * ma
    tb = f * mb
    break if ta > all_a || tb > all_b
    ans = dp[n][ta][tb] if ans > dp[n][ta][tb]
  end

  return -1 if ans == MAXC
  return ans
end

def main
  n,ma,mb = gets.split.map(&:to_i)
  list = []
  n.times do
    list << gets.split.map(&:to_i)
  end
  puts solve(n,ma,mb,list)
end

main


Measured memory_bytes: 24188
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a,b,c,d,cnt=0;cin>>a>>b>>c>>d;
  while(a>0&&c>0) {
    if(cnt%2==0) c-=b;
    else a-=d;
    cnt++;
  } 
  puts((a>0)?"Yes":"No");
  return 0;
}


Measured memory_bytes: 3640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var nk = Console.ReadLine().Split(' ').Select(num => int.Parse(num)).ToArray();
            var k = nk[1];

            Console.WriteLine(Console.ReadLine().Split(' ')
                .Select(num => long.Parse(num))
                .OrderByDescending(x => x)
                .Skip(k)
                .Sum());
        }
    }
}

Measured memory_bytes: 50232
#include <stdio.h> 
#define MAX 100 
int main() {
  int i,j,a,b,n,g[MAX], m[MAX][MAX],u;  
  scanf("%d",&n);
  
  for (i=1;i<=n;i++){
    scanf("%d%d",&g[i-1],&g[i]);
  }
  for(i=1;i<=n;i++) m[i][i]=0;
  for(b=2;b<=n;b++) {
    for(i=1;i<=n-b+1;i++) {
      j=i+b-1;
      m[i][j]=10000000;
      for (a=i;a<=j-1;a++) {
	u=m[i][a]+m[a+1][j]+g[i-1]*g[a]*g[j];
	if(m[i][j]>u) m[i][j]=u; 
      }
    }
  }
  printf("%d\n",m[1][n]);  
  return 0;
}

Measured memory_bytes: 632
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define vec vector<pii>
#define pb push_back
#define iter vector<pii>::iterator
#define _sort(x,y) sort(x.begin(),x.end(),y)
#define N 262150
#define inf 1e9
#define eps 1e-8
using namespace std;
inline int read(){
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return 0-x;
}
 
inline int cmpx(pii x,pii y){return x.fi<y.fi;}
inline int cmpy(pii x,pii y){return x.se<y.se;}
int n,son[N][2],w[N][2],d[N],mn[N];
ll mid;
vec f[N];
 
void solve(vec &ls, vec &rs, vec &s) {
    if(ls.size()>rs.size()) swap(ls,rs);    //启发式合并
    if(!s.empty()) s.clear();
     
    _sort(ls,cmpy), _sort(rs,cmpx);
    mn[0]=rs[0].se;
    for(int i=1; i<rs.size(); i++) mn[i]=min(mn[i-1],rs[i].se);
    for(int p1=0, p2=rs.size()-1; p1<ls.size(); ++p1) {
        while(p2>=0 && ls[p1].se+rs[p2].fi>mid) --p2;
        if(~p2) s.pb(mp(ls[p1].fi,mn[p2]));
    }
     
    _sort(ls,cmpx),_sort(rs,cmpy);
    mn[0]=rs[0].fi;
    for(int i=1; i<rs.size(); i++) mn[i]=min(mn[i-1],rs[i].fi);
    for(int p1=0, p2=rs.size()-1; p1<ls.size(); ++p1) {
        while(p2>=0 && ls[p1].fi+rs[p2].se>mid) --p2;
        if(~p2) s.pb(mp(mn[p2],ls[p1].se));
    }
}
 
void dfs(int x){
    if(!son[x][0]) return f[x].pb(mp(0,0)),void();
    int l=son[x][0], r=son[x][1];
    dfs(l), dfs(r);
    vec &ls=f[l], &rs=f[r];
    for(iter i=ls.begin(); i!=ls.end(); ++i) i->fi+=w[x][0], i->se+=w[x][0];
    for(iter i=rs.begin(); i!=rs.end(); ++i) i->fi+=w[x][1], i->se+=w[x][1];
    solve(ls,rs,f[x]);
    ls.clear(), rs.clear();
}
 
signed main(){
    n=read();
    int x,y;
    for(int i=2; i<=n; i++) x=read(), y=read(), son[x][d[x]]=i, w[x][d[x]++]=y;
    ll l=0, r=131070ll*131072/2, ans=r;
    while(l<=r) {
        mid=(l+r)>>1;
        dfs(1);
        if(f[1].empty()) l=mid+1;
        else ans=mid, r=mid-1;
        f[1].clear();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 38648
#include <bits/stdc++.h>
        #include<iostream>
        #include<cstdio>
        #include<vector>
        #include<queue>
        #include<map>
        #include<cstring>
        #include<string>
        #include <math.h>
        #include<algorithm>
    //    #include <boost/multiprecision/cpp_int.hpp>
        #include<functional>
  //    #define int long long
        #define inf  1000000007
        #define pa pair<int,int>
#define ll long long
        #define pal pair<ll,ll>
        #define ppa pair<int,pa>
        #define  mp make_pair
        #define EPS (1e-10)
        #define equals(a,b) (fabs((a)-(b))<EPS)

        using namespace std;

        class Point{
        	public:
        	double x,y;
        	Point(double x=0,double y=0):x(x),y(y) {}
        	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
        	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
        	Point operator * (double a) {return Point(x*a,y*a);}
        	Point operator / (double a) {return Point(x/a,y/a);}
        	double absv() {return sqrt(norm());}
        	double norm() {return x*x+y*y;}
        	bool operator < (const Point &p) const{
        		return x != p.x ? x<p.x: y<p.y;
        	}
        	bool operator == (const Point &p) const{
        		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
        	}
        };
        typedef Point Vector;

        struct Segment{
        Point p1,p2;
        };

    double hen(Vector a){
    if(fabs(a.x)<EPS && a.y>0) return acos(0);
    else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
    else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
    else if(fabs(a.y)<EPS && a.x>0) return 0.0;
    else if(a.y>0) return acos(a.x/a.absv());
    else return 2*acos(0)+acos(-a.x/a.absv());

    }

        double dot(Vector a,Vector b){
        	return a.x*b.x+a.y*b.y;
        }
        double cross(Vector a,Vector b){
        	return a.x*b.y-a.y*b.x;
        }
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        //----------------kokomade temple------------



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

//printf("%.10f\n",ans);


Measured memory_bytes: 896
#include <iostream>
#include <algorithm>

using namespace std;


int main(){
	/*input*/
	int r, d, x2000;
	cin >> r >> d >> x2000;


	/*calc*/
    int ans[10 + 1];
    ans[0] = x2000;

    for(int i = 1; i <= 10; i++){
    	ans[i] = r*ans[i-1] - d;
    }
	/*output*/
	for(int i = 1; i <= 10; i++){
	   	cout<<ans[i]<<endl;
	}
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String N = sc.next();
        
        int l = N.length();
        
        for(int i=0;i<l;i++){
            System.out.print("x");
        }
    }
}


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

int main()
{
    int n;
    scanf("%i", &n);
    long long a[n];
    scanf("%lld", &a[0]);
    long long sum = 0, mx = a[0];
    for(int i = 1; i < n; i++){
        scanf("%lld", &a[i]);
        if(a[i] < mx) sum += (mx-a[i]);
        else mx = a[i];
    }
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 5364
import sys
import math

input = sys.stdin.readline

K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        n = math.gcd(i, j)
        for l in range(j, K + 1):
            if len(set([i, j, l])) == 1:
                ans += math.gcd(n, l)
            elif len(set([i, j, l])) == 2:
                ans += (math.gcd(n, l) * 3)
            else:
                ans += (math.gcd(n, l) * 6)

print(ans)


Measured memory_bytes: 9212
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        StringTokenizer st=new StringTokenizer(br.readLine());
        int count=0;
        int temp;
        for(int i=0;i<n;i++){
            temp=Integer.parseInt(st.nextToken());
            if(temp%2!=0){ count++; }
        }
        System.out.println((count%2==0) ? "YES":"NO");
    }
}


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

vector<ll> bitconversion(ll i, ll n, ll N){
    ll x = 1;
    rep(j,N){
        x *= n;
    }
    vector<ll> vec(N);
    rep(j,N){
        x /= n;
        vec[j] = i / x;
        i -= x * vec[j];
    }
    return vec;
}

ll iterative_square_method(ll i, vector<ll> &vec, ll N, ll mod){
    ll ans = 1;
    rep(j,N){
        if (vec[N - 1 - j] == 1) ans = (ans * i) % mod;
        i = (i * i) % mod;
    }
    return ans;
}

int main(){
    ll N,K;
    cin >> N >> K;
    ll ans = 0;
    vector<ll> vec_count(100002, 0);
    for (ll i = K; i >= 1; i--){
        ll cnt = K / i;
        vector<ll> binary = bitconversion(N, 2, 20);
        ll ans_sub = iterative_square_method(cnt, binary, 20, 1000000007);
        for (ll j = 2; j * i <= K; j++){
            ans_sub = (ans_sub + 1000000007 - vec_count[i * j]) % 1000000007;
        }
        vec_count[i] = ans_sub;
        ans = (ans + ans_sub * i) % 1000000007;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4048
def compute_current_score(previous_t_score, previous_a_score, current_t_ratio, current_a_ratio):
    initial_divisor = max(previous_t_score // current_t_ratio, previous_a_score // current_a_ratio)
    current_t_score = 0
    current_a_score = 0
    while(True):
        current_t_score = initial_divisor * current_t_ratio
        current_a_score = initial_divisor * current_a_ratio
        if((current_t_score >= previous_t_score) and (current_a_score >= previous_a_score)):
            break
        initial_divisor += 1
    return current_t_score, current_a_score

N = int(input())
t_score, a_score = list(map(int, input().strip().split()))

for  n in range(N-1):
    t_ratio, a_ratio = list(map(int, input().strip().split()))
    t_score, a_score = compute_current_score(t_score, a_score, t_ratio, a_ratio)
    
print(t_score + a_score)

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

typedef pair <int, int> PII;
typedef vector<PII> VPII;
typedef vector<VPII> VVPII;
bool U[2000];
int L[1001];

int main( void )
{
    int N, M;
    while ( cin >> N >> M && N && M ) {
        VVPII T( 10001 );
        memset( L, -1, sizeof(L) );
        int r, q;
        int t, n, m, s, ts, te;
        cin >> r;
        for ( int i = 0; i < r; i++ ) {
            cin >> t >> n >> m >> s;
            if ( s ) {
                L[n] = t;
            } else {
                T[m].push_back( PII( L[n], t ) );
                L[n] = -1;
            }
        }
        cin >> q;
        for ( int i = 0; i < q; i++ ) {
            memset( U, false, sizeof(U) );
            int answer = 0;
            cin >> ts >> te >> m;
            for ( VPII ::iterator it = T[m].begin(); it != T[m].end(); it++ ) {
                PII r = *it;
                if ( r.second < ts || r.first > te ) continue;
                for ( int j = r.first; j < r.second; j++ ) U[j] = true;
            }
            for ( int j = ts; j < te; j++ ) if ( U[j] ) answer++;
            cout << answer << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 0
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))


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

#define ll long long
#define ar array
#define vi vector<int>
#define INF 1000000000

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll X; cin >> X;				
	ll P = 100, years = 0;
	while(P < X){
		P += P / 100;
		years++;
	}
	cout << years << endl;
	return 0;
}


Measured memory_bytes: 3624