akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    VI V(N); REP(i,N) cin >> V[i];
    int X = min(N,K);
    int ans = 0;
    for(int i = 0; i <= X; i++){
        for(int j = 0; j <= X-i; j++){
            VI jue;
            int tmp= 0;
            REP(k,i){
                jue.eb(V[k]);
                tmp+=V[k];
            }
            REP(k,j){
                jue.eb(V[N-1-k]);
                tmp += V[N-1-k];
            }
            sort(jue.begin(),jue.end());
            dump(i)
            dump(j)
            dump(tmp)
            int rem = K - i - j;
            for(auto p : jue){
                if(rem == 0) break;

                dump(p)

                if(p < 0) {
                    tmp -= p;
                    rem--;
                }
                else break;

            }
            dump(tmp)
            if(tmp > ans) ans = tmp;
        }
    }
    cout << ans << endl;


}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  int ans;
  while(cin>>N){
    ans = 0;
    for(int a=0;a<10;++a){
      for(int b=0;b<10;++b){
        for(int c=0;c<10;++c){
          for(int d=0;d<10;++d){
            if(a+b+c+d==N) ans++;
          }
        }
      }
    }
    cout<<ans<<endl;
  }
}



Measured memory_bytes: 3000
n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]
d = {}
for i in range(n):
    if s[i] in d:
        d[s[i]] += 1
    else:
        d[s[i]] = 1
for i in range(m):
    if t[i] in d:
        d[t[i]] -= 1
    else:
        d[t[i]] = 1

# print(d)
v = max(d.values())
if v >= 0:
    print(max(d.values()))
else:
    print(0)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
const long long MOD = 1000000007;

int N;
vector<vector<int>> G;
long long dp[101010][2];

void dfs(int cur, int pre = -1) {
    dp[cur][0] = dp[cur][1] = 1;
    for(auto &to : G[cur]) {
        if(to == pre) continue;
        dfs(to, cur);
        dp[cur][0] *= dp[to][0] + dp[to][1];
        dp[cur][1] *= dp[to][0];
        dp[cur][0] %= MOD;
        dp[cur][1] %= MOD;
    }
}

int main() {
    cin >> N;
    G.resize(N);
    rep(i, 0, N - 1) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(0);
    cout << (dp[0][0] + dp[0][1]) % MOD << endl;
    return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int N;
    cin >> N;
    if (N % 1000 == 0) {
        cout << 0 << endl;
    } else {
        cout << 1000 - (N % 1000) << endl;
    }
    return 0;
}


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

// 各色の長方形が何個ずつあるか
map<vector<int>, long long> ma;
void use(vector<int> v) {
    for (int it = 0; it < 4; ++it) {
        vector<int> col(4);
        for (int j = 0; j < 4; ++j) {
            col[j] = v[(it+j)%4];
        }
        ma[col]--;
    }
}
void add(vector<int> v) {
    for (int it = 0; it < 4; ++it) {
        vector<int> col(4);
        for (int j = 0; j < 4; ++j) {
            col[j] = v[(it+j)%4];
        }
        ma[col]++;
    }
}

int main() {
    int N; cin >> N;
    vector<vector<int> > C(N, vector<int>(4));
    for (int i = 0; i < N; ++i) for (int j = 0; j < 4; ++j) cin >> C[i][j];

    // 追加
    ma.clear();
    for (int i = 0; i < N; ++i) add(C[i]);

    // 集計
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        use(C[i]);
        for (int j = 0; j < N; ++j) {
            if (j == i) continue;
            use(C[j]);
            
            for (int dir = 0; dir < 4; ++dir) {
                auto ue = C[i];
                vector<int> shita(4);
                for (int k = 0; k < 4; ++k) shita[k] = C[j][(dir + k) % 4];
                reverse(shita.begin(), shita.end());

                long long tmp = 1;
                vector<bool> isadd(4, 0);
                for (int it = 0; it < 4; ++it) {
                    vector<int> col = {ue[(it+1)%4], ue[it%4], shita[it%4], shita[(it+1)%4]};
                    if (!ma.count(col)) tmp = 0;
                    else tmp *= ma[col], use(col), isadd[it] = true;
                }
                for (int it = 0; it < 4; ++it) {
                    vector<int> col = {ue[(it+1)%4], ue[it%4], shita[it%4], shita[(it+1)%4]};
                    if (isadd[it]) add(col);
                }
                
                res += tmp;
            }
            add(C[j]);
        }
        add(C[i]);
    }
    cout << res/6 << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
#define pb push_back
#define mp  make_pair
#define loop(a,n) for(long long i=a;i<n;i++)
#define vil vector<long long int>
#define vi vector<int>
#define sz(v) v.size()
#define setbits(x)          __builtin_popcountll(x)
#define ff first
#define ss second
using namespace std;

int nCrevenoroddfinder(int n,int r)
{
    int a=r;
    int b=n-r;
    for(int i=0;i<30;i++)
    {
        int x=1<<i;
        if((x&a)&&(x&b))
        {
            return 0;//even
        }
    }
    return 1;//odd
}

