akhauriyash/Code-Regression huggingface dataset:
import sys
import math
def kaijyo(n):
  return math.factorial(n)%(10**9+7)
N,M=map(int,input().split())
if abs(N-M)>1:
  print(0)
  sys.exit()
if N-M==-1:
  N,M=M,N
if N-M==1:
  print((kaijyo(N)*kaijyo(M))%(10**9+7))
  sys.exit()
else:
  print((2*kaijyo(N)*kaijyo(M))%(10**9+7))
  sys.exit()

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

int main() {
	long long int n,m,l,r,a,b;
	cin>>n>>m;
	cin>>a>>b;
	l=a;
	r=b;
	for(int i=1;i<m;i++){
		cin>>a>>b;
		if(a>r){
			cout<<0;
			return 0;
		}
		if(a>l)
		l=a;
		if(r>b)
		r=b;
	}
	cout<<r-l+1;
	return 0;
}

Measured memory_bytes: 256
number=list(map(int,input().split()))
H,W,K=number[0],number[1],number[2]
answer=0
nums=[]
for i in range(H):
    tmp=list(str(input()))
    nums.append(tmp)
count=0
for cowmask in range(1<<H):
    for rowmask in range(1<<W):
        count=0
        for x in range(H):
            for y in range(W):
                if (cowmask>>x)&1==0 and (rowmask>>y)&1==0 and nums[x][y]=="#":
                    count+=1
        if count==K:
            answer+=1
            
print(answer)

Measured memory_bytes: 73964
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import functools

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
# @functools.lru_cache(maxsize = None)
# def func(N, X):
#     g = gcd(N, X)
#     if g == 1:
#         if X > N // 2:
#             return func(N, N - X)
#         if N == 2:
#             return 3
#         if N == 3:
#             return 6
#         return X * 3 + func(N-X, X)
#     else:
#         return g * func(N//g, X//g)


def func_fast(N, X):
    g = gcd(N, X)
    if g == 1:
        return 3 * N - 3
    else:
        return g * func_fast(N // g, X // g)

N,X = map(int,input().split())
print(func_fast(N,X))
        


Measured memory_bytes: 4212
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

struct Counter {
    map<int, int> m;

    ll _values = 0;

    void push(P p) {
        _values += p.second;
        m[p.first]++;
    }

    void pop(P p) {
        _values -= p.second;
        m[p.first]--;
        if (m[p.first] == 0) m.erase(m.find(p.first));
    }

    ll values() {
        ll c = m.size();
        return _values + c * c;
    }

};

int main() {
    int n, k;
    cin >> n >> k;

    vector<P> v(n);
    for (P &p : v) cin >> p.first >> p.second;

    // 種類を全部洗いだす
    // 種類ごとにおいしい順
    //  おいしい順先頭Kこ
    // おいしい順の先頭を除く全部を一個に並べてソート
    // 種類数がKより少なければ、残りからおいしい順に入れる
    // 種類ごとに一番おいしいものを、おいしく無い順にPopして残りをおいしい順にPushする

    set<int> all_types;
    for (P p : v) all_types.insert(p.first);

    map<int, vector<P>> all_sort;
    for (P p : v) all_sort[p.first].push_back(p);
    for (int t : all_types) sort(all_sort[t].begin(), all_sort[t].end());

    vector<P> top_par_types;
    vector<P> rems;


    for (int t : all_types) {
        top_par_types.push_back(all_sort[t].back());
        rep(i, all_sort[t].size() - 1) {
            rems.push_back(all_sort[t][i]);
        }
    }
    sort(top_par_types.rbegin(), top_par_types.rend(), [](P p1, P p2) { return p1.second < p2.second; });
    sort(rems.begin(), rems.end(), [](P p1, P p2) { return p1.second < p2.second; });

    vector<P> first_top_par_types = top_par_types;
    vector<P> first_top_rems;
    vector<P> first_rems = rems;

    Counter counter;
    for (P p :  first_top_par_types)counter.push(p);

    while (first_top_par_types.size() > k) {
        counter.pop(first_top_par_types.back());
        first_top_par_types.pop_back();
    }

    while (first_top_par_types.size() + first_top_rems.size() < k) {
        counter.push(first_rems.back());
        first_top_rems.push_back(first_rems.back());
        first_rems.pop_back();
    }

    ll ans = counter.values();

    while (!first_top_par_types.empty() && !first_rems.empty()) {
        counter.pop(first_top_par_types.back());
        counter.push(first_rems.back());

        first_top_par_types.pop_back();
        first_rems.pop_back();

        ll now = counter.values();
        cmax(ans, now);
    }

    cout << ans << endl;

}


Measured memory_bytes: 28372
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<vi> to(n);
  vi cnt(n),a(n-1),b(n-1);
  rep(i,n-1){
    cin >> a[i] >> b[i];
    --a[i]; --b[i];
    to[a[i]].push_back(b[i]);
    to[b[i]].push_back(a[i]);
    cnt[a[i]]++;
    cnt[b[i]]++;
  }
  int ans = 0;
  rep(i,n) chmax(ans,(int)to[i].size());
  cout << ans;
  queue<int> q;
  vi node(n,-1);
  q.push(0);
  node[0] = 0;
  while(!q.empty()){
    int now = q.front(); q.pop();
    int cnt = node[now]+1;
    for(int next : to[now]){
      if(0 <= node[next]) continue;
      cnt %= ans;
      node[next] = cnt++;
      q.push(next);
    }
  }
  cout << "\n";
  rep(i,n-1){
    if(b[i] != 0) cout << node[b[i]]+1 << endl;
    else cout << node[a[i]]+1 << endl;
  }
  return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint fact(int n){
	static vector<mint> memo{1};
	if(memo.size()<=n){
		int k=memo.size();
		memo.resize(n+1);
		for(;k<=n;k++) memo[k]=memo[k-1]*k;
	}
	return memo[n];
}

mint fact_inverse(int n){
	static vector<mint> memo{1};
	if(memo.size()<=n){
		int k=memo.size();
		memo.resize(n+1);
		memo[n]=inverse(fact(n));
		for(int i=n;i>k;i--) memo[i-1]=memo[i]*i;
	}
	return memo[n];
}

mint choose(int n,int k,int type=0){
	if(k<0 || n<k) return 0;
	if(type==0){
		return fact(n)*fact_inverse(k)*fact_inverse(n-k);
	}
	else{
		if(k>n-k) k=n-k;
		mint res=fact_inverse(k);
		rep(i,k) res*=n-i;
		return res;
	}
}

int main(){
	int h,w,a,b; scanf("%d%d%d%d",&h,&w,&a,&b);

	choose(h+w,h);

	if(a==h-1){
		printf("%d\n",choose(a+(w-b-1),a).to_int());
		return 0;
	}

	mint ans=0;
	rep(x,b) ans+=choose((h-a-2)+x,x)*choose(a+(w-b-1),a);
	rep(y,h-a-1) ans+=choose((b-1)+y,y)*choose((h-y-1)+(w-b-1),h-y-1);
	printf("%d\n",ans.to_int());

	return 0;
}


Measured memory_bytes: 1792
#include <vector>
#include <iostream>
#include <cassert>
#include <map>

using namespace std;
using ll = long long;
constexpr ll MOD = 1000000009LL;

struct Matrix {
    Matrix(const int N) : N(N), table(N, vector<ll>(N, 0LL)) {}
    static Matrix Unit(const int N)
    {
        Matrix ans(N);
        for (int i = 0; i < N; i++) {
            ans.table[i][i] = 1;
        }
        return ans;
    }
    Matrix operator*(const Matrix& mat) const
    {
        assert(mat.N == N);
        Matrix ans(N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    (ans.table[i][j] += table[i][k] * mat.table[k][j] % MOD) %= MOD;
                }
            }
        }
        return ans;
    }
    int N;
    vector<vector<ll>> table;
};

