akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define mo 1000000007
#define add(a,b) (a+b<mo)?(a+=b):(a+=b-mo)
using namespace std;
int fac[10010],nifac[10010],a[4010][4010],x[200010],y[200010];
int getmi(int a,int x)
{
	int ans=1;
	while (x)
	{
		if (x&1) ans=(long long)ans*a%mo;
		a=(long long)a*a%mo;
		x>>=1;
	}
	return ans;
}
int calc(int x,int y){return (long long)fac[x+y]*nifac[x]%mo*nifac[y]%mo;}
int main()
{
	fac[0]=nifac[0]=1;
	for (int i=1;i<=8000;i++)
	{
		fac[i]=(long long)fac[i-1]*i%mo;
		nifac[i]=getmi(fac[i],mo-2);
	}
	int n;scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		a[-x[i]+2000][-y[i]+2000]++;
	}
	for (int i=0;i<=4000;i++)
	for (int j=0;j<=4000;j++)
	{
		if (i) add(a[i][j],a[i-1][j]);
		if (j) add(a[i][j],a[i][j-1]);
	}
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		add(ans,a[x[i]+2000][y[i]+2000]);
		add(ans,mo-calc(x[i]+x[i],y[i]+y[i]));
	}
	cout<<(long long)ans*nifac[2]%mo<<endl;
}

Measured memory_bytes: 64512
#include<stdio.h>
int main(){
	int W,H,x,y,r;
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
		if(0<=x-r&&W>=x+r&&0<=y-r&&H>=y+r){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	return 0;
}

Measured memory_bytes: 2620
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int[] b = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            b[i] = sc.nextInt();
        }
        int[] a = new int[n];
        a[0] = b[0];
        for (int i = 1; i < n - 1; i++) {
            a[i] = Math.min(b[i - 1], b[i]);
        }
        a[n - 1] = b[n - 2];
        int ans = 0;
        for (int x : a) {
            ans += x;
        }
        System.out.println(ans);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 22356
#include <stdio.h>
#include <algorithm>

constexpr unsigned int N = 2e6;
char buffer[N];
char *ptr = buffer;
constexpr unsigned int S = 5e5;
char Out[2 * S];
char *left = Out + S, *right = Out + S;

int main(void){
    fread(buffer, sizeof(char), N, stdin);
    while('a' <= *ptr) *(right++) = *(ptr++);
    unsigned int q = 0;
    while(*(++ptr) >= '0') q = 10 * q + *ptr - '0';
    bool flag = false;
    while(q--){
        if(*(++ptr) == '1') flag = not flag;
        else{
            if((*(ptr += 2) == '1') ^ flag) *(--left) = *(ptr += 2);
            else *(right++) = *(ptr += 2); 
        }
        ptr++;
    }
    if(flag) std::reverse(left, right);
    fwrite(left, sizeof(char), right - left, stdout);
    return 0;
}

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

template<typename T> vector<int> z_algorithm(int len, T& in) {
  vector<int> res(len, 0);
  int c = 0;
  for (int i = 1; i < len; ++i) {
    if (i + res[i - c] < c + res[c]) {
      res[i] = res[i - c];
    } else {
      int j = max(0, c + res[c] - i);
      while (i + j < len && in[j] == in[i + j]) j++;
      res[i] = j;
      c = i;
    }
  }
  res[0] = len;
  return res;
}

template<typename T> vector<int> z_algorithm(T& in) {
  return z_algorithm((int) in.size(), in);
}

template<typename T> vector<int> z_algorithm(T& in_first, T& in_second) {
  T combined;
  combined.append(in_first);
  combined.append(in_second);
  int n = (int) in_first.size(), m = (int) in_second.size();
  vector<int> v = z_algorithm(n + m, combined);
  vector<int> res(m);
  for (int i = 0; i < m; i++) {
    res[i] = min(n, v[i + n]);
  }
  return res;
}

class UnionFind {
private:
  int siz;
  vector<int> a;

public:
  UnionFind(int x) : siz(x), a(x, -1) {}

  int root(int x) {
    return a[x] < 0 ? x : a[x] = root(a[x]);
  }

  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    siz--;
    if (a[x] > a[y]) swap(x, y);
    a[x] += a[y];
    a[y] =x;
    return true;
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  int size(int x) {
    return -a[root(x)];
  }
  
  int conneted_component() {
  	return siz;
  }
};

signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  string s, t;
  cin >> s >> t;
  int n = (int) s.size(), m = (int) t.size();
  s.append(s);
  s.append(s);
  while ((int) t.size() * 2 >= (int) s.size()) s.append(s);
  vector<int> v = z_algorithm(t, s);
  UnionFind uf(n);
  for (int i = 0; i < n; i++) {
    if (v[i] == m && v[i + m] == m) {
      if (!uf.unite(i, (i + m) % n)) {
        cout << -1 << endl;
        return 0;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] == m) ans = max(ans, uf.size(i));
  }
  cout << ans << endl;
  return 0;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
//constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  string S, T;
  cin >> S >> T;
  int n = S.size();
  string ans = "Yes";
  if(S.size() + 1 != T.size()){
    ans = "No";
  }
  REP(i, min(n, (int)T.size())){
    if(S[i] != T[i]){
      ans = "No";
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

int main(void) {
  int N, Q; cin >> N >> Q;
  multimap<int, int> append;
  multimap<int, int> remove;

  for (int i = 0; i < N; i++) {
    int s, t, x; cin >> s >> t >> x;
    append.insert(make_pair(s-x, x));
    remove.insert(make_pair(t-x, x));
  }

  multimap<int, int> D;
  for (int i = 0; i < Q; i++) {
    int d; cin >> d;
    D.insert(make_pair(i, d));
  }

  multiset<int> ans;
  int A[Q];
  for (auto it = D.begin(); it != D.end(); ++it) {
    while (!append.empty() && append.begin()->first <= it->second) {
      ans.insert(append.begin()->second);
      append.erase(append.begin());
    }
    while (!remove.empty() && remove.begin()->first <= it->second) {
      ans.erase(ans.find(remove.begin()->second));
      remove.erase(remove.begin());
    }

    if (!ans.empty()) {
      A[it->first] = *ans.begin();
    } else {
      A[it->first] = -1;
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << A[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 30848
N,D=map(int,input().split())
X=[]
for i in range(N):
    X.append(list(map(int,input().split())))
ans=0
import math
for i in range(0,N-1):
    for j in range(i+1,N):
        ans+=math.sqrt(sum((X[i][k]-X[j][k])**2 for k in range(D))).is_integer()
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>

using namespace std;

int main() {
  int a,b,c;
  cin >> a >> b >> c;  
  if(b+c <= a) cout << "0" << endl;
  else cout << c-(a-b) << endl;
}

Measured memory_bytes: 3592
a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0
y = x
x_500 = x // 500

for i in range(int(min([x_500+1, a+1]))):
    x = y - i*500
    x_100 = x // 100
    for j in range(int(min([x_100+1, b+1]))):
        x_50 = x // 50
        if x_50 <= c:
            cnt += 1
            x = x - 100
        else:
            x = x - 100
print(cnt)

Measured memory_bytes: 9148
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // 整数スキャン（複数）
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s;
    cin >> s;
    */

    // n個の文字列スキャン
    /*
    vector<string> slist;
    rep(i,n){
        string s;
        cin >> s;
        slist.push_back(s);
    }
    */

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



    ll ans = 0;
    ans= (n+1-h)*(n+1-w);
    
    cout << ans << endl;
    return 0;
}
 
 


Measured memory_bytes: 256
import java.util.*;
import java.util.Scanner;
class Main {
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.remove(list.indexOf(A));
        list.remove(list.indexOf(B));
        System.out.println(list.get(0));
    }
} 

Measured memory_bytes: 21844
#include<iostream>
#include<stdio.h>
using namespace std;
int main(void) {
	int a;
	int i;
	scanf("%d", &a);
	for (i = 2; i < 10; i++) {
		if (i * 200 <= a && a < (i + 1) * 200) {
			cout << 10 - i;
		}
	}



	return 0;
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD (long long)(1e9+7)
ll GCD(ll a,ll b){
    ll hoge;
    do{
        hoge=a%b;
        a=b;
        b=hoge;
    }while(hoge!=0);
    return a;
}
int main(){
	ll n;
	cin>>n;
	vector<ll>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n-1;i++){
		a[i+1]=GCD(a[i],a[i+1]);
	}
	cout<<a[n-1]<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define v(i) vector<i>
#define FOR(i,a,b) for(i=a;i<b;i++)
#define FORE(i,a,b) for(i=a;i<=b;i++)
#define FORV(i,a,b) for(i=a;i>b;i--)
#define FOREV(i,a,b) for(i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define look(v) for(auto c:v) cout<<c<<" "; cout<<"\n";
#define dfdc int i,j,k,m,n,ct=0;string s;
#define ppl(a,st,end) for(i=st;i<=end;i++)cin>>a[i];
#define fz(a) memset(a,0,sizeof a);
#define dp_1(n) int dp[n];fz(dp);
#define dp_2(m,n) int dp[m][n];fz(dp);
#define arpt(a,s,e) for(i=s;i<=e;i++) cout<<a[i]<<" ";cout<<"\n";
#define tk int t;cin>>t;while(t--)
 
using namespace std;
 
typedef long long int ll;
 
 
int main(){
    fastio
    int h,w,m;
    cin>>h>>w>>m;
    set<pair<int,int>> points;
    map<int,int> r,c;
    int mxr = -1,mxc=-1;
    int rct = 0,cct = 0;
    for(int i=0;i<m;i++){
    	int h,w;
    	cin>>h>>w;
    	points.insert({h,w});
    	r[h]++;
    	if(mxr<r[h]){
    		mxr =r[h];
    		rct=1;
    	}
    	else if(mxr == r[h]){
    		rct++;
    	}
    	c[w]++;
    	if(mxc<c[w]){
    		mxc =c[w];
    		cct=1;
    	}
    	else if(mxc == c[w]){
    		cct++;
    	}
    }
    int cnt=0;
    for(auto it = points.begin();it!=points.end();it++){
    	auto cc = *it;
    	int x = cc.first;
    	int y = cc.second;
    	if(r[x] == mxr && c[y] == mxc)
    		cnt++;
    }
    if(cnt == rct*cct){
    	cout<<mxr+mxc-1<<"\n";
    }
    else{
    	cout<<mxr+mxc<<"\n";	
    }
    return 0;
}

Measured memory_bytes: 45808
#include<stdio.h>
int q[2000000];
void swap(int i, int j){

  int tmp;

  tmp=q[i];
  q[i]=q[j];
  q[j]=tmp;

}

int main(){
  int k,s=0;
  int i,pr,l, r;
  char c[2];
  while(1){
    scanf("%s%d",c,&k);
    if(c[0]=='i'){
      i=s;
      q[i]=k;
      while(i>0 && q[i]>q[pr=(i-1)/2]){
          swap(i,pr);
          i=pr;
        }
        ++s;
    }
    else if(c[1]=='n')break;
    else{
      printf("%d\n",q[0]);

      q[i=0]=q[--s];
      --q[s];
      while((l=i*2+1)<s){
        if((r=l+1)<s && q[r] > q[l])l=r;
        if(q[i]<q[l])swap(i,l);
        i=l;
      }
    }
  }
  return 0;
}

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

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

    int h,m,s;
    h = S / 3600;
    m = (S % 3600) / 60;
    s = (S % 3600) % 60;
    cout << h << ":" << m << ":" << s << endl;

    return 0;
}


Measured memory_bytes: 3084
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 5121000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
}
// ここから編集しろ

vector<pair<int,int> > g[1010000];
void ae(int a,int b,int c,int d,int e,int f,int g0){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		g[100000+e*2].push_back(make_pair(f+700000,g0));
		g[f+700000].push_back(make_pair(100000+e*2+1,0));
		return;
	}
	ae(a,(a+b)/2,c,d,e*2,f,g0);
	ae((a+b)/2+1,b,c,d,e*2+1,f,g0);
}

long long ijk[1010000];
int v[1010000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		int tmp=i+131072;
		while(tmp){
			g[i].push_back(make_pair(tmp*2+100000,0));
			g[tmp*2+1+100000].push_back(make_pair(i,0));
			tmp/=2;
		}
	}
	for(int i=0;i<b;i++){
		int p,q,r;scanf("%d%d%d",&p,&q,&r);
		p--;q--;
		ae(0,131071,p,q,1,i,r);
	}
	priority_queue<pair<long long,int> > Q;
	Q.push(make_pair(0LL,0));
	for(int i=0;i<1010000;i++)ijk[i]=inf;
	ijk[0]=0;
	while(Q.size()){
		long long cost=-Q.top().first;
		int at=Q.top().second;
		Q.pop();
		if(v[at])continue;
		v[at]=1;
		for(int i=0;i<g[at].size();i++){
			int to=g[at][i].first;
			long long toc=cost+g[at][i].second;
			if(v[to]||ijk[to]<=toc){
				continue;
			}
			ijk[to]=toc;
			Q.push(make_pair(-toc,to));
		}
	}
	if(ijk[a-1]==inf)ijk[a-1]=-1;
	printf("%lld\n",ijk[a-1]);
}

Measured memory_bytes: 111848
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] xyz = scanner.nextLine().split(" ", 3);
        int x = Integer.parseInt(xyz[0]);
        int y = Integer.parseInt(xyz[1]);
        int z = Integer.parseInt(xyz[2]);

        System.out.println((x - z) / (y + z));
    }
}