ll gcd(ll a, ll b) {
  if (a == 0)return b;
  return gcd(b % a, a);
}
bool isperfect(ll n) {
  ll y = sqrt(n);
  if (n % y == 0 && y * y == n)return true;
  return false;
}
bool comp(pair<int,int> a, pair<int,int> b) {
    if(a.first == b.first) return a.second>b.second;
  return a.first < b.first;
}
 ll powi(ll a, ll b) {
  ll ans = 1;
  while (b > 0) {
    if (b & 1)ans = (ans * a);
    b = b >> 1;
    a = (a * a);
  }
  return ans;
}
bool isprime(ll n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)return false;
  }
  return true;
}
bool prime[10000000];
void seive() {

  prime[1] = true;
  for (int i = 2; i * i < 10000000; i++) {

    if (prime[i])continue;
    for (int j = i * i; j < 10000000; j += i) {
      prime[j] = true;
    }

  }
}

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll d,t,s;
  cin>>d>>t>>s;
  
  ll f=d/s+(d%s!=0);
  if(f<=t) cout<<"Yes";
  else cout<<"No";
}



  

Measured memory_bytes: 3688
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(void)
{
	int n,i;
	long long a[100000],x;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%lld",&a[i]);
	sort(a,a+n);
	printf("\n");
	
	x=0;
	for(i=n-1;i>0;i--){
		if(a[i]==a[i-1]){
			if(x!=0) break;
			x=a[i];
			i--;
		}
	}
	x=x*a[i];
	printf("%lld",x);
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
using namespace std;
int selectionSort(int* a,int n)
{
	int exchangeCount=0;
	int i,j;
	int minj,temp;
	for(i=0; i<n; i++)
	{
		minj = i;
		for(j=i; j<n; j++)
		{
			if(a[j]<a[minj])
			{
				minj = j;
			}
		}
		if(i!=minj) exchangeCount++;
		temp=a[i];
		a[i]=a[minj];
		a[minj]=temp;
	}
	return exchangeCount;
}
void printArr(int *a,int n)
{
	for(int i=0; i<n; i++)
	{
		if(i>0) cout << " ";
		cout << a[i];
	}
	cout << "\n";
}
int main()
{
	int n;
	cin >> n;
	int a[n];
	for(int i=0; i<n; i++)
	{
		cin >> a[i];
	}
	int count=selectionSort(a,n);
	printArr(a,n);
	cout << count << endl;
	return 0;
}

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

#define ll long long
#define ull unsigned long long

using namespace std;

const int INVALID = -1;
using Graph = vector<vector<int>>;
vector <int> a;
vector <int> len;

void dfs(const Graph& graph, int v, int p, vector <int>& dp) {
	for (auto nv : graph[v]){
		if (nv == p) continue;
		auto itr = lower_bound(dp.begin(), dp.end(), a[nv]);
		int idx = itr - dp.begin();
		int pre = -1;
		if (itr == dp.end()){
			dp.push_back(a[nv]);
		} else {
			pre = *itr;
			*itr = a[nv];
		}
		len[nv] = dp.size();

		dfs(graph, nv, v, dp);

		if (pre == -1){
			dp.pop_back();
		} else {
			dp[idx] = pre;
		}
	}
}

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

	a.assign(N, 0);
	for (int ii = 0; ii < N; ++ii){
		cin >> a[ii];
	}

	Graph graph(N);
	for (int ii = 0; ii < N-1; ++ii){
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	len.assign(N, 0);
	len[0] = 1;
	int root = 0;
	vector <int> dp;
	dp.push_back(a[0]);
	dfs(graph, /*v=*/root, /*p=*/-1, dp);

	for (int ii = 0; ii < N; ++ii){
		cout << len[ii] << "\n";
	}

	return 0;
}


Measured memory_bytes: 32964
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();

		x -= a;
		while (x >= b) {
			x -= b;
		}
		System.out.print(x);
	}
}

Measured memory_bytes: 21844
"""
4
WWRR
2
"""
import itertools

n = int(input())
s = list(input())
left_w = [0]
right_r = [0]
for l in s:
    if l == "W":
        left_w.append(1)
    else:
        left_w.append(0)
lacc = list(itertools.accumulate(left_w))
for r in s[::-1]:
    if r == "R":
        right_r.append(1)
    else:
        right_r.append(0)
racc = list(itertools.accumulate(right_r))
racc = racc[::-1]
print(min(map(max, zip(lacc, racc))))


Measured memory_bytes: 30776
#include <stdio.h>
int main(void){
	int a,b;
	scanf("%d %d",&a,&b);
	if(a>b){
		printf("a > b\n");
	}else if(a<b){
		printf("a < b\n");
	}else{
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int a = sc.nextInt();
            String op = sc.next();
            int b = sc.nextInt();

            if(op.equals("?")) break;

            switch(op){
                case "+":
                    System.out.println(a+b);
                    break;
                case "-":
                    System.out.println(a-b);
                    break;
                case "*":
                    System.out.println(a*b);
                    break;
                case "/":
                    System.out.println(a/b);
                    break;
            }
        }
    }
}