Matrix power(const Matrix& mat, const ll n)
{
    if (n == 0) {
        return Matrix::Unit(mat.N);
    }
    if (n % 2 == 1) {
        return mat * power(mat, n - 1);
    } else {
        const Matrix pp = power(mat, n / 2);
        return pp * pp;
    }
}

int main()
{
    int CASE = 0;
    while (true) {
        int W;
        ll H;
        int N;
        cin >> W >> H >> N;
        if (W == 0 and H == 0 and N == 0) {
            break;
        }
        CASE++;
        Matrix usual(W);
        for (int i = 0; i < W; i++) {
            usual.table[i][i] = 1;
            if (i > 0) {
                usual.table[i][i - 1] = 1;
            }
            if (i < W - 1) {
                usual.table[i][i + 1] = 1;
            }
        }
        map<ll, vector<int>> obst;
        for (int i = 0; i < N; i++) {
            int x;
            ll y;
            cin >> x >> y;
            x--, y--;
            obst[y].push_back(x);
        }
        Matrix ans = Matrix::Unit(W);
        ll previous = 0;
        for (const auto& v : obst) {
            const ll h = v.first;
            Matrix unusual = usual;
            for (const int x : v.second) {
                unusual.table[x][x] = 0;
                if (x > 0) {
                    unusual.table[x - 1][x] = 0;
                }
                if (x < W - 1) {
                    unusual.table[x + 1][x] = 0;
                }
            }
            ans = (h - previous > 0 ? ans * power(usual, h - previous - 1) : ans) * unusual;
            previous = h;
        }
        ans = (ans * power(usual, H - previous - 1));
        cout << "Case " << CASE << ": " << ans.table[0][W - 1] << endl;
    }

    return 0;
}



Measured memory_bytes: 3288
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[]po=new int[n];
        for(int i=0;i<n;i++)po[i]=sc.nextInt();
        int[]dp=new int[n+1];
        //dp[1]=Math.abs(po[1]-po[0]);
        for(int i=1;i<n;i++){
            for(int j=Math.max(0,i-k);j<i;j++){
                if(j==Math.max(0,i-k)){
                    dp[i]=dp[j]+Math.abs(po[i]-po[j]);
                }
                else dp[i]=Math.min(dp[i],dp[j]+Math.abs(po[i]-po[j]));
            }
        }
        //for(int i=0;i<=n;i++)System.out.println(dp[i]);
        System.out.println(dp[n-1]);
    }
}


Measured memory_bytes: 50308
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int n,a,b,c,d;
	scanf("%d",&n);
	a=n%10;
	n=n/10;
	b=n%10;
	n=n/10;
	c=n%10;
	d=n/10;
	if((a==b && b==c)||(b==c && c==d))	printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 128
a=input()
b=input()
c=input()

N,M,K=map(int, a.split())
A = list(map(int, b.split()))
B = list(map(int, c.split()))

