akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;
    vector<vector<bool>> avail(H);
    for(int i=0; i<H; i++){
        string s;
        cin >> s;
        avail[i].resize(W);
        for(int j=0; j<W; j++) avail[i][j] = (s[j] == '.');
    }

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    auto inside = [&](int i, int j){ return i>=0 && i<H && j>=0 && j<W && avail[i][j]; };

    vector<vector<int>> dist(H, vector<int>(W, 1e9));
    vector<pair<int, int>> que;
    que.emplace_back(sx, sy);
    dist[sx][sy] = 0;

    vector<vector<bool>> visited(H, vector<bool>(W));

    while(que.size()){
        vector<pair<int, int>> que2;
        for(int k=0; k<4; k++){
            if(k == 0){
                sort(que.begin(), que.end());
            }else if(k == 2){
                sort(que.begin(), que.end(), [](auto a, auto b){ return a.second < b.second; });
            }else{
                reverse(que.begin(), que.end());
            }
            for(auto& [i, j] : que){
                visited[i][j] = 1;
                int nxt = dist[i][j] + 1;
                for(int d=1; d<=K; d++){
                    int x = i+d*dx[k], y = j+d*dy[k];
                    if(!inside(x, y) || dist[x][y] < nxt || visited[x][y]) break;
                    if(dist[x][y] > nxt){
                        dist[x][y] = nxt;
                        que2.emplace_back(x, y);
                    }
                }
            }
            for(auto& [i, j] : que){
                visited[i][j] = 0;
            }
        }
        que = que2;
    }

    int ans = dist[gx][gy];
    if(ans == 1e9) ans = -1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11112
using System;
class c
{
    static void Main()
    {
        var hw = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        long h = hw[0], w = hw[1];
        long ans = (h - (h % 2)) * w / 2;
        if (h % 2 == 1) ans += (w + 1) / 2;
        if (h == 1 || w == 1) ans = 1;
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13140
h,w,k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]
ans = 114514893
for bit in range(1 << (h-1)):
    cut = [-1]
    for i in range(h-1):
        if bit & (1 << i) : cut.append(i)
    cut.append(h-1)
    l = len(cut)-1
    count = l-1
    suml = [0 for i in range(l)]
    ok = True
    for i in range(w):
        sumtemp = [0 for ii in range(l)]
        flag2 = True #kを超えないかどうか
        for j in range(l):
            for kk in range(cut[j]+1,cut[j+1]+1):
                sumtemp[j] = sumtemp[j] + s[kk][i]
            if sumtemp[j] > k:
                ok = False
                break
        if not ok : break
        for j in range(l):
            if suml[j]+sumtemp[j] > k:flag2 = False
        if flag2:
            for j in range(l):
                suml[j] = suml[j]+sumtemp[j]
        else:
            count += 1
            suml = sumtemp[:]   
    if not ok:continue
    ans = min(ans,count)
    
print(ans)

Measured memory_bytes: 75080
import java.io.*;
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;

public class Main
{	
	public static void main(String []args)throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String []s=br.readLine().split(" ");
		int N=Integer.parseInt(s[0]);
		int K=Integer.parseInt(s[1]);
		
		int a[]=new int[N+1]; //you can use a set instead of array
		
		boolean flag=false;
		String ans="";
		int c=0;
		
		for(int i=0;i<K;i++)
		{
			int d=Integer.parseInt(br.readLine());
			s=br.readLine().split(" ");
			for(int j=0;j<d;j++)
			{
				int x=Integer.parseInt(s[j]);
				if(a[x]==0)
				{
					a[x]=1;
					c++;
				}				
			}
			
		}
		
		out.println(N-c);
		
	}
	
	
}




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

