akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for (int i = m; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;

bool isOK(vector<int>& p) {
    rep(i, p.size() - 1) {
        if (p[i] > p[i+1]) {
            return false;
        }
    }
    return true;
}
signed main()
{
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i, n) cin >> p[i];

    if (isOK(p)){
        println("YES");
        return 0;
    }


    
    rep(i, n - 1) rep2(j, i+1, n) {
        auto q = p;
        swap(q[i], q[j]);
        if (isOK(q)){
            println("YES");
            return 0;
        }
    }
    println("NO")
    return 0;
}

Measured memory_bytes: 3564
import static java.lang.System.*;
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n[] = new int[4];
		for(int i = 0;i < 3; i++){
			n[i] = sc.nextInt();
		}
		n[3] = n[2] - (n[0] - n[1]);
		out.println((0 < n[3])? n[3]:0);
	}
}


Measured memory_bytes: 23636
mod=10**9+7
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

h,w,k=map(int, input().split())
a=[[[0]*w for i in range(w)] for j in range(h)]

p=[1,1,1+1,1+2,1+3+1,1+4+3,1+5+6+1,1+6+10+4]

for i in range(w):
    a[0][i][i]=p[w-1-i]*p[i]
    if i<w-1:
        a[0][i][i+1]=a[0][i+1][i]=p[w-2-i]*p[i]

for r in range(1,h):
    for i in range(w):
        for j in range(w):
            a[r][i][j]=mul(a[r-1][i][j],p[w-1-j]*p[j])
            if j>0:
                a[r][i][j]+=mul(a[r-1][i][j-1],p[w-2-(j-1)]*p[j-1])
            if j<w-1:
                a[r][i][j]+=mul(a[r-1][i][j+1],p[w-2-j]*p[j])
                
print(a[h-1][0][k-1]%mod)

Measured memory_bytes: 3292
m = int(input().split()[1])

b = [0]
s = input().split()
for c in s:
    b.append((b[-1] + int(c)) % m)
b.sort()

l = []
j = b[0]
cnt = 1
for i in b[1:]:
    if i == j:
        cnt += 1
    else:
        l.append(cnt)
        j = i
        cnt = 1
l.append(cnt)
res = 0
for i in l:
    res += i * (i-1) // 2 # i==1のときは自動的に0になってくれる
print(res)

Measured memory_bytes: 62576
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.ABC_148
{
    class B
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            string[] st = Read().Split();
            for(int i = 0; i < n; i++)
            {
                Write(st[0][i]);
                Write(st[1][i]);
            }
            WriteLine();
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

using namespace std;

typedef long long LL;
#define N (1<<19)

const LL mod=998244353;
LL n,nn,sum,isum,a[N],ans;

void upd(LL &x,LL y){x=(x+y)%mod;}

LL inv(LL x){
	return x==1?1:(mod-mod/x)*inv(mod%x)%mod;
}

void fwt(LL f[],LL n){
	for (LL i=0;i<n;++i){
		LL t=1<<i;
		for (LL j=0;j<1<<n;j+=t<<1){
			LL *f1=f+j,*f2=f+j+t;
			for (LL k=0;k<t;++k){
				LL x=(f1[k]+f2[k])%mod,y=(f1[k]-f2[k]+mod)%mod;
				f1[k]=x; f2[k]=y;
			}
		}
	}
}

int main(){
	scanf("%lld",&n);
	for (LL i=0;i<1<<n;++i){
		scanf("%lld",a+i);
		upd(sum,a[i]);
	}
	isum=inv(sum);
	for (LL i=0;i<1<<n;++i) a[i]=a[i]*isum%mod;
	fwt(a,n);
	a[0]=0; for (LL i=1;i<1<<n;++i) a[i]=inv((1-a[i]+mod)%mod);
	fwt(a,n); nn=inv(1<<n);
	for (LL i=0;i<1<<n;++i){
		ans=(a[0]-a[i]+mod)%mod;
		printf("%lld\n",ans);
	}
	
	return 0;
}
			

Measured memory_bytes: 6912
#include <iostream>
#include <vector>

using namespace std;

vector<int> data;

void shuffle(int p,int c){
  vector<int> tmp(c);
  int pos = data.size() - p - c + 1;
  for(int i=0;i < c;i++){
    tmp[i] = data[pos+i];
  }
  data.erase(data.begin()+pos, data.begin()+pos+c);
  for(int i=0;i < c;i++){
    data.push_back(tmp[i]);
  }
}

int main(){
  int n, r, p, c;
  while(1){
    cin>> n >> r;
    if(!n && !r) break;
    data.reserve(n+1);
    for(int i=1;i<=n;i++){
      data.push_back(i);
    }
    for(int i=0;i<r;i++){
      cin>> p >> c;
      shuffle(p,c);
    }
    cout << data[data.size()-1] << endl;
    data.clear();
  }
  return 0;
}

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

typedef long long ll;

#define REP(i, N) for (int i = 0; i < (int)(N); i++)

// chmax, chmin
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; }

