akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>
using namespace std;
#define all(x) (x).begin(), (x).end()

const int N = 500000;
const long long MOD = 1e9 + 7;

int n, q;
long long d[N];

long long s[N];

void solve(int k, int x, int m)
{
    s[0] = x;
    for (int i = 1; i < k; i++) s[i] = s[i - 1] + d[(i - 1 + n) % n];
    int r = 0;
    for (int i = 0; i + 1 < k; i++) if (s[i] % m < s[i + 1] % m) r++;
    cout << r << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> d[i];
    }
    for (int i = 0; i < q; i++)
    {
        long long k, x, m, s = 0, ans = 0;
        cin >> k >> x >> m;
        //solve(k, x, m);
        long long K = k;
        vector<long long> w;
        for (int j = 0; j < n; j++) w.push_back(d[j] % m), s += d[j] % m;
        x = x % m;
        for (int j = 0; j < n; j++)
        {
            if (k % n == 1)
            {
                break;
            }
            k--;
            int p = x;
            x = (x + w[j]) % m;
            if (p >= x) ans++;
        }
        x = x % m;
        for (int j = 0; j < n; j++)
        {
            if (w[j] == 0)
            {
                ans += k / n;
            }
        }
        long long y = x + (k / n) * s;
        ans += y / m - x / m;
        cout << K - 1 - ans << "\n";
    }
}


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

int main() {
	std::string abc;
	std::cin >> abc;
	int sum = 0;
	for (int i = 0; i < 3; i++) {
		if (abc[i] == 'a') {
			sum++;
			break;
		}
	}
	for (int i = 0; i < 3; i++) {
		if (abc[i] == 'b') {
			sum++;
			break;
		}
	}
	for (int i = 0; i < 3; i++) {
		if (abc[i] == 'c') {
			sum++;
			break;
		}
	}
	if (sum == 3) {
		std::cout <<"Yes"<< std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int A, B, C;
	cin >> A >> B >> C;
	int money = A + B;
	if (money < C)cout << "No";
	else cout << "Yes";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define MaxN 100003
#define fghiudsh dfguyshyi
#define fers dfguyshyi
#define fersgv dfguyshyi
int N;
int fa[MaxN];
long long ans, cnty[MaxN], cntx[MaxN];
map<int, bool> bk[MaxN];
struct Nd {
	int x, y;
}a[MaxN];

inline int Rd() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
inline int Find(int d) {
	if(fa[d] == d) return d;
	else return fa[d] = Find(fa[d]);
} 
inline bool cmp(Nd aa, Nd bb) {
	return aa.x < bb.x;
}

int main() {
	N = Rd();
	for(reg int i = 1; i <= 100000; ++i)
		fa[i] = i;
	for(reg int i = 1; i <= N; ++i)
		a[i].x = Rd(), a[i].y = Rd();
	sort(a + 1, a + 1 + N, cmp);
	for(reg int i = 1; i < N; ++i)
		if(a[i].x == a[i + 1].x)
			fa[Find(a[i].y)] = Find(a[i + 1].y);
	for(reg int i = 1; i <= 100000; ++i)
		++cnty[Find(i)];
	for(reg int i = 1; i <= N; ++i)
		if(!bk[Find(a[i].y)][a[i].x]) {
			++cntx[Find(a[i].y)];
			bk[Find(a[i].y)][a[i].x] = true;
		}
	for(reg int i = 1; i <= 100000; ++i)
		ans += cnty[i] * cntx[i];
	cout << ans - N << endl;
	return 0;
}

Measured memory_bytes: 9856
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;
#include<algorithm>



int main(){
     
    string s1,s2;
    
    cin>>s1>>s2;
    if(s1.size()>s2.size())cout<<"GREATER"<<endl;
    else if(s1.size()<s2.size())cout<<"LESS"<<endl;
    else{
        for(int i=0;i<s1.size();i++){
            if(s1[i]>s2[i]){
                cout<<"GREATER"<<endl;
                return 0;
            }
            else if(s1[i]<s2[i]){
                cout<<"LESS"<<endl;
                return 0;
            }
        }
        cout<<"EQUAL"<<endl;
    }
     
    return 0;
}
 

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

int main()
{
    long long h,w;
    long long s1,s2,s3,s4;
    cin >> h >> w;
    long long men = h*w;
    long long santou;
    if(men%3 == 0){
        cout << 0 << endl;
        return 0;
    }else{
        santou = min(h,w);
    }
    if(h%3 == 0){
        if(w%2 == 0){
            cout << 0 << endl;
            return 0;
        }else{
            s1 = (w+1)/2*h/3*2-men/3;
            s2 = s1;
        }
    }else{
        if(w%2 == 0){
            s1 = (h/3+1)*w-(h-(h/3+1))*w/2;
            s2 = (h-h/3)*w/2-h/3*w;
        }else{
            s1 = (h/3+1)*w-(h-(h/3+1))*(w-1)/2;
            s2 = (h-h/3)*(w+1)/2-h/3*w;
        }
    }
    if(w%3 == 0){
        if(h%2 == 0){
            cout << 0 << endl;
            return 0;
        }else{
            s3 = (h+1)/2*w/3*2-men/3;
            s4 = s1;
        }
    }else{
        if(h%2 == 0){
            s3 = (w/3+1)*h-(w-(w/3+1))*h/2;
            s4 = (w-w/3)*h/2-w/3*h;
        }else{
            s3 = (w/3+1)*h-(w-(w/3+1))*(h-1)/2;
            s4 = (w-w/3)*(h+1)/2-w/3*h;
        }
    }
    cout << min(santou,min(min(s1,s2),min(s3,s4))) << endl; 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define int long long int
#define mkp make_pair
#define maxN 100005
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<endl;
#define debug2(a,b) cout<<a<<' '<<b<<endl;
#define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,a,b) for(int i=a;i<b;i++)
#define pi pair<int,int>
#define pii pair<int,pi>
#define mp map<int,int>
#define ump unordered_map<int,int>
#define  vi vector<int>
#define st set<int>
#define mst multiset<int>
#define pq priority_queue
#define mpq priority_queue<int,vector<int>,greater<int> >
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define in cin>>
#define out cout<<
using namespace std;
void printArray(int arr[],int n)
{
   for(int i=0;i<n;i++)cout<<arr[i]<<' ';
}
 set<pair<int,int>> primeset;
void SieveOfEratosthenes(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
        for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p])
          primeset.insert(mkp(p,1));
}
int32_t main()
{
fastio;
int a;in a;int b;in b;
if(a>9 || b>9) out -1;
else out a*b;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD (int64_t)1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} // input vector

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

int N; cin >> N;
VI a(N), b(N); invec(a), invec(b);
vector<pair<int, bool>> events;
rep(i, 0, N){
    events.emplace_back(a[i], false);
    events.emplace_back(b[i], true);
}
sort(ALL(events));
i64 res = 1;
int cnt = 0;
for (pair<int, bool> e: events){
    if (cnt != 0 && (cnt>0) != e.second)
        res = (res * abs(cnt)) % MOD;
    cnt += (e.second ? 1 : -1);
}

cout << res << "\n";

return 0;
}
// 書いて考える．場合分け．情報整理．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 3956
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)

	m := map[int]bool{}

	var a int
	for i := 0; i < N; i++ {
		fmt.Scan(&a)
		if _, ok := m[a]; ok {
			delete(m, a)
		} else {
			m[a] = true
		}
	}

	ans := len(m)
	fmt.Println(ans)
}


