akhauriyash/Code-Regression huggingface dataset:
a = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

n = int(input())
s = input()

x = list(s)

for i in range(0,len(s)):
  for j in range(0,len(a)):
    if(x[i] == a[j]):
      t = j
      x[i] = a[t+n]
      break
b = ''.join(x)
print(b)

Measured memory_bytes: 39920
#include <iostream>
#include <set>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#include <iostream> 
using namespace __gnu_pbds; 
using namespace std; 
  

typedef tree<long long, null_type, less<long long>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set; 
 
const long long MAXN = 2e5+5;
long long ans = 0;
set<long long> s1[40];
long long tot;
bool foundodd;
long long arrptr[MAXN];
bool visited[MAXN];
long long l;
long long mid;
string str2;
int main(){
    
    string s;
    cin>>s;
    long long n = s.length();
    for(long long i=0;i<n;i++){
        s1[s[i]-'a'].insert(i);
        str2+=" ";
    }
    for(long long i=0;i<26;i++){
        if(s1[i].size()%2 == 1 && foundodd){
            cout<<-1<<endl;
            return 0;
        }else if(s1[i].size()%2 == 1){
            foundodd = true;
         
        }
    }
    if(n%2 == 1){
        mid = (n/2);
    }
    long long r = n-1;
    for(long long i=0;i<n;i++){
        
        if(visited[i]){
            continue;
        }
       
        if(s1[s[i]-'a'].size()==1){
            str2[mid] = s[i];
            arrptr[i] = mid;
            tot++;
            continue;
        }
        auto hold = s1[s[i]-'a'].end();
        hold--;
        long long pos = *hold;
        visited[pos] = true;
        str2[l] =s[i];
        str2[r] =s[pos];
         arrptr[i] = l;
         arrptr[pos] = r;
        l++;
        r--;
        s1[s[i]-'a'].erase(s1[s[i]-'a'].find(i));
        s1[s[i]-'a'].erase(s1[s[i]-'a'].find(pos));
       
        
    }
    new_data_set p; 
    //cout<<s<<endl;
    //cout<<str2<<endl;
    for(long long i=0;i<n;i++){
        
        p.insert(arrptr[i]);
        ans+=(p.size()-p.order_of_key(arrptr[i])-1);
        //cout<<i<<" "<<arrptr[i]<<" "<<p.order_of_key(arrptr[i])<<" "<<ans<<endl;
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 14852
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#define inf 0x3f3f3f3f
#define maxn 1520
#define maxe 200010
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll ans=0;
    while(n)
    {
        n>>=1;
        ans=2*ans+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int dp[10001]={0};
    int N,W;
    cin>>N>>W;
    int v,w;
    for(int i=0;i<N;i++){
        cin>>v>>w;
        for(int j=0;j<=W;j++){
            if(j>=w){
  //???????????????????????¨?????????????????????????????§????????????value????±???????????????????
 //????????¨???????????\?????????????????????????????????????????????????????¢?????????????±????????????????
 //??????????????§?????????????????£?¶???§?????????????????????????????????????????????????????¨?????????????????§?????????
 //????????????????????????I?????????????????¨????????¢?????´???????????§????????????????????¨??????????????????????????????
 //?????£?????????????????????????????????????????????????????????????????§???????????§???
 //???????????????????????????????????????????????§??????????????????????¨±???????¨±???????????????????????????
 //???????????¨??????OK?????????????????????????????????????????´?????§??????????????????
 //?????????????¬?????????¨??????????????????????????´?????§????????????????????????????????????????????????
 //?¨???????????????¨?????¢??°?£???¶?????????????????¨???????????¨???
            	dp[j] = max(dp[j-w]+v,dp[j]);
            }
        }
    }
    cout<<dp[W]<<endl;
    return 0;
}

Measured memory_bytes: 3148
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int sum =0;
    int v[n],c[n];
    for (int i=0;i<n;i++){
        cin >> v[i];
    }
    for (int j=0;j<n;j++){
        cin >> c[j];
    }
    for (int k=0;k<n;k++){
        int diff = v[k]-c[k];
        if (diff >0){
            sum +=diff;
        }
    }
    cout << sum<< endl;
}


Measured memory_bytes: 256
strToInt :: String -> Int
strToInt x = read x :: Int

leadAns :: Int -> Int -> Int -> Int -> Int
leadAns n k x y 
    | n==1 = x
    | n > k = y + leadAns (n-1) k x y
    | otherwise = x + leadAns (n-1) k x y

main = do
    inn <- getLine
    ink <- getLine
    inx <- getLine
    iny <- getLine
    let n = read inn :: Int
        k = read ink :: Int
        x = read inx :: Int
        y = read iny :: Int
    putStrLn $ show $ leadAns n k x y
    

Measured memory_bytes: 636
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

int main(void) {
    map<Int,Int> A;
    Int N,M;
    cin>>N>>M;
    vector<pair<Int,Int> > sA;

    for(int i = 0;i < N;i++) {
        Int a;
        cin>>a;
        sA.push_back(make_pair(a,1));
        A[a]++;
    }

    for(int i = 0;i < M;i++) {
        Int b,c;
        cin>>b>>c;
        sA.push_back(make_pair(c,b));
        A[c]+=b;
    }

    Int count = 0;
    Int sum = 0;
    sort(sA.begin(),sA.end());
    for(int i = sA.size()-1;i >= 0 && count < N;i--) {
        if(count + sA[i].second <= N) {
            sum += sA[i].first*sA[i].second;
            count += sA[i].second;
        } else {
            sum += (N-count)*sA[i].first;
            count = N;
        }
    }

    /*
    for(map<Int,Int>::iterator it = A.rbegin();it != A.rend() && count < N;it++) {
        cout<<it->first<<" "<<it->second<<endl;
        if(count+it->second < N) {
            sum += it->first*it->second;
            count += it->second;
        } else {
            sum += (N-count)*(it->first);
            count = N;
        }
    }
    if(count < N) {
        map<Int,Int>::iterator it = A.begin();
        sum += (N-count)*(it->first);
    }
    */

    cout<<sum<<endl;

    return 0;
}



Measured memory_bytes: 16620
s = input()

n = int(len(s))

n1 = int ( (n - 1 ) / 2 )
n2 = int ( (n + 1 ) / 2 )

s1 = s[0:n1]
s2 = s[n2:n]

def if_kai( st ):
  ret = True
  nn = len(st)
  nn1 = int ( (nn - 1 ) / 2 )
  for i in range(nn1+1):
    if st[i] != st[nn-i-1] :
       ret = False
       break
  return ret      

if if_kai( s ) and if_kai( s1 ) and if_kai( s2 ) :
  print('Yes')
else:
  print('No')


Measured memory_bytes: 3064
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		final int N = sc.nextInt();
		final int X = sc.nextInt();
		int x[] = new int[N];
		for(int i = 0; i < N; i ++) {
			x[i] = sc.nextInt();
		}
		int minNum = 0;
		for(int i = 0; i < N; i ++) {
			if(i == 0) {
				minNum = Math.abs(X - x[i]);
			} else {
				minNum = Math.min(minNum, Math.abs(X - x[i]));
			}
		}
		
		boolean flag = true;
		
		int answer = Integer.MAX_VALUE;
		
		for(int i = 0; i < N; i ++) {
			answer = Math.min(gcd(Math.abs(X - x[i]), minNum), answer);
		}
		System.out.println(answer);
	}
	
	private static int gcd(int m, int n) {
	    if(m < n) return gcd(n, m);
	    if(n == 0) return m;
	    return gcd(n, m % n);
	}
}