Measured memory_bytes: 26512
n = int(input())
data = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        data[i].append(list(map(int,input().split())))

#print(data)
ans = 0
for i in range(1<<n):
    truth = []
    for x in range(n):
        if i&(1<<x):
            truth.append(x+1)

    q = True
    for j in truth:
        for x,y in data[j-1]:
            if x in truth and y == 0:
                q = False
                break
            if x not in truth and y == 1:
                q = False
                break
    if q:
        ans = max(ans,len(truth))
        #print(truth)

print(ans)

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

using namespace std;

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

	vector<int> H(N);
	vector<vector<int>> table(1);
	int index = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> H[i];

		if (H[i] == 0)
		{
			index++;
			table.push_back(vector<int>());
			continue;
		}

		table[index].push_back(H[i]);
	}

	int ans = 0;
	for (int i = 0; i < table.size(); i++)
	{
		if (table[i].size() == 0)
		{
			continue;
		}

		if (table[i].size() == 1)
		{
			ans += table[i][0];
			continue;
		}

		int min = *min_element(table[i].begin(), table[i].end());

		index++;
		table.push_back(vector<int>());
		if (table[i][0] != min)
		{
			table[index].push_back(table[i][0] - min);
		}
		
		for (int k = 1; k < table[i].size() - 1; k++)
		{
			if (table[i][k] == min && table[index].size() > 0)
			{
				index++;
				table.push_back(vector<int>());
			}
			else
			{
				table[index].push_back(table[i][k] - min);
			}
		}

		if (table[i][table[i].size() - 1] != min)
		{
			table[index].push_back(table[i][table[i].size() - 1] - min);
		}

		if (table[index].size() == 0)
		{
			table.erase(table.begin() + index);
			index--;
		}

		ans += min;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
/*
____    ____ .___________.
\   \  /   / |           |
 \   \/   /  `---|  |----`
  \      /       |  |     
   \    /        |  |     
    \__/         |__|     
                          
 */


#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<iomanip>
#define ll long long
#define mod 1000000007
using namespace std;
const int INF = 2e9 + 1;


/*---------------Graph Class---------*/
class graph
{
private:
	ll novert;
	ll noedges;
	vector< vector<ll> > adjlist;
public:
	graph(ll n,ll m)
	{
		novert=n;
		noedges=m;
		adjlist.resize(n+1);	
	}
	
	void addedge(ll u,ll v)
	{
		//bidirectional
		adjlist[u].push_back(v);
		adjlist[v].push_back(u);	
	}
	
	void dfsutil(ll initvert,vector<bool>& visited,ll lastvert=-1)
	{
		if(lastvert==initvert)
		{
			//do something
		}
		visited[initvert]=true;
		for(auto itr:adjlist[initvert])
		{
			if(!visited[itr])
			{
			}	
		}	
	}	
};
/*-----------------End of graph----------------*/





int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
ll n;
cin>>n;
cout<<(n)*(n+1)/2;


	return 0;
}


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

int main () {
  int a,b,c,k;cin>>a>>b>>c>>k;

  if(k<a){
    cout<<k<<endl;
  }else if(k <= a+b){
    cout<<a<<endl;
  }else {
    cout<<a-(k-a-b)<<endl;
  }

return 0;

}


Measured memory_bytes: 3632
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,D = map(int,readline().split())
XY = np.array(list(map(int,read().split())))

A = np.zeros((D,D),np.int64)
X = XY[::2]; Y = XY[1::2]
np.add.at(A,(X%D,Y%D),1)

maxA = A.max()
n = int((maxA-1)**.5)

# 2周分用意する
AA = np.tile(A,(2,2))

gr1 = (AA > n*n).cumsum(axis=0).cumsum(axis=1)
gr2 = (AA > n*(n+1)).cumsum(axis=0).cumsum(axis=1)

def test(x):
    gr1_rd = gr1[D:D+D,D:D+D] + gr1[x:x+D,x:x+D] - gr1[x:x+D,D:D+D] - gr1[D:D+D,x:x+D]
    condition_rd = (gr1_rd == 0)
    gr2_ru = gr2[x:x+D,D:D+D] + gr2[0:D,x:x+D] - gr2[x:x+D,x:x+D] - gr2[0:D,D:D+D]
    gr2_ld = gr2[D:D+D,x:x+D] + gr2[x:x+D,0:D] - gr2[x:x+D,x:x+D] - gr2[D:D+D,0:D]
    condition_ru = (gr2_ru == 0)
    condition_ld = (gr2_ld == 0)
    return (condition_rd&condition_ru&condition_ld).any()

left = 0 # 足りてない
right = D # 足りてる
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = n*D + right - 1
print(answer)


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

