akhauriyash/Code-Regression huggingface dataset:
D,G = map(int,input().split())
pc = []
for i in range(D):
    pc.append(list(map(int,input().split())))

ans = 10**10
for i in range(1 << D):
    c = 0
    p = 0
    l = []
    for j in range(D):
        if ((i >> j) & 1) == 1:
            c += pc[j][0]
            p += (j+1)*100*pc[j][0] + pc[j][1]
            l.append(j)
    ma = 0
    for ii in range(D-1,-1,-1):
        if ii not in l:
            ma = ii
            break
    for k in range(pc[ma][0]):
        if p >= G:
            break
        c += 1
        p += (ma+1)*100

    if p >= G:
        ans = min(ans , c)
print(ans)


Measured memory_bytes: 42992
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" << v[0]; FOR(i_debug, 1, v.size()){ cout << "," << v[i_debug]; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
// #define f first
// #define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;

int main()
{
	string S;
	cin >> S;
	string ans = "No";
	if (S[0] == S[1] && S[3] == S[2] && S[1] != S[2])
		ans = "Yes";
	if (S[0] == S[2] && S[1] == S[3] && S[1] != S[2])
		ans = "Yes";
	if (S[0] == S[3] && S[1] == S[2] && S[1] != S[0])
		ans = "Yes";

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
a_sort = sorted(a)
a_kosu = [0] * n

for i in range(n):
    a_kosu[a_sort[i] - 1] = a_kosu[a_sort[i] - 1] + 1

sum = 0

for i in range(n):
    if a_kosu[i] != 0:
        sum = sum + int(a_kosu[i] * (a_kosu[i] - 1) / 2)
        
for i in range(n):
    ans[i] = sum - (a_kosu[a[i] -1] - 1)
    print(ans[i])

Measured memory_bytes: 26140
n, m = map(int, input().split())
ac, wa = 0, 0
ac = [0]*(n+1)
wa = [0]*(n+1)
ans1, ans2 = 0, 0
for i in range(m):
    p, s = map(str, input().split())
    if ac[int(p)]==1: continue
    if s=='AC':
        ac[int(p)] = 1
        ans1 += 1
        ans2 += wa[int(p)]
    else:
        wa[int(p)] += 1
print(ans1, ans2)


Measured memory_bytes: 4596
#include <iostream>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;
using edge_set = unordered_set<int>;

int main() {

    int V, E;
    cin >> V >> E;

    int count = 0;
    pair<int, int> order[V];
    edge_set indeg[V], outdeg[V];

    for (int i = 0; i < V; i++) {
        order[i].second = i;
    }

    int s, t;
    for (int i = 0; i < E; i++) {
        int s, t;
        scanf("%d %d", &s, &t);
        indeg[t].insert(s);
        outdeg[s].insert(t);
    }

    queue<int> que;

    for (int i = 0; i < V; i++) {
        if (indeg[i].empty()) {
            que.push(i);
        }
    }

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : outdeg[u]) {
            indeg[v].erase(u);
            if (indeg[v].empty()) {
                que.push(v);
            }
        }
        order[u].first = ++count;
    }

    //count < |V| なら閉路がある

    sort(order, order + V);

    for (int i = 0; i < V; i++) {
        cout << order[i].second << endl;
    }
}


Measured memory_bytes: 8472
/*
    Bismillahir Rahmanir Raheem
    Think Twice Code Once
    author : reaziii
*/
#include<bits/stdc++.h>
#define sc(x)        scanf("%lld",&x)
#define pcase(x)     printf("Case %d: ",x++)
#define pn           printf("\n")
#define fri(f)       for(int i=0;i<f;i++)
#define frj(f)       for(int j=0;j<f;j++)
#define reset(x,e)   memset(x,e,sizeof(x))
#define all(x)       x.begin(),x.end()
#define input        freopen("input.txt","r",stdin);
#define output       freopen("output.txt","w",stdout)
#define infi         INT_MAX
#define m_v          3000000
#define pii          pair<int,int>
#define pch          pair<char,char>
#define pll          pair<ll,ll>
#define mgraph       map<int,vector<int> >
#define mp           make_pair
#define pb           push_back
#define clr(x)       memset(x,0,sizeof(x))
#define frx(x,y)     for(int x=0;x<y;x++)
#define deb(x)       cout<<x
#define ideb(i,x)    cout<<i<<" "<<x
#define F            first
#define S            second
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
bool checkbitt(ll num, int pos);
ll setbitt(ll num, ll pos);
ll resetbitt(ll num, int pos);
//.................___Start from here___.................//
//.................._____________________................//
ll const N = 1000009;
ll const mod = 998244353;
vector<int> divisors[N];

void divisor() {
	for (int i = 1; i < N; i++) {
		for (int j = i; j < N; j += i) {
			divisors[j].pb(i);
		}
	}
}

ll sqsum[N];
ll sumsq[N];
ll power(ll n, ll b) {
	if (b == 0) return 1;
	ll p = power(n, b / 2) % mod;
	p = (p * p) % mod;
	return b & 1 ? (p * n) % mod : p;
}
ll modinverse(ll n) {
	return power(n, mod - 2);
}
int ext[N];

