akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from collections import defaultdict
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]

    p.sort()

    c = defaultdict(int)

    for i in range(n):
        for j in range(i):
            c[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += 1

    print((n - max(c.values())) if c else 1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


Measured memory_bytes: 31468
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}


class Combination {
public:
	Array fact;//n！
	Array inv;//n!の逆元
	ll mod;
	Combination(ll n, ll _mod) {
		mod = _mod;
		fact.resize(n + 1);
		fact[0] = 1;
		REP(i, n) {
			fact[i + 1] = (fact[i] * (i + 1LL)) % mod;
		}
		inv.resize(n + 1);
		inv[n] = mod_inv(fact[n]);
		for (int i = n; i > 0; i--) {
			inv[i - 1] = inv[i] * i % mod;
		}
	}
	//modの逆元
	ll mod_inv(ll x) {
		ll n = mod - 2;
		ll res = 1LL;
		while (n > 0) {
			if (n & 1) res = res * x % mod;
			x = x * x % mod;
			n >>= 1;
		}
		return res;
	}
	ll nCr(ll n, ll r) {
		return ((fact[n] * inv[r] % mod) * inv[n - r]) % mod;
	}
	ll nPr(ll n, ll r) {
		return (fact[n] * inv[n - r]) % mod;
	}
	ll nHr(ll n, ll r) {
		//重複組み合わせ：n種類のものからr個取り出す組み合わせ
		return nCr(r + n - 1, r);
	}
};

Combination com(1e6 + 10, MOD);

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

	double x;
	cin >> x;

	double ans = sqrt(2.0 * x + 1.0 / 4.0) - 1.0 / 2.0;
	if (ans != (double)(ll)ans) ans++;
	cout << (ll)ans << endl;
	

	return 0;
}

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

int main()
{
	int N,C=0,a,b,c;
	cin >> N;
	vector<int> d(N);

	for(int i=0;i<N;i++)
		cin >> d[i];

	sort(d.begin(), d.end());

	for (int i = 0; i < N; i++) 
	{
		a = d[i];
		for (int j = i+1; j < N; j++)
		{
			b = d[j];
			for (int k = j + 1; k < N; k++)
			{
				c = d[k];
				if (a + b > c && b + c > a && c + a > b)
				{
					C++;
				}else {
					break;
				}
			}
		}
	}

	cout << C;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  size_t n;
  scanf("%zu", &n);

  std::vector<intmax_t> s(n);
  for (auto& si: s) scanf("%jd", &si);

  intmax_t res = 0;
  for (size_t c = 1; c <= n-1; ++c) {
    intmax_t cur = 0;
    std::vector<bool> reached(n);
    for (size_t kc = 0; kc <= n-1; kc += c) {
      if (reached[n-1-kc] || reached[kc]) break;
      if (kc == n-1-kc) break;
      reached[n-1-kc] = reached[kc] = true;
      if (n-1-kc < c) break;
      // fprintf(stderr, "+ [%zu] + [%zu]\n", kc, n-1-kc);
      cur += s[n-1-kc] + s[kc];
      res = std::max(res, cur);
    }
    // fprintf(stderr, "===\n");
  }
  printf("%jd\n", res);
}


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

int main() {
    int N; cin >> N;
    long A[N]; for (int i = 0; i < N; i++) cin >> A[i];
    int num_neg = 0;
    long sum = 0, min_abs = abs(A[0]);
    bool is_exist_zero = false;
    for (int i = 0; i < N; i++) {
        if (A[i] < 0) num_neg++;
        else if (A[i] == 0) is_exist_zero = true;
        min_abs = min(min_abs, abs(A[i]));
        sum += abs(A[i]);
    }
    if (is_exist_zero) cout << sum << endl;
    else {
        if (num_neg % 2 == 0) cout << sum << endl;
        else cout << sum - 2 * min_abs << endl;
    }
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double W = sc.nextInt();
		double H = sc.nextInt();
		double x = sc.nextInt();
		double y = sc.nextInt();

		if (W / 2 == x && H / 2 == y) {
			System.out.println(W * H / 2 + " " + 1);
		} else {
			System.out.println(W * H / 2 + " " + 0);
		}
	}
}


Measured memory_bytes: 21716
N = int(input())
A = list(map(int, input().split()))
 
def gcd(a,b):
  if b==0:
    return a
  else:
  	return gcd(b, a%b)

#L=[]
#R=[]
#L.append(0)
#R.append(0)
L=[0]*(N+1)
R=[0]*(N+1)
L[0]=0
R[0]=0

for i in range(N):
  #L.append(gcd(L[i],A[i]))
  #R.append(gcd(R[i],A[N-i-1]))
  L[i+1]=gcd(L[i],A[i])
  R[i+1]=gcd(R[i],A[N-i-1])

R.reverse()

Res=[0]*N
#res=0
for i in range(N):
  #Res.append(gcd(L[i],R[i+1]))
  #res=max(res,gcd(L[i],R[i+1]))
  Res[i]=gcd(L[i],R[i+1])
print(max(Res))

Measured memory_bytes: 14440
from itertools import permutations

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

for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    g[a].append(b)
    g[b].append(a)