Measured memory_bytes: 7552
import Data.STRef
import Control.Monad
import Control.Monad.ST
import Data.Maybe

rmChar :: Char -> String -> String
rmChar c xs = takeWhile (< c) xs ++ dropWhile (<= c) xs

smallest :: String -> Maybe Char
smallest s = runST $ do
  alphabetsRef <- newSTRef ['a'..'z']

  forM_ s $ \c -> do
    alphabets <- readSTRef alphabetsRef
    let newAlphabets = rmChar c alphabets

    writeSTRef alphabetsRef newAlphabets

  alphabetsRemnant <- readSTRef alphabetsRef

  if null alphabetsRemnant
    then return Nothing
    else return $ Just (head alphabetsRemnant)

main :: IO ()
main = do
  s <- getLine

  maybe (putStr "None") putChar $ smallest s


Measured memory_bytes: 21884
# coding: utf-8

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

res = 0
for i in range(N):
    atk = B[i] if B[i] <= A[i] else A[i]
    B[i] = B[i] - atk
    res = res + atk

    atk = B[i] if B[i] <= A[i+1] else A[i+1]
    A[i+1] = A[i+1] - atk
    B[i] = B[i] - atk
    res = res + atk

print(res)


Measured memory_bytes: 18380
#include <iostream>
#include <string>
#include <vector>

typedef long long ll;

int main(int argc, char* argv[])
{
  ll n;
  std::vector< ll > vc;
  std::vector< ll > vs;
  std::vector< ll > vf;
  std::vector< ll > vans;

  std::cin >> n;
  for (int i = 0; i < n-1; i++) {
    ll c, s, f;
    std::cin >> c >> s >> f;
    vc.push_back(c);
    vs.push_back(s);
    vf.push_back(f);
  }

  for (int start = 0; start < n; start++) {
    ll time = 0;
    for (int i = start; i < n-1; i++) {
      ll wait_time = 0;
      if (vs[i] >= time) {
	wait_time = vs[i] - time;
      } else {
	ll tmp = (time - vs[i]) % vf[i];
	wait_time = tmp == 0 ? 0 : vf[i] - tmp;
      }
      time += vc[i] + wait_time;
    }
    std::cout << time << std::endl;
  }

  return 0;
}


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

