akhauriyash/Code-Regression huggingface dataset:
# D - Equals
# https://atcoder.jp/contests/arc097/tasks/arc097_b

class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
#############################################
N,M=map(int,input().split())
p=list(map(int,input().split()))
x=[0]*M
y=[0]*M
UN=UnionFind(N)
for i in range(M):
    x[i],y[i]= map(int,input().split())
    UN.Unite(x[i],y[i])
    
cnt=0
for i in range(N):
    #print(p[i],i+1,UN.root[i])
    if UN.isSameGroup(i+1,p[i]):
        #print(i+1)
        cnt +=1
print(cnt)

Measured memory_bytes: 22908
#include<iostream>
using namespace std;
int main(){
	string s;
	long long k;
	cin>>s>>k;
	for(int i=0;i<s.size();i++){
		if(s[i]=='1'){
			k--;
		}else{
			cout<<s[i];
			break;
		}
		if(k==0){
			cout<<1;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(int i=1,i##_len=(n); i<=i##_len; ++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(obj) (obj).begin(), (obj).end()
#define maxs(x,y) (x=max((x),(y)))
#define mins(x,y) (x=min((x),(y)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define uni(x) x.erase(unique(rng(x)),x.end())
#define PQ(T) priority_queue<T,v(T),greater<T>>
#define dup(x,y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vp = vector<pii>;
template <class T> inline istream& operator>>(istream&i,v(T)&v)
{ rep(j,sz(v))i>>v[j];return i;}
template <class T> string join(const v(T)&v)
{ stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template <class T> inline ostream& operator<<(ostream&o,const v(T)&v)
{ if(sz(v))o<<join(v); return o;}
template <class T1,class T2> inline istream& operator>>(istream&i ,pair<T1,T2>&v)
{ return i>>v.fi>>v.se;}
template <class T1,class T2> inline ostream& operator<<(ostream&o ,pair<T1,T2>&v)
{ return o<<v.fi<<","<<v.se;}
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double eps = 1e-10;
bool comp(pii a,pii b){
  return a.se<b.se;
}
//----------------------------------------------------------------

#define fileio ifstream fio; if(argc>=2){fio.open(argv[1]); std::cin.rdbuf(fio.rdbuf());}
#define fastio ios_base::sync_with_stdio(false);
#define MOD 1000000007
//----------------------------------------------------------------
void Main(){
  int n;cin>>n;
  vl a(n),b(n);
  rep(i,n){
    cin>>a[i]>>b[i];
  }
  ll ans=0;
  drep(i,n){
    a[i]+=ans;
    ans += dup(a[i],b[i])*b[i]-a[i];
  }
  cout<<ans<<endl;
} int main(int argc,char* argv[]){ 
    fastio; fileio; Main();}

Measured memory_bytes: 1792
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

#define ll long long

using namespace std;


int main() {
    ll n;
    cin>>n;
    ll a[n];
    ll s = 0;
    ll m = 202020202024342;
    for(int i=0;i<n;i++){ 
        cin>>a[i];
        s+=a[i];
    }
    ll c= 0;
    for(int i=0;i<n;i++){
        m = min(m, max((s-c)-c, c-(s-c)));
        c+=a[i];
        m = min(m, max((s-c)-c, c-(s-c)));
    }
    cout<<m<<endl;

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}


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

using namespace std;
using ll = int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using tpi = tuple<int, int, int>;

using vqi = vector<queue<int>>;
using vpi = vector<pii>;
using bs = bitset<60>;
using vbi = vector<bs>;

ll gcd(ll a, ll b) {
    if (a < b) {
        swap(a, b);
    }

    /* ユークリッドの互除法 */
    ll r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

constexpr int64_t __pow_mod(int64_t n, int64_t p, int64_t mod) noexcept {
    if (p == 0) {
        return 1;
    }
    if (p % 2 == 0) {
        int64_t t = __pow_mod(n, p / 2, mod);
        return (t * t) % mod;
    }
    return (n * (__pow_mod(n, p - 1, mod) % mod)) % mod;
}

constexpr int64_t pow_mod(int64_t n, int64_t p, int64_t mod) noexcept {
    int64_t res = __pow_mod(n, p, mod);
    if (res == 0) {
        res = mod;
    }
    return res;
}

constexpr int64_t nCr_mod(int64_t n, int64_t r, int64_t mod) noexcept {
    int64_t count = 1;
    auto a = r;
    for (auto i = n; i > n - r; i--) {
        count *= i;
        if (count % mod != 0) {
            count %= mod;
        }
        int64_t inv = pow_mod(a, mod - 2, mod);
        count *= inv;
        if (count % mod != 0) {
            count %= mod;
        }
        a--;
    }
    return count;
}

const string YES = "Yes";
const string NO = "No";

void solve(std::string S) {
    if (S[0] == S[1] && S[1] == S[2]) {
        cout << NO << endl;
    } else {
        cout << YES << endl;
    }
}

int main() {
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXVAL = 100000;

int val;

int d[MAXVAL + 1];
priority_queue<pair<int, int> > pq;
void upd(int x, int cost) { if (cost >= d[x]) return; d[x] = cost; if (x < val) pq.push(MP(-cost, x)); }

// y=10x+dig-a*val

void run() {
	scanf("%d", &val);
	REPE(i, val) d[i] = INT_MAX; pq = priority_queue<pair<int, int> >();
	upd(0, 0);
	while (!pq.empty()) {
		int cost = -pq.top().first, x = pq.top().second; pq.pop();
		if (cost > d[x]) continue;
		REP(dig, 10) {
			int y = 10 * x + dig;
			while (y > val) y -= val;
			upd(y, cost + dig);
		}
	}
	printf("%d\n", d[val]);
}

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


Measured memory_bytes: 2804
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
	int t;
	cin >> t;
	bool flag = true;
	int i, x, y;
	cin >> i >> x >> y;
	if (i < (x + y) || (i & 1) != ((x + y) & 1))
	{
		flag = false;
	}
	int j, k, l;
	for (int o = 0; o < t-1; o++)
	{
		cin >> j >> k >> l;
		i = j - i;
		x = abs(x - k);
		y = abs(y - l);
		if (flag&&(i < (x + y) || (i & 1) != ((x + y) & 1)))
		{
			flag = false;
		}
	}
	if (flag)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input().split()[0])
p = list(map(int, input().split()))
c = 0

for i in range(1, n-1):
	if p[i-1]<p[i]<p[i+1] or p[i-1]>p[i]>p[i+1]:
		c+=1		
print(c)

Measured memory_bytes: 3064
import java.util.Scanner;
 
public class Main {

	public static final MyScanner in = new MyScanner();
	
	public static void main(String[] args) {

		int N = in.nextInt();
		String S = in.next();

		for(char c: S.toCharArray())
			System.out.print(rotateAlphas(c, N));

		System.out.println();

	}

	public static char rotateAlphas(char c, int num) {
		int p = c + num;
		if (p > 90) p = p - 26;
		return Character.toChars(p)[0];
	}

	public static class MyScanner{
		Scanner sc = new Scanner(System.in);
		String nextLine() {return sc.nextLine();}
		String next() {return sc.next();}
		int nextInt() {return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next());}
	}
}

Measured memory_bytes: 26556
#include<bits/stdc++.h>
#include<cmath>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
const ll MOD = 1e9+7;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
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; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
#define fs first
#define sc second


const int INF = 1e9;
const ll LLINF = 1e16;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
template<typename T>
T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T>
T ngcd(vector<T> a){
    T res;
    res = a[0];
    for(int i = 1; i < a.size() && res != 1; i++) {
        res = gcd(a[i], res);
    }
    return res;
}
 
template<typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

template<typename T>
T nlcm(vector<T> numbers) {
    T res;
    res = numbers[0];
    for (int i = 1; i < numbers.size(); i++) {
        res = lcm(res, numbers[i]);
    }
    return res;
}

// 割り算の切り上げ処理
template<typename T>
T round_up(T a, T b) {
  return (a + b - 1) / b;
}

// 約数列挙
template<typename T>
vector<T> calc_divisor(T n) {
   vector<T> res;
   for (T i = 1LL; i*i <= n; ++i) {
       if (n % i == 0) {
           res.push_back(i);
           T j = n / i;
           if (j != i) res.push_back(j);
       }
   }
   sort(res.begin(), res.end());
   return res;
}

// 素数判定
template<typename T>
bool isPrime(T x){
    T i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


using pint = pair<int, int>;
using pll = pair<ll, ll>;

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




int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll n;
    cin >> n;
    vector<ll> s(n);
    rep(i,n) cin >> s[i];
    sort(all(s));
    ll q;
    cin >> q;
    ll t;
    ll ans = 0;
    rep(i,q) {
        cin >> t;
        if(binary_search(all(s), t)) ans++;
    }
    print(ans);

}



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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

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

const ll INF=(ll)1e19;
//const int INF=(1<<30);
//const int INF=(1<<29);

int main(){
  int n,m;
  cin >> n >> m;
  map<int,int> mp;
  REP(i,m){
    int a,b;
    cin >> a >> b;
    mp[a]++; mp[b]++;
  }

  bool ok=true;
  for(auto v: mp){
    if(v.second%2!=0)ok=false;
  }
  cout << (ok ? "YES" : "NO") << endl;
}



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

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int n, q;
long long m;

int main() {
  cin >> n >> m >> q;
  vector<pair<int, int>> s[2];
  while(q--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    s[c].emplace_back(a, b);
  }
  dsu ss(n);
  int comp = n;
  for(auto u : s[0]) {
    comp -= ss.unite(u.first, u.second);
  }
  for(auto u : s[1]) {
    if(ss.get(u.first) == ss.get(u.second)) {
      cout << "No";
      return 0;
    }
  }
  long long L = n - (s[1].empty());
  long long R = (long long) comp * (comp - 1) / 2 + (n - comp);
  if(L <= m && m <= R) cout << "Yes";
  else cout << "No";
  return 0;
}


Measured memory_bytes: 1656
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
 
 
ll arr[100009];
 
int main(){
	int n;
	cin>>n;
	int ans = -1;
	for(ll i = 0 ; i < n ; i++){
		
		cin>>arr[i];
		if(arr[i] == 0) ans = 0;
	}
		
	if(ans == 0) cout<<"0\n";
	else {
		ll div = 1000000000000000000;
		ll mul = 1;
		for(int i = 0 ; i < n; i++) {
			div /= arr[i];
			if(div <= 0) {
				cout<<"-1\n"<<endl;
				return 0;
			}
			mul *= arr[i];
		}
		cout<<mul<<endl;
		
	}
}

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

inline void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

long long N, W, i;
long long w[100], v[100];
long long knapsack_1(long long, long long [], long long [], long long);

int main() {
    fastio();
    cin >> N >> W;
    for(i = 0; i < N; ++i) cin >> w[i] >> v[i];
    cout << knapsack_1(W, w, v, N);
	return(0);
}

long long knapsack_1(long long W, long long wt[], long long val[], long long n) {
    long long i, w, K[n+1][W+1];
    for(i = 0; i <= n; i++)
        for(w = 0; w <= W; w++)
            if(i == 0 || w == 0) K[i][w] = 0;
            else if(wt[i-1] > w) K[i][w] = K[i-1][w];
            else K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w]);
    return(K[n][W]);
}

Measured memory_bytes: 79104
import numpy as np
N, M, Q = map(int, input().split())
table = [[0] * N for _ in range(N)]
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[R][- L - 1] += 1
table = np.array(table, dtype=np.int64).cumsum(axis=0).cumsum(axis=1).tolist()
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[q][- p - 1])

Measured memory_bytes: 22324
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

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


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

int main(){
  int n;
  cin >> n;
  double a[n];
  double sum = 0;
  for(int i = 0;i < n;i++){
    cin >> a[i];
    sum += 1/a[i];
  }
  double ans = 1/sum;
  printf("%.30f\n",ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const long long INF=(1LL<<62);
const double inf=pow(10,10);
double pi=3.141592653589793;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const ll MOD = 1000000007;
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}
int MAX = 100000+10;
long long fac[100010], finv[100010], inv[100010];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 100010; 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;
    }
}

long long COM(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;
}

int main(){
	init();
	ll N,K;cin>>N>>K;
	vector<ll>l(N);
	for(int i=0;i<N;i++)cin>>l[i];
	sort(l.begin(),l.end(),greater<ll>());
	ll ans=0;
	for(int i=0;i<K;i++)ans+=l[i];
	cout<<ans<<endl;
}



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

using namespace std;

typedef long long ll;
#define mems(p) memset(p,-1,sizeof(p))
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define nl "\n"

const int mxN = 1e5;
const ll MOD = 1e9 + 7;

void fast()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}