lis = list(c for c in permutations(range(n), n) if c[0] == 0)

res = 0
for li in lis:
    flg = True
    for i in range(1, n):
        if li[i-1] in g[li[i]]:
            continue
        else:
            flg = False
            break
    if flg:
        res += 1
print(res)


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

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	std::vector<bool> AC(N);
	std::vector<int> penalty(N);
	for (int i{}; i < M; i++)
	{
		int p;
		std::string S;
		std::cin >> p >> S;
		p--;
		if (S == "AC")
			AC[p] = true;
		else if (!AC[p])
			penalty[p]++;
	}
	int ac_num{}, penalty_num{};
	for (int i{}; i < N; i++)
	{
		if (!AC[i]) continue;
		ac_num++;
		penalty_num += penalty[i];
	}
	printf("%d %d\n", ac_num, penalty_num);

	return 0;
}

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

int main() {
  int n;
  std::cin >> n;
  std::string st;
  std::cin >> st;

  int s = 0, e = 0;

  for (int i = st.size() - 1; 0 <= i; i--) {
    if (st[i] == '(') {
      s++;
    } else {
      e++;
    }

    if (e < s) {
      st.push_back(')');
      s--;
    }
  }

  std::string tmp("");

  s = 0;
  e = 0;
  for (int i = 0; i < st.size(); i++) {
    if (st[i] == '(') {
      s++;
    } else {
      e++;
    }

    if (s < e) {
      tmp.push_back('(');
      e--;
    }
  }

  std::cout << tmp << st << std::endl;
  return 0;
}

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

string s="CODEFESTIVAL2016",a; 
int ans=0;

int main()
{
    cin>>a;
    for(int i=0;i<=15;i++)
        if(a[i]!=s[i]) ans++;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    string a;
    cin >> a;
    int mi = (a[5] - '0') * 10 + (a[6] - '0');
    int dz = (a[8] - '0') * 10 + (a[9] - '0');
    if (mi < 4 || (mi == 4 && dz <= 30))
        cout << "Heisei";
    else
        cout << "TBD";
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstring> 

const int Maxv = 100010; 
const int Mod = 1e9 + 7; 

int inv[Maxv], a[Maxv], ans, n, m; 

int main() {
    scanf("%d", &n); 
    
    inv[1] = 1; 
    for (int i = 2; i <= n; i++)
        inv[i] = 1ll * inv[Mod % i] * (Mod - Mod / i) % Mod; 
    for (int i = 2; i <= n; i++)
        inv[i] = (inv[i - 1] + inv[i]) % Mod; 
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x); 
        ans = (ans + 1ll * x * (inv[i] + inv[n - i + 1] - 1)) % Mod; 
    }
    for (int i = 1; i <= n; i++)
        ans = 1ll * ans * i % Mod; 
    
    printf("%d\n", ans); 

    return 0; 
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(void) {
  int n, wmax;
  cin >> n >> wmax;
  vector<int> w(n);
  vector<ll> v(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> v[i];
  }
  vector<vector<ll> > dp(n + 1, vector<ll>(wmax + 1));
  for (int i = 0; i < n; i++) {
    for (int sum_w = 0; sum_w <= wmax; sum_w++) {
      if (sum_w >= w[i]) {
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w] , dp[i][sum_w - w[i]] + v[i]);
      }
      dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w]);
    }
  }
  cout << dp[n][wmax] << endl;
  return 0;
}

Measured memory_bytes: 83152
// MinMaxAndSum.cc
// n個の整数 ai(i=1,2,...n)を入力し、それらの最小値、最大値、合計値を
// 求めるプログラムを作成してください。
// 【入力】
// １行目に整数の数 nが与えられます。２行目に n個の整数 aiが空白区切りで与えられます。
// 【出力】
// 最小値、最大値、合計値を空白区切りで１行に出力してください。
// 【制約】
// ・0<n≤10000
// ・−1000000≤ai≤1000000
// 【例】
// 入力：
// 5
// 10 1 5 4 17
// 出力：
// 1 17 37
#include<iostream>
using namespace std;

int main( void) {
  int n, a;
  long long max = -1000000, min = 1000000, sum = 0;

  cin >> n;

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

    if ( a >= max) max = a;
    if ( a <= min) min = a;

    sum += a;
  }

  cout << min << " " << max << " " << sum << endl;

  return 0;
}