int solve() {
	ll n;
	sc(n);


	ll val;
	fri(n) {
		sc(val);
		for (auto x : divisors[val]) {
			sqsum[x] = (sqsum[x] + power(val, 2)) % mod;
			sumsq[x] = (sumsq[x] + val) % mod;
		}

	}

	ll res = 0;
	for (int i = N - 1; i >= 1; i--) {
		ll cur = (power(sumsq[i], 2) - sqsum[i]) % mod;
		cur = (cur + mod) % mod;

		for (ll j = i + i; j < N; j += i) {
			cur -= ext[j];
			cur = (cur + mod) % mod;
		}
		ext[i] = cur;
		res = (res + (cur * modinverse(i)) % mod) % mod;
	}

	res = (res * modinverse(2)) % mod;

	printf("%lld\n", res);





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


bool checkbitt(ll num, int pos) {
	return (num >> pos) & 1;
}

ll setbitt(ll num, ll pos) {
	return (1 << pos) | num;
}

ll resetbitt(ll num, int pos) {
	if (!checkbitt(num, pos)) {
		return num;
	}
	else {
		return (1 << pos)^num;
	}
}



Measured memory_bytes: 137656
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
typedef set <int> st;
typedef set <char> stc;
typedef vector<int>::iterator itr;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sq(a) a*a
#define cu(a) (sq(a)*a)
#define sf1(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d", &a , &b)
#define pf1(a) printf("%d\n",a)
#define pf2(a,b) printf("%d %d\n", a , b)
#define Last(i) ( (i) & (-i) )
 
const int mod = 1000000007;
const int maxn = (int)2e5+30;
const ll nnn = (ll)5e7+5;
const int inf = 1e9+9;
const ll INF = 1e18;

int main() {
   
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);	
    
    ull a[maxn];
    ull b[maxn];
    ull n;
    ull ans[maxn];
    ull final = 0;
    
    cin >> n;
    
    memset(b,-1,sizeof(b));
    
    f1(n) cin >> a[i] , b[a[i]]++;
    
    f1(n){
        
        
    //	cout << i << ' ' << b[i] << ' ' << ((b[i] + 1) * b[i]) / 2  << endl;
    	
    	if(b[i] > 0)final += ((b[i] + 1) * b[i]) / 2;
    	
	}
	
	
	f1(n){
		
		ull s = a[i];
	    ull ot= b[s]-1;	
	    
	    //cout << s << ' ' << ot << ' ' << ( ((b[s] + 1) * b[s]) / 2 ) << ' ' << (((ot + 1) * ot) / 2) << "\n";
	    
		cout << final -( ((b[s] + 1) * b[s]) / 2 )+ (((ot + 1) * ot) / 2) << "\n";
		
	}
    
    
    return 0;
    
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr auto INF = INT_MAX >> 1;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int n, m;
	cin >> n >> m;
	vi h(n);
	rep(i, n)cin >> h[i];

	vvi e(n, vi(0));

	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--;b--;
		e[a].push_back(b);
		e[b].push_back(a);

	}
	
	int ans = 0;

	rep(i, n) {
		bool good = true;
		rep(j, e[i].size())if (h[i] <= h[e[i][j]])good = false;
		if (good)ans++;
	}

	cout << ans << endl;

}

Measured memory_bytes: 8804
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <fstream>
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
#define eps 1e-10
#define LL_INF 0x33ffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define pper(i,n,m) for(int i = n;i >= m; i--)
#define repp(i, n, m) for (int i = n; i <= m; i++)
#define rep(i, n, m) for (int i = n; i < m; i++)
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back

const int maxn = 1e5 + 5;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
ll po(ll a, ll b,ll mod) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1)res = res*a%mod; a = a*a%mod; }return res; }
ll gcd(ll a,ll b){ if(a==0){return b;}else{ return gcd(b%a,a);}}

int n,cnt;
int vis[maxn],pri[maxn];
ll val[maxn],two[maxn],tri[maxn];
map<ll,int>num;
map<ll,ll>con;

void init()
{
	cnt=0;
	int up=1e5;
	memset(vis,0,sizeof(vis));

	for(int i=2;i<=up;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			cnt++;
			pri[cnt]=i;
		}
		for(int j=i+i;j<=up;j+=i)
		{
			vis[j]=1;
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		two[i] = 1LL*pri[i]*pri[i];
		tri[i] = 1LL*two[i]*pri[i];
	}
}

int max(int a,int b)
{
	if(a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&val[i]);
		
		ll tmp = val[i];
		ll rev=1;
		ll ori=1;
		for(int j=1;j<=cnt&&pri[j]<=tmp;j++)
		{
			if(pri[j]>1200)break;
			if(tmp%pri[j]==0)
			{
				int c=0;
				while(tmp%pri[j]==0)
				{
					c++;
					tmp/=pri[j];
				}
				if(c%3==1)
				{
					rev*=two[j];
					ori*=pri[j];
				}
				else if(c%3==2)
				{
					rev*=pri[j];
					ori*=two[j];
				}
			}
		}
		//cout<<rev<<endl;
		//cout<<tmp*tmp<<endl;
		//cout<<1e18/rev<<endl;
		if(sqrt(1.0*tmp+0.5)*sqrt(1.0*tmp+0.5)==tmp)
		{
			rev*=sqrt(1.0*tmp);
			ori*=tmp;
		}
		else if(tmp*tmp<(1e18/rev))
		{
			ori*=tmp;
			rev*=tmp*tmp;
		}
		else
		{
			ori*=tmp;
			rev=-1;
		}
		con[ori]=rev;
		num[ori]++;

	}
	map<ll,int>::iterator it;
	int ans=0;
	/*
	for(it=num.begin(); it!=num.end(); it++)
	{
		cout<<it->first<<" "<<it->second<<" "<<con[it->first]<<endl;
	}
	*/
	for(it=num.begin(); it!=num.end(); it++)
	{
		if(it->first==1)continue;
		if(it->second==0)continue;
		ll tmp = it->first;
		ll s = con[tmp];

		//cout<<s<<" "<<num[s]<<endl;
		//cout<<it->second<<endl;
		ans+=max(it->second,num[s]);
		//cout<<"ans: "<<ans<<endl;
		it->second=0;
		num[s]=0;
	}
	if(num[1])ans++;
	printf("%d\n",ans);
}

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

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