int main() {
	fast();
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int ans =0;
	for (int i = 0; i < k; ++i) {
		ans += a[i];
	}
	cout << ans << nl;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 a, b, x;
  cin >> a >> b >> x;
  i64 ans = 1e9;
  for (i64 i = 0; i < 100; i++)
    for (i64 j = 0; j < 100; j++)
    {
      i64 cost = i * a + j * b;
      if (x <= i * 1000 + j * 500)
        ans = min(ans, cost);
    }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3080
//Compiler optimization
#pragma GCC optimize("Ofast")

//include
#include <bits/stdc++.h>
using namespace std;

//typedef
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef string S;
typedef queue<int> qi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vl> mat;

//macro
#define reverse(a) reverse(a.begin(),a.end())
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define fr(i,n)for(ll i=0;i<(n);i++)
#define ifr(i,n)for(ll i=(n)-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define each(x, v) for (auto &x : v)

//abbreviation
#define pb push_back
#define elif else if
#define mp make_pair
#define endl '\n'

//debug
#define debug(x) cerr << #x << ": " << x << endl
#define v_debug(v) cerr << #v << endl;fr(i,v.size()) cerr << i << ": " << v[i] << endl

//const
const  ll INF = 1e18;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    ll x = 0;
    fr(i,5){
        ll y;cin >> y;
        x += y;
    }
    cout << 15-x << endl;
}