#define N 257
int main(void){
	int n,m,i,j;
	int type=0;
	char name[N][11];
	char str[11];
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%s",name[i]);

	scanf("%d",&m);

	while(m--){
		scanf("%s",str);
		for(i=0;i<n;i++){
			if(strcmp(str,name[i])==0){
				type = !type;
				if(type) printf("Opened by %s\n",str);
				else printf("Closed by %s\n",str);
				break;
			}
		}
		if(i==n) printf("Unknown %s\n",str);
	}
	return 0;
}

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

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

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

    if(a[0] != 0){ cout << -1 << endl; return 0; }

    long long int ans = 0;
    for(int i=1; i<n; i++){
        if(a[i] - a[i-1] >= 2){ cout << -1 << endl; return 0; }
        else if(a[i] - a[i-1] == 1) ans += 1;
        else ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4816
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    sort(v.begin(), v.end());
    int s = 0;
    for (int i = 0; i < n-1; ++i) {
        s += v[i];
    }
    puts(v[n-1] < s ? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 256
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdint.h>
#include <string.h>

int main(void) {
	uint32_t a, b;
	uint32_t goodCount = 0;

	scanf("%"PRIu32" %"PRIu32, &a, &b);
	printf("%"PRIu32, a - ((b >= a) ? 0 : 1));

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = 3.141592654;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw	 "\n"
#define mod 1000000007


int main(void)
{
	CIN;
	ll tc,l,k=0,sum=0,x=0,y,z=0,m=1,n=0,ans=0,cnt=0;
	cin>>n;
	for(ll i=2;i<=n;i++)
		m=((m%mod)*(i%mod))%mod;
	cout<<m;
}

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

using namespace std;

bool hoge[7368792];
int m,n;
int main(){
	while(true){
		cin >> m >> n;
		if(m == 0 && n == 0)return 0;
		for(int i = 0;i < 7368792;i++){
			hoge[i] = false;
		}
		for(int i = m;;i++){
			if(hoge[i])continue;
			if(n==0){
				cout << i << endl;
				break;
			}
			n--;
			for(long long j = i;j < 7368792;j+=i){
				hoge[j] = true;
			}
		}
	}
}

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

int main(){
  
  	int N=0, x=0, a=0, y=0, z=0;
  
  	cin >> N;
    
    x = N/100;
  	a = N%100;
  
  	y = a/10;
  	z = a%10;
  
  	cout << x+y+z << endl;
}

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

#define int long long

int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int N;
int n[20000];

signed main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int p;
        cin >> p;
        n[p - 1] = i;
    }
    for (int i = 0; i < N; i++) {
        cout << 1 + i * (N + 1) + n[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < N; i++) {
        cout << N * (N + 1) - i * (N + 1) << " ";
    }
    cout << endl;
    return 0;
}


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

using namespace std;

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

int n;

signed main()
{

    cin >> n;
    vector<int> b(n - 1);
    rep(i, n - 1)
    {
        cin >> b[i];
    }

    int ans = b[0];

    rep1(i, n - 1)
    {
        if (b[i] > b[i - 1])
        {
            ans += b[i - 1];
        }
        else
        {
            ans += b[i];
        }
    }

    ans += b[n - 2];

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int a[105]; 
int main()
{
   int n;cin>>n;double p=0.0;
   for(int i=1;i<=n;i++)
   {
   		cin>>a[i];
   }
   sort(a+1,a+1+n);
   p=(double)a[1];
   for(int i=2;i<=n;i++)
   		p=(double)(a[i]+p)/2.0;
   printf("%.8lf",p);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin>>a>>b;
    if(a+b==15)cout<<'+'<<endl;
    else
    if(a*b==15)cout<<'*'<<endl;
    else
    cout<<'x'<<endl;
    return 0;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
l = []
c = 0
k = 0

for i in range(n+1):
    k = i
    c = 0
    while (i > 0):
        c += i%10
        i //= 10
    if (a <= c <= b):
        l.append(k)

print(sum(l))


Measured memory_bytes: 9264
while True:
    a = [0]*11
    
    n = int(input())
    if n==0:
        break
    
    for i in range(n):
        b = int(input())
        a[b] += 1
        
    for i in range(10):
        if a[i]==0:
            print("-")
        else:
            print("*"*a[i])
    


Measured memory_bytes: 5624
def f(x):
    s=set()
    for i in range(1,int(x**(0.5))+6):
        if x%i==0: s.add(i);s.add(x//i)
    return s 


ans=set()
n=int(input())
ans=f(n-1)
ans1=f(n)
ans1.remove(1)

for x in ans1:
    p=n
    while p>=x:
        if p%x==0: p//=x
        else: p%=x
    if p==1: ans.add(x)

if 1 in ans: ans.remove(1)
print(len(ans))

Measured memory_bytes: 40304
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,j,tem,temp1;
	cin>>n;
	string s[n],temp;
	long long int a[n],b[n];
	for(i=0;i<n;i++)
	{
		cin>>s[i]>>a[i];
		b[i]=a[i];
	}
	for(i=0;i<n-1;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(s[i]>s[j])
			{
				temp=s[i];
				s[i]=s[j];
				s[j]=temp;
				temp1=a[i];
				a[i]=a[j];
				a[j]=temp1;
			}
		}
	}
	for(i=0;i<n-1;i++)
	{
	for(j=i+1;j<n;j++)
	{
		if(s[i]==s[j])	
		{
		if(a[i]<a[j])
		{
		tem=a[i];
		a[i]=a[j];
		a[j]=tem;	
		}	
		}
	}
    }
    for(i=0;i<n;i++)
    {
    	for(j=0;j<n;j++)
    	{
    		if(a[i]==b[j])
			{
			cout<<j+1<<endl;
			}
		}
	}
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
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;}
template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){return a/GCD(a,b)*b;}

int main(){
	ll n,c;
	cin >> n >> c;
	vector<pair<ll,ll>> v;
	ll x,a;
	FOR(i,n){
		cin >> x >> a;
		v.push_back(make_pair(x,a));
	}
	sort(all(v));
	vector<pair<ll,ll>> w=v;
	reverse(all(w));
	ll m[100010],m2[100010];
	m[0]=0,m2[0]=0;
	for(int i=1;i<=n;i++){
		m[i]=m[i-1]+v[i-1].second-v[i-1].first+((i!=1)?v[i-2].first:0ll);
		m2[i]=m2[i-1]+w[i-1].second-(c-w[i-1].first)+((i!=1)?c-w[i-2].first:0ll);
	}

	ll k[100010],k2[100010];
	k[0]=0;k2[0]=0;
	for(int i=1;i<=n;i++){
		k[i]=max(m2[i],k[i-1]);
		k2[i]=max(m[i],k2[i-1]);
	}

	ll ans=0;

	for(int i=1;i<=n;i++){
		chmax(ans,k[i]);
		chmax(ans,k2[i]);
		chmax(ans,m[i]+k[n-i]-v[i-1].first);
		chmax(ans,m2[i]+k2[n-i]-(c-w[i-1].first));
	}

	cout << ans << endl;



}

Measured memory_bytes: 6640
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1):
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 1
        if sum(poly) != 0 or A[N]%p != 0:
            check = 0
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)


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

