akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MAX 100000
#define NIL -1

typedef struct node{int p,l,r;}node;
node T[MAX];
int n;

void preparse(int a){
    if(a==NIL)return;
    printf(" %d",a);
    preparse(T[a].l);
    preparse(T[a].r);
}

void inparse(int b){
    if(b==NIL)return;
    inparse(T[b].l);
    printf(" %d",b);
    inparse(T[b].r);
}

void postparse(int c){
    if(c==NIL)return;
    postparse(T[c].l);
    postparse(T[c].r);
    printf(" %d",c);
}

int main(){
    int i,v,l,r,root;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        T[i].p=NIL;
    }
    for(i=0;i<n;i++){
        scanf("%d%d%d",&v,&l,&r);
        T[v].l=l;
        T[v].r=r;
        if(l!=NIL)T[l].p=v;
        if(r!=NIL)T[r].p=v;
    }
    for(i=0;i<n;i++) if(T[i].p==NIL) root=i;

    printf("Preorder\n");
    preparse(root);
    printf("\n");
    printf("Inorder\n");
    inparse(root);
    printf("\n");
    printf("Postorder\n");
    postparse(root);
    printf("\n");

    return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> A;
  for(int i=0; i<n; i++){
    int a; cin >> a;
    A.push_back(a);
  }
  sort(A.begin(), A.end(),greater<int>());
  int tmp = A[0]/2;
  int r1=A[n-1], r2=0;
  for(int i=0; i<n; i++){
    if(A[i]>tmp) continue;
    r1 = A[i-1];
    r2 = A[i];
    break;
  }
  int r;
  if(r1<A[0]-r2){
    r = r1;
  }else r=r2;
  cout << A[0] << " " << r << endl;
  return 0;
}

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

  cout << "ABC" << n << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define B begin()
#define E end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> VL;
typedef set<ll> SL;
typedef pair<ll, ll> p2;
const ll M = 1000000007;
const ll M2= 998244353;

void solve()
{
	ll v[6];
	for(int i=1;i<=5;i++)cin>>v[i];
	for(int i=1;i<=5;i++)
	{
		if(v[i]==0){cout<<i<<endl; return ;}
	}	
}
 
int main()
{
    IOS
    int _=1;
    //cin>>_;
    while(_--)
    {
	    solve();
    }
    
    return 0;
}


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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	int n, t, x, y;
  bool result = true;
  cin >> n;
  rep(i, n) {
    cin >> t >> x >> y;
    if (t < x + y || t % 2 != (x + y) % 2) {
      result = false;
    }
  }
  if (result) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll A, B, C, D;
    ll count = 0;
    cin >> A >> B >> C >> D;
    cout << B - A + 1 - (B / C - (A - 1) / C + B / D - (A - 1) / D - (B / (C * D / __gcd(C, D)) - (A - 1) / (C * D / __gcd(C, D)))) << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict as dd

# お約束
INF = float("inf")
MOD = int(1e9 + 7)
def int1(n):
    return int(n) - 1
def parse(*args):
    return tuple(p(v) for p, v in zip(args, input().split()))

# エントリーポイント
def main():
    N, M = parse(int, int)

    AB = dd(int)
    for _ in range(N):
        a, b = map(int, input().split())  # parse(int, int)
        AB[a] += b
    shops = sorted(AB.keys())

    m, cost = M, 0
    for price in shops:
        count = AB[price]
        if m <= count:
            cost += price * m
            break
        else:
            cost += price * count
            m -= count
    print(cost)

main()


Measured memory_bytes: 18136
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <cstdio>
#include <utility>
#include <bitset>
#include <complex>
#include <stack>
#include <tuple>

using namespace std;
typedef long long ll;
typedef tuple<ll,ll,ll> T;


