akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

typedef long long ll;
typedef vector <bool> v_bool;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

bool TEST=false;
ll MOD = 1000000007;

void show(){if (TEST){cout << endl;}}
void show(string x){if (TEST){cout << x;}}
void show(string x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(ll x){if (TEST){cout << x;}}
void show(ll x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(p_ll p){
  if (TEST){cout << "{ ";show(p.first);cout << " ";show(p.second);cout << " }";}
}
void show(v_ll v){
  if (TEST){
    cout << "<begin> ";
    for (ll i=0;i<v.size();i++){show(v[i]); cout << " ";}cout <<"<end>"<< endl;
}}
void show(vv_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}
void show(vp_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}

ll mod(ll x){
  ll n=MOD;
  ll ret=x%n;
  if (ret<0)ret+=n;
  return ret;
}
void mod_self(ll &x){
  x=mod(x);
}
ll mod_inv(ll x){
  ll n=MOD;
  ll y = x,z = n-2, ret=1;
  y=mod(y);
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  return ret;
}
ll mod_pow(ll x,ll a){
  ll y = x,z = a,ret=1;
  y=mod(y);
  if (z<0)z=-z;
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  if (a<0) ret=mod_inv(ret);
  return ret;
}
v_ll mod_nck(ll n){
  v_ll nck(n+1,0);
  nck[0]=1;
  for (ll i=1;i<=n;i++){
    nck[i]=mod(nck[i-1]*(n+1-i));
    nck[i]=mod(nck[i]*mod_inv(i));
  }
  return nck;
}
v_ll mod_factorial(ll n){
  v_ll fct(n+1,0);
  fct[0]=1;
  for (ll i=1;i<=n;i++){
    fct[i]=mod(fct[i-1]*i);
  }
  return fct;
}

ll N;
vector <string> S;
int main(){
  cin >> N;
  S.assign(N+10,"");
  for (ll i=1;i<=N;i++){
    cin >> S[i];
    sort(S[i].begin(),S[i].begin()+10);
  }
  sort(S.begin()+1,S.begin()+N+1);
  ll t=1,ans=0;
  for (ll i=1;i<=N;i++){
    if (i==N || S[i]!=S[i+1]) {ans+=t*(t-1)/2;t=1;}
    else {t++;}
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
import sys
input = sys.stdin.readline
import numpy as np
def print_ans(N, D, dr):
    """Test Case
    >>> print_ans(3, 2, [[1, 2], [5, 5], [-2, 8]])
    1
    >>> print_ans(3, 4, [[-3, 7, 8, 2], [-12, 1, 10, 2], [-2, 8, 9, 3]])
    2
    >>> print_ans(5, 1, [[1],[2],[3],[4],[5]])
    10
    """
    dr = [np.array(d) for d in dr]
    ans = 0
    for i in range(N-1):
        for k in range(i + 1, N):
            multi_ar = dr[i] - dr[k] 
            abs_tmp = float(np.sum(multi_ar ** 2) ** (1/2))
            if(abs_tmp.is_integer()):
                ans += 1
    print(ans)



if __name__ == '__main__':
    N, D = map(int, input().rstrip().split())
    dr = [list(map(int, input().rstrip().split())) for _ in range(N)]
    print_ans(N, D, dr)


Measured memory_bytes: 18760
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b){
    if(*(int *)a>*(int *)b)return 1;
    return -1;
}
int main()
{   int n;
    scanf("%d",&n);
    int d[n];
    for(int i=0;i<n;i++){
        scanf("%d",&d[i]);
    }
    qsort(d,n,sizeof(int),compare);
    
    printf("%d",d[n/2]-d[n/2-1]);

    return 0;
}


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

void build(ll tree[],ll a[],ll start,ll end,ll node)
{
    if(start==end)
    {
        tree[node]=a[start];
    }else
    {
        ll mid=(start+end)/2;
        build(tree,a,start,mid,2*node);
        build(tree,a,mid+1,end,2*node+1);
        tree[node]=max(tree[2*node],tree[2*node+1]);
    }
}

ll query(ll tree[],ll start,ll end,ll l,ll r,ll node)
{
    if(start>end||start>r||end<l)
    {
        return 0;
    }
    if(start>=l&&end<=r)
    {
        return tree[node];
    }
    ll mid=(start+end)/2,t1,t2;
    t1=query(tree,start,mid,l,r,2*node);
    t2=query(tree,mid+1,end,l,r,2*node+1);
    return max(t1,t2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a[n],tree[4*n],t1,t2;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    build(tree,a,0,n-1,1);
    for(int i=0;i<n;i++)
    {
        t1=0,t2=0;
        if(i>0)
        {
            t1=query(tree,0,n-1,0,i-1,1);
        }
        if(i<n-1)
        {
            t2=query(tree,0,n-1,i+1,n-1,1);
        }
        cout<<max(t1,t2)<<"\n";
    }
}



Measured memory_bytes: 9472
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <tuple>
#include <cmath>
#include <cstring>
#include <cstdio>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

int N;
int P[50];

bool sorted() {
    bool ans = true;
    rep(i, N - 1) if (P[i + 1] < P[i]) ans = false;
    return ans;
}

int main() {
    scanf("%d", &N);
    rep(i, N) scanf("%d", &P[i]);
    if (sorted()) {
        cout << "YES" << endl;
        return 0;
    }
    rep(i, N) for (int j = i + 1; j < N; j ++) {
        swap(P[i], P[j]);
        if (sorted()) {
            cout << "YES" << endl;
            return 0;
        }
        swap(P[i], P[j]);
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,ans=0;
  cin>>n;
  vector<int> p(n);
  for(int i=0;i<n;i++){
    cin>>p[i];
  }
  for(int i=1;i<n-1;i++){
    if(p[i+1]>p[i]&&p[i]>p[i-1])ans++;
    if(p[i-1]>p[i]&&p[i]>p[i+1])ans++;
    
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int N,M;
  int H[100000];
  int A,B;
  bool good[100000];
  int i,ans;
  scanf("%d%d",&N,&M);
  for(i=0;i<N;i++){
    scanf("%d",H+i);
  }
  for(i=0;i<N;i++){
    good[i] = true;
  }
  for(i=0;i<M;i++){
    scanf("%d%d",&A,&B);
    A--;B--;
    if(H[A] == H[B]){
      good[A] = false;
      good[B] = false;
    }
    else if(H[A] > H[B]){ 
      good[B] = false;
    }
    else{
      good[A] = false;
    }
  }
  ans = 0;
  for(i=0;i<N;i++){
    if(good[i]){
      //printf("%d",i+1);
      ans++;
    }
  }
  printf("%d",ans);
}

Measured memory_bytes: 2224
#include <stdio.h>

int main(void)
{
    int a, b;
    int sum;
    int digit;
    while (scanf("%d %d", &a, &b) != EOF) {
        sum = a + b;
        digit = 1;
        while ((sum /= 10) >= 1) {
            digit++;
        }
        printf("%d\n", digit);
    }

    return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N, C;
    cin >> N >> C;
    vector<pair<ll, P>> items;
    ll T = 0;
    rep(i, N) {
        ll s, t, c;
        cin >> s >> t >> c;
        c--;
        T = max(T, t);
        items.emplace_back(c, make_pair(s, t));
    }
    vector<vector<ll>> imos(C, vector<ll>(2 * T + 5, 0));
    vector<ll> ans(2 * T + 5, 0);
    rep(j, N) {
        P p = items[j].second;
        imos[items[j].first][2 * p.first - 1]++;
        imos[items[j].first][2 * p.second]--;
    }
    rep(i, C) {
        rep(j, 2 * T + 4) {
            imos[i][j + 1] += imos[i][j];
            if (imos[i][j + 1] >= 1) {
                ans[j + 1]++;
            }
        }
    }
    cout << (*max_element(ans.begin(), ans.end())) << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 51824
#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    int k =(a + b)/2;
    if (a - k == k - b)
    {
        cout << k;
    }
    else
    {
        cout << "IMPOSSIBLE";
    } 
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false)
int a[200000], vs[200000],vs1[100006],p[300000];
vector<int>v[200000];
queue<int>q;
int f(int n)
{
    int i, k=0;
    vs[n]=1; q.push(n);
    while(q.size()){
            n=q.front(); q.pop();
    for(i=0; i<v[n].size(); i++){
        if(vs1[v[n][i]]==1){
        p[v[n][i]]=n;
        q.push(v[n][i]);
    }
    else vs1[v[n][i]]--;
    }
    }
    return 1;
}
int main()
{
    IO;
    int i, j, m, k, n, t, l=0, mx,ll,mxx,mx1;
    cin>>n>>m;
    for(i=1; i<=n+m-1; i++){
        cin>>j>>k;
        v[j].push_back(k);
        vs1[k]++;
    }
    for(i=1; i<=n; i++)
        if(vs1[i]==0)k=i;
    f(k);
    for(i=1; i<=n; i++) cout<<p[i]<<endl;
    return 0;

}


Measured memory_bytes: 10240
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
using namespace std;


int main(){
    FIO
    ll n;
    cin>>n;
    ll flag=0;
    ll i;
    for( i=sqrt(n);i>0;i--){
        if(n%i==0){
            flag=1;
            break;
        }else{
            flag=0;
        }
    }
    
    ll sum=0;
    if(!flag){
        sum = n-1;
    }else{
       sum = i+n/i-2; 
    }
    cout<<sum;
    
}

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

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins
        self.amins = list(range(N))

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            if self.mins[v] > self.mins[u]:
                self.mins[v] = self.mins[u]
                self.amins[v] = self.amins[u]
            self.mins[u] = -1
            self.amins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.mins[u] > self.mins[v]:
                self.mins[u] = self.mins[v]
                self.amins[u] = self.amins[v]
            self.mins[v] = -1
            self.amins[v] = -1

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A.copy())

for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)


mins = [x for x in uf.mins if x != -1]
amins = set([x for x in uf.amins if x != -1])
ans = sum(mins)
A = [a for i, a in enumerate(A) if i not in amins]
A.sort()
ntrees = len(mins)
if ntrees == 1:
    print(0)
    exit()
if ntrees * 2 - 2 > N:
    print("Impossible")
    exit()
ans += sum(A[:ntrees - 2])
print(ans)


Measured memory_bytes: 25772
class NormalInput {
  input: string[];
  pointer: number;
  constructor(raw: string) {
    this.input = raw.split(/ |\n/);
    this.pointer = 0;
  }
  int = (): number => {
    const ret = parseInt(this.input[this.pointer], 10);
    this.pointer++;
    return ret;
  };
  str = (): string => {
    const ret = this.input[this.pointer];
    this.pointer++;
    return ret;
  };
  strs = (length: number): string[] => {
    let ret: string[] = [];
    for (let i = 0; i < length; i++) {
      ret.push(this.str());
    }
    return ret;
  };
  ints = (length: number): number[] => {
    let ret: number[] = [];
    for (let i = 0; i < length; i++) {
      ret.push(this.int());
    }
    return ret;
  };
}
function rep(a: number, b: number) {
  let arr = [];
  for (let i = a; i < b; i++) arr.push(i);
  return arr;
}

function Main({ int, str, strs, ints }: NormalInput) {
  const [N, K] = ints(2);
  const sunuke = rep(0, N).map((i) => true);
  for (let i = 0; i < K; i++) {
    const d = int();
    const A = ints(d);
    A.forEach(a=>{
      sunuke[a-1]=false;
    })
  }

  console.log(sunuke.filter(s=>s==true).length);
}

//DO NOT EDIT
Main(new NormalInput(require("fs").readFileSync("/dev/stdin", "utf8")));


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

using namespace std;

string t, s;

int main() {
	cin >> s >> t;
	s += s;
	for(int i = 0; i < t.length(); ++i) {
		if(s.substr(i, t.length()) == t) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int A, B, C, D, L, R;
	cin >> A >> B >> C >> D;
	if ((L = A + B) > (R = C + D))
		cout << "Left" << endl;
	else if (L == R)
		cout << "Balanced" << endl;
	else
		cout << "Right" << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
        public static void main(String args[]) {
                try (Scanner sc = new Scanner(System.in)) {
                        int N = sc.nextInt();
                        int[] A = new int[N];
                        long ans = 1;
                        for (int i = 0; i < N; i++) {
                                int B = sc.nextInt();
                                if (B >= N) {
                                        ans = 0;
                                }
                                A[B]++;
                                if (A[B] > 2) {
                                        ans = 0;
                                }
                        }
                        if (A[0] > 1) {
                                ans = 0;
                        }
                        boolean f = true;
                        long memo = 1;
                        for (int i = 1; i < N; i+=2) {
                                if (A[i] == 0) {
                                        f = false;
                                } else if(f == false) {
                                        memo = -1;
                                } else {
                                        if (A[i] == 1) {
                                                f = false;
                                        } else {
                                                memo *= A[i];
                                                memo %= 1e9+7;
                                        }
                                }
                        }
                        if (memo == -1) {
                                ans = 0;
                        }
                        if (ans != 0) {
                                ans = Math.max(ans, memo);
                        }
                        f = true;
                        memo = 1;
                        for (int i = 2; i < N; i+=2) {
                                if (A[i] == 0) {
                                        f = false;
                                } else if(f == false) {
                                        memo = -1;
                                } else {
                                        if (A[i] == 1) {
                                                f = false;
                                        } else {
                                                memo *= A[i];
                                                memo %= 1e9+7;
                                        }
                                }
                        }
                        if (memo == -1) {
                                ans = 0;
                        }
                        if (ans != 0) {
                                ans = Math.max(ans, memo);
                        }
                        System.out.println(ans);


                }
        }
}

Measured memory_bytes: 32316
#include <cstdio>
#include <iostream>
#define MN 5010
#define mod 1000000007

int f[MN][MN][2], s[MN];
int sum[MN][2], mi[MN];

int inc(int a, int b) {return (a += b) >= mod ? a - mod : a;}

int main()
{
	int n, a, b; scanf("%d%d%d", &n, &a, &b);
	if(a > b) std::swap(a, b);
	mi[0] = 1; for(int i = 1; i <= n; i++) mi[i] = mi[i - 1] * 2 % mod;
	f[0][0][0] = f[0][0][1] = s[0] = 1;
	sum[0][1] = 1;
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= std::min(b, i); j++)
		{
			if(j == b)
				ans = (ans + 1ll * mi[n - i] * (sum[i - j][0] + sum[i - j][1])) % mod;
			else
			{
				f[i][j][0] = sum[i - j][1];
				f[i][j][1] = sum[i - j][0];
				s[i] = inc(s[i], f[i][j][0]);
			}
		}
		for(int j = std::max(i - a + 1, 0); j < i; j++)
			f[i][0][1] = inc(f[i][0][1], s[j]);
		if(i - a >= 0)
		{
			for(int j = 0; j <= i - a; j++)
			{
				if(j + a < b)
					f[i][j + a][1] = inc(f[i][j + a][1], f[i - a][j][0]);
				else 
					ans = (ans + 1ll * mi[n - i] * f[i - a][j][0]) % mod;
				
				sum[i - a - j][0] = inc(sum[i - a - j][0], f[i - a][j][0]);
			}
		}
		for(int j = 0; j <= i; j++)
			sum[i - j][1] = inc(sum[i - j][1], f[i][j][1]);
	}
	printf("%d\n", ans);
}

/*考虑检查一种方案是否合法
倒推，相当于把A个0或B个1替换成任意数字
假设 A<=B ，否则相当于初始全为1，然后交换A，B
序列合法当且仅当把所有>=A的0连续段给替换为1后存在>=B的1连续段
充分性就是存在>=B的1连续段后把这个段给全部赋值成0与左右两段0合并
由于B>=A，所以新的0段也可以全部赋成1然后继续搞
必要性就是如果不存在，那除了那些0段可以随便填以外无法进行任何操作，从而无解，逆否命题可知必要性成立
f[i][j + i - k][0] = sigma f[k][j][1]
j + i - k > B 的状态不转移 (=B的状态单独处理，直接对答案贡献)

f[i][0][1] = sigma f[i - A + 1 ~ i][j][0] 长度不够

f[i][j + i - k][1] = sigma f[k][j][0] k < i - A (k = i - A 单独处理，直接对答案贡献)
j + i - k > B 的状态不转移 (=B的状态单独处理，直接对答案贡献)
*/

Measured memory_bytes: 120588
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll int dp[(1<<16)];
ll int sums[(1<<16)];

ll int calculate(vector< vector<ll int> > &score,ll int mask)
{
	ll int ans=0;
	for(int i=0;i<17;i++)
	{
     for(int j=i+1;j<17;j++)
     {if(  ((mask&(1<<i))!=0) && ((mask&(1<<j))!=0) )
     	ans+=score[i][j];

     }

	}
	return ans;
}
ll preparesums(vector< vector<ll int> > &score,ll int n)
{
for(ll int subset=1;subset<(1<<n);subset++)
{
	sums[subset]=calculate(score,subset);
}	

}

ll solve(vector< vector<ll int> > &score,ll int mask)
{
	if(mask==0)
		return 0;
	if(dp[mask]!=INT_MAX)
		return dp[mask];
	dp[mask]=0;
	for(ll int submask=mask;submask!=0;submask=((submask-1)&mask))
	{
		dp[mask]=max(dp[mask],sums[submask]+solve(score,(mask^submask) ));
	}
	return dp[mask];
}
int main()
{
   
 ll int n;
 cin>>n;
 vector< vector<ll int> > score(n,vector<ll int> (n));
 
for(ll int i=0;i<(1<<n);i++)
	dp[i]=INT_MAX;


 for(ll int i=0;i<n;i++)
 {for(ll int j=0;j<n;j++)
 	cin>>score[i][j];}
 	preparesums(score,n);
 	ll int d=solve(score,((1<<n)-1));
 	cout<<d<<endl;



}

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

string s, t;
map<char, vector<int>>occ;
int find_next(int i, char c) {
	auto nxt = lower_bound(occ[c].begin(), occ[c].end(), i);
	if (nxt != occ[c].end()) return *nxt;
	if (occ[c].size() > 0) {
		return occ[c][0];
	}
	return -1;
}


int main() {
	cin >> s >> t;
	rep(i, s.size()) {
		occ[s[i]].push_back(i);
	}
	ll ans = 0;
	int now = 0;
	for(char c: t) {
		int nxt = find_next(now, c);
		if (nxt == -1) {
			ans = -1;
			break;
		}
		if (now <= nxt) ans += nxt - now + 1;
		else ans += s.size() - now + nxt + 1;
		now = (nxt + 1) % s.size();
	}
	cout << ans << endl;
}


Measured memory_bytes: 1216
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#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, M;
  cin>>N>>M;
  int X[N];
  for(int i=0;i<N;++i) cin>>X[i];
  map<int, int> amap, bmap;
  for(int i=0;i<N;++i) {
    amap[X[i]%M]++;
    bmap[X[i]]++;
  }
  map<int, int> cmap;
  for(int i=1;i<=100000;++i) {
    cmap[i%M] += bmap[i]/2;
  }
  int ans = 0;
  ans += amap[0]/2;
  if(M%2==0) {
    for(int i=1;i<M/2;++i) {
      if(amap[i]>amap[M-i]){
        ans += amap[M-i];
        amap[i] -= amap[M-i];
        amap[M-i] = 0;
        ans += min(amap[i]/2, cmap[i]);
      }
      else {
        ans += amap[i];
        amap[M-i] -= amap[i];
        amap[i] = 0;
        ans += min(amap[M-i]/2, cmap[M-i]);
      }
    }
    ans += amap[M/2]/2;
  }
  else {
    for(int i=1;i<=M/2;++i) {
      if(amap[i]>amap[M-i]){
        ans += amap[M-i];
        amap[i] -= amap[M-i];
        amap[M-i] = 0;
        ans += min(amap[i]/2, cmap[i]);
      }
      else {
        ans += amap[i];
        amap[M-i] -= amap[i];
        amap[i] = 0;
        ans += min(amap[M-i]/2, cmap[M-i]);
      }
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 17992
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

const int MOD = 1000000007;

long long max(long long a,long long b){
	if(a<b)return b;
	else return a;	
}
long long min(long long a,long long b){
	if(a>b)return b;
	else return a;	
}
long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	else return gcd(a%b,b);
}

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


long long getDigit(long long n){
	if(n==1)return 1;
	else return log10(n)+1;
}

class Point{
public:
	long long x;
	long long y;
};
long long N,M;
vector<long long>X(100006,0);
bool isOK(long long N){
	string s=to_string(N);
	set<char>set;
	for(int i=0;i<s.length();i++){
		set.insert(s[i]);
	}
	return set.size()==1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin>>s;
	long long ans=INF;
	for(int i=0;i<s.length()-2;i++){
		ans=min(ans,abs((s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0')-753));
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <stdio.h>

using namespace std;

void Solution()
{
    int i, j, n, f;
    
    string s1,s2;
    
    cin>>n;
    
    while(n--)
    {
        cin>>s1>>s2;
        
        f=0;
        
        if(s1.size() < s2.size())
        {
            swap(s1, s2);
        }
        
        for(i = 0; i < s2.size(); i++)
        {
            s1[i + s1.size() - s2.size()] += s2[i] - '0';
        }
        
        for(i = s1.size() - 1; i > 0; i--)
        {
            if(s1[i] > '9')
            {
                s1[i] -= 10;
                s1[i - 1]++;
            }
        }
        
        if(s1[0] > '9')
        {
            s1[0] -= 10;
            
            f++;
        }
        
        if(s1.size() + f <= 80)
        {
            if(f) cout<<"1";
           
            cout<<s1;
        }
        else
        {
            cout<<"overflow";
        }
        
        cout<<endl;
    }
}

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

Measured memory_bytes: 1208
package main

import "fmt"

func main(){
	var s string
	textedit(s)

}

func textedit(s string){
	/*入力を受け取る*/
	fmt.Scan(&s)

	/*入力をstring→文字の配列*/
	sRune := []rune(s)
	size := len(s)

	/*空の文字列*/
	s2 := make([]string, size+1)	
	j := 0;

	for i:=0; i<size; i++{
		switch text := string(sRune[i]); text{
		case "1":
			s2[j]=string(sRune[i])
			j++

		case "0":
			s2[j]=string(sRune[i])
			j++

		case "B":
			if j>0{
				j--
			}

		default:

		}
	}

	for i:= 0; i < j; i++{
		fmt.Printf(s2[i])
	}

	fmt.Printf("\n")

}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,m,n) for(int i=(m);i<(n);i++)
#define debug(a,b) cout << "debug : " << a << " , "<< b << endl
using ll=long long;
const ll INF=1LL<<60;
const ll mod=1E9+7;

ll power(ll a,ll b,ll mod){
  if(b==0)return 1;
  ll u=power(a,b/2,mod);
  u=(u*u)%mod;
  if(b%2)u=(a*u)%mod;
  return u;
}


int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll>pcs(k+1,0);
  Rep(i,1,k+1)pcs[i]=power(k/i,n,mod);
  
  for(int i=k;i>=1;i--){
    for(int j=2*i;j<=k;j+=i){
      pcs[i]=(pcs[i]-pcs[j]+mod)%mod;
    }
  }
  ll ans=0;
  rep(i,k+1){
    ans+=(pcs[i]*(ll)i)%mod;
    ans%=mod;
  }
  cout << ans;

  return 0;

}







Measured memory_bytes: 4044
#include <stdio.h>
long long a [100010];
int main (){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
int zero =0;

for(int i=0;i<n;i++)if(a[i]==0) zero ++;
if(zero >0){
// a[i] contains 0
printf("0\n");
return 0;
}
long long prod =1;
for(int i=0;i<n;i++){
if(a[i ] <=1000000000000000000/ prod ){
// This condition is equivalent to prod*a[i] <=10ˆ18
prod *=a[i];
}else{
printf("-1\n");
return 0;
}
}
printf("%lld\n",prod );
}


Measured memory_bytes: 2516
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))

import sys
stdin = sys.stdin
def tokens(): return stdin.readline().strip().split()
def ints(): return map(int, tokens())
def int1(): return int( stdin.readline().strip() )

INF = 2147483647



N = int1()

aa = ints()

total = 3**N
odds = 1
for a in aa:
    if a & 1 == 0:
        odds *= 2

print total - odds



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

int main() {

    int n,w;

    cin >> n >> w;

    vector<long long int> v[4];

    int weight;
    long long int value;

    cin >> weight >> value;

    v[0].push_back(value);

    for(int i=0; i<n-1; i++){
        int input_w;
        long long int input_v;
        cin >> input_w >> input_v;
        v[input_w-weight].push_back(input_v);
    }

    for(int i=0; i<4; i++){
        sort(v[i].begin(),v[i].end());
        reverse(v[i].begin(),v[i].end());
        v[i].push_back(0LL);
    }

    long long int ans = 0;

    for(int i=0; i<v[0].size(); i++){

        long long int tmp_ans = 0;
        int tmp_w =0;
        for(int r=0; r<i; r++){
            if(w >= tmp_w + weight + 0){
                tmp_w += weight + 0;
                tmp_ans += v[0][r];
            }
        }

        for(int j=0; j<v[1].size(); j++){

            long long int j_tmp = tmp_ans;
            int j_w_tmp = tmp_w;

            for(int r=0; r<j; r++){
                if(w >= j_w_tmp + weight + 1){
                    j_w_tmp += weight + 1;
                    j_tmp += v[1][r];
                }
            }

            for(int k=0; k<v[2].size(); k++){

                long long int k_tmp = j_tmp;
                int k_w_tmp = j_w_tmp;

                for(int r=0; r<k; r++){
                    if(w >= k_w_tmp + weight + 2){
                        k_w_tmp += weight + 2;
                        k_tmp += v[2][r];
                    }
                }

                for(int p=0; p<v[3].size(); p++){

                    long long int p_tmp = k_tmp;
                    int p_w_tmp = k_w_tmp;

                    for(int r=0; r<p; r++){
                        if(w >= p_w_tmp + weight + 3){
                            p_w_tmp += weight + 3;
                            p_tmp += v[3][r];
                        }
                    }
                    ans = max(ans,p_tmp);

                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int func(const void *a, const void *b){
  return *(int*)a - *(int*)b;
}
int main(void){
  int n, d[100000] = {0};
  scanf("%d", &n);getchar();
  for(int i = 0; i < n; i++){
    scanf("%d", &d[i]);getchar();
  }
  qsort(d, n, sizeof(int), func);
  
  printf("%d\n", d[n / 2] - d[(n / 2) - 1]);
  return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n; i++)
#define all(v) (v).begin(), (v).end()
#define decimal fixed << setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
  char x;
  cin>>x;
  char ans='x';
  switch(x){
    case 'A':
    ans='T';
    break;
    case 'T':
    ans='A';
    break;
    case 'C':
    ans='G';
    break;
    case 'G':
    ans='C';
    break;
    }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N = int(input())
a = 0
w = 0
t = 0
r = 0
for i in range(N):
    S = input()
    if S == "AC":
        a += 1
    elif S == "WA":
        w += 1
    elif S == "TLE":
        t += 1
    elif S == "RE":
        r += 1
print("AC","x",a)
print("WA","x",w)
print("TLE","x",t)
print("RE","x",r)

Measured memory_bytes: 9212
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

ll N,ans,mini=1e9,A,cnt;
bool ck=false;

int main(){
    cin>>N;
    rep(i,N){
        cin>>A;
        if(!A)ck=true;
        else if(A<0) cnt++;
        ans+=abs(A);
        if(A)mini=min(mini,abs(A));
    }
    if(cnt%2==0||ck){
        out(ans);
    }
    else{
        out(ans-mini*2);
    }
}


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

#define rep(i, s, n) for (Int i = s; i < (Int)(n); i++)
#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
double EPS = 1e-10;
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int main() {
    Int n, k;
    cin >> n >> k;
    vector<bool> d(10, false);
    rep(i, 0, k) {
        Int x;
        cin >> x;
        d[x] = true;
    }
    while (true) {
        string s = to_string(n);
        bool check = true;
        rep(i, 0, s.size()) {
            if (d[s[i] - '0']) {
                check = false;
            }
        }
        if (check) break;
        n++;
    }
    dump(n);
    return 0;
}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100

ll N, A, B;
vector<ll> V;
vector< pair<ll, ll> > V2;   // first: val second: count

ll dp[MAX_N][2];
ll combination(ll n, ll r) {
    ZERO(dp);
    dp[0][0] = 1;
    int ind1 = 1;
    int ind2 = 0;
    for(ll i = 1; i <= n+1; ++i) {
        dp[0][ind1] = 1;
        for(ll j = 1; j <= i; ++j) {
            dp[j][ind1] = (dp[j-1][ind2] + dp[j][ind2]);
        }
        swap(ind1, ind2);
    }
    return dp[r][ind1];
}

signed main()
{
    cin >> N >> A >> B;
    REP(i, N) {
        ll tmp;
        cin >> tmp;
        V.push_back(tmp);
    }

    sort(V.begin(), V.end(), greater<ll>());
    ll prev = 0;
    ll cnt = 0;
    for(auto& v : V) {
        if(prev == 0) {
            prev = v;
            cnt++;
            continue;
        }
        if(prev != v) {
            V2.push_back(make_pair(prev, cnt));
            cnt = 1;
        } else {
            cnt++;
        }
        prev = v;
    }
    V2.push_back(make_pair(prev, cnt));
    sort(V2.begin(), V2.end(), greater< pair<ll, ll> >());
    ll ans = 0;
    ll prev_sum = 0;
    double ch = 0.0;
    double mo = 0.0;
    for(auto& v2 : V2) {
        DBG("prev_sum: %lld v2.first: %lld v2.second: %lld ch: %f\n",
                prev_sum, v2.first, v2.second, ch);
        ll cur = v2.second;
        if(prev_sum == 0) {
            if(cur >= B) {
                for(int i = A; i <= B; ++i) { ans += combination(cur, i); }
                ch = (double)(v2.first);
                mo = 1.0;
                break;
            }
            else if(cur >= A) {
                for(int i = A; i <= cur; ++i) { ans += combination(cur, i); }
                ch = (double)(v2.first);
                mo = 1.0;
                break;
            }
            else {
                prev_sum += cur;
                ch += (double)(v2.first) * (double)(v2.second);
            }
        } else {
            if(prev_sum + cur >= A) {
                ans += combination(cur, A - prev_sum);
                ch += (double)(v2.first) * (double)(A - prev_sum);
                mo = (double)(A);
                break;
            } else {
                prev_sum += cur;
                ch += (double)(v2.first) * (double)(v2.second);
            }
        }
    }

    printf("%f\n", ch / mo);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
//string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n ; cin >> n ;
	string s = to_string(n) ;
	bool nine = true ;
	for(int i=0;i<s.size()-1;i++){
		if(s.at(s.size()-1-i)!='9') nine = false ;
	}
	ll ans ;
	if(nine) ans = (s.size()-1)*9+s.at(0)-'0' ;
	else ans = (s.size()-1)*9+s.at(0)-1-'0' ;
	cout << ans << endl ;
}


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

using namespace std;

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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

int n;
long double a[200];

int main()
{
	IOS;
	cin >> n;
	long double s = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		s += 1 / a[i];
	}
	s = 1 / s;
	cout << s << endl;
	return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(s: str):
    answer = 0
    for i in range(len(s)):
        ss = s[i]
        if i%2 == 0 and ss=='p':
            answer -= 1
        
        if i%2==1 and ss=='g':
            answer +=1
    
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
N, M = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort()

v = 0
ans = 0

for a, b in l:
    if b+v >= M:
        ans += a*(M-v)
        break
    else:
        ans += a*b
        v+=b

print(ans)

Measured memory_bytes: 16988
#include <iostream>
#include <string>

using namespace std;
int main(void)
{
	string question,answer;

	while( cin >> question >> answer && question != "0" ){
		int hit = 0;
		int blow = 0;

		for( int i = 0;i < 4;i++ ){
			if( question[i] == answer[i] ){
				question[i] = answer[i] = -1;
				hit++;
			}
		}
		for( int i = 0;i < 4;i++ ){
			for( int j = 0;j < 4;j++ ){
				if( question[i] == -1 ) continue;
				if( question[i] == answer[j] ) blow++;
			}
		}
		cout << hit << " " << blow << endl;
	}
	return 0;
}

Measured memory_bytes: 916
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  Int n,d;
  cin>>n>>d;
  vector<Int> ds(n);
  for(Int i=0;i<n;i++) cin>>ds[i];
  // [0, i)
  vector<Int> ps(n);
  {
    Int cur=d;
    for(Int i=0;i<n;i++){
      ps[i]=cur;
      cur=min(cur,abs(cur-ds[i]));
    }
  }

  // min r s.t. before i
  // [i, n)
  vector<Int> rs(n+1);
  rs[n]=1;
  for(Int i=n-1;i>=0;i--){
    rs[i]=rs[i+1]+ds[i];
    if(abs(rs[i+1]-ds[i])>=rs[i+1])
      chmin(rs[i],rs[i+1]);
  }

  Int q;
  cin>>q;
  vector<Int> qs(q);
  for(Int i=0;i<q;i++){
    cin>>qs[i],qs[i]--;
    cout<<(rs[qs[i]+1]<=ps[qs[i]]?"YES":"NO")<<"\n";
  }
  return 0;
}


Measured memory_bytes: 17536
import sys
sys.setrecursionlimit(10**9)
P = 2019

S = input()
N = len(S)
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)


Measured memory_bytes: 68272
# coding: utf-8
# Your code here!

n,k = list(map(int,input().split()))
x = list(map(int,input().split()))

d=0
#print(x)

d= x[k-1]-x[0]
ans = d + min(abs(x[k-1]),abs(x[0]))
#print(d,ans)
for i in range(n-k):
    d += x[k+i] - x[k-1+i] 
    d -= x[i+1] - x[i]
    c=d + min(abs(x[k+i]),abs(x[i+1]))
#    print(d,c)
    ans = min(ans,c)



print(ans)        
    

Measured memory_bytes: 14228
// Problem : B - Tap Dance
// Contest : AtCoder Beginner Contest 141
// URL : https://atcoder.jp/contests/abc141/tasks/abc141_b
// Memory Limit : 1024,000000 MB 
// Time Limit : 2000,000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor2)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <vector>

using namespace std;

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

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cout.precision(16);
  cout << fixed;
  
  string odd = "RUD";
  string even = "LUD";
  
  string s;
  cin >> s;
  
  for (int i = 0; i < (int)s.length(); ++i) {
    int tmp = i + 1;
    
    if ((tmp % 2 != 0 && odd.find(s[i]) == string::npos) ||
        (tmp % 2 == 0 && even.find(s[i]) == string::npos)) {
      cout << "No";
      
      return 0;
    }
  }
  
  cout << "Yes";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  int a, b;
  cin >> a >> b;
  if (a <= 8 && b <= 8) P("Yay!");
  else P(":(");
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

int main(){
  int n,l,ans=0;
  cin >> n >> l;
  if(l<=0&&0<=l+n-1){ans=0;}
  if(0<l){ans=l;}
  if(l+n-1<0){ans=l+n-1;}
  
  ans = (l + l+n-1)*n/2 -ans;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d,e;
	cin>>a;
	cin>>b;
	if(a<b){
		int i=0;
		i=b;
		b=a;
		a=i;
	}
	cin>>c;
	if(a<c){
		int i=0;
		i=c;
		c=a;
		a=i;
	}
	if(b<c){
		int i=0;
		i=c;
		c=b;
		b=i;
	}
	cin>>d;
	if(a<d){
		int i=0;
		i=d;
		d=a;
		a=i;
	}
	if(b<d){
		int i=0;
		i=d;
		d=b;
		b=i;
	}
	if(c<d){
		int i=0;
		i=d;
		d=c;
		c=i;
	}
	cin>>e;
	if(a<e){
		int i=0;
		i=e;
		e=a;
		a=i;
	}
	if(b<e){
		int i=0;
		i=e;
		e=b;
		b=i;
	}
	if(c<e){
		int i=0;
		i=e;
		e=c;
		c=i;
	}
	if(d<e){
		int i=0;
		i=e;
		e=d;
		d=i;
	}
	cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;
}

Measured memory_bytes: 3088
n,m=map(int,input().split())
x=list(map(int,input().split()))
if n>=m:print(0)
else:
  x.sort()
  l=[]
  for i in range(m-1):
    l.append(x[i+1]-x[i])
  l.sort()
  ct=0
  for j in range(m-n):
    ct+=l[j]
  print(ct)

Measured memory_bytes: 13960
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,a[222222];
  cin>>n;
  int su[222222]={};
  int sum=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    sum+=a[i];
    su[i]=sum;
  }
  int ans=1e18;
  for(int i=2;i<n-1;i++){
    int ma=0,mi=1e18;
    int sum=su[i-1];
    int ok=0,ng=i-1,mid;
    while(ng-ok>1){
      mid=(ok+ng)/2;
      if(su[mid]<=sum/2)ok=mid;
      else ng=mid;
    }
    
    
    int l=su[ok],r=su[i-1]-su[ok];
    int tl=su[ok+1],tr=su[i-1]-su[ok+1];
    
    if(ok!=i-2&&abs(tr-tl)<abs(r-l)){
      l=tl;
      r=tr;
    }

    ma=max(r,ma);
    ma=max(l,ma);
    mi=min(r,mi);
    mi=min(l,mi);
    
    sum=su[n-1]-su[i-1];
    ok=i,ng=n-1;
    while(ng-ok>1){
      mid=(ok+ng)/2;
      if(su[mid]-su[i-1]<=sum/2)ok=mid;
      else ng=mid;
    }

    l=su[ok]-su[i-1],r=sum-l;
    tl=su[ok+1]-su[i-1],tr=sum-tl;
    
    if(ok!=i-2&&abs(tr-tl)<abs(r-l)){
      l=tl;
      r=tr;
    }

    ma=max(r,ma);
    ma=max(l,ma);
    mi=min(r,mi);
    mi=min(l,mi);
    
   
    ans=min(ma-mi,ans);
    
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3712
function main(input) {
    const args = input.split('/');
    var Y = parseInt(args[0], 10);
    var M = parseInt(args[1], 10);
    var D = parseInt(args[2], 10);

    if(Y < 2019) {
        console.log('Heisei')
    } else if(Y === 2019 && M < 4) {
        console.log('Heisei')
    } else if (Y === 2019 && M === 4 && D <= 30) {
        console.log('Heisei')
    } else {
        console.log('TBD')
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 300010;
#define int ll
pair<int,int> loc[maxn], ne[maxn];
int dis(auto a, auto b) {
	return abs(a.first-b.first) + abs(a.second-b.second);
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	stack<int> st;
	int n;
	cin >> n;
	for (int i = 0;i < n;++i) {
		cin >> loc[i].first >> loc[i].second;
		ne[i].first = loc[i].first + loc[i].second;
		ne[i].second = loc[i].first - loc[i].second;
	}
	vector<pair<int,int>> pos;
	pos.pb(*max_element(ne, ne+n));
	pos.pb(*min_element(ne, ne+n));
	pos.pb(*max_element(ne, ne+n, [&](auto a, auto b) {
			return a.second < b.second;
			}));
	pos.pb(*min_element(ne, ne+n, [&](auto a, auto b) {
		return a.second < b.second;
		}));
	for (auto &[x, y] : pos) {
		int nx = x+y, ny = x-y;
		x = nx, y = ny;
	}
	ll res = 0;
	for (auto i : pos) for (auto j : pos)
		res = max(res, dis(i, j));
	assert(res % 2 == 0);
	cout << res / 2<< '\n';
}


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

#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define pb emplace_back

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ") 
{ rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

int main() {
	int n;
	
	while (cin >> n, n) {
		bool f[101][101] = {false};
		rep(i, n) {
			int m = in();
			rep(j, m) {
				f[i][in()] = true;
			}
		}

		vi a, l;
		
		int k = in();
		rep(i, k) l.pb(in());

		rep(i, n) {
			bool beet = true;
			rep(j, l.size()) {
				if (!f[i][l[j]]) beet = false;
			}
			if (beet) a.pb(i + 1);
		}

		cout << (a.size() == 1 ? a[0] : -1) << endl;
	}
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;

#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define rep(i, n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define ZP(a, len) cout << setfill('0') << setw(len) << right << a << endl;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

signed main() {
    int n;
    cin >> n;
    vi p = vi(n);
    rep(i, n) cin >> p[i];

    sort(ALL(p));
    int ans = accumulate(p.begin(), p.end() - 1, 0);
    ans += p[p.size() - 1] / 2;

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

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

int main() {
	int H;
	int W;

	cin >> H;
	cin >> W;

	char **m = new char* [H];

	for (int i = 0; i < H;i++) {
		m[i] = new char[W];
	}

	for (int h = 0; h < H;h++) {
		for (int w = 0; w < W;w++) {
			cin >> m[h][w];
		}
	}

	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			int count = 0;
			if (m[h][w]=='#') {
				cout << "#";
			}
			else {
				//上列
				if (w - 1 >= 0 && h - 1 >= 0 && m[h - 1][w - 1] == '#') {
					count++;
				}
				if (h - 1 >= 0 && m[h - 1][w] == '#') {
					count++;
				}
				if (h - 1 >= 0 && w + 1 < W&&m[h - 1][w + 1] == '#') {
					count++;
				}
				//中列
				if (w - 1 >= 0 && m[h][w - 1] == '#') {
					count++;
				}
				if (w + 1 < W&&m[h][w + 1] == '#') {
					count++;
				}
				//下列
				if (w - 1 >= 0 && h + 1 < H && m[h + 1][w - 1] == '#') {
					count++;
				}
				if (h + 1 < H && m[h + 1][w] == '#') {
					count++;
				}
				if (h + 1 < H && w + 1 < W&&m[h + 1][w + 1] == '#') {
					count++;
				}

				cout << count;
			}
		}
		cout << endl;
	}

	return 0;
}



Measured memory_bytes: 256