int main(void){
    int n, m;
    cin>>n>>m;
    vector<pair<int, int> > v(m);
    rep(i, m) {
        int a, b;
        --a;--b;
        cin>>a>>b;
        v[i]=make_pair(b, a);
    }
    int ans=1;
    sort(v.begin(), v.end());
    int l=v[0].second;
    int r=v[0].first;
    for(int i=1;i<m;i++){
        if(v[i].second<r) continue;
        r=v[i].first;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
    int n,m,l;
    cin>>n>>m>>l;
    int a[n][m], b[m][l];
    long long c[n][l];
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin>>a[i][j];
        }
    }
    for(int i=0; i<m; ++i){
        for(int j=0; j<l; ++j){
            cin>>b[i][j];
        }
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<l; ++j){
            c[i][j]=0;
            for(int k=0; k<m; ++k){
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<l; ++j){
            if(j!=l-1)cout<<c[i][j]<<" ";
            else cout<<c[i][j]<<endl;
        }
    }
    return 0;
}


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

using namespace std;
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define tll tuple<ll, ll, ll>
#define all(c) c.begin(),c.end()

const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;

ll h[50];
ll p[50];

ll calc(ll n, ll x){
  //if (x == 1) return 0;
  //if (1 < x && x <= h[n-1]+1) return calc(n-1, x-1);
  //if (x == h[n-1]+2) return p[n-1] + 1;
  //if (h[n-1]+2 < x && x <= 2*h[n-1]+2) return p[n-1] + 1 + calc(n-1, x-h[n-1]-2);
  //if (x == 2*h[n-1]+3) return 2*p[n-1] + 1;
  if (n==0){
    if (x <= 0) return 0;
    else return 1;
  }
  else if (x <= h[n-1]+1) return calc(n-1, x-1);
  else return p[n-1] + 1 + calc(n-1, x-h[n-1]-2);
}

int main() {
  ll n, x;
  cin >> n >> x;
  h[0] = 1;
  p[0] = 1;
  for(int i=1;i<=50;i++){
    h[i] = 2*h[i-1] + 3;
    p[i] = 2*p[i-1] + 1;
  }
  
  ll ans = calc(n,x);
  cout << ans << endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:-x[1])
a.sort()
ans=0
ai=0
for i in bc:
    b,c=i
    for j in range(b):
        if(ai>=n):
            print(ans)
            quit()
        elif(a[ai]>c):
            ans+=sum(a[ai:])
            print(ans)
            quit()
        else:
            ans+=c
            ai+=1
else:
    ans+=sum(a[ai:])
    print(ans)

Measured memory_bytes: 36160
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
typedef long long int ll;

void solve()
{
	double r; 
	cin >> r;
	cout << 3.1415926535 * 2 * r;
}
int main()
{
//	int t;
//	cin >> t;
//	while (t-- > 0)
		solve();
}