Measured memory_bytes: 3076
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = (1LL << 50) * -1;
struct edge {
  int from, to, cost;
};
int main(void) {
  int n, m;
  cin >> n >> m;
  vector<edge> graph(m);
  vector<ll> distance(n, INF);
  distance[0] = 0;
  for (int i = 0; i < m; i++) {
    cin >> graph[i].from;
    cin >> graph[i].to;
    graph[i].from--;
    graph[i].to--;
    cin >> graph[i].cost;
  }
  vector<bool> initial(n, 1);
  for (int loop = 0; loop < n - 1; loop++) {
    for (int i = 0; i < m; i++) {
      if (distance[graph[i].from] == INF) continue;
      if (distance[graph[i].to] < distance[graph[i].from] + graph[i].cost) {
        distance[graph[i].to] = distance[graph[i].from] + graph[i].cost;
      }
    }
  }
  vector<bool> update(0, n);
  for (int loop = 0; loop < n - 1; loop++) {
    for (int i = 0; i < m; i++) {
      if (distance[graph[i].from] == INF) continue;
      if (distance[graph[i].to] < distance[graph[i].from] + graph[i].cost) {
        distance[graph[i].to] = distance[graph[i].from] + graph[i].cost;
        if (graph[i].to == n - 1) {
          cout << "inf" << endl;
          return 0;
        }
      }
    }
  }
  cout << distance[n - 1] << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int a,b,r,tmp;
  scanf("%d%d",&a,&b);
  if(a<b){
    tmp=a;
    a=b;
    b=tmp;
    
  }
    

    
  while(b>0){
    r=a%b;
    a=b;
    b=r;
  }
  printf("%d\n",a);

  return 0;
}

Measured memory_bytes: 592
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    a=i
    while a>0:
        cnt += a%6
        a //= 6
    b=N-i
    while b>0:
        cnt += b%9
        b //= 9
    ans=min(ans,cnt)
print(ans)

Measured memory_bytes: 3060
#include <stdio.h>
int main(void){
  int n,x,t;
  setbuf(stdout,NULL);
  scanf("%d%d%d",&n,&x,&t);
  if(n%x==0){
    printf("%d",(n/x)*t);
  }else{
    printf("%d",(n/x)*t+t);
  }
  return 0;
}

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

int main() {
	int N, t1 = 0, t2, x1 = 0, y1 = 0, x2, y2, check;
	cin >> N;
	for (int i = 0;i < N;i ++) {
		cin >> t2 >> x2 >> y2;
		check = t2 - t1 - abs(x2 - x1) - abs(y2 - y1);
		if (check < 0 || check % 2 == 1) {
			cout << "No";
			return 0;
		}
		t1 = t2;
		x1 = x2;
		y1 = y2;
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
s=input()+"R"
n=len(s)-1
ans=[0 for i in range(n)]
i=0
while i<n:
    r=s.find("L",i)
    l=s.find("R",r)
    ans[r-1]+=(r-i+1)//2+(l-r)//2
    ans[r]+=(r-i)//2+(l-r+1)//2
    i=l
print(" ".join(map(str,ans)))

Measured memory_bytes: 50464
use proconio::input;
use std::cmp;

fn main() {
    input! {
        a: i64,
        v: i64,
        b: i64,
        w: i64,
        t: i64,
    }

    let ans = (a - b).abs() <= t * cmp::max(v - w, 0);
    println!("{}", if ans { "YES" } else { "NO" });
}


Measured memory_bytes: 2116
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; 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 sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 998244353;

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
      mint a = pow(t>>1);
      a *= a;
    if (t&1) a *= *this;
      return a;
  }
   mint inv() const { return pow(MOD-2);}
   mint& operator/=(const mint a) { return *this *= a.inv();}
   mint operator/(const mint a) const { return mint(*this) /= a;}
};
typedef vector<mint> vm;
typedef vector<vm> vvm;