Measured memory_bytes: 48680
#include <bits/stdc++.h>
using namespace std;
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

int dp[2][20010],*now = dp[0],*nxt = dp[1];

signed main(){
	int h,n,a[1010],b[1010];
	cin >> h >> n;
	for(int i = 0;i < n;i++) cin >> a[i] >> b[i];
	for(int i = 0;i <= 20000;i++) now[i] = nxt[i] = INF;
	now[0] = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j <= 20000;j++) nxt[j] = INF;
		for(int j = 0;j <= 20000;j++){
			if(j >= a[i]) nxt[j] = min(nxt[j - a[i]] + b[i],now[j]);
			else nxt[j] = now[j];
		}
		swap(now,nxt);
	}
	int mi = INF;
	for(int i = h;i <= 20000;i++) chmin(mi,now[i]);
	cout << mi << endl;
}

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

// Union-Find, 0-indexed
struct UnionFind {
    int size; // 木の数
    UnionFind(int N) : par(N), scale1(N,1), size(N){
        iota(par.begin(), par.end(), 0);
    }

    // xの木とyの木を併合
    void unite(int x, int y){
        int rx = root(x), ry = root(y);
        if (rx == ry) return;
        par[ry] = rx;
        scale1[rx] += scale1[ry];
        size--;
    }

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

    // xの属する木の要素の数を返す関数
    int scale(int x){ return scale1[root(x)];}

private:
    vector<int> par, scale1;
    int root(int x){
        if (par[x] == x) return x;
        par[x] = root(par[x]);
        return par[x];
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    UnionFind tree(N+1);
    vector<vector<int>>graphF(N+1);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b;
        tree.unite(a, b);
        graphF[a].push_back(b);
        graphF[b].push_back(a);
    }
    vector<vector<int>>graphB(N+1);
    for (int i = 0; i < K; ++i) {
        int a, b; cin >> a >> b;
        graphB[a].push_back(b);
        graphB[b].push_back(a);
    }
    for (int i = 1; i <= N; ++i) {
        int ans = tree.scale(i) - 1;
        for (auto x: graphB[i]) {
            if (tree.same(i, x)) ans--;
        }
        for (auto x: graphF[i]) {
            if (tree.same(i, x)) ans--;
        }
        cout << ans << " ";
    }
    return 0;
}

Measured memory_bytes: 13432
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
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))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int xa, va, xb, vb, t;

bool solve() {
	if (xa > xb) xa = -xa, xb = -xb;
	int dx = xb - xa;
	if (vb >= va) return false;
	int dv = va - vb;
	return (ll)dv * t >= dx;
}

void run() {
	scanf("%d%d%d%d%d", &xa, &va, &xb, &vb, &t);
	printf("%s\n", solve() ? "YES" : "NO");
}

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