kotae=N
Kotae=0
m=0
wa=sum(A)
for i in range(N+1):

    n=N-i-1
    
    if wa<=K:
        while wa+B[m]<=K:
            wa+=B[m]
            m+=1
            kotae+=1
            
            if m==M:
                m-=1
                break
        if kotae>Kotae:
            Kotae=kotae       
    wa-=A[n]
    kotae-=1
print(Kotae)

Measured memory_bytes: 43260
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int n, k;
ll a[200];
vector<ll> f(500000);

int main()
{
	cin >> n >> k;
	f[0] = 1;
	for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        vector<ll> f2(500000);
        ll d = 0;
        for (int j = 0; j <= k; j++)
        {
            d += f[j];
            d %= MOD;
            f2[j] = d;
            if (j - a[i] >= 0)
            {
                d = (d - f[j - a[i]] + MOD) % MOD;
            }
        }
        f = f2;
    }
    cout << f[k];
}


Measured memory_bytes: 8192
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		String s = in.next();
		char[] targ = s.toCharArray();
		
		char temp1 = targ[0];
		int cnt1 = 0;
		for(int i = 0; i<4; i++) {
			if(targ[i] == temp1) cnt1++;
		}
		
		if(cnt1 != 2) {
			System.out.println("No");
			return;
		}
		

		char temp2 = temp1;
		int cnt2 = 0;
		for(int i = 0; i<4; i++) {
			if(targ[i] != temp1) {
				temp2 = targ[i];
				break;
			}
		}
		
		if(temp2 == temp1) {
			System.out.println("No");
			return;
		}
		
		for(int i = 0; i<4; i++) {
			if(targ[i] == temp2) cnt2++;
		}
		
		if(cnt2 != 2) {
			System.out.println("No");
			return;
		}
		
		System.out.println("Yes");
		in.close();
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <algorithm>
#include <map>
#define ll unsigned long long
#define INF ((ll) 1e18)
using namespace std;

ll a, b, c, d;
map <ll, ll> dp;

// nにたどり着くために必要なコスト
ll cost(ll n) {
    if (n == 0) {
        // if 0
        return 0;
    } else if (n == 1) {
        // if remaining step is to minus 1
        return d;
    } else if (n == 2) {
        // if remaining step is to minus 2 or divide 2 and minus 1
        return min(d * 2, a + d);
    } else if (dp.find(n) != dp.end()) {
        // if already calculated cost(n)
        return dp[n];
    }

    // 商を１増やすためには次の倍数にたどり着かせる
    // => (k - n % k) * d
    dp[n] = min({
            d * n,
            (n % 2) * d + a + cost(n / 2),
            (n % 3) * d + b + cost(n / 3),
            (n % 5) * d + c + cost(n / 5),
            (n % 2) ? (2 - n % 2) * d + a + cost(n / 2 + 1) : INF,
            (n % 3) ? (3 - n % 3) * d + b + cost(n / 3 + 1) : INF,
            (n % 5) ? (5 - n % 5) * d + c + cost(n / 5 + 1) : INF
    });
    return dp[n];
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        dp.clear();
        ll n;
        cin >> n >> a >> b >> c >> d;
        cout << cost(n) << endl;
    }
}


Measured memory_bytes: 4280
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define pll pair<ll, ll> 
#define vi vector<int>
#define vl vector<ll> 
#define vvl vector< vector<ll> > 
#define vvi vector< vector<int> >
#define vlp vector< pair<ll, ll> >
#define vllp vector<pair<ll, ll>, ll > 
#define mll map<ll, ll> 
#define rep(i,a)  for(ll i=0; i< a; i++)
#define rep1(i,a)   for(ll i = 1; i< a; i++)
#define foi(i, a, b)    for(ll i = a; i<b ; i++)
#define fod(i, a, b)    for(ll i = a; i>=b ; i--)
#define mp make_pair
#define fst first
#define sec second
#define ff first.first
#define fs first.second
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)
#define MAX 1000001
#define MOD 1000000007
#define INF (ll)1e18
#define s(v) v.size()
#define e(v) v.empty()

using namespace std;

ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll fexp(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%MOD; b/=2;a=a*a%MOD;}return ans;}
ll inverse(ll a, ll p){return fexp(a, p-2);}
// bool sortbysec(const pll &a, const pll &b){return (a.second < b.second);} 
void ingraph(vvl& graph, ll m){ll x, y;rep(i, m){cin>>x>>y;x--, y--;graph[x].pb(y);graph[y].pb(x);}}

int main(){
    // #ifndef ONLINE_JUDGE
    //     freopen("../input.txt", "r", stdin);
    //     freopen("../output.txt", "w", stdout);
    // #endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t;
    // cin>>t;
    t = 1;
    while(t--){
        string str;
        ll n;
        cin>>str;
        cin>>n;
        vector<char> beg, back;
        bool mode = 0;
        ll x, a;
        char b;
        rep(i, n){
            cin>>x;
            if(x == 1)  mode = !mode;
            else{
                cin>>a>>b;
                if(mode == 0){
                    if(a == 1)  beg.pb(b);
                    else back.pb(b);
                }else{
                    if(a == 1)  back.pb(b);
                    else beg.pb(b);
                }
            }
        }
        if(mode){
            fod(i, s(back)-1, 0)    cout<<back[i];
            fod(i, s(str)-1, 0)     cout<<str[i];
            rep(i, s(beg))          cout<<beg[i];
        }else{
            fod(i, s(beg)-1, 0)     cout<<beg[i];
            rep(i, s(str))          cout<<str[i];
            rep(i, s(back))         cout<<back[i];
        }

    }
}