class Combi {
private:
  v(ll) fac, inv, finv;
  void init(int N) {
    fac[0] = fac[1] = 1; inv[1] = 1; finv[0] = finv[1] = 1;
    for (int i = 2; i < N; i++) {
      fac[i] = fac[i - 1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
      finv[i] = finv[i - 1] * inv[i] % MOD;
    }
  }
public:
  Combi(int N) : fac(N + 1), inv(N + 1), finv(N + 1) { init(N + 1); }
  ll Cmod(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
  }
  ll Pmod(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[n - k] % MOD;
  }
};
  
int main() {
  int N,M,K;
  cin >> N >> M >> K;
  mint ans = 0;
  Combi c(N);
  rep(k,K+1) {
    mint res = mint(M-1).pow(N-k-1);
    res *= M;
    res *= c.Cmod(N-1,k);
    ans += res;
  }
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 7828
al = [input().split() for _ in range(3)]
n = int(input())
for _ in range(n):
    b = input()
    for i in range(3):
        for j in range(3):
            if al[i][j]==b:
                al[i][j] = "0"

if al[0][0]=="0" and al[0][1]=="0" and al[0][2]=="0":
    print("Yes")
elif al[1][0]=="0" and al[1][1]=="0" and al[1][2]=="0":
    print("Yes")
elif al[2][0]=="0" and al[2][1]=="0" and al[2][2]=="0":
    print("Yes")
elif al[0][0]=="0" and al[1][0]=="0" and al[2][0]=="0":
    print("Yes")
elif al[0][1]=="0" and al[1][1]=="0" and al[2][1]=="0":
    print("Yes")
elif al[0][2]=="0" and al[1][2]=="0" and al[2][2]=="0":
    print("Yes")
elif al[0][0]=="0" and al[1][1]=="0" and al[2][2]=="0":
    print("Yes")
elif al[0][2]=="0" and al[1][1]=="0" and al[2][0]=="0":
    print("Yes")
else:
    print("No")

Measured memory_bytes: 39760
N, M = map(int, input().split())
A = list(map(int, input().split()))

max_diff = A[0]+N-A[-1]
for i in range(1,M):
  max_diff = max(A[i]-A[i-1],max_diff)
ans = N-max_diff
print(ans)

#print(*ans, sep='\n')

Measured memory_bytes: 26444
<?php

$s = str_split(getOneLine());

$patternA = 0; // 偶数で0、奇数で1
$patternB = 0; // 偶数で1、奇数で0

foreach ($s as $i => $color) {
    if ($i % 2 == 0) { // 偶数
        if ($color == 0) {
            $patternB++;
        } else {
            $patternA++;
        }
    } else { // 奇数
        if ($color == 0) {
            $patternA++;
        } else {
            $patternB++;
        }
    }
}

println(min([$patternA, $patternB]));







function println($str)
{
    echo $str . "\n";
}

function sprintlnFormat($format, $str)
{
    println(sprintf($format, $str));
}

function getOneLine()
{
    $str = trim(fgets(STDIN));
    return $str;
}

function getLineExploded($delimiter = ' ')
{
    $str = getOneLine();
    $ret = explode($delimiter, $str);
    return $ret;
}

Measured memory_bytes: 10744
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), d = sc.nextInt(), a = sc.nextInt();
        PriorityQueue<P> q = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            q.add(new P(sc.nextInt(), sc.nextInt(), 0));
        }

        long dm = 0;
        long ans = 0;
        while (!q.isEmpty()) {
            P cur = q.remove();
//            debug(dm, ans, cur.x, cur.h, cur.t);
            switch (cur.t) {
                case 0:
                    cur.h -= dm;
                    if (cur.h < 0) break;
                    long k = (cur.h + a - 1) / a;
                    ans += k;
                    dm += k * a;
                    q.add(new P(cur.x + 2 * d, -k * a,1));
                    break;
                case 1:
                    dm += cur.h;
            }
        }

        System.out.println(ans);
    }

    class P implements Comparable<P> {
        long x, h;
        int t;
        P(long x, long h, int t) {
            this.x = x;
            this.h = h;
            this.t = t;
        }

        @Override
        public int compareTo(P o) {
            if (x != o.x) {
                return Long.compare(x, o.x);
            }
            return t - o.t;
        }
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

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

}


Measured memory_bytes: 104752
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
  
using namespace std;

int main() {
    long long n, m, k;
    cin>>n>>m>>k;
    vector<long long> A(n, 0);
    vector<long long> B(m, 0);
    cin>>A[0];
    for(int i = 1; i < n; i++) {
        cin>>A[i];
        A[i] += A[i-1];
    }
    cin>>B[0];
    for(int i = 1; i < m; i++) {
        cin>>B[i];
        B[i] += B[i-1];
    }

    int i1 = (int)(upper_bound(B.begin(), B.end(), k) - B.begin());
    int i2 = (int)(upper_bound(A.begin(), A.end(), k) - A.begin());
    i1--; i2--;
    int res = 0;
    if(B[i1] <= k && A[i2] <= k) {
        res = max(i1+1, i2+1);
    } else if(B[i1] <= k) {
        res = i1+1;
    } else if(A[i2] <= k) {
        res = i2+1;
    }

    for(int i = 0; i < n; i++) {
        long long t = k - A[i];
        if(t >= 0) {
            int lbIndex = (int)(upper_bound(B.begin(), B.end(), t) - B.begin());
            lbIndex--; 
            if(lbIndex >= 0 && B[lbIndex] <= t) {
                res = max(res, i+1 + lbIndex+1);
            }
        } else {
            break;
        }
    }
    cout<<res<<endl;
    return 0;
}

// 60 150 270
// 80 230 310 460

Measured memory_bytes: 6424
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
using ll = long long;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    int n;
    cin >> n;
    vector<int>hn(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> hn.at(i);
    }
    vector<int>dp(n + 1);
    dp.at(1) = 0;
    dp.at(2) = dp.at(0) + abs(hn.at(1) - hn.at(2));
    for(int i = 3; i <= n; i++){
        dp.at(i) = min(dp.at(i - 2) + abs(hn.at(i - 2) - hn.at(i)), dp.at(i - 1) + abs(hn.at(i - 1) - hn.at(i)));
    }
    cout << dp.at(n) << endl;
    solve();
    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

ll m = 1e9+7;

ll pw(ll a, ll n)
{
    ll ans = 1;
    while (n > 0)
    {
        if (n % 2 != 0)
            ans = (ans * a) % m;
        a = (a * a) % m;
        n = n / 2;
    }
    return ans % m;
}

int main()
{
    ll n;
    cin >> n;
    map<ll, ll> mp;
    rep(i, 0, n)
    {
        ll a;
        cin >> a;
        mp[a]++;
    }
    bool y = true;
    for (auto x:mp)
    {
        if (n%2 == 0 && x.second != 2)
            y = false;
        if (n%2 == 1 && x.second != 2 && x.first != 0)
            y = false;
        if (n%2 == 1 && x.second != 1 && x.first == 0)
            y = false;
    }
    if (y == false)
        cout << 0;
    else 
        cout << (ll)pw(2, n/2) % m;
    return 0;
}