Measured memory_bytes: 3764
#include<bits/stdc++.h>
#define int long long 
using namespace std;
vector<int> vet;
const int ms =50;



main(){
	int n,k;
	cin >> n >> k;
	vet.resize(n);
	for(int i= 0;i<n;i++) cin >> vet[i];
	int soma =0;
	int base = 1;
	int num=0,val=0;
	
	
	
	for(int i = ms;i>=0;i-- ){
		int u=0,b=0;
		for(auto &it: vet){
			if(it&(1LL<<i))
				u++;
			else
				b++;
		}
		
		if( b > u and val + (1LL<<i) <= k){
			soma += b*(1LL<<i);
			val += (1LL<<i);
		}else
			soma += (u)*(1LL<<i);
			
	}
	cout<<soma<<endl;
}


Measured memory_bytes: 1024
from collections import *

N = input()
v_list = input().split()

if len(set(v_list)) == 1:
    print(len(v_list) // 2)
    exit()

v1_count_list = Counter(v_list[::2]).most_common(2)
v2_count_list = Counter(v_list[1::2]).most_common(2)

if v1_count_list[0][0] != v2_count_list[0][0]:
    leave_value = v1_count_list[0][1] + v2_count_list[0][1]
else:
    leave_value = max(v1_count_list[1][1] + v2_count_list[0][1], v1_count_list[0][1] + v2_count_list[1][1])
print(len(v_list) - leave_value)

Measured memory_bytes: 16884
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
a=int(input())
b=list(map(int,input().split()))
n=lcm_list(b)
m=0
for i in b:
    m+=n//i
print(n/m)

Measured memory_bytes: 9584
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(a) cout << #a << ": " << a << endl
#define sz(a) int(a.size())
#define rep(i,n) for(int i=0;i<n;i++)
#define forr(i, st, en) for(int i = st; i < en; i++)
#define all(v) (v).begin(),(v).end()
#define fast cin.tie(0); ios::sync_with_stdio(false)

int32_t main(){ fast;
	//string s; cin>>s;
	int a, b, c; cin>>a>>b>>c;
	swap(a, b);
	swap(a, c);
	cout<<a<<" "<<b<< " "<<c<<endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    int[] mt = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    boolean uru1, uru2;
    int y1, m1, d1, y2, m2, d2;
    int ans;

    void run(){
	while(sc.hasNext()){
	    y1 = sc.nextInt();
	    m1 = sc.nextInt();
	    d1 = sc.nextInt();
	    y2 = sc.nextInt();
	    m2 = sc.nextInt();
	    d2 = sc.nextInt();
	    if(y1>0 && m1>0 && d1>0 && y2>0 && m2>0 && d2>0){
		uru1 = uru(y1);
		if(uru1) mt[2] = 29;
		else mt[2] = 28;
		ans = 0;
		solve();
	    }
	}
    }

    void solve(){
	while(y1!=y2 || m1!=m2 || d1!=d2){	   
	    ans++;
	    d1++;
	    if(d1 > mt[m1]){
		d1 = 1;
		m1++;
		if(m1 > 12){
		    m1 = 1;
		    y1++;
		    uru1 = uru(y1);
		    if(uru1) mt[2] = 29;
		    else mt[2] = 28;   
		    //System.out.println(y1+" "+mt[2]);
		}
	    }
	}
	System.out.println(ans);
    }

    boolean uru(int y){
	if(y%4==0){
	    if(y%100==0){
		if(y%400==0) 
		    return true;
		return false;
	    }
	    return true;
	}
	return false;
    }
}

Measured memory_bytes: 21576
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N, K = map(int, sys.stdin.readline().rstrip().split(" "))
Vs = list(map(int, sys.stdin.readline().rstrip().split(" ")))
result = 0
for L in range(min(N + 1, K + 1)):
    for R in range(min(N + 1 - L, K + 1 - L)):
        gems = Vs[:L]
        if R > 0:
            gems += Vs[-R:]

        gems.sort()
        rest = K - L - R
        # print(L, R, gems)
        for _ in range(rest):
            if len(gems) > 0 and gems[0] < 0:
                gems.pop(0)
            else:
                break
        # print(gems, sum(gems))
        result = max(result, sum(gems))
print(result)
exit(0)


Measured memory_bytes: 3440
/*
Where is frankenstein??
▒▒▒▒▒▒▐███████▌
▒▒▒▒▒▒▐░▀░▀░▀░▌
▒▒▒▒▒▒▐▄▄▄▄▄▄▄▌
▄▀▀▀█▒▐░▀▀▄▀▀░▌▒█▀▀▀▄
▌▌▌▌▐▒▄▌░▄▄▄░▐▄▒▌▐▐▐▐

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <sstream>
#include <cstring>
#include <numeric>
#include <ctime>
#include <cassert>
#include <random>
#include <valarray>
//#include <fstream>
#define re return
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define y0 y32479
#define y1 y95874
#define next next239
#define prev prev239
#define fill(x, y) memset(x, y, sizeof(x))
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(abs(x))
#define unq(x) (x.resize(unique(all(x)) - x.begin()))
#define ba back()
#define popcount __builtin_popcountll
#define fastIO()                 \
    {                            \
        ios::sync_with_stdio(0); \
        cin.tie(0);              \
        cout.tie(0);             \
    }
#define in(x) \
    int x;    \
    cin >> x;
#define in1(x) \
    int x;     \
    cin >> x;  \
    x--;
#define inll(x) \
    ll x;       \
    cin >> x;
#define ins(x) \
    string x;  \
    cin >> x;

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef pair<double, double> pdd;
typedef long double LD;
typedef double D;

int main()
{
    inll(n);

    ll ans=0;

    ans=(n/500)*1000;

    n=n%500;
    ans+=(n/5)*5;

    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())

static const int MAX = 10000;
static const int INFTY = (1 << 20);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int>> adj[MAX];

void dijkstra() {
    priority_queue<pair<int, int>> PQ;
    int color[MAX];
    int d[MAX];
    for (int i = 0; i < n; i++) {
        d[i] = INFTY;
        color[i] = WHITE;
    }
    d[0] = 0;
    PQ.push(make_pair(0, 0));
    color[0] = GRAY;
    while (!PQ.empty()) {
        pair<int, int> f = PQ.top();
        PQ.pop();
        int u = f.second;
        color[u] = BLACK;
        if (d[u] < f.first * (-1)){
            continue;
        }
        for (int j = 0; j < adj[u].size(); j++) {
            int v = adj[u][j].first;
            if (color[v] == BLACK) {
                continue;
            }
            if (d[v] > d[u] + adj[u][j].second) {
                d[v] = d[u] + adj[u][j].second;
                PQ.push(make_pair(d[v] * (-1), v));
                color[v] = GRAY;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
    }
}

int main() {
    int k, u, v, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            cin >> v >> c;
            adj[u].push_back(make_pair(v, c));   
        }
    }
    dijkstra();
    return 0;
}


Measured memory_bytes: 7976
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<functional>
using namespace std;
int main(void) {
    
   
   int n;
   cin>>n;
   int a[1000];
   for(int i=0;i<n;i++){
       cin>>a[i];
   }

   sort(a,a+n);
    cout<<a[n-1]-a[0]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e9;

/* BIT: RAQ対応BIT
    初期値は a_1 = a_2 = ... = a_n = 0
    ・add(l,r,x): [l,r) に x を加算する
    ・sum(i): a_1 + a_2 + ... + a_i を計算する
    計算量は全て O(logn)
*/
template <typename T>
struct BIT {
    ll n;             // 要素数
    vector<T> bit[2];  // データの格納先
    BIT(ll n_) { init(n_); }
    void init(ll n_) {
        n = n_ + 1;
        for (ll p = 0; p < 2; p++) bit[p].assign(n, 0);
    }
    void add_sub(ll p, ll i, T x) {
        for (ll idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(ll l, ll r, T x) {  // [l,r) に加算
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }
    T sum_sub(ll p, ll i) {
        T s(0);
        for (ll idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(ll i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
};

//入力
ll n,d,a;
vector<P>x;

//二分探索
// index が条件を満たすかどうか
bool isOK(ll mid,ll id) {
    ll r = x[id].first + 2*d;
    if(x[mid].first<=r)return true;
    else return false;
}
// 汎用的な二分探索のテンプレ
ll binary_search(ll id) {
    ll ok = id; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll ng = n; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;

        if (isOK(mid,id)) ok = mid;
        else ng = mid;
    }
    return ok;
}

int main(){
    cin >> n >> d >> a;
    
    x.resize(n);
    vector<ll>attack(n+1);
    rep(i,n){
        ll a,b;
        cin >> a >> b;
        x[i]={a,b};
    }
    sort(x.begin(),x.end());
    rep(i,n){
        attack[i]=binary_search(i);
    }

    BIT<ll>bit(n);
    rep(i,n){
        bit.add(i+1,i+2,x[i].second);
    }
    ll ans = 0;
    rep(i,n){
        if(bit.sum(i+1)-bit.sum(i)>0){
            ll now = bit.sum(i+1)-bit.sum(i);
            ll c = (now+a-1)/a;
            bit.add(i+1,attack[i]+2,-a*c);
            ans+=c;
        }
    }
    cout << ans << endl;
    return 0;
}


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

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;

const int MAX_V = 12, MAX_L = 2505;
const int INF = 1e+9+1;

int  V,E;
int G[MAX_V][MAX_V];


//弗洛伊德模板题
void solve(){
    for(int k = 0;k < V;k++){
        for(int i =0 ;i < V;i++){
            for(int j = 0;j <V;j++){
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }

    int minSum = INF, minarg = 0;
    for(int i = 0;i < V;i++){
        int sum = 0;
        for(int j = 0;j < V;j++){
            sum+=G[i][j];
        }
        if(sum < minSum){
            minSum = sum;
            minarg = i;
        }
    }
    cout<<minarg<<' '<<minSum<<endl;
}

/*
6
0 1 80
1 2 20
0 2 60
2 3 50
3 4 60
1 4 90
2
0 1 1
1 2 1
0
 */


int main(){
    ios::sync_with_stdio(false);
    while(cin>>E)
    {
        if(E == 0) break;
        V = 0;
        for(int i = 0;i < MAX_V;i++){
            for(int j = 0;j < MAX_V;j++){
                G[i][j] = INF;
                if(i == j) G[i][j] = 0;
            }
        }

        for(int i = 0;i < E;i++){
            int u,v,c;
            cin>>u>>v>>c;
            V = max(V, max(u, v));
            G[u][v] = G[v][u] = c;
        }
        V++;
        solve();

    }

    return 0;

}


Measured memory_bytes: 3056
#include <stdio.h>
#define N 100000
#define NIL -1

struct Node{
  int parent;
  int left;
  int right;
};
struct Node T[25];
int C[25];
int H[25];

void getDepth(int, int);
int getHeight(int);

int main()
{
  int n, i, j, k, x, y, id, left, right, root;


  scanf("%d",&n);
  for( i=0 ; i<n ; i++ ){
    T[i].parent = NIL;
  }
  for( i=0 ; i<n ; i++ ){
    scanf("%d %d %d",&id,&left,&right);
    T[id].left = left;
    T[id].right = right;   

      T[left].parent = id;

      T[right].parent = id;
  }

  for( i=0 ; i<n ; i++ )
    if(T[i].parent==NIL) root = i;

  getDepth(root,0);
  getHeight(root);

  for( i=0 ; i<n ; i++ ){
    printf("node %d: parent = %d, sibling = ",i,T[i].parent);
    
    j=i;
    while(1){
      if(T[i].parent==NIL) {
	printf("%d",T[i].parent);
	break;
      }
      if(T[T[i].parent].left==j) {
	printf("%d",T[T[i].parent].right);
	break;
      }
      if(T[T[i].parent].right==j){
	printf("%d",T[T[i].parent].left);
	break;
      }
      j++;
    }
        
    printf(", degree = ");
    if(T[i].left==NIL && T[i].right==NIL) printf("0");
    else if(T[i].left==NIL && T[i].right!=NIL)printf("1");
    else if(T[i].left!=NIL && T[i].right==NIL)printf("1");
    else printf("2");

    printf(", depth = %d,",C[i]);

    printf(" height = %d,",H[i]);
    
    if(T[i].parent==NIL)
      printf(" root\n");
    else if(T[i].left==NIL && T[i].right==NIL)
      printf(" leaf\n");
    else
      printf(" internal node\n");
  }

  return 0;
}
void getDepth(int r, int d)
{
  if(r==NIL) return;
  C[r] = d;


  getDepth(T[r].right,d+1);

  getDepth(T[r].left,d+1);
}

int getHeight(int r)
{
  int x=0, y=0;

  if(T[r].right!=NIL)
    x = getHeight(T[r].right)+1;
  if(T[r].left!=NIL)
    y = getHeight(T[r].left)+1;
  if(x>y) H[r] = x;
  else H[r] = y;
  return H[r];
}

Measured memory_bytes: 616
#include <iostream>
#include <algorithm>
#define inf 1e9

using namespace std;

int n, m;
int c[20], x[20005];
int dp[20005][300];

int main(void)
{
  while(cin >> n >> m, n&&m){
    for(int i = 1; i <= m; i++) cin >> c[i];
    for(int i = 1; i <= n; i++) cin >> x[i];

    for(int i = 0; i <= n; i++){
      for(int j = 0; j < 256; j++){
        dp[i][j] = inf;
      }
    }
    dp[0][128] = 0;

    for(int i = 0; i < n; i++){
      for(int j = 0; j < 256; j++){
        for(int k = 1; k <= m; k++){
          int nj = j + c[k];
          nj = min(nj, 255), nj = max(0, nj);
          dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + (x[i+1]-nj)*(x[i+1]-nj));
        }
      }
    }

    int ans = inf;
    for(int i = 0; i < 256; i++) ans = min(ans, dp[n][i]);
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 26604
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> PLL;
#define chmax(x, y) do { x = max(x, y); } while(0)
#define chmin(x, y) do { x = min(x, y); } while(0)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (ll i = static_cast<ll>(a); i < static_cast<ll>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;

bool v[200];
signed main() {
  ll N, K;
  cin >> N >> K;
  rep(i, K) {
    ll d;
    cin >> d;
    rep(i, d) {
      ll x;
      cin >> x;
      v[x] |= true;
    }
  }
  ll ans = 0;
  for (int i=1; i<=N; i++)
    if (!v[i])
      ans++;
  cout << ans << endl;
  return 0;
}


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

using namespace std ;

int main()
{
    string s ;
    deque < char > dq ;
    bool _reverse = false ; // we declare a boolean variable to know when its reversed so we assignee it with false
    cin >> s ;

    for ( int i = 0 ; i < s.size() ; i++ ) // first we initiate the dequeue with the string given
        dq.push_back(s[i]);

    int q ;
    cin >> q ;
    for ( int i = 0 ; i < q ; i++ )
    {
        int t ;
        cin >> t ;
        if ( t == 1 )               _reverse = !_reverse ; // if ( t = 1 ) this means we will reverse the string so we assignee the variable with it's opposite
        else
        {
            int f ;
            char c ;
            cin >> f >> c ;
            if ( f == 1 )
            {
                if ( !_reverse )    dq.push_front(c) ; // if its not reversed we add the character from the back like we were told
                else                dq.push_back(c) ; // else we add from the front because it's reversed
            }
            else // same for this case
            {
                if ( !_reverse )    dq.push_back(c) ;
                else                dq.push_front(c) ;
            }
        }
    }
    if ( !_reverse ) // if the last state of the string is normal and not reversed we print it frontward
    {
        for ( auto it = dq.begin() ; it != dq.end() ; it++ )
            cout << *it ;
    }
    else // else we print it backwards
    {
        for ( auto it = dq.rbegin() ; it != dq.rend() ; it++ )
            cout << *it ;
    }
	return 0;
}




Measured memory_bytes: 896
import itertools
def generateA(N, M, minv=1):
    if N < 0:
        return
    if N == 0:
        yield []
    if N == 1:
        for i in range(minv, M):
            yield [i]
    for v in range(minv, M+1):
        for subA in generateA(N-1, M, v):
            yield [v] + subA

def point(A, L):
    result = 0
    for (a, b, c, d) in L:
        if A[b-1] - A[a-1] == c:
            result += d

    return result

def summary(N, M, L):
    As = generateA(N, M)

    results = []
    for A in As:
        results.append(point(A,L))
    return results

def test():
    As = generateA(3,4)
    for A in As:
        print(A)

def main():
    #test()
    N, M ,Q = map(int, input().split())
    L = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        L.append((a,b,c,d))
    results = summary(N,M,L)

    print(max(results))

if __name__ == '__main__':
    main()

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

int main(){
  int n;
  
  while(true){
  cin>>n;
  if(n==0){
    break;
  }else{
    int a[100]={};
  int ushi=0;
  int uma=10000;
  int yagi=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
      if(a[i]>ushi){
	ushi=a[i];}
    if(a[i]<uma)
      {uma=a[i];}
    yagi=yagi+a[i];
  }
  cout<<(yagi-uma-ushi)/(n-2)<<endl;
  }
  }
}

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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if((a==b && a!=c)||(a==c && a!=b)||(b==c && b!=a)) {
        cout << "Yes" << "\n";
    }
    else {
        cout << "No" << "\n";
    }
}

Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val x1, y1, x2, y2 = ni()
    val x3 = x2 - (y2 - y1)
    val y3 = y2 + (x2 - x1)
    val x4 = x3 - (y3 - y2)
    val y4 = y3 + (x3 - x2)
    out.println(s"$x3 $y3 $x4 $y4")
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int): Array[Int] = map(n)(_ => ni())
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def rep(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def rep_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  def sumL(as: Array[Int]): Long = {
    var s = 0L
    rep(as.length)(i => s += as(i))
    s
  }
}

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

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILL(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};


int main(){

  int n;
  cin >> n;
  vector<P> v;
  REP(i,n){
    int x;cin >> x;
    v.push_back({x,i});
  }
  sort(ALL(v));
  REP(i,n)cout << v[i].second+1 << " ";

  return 0;
}

Measured memory_bytes: 2544
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll LINF = 1001002003004005006LL;
const int INF = 1001001001;

const int mod = 1000000007;

int dp[100100][3];

int main() {
    int n; cin >> n;
    vector<int> a(n), b(n), c(n);
    rep(i,n) cin >> a[i] >> b[i] >> c[i];
    rep(i,n) {
        dp[i+1][0] = max(dp[i][1]+a[i], dp[i][2]+a[i]);
        dp[i+1][1] = max(dp[i][0]+b[i], dp[i][2]+b[i]);
        dp[i+1][2] = max(dp[i][0]+c[i], dp[i][1]+c[i]);
    }
    cout << max({dp[n][0],dp[n][1],dp[n][2]}) << endl;
    return 0;
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const long long MOD = 1000000007LL;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

bool solve(void){
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    --a;
    --b;
    --c;
    --d;

    string s;
    cin >> s;

    REP(i, a, c){
        if(s[i] == '#' && s[i + 1] == '#'){
            return false;
        }
    }
    REP(i, b, d){
        if(s[i] == '#' && s[i + 1] == '#'){
            return false;
        }
    }

    if(c < d){
        return true;
    }

    REP(i, b, d + 1){
        if(s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.'){
            return true;
        }
    }

    return false;
}

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

    if(solve()){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

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

import bisect

def f(D, T, lenOfS):
    x = 0
    p = -1
    for c in T:
        d = D[ord(c) - 97]
        if len(d) == 0:
            return -1
            
        idx = bisect.bisect_left(d, p+1)

        if idx < len(d):
            p2 = d[idx]
        else:
            p2 = d[0]
            x += lenOfS;

        x += (p2 - p)
        p = p2
            
    return x


def main():
    S = input()
    T = input()

    D = [[] for _ in range(26)]
    for i, c in enumerate(S):
        D[ord(c) - 97].append(i)

    print(f(D, T, len(S)))
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 7540
#include<bits/stdc++.h>
#include<set>
#include<bitset>
#define rep(i,a,b)  for(i=a;i<b;i++)
#define itrep(at)	for(auto it=at.begin();it!=at.end();it++)
//#define sort(v)	sort(v.begin(),v.end());
//#define rsort(v) sort(v.rbegin(),v.rend());
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vb vector<bool>
#define vc vector<char>
#define vvll vector<vector<long long int> >
#define sll set<long long int>
#define mll map<long long int,long long int>
#define sllit set<long long int>::iterator
#define db double
#define M 1000000007
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
lli min(lli a,lli b){return a<b?a:b;}
lli min(lli a,lli b,lli c){a=min(a,b);a=min(a,c);return a;}
lli max(lli a,lli b){return a>b?a:b;}
lli max(lli a,lli b,lli c){a=max(a,b);a=max(a,c);return a;}
lli power(lli a,lli b){lli res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;}
lli mpower(lli a,lli b,lli m){lli res=1;a=a%m;while(b){if(b&1){res=(res*a)%m;}a=((a%m)*(a%m))%m;b>>=1;}return res;}
lli gcd(lli a,lli b){if(b==0) return a;if(a==0) return b;if(a>=b) return gcd(b,a%b);else return gcd(a,b%a);}
lli lcm(lli a,lli b){lli p=a*b;return p/gcd(a,b);}
lli dsum(lli n){lli ans=0;while(n){ans+=(n%10);n/=10;}return ans;}


/******************************START********************************/
bool found(lli arr[],lli n,lli x)
{
	for(lli i=0;i<n;i++){
		if(arr[i]==x)	return true;
	}
	return false;
}
int main()
{
	//init();
	char ch1,ch2,ch3;
	string s1,s2,s3,str;
    lli i,j,k,a,t,b,c,n,z,m,sum=0,ans=0,temp;
    cin >> n;
    lli v[n];
    rep(i,0,n)	cin >> v[i];
    sort(v,v+n);
    ans=99999999999999999;
    rep(i,1,v[n-1]+1){
    	sum=0;
    	for(j=0;j<n;j++){
    		sum=sum+(v[j]-i)*(v[j]-i);
		}
		if(ans>sum)	ans=sum;
	}
	cout << ans << endl;
    
    
    
    
    
    return 0;
}





















/* UJJWAL KESHRI */

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())

X = int(input())

ans = 0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if a * 500 + b * 100 + c * 50 == X:
        ans += 1

print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

int const N = 100000;
int g[3][3], a[3], b[3], fr[200], fr0[200], fr1[200];

int main(){
    for(int i = 0; i<3; ++i){
         for(int j = 0; j<3; ++j)scanf("%d", &g[i][j]);
    }
    for(int a0 = 0; a0 <= 100; ++a0){
          b[0] = g[0][0] - a0;
          b[1] = g[0][1] - a0;
          b[2] = g[0][2] - a0;
          if(b[0] < 0 || b[1] < 0 || b[2] < 0)continue;
          bool f = true;
         for(int i = 0; i<3; ++i){
             int mx = 0;
             memset(fr,0,sizeof fr);
             for(int j = 0; j<3; ++j){
                 ++fr[g[i][j] - b[j]];
                 mx = max(mx, fr[g[i][j] - b[j]]);
             }
             if(mx != 3){f = false; break;}
         }
         if(f)return puts("Yes"),0;
    }
    puts("No");
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 200

int top, a[MAX_N];

void push(int x)
{
	a[top + 1] = x;
	top++;
}
int pop(void)
{
	int tmp = a[top];
	a[top] = 0;
	top--;
	return tmp;
}

int main(void)
{
	char c[100];
	top = 0;

	while (scanf("%s", c) != EOF) {
		int a, b;
		if (c[0] == '+') { 
			a = pop();
			b = pop();
			push(a + b);
		}
		else if (c[0] == '-') {
			a = pop();
			b = pop();
			push (b - a);
		}
		else if(c[0] == '*') {
			a = pop();
			b = pop();
			push (b*a);
		}
		else push(atoi(c));
	}

	printf("%d\n", pop());

    return 0;
}

Measured memory_bytes: 548
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX=10000;
static const int INFTY = (1<<20);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n;
vector<pair<int,int> > adj[MAX];
void dijkstra(){
  priority_queue<pair<int,int> > PQ;
  int color[MAX];
  int d[MAX];
  for(int i=0;i<n;i++){
    d[i]=INFTY;
    color[i]=WHITE;
  }
  d[0]=0;
  PQ.push(make_pair(0,0));
  color[0]=GRAY;

  while(!PQ.empty()){
    pair<int,int>f=PQ.top();PQ.pop();
    int u=f.second;
    color[u]=BLACK;
    if(d[u]<f.first*(-1))continue;
    for(int j=0;j<adj[u].size();j++){
      int v=adj[u][j].first;
      if(color[v]==BLACK)continue;
      if(d[v]>d[u]+adj[u][j].second){
        d[v]=d[u]+adj[u][j].second;
        PQ.push(make_pair(d[v]*(-1),v));
        color[v]=GRAY;
      }
    }
  }
  for(int i=0;i<n;i++){
    cout<<i<<" "<<(d[i]==INFTY ? -1:d[i])<<endl;
  }
}

int main(){
  int k,u,v,c;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin>>v>>c;
      adj[u].push_back(make_pair(v,c));
    }
  }
  dijkstra();
  return 0;
}

Measured memory_bytes: 8124
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59

ll gcd(ll a,ll b){
  if(a<b) swap(a,b);
  if(a%b==0) return b;
  else return gcd(b,a%b);
}

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

int main(){
  ll i,j; 
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll l=lcm(c,d);
  ll ans=b/c-(a-1)/c+b/d-(a-1)/d-b/l+(a-1)/l;
  ans=b-a+1-ans;
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  





void solve(){
	int n , m; 
	cin >> n >> m; 
	vi a(n);
	re(a);
	vi b(m) , c(m);
	rep(i,0,m){
		cin >> b[i] >> c[i];
	}
	vi idx(m);
	iota(all(idx),0);
	auto cmp  =[&](int i ,int j){return c[i] > c[j];};
	sort(all(idx),cmp);
	multiset<int>se(all(a)) ; 
	int mx = n ;
	trav(i,idx){
		int cur = min(mx,b[i]);
		rep(j,0,cur) se.insert(c[i]);
		mx-=cur;
	}
	while(sz(se)>n) se.erase(se.begin());
	ll ans = 0 ;
	trav(i,se) ans+=i;
	cout << ans << endl; 
}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


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

using namespace std;

int main() {

	int n;
	cin >> n;

	int nn;
	nn = n % 10;
	if (nn == 2 || nn == 4 || nn == 5 || nn == 7 || nn == 9) {
		cout << "hon" << endl;
		return 0;
	}

	if (nn == 0 || nn == 1 || nn == 6 || nn == 8 ) {
		cout << "pon" << endl;
		return 0;
	}
	if (nn == 3) {
		cout << "bon" << endl;
		return 0;
	}

	return 0;
}

Measured memory_bytes: 3636
X, K, D = map(int, input().split())
X = abs(X)
if X // D <= K:
    print(min(abs(X % D - (K - (X // D))%2*D), abs(X % D + (K - (X // D))%2*D)))
else:
    print(min(abs(X - K*D), abs(X + K*D)))


Measured memory_bytes: 9176
#include <cstdio>

using s32 = int;
using u32 = unsigned int;
using s64 = long long int;
using u64 = unsigned long long int;

u64 a, bb;
double b;

int main(){
  scanf("%lld%lf", &a, &b);
  
  bb = b * 100 + 0.5;

  printf("%lld\n", a*bb/100);
  return 0;
}


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

const int INF = 2001;
const int MAX_N = 100;

int N;
int A[MAX_N][MAX_N];

void solve() {
  int cost , d[MAX_N], p[MAX_N];
  bool c[MAX_N];

  for (int i = 0; i < N; i++) {
    c[i] = false;
    d[i] = INF;
    p[i] = -1;
  }

  d[0] = 0;
  
  while (1) {
    int cost = INF;
    int from = -1;

    for (int i = 0; i < N; i++) {
      if (d[i] < cost && !c[i]) {
        cost = d[i];
        from = i;
      }
    }

    if (from == -1) break;

    c[from] = true;

    for (int dest = 0; dest < N; dest++) {
      if (!c[dest] && A[from][dest] != -1) {
        if (A[from][dest] < d[dest]) {
          d[dest] = A[from][dest];
          p[dest] = from;
        }
      }
    }
  }

  int sum = 0;
  for (int i = 0; i < N; i++)
    if (p[i] != -1) sum += A[i][p[i]];

  cout << sum << endl;
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      cin >> A[i][j];
  solve();
}

Measured memory_bytes: 1204
n, q = map(int, input().split())
data = [list(map(str, input().split())) for i in range(n)]

time = 0
tmp = []
answer = []

while True:
    tmp = data.pop(0)
    if int(tmp[1]) <= q:
        time += int(tmp[1])
        answer.append([tmp[0], time])
        if len(data) == 0:
            break
    else:
        tmp[1] = int(tmp[1]) - q
        time += q
        data.append(tmp)
for i in answer:
    print(i[0], i[1])


Measured memory_bytes: 16264
import itertools
N = int(input())
L = list(map(int,input().split()))
ans=0
for v in itertools.combinations(list(range(N)), 3):
  if max(L[v[0]],L[v[1]],L[v[2]])<L[v[0]]+L[v[1]]+L[v[2]]-max(L[v[0]],L[v[1]],L[v[2]]):
    if L[v[0]]!=L[v[1]] and L[v[1]]!=L[v[2]] and L[v[2]]!=L[v[0]]:
      ans+=1
    
print(ans)

Measured memory_bytes: 9212
/*
********************
Author : Sahil Kundu
********************
*/
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb(i) push_back(i)
#define pp() pop_back()
#define f first
#define s second
#define mk(l,r) make_pair(l,r)
#define all(vc) vc.begin(),vc.end()
#define bg(vc) vc.begin()
#define ed(vc) vc.end()
#define ms(i,j) memset(i,j,sizeof i)
#define w(t) while(t--)
const ll MAX=1e5+5;
const ll INF=2e18;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin>>t;
    w(t)
    {
        ll n,m;
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            ll x;
            cin>>x;
            n-=x;
        }
        if(n>=0)cout<<n<<endl;
        else cout<<"-1\n";
    }
}
/*ll msb(ll x)
{
	ll k=(ll)log2(x);
	return (ll)(pow(2,k));
}
#define gc getchar_unlocked
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}*/

Measured memory_bytes: 3616