Measured memory_bytes: 3572
#include <iostream>
using namespace std;
int main(){
  int64_t N,a,b;
  cin >> N >> a >> b;
  int64_t k=N/(a+b);
  int64_t h=N%(a+b);
  int64_t u=k*a+min(h,a);
  cout << u << endl;
}

Measured memory_bytes: 256
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	X = getlist()
	ans = 10000000000
	for i in range(1, 101):
		var = 0
		for j in range(N):
			var += (X[j] - i) ** 2

		ans = min(ans, var)

	print(ans)

if __name__ == '__main__':
	main()

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n;
	string s; cin>>s;
	int sz=s.size();
	for (int i=0; i<sz; i++)
		s[i]='A'+((s[i]-'A')+n)%26;
	cout<<s<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int digit_sum(int num){
	int sum = 0;
  	while(num > 0){
    	sum += num % 10;
      	num /= 10;
    }
  	return sum;
}

int main()
{
	int n, dsum;
  	scanf("%d", &n);
  	dsum = digit_sum(n);
	if (n % dsum == 0){
    	printf("Yes");
    } else {
    	printf("No");
    }
}

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;
const int INF = 2147483647;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
	bool ret = true;
	if (x < 2) {
		ret = false;
	}
	for (LL i = 2; i <= sqrt(x); i++) {
		if (x%i == 0) {
			ret = false;
		}
	}
	return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

