akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e9)
using namespace std;
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;

ll pow_mod(ll N, ll M, ll P){
    if(P == 0) return 1;
    if(P % 2 == 1){
        return N * pow_mod(N,M,P-1) % M;
    }else{
        ll tmp = pow_mod(N,M,P/2);
        return tmp * tmp % M;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    cin >> N >> M;
    const ll MOD = 1e9 + 7;
    ll x[100010], y[100010];
    rep(i,0,N){
        cin >> x[i];
    }
    rep(i,0,M){
        cin >> y[i];
    }
    ll ans_x = 0, ans_y = 0;
    rep(i,0,N){
        ans_x += (2 * i - N + 1) * x[i];
        ans_x %= MOD;
    }
    rep(i,0,M){
        ans_y += (2 * i - M + 1) * y[i];
        ans_y %= MOD;
    }
    ll ans = ans_x * ans_y % MOD;
    print(ans);

}


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

typedef long long ll;

const int MOD = 1e9 + 7;
const int INF = 0x3F3F3F3F;
const ll INFLL = 0x3F3F3F3F3F3F3F3FLL;

int n;
int points[112345][3];
int ans[112345][3];

int main(){
	
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0 ; i < n ; i ++)
		cin >> points[i][0] >> points[i][1] >> points[i][2];
	
	ans[0][0] = points[0][0];
	ans[0][1] = points[0][1];
	ans[0][2] = points[0][2];
	
	for(int i = 1 ; i < n ; i ++){
		ans[i][0] = max(ans[i - 1][1], ans[i - 1][2]);
		ans[i][0] += points[i][0];
		
		ans[i][1] = max(ans[i - 1][0], ans[i - 1][2]);
		ans[i][1] += points[i][1];
		
		ans[i][2] = max(ans[i - 1][0], ans[i - 1][1]);
		ans[i][2] += points[i][2];
	}
	
	cout << max(ans[n - 1][0], max(ans[n - 1][1], ans[n - 1][2])) << "\n";
	
	return 0;
}

Measured memory_bytes: 5964
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String A = sc.next();
        String B = sc.next();
        String C = sc.next();
        int ans = 0;
        for(int i = 0; i < N; i++){
            if(A.charAt(i) != B.charAt(i) && A.charAt(i) != C.charAt(i) && B.charAt(i) != C.charAt(i)) ans += 2;
            else if(A.charAt(i) != B.charAt(i) && A.charAt(i) != C.charAt(i) && B.charAt(i) == C.charAt(i)) ans += 1;
            else if(A.charAt(i) != B.charAt(i) && A.charAt(i) == C.charAt(i) && B.charAt(i) != C.charAt(i)) ans += 1;
            else if(A.charAt(i) == B.charAt(i) && A.charAt(i) != C.charAt(i) && B.charAt(i) != C.charAt(i)) ans += 1;
        }

        System.out.println(ans);
        sc.close();
    }

}


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

using namespace std;

namespace mod {

template <class T, int M>
class MInt;

template <class T, int M>
MInt<T, M> Pow(const MInt<T, M> &base, T exp);

template <class T, int M>
MInt<T, M> Inv(const MInt<T, M> &n);

template <class T, int M>
class MInt {
  T n_;

 public:
  MInt() : n_(0) {}
  MInt(T n) : n_((n % M + M) % M) {}

  MInt &operator+=(const MInt &rhs) {
    n_ += rhs.n_;
    if (n_ >= M) {
      n_ -= M;
    }

    return *this;
  }

  MInt &operator-=(const MInt &rhs) {
    n_ += M - rhs.n_;
    if (n_ >= M) {
      n_ -= M;
    }

    return *this;
  }

  MInt &operator*=(const MInt &rhs) {
    n_ = n_ * rhs.n_ % M;
    return *this;
  }

  MInt &operator/=(const MInt &rhs) { return (*this) *= Inv(rhs); }

  T Get() { return n_; }
};

template <class T, int M>
MInt<T, M> operator-(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res -= rhs;
}

template <class T, int M>
MInt<T, M> operator+(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res += rhs;
}

template <class T, int M>
MInt<T, M> operator*(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res *= rhs;
}

template <class T, int M>
MInt<T, M> operator/(const MInt<T, M> &lhs, const MInt<T, M> &rhs) {
  MInt<T, M> res(lhs);
  return res /= rhs;
}

template <class T, int M>
MInt<T, M> Pow(const MInt<T, M> &base, T exp) {
  if (exp == 0) {
    return 1;
  }

  auto a = Pow(base, exp / 2);
  a *= a;
  if (exp % 2 == 1) {
    a *= base;
  }

  return a;
}

template <class T, int M>
MInt<T, M> Inv(const MInt<T, M> &n) {
  return Pow(n, static_cast<T>(M - 2));
}
}  // namespace mod

const int md = 1e9 + 7;
using MInt = mod::MInt<long long, md>;

class BinCoef {
  vector<MInt> f;

 public:
  BinCoef(int n) : f(n + 1) {
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i++) {
      f[i] = MInt(i) * f[i - 1];
    }
  }

  MInt NCM(int n, int m) {
    if (n < m) {
      return 0;
    }
    return f[n] * mod::Inv(f[m] * f[n - m]);
  }

  MInt HCM(int n, int m) { return NCM(n + m - 1, m); }
};
using ll = long long;

