akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.buffer.readline

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)

ctr = n-1
idx = 0
res = 0

while ctr > 0:
    if idx == 0:
        ctr -= 1
        res += a[idx]
    else:
        ctr -= 2
        if ctr == -1:
            res += a[idx]
        else:
            res += a[idx]*2
    idx += 1

print(res)

Measured memory_bytes: 100688
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_8_D&lang=jp
  * Character - Ring
  */
object Main {
  def main(args: Array[String]): Unit = {
    val s = io.StdIn.readLine()
    val p = io.StdIn.readLine()
    if ((s * 2).contains(p))
      println("Yes")
    else
      println("No")
  }
}

Measured memory_bytes: 43572
#python3
INF = int(1e9)
def main():
    a, b, c, x, y = map(int, input().split())
    ans = INF
    for k in range(10**5+10):
        tmp = 2*c*k + max(x-k, 0)*a + max(y-k, 0)*b
        ans = min(ans, tmp)
    print(ans)
main()


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

int main(){
	int H,W;
	cin>>H>>W;
	int i,j;
	char temp;
	vector<vector<long long int>>Grid(H+10,vector<long long int>(W+10,0));
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			cin>>temp;
			if(temp=='#'){
				Grid[i][j]=-1;
			}
		}
	}
	Grid[1][1]=1;
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			/*if(i-1>0&&Grid[i-1][j]!=-1){
				Grid[i][j]+=Grid[i-1][j];
			}*/
			if(Grid[i][j]!=-1){
				if(Grid[i+1][j]!=-1)
					Grid[i+1][j]+=Grid[i][j]%1000000007;
				if(Grid[i][j+1]!=-1)
					Grid[i][j+1]+=Grid[i][j]%1000000007;
			}
		}
	}
	cout<<Grid[H][W]%1000000007;
	return 0;
}


Measured memory_bytes: 8320
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <functional>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <climits>

using namespace std;

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

const ll MOD = 1000000007;
const ll INF = LLONG_MAX;
const ll MAX_N = 100000;
const double EPS = 10e-8;

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


int main() {
	int n, ans = 0;
	vector<int> t;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int s;
		cin >> s;
		if (s % 10 != 0)t.push_back(s);
		ans += s;
	}
	if (!t.empty()) {
		sort(t.begin(), t.end());
		if (ans % 10 == 0)ans -= t[0];
	}
	else if (ans % 10 == 0)ans = 0;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val m = sc.nextInt()
    val a = (0 until n).map {
        (0 until sc.next().toInt()).map { sc.next().toInt() }
    }
    println(problem118b(n, m, a))
}

fun problem118b(n: Int, m: Int, a: List<List<Int>>): Int {
    val foods = IntArray(m) { 0 }
    for (i in 0 until n) {
        val ai = a[i]
        for (j in 0 until ai.size) {
            val aij = ai[j]
            foods[aij - 1]++
        }
    }
    return foods.count { it == n }
}