int main(int argc, char const* argv[])
{
    int n;
    cin >> n;
    if (n < 1200) {
        cout << "ABC" << endl;
    }
    else if (n < 2800) {
        cout << "ARC" << endl;
    }
    else {
        cout << "AGC" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
a,b=input().split()
c,d=int(a),int(b)
l=[int(input()) for i in range(c)]
L=sorted(l)
x=L[d-1]-L[0]
for i in range(c-d+1):
    if L[d+i-1]-L[i]<x:
        x=L[d+i-1]-L[i]
print(x)

Measured memory_bytes: 8280
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

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


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll ans = b * d;
	ans = max(ans, a * c);
	if ((a <= 0 && 0 <= b) || (c <= 0 && 0 <= d)) {
		ans = max(ans, 0ll);
	}
	ans = max(ans, b * c);
	ans = max(ans, a * d);
	cout << ans << endl;
}


Measured memory_bytes: 3648
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N), B(N), C(N - 1);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i < N; i++) {
        cin >> B[i];
    }
    for (ll i = 0; i < N - 1; i++) {
        cin >> C[i];
    }

    ll ans = accumulate(B.begin(), B.end(), (ll)0);
    for (ll i = 0; i < N - 1; i++) {
        if (A[i + 1] == A[i] + 1) {
            ans += C[A[i] - 1];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
  
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <cassert>
#include <numeric>
#include <math.h>
#include <bitset>
#include <random>
#include <regex>

using namespace std;
  
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,f,n) for(int i=f;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(14)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;
constexpr int dy[] = {0,1,0,-1,1,-1,-1,1};
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
 
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class A, class B> inline A updiv(const A a,const B b){ return (a + b - 1) / b; }
template <class A, class B> inline A gcd(const A a,const B b){ return b ? gcd(b,a % b) : a; }
template <class A, class B> inline A lcm(const A a,const B b){ return a / gcd(a,b) * b; }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A,class B> using umap = unordered_map<A,B>;


signed main(void){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<int> a(m), b(m), c(m);

    rep(i,m){
        cin >> a[i] >> b[i];
        rep(j, b[i]){
            int x;
            cin >> x;
            c[i] |= 1 << x - 1;
        }
    }

    vector<int> dp(1 << n, LINF);

    dp[0] = 0;

    rep(bit, 1 << n){
        rep(i, m){
            chmin(dp[bit | c[i]], dp[bit] + a[i]);
        }
    }

    int ans = dp[(1 << n) - 1];

    if(ans == LINF){
        cout << -1 << '\n';
    }else{
        cout << ans << '\n';
    }

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <cstdio>
#include  <cstdlib>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long lint;
#define SZ(x) ((int)(x).size())


int main()
{
	char map[100][100];
	int h, w;
	int count = 0;
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
		}
	}

		bool a = false;//end_flg
		
	for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == '#') {
					//
					count++;
					if (i - 1 != -1 && map[i - 1][j] == '#') {
						continue;
					}
					else if (i + 1 != h && map[i + 1][j] == '#') {
						continue;
					}
					else if (j-1 != -1 && map[i ][j-1] == '#') {
						continue;
					}
					else if (j + 1 != w && map[i][j+ 1] == '#') {
						continue;
					}
					else {
						goto end;
					}
					
					//

				}
				
			}
		}
	



	cout << "Yes" << endl;
	return 0;