Measured memory_bytes: 976
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) i64((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

int main(int argc, char *argv[]) {

  i64 N, A, B;
  cin >> N >> A >> B;
  i64 L = A + B;
  cout << ((N / L * A) + min(A, N % L)) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int start = h1 * 60 + m1;
    int end = h2 * 60 + m2;
    int res = end - start - k;
    cout << max(res, 0) << endl;
}


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

using namespace std;
bool cmp(double a,double b){
    return a > b;
}
int main(){
    int T;
    cin>>T;
    double sum;
    double a[55];
    for(int i = 0;i < T;i++){
        cin>>a[i];
    }
    sort(a,a+T);
    sum = (a[1]+a[0])/2.0;
    for(int i = 2;i < T;i++){
        sum = (a[i] + sum)/2.0;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = (1 << 30) - 1;

int H, W, ans, cost[1111][1111], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
char grid[1111][1111];
queue<pair<int, pair<int, int>>> que;

int main()
{
    cin >> H >> W;

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> grid[i][j];
            cost[i][j] = inf;
            if (grid[i][j] == '#')
            {
                que.emplace(0, make_pair(i, j));
            }
        }
    }

    while (!que.empty())
    {
        auto p = que.front();
        que.pop();
        int y = p.second.first, x = p.second.second, cnt = p.first;
        if (cost[y][x] != inf)
            continue;
        ans = max(cnt, ans);
        cost[y][x] = cnt, grid[y][x] = '#', cnt++;
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i], nx = x + dx[i];
            if ((ny < 0 || ny >= H) || (nx < 0 || nx >= W) || (grid[ny][nx] == '#'))
                continue;
            que.emplace(cnt, make_pair(ny, nx));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 17808
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2, 3]
n_2, n_1 = 2, 3
for i in range(3, n):
    n_2, n_1 = n_1, (n_2+n_1)%(10**9+7)
    comb_list.append(n_1)
for _ in range(m):
    a = int(input())
    a_list.append(a)
start = 0
ans = 1
if m == 0:
    ans = comb_list[n]
else:
    for a in a_list+[n+1]:
        if a == 1:
            start = a + 1
            continue
        else:
            if start == a:
                ans = 0
                break
            elif start == a - 1:
                start = a + 1
            else:
                tmp = a - start - 1
                ans = (ans * comb_list[tmp])%(10**9+7)
                if a == n-1:
                    break
                else:
                    start = a + 1
print(ans)


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

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< int, int > pii;

const double pi = 3.14159265358979323846;

// #define fio() cin.tie(0); ios::sync_with_stdio(false);
// template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
// template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos
// 1e18

ll N, M, X;
ll res = LLONG_MAX;
ll a0[12];
ll C[12];
ll A[12][12];

void dfs(ll price, long long a[], ll i) {
  // cout << price << " " << i << endl;
  // for (ll j = 0; j < M; j++) {
  //   cout << " " << a[j] << " ";
  // }
  // cout << endl;
  // check
  if (i == N) {
    for (ll j = 0; j < M; j++) {
      if (a[j] < X) {
        // cout << "  aj " << a[j] << endl;
        return;
      }
    }
    res = min(res, price);
    return;
  }

  // buy
  ll buy[12];
  memcpy(buy, a, sizeof(buy));
  for (ll j = 0; j < M; j++) {
    buy[j] += A[i][j];
  }
  dfs(price + C[i], buy, i + 1);

  // no buy
  dfs(price, a, i + 1);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> M >> X;

  for (ll i = 0; i < N; i++) {
    cin >> C[i];
    for (ll j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }

  dfs(0, a0, 0);

  if (res == LLONG_MAX) {
    res = -1;
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3600
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}


int h,w;
int D;
char buf[505][505];
int main(){
#ifdef LOCAL_REDIR
  freopen("/home/hog/Dropbox/pg/working/in.txt","r",stdin);
#endif
  cin>>h>>w>>D;

  string code="RYGB";
  const int M=500;
  REP(i,h) REP(j,w){
      int x=(i+j),y=(i-j)+M;

      x/=D;y/=D;
      int val=0;
      if(x&1) ++val;
      if(y&1) val+=2;

      buf[i][j]=code[val];
    }
  REP(i,h) printf("%s\n",buf[i]);
  return 0;
}






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

using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using vs=vector<string>;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define rep(i, a, n) for (int i = (n); i < (a); ++i)
#define repr(i, a, n) for (int i = (n); i >= (a); --i)

template<typename T,typename U>
void Inparray(T &f,U n){
  for(int i=0;i<n;i++) cin>>f[i];
}

template<typename T,typename U>
void Printarray(T f,U n){
  for(int i=0;i<n;i++) i!=n ? cout<<f[i]<<" " : cout<<f[i];
}

void flagfunc(bool flag,string A,string B){
  flag ? cout<<A<<endl : cout<<B<<endl;
}

void flag2func(bool flag){
  flag ? cout<<"Yes"<<endl : cout<<"No"<<endl;
}

void flag3func(bool flag){
  flag ? cout<<"YES"<<endl : cout<<"NO"<<endl;
}

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int a,b;cin>>a>>b;
  string c;
  int ans=0;
  for (int i = a; i <= b; ++i){
  	c=to_string(i);
  	if ((c[0]==c[4])&&(c[1]==c[3])) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
from datetime import datetime as dt

tstr = input()
tdatetime = dt.strptime(tstr, '%Y/%m/%d')
tdatetimea = dt.strptime('2019/05/01', '%Y/%m/%d')
if tdatetimea <= tdatetime:
    print('TBD')
else:
    print('Heisei')

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

using namespace std;
 
int main() {
  string text;
  cin >> text;
  auto year =(text.at(0)-'0')*1000+(text.at(1)-'0')*100+(text.at(2)-'0')*10+text.at(3)-'0';
  auto month = (text.at(5)-'0')*10+text.at(6)-'0';
  auto day = (text.at(8)-'0') * 10 + text.at(9)-'0';
  if (day + 100 * month + year * 10000 <=20190430) cout << "Heisei" << endl;
  else cout << "TBD" << endl;
  return 0;
}

Measured memory_bytes: 256
"""
    Template written to be used by Python Programmers.
    Use at your own risk!!!!
    Owned by enraged(rating - 5 star at CodeChef and Specialist at Codeforces).
"""
import sys
import bisect
import heapq
# from math import *
from collections import defaultdict as dd  # defaultdict(<datatype>) Free of KeyError.
from collections import deque  # deque(list) append(), appendleft(), pop(), popleft() - O(1)
from collections import Counter as c  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb
from bisect import bisect_left as bl, bisect_right as br, bisect
# sys.setrecursionlimit(2*pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()


def out(var): sys.stdout.write(var)


def l(): return list(map(int, data().split()))


def sl(): return list(map(str, data().split()))


def sp(): return map(int, data().split())


def ssp(): return map(str, data().split())


def l1d(n, val=0): return [val for i in range(n)]


def l2d(n, m, val=0): return [[val for i in range(n)] for j in range(m)]


s = deque(data())
q = int(data())
rev = 0
for i in range(q):
    arr = sl()
    if arr[0] == '1':
        rev = 1-rev
    else:
        if (arr[1] == '1' and rev == 0) or (arr[1] == '2' and rev == 1):
            s.appendleft(arr[2])
        else:
            s.append(arr[2])
s = list(s)
if rev == 1:
    s = s[::-1]
s = list(s)
print(''.join(s))


Measured memory_bytes: 71772
import collections

n = int(raw_input())
elems = map(int, raw_input().split(' '))
a = min(map(abs, elems))
s = sum(map(abs, elems))
count = 0
for c in elems:
	if c < 0: count +=1		
a = a if count % 2 else 0

print s - 2*a
"""
+++++----+++

obs 1
if the connected component has || even cardinality % 2==0


obs 2
if the connected component has odd cardinality I can reduce it to 1 
and move the - sign around 

obs 3
as I can move things around, I can merge ccs 


a = 0 if even number of negative signs else min([|v| for v in nums])
return sum([abs(v) for v in nums]) - a

"""

Measured memory_bytes: 40564
temp1 = input()
n = int(temp1)

temp2 = input().split(" ")

nums = [int(a) for a in temp2]


temp = nums[0]

limit = pow(10, 18)

for i in range(1, n):
    temp = temp * nums[i]
    if temp > limit:
        break;

if temp <= limit:
    print(temp)
else:
    if 0 in nums:
        print(0)
    else:
        print(-1)

Measured memory_bytes: 21784
#include <algorithm>
#include <cctype>
#include <complex>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

const int INF = 1e9;

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

    vector<int> a('z' + 1, INF);
    for(int i = 0; i < n; i++){
        vector<int> b('z' + 1, 0);
        string s;
        cin >> s;
        for(char c : s){
            b[c]++;
        }
        for(int j = 'a'; j <= 'z'; j++){
            a[j] = min(a[j], b[j]);
        }
    }

    string ans;
    for(int i = 'a'; i <= 'z'; i++){
        for(int j = 0; j < a[i]; j++){
            ans.push_back((char)i);
        }
    }

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


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static edge[][] V=new edge[30][30];
    
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);

        while(true){
            int n=cin.nextInt();
            if(n==0)break;
            int m=cin.nextInt();
            int p=cin.nextInt();
            int a=cin.nextInt()-1;
            int b=cin.nextInt()-1;
            int[] ti=new int[n];
            int[] Vs=new int[m];
            for(int i=0;i<n;i++)ti[i]=cin.nextInt();

            Arrays.fill(Vs,0);

            for(int i=0;i<p;i++){
                int x=cin.nextInt()-1;
                int y=cin.nextInt()-1;
                int z=cin.nextInt();
                V[x][Vs[x]++]=new edge(y,z);
                V[y][Vs[y]++]=new edge(x,z);
            }
            Queue<node> q=new PriorityQueue<node>();
            q.add(new node(0,a,0));

            Boolean[][] vis=new Boolean[m][1<<n];
            for(int i=0;i<m;i++)
                Arrays.fill(vis[i],false);
            
            double ans=-1;
            
            while(q.isEmpty()==false){
                node cn=q.poll();

                if(vis[cn.v][cn.st]==true)continue;
                vis[cn.v][cn.st]=true;
                if(cn.v==b){
                    ans=cn.cc;
                    break;
                }

                for(int i=0;i<n;i++){
                    if(((cn.st>>i)&1)==1)continue;
                    for(int j=0;j<Vs[cn.v];j++){
                        int nv=V[cn.v][j].v;
                        int tc=V[cn.v][j].c;
                        int nst=cn.st|(1<<i);
                        if(vis[nv][nst]==true)continue;
                        double nc=cn.cc+1.0*tc/ti[i];
                        q.add(new node(nc,nv,nst));
                    }
                }
            }
            if(ans<0)System.out.println("Impossible");
            else System.out.println(ans);
        }
    }

    public static class edge{
        public int v,c;
        public edge(int iv,int ic){
            v=iv;
            c=ic;
        }
    }
}

class node implements Comparable<node>{
    public double cc;
    public int v,st;
    public node(double icc,int iv,int ist){
        cc=icc;
        v=iv;
        st=ist;
    }
    public int compareTo(node s){
        if(cc>s.cc)return 1;
        else if(cc<s.cc)return -1;
        else return 0;
    }
}

Measured memory_bytes: 30000
def cal(dx,dy):
    cnt=0
    for x in s:
        flag=False
        for y in s:
            if(x==y):
                continue
            if(x[0]+dx==y[0] and x[1]+dy==y[1]):
                flag=True
        if(flag==False):
            cnt+=1
    return cnt

n=int(input())
s=[list(map(int,input().split())) for _ in range(n)]
ans=n
for x in s:
    for y in s:
        if(x==y):
            continue
        dx=x[0]-y[0]
        dy=x[1]-y[1]
        tmp=cal(dx,dy)
        if(tmp<ans):
            ans=tmp
print(ans)

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

Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 500000
#define SEN 2000000000

void marge(int*,int,int,int,int);
void margeSort(int*,int,int,int);

int L[MAX/2+2],R[MAX/2+2];
int cnt;

int main(){
  int i,n;
  int S[MAX];
  cnt = 0;

  scanf("%d",&n);

  for(i = 0;i < n;i++){
    scanf("%d",&S[i]);
  }

  margeSort(S,n,0,n);

  for(i = 0;i < n;i++){
    printf("%d",S[i]);
    if(i == n-1)break;
    printf(" ");
  }

  printf("\n%d\n",cnt);

  return 0;
}

void marge(int S[],int n,int left,int mid,int right){
  int i,k;
  int n1 = mid - left;
  int n2 = right - mid;

  for(i = 0;i < n1;i++){
    L[i] = S[left + i];
  }
  for(i = 0;i < n2;i++){
    R[i] = S[mid + i];
  }
  
  L[n1] = R[n2] = SEN;
  i = 0;
  int j = 0;

  for(k = left;k < right;k++){
    cnt++;
    if(L[i] <= R[j]){
      S[k] = L[i++];
    } else {
      S[k] = R[j++];
    }
  }
}

void margeSort(int S[],int n,int left,int right){
  if(left+1 < right){
    int mid = (left+right)/2;
    margeSort(S,n,left,mid);
    margeSort(S,n,mid,right);
    marge(S,n,left,mid,right);
  }
}



Measured memory_bytes: 5600
#include <stdio.h>

long long tribo(int n, long long* a){
  long long x;
  if (n <= 1) x = a[n];
  else {
    for (int i = 0; i < n - 1; i++){
      long long temp = a[0];
      a[0] = a[1];
      a[1] = a[0] + temp;
    }
    x = a[1];
  }
  return x;
}

int main(void){
  int N;
  long long a[] = {2,1};
  scanf("%d\n", &N);
  printf("%lld\n", tribo(N, a));
  return 0;
}


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

using namespace std;

int main()
{
    int A, B, M;
    cin >> A >> B >> M;
    int a[A], b[B];
    int mina = 200000, minb = 200000;

    for (int i = 0; i < A; i++)
    {
        cin >> a[i];
        if (a[i] < mina)
            mina = a[i];
    }
    for (int i = 0; i < B; i++)
    {
        cin >> b[i];
        if (b[i] < minb)
            minb = b[i];
    }
    int ans = mina + minb;
    int x, y, c;
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y >> c;
        if (a[x - 1] + b[y - 1] - c < ans)
            ans = a[x - 1] + b[y - 1] - c;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(e) e.begin(), e.end()
#define RALL(e) e.rbegin(), e.rend()
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define dbg(x) (cerr << #x << ":" << x << endl)
#define mid (l + r) / 2
#define pii pair <int, int>
#define fi first
#define sc second
#define N 1000000009

using namespace std;

typedef long long int lli;

int main(){
	ios::sync_with_stdio(0);
	float h, a;
	cin >> h >> a;

	cout << ceil(h/a);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// ll abs(ll n){
//     return n>0? n : n*(-1);
// }
int main() {
    int n , k;
    cin>>n>>k;
    ll arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i]; 
    }
    ll dp[n];
    for(int i=0; i<n ; i++){
        dp[i]=INT_MAX;
    }
    dp[0]=0;
    
    for(int i=1; i<n ; i++){
        for(int j=1; j<k+1 && (i-j) >=0 ; j++){
            dp[i] = min(dp[i-j]  + abs((arr[i]- arr[i-j]) ), dp[i]);
        }
    
    }
    cout<<dp[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
     
     
#define ll long long
#define sd(x) scanf("%d",&x)
#define sld(x) scanf("%lld",&x)
#define pld(x) printf("%lld\n",x)
#define pd(x) printf("%d\n",x)

int main(){
    int N;
    sd(N);
    int arr[N];
    for (int i = 0; i < N; i++){
        sd(arr[i]);
    }
    int isum = 0;
    for (int i = 0; i < N; i++){
        isum += arr[i];        
    }
    
    int d = isum;
    int f = 0;
    int l = isum;
    for (int i = 0; i < N; i++){
        f += arr[i];
        l -= arr[i];
        int x = max(f,l);
        int y = min(f,l);
        int cd = x-y;
        if(cd < d)
            d = cd;
        else
            break;
    }
    pd(d);
    return 0;
    
    
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int n,m,c;
  cin >> n >> m >> c;
  vector<int> b(m);
  vector<vector<int>> a(n,vector<int>(m));
  rep(i,m) cin >> b.at(i);
  rep(i,n){
    rep(j,m){
      cin >> a.at(i).at(j);
    }
  }
  int ans = 0;
  rep(i,n){
    int sum = c;
    rep(j,m){
      sum += a.at(i).at(j)*b.at(j);
    }
    if(sum>0) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
def bubble_sort(n, line)
  n.times do |i|
    trade = 0
    (n-i).times do |j|
      next if line[j+1].nil?

      if line[j][1].to_i > line[j+1][1].to_i
        tmp = line[j]
        line[j] = line[j+1]
        line[j+1] = tmp
        trade += 1
      else
        next
      end
    end
    break if trade == 0
  end

  line
end

def selection_sort(n, line)
  n.times do |i|
    num_line = line.map{ |l| l[1].to_i }
    index = num_line[i..-1].index(num_line[i..-1].min) + i
    next if i == index
  
    tmp = line[i]
    line[i] = line[index]
    line[index] = tmp
  end

  line
end

def stable_state(gets, results)
  gets_dups = []
  results_dups = []

  1.upto(13) do |i|
    gets_dups << gets.select { |g| g[1].to_i == i }
    results_dups << results.select { |r| r[1].to_i == i }
  end

  gets_dups.each_with_index do |g, i|
    return 'Not stable' if g != results_dups[i]
  end

  'Stable'
end

n = gets.to_i
line = gets.split(' ')
bubble_line = line.dup
selection_line = line.dup

bubble = bubble_sort(n, bubble_line)
selection = selection_sort(n, selection_line)

puts bubble.join(' ')
puts stable_state(line, bubble_line)
puts selection.join(' ')
puts stable_state(line, selection_line)


Measured memory_bytes: 6880
#include <algorithm>
#include <iostream>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<ll> VL;

template <class I, class BiOp> class SegmentTree {
  int n;
  std::vector<I> dat;
  BiOp op;
  I e;

public:
  typedef int size_type;
  typedef I value_type;
  SegmentTree(int n_, BiOp op, I e) : op(op), e(e) {
    n = 1;
    while (n < n_)
      n *= 2; // n is a power of 2
    dat.resize(2 * n);
    for (int i = 0; i < 2 * n - 1; i++) {
      dat[i] = e;
    }
  }
  /* ary[k] <- v */
  void update(int k, I v) {
    k += n - 1;
    dat[k] = v;
    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]);
    }
  }
  /* http://proc-cpuinfo.fixstars.com/2017/07/optimize-segment-tree/
   * [a, b)
   */
  I query(int a, int b) const {
    I left = e;
    I right = e;
    a += n - 1;
    b += n - 1;
    while (a < b) {
      if ((a & 1) == 0) {
        left = op(left, dat[a]);
      }
      if ((b & 1) == 0) {
        right = op(dat[b - 1], right);
      }
      a = a / 2;
      b = (b - 1) / 2;
    }
    return op(left, right);
  }
  I operator[](int idx) const {
    return dat[idx + n - 1];
  }
};


const ll inf = 1e16;

struct min_fun {
  ll operator()(ll x, ll y) const {
    return min(x, y);
  }
};

int main(void){
  int n;
  ll e, t;
  cin >> n >> e >> t;
  VL x(n);
  SegmentTree<ll, min_fun> raw(n + 1, min_fun(), inf); // dp[i]
  SegmentTree<ll, min_fun> boiled(n + 1, min_fun(), inf); // dp[i] - 2 * x[i]
  REP(i, 0, n) {
    cin >> x[i];
  }
  raw.update(0, 0);
  boiled.update(0, -2 * x[0]);
  REP(i, 0, n) {
    // Compute the range of j s.t. t <= 2 * (x[i] - x[j]) (0 <= j <= i)
    int j_boundary =
      upper_bound(x.begin(), x.begin() + i + 1, x[i] - (t+1)/2) - x.begin();
    ll ret = inf;
    ret = min(ret, boiled.query(0, j_boundary) + 2 * x[i]);
    ret = min(ret, raw.query(j_boundary, i + 1) + t);
    raw.update(i + 1, ret);
    if (i < n - 1) {
      boiled.update(i + 1, ret - 2 * x[i + 1]);
    }
  }
  cout << raw[n] + e << endl; 
}


Measured memory_bytes: 5140
def main

  while (n = gets.to_i) != 0
    arr = array
    n.times do |i|
      data = gets.split(" ").map(&:to_i)
      arr[data[0]][1] += data[1] * data[2]
      arr[data[0]][2] ||= i
    end
    arr.select!{|item|item[1] >= 10 ** 6}.sort_by!{|item|item[2]}
    if arr.length == 0
      puts "NA"
    else
      puts arr.collect{|item|item[0]}
    end
  end
  
end
def array
  arr = Array.new(4000){|i|[i + 1, 0, nil]}
  def arr.[]=(n, other)
    super(n - 1, other)
  end

  def arr.[](n)
    super(n - 1)
  end

  return arr
end
main

Measured memory_bytes: 6152
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long k = sc.nextLong();
		int[] a = new int[n];
		long[] b = new long[n];
		for(int i = 0 ; i < n ; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextLong();
		}
		long[] x = new long[100010];
		for(int i = 0 ; i < n ; i++) {
			x[a[i]] = 0;
		}
		for(int i = 0 ; i < n ; i++) {
			x[a[i]] += b[i];
		}
		for(int i = 1 ; i <= 100000 ; i++) {
			if(x[i] >= 0) {
				k -= x[i];
				if(k <= 0) {
					System.out.println(i);
					return;
				}
			}
		}
	}
}


Measured memory_bytes: 77096
#include "iostream"
#include "algorithm"
#include "math.h"
#include "vector"
#include "string"
#include "map"
using namespace std;
typedef long long ll;
int main()
{
    int x ;
    cin>>x;
    int p = (x == 0)? 1:0;
    cout<<p;     
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<functional>
using namespace std;
int stoi(string x){stringstream ss;ss<<x;int tmp;ss>>tmp;return tmp;}
string itos(int x){stringstream ss;ss<<x;return ss.str();}
int main(){
	int ta[]={1,2,4,8,16,32,64,128,256,512},n;
	while(cin>>n){
	vector<int>ans(0);
	for(int i=9;i>=0;i--){
	if(n>=ta[i]){ans.push_back(ta[i]);n-=ta[i];}
	}
	reverse(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++){cout<<ans[i];if(i==ans.size()-1)cout<<endl;else cout<<" ";}
	}
	return 0;
}

Measured memory_bytes: 1220
h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
r, c, d = 0, 0, 3
ret = []
for y in range(h * w - 1):
    if y % w == 0:
        d = (d + 1) % 4
    if y % w == w - 1:
        d = (d + 1) % 4
    dy, dx = [(0, 1), (1, 0), (0, -1), (1, 0)][d]
    if a[r][c] % 2 != 0:
        ret.append((r, c, r + dy, c + dx))
        a[r + dy][c + dx] += 1
    r, c = r + dy, c + dx
print(len(ret))
for r1, c1, r2, c2 in ret:
    print(r1 + 1, c1 + 1, r2 + 1, c2 + 1)


Measured memory_bytes: 75740
N,M=[int(s) for s in input().split()]
if N>=M:
  print(0)
else:
  ls=[int(s) for s in input().split()]
  ls.sort()
  d=[ls[i+1]-ls[i] for i in range(M-1)]
  d.sort()
  print(sum(d[:M-N]))

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)

struct query {
    i32 t, f, c;
};


int main() {
  string s;
  i32 q;
  cin >> s >> q;

  vector<query> qs(q);

  bool rev = false;

  string left, right;

  rep(i, q) {
    i32 qi;
    cin >> qi;
    if (qi == 1) {
      rev = !rev;
    } else if (qi == 2) {
      i32 f;
      char c;
      cin >> f >> c;

      if ((f == 1 && !rev) || (f == 2 && rev)) {
        left += c;
      } else {
        right += c;
      }
    }
  }


  if (rev) {
    reverse(s.begin(), s.end());
    reverse(right.begin(), right.end());
    s = right + s + left;
  } else {
    reverse(left.begin(), left.end());
    s = left + s + right;
  }

  cout << s;

  return 0;
}


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

int main(){
  
  int a=0,b=0,c=0;
  int x;
  int count=0;
  
  cin >> a >> b >> c;
  
  cin >> x;
  
  for(int i=0; i<=a; i++){
    
    for(int j=0; j<=b; j++){
      
      for(int k=0; k<=c; k++){
        
        if(500*i + 100*j + 50*k == x)
          count++;
      }
    }
  }
  
  cout << count;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    cin >> A >> B;
    cout << A*B;
    
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
 
#define rep(i,n) for(ll i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;
 
const int INF = 1001001001;
const long double PI = (acos(-1));
const int mod = 1e9+7;
const int vx[6] = {0,1,0,-1,1,-1};
const int vy[6] = {1,0,-1,0,1,1};

ll f(ll a){
    ll rep = 0;
    for(ll i = 1;i <= a/2;++i){
        if(a%i == 0){
            rep++;
        }
    }
    return rep+1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n,m,k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    vector<ll> b(m);
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];
    ll ans = 0;
    ll sum = 0;
    ll i = 0;
    ll j = 0;
    while(sum <= k){
        if(i==n) break;
        i++;
        sum += a[i-1];
    }
    if(sum == k || sum < k){
        ans = i;
    }else {
        ans = i-1;
    }
    while(sum <= k){
        if(j==m) break;
        j++;
        sum += b[j-1];
    }
    if(sum == k || sum < k){
        ans += j;
        cout << ans << endl;
        return 0;
    }else {
        ans += j-1;
        sum -= b[j-1];
        j--;
    }
    while(i){
        i--;
        sum -= a[i];
        while(sum <= k){
            if(j==m) break;
            j++;
            sum += b[j-1];
        }
        ll tmp;
        if(sum == k || sum < k){
            tmp = j;
        }else {
            tmp = j-1;
            sum -= b[j-1];
            j--;
        }
        ans = max(ans,i+j);
    }
    cout << ans << endl;
    
    cout << endl;
    return 0;
}


Measured memory_bytes: 6328