using namespace std;

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

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

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

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

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

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

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

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

    if (k > (n + 1) / 2) {
        cout << -1 << endl;
        ret();
    }

    ll a = k;
    ll b = k + 2 * n - 1;
    ll c = b + k;

    set<int> sa, sb, sc;
    vector<vector<ll>> ans;

    while (k + n <= b && k + 2 * n <= c) {
        sa.insert(a);
        sb.insert(b);
        sc.insert(c);
        ans.push_back({a, b, c});
        a++;
        b -= 2;
        c--;
    }

    b = k + 2 * n - 1;
    c = k + 3 * n - 1;

    while (sb.count(b)) b--;
    while (sc.count(c)) c--;
    while (a < k + n && k + n <= b && k + 2 * n <= c) {
        sa.insert(a);
        sb.insert(b);
        sc.insert(c);

        ans.push_back({a, b, c});
        a++;
        b--;
        c--;

        while (sb.count(b)) b--;
        while (sa.count(c)) c--;

    }

    for (vector<ll> &v: ans) printf("%lld %lld %lld\n", v[0], v[1], v[2]);


}




Measured memory_bytes: 22800
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define N 4100
#define NN 201000
typedef long long ll;
template<typename T> inline void read(T &x) {
  x = 0; char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
}
using namespace std;
const int up = 4010;
const int base = 2001;
const int P = 1e9 + 7;
const int inv2 = 5e8 + 4;
inline ll quickpow(ll x, int k) {
  ll res = 1;
  while (k) {
    if (k & 1)  res = res * x % P;
    x = x * x % P;
    k >>= 1;
  }
  return res;
}
int n;
int a[NN], b[NN];
int f[N][N];
int ed[N][N];
ll jie[NN], jieni[NN];
inline void init() {
  jie[0] = jieni[0] = 1;
  for (int i = 1; i <= 10000; ++i)  jie[i] = jie[i - 1] * i % P;
  jieni[10000] = quickpow(jie[10000], P - 2);
  for (int i = 9999; i; --i)  jieni[i] = jieni[i + 1] * (i + 1) % P;
}
inline ll get_c(int n, int m) {
  if (n < 0 || m < 0 || n - m < 0)  return 0;
  return jie[n] * jieni[m] % P * jieni[n - m] % P;
}

inline void work() {
  ll ans = 0;
  for (int i = 1; i <= up; ++i) {
    for (int j = 1; j <= up; ++j) {
      f[i][j] = (1ll * f[i][j] + f[i - 1][j] + f[i][j - 1]) % P;
//      if (i <= base + 3 && i >= base - 3 && j <= base + 3 && j >= base - 3) printf("f[%d][%d] = %d\n", i - base, j - base, f[i][j]);
      if (ed[i][j]) ans = (ans + 1ll * ed[i][j] * f[i][j]) % P;//, printf("ans += %d * %d\n", ed[i][j], f[i][j]);
    }
//    if (i <= base + 3 && i >= base - 3) puts("");
  }
//  printf("yuan : ans = %lld\n", ans);
  for (int i = 1; i <= n; ++i) {
    ans = (ans - get_c((a[i] + b[i]) << 1, a[i] << 1) + P) % P;
  }
//  printf("now ans = %lld\n", ans);
  ans = ans * inv2 % P;
  printf("%lld\n", (ans % P + P) % P);
}

int main() {
  read(n);
  for (int i = 1; i <= n; ++i)  read(a[i]), read(b[i]), ++f[base - a[i]][base - b[i]], ed[base + a[i]][base + b[i]]++;
  init();
  work();
  return 0;
}


Measured memory_bytes: 92428
#include<iostream>
using namespace std;
int main(){
  int a, b;
  cin >> a >> b;

  int c[3][7] ={ {1,3,5,7,8,10,12}
   ,{4,6,9,11}
  ,{2}};
  
  bool ans = false;
  int cnt = 0;
  for(int i=0; i<7; i++){
if(a==c[0][i] || b==c[0][i])
  cnt++;
  }
  if(cnt ==2){
    cout << "Yes";
return 0;
  }
  cnt =0;
for(int i=0; i<4; i++){
if(a==c[1][i] || b==c[1][i])
  cnt++;
  }
  if(cnt ==2){
    cout << "Yes";
return 0;
  }
  else
    cout << "No";
  
  return 0;
}


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

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

	int sum = 0;
	vector<int> w(n);
	rep(i, n){
		cin >> w.at(i);
		sum += w.at(i);
	}

	int ma = 100;
	int now = 0;
	rep(i, n){
		now += w.at(i);
		int leave = sum-now;
		ma = min(ma, abs(leave-now));
	}
	
	cout << ma << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int N;
  long K;
  scanf("%d %ld", &N, &K);
  long num[100001];
  for(int i = 0; i < 100001; i++)
    num[i] = 0;
  for(int i = 0; i < N; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    num[a] += b;
  }
  long k = 0;
  for(int i = 1; i < 100001; i++){
    k += num[i];
    if(k >= K){
      printf("%d\n", i);
      return 0;
    }
  }
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';