end://孤立した#があった場合
	cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n)     for(int i = 0;i < n;i++)
#define REPR(i, n)    for(int i = n;i >= 0;i--)
#define FOR(i, m, n)  for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VRSORT(v) sort(v.begin(), v.end(),greater<long long>());
#define ALL(X) (X).begin(),(X).end()
#define INF 99999999
#define M_PI 3.14159265358979323846
#define MOD 1000000007

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) os << "[" << el.first << " " << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

ll M,K;

void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    cin >> M >> K;
}

int solve(){
  if(K>=(1LL<<M)) {cout << -1 << endl; return 0;}
  if(M==0){
    if(K==0) {cout << 0 << " " << 0 << endl; return 0;}
    else {cout << -1 << endl; return 0;}
  }
  if(M==1){
    if(K==0) {cout << 0 << " " << 0  << " " << 1 << " " << 1 << endl; return 0;}
    else {cout << -1 << endl; return 0;}
  }

  for (ll i = 0; i < (1LL<<M); i++)
  {
    if(i==K) continue;
    cout << i << " ";
  }
  cout << K << " ";
  for (ll i = ((1LL<<M)-1LL); i >=0 ; i--)
  {
    if(i==K) continue;
    cout << i << " ";
  }
  cout << K << "\n";


  return 0;
}


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


Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
    int k,a,b;
    scanf("%d%d%d",&k,&a,&b);
    int m=0;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0){m++;}
    }
    if(m>0){printf("OK");}
    else {printf("NG");}
    return 0;
}

Measured memory_bytes: 1732
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <numeric>

/* debug macros */
#ifdef WAFDAYO
#define DBG_LINE() {std::cerr<<"\e[2m[L"<<__LINE__<<"]\e[m ";}
#define DBG_PRINT(s,t,u) {std::cerr<<(s)<<" \e[2m=\e[m \e[1m"<<(t)<<"\e[m"<<(u);}
#define SELECT_7TH(x1,x2,x3,x4,x5,x6,x7,...) x7
#define dbg1(x1) DBG_PRINT(#x1,x1,std::endl)
#define dbg2(x1,x2) DBG_PRINT(#x1,x1,", ")dbg1(x2)
#define dbg3(x1,x2,x3) DBG_PRINT(#x1,x1,", ")dbg2(x2,x3)
#define dbg4(x1,x2,x3,x4) DBG_PRINT(#x1,x1,", ")dbg3(x2,x3,x4)
#define dbg5(x1,x2,x3,x4,x5) DBG_PRINT(#x1,x1,", ")dbg4(x2,x3,x4,x5)
#define dbg6(x1,x2,x3,x4,x5,x6) DBG_PRINT(#x1,x1,", ")dbg5(x2,x3,x4,x5,x6)
#define dbg(...) DBG_LINE()\
SELECT_7TH(__VA_ARGS__,dbg6,dbg5,dbg4,dbg3,dbg2,dbg1)(__VA_ARGS__)
#else
#define dbg(...) {}
#endif

/* utility functions */
struct read_item{read_item(){};
template<class T>operator T(){T t;std::cin>>t;return t;}};
char splf(int i,int n){return(i+1<n)?' ':'\n';};
template<bool up>
struct _RI{int i;_RI(int a):i(a){}
int operator*(){return i;}void operator++(){i+=(up?1:-1);}
bool operator!=(const _RI& r){return up?i<r.i:i>=r.i;}};
template<bool up>
struct _RX{_RI<up> x,y;_RI<up> begin(){return x;}_RI<up> end(){return y;}
_RX(int a,int b):x(up?a:(a-1)),y(b){}_RX(int a):_RX(up?0:a,up?a:0){}};
typedef _RX<true> range;
typedef _RX<false> revrange;

/* types and constants */
typedef int64_t i64;
typedef uint64_t u64;
typedef __int128 i128;
// const i64 inf = (i64)1.05e18;
// const int inf = (int)1.05e9;

