akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void)
{
    int n, count;
    char feet, buf[3], next;

    while(scanf("%d", &n), n)
    {
        count = feet = 0, next = 3;

        while(n--)
        {
            scanf("%s", buf);

            switch(buf[0] + buf[1])
            {
              case 225: feet |= 2; break; /* lu */
              case 208: feet &= 1; break; /* ld */
              case 231: feet |= 1; break; /* ru */
              case 214: feet &= 2; break; /* rd */
            }

            if(feet == next) next ^= 3, count++;
        }

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

    return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <list>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <fstream>
#include <sstream>
#include <unordered_map>
#include <ctime>
#include <assert.h>
using namespace std;

#define ATCODER

#ifdef ATCODER
#include <atcoder/all>
#endif

const unsigned long long MOD = (unsigned long long)(1e9 + 7);

#define FROM_0(i, n) for(int i = 0; i < (n); i++)
#define FROM_S(i, s, e) for(int i = (s); i < (e); i++)
#define ITER_BEGIN_END(iter, vec) for(auto iter = vec.begin(); iter != vec.end(); iter++)

string board[51];
int emptyIdx[51][51];
bool visited[51][51];

struct Item
{
    Item(int xx, int yy, int ss) : x(xx), y(yy), step(ss) {}
    int x;
    int y;
    int step;
};

int main()
{
    int m, n;
    cin >> n >> m;
    vector<pair<int, int>> chess;
    int emptyCount = 0;
    FROM_0(i, n)
    {
        cin >> board[i];
        FROM_0(j, m)
        {
            emptyIdx[i][j] = -1;
            if (board[i][j] == 'o')
                chess.push_back(make_pair(j, i));
            if (board[i][j] == 'o' || board[i][j] == '.')
            {
                emptyIdx[i][j] = emptyCount;
                emptyCount++;
            }
        }
    }

    // graph
    atcoder::mcf_graph<int, int> graph(chess.size() + emptyCount + 2);
    FROM_0(idx, chess.size())
    {
        const auto & c = chess[idx];
        list<Item> buffer;
        buffer.push_back(Item(c.first, c.second, 0));
        FROM_0(i, n)
        {
            FROM_0(j, m)
                visited[i][j] = false;
        }
        while (!buffer.empty())
        {
            int x = buffer.front().x, y = buffer.front().y, step = buffer.front().step;
            buffer.pop_front();
            if (visited[y][x])
                continue;
            visited[y][x] = true;
            //cout << idx << ' ' << chess.size() + emptyIdx[y][x] << ' ' << -step << endl;
            graph.add_edge(idx, chess.size() + emptyIdx[y][x], 1, 200 - step);
            if (x + 1 < m && board[y][x + 1] != '#' && !visited[y][x + 1])
                buffer.push_back(Item(x + 1, y, step + 1));
            if (y + 1 < n && board[y + 1][x] != '#' && !visited[y + 1][x])
                buffer.push_back(Item(x, y + 1, step + 1));
        }
    }
    // max flow
    int start = chess.size() + emptyCount;
    int end = start + 1;
    FROM_0(i, chess.size())
    {
        //cout << i << ' ' << start << endl;
        graph.add_edge(start, i, 1, 0);
    }
    FROM_0(i, emptyCount)
    {
        //cout << i + chess.size() << ' ' << end << endl;
        graph.add_edge(i + chess.size(), end, 1, 0);
    }
    auto ret = graph.flow(start, end);
    cout << 200 * chess.size() - ret.second << endl;

    return 0;
}

Measured memory_bytes: 7048
// import std = require('tstl')

{
  type Print = void | string | number | string[] | number[]
  let outs: Print[] = []

  const main = (): Print => {
    const r = _io()
    const [N, K] = r.nn()
    const p = r.nn()

    p.sort((a, b) => a - b)

    let sum = 0

    for (let i = 0; i < K; i++) {
      sum += p[i]
    }

    return sum
  }

  const _io = (i = 0) => {
    const str = require('fs').readFileSync('/dev/stdin', 'utf8')
    const lines = str.trim().split('\n')
    const s = () => lines[i++] || ''
    const n = () => Number(s())

    const mn = (v: string[]) => v.map(Number)
    const sp = (v: string) => v.split(' ')

    const ss = () => sp(s())
    const nn = () => mn(ss())
    const nls = () => mn(lines.slice(i))
    const nnls = () => lines.slice(i).map((v) => mn(sp(v)))

    return { lines, s, n, ss, nn, nls, nnls }
  }

  outs.push(main())

  console.log(
    outs
      .map((line) => (typeof line === 'object' ? line.join(' ') : String(line)))
      .join('\n')
  )
}


Measured memory_bytes: 29744
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

using ll = long long;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int a[1 + nmax], b[1 + nmax];

int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> a[i];
  for(int i = 1;i <= n; i++)
    cin >> b[i];

  ll sum = 0;
  for(int i = 1;i <= n; i++)
    sum += b[i] - a[i];

  ll op1 = 0, op2 = 0;
  for(int i = 1;i <= n; i++){
    if(b[i] < a[i])
      op1 += a[i] - b[i];
    else if(a[i] < b[i]){
      int dif = b[i] - a[i];
      if(dif % 2 == 1)
        op1++;
      op2 += (dif + 1) / 2;
    }
  }

  if(op1 <= sum && op2 <= sum)
    cout << "Yes\n";
  else
    cout << "No\n";
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1000000000000000000;
signed main(){
  int N,M;
  cin>>N>>M;
  vector<pair<pair<int,int>,int>> A(M);
  vector<vector<int>> D(N);
  for(int i=0;i<M;i++){
    int a,b,c;
    cin>>a>>b>>c;
    A[i]=make_pair(make_pair(a-1,b-1),c);
    D[a-1].push_back(b-1);
  }
  vector<int> B(N,-INF);
  B[0]=0;
  vector<bool> C(N,false);
  queue<int> Q;
  for(int i=0;i<=N;i++){
    bool b=true;
    for(auto p:A){
      if(B[p.first.first]!=-INF && B[p.first.first]+p.second>B[p.first.second]){
        b=false;
        B[p.first.second]=B[p.first.first]+p.second;
        if(i==N-1){
          C[p.first.second]=true;
          Q.push(p.first.second);
        }
      }
    }
    if(b)break;
  }
  while(!Q.empty()){
    int I=Q.front();
    Q.pop();
    for(int i:D[I])
      if(!C[i]){
        C[i]=true;
        Q.push(i);
      }
  }
  if(C[N-1])puts("inf");
  else cout<<B[N-1]<<endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;

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

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

    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);

    long long int res = 0;

    for(int i=n-1;i>=0;--i){

        int f=-1,l=n;
        while(l-f>1){
            int m=(l+f)/2;
            if(a[m]>=b[i]){
                l=m;
            } else f=m;
        }
        int t = f+1;
        f=-1,l=n;
        while(l-f>1){
            int m=(l+f)/2;
            if(c[m]>b[i]){
                l=m;
            } else f=m;
        }
        res += (long long )(t)*(long long)(n-l);
    }
    cout << res;

}

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

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

struct StronglyConnectedComponents{
  vector<vector<int>> g, rev_g;
  vector<int> visited, order, root;
  StronglyConnectedComponents(vector<vector<int>> &g):g(g){
    int n=g.size();
    rev_g.resize(n);
    visited.resize(n, false);
    root.resize(n, -1);
    rep(i, n)for(int j: g[i]){
      rev_g[j].push_back(i);
    }
  }
  void dfs(int i){
    if(visited[i]) return;
    visited[i]=true;
    for(int j: g[i])if(visited[j]==false) dfs(j);
    order.push_back(i);
  }
  void rev_dfs(int i, int itr){
    if(root[i]>=0) return;
    root[i]=itr;
    for(int j: rev_g[i])if(root[j]<0) rev_dfs(j, itr);
  }
  void compress(){
    rep(i, g.size())if(visited[i]==false) dfs(i);
    assert(order.size()==g.size());
    reverse(order.begin(), order.end());
    int itr=0;
    for(int i: order)if(root[i]<0) rev_dfs(i, itr++);
    rep(i, g.size()) assert(root[i]>=0);
  }
};

int main(){

  int n, m; cin>> n>> m;
  vector<vector<int>> g(n);
  rep(_, m){
    int a, b; cin>> a>> b;
    g[a].push_back(b);
  }

  StronglyConnectedComponents scc(g);
  scc.compress();

  int q; cin>> q;
  while(q--){
    int a, b; cin>> a>> b;
    if(scc.root[a]==scc.root[b]) cout<< 1<< endl;
    else cout<< 0<< endl;
  }

  return 0;
}


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

using namespace std;
char str[300010];
int lft[300010];
int rght[300010];
int main()
{
   char c;
   int len;
   scanf("%d",&len);
   getchar();
   int tot1=0,tot2=0;
   memset(lft,0,sizeof(lft));
   memset(rght,0,sizeof(rght));
    for(int i=0;i<len;++i){
        scanf("%c",&c);
        str[i]=c;
        lft[i]+=tot1;
        if(c=='W')
        {
            tot1++;
        }
    }
     for(int i=len-1;i>=0;--i){
        rght[i]+=tot2;
        if(str[i]=='E')
        {
            tot2++;
        }
    }
    int mn=min(rght[0],lft[len-1]);
    for(int i=1;i<len-1;++i)
    {
        mn=min(mn,lft[i]+rght[i]);
      //  cout<<mn<<endl;
    }
    cout<<mn<<endl;
    return 0;
}

Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>

using namespace std;

#define ll long long

int main(void){
    int h, w, k;
    cin >> h >> w >> k;
    vector<vector<char>> c(h, vector<char>(w));

    for(int i = 0;i < h;++i){
        for(int j = 0;j < w;++j){
            cin >> c[i][j];
        }
    }

    int ans = 0;
    for(int i = 0;i < (int)pow(2,h);++i){
        for(int j = 0;j < (int)pow(2,w);++j){

            int b_num = 0;
            for(int a = 0;a < h;++a){
                for(int b = 0;b < w;++b){
                    if((i & (1<<a)) == 0 && (j & (1<<b)) == 0 && c[a][b] == '#'){
                        b_num += 1;
                    }
                }
            }
            // cout << b_num << endl;

            if(b_num == k){
                ans += 1;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4104
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int main(){
    int N;
    cin >> N;
    ll A[N];
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    sort(A,A+N);
    ll min = 1e9+1;
    int index = 0;
    ll d = A[index];
    while(true){
        ll min_d = 1e9;
        int count=0;
        for(int i=0;i<N;i++){
            ll amari = A[i] % d;
            if(amari == 1){
                cout << 1 << endl;
                return 0;
            }
            else if(amari != 0){
                if(amari < min_d) min_d = amari;
                count++;
            }
        }
        if(count == 0){
            cout << d <<endl;
            return 0;
        }
        d = min_d;
    }
        
}

Measured memory_bytes: 1024
import Data.Array
import Data.List

foldl_trace::(b->a->b)->b->[a]->[b]
foldl_trace f seed []     = []
foldl_trace f seed (x:xs) = (f seed x):(foldl_trace f (f seed x) xs)


sum_trace::[Int]->[Int]
sum_trace ls = 0:(foldl_trace (+) 0 ls)

still_n::[Int]->Array Int Int
still_n ls = listArray (0,length ls) (sum_trace ls)

solver::String->Int
solver dat = let n = length dat in
             let ar = still_n (map (\ c -> if c == '#' then 1 else 0) dat) in
             minimum [ar!(k-1) + (n - (k-1) - (ar!n) + ar!(k-1)) |k<-[1..(n+1)]]

main::IO()
main=do
  _<-getLine
  print.solver=<<getLine

Measured memory_bytes: 47484
import java.util.Scanner;

class Main{

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

        int N = scan.nextInt();
        int T = 0;
        int X = 0;
        int Y = 0;
        for(int i=0;i<N;++i){
            int t=scan.nextInt();
            int x=scan.nextInt();
            int y=scan.nextInt();
            int dis =Math.abs(X-x) + Math.abs(Y-y);
            if(dis <= t-T && (t-T-dis)%2==0){

            }else{
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");

    }
}

Measured memory_bytes: 87024
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	X := make([]int, M)
	for i := 0; i < M; i++ {
		fmt.Scan(&X[i])
	}
	sort.Ints(X)

	d := make([]int, M-1)
	for i := 0; i < M-1; i++ {
		d[i] = X[i+1] - X[i]
	}
	sort.Ints(d)

	ans := 0
	for i := 0; i < len(d)-(N-1); i++ {
		ans += d[i]
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class T> inline int isPrime_L(T n){
  T i;
  if(n<=1){
    return 0;
  }
  if(n<=3){
    return 1;
  }
  if(n%2==0){
    return 0;
  }
  for(i=3;i*i<=n;i+=2){
    if(n%i==0){
      return 0;
    }
  }
  return 1;
}
int main(){
  int X;
  rd(X);
  while(!isPrime_L(X)){
    X++;
  }
  wt_L(X);
  wt_L('\n');
  return 0;
}
// cLay varsion 20191229-1 [beta]

// --- original code ---
// {
//   int X;
//   rd(X);
//   while(!isPrime(X)) X++;
//   wt(X);
// }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
int main() {
	int n;
	cin >> n;
	vector<P<int>> a(n);
	rep(i, n) {
		cin >> a[i].first >> a[i].second;
	}
	int ans = n;
	rep(i, n) {
		rep(j, n) {
			if (i == j) continue;
			P<int> d = { a[i].first - a[j].first,a[i].second - a[j].second };
			int cnt = 0;
			rep(k, n) {
				rep(l, n) {
					if (k == l) continue;
					P<int> e = { a[k].first - a[l].first,a[k].second - a[l].second };
					if (d == e) cnt++;
				}
			}
			chmin(ans, n - cnt);
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
	int n, mas = 0, mas1 = 0;
	cin >> n;
	vector <int> arr(3,0), dp(3,0), dp1(3,0);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			cin >> arr[j];
			if(i == 0)
				dp[j] = arr[j];
		}
//		for(int j = 0; j < 3; j++)
//		{
//			for(int k = 0; k < 3; k++)
//			{
//				if(j != k)
//					dp1[k] = max(dp1[k], dp[j] + arr[k]);
//			}
//		}
//		for(int k = 0; k < 3; k++) cout << "dp = " << dp1[k] << " ";
//		cout<<"\n";
//		dp = dp1;
		if(i > 0)
		{
			for(int j = 0; j < 3; j++)
			{
				int mas = 0;
				for(int k = 0; k < 3; k++)
				{
					if(j != k)
						mas = max(mas, dp[k]);
				}
				dp1[j] = arr[j] + mas;
			}
			dp = dp1;
		}
	}
	for(int i = 0; i < 3; i++) mas1 = max(mas1, dp[i]);
	cout << mas1 << "\n";
}


Measured memory_bytes: 256
sys={}
sys['S']=[]
sys['H']=[]
sys['C']=[]
sys['D']=[]
s=[]
h=[]
c=[]
d=[]
for i in range(input()):
    x=raw_input().split()
    if x[0]=='S':
        sys['S'].append(int(x[1]))
    elif x[0]=='H':
        sys['H'].append(int(x[1]))
    elif x[0]=='C':
        sys['C'].append(int(x[1]))
    elif x[0]=='D':
        sys['D'].append(int(x[1]))

for i in range(1,14):
    if i not in sys['S']:
        s.append(str(i))
    if i not in sys['H']:
        h.append(str(i))
    if i not in sys['C']:
        c.append(str(i))
    if i not in sys['D']:
        d.append(str(i))
for w in s:
    print 'S '+w
for w in h:
    print 'H '+w
for w in c:
    print 'C '+w
for w in d:
    print 'D '+w

Measured memory_bytes: 4696
import numpy as np

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = np.zeros([H * W + 1]).astype(np.int)
for i in range(H * W, 0, -1):
    if i + D > H * W:
        scores[i] = 0
    else:
        x, y = stage[i]
        ox, oy = stage[i + D]
        scores[i] = scores[i + D] + abs(x - ox) + abs(y - oy)

for i in range(Q):
    L, R = tests[i]
    print(scores[L] - scores[R])




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

int main() {
    int n, k, ans = 0; cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int h; cin >> h;
        if (h >= k) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#初期定義
global result
global s_list
result = 0

#アルゴリズム：ソート
def merge(left, mid, right):
    global result
    
    n1 = mid - left
    n2 = right - mid
    inf = 10**9
    L_list = s_list[left: mid] + [inf]
    R_list = s_list[mid: right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        result += 1
        if L_list[i] <= R_list[j]:
            s_list[k] = L_list[i]
            i += 1
        else:
            s_list[k] = R_list[j]
            j += 1

#アルゴリズム：マージソート
def mergeSort(left, right):
    if (left + 1) < right:
        mid = (left + right) // 2
        mergeSort(left, mid)
        mergeSort(mid, right)
        merge(left, mid, right)

#初期値
n = int(input())
s_list = list(map(int, input().split()))

#処理の実行
mergeSort(0, n)

#結果の表示
print(" ".join(map(str, s_list)))
print(result)


Measured memory_bytes: 66580
#include<stdio.h>
#include<stdlib.h>

int main(void)
{
  int n;
  double a[110];
  scanf("%d",&n);
  double sum=0;
  for(int i=0;i<n;i++){
    scanf("%lf",&a[i]);
    sum+=a[i];
  }

  sum;
  //printf("%lf\n",sum);
  int min_num=0;
  double min=abs(n*a[0]-sum);
  for(int i=1;i<n;i++){
    double tmp=abs(n*a[i]-sum);
    if(tmp<min){
      min=tmp;
      min_num=i;
    }
  }
  printf("%d\n",min_num);
  return 0;
}


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

int main()
{
  int n,k;
  cin>>n>>k;
  int num=1;
  int min;
  for(int i=0; i<n+1; i++){//iをAの回数とする。
    
    num=std::pow(2,i);
    num+=k*(n-i);


    if(i==0) min=num;
    
    else{
      if(num<min) min=num;

      else{}
    }

  }
   
  cout<<min<<endl;


}


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

ll get_sq(ll x) {
	ll lb = 0, ub = 1e9;
	while (ub - lb > 1) {
		ll m = (lb + ub) / 2;
		(x <= m * m ? ub : lb) = m;
	}
	return ub;
}

int main()
{
	ll S;
	cin >> S;
	ll sq = get_sq(S);
	ll x = S / sq;
	assert(sq >= 1 && x >= 1);
	if (sq * x == S) {
		ll X1 = x, Y1 = 0;
		ll X2 = x, Y2 = sq;
		ll X3 = 0, Y3 = 0;
		cout << X1 << ' ' << Y1 << ' ' << X2 << ' ' << Y2 << ' ' << X3 << ' ' << Y3 << endl;
		return 0;
	}
	ll X1 = x, Y1 = 0;
	ll X2 = x + 1, Y2 = sq;
	ll X3 = 0, Y3 = S - x * sq;
	cout << X1 << ' ' << Y1 << ' ' << X2 << ' ' << Y2 << ' ' << X3 << ' ' << Y3 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int main(int argc, char* argv[])
{
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) {
    cin >> a[i];
  }
  int ans = INF;
  for (int i = MIN(a); i <= MAX(a); i++) {
    int tmp = 0;
    rep(j, n) {
      tmp += pow((i - a[j]), 2);
    }
    chmin(ans, tmp);
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

double zero(double d) {
    return d < EPS ? 0.0 : d;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, a.size()) os << (i ? " " : "") << a[i];
    return os << ']';
}

// to avoid error on mingw
string toString(int i) {
    stringstream ss;
    ss << i;
    return ss.str();
}

const int MOD = 1000000007;
// a^k
ll fpow(ll a, ll k, int M) {
    ll res = 1ll;
    ll x = a;
    while (k != 0) {
        if ((k & 1) == 1)
            res = (res * x) % M;
        x = (x * x) % M;
        k >>= 1;
    }
    return res;
}

int gcd(int a, int b) {
    if(a == 0)
        return 1;
    if(b == 0)
        return a;
    return gcd(b, a%b);
}
int lcm(int a, int b) {
    return a / gcd(a,b) * b;
}

int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(8);
    ios_base::sync_with_stdio(false);

    int a,b;
    while(cin>>a>>b) {
        cout << gcd(a,b) << " " << lcm(a,b) << endl;
    }

    return 0;
}

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

int main() {
  int n,m; cin >>n >>m;
  vector<int> fav(m,1); //みんな
  vector<int> a(m);     //個人
  int k;
  int buf;
  for (int i=0; i<n; i++){
    a = vector<int> (m,0);
    cin >>k;
    for (int j=0; j<k; j++){
      cin >>buf;
      a.at(buf-1) = 1;
    }
    for (int j=0; j<m; j++){
      fav.at(j) *= a.at(j);
    }
  }
  int ans=0;
  for (int i=0; i<m; i++){
    ans += fav.at(i);
  }
  
  cout <<ans;
  cout <<endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    XL = []
    for i in range(N):
        x, l = map(int, input().strip().split())
        XL.append((x, l))
    return N, XL


def solve(N, XL):
    XL.sort(key=lambda x: x[0]+x[1])
    r = -10**9-1
    count = 0
    for x, l in XL:
        if r <= x - l:
            r = x + l
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 21380
n = int(input())
headList = [0] * 5

for i in range(n):
  s = input()
  if s[0] == 'M':
    headList[0] += 1
  elif s[0] == 'A':
    headList[1] += 1
  elif s[0] == 'R':
    headList[2] += 1
  elif s[0] == 'C':
    headList[3] += 1
  elif s[0] == 'H':
    headList[4] += 1
else:
  result = 0
  result += headList[0]*headList[1]*headList[2]
  result += headList[0]*headList[1]*headList[3]
  result += headList[0]*headList[1]*headList[4]
  result += headList[0]*headList[2]*headList[3]
  result += headList[0]*headList[2]*headList[4]
  result += headList[0]*headList[3]*headList[4]
  result += headList[1]*headList[2]*headList[3]
  result += headList[1]*headList[2]*headList[4]
  result += headList[1]*headList[3]*headList[4]
  result += headList[2]*headList[3]*headList[4]

print(result)

Measured memory_bytes: 44264
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int Mmax = 1e5;
int N, M, X[Mmax], Y[Mmax], Z[Mmax];

void dfs(int v, vector<vector<int>> &graph, vector<bool> &visit){
    for(int u: graph[v]){
        if(visit[u]) continue;
        visit[u]=true;
        dfs(u, graph, visit);
    }
}

int main(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        cin >> X[i] >> Y[i] >> Z[i];
        X[i]--; Y[i]--;
    }

    vector<vector<int>> graph(N);
    for(int i=0; i<M; i++){
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    vector<bool> visit(N, false);
    int ans = 0;
    for(int i=0; i<N; i++){
        if(!visit[i]){
            ans++;
            visit[i]=true;
            dfs(i, graph, visit);
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11648
import java.util.Arrays;
import java.util.Scanner;

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

    public static void solve(Scanner sc) {
        int d = sc.nextInt();
        switch (d) {
            case 25:
                System.out.println("Christmas");
                return;
            case 24:
                System.out.println("Christmas Eve");
                return;
            case 23:
                System.out.println("Christmas Eve Eve");
                return;
            case 22:
                System.out.println("Christmas Eve Eve Eve");
                return;
        } 
    }
}

Measured memory_bytes: 21588
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int i;
			int cnt = sc.nextInt();
			double ret = 100;
			for (i = 0; i < cnt; i++) {
				ret = ret + ret * 0.05;
				ret = Math.ceil(ret);
			}
			System.out.println((int) ret * 1000);
		}
	}
}

Measured memory_bytes: 26092
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, X):
    X.sort()
    diff = []
    for i in range(len(X)-1):
        diff.append(X[i+1] - X[i])
    diff.sort(reverse=True)
    diff = diff[N-1:]
    return sum(diff)


def main():
    # N = read_int()
    N, M = read_int_n()
    # A = [read_int_n() for _ in range(N)]
    X = read_int_n()
    print(slv(N, M, X))


if __name__ == '__main__':
    main()


Measured memory_bytes: 16272
import collections 
n=int(input())
v=list(map(int,input().split()))
c1,c2,ans=collections.Counter(v[::2]),collections.Counter(v[1::2]),0
a,b=c1.most_common(),c2.most_common()
if len(a)==len(b)==1:
  print(n//2 if a==b else 0)
  exit()
ans=n+(-a[0][1]-b[0][1] if a[0][0]!=b[0][0] else (-a[0][1]-b[1][1] if b[1][1]>=a[1][1] else -a[1][1]-b[0][1]))
print(ans)

Measured memory_bytes: 21184
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod



def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    for i in range(k):
        if n - k + 1 >= i + 1 and k - 1 >= i:
            print((alg_combination_mod(n - k + 1, i + 1, mod) * alg_combination_mod(k - 1, i, mod)) % mod)
        else:
            print(0)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 42224
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
// 293206GT
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
#include <stack>
#include <string>
#include<algorithm>
#include <random>
#include <bitset>
#include <chrono>

typedef long long ll;

using namespace std;
#define put(a) cout << (a) << '\n'
#define sqr(x) (x) * (x)
typedef pair<ll, ll> pii;
typedef long double ld;

typedef pair<ld, ld> pld;
#define rep(x, y, a) for (int x = (y); x < (int)(a); ++x)
#define all(a) a.begin(), a.end()
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))
#define prev asasdasd
#define next aasdasda
#define left asdasdasdasd
#define right asnabsdkasdl
#define rank asdasdknlasd
#define move asdasdas

typedef vector<ll> vi;
typedef vector<pii> vpii;
namespace IO {
    template<class A, class B>
    ostream &operator<<(ostream &out, pair<A, B> &a) {
        out << a.first << " " << a.second;
        return out;
    }

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> &a) {
        for (pair<A, B> x: a)
            out << x.first << " " << x.second << '\n';
    }

    template<class A>
    ostream &operator<<(ostream &out, vector<A> &a) {
        for (A x: a) out << x << ' ';
        return out;
    }

    template<class A, class B>
    istream &operator>>(istream &in, pair<A, B> &a) {
        in >> a.first >> a.second;
        return in;
    }

    template<class A>
    istream &operator>>(istream &in, vector<A> &a) {
        for (A &x: a) in >> x;
        return in;
    }
}
using namespace IO;
#define int ll

void solve() {
    int n, k;
    cin >> n >> k;
    vi cnt(n, 0);
    rep(i, 0, k) {
        int d;
        cin >> d;
        rep(j, 0, d) {
            int x;
            cin >> x;
            --x;++cnt[x];
        }
    }
    put(count(all(cnt), 0));
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(30);
//    freopen("input.txt", "r", stdin);
    int q = 1;
//    cin >> q;
    while (q--) solve();
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define maxn 200005


int main() {
    fastio;
    lli n;
    cin>>n;
    vi vls;
    for(int i=1;i<=100;i++)
        vls.pb((i*(i+1))/2);
    vi pr;
    for(int i=2;i<=sqrt(n);i++)
    {
        int cnt=0;
        while(n%i==0)
        {
            n/=i;
            cnt++;
        }
        if(cnt)
            pr.pb(cnt);
    }
    if(n>1)
        pr.pb(1);
    lli ans=0;
    for(int x : pr)
    {
        auto it=lower_bound(all(vls),x);
        if(*it>x)
            it--;
        ans+=it-vls.begin()+1;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 3648
n = int(input())
a = list(map(int, input().split()))
b = [[] for _ in range(n)]
c = [0]*30
d = []
for i in range(n):
    m = a[i]
    while m > 0:
        b[i].append(m%2)
        m //= 2
for i in range(n):
    for j in range(len(b[i])):
        c[j] += b[i][j]
for i in range(30):
    c[i] = c[i]%2
for i in range(n):
    e = 0
    for j in range(len(b[i])):
        if b[i][j]+c[j] == 1:
            e += 2**j
    for j in range(len(b[i]), 30):
        if c[j] == 1:
            e += 2**j
    d.append(e)
print(*d)

Measured memory_bytes: 174272
import java.util.Scanner;
class Main{
	static Scanner sc = new Scanner(System.in);
  public static int nextSunday(String str){
      	final int SUNDAY = 7;
  	switch(str){
      case "SUN":
          return SUNDAY - 0;
      case "MON":
          return SUNDAY - 1;
      case "TUE":
          return SUNDAY - 2;
      case "WED":
          return SUNDAY - 3;
      case "THU":
          return SUNDAY - 4;
      case "FRI":
          return SUNDAY - 5;
      default:
        return 1;
    }
  }
  public static void main(String[] args){
  	final int SUNDAY = 7;
    String str = sc.next();
    System.out.println(nextSunday(str));
  }
}

Measured memory_bytes: 21460
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc *bufio.Scanner

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func main() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	nums := make([]int, 3)
	for i := 0; i < 3; i++ {
		nums[i] = nextInt()
	}
	for i := 0; i < 2; i++ {
		if nums[i] > nums[i+1] {
			*&nums[i+1], *&nums[i] = *&nums[i], *&nums[i+1]
		}
	}
	i := 0
	if nums[i] > nums[i+1] {
		*&nums[i+1], *&nums[i] = *&nums[i], *&nums[i+1]
	}
	fmt.Println(nums[0], nums[1], nums[2])

}



Measured memory_bytes: 1124
#include <iostream>
#include <cstdio>
using namespace std;
int n,ans;
signed main()
{
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                        if (i*j<n) ans++;
                        else break;
                }
        }
        cout<<ans<<"\n";
        return 0;
}


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

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    ll odp = 0;
    vector<ll> pas(n, 0);
    for (int i = 0; i < n; ++i)
    {
        if (i - a[i] >= 0)
            odp += pas[i - a[i]];
        if (i + a[i] < n)
            ++pas[i + a[i]];
    }
    cout << odp;
    return 0;
}


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

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

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k;
	cin >> k;
	long long int sum = 0;
	for (int a = 1; a <= k; ++a){
		for (int b = 1; b <= k; ++b){
			int r = gcd(a,b);
			for (int c = 1; c <= k; ++c){
				sum += gcd(r,c);
			}
		}
	}
	cout << sum << "\n";	
	return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

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

int compress(vector<int> &s, vector<int> &e, int D) {
	vector<int> arr;
	int N = s.size();
	for (int i = 0; i < N; i++) {
		for (int j = -1; j <= 1; j++) {
			int x1 = s[i] + j;
			int x2 = e[i] + j;
			if (x1 >= 0 && x1 < D) arr.push_back(x1);
			if (x2 >= 0 && x2 < D) arr.push_back(x2);
		}
	}
	arr.push_back(0);
	arr.push_back(D - 1);
	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end());
	for (int i = 0; i < N; i++) {
		s[i] = lower_bound(arr.begin(), arr.end(), s[i]) - arr.begin();
		e[i] = lower_bound(arr.begin(), arr.end(), e[i]) - arr.begin();
	}
	return arr.size();
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (1) {
		int H, W; cin >> W >> H;
		if (W == 0 && H == 0)break;
		int N; cin >> N;

		VI sx(N), sy(N), ex(N), ey(N);
		REP(i, N)cin >> sx[i] >> sy[i] >> ex[i] >> ey[i];
		W = compress(sx, ex, W);
		H = compress(sy, ey, H);
		vector<vector<int>> imos(H + 1, vector<int>(W + 1, 0));

		REP(i, N) {
			int x1 = sx[i];
			int x2 = ex[i];
			int y1 = sy[i];
			int y2 = ey[i];
			imos[y1][x1]++;
			imos[y2][x2]++;
			imos[y1][x2]--;
			imos[y2][x1]--;
		}
		REP(i, H) {
			REP(j, W) {
				imos[i][j + 1] += imos[i][j];
			}
		}

		REP(j, W) {
			REP(i, H) {
				imos[i + 1][j] += imos[i][j];
			}
		}

		int ans = 0;
		REP(i, H) {
			REP(j, W) {
				if (imos[i][j] == 0) {
					queue<pair<int, int>> Q;
					Q.push(make_pair(i, j));
					imos[i][j] = 1;
					ans++;
					while (!Q.empty()) {
						auto p = Q.front();
						Q.pop();
						int y = p.first;
						int x = p.second;
						for (int k = 0; k < 4; k++) {
							int toY = y + dy[k];
							int toX = x + dx[k];
							if (toY < 0 || toY >= H || toX < 0 || toX >= W) continue;
							if (imos[toY][toX]) continue;
							imos[toY][toX] = 1;
							Q.push(make_pair(toY, toX));
						}
					}
				}
			}
		}

		cout << ans << endl;


	}
	return 0;
}




Measured memory_bytes: 17084
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>
using namespace std;
typedef  long long int lint;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (lint i = 0; i < n; i++)
#define repr(i, n) for (lint i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define mp make_pair
#define P pair<int,int>

//sqrtN -> 最大値のみに対応できればいいので，それを使う
const int sqrtN = 512;
struct SqrtDecomposition {
	int N, K;
	vector<int> data;
	vector<int> bucketSum;
	SqrtDecomposition(int n) : N(n) {
		K = (N + sqrtN - 1) / sqrtN;
		data.assign(K * sqrtN, 0);
		bucketSum.assign(K, 0);
	}
	void add(int x, int y) {
		int k = x / sqrtN;
		data[x] += y;
		int sum = 0;
		for (int i = k * sqrtN; i < (k + 1) * sqrtN; ++i) {
			sum += data[i];
		}
		bucketSum[k] = sum;
	}
	// [x, y)
	int getSum(int x, int y) {
		int sum = 0;
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= x || y <= l)
				continue;
			if (x <= l && r <= y) {
				sum += bucketSum[k];
			}
			else {
				for (int i = max(x, l); i < min(y, r); ++i) {
					sum += data[i];
				}
			}
		}
		return sum;
	}
};

int main() {
	//range sum query
	int n, q;
	cin >> n >> q;

	SqrtDecomposition dec(n);
	//vector<string> res;
	rep(_, q) {
		int c, x, y;
		cin >> c >> x >> y;
		if (c == 0) {
			dec.add(x, y);
		}
		else {
			cout << dec.getSum(x, y + 1) << endl;
		}
	}
}



Measured memory_bytes: 3164
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, D, A = MAP()
XH = [LIST() for _ in range(N)]

XH.sort(key = lambda x: x[0])

X, H = zip(*XH)
right = [0]*N
for i, x in enumerate(X):
	right[i] = bisect(X, x+2*D)

damage = [0]*(N+1)
ans = 0

for i, (X, H) in enumerate(XH):
	if i != 0:
		damage[i] += damage[i-1]
	H -= damage[i]
	if 0 < H:
		n = -(-H//A)
		ans += n
		d = A*n
		damage[i] += d
		damage[right[i]] -= d
print(ans)


Measured memory_bytes: 65760
import numpy as np
import math

a,b,x = map(int, input().split())
if 2 * x > a * a *b:
    ans = math.atan(2 * (a * a * b - x) / (a * a * a))
    ans = math.degrees(ans)
    print(ans)
else:
    ans = math.atan(a * b * b / (2 * x))
    ans = math.degrees(ans)
    print(ans)
    


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

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define ALL(x) (x).begin(),(x).end()

using ll = long long;
using ull = unsigned long long;
 
const ll INF = 1LL<<60;
const int MINF = 1e9;
const int MOD = 1e9+7;

using vi = vector<int>;
using vii = vector<vi>;

template<typename T,typename U> bool chmax(T& a, U b) { if (a < b) { a = b; return true; } return false; }
template<typename T,typename U> bool chmin(T& a, U b) { if (a > b) { a = b; return true; } return false; }

template<typename T>
T GCD(T a,T b){ return b ? GCD(b,a%b) : a ;}
template<typename T>
T LCM(T a,T b){ return a*b / GCD(a,b) ;}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n,a,b;cin >> n >> a >> b;
    if((a+b)%2==0){
        cout << (b-a)/2 << endl;
    }else{
        cout << min(a-1,n-b) + 1 + (b-a-1)/2 << endl;
    }
    return 0;
}

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

using namespace std;

int main()
{
    int N;
    int M;
    cin >> N >> M ;
    
    long int a[N];
    long int b[N];
    long int c[M];
    long int d[M];
    
    
    for (int i=0;i<N;i++){
        cin >> a[i] >> b[i];
    }
    for (int j=0;j<M;j++){
        cin >> c[j] >> d[j];}
    
    
    for (int i=0;i<N;i++){
        long int m = abs(a[i]-c[0])+ abs(b[i]- d[0]);
        int n=0;
        for (int j=0;j<M;j++){
            if (abs(a[i]-c[j])+ abs(b[i]- d[j]) < m){
                m = abs(a[i]-c[j])+ abs(b[i]- d[j]);
                n = j;}}
        cout <<n+1<< "\n";
    }
    
}






Measured memory_bytes: 256
//@formatter:off
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define rrep(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = int(s); i < int(n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vp vector<P>
#define vvp vector<vector<P>>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==int(v.size()-1)?"":","); return os<<']'; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << '\n'; }
void YES(bool b) { cout << (b ? "YES" : "NO") << '\n'; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
//@formatter:on

int dp[200010][50];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, t;
    cin >> n >> t;
    vi a, b;
    vi pm;
    rep(i, n) {
        int na, nb;
        cin >> na >> nb;
        if (na == 0) {
            pm.pb(nb);
        } else {
            a.pb(na);
            b.pb(nb);
        }
    }
    sort(all(pm));
    int sz = a.size();
    vi ord(sz);
    iota(all(ord), 0);
    sort(all(ord), [&](int x, int y) { return (ll) (b[x] + 1) * a[y] < (ll) (b[y] + 1) * a[x]; });
    rep(i, 200010) rep(j, 50) dp[i][j] = inf;
    dp[0][0] = 0;
    rep(i, sz) rep(j, 50) {
            if (dp[i][j] > t) continue;
            chmin(dp[i + 1][j], dp[i][j]);
            ll nx = (ll) (dp[i][j] + 1) * a[ord[i]] + b[ord[i]] + 1;
            if (nx > t) continue;
            chmin(dp[i + 1][j + 1], dp[i][j] + (int) nx);
        }
    int ans = 0;
    rep(i, 50) {
        if (dp[sz][i] > t) continue;
        int rem = t - dp[sz][i];
        int now = i;
        for (int j : pm) {
            if (rem >= j + 1) {
                rem -= j + 1;
                now++;
            }
        }
        chmax(ans, now);
    }
    cout << ans << endl;
}


Measured memory_bytes: 44728
#include <bits/stdc++.h>
using namespace std;
#define ff(i,s,n) for(int i=s;i<n;i++)
#define fr(i,s,n) for(int i=n-1;i>=s;i--)
#define llu long long int
const int mod=1000000007;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	llu p=max((llu)a*c,max((llu)a*d,max((llu)b*c,(llu)b*d)));
	cout<<p;
	return 0;
}


//1
//7 2
//3 5 4 5 1 1 1


Measured memory_bytes: 3612