int main() {
  int a, b;
  cin >> a;
  cin >> b;
  int sum = a + b;
  int mean;
  if (sum % 2 == 0) {
    mean = sum / 2;
  }
  else {
    mean = sum / 2 + 1;
  }
  cout << mean << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second 
#define mp make_pair
#define int long long
string longestRepeatedSubstring(string str) 
{ 
    int n = str.length(); 
    int LCSRe[n+1][n+1]; 
  
    // Setting all to 0 
    memset(LCSRe, 0, sizeof(LCSRe)); 
  
    string res; // To store result 
    int res_length  = 0; // To store length of result 
  
    // building table in bottom-up manner 
    int i, index = 0; 
    for (i=1; i<=n; i++) 
    { 
        for (int j=i+1; j<=n; j++) 
        { 
            // (j-i) > LCSRe[i-1][j-1] to remove 
            // overlapping 
            if (str[i-1] == str[j-1] && 
                LCSRe[i-1][j-1] < (j - i)) 
            { 
                LCSRe[i][j] = LCSRe[i-1][j-1] + 1; 
  
                // updating maximum length of the 
                // substring and updating the finishing 
                // index of the suffix 
                if (LCSRe[i][j] > res_length) 
                { 
                    res_length = LCSRe[i][j]; 
                    index = max(i, index); 
                } 
            } 
            else
                LCSRe[i][j] = 0; 
        } 
    } 
  
    // If we have non-empty result, then insert all 
    // characters from first character to last 
    // character of string 
    if (res_length > 0) 
        for (i = index - res_length + 1; i <= index; i++) 
            res.push_back(str[i-1]); 
  
    return res; 
} 
signed main()
{
    IOS
    int n; cin>>n;
    string str; cin>>str;
    string ans = longestRepeatedSubstring(str);
    int si = ans.length();
    cout<<si;
    return 0;
}

Measured memory_bytes: 195712
#include<bits/stdc++.h>
#define ll long long
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define f(i,s,e) for(ll i=s;i<e;i++)
#define pb(x) push_back(x)
#define mp make_pair
#define mod 1000000007
#define all(x) x.begin(),x.end()
using namespace std;
char arr[1002][1002];
int dp[1002][1002],n,m;

int dfs(int x,int y){
    if(x==n && y==m)
        return 1;
    if(x<1 || y<1 || x>n || y>m)
        return 0;
    if(arr[x][y]=='#')
        return 0;


    int &ret = dp[x][y];
    if(ret!=-1)
        return ret;

    int ans = 0;

    ans = (dfs(x+1,y) + dfs(x,y+1))%mod;

    return ret = ans;
}
int main(){
    fast;

    cin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>arr[i][j];

    memset(dp,-1,sizeof(dp));
    cout<<dfs(1,1);
}


Measured memory_bytes: 5248
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def check(s):
    for i in range(len(s)):
        if s[i] != s[len(s)-1-i]:
            return False
    return True

def kyu(x):
    if x <= 599:
        return 8
    if x <= 799:
        return 7
    if x <= 999:
        return 6
    if x <= 1199:
        return 5
    if x <= 1399:
        return 4
    if x <= 1599:
        return 3
    if x <= 1799:
        return 2
    return 1

def main():
    x = ri()
    print(kyu(x))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m;cin >> n >> m;
  vector<ll> a(n),sum(n+1),d(200005);
  for(int i=0;i<n;i++){
    cin >> a[i];
    d[a[i]]++;
  }
  for(int i=d.size()-1;i>=1;i--){
    d[i-1]+=d[i];
  }
  int cnt=0;
  sort(a.begin(),a.end(),greater<ll>());
  for(int i=0;i<n;i++){
    sum[i+1]=sum[i]+a[i];
  }
  ll l=-1,r=200005;
  while(r-l>1){
    ll mid=(l+r)/2;
    ll cnt=0;
    for(int i=0;i<n;i++){
      cnt+=d[max(1LL,mid-a[i])];
    }
    if(cnt>=m){
      l=mid;
    }
    else{
      r=mid;
    }
  }
  ll ans=0,s=0;
  for(int i=0;i<n;i++){
    ll t=max(0LL,d[max(0LL,l-a[i])]);
    ans+=sum[t]+t*a[i];
    s+=t;
  }
  ans-=(s-m)*l;
  cout << ans << endl;
}

Measured memory_bytes: 3456
while(True):
	N, Q = map(int, input().split())
	if (N+Q) == 0:break
	D = list(list(int(i) for i in input().split()) for i in range(N))
	D_i  = [1]*N
	answer = 0
	now_max = Q -1
	for i in range(1,100):
		member = 0
		for j in range(N):
			if D[j][0] < D_i[j]:
				continue
			if D[j][D_i[j]] == i:
				member += 1
				D_i[j] += 1
		if member > now_max :
			answer = i
			now_max = member
		if member == N:
			answer = i
			break
	print(answer)



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

int main(void){
  string s, result = "";

  cin >> s;

  for(int i = 0; i < s.size(); i ++){
    if(s[i] == '0') result += "0";
    if(s[i] == '1') result += "1";
    if(s[i] == 'B' && !result.empty()) result.pop_back();
  }

  cout << result << endl;

  return 0;
}


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

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, q; cin >> n >> q;
	set<pair<int, int>> r, c;
	r.insert({n, n});
	c.insert({n, n});
	while (q--) {
		int ty, i; cin >> ty >> i;
		if (ty == 1) {
			auto it = r.lower_bound({i, -1});
			int k = (*it).second;
			c.insert({(k - 1), i});
		}
		else {
			auto it = c.lower_bound({i, -1});
			int k = (*it).second;
			r.insert({(k - 1), i});
		}
	}
	long long ans = 1LL * (n - 2) * (n - 2);
	for (auto x: r) {
		if (x.second != n) ans -= x.first - 1;
	}	
	for (auto x: c) {
		if (x.second != n) ans -= x.first - 1;
	}
	cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 13024
#include <stdio.h>
#include <math.h>
int main(){
	int n,t,a,h[10000],s;
	double f=2147483647;
	double k,x[10000];
	scanf("%d",&n);
	scanf("%d %d",&t,&a);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d",&h[i]);
		x[i]=t-h[i]*0.006;
		k=fabs(x[i]-a);
		if (k<f)
		{
			f=k;
			s=i+1;
		}
	}
	printf("%d\n",s);
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
#define int long long
#define vel vector<int>
#define vvel vector<vel>
#define vvvel vector<vvel>
#define veb vector<bool>
long long rui(long long a, long long n, long long p) {
	if (n == 0) { return 1; }
	int x = rui(a, n / 2, p);
	x = (x*x) % p;
	if (n % 2 == 1) {x = (x*a) % p;}
	return x;
}
signed main() {
	int n; cin >> n;
	string s;
	cin >> s;
	string hen = "abcdefghijklmnopqrstuvwxyz";
	vel count(26,0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 26; j++) {
			if (s[i] == hen[j]) { count[j]++; }
		}
	}
	int p = 1000;
	p *= p * p; p += 7;
	int ans = 1;
	for (int i = 0; i < 26; i++) {
		ans *= (count[i] + 1);
		ans = ans % p;
	}
	ans = (ans + p - 1) % p;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cassert>