using namespace std;

i128 compute(i64 n, map<i64,i128>& memo, i64 a, i64 b, i64 c, i64 d) {

	if(n == 1) {
		return d;
	}
	if(memo.count(n) > 0) {
		return memo[n];
	}
	i128 x = (i128)n * d;
	memo[n] = x;

	i64 next3 = n / 3 * 3;
	i64 next5 = n / 5 * 5;

	if(n - next3 > (next3 + 3) - n) {
		next3 += 3;
	}
	if(n - next5 > (next5 + 5) - n) {
		next5 += 5;
	}

	if(n % 2 == 0) {
		i128 y = compute(n / 2, memo, a, b, c, d) + a;
		x = min(x, y);
	} else {
		i128 y1 = compute((n - 1) / 2, memo, a, b, c, d) + a + d;
		i128 y2 = compute((n + 1) / 2, memo, a, b, c, d) + a + d;
		x = min(x, min(y1, y2));
	}

	i128 y3 = compute(next3 / 3, memo, a, b, c, d) + d * abs(next3 - n) + b;
	i128 y5 = compute(next5 / 5, memo, a, b, c, d) + d * abs(next5 - n) + c;
	x = min(x, min(y3, y5));

	return memo[n] = x;
}

void solve() {

	const i64 N = read_item();
	const i64 A = read_item();
	const i64 B = read_item();
	const i64 C = read_item();
	const i64 D = read_item();

	map<i64,i128> memo;
	i64 ans = compute(N, memo, A, B, C, D);
	printf("%lld\n", ans);
}

int main() {

	const int T = read_item();
	for(auto i : range(T)) {
		solve();
	}

	return 0;
}

/* wafdayo~~~ */


Measured memory_bytes: 4584
#include<bits/stdc++.h>
inline int read(){
	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
	int k=1,kk=0;if (c=='-')c=getchar(),k=-1;
	while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(int x){if (x<0)putchar('-'),x=-x;if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(int x){write(x);puts("");}
int n,k,kk,x,y,xx,yy,xxx,yyy,a[3000][3000],b[3000][3000],ans ;
char c;
signed main(){
	n=read();k=read();kk=k*2;
	for (int i=1;i<=n;i++){
		x=read();y=read();c=getchar();while (c!='B'&&c!='W')c=getchar();
		if (c=='B')a[x%kk+1][y%kk+1]++;else b[x%kk+1][y%kk+1]++;
	}for (int i=1;i<=kk;i++)for (int j=1;j<=kk;j++)
		a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1],b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];
	for (int i=1;i<=k;i++)
		for (int j=1;j<=k;j++){
			xx=a[kk][kk]-a[i+k-1][kk]-a[kk][j+k-1]+a[i+k-1][j+k-1]*2+a[i-1][kk]+a[kk][j-1]-a[i+k-1][j-1]*2-a[i-1][j+k-1]*2+a[i-1][j-1]*2;
			xxx=a[kk][kk]-xx;
			yy=b[kk][kk]-b[i+k-1][kk]-b[kk][j+k-1]+b[i+k-1][j+k-1]*2+b[i-1][kk]+b[kk][j-1]-b[i+k-1][j-1]*2-b[i-1][j+k-1]*2+b[i-1][j-1]*2;
			yyy=b[kk][kk]-yy;
			ans=max(ans,max(xx+yyy,xxx+yy));
		}writeln(ans);
}



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

int main(){
 int A, B;
 cin >> A >> B;
  int count=0;
  for(int i=A;i<=B;i++){
  if((i/10000 ==i%10) && ((i/1000)%10==(i/10)%10  ))
    count+=1;
  }
  cout<<count<<endl;
}

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

uint64_t K, N;

struct sushi
{
	uint64_t kind;
	uint64_t value;
	bool use_flag;

	sushi(uint64_t k, uint64_t v)
	{
		kind = k;
		value = v;
		use_flag = false;
	}

	bool operator<(const sushi &another) const
	{
		return value < another.value;
	}

	bool operator>(const sushi &another) const
	{
		return value > another.value;
	}

};

