akhauriyash/Code-Regression huggingface dataset:
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>
using namespace std;

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 100005
#define LOG_MAX 20
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define in(x) scanf("%d", &x)
#define inl(x) scanf("%lld", &x)
#define in2(x, y) scanf("%d %d", &x, &y)
#define inl2(x, y) scanf("%lld %lld", &x, &y)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const char en = '\n';

void solve() {
	int n, x;
	in2(x, n);
	
	if(n == 0) {cout<<x<<en; return;}
	
	int a;
	int f[105] = {0};
	for(int i=0;i<n;i++) {in(a);f[a]++;}
	
	int mini = INT_MAX, ans = -1;
	for(int i=0;i<=101;i++) {
		if(f[i] == 0 && mini > abs(i-x)) {
			mini = abs(i-x);
			ans = i;
		}
	}

	cout<<ans<<en;
}

int main() {
	int t = 1;
	
	//~cin>>t;
	while(t--) {
		solve();
	}
    return 0;
}


Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t N;
  cin >> N;
  vector<pair<int64_t, int>> table;
  
  int y = 0;
  while (N % 2 == 0) {
    N /= 2;
    y++ ;
    if ( N % 2 != 0) {
     table.emplace_back(2,y);
    }
   }
  
  int64_t i = 3;
  while (i*i < N ) {
    int x = 0;
    while (N % i == 0) {
      N /= i;
      x++ ;
    }
    if (x != 0) {
    table.emplace_back(i,x);
    }
    i += 2;
  }
  
  if (N != 1) {
    table.emplace_back(N, 1);
  }
  
  
  /*for (int i = 0; i < table.size(); i++) {
   	cout << table.at(i).first << " " << table.at(i).second <<endl;
  }*/
  
  int ans = 0;
  
  for (int i = 0; i < table.size(); i++) {
    int y = table.at(i).second;
    int b = 1;
    while (y >= b ) {
      ans++ ;
      y -= b; 
      b++ ;
    }
  }
  
   cout << ans << endl;
  
  return 0;
}


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

int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  cout << (char)toupper(s1[0])
       << (char)toupper(s2[0])
       << (char)toupper(s3[0])
       << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define ull unsigned long long int
#define ll long long int
#define pb push_back
 
#define PI 3.1415926535897932385
#define INF 1e18
#define EPS 1e-7
#define MOD 1000000007 
                                 
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
ll exp(ll x, ll y, ll p)
{
    ll res = 1;   
    x = x % p;  
    while (y > 0)
    {
        if (y & 1)    
            res = (res*x) % p;
        y = y>>1;     
        x = (x*x) % p; 
    }
    return res;
}

 
int main() {
   
    fastio;
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll x = a * c;
    x = max(x, a * d);
    x = max(x, b * d);
    x = max(x, b * c);
    cout << x;
 
    return 0; 
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; 

int main(){
  int n;
  cin >> n;
  if(n == 1 || n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 || n == 15 || n == 17 || n == 19 || n == 23 || n == 29 || n == 31){
    cout << 1 << endl;
    return 0;
  }
  if(n == 4 || n == 6 || n == 9 || n == 10 | n == 14 || n == 21 || n == 22 || n == 25 || n == 26){
    cout << 2 << endl;
    return 0;
  }
  if(n == 8 || n == 12 || n == 18 || n == 20 || n == 27){
    cout << 5 << endl;
    return 0;
  }
  if(n == 16){
    cout << 14 << endl;
    return 0;
  }
  if(n == 28 || n == 30){
    cout << 4 << endl;
  }
  if(n == 24){
    cout << 15 << endl;
    return 0;
  }
  if(n == 32){
    cout << 51 << endl;
  }
}

Measured memory_bytes: 256
W, H ,N = [int(i) for i in input().split()]
X = [0, W]
Y = [0, H]
for _ in range(N):
    x, y, a = [int(i) for i in input().split()]
    if a == 1:
        X = [max(X[0], x), X[1]]
        if X[0] >= X[1]:
            break
    elif a == 2:
        X = [X[0], min(X[1], x)]
        if X[0] >= X[1]:
            break
    elif a == 3:
        Y = [max(Y[0], y), Y[1]]
        if Y[0] >= Y[1]:
            break
    else:
        Y = [Y[0], min(Y[1], y)]
        if Y[0] >= Y[1]:
            break
print(max(0, X[1] - X[0]) * max(0, Y[1] - Y[0]))

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

int n;
int ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		ans+=x-1;
	}
	printf("%d",ans);
	return 0;
}

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

int n;
int a[20];

bool rep(int ans,int val,int pos){

    if(ans == val){
        return true;
    }
    if(pos == n){
        return false;
    }

    return rep(ans,val,pos+1) || rep(ans,val+a[pos],pos+1);

}