Measured memory_bytes: 4224
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

typedef long long LL;

long long solve(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    int ans = 0;
    for(int i = 0;i<(n-2);i++){
        if(str[i]=='A' && str[i+1]=='B' && str[i+2]=='C') ans++;
    }
    cout<<ans<<endl;
    return 0;
}

int main(){
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const int n_max = 1e5+10;
#define int ll

void YES(bool ok){
    cout << (ok ? "Yes" : "No") << endl;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll a,b; cin >> a >> b;
    ll c,d; cin >> c >> d;

    bool ok = false;
    ll turn = 0;
    while(a > 0 && c > 0){
        if(turn & 1){
            a -= d;
        }
        else{
            c -= b;
        }
        turn++;
    }
    if(c <= 0)ok = true;

    YES(ok);
}

Measured memory_bytes: 3612
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  String[]a=new String[]{"pon","pon","hon","bon","hon","hon","pon","hon","pon","hon","hon","hon","hon",};
  int n=sc.nextInt()%10;
  System.out.println(a[n]);
}
}


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

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++

def main(io):
	a,b,t= map(int, io().split())
	return (t // a)*b

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Measured memory_bytes: 2940
n = int(input())
s = input()

ans = [0]*(n+1)
for i in range(n):
  if s[i] == 'E':
    ans[i+1] = ans[i] + 1
  else:
    ans[i+1] = ans[i]
    
print(min(i-ans[i]+ans[n]-ans[i+1] for i in range(n)))

Measured memory_bytes: 21040
n, m, c = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
ans = 0

n.times do |i|
  a = gets.split.map(&:to_i)
  sum = 0
  m.times do |j|
    sum += a[j] * b[j]
  end
  ans += 1 if sum + c > 0
end

puts ans

Measured memory_bytes: 1788
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

int N, M, K, H, W, L, R;
//long long int N, M, K, H, W, L, R;


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

	cin >> N;
	cout << (N - 1) / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		while (true) {
			int n = s.nextInt();
			int m = s.nextInt();
			int p = s.nextInt();

			if (n == 0 && m == 0 && p == 0)
				break;

			int[] participant = new int[n];
			int bet = 0;
			int payment = 0;

			for (int i = 0; i < n; i++) {
				participant[i] = s.nextInt();
				bet += participant[i] * 100;
			}

			if (participant[m - 1] != 0) {
				payment = (bet - bet * p / 100) / participant[m - 1];
			}
			System.out.println(payment);
		}
		s.close();
	}
}

Measured memory_bytes: 27692
from collections import defaultdict
r, g, b, n = map(int, input().split())

