akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

const int MOD = int(1e9) + 7;
using lint = long long;

struct modint {
  int v;
  modint(long long v_ = 0): v(v_ % MOD) { }
  modint operator+ (modint other) {
    return modint(v + other.v);
  }
  modint operator- (modint other) {
    return modint(v - other.v + MOD);
  }
  modint operator* (modint other) {
    return modint((lint)v * other.v % MOD);
  }
  modint operator+= (modint other) {
    (v += other.v) %= MOD;
    return *this;
  }
  modint operator*= (modint other) {
    v = ((lint)v * other.v) % MOD;
    return *this;
  }
  modint operator-= (modint other) {
    (v += MOD - other.v) %= MOD;
    return *this;
  }
};

const int N_ = 45, X_ = 6, Y_ = 8, Z_ = 6;
int N, X, Y, Z;

modint ways[2][N_][1<<18];
modint ans;

int main() {
  scanf("%d%d%d%d", &N, &X, &Y, &Z);

  int haiku_mask = (1 << Z) | (1 << (Y + Z)) | (1 << (X + Y + Z));
  auto completed = [&](int mask) {
    return (haiku_mask & mask) == haiku_mask;
  };


  ways[0][0][1] = 1;
  for(int n = 0; n < N; n++) {
    for(int mask = 0; mask < (1<<18); mask++) {
      for(int last = 1; last <= 10; last++) {
        int nxt_mask = ((mask << last) | 1) & ((1 << 18) - 1);
        ways[1][n+1][nxt_mask] += ways[1][n][mask];
        ways[completed(nxt_mask) ? 1 : 0][n+1][nxt_mask] += ways[0][n][mask];
      }
    }
  }

  for(int mask = 0; mask < (1<<18); mask++) {
    ans += ways[1][N][mask];
  }

  printf("%d\n", ans.v);
  return 0;
}

Measured memory_bytes: 92416
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s;
	cin >> n >> s;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans++;
		for (; s[i] == s[i + 1]; i++);
	}
	cout << ans;
	return 0;
}

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

int main(){
	int H, W, i;
	scanf("%d%d", &H, &W);
	vector<string> C(H);
	for(i = 0; i < H; i++){
		cin >> C[i];
	}
	for(i = 0; i < H; i++){
		cout << C[i] << endl;
		cout << C[i] << endl;
	}
	return 0;
}

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

c = -1
falg = True
while falg:
    a_t = []
    c = c + 1
    for i in a:
        if i % 2 == 1:
            falg = False
            break
        a_t.append(i / 2)
    a = a_t

print(c)


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

int main(){
  int N;
  int Q;
  string S;
  cin >> N >> Q >> S;
  
  vector<int> X(N);
  X.at(0)=0;
  for(int i=1; i<N; i++){
    int count =0;
    if(S.at(i-1)=='A' && S.at(i)=='C'){
      count = 1;
    }
    
    X.at(i)=X.at(i-1)+count;
  }
  //X.at(N-1) = X.at(N-2);
  
  /*
  for(int i=0; i<N; i++){
    cout << X.at(i);
  }
  */
  
  int l;
  int r;
  for(int i=0; i<Q ; i++){
    cin >> l >> r;
    cout << X.at(r-1)-X.at(l-1) << endl;
  }
  
}

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

#ifndef ONLINE_JUDGE
	#define W(x, y) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << y;
#else
	#define W(x, y)
#endif

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define vl vector<ll>
#define vll vector<pll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pi acosl(-1)
#define ld long double
#define prime (1000000000 + 7)
#define INF 1000000000

using namespace std;

vl kmp(string &&s, string &r){
	vl vet(s.size() + 1, -1);
	ll t = -1;
	for(int i = 0; i < s.size(); ++i){
		while (t > -1 && s[i] != s[t]){
			t = vet[t];
		}
		vet[i+1] = ++t;
	}
	vl res;
	res.insert(res.begin(), vet.begin() + r.size() + 1, vet.end());
	res[0] = -1;
	return res;
}

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

	vector<vl> mat(3, vl(3));
	string res = "Yes";
	for(auto&p:mat){
		for(auto&q:p){
			cin >> q;
		}
	}
	for(int i = 0; i < 3; ++i){
		int k = (i+1)%3;
		for(int j = 1; j < 3; ++j){
			if(mat[i][j] - mat[k][j] != mat[i][0] - mat[k][0]){
				res = "No";
			}
		}
		for(int j = 1; j < 3; ++j){
			if(mat[j][i] - mat[j][k] != mat[0][i] - mat[0][k]){
				res = "No";
			}
		}
	}
	cout << res << "\n";

	return 0;
}


// c11 = a1 + b1
// c12 = a1 + b2
// c13 = a1 + b3
// c21 = a2 + b1
// c22 = a2 + b2
// c23 = a2 + b3
// c31 = a3 + b1
// c32 = a3 + b2
// c33 = a3 + b3








Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n;
ll a[N], p[62];