int main(int argc, const char *argv[]) {
  // 9^n
  ll n;
  cin >> n;
  BinCoef bc(n);
  MInt ans = mod::Pow(MInt(10), n) - mod::Pow(MInt(9), n) * MInt(2) +
             mod::Pow(MInt(8), n);
  cout << ans.Get() << '\n';
  return 0;
}

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

int main() {
    int d; cin >> d;
    int n = 26;
    vector<int> c(n);
    rep(i,n) cin >> c[i];
    vector<vector<int>> s(d,vector<int>(n));
    rep(i,d){
        rep(j,n){
            cin >> s[i][j];
        }
    }
    vector<int> t(d);
    rep(i,d){
        cin >> t[i];
        t[i]--;
    }

    vector<int> last(n,1);
    int64_t happy = 0;
    rep(i,d){
        rep(j,n){
            happy -= c[j]*last[j];
        }
        happy += c[t[i]]*last[t[i]]+s[i][t[i]];
        cout << happy << endl;

        last[t[i]] = 1;
        rep(j,n){
            if(j != t[i]) last[j]++;
        }
    }

}


Measured memory_bytes: 3648
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int h,w,d[1000][1000],k,x,y,ans=1<<30,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
queue<pair<int,int> > q;
char s[1000][1000];
int main()
{
	scanf("%d%d%d",&h,&w,&k);
	memset(d,-1,sizeof d);
	for(int i=0;i<h;i++)
	{
		scanf("%s",s[i]);
		for(int j=0;j<w;j++)
			if(s[i][j]=='S')x=i,y=j;
	}
	q.push(make_pair(x,y));
	d[x][y]=k;
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;q.pop();
		ans=min(ans,min(min(x,y),min(h-x-1,w-y-1)));
		if(!x||!y||x==h-1||y==w-1)ans=0;
		else for(int r=0;r<4;r++)
		{
			int tx=x+dx[r],ty=y+dy[r];
			if(s[tx][ty]!='#'&&d[tx][ty]<d[x][y]-1)
			{
				d[tx][ty]=d[x][y]-1;
				q.push(make_pair(tx,ty));
			}
		}
	}
	printf("%d\n",(ans+k-1)/k+1);
	return 0;
}