dic = defaultdict(int)
for i in range(n // r + 1):
    for j in range(n // g + 1):
        dic[i * r + j * g] += 1


ans = 0
for k in range(n // b + 1):
    num = n - k * b
    ans += dic.get(num, 0)
print(ans)

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

int main(){
  long N;
  cin >> N;
  vector<long> v(N);
  map<long, long> m;
  for(int i = 0; i < N; i++){
    cin >> v.at(i);
    if(m.count(v[i]) == 0){
      m[v[i]] = 1;
    } else { 
      m[v[i]] += 1;
    }
  }
  
  long all = 0;
  for(auto x : m){
    all += x.second * (x.second-1) / 2;
  }
  
  for(int i = 0; i < N; i++){
    long num = m[v[i]];
    cout << all - (num - 1) << endl;
  }
}


Measured memory_bytes: 11008
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    std::vector<int> v(3);
    int k;
    std::cin>>v[0]>>v[1]>>v[2]>>k;

    for(int i = 0;i < k;i++){
        auto itr = std::max_element(v.begin(), v.end());
        *itr = *itr * 2;
    }
    std::cout<<std::accumulate(v.begin(), v.end(), 0)<<std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

int main() {
    int h, w, n, sr, sc;
    vector<char> d = {'U', 'L', 'D', 'R'};
    vector< pair<int, int> > m4 = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    scanf("%d%d%d%d%d\n", &h, &w, &n, &sr, &sc);
    vector<char> s(n), t(n);
    scanf("%s\n%s\n", s.begin(), t.begin());
    for (int i = 0; i < 4; ++i) {
        int y = sr, x = sc;
        for (int j = 0; j < n; ++j) {
            if (s.at(j) == d.at(i)) y += m4.at(i).first, x += m4.at(i).second;
            if (y < 1 || y > h || x < 1 || x > w) {
                printf("NO\n");
                return 0;
            }
            int dy = y + m4.at((i + 2) % 4).first, dx = x + m4.at((i + 2) % 4).second;
            if (t.at(j) == d.at((i + 2) % 4) && dy >= 1 && dy <= h && dx >= 1 && dx <= w) y = dy, x = dx;
        }
    }
    printf("YES\n");
    return 0;
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9)+7)

int main(){
    int n;
    cin >> n;
    vector<ll> A;
    vector<ll> B;
    for(int i = 0;i < n+1;i++)
    {
      int a;
      cin >> a;
      A.push_back(a);
    }
    for(int i = 0;i < n;i++)
    {
      int b;
      cin >> b;
      B.push_back(b);
    }

    ll ans = 0;
    for(int i = 0;i < n;i++)
    {
      if(A[i]+A[i+1] > B[i])
      {
        if(A[i] > B[i])
        {
          ans += B[i];
          A[i] -= B[i];
          B[i] = 0;
        }
        else
        {
          ans += B[i];
          B[i] -= A[i];
          A[i+1] -= B[i];
        }
      }
      else
      {
        ans += A[i]+A[i+1];
        B[i] -= A[i];
        B[i] -= A[i+1];
        A[i] = 0;
        A[i+1] = 0;
      }
    }
    cout << ans << endl;
}


Measured memory_bytes: 2548
#include<stdio.h>
int main(void){
	int i, sec = 0, input;
	for (i = 0; i < 4; i++){
		scanf(" %d", &input);
		sec += input;
	}
	for (i = 0; sec >= 60; i++){
		sec -= 60;
	}
	printf("%d\n%d\n", i, sec);
	return 0;
}

Measured memory_bytes: 596
using System;

namespace ITP1_8_D
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string p = Console.ReadLine();

            string ss = s + s;

            if (0 <= ss.IndexOf(p))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 8236
S = int(input())
a = S // 100
b = S % 100
def f(p,q):
    if p ==1:
        if q == 1:
            return 'AMBIGUOUS'
        else:
            return 'MMYY'
    else:
        if q == 1:
            return 'YYMM'
        else:
            return 'NA'
s = 0
t = 0
if 1 <= a <= 12:
    s = 1
if 1 <= b <= 12:
    t = 1
print(f(s,t))

Measured memory_bytes: 3060
#include<stdio.h>
#include<string.h>
int main(void)
{
	char s1[11],s2[11],s3[11];
	scanf("%s %s %s",s1,s2,s3);
	s1[0]=s1[0]-('a'-'A');
	s2[0]=s2[0]-('a'-'A');
	s3[0]=s3[0]-('a'-'A');
	printf("%c%c%c\n",s1[0],s2[0],s3[0]);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>

int main() {
  int k;
  std::cin >> k;

  std::string s;
  std::cin >> s;

  if (s.length() <= k) {
    std::cout << s << std::endl;
  } else {
    std::cout << s.substr(0, k) << "..." << std::endl;
  }
  return 0;
}


Measured memory_bytes: 3136
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iterator>
#include <fstream>
#include <math.h>

#include <random>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <list>
#include <bitset>
#include <unordered_set>
#include <unordered_map>

#include <random>
#include <ctime>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i, from, to) for (int i = from; i < to; i++)
#define ROF(i, from, to) for (int i = from; i > to; i--)

const long double PI = 3.141592653589793238463;
const int INF = 0x3f3f3f3f;
const int INFS = 1000000000;
const ll M = 1000000007;
const ll LLINF = 1000000000000000000;
const double EPS = 1e-8;

#define int long long

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, c;
    cin >> n >> c;
    vector<int> a(n), b(n);
    FOR(i, 0, n)
        cin >> a[i];
    FOR(i, 0, n)
        cin >> b[i];
    vector<vector<int> > dp(n, vector<int>(c + 1, 0)), pows(401, vector<int>(401));
    FOR(i, 1, 401) {
        pows[i][0] = 1;
        FOR(p, 1, 401) {
            pows[i][p] = (pows[i][p - 1] * i) % M;
        }
    }
    vector<vector<int> > prec(n, vector<int>(c + 1, 0));
    FOR(i, 0, n) {
        FOR(j, 0, c + 1) {
            FOR(x, a[i], b[i] + 1) {
                prec[i][j] = (prec[i][j] + pows[x][j]) % M;
            }
        }
    }
    FOR(tc, 0, c + 1) {
        dp[0][tc] = prec[0][tc];
    }
    FOR(i, 1, n) {
        FOR(tc, 0, c + 1) {
            FOR(lc, 0, tc + 1) {
                dp[i][tc] = (dp[i][tc] + dp[i - 1][lc] * prec[i][tc - lc]) % M;
            }
        }
    }
    cout << dp[n - 1][c] << "\n";

    return 0;
}


Measured memory_bytes: 7128
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		while(true){
			int a=cin.nextInt(),b=cin.nextInt();
			if(a==0 && b==0)break;
			
			if(a>b)System.out.println(b+" "+a);
			else System.out.println(a+" "+b);
		}
	}

}



Measured memory_bytes: 34680
#![allow(clippy::needless_range_loop)]
#![allow(unused_macros)]
#![allow(dead_code)]

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => (std::cmp::min($x, min!($($z),*)));
}

fn main() {
    input! {
        h: usize,
        n: usize,
        spells: [(usize, usize); n],
    }
    let mut dp = vec![10000000000usize; h + 10000];
    dp[0] = 0;
    for i in 1..(h + 10000) {
        for (damage, cost) in &spells {
            if *damage > i {
                continue;
            }
            dp[i] = std::cmp::min(dp[i], dp[i - *damage] + *cost);
        }
    }
    let ans = dp[h..].iter().min().unwrap();
    println!("{}", ans);
}