Measured memory_bytes: 3788
#include<bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
signed main(){
  int n;
  cin>>n;
  map<int,bool> m;
  for(int i=0;i<n;++i){
    int t;
    cin>>t;
    m[t]=true;
  }
  cout<<m.size();
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>

using namespace std;

typedef long long ll;

#ifdef ONPC
    mt19937 rnd(228);
#else
    mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 2e5 + 7;

int par[N];

int get(int v)
{
    if (v == par[v])
    {
        return v;
    }
    else
    {
        return par[v] = get(par[v]);
    }
}

void uni(int u, int v)
{
    par[get(u)] = get(v);
}

const ll inf = 1e18 + 7;

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, d;
    cin >> n >> d;
    vector <int> a(n);
    vector <int> ind(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        ind[i] = i;
    }
    for (int i = 0; i < n; i++)
    {
        par[i] = i;
    }
    int comp = n;
    ll ans = 0;
    while (comp > 1)
    {
        vector <ll> best(n, inf);
        vector <int> him(n, -1);
        auto rlx = [&] ()
        {
            vector <pair <ll, int> > arr;
            for (int i = 0; i < n; i++)
            {
                int real_ind = ind[i];
                ll value = -i * (ll) d + a[real_ind];
                int who = get(real_ind);
                arr.push_back({value, who});
                sort(arr.begin(), arr.end());
                vector <pair <ll, int> > now;
                for (int i = 0; i < (int) arr.size(); i++)
                {
                    if (now.empty() || now.back().second != arr[i].second)
                    {
                        now.push_back(arr[i]);
                    }
                }
                while (now.size() > 2) now.pop_back();
                arr = now;
                for (auto c : now)
                {
                    if (c.second != who)
                    {
                        ll relax_cur = i * (ll) d + a[real_ind] + c.first;
                        int relax_who = c.second;
                        if (relax_cur < best[who])
                        {
                            best[who] = relax_cur;
                            him[who] = relax_who;
                        }
                    }
                }
            }
        };
        rlx();
        reverse(ind.begin(), ind.end());
        rlx();
        for (int i = 0; i < n; i++)
        {
            if (get(i) == i)
            {
                if (get(him[i]) != i)
                {
                    uni(him[i], i);
                    ans += best[i];
                    comp--;
                }
            }
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 4992
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

C = np.array([list(sr()) for _ in range(3)])
answer = np.diag(C)
print(''.join(answer.astype(str)))


Measured memory_bytes: 27032
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






int ggcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int h,w,a=0,b=0;
  cin>>h>>w;
  vector<vector<string>> v(h,vector<string>(w));
  rep(i,h) rep(j,w) cin>>v[i][j];
  rep(i,h){
    rep(j,w){
      if(v[i][j]=="snuke"){
        a=i;
        b=j;
        break;
      }
    }
  }
 
  cout<<(char)('A'+b)<<a+1<<endl;
  

  
}
///////////////////////////

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

int main() {
  int X;
  cin >> X;
  if(X>399 && X<600){
    cout << 8 << endl;
  }
  else if(X>599 && X<800){
    cout << 7 << endl;
  }
  else if(X>799 && X<1000){
    cout << 6 << endl;
  }
  else if(X>999 && X<1200){
    cout << 5 << endl;
  }
  else if(X>1199 && X<1400){
    cout << 4 << endl;
  }
  else if(X>1399 && X<1600){
    cout << 3 << endl;
  }
  else if(X>1599 && X<1800){
    cout << 2 << endl;
  }
  else if(X>1799 && X<2000){
    cout << 1 << endl;
  }
  cout << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int N = s.size();
  string t;
  t += s[0];
  for (int i = 1; i < N; i++){
    if (t.back() == 'B' && s[i] == 'C'){
      t.pop_back();
      t += 'X';
    } else {
      t += s[i];
    }
  }
  int M = t.size();
  long long ans = 0;
  int cnt = 0;
  for (int i = 0; i < M; i++){
    if (t[i] == 'A'){
      cnt++;
    } else if (t[i] == 'X'){
      ans += cnt;
    } else {
      cnt = 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3932
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;

    int hP = N / 100;
    int tP = (N - (hP * 100)) / 10;
    int oP = N - (hP * 100 + tP * 10);

    if (hP == 7 || tP == 7 || oP == 7) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
int ans;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<vector<int> > C(10, vector<int>(10));
    for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) cin >> C[i][j];
    int count = 1;
    while (count) {
        count = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == j) continue;
                for (int k = 0; k < 10; k++) {
                    if (i == k || j == k) continue;
                    if (C[j][k] > C[j][i]+C[i][k]) {
                        C[j][k] = C[j][i]+C[i][k];
                        count++;
                    } 
                }
            }
        }
    }
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<W; j++) {
            int a;
            cin >> a;
            if (a == -1 || a == 1) continue;
            ans += C[a][1];
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

constexpr auto INF = INT_MAX/2;
constexpr auto MOD = 1000000007;


int main() {

	int n;
	cin >> n;

	string sex0;
	cout << 0 << endl;
	cin >> sex0;
	if (sex0 == "Vacant")return 0;

	int l = 0, r = n, c;

	while (true) {
		c = (l + r) / 2;

		string res;
		cout << c << endl;
		cin >> res;
		if (res == "Vacant")break;

		if ((res == sex0) ^ (c % 2 == 0))r = c;
		else l = c;
	}
}

Measured memory_bytes: 852
#include <stdio.h>

main(){
  char map[10][10];
  int i, j,p=0,t;

  while(1){
    for(i=0;i<8;i++){
      for(j=0;j<8;j++){
	if(scanf("%c", &map[i][j])==EOF) p=1;
      }
      if(getchar()==EOF) p=1;
    }
    if(getchar()==EOF) p=1;
    if(p==1 && i<7 && j<7) break;


    t=0;
    for(i=0;i<8;i++){
      for(j=0;j<8;j++){
	if(map[i][j]=='1' && t==0){
	  if(j<=6 && i<=6 ){
	    if(map[i][j+1]=='1' && map[i+1][j]=='1' && map[i+1][j+1]=='1'){
	      printf("A\n");
	      t=1;
	    }
	  }
	  
	  if(j<=7 && i<=4 ){
	    if(map[i+1][j]=='1' && map[i+2][j]=='1' && map[i+3][j]=='1'){
	      printf("B\n");
	      t=1;
	    }
	  }
	  
	  if(j<=4 && i<=7 ){
	    if(map[i][j+1]=='1' && map[i][j+2]=='1' && map[i][j+3]=='1'){
	      printf("C\n");
	      t=1;
	    }
	  }
	  
	  if(j>=1 && j<=7 && i<=5 ){
	    if(map[i+1][j-1]=='1' && map[i+1][j]=='1' && map[i+2][j-1]=='1'){
	      printf("D\n");
	      t=1;
	    }
	  }
	  
	  if(j<=5 && i<=6 && t==0){
	    if(map[i][j+1]=='1' && map[i+1][j+1]=='1' && map[i+1][j+2]=='1'){
	      printf("E\n");
	      t=1;
	    }
	  }
	  
	  if(j<=6 && i<=5 ){
	    if(map[i+1][j]=='1' && map[i+1][j+1]=='1' && map[i+2][j+1]=='1'){
	      printf("F\n");
	      t=1;
	    }
	  }
	  
	  if(j>=1 && j<=6 && i<=6 ){
	    if(map[i][j+1]=='1' && map[i+1][j-1]=='1' && map[i+1][j]=='1'){
	      printf("G\n");
	      t=1;
	    }
	  }
	}
	if(t==1) break;
      }
      if(t==1) break;
    }
    if(p==1) break;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	
	int N, k;
	
	int x, y, ans;
	
	cin >> N >> k;
	
	for(int i = 0; i < k; i++){
		cin >> x >> y;
		if(x > N / 2){
			x = N - x + 1;
		}
		if(y > N / 2){
			y = N - y + 1;
		}
		if(x > y){
			ans = (y - 1) % 3 + 1;
		}else{
			ans = (x - 1) % 3 + 1;
		}
		printf("%d\n", ans);
	}
	
	return 0;
}

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

int main(int argc, char const *argv[])
{
	int n,r;
	cin>>n>>r;
	if (n<10)
	{
		cout<<r+100*(10-n)<<endl;
	}
	else
	{
		cout<<r<<endl;
	}
	return 0;
}


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

#define int long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define F first
#define S second

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

int dp[300200][2];

signed main()
{
    string s;
    cin >> s;
    dp[0][0] = 1;
    dp[1][1] = 1;
    if (s.size() == 1)
    {
        cout << 1;
        return 0;
    }
    if (s[0] == s[1])
        dp[1][0] = 0;
    else
        dp[1][0] = 2;
    for(int i = 0; i + 1 < s.size(); ++i)
    {
        for(int j = 0; j < 2; ++j)
        {
            if (dp[i][j] == 0)
                continue;
            if (j == 0)
            {
                if (s[i] != s[i + 1])
                    dp[i + 1][0] = max(dp[i][j] + 1, dp[i + 1][0]);
                if (i + 2 < s.size())
                    dp[i + 2][1] = max(dp[i][j] + 1, dp[i + 2][1]);
            }
            else
            {
                dp[i + 1][0] = max(dp[i][j] + 1, dp[i + 1][0]);
                if (i + 2 < s.size() && (s[i - 1] + s[i]) != (s[i + 1] + s[i + 2]))
                    dp[i + 2][0] = max(dp[i + 2][0], dp[i][j] + 1);
            }
        }
    }
    //cout << dp[1][0] << endl;
    cout << max(dp[(int)s.size() - 1][0], dp[(int)s.size() -1][1]);
    return 0;
}


Measured memory_bytes: 4612
#include <stdio.h>
 
int main(){
  int a, b;
  char op;
  while(scanf("%d %c %d", &a, &op, &b) && op != '?'){
    if(op == '+') a += b;
    else if(op == '-') a -= b;
    else if(op == '*') a *= b;
    else if(op == '/') a /= b;
    printf("%d\n", a);
  }
  return 0;
}


Measured memory_bytes: 2104
#include<iostream>
#include<algorithm>
#include<climits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
char b;
int main(){
  cin>>b;
  switch(b){
  case 'A':
    prin("T");
    break;
  case 'T':
    prin("A");
    break;
  case 'C':
    prin("G");
    break;
  case 'G':
    prin("C");
    break;
  }

  return 0;
}


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

int main() {
  int m1, d1, m2, d2; cin >> m1 >> d1 >> m2 >> d2;
  if(d2 != 1) {
    cout << 0 << endl;
  } else {
    cout << 1 << endl;
  }
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vel;
typedef vector<string> ves;
typedef vector<int> vei;
typedef vector<vector<ll>> vvel;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REP(a, b, m) for (ll a = (ll)(b); a < (ll)(m); a++)

int main() {
    int x,y;cin>>x>>y;
    if(y%2==0&&(2*x)<=y&&y<=(4*x)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int main(){
long long n,k;
cin>>n>>k;
long long a[n];
for(long long i=0;i<n;i++){
    cin>>a[i];
}
sort(a,a+n);
long long ans=0;
for(long long i=0;i<k;i++){
    ans+=a[i];
}
cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i++)
#define all(cont) cont.begin(), cont.end()
#define unique(a)  sort(all(a)) , (a).erase(unique((a).begin(), (a).end()),(a).end())
#define rall(cont) cont.rbegin(), cont.rend()
#define sz(x) (int)(x).size()
#define fastio          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define PB push_back
#define endl "\n"
#define f first
#define s second
#define mset(m,v) memset(m,v,sizeof(m))
#define mod 1000000007
const int N = 2e5 + 5;
#define PI acos(-1.0)
long double EPS = 1e-9;
typedef long long ll;
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
#define pqll_max priority_queue<ll> // max heap. push(),pop(),top(),size(),empty()
#define pqll_min priority_queue<ll,vector<ll>,greater<ll> >
#define lb(v,val)   lower_bound(v.begin(),v.end(),val) //first equal to or lower than [------------
#define ub(v,val)   upper_bound(v.begin(),v.end(),val) //first greater than ------------)
#define bs(v,x) binary_search(v.begin(),v.end(),x)
inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x; }
inline ll sub(int x, int y) { x -= y; if (x < 0) x += mod; return x; }
inline ll mul(ll x, ll y) { return (x%mod * 1ll * y%mod) % mod; }
inline ll pwr(ll a, ll b) { ll x = 1 % mod; while (b) { if (b & 1) x = mul(x, a); a = mul(a, a); b >>= 1; }return x % mod; }
inline ll inv(ll a) { return pwr(a, mod - 2) % mod; }
ll gcd(ll a, ll b) { if (!a)return b % mod; return gcd(b%a, a) % mod; }
#define debug(x) cout << #x << " = " << x << endl;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#define in(container) for (auto &it : container) cin>>it;
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
void solve() {
	vi v(5);
	in(v);
	rep(i, 5) {
		if (v[i] == 0) {
			cout << i + 1 << endl;
			return;
		}
	}
}
signed main()
{
	fastio;
	//cout<<fixed<<setprecision(15);
	//clock_t begin = clock();
	int tc;
	tc = 1;
	//cin >> tc;
	while (tc--) {
		solve();
	}
	//clock_t end = clock();double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;cerr << elapsed_secs;
}


//Error?
// clear lists for every test case
// print new line for each tc
// check for int or ll
// check if problem can be solved without any heavy DS like priority_queue or map



Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
  int X, Y, Z;
  cin >> X >> Y >> Z;
  X -= Z;
  cout << X/(Y+Z) << endl;
}

Measured memory_bytes: 3604
A, B, K = map(int, input().split())
for i in range(K):
    if i % 2 == 0:
        if A % 2 == 1:
            A -= 1
        B += A // 2
        A -= A // 2
    else:
        if B % 2 == 1:
            B -= 1
        A += B // 2
        B -= B // 2
print(A, B)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define pr pair<int,int>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    #define bin(x) (1ll<<(x))
    #define GG(x) if(x) {puts("error");exit(666);}
    #define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
    #define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

    const int INF=0x3f3f3f3f;
    const int MOD=998244353;
    inline int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> inline void add(T &x,const T y){x=mm(x+y);}
    inline ll qpower(ll x,ll e,int mod=MOD){ll ans=1;GG(e<0)while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=2e5+10;

    int n,mx[N],now[N];
    int solve(int d)
    {
        ll num=0;fo(i,1,d) now[i]=mx[i],num=(num*2+mx[i])%MOD;
        if(d==n) num=mm(num+1);
        else
        {
            fo(i,d+1,2*d) now[i]=mx[i-d]^1;
            fo(i,d+d+1,n) now[i]=now[i-d-d];mx[n+1]=1;
            fo(i,1,n+1) if(now[i]!=mx[i]) {num=mm(num+(now[i]<mx[i]));break;}
        }
        return num;
    }
    int f[N];
    char str[N];
    void main()
    {
        n=qread();scanf("%s",str+1);fo(i,1,n) mx[i]=str[i]-'0';
        fo(d,1,n) if(n%d==0 and (n/d)&1) f[d]=solve(d);
        fo(i,1,n) for(int j=i+i;j<=n;j+=i) f[j]=mm(f[j]+MOD-f[i]);//莫反
        ll ans=0;fo(d,1,n) if(n%d==0 and (n/d)&1) add(ans,1ll*f[d]*(d+d)%MOD);write(ans);
    }
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 2816
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
typedef long long int LL;
int n,m;
struct node{
	int l, r;
	bool friend operator < (node a,node b){
		return a.r < b.r;
	}
}a[111111];
int main()
{
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i].l,&a[i].r);
	}
	sort(a+1, a+1+m);
	int mi = 0, ans = 0;
	for(int i=1;i<=m;i++){
		if(a[i].l>=mi){
			ans ++;
			mi = a[i].r;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>   II;
typedef vector< II >      VII;
typedef vector<int>     VI;
typedef vector< VI > 	VVI;
typedef long long int 	LL;
typedef vector<LL> 		VL;
typedef unsigned long long int ULL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
//Works for forward as well as backward iteration

#define gu getchar
#define pu putchar
#define si(n) cin>>n
#define dout(n) cout<<n<<"\n"
//# define M_PI           3.14159265358979323846264338327950288

#define DRT() int t; si(t); while(t--)

#define PlUSWRAP(index,n) index = (index+1)%n		//index++; if(index>=n) index=0
#define MINUSWRAP(index,n) index = (index + n -1)%n 	//index--; if(index<0) index=n-1
#define ROUNDOFFINT(d) d = (int)((double)d + 0.5)	//Round off d to nearest integer

#define FLUSHN while(gu()!='\n')
#define FLUSHS while(gu()!=' ')

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.

int main() {
	#ifndef ONLINE_JUDGE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
	#endif
	srand(chrono::steady_clock::now().time_since_epoch().count());
	off;
	LL n,m;
	cin>>n>>m;
	VL arr(m);
	rep(i,0,m){
		cin>>arr[i];
	}
	if(m == 1 || n >= m)
		cout<<0;
	else{
		sort(ALL(arr));
		VL diff(m-1);
		rep(i,1,m){
			diff[i-1] = arr[i] - arr[i-1];
		}
		sort(ALL(diff));
		reverse(ALL(diff));
		LL sum = 0;
		rep(i,n-1,m-1){
			sum += diff[i];
		}
		cout<<sum;
	}
  	return 0;
}

Measured memory_bytes: 4708
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

#define int long long

int solve(int x) {
    if (x == 1) {
        return 1;
    }
    return 2 * solve(x / 2) + 1;
}

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

    int x;
    cin >> x;
    cout << solve(x) << endl;
}   


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li aa[100100];
li bb[100100];
li cc[100100];

int main() {
    li x, y;
    li a, b, c;
    cin >> x >> y >> a >> b >> c;
    rep(i, a) {
        cin >> aa[i];
    }
    sort(aa, aa + a);
    rep(i, b) {
        cin >> bb[i];
    }
    sort(bb, bb + b);
    rep(i, c) {
        cin >> cc[i];
    }
    sort(cc, cc + c);

    priority_queue<li> pq;
    rep(i, x) {
        pq.push(-aa[a - 1 - i]);
    }
    rep(i, y) {
        pq.push(-bb[b - 1 - i]);
    }
    for (li i = c - 1; i >= 0; i--) {
        if (-pq.top() >= cc[i]) {
            break;
        }
        pq.pop();
        pq.push(-cc[i]);
    }

    li res = 0;
    while (!pq.empty()) {
        res += -pq.top();
        pq.pop();
    }
    cout << res << endl;


    return 0;
}

Measured memory_bytes: 4724
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc154_c
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            var aList = Console.ReadLine().Split(' ').Select(int.Parse);



            string output = "YES";


            HashSet<int> aHash = new HashSet<int>(aList);


            if (aList.Count() != aHash.Count())
            {
                output = "NO";
            }



            Console.WriteLine(output);

        }
    }
}