Measured memory_bytes: 31264
n = int(input())
a = list(map(int, input().split()))
a.sort()
tf = True
if n % 2 == 1:
    for i in range(1, n):
        a[i] -= i
    ans = int(n//2)
    if ans != sum(a):
        tf = False
else:
    for i in range(n):
        a[i] -= i
    ans = int(n//2)
    if ans != sum(a):
        tf = False
if tf:
    print(2 ** int(n//2) % (10**9+7))
else:
    print(0)


Measured memory_bytes: 13880
//abc108_b.cpp
//Sat Sep  1 20:28:39 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int even;
	int odd;
	if (k%2==0){
		even = k/2;
		odd = k/2;
	}else {
		even = (k-1)/2;
		odd = (k+1)/2;
	}


	cout << even*odd << endl;
//	printf("%.4f\n",ans);
}

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

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

    int n;
    cin >> n;
    int ans = 0;
    for(int i=1; i<=n; ++i){
        int x; cin>>x;
        if( (i % 2) == 1 and (x % 2) == 1 ){
            ++ans;
        }
    }
    cout << ans << '\n';


    return 0;
}

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

int main(){
  int N;cin>>N;
  int K;cin>>K;
  vector<int> p(N);
  int ans = 0;
  for(int i=0;i<N;i++){
    cin>>p[i];
  }
  sort(p.begin(),p.end());
  for(int i=0;i<K;i++){
    ans += p[i];
  }
  cout<<ans<<endl;
}
    

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define sort(a) sort((a).begin(),(a).end())
#define rev(a) reverse((a).begin(),(a).end())
using db = double;
using namespace std;
typedef long long ll;


int main() {
  int n, a, b;
  cin >> n >> a >> b;
  int ans;
  if (n*a > b) cout <<  b;
  else cout << n*a;
}



Measured memory_bytes: 256
inf = float('inf')

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

N = int(input())
A = list(map(int,input().split()))

accmulate(A)

dp = [[inf]*(N+1) for _ in range(N+1)]

for i in range(N):
    dp[i][i+1] = 0

for b in range(2,N+1):
    for i in range(N-b+1):
        j = i + b
        for k in range(i+1,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + query(i,j-1))

ans = dp[0][N]
print(ans)

Measured memory_bytes: 46812
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
int main()
{
    FASTINOUT;
    int x;
    cin>>x;
    int y[x-1];
    ll sum=0;
    for (int i=0;i<x-1;i++){
        cin>>y[i];
    }
    sum+=y[x-2]+y[0];
    for (int i=0;i<x-2;i++){
        if (y[i]<=y[i+1]){
            sum+=y[i];
        }
        else{
            sum+=y[i+1];
        }
    }
    cout<<sum<<endl;
    return 0;
}


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

int main() {
  long long X,N,A,B,C,ans,ans2;
  cin >>A>>B>>N;
  ans=0;
  ans2=0;
  if(B>N){
    ans=floor(A*N/B)-A*floor(N/B);
  }
  else{
    C=B-1;
    ans=floor(A*C/B)-A*floor(C/B);
    C=N-N%B-1;
    if(C>0){
      ans2=floor(A*C/B)-A*floor(C/B);
    }
  }
  if(ans2>ans){
    cout<<ans2<<endl;
    return 0;
  }
  cout <<ans<< endl;
}


Measured memory_bytes: 3636
from operator import itemgetter


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(n, aaa, bbb):
    aai = sorted(enumerate(aaa), key=itemgetter(1))
    bbi = sorted(enumerate(bbb), key=itemgetter(1))
    uft = UnionFind(n)
    for (ai, a), (bi, b) in zip(aai, bbi):
        if a > b:
            return False
        uft.union(ai, bi)
    if sum(r < 0 for r in uft.table) > 1:
        return True
    return any(a <= b for (ai, a), (bi, b) in zip(aai[1:], bbi))


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print('Yes' if solve(n, aaa, bbb) else 'No')


Measured memory_bytes: 33780
#include <iostream>
#include<stdio.h>
#define MAXSIZE 10000
#define PI 3.141592653589
using namespace std;
int main(){
  while(1){
    int H,W;
    std::cin >> H>>W;
    if(0==H&&0==W){
      return 0;
    }
    for(int i=0;i<H;i++){
      if(0==i||H-1==i){
        for(int j=0;j<W;j++){
          std::cout << "#" ;
        }
      }else{
        std::cout << "#";
        for(int j=1;j<W-1;j++){
          std::cout << "." ;
        }
        std::cout << "#";
      }


      std::cout  << '\n';
    }
    std::cout  << '\n';
  }

}

Measured memory_bytes: 3076
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {	
		Scanner scanner = new Scanner(System.in);
		int[] a = new int[scanner.nextInt()];
		for(int i = 0; i < a.length ; i++) {
			a[i] = scanner.nextInt();
		}
		for(int k = 0; k < a.length - 1; k++) {
			System.out.print(a[k] + " ");
		}
		System.out.print(a[a.length - 1]);
		System.out.println();
		insertionSort(a);	
	}
		
	public static void insertionSort(int[] a) {
		for(int i = 1; i < a.length ; i++) {
			int key = a[i];
			int j = i;
			while(j > 0 && key < a[j - 1]) {
				j--;
				a[j+1] = a[j];
			}
			a[j] = key;
			for(int k = 0; k < a.length - 1; k++) {
				System.out.print(a[k] + " ");
			}
			System.out.print(a[a.length - 1]);
			System.out.println();
		}
	}
}



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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 100010;
int R,C,N;
int x[MC][2],y[MC][2];
bool p[MC];
vector<P2> V;
stack<int> S;

int main(){
	scanf("%d%d%d" , &R , &C , &N);
	repp(i,0,N){
		bool b = 1;
		repp(j,0,2){
			scanf("%d%d" , x[i]+j , y[i]+j);
			if((x[i][j] != 0 && x[i][j] != R && y[i][j] != 0 && y[i][j] != C)) b = 0;
		}
		if(b){
			repp(j,0,2){
			if(x[i][j] == 0){
				V.PB(MP(y[i][j] , i));
			} else if(x[i][j] == R){
				V.PB(MP(R+2*C-y[i][j] , i));
			} else if(y[i][j] == 0){
				V.PB(MP(2*R+2*C-x[i][j] , i));
			} else {
				V.PB(MP(C+x[i][j] , i));
			}
			}
		}
	}
	sort(V.begin(),V.end());
	bool b = 1;
	for(auto z : V){
		if(p[z.second]){
			p[z.second] = 0;
			if(S.top() != z.second){
				b = 0;
				break;
			}
			S.pop();
		} else {
			p[z.second] = 1;
			S.push(z.second);
		}
	}
	printf("%s\n" , b ? "YES" : "NO");
	return 0;
}


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

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

const int INF = 1 << 30;
int n;
int p[41], t[41];
int dp[41][4];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> n, n) {
    for (int i = 1; i <= n; i++) {
      cin >> p[i] >> t[i];
    }

    fill((int *)dp, (int *)(dp + 41), INF);
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 4; j++) {
        if (t[i] + (j + 1) * p[i] + p[i + 1] <= t[i + 1]) {
          dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + p[i] + p[i + 1]);
        }
        if (j < 3 && t[i] + (j + 1) * abs(p[i + 1] - p[i]) <= t[i + 1]) {
          dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(p[i + 1] - p[i]));
        }
      }
    }
    
    int ans = INF;
    for (int i = 0; i < 4; i++) {
      ans = min(ans, dp[n][i] + p[n]);
    }

    if (ans != INF) {
      cout << "OK " << ans << endl;
    } else {
      for (int i = 0; i <= n; i++) {
        bool ng = true;
        for (int j = 0; j < 4; j++) {
          ng &= dp[i][j] == INF;
        }
        if (ng && ans == INF) ans = i;
      }
      cout << "NG " << ans << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3044
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);++i)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;--i)
#define FOR(i,s,n) for(int i = s;i < (int)n;++i)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;--i)
#define ALL(a) a.begin(),a.end()
#define IN(a, x, b) (a<=x && x<b)
template<class T>inline void out(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout<<t<<" ";out(ts...);}
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a = b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a = b;return true;}return false;}
constexpr int INF = 1e18;



