akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


signed main()
{

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

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int a,b;
    cin>>a>>b;
    cout<<a*b;

} 



Measured memory_bytes: 3608
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int[] fruits = new int[N];
        for(int i=0;i<N;i++)
            fruits[i] = scanner.nextInt();
        Arrays.sort(fruits);
        int total = 0;
        for(int i=0;i<K;i++)
            total += fruits[i];
        System.out.println(total);
    }
}


Measured memory_bytes: 38656
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long 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*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return 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;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////


int main() {
	
	ll s, w;
	cin >> s >> w;

	if (w >= s) { cout << "unsafe" << endl; }
	else { cout << "safe" << endl; }

	system("PAUSE");
}


Measured memory_bytes: 3660
const input = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');

function main(input) {
  const num = Number(input[0]);
  var str = input[1].split('');
  
  for(var i = 0;i < str.length ;i++){
    var afterInc = str[i].charCodeAt(0) + num;
    if(afterInc > 90){
      afterInc -= 26;
    }
    str[i] = String.fromCharCode(afterInc);
  }
  console.log(str.join(''));
};

main(input);




Measured memory_bytes: 7372
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

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

  	//insertionSort(a, 1);
  	shellSort(a);
  	System.out.println(cnt);
  	for(int i = 0; i < n; ++i) {
  		System.out.println(a[i]);
  	}
  }
  
  public static void insertionSort(int[] a, int g){
  	for(int i = g; i < a.length; ++i) {
  		int v = a[i];
  		int j = i - g;
  		while(j >= 0 && a[j] > v) {
  			a[j + g] = a[j];
  			j = j - g;
  			cnt += 1;
  		}
  		a[j + g] = v;
  	}
  }
  
  public static void shellSort(int[] a) {
  	List<Integer> g = new ArrayList<Integer>();
  	for(int t = 1; t < a.length; t *= 3){
  		g.add(0, t);
  	}
  	
	if(g.size() == 0){
		g.add(0, 1);
	}
  	
  	int m = g.size();
  	System.out.println(m);
	
	for(int i = 0; i < m; ++i) {
		System.out.print(i == 0 ? "" : " ");
		System.out.print(g.get(i));
	}
  	System.out.println();
  	
  	for(int i = 0; i < m; ++i) {
  		insertionSort(a, g.get(i));
  	}
  }
}

Measured memory_bytes: 298696
inf = 10**12