using namespace std;

const int md = 1e9 + 7;

int main(){
  int a, b;
  cin >> a >> b;
    if (a == b)
        puts("Draw");
    else if ((a > b && b != 1) || a == 1)
            puts("Alice");
    else 
            puts("Bob");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>

int main()
{
	long r, D, x2000;
	
	std::cin >> r >> D >> x2000;

	long x = x2000;
	for (int i = 0; i < 10; ++i) {
		x = x * r - D;
		std::cout << x << "\n";
	}
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
ll a[200001];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,k;
	cin>>n>>k;
	ll sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n-k;i++){
		sum+=a[i];
	}
	cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a<=c&&c<=b) pr("Yes");
  else pr("No");
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
int main (){
  string a,b;
  cin >> a >> b;
  for(int i=0;i<3;i++){
      if(a[i]!=b[2-i]){
         cout << "NO" << endl;
         return 0;
         }
      }
     cout << "YES" << endl;
     return 0;
  }
    

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n,a,b,c=1;
    cin>>n>>a;
    for(int i=0;i<n-1;i++){
        cin>>b;
        if(a<=b){
            c++;
            a=b;
        }
    }
    cout<<c<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll 	 long long
#define pb push_back
#define mp make_pair
using namespace std;

int main()
{

string s; cin>>s;

vector<int>a;
int cnt=0;
for(int i=0; i<s.size(); i++)
{
	if(s[i]=='R')
	cnt++;
	if(s[i]=='S')
	{
		a.pb(cnt);
		cnt=0;
	}
	}	
a.pb(cnt);

sort(a.rbegin(), a.rend());

cout<<a[0]<<endl;

    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <cmath>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>

using namespace std;

int main() {
    long long n;
    long long ans = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        ans *= i;
        ans %= 1000000007;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound

int main(){
  int N;
  cin>>N;
  VI A(N),B(N);
  rep(i,N) cin>>A[i];
  rep(i,N) cin>>B[i];
  ll sum=0;
  rep(i,N) sum+=max(0,B[i]-A[i]);
  if(sum==0){
    cout<<0<<endl;
    return 0;
  }
  VI C;
  rep(i,N) if(A[i]>B[i]) C.pb(A[i]-B[i]);
  sort(all(C),greater<int>());
  ll tmp=0;
  rep(i,C.size()){
    tmp+=C[i];
    if(tmp>=sum){
      cout<<N-C.size()+i+1;
      return 0;
    }
  }
  cout<<-1<<endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define elif(a) else if(a)
#define INF INT_MAX
#define F first
#define S second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c;
  cin>>a>>b>>c;
  if(a==b && b==c) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}



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

main(){
  int i,n,sum=0;
  cin >> n;
  
  for(i=1;i<=n;i++){ 
  	size_t size = to_string(i).length();
    if (size%2==1){
      sum++;
    }
  }
  cout << sum << endl;
}
  
  

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

using namespace std;
using lint = long long;

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

lint n, x, m, w, cnt1, cnt2, sum1, res;
vector<lint>vec;
bool used[100010];
int main() {
	cin >> n >> x >> m;

	lint a1 = x;
	while (true) {
		used[a1] = true;
		vec.push_back(a1);
		a1 = a1 * a1 % m;
		if (used[a1]) {
			w = a1;
			break;
		}
	}

	cnt1 = find_if(vec.begin(), vec.end(), [=](lint x) { return w == x; }) - vec.begin();
	cnt2 = vec.size() - cnt1;

	if (n <= cnt1 + 1) {
		cout << accumulate(vec.begin(), vec.begin() + n, 0LL) << endl;
	}
	else {
		res = accumulate(vec.begin(), vec.begin() + cnt1, 0LL);

		n -= cnt1;
		sum1 = accumulate(vec.begin() + cnt1, vec.end(), 0LL);
		res += n / cnt2 * sum1;

		n %= cnt2;
		res += accumulate(vec.begin() + cnt1, vec.begin() + cnt1 + n, 0LL);
		cout << res << endl;
	}
}

Measured memory_bytes: 3924
n = int(input())
a = list(map(int,input().split()))
a.sort()
l = a[-1]
x = l // 2
y = 10 ** 12
z = 0
for i in range(n-1):
    if y >= abs(x-a[i]):
        y = abs(x-a[i])
        z = i
print(l,a[z])

Measured memory_bytes: 20028
<?php
  
while ($line = fgets(STDIN)) {
   $stdin[] = trim($line);
}
#$v2 = str_split($stdin[0]);
$v2 = explode(" ", $stdin[0]);

#dream dreamer erase eraser

#var_dump($v2);

if($v2[0] * $v2[1] < $v2[2]){
  $ans = $v2[0] * $v2[1];
}else{
  $ans = $v2[2];
}

echo $ans;

Measured memory_bytes: 3700
a,b,c=map(int,input().split())
k=int(input())
min_k=0

while b<=a:
    b=b*2
    min_k+=1
  
while c<=b:
    c=c*2
    min_k+=1
    
#print(min_k)
if min_k>k:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 61628
N,w = [int(x) for x in input().split()]
ll = []
for i in range(N):
    abc = [int(x) for x in input().split()]
    ll.append(abc)
DP = [[0]*(w+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,w+1):
        if ll[i-1][0] <= j:
            DP[i][j] = max(DP[i-1][j-ll[i-1][0]]+ll[i-1][1],DP[i-1][j])
        else:
            DP[i][j] = DP[i-1][j]
print(DP[N][w])

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

int main(){
    int a[5];
    int mini = 10000;
    int minic = 1000;
    int sum = 0;
    for(int i = 0;i < 5;i++)
    {
        cin >> a[i];
        if((mini > a[i] % 10) && (a[i] % 10 != 0)){
            minic = i;
        mini = min(mini,a[i] % 10);
        }
    }


    for(int i = 0;i < 5;i++)
    {
        if(i != minic){
            if(a[i] % 10 == 0){
                sum += a[i];
            }else{
            sum += a[i] + (10 - (a[i] % 10));
            }
        }
        else{
            sum += a[i];
        }
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define ll long long
#define endl "\n"
#define print_array(name,n) for(ll o=0;o<n;o++) cout<<name[o]<<" "
#define fr(i,f,t) for(ll i=(f);i<t;i++)
#define fb(i,f,t) for(ll i=(f);i>=t;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 2e18
bool sortbysecond(const pair<int,int> &a,const pair<int,int> &b){
	return (a.ss>b.ss);
}
template <typename T>
string NumberTostring(T Number )
{
	ostringstream ss;
	ss<<Number;
	return ss.str();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> vec(m,0);
    ll sum = 0;
    for(int i=0;i<m;i++){
    	cin>>vec[i];
    	sum+=vec[i];
    }
    ll ans = n-sum;
    if(ans>=0){
    	cout<<ans<<endl;
    }
    else{
    	cout<<-1<<endl;
    }
    return 0;
}

Measured memory_bytes: 3688
gcd(int n1,int n2){
    if(n2==0)return n1;
    else gcd(n2,n1%n2);
}
int main()
{
    int n1, n2, i, ans;
    scanf("%d %d",&n1,&n2);
    if(n1>n2)ans=gcd(n1,n2);
    else ans=gcd(n2,n1);
    printf("%d\n",ans);
    
    return 0;
}


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

int main() {
    string S;
    cin >> S;
    bool isSame = false;
    if(S.at(0) == S.at(1) && S.at(2) == S.at(3) && S.at(0) != S.at(2)) isSame = true;
    if(S.at(0) == S.at(2) && S.at(1) == S.at(3)&& S.at(0) != S.at(1)) isSame = true;
    if(S.at(1) == S.at(2) && S.at(0) == S.at(3)&& S.at(1) != S.at(0)) isSame = true;

    if(isSame == true){
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
/*
* @Author Silviase(@silviasetitech)
* For ProCon
*/

import java.util.*;
import java.lang.*;
import java.math.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] rab = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int tmp = sc.nextInt();
            rab[i] = tmp-1;
        }
        for (int i = 0; i < n; i++) {
            if (rab[rab[i]] == i) {
                ans++;
            }
        }
        System.out.println(ans/2);

        sc.close();
    }

}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edge(n, vector<int>(n));
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edge[a][b] = edge[b][a] = 1;
    }
    vector<int> v(n);
    for (int i = 0; i < n; ++i)
        v[i] = i;

    int ans = 0;
    do {
        int ok = 1;
        if (v[0] != 0) continue;
        for (int i = 0; i < n - 1; ++i) {
            if (!edge[v[i]][v[i + 1]]) {
                ok = 0;
                break;
            }
        }
        ans += ok;
    } while (next_permutation(v.begin(), v.end()));
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 29);

int main()
{
  int D, G;
  cin >> D >> G;
  vector<int> p(D), c(D);
  for (int i = 0; i < D; i++)
  {
    cin >> p.at(i) >> c.at(i);
  }
  int ans = INF;
  for (int bit = 0; bit < (1 << D); bit++)
  {
    int now = 0, cnt = 0;
    for (int i = 0; i < D; i++)
    {
      if (bit & (1 << i))
      {
        now += (100 * (i + 1) * p.at(i) + c.at(i));
        cnt += p.at(i);
      }
    }
    if (now >= G)
    {
      ans = min(ans, cnt);
    }
    else
    {
      for (int i = D - 1; i >= 0; i--)
      {
        if (!(bit & (1 << i)))
        {
          if ((G - now) < (100 * (i + 1)) * p.at(i))
          {
            cnt += (G - now) / (100 * (i + 1));
            if ((G - now) % (100 * (i + 1)))
            {
              cnt++;
            }
            ans = min(ans, cnt);
          }
          break;
        }
      }
    }
  }
  cout << ans << endl;
}

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

using namespace std;

#define MAX_N  101
#define MAX_W   100001
int N, W;
vector<vector<long long> >  Lookup(MAX_N,vector<long long> (MAX_W,-1));
//vector < vector long long> >  Lookup(MAX_N)(MAX_W);
vector<int> wei(MAX_N);
vector<long long> val(MAX_N);

long long Knapsack(int c,int  n){
	if(c==0|| n==0)return 0;
	if(Lookup[n][c]!=-1) return 	Lookup[n][c];
	if(c-wei[n]>=0)
		return Lookup[n][c] = max(Knapsack(c-wei[n],n-1)+val[n],Knapsack(c,n-1));
	return Knapsack(c,n-1);
	}
void fillDp(){
	for(int i =0;i<MAX_N;i++){
		for (int j=0;j<MAX_W;j++)
			Lookup[i][j]=-1;
	}	
}

int main(int argc, char** argv) 
{
	cin>>N>>W;
	for (int i =1;i<=N;i++){
		cin>>wei[i]>>val[i];
	}
	fillDp();
	cout<<Knapsack(W,N)<<endl;

	return 0;
}


Measured memory_bytes: 80256
n, m = map(int, input().split())
xtoy = []

for _ in range(m):
    a, b = map(int, input().split())
    xtoy.append([a, b])
    
exist_red = [0]*n
exist_red[0] = 1
exist_ball = [1]*n

for x, y in xtoy:
    if exist_red[x-1] == 1:
        exist_red[y-1] = 1
        
        if exist_ball[x-1] == 1:
            exist_red[x-1] = 0
    
    exist_ball[x-1] -= 1
    exist_ball[y-1] +=1
    

print(exist_red.count(1))  

Measured memory_bytes: 21064
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  map<int, int> amap;
  int tmp;
  for(int i=0;i<N;++i) {
    cin>>tmp;
    amap[tmp] = i+1;
  }
  for(int i=1;i<=N;++i) {
    cout<<amap[i]<<" ";
  }
  cout<<endl;
}