Measured memory_bytes: 4992
#include<stdio.h>
int main(void){
	int W,H,x,y,r;
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	if(x-r>=0&&y-r>=0&&x+r<=W&&y+r<=H)
	printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 2676
// 三井住友信託2019
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main(){
    int x; cin >> x;
    int n = x/100, m = x%100;
    int now = 0;
    for(int i = 5; i > 0; i--){
        if(m == 0) break;
        now += m/i;
        m -= (m/i)*i;
        if(now > n){
            cout << 0 << endl;
            return 0;
        }
    }
    cout << 1 << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll X, Y;

int main() {
	cin >> X >> Y;
	if (abs(X - Y) <= 1) {
		cout << "Brown" << endl;
	}
	else {
		cout << "Alice" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)
#define MAX 10000000
#define MOD 1000000007
 
 
vector<long> fac(MAX);
vector<long> finv(MAX);
vector<long> inv(MAX);
 
//template functions
/////////////////////////
void Cominit(){
  fac.at(0)=fac.at(1)=1;
  finv.at(0)=finv.at(1)=1;
  inv.at(1)=1;
  for(long i=2;i<MAX;i++){
      fac.at(i)=(fac.at(i-1)*i)%MOD;
      inv.at(i)=MOD-inv.at(MOD%i)*(MOD/i)%MOD;
      finv.at(i)=finv.at(i-1)*inv.at(i)%MOD;
  }
}

long facComb(long N,long M){// nCm%
if(N<M) return 0;
if(N<0||M<0) return 0;
return fac.at(N)*(finv.at(M)*finv.at(N-M)%MOD)%MOD;
}

long Comb(long N,long M){// nCm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
for(long i=M;i>0;i--){
    ans=ans/i;
}
return ans;
}

long Perm(long N,long M){// nPm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
return ans;
}

long GCM(long A,long B){
            long W,r;
    if(A<B){

        W=B;
        B=A;
        A=W;
    }
    while(A%B!=0){
        r=A%B;
        A=B;
        B=r;
    }
    return B;
}
long LCM(long A,long B){
    return (A*B)/GCM(A,B);
}

long upDiv(long a,long b){
  return (a+b-1)/b;
}

long strtolong(string str){
istringstream ss;
ss=istringstream(str);
long num;
ss>>num;
return num;
}

long chartolong(char ch){
long num;
num=ch-'0';
return num;
}

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


//Answer


int main() {
 
string N;
cin>>N;
vector<long> X(N.size());
long ans=0;

for(int i=0;i<N.size();i++){
X.at(i)=chartolong(N.at(i));
ans=(ans+X.at(i))%9;
}
if(ans==0){
    cout<<"Yes"<<endl;
}else{
    cout<<"No"<<endl;
}
 
 
}




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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;

// 今 i 桁目を見ていて、 現在の値が cur, 見るのは n 桁の数のとき、
// three, five, seven がそれぞれ出ているとき true である場合の
// パターン数
ll dfs(ll i, ll cur, ll n, bool three, bool five, bool seven) {
    if(i >= n) {
        if(cur <= N && three && five && seven) { return 1; }
        return 0;
    }
    ll ret = 0;
    ret += dfs(i+1, cur * 10 + 3, n, true, five, seven);
    ret += dfs(i+1, cur * 10 + 5, n, three, true, seven);
    ret += dfs(i+1, cur * 10 + 7, n, three, five, true);
    return ret;
}

signed main()
{
    cin >> N;
    ll ans = 0;
    for(int i = 3; i < 10; ++i) {
        ans += dfs(0, 0, i, false, false, false);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 384
#!/usr/bin/env python
# coding: utf-8

# In[19]:


import numpy as np


# In[49]:


N = int(input())
H = list(map(int, input().split()))
H = np.array(H)


# In[50]:


count = 1

for i in range(1,N):
    #print(i)
    if np.all(H[i] >= H[:i]):
        count += 1

print(count)


# In[ ]:






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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)


int main()
{
  ll n, c=0;
  cin >> n;
  forll(i, 0, n){
	c += (i + 1);
	if (c == n){
	  forll(j, 0, i+1)
		cout << j + 1 << endl;
	  return 0;
	}
	if (c > n){
	  forll(j, 0, i+1){
		if (j+1 != c - n)
		  cout << j + 1 << endl;
	  }
	  return 0;
	}
  }
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;


int main() {

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

	Int N, M;
	cin >> N >> M;

	vector<Int> dp(N + 3, 0);
	vector<Int> stair(N+3,0);
	vector<Int> a(M, 0);
	dp[0] = 1;

	for (Int i = 0; i < M; i++)cin >> a[i];

	for (Int i = 0; i < M; i++)stair[a[i]]++;

	for (Int i = 0; i < N; i++) {
		if (stair[i + 1] == 0) {
			dp[i + 1] += dp[i];
			dp[i + 1] %= 1000000007;
		}
		if (stair[i + 2] == 0) {
			dp[i + 2] += dp[i];
			dp[i + 2] %= 1000000007;
		}
	}

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

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int t[] = new int[a];
        
        for(int i = 0; i < a; i++){
            t[i] = sc.nextInt();
        }
        for(int i = a; i> 0;i--){
            
            int count = 0;
            
            for(int j = 0; j<a;j++){   
                if(t[j] >= i){
                    count++;
                }
            }
            
            if(i <= count){
                System.out.println(i);
                break;
            }
                
        }
    }
}


Measured memory_bytes: 26308
x, n = map(int, input().split())
if n == 0:
    print(x)
    exit()

p = list(map(int, input().split()))
for i in range(100):
    if not x-i in p:
        print(x-i)
        exit()
    elif not x+i in p:
        print(x+i)
        exit()


Measured memory_bytes: 9152
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007

using namespace std;


int main(void){
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	int a[n];
	rep(i,n)a[i]=0;
	rep(i,n-1){
		if(s[i+1]=='C' && s[i]=='A')a[i+1]=a[i]+1;
		else a[i+1]=a[i];
	}
	
	int l,r;
	rep(i,q){
		cin>>l>>r;
		cout<<a[r-1]-a[l-1]<<endl;
	}

	return 0;

}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

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


int main() {
	string S;
	cin >> S;
	if (S == "ABC") { cout << "ARC" << endl; }
	if (S == "ARC") { cout << "ABC" << endl; }
	
	system("PAUSE");
}


Measured memory_bytes: 3616
import sys
input = sys.stdin.readline
import numpy as np
from decimal import *

n = int(input())

Li = [[int(e) for e in input().split()] for _ in range(n)]

Li = np.array(Li)
LA = Li[:,0]
LB = Li[:,1]

LA.sort()
LB.sort()


if n %2 == 0: # n = 2m
    idx =n //2 -1
    min = (LA[idx] + LA[idx+1])
    max = (LB[idx] + LB[idx+1])

else: # n = 2m - 1
    idx =(n+1) //2 -1
    min = LA[idx]
    max = LB[idx]

print(max - min +1 )


Measured memory_bytes: 63220
//Try until you reach your goal
#include <bits/stdc++.h>
using namespace std;
# define ll long long
# define endl "\n"
# define str string
# define vll vector<ll>
# define pb push_back
# define mll map<ll,ll>
# define mp make_pair
# define ff first
# define ss second
# define pll pair<ll,ll>
# define f(x,y) for(int x=0;x<y;x++)
ll x,y;
vector<vector<ll>> v;
vll visited;
ll ans=0;
void dfs(ll p){
    visited[p]=1;
    for(ll j=0;j<v[p].size();j++){
        if(visited[v[p][j]]==0){
            dfs(v[p][j]);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>x>>y;
    v.resize(x);
    for(ll i=0;i<y;i++){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        v[a].pb(b);
        v[b].pb(a);
    }
    visited.resize(x,0);
    for(ll i=0;i<x;i++){
        if(visited[i]==0){
            ans++;
            dfs(i);
        }
    }
    cout<<ans-1;
    return 0;
}

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

using std::cout;
using std::cin;
using std::endl;
using std::pow;
using std::vector;
using std::string;

int main(){
    long long int N,Q,i,tmp,out=0;
    cin >> N;
    vector<int> a(1000000,0);
    for(i=0;i<N;i++){
        cin >> tmp;
        a.at(tmp)++;
        out += tmp;
    }
    cin >> Q;
    vector<int> b(Q),c(Q);
    for(i=0;i<Q;i++) cin >> b.at(i) >> c.at(i);
    for(i=0;i<Q;i++){
        tmp = a.at(b.at(i));  //count
        out -= tmp * b.at(i); //count*value
        out += tmp * c.at(i);
        cout << out << endl;
        a.at(b.at(i)) = 0;
        a.at(c.at(i)) += tmp;
    }

}

Measured memory_bytes: 7948
#include<bits/stdc++.h>
#define ll long long
#define MOD int(1e9+7)
#define mp make_pair
#define pb push_back
using namespace std;

vector<vector<ll>> dp(1000,vector<ll>(10001,INT_MAX));

ll dfs(auto& a,auto& b,int index,ll h)
{
    if(index>=b.size())
    {
        if(h>0) return INT_MAX;
        return 0;
    }
    if(h<=0) return 0;
    if(dp[index][h]!=INT_MAX) return dp[index][h];

    dp[index][h]=min(dfs(a,b,index+1,h),dfs(a,b,index,h-a[index])+b[index]);

    return dp[index][h];
}

int main()
{
    ll h,n;
    cin>>h>>n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];

    cout<<dfs(a,b,0,h);

    return 0;
}


Measured memory_bytes: 79360
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>



using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}
int abs(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}

int moji(char in)
{
    int ans = (int)in-(int)'a'+1;
    if((in < 1) || (in > 26)){
        ans = 100;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}





int main(){
  int A,B,K;
  cin>>A>>B>>K;
  int C=B-A+1;
  if(C<=2*K){
    for(int i=A;i<=B;i++)
    cout<<i<<endl;
  }else{
    for(int i=A;i<A+K;i++){
      cout<<i<<endl;
    }
    for(int i=B-K+1;i<=B;i++){
      cout<<i<<endl;
    }
  }
  
  
}


  
  

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;

int bubble_sort(int N, char suits[],int numbers[]){
	
	char tmp_c;
	int tmp_i;
	
	for(int i=0;i<N;++i){
		for(int j=N-1;i<j;--j){
			if(numbers[j-1]>numbers[j]){
				tmp_c = suits[j-1];
				suits[j-1] = suits[j];
				suits[j] = tmp_c;
				
				tmp_i = numbers[j-1];
				numbers[j-1] = numbers[j];
				numbers[j] = tmp_i;
			}
		}
	}
	return 0;
}

int selection_sort(int N, char suits[],int numbers[]){
	
	int min;
	
	char tmp_c;
	int tmp_i;
	
	for(int i=0;i<N;++i){
		min = i;
		for(int j=i;j<N;++j){
			if(numbers[min] > numbers[j]){
				min = j;
			}
		}
		if(min != i){
			tmp_c = suits[min];
			suits[min] = suits[i];
			suits[i] = tmp_c;
				
			tmp_i = numbers[min];
			numbers[min] = numbers[i];
			numbers[i] = tmp_i;
		}
	}
	
	return 0;
}

bool judge(int N,char ord_suits[], char suits[], int ord_numbers[], int numbers[]){
	
	int k = 0,j = 0;
	int prev_num = 0;
	bool f = true;
	
	for(int i=0;i<N;++i){
		if(prev_num != numbers[i]){
			k = i;
			j = 0;
			while(j<N){
				while(numbers[k] != ord_numbers[j]) j++;
				
				if(suits[k] != ord_suits[j]){
					f = false;
				}
				if(numbers[k] == numbers[k+1]){
					k++;
				}else{
					break;
				}
				j++;
			}
			prev_num = numbers[i];
		}
	}
	
	return f;
}

int main(void){
	
	int N;
	
	char ord_suits[36];
	char bubble_suits[36];
	char selection_suits[36];
	
	int ord_numbers[36];
	int bubble_numbers[36];
	int selection_numbers[36];
	
	cin >> N;
	
	for(int i=0;i<N;++i){
		cin >> ord_suits[i] >> ord_numbers[i];
	}
	
	memcpy(bubble_suits,ord_suits,sizeof(char)*N);
	memcpy(bubble_numbers,ord_numbers,sizeof(int)*N);
	memcpy(selection_suits,ord_suits,sizeof(char)*N);
	memcpy(selection_numbers,ord_numbers,sizeof(int)*N);
	
	bubble_sort(N,bubble_suits,bubble_numbers);
	selection_sort(N,selection_suits,selection_numbers);
	
	for(int i=0;i<N;++i){
		cout << bubble_suits[i] << bubble_numbers[i];
		if(i<N-1){
			cout << " ";
		}
	}
	cout << endl;
	if(judge(N,ord_suits,bubble_suits,ord_numbers,bubble_numbers)){
		cout << "Stable" << endl;
	}else{
		cout << "Not stable" << endl;
	}
	
	for(int i=0;i<N;++i){
		cout << selection_suits[i] << selection_numbers[i];
		if(i<N-1){
			cout << " ";
		}
	}
	cout << endl;
	if(judge(N,ord_suits,selection_suits,ord_numbers,selection_numbers)){
		cout << "Stable" << endl;
	}else{
		cout << "Not stable" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1168
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		int s_count = sc.nextInt();
		int t_count = sc.nextInt();
	    String u = sc.next();
	    if(s.equals(u)) {
	    	s_count = s_count -1;
	    }else if(t.equals(u)) {
	    	t_count = t_count -1;
	    }
	    
	    System.out.println(s_count+" "+t_count);

	}

}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define sc(x) scanf("%d",&x);

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

int main(){
    int n, X, minv = 1e9+7;
    sc(n) sc(X)
    vector<int> x(n), y;
    for (int i = 0; i < n; i++) sc(x[i])
    x.push_back(X);
    sort(x.begin(), x.end());
    for (int i = 0; i < n; i++) y.push_back(x[i+1] - x[i]);
    ll ans;
    if (n > 1) ans = gcd(y[0], y[1]);
    else ans = y[0];
    for (int i = 2; i < n; i++) ans = gcd(ans, y[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
using P = pair<int, int>;
const ll inf = 1e9;
const int MAX = 1e5+5;
const ll MOD = 1e9+7;

struct edge{
    int to;
    int cost;
};

using graph = vector<vector<edge>>;

int main(){
    int n; cin >> n;
    if(n%2==0) cout << n/2 << endl;
    else cout << n/2 + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <deque>
using namespace std;

int ans[100010];

int main() {
	int K; scanf("%d", &K);
	for(int i=0;i<K;i++) ans[i] = 1e9;
	deque <int> D; D.push_back(1); ans[1] = 1;
	while(!D.empty()) {
		int t = D.front(); D.pop_front();
		if(ans[t] < ans[10*t%K]) ans[10*t%K] = ans[t], D.push_front(10*t%K);
		if(ans[t] + 1 < ans[(t+1)%K]) ans[(t+1)%K] = ans[t] + 1, D.push_back((t+1)%K);
	}
	printf("%d\n", ans[0]);
	return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;


int main() {

	vector<vector<int>> data(3, vector<int>(3));

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> data.at(i).at(j);
		}
	}
	bool flag = true;
	string ans = "No";
	for (int i = 0; i <= 100; i++)
	{
		int a[3] = { 0 };
		int b[3] = { 0 };

		a[0] = i;
		for (int j = 0; j < 3; j++)
		{
			b[j] = data.at(0).at(j) - a[0];
		}

		for (int j = 1; j < 3; j++)
		{
			a[j] = data.at(j).at(0) - b[0];
		}
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				if (data.at(i).at(j)  != a[i] + b[j])
				{
					flag = false;
					break;
				}
			}
		}
		if (flag) ans = "Yes";
	}

	cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//T+N
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string a;
    cin >> a;
    bool y = false, m = false;
    int first = (a[0] - '0') * 10 + a[1] - '0';
    int second = (a[2] - '0') * 10 + a[3] - '0';
    if(first != 0 && first < 13) {
        m = true;
    }
    if(second != 0 && second < 13) {
        y = true;
    }
    if(m && y) {
        cout << "AMBIGUOUS" << endl;
    } else if(m) {
        cout << "MMYY" << endl;
    } else if(y) {
        cout << "YYMM" << endl;
    } else {
        cout << "NA" << endl;
    }
    return 0;
}




Measured memory_bytes: 3608
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int n, i;
    cin >> n >> i;

    cout << n + 1 - i << endl;
}

Measured memory_bytes: 3612
# ALDS1_9_A Complete Binary Tree
import sys

H = int(input())

A = sys.stdin.readline().strip().split()

for i in range(H):
    print('node {}: key = {}, '.format(i + 1, A[i]), end='')

    if i != 0:
        print('parent key = {}, '.format(A[(i + 1) // 2 - 1]), end='')

    if (i + 1) * 2 - 1 <= H - 1:
        print('left key = {}, '.format(A[(i + 1) * 2 - 1]), end='')
        if (i + 1) * 2 <= H - 1:
            print('right key = {}, '.format(A[(i + 1) * 2]), end='')

    print('')




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

using namespace std;

template<typename T>
class RangeAddQuery {
public:
    explicit RangeAddQuery(int n) : N(calcN_(n)) {
        mVal.assign(2*N+1, 0);
    }
    void update(int l, int r, T value){
        updateImpl_(l, r, value, 0, 0, N);
    }
    T get(int idx){
        int i = N + idx - 1;
        auto res = mVal[i];
        while(i > 0){
            i = (i-1)/2;
            res += mVal[i];
        }
        return res;
    }
private:
    int calcN_(int n){
        int res = 1;
        while(res < n) res *= 2;
        return res;
    }
    void updateImpl_(int l, int r, T value, int idx, int rangeL, int rangeR){
        if(r <= rangeL || rangeR <= l) return;
        if(l <= rangeL && rangeR <= r){
            mVal[idx] += value;
        } else {
            int rangeM = (rangeL+rangeR)/2;
            updateImpl_(l, r, value, 2*idx+1, rangeL, rangeM);
            updateImpl_(l, r, value, 2*idx+2, rangeM, rangeR);
        }
    }
    const int N;
    vector<T> mVal; 
};

int main(){
    int n, q;
    while(cin >> n >> q){
        RangeAddQuery<int> raq(n);
        for(int i=0;i<q;i++){
            int c; cin >> c;
            if(c == 0){
                int s, t, x; cin >> s >> t >> x;
                raq.update(s-1, t, x);
            } else {
                int p; cin >> p;
                cout << raq.get(p-1) << endl;
            }
        }
    }
}



Measured memory_bytes: 3884
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

c = 0
for i in range(n):
    a_m = min(a[i], b[i])
    c += a_m
    b[i] -= a_m
    b_m = min(a[i+1], b[i])
    a[i+1] -= b_m
    c += b_m

print(c)


Measured memory_bytes: 18624
#include <bits/stdc++.h>
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.14159265
#define MOD 1000000007
#define PSET(x,y) fixed<<setprecision(y)<<x
#define ll long long
#define ld long double
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define lop(i,a,b) for(ll i=a;i<b;i++)
#define lopr(i,a,b) for(ll i=a;i>=b;i--)
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define eb emplace_back
#define fi first
#define se second
#define pi pair<int,int>
#define pll pair<ll, ll>
#define si set<int>
#define sll set<ll>
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
#define state tuple<int,int,int>
#define graph map<ll,list<ll>>

inline int sbt(int x){return __builtin_popcount(x);} //returns number of set bits

using namespace std;

#define TRACE
#ifdef TRACE
#define deb(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << std::endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define deb(...)
#endif

int main(){
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    
    fast_io()
    
    ll n;
    cin>>n;

    ll b[n];
    lop(i,0,n)
    	cin>>b[i];
	sort(b,b+n);

	bool not_stop=true;
	while(not_stop){
		not_stop=false;
		lop(i,0,n)
			if(b[i]!=0)
				lop(j,0,n)
					if(i!=j){
						int tp = b[j] % b[i];
						if(tp!=b[j]){
							b[j]=tp;
							not_stop=true;
						}
					}

		sort(b,b+n);
	}

	cout<<b[n-1];

    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string s;
	cin>>s;
		int f=1;
		if(s[0]!='A')
			f=0;
		for(int i=0;i<s.size();i++)
			if(s[i]!='A' && s[i]!='C')
				if(s[i]<'a' || s[i]>'z')
					f=0;
		int sum=0;
		for(int i=2;i<s.size()-1;i++)
			if(s[i]=='C')
				sum++;
		if(sum!=1)
			f=0;
		if(f==1)
			cout<<"AC"<<endl;
		else
			cout<<"WA"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
typedef vector<pii> vpii;
struct Edge {
  ll s,t,d;
};
typedef vector<vector<Edge>> Graph;

int main() {
  ll N; cin>>N;
  vi a(3*N); REP(i,3*N) cin>>a[i];
  multiset<ll> S;
  REP(i,N) S.insert(a[i]);
  ll sum=0;
  REP(i,N) sum+=a[i];

  vi A(3*N);
  A[N-1]=sum;
  FOR(i,N,2*N) {
    if(a[i]>*S.begin()) {
      sum+=a[i]-*S.begin();
      S.erase(S.begin());
      S.insert(a[i]);
    }
    A[i]=sum;
  }

  vi B(3*N);
  sum=0;
  multiset<ll,greater<ll>> S2;
  FOR(i,2*N,3*N) sum+=a[i];
  FOR(i,2*N,3*N) S2.insert(a[i]);
  B[2*N]=sum;
  for(ll i=2*N-1;i>=N;i--) {
    if(a[i]<*S2.begin()) {
      sum+=a[i]-*S2.begin();
      S2.erase(S2.begin());
      S2.insert(a[i]);
    }
    B[i]=sum;
  }
  ll ans=-INF;
  FOR(i,N-1,2*N) ans=max(ans,A[i]-B[i+1]);
  cout<<ans<<endl;
}


Measured memory_bytes: 16640
#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
long long ans=0;
int main(){
	int i,o,f,j,l,s,z,t;
	cin>>i>>o>>f>>j>>l>>s>>z;
	if((i%2)+(j%2)+(l%2)>=2 && i>0 && j>0 && l>0){ans+=3;i--;j--;l--;}
	ans+=o;
	ans+=(i/2)*2;
	ans+=(j/2)*2;
	ans+=(l/2)*2;
	cout<<ans<<endl;
	return 0;
}

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

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
} Accelerate_Cin;

int s(int n) {
  int res = 0;
  while (n > 0) {
    res += n % 10;
    n /= 10;
  }
  return res;
}

bool cmp(int y, int x) {
  return y * s(x) <= x * s(y);
}

signed main() {
  int K;
  cin >> K;
  int d = 1, now = 0;
  for (int i = 1; i <= K; i++) {
    int x = now + d, y = now + d * 10;
    if (cmp(x, y)) {
      now = x;
    } else {
      now = y;
      d *= 10;
    }
    cout << now << endl;
  }

  return 0;
}


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

int main()
{
    int n;
    vector<int> d;
    int temp;
    cin>>n;
    int k=n/2;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        d.push_back(temp);
    }
    sort(d.begin(),d.end());
    
    cout<<d[k]-d[k-1]<<endl;
}

Measured memory_bytes: 892
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

int main() {
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<tuple<ll,ll,ll>> stop(n);
  FOR(a,stop) {
    ll s, t, x;
    cin >> s >> t >> x;
    a = make_tuple(s, t, x);
  }
  VL ds(q);
  FOR(d,ds) {
    cin >> d;
  }
  vector<tuple<ll, bool, ll>> interval;
  FOR(a,stop) {
    interval.emplace_back(get<0>(a) - get<2>(a), true, get<2>(a));
    interval.emplace_back(get<1>(a) - get<2>(a), false, get<2>(a));
  }
  sort(interval.begin(), interval.end());
  multiset<ll> current_belong;
  int person = 0;
  FOR(i,interval) {
    while (person < q && ds[person] < get<0>(i)) {
      if (current_belong.size() == 0) {
        cout << -1 << endl;
      } else {
        cout << *current_belong.begin() << endl;
      }
      person++;
    }
    if (get<1>(i)) {
      current_belong.insert(get<2>(i));
    } else {
      current_belong.erase(get<2>(i));
    }
  }
  while (person < q) {
    cout << -1 << endl;
    person++;
  }

  return 0;
}


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

using namespace std;

int main(){
	int n,k;
	cin >> n>>k;
	vector<int>P(n);
	for(int i=0; i<n; i++) cin >> P[i];
	int sum = 0;
	sort(P.begin(),P.end());
	for(int i=0; i<k; i++) sum+=P[i];
	cout<<sum<<endl;
}


Measured memory_bytes: 3544
#include "bits/stdc++.h"
using namespace std;

int main() {
    int d, n;
    cin >> d >> n;
    if (d == 0) {
        if (n == 100) cout << n + 1 << endl;
        else cout << n << endl;
    }
    else if (d == 1) {
        if(n == 100) cout << (n + 1) * 100 << endl;
        else cout << n * 100 << endl;
    }
    else {
        if(n == 100) cout << (n + 1) * 100 * 100 << endl;
        else cout << n * 100 * 100 << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  int d=min(a,b);
  int e=max(a,b);
  cout<<min(d,c)<<" "<<max(e,c)<<endl;
}



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


void solve(std::string S){
    vector<bool> ans(26, false);
    for(ll i=0; i< S.length(); i++){
        ans[S.at(i)-'a'] = true;
    }
    for(ll i=0; i< 26; i++){
        if(!ans[i]) {
            cout << (char)(i+'a') << endl;
            return;
        }
    }
    cout << "None" << endl;
    
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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



int main(){
	int n;
	cin >> n;
	int a, b, c;
	long long int dpa, dpb, dpc;
	long long int tdpa, tdpb, tdpc;
	dpa = dpb = dpc = 0;
	for(int i = 0; i < n; i++){
		cin >> a >> b >> c;
		tdpa = max(dpb, dpc) + a;
		tdpb = max(dpc, dpa) + b;
		tdpc = max(dpa, dpb) + c;
		dpa = tdpa;
		dpb = tdpb;
		dpc = tdpc;
	}
	cout << max(dpa, max(dpb, dpc)) << endl;
	return 0;
		
}

Measured memory_bytes: 3472
#include <bits/stdc++.h>
using namespace std;
#define LD long double
#define LL long long int
#define ULL unsigned long long
#define vi vector<int>
#define mod 1000000007

int main(){
    
    int N,W;
    cin>>N>>W;
    
    vector<ULL> weights;
    vector<ULL> values;
    
    weights.push_back(0);
    values.push_back(0);
    
    for(int i=0; i<N; i++)
    {
       int w, v;
       cin>>w>>v;
       weights.push_back(w);
       values.push_back(v);
    }
    
    vector<vector<ULL>> dp(N+1, vector<ULL> (W+1, 0));
    
    for(int i=1 ; i<=N ; i++)
    {
        for(int j =1 ; j<=W ; j++)
        {
            if(j>= weights[i])
            {
                dp[i][j] = max(dp[i-1][j], values[i]+dp[i-1][j-weights[i]] );
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
            
        }
        
    }
    
    std::cout << dp[N][W] << std::endl;

    
}

Measured memory_bytes: 80256
#include<stdio.h>
#include<stdlib.h>
int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}
int asc(const void *a, const void *b) 
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    int i;
    int a[200005];
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), asc);
    int j;
    int b[200005] = {};
    j = i = 0;
    while (i < n)
    {
        while (a[i] == a[i + 1])
        {
            b[j]++;
            i++;
        }
        b[j]++;
        i++;
        j++;
    }
    qsort(b, j, sizeof(int), asc);
    int ans = n;
    for (i = j - 1; i >= max(j - k, 0); i--)
        ans -= b[i];
    printf("%d\n", ans);
    return 0;
}

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

using namespace std;

using ll = long long;

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

void ALLIN1_NUMBER(vector<ll>& V)
{
    for(auto& x : V)
    {
        cin >> x;
    }
}

template<class T>
void OUT0(T N)
{
    cout << N << endl;
}

static const double pi = acos(-1.0);

double Cos(double D)
{
    return cos(pi/180 * D);
}

class Query
{
    public:
    ll l,r;
};

void ALLIN_QUERIES(vector<Query>& Qs)
{
    for(auto& x : Qs)
    {
        cin >> x.l >> x.r;
    }
}

bool PRIME(ll N)
{
    if(N==1) return false;
    ll N_copy = N;
    for(ll i=2;i*i<=N;i++)
    {
        while(N_copy%i==0)
        {
            N_copy /= i;
        }
    }
    if(N_copy==N) return true;
    return false;
}

vector<bool> PRIME_OR_NOT()
{
    vector<bool> ret((1e5)+1);
    ret[0] = false;
    for(ll i=1;i<=1e5;i++)
    {
        if(PRIME(i))
        {
            ret[i] = true;
        }
        else
        {
            ret[i] = false;
        }
    }
    return ret;
}

vector<ll> RUI_SIMILAR_2017(vector<bool> Prime_Or_Not)
{
    vector<ll> ret((1e5)+1,0);
    ret[1] = 0;
    for(ll i=3;i<=1e5;i+=2)
    {
        if(Prime_Or_Not[i] && Prime_Or_Not[(i+1)/2])
        {
            ret[i] = ret[i-2] + 1;
        }
        else
        {
            ret[i] = ret[i-2];
        }
        ret[i-1] = ret[i-2];
    }
    return ret;
}

void Ans(vector<Query> Qs, vector<ll> Rui_Similar_2017)
{
    for(auto x : Qs)
    {
        OUT0(Rui_Similar_2017[x.r]-Rui_Similar_2017[x.l-1]);
    }
}

int main()
{
    ll Q;
    cin >> Q;

    vector<Query> Qs(Q);
    ALLIN_QUERIES(Qs);

    Ans(Qs,RUI_SIMILAR_2017(PRIME_OR_NOT()));

    return 0;
}

Measured memory_bytes: 4608
import fractions
import copy
n=int(input())
a = list(map(int, input().split()))
b=copy.copy(a)
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
cut=0
for i in range(n):
    cut+=ans//b[i]
print(cut%((10**9)+7))


Measured memory_bytes: 6200
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
index = int(input())

print(l[index-1])

Measured memory_bytes: 3060
from itertools import accumulate

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def main():
    N, K, *A = map(int, open(0).read().split())

    B = [0] + list(accumulate(a - K for a in A))

    memo = {n: i for i, n in enumerate(sorted(set(B)), 1)}
    bit = BIT(N + 1)

    ans = 0
    for b in map(memo.get, B):
        ans += bit.sum(b)
        bit.add(b, 1)

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 52944
package main
import (
  "fmt"
)
func main() {
  var n, k int
  fmt.Scanf("%d %d", &n, &k)
  a := make([]int, n)
  for i:=0;i<n;i++ {
    fmt.Scanf("%d", &a[i])
  }
  fmt.Println(solve(n, k, a))
}

func solve(n, k int, a []int) string {
  dp := make([]bool, k+1)
  dp[0] = false
  for i:=1;i<=k;i++ {
    for j:=0;j<n;j++ {
      if i-a[j]>=0 && !dp[i-a[j]] {
        dp[i] = true
      }
    }
  }
//  fmt.Println(dp)
  if dp[k] {
    return "First"
  }
  return "Second"
}

Measured memory_bytes: 640
# coding: utf-8
"""Snuke's Coloring 2 (ABC Edit)
 
@author: hijiri.n
@modified: 11-19-2016
 
"""
 
def data(): return list(map(int, input().split()))
 
 
def solve(init, point):
    w, h, N = init
    rect = [0, w, 0, h]
 
    for p in point:
        x, y, a = p
 
        rect[a - 1] = [min, max][a % 2](rect[a - 1], [x, y][a > 2])
 
        if rect[1] <= rect[0] or rect[3] <= rect[2]:
            return 0
        
    return (rect[1] - rect[0]) * (rect[3] - rect[2])
 
# Input init & points data
i_in = data()
p_in = [data() for _ in range(i_in[-1])]
print(solve(i_in, p_in))

Measured memory_bytes: 3064
//#typedef int ll
// include
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <tuple>
// namespace
using namespace std;
// typedef
typedef long long ll;
typedef long double ld;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pint;
// const
const int inf = 1e9;
const int mod = ((int)1e9 + 7);
// loop
#define rep(i, n) for(int i = 0, i##_mx = n; i < i##_mx; i++)
#define brep(i, b, e) for(int i = b; i < e; i++)
#define erep(i, b, e) for(int i = b; i <= e; i++)
#define rrep(i, b, e) for(int i = b; i >= e; i--)
// STL
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
// function
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
void prime(vint& v, int n){brep(i, 2, n){bool fg = false; for(auto e : v){if(i % e == 0){fg = true;}} if(fg){continue;} v.pb(i);}}
void in(vint& v){for(auto& i : v){cin >> i;}}
void in(vll& v){for(auto& i : v){cin >> i;}}

signed main(){
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> task;
    ll a, b;
    rep(i, n){
        cin >> a >> b;
        task.pb(mp(a, b));
    }
    
    sort(all(task), [](auto l, auto r){return l.second < r.second;});
    
    ll sum = 0;
    for(auto i : task){
        sum += i.first;
        if(sum > i.second){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 6128
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int a,b,c,d;cin>>a>>b>>c>>d;
  int x=(a+d-1)/d;
  int y=(c+b-1)/b;
  if(x<y) cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
  return 0;
}


Measured memory_bytes: 3620