int main()
{
	uint64_t max_ans = 0;
	vector<sushi> s;

	// データ読み込み
	cin >> N >> K;

	uint64_t a, b;

	for (uint64_t i = 0; i < N; i++)
	{
		cin >> a >> b;
		s.push_back(sushi(a, b));

	}

	// value順に並び替え
	sort(s.begin(), s.end(), greater<>());

	// 暫定topを計算：種類MAXで最大のvalueを選択
	uint64_t c = 0;
	map<uint64_t, uint32_t> eat_kind;
	vector<uint32_t> eat;

	// 得点計算用
	uint64_t ans1 = 0;

	for (uint32_t i = 0; i < N; i++)
	{
		// すべて違う種類の寿司を食べる
		if (eat_kind.count(s[i].kind) == 0)
		{
			ans1 += s[i].value;
			s[i].use_flag = true;
			eat_kind[s[i].kind] = 1;
			eat.push_back(i);
			c++;
		}

		if (c >= K)
		{
			break;
		}
	}

	// c < Kの場合、価値の高いものをc>=Kとなるまで設定する
	for (uint32_t i = 0; i < N; i++)
	{
		if (c >= K)
		{
			break;
		}

		if (s[i].use_flag == false)
		{
			ans1 += s[i].value;
			s[i].use_flag = true;
			eat_kind[s[i].kind]++;
			eat.push_back(i);
			c++;
		}
	}

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

	max_ans = ans1 + eat_kind.size() * eat_kind.size();

	// valueの高いものを採用し、暫定topより高くなれば続ける。高くならなければEND
	uint64_t tmp_ans = 0;
	for (uint32_t i = 0; i < N; i++)
	{
		if (s[i].use_flag == false)
		{
			s[i].use_flag = true;
			s[eat.back()].use_flag = false;
			ans1 = ans1 - s[eat.back()].value + s[i].value;
			eat_kind[s[eat.back()].kind]--;
			if (eat_kind[s[eat.back()].kind] == 0)
			{
				eat_kind.erase(s[eat.back()].kind);
			}

			eat.pop_back();
			eat.insert(eat.begin(), i);
			tmp_ans = ans1 + eat_kind.size() * eat_kind.size();
			if (max_ans > tmp_ans)
			{
				break;
			}
			max_ans = tmp_ans;
		}
	}

	cout << max_ans << endl;
	return(0);
}


Measured memory_bytes: 7792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> i_i;

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((int)(x).size())

const double PI  = acos(-1.0);
const double EPS = 1e-9;
const ll INF = 1e9+10;
const ll mod = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define print(x) cerr << #x << " is " << x << endl;
//#define print(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 

ll get_times(ll x, ll A)
{
    return (x + A - 1)/A;
}

int main() {
    ll N, D, A, ans = 0;
    cin >> N >> D >> A;
    vector<P> C(N);
    vector<ll> X(N), H(N), Y(N);
    
    rep(i, N){
        ll a, b;
        cin >> a >> b;
        C[i] = make_pair(a, b);
    }
    sort(ALL(C));
    rep(i, N){
        X[i] = C[i].first;
        H[i] = C[i].second;
        //cout << X[i] << " " << H[i] << endl;
        
    }
    
    
    //vector<ll> queue(N + 1);
    queue<int> q;
    ll minus = 0;
    for (int i = 0; i < N; i++){
        while(!q.empty() && X[q.front()] + 2 * D < X[i]){
            minus -= Y[q.front()];
            q.pop();
        }
        if (H[i] - minus * A > 0){
            q.push(i);
            Y[i] = get_times(H[i] - minus * A, A);
            minus += Y[i];
            ans += Y[i];
        }
    }
    cout << ans;
    return 0;
}


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

int main() {
    i64 n, q;
    std::string s;
    std::cin >> n >> s >> q;
    std::vector<i64> b(n + 1), bc(n + 1), c(n + 1);
    for (int i = 0; i < s.size(); i++) {
        b[i + 1] = b[i] + (s[i] == 'M');
        c[i + 1] = c[i] + (s[i] == 'C');
        bc[i + 1] = bc[i] + (s[i] == 'C' ? b[i] : 0);
    }

    i64 k;
    for (; q--;) {
        std::cin >> k;
        i64 ret = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != 'D') continue;
            auto last = std::min(i + k, n);
            ret += bc[last] - bc[i + 1] - b[i + 1] * (c[last] - c[i + 1]);
        }
        std::cout << ret << std::endl;
    }

    return 0;
}

Measured memory_bytes: 24836
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(){
    long long int N,Y;
    cin >> N >> Y; 
    long long int A=1000,B=5000,C=10000;
    bool exist=false;
    long long int res1=-1;
    long long int res2=-1;
    long long int res3=-1;
    for(int i=0;i<=N;++i){
     for(int j=0;j<=N-i;++j){
        if(A*i+B*j+C*(N-i-j)==Y){
            res1=i;
            res2=j;
            res3=N-i-j;
            break;
        }
    }
    }
        cout << res3 << " " << res2 << " " << res1;
    }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