Measured memory_bytes: 37832
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 105;
int n,m,k,mo,f[N][N][N],g[N][N][N],C[N][N],mi1[N*N],mi2[N*N];
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}

int main() {
	read(n);read(m);read(k);read(mo);
	rep(i,0,N-1){
		C[i][0]=C[i][i]=1;
		rep(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
	g[0][0][0]=1;
	const ll MOD=7LL*mo*mo;
	rep(v,1,k){
		mi1[0]=1;rep(i,1,n*m)mi1[i]=1LL*mi1[i-1]*v%mo;
		mi2[0]=1;rep(i,1,n*m)mi2[i]=1LL*mi2[i-1]*(k-v+1)%mo;
		static int xs[N][N];
		rep(j,0,m){int t=power(v-1,m-j);xs[j][0]=1;rep(x,1,n)xs[j][x]=1LL*xs[j][x-1]*(mi1[m-j]-t+mo)%mo;}
		rep(j,0,m)rep(x,0,n)xs[j][x]=1LL*xs[j][x]*mi2[x*j]%mo;
		rep(i,0,n)rep(j,0,m)if(g[v-1][i][j])rep(x,0,n-i)
			f[v][i+x][j]=(f[v][i+x][j]+1LL*g[v-1][i][j]*C[n-i][x]%mo*xs[j][x])%mo;
		rep(i,0,n){int t=power(k-v,i);xs[i][0]=1;rep(y,1,m)xs[i][y]=1LL*xs[i][y-1]*(mi2[i]-t+mo)%mo;}
		rep(i,0,n)rep(y,0,m)xs[i][y]=1LL*xs[i][y]*mi1[(n-i)*y]%mo;
		rep(i,0,n)rep(j,0,m)if(f[v][i][j])rep(y,0,m-j)
			g[v][i][j+y]=(g[v][i][j+y]+1LL*f[v][i][j]*C[m-j][y]%mo*xs[i][y])%mo;
	//	rep(i,0,n)rep(j,0,m)cerr<<i<<' '<<j<<' '<<f[v][i][j]<<' '<<g[v][i][j]<<endl;
	}
	cout<<g[k][n][m]<<endl;
	return 0;
}


Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
int cnt,n;
void dfs(int m,int d,int x){
  if(m==n){cnt++;return;}
  if(d==4 ||m>n)return;
  for(int i=x;i*i<=n;i++)dfs(m+i*i,d+1,i);
}
int main(){
  while(1){
  cin>>n;
  if(n==0)break;
  cnt=0,dfs(0,0,1),cout<<cnt<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    e = [a[i] for i in range(0, n, 2)]
    a.sort()
    o = set(a[i] for i in range(1, n, 2))
    ans = 0
    for i in range((n + 1) // 2):
        if e[i] in o:
            ans += 1
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 10128
N, Y = map(int, input().split())

flag = False
for x in range(N+1):
    for y in range(N-x+1):
        z = N - (x + y)
        if Y == 10000 * x + 5000 * y + 1000 * z:
            flag = True
            print(x, y, z)
            break
    if flag:
        break
else:
    print(-1, -1, -1)

Measured memory_bytes: 3060