using namespace mp;
using namespace std;

int main(void){
    ll K;
    cpp_int N;
    ll dl=0, di[101];
    cin>>N;
    cin>>K;
    rep(i, 100){
        if(N==(cpp_int)0) break;
        di[i]=(ll)(N%10);//cout<<di[i]<<endl;
        N/=10;
        dl++;
    }
    ll binded[3], nonbi[3];
    MEMSET(binded, 0);
    MEMSET(nonbi, 0);
    binded[2]=1;
    nonbi[2]=di[dl-1]-1;
    nonbi[3]=1;
    rep(i, dl-1){
        ll non[3];
        MEMSET(non, 0);
        int index=dl-i-2;
        if(di[index]!=0){
            //cout<<i<<sp<<di[index]<<endl;
            non[2]=binded[2];
            non[1]=binded[2]*(di[index]-1)+binded[1];
            non[0]=binded[1]*(di[index]-1)+binded[0];
            binded[0]=binded[1];
            binded[1]=binded[2];
            binded[2]=0;
        }
        nonbi[0]=nonbi[1]*9+nonbi[0]+non[0];
        nonbi[1]=nonbi[2]*9+nonbi[1]+non[1];
        nonbi[2]=nonbi[3]*9+nonbi[2]+non[2];
        /*cout<<binded[0]<<sp<<nonbi[0]<<endl;
        cout<<binded[1]<<sp<<nonbi[1]<<endl;
        cout<<binded[2]<<sp<<nonbi[2]<<endl;
        cout<<endl;*/
    }
    cout<<nonbi[3-K]+binded[3-K]<<endl;
    return 0;
}


Measured memory_bytes: 256
use proconio::{fastout, input};

fn pow<T>(mut x: T, mut y: T, p: T) -> T
where
    T: num::PrimInt,
{
    let mut ret = num::one();
    while y > num::zero() {
        if y & num::one() == num::one() {
            ret = ret * x % p;
        }
        x = x * x % p;
        y = y >> 1;
    }
    ret
}