int main(){
	ll sx,sy,tx,ty;
	cin >> sx >> sy >> tx >> ty;
	for(int i=sx;i<tx;i++)
		cout << "R";
	for(int i=sy;i<ty;i++)
		cout << "U";
	for(int i=tx;i>sx;i--)
		cout << "L";
	for(int i=ty;i>sy;i--)
		cout << "D";
	cout << "L";
	for(int i=sy;i<ty+1;i++)
		cout << "U";
	for(int i=sx-1;i<tx;i++)
		cout << "R";
	cout << "DR";
	for(int i=ty;i>sy-1;i--)
		cout << "D";
	for(int i=tx+1;i>sx;i--)
		cout << "L";
	cout << "U";


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
int main(){
	fast;
	int n,m,w1,w2,cnt=0;
	cin>>n>>m;
	string arr1[n],arr2[m];
	for(int i=0;i<n;i++)
		cin>>arr1[i];
	for(int i=0;i<m;i++)
		cin>>arr2[i];
	w1=arr1[0].length();
	w2=arr2[0].length();
	for(int j=0;j+m<=n;j++)				//row
		for(int i=0;i+w2<=w1;i++)		//column
		{
			cnt=0;
			for(int k=0;k<m;k++)
				for(int l=0;l<w2;l++)
					if(arr1[j+k][i+l]==arr2[k][l])
						cnt++;
			if(cnt==m*w2)
			{
				cout<<"Yes";
				return 0;
			}
		}
	cout<<"No";
	return 0;
	
}



Measured memory_bytes: 3668
#include<iostream>
using namespace std;
int a,b,c,f[5][5],i;
int main()
{
	cin>>a>>b>>c;
	f[1][1]=a;
	f[1][2]=b;
	f[2][2]=c;
	while(1)
	{
		i++;
		f[1][3]=i;
		f[3][3]=i+f[1][2]-f[2][2];
		f[3][2]=i+f[1][1]-f[2][2];
		f[3][1]=f[1][1]+f[1][2]+f[1][3]-f[3][2]-f[3][3];
		f[2][1]=f[1][2]+f[1][3]-f[3][1];
		f[2][3]=f[1][1]+f[1][2]-f[3][3];
				if(f[1][1]+f[1][2]+f[1][3]==f[2][1]+f[2][2]+f[2][3]&&f[3][1]+f[3][2]+f[3][3]==f[1][1]+f[2][1]+f[3][1]&&f[1][2]+f[2][2]+f[3][2]==f[1][3]+f[2][3]+f[3][3]&&f[1][1]+f[2][2]+f[3][3]==f[1][3]+f[2][2]+f[3][1])
				{
					cout<<f[1][1]<<" "<<f[1][2]<<" "<<f[1][3]<<endl;
					cout<<f[2][1]<<" "<<f[2][2]<<" "<<f[2][3]<<endl;
					cout<<f[3][1]<<" "<<f[3][2]<<" "<<f[3][3]<<endl;
					return 0;
				}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
double Pi = 3.1415926535897932384626;
 
vector<ll> G1[500005];
vector<ll> G2[500005];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
 
 
ll mod = 1000000007;
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}

 
//ll fact[800005],rfact[800005];
/*
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=800000; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[800000] = rui(fact[800000],mod - 2);
    for(ll i=800000; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,ans,a,b,c,e,g,h,w,i,j,k,q;
ll x[500005],y[500005],z[500005];
bool dp[100005];
bool dame;


int main(){
    cin >> n;
    for(i=0;i<n;i++){
        cin >> x[i];
    }
    ll nowbond = -1;
    for(i=0;i<n-1;i++){
        if(x[i] < x[i+1]){
            continue;
        }else if(x[i] > x[i+1]){
            if(x[i] <= nowbond){
                dame = true;
                break;
            }
            x[i] -= 1;
            nowbond = x[i];
            if(x[i] > x[i+1]){
                dame = true;
                break;
            }
        }
    }
    Yes(!dame);
    return 0;
}












Measured memory_bytes: 29312
#include<bits/stdc++.h>
using namespace std;
int n,x[200001],y[200001],a[200001],b[200001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),a[i]=x[i]+y[i],b[i]=y[i]-x[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	printf("%d",max(a[n]-a[1],b[n]-b[1]));
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int64_t> a(n), b(n);
    for(auto& e : a) cin >> e;
    partial_sum(begin(a), end(a), begin(a));
    int64_t ans = 1e16;
    for(int i = 0; i < n - 1; i++){
        ans = min(ans, abs(a[i] - (a[n-1] - a[i])));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3328
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int K, N;
        Scanner sc = new Scanner(System.in);
        K = sc.nextInt();
        N = sc.nextInt();
        int[] a = new int[N];
        for(int i = 0 ; i < N ; i++)
        {
            a[i] = sc.nextInt();
        }
        int max = 0;
        Arrays.sort(a);
        for(int i = 0 ; i < a.length - 1; i++)
        {
            max = Math.max(max,Math.min(a[i+1]-a[i],K-a[i+1]+a[i]) );

        }
        max=Math.max(max,Math.min(a[N-1]-a[0],K-a[N-1]+a[0]));
        System.out.println(K - max);
    }
}


Measured memory_bytes: 78800
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    x, y = map(int, input().split())
    if x == 1 and y == 1:
        print(1000000)
        exit()
    ans = 0
    if x <= 3:
        ans += (4 - x) * 100000
    if y<=3:
        ans += (4 - y) * 100000
    print(ans)
                    


if __name__ == '__main__':
    main()


Measured memory_bytes: 68460
L=int(input())
l=0
pp=0
tmp=L
while tmp>0:l+=1;pp+=tmp%2;tmp//=2
print(l,l*2-3+pp)
for i in range(1,l):
  print(i,i+1,0)
  a=1<<(i-1)
  print(i,i+1,a)
  if L&a:L-=a;print(i,l,L)

Measured memory_bytes: 3064
#include <stdio.h>

int main()
{
	int i, N, P[200001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(P[i]));
	
	int len[200001] = {}, max = 0;
	for (i = 1; i <= N; i++) {
		len[P[i]] = len[P[i]-1] + 1;
		if (len[P[i]] > max) max = len[P[i]];
	}
	
	printf("%d\n", N - max);
	fflush(stdout);
	return 0;
}

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

int main()
{
  int N;
  cin >> N;
  vector<long long int> a(N);
  for (int i = 0; i < N; i++)
  {
    cin >> a[i];
  }
  vector<long long int> S(N);
  S[0] = a[0];
  for (int i = 1; i < N; i++)
  {
    S[i] = S[i - 1] + a[i];
  }
  long long int ans = 1LL << 60;
  for (int i = 0; i < N - 1; i++)
  {
    long long int x = S[i];
    long long int y = S[N - 1] - x;
    ans = min(ans, abs(x - y));
  }
  cout << ans << endl;
}


Measured memory_bytes: 3456
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
int main(){
  int n,a,i,d[200010];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    hin(a);
  }
  for(i=0;i<n;i++)d[i]=N[hout()];
  for(i=0;i<n;i++)printf("%d\n",N[i+1]>d[n/2-1]?d[n/2-1]:d[n/2]);
  return 0;
}


Measured memory_bytes: 7808
#include <iostream>
#include <string>
#include <vector>
#include <valarray>
#include <algorithm>
#include <utility>

using namespace std;

int main() {
	int n, m, x, ans, temp, cost1 = 0, cost2 = 0;
	cin >> n >> m >> x;
	for (int i = 1; i <= m; i++)
	{
		cin >> temp;
		if (x < temp) {
			cost1++;
		}
		else {
			cost2++;
		}
	}
	ans = min(cost1, cost2);
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<vector<long long>> d(n + 1);
    for(int i = 0; i < n; i++){
        long long x, y;
        cin >> x >> y;
        d[x].emplace_back(y);
    }
    priority_queue<pair<long long, int>> q1;
    priority_queue<long long, vector<long long>, greater<long long>> q2;
    for(int i = 1; i <= n; i++){
        if(d[i].size() == 0) continue;
        sort(rbegin(d[i]), rend(d[i]));
        q1.push({d[i][0], 1});
        for(int j = 1; j < d[i].size(); j++){
            q1.push({d[i][j], 0});
        }
    }
    long long ans = 0, sum = 0, c = 0;
    for(int i = 0; i < k; i++){
        auto p = q1.top();
        q1.pop();
        sum += p.first;
        if(p.second == 0) q2.push(p.first);
        else c++;
    }
    ans = sum + c * c;
    while(!q1.empty() && !q2.empty()){
        auto p = q1.top();
        q1.pop();
        if(p.second == 0) continue;
        sum -= q2.top();
        q2.pop();
        sum += p.first;
        c++;
        ans = max(ans, sum + c * c);
    }
    cout << ans << endl;
    return 0;
}


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

const int MAX = 10020;
int d[MAX + 5];
int a[MAX + 5];

void div(int n, int *d) {
	int val = 1;
	for (int i = 0; i < MAX; i++) {
		d[i] = val / n;
		val %= n;
		val *= 10;
	}
}

void add(int *src, int *dst) {
	for (int i = MAX - 1; i >= 0; i--) {
		dst[i] += src[i];
	}
	for (int i = MAX - 1; i > 0; i--) {
		dst[i - 1] += dst[i] / 10;
		dst[i] %= 10;
	}
}

void fix(int *tmp, int *a) {
	for (int i = 0; i < MAX; i++) tmp[i] = 0;
	tmp[MAX - 5] = 1;
	add(tmp, a);
}

int main() {
	int n, k, m, r;
	while (cin >> n >> k >> m >> r) {
		if (!n) break;
		for (int i = 0; i < MAX; i++) a[i] = 0;
		
		//add 1/n
		div(n, d);
		add(d, a);
		
		if (m == 1) {
			for (int i = n - 1; i > 0; i--) {
				div(n * i, d);
				add(d, a);
			}
		}
		
		//fix(d, a);
		
		cout << a[0] << ".";
		for (int i = 1; i <= r; i++) cout << a[i];
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3160
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <random>
#include <tuple>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
//typedef pair<ll, ll> P;
//typedef pair<ll, pair<ll, ll>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)
#define pb push_back
#define f first
#define s second
//const ll INFL = 1LL << 60;//10^18 = 2^60
const ll INFL = 1LL << 60;
const int INF = 1 << 30;//10^9
ll MOD = 1e9 + 7;
//ll MOD  = 998244353;
vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}
ll inverse(ll x){return pow_mod(x, MOD - 2);};

//最大公約数
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; 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 comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

int main(void){
  ll N, X;
  cin >> N >> X;
  ll a = X, b = N-X;
  ll ans = N;
  while(true){
    ans += (a / b * b) * 2;
    a %= b;
    if(a == 0){
      ans -= b;
      break;
    }
    swap(a, b);
  }
  cout << ans << endl;
}


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

int main()
{
  string S;
  int res=0;
  int len;
  cin >> S;

  char s[110];

  strcpy(s, S.c_str());

  len = (int)S.length();
  
  bool easy=true;
  rep(i,len){
    if(i%2==0 && (s[i]=='L')) easy=false;
    if(i%2==1 && (s[i]=='R')) easy=false;
  }

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



Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

double eps = 1e-9;

int main()	{
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  double max_density = -10.0;
  int max_density_mass = 0;
  int max_density_sugar_mass = 0;
  int sum_water = 0;
  int sum_sugar = 0;
  for (int i = 0; i < 31; i++)	{
    for (int j = 0; j < 31; j++)	{
      for (int k = 0; k < f - (100*(a*i + b*j)); k++)	{
        for (int l = 0; l < f - (100*(a*i + b*j)); l++)	{
          sum_water = 100 * (a*i + b*j);
          sum_sugar = k*c + l*d;
          if (sum_water + sum_sugar > f || e * (sum_water) < 100 * sum_sugar)	{
            continue;
          }
          /*if (sum_water == 0)	{
            continue;
          }*/
          double density = (100.0 * sum_sugar) / (sum_water + sum_sugar);
          if (density > max_density + eps)	{
            max_density = density;
            max_density_mass = sum_sugar + sum_water;
            max_density_sugar_mass = sum_sugar;
          }
        }
      }
    }
  }
  cout << max_density_mass << " " << max_density_sugar_mass << endl;
  return 0;
}

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