Measured memory_bytes: 2288
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N;cin>>N;
  cout<<0<<endl;
  string p;cin>>p;cout<<flush;if(p=="Vacant")return 0;
  cout<<N/2<<endl;
  string q;cin>>q;cout<<flush;if(q=="Vacant")return 0;
  long l,r;
  string a,b;
  if(((N/2)%2==0&&p!=q)||((N/2)%2==1&&p==q)){l=0;r=N/2;a=p,b=q;}
  else {l=N/2;r=N;a=q,b=p;}
  while(1){
    long z=(l+r)/2;cout<<z<<endl;
    string c;cin>>c;cout<<flush;if(c=="Vacant")return 0;
    if(((z-l)%2==0&&a!=c)||((z-l)%2==1&&a==c)){assert(r!=z);r=z;b=c;}
    else if(((r-z)%2==0&&b!=c)||((r-z)%2==1&&b==c)){assert(l!=z);l=z;a=c;}
    else assert(0);
  }
}


Measured memory_bytes: 852
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(int argc, char* argv[]){
    ll s[] = {0, 0, 0, 0, 0};\
    ll n;
    ll min = (1LL<<62);
    cin >> n;
    rep(i, 5){
        cin >> s[i];
        min = std::min(min, s[i]);
    }
    ll time = (std::ceil(1.0*n/min))+4;
    cout << time << endl;
}


Measured memory_bytes: 256
//By Vlgd
#include<bits/stdc++.h>
using namespace std;
const int INF=300000000;
const int N=100000;
int dis[N],n;
struct edge{int v,w;};
vector<edge>G[N];
queue<int>Q;
void bfs(int s){
	for(int i=0;i<n;i++) dis[i]=INF;
	Q.push(s);
	dis[s]=0;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(int v=0;v<G[u].size();v++){
			int x=G[u][v].v;
			if(dis[x]==INF){
				dis[x]=dis[u]+G[u][v].w;
				Q.push(x);
			}
		}
	}
}
main(){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int x,y,z;edge e;
		scanf("%d%d%d",&x,&y,&z);
		e.v=y;e.w=z;G[x].push_back(e);
		e.v=x;e.w=z;G[y].push_back(e);
	}
	int M=0,enter=0;
	bfs(0);
	for(int i=0;i<n;i++){
		if(dis[i]==INF) continue;
		if(M<dis[i]){
			M=dis[i];
			enter=i;
		}
	}
	bfs(enter);
	for(int i=0;i<n;i++){
		if(dis[i]==INF) continue;
		M=max(M,dis[i]);
	}
	printf("%d\n",M);
}  


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

#define ll long long

using namespace std;
const int OO = 0x3f3f3f3f, MOD = 1000000007;

int n, s;
ll mem[101][100005]; /// Idx, Sack
ll w[101], v[101];

ll solve(int idx = 0, int rw = s)
{
    ll& ret = mem[idx][rw];

    if(~ret) return ret;
    if(idx >= n || rw <= 0) return 0;

    ret = solve((idx + 1), rw);
    if(rw >= w[idx])
        ret = max(ret, solve((idx + 1), rw - w[idx]) + v[idx]);
    return ret;
}

int main()
{
    //freopen ("out.txt","w",stdout);

    cin >> n >> s;
    memset(mem, -1, sizeof mem);
    for(int i = 0;i < n; i++)
        cin >> w[i] >> v[i];

    cout << solve();

	return 0;
}


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

int main () {
  
  int A, B, K;
  cin >> A >> B >> K;
  
  for (int i = min(A, B); i > 0; i--) {
    if (A % i == 0 && B % i == 0) {
      K--;
      if (K == 0) {
        cout << i << endl;
        break;
      }
    }
  }
  
}

Measured memory_bytes: 256
import bisect
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [0]+a
b = [0]+b
ans = 0
for i in range(1, n):
    a[i+1] += a[i]
for i in range(1, m):
    b[i+1] += b[i]
for i in range(n+1):
    res = k - a[i]
    if res<0: continue
    index = bisect.bisect_right(b, res)
    ans = max(ans, index+i-1)
print(ans)

Measured memory_bytes: 40636
#include <cstdio>
#include <vector>
using namespace std;

int a[100005], par[100005], vi[100005], chk[100005];

int find(int x){
	return x == par[x] ? x : (par[x] = find(par[x]));
}

void link(int x, int y){
	int px = find(x), py = find(y);
	if(px != py) par[py] = px;
}

int main()
{
	int N, M; scanf("%d %d", &N, &M);
	for(int i = 1; i <= N; i++){
		scanf("%d", &a[i]);
		par[i] = i;
	}

	for(int i = 0, u, v; i < M; i++){
		scanf("%d %d", &u, &v);
		link(u, v);
	}

	vector<vector<int>> v;
	for(int i = 1; i <= N; i++){
		int px = find(i);
		if(!vi[px]){
			v.push_back(vector<int>());
			vi[px] = v.size();
		}
		v[vi[px] - 1].push_back(i);
	}

	int ans = 0, ts = 1;
	for(vector<int> &bucket : v){
		for(int idx : bucket) chk[idx] = ts;
		for(int idx : bucket) ans += (chk[a[idx]] == ts);
		ts++;
	}
	printf("%d\n", ans);
	return 0;
}

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