def main():
    import sys
    from random import randint
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    D = int(input())
    C = list(map(int, input().split()))
    S = [[]]
    for _ in range(D):
        S.append(list(map(int, input().split())))
    ans = 0
    last = [0] * 26
    days = [Bit(D+1) for _ in range(26)]
    for i in range(26):
        days[i].add(D+1, 1)
    T = [-1]
    # greedy
    for d in range(1, D+1):
        plus = -inf
        t = -1
        for tt in range(26):
            plus_new = S[d][tt] + C[tt] * (d - last[tt])
            if plus_new > plus:
                t = tt
                plus = plus_new
        T.append(t)
        ans += S[d][t]
        last[t] = d
        days[t].add(d, 1)
        for i in range(26):
            ans -= C[i] * (d - last[i])

    def calc(d_list, q_list, cur):
        for d, q in zip(d_list, q_list):
            t = T[d]
            cur += S[d][q]
            cur -= S[d][t]
            k = days[q].sum(d)
            i = days[q].lower_bound(k)
            j = days[q].lower_bound(k+1)
            cur += C[q] * (d - i) * (j - d)
            k = days[t].sum(d)
            i = days[t].lower_bound(k-1)
            j = days[t].lower_bound(k+1)
            cur -= C[t] * (d - i) * (j - d)

            T[d] = q
            days[q].add(d, 1)
            days[t].add(d, -1)
        return cur

    # climb
    size = 5
    try_num = 1000
    for x in range(D // size):
        d_list = list(range(x*size+1, (x+1)*size+1))
        for _ in range(try_num):
            t_new = [randint(0, 25) for _ in range(size)]
            t_ori = []
            for d in d_list:
                t_ori.append(T[d])
            ans_new = calc(d_list, t_new, ans)
            if ans_new < ans:
                for i, d in enumerate(d_list):
                    T[i] = t_ori[i]
                    days[t_ori[i]].add(d, 1)
                    days[t_new[i]].add(d, -1)
            else:
                ans = ans_new

    for t in T[1:]:
        print(t+1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 95108
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define INF 1e9
#define INFL 1e18
#define mod 1000000007
//#define mod 998244353
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> os_pair;

ll power(ll x,ll n){ll res =1;while(n>0){if(n%2==1){res=res*x;}x=x*x;n=n/2;}return res;}
ll powm(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

//cout<< fixed << setprecision(10)
//__builtin_popcountll()



int main(){

    fast;
    ll n;
    cin>>n;
    if(n==1)
    cout<<0;
    else
    {
    	ll ans=powm(10,n);
    	ll z=powm(9,n);
    	z=z*2;
    	z=z%mod;
    	ans=(ans-z+mod)%mod;
    	ans=ans+powm(8,n);
    	ans=ans%mod;
    	cout<<ans;
	}
    

    

}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int g(int x)
{
    vector<int> tmp;
    tmp.push_back(x);
    while (x % 4 != 0)
    {
        x--;
        tmp.push_back(x);
    }
    int res = 0;
    rep(i, tmp.size()) res = res ^ tmp[i];
    return res;
}

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

    int a, b;
    cin >> a >> b;
    int n = g(b), m = g(a - 1), ans = n ^ m;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define maxN 200005
#define mod 1000000007
#define pi 3.14159265358979323846264338327950

void solve()
{
    int n, temp = 0;
    cin >> n;
    vector<int> all;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        all.push_back(t);
        temp ^= t;
    }
    for (int i = 0; i < n; i++)
    {
        cout << (temp ^ all[i]) << " ";
    }
    cout << endl;
}

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

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

using namespace std;

int main() {
    string S;
    cin >> S;

    string ans;
    // 表示されている文字列

    for (char c : S) {
        if (c == 'B') {
            // ansが既に空の場合に注意
            if (!ans.empty()) ans.pop_back();
        } else {
            // 0か1の場合はそのまま末尾に挿入
            ans.push_back(c);
        }
    }

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


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define Nmax 100000
#define INF 1000000000

int a[Nmax];
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	int pm = 1;
	int min = INF;
	for (int i = 0; i < n; i++) {
		if (a[i] < 0) pm *= -1;
		if (a[i] == 0) pm = 0;
		if (min > abs(a[i])) min = abs(a[i]);
	}
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		sum += abs(a[i]);
	}
	if (pm < 0) sum -= 2 * min;

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 640
#define _GLIBCXX_DEBUG //GCC環境での[]デバッグ
#include <bits/stdc++.h> //全ての標準ライブラリ
#define rep(i,n) for(int i = 0;i < n;i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
using namespace std;
using ll = long long;
int sumVector (const std::vector<int>& v){ //int配列計算
    int sum = 0;
    rep(i, v.size()) sum += v.at(i);
    return sum; 
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s=="ABC"){
        cout << "ARC";
    }
    else cout << "ABC";

}

Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 16:47:54 2020

@author: liang
"""
INF = 10**6
N = int(input())
B = [INF]+list(map(int,input().split()))+[INF]

ans = 0

for i in range(1,N+1):
    ans += min(B[i-1], B[i])

print(ans)

Measured memory_bytes: 9000
#include <bits/stdc++.h>
#define Y "Yes"
#define N "No"
using namespace std;

int a, b, c;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> a >> b >> c;
	if (c >= a && c <= b) cout << Y;
	else cout << N;
}

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

int main() {
		
	// recieve |V| and |E|
	int V, E; std::cin >> V >> E;
	std::vector<std::vector<std::pair<int, int>>> G(V);
	
	for(int i = 0; i < E; i++) {
		// recieve edges
		int u, v, d; std::cin >> u >> v >> d;
		u--; v--;
		G[u].push_back({v, d});
		G[v].push_back({u, d});
	}
	
	int Tmax; std::cin >> Tmax;

	// recieve info
	for(int i = 0; i < Tmax; i++) {
		int Nnew; std::cin >> Nnew;
		for(int j = 0; j < Nnew; j++) {
			int new_id, dst; std::cin >> new_id >> dst;
		}
	}

  // insert your code here to get more meaningful output
	// all stay
	for(int i = 0; i < Tmax; i++) std::cout << -1 << std::endl;
	return 0;
}


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

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;


vector<int> to[200100];

void dfs(int v, bool color, vector<int>&memo) {
    memo[v] = color;
    for (int nv: to[v]) {
        if (memo[nv] != -1) continue;
        dfs(nv, color^1, memo);
    }
}

int main() {
    int n; cin >> n;
    rep(i, n-1) {
        int a, b; cin >> a >> b;
        a--; b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    vector<int> memo(n, -1);
    dfs(0, 0, memo);

    int color1 = 0;
    int color2 = 0;
    rep(i, n) {
        if (memo[i] == 0) color1++;
        else color2++;
    }
    if (color1 < color2) {
        rep(i, n) {
            memo[i] = memo[i] ^ 1;
        }
        swap(color1, color2);
    }

    int num0 = n / 3;
    int num1 = n / 3 + (n % 3 >= 1);
    int num2 = n / 3 + (n % 3 >= 2);


    int diff1 = color1 - num1;
    int diff2 = color2 - num2;


    if (diff1 >= 0 && diff2 >= 0) {
        rep(i, n) {
            memo[i]++;
        }

        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        rep(i, n) {
            if (memo[i] == 1) {
                if (diff1 > 0) {
                    diff1--;
                    memo[i] = 3 + p3*3;
                    p3++;
                } else {
                    memo[i] = 1 + p1*3;
                    p1++;
                }
            } else {
                if (diff2 > 0) {
                    diff2--;
                    memo[i] = 3 + p3*3;
                    p3++;
                } else {
                    memo[i] = 2 + p2*3;
                    p2++;
                }
            }
        }

        rep(i, n-1) {
            cout << memo[i] << " ";
        }
        cout << memo[n-1] << endl;
    } else {
        rep(i, n) {
            memo[i]++;
        }
        rep(i, n) {
            if (memo[i] == 2) memo[i] = 0;
        }

        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        int diff0 = num0 - color2;
        int diff2 = num2;
        rep(i, n) {
            if (memo[i] == 1) {
                if (diff0 > 0) {
                    diff0--;
                    memo[i] = 3 + p3*3;
                    p3++;
                } else if (diff2 > 0) {
                    diff2--;
                    memo[i] = 2 + p2*3;
                    p2++;
                } else {
                    memo[i] = 1 + p1*3;
                    p1++;
                }
            } else {
                memo[i] = 3 + p3*3;
                p3++;
            }
        }

        rep(i, n-1) {
            cout << memo[i] << " ";
        }
        cout << memo[n-1] << endl;
    }


    return 0;
}

Measured memory_bytes: 18432
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=5e5+10;
main(){
    int n,a[110];
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if((i&1)&&(a[i]&1))ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3548
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
using Graph = vector<vector<int>>;

int main(){
    int n;
    cin>>n;
    string s;
    map<int,ll> memo;

    for(int i=0;i<n;i++){
        cin>>s;
        if(s[0]=='M') memo[s[0]-'A']++;
        else if(s[0]=='A') memo[s[0]-'A']++;
        else if(s[0]=='R') memo[s[0]-'A']++;
        else if(s[0]=='C') memo[s[0]-'A']++;
        else if(s[0]=='H') memo[s[0]-'A']++;
    }

    ll ans = 0;

    for(int i=0;i<24;i++){
        for(int j=i+1;j<25;j++){
            for(int k=j+1;k<26;k++){
                ans += memo[i]*memo[j]*memo[k];
            }
        }
    }

    cout<<ans<<endl;
}

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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;

typedef long long ll;

template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

const ll mod=1e9+7;

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

	string ans="No";
	if(n[0]==n[1]){
		if(n[1]!=n[3]&&n[2]==n[3])ans="Yes";
	}else if(n[0]==n[2]){
		if(n[0]!=n[1]&&n[1]==n[3])ans="Yes";
	}else if(n[0]==n[3]){
		if(n[0]!=n[1]&&n[1]==n[2])ans="Yes";
	}

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

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int N,re = 0;
    char s[100000];
    scanf("%d",&N);
    scanf("%s",&s);
    for(int i = 0;i < N;i++)
    {
        if(s[i] == s[i+1])re--;
    }
    re += N;
    printf("%d",re);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  vector<int>values;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    for(int j=0;j<x;j++){
        int f;
        cin>>f;
        values.push_back(f);
    }
  }
  int ans=0;
  for(int i=1;i<=31;i++){
    int counter = 0;
    for(int j=0;j<values.size();j++){
        if(values[j]==i){
            counter++;
        }
    }
    if(counter==n){
        ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007
#define INF (1 << 30)
#define REP(i, m, n) for(int i = (int)m; i < (int)n; ++i)
#define rep(i, n) REP(i, 0, n)


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

    string s; cin >> s;
    int N = s.size();
    bool flag = false;
    rep(i, N-1) if(s.substr(i, 2) == "AC") flag = true;
    cout << (flag ? "Yes" : "No") << '\n';
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a_list = [int(i) for i in input().split()]
a_dict = {}

for a in a_list:
    if a in a_dict.keys():
        a_dict[a] += 1
    else:
        a_dict[a] = 1

for i in range(n):
    if i+1 in a_dict.keys():
        print(a_dict[i+1])
    else:
        print(0)

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

int main() {
	int A, B, C, D, ans=0;
	cin >> A >> B >> C >> D;
	
	int start = max(A, C);
	int end = min(B, D);

	cout << max(0, end - start) << endl;

	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

ans = A[0] // 2
mod = A[0] % 2
for i in range(1, N):
    ans += A[i] // 2
    tmpmod = A[i] % 2
    if mod == tmpmod == 1:
        ans += 1
        mod = 0
    elif tmpmod == 1:
        mod = 1
    elif A[i] == 0:
        mod = 0
print(ans)


Measured memory_bytes: 7072
#include <bits/stdc++.h>
 
using namespace std;
 
#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define For(I,N)   for(int I=1;I<=(N);I++)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
#define SZ(X) ((int)(X.size()))
#define LG(X) ((int)(X.length()))
#define CL(X) (X).clear()
#define MAXEL(A,B) (*max_element(A,B))
#define MINEL(A,B) (*min_element(A,B))
#define ROPEN(X) freopen(X,"r",stdin)
#define WOPEN(X) freopen(X,"w",stdout)
#define BG(X) (X.begin())
#define EN(X) (X.end())
#define VI vector<int>
#define PII pair<int,int>
 
//cout << fixed << setprecision(20) << p << endl;
 
template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	LL N;
	LL A,B;
	cin>>N>>A>>B;
	//cout<<N/(a+b)*a+min(n%(a+b),a);
	cout<<N/(A+B)*A+min(N%(A+B),A);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 100005
struct BIT{
  void init(){  memset(bit,0,sizeof(bit));  }
  ll bit[MAX];
  void set(int r,ll x){
    r=MAX-r-1;
    while(r){
      bit[r]=max(bit[r],x);
      r-=(r&-r);
    }
  }
  ll get(int i){
    i=MAX-i-1;
    ll res=0;
    while(i<MAX){
      res=max(res,bit[i]);
      i+=(i&-i);
    }
    return res;
  }
};

int n;
ll sum,ans,a[MAX];
BIT A;

int main(){
  A.init();
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    sum+=a[i];
    ll k=A.get(a[i]);
    ans=max(ans,k+a[i]);
    A.set(a[i],k+a[i]);
  }
  cout<<sum-ans<<endl;
  return 0;
}

Measured memory_bytes: 2732
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1010;
long long n,t[maxn],a[maxn],t1=1,t2=1;
int main()
{
	cin>>n;
	for(long long i=0;i<n;i++)
	{
		cin>>t[i]>>a[i];
		long long cnt1=t1/t[i],cnt2=t2/a[i];
		if(t1%t[i])
			++cnt1;
		if(t2%a[i])
			++cnt2;
		long long cnt=max(cnt1,cnt2);
		t1=cnt*t[i],t2=cnt*a[i];
	}
	cout<<t1+t2<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <map>
using namespace std;
int w;

map<int, int> create_map() {
    map<int, int> m;
    m.insert({1, 0});
    m.insert({2, 0});
    m.insert({3, 0});
    return m;
}
map<int, int> m = create_map();
bool isEqual() {
    int idx = 0;
    for (int i = 1; i <= 3; i++) {
        if (m[i] == 5) { return true; }
        if (m[i] > 0) idx++;
    }
    return (idx == 3);
}

void setWinner() {
    if (m[3] == 0) w=1;
    else if (m[2] == 0) w=3;
    else if (m[1] == 0) w=2;
}

int main() {

    int p[5];
    for (; ;) {
        scanf("%d", &p[0]);
        if (p[0] == 0) break;
        m[1] = m[2] = m[3] = 0;
        m[p[0]]++;
        for (int i = 1; i < 5; i++) {
            scanf("%d", &p[i]);
            m[p[i]]++;
        }
        if (isEqual()) {
            for (int i = 0; i < 5; i++) printf("%d\n", 3);
        }
        else {
            setWinner();
            for (int i = 0; i < 5; i++) {
                (p[i] == w) ? printf("%d\n", 1) : printf("%d\n", 2);
            }
        }
    }

    return 0;
}



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

int main(void)
{
    int N;
    char S[1<<14];

    scanf("%d %s", &N, S);
    int M = strlen(S);
    for(int i = 0; i < M; i++){
        S[i] = (char)('A' + (S[i] - 'A' + N)%26);
    }
    printf("%s", S);
    return 0;
}


Measured memory_bytes: 128
a,b,k =  map(int,input().split())
if (b-a+1)/2 < k:
  for i in range(a,b+1):
    print(i)
else:
  for i in range(a,a+k):
    print(i)
  for i in range(b-k+1,b+1):
    print(i)

Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;

int main ()
{
	int n,k,a[55];
	scanf("%d%d",&n,&k);
	rep(i,0,n)
		scanf("%d",&a[i]);
	
	sort(a,a+n);
	int ans=0;
	rep(i,0,k) {
		ans+=a[n-i-1];
	}
	printf("%d\n",ans);


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
int main() {
	int N;
	cin>>N;
	string ans="No";
	int one=N%10;
	int th=N/1000;
	if((N-one)%111==0|(N-1000*th)%111==0){
		ans="Yes";
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

int main(){
  int N;
  scanf("%d", &N);
  
  set<int> primes;
  int all_gcd = 0;
  
  bool pairwise_coprime = true;
  for(int i = 0; i < N; i++){
    int A;
    scanf("%d", &A);
    all_gcd = gcd(all_gcd, A);
    
    for(int j = 2; j * j <= A; j++){
      if(A % j) continue;
      
      if(primes.count(j)){
        pairwise_coprime = false;
        break;
      }
      
      primes.insert(j);
      while(A % j == 0) A /= j;
    }
    
    if(A > 1){
      if(primes.count(A)) pairwise_coprime = false;
      primes.insert(A);
    }
  }
  
  if(all_gcd == 1){
    if(pairwise_coprime) puts("pairwise coprime");
    else puts("setwise coprime");
  }else{
    puts("not coprime");
  }
  
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
#define int ll

PII a[35];
signed main(void)
{
  int w, n;
  cin >> w >> n;
  REP(i, n) {
    int x, y;
    cin >> x; cin.ignore(); cin >> y;
    a[i] = MP(x, y);
  }
  int ans[50];
  REP(i, w) {
    int now = i+1;
    REP(j, n) {
      if(now == a[j].first) now = a[j].second;
      else if(now == a[j].second) now = a[j].first;
    }
    ans[now] = i+1;
  }
  FOR(i, 1, w+1) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 2992
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
/*-------------------------------------------*/

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

    int l, r, d;
    cin >> l >> r >> d;

    int cnt = 0;
    for(int i = l; i <= r; i++)
        if(i % d == 0) cnt++;

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <utility>
#include <string>
#include <cmath>
#include <set>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    int n;
    cin >> n;
    vector<int>x(n);
    set<int>y;
    rep(i,n){
        cin >> x[i];
        if(i%2){
            y.insert(x[i]);
        }
        
    }
    sort(x.begin(),x.end());
    ll ans = 0;
    rep(i,n){
        if(i%2){
            if(y.count(x[i])==0){
                ans++;
            }
        }
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define endl '\n'
#define pb push_back
#define debug(x) cout<<#x<<" "<<x<<endl;
const int mod = 999983;
const int MAX = 2e5+7;
const double pi = 3.141592653589793238460;
using namespace std;

bool is_pal (string s){
	return equal(s.begin(), s.begin() + s.size()/2, s.rbegin()) ? 1 : 0;
}

int power (int x , int y){
	if(y==0){
		return 1;
	}
	if(y&1){
		return x*power(x,y/2)%mod*power(x,y/2)%mod;
	}
	return power(x,y/2)%mod*power(x,y/2)%mod;
}

int modInv (int x){
	return power(x,mod-2);
}

int fact (int n){
	int f =1;
	for(int i=0; i<n; i++){
		f=(f*(i+1))%mod;		
	}
	return f;
}

int max (int x, int y){
	return x>y ? x : y;
}

int min (int x, int y){
	return x<y ? x : y;
}

int lcm (int x, int y){
	return (x*y)/__gcd(x,y);
}

bool prime[MAX]; 

void SieveOfEratosthenes(int n){
	 
    memset(prime, true, sizeof(prime)); 
    for (int p=2; p*p<=n; p++){ 
        if (prime[p] == true){ 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
         } 
    }  
}

int ans;

void solve(void){
	int a, b, c, k;
	cin>>a>>b>>c>>k;
	
	if(k >= a){
		ans+=a;
		k-=a;
	}

	else{
		cout<<k;
		return;
	}

	if(k>b){
		k = k- b;
	}

	else{
		cout<<a;
		return;
	}


	cout<<ans - k;
}
signed main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

fio;
int t = 1;
// cin>>t;
	while(t--)
	solve();

	return 0;
}


Measured memory_bytes: 3620
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ECHO(x) cout<<x<<endl;
#define MEMSET(a, n, x) REP(i, n) a[i]=x;
#define ARRIN(a, n) REP(i, n) cin>>a[i];
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;


int main(){
  int n;
  cin>>n;
  int m;
  while(m*(m-1)<2*n)++m;
  int sum=m*(m-1)/2;
  int rem=sum-n;
  FOR(i, 1, m){
    if(i==rem) continue;
    ECHO(i);
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;

    cout << min(b, a*n) << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
li = list(map(int,input().split()))

ans = 0
cnt = 0
for i in range(n-1):
  if li[i] >= li[i+1]:
    cnt += 1
  else:
    ans = max(cnt,ans)
    cnt = 0
ans = max(cnt,ans)
print(ans)

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

#define FIND(c, e) ((c).find(e) != (c).end())
#define NFIND(c, e) ((c).find(e) == (c).end())
#define ALL(t) (t).begin(), (t).end()
#define ALLR(t) (t).rbegin(), (t).rend()
#define MP make_pair

const int N = int( 2e5 ) + 10;
const int M = int( 1e6 ) + 1;
const int MOD = int( 1e9 ) + 7;
const double PI = acos(-1.0);
const double eps = 1e-6;
template<class T> T gcd(T a,T b){while(b){T r=a%b;a=b;b=r;}return a;}
template<class T> T lcm(T a,T b){return (a*b)/gcd(a,b);}
template<class T> T max(T a,T b,T c){return max(max(a,b),c);}
template<class T> T min(T a,T b,T c){return min(min(a,b),c);}
int n, a;
unordered_set<int> s;
void __answer()
{
    cin >> n;
    while(n--) {
        cin >> a;
        if(FIND(s, a)) {
            s.erase(a);
        } else s.insert(a);
    }
    cout << s.size() << endl;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cout << setprecision(11) << fixed;
    #ifdef LOCAL
        freopen("TEST.txt", "r", stdin);
    #endif
    __answer();
    return 0;
}


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

using namespace std;

int main() {
	int a, b, x;
	cin >> a >> b >> x;
	if (a <= x && (a + b) >= x) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

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

int main() {
    long long N;
    cin>>N;
    vector<long long> H(N);
    for(long long i=0;i<N;i++) cin>>H.at(i);
    
    long long answer = 0;
    long long counter=0;
    for(long long i=0;i<N-1;i++) {
        if (H.at(i)>=H.at(i+1)) counter++;
        else {
            answer = max(answer,counter);
            counter=0;
        }
    }

    answer = max(answer,counter);
    cout<<answer<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define si set <ll>
#define vi vector <ll>
#define popcount(x) __builtin_popcountll(x)
#define mii map <ll,ll>
#define vpi vector <pair <ll,ll> >
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mem0(a) memset(a,0,sizeof(a))
#define rep(i,a,n) for(ll i=a ; i<n ; i++)
#define ld long double
#define rall(a) (a).rbegin(),(a).rend()
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
 
ll power(ll b,ll e,ll m)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b%m,e/2,m)%m;
  return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b,e/2);
  return power(b*b,e/2);
}  
bool isPowerOfTwo(ll x)
{
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

ll pts[1000005][2]={0};
 
ll mnht(ll pt[1000005][2], int kth, int idx, int d)
{
    ll dist=0;
 
    for(int i=0;i<d;i++)
    {
        dist+=abs(pt[kth][i]-pt[idx][i]);
    }
 
    return dist;
}
ll max_cmb(ll cmbn[2], ll pt[1000005][2], int n, int d)
{
    ll pk=0;ll idx=0;
 
   for(int i=0;i<n;i++)
   {
       ll val=0;
 
       for(int j=0;j<d;j++)
       {
           val+=(1-2*cmbn[j])*pt[i][j];
       }
 
       if(val>pk)
       {
           pk=val;
           idx=i;
       }
   }
 
   return idx;
}



void solve()
{
  ll n,d;
   cin>>n;
   d=2;
 
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<d;j++)
        cin>>pts[i][j];
   }
 
   ll pk[2<<d];
 
   for(int j=0;j< 1<<(d);j++)
   {
       ll cmbn[2]={0};
       for(int dig=0;dig< d; dig++)
       {
           if(j & 1<<dig)
             cmbn[dig]=1;
          // cout<<cmbn[dig]<<" ";
       }
//cout<<endl;
       pk[j]=max_cmb(cmbn, pts, n, d);
   }
 
   ll maxd=0;
   for(int i=0;i<n;i++)
   {
       for(int j=0;j< 1<<(d);j++)
       maxd=max(maxd, mnht(pts, i, pk[j], d));
   }
 
   cout<<maxd<<endl;
}

int main()
{
  ll tt=1;
  // cin>>tt;
  while(tt--)
  {
    solve();
    cout<<"\n";
  }
}

Measured memory_bytes: 6744
#include <iostream>
using namespace std;
int main(void){
    int n, c[505], s[505], f[505];
    cin >> n;
    for (int i = 0; i < n - 1; i++) cin >> c[i] >> s[i] >> f[i];
    
    for (int i = 0; i < n - 1; i++) {
        int ans = 0;
        for (int j = i; j < n - 1; j++) {
            if (ans < s[j]) ans = s[j];
            else if (ans % f[j] != 0) ans = (ans / f[j] + 1) * f[j];
            ans += c[j];
        }
        cout << ans << endl;
    }
    cout << 0 << endl;
    
}


Measured memory_bytes: 256
# include <iostream>
# include <stdint.h>
# include <stdio.h>
# include <math.h>
using namespace std;


int main(){
	string str; 
    int m ,h;
    while(cin >>str){
        if(str =="-") break;
        string sss =str;
        cin >>m;
        int a =(int)str.size();
        for(int i=0;i<m;i++){
            cin >>h;
            for(int j=0;j<a;j++){
                if(j <h) sss[a-h+j] = str[j];
                else     sss[j-h] =str[j];
            }
            str = sss;
        }
        cout <<sss <<"\n";
    }
	return 0;
}



Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for( int i = 0 ; i < n ; i++ )
typedef long long ll ;
int main() {
  int N ;
  cin >> N ;
  int A[N] ;
  rep(i,N) cin >> A[i] ;
  int ans = 0 ;
  rep(i,N){
    if( A[i] == i+1 ){
      ans++ ;
      if(A[i+1] == i + 2 ) i++ ;
  	}
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    long a[] =new long[n];
    long count = 1;
    
    //入力値を配列に格納
    for(int i = 0; i < n; ++i){
      a[i] = sc.nextLong();
      //0があったら0を代入
      if(0 == a[i]){
        count = 0;
      }
    }
    //0が含まれてなかった場合
    if(count != 0){
      for(int i = 0 ; i < n ; ++i){
        if(a[i]<=(long)Math.pow(10,18)/count){
          count *= a[i];
        }else{
          count = -1;
          break;
        }
        
      }
     
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 61856
void main() {
    readln.chomp.stride(2).writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 508
#include<bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define INF (ll)1e18
#define pii pair<ll,ll>
#define mod 1000000007 //998244353
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fb(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define PI 3.141592653589793238
#define pq priority_queue<ll>
#define pqr priority_queue<ll,vector<ll>,greater<ll>()>
using namespace std;
ll pow_mod(ll a,ll b)
{
	ll res=1;
	while(b!=0)
	{
		if(b&1)
		{
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
void solve()
{
   ll n,k;
   
   cin>>n>>k;
   
   ll p[n+1];
   ll c[n+1];
   
   vector<ll>adj[n+1];
   
   for(ll i=1;i<=n;i++){
       cin>>p[i];
       adj[i].pb(p[i]);
   }
   
   for(ll i=1;i<=n;i++)
   cin>>c[i];
   
   
   bool mark[n+1];
   
   memset(mark,false,sizeof(mark));
   
   ll mx=-INF;
   
   
   function<void(ll,vector<ll>&,bool [])>dfs=[&](ll s,vector<ll> &t,bool mark[]){
      t.pb(s);
       mark[s]=true;
       
       for(auto a:adj[s]){
           if(!mark[a])
           dfs(a,t,mark);
       }
   };
   
   
   
   
   function<ll(vector<ll> &,ll )>max_val=[&](vector<ll> &t,ll jk){
     ll sz=(ll)t.size();
     
         ll p[sz+1]={0};
         
         
         ll mxx=-INF;
         
         for(ll i=1;i<=sz;i++)
         p[i]=c[t[i-1]]+p[i-1];
         
         for(ll i=jk;i<=sz;i++)
         mxx=max(mxx,p[i]-p[i-jk]);
         
         
         return mxx;
   };
   for(ll i=1;i<=n;i++){
       if(!mark[i]){
           vector<ll>v;
           
           dfs(i,v,mark);
           
           vector<ll>temp(2*(ll)v.size());
           
           
           for(ll j=0;j<(ll)v.size();j++)
           temp[j]=v[j];
           
           for(ll j=(ll)v.size();j<2*(ll)v.size();j++)
           temp[j]=v[j-(ll)v.size()];
           
           ll sm=0;
           
           for(ll j=0;j<(ll)v.size();j++)
           sm+=c[v[j]];
           
           for(ll j=1;j<=min(k,(ll)v.size());j++){
               ll res=max_val(temp,j);
               
               res+=max(0LL,sm*((k-j)/(ll)v.size()));
               mx=max(mx,res);
           }
          
          if(k>(ll)v.size()){
              mx=max(mx,sm*(k/(ll)v.size()));
          }
           
           }
   }
   
   cout<<mx<<endl;
}
int32_t main()
{    ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     
//Start from Here.

  ll t;
  t=1;
 // cin>>t;
  while(t--)
  solve();
  
//Good Bye!
    return 0;
}


Measured memory_bytes: 4572
#include<bits/stdc++.h>
using namespace std;
int d;
int main(){
	cin>>d;
	if(d==25)cout<<"Christmas";
	if(d==24)cout<<"Christmas Eve";
	if(d==23)cout<<"Christmas Eve Eve";
	if(d==22)cout<<"Christmas Eve Eve Eve";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN   1000001
using namespace std;
typedef long long ll;
int spf[MAXN];
void sieve()
{
    spf[1] = 1;
    for (int i=2; i<MAXN; i++)

        spf[i] = i;

    for (int i=4; i<MAXN; i+=2)
        spf[i] = 2;

    for (int i=3; i*i<MAXN; i++)
    {

        if (spf[i] == i)
        {

            for (int j=i*i; j<MAXN; j+=i)


                if (spf[j]==j)
                    spf[j] = i;
        }
    }
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
    sieve();
    int n;
    cin>>n;
    int ar[n];
    for(int i=0;i<n;i++)
        cin>>ar[i];

    map<int,int> mp;
    int gcd=0;
    for(int i=0;i<n;i++){
        gcd=__gcd(gcd,ar[i]);
        int temp=ar[i];
        map<int,int> mp1;
        while(temp!=1){
            mp1[spf[temp]]++;
            while(temp%spf[temp]==0 && temp>1){
                temp/=spf[temp];
                mp1[spf[temp]]++;
            }
        }
        for(auto it: mp1)
            mp[it.first]++;
    }
    int flag=1;
    for(auto it: mp)
        if(it.second>1 && it.first!=1){
            flag=0;break;
        }
    if(flag && gcd==1){
        cout<<"pairwise coprime"<<endl;
        return 0;
    }
    if(flag)
        cout<<"pairwise coprime"<<endl;
    else if(gcd==1)
        cout<<"setwise coprime"<<endl;
    else
        cout<<"not coprime"<<endl;
}

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

using namespace std;

typedef long long LL;

const int N = 100005;

int a[N], vt[N];

bool cmp(int i, int j) {
    return a[i] < a[j];
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        vt[i] = i;
    }
    sort(vt+1, vt+n+1, cmp);
    int ans1 = 0, ans0 = 0;
    for (int i = 1; i <= n; i++) {
        if ((vt[i]-i) & 1) {
            if (vt[i] & 1) ans1++;
            else ans0++;
        }
    }
    printf("%d", max(ans0, ans1));
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
    char s1[100];
    int i,n,max=0,x=0;
    scanf("%d%s",&n,s1);
    for(i=0; i<n; i++)
    {
        if(s1[i]=='I')
            x++;
        else if(s1[i]=='D')
            x--;
        if(max<x)
            max=x;
    }
    printf("%d\n",max);
    return 0;
}


Measured memory_bytes: 1728
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
                que.append((count + 1, py, px))

print(grid[dh][dw])


Measured memory_bytes: 129488
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
using namespace std;


int main()
{
	char s1[201], s2[101],s3[101];

	scanf("%s %s", &s2, &s3);
	strcpy(s1, s2);
	strcat(s1, s2);
	
	if (strstr(s1, s3)==NULL)cout << "No" << endl;
	else cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 3228
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

int main()
{
	ll n, x;
	cin >> n >> x;

	vector<ll> w(n);
	vector<ll> v(n);

	for (int i = 0; i < n; i++)
	{
		cin >> w.at(i) >> v.at(i);
	}

	vector<vector<ll>> dp(n + 1, vector<ll>(x + 1));



	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= x; j++)
		{
			if (j - w.at(i - 1) >= 0)
			{
				dp.at(i).at(j) = max(dp.at(i).at(j), dp.at(i - 1).at(j - w.at(i - 1)) + v.at(i - 1));
			}
			dp.at(i).at(j) = max(dp.at(i).at(j), dp.at(i - 1).at(j));
		}
	}

	cout << dp.at(n).at(x) << endl;
}


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

int main() {
  string N; cin >> N;
  int x = N.length()-1;
  if (N[x] == '3') cout << "bon";
  else if (N[x] == '0' || N[x] == '1' || N[x] == '6' || N[x] == '8') cout << "pon";
  else cout << "hon";
}

Measured memory_bytes: 3624
A = input()
B = input()
dA = len(A)
dB = len(B)
if dA > dB:
    print("GREATER")
elif dA < dB:
    print("LESS")
else:
    judge = 1
    for i in range(dA):
        if int(A[i]) > int(B[i]):
            print("GREATER")
            judge = 0
            break
        elif int(A[i]) < int(B[i]):
            print("LESS")
            judge = 0
            break
    if judge == 1:
        print("EQUAL")

Measured memory_bytes: 3064
#include"bits/stdc++.h"
 
using namespace std;
 
typedef long long LL;
 
const int N=132005;
 
struct pr{
	LL in,out;
	pr(LL _i=0,LL _o=0){in=_i,out=_o;}
};
vector<pr>dp[N],temp1,temp2;
vector<int>e[N];
int n,fa[N],dis[N],son[N][2],d[N];
LL deep[N],lim;
 
void insert(vector<pr>&v,const pr&i){
	int p=v.size()-1;
	if(!~p)v.push_back(i);
	else if(i.out<v[p].out)v.push_back(i);
}
 
void vector_merge(vector<pr>&v,vector<pr>&l,vector<pr>&r){
	v.clear();
	int x=l.size(),y=r.size(),p=0,q=0;
	if(!y)return;
	while(p!=x){
		while(q!=y&&l[p].out+r[q].in<=lim)q++;
		if(q)q--;
		if(l[p].out+r[q].in<=lim)v.push_back(pr(l[p].in,r[q].out));
		p++; 
	}
}
 
void merge_sort(vector<pr>&v,vector<pr>&l,vector<pr>&r){
	v.clear();
	int x=l.size(),y=r.size(),p=0,q=0;
	while(p!=x||q!=y){
		if(p==x)insert(v,r[q++]);
		else if(q==y)insert(v,l[p++]);
		else if(l[p].in<r[q].in)insert(v,l[p++]);
		else insert(v,r[q++]);
	}
}
 
void dfs(int x){
	if(!d[x]){
		dp[x].clear();
		dp[x].push_back(pr(deep[x],deep[x]));
		return;
	}
	int ls=son[x][0],rs=son[x][1];
	dfs(ls),dfs(rs);
	lim+=2*deep[x];
	vector_merge(temp1,dp[ls],dp[rs]);
	vector_merge(temp2,dp[rs],dp[ls]);
	merge_sort(dp[x],temp1,temp2);
	lim-=2*deep[x];
}
 
int main(){
#ifdef whzzt
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d%d",fa+i,dis+i);
		deep[i]=deep[fa[i]]+dis[i];
		son[fa[i]][d[fa[i]]++]=i;
	}
	LL l=0,r=1E13,ans=(l+r)>>1;
	while(l<r){
		lim=ans,dfs(1);
		if(dp[1].size())
			r=ans;
		else
			l=ans+1;
		ans=(l+r)>>1;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 33512