Measured memory_bytes: 23252
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
sumdigits(n) = sum(digits(n))

function main()
    x=parseInt(readline())
    now=100
    ans=0
    while now<x
        now=now+now÷100
        ans+=1
    end
    println(ans)
end
main()

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

N = int(input())
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1],t[i] = t[i],t[i-1]
        if "".join(t).count("AGC") >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in "ACGT":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % (10 ** 9 + 7)
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))


Measured memory_bytes: 3812
#include <stdio.h>

int main(){
	int w,h;
	int i,j,k;

	while(1){
		scanf("%d %d",&h,&w);
		if(h == 0 && w == 0) break;

		for(i = 0;i < w;i++){
			printf("#");
		}
		printf("\n");
		
		for(i = 0;i < h - 2;i++){
			printf("#");
			for(j = 0;j < w - 2;j++){
				printf(".");
			}
			printf("#\n");
		}
		
		if(h - 1 > 0){
			for(i = 0; i < w;i++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

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

using namespace std;

using ll = long long;

bool check(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll s) {
    if (x1 < 0 || x1 > 1000000000) return false;
    if (y1 < 0 || y1 > 1000000000) return false;
    if (x2 < 0 || x2 > 1000000000) return false;
    if (y2 < 0 || y2 > 1000000000) return false;
    if (x3 < 0 || x3 > 1000000000) return false;
    if (y3 < 0 || y3 > 1000000000) return false;
    ll X1 = abs(x2 - x1), Y1 = abs(y2 - y1);
    ll X2 = abs(x3 - x1), Y2 = abs(y3 - y1);
    return abs(X1 * Y2 - X2 * Y1) == s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll s;
    cin >> s;
    ll x1 = 0, y1 = 0;
    ll x2, y2, x3, y3;

    ll ng = 1000000001, ok = 0;
    while (ng - ok > 1) {
        ll mid = (ng + ok) / 2;
        if (mid * mid <= s) ok = mid;
        else ng = mid;
    }
    ll val1 = (ng + 1) * (ng + 1) - s;
    ll val2 = ng * ng - s;
    if (ok * ok == s) {
        x2 = ok;
        y3 = ok;
        x3 = 0;
        y2 = 0;
    } else if (val2 <= 1000000000) {
        x2 = ng;
        y3 = ng;
        x3 = val2;
        y2 = 1;
    } else if (val2 % 2 == 0) {
        x2 = ng;
        y3 = ng;
        x3 = val2 / 2;
        y2 = 2;
    } else if (val1 % 2 == 0) {
        x2 = ng + 1;
        y3 = ng + 1;
        x3 = val1 / 2;
        y2 = 2;
    } else {
        assert(false);
    }
    assert(check(x1, y1, x2, y2, x3, y3, s));
    cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const int DIV = 1e9+7;

ll n,a,b;
vl h;
bool check(ll m){
  vl hc = h;
  int minus;
  rep(i, n) hc[i] -= b*m;
  rep(i, n){
    if(hc[i] <= 0) continue;
    else{
      minus = hc[i]/(a-b);
      if(hc[i]%(a-b) != 0) minus++;
      m -= minus;
    }
  }
  return m >= 0;
}
int main(){
  cin >> n >> a >> b;
  h.resize(n);
  rep(i, n) cin >> h[i];
  sort(all(h));

  ll lb = -1;
  ll ub = INF;
  while(ub - lb > 1){
    ll mid = (ub + lb) / 2;
    if(check(mid)) ub = mid;
    else lb = mid;
  }
  cout << ub << endl;
  return 0;
}


Measured memory_bytes: 1792
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
import sys
input = sys.stdin.readline





S=one_str()
T=one_str()

same_alpha_A = set(list(S))
same_alpha_B = set(list(T))
same_alpha_flg=False

if len(same_alpha_A) and len(same_alpha_A & same_alpha_B):
    same_alpha_flg=True

A_set={}
A_list=[]
for i in list(S):
    if i not in A_set:
        A_set[i]=len(A_set)+1
        
    A_list.append(A_set[i])

B_set={}
B_list=[]
for i in list(T):
    if i not in B_set:
        B_set[i]=len(B_set)+1
    B_list.append(B_set[i])

same_list_flg=True
for a,b in zip(A_list, B_list):
    if a!=b:
        same_list_flg=False
        break

if same_alpha_flg and same_list_flg:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 89296
#include<stdio.h>

int main(){
    int d, n;
    int i;
    int count = 0;
    int max = 0;
    int c[100002];
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d", &c[i]);
    }
    max = c[0];
    c[n] = 2000000000;
    for(i = n-1; i > 0; i--){
        if(c[i-1] - c[i] > 1){
            count = 1;
            break;
        }
        if(c[i-1] - c[i] == 1){
            c[i-1] -= 1;
        }
    }
    if(count == 0){
        printf("Yes\n");
    }else
    {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
using namespace std;

inline int max(int a, int b) { return a > b ? a : b; }
int dp[21];

int main() {
    char s[20] = {};
    scanf("%s", s);
    int len = strlen(s);
    int ans = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C') {
            dp[i] += dp[i-1] + 1;
        }
        ans = max(dp[i], ans);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <iostream>

using namespace std;

typedef struct {
	char suit;
	char value;
} CARD;

void bubble(CARD *c1, int n);
void selection(CARD *c2, int n);
bool isStable(CARD *c1, CARD *c2, int n);
void print(CARD *array, int n);

int main()
{
	CARD c1[100], c2[100];
	int n;
	
	scanf("%d", &n);

	for (int i = 0; i < n; i++){
		cin >> c1[i].suit >> c1[i].value;
	}

	for (int i = 0; i < n; i++){
		c2[i] = c1[i];
	}

	bubble(c1, n);
	selection(c2, n);

	print(c1, n);
	cout << "Stable" << endl; // ???????????????????????????

	print(c2, n);
	if (isStable(c1, c2, n)){
		cout << "Stable" << endl;
	}
	else {
		cout << "Not stable" << endl;
	}

	return (0);
}

void bubble(CARD *c1, int n)
{
	CARD tmp;

	for (int i = 0; i < n; i++){
		for (int j = n - 1; j >= i; j--){
			if (c1[j].value < c1[j - 1].value){
				tmp = c1[j];
				c1[j] = c1[j - 1];
				c1[j - 1] = tmp;
			}
		}
	}
}

void selection(CARD *c2, int n)
{
	CARD tmp;

	for (int i = 0; i < n; i++){
		int minj = i;
		for (int j = i; j < n; j++){
			if (c2[j].value < c2[minj].value){
				minj = j;
			}
		}
		tmp = c2[i];
		c2[i] = c2[minj];
		c2[minj] = tmp;
	}
}

void print(CARD *a, int n)
{
	for (int i = 0; i < n; i++){
		if (i == n - 1){
			cout << a[i].suit << a[i].value << endl;
		}
		else {
			cout << a[i].suit << a[i].value << " ";
		}
	}
}

bool isStable(CARD *c1, CARD *c2, int n)
{
	for (int i = 0; i < n; i++){
		if (c1[i].suit != c2[i].suit){
			return (false);
		}
	}

	return (true);
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long int n; cin >> n;
	long long int ans = n;
	vector<pair<long long int, long long int>> p;
	for(long long int i=1;i*i<=n;i++){
		if(n%i==0){
			ans = min(ans, i+n/i - 2);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

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

typedef vector<P> vp;
typedef vector<vp> matP;

ll fastpow(ll a, ll pw) {
    ll res = 1;
    while (pw) {
        if (pw & 1) res = res * a % MOD;
        a = a * a % MOD;
        pw >>= 1;
    }
    return res;
}

vec Cb(200010,0),Cw(200010,0);
void makeCC(){
    Cb[B] = 1;
    reps(i,B+1,B+W){
        Cb[i] = Cb[i-1];
        (Cb[i] *= i-1)%=MOD;
        (Cb[i] *= fastpow(i-B, MOD-2))%=MOD;
    }
    Cw[W] = 1;
    reps(i,W+1,B+W){
        Cw[i] = Cw[i-1];
        (Cw[i] *= i-1)%=MOD;
        (Cw[i] *= fastpow(i-W, MOD-2))%=MOD;
    }
}

int main() {
    cin>>B>>W;
    mat dp(B+W, vec(3,0));
    makeCC();
    ll inv2 = fastpow(2LL, MOD-2);
    dp[0][0] = 1;
    reps(i,1,B+W){
        ll temp = 1;
        if(i >= B){
            dp[i][2] = dp[i-1][2];
            (dp[i][2] += fastpow(inv2, i) * Cb.at(i))%=MOD;
            ((temp += MOD) -= dp[i][2])%=MOD;
        }
        if(i >= W){
            dp[i][1] = dp[i-1][1];
            (dp[i][1] += fastpow(inv2, i) * Cw.at(i))%=MOD;
            ((temp += MOD) -= dp[i][1])%=MOD;
        }
        dp[i][0] = temp;
    }
    rep(i,B+W){
        ll ans = 0;
        (ans += dp[i][0] * inv2)%=MOD;
        (ans += dp[i][1])%=MOD;
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 16256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k,i;
  scanf("%d%d",&n,&k);
  int ar[n];
  for(i=0;i<n;i++)
    scanf("%d",ar+i);
  sort(ar,ar+n);
  long long sum=0;
  for(i=0;i<k;i++)
    sum+=ar[i];
  printf("%lld\n",sum);
 /*   printf("A\n");
  else
    printf("a\n");*/
}


Measured memory_bytes: 3736
# include <bits/stdc++.h>
using namespace std;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 210;
ll a[N], b[N];
char s[N];
int n, m, t;
bool add(ll x){
	for (int i = 1; i <= m; i++){
		if (x > b[i]) swap(x, b[i]);
		if ((x ^ b[i]) < x) x ^= b[i];
	}
	if (x == 0) return 0;
	b[++m] = x;
	return 1;
}
int main(){
	read(t);
	while (t--){
		read(n); m = 0;
		for (int i = 1; i <= n; i++) read(a[i]);
		scanf("\n%s", s + 1);
		bool flag = true;
		for (int i = n; i >= 1; i--)
			if (add(a[i]) && s[i] == '1')
				flag = false;
		if (flag == false)
			cout << 1 << endl;
			else cout << 0 << endl; 
	} 
    return 0;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
#define lli long long int

using namespace std;

int dfs(int src, std::vector<bool>& visited, 
        std::unordered_map<int,std::vector<int>>& adj_list) 
{
  visited[src] = true;
  int cnt = 1;
  for (auto neighbor : adj_list[src]) {
    if (!visited[neighbor]) {
      cnt += dfs(neighbor, visited, adj_list);
    }    
  }
  return cnt;
}

int main() {
  int n, m;
  std::cin >> n >> m;
  std::unordered_map<int,std::vector<int>> adj_list{};
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
  }
  int max_size = 0;
  std::vector<bool> visited(n+1, false);
  for (int i = 1; i <= n; ++i) {
    if (!visited[i]) {
      int size = dfs(i, visited, adj_list);
      max_size = max(size, max_size);
    }
  }
  std::cout << max_size << std::endl;
}

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

using namespace std;

short A,B,K;
int ans[100];

int main(){
  cin >> A >> B >> K;
  int m  = max(A, B);
  int count = 0;
  for (int i = 1; i <= m; i++){
    if (A % i == 0 && B % i ==0){
      ans[count] = i;
      count++;
    }
  }
  sort(ans, ans + 100,greater<int>());
  cout << ans[K - 1];
  return 0;
}

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

int main() {
	int n,d,ans=0;
	
	cin >> n >> d;
	
	vector < int >v[n];
	
	for(int i=0;i<n;i++)
	{
		for(int a,j=0;j<d;j++){
			cin >>a;
			v[i].push_back(a);
		}
	}
	
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int64_t sum=0,root=0;
			for(int k=0;k<d;k++)
			{
			 sum+=abs(v[i][k]-v[j][k])*abs(v[i][k]-v[j][k]);
			}
			root=sqrt(sum);
			if(sum==root*root) ans++;
		}
	}
	
	cout << ans;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#include<iomanip>

using namespace std;
int main(void){
 int A,B,K;
 int ans=0;
 cin>>A>>B>>K;

 for(int i=min(A,B); i>=1; i--){
  if(A%i==0 && B%i==0)ans++;
  if(ans==K){
   cout<<i<<endl; 
   return 0;
  }
 }
 return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (__typeof(a) i = (a); i < (b); ++i)
#define iter(it, c) \
  for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = ~(1 << 31);

#define sc second
#define fs first
#define pb push_back

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T>
T smod(T a, T b) {
  return (a % b + b) % b;
}
// vim: cc=60 ts=2 sts=2 sw=2:

string s, t;

int memo[3010][3010];
int dp(int at1, int at2) {
  if (at1 == -1 || at2 == -1) return 0;
  if (memo[at1][at2] != -1) return memo[at1][at2];
  int bst = 0;
  if (s[at1] == t[at2])
    bst = max(bst, dp(at1 - 1, at2 - 1) + 1);
  else {
    bst = max(bst, dp(at1 - 1, at2));
    bst = max(bst, dp(at1, at2 - 1));
  }

  return memo[at1][at2] = bst;
}

string res = "";
void rec(int at1, int at2) {
  if (at1 == -1 || at2 == -1) return;
  int bst = 0;
  if (s[at1] == t[at2]) {
    bst = max(bst, dp(at1 - 1, at2 - 1) + 1);
    res += s[at1];
    rec(at1 - 1, at2 - 1);
  } else {
    bst = max(bst, dp(at1 - 1, at2));
    bst = max(bst, dp(at1, at2 - 1));
    if (bst == dp(at1 - 1, at2))
      rec(at1 - 1, at2);
    else
      rec(at1, at2 - 1);
  }
}

int main() {
  // code
  memset(memo, -1, sizeof(memo));

  cin >> s >> t;

  rec(s.size() - 1, t.size() - 1);

  reverse(res.begin(), res.end());

  cout << res << endl;

  // codend
}


Measured memory_bytes: 35968
use strict;
use warnings;
use utf8;
my($n,$m)=split/ /,<>;
my@a=<>;
my$c=0;
my@dp=(1,(0)x$n);
my$mod=1000000007;
for(my$i=1;$i<=$n;$i++){
 if($c<@a&&$i==$a[$c]){
  $dp[$i]=0;
  $c++;
 }elsif($i==1){
  $dp[$i]=1;
 }else{
  $dp[$i]=$dp[$i-2]+$dp[$i-1];
  $dp[$i]%=$mod;
 }
}
print$dp[$n];


Measured memory_bytes: 23296
/******************************\
*  Everyone has a different way of thinking, so God Created us
Hope You Respect My Way..,Thank You ):  *
*                            *
*   Created by : Murad   *
\******************************/
//std::transform(s1.begin(), s1.end(), s1.begin(),::tolower);
#include<bits/stdc++.h>
using namespace std;
#define pi 3.1415926536
#define forn(i,a,b)for(int i=a;i<b;i++)
#define LL long long
#define MP make_pair
#define ff first
#define ss second
#define INF 2147483647
#define _INF -2147483647
#define pq priority_queue
#define MM multimap
#define PB push_back
#define ipair pair<int,int>
#define lpair pair<LL,LL>
#define MAXN 100004
#define El3zba ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define modd 1000000007
LL MMIN(LL a, LL b)
{
	if (a <= b)
		return a;
	else
		return b;
}
LL MMAX(LL a, LL b) {
	if (a >= b)
		return a;
	else
		return b;
}
LL gcd(LL a, LL b) {
	LL c;
	while (a != 0) {
		c = a;
		a = b % a;
		b = c;
	}
	return b;
}
LL f(LL a, LL mul)
{
	return a / mul;
}
int main()
{
	El3zba;
	LL A, B, C, D;
	cin >> A >> B >> C >> D;
	LL lcm = C*D / gcd(C, D);
	LL range = B - A + 1;
	LL divByc = f(B, C) - f(A - 1, C);
	LL divByd = f(B, D) - f(A - 1, D);
	LL divBylcm = f(B, lcm) - f(A - 1, lcm);
	cout <<range-(divByc+divByd-divBylcm) << endl;
	return 0;
}

Measured memory_bytes: 256
//url:
//problem name: Brick Break

#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    int N,K; cin >> N >> K;
    if(N < K) cout << 1 << endl;
    else if(N%K == 0) cout << 0 << endl;
    else cout << 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int a[101][101]={};
int u, k, s;
int main() 
{
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> u >> k;
		for(int j=0; j<k; j++)
		{
			cin >> s;
			a[u][s]=1;
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cout << a[i][j] << (j==n ? '\n' : ' ');
		}
	}
	return 0;
}

Measured memory_bytes: 3132
#問題D
#これだとタイムアウト
import numpy as np
import warnings
warnings.filterwarnings('ignore')

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])



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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int H,W,h,w; cin>>H>>W>>h>>w;
	cout<<(H-h)*(W-w)<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
int main(){
long long int n, m,a,b,ans=0,count=1;
vector<int> l,r;
cin>>n>>m;
while(1){
ans++;
count*=m;
if(n<count)break;
}
cout<<ans<<endl;
return 0;
} 

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

using namespace std;

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

    string s;
    cin>>s;

    int x=s.find("YAKI");
    if(x==0)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 256
/// Updated! https://www.youtube.com/watch?v=U07_n9xGIlM
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define dbug prllf("I am here\n");
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll maxn = 2e5+100;

const ll inf = 2e9;
ll ans = 0;
unordered_map < ll , ll > bit;
vector < pair < ll , ll > > arr;
ll n , d , a;

void update(ll ind , ll val){
    while(ind < inf){bit[ind] += val ; ind += (ind & (-ind));}
}
ll query(ll ind , ll sum = 0){
    while(ind > 0){sum += bit[ind] ; ind -= (ind & (-ind));}
    return sum;
}


int main()
{
    fast;
    cin >> n >> d >> a;
    for(ll i = 0; i<n; i++){
        ll c , d ; cin >> c >> d;
        arr.push_back({c,d});
    }
    sort(arr.begin(),arr.end());
    for(ll i = 0; i<n; i++){
        ll pnt , val;
        pnt = arr[i].first , val = arr[i].second;
        ll get = query(pnt);

        if(get >= val)continue;
        ll ab = abs(val-get);
        ll now = (ab + a-1)/a;
        ll ad = now*a;
        ans += now;
        update(pnt,ad);
        update(pnt+2*d+1,-ad);
    }
    cout << ans << endl;
    return 0;
}
/*



*/



Measured memory_bytes: 121800
#include"bits/stdc++.h"
using namespace std;
int main(){
	string x("abcdefghijklmnopqrstuvwxyz");
	string y;
	cin>>y;
	set<char> z;
	for(auto i:y)
		z.insert(i);
	string ans("None"),d;
	for(auto i:x){
		if(z.find(i)==z.end()){
			ans=(d+i);
			break;
		}
	}
	cout<<ans;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,*b;
  cin>>a;
  b = (int *)malloc(sizeof(int)*(a+1));

  for(int i=1;i<=a;i++)
    cin>>b[i];
 
  for(int i=1;i<=a;i++){
    cout<<"node "<<i<<": key = "<<b[i]<<", ";
    if(i!=1) cout<<"parent key = "<<b[i/2]<<", ";
    if(i*2<=a) cout<<"left key = "<<b[i*2]<<", ";
    if((i*2+1)<=a) cout<<"right key = "<<b[i*2+1]<<", ";
    cout<<endl;
  }
 
  return 0;
}
 

Measured memory_bytes: 1188
{-# LANGUAGE BangPatterns #-}

module Main where

import Data.Char
import Data.List
import Control.Monad
import Control.Monad.ST
import Control.Monad.State.Strict
import Data.Array.IO
import Data.Array.Unboxed
import Control.Applicative
import Text.Printf
import Debug.Trace


readInt :: IO Int
readInt = read <$> (input `seq` input)
    where input = do
            !c <- getChar
            if isDigit c || c == '-'
                then (c :) <$> input
                else return []

prints :: Show a => [a] -> IO ()
prints as = putStrLn $ concat $ intersperse " " $ map show as

main = do
    [r, c] <- replicateM 2 readInt
    s <- newArray (1,c) 0 :: IO (IOUArray Int Int)
    forM_ [1..r] $ \_ ->
        let g n | n == c + 1 = return 0
                | otherwise = do
                    x <- readInt
                    putStr $ show x ++ " "
                    writeArray s n . (+x) =<< (readArray s n)
                    (+x) <$> g (n+1)
        in print =<< g 1
    let g n | n == c + 1 = return 0
            | otherwise = do
                t <- readArray s n
                putStr $ show t ++ " "
                (+t) <$> g (n+1)
        in print =<< g 1


Measured memory_bytes: 4240
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String s = scan.next();
        String t = scan.next();
        for(int i = 0; i < n; i++){
            System.out.print(s.charAt(i));
            System.out.print(t.charAt(i));
        }
    }
}

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

int main(){
  long long N;
  cin >> N;
  vector<long long> X(N);
  for(int i=0;i<N;i++) cin >> X[i];
  
  long long ans=1001001001;
  for(int i=1;i<=100;i++){
    long long sum=0;
    for(int j=0;j<N;j++){
      sum += (i-X[j])*(i-X[j]);
    }
    ans = min(ans,sum);
  }
  
  cout << ans << endl;
  return 0;
}


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

#define rep(i,N) for(int (i)=0;(i)<(N);(i)++)
#define repi(i,j,N) for(int (i)=(j);(i)<(N);(i)++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define ll long long
#define numberofdigits(x) floor(log10(x)) + 1


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;

const char nl = '\n';

void solve() {
    string s,t;
    cin>>s>>t;

    int n = s.length(), m = t.length();
    int ans = m;
    for(int i=0;i+m<=n;i++) {
        int c=0;
        for(int j=0;j<m;j++) {
            c += s[i+j] != t[j];
        }
        ans = min(ans, c);
    }

    cout<<ans<<nl;

}

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

//    int t;cin>>t;
//    while(t--) {
	solve();
//    }
    return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		long ary[] = new long[k];
		for(int i=0; i<k; i++) {
			ary[i] = sc.nextLong();
		}
		sc.close();
		long l = 2L, r = 2L;
		
		for(int i=k-1; i>=0; i--) {
			l = (long)Math.ceil((double)l/ary[i]) * ary[i];
			r = (long)Math.floor((double)r/ary[i]) * ary[i] + ary[i] - 1;
			if(!exist(l,r,ary[i])) {
				System.out.println(-1);
				return;
			}
		}
		
		System.out.println(l+" "+r);
	}
	
	boolean exist(long l, long r, long a) {
		for(long i=l; i<=r; i++) {
			if(i%a == 0) {
				return true;
			}
		}
		return false;
	}
}

Measured memory_bytes: 52020
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String...args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int q = in.nextInt();
        int[] poinst = new int[n];
        for (int i = 0; i < poinst.length; i++){
            poinst[i] = k - q;
        }
        for(int i = 0; i < q ; i++) {
            int a = in.nextInt();
            poinst[a - 1] = poinst[a - 1] + 1;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < poinst.length; i++) {
            if(poinst[i] > 0) {
                sb.append("Yes" + System.lineSeparator());
            } else {
                sb.append("No" + System.lineSeparator());
            }
        }
        System.out.print(sb.toString());
    }
}


Measured memory_bytes: 58236
int main()
{
    char str1[4]={'\0'};
    char str2[4]={'\0'};
    scanf("%s %s",str1,str2);
    int flag=0;
    for(int i=0;i<3;i++)
    {
        if(str1[i]!=str2[2-i])
        {
            flag=1;
            break;
        }
    }
    if(flag==0)printf("YES");
    else printf("NO");
    return 0;
}

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

typedef long long ll;

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

        vector<pair<ll,ll>> ab(n);
        for(int i=0; i<n; i++) cin >> ab[i].first >> ab[i].second;
        sort(ab.begin(), ab.end());

        long long ans = 0;
        for(int i=0; i<n; i++){
                if(m <= ab[i].second){
                        ans += ab[i].first * m;
                        break;
                }
                else{
                        ans += ab[i].first * ab[i].second;
                        m -= ab[i].second;
                }
        }

        cout << ans << endl;
}

Measured memory_bytes: 4756
local mod = 998244353
local mfl = math.floor
local function bmul(x, y)
  local x0, y0 = x % 31596, y % 31596
  local x1, y1 = mfl(x / 31596), mfl(y / 31596)
  return (x1 * y1 * 62863 + (x1 * y0 + x0 * y1) * 31596 + x0 * y0) % mod
end

local function badd(x, y)
  return (x + y) % mod
end

local function bsub(x, y)
  return x < y and x - y + mod or x - y
end

local s = io.read()
s, k = s:match("(%d+) (%d+)")
k = tonumber(k)
s = s:reverse()
local n = #s
local t = {}
local total_one = 0
for i = 1, n do
  if s:byte(i) == 49 then --1
    total_one = total_one + 1
  end
end

do
  local last_zero_pos = false
  for i = 1, n do
    if last_zero_pos then
      if s:byte(i) == 48 then
        table.insert(t, i - last_zero_pos - 1)
        last_zero_pos = i
      end
    else
      if s:byte(i) == 49 then
        last_zero_pos = i - 1
      end
    end
  end
  if last_zero_pos then
    table.insert(t, n - last_zero_pos)
  end
end

k = math.min(k, total_one)
local cur_one_cnt = 0
local dp1, dp2 = {}, {}
for i = 1, k + 1 do
  dp1[i] = {0}
  dp2[i] = {}
end
dp1[1][1] = 1
for i = 1, #t do
  local src = i % 2 == 1 and dp1 or dp2
  local dst = i % 2 == 1 and dp2 or dp1
  local ti = t[i]
  -- initialize
  for j = 1, k + 1 do
    local dj = dst[j]
    for q = 0, cur_one_cnt + ti do
      dj[q + 1] = 0
    end
  end
  -- copy
  for j = 1, k + 1 do
    local dj = dst[j]
    local sj = src[j]
    for q = 0, cur_one_cnt do
      dj[q + ti + 1] = sj[q + 1]
    end
  end
  -- cumulate
  for j = 1, k + 1 do
    local dj = dst[j]
    for q = 1, cur_one_cnt + ti do
      dj[q + 1] = badd(dj[q + 1], dj[q])
    end
  end
  -- copy add
  for j = 1, ti do
    for ik = 1, k + 1 do
      if k + 1 < ik + j then break end
      local dikj = dst[ik + j]
      local sik = src[ik]
      for q = 0, cur_one_cnt do
        dikj[q + ti - j + 1] = badd(dikj[q + ti - j + 1], sik[q + 1])
      end
    end
  end
  -- print("--- " .. i .. " ---")
  -- for ik = 1, k + 1 do
  --   print(table.concat(dst[ik], " "))
  -- end
  cur_one_cnt = cur_one_cnt + ti
end
local ret = 0
local tbl = #t % 2 == 1 and dp2 or dp1
for ik = 1, k + 1 do
  ret = badd(ret, tbl[ik][total_one + 1])
end
print(ret)


Measured memory_bytes: 4216