#define REP(i, n) for(decltype(n) i = 0; i < n; i++)

#define INF  (int)1e9
#define LINF (long long)1e18

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

bool check(const string& a, const string& b) {
    REP(i, a.size()) {
        if(a[i] != b[i] && a[i] != '?') {
            return false;
        }
    }

    return true;
}

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

    string S, T;
    std::cin >> S >> T;

    vector<string> ans_v;
    if(T.size() <= S.size()) {
        REP(i, S.size() - T.size() + 1) {
            if(check(S.substr(i, T.size()), T)) {
                auto s = S;
                s.replace(s.begin() + i, s.begin() + i + T.size(), T);
                REP(j, s.size()) {
                    s[j] = (s[j] == '?') ? 'a' : s[j];
                }
                ans_v.push_back(s);
            }
        }
    }

    if(!ans_v.empty()) {
        SORT(ans_v);
        std::cout << ans_v[0] << std::endl;
    }
    else {
        std::cout << "UNRESTORABLE" << std::endl;
    }

    return 0;
}


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

int solve(vector<int> a, int x){
	bitset<40000> aset;
	aset[20000] = 1;
	int n = a.size();
	for(int i = 0;i < n;i++){
		bitset<40000> bset;
		bset |= aset << a[i];
		bset |= aset >> a[i];
		swap(aset, bset);
	}
	if(aset[20000+x])return 1;
	return 0;
}

int main(){
	vector<int> a, b;
	string str;
	int f = 0, sum = 0, from, x, y;
	cin >> str >> x >> y;
	str.push_back('T');
	
	for(from = 0;from < str.size();from++, x--){
		if(str[from] == 'T')break;
	}
	for(int i = from;i < str.size();i++){
		if(str[i] == 'T' && sum){
			if(f == 0)a.push_back(sum);
			else b.push_back(sum);
			sum = 0;
		}
		if(str[i] == 'F')sum++;
		if(str[i] == 'T')f = !f;
	}
	
	int t1 = solve(a, x);
	int t2 = solve(b, y);
	if(t1 && t2)printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R

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

	long double a, b, c;
	cin >> a >> b >> c;
	cout << a * b / 2 << endl;
	return 0;
}

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

template <typename T>
class UnionFind {
 private:
  T _size;
  vector<T> _parent; // 親の番号（親自身はー（マイナス）集合要素の個数）

 public:
  // n要素で生成
  explicit UnionFind(T n) : _size{n}, _parent{vector<T>(n, -1)} {}

  // 木の根を求める
  T find(T x) {
    if (x < 0 || x >= _size) {
      return x;
    }

    if (_parent[x] < 0) {
      return x;
    }

    return _parent[x] = find(_parent[x]);
  }

  // xとyの属する集合を併合する
  bool unite(T x, T y) {
    if (x < 0 || x >= _size || y < 0 || y >= _size) {
      return false;
    }

    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }

    if (size(x) > size(y)) {
      _parent[x] += _parent[y];
      _parent[y] = x;
    } else {
      _parent[y] += _parent[x];
      _parent[x] = y;
    }

    return true;
  }

  // xとyが同じ集合に属するか
  bool same(T x, T y) {
    return find(x) == find(y);
  }

  // xの属する集合の個数を求める
  T size(T x) {
    if (x < 0 || x >= _size) {
      return 1;
    }

    return -_parent[find(x)];
  }

  // 全体の個数を求める
  T size() {
    return _size;
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i{}; i < M; ++i) {
    cin >> A[i] >> B[i];
    --A[i];
    --B[i];
  }

  UnionFind<int> uni(N);

  vector<long long> ans(M);
  ans[M - 1] = (long long) N * (N - 1) / 2;

  for (int i{M - 1}; i >= 1; --i) {
    ans[i - 1] = ans[i];
    if (uni.find(A[i]) != uni.find(B[i])) {
      ans[i - 1] -= (long long) uni.size(A[i]) * uni.size(B[i]);
      uni.unite(A[i], B[i]);
    }
  }

  for (int i{}; i < M; ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 3328
# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

# define pb push_back
# define fr first
# define sc second
# define mk make_pair
# define int long long

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;

typedef long long ll;

int n, t[N], a[N], x, y;

main(){
      cin >> n;

      for(int i = 1; i <= n; i ++){
            cin >> t[i] >> a[i];
            if(i == 1)
                  x = t[i], y = a[i];
            else{
                  int l = 1, r = 5e18 / max(a[i], t[i]);
                  while(r - l > 1){
                        int md = (l + r) >> 1;
                        if(a[i] * md >= y && t[i] * md >= x)
                              r = md;
                        else
                              l = md;
                  }
                  if(a[i] * l >= y && t[i] * l >= x)
                        r = l;
                  x = t[i] * r;
                  y = a[i] * r;
            }
      }

      cout << x + y << endl;
}


Measured memory_bytes: 2304
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    cout << (1000-n%1000)%1000 << endl;
}

Measured memory_bytes: 3652