signed main(){
	string s;
	cin >> s;
	int ans = 0;
	string t = "AGCT";
	REP(i,s.size()){
		FOR(j,i,s.size()){
			int flg = 1;
			FOR(k,i,j+1){
				int ok = 0;
				if(s[k] == 'A')ok = 1;
				if(s[k] == 'C')ok = 1;
				if(s[k] == 'G')ok = 1;
				if(s[k] == 'T')ok = 1;
				if(!ok)flg = 0;
			}
			if(flg)CHMAX(ans,j-i+1);
		}
	}
	out(ans);
}

Measured memory_bytes: 256
n, m = map(int, input().split())
p = 10**9 + 7
if n == m:
    ans = 2
    for i in range(1, n+1):
        ans *= (i%p)**2%p
        ans %= p
    print(ans%p)

elif abs(n-m) == 1:
    x = max(n, m)
    y = min(n, m)
    ans = 1
    for i in range(1, y+1):
        ans *= (i%p)**2%p
        ans %= p
    ans *= x%p
    print(ans%p)
else:
    print(0)


Measured memory_bytes: 3064
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Integer[] a = new Integer[N];
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
        }
        Arrays.sort(a, Comparator.reverseOrder());

        int alicePoint = 0;
        int bobPoint = 0;
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                alicePoint += a[i];
            } else {
                bobPoint += a[i];
            }
        }

        System.out.println(alicePoint - bobPoint);
    }
}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 2e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


ll n, a[N], pref[N];    

void solve()
{
    cin >> n;
    pref[0];
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    sort(pref,pref+n+1);
    ll ans = 0, temp = pref[0], cnt=1;
    for (int i=1; i<=n; i++) {
        if (pref[i]==temp) cnt++;
        else {
            ans += ((cnt)*(cnt-1))/2;
            cnt = 1;
            temp = pref[i];
        }
    }
    ans += ((cnt)*(cnt-1))/2;
    nout(ans);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 6752
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long n,minm;
  cin>>n;
  vector<long long>a(5);
  for(int i=0;i<5;i++)
  {
    cin>>a[i];
    if(i==0)minm=a[i];
    else if(a[i]<minm)minm=a[i];
  }
  if(minm>=n)cout<<5<<endl;
  else 
  {
    long long t=(n/minm);
    if(n%minm!=0)t++;
    cout<<t+4<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	System.out.println(N * N * N);
    }
}