int main() {
    int N;
    cin >> N;
    vector<int> A(N),B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    
    if ( N % 2 == 0 ){
        vector<int> B2(N),B3(N),B4(N);
        REP(i,N){
            B2[i] = B[(i+N/2)%N];
            B3[i] = B[N-1-i];
            B4[i] = B[i];
        }
        bool exist2 = true, exist3 = true, exist4 = true;
        REP(i,N){
            if ( B2[i] == A[i] ) exist2 = false;
            if ( B3[i] == A[i] ) exist3 = false;
            if ( B4[i] == A[i] ) exist4 = false;
        }
        
        if ( exist2 ) {
            cout << "Yes" << endl;
            REP(i,N) cout << B2[i] << " " ;
            cout << endl;
        } else if ( exist3 ){
            cout << "Yes" << endl;
            REP(i,N) cout << B3[i] << " " ;
            cout << endl;
        } else if (exist4) {
            cout << "Yes" << endl;
            REP(i,N) cout << B4[i] << " " ;
            cout << endl;
        } else {
            cout << "No" << endl;
        }
    } else {
        vector<int> B2(N),B3(N),B4(N),B5(N);
        REP(i,N){
            B2[i] = B[(i+N/2)%N];
            B3[i] = B[(i+N/2+1)%N];
            B4[i] = B[N-1-i];
            B5[i] = B[i];
        }
        bool exist2 = true, exist3 = true, exist4 = true,exist5 = true;
        REP(i,N){
            if ( B2[i] == A[i] ) exist2 = false;
            if ( B3[i] == A[i] ) exist3 = false;
            if ( B4[i] == A[i] ) exist4 = false;
            if ( B5[i] == A[i] ) exist5 = false;
        }
        
        if ( exist2 ) {
            cout << "Yes" << endl;
            REP(i,N) cout << B2[i] << " " ;
            cout << endl;
        } else if ( exist3 ){
            cout << "Yes" << endl;
            REP(i,N) cout << B3[i] << " " ;
            cout << endl;
        } else if ( exist4 ){
            cout << "Yes" << endl;
            REP(i,N) cout << B4[i] << " " ;
            cout << endl;
        } else if ( exist5 ){
            cout << "Yes" << endl;
            REP(i,N) cout << B5[i] << " " ;
            cout << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    
    return 0;
}


Measured memory_bytes: 7208
local r_eat, g_eat, r_num, g_num, a_num 
= io.read("*n", "*n", "*n", "*n", "*n")

local function writeList(num)
    local list = {}
    for i = 1, num do
        list[i] = io.read("*n")
    end
    return list
end

local r_taste = writeList(r_num)
local g_taste = writeList(g_num)
local a_taste = writeList(a_num)

table.sort(r_taste, function(x, y) return x > y end)
table.sort(g_taste, function(x, y) return x > y end)
table.sort(a_taste, function(x, y) return x > y end)
for i = 1, r_num - r_eat do
    r_taste[#r_taste] = nil
end
for i = 1, g_num - g_eat do
    g_taste[#g_taste] = nil
end

local function removeMin(list1, list2, list3)
    if     list3 and (list1[#list1] <= list2[#list2]) then
        table.remove((list1[#list1] <  list3[#list3]) and list1 or list3)
    elseif list3 and (list2[#list2] <  list1[#list1]) then
        table.remove((list2[#list2] <  list3[#list3]) and list2 or list3)
    else
        table.remove((list1[#list1] <  list2[#list2]) and list1 or list2)
    end
end

for i = 1, #a_taste do
    if r_taste[#r_taste] and g_taste[#g_taste] and a_taste[#a_taste] then
        removeMin(r_taste, g_taste, a_taste)
    elseif r_taste[#r_taste] and g_taste[#g_taste] then
        removeMin(r_taste, g_taste)
    elseif g_taste[#g_taste] and a_taste[#a_taste] then
        removeMin(g_taste, a_taste)
    elseif a_taste[#a_taste] and r_taste[#r_taste] then
        removeMin(a_taste, r_taste)
    elseif r_taste[#r_taste] then
        table.remove(r_taste)
    elseif g_taste[#g_taste] then
        table.remove(g_taste)
    elseif a_taste[#a_taste] then
        table.remove(a_taste)
    end
end

local function samList(list)
    local result_sam = 0LL
    for i = 1, #list do
        result_sam = result_sam + list[i]
    end
    return result_sam
end
local result = 0LL
result = samList(r_taste) + samList(g_taste) + samList(a_taste)

print(tostring(result):sub(1, -3))

Measured memory_bytes: 3456
X, N = map(int, input().split())
if N != 0:
    p = list(map(int, input().split()))

if N == 0:
    print(X)
else:
    m = 1000
    n = 1000

    for i in range(102):
        c = i
        d = abs(X - c)
        if c not in p:
            if d < m:
                m = d
                n = c
            elif d == m and c < n:
                n = c
    print(n)

Measured memory_bytes: 9204
n, m = map(int, input().split())
C = list(map(int, input().split()))
dp = [-1] * (n+1)

for c in C:
    if c <= n:
        dp[c] = 1

for p in range(1, n+1):
    for c in C:
        if p-c < 0 or dp[p-c] < 0:
            continue
        dp[p] = min(dp[p], dp[p-c] + 1) if dp[p] > 0 else dp[p-c] + 1

# print(*dp)
print(dp[n])



Measured memory_bytes: 7256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int a[101][101] = {0};
    rrep(i, 1, n + 1) rrep(j, 1, n + 1) cin >> a[i][j];
    rrep(i, 1, n + 1) rep(j, n + 1) a[i][j] += a[i - 1][j];
    rep(i, n + 1) rrep(j, 1, n + 1) a[i][j] += a[i][j - 1];
    /*
    rep(i, n + 1) {
        rep(j, n + 1) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    */
    int ans = -inf;
    rep(i, n) rep(j, n) {
        rrep(k, i + 1, n + 1) rrep(l, j + 1, n + 1) {
            ans = max(ans, a[k][l] - a[k][j] - a[i][l] + a[i][j]);
        }
    }
    cout << ans << endl;
}




Measured memory_bytes: 3244
#include <stdio.h>
#include <string.h>

int main(void){
    char s[10];
    char t[1000];
    int count = 0;
    int i;

    scanf("%s", s);
    for(i = 0; s[i]; i++)
        s[i] = toupper(s[i]);
    for(scanf("%s", t); strcmp(t, "END_OF_TEXT"); scanf("%s", t)){
        for(i = 0; t[i]; i++)
            t[i] = toupper(t[i]);
        if(!strcmp(s, t))
        count++;
    }
    printf("%d\n", count);
    return 0;
}


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

#define pb push_back
#define fst first
#define snd second
#define ALL(s) s.begin(),s.end()
#define fill(a,c) memset(&a, c, sizeof(a))
#define fore(i,x,y) for(ll i=x;i<y;i++)
#define SZ(x) ((int)(x).size())
#define PI acos(-1)
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long ll;
using namespace std;

const int MAXN = 1e5+5;
ll dp[110][MAXN];

int main() {FIN;
    int n; ll w; cin>>n>>w;
    vector<vector<ll>> v(n,vector<ll> (2));
    fore(i,0,n) fore(j,0,2) cin>>v[i][j];
    fore(i,0,n+1) fore(j,0,MAXN) dp[i][j] = 1e15;
    dp[0][0] = 0;
    fore(i,1,n+1){
        fore(j,0,MAXN){
            dp[i][j] = dp[i-1][j];
            if(v[i-1][1]<=j) dp[i][j] = min(dp[i][j],dp[i-1][j-v[i-1][1]]+v[i-1][0]);
        }
    }
    for(int i = MAXN-1; i >= 0; i--){
        if(dp[n][i] <= w){ cout<<i<<"\n"; return 0;}
    }
    return 0;
}




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

int main(){
	int a, b, t;

	while(1){
		cin >> a >> b;

		if(a == 0 && b == 0) break;

		if(a > b){
			t = a;
			a = b;
			b = t;
		}

		cout << a << " " << b << endl;
	}

	return 0;
}


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

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '9') s[i] = '1';
		else s[i] = '9';
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {
	
	int n; cin >> n;
	int idx = 1;

	vector<int> b;
	if (n % 2 != 0) {
		idx = -1;	
	}

	for (int i = 0; i < n; i++) {
		int a; cin >> a;

		if (idx == 1) {
			b.push_back(a);									
		}else {
			b.insert(b.begin(), a);	
		}
		idx *= -1;
	}


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

	return 0;
}


Measured memory_bytes: 4260
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map(String::toInt)
    val xArray = LongArray(n) { 0 }
    val yArray = LongArray(n) { 0 }
    (0 until n).forEach {
        val (x, y) = readLine()!!.split(' ').map(String::toLong)
        xArray[it] = x
        yArray[it] = y
    }
    var ans = Long.MAX_VALUE / 2
    for (i1 in 0 until n) {
        val x1 = xArray[i1]
        val y1 = yArray[i1]
        for (i2 in 0 until n) {
            val x2 = xArray[i2]
            val y2 = yArray[i2]
            for (i3 in 0 until n) {
                val x3 = xArray[i3]
                val y3 = yArray[i3]
                for (i4 in 0 until n) {
                    val x4 = xArray[i4]
                    val y4 = yArray[i4]
                    val minX = Math.min(x1, Math.min(x2, Math.min(x3, x4)))
                    val minY = Math.min(y1, Math.min(y2, Math.min(y3, y4)))
                    val maxX = Math.max(x1, Math.max(x2, Math.max(x3, x4)))
                    val maxY = Math.max(y1, Math.max(y2, Math.max(y3, y4)))
                    var countInnerP = 0
                    for (j in 0 until n) {
                        val x = xArray[j]
                        val y = yArray[j]
                        if (x in minX..maxX && y in minY..maxY) countInnerP++
                    }
                    if (countInnerP >= k) ans = Math.min(ans, (maxX - minX) * (maxY - minY))
                }
            }
        }
    }
    println(ans)
}


Measured memory_bytes: 77024
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int sum=0;
		
		for(int i=0; i<10; i++){
			int n = sc.nextInt();	
			sum += n;
		}	
	
		System.out.println(sum);
	
	}
}

Measured memory_bytes: 17328
def input_from_console():
    x,a = map(int, input().split())

    return x,a


def solve(x,a):
    result = 0
    if x >= a:
        result = 10
    return result


def main():
    x,a = input_from_console()
    print(solve(x,a))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()


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

int main(){
	while (true){
		int n, r,a[50];
		cin >> n >> r;
		if (n == 0 && r == 0){ break; }
		for (int i = 0; i < n; i++){
			a[i] = n-i;
		}

		for (int i = 0; i < r; i++){
			int p, c, b[50];
			cin >> p >> c;
			for (int j = 0; j < p-1; j++){
				b[j] = a[j];
			}
			for (int j = 0; j < c; j++){
				a[j] = a[p + j-1];
			}
			for (int j = 0; j < p-1; j++){
				a[c + j] = b[j];
			}
		}

		cout << a[0] << endl;
	}
	return 0;
}


Measured memory_bytes: 3084
#include<iostream>
using namespace std;long long e(long long n){long long r=n;for(long long i=2;i*i<=n;i++)if(n%i==0){r-=r/i;while(n%i== 0)n/=i;}if (n > 1) r -= r / n;return r;}int main(){long long n;cin>>n;cout<<e(n)<<endl;}

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

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

  long long ans,cnt=0;
  string s,t;
  cin >> s >> t;
  long long alph[26]={};
  for(size_t i=0;i<s.size();i++){
    alph[s[i]-'a']++;
  }
  for(size_t i=0;i<t.size();i++){
    if(alph[t[i]-'a']==0){
      cout << -1 << endl;
      return 0;
    }
  }
  long long top[26][s.size()];
  long long next[26][s.size()];
  for(int i=0;i<26;i++){
    for(size_t j=0;j<s.size();j++){
      top[i][j]=-1;
      next[i][j]=-1;
    }
  }
  top[s[0]-'a'][0]=0;
  next[s[s.size()-1]-'a'][s.size()-1]=s.size()-1;
  for(size_t i=1;i<s.size();i++){
    top[s[i]-'a'][i]=i;
    for(int j=0;j<26;j++){
      top[j][i]=min(((top[j][i]!=-1)?top[j][i]:top[j][i-1]), ((top[j][i-1]!=-1)?top[j][i-1]:100000000));
    }
  }
  for(int i=(int)s.size()-2;i>=0;i--){
    next[s[i]-'a'][i]=i;
    for(int j=0;j<26;j++){
      next[j][i]=min(((next[j][i]!=-1)?next[j][i]:next[j][i+1]), ((next[j][i+1]!=-1)?next[j][i+1]:100000000));
    }
  }
  int now=0;
  for(size_t i=0;i<t.size();i++){
    if(next[t[i]-'a'][now]!=-1){
      if(next[t[i]-'a'][now]+1==(long long)s.size()){
        cnt++;
      }
      now=(next[t[i]-'a'][now]+1)%s.size();
    }else{
      now=top[t[i]-'a'][now]+1;
      cnt++;
    }
    ans=cnt*s.size()+now;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 41168
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    ll n,k;
    std::cin >> n>>k;
    std::cout << n-k+1 << std::endl;
}

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

int main() {
	int k;
	string s;
	cin >> k >> s;

	if (s.size() <= k) {
		cout << s << "\n";
	}
	else {
		for (int i = 0; i < k; i++) {
			cout << s[i];
		}
		cout << "..." << "\n";
	}
	return 0;
}

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

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

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());
 
    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define double 0long double
#define low lower_bound
#define upp upper_bound
#define mod (int)1e9+7
#define inf (int)1e16
#define rep(i,n) for (int i = 0; i < (int)n; i++)
#define Rep(i,n) for (int i = n; i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define P pair<int, int>
#define F first
#define S second
#define prique priority_queue<P, vector<P>, greater<P>>
using namespace std;


int n,m,q,l,r,a,b;
int ta[514][514];

signed main() {
	cin>>n>>m>>q;
	rep(i,m){
		cin>>l>>r;
		ta[l][r]++;
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j>=1;j--){
			ta[j][i]=ta[j][i-1]+ta[j+1][i]-ta[j+1][i-1]+ta[j][i];
		}
	}
	rep(i,q){
		cin>>a>>b;
		cout<<ta[a][b]<<endl;
	}
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define rep1(i, n) for (int i = 1; i < int(n); ++i)
#define repx(i, x, n) for (int i = int(x); i < int(n); ++i)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) ((a) <= (x) && (x) < (b))
#define OUT(a, x, b) ((x) < (a) || (x) < (b))
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const ll MOD = 1000000007;

int main()
{
    int N, M;
    cin >> N >> M;
    int a[N], b[N], c[M], d[M];
    rep(i, N)
    {
        cin >> a[i] >> b[i];
    }
    rep(i, M)
    {
        cin >> c[i] >> d[i];
    }
    rep(i, N)
    {
        ll now = 1e10, tmp, ans_idx;
        rep(j, M)
        {
            tmp = abs(a[i] - c[j]) + abs(b[i] - d[j]);
            if (now > tmp)
            {
                now = tmp;
                ans_idx = j + 1;
            }
        }
        cout << ans_idx << endl;
    }
    return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
int main(void){
    int n;
    scanf("%d",&n);
    
    int sides[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&sides[i]);
    }
    
    int sum=0,max = 0;
    for(int i=0;i<n;i++)
    {
        sum+=sides[i];
        if(max<sides[i])
        {
            max = sides[i];
        }
    }
    
    puts(max<sum-max?"Yes":"No");
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int main(){
    long long N,H;
    cin>>N>>H;
    vector <long long>a(N);
    vector <long long>b(N);
    for(int i=0 ; i<N ; i++){
        cin>>a[i];
        cin>>b[i];
    }
    long long ans=0;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    for(long long i=N-1 ; i>=0 ; i--){
        if(a[N-1]<=b[i] && H>0){
           H-=b[i];
           ans+=1;
        }
    }
    if(H>0){
    	ans+=(long)H/a[N-1];
        if(H%a[N-1]!=0)ans+=1;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)
using mint=modint998244353;
using S=pair<mint,int>;
using P=pair<mint,mint>;
S pl(S a,S b){
    return {a.first+b.first,a.second+b.second};
}

S e(){
    return {0,1};
}

S mp(P f,S x){
    return {x.first*f.first+f.second*x.second,x.second};
}

P cp(P f,P g){
    return {f.first*g.first,f.first*g.second+f.second};
}

P id(){
    return {1,0};
}

void solve(){
    int n,q;
    cin>>n>>q;
    vector<S> a;
    a.reserve(n);
    {
        int A;
        fr(i,n) cin>>A,a.emplace_back(A,1);
    }
    lazy_segtree<S,pl,e,P,mp,cp,id> sg(a);
    int t,l,r,b,c;
    fr(_,q){
        cin>>t>>l>>r;
        if(t) cout<<sg.prod(l,r).first.val()<<'\n';
        else{
            cin>>b>>c;
            sg.apply(l,r,make_pair(mint(b),mint(c)));
        }
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Measured memory_bytes: 19524
use std::io::{Read, StdinLock};
use std::str::{from_utf8, FromStr};
use std::vec::Vec;
use std::cmp::min;

struct StdinReader<'a> {
    reader: StdinLock<'a>,
}

impl<'a> StdinReader<'a> {
    pub fn new(reader: StdinLock<'a>) -> Self {
        Self { reader: reader }
    }

    pub fn read<T: FromStr>(&mut self) -> T {
        fn is_whitespace(ch: u8) -> bool {
            ch == 0x20 || ch == 0x0a || ch == 0x0d
        }

        let token: Vec<u8> = self.reader
            .by_ref()
            .bytes()
            .map(|ch| ch.expect("failed to read a byte"))
            .skip_while(|ch| is_whitespace(*ch))
            .take_while(|ch| !is_whitespace(*ch))
            .collect();
        let token_str = from_utf8(&token)
            .unwrap_or_else(|_| panic!(format!("invalid utf8 sequence: {:?}", token)));
        token_str
            .parse()
            .unwrap_or_else(|_| panic!(format!("failed to parse input: {}", token_str)))
    }
}

type Weight = i32;

fn main() {
    let INF = Weight::max_value() / 10;
    let stdin = std::io::stdin();
    let mut reader = StdinReader::new(stdin.lock());

    loop {
        let n: usize = reader.read();
        let m: usize = reader.read();

        if n == 0 { break; }

        let source = reader.read::<usize>() - 1;
        let g1 = reader.read::<usize>() - 1;
        let g2 = reader.read::<usize>() - 1;

        let mut dist = vec![vec![INF; n]; n];

        for _ in 0..m {
            let b1 = reader.read::<usize>() - 1;
            let b2 = reader.read::<usize>() - 1;
            let c: i32 = reader.read();

            dist[b1][b2] = c;
        }

        for i in 0..n {
            dist[i][i] = 0;
        }
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                }
            }
        }

        let mut min_cost = dist[source][g1] + dist[source][g2];
        for v in 0..n {
            min_cost = min(min_cost, dist[source][v] + dist[v][g1] + dist[v][g2])
        }

        println!("{}", min_cost);
    }
}



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

int main(){
	string s;
	cin>>s;
	int dist=0;
	//10101...に揃えるときの塗り替え数を計算
	for (int i = 0; i < s.length(); i++) {
		if (i%2==0) {
			if (s[i]=='0') {
				dist++;
			}
		}else {
			if (s[i]=='1') {
				dist++;
			}
		}
	}
	//01010...に塗る＝s.length()-dist
	cout<<min(dist,(int)s.length()-dist)<<endl;
}

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

long long n;
vector<long long> a;

long long solve();

int main() {
  cin >> n;
  a.resize(n);
  for (auto& p : a) cin >> p;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0, now = 1;
  for (int i = 0; i < n; ++i) {
    long long x = (a[i] - 1) / now;
    res += x;
    if (x) a[i] = 1;
    now = max(now, a[i] + 1);
  }
  return res;
}

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

using namespace std;


int main()
{
  int N;
  map< int, int > mp;

  cin >> N;
  for(int i = 0; i < N; i++) {
    int A;
    cin >> A;
    ++mp[A];
  }
  vector< int > luz{0};
  for(auto &&p : mp) {
    if(p.second >= 4) luz.push_back(p.first);
    if(p.second >= 2) luz.push_back(p.first);
  }
  sort(luz.rbegin(), luz.rend());
  cout << 1LL * luz[0] * luz[1] << endl;
}



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

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 (a>b) { a=b; return 1; } return 0; }
#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<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

struct UnionFind {
    vector< int > data;

    UnionFind(int sz) {
        data.assign(sz, -1);
    }

    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return (false);
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return (true);
    }

    int find(int k) {
        if(data[k] < 0) return (k);
        return (data[k] = find(data[k]));
    }

    int size(int k) {
        return (-data[find(k)]);
    }
};



int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(m), b(m), c(k), d(k);
    vector<int> friend_ctr(n, 0);
    rep (i, m) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        friend_ctr[a[i]]++;
        friend_ctr[b[i]]++;
    }
    rep (i, k) {
        cin >> c[i] >> d[i];
        c[i]--; d[i]--;
    }

    UnionFind uf(n);
    rep (i, m) {
        uf.unite(a[i], b[i]);
    }
    vector<int> p(n, 0);
    rep (i, n) {
        p[i] = uf.size(i) - 1;
    }
    rep (i, k) {
        if (uf.find(c[i]) == uf.find(d[i])) {
            p[c[i]]--;
            p[d[i]]--;
        }
    }
    rep (i, n) {
        p[i] -= friend_ctr[i];
    }
    rep (i, n) {
        if (i) cout << " ";
        cout << p[i];
    }
    cout << endl;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  vector<int> b(N);
  for(int i=0; i<N; i++) cin >> a.at(i);
  for(int i=0; i<N-1; i++){
    if(a.at(i)==a.at(i+1)){
      b.at(i+1)=b.at(i)+1;
      b.at(i)=0;
    }
    else{
      b.at(i+1)=0;
    }
  }
  int ans=0;
  for(int i=0; i<N; i++){
    ans+= (b.at(i)+1)/2;
  }
  cout << ans << endl;
}

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

int maxAbsValExpr(vector<int>& x, vector<int>& y) {
        int res = 0, n = x.size(), smallest, cur;
        for (int p : {1, -1}) {
            for (int q : {1, -1}) {
                smallest = p * x[0] + q * y[0] + 1;
                for (int i = 1; i < n; ++i) {
                    cur = p * x[i] + q * y[i] + i+1;
                    res = max(res, cur - smallest);
                    smallest = min(smallest, cur);
                }
            }
        }
        return res;
    }

signed main() {
   int n;
   cin>>n;
//    vector<int>x,y;
    int mini1=1000000000000;
    int maxx1=-1000000000000;
    int mini2=1000000000000;
    int maxx2=-1000000000000;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        mini1=min(mini1,x+y);
        mini2=min(mini2,x-y);
        maxx1=max(maxx1,x+y);
        maxx2=max(maxx2,x-y);
    }
    int res=max((maxx1-mini1),(maxx2-mini2));
    cout<<res<<endl;
   }

Measured memory_bytes: 3608
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1001001001;
const ll LONGINF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
int main() {
    int N; cin >> N;
    int ans = 1;
    for(int i=0; i<3; i++) ans *= N;
    cout << ans << endl;
    return 0;
}


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

typedef long long STATES;

int main( void )
{
	STATES free_days[31], dp[51], goal_state, next;
	STATES* p;
	int i, j, n, answer, free_day, k;

	while ( scanf( "%d", &n ) == 1 && n )
	{
		memset( free_days, 0, sizeof(free_days) );
		memset( dp, 0, sizeof(dp) );

		goal_state = 0;
		for ( i = 0; i < n; i++ ) goal_state |= 1LL << i;

		for ( i = 0; i < n; i++ )
		{
			scanf( "%d", &k );
			for ( j = 0; j < k; j++ )
			{
				scanf( "%d", &free_day );
				free_days[free_day] |= 1LL << i;
			}
		}

		answer = -1;
		for ( i = 0; i < n; i++ ) dp[i] = 1LL << i;
		p = free_days + 1;
		for ( i = 1; i <= 30; i++, p++ )
		{
			next = 0;
			for ( j = 0; j < n; j++ ) if ( *p & 1LL << j ) next |= dp[j];
			if ( next == goal_state )
			{
				answer = i;
				break;
			}
			for ( j = 0; j < n; j++ ) if ( *p & 1LL << j ) dp[j] |= next;
		}

		printf( "%d\n", answer );
	}

	return 0;
}

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

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

  double d_price = N / 1.08;
  int i_price1 = int(d_price);
  int i_price2 = i_price1 + 1;

  if(int(i_price1 * 1.08) == N) {
    cout << i_price1 << endl;
  } else if(int(i_price2 * 1.08) == N) {
    cout << i_price2 << endl;
  } else {
    cout << ":(" << endl;
  }
  return 0;
}

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int r,c;
    cin>>r>>c;
    vector<string> v(r);
    for(int i=0; i<r; ++i)
        cin>>v[i];
    vector<vector<int>> dp(r, vector<int>(c));
    for(int i=0; i<r; ++i){
        for(int j=0; j<c; ++j){
            dp[i][j] = INT_MAX;
            if(i+j==0)
                dp[i][j] = (v[i][j]=='#');
            if(i>0) dp[i][j] = min(dp[i][j], dp[i-1][j]+(v[i][j]=='#' && v[i-1][j]=='.'));
            if(j>0) dp[i][j] = min(dp[i][j], dp[i][j-1]+(v[i][j]=='#' && v[i][j-1]=='.'));
        }
    }
    cout<<dp[r-1][c-1]<<endl;
}

Measured memory_bytes: 384
n = int(input())
p = list(map(float, input().split()))
dp = []
for i in range(n+1):
    dp.append([0]*(n+1))
dp[0][0]=1
for i in range(1,n+1):
    dp[i][0]=(1-p[i-1])*dp[i-1][0]
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j]=p[i-1]*dp[i-1][j-1]+(1-p[i-1])*dp[i-1][j]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Measured memory_bytes: 345992
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N; cin >> N;
  vector<string>S(N);
  set<string>set;
  for (int i=0; i<N; i++){
    cin >> S[i];
  }
  for (int i=0; i<N; i++){
    set.insert(S[i]);
  }
  int ans = set.size();
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 25168
package main

import (
	"bufio"
	"fmt"
	"os"
)

var scanner = bufio.NewScanner(os.Stdin)

func init() {
	buf := make([]byte, 0)
	scanner.Buffer(buf, 10000000000)
	scanner.Split(bufio.ScanWords)
}

func ScanText() string {
	if scanner.Scan() {
		return scanner.Text()
	}
	return ""
}

func main() {
	s := []byte(ScanText())

	cnt1 := 0
	cnt2 := 0

	for i, c := range s {
		switch i % 2 {
		case 0:
			if c == '0' {
				cnt2++
			} else {
				cnt1++
			}
		case 1:
			if c == '1' {
				cnt2++
			} else {
				cnt1++
			}
		}
	}
	if cnt1 > cnt2 {
		fmt.Println(cnt2)
	} else {
		fmt.Println(cnt1)
	}
}


Measured memory_bytes: 2212
import sys

n, m = map(int, input().split())

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

gap = []


if( n >= m):
    print(0)
    sys.exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
    gaps = sorted(gap)

print(sum(gaps[:m-n]))

Measured memory_bytes: 13968
# -*- coding: utf-8 -*-
def remain(l_p, sw_p):
    cnt = 0
    for l, on in zip(l_p, sw_p):
        _on = int(on)
        if _on == 0:
            continue
        if l == _on:
            cnt += 1
    return cnt % 2


n, m = map(int, input().split())

on_table = [[0] * n for _ in range(m)]

for i in range(m):
    line = input().split()
    for j in map(int, line[1:]):
        on_table[i][j-1] = 1


p = list(map(int, input().split()))

pattern = 2 ** n
max_bin = bin(pattern - 1)
bin_len = len(max_bin) - 2
format_pattern = "{:0" + str(bin_len) + "b}"
sw = [format_pattern.format(i) for i in range(pattern)]

cnt = 0
for _sw in sw:
    flag = True
    for _p, lite in zip(p, on_table):
        chk = remain(lite, _sw)
        if chk != _p:
            flag = False
            break

    if flag:
        cnt += 1

print(cnt)


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    C=[None]*n
    for i in range(n):
        x,y=map(int,input().split())
        C[i]=x+y*1j

    s=sum(abs(C[i]-C[j]) for i in range(n) for j in range(n))
    print(s/n)
resolve()

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    ll X[N+1],S[N+1];
    X[0] = S[0] = 0;
    for(int i=0;i<N;i++){
        X[i+1] = X[i]^ A[i];
        S[i+1] = S[i]+A[i];
    }
    ll ans =0;
    int r=1;
    for(int l=1;l<=N;l++){
        int oldr =r;
        while(r<=N&& (S[r]-S[l-1])==(X[r]^X[l-1])){
            r++;
        }
        // cerr <<"l=" << l <<", r=" << r << endl;
        ans += (r-l);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    k,n = map(int,input().split())
    a = list(map(int,input().split()))
    anslist = []
    a.append(k+a[0])
    for i in range(n):
        anslist.append(abs(a[i+1]-a[i]))
    print(k-max(anslist))
if __name__ == "__main__":
    main() #endline===============================================

Measured memory_bytes: 36088
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void chmin(int *a,int b){
  if(*a > b){
    *a =b;
  }
  
  return;
}

int main(void){
  char s[1010],t[1010];
  scanf("%s%s",s,t);
  int n,m;
  n=strlen(s);
  m=strlen(t);
  int min=1010;
  int count;
  for(int i=0;i<n-m+1;i++){
    int k=i;
    count=0;
    for(int j=0;j<m;j++){
      if(s[k]!=t[j]){
        count++;
      }
      k++;
    }
    if(count <= min){
      chmin(&min, count);
    }
  }
  printf("%d\n",min);
  return 0;
}



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

string s;
string beg = "", endd = "";
int q, t, f;
char c;
int state = 1;

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> s >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> t;
        if (t == 1)
        {
            state *= -1;
        }
        else
        {
            cin >> f >> c;
            if (state == 1)
            {
                if (f == 1)
                {
                    beg += c;
                }
                else
                {
                    endd += c;
                }
            }
            if (state == -1)
            {
                if (f == 1)
                {
                    endd += c;
                }
                else
                {
                    beg += c;
                }
            }
        }
    }
    if (state == 1)
    {
        reverse(beg.begin(), beg.end());
        cout << beg + s + endd;
    }
    if (state == -1)
    {
        reverse(endd.begin(), endd.end());
        reverse(s.begin(), s.end());
        cout << endd + s + beg;
    }
}

Measured memory_bytes: 1300
#define lli long long int
#define TC long long int T;cin>>T;while(T--)
#include<iostream>
using namespace std;
#include<bits/stdc++.h>

lli wt[102],val[102];
lli mat[102][100005]={0};
lli n,W;
lli rec(lli n,lli w)
{
	if(n==-1) return 0;
	
	if(mat[n][w])
	 return mat[n][w];
	 
	if(wt[n]<=w)
	{
	   return mat[n][w]=max(val[n]+rec(n-1,w-wt[n]),rec(n-1,w));
	}
	else
	   return mat[n][w]=rec(n-1,w);
}
int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n>>W;
    for(lli i=0;i<n;i++)
    {
    	cin>>wt[i]>>val[i];
    }
    
    cout<<rec(n-1,W);
    
	return 0;
}
    


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

int main(){

	int k,t;
	cin>>k>>t;


	vector<int> a(t);
	for(int i=0;i<t;i++)cin>>a[i];


	if(t==1){
		cout<<k-1<<endl;
	}else{
		sort(a.begin(),a.end());
		int l=0,r=t-1;
		bool b=true;
		while(l<r){
			if(a[l]<=a[r]) a[r]-=a[l],a[l]=0;
			else a[l]-=a[r],a[r]=0;
			
			if(a[l]==0)l++;
			if(a[r]==0)r--;
		}

		int res=0;
		for(int i=0;i<t;i++) res+=a[i];
		cout<<max(0,res-1)<<endl;


	}



}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& x : a) cin >> x;
  int ans = 1e9;
  for (int i = 1; i <= 100; i++) {
    int t = 0;
    for (auto& x : a) t += (i - x) * (i - x);
    ans = min(ans, t);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

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


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


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


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


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n;
  cin>>n;
  vector<ll> v(n);
  rep(i,n) cin>>v[i];
  ll ans=1e17;
  for(ll i=-100;i<=100;i++){
    ll tmp=0;
    rep(j,n){
      tmp+=((v[j]-i)*(v[j]-i));
    }
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;
}

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

static const int INF=1e9;
typedef long long ll;
typedef pair<int,int> P;

int main(){
   int x,a;
   cin >> x >> a;
   if(x<a) cout << 0 << endl;
   else cout << 10 << endl;
}


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



int main() {
	int a, b, c, d, e, k;
	int count = 0;
	cin >> a >> b >> c >> d >> e >> k;
	if (e - a > k) {
		++count;
	}
	if (count == 0) {
		cout << "Yay!" << endl;
	}
	else if (count != 0) {
		cout << ":(" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef pair<pii,pii> pippi;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
typedef vector<vector<ll>> mat;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<61;
int iinf=1<<30;
double pi=3.14159265358979323846;
double pi2=pi/2.0;
double eps=1e-8;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto& itr:mp)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
//#define endl "\n"
int dh[4]={1,0,-1,0};
int dw[4]={0,1,0,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umh unordered_map<int,int,custom_hash>
ll gcd(ll a,ll b){
    if(a<0)a=-a;
    if(b<0)b=-b;
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll c=gcd(a,b);
    return a*b/c;
}
ll Pow(ll n,ll k){
    if(k<0)return 0;
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
    now%=md;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll popcount(ll n){
    ll ret=0;
    ll u=n;
    while(u>0){
        ret+=u%2;
        u/=2;
        
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    string s;cin>>s;
    int ans=0;
    int now=0;
    rep(i,0,3){
        if(s[i]=='R')now++;
        else now=0;
        Max(ans,now);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>  //儀式1:pythonでいうimport
using namespace std;  //儀式2:関数名の省略

int main() { //main関数...行われる処理
  int N,M,ans=0; //int型のN,M,ans=0を宣言
  cin >> N >> M; //入力を代入
  ans = N*(N-1)/2+M*(M-1)/2; //ansに答えを代入
  cout << ans << endl; //ansを出力
}

Measured memory_bytes: 256