#[fastout]
fn main() {
    input! {
        n: u64, k: u64
    }
    const M: u64 = 1000000007;
    let mut v = vec![0; (k + 1) as usize];
    let mut ans = 0;
    for x in (1..=k).rev() {
        let mut s = pow(k / x, n, M);
        for y in 2..=(k / x) {
            s = (s + (M - v[(x * y) as usize])) % M;
        }
        v[x as usize] = s;
        ans += s * x;
        ans %= M;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2800
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
//#include <map>
#include <vector>

using namespace std;



int main()
{
	int n;
	int bunpu[6];
	double sintyou;
	
	for (int i=0; i<6; i++) bunpu[i] = 0;
	cin >> n;
	for (int i=0; i<n; i++)
	{
		cin >> sintyou;
		if (sintyou < 165.0)
		{
			bunpu[0]++;
		} else if (165.0 <= sintyou && sintyou < 170.0) {
			bunpu[1]++;
		} else if (170.0 <= sintyou && sintyou < 175.0) {
			bunpu[2]++;
		} else if (175.0 <= sintyou && sintyou < 180.0) {
			bunpu[3]++;
		} else if (180.0 <= sintyou && sintyou < 185.0) {
			bunpu[4]++;
		} else if (185.0 <= sintyou) {
			bunpu[5]++;
		}
	}
	for (int i=0; i<6; i++)
	{
		cout << i + 1 << ":";
		for (int j=0; j<bunpu[i]; j++)
		{
			cout << "*";
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1232
/**
 *    author:  Mohamad Milhem
 *    created: 2020-02-28-10.32.55
**/

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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define MOD ll(1000000007)
#define debug(x) cout << '[' << #x << " is: " << x << "] " <<endl;
#define decimalpoint cout << std::fixed << setprecision(5)


int main(){

    FAST;

    long long n;
    int s;

    cin >> n >> s;

    int cont = 0;
    while(n){
        n/=s;
        cont++;
    }
    cout << cont <<endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
    
int main()
{
   string s,t;
   cin >> s >> t;
   int m = s.size(); int n = t.size();
    int ans = n;
   for(int i = 0 ; i <= m-n ; i++){
       int c = 0;
       for(int j = 0 ; j < n ; j++){
           if(s[i+j] == t[j]){
               c++;
           }
       }
       ans = min(ans,n-c);
   }

    cout << ans;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる





int main() {
  int a,b;
  cin>>a>>b;

  cout << 2*b-a << endl;
}

Measured memory_bytes: 256
#117-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,m=IL()
xl=IL()
if n>=m:
    print(0)
else:
    dif=[]
    xl.sort()
    for i in range(m-1):
        dif.append(xl[i+1]-xl[i])
    dif.sort()
    print(sum(dif[:m-n]))

Measured memory_bytes: 13968
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int n, k; string s;

int main() {
	cin >> n >> k >> s;
	int t = 0, y = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '0') {
			t++;
		}
		else if (s[i] == '1') {
			y++;
		}
	}
	if (t == n || y == n) {
		cout << n << endl;
		return 0;
	}
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}
	int count = 1;
	vector<int>h;
	vector<int>w;
	for (int i = 1; i < n; i++) {
		if (s[i - 1] == s[i]) {
			count++;
		}
		else {
			h.push_back(count);
			w.push_back(s[i - 1] - '0');
			count = 1;
		}
		if (i == n - 1) {
			w.push_back(s[i] - '0');
			h.push_back(count);
		}
	}
	for (int i = 1; i < h.size(); i++) {
		h[i] += h[i - 1];
	}
	h.insert(h.begin() + 0, 0);
	h.insert(h.end() + 0, h[h.size() - 1]);
	if (w[0] == '0') {
		w.insert(w.begin(), '1');
	}
	else {
		w.insert(w.begin(), '0');
	}
	count = 0;
	for (int i = 0; i < w.size(); i++) {
		if (w[i] == 0) {
			count++;
		}
	}
	k = min(count, k);
	int ans = 0;
	for (int i = 0; i < h.size() - (k * 2 + 1); i++) {
		if (w[i + 1] == 0) {
			ans = max(ans, h[i + k * 2] - h[i]);
		}
		else {
			ans = max(ans, h[i + k * 2 + 1] - h[i]);
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int h,w; cin >> h >> w;
  int flg = 1;
  char tizu[h][w];

  rep(i,h)rep(j,w) cin >> tizu[i][j];
  rep(i,h)rep(j,w) {
    if(tizu[i][j]=='#') {
      int dx1 = i+1;
      int dx2 = i-1;
      int dy1 = j+1;
      int dy2 = j-1;
      if (dx1>=0 && dx1 < h && tizu[dx1][j]=='#' || dx2>=0 && dx2 < h && tizu[dx2][j]=='#' || dy1>=0 && dy1 < w && tizu[i][dy1]=='#' || dy2>=0 && dy2 < w && tizu[i][dy2]=='#' ) {
        continue;
      } else {
        flg = 0;
        break;
      }
    }
  }
  if (flg) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>

int main(void)
{
  int N,A,B;
  scanf("%d",&N);
  if(N==1)
  {
    printf("Hello World\n");
  }
  else
  {
    scanf("%d %d",&A,&B);
    printf("%d\n",A+B);
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}


int main(){

  ll x,y,a,b,c;
  cin >> x >> y >> a >> b >> c;

  vector<ll> p(a),q(b),r(c);
  for(auto &&x:p)cin>>x;
  for(auto &&x:q)cin>>x;
  for(auto &&x:r)cin>>x;

  SORT(p);REV(p);
  SORT(q);REV(q);
  SORT(r);REV(r);

  int i = x-1;
  int j = y-1;
  int k = 0;

  ll ans = 0;
  bool ok=true;
  while(ok){
    if(k==c)break;
    if(i>=0 && j>=0){
      if(p[i]<q[j] && p[i]<r[k]){
        k++;
        i--;
      }else if(p[i]>=q[j] && q[j]<=r[k]){
        k++;
        j--;
      }else{
        ok = false;
      }
    }else if(j>=0){
      if(q[j]<=r[k]){
        k++;
        j--;
      }else{
        ok = false;
      }
    }else if(i>=0){
      if(p[i]<=r[k]){
        k++;
        i--;
      }else{
        ok = false;
      }
    }else{
      ok = false;
    }
  }

  FOR(l,0,i+1)ans += p[l];
  FOR(l,0,j+1)ans += q[l];
  FOR(l,0,k)ans += r[l];
  cout << ans << endl;
}

Measured memory_bytes: 2560
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    rep (i, 3) {
        rep (j, 3) {
            char c;
            cin >> c;
            if (i == j) {
                cout << c;
            }
        }
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <iostream>

#define INF 1000000010

using namespace std;

void swap(int *a,int *b){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main(){
	int n,m;

	while(cin>>n>>m){
		if(n==0 && m==0)break;

		int *t,*state;
		int *s,*d;

		t = new int[m];
		state = new int[n+1];
		s = new int[m];
		d = new int[m];

	
		for(int i=0;i<m;i++){
			t[i]=INF;
			s[i]=0;
			d[i]=0;
		}
		for(int i=0;i<=n;i++){
			state[i]=0;
		}
		state[1]=1;

		for(int i=0;i<m;i++){
			cin>>t[i]>>s[i]>>d[i];
		}

		for(int i=0;i<m;i++){
			for(int j=m-1;j>i;j--){
				if(t[j]<=t[j-1]){
					swap(&t[j],&t[j-1]);
					swap(&s[j],&s[j-1]);
					swap(&d[j],&d[j-1]);
				}
			}
		}

		/*
		for(int i=0;i<m;i++){
			cout<<t[i]<<" "<<s[i]<<" "<<d[i]<<endl;
		}
		*/


		for(int i=0;i<m;i++){
			if(state[s[i]]==0)continue;

			state[d[i]]=1;
		}

		int ans=0;
		for(int i=1;i<=n;i++){
			if(state[i]==1){
				ans++;
			}
		}

		cout<<ans<<endl;


	}
	return 0;
}

Measured memory_bytes: 5180
#include<stdio.h>

#define MAX 100

int main(void){

  int x, n, A[MAX], i, j, c=0;
  int cnt=0;

  scanf("%d",&n);

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

    while(1){

      for(j = n-1; j > 0; j--){
        if(A[j] < A[j-1]){
          x = A[j];
          A[j] = A[j-1];
          A[j-1] = x;
          c++;
        }
        else cnt++;
      }
      if(cnt != n-1) cnt=0;
      if(cnt == n-1) break;
    }

  for(i = 0;i < n; i++){
    printf("%d",A[i]);
    if(i != n-1){
      printf(" ");
    }
  }
  printf("\n");
  printf("%d\n",c);

  return 0;
}

Measured memory_bytes: 604
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int N;
int main() {
	cin >> N;
	int ans = INF;
	int x[51], y[51];
	for (int i = 0; i < N; ++i) {
		cin >> x[i] >> y[i];
	}
	map<pii, int>ma;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i == j)continue;
			ma[make_pair(x[i] - x[j], y[i] - y[j])]++;
		}
	}
	int key = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			key = max(key, ma[{x[i] - x[j], y[i] - y[j]}]);
		}
	}
	cout << N - key << endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  double sum = 0;
  REP(i, n) cin >> a[i], sum += a[i];
  sort(ALLr(a));
  if(a[m-1] >= sum/(4*m)) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
l=[[0]*(w+2)]
for i in range(h):
  a=list(input())
  a.insert(0,0)
  a.append(0)
  l.append(a)
l.append([0]*(w+2))
pointx=[-1,0,1]
pointy=[-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='.':
      count=0
      for k in pointx:
        for m in pointy:
          if l[i+k][j+m]=='#':
            count+=1
      l[i][j]=str(count)

del l[0]
del l[h]
for i in range(h):
  l[i]=l[i][1:w+1]
for i in l:
  print(''.join(i))

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

#define endl '\n'

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

    string a = "YAKI";
    string b;
    cin >> b;
    if(b.size() < 4) {
        cout << "No";
        return 0;
    }
    for(int i = 0; i < 4; i++) {
        if(a[i] != b[i]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";

    return 0;
}

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

int main () {
  int N;
  string S;
  cin >> N >> S;
  if (N % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  else {
    for (int i=0; i<N/2; i++) {
      if (S[i] != S[i+N/2]) {
        break;
      }
      if (i == N/2-1) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main() {
	int a,b;
	cin >> a >> b;
	if ( a > 12 )
	{
		cout << b << endl;
	}
	else if ( a < 6 ){
		cout << 0 << endl;
	}
	else {
		cout << b / 2 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
int main(){
int n,m,b,c;
std::cin>>n>>m>>b;c=b;
for(int i=0;i<99;i++){
if(c%(n+m)<=n){goto a;}
c+=60;
}
c=-1;
a:
std::cout<<c<<"\n";
for(int i=0;i<20000;i++){
for(int j=0;j<20000;j++){
c+=1;
}
}
return 0;}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> N;
    vi a(N);
    cin >> a;
    vi mem(100010);
    REP(i, N) {
        mem[a[i]]++;
        ans += a[i];
    }
    cin >> Q;
    REP(_, Q) {
        cin >> B >> C;
        ans += (C - B) * mem[B];
        mem[C] += mem[B];
        mem[B] = 0;
        cout << ans << endl;
    }
}

Measured memory_bytes: 4048
#include<stdio.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i = 0;i < n;i++)
#define PRN(n) printf("%d\n",n)
#define PRS(s) printf("%s\n",s)
int main(void){
  int a,b;
  scanf("%d %d %d",&a,&b);
  PRN(a*a-b);
  return 0;
}
/*
scanf("%d",&n);
scanf("%d %d",&a,&b);
*/

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

template< typename T, typename E = T >
struct LazySegmentTree {
	using F = function< T(T, T) >;
	using G = function< T(T, E) >;
	using H = function< E(E, E) >;
	using P = function< E(E, int) >;
	int sz;
	vector<T> dat;
	vector<E> lazy;
	F f;
	G g;
	H h;
	P p;
	T d1;
	E d0;

	LazySegmentTree(int n, F f, G g, H h, P p, T d1, E d0) : f(f), g(g), h(h), p(p), d1(d1), d0(d0) {
		sz = 1;
		while(sz < n) sz *= 2;
		dat.clear();
		dat.resize(2 * sz - 1, d1);
		lazy.clear();
		lazy.resize(2 * sz - 1, d0);
	}
	void set(int k, T x) { dat[k + sz - 1] = x; }
	void build() {
		for(int k = sz - 2; k >= 0; k--) {
			dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
		}
	}
	inline void eval(int k, int len){
		if(lazy[k] == d0) return;
		if(k * 2 + 1 < sz * 2 - 1) {
			lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
			lazy[2 * k + 2] = h(lazy[2 * k + 2], lazy[k]);
		}
		dat[k] = g(dat[k], p(lazy[k], len));
		lazy[k] = d0;
	}
	T update(int a, int b, E x, int k, int l, int r) {
		eval(k, r - l);
		if(r <= a || b <= l) return dat[k];
		if(a <= l && r <= b) {
			lazy[k] = h(lazy[k], x);
			eval(k, r - l);
			return dat[k];
		}
		return dat[k] = f(update(a, b, x, 2 * k + 1, l, (l + r) / 2), update(a, b, x, 2 * k + 2, (l + r) / 2, r));
	}
	T update(int a, int b, E x) { return update(a, b, x, 0, 0, sz); }
	T query(int a, int b, int k, int l, int r) {
		eval(k, r - l);
		if(r <= a || b <= l) return d1;
		if(a <= l && r <= b) return dat[k];
		T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
		T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
		return f(vl, vr);
	}
	T query(int a, int b) { return query(a, b, 0, 0, sz); }
	T operator[](int k) { return query(k, k + 1); }
};

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, d, a;
	cin >> n >> d >> a;
	vector<P> b(n);
	rep(i, 0, n){
		cin >> b[i].first >> b[i].second;
	}
	sort(b.begin(), b.end());
	vector<int> x(n), h(n);
	rep(i, 0, n){
		x[i] = b[i].first;
		h[i] = b[i].second;
	}
	auto f = [](int a, int b) { return max(a, b); };
	auto g = [](int a, int b) { return a + b; };
	auto hh = [](int a, int b) { return a + b; };
	auto p = [](int a, int b) { return a; };
	LazySegmentTree<int> seg(n, f, g, hh, p, -INF, 0);
	rep(i, 0, n){
		seg.set(i, h[i]);
	}
	seg.build();
	int ans = 0;
	// cout << " : ";
	// 	rep(j, 0, n){
	// 		cout << seg[j] << " ";
	// 	}
	// 	cout << endl;
	rep(i, 0, n){
		int idx = upper_bound(x.begin(), x.end(), x[i] + 2 * d) - x.begin();
		int tmp = max(0LL, (seg[i] + a - 1) / a);
		// cout << i << " " << idx << " " << seg[i] << " " << tmp << " " << tmp * a << endl;
		ans += tmp;
		seg.update(i, idx, -tmp * a);
		// cout << " : ";
		// rep(j, 0, n){
		// 	cout << seg[j] << " ";
		// }
		// cout << endl;
	}
	cout << ans << endl;
}

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

int main()
{
  	int k, s;
  	cin>>k>>s;
  	int res = 0;
  	for(int x = 0; x <= k; x++)
    {
    	for(int y = 0; y <= k; y++)
        {
        	int z = s-x-y;
          	if(z >= 0 && z <= k)
              	res++;
        }
    }
  	cout<<res<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  int sx,sy,gx,gy;
  cin>>sx>>sy>>gx>>gy;
  string s11;
  string s12;
  string s21;
  string s22;

  for(int j = 0; j < gy-sy; j++) s11+='U';
  for(int i = 0; i < gx-sx; i++) s12+='R';
  for(int j = 0; j < gy-sy; j++) s21+='D';
  for(int i = 0; i < gx-sx; i++) s22+='L';
  
  cout<<s11<<s12<<s21<<s22;

  cout<<"L"<<s11<<"UR"<<s12<<"D"<<"R"<<s21<<"DL"<<s22<<"U"<<endl;

 


  return 0;
}


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

using namespace std;

#define int long long

signed main(){
	int n,m;
	cin >> n >> m;
	int a[n];
	int sum=0;
	for(int i=0;i<n;i++){
		cin >> a[i];
		sum+=a[i];
	}
	sort(a,a+n,greater<int>());
	int temp=ceil((double)sum/(4*m));
	int i=0;
	while(m--){
		if(a[i]<temp){
			cout << "No";
			exit(0);
		}
		i++;
	}
	cout << "Yes";
}

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

using namespace std;

int main(void)
{
    int N;
    cin >> N;
    vector<int> H(N);
    for (auto &i: H) cin >> i;
    int max = H[0];
    int ans = 1;
    for (int i = 1; i < N; i++)
    {
        if (H[i] >= max)
        {
            max = H[i];
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(int argc, char *argv[]){
    int A,B;
    std::cin >> A >> B;
    int tap = 0;
    int output = 1;
    while(output < B){
        output += A-1;
        ++tap;
    }
    std::cout << tap << std::endl;
    return 0;
}


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

using namespace std;
using vl = vector<long long>;

#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 OUT(v) cout<<v<<"\n"

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

  int N;
  long long L;
  if (scanf("%d%lld", &N, &L));

  vl A(N);
  REP(i, N) if (scanf("%d", &A[i]));
  int index = -1;
  REP(i, N-1) if (A[i] + A[i+1] >= L) index = i;
  if (index == -1)
    OUT("Impossible");
  else {
    OUT("Possible");
    FOR(i, 1, index +1) OUT(i);
    RFOR(i, N-1, index +1) OUT(i);
    OUT(index+1);
  }

  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> k(M);
  vector<vector<int>> s(M, vector<int>(0));
  int ans = 0;
  for (int i = 0; i < M; i++){
    cin >> k.at(i);
    for (int j = 0; j < k.at(i); j++){
      int a;
      cin >> a;
      s.at(i).push_back(a);
    }
  }
  vector<int> p(M);
  for(int i = 0; i < M; i++){
    cin >> p.at(i);
  }
  vector<int> sw(N);
  for (int i = 0; i < pow(2, N); i++){
    int now = i;
    for (int j = 0; j < N; j++){
      sw.at(j) = 0;
    }
    for (int j = 0; j < N; j++){
      sw.at(j) = now % 2;
      now /= 2;
    }
    for (int j = 0; j < M; j++){
      int sum = 0;
      for (int l = 0; l < k.at(j); l++){
        sum += sw.at(s.at(j).at(l)-1);
      }
      if (sum % 2 != p.at(j)){
        ans--;
        break;
      }
    }
    ans++;
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    int a,b;
    string s;
    cin >> a >> b >> s;
    string ans="Yes";
    for(int i=0; i<a; i++){
        if(0>s.at(i)-'0'||s.at(i)-'0'>9) ans="No";
    }
    if(s.at(a)!='-') ans="No";
    for(int i=0; i<b; i++){
        if(0>s.at(i+a+1)-'0'||s.at(i+a+1)-'0'>9) ans="No";
    }
    cout << ans << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c,ac=0,wa=0,tl=0,re=0;
  string x;
  vector<string> v;
  cin>>a;
  b=a;
  while(b--)
  {
    cin>>x;
    v.push_back(x);
  }
  for(int i=0;i<a;i++)
  {
    if(v[i]=="AC") ac++;
     if(v[i]=="WA") wa++;
     if(v[i]=="TLE") tl++;
     if(v[i]=="RE") re++;
  }
  cout<<"AC x "<<ac<<endl;
  cout<<"WA x "<<wa<<endl;
  cout<<"TLE x "<<tl<<endl;
  cout<<"RE x "<<re<<endl;
  return 0;
}


Measured memory_bytes: 7448
#include<stdio.h>
int main(){

  int N;
  int cut,m,fa,fb,i,max=0;
  char S[101];
  char alpha;

  scanf("%d", &N);
  scanf("%s", S);
  if(N<2)return (-1);

  for(cut=1;cut<=N;cut++){

    m = 0;

    for(alpha='a';alpha<='z';alpha++){
      for(i=0;i<cut;i++){
        if(S[i] == alpha){
          fa = 1;
        }
      }
      for(i=cut;i<N;i++){
        if(S[i] == alpha){
          fb = 1;
        }
      }
      if(fa == 1 && fb == 1){
        m++;
      }
      fa = 0;
      fb = 0;
    }
    if(m>=max){
      max = m;
    }
  }

  printf("%d\n", max);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    vector<int> v(3);
    rep(i, 3) cin>>v[i];
    sort(v.begin(), v.end());
    int ans = 0;
    if((v[2]-v[0] + v[2]-v[1])%2 == 0){
        ans = (v[2]-v[0] + v[2]-v[1])/2;
    }
    else{
        ans = (v[2]-v[0] + v[2]-v[1]+3)/2;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
use std::collections::HashMap;


fn main() {
    let s: String = read();
    let t: String = read();

    let text = if is_bijection(&s, &t) && is_bijection(&t, &s) { "Yes" } else { "No" };
    println!("{}", text);
}


fn is_bijection(s: &String, t: &String) -> bool {
    let mut is_bijection = true;
    let mut hmap = HashMap::new();
    for (cs, ct) in s.chars().zip(t.chars()) {
        let c = hmap.entry(cs).or_insert(ct);
        if *c != ct {
            is_bijection = false;
            break;
        }
    }
    is_bijection
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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; }

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;cin>>n;
  string s;cin>>s;
  vector<int>east(n+1);
  rep(i,n)east[i+1]=east[i]+(s[i]=='E');
  int  res=1e9;
  rep(i,n)
  {
    int tres=0;
    tres+=i-east[i];
    tres+=east[n]-east[i+1];
    chmin(res,tres);
  }
  cout<<res<<endl;


  return 0;

}


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

int main(void){
  char s[210], p[110];
  cin >> s >> p;
  strcpy(s+strlen(s), s); // sの直後にsをつなげる
  cout << (strstr(s, p)?"Yes":"No") << endl;
    
  return 0;
}



Measured memory_bytes: 3176
#include <iostream>
using namespace std;
#define finish(x) return cout << x << endl, 0;
#define ll long long

int a, b;
string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a >> b >> s;
    if(s[a] != '-') finish("No");
    for(int i = 0 ; i < s.size() ; i++){
        if(i == a) continue;
        if(s[i] < '0' || s[i] > '9') finish("No");
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
def lower_bound(arr, v)
  l = -1
  r = arr.size
  while l + 1 < r
    m = (l + r) / 2
    if arr[m] <= v then l = m
    else r = m
    end
  end
  l
end

loop do
  n, q = gets.split.map(&:to_i)
  break if n == 0
  era = {}
  n.times do
    name, ey, wy = gets.split
    era[wy.to_i] = [name, ey.to_i]
  end
  era = era.sort
  q.times do
    y = gets.to_i
    k = era.transpose[0]
    v = era.transpose[1]
    x = lower_bound(k, y)
    if x != -1 && y == k[x]
      puts "#{v[x][0]} #{v[x][1]}"
    elsif x != n - 1
      if k[x+1] - y < v[x+1][1]
        puts "#{v[x+1][0]} #{v[x+1][1] - (k[x+1] - y)}"
      else puts "Unknown"
      end
    else puts "Unknown"
    end
  end
end

Measured memory_bytes: 57128