Measured memory_bytes: 21076
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
const int N=1e6+10,M=21,mod=1e9+7;
ll a[N];
int32_t main(){
    ll n;
    cin >> n;
    ll ans=0;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    for (int i=0;i<n;i++){
        ans+=a[i]/2;
        if (a[i]%2==1 && a[i+1]>0){
            a[i+1]--;
            ans++;
        }
    }
    cout << ans;
}


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

long long A[100][10];
int mod = 1000000007;

int main() {
  int H, W, K;
  cin >> H >> W >> K;
  
  if(W==1) {
    cout << 1 << endl;
    return 0;
  }
  
  
  A[0][1] = 1;
  for(int h=1; h<=H; h++) {
    for(int w=1; w<=W; w++) {
      for(int i=0; i<1<<(W-1); i++) {
        bool connected = false;
        for(int j=0; j<W-2; j++) {
          if(i>>j&1 && i>>j+1&1) {
            connected = true;
            break;
          }
        }
        if(!connected) {
          if(w!=W && i>>w-1&1) {
            A[h][w+1] = (A[h][w+1] + A[h-1][w])%mod;
          } else if(w!=1 && i>>w-2&1) {
            A[h][w-1] = (A[h][w-1] + A[h-1][w])%mod;
          } else {
            A[h][w] = (A[h][w] + A[h-1][w])%mod;
          }
        }
      }
    }
  }
  
  cout << A[H][K] << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const ll mod = 1e9 + 7;
int main()
{
	SPEED
	ll x;
	cin >> x;
	ll p = 100, step = 0;
	while(p<x)
	{
		p += (p/100);
		step++;
	}

	cout << step;

	return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define r1(i, n) for (int i=0;i<n;i++)
#define r2(i, n) for (int i=1;i<n;i++)
#define intc(n) int n; cin >> n;
#define ll long long
#define llc(n) ll n; cin >> n;
using namespace std;
int main() {
  string s;
  cin >> s;
  string a="No";
  if(s.at(2)==s.at(3)&&s.at(4)==s.at(5)) a="Yes";
  cout << a << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] xi = new int[N];
        int[] yi = new int[N];
        int[] hi = new int[N];

        for(int i = 0; i < N; i++) {
            xi[i] = scanner.nextInt();
            yi[i] = scanner.nextInt();
            hi[i] = scanner.nextInt();
        }


        int xt = 0, yt = 0, ht = 0;
        for(int i = 0; i < N; i++) {
            if(hi[i] > 0) {
                xt = xi[i];
                yt = yi[i];
                ht = hi[i];
                break;
            }
        }

        for(int cx = 0; cx <= 100; cx++) {
            for(int cy = 0; cy <= 100; cy++) {
                int H = ht + Math.abs(cx - xt) + Math.abs(cy - yt);
                boolean stop = true;
                for(int i = 0; i < N; i++) {
                    if(hi[i] != Math.max(0, H - Math.abs(xi[i] - cx) - Math.abs(yi[i] - cy))) {
                        stop = false;
                        break;
                    }
                }
                if(stop) {
                    System.out.println(cx + " " + cy + " " + H);
                    return;
                }
            }
        }

    }
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define INF (ll)1e18



ll N,A[202020];
ll mk[202020];
ll i, j, k,ans;

void no(){
    printf("-1\n");
    exit(0);
}
pll calc(ll d,ll mx){
    if(d==N){
        //printf("a%lld,%lld\n", d, mx);
        if(mx<A[d])
            no();
        ans += A[d];
        return {(A[d] + 1) / 2, min(A[d], mx / 2)};
    }
    if(mx<=A[d])
        no();
    pll rt = calc(d + 1, min((mx - A[d]) * 2, (ll)1e18));
    //printf("a%lld,%lld ", d, mx);
    //printf("b%lld,%lld,%lld\n", ans, rt.first, rt.second);
    if(rt.first>rt.second){
        no();
    }
    ans += min(rt.second + A[d], mx);
    return {(rt.first + A[d] + 1) / 2, min(rt.second + A[d], mx / 2)};
}
int main(){
    scanf("%lld", &N);
    fornum(i,0,N+1){
        scanf("%lld", &A[i]);
    }

    calc(0, 1);
    printf("%lld\n", ans);

    return 0;
}

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 60;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  int n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  rep(i, n) {
    if(a[i]%2==1) {
      cout << "first" << endl;
      return 0;
    }
  }
  cout << "second" << endl;
}


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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b;
    cin>>a>>b;
    if(a==2||b==2){
    	cout<<"No";
	}
	else{
		cout<<"Yes";
	}
	return 0;
}


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

BTC = 380000.0