typedef long long ll;

using namespace std;
int gcm(int n, int m) {
    if (m > n) {
        swap(m, n);
    }
    int d = n%m;
    if (d == 0) {
        return m;
    }
    return gcm(m, d);
}

int main() {
    ll N, M; cin >> N >> M;
    string s, t;
    cin >> s;
    cin >> t;
    
    ll g = gcm(N, M);
    ll i = N/g;
    ll j = M/g;
    for (int mul = 0; mul < g; mul++) {
        ll x = mul *i; ll y = mul *j;
        if (s[x] != t[y]) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << N/g*M<< endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
#define edge(u) for(re int i=head[u];i;i=e[i].nxt)
using namespace std; 
const int N=1e5+5;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int n,head[N],deg[N],val[N],cnt,num,ans,a[N],b[N],dep[N];
char s[N];
bool del[N];
struct edge{
	int to,nxt;
}e[N<<1];
void add(int a,int b){
	e[++cnt].to=b;
	e[cnt].nxt=head[a];
	head[a]=cnt;
	deg[b]++;
}
void init(){
	queue<int> q;
	inc(i,1,n) if(deg[i]==1&&s[i]=='B') q.push(i);
	while(q.size()){
		int u=q.front();q.pop();
		del[u]=1;
		edge(u){
			int v=e[i].to;
			if(--deg[v]==1&&s[v]=='B') q.push(v);
		}
	}
	memset(head,0,sizeof(head)),cnt=0;
	memset(deg,0,sizeof(deg));
	inc(i,1,n-1){
		if(del[a[i]]||del[b[i]]) continue;
		add(a[i],b[i]),add(b[i],a[i]);
	}
	inc(i,1,n){
		if(del[i]) continue;
		if((s[i]=='B'&&deg[i]%2==1)||(s[i]=='W'&&deg[i]%2==0)){
			val[i]=2;
			num++;
		}
	}
}
void dfs(int u,int f){
	dep[u]=val[u];
	edge(u){
		int v=e[i].to;
		if(v==f) continue;
		dfs(v,u);
		ans=max(ans,dep[u]+dep[v]);
		dep[u]=max(dep[u],dep[v]+val[u]);
	}
}
int main(){
	n=read();
	inc(i,1,n-1){
		a[i]=read(),b[i]=read();
		add(a[i],b[i]),add(b[i],a[i]);
	}
	scanf("%s",s+1);
	init();
	inc(i,1,n){
		if(del[i]) continue;
		dfs(i,0);
		break;
	}
	printf("%d",cnt+num-ans);
}

Measured memory_bytes: 8448
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

const int N = 200005;
long long fact[N];
long long invfact[N];
long long inv[N];

void init() {
	fact[0] = fact[1] = 1;
	for (int i = 2; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
	inv[1] = 1;
	for (int i = 2; i < N; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
	invfact[0] = invfact[1] = 1;
	for (int i = 2; i < N; i++) invfact[i] = invfact[i - 1] * inv[i] % MOD;
}

LL nCr(LL n, LL r) {
	if (n < r || r < 0)return 0;
	return (((fact[n] * invfact[r]) % MOD) * invfact[n - r]) % MOD;
}

int main() {
	LL n, m, k;
	cin >> n >> m >> k;
	init();
	LL cc = nCr(m * n - 2, k - 2);
	LL x1 = (m * m) % MOD;
	LL x2 = ((n * (n - 1) * (n + 1)) / 6) % MOD;
	LL y1 = (n * n) % MOD;
	LL y2 = ((m * (m - 1) * (m + 1)) / 6) % MOD;
	cout << (((x1*x2 + y1*y2) % MOD) * cc)%MOD << endl;
	return 0;
}

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

int g[10][10];
int main()
{
    int n, m; cin>>n>>m;
    while (m--) {
        int a, b; cin>>a>>b;
        --a, --b;
        g[a][b]=g[b][a]=1;
    }

    int a[n];
    for(int i=0; i<n; ++i) a[i]=i;

    int res=0;
    do {
        bool ok=true;
        for(int i=1; i<n; ++i) if (!g[a[i]][a[i-1]]) ok=false;
        if (ok) ++res;
    } while (next_permutation(a+1, a+n));
    cout<<res<<endl;
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

h, n = ril()
ls = rils(n)
dp = [float('inf')] * (h + 1)
dp[0] = 0
for i, (a, b) in enumerate(ls):
    for j in range(h + 1):
        dp[min(j + a, h)] = min(dp[min(j + a, h)], dp[j] + b)
print(dp[-1])

Measured memory_bytes: 50780