#include <cstring>

using namespace std;

int main(){
  char S[101];
  char T[101];
  scanf("%s\n", S);
  scanf("%s", T);
  assert(strlen(S) == strlen(T));
  int n = strlen(S);
  bool ok = false;
  for(int i=0; i < n; i++){
    if(strcmp(S, T) == 0){
      ok = true;
      break;
    }

    char temp = S[0];
    for(int j = 0; j < n - 1; j++){
      S[j] = S[j + 1];
    }
    S[n - 1] = temp;
  }
  if(ok){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    int n , k ;
    cin >> n >> k ;
    int a[n] ;
    for(int i = 0 ; i < n ; i++){
      cin >> a[i] ;
    }
    sort(a ,a + n) ;

    long long int ans = 0 ;
    for(int j = 0 ; j < n-k ; j++ ){
        ans += a[j] ;
    } 

    

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

Measured memory_bytes: 1024
import sys

s = input()

reslt_sum = 0

for bit in range(1<<len(s)-1):
    temp_sum = ''
    for i in range(len(s)):
        temp_sum += s[i]
        if bit & (1<<i):
            temp_sum += '-'
        elif i != len(s)-1:
            temp_sum += '+'
    if eval(temp_sum) == 7:
        print(temp_sum,'=7',sep='')
        sys.exit()

Measured memory_bytes: 3060
using System;

namespace GCD
{
    class Program
    {
        private static int Gcd(int[] i)
        {
            int a = i[0], b = i[1];
            if (a < b)
            {   
                int t = a;
                a = b;
                b = t;
            }
            while(true)
            {
                int c = a % b;
                if(c == 0) return b;
                a = b;
                b = c;
            }
        }
        static void Main()
        {
            Console.WriteLine(Gcd(Array.ConvertAll(Console.ReadLine().Split(), e => int.Parse(e))));
        }
    }
}

Measured memory_bytes: 9192
#pragma GCC optimize("Ofast")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

int main(){	
	
	string s;
	cin >> s;
	reverse(s.begin(),s.end());
  
	for(int i=0;i<s.size();i++){
		bool ok=false;
		
		string t=s.substr(i,5);
		if(t=="maerd" || t=="esare"){
			i+=4;
			ok=true;
			continue;
		}
		
		t=s.substr(i,6);
		if(t=="resare"){
			i+=5;
			ok=true;
			continue;
		}
		
		t=s.substr(i,7);
		if(t=="remaerd"){
			i+=6;
			ok=true;
			continue;
		}
		
		if(!ok){
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 3760
def gcd(x, y):
  if y == 0:
    return x
  return gcd(y, x % y)
N, M = map(int, input().split())
S = input()
T = input()
g = gcd(N, M)
ans = int(N * M / g)
for i in range(g):
  if S[int(N / g * i)] != T[int(M / g * i)]:
    ans = -1
    break
print(ans)

Measured memory_bytes: 3316
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] g = new int[n+1][n+1];
        
        for (int i = 0; i < n; i++) {
            int u = sc.nextInt();
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                int v = sc.nextInt();
                g[u][v] = 1;
            }
        }
        
        int[] d = new int[n+1];
        for (int i = 0; i <= n; i++) {
            d[i] = -1;
        }
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(1);
        d[1] = 0;
        while (!que.isEmpty()) {
            int top = que.poll();
            for (int j = 1; j <= n; j++) {
                if (g[top][j] == 1 && d[j] == -1) {
                    que.add(j);
                    d[j] = d[top] + 1;
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            System.out.println(i + " " + d[i]);
        }
    }
}



Measured memory_bytes: 28428
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())


if abs(a-b) > k or abs(b-c) > k or abs(c-d) > k or abs(d-e) > k or abs(a-d) > k or abs(a-c) > k or abs(a-e) > k or abs(b-d) > k or abs(b-e) > k or abs(c-e) > k:
    print(":(")
else:
    print("Yay!")




Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    list<long> lis;
    for (int i=0; i<n; ++i) {
        string ope; long key;
        cin >> ope;
        if (ope == "insert") {
            cin >> key;
            lis.push_front(key);
        } else if (ope == "delete") {
            cin >> key;
            list<long>::iterator pos = find(lis.begin(), lis.end(), key);
            if (pos != lis.end()) {
                lis.erase(pos);
            }
        } else if (ope == "deleteFirst") {
            lis.pop_front();
        } else if (ope == "deleteLast") {
            lis.pop_back();
        }
    }
    for (list<long>::iterator it = lis.begin(); it != lis.end(); ++it) {
        cout << ((it == lis.begin()) ? "" : " ") << *it;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 32480
IDENTIFICATION DIVISION.
PROGRAM-ID. B-String-R.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 S      PIC X(100).
01 T      PIC X(100).
01 SS     PIC X(200).
01 S-LEN  PIC 9(3).
01 I      PIC 9(3).
 
PROCEDURE DIVISION.
MAIN-001.
  ACCEPT S.
  ACCEPT T.

  UNSTRING S DELIMITED BY ' '
    INTO S COUNT S-LEN. 
  STRING S S DELIMITED BY ' '
    INTO SS.

  INSPECT SS TALLYING I FOR ALL T(1:S-LEN).

  IF (I > 0)
    DISPLAY 'Yes'
  ELSE
    DISPLAY 'No'
  END-IF.
 
MAIN-EXIT.
  STOP RUN.


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

int main()
{
    int n = 5;
    int ans = 0;
    int ext = 0;
    int mx = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        ans += x;
        x = x%10;
        int t;
        if(x == 0) t = 0;
        else t = 10 - x;
        mx = max(t, mx);
        ext += t;
    }
    cout << (ans + ext - mx)<< endl;
    return 0;
}



Measured memory_bytes: 256
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <map>
using namespace std;


#define prec(i) cout << fixed << setprecision(i)

const long long int MOD = 1000000007;

int ctoi(char c) {
	return c - '0';
}


int main()
{
	long long int n, cnt = 0;

	cin >> n;

	if (n < 10) {
		cnt += n;
	}	
	else {
		cnt += 9;
		if (n < 100) {

		}
		else {
			if (n < 1000) {
				cnt += n - 99;
			}
			else {
				cnt += 900;
				if (n < 10000) {

				}
				else {
					if (n < 100000)
						cnt += n - 9999;
					else {
						cnt += 90000;
					}
				}
			}
		}
		
	}

	cout << cnt << endl;

	return 0;

}

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

int main(void)
{
   char s[101];
   char t[101];
   char stmp;
   int slen;
   int i ,j;
   int yn = 0;

   scanf("%s", s);
   scanf("%s", t);

   slen = strlen(s);

   for(i=0;i<slen;i++){
      stmp = s[slen-1];
      for(j=slen-1;j>0;j--){
         s[j] = s[j-1];
      }
      s[0] = stmp;

      if(strcmp(s,t)==0){
         yn = 1;
         break;
      }
   }

   if(yn==1){
      printf("Yes\n");
   }
   else {
      printf("No\n");
   }

   return 0;
}


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

int main(){
    int N;
    std::string S;

    std::cin >> N;
    std::cin >> S;

    if(N % 2 != 0){
        std::cout << "No" << std::endl;
        return 0;
    }

    int half = N / 2;

    std::string front = S.substr(0, half);
    std::string whole = front + front;

    if(whole == S){
        std::cout << "Yes" << std::endl;
        return 0;
    }

    std::cout << "No" << std::endl;
    return 0;

}


Measured memory_bytes: 256
import os
import sys
import math

def func(h, w, ans):
    for i in range(1, w + 1):
        first = h * i

        if (w - i) % 2 == 0:
            second = h * ((w - i) // 2)
            s = abs(first - second)
            ans = min(s, ans)
        else:
            second = h * ((w - i) // 2)
            third = h * (w - i - (w - i) // 2)
            s = max(abs(first - second), abs(second - third), abs(third - first))
            ans = min(s, ans)

        if h % 2 == 0:
            second = (h // 2) * (w - i)
            s = abs(first - second)
            ans = min(s, ans)
        else:
            second = (h // 2) * (w - i)
            third = (h - (h // 2)) * (w - i)
            s = max(abs(first - second), abs(second - third), abs(third - first))
            ans = min(s, ans)
    return ans

h, w = map(int, input().split())

if h % 3 == 0 or w % 3 == 0:
    print(0)
    exit()

ans = float('inf')

ans = func(h, w, ans)
ans = func(w, h, ans)
    
print(ans)


Measured memory_bytes: 3444
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}
int main() {
	cin >> n;
	if (n % 2 == 1) {
		cout << 0 << endl;
		return 0;
	}

	ll res = n / 10;
	for (ll i = 50;; i *= 5) {
		if (i > n)break;
		res += n / i;
	}
	cout << res << endl;
}

Measured memory_bytes: 256
//ProblemA

//#define USE_STDIO
//#define USE_LOG
//#define FILE_ERR

#ifdef _MYPC
#include "mypc.h"
#endif // _MYPC

#ifndef debug
#define debug(...)
#endif // !LOG

#ifndef REDIRECT_STDIO
#define REDIRECT_STDIO {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
#endif // REDIRECT_STDIO

//include
#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <memory>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iomanip>

using namespace std;

//int
using ll = long long;
using ull = unsigned long long;
using uint = unsigned;

//pair
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

//vector
template<typename T> using vt = std::vector<T>;
template<typename T> using vvt = vt<vt<T>>;
template<typename T> using vvvt = vt<vvt<T>>;
using vi = vt<int>;
using vvi = vvt<int>;
using vvvi = vvvt<int>;
using vl = vt<ll>;
using vvl = vvt<ll>;
using vvvl = vvvt<ll>;
using vb = vt<bool>;
using vpii = vt<pii>;

static inline void Solve();

int main(int argc, char* argv[]) {
	REDIRECT_STDIO;

	Solve();
	return 0;
}

//ProblemA
void Solve() {
	int n; cin >> n;
	vi a(n, 0);
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());

	ll ans = 0;
	if(n % 2 == 0) {
		for(int i = 0; i < n / 2 - 1; i++) ans -= 2 * a[i];
		ans -= a[n / 2 - 1];
		ans += a[n/2];
		for(int i = n / 2 + 1; i < n; i++) ans += 2 * a[i];
	} else {
		ll ans1 = 0;
		for(int i = 0; i < n / 2 - 1; i++) ans1 -= 2 * a[i];
		ans1 -= a[n/2-1] + a[n/2];
		for(int i = n / 2 + 1; i < n; i++) ans1 += 2 * a[i];

		ll ans2 = 0;
		for(int i = 0; i < n / 2; i++) ans2 -= 2 * a[i];
		ans2 += a[n/2] + a[n/2 + 1];
		for(int i = n / 2 + 2; i < n; i++) ans2 += 2 * a[i];

		ans = max(ans1, ans2);
	}
	cout << ans << endl;
}


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

int main() {
  int a, b, k, c, ans, cnt = 0;
  scanf("%d %d %d", &a, &b, &k);
  c = min(a, b);
  for(int i = c; i > 0; i--) {
    if(a % i == 0 && b % i == 0) {
      cnt++;
    }
    if(cnt == k) {
      ans = i;
      break;
    }
  }
  cout << ans;
}

Measured memory_bytes: 3668
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/30 05:57:50 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	vector<ll>	V(45);
	V.at(0) = V.at(1) = 1;
	rep2(i, 2, 45)
		V.at(i) = V.at(i - 2) + V.at(i - 1);
	int	n;
	cin >> n;
	cout << V.at(n) << endl;
}
// END

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



Measured memory_bytes: 3172
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main () {
  stringstream s;
  string str;
  int num;
  int n;
  int len;
  
  cin >> n;
  for(int cnt = 0; cnt < n; cnt++) {
    cout << "Case " << cnt+1 << ":" << endl;
    cin >> num;
    for(int j = 0; j < 10; j++) {
      num *= num; 
      s <<  num; s >> str; s.clear(); s.str("");
      
      len = str.length();
      for(int i = 0; i < 8 - len; i++) str = "0" + str;
      num = 0;
      for(int i = 0; i < 4; i++) {
	num *= 10;
	num += str[2+i] - '0';
      }
      cout << num << endl;
    }
  } 
  return 0;
}

Measured memory_bytes: 1232
#!/usr/local/gnu/bin/bash
read n m
for i in `seq $n`
do
    read s
    a+=($s)
done
for i in `seq $m`
do
    read s
    b+=($s)
done
l=$((n-m))
for i in `seq 0 $l`
do
    for j in `seq 0 $l`
    do
        flag=1
        for k in `seq 0 $((m-1))`
        do
            if [ ${a[i+k]:j:m} != ${b[k]} ]
            then
                flag=0
                break
            fi
        done
        if((flag))
        then
            echo Yes
            exit
        fi
    done
done
echo No


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

int main ()
{
    char s[101],t[101],x[101];
    int i,j,l1,l2,k,p;
    scanf("%s %s",s,t);
    
    l1=strlen(s);
    l2=strlen(t);

    if(l1==l2)
    {
	for(i=l1-1;i>=0;i--)
	{
	    x[0]=s[i];
	    for(j=i+1,k=1;j<l1;j++,k++)
	    {
		x[k]=s[j];
	    }
	    for(j=0;j<i;j++,k++)
	    {
		x[k]=s[j];
	    }
	    for(j=0,p=0;j<l1;j++,p++)
	    {
		if(t[j]!=x[j]) break;
	    }
	    if(p==l1)
	    {
		printf("Yes\n");
		break;
	    }
	    else if(i==0)
	    {
		printf("No\n");
		break;
	    }
	}
    }
    else printf("No\n");




    return 0;
}


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

int main()
{
  int N, Y; cin >> N >> Y;
  int A = -1, B = -1, C = -1;
  rep(a,N)
  {
    rep(b,N)
    {
      int sum = 10000*a + 5000*b + 1000*(N-a-b);
      if(sum == Y && N-a-b >= 0){
        A = a; B = b; C = N-a-b;
      }
    }
  }
  cout << A << " " << B << " " << C << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(in.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    int[] A = new int[M], B = new int[M];
    for (int i = 0; i < M; ++i) {
      st = new StringTokenizer(in.readLine());
      A[i] = Integer.parseInt(st.nextToken());
      B[i] = Integer.parseInt(st.nextToken());
    }

    System.out.println(solve(N, M, A, B));

    in.close();
  }

  private static int solve(int N, int M, int[] A, int[] B) {
    Map<Integer, Set<Integer>> graph = new HashMap<>();
    for (int i = 0; i < M; ++i) {
      addEdge(graph, A[i], B[i]);
      addEdge(graph, B[i], A[i]);
    }

    int numGroups = 0;
    Integer[] nodeGroupMap = new Integer[N + 1];
    for (int i = 1; i <= N; ++i) {
      if (nodeGroupMap[i] == null) {
        nodeGroupMap[i] = numGroups;
        groupNodes(graph, i, nodeGroupMap, numGroups++);
      }
    }

    int maxGroupSize = 0;
    int[] groupSizes = new int[numGroups];
    for (int i = 1; i <= N; ++i) {
      groupSizes[nodeGroupMap[i]]++;
      maxGroupSize = Math.max(maxGroupSize, groupSizes[nodeGroupMap[i]]);
    }

    return maxGroupSize;
  }

  private static void addEdge(Map<Integer, Set<Integer>> graph, int from, int to) {
    Set<Integer> adjacents = graph.getOrDefault(from, new HashSet<>());
    adjacents.add(to);
    graph.put(from, adjacents);
  }

  private static void groupNodes(Map<Integer, Set<Integer>> graph, int node, Integer[] nodeGroupMap, int group) {
    if (graph.containsKey(node)) {
      for (int next : graph.get(node)) {
        if (nodeGroupMap[next] == null) {
          nodeGroupMap[next] = group;
          groupNodes(graph, next, nodeGroupMap, group);
        }
      }
    }
  }
}

Measured memory_bytes: 157668
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <bitset>
#include <tuple>
#include <set>
#include <map>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int N, X;
  std::cin >> N >> X;
  std::vector<int> l(N);
  for(int i=0;i<N;i++) std::cin >> l[i];
  int now = 0;
  for(int i=0;i<N;i++){
    now += l[i];
    if(now>X){
      std::cout << i + 1 << '\n';
      return 0;
    }else if(i==N-1){
      std::cout << i + 2 << '\n';
    }
  }
  return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
 
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef complex<double> base;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) { 
    return os << '(' << pai.first << ' ' << pai.second << ')';
}
 
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    cout << '[';
    for (auto p : v) cout << p << ",";
    cout << "]";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif
 
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}

int N;
int A[401];
ll dp[401][401];
int dv[401][401];
ll S[401];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    repp(i, 1, N+1) cin >> A[i], S[i] = S[i-1]+A[i];
    repp(i, 1, N+1) dv[i][i] = i;
    repp(d, 1, N) {
        repp(i, 1, N-d+1) {
            pair<ll, int> cd = {INFL, 0};
            repp(j, dv[i][i+d-1], dv[i+1][i+d]+1) {
                get_min(cd, {dp[i][j]+dp[j+1][i+d], j});
            }
            dp[i][i+d] = cd.fi+S[i+d]-S[i-1];
            dv[i][i+d] = cd.se;
        }
    }

    cout << dp[1][N] << endl;
}

Measured memory_bytes: 2176
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a, b, c, count = 0;
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		for(int i = a; i <= b; i++){
			if(c % i == 0){
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 26312
#include <iostream>
#include <cmath>
#define PI 3.141592
using namespace std;

int main()
{
    char s;
   cin >> s;

   if (isupper(s))
   {
       cout << 'A' << endl;
   }
   else
   {
       cout << "a" << endl;
   }

   return 0;
}
        
    


Measured memory_bytes: 3600
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	          int i;

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

	      	  int N;
	      	  cin >> N;

	      	  ll t=1;
	      	  for(i=1;i<=N;i++){
	      		  t*=3;
	      	  }

	      	  ll u=1;
	      	  for(i=1;i<=N;i++){
	      		  ll a;
	      		  cin >> a;
	      		  if(a%2==0) u*=2;
	      	  }

	      	  cout << t-u << endl;



	          return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
typedef long long int ll;

#define MOD 998244353

int main(){
    ll a,b;
    cin >> a >> b;
    for (ll i=1;i<4;i++){
        if (a!=i && b!=i)cout << i << endl;
    }
}






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

typedef long long ll;
typedef pair<ll, ll> P;

int N, L[10];

int main(){
    cin >> N;
    for(int i=0;i<N;i++)    cin >> L[i];

    int mx = 0, sum = 0;
    for(int i=0;i<N;i++){
        mx = max(mx, L[i]);
        sum += L[i];
    }

    sum -= mx;

    if(mx < sum)    cout << "Yes" << endl;
    else            cout << "No" << endl;
}

Measured memory_bytes: 256
/* 
  ╔╗         ╔╗              ╔═══╗                                  
  ║║        ╔╝╚╗             ║╔═╗║                                  
  ║║╔╗╔╗╔══╗╚╗╔╝    ╔══╗     ║╚═╝║╔═╗╔══╗╔══╗╔═╗╔══╗ ╔╗╔╗╔╗╔╗╔══╗╔═╗
╔╗║║║║║║║══╣ ║║     ╚ ╗║     ║╔══╝║╔╝║╔╗║║╔╗║║╔╝╚ ╗║ ║╚╝║║╚╝║║╔╗║║╔╝
║╚╝║║╚╝║╠══║ ║╚╗    ║╚╝╚╗    ║║   ║║ ║╚╝║║╚╝║║║ ║╚╝╚╗║║║║║║║║║║═╣║║ 
╚══╝╚══╝╚══╝ ╚═╝    ╚═══╝    ╚╝   ╚╝ ╚══╝╚═╗║╚╝ ╚═══╝╚╩╩╝╚╩╩╝╚══╝╚╝ 
                                         ╔═╝║                       
                                         ╚══╝                       */


//Header files
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#ifndef ONLINE_JUDGE
#include<Personal/debug.h>
#else
#define debug(x...)
#endif

//Short data-types declaration
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<string> vs;
typedef vector<vector<int> > vii;  
typedef vector<vector<long long> >vll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vbb;

//Macros
#define MK make_pair
#define EB emplace_back
#define PB push_back
#define F first
#define S second
#define rep(i,start,end) for(int i=(int)start;i<(int)end;i++)
#define repr(i,start,end) for(int i=(int)start;i>(int)end;i--)
#define all(x) (x).begin(), (x).end()

//Constants
const int mod = 1e9+7;

//Some useful functions
ll binpow(ll num,ll pow);
inline int mul(int a,int b) {return (a*1ll*b)%mod;}
inline int add(int a,int b) {return (a+0ll+b)%mod;}
inline int sub(int a,int b) {return ((a+0ll-b)%mod+mod)%mod; }
/*------------------------------------------------------Code Starts------------------------------------------------------*/
inline void solve()
{
	ll x,k,d;
	cin>>x>>k>>d;
	x=abs(x);
	ll m=min(x/d,k);
	ll pos=x-m*d;
	k-=m;
	if(k&1)
		cout<<abs(pos-d)<<'\n';
	else cout<<pos<<'\n';	
}

int main()
{
	auto start = high_resolution_clock::now();
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	auto stop = high_resolution_clock::now(); 
	auto duration = duration_cast<microseconds>(stop - start); 
	cerr<<duration.count()<<" microseconds\n";
	return 0;
}
/*------------------------------------------------------Code ends------------------------------------------------------*/
ll binpow(ll num,ll pow)
{
	if(pow==0)
		return 1;
	ll val=binpow(num,pow/2);
	val*=val;
	if(pow&1) val*=num;
	return val;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);
//ios::sync_with_stdio(false);


signed main(){
    ll n,ans=0;cin>>n;
    vector<ll> v(n);
    rep(i,n)cin>>v[i];
    ans=0;

    for(int i=1;i < n-1;i++)//a-b
    {
        ll res=0;
        set<ll> se;
        for(int j=1;i*(j+1)<n-1;j++)//係数
        {
            if(!se.count(i*j) && !se.count(n-1-i*j) && i*j!=n-1-i*j){
                res+=v[i*j]+v[n-1-i*j];
                ans=max(ans,res);
                se.emplace(i*j);
                se.emplace(n-1-i*j);
                //cout<<i*j<<" "<<n-1-i*j<<endl;
            }
        }
        se.clear();
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5760
#include<iostream>
using namespace std;
int main()
{
    int n,t,x,y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t>>x>>y;
        if(x+y>t)
        {
            cout<<"No"<<endl;
            return 0;
        }
        if((x+y)%2==0&&t%2==1)
        {
            cout<<"No"<<endl;
            return 0;
        }
        if((x+y)%2==1&&t%2==0)
        {
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100001
#define max2(a,b) a<b?b:a
#define max3(a,b,c) max2((max2(a,b)),c)
#define max4(a,b,c,d) max3((max2(a,b)),c,d)

void sort(int a[],int t){
	int i,j;
	for(i=0;i<t-1;i++){
      for(j=t-1;j>i;j--){
		if(a[j]>a[j-1]){
		  int tmp=a[j];
		  a[j]=a[j-1];
		  a[j-1]=tmp;
		}
      }
    }
}
int main(){
	int i,j;
	int n,m;
	int k,t;
	int a[100];
	
	scanf("%d%d",&k,&t);
	for(i=0;i<t;i++){
		scanf("%d",&a[i]);
	}
	
	if(t==1){
		printf("%d\n",a[0]-1);
		return 0;
	}
	
	sort(a,t);
	
	int cnt = 0;
	int ans = 0;
	
	for(i=1;i<t;i++){
		cnt+=a[i];
	}
	if(a[0]>cnt+1){
		ans+=(a[0]-cnt-1);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
static const int MAX_N = 100000;
static const int MAX_M = 100000;

int N, M;
int memo[MAX_M];

int main(){
	cin >> N >> M;
	fill(memo, memo + M, 0);
	int s, t;
	for(int i = 0; i < M; i++){
		cin >> s;
		s--;
		if(i != 0) memo[min(s, t)]++, memo[max(s, t)]--;
		t = s;
	}
	for(int i = 1; i < N; i++) memo[i] += memo[i - 1];
	ll ans = 0;
	for(int i = 0; i < N - 1; i++){
		ll A, B, C;
		cin >> A >> B >> C;
		ans += min(A * (ll)memo[i], B * (ll)memo[i] + C);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3496
module MakeBinaryHeap (M : sig type t val compare : t -> t -> int end) = struct

  type t = { node : M.t array; mutable size : int }

  let make n (init : M.t) = { node = Array.make n init; size = 0 }

  let empty_p t = if t.size = 0 then true else false

  let pop t =
    if t.size <= 0 then failwith "out of size" else
    let rec max_heapify i =
      let l = 2*i in
      let r = 2*i + 1 in
      let m = if l <= t.size && M.compare t.node.(l) t.node.(i) > 0 then l else i in
      let m = if r <= t.size && M.compare t.node.(r) t.node.(m) > 0 then r else m in
      if m = i then ()
      else begin
        let tmp = t.node.(i) in
        t.node.(i) <- t.node.(m);
        t.node.(m) <- tmp;
        max_heapify m
      end in
    let ret = t.node.(1) in
    t.node.(1) <- t.node.(t.size);
    t.size <- t.size - 1;
    max_heapify 1;
    ret

  let push x t =
    let parent i = int_of_float (floor (float_of_int i) /. 2.) in
    let rec doit i =
      let p = parent i in
      if i <= 1 || M.compare t.node.(p) t.node.(i) >= 0 then ()
      else begin
        let tmp = t.node.(i) in
        t.node.(i) <- t.node.(p);
        t.node.(p) <- tmp;
        doit p
      end in
    t.size <- t.size + 1;
    t.node.(t.size) <- x;
    doit t.size

end

module H = MakeBinaryHeap(struct type t = (int * int) let compare (_, x) (_, y) = y - x end)

let dijkstra g n =
  let reached_p = Array.make n false in
  let min_costs = Array.make n max_int in
  min_costs.(0) <- 0;
  let h = H.make 10000 (0, 0) in
  H.push (0, 0) h;
  while not (H.empty_p h) do
    let (u, x) = H.pop h in
    reached_p.(u) <- true;
    if x > min_costs.(u) then ()
    else
      List.iter (fun (v, c) ->
        let x = min_costs.(u) + c in
        if not reached_p.(v) && x < min_costs.(v) then begin
          min_costs.(v) <- x;
          H.push (v, x) h;
        end) g.(u);
  done;
  min_costs

let rec make_pair acc = function
  | [] -> acc
  | v :: c :: tl -> make_pair ((v, c) :: acc) tl
  | _ -> assert false

let make_pair lst = make_pair [] lst

let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let n = read_int () in
  let g = Array.make n [] in
  for _ = 0 to n - 1 do
    match read_line () |> split_on_char ' ' |> List.map int_of_string with
    | u :: _ :: l -> g.(u) <- make_pair l
    | _ -> assert false
  done;
  dijkstra g n |> Array.iteri (fun i e -> Printf.printf "%d %d\n" i e)

Measured memory_bytes: 3312
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define A_MAX 2000100
bool dp[A_MAX];

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    fill(dp, dp + A_MAX, true);
    for (int i = 0; i < N; i++) {
        if (!dp[A[i]]) continue; 
        if (i > 0 && A[i-1] == A[i]) dp[A[i]] = false;
        int tmp = 2 * A[i];
        while (tmp <= A_MAX) {
            dp[tmp] = false;
            tmp += A[i];
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (dp[A[i]]) ans++;
    }
    cout << ans << endl;
}

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

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

  vector<int> p(n);
  for (int i = 0; i < n; i++) cin >> p[i];

  vector<int> e(n);
  for (int i = 0; i < n; i++) {
    e[i] = p[i] + 1;
  }

  double sum = 0;
  for (int i = 0; i < k; i++) sum += e[i];

  double ans = sum / 2.0;
  for (int i = 0; i + k < n; i++) {
    sum = sum - e[i] + e[i + k];
    double tmp = sum / 2.0;
    ans = max(ans, tmp);
  }
  printf("%.8f\n", ans);
}


Measured memory_bytes: 4796
#include <iostream>
using namespace std;
using ll = unsigned long long;

ll sumarr(int a[], int n) {
  ll s = 0;
  for (int i = 0; i < n; i++) {
    s += a[i];
  }
  return s;
}


int main() {
  const int hmax = 300;
  const int wmax = 300;
  int H, W, K;
  int pos[hmax * wmax][2];
  int a[hmax][wmax];

  cin >> H;
  cin >> W;
  cin >> K;

  int k = 0;
  int B = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      char c;
      cin >> c;
      if (c == '#') {
        pos[k][0] = i;
        pos[k][1] = j;
        k++;
        if (B < i) B = i;
      }
    }
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      a[i][j] = 0;
    }
  }

  for (k = 0; k < K; k++) {
    int right, bottom;

    if (pos[k][0] == B) {
      bottom = H - 1;
    } else {
      bottom = pos[k][0];
    }

    if (k == K - 1 || pos[k][0] != pos[k + 1][0]) {
      right = W - 1;
    } else {
      right = pos[k][1];
    }

    for (int i = 0; i <= bottom; i++) {
      for (int j = 0; j <= right; j++) {
        // cout << i << " " << j << endl;
        if (a[i][j] == 0) a[i][j] = k + 1;
      }
    }
  }
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
}


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

int main(){
    string s;
    cin >> s;
    sort(s.begin(),s.end());

    //cout << s << endl;

    for(int i = 0; i < 3; ++i){
        if(s[i] != char('a' + i)){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 256