def main():
  n = int(input())
  gains = [tuple(input().split()) for _ in range(n)]
  rewards = [float(v) if u == 'JPY' else float(v) * BTC for v, u in gains]

  print('{:.5f}'.format(sum(rewards)))


if __name__ == '__main__':
  main()



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

const int MOD = 1000000007;

int main()
{
	string str;
	cin >> str;
	str += '@';

	unsigned long long ans = 0;
	string prev = "";
	for(int i=0;i<str.size();i++){
		int len = 1;
		while(prev == str.substr(i, len)){
			len++;
		}
		prev = str.substr(i, len);
		i += len-1;
		//cout << prev << endl;
		ans++;
	}
	ans--;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1152
//                             In The Name Of Allah
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
using namespace std; 
 
const int N = 3e5 + 100, OO = 1e4, M = 998244353, P = 6151, SQ = 120, lg = 22;
typedef pair <int, int> pii;
int n, c[30], a[30], b[30], t[30];
bool mark[30], is[30], nis[30];

inline int smin(int x, int y) {
	if(x < y) return x;
	return y;
}

inline int sabs(int x) {
	if(x < 0) return -x;
	return x;
}

inline int check(int i) {
	for(int j = 0; j < n; j++) {
		is[j] = false;
		if((i & (1 << j)))
			c[j] = b[j], nis[j] = true;
		else
			c[j] = a[j], nis[j] = false;
		t[j] = j;
	}
	sort(c, c + n);
	int ans = 0;
	for(int k = 0; k < n; k++) {
		int h = -1;
		for(int j = k; j < n; j++) {
			if(is[j] == false) {
				if(c[k] == a[t[j]] && (j % 2) == (k % 2) && nis[j] == false) {
					h = j;
					break;
				}
				else if(c[k] == b[t[j]] && (j % 2) != (k % 2) && nis[j] == true) {
					h = j;
					break;
				}
			}
			else {
				if(c[k] == b[t[j]] && (j % 2) == (k % 2) && nis[j] == true) {
					h = j;
					break;
				}
				else if(c[k] == a[t[j]] && (j % 2) != (k % 2) && nis[j] == false) {
					h = j;
					break;
				}
			}
		}
		if(h == -1)
			return OO;
		for(int j = h; j > k; j--) {
			swap(is[j], is[j - 1]);
			swap(t[j], t[j - 1]);
			swap(nis[j], nis[j - 1]);
			if(is[j] == true)
				is[j] = false;
			else
				is[j] = true;
			ans++;
		}
	}
	return ans;
}

int32_t main() {
    use_fast;
	cin >> n;
	for(int i = 0; i < n; i++)	
		cin >> a[i];
	for(int i = 0; i < n; i++)
		cin >> b[i];
	int mn = OO;
	for(int i = 0; i < (1 << n); i++) 
		mn = smin(mn, check(i));
	if(mn == OO)
		return cout << -1, 0;
	cout << mn << endl;
	return 0; 
}
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- ... 
*/	

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

int main() {
	int a, b;
	char op;

	bool isActive = true;
	do {
		cin >> a >> op >> b;
		switch(op) {
			case '+':
				cout << a + b << endl;
				break;
			case '-':
				cout << a - b << endl;
				break;
			case '*':
				cout << a * b << endl;
				break;
			case '/':
				cout << a / b << endl;
				break;
			case '?':
				isActive = false;
				break;
		}
	} while(isActive);

	return 0;
}

Measured memory_bytes: 3088
function Main(input){
    const arr = input.trim().split('\n');
    const XN = arr[0].split(' ').map(Number);
    if(XN[1] == 0){
        console.log(XN[0]);
        return;
    }
    const pn = arr[1].split(' ').map(Number);
    let diff = 999;
    let answer = 0;
    for(i=0; i<=101; i++){
        if(pn.indexOf(i)>=0) continue;
        if(Math.abs(XN[0]-i) < diff){
            diff = XN[0]-i;
            answer = i;
        }
    }
    console.log(answer);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

int main(void) {
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> a(q);
    vector<int> b(q);
    vector<int> c(q);
    vector<int> d(q);

    for(int iq=0;iq<q;iq++) {
        cin >> a.at(iq) >> b.at(iq) >> c.at(iq) >> d.at(iq);
    }

    llint ans = 0, anstmp;
    for(int i2=1;i2<=m;i2++) {
        for(int i3=i2;i3<=m;i3++) {
            for(int i4=i3;i4<=m;i4++) {
                for(int i5=i4;i5<=m;i5++) {
                    for(int i6=i5;i6<=m;i6++) {
                        for(int i7=i6;i7<=m;i7++) {
                            for(int i8=i7;i8<=m;i8++) {
                                for(int i9=i8;i9<=m;i9++) {
                                    for(int i10=i9;i10<=m;i10++) {
                                        vector<int> nowvec;
                                        nowvec.push_back(1);
                                        if(n>=2) nowvec.push_back(i2);
                                        if(n>=3) nowvec.push_back(i3);
                                        if(n>=4) nowvec.push_back(i4);
                                        if(n>=5) nowvec.push_back(i5);
                                        if(n>=6) nowvec.push_back(i6);
                                        if(n>=7) nowvec.push_back(i7);
                                        if(n>=8) nowvec.push_back(i8);
                                        if(n>=9) nowvec.push_back(i9);
                                        if(n>=10) nowvec.push_back(i10);
                                        anstmp = 0;
                                        for(int iq=0;iq<q;iq++) {
                                            if(nowvec.at(b.at(iq)-1)-nowvec.at(a.at(iq)-1)==c.at(iq)) anstmp += d.at(iq);
                                        }
                                        ans = max(ans, anstmp);
                                        // for(auto v:nowvec) cout << v;
                                        // cout << endl;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


ll n, a[N], q, b, c, cnt[N], s=0;

void solve()
{
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a[i]; cnt[a[i]]++; s+=a[i];
    }
    cin >> q;
    while (q--) {
        cin >> b >> c;
        if (b > c) {
            s = s-((b-c)*cnt[b]);
        }else {
            s = s+((c-b)*cnt[b]);
        }
        nout(s);
        cnt[c] += cnt[b];
        cnt[b] = 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 5080
import sys
import math
import numpy as np
from collections import Counter, defaultdict, deque
import itertools

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


inf = float("inf")
mod = 10 ** 9 + 7

n, m = MI()
d = defaultdict(set)
for _ in range(m):
    a, b = MI()
    d[a].add(b)
    d[b].add(a)

li = list(range(2, n + 1))

ans = 0
for l in itertools.permutations(li):
    now = 1
    for i, next in enumerate(l):
        if next in d[now]:
            now = next
            if i == n - 2:
                ans += 1
        else:
            break

print(ans)


Measured memory_bytes: 12492
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define MAXN 21
int main(){
    int n;
    int p[MAXN];
    cin >> n;
    rep(i,n)cin >> p[i];
    int count = 0;
    for(int i=1;i<n-1;i++){
        if(p[i-1]<p[i]&&p[i]<p[i+1])count++;
        else if(p[i-1]>p[i]&&p[i]>p[i+1])count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        static final int BASE = 10;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String n = in.next();
            long left = 0;
            long right = 1;
            while (!enough(n, right)) right *= 2;
            while (right - left > 1) {
                long middle = (left + right) / 2;
                if (enough(n, middle)) {
                    right = middle;
                } else {
                    left = middle;
                }
            }
            out.println(right);
        }

        private boolean enough(String n, long limit) {
            limit *= (BASE - 1);
            long carry = 0;
            for (int i = n.length() - 1; i >= 0; --i) {
                long cur = n.charAt(i) - '0';
                cur -= carry;
                carry = 0;
                if (cur > limit) return false;
                long sub = (limit - cur) % BASE;
                limit -= sub;
                carry += (limit - cur) / BASE;
                if (limit < 0) return false;
            }
            return true;
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

    }
}



Measured memory_bytes: 27220
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll modpow(ll x, ll n){
    ll res = 1, r = x;
    while(n){
        if(n % 2) res = res * r % MOD;
        r = r * r % MOD;
        n /= 2;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    ll s = 0;
    ll a[200005];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        s = (s + a[i]) % MOD;
    }
    ll ans = s * s % MOD;
    for(int i = 0; i < n; i++) ans = (ans + MOD - a[i] * a[i] % MOD) % MOD;
    cout << ans * modpow(2, MOD - 2) % MOD << endl;
}


Measured memory_bytes: 5176
#include <iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
static const int MAX=10000;
static const int INFTY=(1<<20);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
 
int n;
vector<pair<int, int> >adj[MAX];
 
void dijkstra(){
    priority_queue<pair<int, int> > PQ;
    int d[MAX],color[MAX];
    for(int i=0;i<n;i++){
        d[i]=INFTY;
        color[i]=WHITE;
    }
     
    d[0]=0;
    PQ.push(make_pair(0, 0));
    color[0]=GRAY;
 
     
    while (!PQ.empty()) {
        pair<int, int> f=PQ.top(); PQ.pop();
        int u=f.second;
        color[u] = BLACK;
        if ( d[u]<f.first *(-1))continue;
         
         
        for(int j=0;j<adj[u].size(); j++){
            int v=adj[u][j].first;
            if(color[v]==BLACK)  
                        continue;
            if(d[v] >d[u]+adj[u][j].second){
                d[v]=d[u]+adj[u][j].second;
                PQ.push(make_pair(d[v]*(-1),v));
                color[v]=GRAY;
            }
            }
        }
     
     
    for(int i=0;i<n;i++){
      cout<<i<< " "<<(d[i]==INFTY ?-1:d[i])<<endl;
    }
}
 
 
 
int main(){
    int k, u, v, c;
     
    cin>>n;
     
    for(int i=0;i<n;i++){
         cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
             adj[u].push_back(make_pair(v, c));
        }
    }
   
    dijkstra();
    return 0;
     
     
}



Measured memory_bytes: 8012
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void solve(int a,int b,int c)
{
	if(c==0){
		if(a==1 && b<0)
			printf("1 0 1 %d\n",b);
		else
			printf("%d %d 1 0\n",a,b);
		return;
	}
	
	vector<int> ps,qs;
	for(int i=1;i<=a;i++)
		if(a%i==0)
			ps.push_back(i);
	for(int i=1;i<=abs(c);i++)
		if(c%i==0){
			qs.push_back(i);
			qs.push_back(-i);
		}
	sort(ps.begin(),ps.end(),greater<int>());
	sort(qs.begin(),qs.end(),greater<int>());
	
	for(int i=0;i<ps.size();i++)
		for(int j=0;j<qs.size();j++){
			int p=ps[i],r=a/p;
			int q=qs[j],s=c/q;
			if(p*s+r*q==b){
				printf("%d %d %d %d\n",p,q,r,s);
				return;
			}
		}
	puts("Impossible");
}

int main()
{
	for(int a,b,c;cin>>a>>b>>c,a|b|c;)
		solve(a,b,c);
	
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int a, b;
 cin >> a >> b;
 
 if(22 > a*10+b && a*10+b >= 11)
   cout << 1 << endl;
 
 if(33 > a*10+b && a*10+b >= 22)
   cout << 2 << endl;
 
 if(44 > a*10+b && a*10+b >= 33)
   cout << 3 << endl;
 
 if(55 > a*10+b && a*10+b >= 44)
   cout << 4 << endl;
 
 if(66 > a*10+b && a*10+b >= 55)
   cout << 5 << endl; 
 
 if(77 > a*10+b && a*10+b >= 66)
   cout << 6 << endl;
 
 if(88 > a*10+b && a*10+b >= 77)
   cout << 7 << endl;
  
 if(99 > a*10+b && a*10+b >= 88)
   cout << 8 << endl;
  
 if(1010 > a*100+b && a*10+b >= 99)
   cout << 9 << endl;
  
 if(1111 > a*100+b && a*100+b >= 1010)
   cout << 10 << endl;
  
 if(1212 > a*100+b && a*100+b >= 1111)
   cout << 11 << endl;
  
 if(a*100+b >= 1212)
   cout << 12 << endl;
}

Measured memory_bytes: 256
//B Palindrome-philia
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,count;
  string s;
  cin>>s;
  n=s.size();
  count=0;
  for(int i=0;i<n/2;i++)
  {
    if(s.at(i)!=s.at(n-i-1))
    {
      count++;
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 384
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            char[] s = in.next().toCharArray();
            char[] t = in.next().toCharArray();

            Arrays.sort(s);
            Arrays.sort(t);

            for (int i = 0; i < Math.min(s.length, t.length); i++) {
                char c = s[i];
                char c2 = t[t.length - 1 - i];
                if (c < c2) {
                    out.print("Yes");
                    return;
                } else if (c2 < c) {
                    out.print("No");
                    return;
                } else {
                    continue;
                }
            }
            if (s.length < t.length) {
                out.print("Yes");
            } else {
                out.print("No");
            }
        }

    }
}



Measured memory_bytes: 24020
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
 
int main() {
	ll x;
	cin >> x;
	int y=0,j=0;
	for (int i=1;y<x;i++) {
		y+=i;
		j+=1;
	}
	cout << j;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int a,b,c;
  cin >> a >> b >> c;
  cout << min(b,c) << " ";
  if(c + b - a > 0){
    cout << c + b - a;
  }else{
    cout << 0;
  }
}

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

using namespace std;

long long int f(long long int p)
{
    if(p<=0)return 0;
    else return p;
}

int main()
{

    long long int n,k;
    scanf("%lld %lld",&n,&k);
    int i;
    long long int cnt = 0;
    for(i=k+1;i<=n;i++){
        cnt+=(n/i)*(i-k);
        if(!k)cnt+=n%i;
        else cnt+=f(n%i-k+1);
    }

    printf("%lld",cnt);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
template<class T> inline istream& operator >> (istream & c, vector<T> & A) {rep(i, A.size()) c >> A[i];return c;}
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<long long> a(n);
	cin >> a;
	long long ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		ans += a[i] / 2;
		a[i] %= 2;
		if (a[i + 1] > 0 && a[i]) a[i + 1]--, ans++;
	}
	ans += a[n - 1] / 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3968
import java.util.*;
import java.lang.*;
import java.io.*;

class Counter<T> extends TreeMap<T,Long>{
    public Counter(){
        super();
    }
    public Counter(List<T> list){
        super();
        for(T e: list) this.addOne(e);
    }
    public Long count(Object elm){
        return getOrDefault(elm,0L);
    }
    public void add(T elm, long amount){
        if(!this.containsKey(elm)) put(elm, amount);
        else replace(elm, get(elm)+amount);
        if(this.count(elm)==0) this.remove(elm);
    }
    public void addOne(T elm){
        this.add(elm, 1);
    }
    public void removeOne(T elm){
        this.add(elm, -1);
    }
    public void removeAll(T elm){
        this.add(elm, this.count(elm));
    }
    public static<T> Counter<T> merge(Counter<T> a, Counter<T> b){
        Counter<T> c = new Counter<>();
        for(T x: a.keySet()) c.add(x, a.count(x));
        for(T y: b.keySet()) c.add(y, b.count(y));
        return c;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        long[] A = new long[N];
        for(int n=0; n<N; n++) A[n] = sc.nextLong();

        long ans = 0;

        Counter<Long> counter = new Counter<>();
        for(int m = 0; m < N; m++){
            ans += counter.count(m - A[m]);
            counter.addOne(m + A[m]);
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 67836
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
using Graph=vector<vector<int> >;

int main(){
    int N,M;
    cin>>N>>M;
    Graph G(N+1);
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    queue<int> Q;
    vector<int> dist(N+1,-1);
    Q.push(1);
    dist[1]=0;
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        for(auto next_v:G[v]){
            if(dist[next_v]!=-1){
                continue;
            }
            dist[next_v]=v;
            Q.push(next_v);
        }
    }
    for(int i=1;i<=N;i++){
        if(dist[i]==-1){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    for(int i=2;i<=N;i++){
        cout<<dist[i]<<endl;
    }
    return 0;
}

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

int main(){
  int n;
  while(cin>>n,n){
    bool end=false;
    vector<int> f(n);
    vector<vector<int>> d(n,vector<int>(30,0));
    for(int i=0;i<n;i++){
      cin>>f[i];
      for(int j=0;j<f[i];j++){
	int day; cin>>day;
	d[i][day-1]=1;
      }
    }
    vector<vector<int>> pm(n,vector<int>(n,0)); // pm[i][j] = p_i can have j
    for(int i=0;i<n;i++) pm[i][i]=1;
    for(int i=0;i<30;i++){
      vector<int> meeting;
      for(int j=0;j<n;j++){
	if(d[j][i]) meeting.push_back(j);
      }
      vector<int> possible(n,0);
      for(int j=0;j<meeting.size();j++){
	for(int k=0;k<n;k++){
	  possible[k]|=pm[meeting[j]][k];
	}
      }

      for(int j=0;j<meeting.size();j++){
	for(int k=0;k<n;k++){
	  pm[meeting[j]][k]=possible[k];
	}
      }

      for(int j=0;j<n;j++){
	bool isfin=true;
	for(int k=0;k<n;k++){
	  isfin&=pm[j][k];
	}
	if(isfin && !end){
	  cout<<i+1<<endl;
	  end=true;
	}
      }
      
    }
    if(!end) cout<<-1<<endl;
    
  }
  return 0;
}

Measured memory_bytes: 3024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    ll N; cin >> N;
    int ans = 0;
    FOR(i, 2, 100000000) {
        int cur = 0;
        while (N % i == 0) {
            cur++;
            N /= i;
        }
        FOR(j, 1, 10000) {
            if (cur < j) break;
            ans++; cur -= j;
        }
    }
    if (N > 1) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <cctype>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, std::greater<>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//*/998244353;
const int base = 2187;
const double eps = 1e-9;
const int N = 300'000;
const int LOGN = 19;

int n, m, k;

void solve(int) {
  cin >> n >> m;
  cout << (n - 1 + m) / m << '\n';
}

void precalc() {
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i) {
    solve(i);
  }
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}



Measured memory_bytes: 384