void insert(ll x) {
    for(int i = 60; i >= 0; i--) {
        if(x >> i & 1) {
            if(!p[i]) {
                p[i] = x;
                break;
            }
            x ^= p[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    ll all = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], all ^= a[i];
    for(int i = 0; i <= 60; i++) {
        if(all >> i & 1) {
            for(int j = 1; j <= n; j++) {
                if(a[j] >> i & 1) a[j] -= (1ll << i);
            }
        }
    }
    for(int i = 1; i <= n; i++) insert(a[i]);
    ll ans = 0;
    for(int i = 60; i >= 0; i--) {
        if((p[i] ^ ans) > ans) ans = p[i] ^ ans;
    }
    cout << ans + (ans ^ all);
    return 0;
}


Measured memory_bytes: 1024
def get_set(_max, a, b):
    ans = set()
    g = _max // a
    for h in range(g + 1):
        k = (_max - a * h) // b
        for l in range(k + 1):
            ans.add(a * h + b * l)
    ans.discard(0)
    return ans


a, b, c, d, e, f = map(int, input().split())
ab = get_set(f, a * 100, b * 100)
max_l, max_s, max_r = 0, 0, 0
for n in ab:
    o = min(f - n, n * e // 100)
    if o / (n + o) < max_r:
        continue
    tmp_max = max(get_set(o, c, d), default=0)
    tmp_rate = tmp_max / (n + tmp_max)
    if tmp_rate >= max_r:
        max_l = n + tmp_max
        max_s = tmp_max
        max_r = tmp_rate

print(max_l, max_s)


Measured memory_bytes: 3064
def solve():
    mod = 10**9+7
    L = input()
    N = len(L)
    dp = [0]*2
    dp[0] = 1
    dp[1] = 2
    for i in range(1, N):
        if L[i]=='0':
            dp[0], dp[1]=dp[0]*3, dp[1]
        else:
            dp[0], dp[1]=dp[0]*3+dp[1], dp[1]*2
    print((dp[0]+dp[1])%mod)
solve()

Measured memory_bytes: 45660
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i;
  int n;
  while(cin>>n&&n){
    int a[6];
    for(i=0;i<6;i++)
      a[i]=i+1;
    for(i=0;i<n;i++){
      string s;
      cin>>s;
      if(0){
      }else if(s=="north"){
	int s=a[0];
	a[0]=a[4];
	a[4]=a[5];
	a[5]=a[1];
	a[1]=s;
      }else if(s=="south"){
	int s=a[0];
	a[0]=a[1];
	a[1]=a[5];
	a[5]=a[4];
	a[4]=s;
      }else if(s=="east"){
	int s=a[0];
	a[0]=a[2];
	a[2]=a[5];
	a[5]=a[3];
	a[3]=s;
      }else if(s=="west"){
	int s=a[0];
	a[0]=a[3];
	a[3]=a[5];
	a[5]=a[2];
	a[2]=s;
      }
    }
    cout<<a[0]<<endl;
  }
  return 0;
}

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

#define int long long
#define endl '\n'

const int MOD = 1e9 + 7;

int add(int a, int b, int m = MOD) {
    a %= m, b %= m;
    return (a + b) % m;
}

int sub(int a, int b, int m = MOD) {
    return add(a, m - b, m);
}

int mult(int a, int b, int m = MOD) {
    a %= m, b %= m;
    return 1ll * a * b % m;
}

int fpow(int x, int y, int m = MOD) { 
    int res = 1;
    if (y < 0)   y += m - 1;   //only if m is prime
    while (y > 0) {
        if (y & 1)   res = mult(res, x, m);
        x = mult(x, x, m);
        y >>= 1;
    }
    return res;
}

int inv(int a, int md = MOD) {
    a %= md;
    if (a < 0)   a += md;
    int b = md, u = 0, v = 1;
    while (a) {
        int t = b / a;
        b -= t * a; swap(a, b);
        u -= t * v; swap(u, v);
    }
    if (u < 0)   u += md;
    return u;
}

vector<int> fac, ifac;

void precomp(int N = 1e5 + 5) {
    fac.assign(N, 1);
    ifac.assign(N, 1);
    for (int i = 1; i < N; i++)    fac[i] = mult(fac[i - 1], i);
    ifac[N - 1] = inv(fac[N - 1]);
    for (int i = N - 2; i > 0; i--)    ifac[i] = mult(ifac[i + 1], i + 1);
}

int ncr(int n, int r) {
    if (r > n)   return 0;
    return mult(fac[n], mult(ifac[r], ifac[n - r]));
}

vector<int> pr, lp;

void sieve(int N = 1e6 + 5) {
    lp.assign(N, 0);
    for (int i = 2; i < N; i++) {
        if (!lp[i]) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (auto &j: pr) {
            if (j > lp[i] || i * j >= N) break;
            lp[i * j] = j;
        }
    }
}

vector<int> a(1e6 + 5);

void factorize(int n) {
    unordered_map<int, int> m;
    while (n > 1) {
        m[lp[n]]++;
        n /= lp[n];
    }
    for (auto i: m)
        a[i.first] = max(a[i.first], i.second);
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    sieve();
    int n; cin >> n;
    vector<int> aux(n);
    for (auto &x: aux)
        cin >> x, factorize(x);
    int lcm = 1;
    for (int i = 2; i <= 1e6; i++)
        lcm = mult(lcm, fpow(i, a[i]));
    int ans = 0;
    for (auto i: aux)
        ans = add(ans, mult(lcm, inv(i)));
    cout << ans;
}

Measured memory_bytes: 17016
n, y = gets.split.map(&:to_i)
0.upto(n) do |man|
  0.upto(n-man) do |gosen|
    sen = n-man-gosen
    if man*10000 + gosen*5000 + sen*1000 == y
      puts [man, gosen, sen].join(' ')
      exit
    end
  end
end
puts "-1 -1 -1"


Measured memory_bytes: 1788
#include<stdio.h>
int main()
{
    int a,b,c,d,excalibur,max0,min0;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    scanf("%d",&d);
    if(a>c)
        max0=a;
    else max0=c;
    if(b>d)
        min0=d;
    else min0=b;
    excalibur=min0-max0;
    if(excalibur<0)
        printf("0");
    else printf("%d",excalibur);
    return 0;
}

Measured memory_bytes: 128
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto s = readln.chomp.to!(char[]);
  auto t = readln.chomp.to!(char[]);
  bool[char] done;
  auto f = true;

  foreach (i; 0..s.length) {
    if (s[i] != t[i]) {
      if (done.get(s[i], true) && done.get(t[i], true)) {
        foreach (j; i+1..s.length) {
          if (s[j] == t[i]) {
            s[j] = s[i];
          } else if (s[j] == s[i]) {
            s[j] = t[i];
          }
        }
        s[i] = t[i];
      } else {
        f = false;
        break;
      }
    }
    done[s[i]] = false;
  }

  if (f) {
    writeln("Yes");
  } else {
    writeln("No");
  }
}


Measured memory_bytes: 3256
#include <iostream>

using namespace std;

int main(){
  int n;cin>>n;
  for(int i=0;i<n;i++){
    int x,y,b,p;cin>>x>>y>>b>>p;
    int sum = x*b + y*p;
    if(b>=5 && p>=2){
      sum = sum * 0.8;
    }else{
      if(b<5){b=5;}
      if(p<2){p=2;}
      int discount = (x*b + y*p)*0.8;
      if(discount<sum){
        sum = discount;
      }
    }
    cout<<sum<<endl;
  }
}


Measured memory_bytes: 3112
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  a[i] = a[i]*-1
heapq.heapify(a)
for _ in range(m):
  t = heapq.heappop(a)
  t = int(t/2)
  heapq.heappush(a, t)
print(sum(a)*-1)


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

#define el '\n'

typedef long long ll;

ll a,b,c,d;

void input()
{
    cin>>a>>b>>c>>d;
    cout<<min(a,b)+min(c,d);
}

int main ()
{
    ios_base::sync_with_stdio(0);
    //freopen("2.inp","r",stdin);
    //freopen("2.out","w",stdout);
    input();
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
void dbg_out(){
	cerr<<endl;
}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){
	cerr<<' '<< H; 
	dbg_out(T...);
}
int const MAXN=22, MOD=1e9+7;
int n, v[MAXN][MAXN], memo[MAXN][1<<MAXN];
int dp(int row, bitset<MAXN> &usati){
	if(row==n)
		return 1;
	int col=usati.to_ulong();
	if(memo[row][col]!=-1)
		return memo[row][col];
	int ans=0;
	for(int i=0;i<n;i++){
		if(v[row][i]==1 && usati[i]==0){
			usati[i]=1;
			ans=(ans+dp(row+1,usati))%MOD;
			usati[i]=0;
		}
	}
	return memo[row][col]=ans;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>v[i][j];
	bitset<MAXN> vuoto;
	memset(memo,-1,sizeof(memo));
	cout<<dp(0,vuoto);
}


Measured memory_bytes: 360704
#include <bits/stdc++.h>
#define MOD 998244353LL
using namespace std;
typedef long long ll;

#define MAX_N 300005
ll factorial[MAX_N];

void make_factorial_tableMOD(){
    factorial[0] = 1;
    for(int i = 1; i < MAX_N; i++){
        factorial[i] = factorial[i-1]*i%MOD;
    }
}

ll bisection_powerMOD(ll x,ll y){
    if(y==0)        { return 1; }
    ll t = bisection_powerMOD(x*x%MOD,y/2);
    if(y%2==1)      { t = t*x%MOD; }
    return t;
}

ll nCrMOD(int n, int r){
    ll a = factorial[n];
    ll b = a*bisection_powerMOD(factorial[r],(MOD-2))%MOD;
    ll c = b*bisection_powerMOD(factorial[n-r],MOD-2)%MOD;
    return c % MOD;
}

int main(){
    ll n, a, b, k;
    cin >> n >> a >> b >> k;
    ll ans = 0;
    make_factorial_tableMOD();

    for(int i = 0; i < n+1; i++){
        ll anum = (ll)i;
        ll r = k - anum*a;
        ll bnum = r/b;
        if(bnum < 0){continue;}
        if(r % b == 0LL && bnum <= n){
            ans += (nCrMOD(n,anum)*nCrMOD(n,bnum))%MOD;
        }
    }

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


Measured memory_bytes: 2560
N = int(input())
S = input()
num = S[1:].count('E')
anss = []
anss.append(num)
for i in range(1,len(S)):
  if S[i] == 'E' and S[i - 1] == 'E':
    num -= 1
    anss.append(num)
  elif S[i] == 'W' and S[i - 1] == 'W':
    num += 1
    anss.append(num)
print(min(anss))

Measured memory_bytes: 15564
/* Author rumoisen */
/* created 2018/10/24 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <numeric>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7
#define pb push_back

void no() { cout << "No" << endl;exit(0);}
void yes() { cout << "Yes" << endl;exit(0);}
void No() { cout << "NO" << endl;exit(0);}
void Yes() { cout << "YES" << endl;exit(0);}

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    vector<int> d(112);
    for (int i = 0; i < n; i++ ){
        cin >> d.at(i);
    }
    bool used[112] = {false};
    int sum = 0;
    for (int i = 0; i < n; i++ ){
        if(used[d[i]]==false){
            sum++;
            used[d[i]] = true;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int i,j,k,l,m,n,x=0,y=0;
    cin>>n;
    int a[n];
    int dp[n];
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++){
 dp[i]=min((dp[i-1]+abs(a[i]-a[i-1])),(dp[i-2]+abs(a[i-2]-a[i])));
    }
    
    cout<<dp[n-1]<<"\n";
}

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

int main(){
    using namespace std;
    unsigned long Q;
    cin >> Q;
    constexpr auto M{205891132094649UL};
    const auto& calc = [](auto a, auto b, auto c, auto d){
        auto u{b}, l{b}, p{M};
        while(p /= 3)if((a / p + (4 - a / p % 3) % 3) * p <= c){
            if(u / p % 3 == 1){
                u = u / (3 * p) * 3 * p + 2 * p;
                l = l / (3 * p) * 3 * p + p - 1;
                break;
            }
        }
        return c - a + min(u - b + max(u, d) - min(u, d), b + d - 2 * l);
    };
    for(unsigned long _{0}, a, b, c, d; _ < Q; ++_){
        cin >> a >> b >> c >> d;
        if(--a > --c)swap(a, c), swap(b, d);
        if(--b > --d){
            b = M - b - 1;
            d = M - d - 1;
        }
        cout << max(calc(a, b, c, d), calc(b, a, d, c)) << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> H(n);
  vector<int> flag(n,0);
  for(int i=0; i<n; i++)cin>>H.at(i);
  for(int i=0; i<m; i++){
    int a,b;
    cin>>a>>b;
    a-=1;
    b-=1;
    if(H.at(a)>H.at(b)){
      flag.at(b)=1;
    }else if(H.at(a)<H.at(b)){
      flag.at(a)=1;
    }else{
      flag.at(a)=1;
      flag.at(b)=1;
    }
  }
  int ans=0;
  for(int i=0; i<n; i++){
    if(flag.at(i)==0)ans++;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4048
# リストの中から最小値のインデックスを返す方法が肝

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

x = []
for i in range(n):
    x.append(abs(a- (t - l[i] * 0.006)))
print(x.index(min(x))+1) # リストの最小値のインデックス ＋ 1


Measured memory_bytes: 3060
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e9
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	int m;
	cin >> m;
	REP(tea, m) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());
		string b;
		set<string> ans;
		while (s.length() != 1) {
			b.push_back(s[s.length() - 1]);
			s.pop_back();
			REP(i, 2) {
				REP(q, 2) {
					ans.insert(b + s);
					reverse(s.begin(), s.end());
				}
				reverse(b.begin(), b.end());
			}
			REP(i, 2) {
				REP(q, 2) {
					ans.insert(s + b);
					reverse(s.begin(), s.end());
				}
				reverse(b.begin(), b.end());
			}
		}
		cout << ans.size() << endl;
	}
}


Measured memory_bytes: 3088
// * template

#include <bits/stdc++.h>
#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

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

template<class T, class U> inline void fill_array(T &e, const U &v) { e = v; }
template<class T, class U, size_t s> inline void fill_array(T (&a)[s], const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U, size_t s> inline void fill_array(array<T, s> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U> inline void fill_array(vector<T> &a, const U &v) {for(auto&e:a)fill_array(e,v);}

struct range {
	typedef int Int;
	struct iter {
		Int i;
		const Int s;
		iter(const Int &i_, const Int &s_):i(i_), s(s_) {}
		bool operator!=(const iter &r) const { return s > 0 ? i < r.i : i > r.i; }
		const Int &operator*() const { return i; }
		iter &operator++() { i += s; return *this; }
	};
	const Int f, l, s;
	range(const Int &f_, const Int &l_, const Int &s_):f(f_), l(l_), s(s_) {}
	range(const Int &f_, const Int &l_):f(f_), l(l_), s(1) {}
	range(const Int &num):f(0), l(num), s(1) {}
	iter begin() const { return iter(f, s); }
	iter end() const { return iter(l, s); }
};

// * solve

class BIT {
private:
	int size;
	vector<int> bit;

public:
	BIT(int n = 0):size(n), bit(n + 1, 0) {}

	void add(int i, int x) {
		++i;
		while(i <= size) {
			bit[i] += x;
			i += i & -i;
		}
	}

	int sum(int i) const {
		++i;
		int s = 0;
		while(i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
};

struct line {
	typedef long long Int;
	Int a, b;
	line(Int a_, Int b_):a(a_), b(b_) {}
	Int operator()(Int x) const {
		return a * x + b;
	}
};

inline bool check(const line &f1, const line &f2, const line &f3) {
	return (f2.a - f1.a) * (f3.b - f2.b) >= (f2.b - f1.b) * (f3.a - f2.a);
}

constexpr int MAX_X = 1e6;

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

	int n, m, day, speed;
	cin >> n >> m >> day >> speed;

	vector<int> pos(n);
	for(auto &e : pos) cin >> e;

	BIT bit(MAX_X + 2);
	bit.add(0, m);

	vector<int> enemy(m);
	for(auto &e : enemy) {
		int a, b;
		cin >> a >> b;
		e = a - abs(b);
		bit.add(max(e + 1, 0), -1);
	}


	vector<long long> dp(n, 1e12);
	dp[0] = 0;

	const auto make_f = [&](int i) { const long long w = bit.sum(pos[i]); return line(w, dp[i] - w * pos[i]); };

	for(const int d : range(day)) {
		vector<long long> next_dp(dp);
		deque<line> deq{make_f(0)};
		for(const int i : range(1, n)) {
			const int &p = pos[i];

			while(deq.size() > 1 && deq[0](p) >= deq[1](p)) deq.pop_front();

			chmin(next_dp[i], deq.front()(p));

			const auto f = make_f(i);
			while(deq.size() > 1 && check(deq[deq.size() - 2], deq.back(), f)) deq.pop_back();
			deq.emplace_back(move(f));
		}

		dp = move(next_dp);
		dump(dp);
		for(auto &e : enemy) {
			bit.add(max(e + 1, 0), 1);
			e = min(e + speed, MAX_X + 1);
			bit.add(max(e + 1, 0), -1);
		}
	}

	cout << dp.back() << endl;

	return EXIT_SUCCESS;
}

Measured memory_bytes: 5332
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn solve(M: usize, K: i64, v: &mut Vec<i64>) {
    v.clear();
    if K == 0 {
        for i in 0..(1_i64 << M) {
            v.push(i);
            v.push(i);
        }
    } else {
        v.extend(&[0, K, 0]);
        for i in 1..(1_i64 << M) {
            if i == K {
                continue;
            }
            v.push(i);
        }
        v.push(K);
        for i in (1..(1_i64 << M)).rev() {
            if i == K {
                continue;
            }
            v.push(i);
        }
    }
}

fn main() {
    let (M, K) = read!(usize, i64);
    if (M == 1 && K == 1) || K >= (1_i64 << M) {
        println!("-1");
        return;
    }

    let mut v = vec![];
    solve(M, K, &mut v);

    let stdout = std::io::stdout();
    let mut stdout = std::io::BufWriter::new(stdout.lock());
    write!(stdout, "{}", v[0]).unwrap();
    for i in 1..v.len() {
        write!(stdout, " {}", v[i]).unwrap();
    }
    write!(stdout, "\n").unwrap();
    stdout.flush().unwrap();
}


Measured memory_bytes: 9208
import java.util.Scanner;

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

		int n = sc.nextInt();
		int k = sc.nextInt();

		String[] d = new String[k];
		for(int i=0;i<k;i++) {
			d[i] = sc.next();
		}

		int i=n;
		while(true) {
			String s = Integer.toString(i);
			int flg = 0;
			for(int j=0;j<s.length();j++) {
				String str = s.substring(j, j+1);
				for(int l=0;l<d.length;l++) {
					if(str.equals(d[l])) {
						flg = 1;
					}
				}
			}
			if(flg==0) {
				break;
			}
			i++;
		}

		System.out.println(i);

	}
}


Measured memory_bytes: 53508
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

const int N = 20;
const int K = 17712;
const ll mod = 100000;

int mask;

char m[N][N];
map<int,int> M;
int memo[20][20][K];


inline int getIndex(int state)
{
	int index = M.size();
	if (M.find(state) == M.end()) M[state] = index;
	return M[state];
}

int rec(int &h, int &w, int now, int state)
{
	if(w * h == now) return 1;
	int index = getIndex(state);
	
	int y = now / w, x = now % w;
	if(memo[y][x][index] != -1) return memo[y][x][index];
	
	ll res = 0;
	
	// J
    if (m[y][x] == '?' || m[y][x] == 'J')
	{
		int next =  (state << 1) & (~2) | 1;
		
		res = (res + rec(h, w, now + 1, next & mask)) % mod;
    }
	
	// O
    if (m[y][x] == '?' || m[y][x] == 'O')
	{
		int next = state;
		next = (next << 1);
		
		res = (res + rec(h, w, now + 1, next & mask)) % mod;
    }
	
	// I
    if (m[y][x] == '?' || m[y][x] == 'I')
	{
		if (((1 << (w - 1)) & state) == 0 || x == w - 1)
		{
			int next = (state << 1) & (~2);
			
			res = (res + rec(h, w, now + 1, next & mask)) % mod;
		}
    }
	
	return memo[y][x][index] = res;
}

int main()
{
    int h, w;
	while(cin >> h >> w && h)
	{
		ll all = 1;
		
		rep(i, h) cin >> m[i];
		rep(y, h) rep(x, w)if (m[y][x] == '?') all = (all * 3) % mod;
		rep(k, K) rep(y, h) rep(x, w) memo[y][x][k] = -1;
		
		mask = (1 << w) - 1;
		
		ll cans = rec(h, w, 0, 0);
		ll ans = (all - cans + mod) % mod;
		
		cout << ans << endl;
	}
}

Measured memory_bytes: 28000
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

min_count = N
for i in range(N+1):
    count = 0
    t = i
    while t > 0:
        count += t % 6
        t //= 6

    t = N - i
    while t > 0:
        count += t % 9
        t //= 9

    if count < min_count:
        min_count = count
print(min_count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define len(x) (ll) (x.size())
using namespace std;
typedef long long ll;

// vector<ll> prims;
// void primes(ll n) {
//     while (n % 2 == 0) {
//         prims.push_back(2);
//         n = n/2;
//     }
//     for(ll i = 3; i <= sqrt(n); i+= 2) {
//         while (n % i == 0) {
//             prims.push_back(i);
//             n = n/i;
//         }
//     }
//     if (n > 2)
//         prims.push_back(n);
// }

vector<ll> divv;
void find_div(ll n) {
    for(ll i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            divv.push_back(i);
            if (n/i != i) {
                divv.push_back(n/i);
            }
        }
    }
} 


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

    // primes(n);
    find_div(n);
    ll ans = n-1;
    for(ll i = 0; i < len(divv); i++) {
        ans = min(ans, abs(divv[i]+n/divv[i]-2));
    }
    cout << ans << '\n';
    
    return 0;
}

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

int main() {
  int a, b, c;
  int A;
  cin >> A;
  a = A / 100;
  b = A / 10 - 10 * a;
  c = A - 100 * a - 10 * b;
  
  cout << a + b + c << endl;
}

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

int main()
{
  string s,t;cin>>s>>t;
  int ls=s.size();
  int lt=t.size();
    for (int i=0;i<ls;i++)
    {
      if (s[i]!=t[i])
      {
         cout<<"No"<<endl;
        return 0;
      }
    }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <stack>

using namespace std;

int  main(void) {
	string s;
	cin >> s;
	int i;
	stack<int> st;
	for (i = 0; i < s.size(); i++) {
		if (s[i] == 'S')
			st.push(0);
		else if (!st.empty() && st.top() == 0)
			st.pop();
		else
			st.push(1);
	}
	cout << st.size() << "\n";

	return 0;
}

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define CEIL(n, m) ceil(n/pow(10.0, m))*pow(10.0, m)
#define FLOOR(n, m) floor(n/pow(10.0, m))*pow(10.0, m)
#define ROUND(n, m) round(n/pow(10.0, m))*pow(10.0, m)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

typedef long long ll;
const int mod = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

void solve()
{

  string s; cin >> s;
  vector<int> a(4, 0);
  for (int i=0; i<4; i++) {
    a[i] = (int)(s[i] - '0');
  }

  int ans=0;
  for (int i=0; i<8; i++) {
    int sum=a[0];
    for (int j=0; j<3; j++) {
      if ((i>>j)&1) {
        sum-=a[j+1];
      } else {
        sum+=a[j+1];
      }
    }
    if (sum==7) {
      ans=i;
      break;
    }
  }

  cout << a[0];
  for (int i=0; i<3; i++) {
    if ((ans>>i)&1) {
      cout << "-";
    } else {
      cout << "+";
    }
    cout << a[i+1];
  }

  cout << "=7" << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
N, K = gets.split.map(&:to_i)
n = N.to_s
D = gets.split
# OK = Array.new(0)
# 10.times do |i|
#   ii = i.to_s
#   OK << i.to_s unless D.find {|v| v == ii}
# end
# #p OK
# s = N.to_s
# size = s.length

# D.each do |d|
#   pos = s.index(d)
#   s[pos] = 
# end

while true do
  pos = nil
  D.each do |d|
    pos = n.index(d)
    break if pos != nil
  end
  break if pos == nil
  n = (n.to_i+1).to_s
end

puts n


Measured memory_bytes: 1788
#include <stdio.h>

int main(){
  int n=0,i,j,k,a[500005]={},f,b[500005],d;
  char s[500005];
  long m=0;
  scanf("%s",&s);
  for(i=0;s[i]!=0;i++) n++;
  for(i=0;i<n;i++){
    f=(s[i]=='<');
    a[i+f]|=1<<f;
  }
  n++;
  for(i=0;i<n;i++){
    b[i]=-(a[i]!=0);
  }
  for(i=0;i<n;i++){
    if(b[i]==0){
      for(j=0;j<2;j++){
        k=i;
        d=0;
        while(1){
          k+=(j<<1)-1;
          if((a[k]>>j&1)^1) break;
          if((k<0)||(k>=n)) break;
          d++;
          if(b[k]<d){
            b[k]=d;
          }
        }
      }
    }
  }
  for(i=0;i<n;i++){
    m+=b[i];
  }
  printf("%ld",m);
  return(0);
}

Measured memory_bytes: 4608
#include<stdio.h>
int main(void)
{
	int n,w[100],a,b,t,min=10001,i,j;
	scanf("%d", &n);
	for(i=0; i<n; i++)
	scanf("%d", &w[i]);
	for(i=0; i<n-1; i++)
	{
		a=0;
		b=0;
		for(j=0; j<=i; j++)
		a+=w[j];
		for(j=i+1; j<n; j++)
		b+=w[j];
		if(a<b)
		{
			t=a;
			a=b;
			b=t;
		}
		if(min>a-b)
		min=a-b;
	}
	printf("%d\n", min);
	
	return 0;
}

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

// 小数点以下桁数
// fixed << setprecision(i)

int64_t gcd(int64_t a,int64_t b){return (a%b==0?b:gcd(b, a%b));}
int64_t lcm(int64_t a,int64_t b){return a/gcd(a, b)*b;}
int factorial(int a){int b=1;while(a){b*=a--;}return b;} //13以下対応
bool is_prime(int a){if(a<=1)return false;for(int i=2;(int64_t)i*i<=a;i++){if(a%i==0)return false;}return true;}
int get_adp(double x, int n){return (int)round((x-(int)x)*pow(10,n))%10;} // 小数点以下の指定桁の値を取得
int64_t sigma(int64_t s, int64_t n){return n*(2*s+n-1)/2;}

//順列の全列挙
// vector<int> v(N);
// iota(v.begin(), v.end(), 1);       // v に 1, 2, ... N を設定
// do {
//	for(auto x : v) cout << x << " "; cout << "\n";     // v の要素を表示
// } while( next_permutation(v.begin(), v.end()) ); 

//bit全探索
// for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
//	bitset<ビット数> s(tmp);
//	// (ビット列sに対する処理)
// }

int main()
{
	int n;
	vector<int> alp(26);
	string s;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		vector<int> alp_temp(26, 0);
		for (int j = 0; j < s.size(); j++)
			alp_temp[(int)(s[j] - 'a')]++;
		if (i == 0)
			for (int j = 0; j < 26; j++)
				alp[j] = alp_temp[j];
		else
			for (int j = 0; j < 26; j++)
				alp[j] = min(alp[j], alp_temp[j]);
	}
	for (int i = 0; i < 26; i++)
		for (int j = 0; j < alp[i]; j++)
			cout << (char)('a' + i);
	cout << endl;
}


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

int main(){
  ll n, d, cnt=0;
  cin >> n >> d;
  rep(i, n){
    ll x, y;
    cin >> x >> y;
    if(sqrt(x*x+y*y)<=d)cnt++;
  }

  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 3676
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
db dp[3005][3005];
int main()
{ quick;

    int n;
    cin>>n;
    db a[n];
    fab(0,n,i)
    cin>>a[i];
    dp[0][0]=1-a[0];
    fab(1,n,i)
    {
        dp[i][0]=dp[i-1][0]*(1-a[i]);
    }
    dp[0][1]=a[0];
    fab(1,n,i)
    {
        fab(1,n+1,j)
        {
        dp[i][j]=dp[i-1][j]*(db(1)-a[i])+dp[i-1][j-1]*(a[i]);
        }
    }
    
    db ans=0;
    fab((n+1)/2,n+1,i)
    ans+=dp[n-1][i];

    cout<<setprecision(10)<<ans<<endl;



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

Measured memory_bytes: 74204
cat<<EOF>Source.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

int x[100000],y[100000],x_mod_k[100000],x_div_k[100000];
char s[100000][2];
int n,k;

void add(vector<int>&cnt,int x,int t){
	if((x_div_k[x]&1)==0){
		if(t==0){
			cnt[0]++;
			cnt[k-x_mod_k[x]]--;
		}
		else{
			cnt[k-x_mod_k[x]]++;
		}
	}
	else{
		if(t==0){
			cnt[k-x_mod_k[x]]++;
		}
		else{
			cnt[0]++;
			cnt[k-x_mod_k[x]]--;
		}
	}
}
int ans[2000];
int main(){
	scanf("%d%d",&n,&k);
	rep(i,n){
		scanf("%d%d%s",&x[i],&y[i],s[i]);
		x_mod_k[i]=y[i]%k;
		x_div_k[i]=y[i]/k;
	}
	int Max=0;
	#pragma omp parallel for schedule(dynamic, 1) num_threads(10)
	rep(i,k){
		vector<int>cnt(max(n,k));
		rep(j,n){
			if(s[j][0]=='B'){
				if(((x[j]+i)/k)%2==0){
					add(cnt,j,0);
				}
				else{
					add(cnt,j,1);
				}
			}
			else{
				if(((x[j]+i)/k)%2==0){
					add(cnt,j,1);
				}
				else{
					add(cnt,j,0);
				}
			}
		}
		rep(j,k){
			if(j)cnt[j]+=cnt[j-1];
			ans[i]=max({ans[i],cnt[j],n-cnt[j]});
		}
	}
	rep(i,k)Max=max(Max,ans[i]);
	cout<<Max<<endl;
}
EOF
g++ -O3 Source.cpp -o Source -fopenmp -std=c++11
./Source

Measured memory_bytes: 64656
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int h, w, n, x, y;
    std::string s, t;
    std::cin >> h >> w >> n
        >> x >> y
        >> s >> t;

    // [lb, ub]
    std::vector<std::pair<int, int>> lr(2 * n + 1), ud(2 * n + 1);
    ud[2 * n] = std::make_pair(1, h);
    lr[2 * n] = std::make_pair(1, w);

    auto check = [&](int i) {
        if (lr[i].first > lr[i].second || ud[i].first > ud[i].second) {
            std::cout << "NO" << std::endl;
            exit(0);
        }
    };

    for (int i = n; i; i--) {
        if (t[i - 1] == 'D') {
            ud[2 * i - 1].first = std::max(1, ud[2 * i].first - 1);
            ud[2 * i - 1].second = ud[2 * i].second;
            lr[2 * i - 1] = lr[2 * i];
        } else if (t[i - 1] == 'U') {
            ud[2 * i - 1].first = ud[2 * i].first;
            ud[2 * i - 1].second = std::min(h, ud[2 * i].second + 1);
            lr[2 * i - 1] = lr[2 * i];
        } else if (t[i - 1] == 'R') {
            lr[2 * i - 1].first = std::max(1, lr[2 * i].first - 1);
            lr[2 * i - 1].second = lr[2 * i].second;
            ud[2 * i - 1] = ud[2 * i];
        } else if (t[i - 1] == 'L') {
            lr[2 * i - 1].first = lr[2 * i].first;
            lr[2 * i - 1].second = std::min(w, lr[2 * i].second + 1);
            ud[2 * i - 1] = ud[2 * i];
        }

        if (s[i - 1] == 'D') {
            ud[2 * i - 2].first = ud[2 * i - 1].first;
            ud[2 * i - 2].second = ud[2 * i - 1].second - 1;
            lr[2 * i - 2] = lr[2 * i - 1];
        } else if (s[i - 1] == 'U') {
            ud[2 * i - 2].first = ud[2 * i - 1].first + 1;
            ud[2 * i - 2].second = ud[2 * i - 1].second;
            lr[2 * i - 2] = lr[2 * i - 1];
        } else if (s[i - 1] == 'R') {
            lr[2 * i - 2].first = lr[2 * i - 1].first;
            lr[2 * i - 2].second = lr[2 * i - 1].second - 1;
            ud[2 * i - 2] = ud[2 * i - 1];
        } else if (s[i - 1] == 'L') {
            lr[2 * i - 2].first = lr[2 * i - 1].first + 1;
            lr[2 * i - 2].second = lr[2 * i - 1].second;
            ud[2 * i - 2] = ud[2 * i - 1];
        }

        check(2 * i - 2);
    }

    bool flg = ud[0].first <= x && x <= ud[0].second && lr[0].first <= y && y <= lr[0].second;
    std::cout << (flg ? "YES" : "NO") << std::endl;

    return 0;
}


Measured memory_bytes: 7048
<?php
fscanf(STDIN,"%d %d",$a,$b);

if($b==1){
	$out=0;
}elseif($a==$b || $a>$b){
	$out=1;
}else{
	for($i=1;$i<=20;$i++){
		//echo ($i-1)*($a-1)+$a." ".$b."\r\n";
		if(($i-1)*($a-1)+$a>=$b){
			$out=$i;
			break;
		}
	}
}
echo $out;

?>

Measured memory_bytes: 3828
def main():
    W, H, x, y = [int(val) for val in input().split()]
    area = W * H
    if (x == W / 2) and (y == H / 2):
        print(area / 2, 1)
    else:
        print(area / 2, 0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<58);


int main() {
    cin>>N;
    vec a(N);
    rep(i,N) cin>>a[i];
    ll now = 1000, last = a[0];
    a.push_back(99);
    reps(i, 1, N){
        if(last < a[i]){
            while(a[i] <= a[i+1]) ++i;
            ll num = now / last;
            (now -= num * last) += num * a[i];
            ++i;
            if(i < N) last = a[i];
        }else{
            last = min(last, a[i]);
        }
    }
    cout<<now<<endl;
}


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


class Program
{
    static void Main(string[] args)
    {
        int a = int.Parse(Console.ReadLine());
       // int[] x1 = new int[a];
        int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
       // Array.Reverse(x);
        for (int a1 = a-1; a1 >=0; a1--)
        {
            if (a1 > 0) { Console.Write(x[a1]+" "); }
            else
            {
                Console.WriteLine(x[a1]);
            }
        }
    }
}

Measured memory_bytes: 9456
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

const long long N = 2010;
long long n, m, use[N], d[N], uz[N], a, b, c;

vector <long long> g[N];
vector <pair <long long, long long> > v[N];

void dfs(long long node) {
	use[node] = 1;
	for(auto i : g[node])
		if(!use[i])
			dfs(i);
}

long long dijkstra() {
	priority_queue <pair<long long, long long> > pq;
	pq.push({0, 1});
	
	for(long long i = 1; i <= n; i++) d[i] = -1e18;
	d[1] = 0;

	while(!pq.empty()) {
		long long x = pq.top().nd; pq.pop();
		// if(x == n) return d[n];

		for(auto i : v[x])
			if(use[i.st] && d[i.st] < d[x] + i.nd && uz[i.st] < n + 1) {
				uz[i.st]++;
				d[i.st] = d[x] + i.nd;
				pq.push({d[i.st], i.st});
			} else if(uz[i.st] >= n + 1) 
				return 1e18;
	}
	return d[n];
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	for(long long i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		// v[b].push_back({a, c});
		g[b].push_back(a);
	}

	dfs(n);

	// dbg_v(use, n + 1);

	long long ans = dijkstra();
	if(ans < 1e18) cout << ans << '\n';
	else cout << "inf\n";
}	

	

Measured memory_bytes: 1148
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		long[] array = new long[n];
		for (int i = 0; i < array.length; i++) {
			array[i] = sc.nextLong();
		}
		Prime pri = new Prime();
		int count = 0;
		for (int i = 0; i < array.length; i++) {
			if (pri.primeNumbers(array[i])) {
				count++;
			}
		}
		System.out.println(count);
	}
}

class Prime {
	long[] primeArray;
	public Prime(){
		primeArray = new long[10000];
		int primeCount = 0;
		boolean flag = true;
		for (int i = 2; primeCount < primeArray.length; i++) {
			flag = true;
			for (int j = 2; j <= (i / 2) + 1; j++) {
				if(i != j && i % j == 0){
					flag = false;
					break;
				}
			}
			if(flag) {
				primeArray[primeCount++] = i;
			}
		}
	}
	public boolean primeNumbers(long x) {
		for (int i = 0; i < primeArray.length; i++) {
			if(primeArray[i] == x){
				return true;
			}
		}
		if(primeArray[primeArray.length - 1] >= x){
			return false;
		}
		for (int i = 0; i < primeArray.length; i++) {
			if(x != primeArray[i] && x % primeArray[i] == 0){
				return false;
			}
		}
		return true;
	}
}


Measured memory_bytes: 43704
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    
    
    vector<pair<int,int>> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i].first;
        A[i].second = i+1;
    }
    
    sort(A.begin(),A.end());
    
    for(int i=0;i<N;i++){
        cout << A[i].second << endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 1664
package main

import (
	"fmt"
	"strings"
)

func main() {
	for {
		var h, w int

		fmt.Scan(&h)
		fmt.Scan(&w)

		if h == 0 && w == 0 {
			break
		}

		fmt.Println(strings.Repeat(strings.Repeat("#", w)+"\n", h))
	}
}



Measured memory_bytes: 1316
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cstdlib>
#include <memory.h>
#include <ctime>
#include <bitset>

using namespace std;

#define ABS(a) ((a>0)?a:-(a))
#define MIN(a,b) ((a<b)?(a):(b))
#define MAX(a,b) ((a<b)?(b):(a))
#define FOR(i,a,n) for (int i=(a);i<(n);++i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define pnt pair <int, int>
#define mp make_pair
#define PI 3.1415926535897
#define MEMS(a,b) memset(a,b,sizeof(a))
#define LL long long
#define U unsigned

int main()
{
#ifdef Fcdkbear
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	double beg = clock();
#endif

	LL a, b, c;
	cin >> a >> b >> c;
	int res = 0;
	FOR(it, 0, 1000000) {
		if ((a & 1) || (b & 1) || (c & 1)) {
			cout << res << endl;
			return 0;
		}
		res++;
		LL na = b / 2 + c / 2;
		LL nb = a / 2 + c / 2;
		LL nc = a / 2 + b / 2;
		a = na;
		b = nb;
		c = nc;
	}
	cout << -1 << endl;

#ifdef Fcdkbear
	double end = clock();
	fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
#endif
	return 0;
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vvi v(n, vi(3));
	REP(i, n)REP(j, 3)cin >> v[i][j];
	vvi dp(n + 1, vi(3,-INF));
	REP(i, 3)dp[0][i] = 0;
	REP(i, n) {
		REP(j, 3) {
			REP(k, 3) {
				if (j == k)continue;
				dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + v[i][k]);
			}
		}
	}
	cout << *max_element(ALL(dp[n])) << endl;

}

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

using namespace std;

#define MAX 310
#define INF LLONG_MAX/4
typedef long long ll;

ll N,a[MAX],s[MAX];
ll memo[MAX][MAX];

int getSize(ll v){
    int cnt = 0;
    while(v > 0){
        v /= 10; cnt++;
    }
    return cnt;
}

ll calc(ll X,ll Y){
    ll res = 0LL,c = 0;
    int size = max(getSize(X),getSize(Y));
    for(int i = 0 ; i < size ; i++){
        ll x = X%10,y = Y%10;
        c = (x + y + c) / 10;
        res += x*y+c;
        X /= 10; Y /= 10;
    }
    return res;
}

ll solve(int L,int R){
    if(L+1 == R) return 0;
    ll &res = memo[L][R];
    if(res != INF) return res;
    for(int i = L+1 ; i < R ; i++){
        ll cost = calc(s[i]-s[L],s[R]-s[i]);
        res = min(res,solve(L,i)+solve(i,R)+cost);
    }
    return res;
}

int main(){
    int N;
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> a[i];
        s[i+1] = a[i] + s[i];
    }
    fill(memo[0],memo[0]+MAX*MAX,INF);
    cout << solve(0,N) << endl;
    return 0;
}

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

typedef long long ll;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}


int main(){
 ll N,M;
 cin >> N >> M;
 if(2*N > M){
   cout << M / 2 << endl;
 }else{
   cout << (2*N+M)/4 << endl;
 }
}

Measured memory_bytes: 256