int main(){
  int a,b;cin >> a >> b;
  if(a <= 2*b)cout << 0 << endl;
  else cout << a - 2*b << endl;
  return 0;
}


Measured memory_bytes: 256
def solve():
    N = int(input())

    min_length = 11
    for a in range(1, int(N ** 0.5) + 1):
        if N % a == 0:
            min_length = min(min_length, max(len(list(str(a))), len(list(str(N // a)))))

    print(min_length)


solve()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
#define ENDL cout<<endl
#define MAXE(a,b) a=max(a,b)
#define MINE(a,b) a=min(a,b)

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    int from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};
int main(){
    string str;
    cin >> str;
    string ins = str;
    reverse(ALL(str));
    for(int a = 0;a < str.size();a++){
        if(str.at(a)=='b'){
            str.at(a)='d';
            continue;
        }
        if(str.at(a) == 'd'){
            str.at(a)='b';
            continue;
        }
        if(str.at(a)=='p'){
            str.at(a)='q';
            continue;
        }
        if(str.at(a)=='q'){
            str.at(a)='p';
            continue;
        }
    }
    Yes(ins==str);
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;

#define fr(i,n) for(int i=0;i<(n);i++)
#define Fr(i,n) for(int i=0;i++<(n);)
#define ifr(i,n) for(int i=(n)-1;i>=0;i--)
#define iFr(i,n) for(int i=(n);i>0;i--)
 
const ll MOD=1e9+7;

//足し算してmodをとる
ll ad(ll x,ll y=0){
    return (x+y)%MOD;
}

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

 //xのy条
ll pwr(ll x,ll n){
    ll v=1;
    while(n>0){
      if (n%2==1) v=mlt(v, x);
      x=mlt(x,x);
      n/=2;
    }
    return v;
}

 //フェルマーの小定理に夜と、　x^(mod-2)=-1
ll inv(ll x){
    return pwr(x,MOD-2);
}

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

 //inverse_factorial
ll ifc[200010]={1};
ll ifct(ll x){
    if(ifc[x]==0) ifc[x]=inv(fct(x));
    return ifc[x];
}
 
ll comb(ll n,ll r){
    if(n<0 || r<0 || n<r) return 0;
    return mlt(fct(n),mlt(ifct(r),ifct(n-r)));
}
 
int main(){
    ll n,a,b,c,d,f;
    cin>>n>>a>>b>>c>>d;
    ll dp[1010][1010]={};
    fct(1010);
    ifct(1010);
    ifr(i,1010){
        ifc[i]=mlt(i+1,ifc[i+1]);
    }
    dp[b+1][n]=1;
    for(ll i=b;i>=a;i--){
        //cout << i << endl;
        fr(j,n+1){
            dp[i][j]=ad(dp[i][j],dp[i+1][j]);
            f=1;
            Fr(k,c-1) f=mlt(f,comb(j+k*i,i));
            for(ll k=c;k<=d;k++){
                if(j+i*k>n) break;
                f=mlt(f,comb(j+k*i,i));
                dp[i][j]=ad(dp[i][j],mlt(dp[i+1][j+i*k],mlt(f,ifct(k))));
            }
        }
    }
    /*for(int i=2;i<4;i++){
        fr(j,8) cout<<dp[i][j]<<" ";
        cout<<endl;
    }*/
    cout<<dp[a][0]<<endl;
}

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int main(){ _;
  int a,b,c;
  cin>>a>>b>>c;
  int count=0;
  for(int i=a;i<=b;i++)
    if(c%i==0)
      count++;
  cout<<count<<endl;
}

Measured memory_bytes: 1192
package main

import (
	"fmt"
	"math"
)

var A, B int

func main() {
	fmt.Scan(&A, &B)

	if A == 1 && B != 1 {
		fmt.Println("Alice")
	} else if B == 1 && A != 1 {
		fmt.Println("Bob")
	} else if A < B {
		fmt.Println("Bob")
	} else if A > B {
		fmt.Println("Alice")
	} else {
		fmt.Println("Draw")
	}
}

/*  ----------------------------------------  */
func lcm(x, y uint64) uint64 {
	return (x / gcd(x, y)) * y
}

func gcd(x, y uint64) uint64 {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

func combination(x, y int) int {
	return permutation(x, y) / permutation(y, y)
}

func permutation(x, y int) int {
	var ans int = 1
	for i := x - y; 0 < i; i-- {
		ans *= i
	}
	return ans
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }

type XY struct {
	x int
	y int
}

type SortBy [][]int

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


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n; cin >> n;
  vector<int> a(n),b(n);
  cin >> a;
  cin >> b;
  {
    ll sum = 0;
    for(auto e:a)sum += e;
    for(auto e:b)sum -= e;
    if(sum < 0){
      cout << -1 << endl;
      return 0;
    }
  }
  vector<int> v;
  ll d=0;
  int ans = 0;
  for(int i = 0; i < n; ++i){
    if(a[i] < b[i]){
      d += b[i]-a[i];
      ans++;
    } else {
      v.push_back(a[i]-b[i]);
    }
  }
  sort(v.begin(),v.end());
  while(d > 0){
    d -= v.back();
    v.pop_back();
    ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 4584
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
long double a,b,x,c;
long double ans;
int main()
{
	cin>>a>>b>>x;
	if(a*a*b/2<x)
	{
		c=2*b-2*x/(a*a);
		ans=atan(c/a)/pi*180;
		cout<<fixed<<setprecision(10)<<ans;
	}
	else
	{
		c=2*x/a/b;
		ans=atan(b/c)/pi*180;
		cout<<fixed<<setprecision(10)<<ans;
	}
	return 0;
}

Measured memory_bytes: 256
/**
 * @author Finn Lidbetter
 */
import java.util.*;
import java.io.*;
import java.awt.geom.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    String[] s = br.readLine().split(" "); 
    int a = 100*Integer.parseInt(s[0]);
    int b = 100*Integer.parseInt(s[1]);
    int c = Integer.parseInt(s[2]);
    int d = Integer.parseInt(s[3]);
    int e = Integer.parseInt(s[4]);
    int f = Integer.parseInt(s[5]);
    boolean[] water = new boolean[f+1];
    boolean[] sugar = new boolean[f+1];
    water[0] = true;
    sugar[0] = true;
    for (int i=0; i<f+1; i++) {
      if (i-a>=0 && water[i-a]) {
        water[i] = true;
      }
      if (i-c>=0 && sugar[i-c]) {
        sugar[i] = true;
      }
    }
    for (int i=0; i<f+1; i++) {
      if (i-b>=0 && water[i-b]) {
        water[i] = true;
      }
      if (i-d>=0 && sugar[i-d]) {
        sugar[i] = true;
      }
    }
    double bestDens = 0;
    int bestSug = 0;
    int bestMass = a;
    for (int i=1; i<f+1; i++) {
      if (!water[i])
        continue;
      int wat = i;
      for (int j=0; j+i<=f; j++) {
        if (!sugar[j])
          continue;
        int sug = j;
        if (100*sug>wat*e)
          continue;
        if ((100.0*sug)/(sug+wat)>bestDens) {
          bestDens = (100.0*sug)/(sug+wat);
          bestSug = sug;
          bestMass = sug+wat;
        }
      }
    }
    System.out.println(bestMass+" "+bestSug);
  }
}


Measured memory_bytes: 22996
#include <iostream>
//#include <iomanip>
//#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll n ; cin >> n ;
	map<ll,ll> m ;
	m[-1] = 3 ;
	ll ans = 1 ;
	for(int i=0;i<n;i++){
		ll a ; cin >> a ;
		ans = ans*(m[a-1]-m[a])%mod ;
		m[a]++ ;
	}
	cout << ans << endl ;
}


Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <queue>
#include <cmath>
#include <numeric>
using namespace std;

int inf = (1 << 30);
int mod = 1e9 + 7;
int64_t inf64 = (1LL << 60);

template <typename T>
T gcd(T a, T b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

template <typename T>
T lcm(T a, T b) {
    T g = gcd(a, b);
    return a / g * b;
}

bool check(vector<int> a, int index, int key){
    if(a[index] >= key) return true;
    else return false;
}

int lower_bound(vector<int> a, int key){
    int left = -1, right = a.size();
    while(right - left > 1){
        int mid = left + (left + right) / 2;
        if(check(a, mid, key)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){

    int A, B;
    cin >> A >> B;

    if(A >= 13) cout << B << endl;
    else if(A >= 6) cout << (B / 2) << endl;
    else cout << 0 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
long long cnt;
int  A[1000000];
int n;
vector <int> G;

void insertionSort(int A[], int n, int g)
{
    for (int i = g; i < n; i++)
    {
        int v = A[i];
        int j = i-g;
        while (j >= 0 && A[j] > v)
        {
            A[j+g] = A[j];
            j -= g;
            cnt++;
        }
        A[j+g] = v;
    }
}

void shellSort(int A[], int n)
{
    for (int h = 1; ;)
    {
        if (h > n)
            break;
        G.push_back(h);
        h = 3*h+1;
    }
    for (int i = G.size()-1; i >= 0; i--)
    {
        insertionSort(A, n, G[i]);
    }
}
int main()
{
    cin >> n;
    cnt = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
    }

    shellSort(A, n);

    cout << G.size() <<endl;
    for (int i = G.size()-1; i >= 0; i--)
    {
        printf("%d", G[i]);
        if (i) printf(" ");
    }
    printf("\n%d\n", cnt);
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", A[i]);
    }

    return 0;
}



Measured memory_bytes: 7196
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
k = sorted(list(c.keys()))

kl =k[-1]
b = [1] * kl
cnt = 0
for i in k:
    if c[i] == 1 and b[i-1] == 1:
        cnt += 1
    for j in range(1, kl+1):
        if i*j > kl:
            break
        else:
            b[i*j-1] = 0
print(cnt)

Measured memory_bytes: 40068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    int n, k;
    cin >> n >> k;
    vector<ll> h(n), cost(n, INF);
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    cost[0] = 0;
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= k; j++){
            if(i - j >= 0){
                cost[i] = min(cost[i], cost[i - j] + abs(h[i] - h[i - j]));
            }
        }
    }
    cout << cost[n - 1];
}

Measured memory_bytes: 1792
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <string.h>

using namespace std;
int sum(vector<int> &v)
{
	int ret = 0;
	for(int i = 0; i < v.size(); i++)
		ret += v[i];
	return ret;
}
int n,m;

void solve()
{
	typedef vector<int> V;
	V sn(n);
	V sm(m);
	for(int i = 0; i < n; i++)
		cin >> sn[i];

	for(int i = 0; i < m; i++)
		cin >> sm[i];

	int diff = sum(sn) - sum(sm);

	int l = 1000,r = 1000;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(diff == 2 * (sn[i] - sm[j])){
				if(l + r > sn[i] + sm[j])
				{
					l = sn[i]; r = sm[j];
				}
			}
		}
	}

	if(l == 1000)
		cout << -1 << endl;
	else 
		cout << l << ' ' << r << endl;
}

int main()
{
	while(cin >> n >> m,(n||m)){
		solve();
	}

	return 0;
}

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

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

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

    vector<pair<int, int>> vt(n);
    for (int i = 0; i < n; ++i) {
        cin >> vt[i].first >> vt[i].second;
    }
    sort(vt.begin(), vt.end(), cmp);

    bool flag = true;
    long long tot = 0;
    for (int i = 0; i < n; ++i) {
        tot += vt[i].first;
        if (tot > vt[i].second) flag = false;
    }

    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
N = int(input())
 
org_sum = 1 * N * (N+1) // 2
div3 = N // 3
sum3 = 3 * div3 * (div3+1) //2
div5 = N // 5
sum5 = 5 * div5 * (div5+1) // 2
div15 = N // 15
sum15 = 15 * div15 * (div15+1) // 2
 
print(org_sum - sum3 - sum5 + sum15)

Measured memory_bytes: 9180
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;
const int M = 1e9 + 7;
#pragma unused(M)

int main(){
	int n, a, b;
	cin >> n >> a >> b;
	int ans = 0;
	for(int i=0;i<n;i++){
		int t;
		cin >> t;
		if(!(a <= t && t < b)){
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
gets; a = gets.split.map(&:to_i).sort + [Float::INFINITY]
gets; b = gets.split.map(&:to_i).sort + [Float::INFINITY]

i = []
until a.empty?
  if a[0] < b[0]
    a.shift
  elsif a[0] > b[0]
    b.shift
  else
    i << a.shift
    b.shift
  end
end
i[0..-2].each {|x| p x }


Measured memory_bytes: 48900
//0016 Treasure Hunt

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

template<class T>
T DigToRad(T x)
{
	return x / T(180) * 3.14159265358979323846264338327950;
}


int main(void)
{
	double x, y;
	double d, dd, r;
	char dummy;

	x = y = 0;
	d = 90;
	//üÍÍR}ÅæØçêÄ^¦çêé
	while(cin >> r >> dummy >> dd, r)
	{
		x += r*cos(DigToRad(d));
		y += r*sin(DigToRad(d));
		//³ÌÈçEñè
		d -= dd;
	}
	//®ðoÍ
	cout << (int)x << endl << (int)y << endl;
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int m=n,s=0;
  while(m>=10){
    s+=m%10;
    m/=10;
  }
  s+=m;
  if(n%s==0) cout << "Yes\n";
  else cout << "No\n";
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int N;
  cin >> N;
  vector<int> H(N);
  rep(i, N) cin >> H[i];
  int cnt {1};
  int highest {H[0]};
  srep(i,1, N) {
    if (H[i] < highest) {
      ;
    } else {
      ++cnt;
      highest = H[i];
    }
  }
  cout << cnt << '\n';
}


Measured memory_bytes: 256
object Main extends App {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt // 最初の数字を読み取る
    val seq = Seq.fill(n)(sc.nextInt) // nextIntがn回呼ばれる
    var c = 0

    for (i <- 1 to n - 2 ) yield {
        val (p1, p2, p3) = (seq(i - 1), seq(i), seq(i + 1))
        if (p1 < p2 && p2 < p3 || p1 > p2 && p2 > p3) c += 1
        c
    }

    println(c)
}

Measured memory_bytes: 26012
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
  int w,h,n;
  cin>>n>>w>>h;
  int x,y,B=2*(w+h),ans=n;
  char c;
  vector<P> m;
  for(int i=0;i<n;i++){
    cin>>x>>y>>c;
    P A;
    if(c=='S')A=P(x+y,(x-y+B)%B);
    if(c=='E')A=P(w+y+(w-x),w+y-(w-x));
    if(c=='N')A=P(w+h+(w-x)+(h-y),w+h+(w-x)-(h-y));
    if(c=='W')A=P((w*2+h+(h-y)+x)%B,w*2+h+(h-y)-x);
    m.push_back(A);
  }
  sort(m.begin(),m.end());
  for(int i=0;i<n;i++){
    int tp=1,p=m[i].first;
    for(int j=0;j<n;j++){
      int s=m[(i+j)%n].second,g=m[(i+j)%n].first;
      if(!(s>g&&!(g<p&&p<s))&&!(s<g&&s<=p&&p<=g))tp++,p=g;
    }
    ans=min(tp,ans);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3108
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
int INF = INT_MAX / 2;
double EPS = 1e-10;

int main() {
	int N, M, K, Q;
	cin >> N >> M >> K >> Q;
	vector<vector<int> > dp(M + 1, vector<int>(K * 2));
	dp[0][0] = 1;
	for (int t = 0; t < M; t++) {
		vector<int> diff(K * 2 + 1);
		for (int i = 0; i < K * 2; i++) {
			int l = i, r = i + K, x = (ll)dp[t][i] * (N / (K * 2)) % MOD;
			if (t == 0) x = dp[t][i];
			diff[l] = (diff[l] + x) % MOD;
			if (r <= K * 2) diff[r] = (diff[r] - x) % MOD;
			else {
				diff[K * 2] = (diff[K * 2] - x) % MOD;
				diff[0] = (diff[0] + x) % MOD;
				diff[r % (K * 2)] = (diff[r % (K * 2)] - x) % MOD;
			}
		}
		int x = 0;
		for (int i = 0; i < K * 2; i++) {
			x = (x + diff[i]) % MOD;
			dp[t + 1][i] = x;
		}
	}
	while (Q--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		int ans = dp[b][(c - a + N) % (K * 2)];
		if (b == 0) ans = (a == c ? 1 : 0);
		printf("%d\n", (ans + MOD) % MOD);
	}
}

Measured memory_bytes: 50100
package main

import (
	"fmt"
)

func main() {

	var N,K,Q int

	fmt.Scan(&N,&K,&Q)

	A:= SliceInt(Q)

	for i:=0;i<Q;i++{

		fmt.Scan(&A[i])
	}

	result := make(map[int]int)

	for i:=0;i<Q;i++{

		value,exit :=  result[A[i]]

		if exit == true{

			result[A[i]] = value + 1
		
		}else{

			result[A[i]] = 1
		}
	}


	for i:=1;i<=N;i++{

		value,_ := result[i]

		score := K+value-Q

		if score < 1{

			fmt.Println("No")
		
		}else{

			fmt.Println("Yes")
		}

	}

}


//SliceInt 引数サイズのSliceを返す
func SliceInt(a int) []int {

	IntSample := make([]int, a)

	return IntSample
}


Measured memory_bytes: 9344
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main(){
    long long A, B, Q;
    cin >> A >> B >> Q;
    vector<long long> s(A+2), t(B+2), x(Q);
    for(int i=1; i<=A; i++)
        cin >> s[i];
    for(int i=1; i<=B; i++)
        cin >> t[i];

    s[0] = -(1LL<<60);
    s[A+1] = +(1LL<<60);
    t[0] = -(1LL<<60);
    t[B+1] = +(1LL<<60);

    for(int i=0; i<Q; i++)
        cin >> x[i];

    for(int i=0; i<Q; i++){
        int id0 = lower_bound(s.begin(), s.end(), x[i]) - s.begin();
        long long d = s[id0];
        long long a = s[id0-1];

        int id1 = lower_bound(t.begin(), t.end(), x[i]) - t.begin();
        long long c = t[id1];
        long long b = t[id1-1];

        //cerr << a << " " << b << " " << x[i] << " " << c << " " << d << endl;

        long long ans = 1LL<<60;
        ans = min(ans, max(c, d)-x[i]);
        ans = min(ans, x[i]-min(a, b));
        ans = min(ans, x[i]+d-2*b);
        ans = min(ans, -x[i]-b+2*d);
        ans = min(ans, x[i]+c-2*a);
        ans = min(ans, -x[i]-a+2*c);
        cout << ans << endl;
    }


    return 0;
}

Measured memory_bytes: 3712
import sys
sys.setrecursionlimit(10**9)

def LI(): return [int(x) for x in sys.stdin.readline().split()]

n,q = LI()

v = [[] for i in range(n)]
for i in range(n-1):
	a,b = LI()
	a -= 1
	b -= 1
	v[a].append(b)
	v[b].append(a)

f = [0]*n
for i in range(q):
	p,x = LI()
	p -= 1
	f[p] += x

def dfs(x,d,s):
	for y in v[x]:
		if d[y]:
			s += f[y]
			ans[y] = s
			d[y] = 0
			dfs(y,d,s)
			s -= f[y]

ans = [0]*n
d = [1]*n
d[0] = 0
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans)

Measured memory_bytes: 238536
#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[4000]; int memo[4000][4000];
int saiki(int a, int b) {
	if (memo[a][b] != -1)return memo[a][b];
	if (a > b)return 0;
	if ((b - a) & 1) {//??????
		int S = 0;
		if (::a[a] >= ::a[b + 1]&&::a[b+1]!=0)S = saiki(a + 1, b);
		if (::a[a - 1] <= ::a[b]&&::a[a-1]!=0)S = max(S, saiki(a, b - 1));
		return memo[a][b]=S;
	}
	else {//??????
		return memo[a][b]=max(saiki(a + 1, b) + ::a[a], saiki(a, b - 1) + ::a[b]);
	}
	return 0;
}
signed main() {
	memset(memo, -1, sizeof(memo));
	int b;
	cin >> b;
	for (int c = 0; c < b; c++) {
		scanf("%lld", &a[c]);
		a[b + c] = a[c];
	}
	int MAX = 0;
	for (int d = 1; d <= b; d++) {
		MAX = max(MAX, saiki(d, d + b - 1));
	}
	cout << MAX << endl;
}

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

#define long long long int
using namespace std;


#ifdef JUDGE
std::ifstream cin("input.txt");
std::ofstream cout("output.txt");
#else
using std::cin;
using std::cout;
#endif

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(6);


    int n;
    cin >> n;
    int start = ceil(n / 1.08);
    int get = (int) (start * 1.08);
    if (n == get) {
        cout << start;
    } else {
        cout << ":(";
    }

    return 0;


}


Measured memory_bytes: 256
/*
 *                             _ooOoo_
 *                            o8888888o
 *                            88" . "88
 *                            (| -_- |)
 *                            O\  =  /O
 *                         ____/`---'\____
 *                       .'  \\|     |//  `.
 *                      /  \\|||  :  |||//  \
 *                     /  _||||| -:- |||||-  \
 *                     |   | \\\  -  /// |   |
 *                     | \_|  ''\---/''  |   |
 *                     \  .-\__  `-`  ___/-. /
 *                   ___`. .'  /--.--\  `. . __
 *                ."" '<  `.___\_<|>_/___.'  >'"".
 *               | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *               \  \ `-.   \_ __\ /__ _/   .-` /  /
 *          ======`-.____`-.___\_____/___.-`____.-'======
 *                             `=---='
 *          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 *                     佛祖保佑        永无BUG
 */

#include<bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 50;
int n, x, y, t, k, cnt;
int last[N];
ll z, dis[N];
bool vis[N];
struct orz {
    int v, next;
    ll w;
} e[N * 4];

struct stu {
    int s, dis;

    bool operator<(const stu &a) const {
        return dis > a.dis;
    }
};

void add(int u, int v, ll w) {
    cnt++;
    e[cnt].v = v;
    e[cnt].next = last[u];
    last[u] = cnt;
    e[cnt].w = w;
}

void Dij(int s) {
    priority_queue<stu> q;
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; i++) dis[i] = 1e16;
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    stu now;
    now.dis = 0;
    now.s = s;
    q.push(now);
    while (!q.empty()) {
        now = q.top();
        q.pop();
        if (vis[now.s]) continue;
        vis[now.s] = 1;
        for (int i = last[now.s]; i; i = e[i].next) {
            int to = e[i].v;
            if (dis[to] > dis[now.s] + e[i].w) {
                dis[to] = dis[now.s] + e[i].w;
                stu nex;
                nex.s = to;
                nex.dis = dis[to];
                q.push(nex);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    scanf("%d%d", &t, &k);
    Dij(k);
    //cout<<"sd"<<dis[k]<<endl;
    while (t--) {
        scanf("%d%d", &x, &y);
        printf("%lld\n", dis[x] + dis[y]);
    }
    return 0;
}


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

int main() {
	int n, k;
	cin >> n >> k;
	int a[n];
	for (int i = 0;i < n;i++)scanf("%d", &a[i]);
	int num[n] = {};
	for (int i = 0;i < n;i++)num[a[i]-1]++;
	sort(num, num + n);
	reverse(num, num + n);
	int ans = 0;
	for (int i = 0;i < k;i++)ans += num[i];
	cout << n - ans << endl;
}

Measured memory_bytes: 1792
N = int(input())
H = list(map(int,input().split()))
mlist = []
hmax = max(H)
count = 0
divide = 1
for i in range(hmax+1):
    for n,k in enumerate(H):
        if k >= i:
            mlist.append(n)
            
    for p in range(len(mlist)-1):
        if mlist[p + 1] - mlist[p] != 1:
            divide+=1
    count+=divide
    divide = 1
    mlist.clear()
print(count-1)

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

using namespace std;

int main() {
	int a, b;
	scanf("%d", &a);
	string str;
	cin >> str;
	scanf("%d", &b);
	if (str[0] == '-') {
		cout << a - b << endl;
	} else {
		cout << a + b << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    char ans = '1';
    long k;
    int i;
    cin >> s >> k;
    for (int i = 0; i < k; ++i)
    {
        if (s[i] != '1')
        {
            ans = s[i];
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Mon Jul 29 02:16:51 2019

@author: matsui
"""

N=int(input())
A=input().split()
B=input().split()

count=0
carry=0
for i in range(N):
    if int(A[i]) > int(B[i]) +carry:
        count+=int(B[i]) +carry
        carry=0
    else:
        count+=int(A[i])
        if carry > int(A[i]):
            carry=int(B[i])
        else:  
            carry= int(B[i])+carry-int(A[i])
        
if int(A[-1]) > carry:
    count+=carry
else:
    count+=int(A[-1])
print(count)

        

Measured memory_bytes: 19412
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 100010;

int n;
int dp[N];
int h[N];

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif

  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &h[i]);
  dp[2] = abs(h[1] - h[2]);
  for (int i = 3; i <= n; ++i)
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
  printf("%d\n", dp[n]);

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 1024