int main() {

    cin >> n;

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

    int q;

    cin >> q;

    int m;

    for(int i=0;i<q;i++){
        cin >> m;
        if(rep(m,0,0)){
            cout << "yes" << endl;
        }
        else{
            cout << "no" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3092
n, k = map(int, input().split())

ks = [i for i in range(k, n + 1, k)] #n以下のkの倍数のリスト

count = len(ks) ** 3 #a,b,c全てがkの倍数のときの組み合わせ

if k % 2 == 0:
  khalfs = [i for i in range(k // 2, n + 1, k)] #n以下で、kで割った余りがk / 2になる数のリスト
  count += len(khalfs) ** 3 #a,b,c全てが余りk / 2のときの組み合わせをcountに追加する

print(count)

Measured memory_bytes: 11032
#include<iostream>
using namespace std;
int main() {

	int n, m, l;

	cin >> n >> m >> l;

	long long a[101][101] = { 0 };
	long b[101][101] = { 0 };

	long c[101][101] = { 0 };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < l; j++) {
			cin >> b[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < l; j++) {
			for (int k = 0; k < m; k++) {
				c[i][j] += a[i][k] * b[k][j];
			}
			cout << c[i][j];
			if (j != l-1) cout << " ";
		}
		cout << endl;
	}



	return 0;

}



Measured memory_bytes: 3348
#include <stdio.h>
#define show {printf("l:%d r:%d next:%d\n",top[0],top[1],b[i]);}

int main(void){
	int n, b[10], top[2]={0,0}, i, t;
	
	scanf("%d",&n);
	
	for(;n--;){
		scanf("%d %d %d %d %d %d %d %d %d %d",&b[0],&b[1],&b[2],&b[3],&b[4],&b[5],&b[6],&b[7],&b[8],&b[9]);
		
		top[0]=0, top[1]=0;

		for(i=0; i<10; i++){
			if(top[0]>b[i] && top[1]>b[i]) break;
			
			t=(top[0]>top[1])?0:1;
			
			if(top[t]<b[i]) top[t]=b[i];
			else top[!t]=b[i];
		}

		if(i==10) printf("YES\n");
		else printf("NO\n");
	}
	
	return 0;
}

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

int main() {
  string S, T;
  cin >> S >> T;
  int count = 0;
  
  for (int i = 0; i < 3; i++) {
    if (S.at(i) == T.at(i)) count++;
  }
  
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>	
#define inf ll(1e18)
using namespace std;
typedef long long ll;

int main()
{
    char a[10];
    int sum = 0;
    for (int i = 1; i <= 3; i++) {
        scanf("%c", &a[i]);
        if (a[i] == 'R')sum = 1;
    }
   
    for (int i = 1; i < 3; i++) {
        if (a[i] == 'R' && a[i + 1] == 'R') {
            sum++;
        }
    }
    printf("%d", sum);
    return 0;
}

Measured memory_bytes: 3824
#include<bits/stdc++.h>
using namespace std;
int a,b,s,ans;
int main() {
	cin >> a >> b;
	if (b == 1)
		ans = 0;
	else {
		s = a;
		ans = 1;
		while(s < b) {
			s = s + a - 1;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  ll a[n];
  rep(i,n) cin >> a[i];
  ll sum[n];
  sum[0]=a[0];
  ll ans=0;
  if(sum[0]==0){
    ans=1;
    sum[0]=1;
  }
  rep1(i,n-1){
    ll t=sum[i-1]+a[i];
    //    cout << sum[i-1] << endl;
    if(t==0){
      ans+=1;
      sum[i]=-abs(sum[i-1])/sum[i-1];
    }
    else if(abs(t)/t != abs(sum[i-1])/sum[i-1]){
      sum[i]=t;
    }
    else{
      ans += abs(t)+1;
      sum[i]=-abs(t)/t;
    }
  }
  //  rep(i,n) cout << sum[i] << endl;
  ll ans2=0;
  if(a[0]==0){
    ans2=1;
    sum[0]=-1;
  }else{
    sum[0]=-abs(a[0])/a[0];
    ans2=abs(a[0])+1;
  }
  rep1(i,n-1){
    ll t=sum[i-1]+a[i];
    if(t==0){
      ans2+=1;
      sum[i]=-abs(sum[i-1])/sum[i-1];
    }
    else if(abs(t)/t != abs(sum[i-1])/sum[i-1]){
      sum[i]=t;
    }
    else{
      ans2 += abs(t)+1;
      sum[i]=-abs(t)/t;
    }
  }

  
  
  cout << min(ans,ans2) << endl;

  
  return 0;
    

}


Measured memory_bytes: 1792
#include<stdio.h>

int main(){

	int x, y;
	int i;
	while(1){
		scanf("%d %d",&x, &y);
		if (x == 0 && y == 0) break;
		if (x > y){ printf("%d %d\n", y, x); }
		else{ printf("%d %d\n", x, y); }
	}
	
	return 0;
}


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

int main(){
    ll N;
    cin >> N;
    vector<ll> H(N);
    for(int i=0; i<N; i++)cin >> H[i];
    ll maxh = 0;
    bool check = true;
    ll cnt = 0;
    for (int i = 1; i < N; i++) {
        if(H[i]==H[i-1]-1){
          H[i]++;
        }
        else if(H[i]<H[i-1]-1){
          check = false;
          break;
        }
    }
    if(check) cout << "Yes" << endl;
    else
      cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 4032
// God put a smile upon your face <3

#include <bits/stdc++.h>`

#define slld(longvalue) scanf("%lld", &longvalue)

#define ll long long
#define ull unsigned long long
#define pll pair < long long, long long >

#define fastio ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0)

#define pb push_back

#define bug printf("BUG\n")

#define mxlld LLONG_MAX
#define mnlld -LLONG_MAX

#define mxd 2e8
#define mnd -2e8

#define pi 3.14159265359

#define mod 958585860497

#define base 2001487

using namespace std;

bool check(ll n, ll pos)
{
    return n & (1LL << pos);
}

ll Set(ll n, ll pos)
{
    return n = n | (1LL << pos);
}


double calc(double h, double m)
{
    double hh = 0.5 * (h * 60 + m);
    double mm = (6 * m);

    double ang = abs(hh - mm);

    ang = min(ang,360-ang);

    ang = (acos(-1.0) * ang) / 180;

    return ang;
}

double calcAngle(double h, double m)
{

    double hour_angle = 0.5 * (h * 60 + m);
    double minute_angle = 6 * m;


    double angle = abs(hour_angle - minute_angle);

    angle = min(360 - angle, angle);

    angle = (angle / 180) * pi;
    return angle;
}
int main()
{
    ll i, j, k, l, m, n, o, r, q;
    ll testcase;
    ll input, flag, tag, ans;

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

//    freopen("output.txt", "w", stdout);

    while(cin >> n >> m >> l >> r)
    {
        double ang = calc(l,r);

//        cout << ang << " " << cos(ang) << endl;

        double c = (n * n) + (m * m) - (2 * n * m * cos(ang));

        printf("%.10f\n", sqrt(c));
    }
}






Measured memory_bytes: 4112
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

int main()
{
    string s;
    int num = 0;
    vector<int> rhombus;

    // Input
    while (cin >> s) {
        for (int i = 0; i < s.size(); i++) {
            int n = s[i++] - '0';
            while ('0' <= s[i] && s[i] <= '9') 
                n = n * 10 + (s[i++] - '0');

            rhombus.push_back(n);
            num++;
        }
    }

    int index = 1;
    for (int i = 2; i * i <= num; i++) {
        rhombus[index] += rhombus[index - i + 1];
        index++;
        for (int j = 1; j <= i - 2; j++) {
            rhombus[index] += max(rhombus[index - i], rhombus[index - i + 1]);
            index++;
        }
        rhombus[index] += rhombus[index - i];
        index++;
    }
    for (int i = sqrt(num) - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            rhombus[index] += max(rhombus[index - i - 1], rhombus[index - i]);
            index++;
        }
    }

    cout << rhombus[num - 1] << endl;

    return 0;
}

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

using namespace std;

struct shop{
	int64_t nedan;
	int64_t honsu;
};

struct shop buf[110000];

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

	for(int i = 0; i < n; ++i){
		cin >> buf[i].nedan >> buf[i].honsu;
	}

	sort(buf, buf+n, [](const shop& x, const shop& y) { return x.nedan < y.nedan; });

	int64_t sum = 0;
	int64_t value = 0;

	for(int i = 0; i < n; ++i){
		int64_t tmp_sum = sum + buf[i].honsu;
		if(tmp_sum >= m){
			value += (m-sum) * buf[i].nedan;
			break;
		}else{
			sum += buf[i].honsu;
			value += buf[i].nedan * buf[i].honsu;
		}
	}

	cout << value << endl;

	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<map>
#include<set>
//#include <Eigen/Dense>
//#include <Eigen/Geometry>
//using namespace Eigen;

using namespace std;


const int mod = 2019;


string s;
int a[200005],res[200005];
int main() 
{
	cin >> s;
	for (int i = 0; i < s.size(); i++)
		a[i] = s[i] - '0';
	
	int b = 1;
	int ans = 0;
	long long temp = 0;
	res[0] = 1;
	for (int i = s.size() - 1; i >= 0; i--)
	{
		temp += a[i] * b%mod;
		temp %= mod;
		b = b * 10 % mod;
		ans += res[temp];
		res[temp]++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4492
from itertools import chain
from collections import Counter
H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = Counter(list(chain.from_iterable([list(map(int, input().split())) for _ in range(H)])))
for _ in range(100):
    for i in range(10):
        for j in range(10):
            c = min([C[i][k] + C[k][j] for k in range(10)])
            C[i][j] = min(c, C[i][j])
num = 0
for i, n in A.items():
    if i == -1:
        continue
    num += C[i][1] * n
print(num)


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

class UnionFindTree {
public:
  vector<int> per, rank;
  void init(int n) {
    per.resize(n,0);
    rank.resize(n,0);
    for (int i=0; i<n; i++) {
      per[i]=i;
      rank[i]=0;
    }
  }
  int find(int x) {
    if (x==per[x]) {
      return x;
    } else {
      per[x]=find(per[x]);
      return per[x];
    }
  }
  void unite(int x,int y) {
    x=find(per[x]);
    y=find(per[y]);
    if (x==y) {
      return ;
    }
    if (rank[x]<rank[y]) {
      per[x]=y;
    } else {
      per[y]=x;
      if (rank[x]==rank[y]) {
        rank[x]++;
      }
    }
  }
  bool same(int x,int y) {
    x=find(x);
    y=find(y);
    return x==y;
  }
};
int main() {
  int n, q;
  cin >> n >> q;
  UnionFindTree S;
  S.init(n);
  while (q--) {
    int com, x, y;
    cin >> com >> x >> y;
    if (!com) {
      S.unite(x,y);
    } else {
      printf("%d\n",S.same(x,y));
    }
  }
  return 0;
}

Measured memory_bytes: 3236
package main

import (
	"fmt"
)

func main() {
	var str string
	fmt.Scanf("%s", &str)
	fmt.Printf("%s\n", strReverse(str))
}

func strReverse(str string) string {
	data := []rune(str)
	result := []rune{}

	for i := len(data) - 1; i >= 0; i-- {
		result = append(result, data[i])
	}

	return string(result)
}



Measured memory_bytes: 1088
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int main()
{
    int a,b,c,k;
    scanf("%d %d %d %d",&a,&b,&c,&k);
    int ca=min(k,a);
    k-=ca,ans+=ca;
    int cb=min(k,b);
    k-=cb;
    if(k)
    {
        ans-=k;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 3844
s = input().strip()
t = input().strip()

csa = [0]
csb = [0]
for ch in s:
  if ch == "A":
    csa.append(csa[-1]+1)
    csb.append(csb[-1])
  else:  
    csa.append(csa[-1])
    csb.append(csb[-1]+1)
cta = [0]
ctb = [0]
for ch in t:
  if ch == "A":
    cta.append(cta[-1]+1)
    ctb.append(ctb[-1])
  else:  
    cta.append(cta[-1])
    ctb.append(ctb[-1]+1)
    
Q = int(input())
for q in range(Q):
  a, b, c, d = map(int, input().split())
  sa = csa[b] - csa[a-1]
  sb = csb[b] - csb[a-1]
  ta = cta[d] - cta[c-1]
  tb = ctb[d] - ctb[c-1]
  if (sa - sb + tb - ta) % 3:
    print("NO")
  else:  
    print("YES")


Measured memory_bytes: 13396
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    p = [[] for _ in range(n)]

    for i in range(m):
        ai, bi = map(int, input().split())

        ai -= 1
        bi -= 1

        p[ai].append(h[bi])
        p[bi].append(h[ai])

    ans = 0

    for index, pi in enumerate(p):
        p_count = len(pi)

        if p_count == 0:
            ans += 1
            continue

        pmax = max(pi)

        if h[index] > pmax:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 23120
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
  int N,H; cin >> N >> H;
  vector<ll> a(N),b(N);
  rep(i,N){
     cin >> a[i] >> b[i];
  }
  sort(a.begin(),a.end(),greater<ll>());
  sort(b.begin(),b.end(),greater<ll>());
  ll sum = 0;
  int cnt = 0;
  rep(i,N){
     if(b[i] > a[0]){
        sum += b[i];
        cnt++;
        if(sum >= H) break;
     }
  }
  if(sum >= H){
     cout << cnt << endl;
     return 0;
  }
  while(true){
     sum += a[0];
     cnt++;
     if(sum >= H){
        cout << cnt << endl;
        return 0;
     }
  }
}



Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(void) {
    int N, X;
    cin >> N >> X;
    int ans = 1;
    int d = 0;
    for(int i=0; i<N; i++) {
        int L;
        cin >> L;
        d += L;
        if(d <= X) {
            ans ++;
        } else {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = fact[1] = 1;
    for(int i=2; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
}

void create_seq_inv_mod(int num){
    seq_inv[0] = seq_inv[1] = 1;
    for(int i=2; i<=num; i++) seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
}

void create_fact_inv_mod(int num){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i=2; i<=num; i++) fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int main(){
    int N;
    cin >> N;
    create_mod_tables(N);
    int64_t ans = power_mod(3, N);
    for(int k=N/2+1; k<=N; k++){
        int64_t res = 2 * comb_mod(N, k) * power_mod(2, N-k) % MOD;
        add(ans, MOD - res);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 234624
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

ll inf=1ll<<60,mod=1e9+7;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll n,m,i,ans=1;
	cin>>n>>m;
	if (n==m){
		for (i=2;i<=n;i++){
			ans=(ans*i)%mod;
		}
		ans=(2*ans*ans)%mod;
	}
	else if (abs(n-m)==1){
		ans=min(n,m);
		for (i=ans-1;i>=2;i--){
			ans=(ans*i)%mod;
		}
		ans=(ans*ans)%mod;
		ans=(max(m,n)*ans)%mod;
	}
	else {
		ans=0;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)

array<array<int,10>,10> r;

bool get(){
	rep(i,10)rep(j,10) if(!(cin>>r[i][j])) return false;
	return true;	
}

int calc(vi v){
	int ret=0;
	rep(i,4) ret=r[ret][v[i]];
	return ret;
}

bool isValid(int n){
	vi v={n/1000%10, n/100%10, n/10%10, n%10, -1};
	v[4]=calc(v);
	vi l;
	rep(i,5)rep(j,10){
		if(v[i]!=j) {
			auto tmp=v; tmp[i]=j;
			if(r[calc(tmp)][tmp[4]]==0) return false; 
		}
	}
	rep(i,4){
		if(v[i]!=v[i+1]){
			auto tmp=v; swap(tmp[i],tmp[i+1]);
			if(r[calc(tmp)][tmp[4]]==0) return false; 			
		}
	}
	return true;
}

int solve(){
	int ans=0;
	rep(i,10000) if(!isValid(i)) ans++;
	return ans;	
}

int main(){
	while(get()){
		cout<<solve()<<endl;
	}
	return 0;
}



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

//まるでわからん。
int main(){
    cout<<setprecision(10);
    double x[3],y[3];
    rep(i,3){
        cin>>x[i]>>y[i];
    }
    double s=abs((x[0]-x[2])*(y[1]-y[2])-(x[1]-x[2])*(y[0]-y[2]))*0.5;

    double a=(x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1]);
    double b=(x[1]-x[2])*(x[1]-x[2])+(y[1]-y[2])*(y[1]-y[2]);
    double c=(x[2]-x[0])*(x[2]-x[0])+(y[2]-y[0])*(y[2]-y[0]);
    a=sqrt(a);b=sqrt(b);c=sqrt(c);

    double r=2*s/(a+b+c);
    double m=max({a,b,c});
    double ans=m*r/(2.0*r+m);
    cout<<ans<<endl;
    return 0;
}

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

int main(){
    int s,w;
    cin >> s >> w;
    if(s<=w)cout<<"unsafe"<<endl;
    else cout<<"safe"<<endl;
    return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>

int main(){

    int i, n;
    scanf("%d\n", &n);
    int a[n];

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

    for ( i = n - 1 ; i >= 0 ; i-- ){
    	printf("%d", a[i]);
    	if (i) printf(" ") ;
    }

    printf("\n");

    return 0;
}

Measured memory_bytes: 600
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] aArr = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            aArr[i] = sc.nextInt();
            sum += aArr[i];
        }

        System.out.println(sum%2 == 0 ? "YES" : "NO");
    }
}


Measured memory_bytes: 50792
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

constexpr int mod = 10000;
constexpr int MAX_DIGIT = 500;
constexpr int MAX_M = 500;

int dp[MAX_DIGIT + 1][MAX_M][10][2][2]; // digit, modulo m, prev, less flag, zig-zag flag

int calc(const string &limit, int m) {
	const int n = limit.size();

	memset(dp, 0, sizeof(dp));

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < 10; ++j) {
			const bool lt = (j < limit[i] - '0');
			const bool le = (j <= limit[i] - '0');

			if(j && (i || le)) {
				(dp[i + 1][j % m][j][i || lt][true] += 1) %= mod;
				(dp[i + 1][j % m][j][i || lt][false] += 1) %= mod;
			}

			for(int k = 0; k < m; ++k) {
				const int next_rest = (k * 10 + j) % m;

				for(int l = 0; l < j; ++l) {
					(dp[i + 1][next_rest][j][true][true] += dp[i][k][l][true][false]) %= mod;

					if(le) {
						(dp[i + 1][next_rest][j][lt][true] += dp[i][k][l][false][false]) %= mod;
					}
				}

				for(int l = j + 1; l < 10; ++l) {
					(dp[i + 1][next_rest][j][true][false] += dp[i][k][l][true][true]) %= mod;

					if(le) {
						(dp[i + 1][next_rest][j][lt][false] += dp[i][k][l][false][true]) %= mod;
					}
				}
			}
		}
	}

	int res = 0;
	for(int i = 0; i < 10; ++i) {
		res += dp[n][0][i][true][true];
		res += dp[n][0][i][true][false];

		if(i && (n > 1 || i < limit.back() - '0') && i % m == 0) {
			--res;
		}
	}

	return res % mod;
}

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

	string a, b;
	int m;

	cin >> a >> b >> m;

	int carry = 1;
	for(int i = b.size() - 1; i >= 0; --i) {
		b[i] += carry;
		if(b[i] <= '9') {
			carry = 0;
			break;
		}
		else {
			b[i] = '0';
		}
	}

	if(carry) b = '1' + b;

	cout << (calc(b, m) - calc(a, m) + mod) % mod << endl;

	return EXIT_SUCCESS;
}

Measured memory_bytes: 40360
#include <stdio.h>

int main(void){
    
    int n,i,ii,iii,b,f,r,v,count[4][3][10]= {0};
    
    scanf("%d",&n);
    
    for(i=0;i<n;i++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        if(b==1){
        count[0][f-1][r-1] += v;
        }else if(b==2){
            count[1][f-1][r-1] += v;
        }else if(b==3){

            count[2][f-1][r-1] += v;
        }else if(b==4){

    count[3][f-1][r-1] +=v;
     }
    }for(i=0;i<4;i++){
        for(ii=0;ii<3;ii++){
            for(iii=0;iii<10;iii++){
                printf(" %d",count[i][ii][iii]);
            }printf("\n");
        }if(i==3)
            break;
        printf("####################\n");
        
    }return 0;
    
}
    

Measured memory_bytes: 612
#include <vector>
#include <iostream>
#include <cmath>
#include <numeric>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    long long c=0;
    string s;
    cin>>s;
    for(int i=0;i<s.length()-1;i++){
        if(s[i]!=s[i+1]){
            c++;
        }
    }
    cout<<c;
}

Measured memory_bytes: 512
def main():
    A = int(input())
    B = int(input())
    C = int(input())
    X = int(input())
    l = []
    cnt = 0

    for i in range(C+1):
        for j in range(B+1):
            for k in range(A+1):
                if 50*i + 100*j + 500*k == X:
                    if not [i, j, k] in l:
                        cnt += 1
    print(cnt)
main()

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n,x,t;
  cin>>n>>x>>t;
  int num=(n+x-1)/x;
  cout<<num*t<<endl;
  
  return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <utility>
#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

using namespace std;

int main(){
	int N;
  cin >> N;
	ll A[N+1];
	ll B[N];
	
	rep(i,0,N+1) cin >> A[i];
	rep(i,0,N) cin >> B[i];
	ll ans=0;
	rep(i,0,N){
		if(B[i]>=A[i]){ 
			ans += A[i];
			B[i] -= A[i];
			if(A[i+1]>=B[i]){
				ans += B[i];
				A[i+1] -= B[i];
			}else{
				ans += A[i+1];
				A[i+1] = 0;
			}
		}else{
			ans += B[i];
		}
        //cout << ans << endl;
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
	int N,K,d,A,ans=0;
	bool a[100]={0};
	cin>>N>>K;
	for(int i=0;i<K;i++){
		cin>>d;
		for(int j=0;j<d;j++){
			cin>>A;
			a[A-1]=true;
		}
	}
	for(int i=0;i<N;i++){
		if(!a[i])ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> x(n);
    for(int i=0; i<n; i++) cin>>x[i];
    ll ans = 0;
    for(int i=0; i<n; i++){
        ans+=min(x[i]*2,abs(k-x[i])*2);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        int K=scanner.nextInt();
        int[] A=new int[N];
        int minIndex=0;
        for(int i=0;i<N;i++){
            A[i]=scanner.nextInt();
            if(A[i]==1){
                minIndex=i;
            }
        }
        int result1=0;
        int result2=0;
        int left=minIndex;
        int right=minIndex;
        while(true){
            if(left<=0){
                right=right-left;
                break;
            }
            left=left-K+1;
            //System.out.println("new left"+left);
            result1++;
        }
        while(true){
            if(right>=N-1){
                break;
            }
            right=right+K-1;
            //System.out.println("new right"+right);
            result1++;
        }
        
        left=minIndex;
        right=minIndex;
        while(true){
            if(right>=N-1){
                break;
            }
            right=right+K-1;
            //System.out.println("new right"+right);
            result2++;
        }
        while(true){
            if(left<=0){
                right=right-left;
                break;
            }
            left=left-K+1;
            //System.out.println("new left"+left);
            result2++;
        }
        
        System.out.println(Math.min(result1,result2));
    }
}


Measured memory_bytes: 49992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()


int main() {
    ll N;
    cin >> N;
    ll ans = N - 1;
    for (ll i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            ans = min(ans, i + N / i - 2);
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;

void solve(){
    string s;
    cin >> s;
    string x(s.size(), 'x');
    cout << x << endl;
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(16);
    
    solve();

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace AOJ
{
	class Program
	{
		public static void Main(string[] args)
		{
			var a = Console.ReadLine().Split(' ').Select(x=>int.Parse(x)).ToList();
			Console.WriteLine(a[0]<a[1]&&a[1]<a[2]?"Yes":"No");
		}
	}
}

Measured memory_bytes: 5628
while True:
    h,w = map(int,input().split())
    if w==0 and h==0:
        break
    for j in range(h):
        for i in range(w):
            if (i+j)%2 == 0:
                print("#", end=(""))
            else:
                print(".", end=(""))
        print()
    print()


Measured memory_bytes: 7008
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
 
#define barsik ios::sync_with_stdio(false)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair <int, int> pii;
typedef std::unordered_set <int> u_si;
const double PI = acos(-1);
const long double EPS = 1e-9;
using namespace std;

 
void solve(){
    int n;
    cin >> n;
    int sum = 0;
    int mx = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        mx = max(mx, x);
        sum += x;
    }
    cout << sum - mx / 2;
}

 
int main() {
    barsik;
    int q = 1;
    //cin >> q;
    while(q--) solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
#define ll  long long int

int main()
{
	ll x; cin >> x;
	string str; cin >> str;
	if (str.size() > x) {
		for (ll i = 0; i < str.size(); i++) {
			if (i < x)  cout << str[i];
		}cout << "...";
	}
	else
		cout << str;

	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

ll ll_gcd(ll a, ll b) {
    if (a < b) return ll_gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll d;
    cin >> d;
    vector<ll> z(d);
    for (int i = 0; i < d; i++) {
        cin >> z[i];
    }
    vector<vector<ll>> x(d,vector<ll>(26));
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < 26; j++) {
            cin >> x[j][d];
        }
    }
    vector<ll> ans(d);
    for (int i = 0; i < d/26; i++) {
        vector<bool> flag(26,false);
        for (int j = 0; j < 26; j++) {
            ll mx = 0;
            ll atai = 0;
            for (int k = 0; k < 26; k++) {
                if (flag[k] == false) {
                    mx = max(x[i * 26 + j][k], mx);
                    if (mx == x[i * 26 + j][k])atai = k;
                }
            }
            flag[atai] = true;
            ans[i * 26 + j] = atai+1;
        }
    }
    ll mix = 0;
    ll ataii = 0;
    for (int k = 0; k < 26; k++) {
            mix = max(x[364][k], mix);
            if (mix == x[364][k])ataii = k;
    }
    ans[364] = ataii;
    for (int i = 0; i < d; i++) {
        cout << ans[i] << endl;
    }
}

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

using namespace std;

int main() {
  string S;
  cin >> S;
  int cnt = 0;
  for (int i = 0; i < (int)S.size(); ++i) {
    if (S[i] == 'x') cnt++;
  }
  cout << (cnt <= 7 ? "YES": "NO") << endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        float[] a = new float[n];
        for(int i =0; i< n; i++){
            a[i] = sc.nextFloat();
        }
        Arrays.sort(a);
        double ans = (a[0]+ a[1])/2;
        if(n>2) {
            for (int j = 2; j < n; j++) {
                ans = (ans + a[j]) / 2;

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


Measured memory_bytes: 24660
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
typedef long long ll; 
int a[100005], b[100005], fa[100005], idx[100005]; 
ll dp[100005], sum[100005]; 
std::vector<int> adj[100005], son; 
bool vis[100005]; 
int getfa(int u)
{
	if (u == fa[u])
		return u; 
	return fa[u] = getfa(fa[u]); 
}
int main()
{
	// freopen("ARC098-F.in", "r", stdin); 
	int n, m; 
	scanf("%d%d", &n, &m); 
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", a + i, b + i); 
		a[i] = std::max(a[i] - b[i], 0); 
		fa[i] = idx[i] = i; 
	}
	std::sort(idx, idx + n, [&] (int x, int y) { return a[x] < a[y]; }); 
	for (int i = 0; i < m; i++)
	{
		int u, v; 
		scanf("%d%d", &u, &v); 
		adj[--u].pb(--v); 
		adj[v].pb(u); 
	}
	for (int i = 0; i < n; i++)
	{
		int u = idx[i]; 
		vis[u] = true; 
		son.clear(); 
		sum[u] = b[u]; 
		for (int v : adj[u])
		{
			if (!vis[v] || getfa(v) == getfa(u))
				continue; 
			sum[u] += sum[getfa(v)]; 
			son.pb(getfa(v)); 
			fa[getfa(v)] = getfa(u); 
		}
		dp[u] = sum[u] + a[u]; 
		for (int v : son)
			dp[u] = std::min(dp[u], sum[u] - sum[v] + std::max((ll)a[u], dp[v])); 
	}
	printf("%lld\n", dp[idx[n - 1]]);
	return 0; 
}


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

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

  ll H; cin >> H;
  ll N; cin >> N;
  vector<ll> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }
  
  ll INF = 1e15;
  vector<vector<ll>> dp(N + 1, vector<ll>(H + 1, INF));
  dp[0][0] = 0;
  for (int i = 0; i < N; i++) {
    dp[i + 1][0] = 0;
    for (int j = 0; j <= H; j++) {
      if (j < A[i]) dp[i + 1][j] = min(B[i], dp[i][j]);
      else dp[i + 1][j] = min(dp[i + 1][j - A[i]] + B[i], dp[i][j]);
    }
  }

  cout << dp[N][H] << '\n';
  return 0;
}

Measured memory_bytes: 78592
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let a: i32 = read(&mut stdin_lock, &mut buf, b' ');
    let b: i32 = read(&mut stdin_lock, &mut buf, b'\n');
    let ans: i32 = (1..(b - a)).sum::<i32>() - a;
    println!("{}", ans);
}


Measured memory_bytes: 4352
// Daniel Grzegorzewski
// while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

int a, b;

int main() {
  init_ios();
  cin >> a >> b;
  if (abs(a-b)&1)
    cout<<"IMPOSSIBLE\n";
  else
    cout<<(a+b)/2<<"\n";
}

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

using namespace std;



int main(void) {
  int N;

  vector<int> res(100001);
  res[0] = 0;
  res[1] = 1;
  for(int i = 2; i <= 100000; i++) {
    int min = res[i - 1] + 1;
    for(int six = 6; six <= i; six *= 6) {
      if(res[i - six] + 1 < min) {
        min = res[i - six] + 1;
      }
    }
    for(int nine = 9; nine <= i; nine *= 9) {
      if(res[i - nine] + 1 < min) {
        min = res[i - nine] + 1;
      }
    }

    res[i] = min;
  }
  cin >> N;
  cout << res[N] << endl;
 return 0;
}


Measured memory_bytes: 768
N = int(input())

import math

# Mまでの素数全列挙(エラトステネスの篩)
def primes(M):
    is_prime = [-1 for _ in range(M+1)]
    for m in range(2, M+1):
        if is_prime[m] == -1:
            is_prime[m] = 1
            l = 2
            while m*l <= M:
                is_prime[m*l] = 0
                l += 1
    primes = []
    for p in range(2, M+1):
        if is_prime[p] == 1:
            primes.append(p)
    return primes


P = primes(2*N)
ans = -1
for p in P:
    if p >= N:
        ans = p
        break
print(ans)

Measured memory_bytes: 11244
// 16:32 -
#include <iostream>

using ll = long long;

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

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

int main() {
  ll a, b, c, d;
  std::cin >> a >> b >> c >> d;

  ll minc = (a % c == 0) ? a : a + (c - a % c);
  ll maxc = b - b % c;
  ll mind = (a % d == 0) ? a : a + (d - a % d);
  ll maxd = b - b % d;
  ll cd = c * d / gcd(c, d);
  ll mincd = (a % cd == 0) ? a : a + (cd - a % cd);
  ll maxcd = b - b % cd;

  ll sum = b - a + 1;
  ll sumc = (maxc - minc) / c + 1;
  ll sumd = (maxd - mind) / d + 1;
  ll sumcd = (maxcd - mincd) / cd + 1;

  ll ans = sum - sumc - sumd + sumcd;
  std::cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")  
#include<bits/stdc++.h>
using namespace std;

#define ll 				long long
#define eb 				emplace_back
const long long 		MOD = 1e9 + 7;
#define rep(i,n) 		for (int (i) = 0; (i) < (n); (i)++) 
#define REP(i,k,n)  	for (int (i) = (k); (i) <= (n); (i)++) 
#define REPR(i,k,n) 	for (int (i) = (k); (i) >= (n); (i)--)
#define watch(x) 		cout << (#x) << " = " << (x) << endl
#define t(x)			int x; cin >> x; while(x--)

int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	/*---- continue Coding ;----*/

	int x;
    cin >> x;
    x == 1 ? cout << "0\n" : cout << "1\n";
	
	/*---- break ;----*/

	cerr<<"Execution time: "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
	return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long int n,d,sum=0;
	long double a,b,ans;
	cin>>n>>d;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		ans=sqrt(a*a+b*b);
		if(ans<=d)
		sum++;
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 3844
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using P = pair<int,int>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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 n, m;
  cin >> n >> m;
  vi a(m);
  REP(i, m) cin >> a[i];
  int sum = 0;
  REP(i, m) sum += a[i];
  if (n>=sum) cout << n-sum << endl;
  else cout << -1 << endl;

  return 0;
}

Measured memory_bytes: 3620
#include <iostream>
using namespace std;
int main(void) {
    int num;
    string str;
    cin >> num;
    cin >> str;
    if (num >= str.size()) {
        cout << str << endl;
    }
    else {
        for (int i = 0; i < num; i++) {
            cout << str[i];
        }
        cout << "...";
    }
}

Measured memory_bytes: 3124
#include <stdio.h>

int main(void)
{
    char x[1001];
    int sum, i;

    while(scanf("%s", &x) != EOF)
    {
        if(x[0] == '0')
        {
            return 0;
        }

        sum = 0;

        for(i = 0; x[i] != '\0'; ++i)
        {
            sum += x[i] - '0';
        }

        printf("%d\n", sum);
    }
}

Measured memory_bytes: 536
#include <iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
#include<array>
#include<functional>
#include<iomanip>
#include<ios>
using namespace std;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)

typedef int value_type; /* ソートするキーの型 */

value_type med3(value_type x, value_type y, value_type z)
/* x, y, z の中間値を返す */
{
    if (x < y)
        if (y < z) return y; else if (z < x) return x; else return z; else
        if (z < y) return y; else if (x < z) return x; else return z;
}

void quicksort(value_type a[], int left, int right,value_type index[])
/* クイックソート
 * a     : ソートする配列 
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 * index: index配列
 */
{
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i],a[j] を交換 */
            tmp = index[i]; index[i] = index[j]; index[j] = tmp;
            i++; j--;
        }
        quicksort(a, left, i - 1,index);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right,index); /* 分割した右を再帰的にソート */
    }
}


int dfs(int n,int N){
    if (n>N){
        return 0;
    }
    

    int ret;
    
    return ret;
}
int main(){
    int N;
    cin >>N;

    int M;
    cin >>M;

    double ans= 100*N +1800*M;
    ans=ans*pow(2,M);
    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 256