Measured memory_bytes: 8144
#include<stdio.h>
#define M 1000000
int main(){
  char p[M]={1,1};
  int i,c,j,a;
  for(i=2;i*i<M;i++){
    if(p[i])continue;
    for(j=i*i;j<M;j+=i)p[j]=1;
  }
  while(scanf("%d",&a)!=EOF){
    c=a+1;
    for(i=0;i<=a;i++)c-=p[i];
    printf("%d\n",c);
  }
  return 0;
}

      

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

int main() {
    int N;  cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];
    int M;  cin >> M;
    vector<string> T(M);
    for (int i = 0; i < M; i++) cin >> T[i];

    int ans = 0;
    for (string s : S) {
        int tmp = 0;
        for (int i = 0; i < N; i++) {
            tmp += S[i] == s;
        }
        for (int i = 0; i < M; i++) {
            tmp -= T[i] == s;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define vs vector<string>
#define vll vector<ll>
#define ii pair<int, int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>
#define ld long double
#define iii tuple<int, int, int>
#define sc scanf
#define pb push_back
#define FOR(i, x, n) for(int i=x; i<=n; ++i)
#define ROF(i, x, n) for(int i=x; i>=n; --i)
#define MOD 1000000007
#define F first
#define S second

int main() {
    
    int x;
    sc("%d", &x);
    
    if(x == 0) {
        printf("1\n");
    }
    else {
        printf("0\n");
    }
}



Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=1000000000;



int main(){
    int a,b,c;cin >> a >> b >> c;
    cout << a*b/2 << endl;
    return 0;
}


Measured memory_bytes: 256
t = 0
while t == 0:	
	try:
		x,y=[int(i) for i in input().split()]
	except:
		break
	else:
		a = x * y
		if x < y:
			x,y =y,x
		while y > 0:
			r = x % y
			x = y
			y = r
	print(str(x) + " " + str(int(a / x)))

Measured memory_bytes: 7608
from fractions import gcd  # use math.gcd for python 3.5~


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    A.sort()
    print(min([gcd(A[0], a) for a in A[1:]]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 16276
#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define f first
	#define s second
	
	using namespace std;
	

	int main()
	{
		std::ios::sync_with_stdio(false);
		
		ll h,w;
		cin>>h>>w;
		char arr[h+1][w+1];
		for(ll i=0; i<h; i++) {
			for(ll j=0; j<w; j++) {
				cin>>arr[i][j];
			}
		}

		ll dp[h+1][w+1];

		memset(dp,0,sizeof(dp));
		ll tag = 0;
		for(ll i=1; i<h; i++) {
			if(arr[i][0] == '.' && tag == 0) {
				dp[i][0] = 1;	
			}
			else {
				tag = 1;
			}
			
		}

		tag = 0;
		for(ll j=0; j<w; j++) {
			if(arr[0][j] == '.' && tag == 0) {
				dp[0][j] = 1;
			}
			else {
				tag = 1;
			}
			
		}

		for(ll i=1; i<h; i++) {
			for(ll j=1; j<w; j++) {
				if(arr[i][j] == '.') {
					dp[i][j] += (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
				}
			}
		}

		cout<<dp[h-1][w-1]<<endl;

		return 0;
	}


Measured memory_bytes: 12384
/*
    Author - Param Kothari
    Ah shit, here we go again
*/

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

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define mk make_pair

typedef long long ll;
typedef long double ld;

void solve(){
    int res = 0;
    for(int i = 1; i <= 5; i++){
        int x;
        cin >> x;
        if(x == 0){
            res = i;
            break;
        }
    }
    cout << res << "\n";
    return;
}

int main(){
    IOS;
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
    return 0;
}

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

int main() {
    ll N, A, B;

    cin >> N >> A >> B;

    if ((B - A) % 2 == 0) {
        cout << (B - A) / 2 << endl;
    }
    else {
        cout << min(A - 1, N - B) + 1 + (B - A - 1) / 2 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll q;
  cin >>q;
  vector<int>prime(100010,0);
  rep(i,100000){
    if((i+1)%2==1 && is_prime(i+1) && is_prime((i+2)/2)){
      prime[i+1]=1;
    }
  }
  rep(i,100005){
    prime[i+1]+=prime[i];
  }
  rep(i,q){
    int l,r;
    cin >> l >> r;
    cout << prime[r]-prime[l-1] << endl;
  }
  
}


Measured memory_bytes: 1024
/*  UntilDeathDoesUsApart
    DO   NOT   GIVE   UP!
*/

#include <bits/stdc++.h>

using namespace std;

#define inc(a)           a.begin(), a.end()
#define dec(a)           a.rbegin(), a.rend()
#define Unique(n)        (n).erase(unique(in(n)), (n).end())
#define to(i, a, n)      for(int i=a; i<n; i++)
#define fr(i, a, n)      for(int i=a; i>=n; i--)
#define read(arr, l, r)  for(int i=l; i<r; cin >> arr[i++])
#define prnt(arr, l, r)  for(int i=l; i<r; cout << arr[i++] << " \n"[i==r])

typedef long long ll;
typedef long double ld;

unsigned long long Pow(long long base, long long power){  /// mod?
    if(power==0)
        return 1;
    if(power==1)
        return base;

    unsigned long long ans = Pow(base, power/2); /// mod?
    ans *= ans; /// ((ans%mod)*(ans%mod))%mod;

    if(power&1)
        return ans*base; /// ((ans%mod)*(base%mod))%mod;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n; cin >> n;
    for(int i=-1001; i<=1001; i++)
        for(int j=-1001; j<=1001; j++)
            if(Pow(i, 5) - Pow(j, 5) == n)
                return cout << i << ' ' << j, 0;


    return 0;
}


Measured memory_bytes: 3604
# coding: utf-8
# Your code here!

A,B,K = list(map(int,input().split(" ")))
ans = []
for i in range(K):
    if A<=A+i<=B:
        ans.append(A+i)
    if A<=B-i<=B:
        ans.append(B-i)
ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)
        

Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;

fn solve(d: f64) -> f64{
    let mut max = d;
    let mut x: f64 = 1.0;
    while x <= d {
        let y = (d * d - x * x).sqrt();
        let mut local_min = x + y;
        if y < 1.0 {
            local_min = x + 1.0;
        }
        if max < local_min {
            max = local_min;
        }
        x += 1.0;
    }

    if max < d * 2.0_f64.sqrt() {
        max = d * 2.0_f64.sqrt();
    }
    max
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();

    let d: f64 = iter.next().unwrap().parse().unwrap();
    println!("{:.12}", solve(d));
}



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

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

    priority_queue<int> que;
    for(int i = 0; i < W; i++) {
        int a; cin >> a;
        if(a != 0) que.push(a);
    }

    bool yes = true;
    for(int i = 0; i < H; i++){
        int b; cin >> b;

        if(que.size() < b) {
            yes = false;
            break;
        }
        queue<int> used;
        while(b){
            used.push(que.top() - 1);
            que.pop();
            b--;
        }
        while(!used.empty()){
            if(used.front() != 0) que.push(used.front());
            used.pop();
        }
    }

    cout << yes << endl;

}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
int c=0,n;
vector<int> ans(12);
void dfs(int digit,int now){
  if(digit==0){
    c++;
    if(c==n){
      ans[digit]=now;
      return;
    }
  }else{
    if(now!=0){
      dfs(digit-1,now-1);
      if(c==n){
        ans[digit]=now;
        return;
      }
    }
      dfs(digit-1,now);
      if(c==n){
        ans[digit]=now;
        return;
      }
    if(now!=9){
      dfs(digit-1,now+1);
      if(c==n){
        ans[digit]=now;
        return;
      }
    }
  }
}
      
int main(){
  cin>>n;
  int d=0;
  while(true){
    reps(i,1,10){
      dfs(d,i);
      if(c==n){
        for(int j=d;j>=0;j--){
          cout<<ans[j];
        }
        return 0;
      }
    }
    d++;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#define int long long
#define ll long long
#define mod  1000000007
#define MOD  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
#define ps push_back
#define all(x) x.begin(),x.end()
double pi = 3.141592653589793;
using namespace std;
//ここから始めよう
int dp[111][11111];//i番目、価値jの時の最小の重さ
signed main(){
    int n,w;cin>>n>>w;
    rep(i,0,n+1)rep(j,0,111110){
        dp[i][j]=mod;
    }
    dp[0][0]=0;
    rep(i,1,n+1){
        int a,b;cin>>a>>b;
        for(int j=111100;j>=0;j--){
            if(j>=b)dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a);
            else dp[i][j]=dp[i-1][j];
            //cout<<dp[i][j]<<" ";
        }//cout<<endl;
    }
    for(int i=100002;i>=0;i--){
        //cout<<dp[n][i]<<" ";
        if(dp[n][i]<=w){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

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

#define N 3
#define LIM 32
#define HN 362897

struct dep{
  int depth,key;
};

int ans[N][N]={
  {1,2,3},
  {4,5,6},
  {7,8,0}
};

int min = LIM;
struct dep h[HN];

int hash1(int k)
{
  return k % HN;
}
int hash2(int k)
{
  return 1 + k%(HN-1);
}
int hash(int k, int i)
{
  return (hash1(k) + i*hash2(k))%HN;
}


void dfs(int p[N][N], int n)
{
  int i,j,i0,j0,a=0,b=1;
  int f=0;
  int tmp[N][N];
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      if(ans[i][j]!=p[i][j])f++;
      if(p[i][j]==0)
      {
        i0=i;
        j0=j;
      }
      a+=p[i][j]*b;
      b*=10;
    }
  }

  if(f==0)
  {
    if(min>=n)
    {
      min=n;
    }
    return;
  }
  if(n>min) return;
  i=0;
  while(1)
  {
    b=hash(a, i);
    if(h[b].key == 0)
    {
      h[b].key=a;
      h[b].depth=n;
      break;
    }
    else if(h[b].key == a)
    {
      if(h[b].depth>n)
      {
        h[b].depth=n;
        break;
      }
      else return;
    }
    i++;
  }

  if(i0>0 && i0<N)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0-1][j0];
    tmp[i0-1][j0]=f;
    dfs(tmp, n+1);
  }
  if(j0>0 && j0<N)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0][j0-1];
    tmp[i0][j0-1]=f;
    dfs(tmp, n+1);
  }

  if(i0>=0 && i0<N-1)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0+1][j0];
    tmp[i0+1][j0]=f;
    dfs(tmp, n+1);
  }
  if(j0>=0 && j0<N-1)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0][j0+1];
    tmp[i0][j0+1]=f;
    dfs(tmp, n+1);
  }

}

int main()
{
  int i,j;
  int p[N][N];

  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      scanf("%d",&p[i][j]);
    }
  }
  dfs(p,0);

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

  return 0;
}



Measured memory_bytes: 4624