akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<cassert>
#include<map>
#include<set>

using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<b;++i)
#define fj(a,b) for(int j=a;j<b;++j)
#define fo(a,b) for(int o=a;o<b;++o)
#define fdi(a,b) for(int i=a-1;i>=b;--i)
#define fdj(a,b) for(int j=a-1;j>=b;--j)
#define fdo(a,b) for(int o=a-1;o>=b;--o)
#define mp make_pair
#define pb push_back
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
////////////////////////

int n;
map<int, int> q;
int ans;

void solve(){
	for(pii it : q){
		int v = it.first;
		int q = it.second;
		if(q >= v) ans += (q - v);
		else ans += q;
	}
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	scanf("%d",&n);
	fi(0, n){
		int v;
		scanf("%d",&v);
		++q[v];
	}

	solve();

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

	return 0;
}

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

int main()
{
    string c;

    cin >> c;

    if(c == "Sunny") cout << "Cloudy" << endl;
    else if(c == "Cloudy") cout << "Rainy" << endl;
    else cout << "Sunny" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<string>v;
int main()
{
	string s;
	int k;
	cin>>s>>k;
	for(int i=0;i<s.size();i++)
		for(int j=0;j+i<s.size()&&j<5;j++)v.push_back(s.substr(i,j+1));
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	cout<<v[k-1]; 
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			(3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
template<class T> void chmax(T &a, const T &b){if(a<b)a=b;}
template<class T> void chmin(T &a, const T &b){if(a>b)a=b;}
void YN(bool b){cout<<(b?"YES":"NO")<<endl;}
void Yn(bool b){cout<<(b?"Yes":"No")<<endl;}
void yn(bool b){cout<<(b?"yes":"no")<<endl;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	vl v(3);
	rep(i,3)cin>>v[i];
	sort(all(v));
	cout<<v<<endl;
}




Measured memory_bytes: 3140
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<numeric>
#include<algorithm>
#include<limits.h>
#include<utility>
#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(i,n,a) for(int i=0;i<n;i++)cin >> a[i]
long long int n;
using namespace std;

int main(){
    char c;
    cin >> c;
    if('A' == c)cout << 'T' << endl;
     if('T' == c)cout << 'A' << endl;
     if('C' == c)cout << 'G' << endl;
          if('G' == c)cout << 'C' << endl;
          return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int r,c,k;
    cin >> r >> c >> k;
    int i,j;
    long long **v;
    v = (long long**)malloc(sizeof(long long *) * r);
    for (i=0;i<r;i++) {
        v[i] = (long long*)malloc(sizeof(long long) * c);
    }
    for(i=0;i<r;i++){
        for(j=0;j<c;j++)v[i][j]=0;
    }
    int ri, ci, vi;
    for(i=0;i<k;i++){
        cin >> ri >> ci >> vi;
        v[ri-1][ci-1] = vi;
    }

    long long ki[4][c];
    for(i=0;i<c;i++){
        for(j=0;j<4;j++) ki[j][i]=0;
    }

    for(i=0;i<r;i++){
        ki[1][0]=ki[0][0] + v[i][0];
        ki[2][0]=ki[1][0];
        ki[3][0]=ki[1][0];
        //cout << ki[3][c-1] << endl;
        for(j=1;j<c;j++){
            ki[1][j] = max(max(ki[1][j-1], ki[0][j]), ki[0][j] + v[i][j]);
            ki[2][j] = max(max(ki[2][j-1], ki[1][j]), ki[1][j-1] + v[i][j]);
            ki[3][j] = max(max(ki[3][j-1], ki[2][j]), ki[2][j-1] + v[i][j]);
        }
        for(j=0;j<c;j++){
            ki[0][j] = ki[3][j];
        }
    }
    cout << ki[3][c-1] << endl;
    return 0;
}

Measured memory_bytes: 73908
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1)<<endl;
    return 0;
}

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

int main()
{
    string s;
    getline (cin,s);
    int n=s.size();
	int aa=0,ba=0;
	
	for(int i=0;i<n;i++)
	{
		if(i%2==0)
		{
			if(s[i]=='0')
			   ba++;
			else
			   aa++;
		}
		else 
		  if(s[i]=='1')
		  	ba++;
		  else
		    aa++;
	}
	
		  if(aa<ba)
		    cout<<aa;
		  else
		    cout<<ba;
	
	return 0;
}

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

#define _sel(_1, _2, x, ...) x
#define repn(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, ...) _sel(__VA_ARGS__, reps, repn)(i, __VA_ARGS__)
#define reppn(i, n) for (ll i = 1; i <= (n); i++)
#define repps(i, a, b) for (ll i = (a); i <= (b); i++)
#define repp(i, ...) _sel(__VA_ARGS__, repps, reppn)(i, __VA_ARGS__)
#define rrepn(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, a, b) for (ll i = (b) - 1; i >= (a); i--)
#define rrep(i, ...) _sel(__VA_ARGS__, rreps, rrepn)(i, __VA_ARGS__)
#define rreppn(i, n) for (ll i = (n); i >= 1; i--)
#define rrepps(i, a, b) for (ll i = (b); i >= (a); i--)
#define rrepp(i, ...) _sel(__VA_ARGS__, rrepps, rreppn)(i, __VA_ARGS__)

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define rng(v) (v).begin(), (v).end()
#define rrng(v) (v).rbegin(), (v).rend()
#define _shv(v) for (auto _t1 : v) cerr << _t1 << " "; cerr << endl;
#define dg(x) cerr << #x << ": " << (x) << endl;
#define dgv(v) cerr << #v << ": "; _shv(v);
#define dgm(m) cerr << #m << ":" << endl; for (auto _t2 : m) { _shv(_t2); }

using namespace std;
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;

const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
const int DX[4] = {1, 0, -1, 0};
const int DY[4] = {0, 1, 0, -1};

template<typename T> inline void pt(T x) { cout << x << endl; }
template<typename T> inline void inv(T& v) { for (auto& t : v) cin >> t; }
template<typename T> inline int siz(T& x) { return x.size(); }
template<typename T> inline ll pow2(T n) { return 1ll << n; }
template<typename T, typename U> inline int bit(T x, U n) { return x >> n & 1; }
template<typename T, typename U>
inline bool umax(T& m, U x) { if (m < x) { m = x; return true; } return false; }
template<typename T, typename U>
inline bool umin(T& m, U x) { if (m > x) { m = x; return true; } return false; }


int main() {
    string s, t;
    cin >> s >> t;

    vvl dp(siz(s) + 1, vl(siz(t) + 1, 0));
    rep(i, siz(s)) {
        rep(j, siz(t)) {
            if (s[i] == t[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                if (dp[i + 1][j] > dp[i][j + 1])
                    dp[i + 1][j + 1] = dp[i + 1][j];
                else
                    dp[i + 1][j + 1] = dp[i][j + 1];
            }
        }
    }

    string ans = "";
    int i = siz(s), j = siz(t);
    while (i && j) {
        if (s[i - 1] == t[j - 1]) {
            ans.pb(s[i - 1]);
            i--;
            j--;
        } else {
            if (dp[i][j - 1] > dp[i - 1][j]) {
                j--;
            } else {
                i--;
            }
        }
    }
    reverse(rng(ans));
    pt(ans);

    return 0;
}


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

struct gates {
	int b;
	int e;
}s[100010];

int main ()
{
	int n,m;
	cin>>n>>m;
	int maxb=0,mine=10000000;
	for(int i=0;i<m;i++)
	{
		cin>>s[i].b>>s[i].e;
		if(s[i].b>maxb)
		{
			maxb=s[i].b;
		}
		if(s[i].e<mine)
		{
			mine=s[i].e;
		}
	}
	if(mine-maxb+1>0)
	{
		cout<<mine-maxb+1<<endl;
		return 0;
	}
	else{
		cout<<'0'<<endl;
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
long long a[87]={2,1},n,i;
int main()
{
    cin>>n;
    for(i=2;i<=n;i++)
    a[i]=a[i-1]+a[i-2];
    cout<<a[n]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
long long a[maxn],b[maxn];
long long f(long long t,long long*a,int A){
    int p=lower_bound(a,a+A,t)-a;
    if(p>=A)p--;
    long long ans=1e13;
    ans=abs(a[p]-t);
    if(p>=1)ans=min(ans,abs(a[p-1]-t));
    return ans;
}
int main()
{
    int A,B,q;
    cin>>A>>B>>q;
    for(int i=0; i<A; i++)
    {
        scanf("%lld",&a[i]);
        //cout<<a[i]<<endl;
    }
    for(int i=0; i<B; i++)
    {
        scanf("%lld",&b[i]);
    }
    sort(a,a+A),sort(b,b+B);
    while(q--)
    {
        long long t;
        scanf("%lld",&t);
        int p1=lower_bound(a,a+A,t)-a;
        if(p1>=A)p1--;
        long long ans=1e13;
        ans=min(ans,abs(a[p1]-t)+f(a[p1],b,B));
        if(p1>=1)ans=min(ans,abs(t-a[p1-1])+f(a[p1-1],b,B));
        p1=lower_bound(b,b+B,t)-b;
        if(p1>=B)p1--;
        ans=min(ans,abs(b[p1]-t)+f(b[p1],a,A));
        if(p1>=1)ans=min(ans,abs(t-b[p1-1])+f(b[p1-1],a,A));
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 2944
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    s = s_input()
    t = s_input()

    len_s = len(s)
    len_t = len(t)

    if len_s < len_t:
        print('UNRESTORABLE')
        exit()

    ans_list = []

    flag = False
    for i in range(len_s-len_t+1):
        tmp_s = s[i:i+len_t]
        for j in range(len_t):
            if tmp_s[j] != t[j] and tmp_s[j] != '?':
                break
        else:
            flag = True
            ans_s = s[0:i] + t + s[i+len_t:len_s]
            ans_list.append(ans_s.replace('?', 'a'))

    if not flag:
        print('UNRESTORABLE')
        exit()

    ans_list.sort()

    print(ans_list[0])
 
if __name__ == '__main__':
    main()


Measured memory_bytes: 77160
N = int(input())
ab = sorted([list(map(int,input().split())) for i in range(N)])
diff = {}
for i in range(N-1):
    for j in range(i+1,N):
        a = (ab[i][0]-ab[j][0],ab[i][1]-ab[j][1])
        if a not in diff:
            diff[a] = 1
        else:
            diff[a] += 1
if diff:
    maxv = max(diff.values())
    print(N-maxv)
else:
    print(N)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
const int INF = 1e+8;
#define REP(i, n) for(int i=0;i<n;++i)
typedef pair<int, int> P;

//迷路
char maze[100][100];
//．をカウントするため
string s ;
// w:幅h:高さ
int w, h;
//最短距離
int d[101][101];
//近傍
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};


int bfs(){
  queue<P> que;
  // すべて点を初期化
  REP(i, h) REP(j, w) d[i][j] = INF;
  // スターと地点をキューに入れてその点の距離を0
  que.push(P(0, 0));
  d[0][0] = 0;

  while(que.size()){
    P p = que.front();
    que.pop();
    // 取り出した状態がゴールなら探索を止める
    if(p.first == h-1 && p.second == w-1) break;
    ;
    REP(i, 4){
      int ny = p.first + dy[i];
      int nx = p.second + dx[i];
      //if( nx < 0 || ny < 0 || nx >= w || ny >= h ) continue;
      // 範囲外に出たときは次の処理へ
      if(0 <= ny && ny < h && 0 <= nx && nx < w
          && maze[ny][nx] != '#' && d[ny][nx] == INF){
	        que.push(P(ny, nx));
	        d[ny][nx] = d[p.first][p.second] + 1;
      }
    }
  }

  return d[h-1][w-1];
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> h >> w;

    int cnt = 0;
    for(int x=0 ; x < h ; x++ ){
        cin >> s;
        for(int y=0 ; y < w ; y++ ){
            if( s[y] == '.') cnt++;
            maze[x][y] = s[y];
        }
    }

    //白全部　ー　最短経路　＝　塗れる白
    int ans = bfs();

    if ( ans ==  INF ){
        cout << "-1" << endl;
    }else{
        cout << cnt - ans - 1  << endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int abs(int a){return a>=0?a:-a;}
int arr[99999][2], map[99999];
int main(){
	int h,w,d; scanf("%d%d%d",&h,&w,&d);
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			int a; scanf("%d",&a);
			arr[a][0] = i; arr[a][1]=j;
		}
	}
	for(int i = d; i <= h*w; i++){
		map[i]=map[i-d]+abs(arr[i][0]-arr[i-d][0])+abs(arr[i][1]-arr[i-d][1]);
	}
	int q; scanf("%d",&q);
	for(int i = 1; i <= q; i++){
		int a,b; scanf("%d%d",&a,&b);
		printf("%d\n",map[b]-map[a]);
	}
}

Measured memory_bytes: 2048
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
 
N=II()
xs=LI()
 
cur = 1
idx = 0
res = 0
for x in xs:
    if x == cur:
        cur += 1
    else:
        res += 1
if cur != 1:
    print(res)
else:
    print(-1)

Measured memory_bytes: 25116
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;

    int ans = 2*n;
    rep(i, n) {
        bool c = true;
        rep(j, n-i) {
            if (s[i+j] != t[j]) {
                c = false;
                break;
            }
        }
        if (c) {
            ans = n+i;
            break;
        }
    }

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

Measured memory_bytes: 256
import sys
while True:
    ls = map(int, raw_input().split())
    if ls[0]==0 and ls[1]==0:
        break
    for h in xrange(ls[0]):
        for w in xrange(ls[1]):
            if h==0 or h==ls[0]-1 or w==0 or w==ls[1]-1:
                sys.stdout.write('#')
            else:
                sys.stdout.write('.')
        print ''
    print ''
                

Measured memory_bytes: 6376
N,K = map(int,input().split())
h = list(map(int,input().split()))

cost = [0]
for i in range(2,N+1):
    cost.append( min([cost[j] + abs(h[i-1]-h[j]) for j in range(max(0,i-K-1), i-1)]) )
print(cost[-1])


Measured memory_bytes: 20680
import sys
def win(c, line):
	for i in range(0, 9, 3):
		if all(p == c for p in line[i:i + 3:1]):
			return True
	for i in range(3):
		if all(p == c for p in line[i:i + 9:3]):
			return True
	if all(p == c for p in line[0::4]): return True
	if all(p == c for p in line[2:8:2]): return True
	return False;
for line in sys.stdin:
	for c in ['o', 'x']:
		if win(c, line):
			print c
			break
	else:
		print 'd'

Measured memory_bytes: 4248
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  int64_t c=0;
  for(int b=k+1;b<=n;b++)
    for(int x=0;x<=n/b;x++)
      c+=max(min(n-x*b,b-1)+1-k,0);
  cout<<c-(k==0?n:0)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int X,t;
  cin >> X >> t;
  cout << max(0,X-t) << endl;
  return 0;
}


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

int main(){
	int n,x,t;
	cin>>n>>x>>t;
	if(n%x==0)
	{
		cout<<(n/x)*t<<endl;
	}
	else
	{
		cout<<((n/x)+1)*t<<endl;
	}
	
  return 0;

}

    






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

int main(){
  int n;
  int dum = 0;
  int dum_bar_1 = 0;
  cin >> n;
  vector<int> a(n);
  vector<int> out(n);

  for(int i = 0 ; i < n ; i++){
    cin >> a[i];
    dum += a[i];
  }
  for(int i = 0 ; i*2+1 < n ; i++){
    dum_bar_1 += a[2*i+1];
  }
  out[0] = dum - (dum_bar_1 * 2);

  for(int i = 1 ; i < n ; i++){
    out[i] = (a[i-1] -  out[i-1]/2)*2;
  }

  for(int i = 0 ; i < n-1 ; i++){
    cout << out[i] << " ";
  }
  cout << out[n-1] << endl;

  return 0;
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j,l,m;
    ll h,w,k;
    cin >> h >> w >> k;
    const ll MOD = 1e9+7;
    vector<vector<ll>> dp(h+1,vector<ll>(w,0));
    dp.at(0).at(0) = 1;
    for(i = 0;i < h;++i){
        rep(j,w){
            rep(l,(1 << (w-1))){
                bool flag = true;
                rep(m,w-2){
                    if((l & (1 << m)) && (l & (1 << m+1))) flag = false;
                }
                if(flag){
                    if(j >= 1 && (l & (1 << j-1))){
                        dp.at(i+1).at(j-1) += dp.at(i).at(j);
                        dp.at(i+1).at(j-1) %= MOD;
                    }else if(j <= w-2 && (l & (1 << j))){
                        dp.at(i+1).at(j+1) += dp.at(i).at(j);
                        dp.at(i+1).at(j+1) %= MOD;
                    }else{
                        dp.at(i+1).at(j) += dp.at(i).at(j);
                        dp.at(i+1).at(j) %= MOD;
                    }
                }
            }
        }
    }
    cout << dp.at(h).at(k-1) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int gcd(int x, int y) {
  while (y != 0) {
    int r = x % y;
    x = y;
    y = r;
  }
  return x;
}

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

  vector<int> dif(n);
  for (int i = 0; i < n; i++) {
    int a; cin >> a;
    dif[i] = abs(a-X);
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans = gcd(ans, dif[i]);
  }

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <numeric>
#include <limits>
#include <numeric>
#include <type_traits>
using namespace std;
typedef pair<int, int> P;

typedef long long ll;
const int MOD = 1000000007;

int main(){  
  int N,A,B;
  cin >> N >> A >> B;
  cout << min(N*A,B);
}



Measured memory_bytes: 256
#include <stdio.h>
long long Min(long long a,long long b){
    return a<=b?a:b;
}
int main()
{   long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    if(a%2==1&&b%2==1&&c%2==1){
        printf("%lld",Min(a*b,Min(b*c,c*a)));
    }else{
        printf("0");
    }

    return 0;
}


Measured memory_bytes: 128
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define dpr(x) cerr<<#x<<": "<<x<<endl;
#define dprc(c) do{cerr<<#c<<":";for(auto&_i:(c)){cerr<<" "<<_i;}cerr<<endl;}while(0)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
int INF = 1e9+7;
#define all(c) (c).begin(), (c).end()
#define tr(i,c) for(auto i=(c).begin();i!=(c).end();i++)
#define rtr(i,c) for(auto i=(c).rbegin();i!=(c).rend();i++)
#define rep(i,b) for(auto i=0;i<(b);i++)
#define pb push_back
#define sz(c) int((c).size())

#define HASH_SIZE (1000003)

enum ALPHABET {
  C,
  T,
  G,
  A,
  NUL,
};

struct node {
  string key;
  struct node *next;
};

struct node *H[HASH_SIZE];
struct node H_instance[HASH_SIZE];

int calchash(string& s) {
  int res = 0;
  for (int i = 0; i < sz(s); i++) {
    res = (res*47 + s[i])%HASH_SIZE;
  }
  return res;
}

void insert(string& s) {
  int h = calchash(s);

  node *p = H[h];
  while (p->next != nullptr) {
    if (p->key == s) return;
    p = p->next;
  }
  node *n = new node;
  n->key = s;
  n->next = nullptr;
  p->next = n;
}

bool find(string& s) {
  int h = calchash(s);

  for (node *p = H[h]->next; p != nullptr; p = p->next) {
    if (p->key == s) return true;
  }
  return false;
}

int main(int argc, char **argv)
{
  for (int i = 0; i < HASH_SIZE; i++) {
    H[i] = &H_instance[i];
    H[i]->key = string("x"); // will not be matched with input
    H[i]->next = nullptr;
  }

  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    char cmd[16], sc[16];
    scanf("%s %s", cmd, sc);
    string s(sc);
    if (cmd[0] == 'i') insert(s);
    else if (cmd[0] == 'f') {
     if (find(s)) cout << "yes" << endl;
     else cout << "no" << endl;
    }
  }
  return 0;
}

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

int main(){
  int t,n,s,f,cnt;
  while(true){
    cin>> t;
    cnt = 0;
    if(t==0)break;
    cin >> n;
    for(int i=0;i<n;i++){
      cin >> s >> f;
      cnt+= f-s;
    }
    if(cnt >= t)cout<< "OK" << endl;
    else cout << t-cnt << endl;

  }
  return 0;
}

Measured memory_bytes: 1160
# -*- coding: utf-8 -*-
w, a, b = map(int, input().split())
ax = [a + x for x in range(w + 1)]
bx = [b + x for x in range(w + 1)]
if a > b:
    print(ax[0] - bx[-1] if ax[0] - bx[-1] >= 0 else 0)
elif a < b:
    print(bx[0] - ax[-1] if bx[0] - ax[-1] >= 0 else 0)
else:
    print(0)

Measured memory_bytes: 11032
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
string pin = "";
int ans = 0;
void checkPin(){
    //cout << pin << endl;
    int pin0 = -1;
    int pin1 = -1;
    int pin2 = -1;
    for(int i = 0; i < n; i++){
        if(pin0==-1){
            if(pin[0]==s[i]){
                pin0=i;
            }
        }else if(pin1==-1){
            if(pin[1]==s[i]){
                pin1=i;
            }
        }else if(pin2==-1){
            if(pin[2]==s[i]){
                pin2=i;
                //cout << pin << endl;
                ans++;
                break;
            }
        }else{
            break;
        }
    }    
}
void dfs(int digit){
    char c = '0';
    if((0<=digit)&&(digit<=9)){
        c+=digit;
    }
    pin+=c;
    if(pin.length()>=3){
        checkPin();
        return;
    }else{
        for(int i = 0; i <= 9; i++){
            dfs(i);
            pin.pop_back();
        }
    }
}
int main(){
    cin >> n;
    cin >> s;
    for(int i = 0; i <= 9; i++){
        dfs(i);
        pin.pop_back();
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3692
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <deque>
#include <numeric>
using lint = long long;

int main()
{

    lint n, m;

    scanf("%lld", &n);
    scanf("%lld", &m);

    std::map<lint, lint, std::greater<lint>> map;

    for (int i = 0; i < n; ++i)
    {
        lint a;
        scanf("%lld", &a);

        if (map.find(a) == map.end())
        {
            map[a] = 1;
        }
        else
        {
            map[a]++;
        }
    }

    for (int i = 0; i < m; ++i)
    {
        lint b, c;
        scanf("%lld", &b);
        scanf("%lld", &c);

        if (map.find(c) == map.end())
        {
            map[c] = b;
        }
        else
        {
            map[c] += b;
        }
    }

    lint sum = 0;
    lint card_num = 0;

    for (auto num = map.begin(); num != map.end(); num++)
    {
        if (card_num + num->second <= n)
        {
            sum += num->first * num->second;
            card_num += num->second;
        }
        else
        {
            sum += num->first * (n - card_num);
            break;
        }
    }

    printf("%lld", sum);

    return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
long double const pi = std::acos(-1.0L);
typedef pair<int,int> P;
const int INF = 1001001001;


int main() {
  int x;
  cin >> x;
  if(x==1) cout << "0" << endl;
  else cout << "1" << endl;
  return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define mod 1000000007
#define P pair<int,int>
using namespace std;
int n;
int mutu(int b){
	if(b>n) return (int)(0);
	int c=b,x=0;
	bool b3=false,b5=false,b7=false;
	while(c){
		if(c%10==3) b3=true;
		else if(c%10==5) b5=true;
		else b7=true;
		c/=10;
	}
	if(b3&&b5&&b7) x++;
	x+=mutu(b*10+3)+mutu(b*10+5)+mutu(b*10+7);
	return x;
}
signed main(){
	cin>>n;
	cout<<mutu(0)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
signed main(){
    bool f = true;
    long long x , a , b , i , j;
    cin >> x;
    
    for(a=-1000 ;a<=1000 ;a++){
        for(b=-1000; b<=1000 ;b++){
            if(a*a*a*a*a - b*b*b*b*b == x){
                i = a , j = b;
            }
        }
    }
    
    cout << i << ' ' << j << ' ' << endl;
    return(0);
}

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

int main(){

    int n;
    cin >> n;
    for(int b = 0; b < (1<<n); b++){
        cout << b << ":";
        for(int i = 0; i < n; i++){
            if((b>>i) & 1){
                cout << " " << i;
            } 
        }
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3092
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define ms(a,v) memset(a,v,sizeof(a))
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; }return 0; }
constexpr ll pow2(const int n) { return 1ll << n; }
constexpr int INF = 1 << 28; constexpr ll LINF = 1ll << 60;
constexpr int MAX = 1e5 + 5; constexpr int MOD = 1e9 + 7; constexpr double EPS = 1e-6;
constexpr int dy[4] = { 0,1,0,-1 }; constexpr int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;
// 1. 問題よくよめえええええええええええええええええええええええええ
// 2. intオーバーフロー << * + あたり
// 3. 落ち着け

int N;
vi b;
vi ans;

int dfs(int n, vector<int> v) {
    if (n == 1 && v[0] == 1) return 1;

    for (int i = 0; i < n; ++i) {
        if (v[i] == i + 1) {
            vector<int> w(v);
            w.erase(w.begin() + i);
            int ret = dfs(n - 1, w);
            if (ret) {
                ans.push_back(ret);
                return i + 1;
            }
        }
    }

    return 0;

}

int main() {
    cin >> N;
    b.resize(N);
    rep(i, N) cin >> b[i];

    bool can = true;
    rep(i, N) {
        if (b[i] > i + 1) {
            can = false;
        }
    }

    if (!can) {
        write(-1);
        return 0;
    }

    ans.resize(N);

    rep(i, N) {
        for (int j = b.size() - 1; j >= 0; --j) {
            if (b[j] == j + 1) {
                ans[i] = j + 1;
                b.erase(b.begin() + j);
                break;
            }
        }
    }
    reverse(all(ans));

    rep(i, N) {
        write(ans[i]);
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arra[n+5];
    for(int i=0; i<n; i++)
    {
        cin>>arra[i];
    }
    int cnt=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(arra[j]!=arra[i])
            {
                int sum=arra[i]+arra[j];
                // cout<<sum<<endl;
                for(int k=j+1; k<n; k++)
                {
                    int sum1=arra[i]+arra[k];
                    int sum2=arra[j]+arra[k];

                    if(sum>arra[k]   && sum1>arra[j] &&sum2>arra[i]&& arra && arra[i]!=arra[j] && arra[i]!=arra[k] && arra[j] !=arra[k])
                    {
                       // cout<<i<<" "<<j<<" "<<k<<endl;
                      //  cout<<sum<<" "<<arra[k]<<endl;
                        cnt++;
                    }
                }
            }

        }

    }
    cout<<cnt<<endl;

}


Measured memory_bytes: 3628
#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

struct Data {
  int idx;
  int P; // prefacture
  int Y; // year
};
inline bool operator<(const Data& a, const Data& b) { return a.Y > b.Y; }

int keta(int a) {
  auto as = to_string(a);
  return as.length();
}

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

  map<int, priority_queue<Data>> pms;
  int p, y;
  for(int i = 0; i < M; ++i) {
    cin >> p >> y;
    pms[p].push({i, p, y});
  }

  auto compare_idx = [](Data a, Data b) { return a.idx > b.idx; };
  priority_queue<Data, vector<Data>, decltype(compare_idx)> ans(compare_idx); // (index, (p, y));
  for(auto pm : pms) {
    int y = 1;
    while(!pm.second.empty()) {
      auto top = pm.second.top();
      pm.second.pop();
      ans.push({top.idx, top.P, y});
      y++;
    }
  }
  while(!ans.empty()) {
    auto a = ans.top();
    ans.pop();

    int pk = max(6, keta(a.P));
    cout << setfill('0') << right << setw(pk) << a.P;
    int yk = max(6, keta(a.Y));
    cout << setfill('0') << right << setw(yk) << a.Y << endl;
  }

  return 0;
}

Measured memory_bytes: 13684
n = int(input())
F = []
for i in range(n):
    F.append(input().replace(" ", ""))
P = []
for i in range(n):
    P.append(list(map(int, input().split())))

ans = -1e10
for i in range(1, 2**10):
    s = 0
    for j in range(n):
        tmp = int(F[j], 2)
        tmp = i & tmp
        c = bin(tmp).count("1")
        s += P[j][c]
    if s > ans:
        ans = s
print(ans)


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

int main() {
  int A, B, S = 0, N;
  cin >> A >> B;
  N = B - A;
  for(int i = 0; i <= N; i++){
  if(A / 10000 == A % 10 && A % 10000 / 1000 == A % 100 / 10 ){
    S++;
  	}
    A++;
  }
  cout << S;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9+7;
 
int main(){
  int n;
  cin >> n;
  vector<char> s(n);
  bool T= false;
  for(int i=0; i<n; i++){
    cin >> s[i];
    if(s[i]=='Y') T=true;
  }

  if(T){
    cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int64_t L0 = 2;
  int64_t L1 = 1;
  int N;
  cin >> N;
  for (int i = 1; i < N; i++)
  {
    int64_t s = L1;
    L1 += L0;
    L0 = s;
  }
  cout << L1 << endl;
}

Measured memory_bytes: 256
# encoding: utf-8
N = int(input())
A = list(map(int, input().split()))

Amb = sorted([Ai - (i + 1) for i, Ai in enumerate(A)])
b = Amb[N // 2]

ans = 0
for i, Ambi in enumerate(Amb):
    if i <= N // 2: ans += b - Ambi
    else: ans += Ambi - b

print(ans)

Measured memory_bytes: 26708
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll n;
    cin >> n;
    REP(i, 9){
        REP(j, 9){
            if((i + 1) * (j + 1) == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>

#define MOD 1e9+7;
#define INF 1e17+9;
#define PI acos(-1);

typedef long long LL;

using namespace std;

int two_div(LL x){
	int cnt=0;
	while(1){
		if(x%2!=0 || x==0){
			return cnt;
		}else{
			cnt++;	
			x/=2;
		}
	}	
	return cnt;
}

int main(){
	int n;
	cin >> n;
	vector<LL> a(n);
	int sum=0;
	
	for(int i=0;i<n;i++){
		cin >> a[i];
		if(a[i]%2==0)sum+=two_div(a[i]);
	}
	
	cout << sum << endl;
	return 0;
}


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

#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<30)
#define INFLL (1LL<<62LL)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  rep(i, N) cin >> A[i] >> B[i];

  ll ans = 0;
  for (int i = N - 1; i >= 0; i--) {
    ll now = ans + A[i];
    ll target_val = ceil(1.0 * now / B[i]) * B[i];
    ans += target_val - now;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define B 998244353ll
#define C 1000000000000000000ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.1415926535

ll dp[10005][10][105],pre[10005][105],ans[10005][105];

int main() 
{
    FAST;
    string k;
    cin>>k;
    ll n,d;
    n=k.length();
    cin>>d;
    for(int i=0;i<10;i++)
    {
        dp[0][i][i%d]++;
        pre[0][i%d]++;
    }
    for(int i=1;i<10005;i++)
        for(int j=0;j<10;j++)
            for(int w=0;w<d;w++)
            {
                dp[i][j][(w+j)%d]=(dp[i][j][(w+j)%d]+pre[i-1][w])%A;
                pre[i][(w+j)%d]=(pre[i][(w+j)%d]+pre[i-1][w])%A;
            }
    reverse(k.begin(),k.end());
    for(int i=0;i<=k[0]-'0';i++)
        for(int j=0;j<d;j++)
            ans[0][j]=(ans[0][j]+dp[0][i][j])%A;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<k[i]-'0';j++)
            for(int w=0;w<d;w++)
                ans[i][(w+j)%d]=(ans[i][(w+j)%d]+pre[i-1][w])%A;
        for(int w=0;w<d;w++)
            ans[i][(w+(k[i]-'0'))%d]=(ans[i][(w+(k[i]-'0'))%d]+ans[i-1][w])%A;
    }
    cout<<(ans[n-1][0]+A-1)%A;
    return 0;
}

Measured memory_bytes: 98816
#include<bits/stdc++.h>
using namespace std;
int a[1001]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51}; 
int main(){
	int k;
	cin>>k;
	cout<<a[k-1];
}



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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define rep(i,n) for(int i=0;i<n;i++)
#define mp(a,b) make_pair(a,b)
const ll MOD=1000000007;

int main(){
	int n; cin>>n;
    int ans=0;
    vector<int> d(n);
    rep(i,n) cin>>d[i];
  sort(d.begin(),d.end());
  printf("%d",d[n/2]-d[n/2-1]);
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
  double a, b, c, d, e, f;
  double x, y;

  while(scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF){
    y = (c * d - a * f) / (b * d - a * e);
    x = (c - (b * y)) / a;

    printf("%.3f %.3f\n", x, y);
  }

  return(0);
}

Measured memory_bytes: 652
n = int(input())
h = list(map(int, input().split()))
progress = [0]*n
ans = 0
MAX = max(h)

for i in range(MAX):
  for j in range(n):
    if progress[j] < h[j]:
      progress[j] += 1
      if j+1 >= n:
        ans += 1
      elif j+1 < n:
        if progress[j+1] == h[j+1]:
          ans += 1

print(ans)


Measured memory_bytes: 3064
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    if M <= N:
        print(0)
        return
    X.sort(reverse=True)
    diff = []
    pre = X.pop()
    for i in range(M - 1):
        cur = X.pop()
        heappush(diff, cur - pre)
        pre = cur
    ans = 0
    for _ in range(M - N):
        ans += heappop(diff)
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 57128
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void run(void){
  int n;
  scanf("%d",&n);
  int *a=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  int *b=(int *)malloc(sizeof(int)*n);
  int l=0;
  int r=n-1;
  i=n-1;
  while(i>=1){
    b[l++]=a[i--];
    b[r--]=a[i--];
  }
  if(i>=0) b[l]=a[i];

  printf("%d",b[0]);
  for(i=1;i<n;i++) printf(" %d",b[i]);
  printf("\n");
  return;
}

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


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e16+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

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

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll a,b,q;
    cin>>a>>b>>q;

    set<ll> s;
    set<ll> t;
    s.insert(-1e11);
    t.insert(-1e11);
    s.insert(1e11);
    t.insert(1e11);
    rep(i,a){
        ll tmp;
        cin>>tmp;
        s.insert(tmp);
    }
    rep(i,b){
        ll tmp;
        cin>>tmp;
        t.insert(tmp);
    }
    while(q--){
        ll ans=INF;
        ll x;
        cin>>x;
        ll ra,la,rb,lb;
        {
            auto it = s.lower_bound(x);
            ra = *it;
            it--;
            la = *it;
        }
        {
            auto it = t.lower_bound(x);
            rb = *it;
            it--;
            lb = *it;
        }

        la = x-la;
        lb = x-lb;
        ra = ra-x;
        rb = rb-x;

        ans = min(ans,max(la,lb));
        ans = min(ans,max(ra,rb));
        ans = min(ans,ra*2+lb);
        ans = min(ans,la*2+rb);
        ans = min(ans,rb*2+la);
        ans = min(ans,lb*2+ra);
        cout<<ans<<endl;
    }
    return  0;
}


Measured memory_bytes: 10752
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define sz(x) (int)(x).size()

const int N = 100100;
int h[N], f[N], n, k;

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

  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> h[i];

  f[n - 1] = 0;
  for (int i = n - 2; i >= 0; i--) {
    int x = min(n - 1, i + k);
    f[i] = abs(h[i] - h[i + 1]) + f[i + 1];
    for (int j = i + 1; j <= x; j++)
      f[i] = min(f[i], abs(h[i] - h[j]) + f[j]);
  }

  cout << f[0] << "\n";
}



Measured memory_bytes: 4416
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
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; }
//constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;
const long double PI = acos((long double)(-1));

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;


vector<ll> dijkstra(int start, vector<vector<pair<int, ll>>>& graph) {
    vector<ll> dist(graph.size(), INF); dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.emplace(0, start);
    while (!pq.empty()) {
        ll cost; int idx; tie(cost, idx) = pq.top(); pq.pop();
        if (dist[idx] < cost) continue;
        for (auto next : graph[idx]) if (chmin(dist[next.first], cost + next.second)) pq.emplace(dist[next.first], next.first);
    }
    return dist;
}

void solve() {
    int n, m, s, t[2]; scanf("%d %d %d %d %d", &n, &m, &s, &t[0], &t[1]); if (n == 0) exit(0);
    s--; t[0]--; t[1]--;
    vector<vector<pair<int, ll>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        u--; v--;
        g[u].emplace_back(v, w);
    }
    vector<vector<ll>> d(n); for (int i = 0; i < n; i++) d[i] = dijkstra(i, g);
    ll res = INF;
    for (int i = 0; i < n; i++) {
        ll sm = d[s][i] + d[i][t[0]] + d[i][t[1]];
        chmin(res, sm);
    }
    printf("%lld\n", res);
}
int main()
{
    /*
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    */

    int kkt = 89;
    while (kkt) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3300
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll>PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e4+7;
int main() {
    int n;
    ll x;
    cin >> n >> x;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    ll rest = x;
    while( 1 ) {
        if ( ans == n ) {
            if ( rest != 0 ) --ans;
            break;
        }
        if ( rest - a[ans] < 0 ) break;
        rest -= a[ans];
        ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
while True:
    n = int(raw_input())
    if n != 0:
        max = -9999999999999
        a =[int(raw_input()) for i in range(n)]
        #print a
        for j in range(0,n):
            sum = 0
            for k in range(0,n-j):
                sum += a[k+j]
                if sum > max:
                    max = sum
        print max
    else:
        break


Measured memory_bytes: 4896
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <set>
#include <limits.h>

#define rep(i,N) for(int (i)=0;(i)<(N);(i)++)
#define MOD 1000000007

using ll = long long;

using namespace std;

ll pow_mod(ll a, ll b, ll p) {
	if (b == 0)return 1;
	else if (b % 2 == 0)return (pow_mod(a*a, b / 2, p) % p);
	else return (pow_mod(a, b - 1, p)*a%p);
}

ll sum_digit(ll N) {
	int ans = 0;
	for (; N != 0;) {
		ans += N % 10;
		N /= 10;
	}
	return ans;
}

ll gcd(ll a,ll b) {
	if (!b)return a;
	return gcd(b, a%b);
}

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

int N,Y;

int ans = 0;

int main(){
	scanf("%d %d", &N, &Y);
	for (int i = 0; i < N + 1; i++) {
		for (int j = 0; j < N + 1 - i; j++) {
			if (Y == 9000 * i + 4000 * j + 1000 * N) {
				printf("%d %d %d", i, j, N - i - j);
				return 0;
			}
		}
	}
	printf("-1 -1 -1");
	return 0;
}

Measured memory_bytes: 256