akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
#define vv(a,b) vector< vector<int> > v(a,vector<int>(b,0));
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

ll gcd(ll a,ll b)
{
    if(a!=0 && b==0)
    {
        return a;
    }
    if(a%b==0)
    {
        return b;
    }
    else
    {
        return(gcd(b,a%b));
    }
    
}
int main()
{
    ll x,n;
    cin>>n>>x;
    cout<<3*(n-gcd(n,x));
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#define maxn 200010
using namespace std;
typedef long long ll;
int n;
ll k,d[maxn],s[maxn],ans;
ll f[maxn];
struct node {
	int id;
	ll v;
} e[maxn];
bool cmp(node a,node b) {
	if (a.v<b.v)
		return 1;
	else if (a.v>b.v)
		return 0;
	else return a.id<b.id;
}
void update(int a) {
	while (a<=n) {
		f[a]+=1;
		a+=a&(-a);
	}
}
ll query(int a) {
	ll s=0;
	while (a>0) {
		s+=f[a];
		a-=a&(-a);
	}
	return s;
}
int main() {
	scanf("%d %lld",&n,&k);
	for (int i=1;i<=n;i++)
		scanf("%lld",&d[i]);
	s[0]=0;
	for (int i=1;i<=n;i++)
		s[i]=s[i-1]+d[i];
	for (int i=1;i<=n;i++) {
		e[i].id=i;
		e[i].v=s[i]-i*k;
	}
	sort(e+1,e+(n+1),cmp);
	for (int i=1;i<=n;i++) {
		ans+=query(e[i].id);
		update(e[i].id);
	}
	for (int i=1;i<=n;i++)
		if (e[i].v>=0)
			ans++;
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
    int W, H, x, y, r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if (0 <= x - r && 0 <= y - r && x + r <= W && y + r <= H)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
}


Measured memory_bytes: 3156
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
//もう二度とつかわん//
//    ↓ ↓　↓　　 //
#define ll long long
//    ↑　↑　↑    //
//フェルマー方程式の恨み//
#define rep(i,n) for(int i=0;i<n;i++)
#define ggr getchar(); getchar();return 0;
//素数判定
bool prime(ll n) {
	if (n == 1)return false;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0)return false;
	}
	return true;
}
using namespace std;
signed main() {
	ll n, ans = 1, memo, cnt = 0;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		memo = n;
		while (prime(i) && memo / i >= 1) {
			cnt += memo / i;
			memo /= i;
		}
		ans *= (cnt + 1);
		ans %= 1000000007;
		cnt = 0;
	}
	cout << ans << endl;
	ggr
}


Measured memory_bytes: 256
h,w = map(int,raw_input().split())
s = []
a = True
for i in range(h):
    s.append(raw_input())
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            if i - 1 >= 0 and s[i-1][j] == '#':
                continue
            if i + 1 < h and s[i+1][j] == "#":
                continue
            if j - 1 >= 0 and s[i][j-1] == '#':
                continue
            if j + 1 < w and s[i][j+1] == '#':
                continue
            a = False
if a == True:
    print 'Yes'
else:
    print 'No'                


Measured memory_bytes: 2568
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)

ll MOD = pow(10, 9) + 7;

ll powmod(ll a, ll p, ll MOD) {
	ll ans = 1;
	ll mul = a;
	for (; p > 0; p >>= 1, mul = (mul * mul) % MOD) {
		if ((p & 1) == 1)ans = (ans * mul) % MOD;
	}
	return ans;
}

ll combmod(ll n, ll r, ll MOD){
  if(n < r) return 0LL;
  if (n < 0 || r < 0) return 0LL;
  vector<ll> ff(n+1), vff(n+1);
  // 1! ~ n!
  ff[0] = 1;
  for(ll i = 1; i < n + 1; i++) {
    ff[i] = ff[i - 1] * i % MOD;
  }
  // n!^(MOD-2) (= n!^(-1))
  ll inv = powmod(ff[n], MOD - 2, MOD);

  // n!^(-1) ~ 1!^(-1)
  vff[n] = inv;
  for(ll i = n - 1; i >= 0; i--) {
    vff[i] = vff[i + 1] * (i + 1) % MOD;
  }

  // n combination r
  ll comb = (((ff[n] * vff[r]) % MOD) * vff[n - r]) % MOD;

  return comb;
}

int main() {

    ll n;
    cin >> n;
    vector<ll> A(n);
    REP(i, n) cin >> A[i];

    sort(A.begin(), A.end());

    ll cn = A[n-1];

    int l = 0;
    int r = n-2;
    while(r - l > 1){
        int tmp = (r + l) / 2;
        double val = (double)A[tmp] - (double)cn / 2.0;
        if (val < 0) l = tmp;
        else r = tmp;

    }

    double a = abs((double)cn / 2.0 - A[r]);
    double b = abs((double)cn / 2.0 - A[l]);

    ll cr = a < b ? A[r] : A[l];
    cout << cn << " " << cr << endl;

    return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class A_173_Payment
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);


            // 整数の入力
            long N = long.Parse(Console.ReadLine());

            long sho = N / 1000;
            long amari = N % 1000;
            long result = 0;

            if (amari == 0)
            {
                result = 0;
            }
            else
            {
                result = (sho + 1) * 1000 - N;
            }


            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27440
import java.util.*;

public class Main {
	void solve() {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		int out = 0;
		for(int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == '+') out++;
			else out--;
		}
		System.out.println(out);
		scan.close();
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}


Measured memory_bytes: 35752
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<string, string> P;
const ll MOD = 1000000007LL;
int A[200001];
int pos[200000];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	if (A[0] != 0) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 0; i + 1 < N; i++) {
		if (A[i + 1] - A[i] > 1) {
			cout << -1 << endl;
			return 0;
		}
	}
	pos[0] = 0;
	for (int i = 1; i < N; i++) {
		if (A[i] != 0) pos[i] = pos[i - 1];
		else pos[i] = i;
	}
	for (int i = N - 1; i >= 0; i--) {
		if (A[i] > i - pos[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	A[N] = -1;
	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		if (A[i - 1] + 1 != A[i]) {
			ans += A[i - 1];
		}
	}
	cout << ans << endl;
}

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

using namespace std;

int main(){
    int sx,sy,tx,ty;
    string s1="U",s2="D",s3="L",s4="R";

    cin >> sx >> sy >> tx >> ty;


    for (int i=0; i<(tx-sx); i++){
        cout << s4;
    }
    for (int i=0; i<(ty-sy); i++){
        cout << s1;
    }

    for (int i=0; i<(tx-sx); i++){
        cout << s3;
    }
    for (int i=0; i<(ty-sy); i++){
        cout << s2;
    }

    cout << s2;
    for (int i=0; i<(tx-sx)+1; i++){
        cout << s4;
    }
    for (int i=0; i<(ty-sy)+1; i++){
        cout << s1;
    }
    cout << s3;


    cout << s1;
    for (int i=0; i<(tx-sx)+1; i++){
        cout << s3;
    }
    for (int i=0; i<(ty-sy)+1; i++){
        cout << s2;
    }
    cout << s4 << endl;



    return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if((a+b)%2!=0) {
            System.out.println("IMPOSSIBLE");
        }else {
            System.out.println((a+b)/2);
        }
    }

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef double D;
struct P{
	D x,y,z;
	P(D a,D b,D c){x=a,y=b,z=c;}
};
P operator+(P a,P b){
	return P(a.x+b.x,a.y+b.y,a.z+b.z);
}
P operator-(P a,P b){
	return P(a.x-b.x,a.y-b.y,a.z-b.z);
}
P operator*(P a,D b){
	return P(a.x*b,a.y*b,a.z*b);
}
P operator/(P a,D b){
	return P(a.x/b,a.y/b,a.z/b);
}
typedef pair<P,P> L;
D dot(P a,P b){return a.x*b.x+a.y*b.y+a.z*b.z;}
D norm(P a){return dot(a,a);}
P perp(L l,P p){
	D t=dot(p-l.fs,l.fs-l.sc)/norm(l.fs-l.sc);
	return l.fs+(l.fs-l.sc)*t;
}
P refl(L l,P p){
	return p+(perp(l,p)-p)*2.0;
}
double x_[100],y_[100],z_[100],r_[100];
int main(){
	while(true){
		int N;
		cin>>N;
		if(N==0) break;
		double a=0,b=0,c=0,d,e,f;
		cin>>d>>e>>f;
		rep(i,N) cin>>x_[i]>>y_[i]>>z_[i]>>r_[i];
		while(true){
			int id=-1;
			double mn=1e9;
			rep(i,N){
				double x=x_[i],y=y_[i],z=z_[i],r=r_[i];
				double A=d*d+e*e+f*f;
				double B=2*(d*(a-x)+e*(b-y)+f*(c-z));
				double C=(a-x)*(a-x)+(b-y)*(b-y)+(c-z)*(c-z)-r*r;
				double D=B*B-4*A*C;
				if(D<0) continue;
				double t=(-B-sqrt(D))/(2*A);
				if(t<1e-7) continue;
				if(t<mn) mn=t,id=i;
			}
			if(id<0){
				printf("%.4f %.4f %.4f\n",a,b,c);
				break;
			}
			double t=mn;
			double na=a+t*d,nb=b+t*e,nc=c+t*f;
			P p(a,b,c);
			P np(na,nb,nc);
			L l=L(P(x_[id],y_[id],z_[id]),np);
			P ref=refl(l,p);
			P nd=ref-np;
			nd=nd/norm(nd);
			a=na,b=nb,c=nc;
			d=nd.x,e=nd.y,f=nd.z;
		}
	}
}

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

typedef long long ll;

ll oddsolve(ll a) {
    return (a+1)/2 % 2;
}

ll solve(ll a) {
    if (a % 2 == 1) return oddsolve(a);
    else return oddsolve(a+1) ^ (a+1);
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << (solve(B)^solve(A-1)) << endl;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    ans = 800 * N - 200 * (N // 15)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Measured memory_bytes: 2940
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{
	int n, y, b[50], r[50], t[50], a;
	double s, m;

	while (cin >> n, n)
	{
		cin >> y;
		for (int i = m = a = 0; i < n; ++i)
		{
			cin >> b[i] >> r[i] >> t[i];
			if (t[i] == 1 && (s = 1.0 + y*r[i]/100.0) > m)	m = s, a = b[i];
			else if (t[i] == 2 && (s = pow(1.0 + r[i]/100.0, y)) > m)	m = s, a = b[i];
		}
		cout << a << endl;
	}
	return 0;
}

Measured memory_bytes: 0
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scanf("%d", &N)
	ans := 0
	for i := 0; i < N; i++ {
		var ai int
		fmt.Scanf("%d", &ai)
		ans += ai - 1
	}
	fmt.Printf("%d\n", ans)
}


Measured memory_bytes: 640
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		
		if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
			System.out.println("Possible");
		} else {
			System.out.println("Impossible");
		}
	} 
}


Measured memory_bytes: 23764
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1LL<<31;

int main(){
    vector<vector<char>> ans(100,vector<char>(100));
    rep(i,100){
        rep(j,100){
            if(j<=49){
                ans[i][j]='.';
            }
            else{
                ans[i][j]='#';
            }
        }
    }
    ll a,b;
    cin >> b >> a;
    a--; b--;
    ll p=0,q=0;
    while(a){
        ans[p][q]='#';
        a--;
        if(p==48){
            p=0;
            q+=2;
        }
        else{
            p+=2;
        }
    }
    ll r=0,s=51;
    while(b){
        ans[r][s]='.';
        b--;
        if(r==48){
            r=0;
            s+=2;
        }
        else{
            r+=2;
        }
    }
    cout << 100 << " " << 100 << endl;
    rep(i,100){
        rep(j,100){
            cout << ans[i][j];
        }
        cout << endl;
    }
} 

Measured memory_bytes: 3648
#include <iostream>
#include <cmath>

int n;
int known_primes[500000];
int pointer = 0;

void dump_known_primes()
{
	for (int i = 0; i < pointer; i++) {
		std::cout << known_primes[i] << ' ';
	}
	std::cout << std::endl;
}

bool get_input()
{
//	std::cout << "get_input\n";
	return (std::cin >> n);
}

// a < known_primes[pointer+1] ÌÍÍÅ
// a ªf©Ç¤©»è·é
bool is_prime(int a)
{
//	std::cout << "is_prime\n";
	for (int i = 0; known_primes[i] <= std::sqrt(a); i++) {
		if (a % known_primes[i] == 0) {
			return false;
		}
	}
	return true;
}

// mçêÄ¢È¢ÌfðT·
void search_next_prime()
{
//	std::cout << "searcn_next_prime\n";
	int a;
	for (a = known_primes[pointer] + 2; !is_prime(a); a += 2);
	pointer++;
	known_primes[pointer] = a;
}

// XXX
int solve(int a)
{
//	std::cout << "solve\n";
	if (a <= known_primes[pointer]) {
//		std::cout << "a: " << a << ' ' << "pointer: " << pointer << std::endl;
		int i = pointer;
		while (a < known_primes[i]) {
//			std::cout << "i: " << i << std::endl;
			i--;
		}
		return i+1;
	} else {
		search_next_prime();
		return solve(a);
	}
}

int main()
{
//	std::cout << "main\n";
	known_primes[0] = 2;
	known_primes[1] = 3;
	known_primes[2] = 5;
	pointer = 2;
	while (get_input()) {
		std::cout << solve(n) << std::endl;
//		dump_known_primes();
	}
	return 0;
}

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

int main(){
    int ans = 0;   
    string s; cin >> s;
    string pre;

    for(;;){
        if(s.size() < 1){ break; }
        string tmp;
        string cur = {s[s.size()-1]};
        if(pre == cur){
            if(cur.size() == 1){
                if(s.size() < 2){
                    break;
                }
                tmp = s.substr(s.size()-2);
                s.erase(s.size()-2);
            }else{
                tmp = s.substr(s.size()-1);
                s.erase(s.size()-1);
            }
        }else{
            tmp = s.substr(s.size()-1);
            s.erase(s.size()-1);
        }
        pre = tmp;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
x1, y1, x2, y2 = (int(i) for i in input().split())
x4 = x1 - (y2 - y1)
y4 = y1 + (x2 - x1)
x3 = x4 - (y1 - y4)
y3 = y4 + (x1 - x4)
print(x3, y3, x4, y4)

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

int main()
{
  ll n;
  cin >> n;
  set<ll> ans;

  rep(i, n){
    ll a;
    cin >> a;
    ans.insert(a);
  }


  if (ans.size() == n)
  {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 9600
#include <stdio.h>
#include <stdlib.h>

int m, key;
struct node{
  struct node *left;
  struct node *right;
  struct node *parent;
  int key;
};

struct node *t;
struct node *root, *NIL;

void insert(struct node *, int key);
void inorder(struct node *t);
void preorder(struct node *t);
	  
int main(){

  int i, j, k;
  char order[20];
  
  scanf("%d", &m);
  for(i=0; i<m; i++){
    scanf("%s", order);

    if(order[0]=='i'){
      scanf("%d", &key);
      insert(t, key);
     
    }//insert
    
    else if(order[0]=='p'){

      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }//print
  }
  return 0;
}

void insert(struct node *t, int key){

  struct node *y=NIL;
  struct node *x=root;
  struct node *z;

  z=(struct node*)malloc(sizeof(struct node));
  z->key=key;
  z->left=NIL;
  z->right=NIL;
  
  while(x!=NIL){//適した入れる場所見付けるまで繰り返す
    y=x;
    if(z->key < x->key){
      x=x->left;
    }
    else x=x->right;
  }
  z->parent=y;

  if(y==NIL){
    root = z;
  }
  else {
    if(z->key < y->key){
    y->left = z;
    }
    else y->right=z;
  }
}
void inorder(struct node *t){

  if(t==NIL) return;

  inorder(t->left);
  printf(" %d", t->key);
  inorder(t->right);
}
void preorder(struct node *t){

  if(t==NIL) return;
  printf(" %d", t->key);
  preorder(t->left);
  preorder(t->right);
}
  



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

#ifdef ONLINE_JUDGE
using std::vector;
#else
template <class T>
struct vector: public std::vector<T> {
	using super = std::vector<T>;
	template <class ...Args>
	vector(Args &&...args): super(args...) {}
	typename super::reference operator [] (int i) { return super::at(i); }
	typename super::const_reference operator [] (int i) const { return super::at(i); }
};
#endif

int highbit(int x) { return 32 - __builtin_clz(x); }

struct stb_t {
	vector<vector<int>> stb;
	function<int(int, int)> fun;
	stb_t(vector<int>& a, function<int(int, int)> fun): stb(highbit(a.size())), fun(fun) {
		stb[0] = a;
		for (int k = 1; k < stb.size(); k++) {
			stb[k].resize(a.size() + 1 - (1 << k));
			for (int i = 0; i < stb[k].size(); i++)
				stb[k][i] = fun(stb[k - 1][i], stb[k - 1][i + (1 << k - 1)]);
		}
	}
	int query(int l, int r) {
		int k = highbit(r - l) - 1;
		return fun(stb[k][l], stb[k][r - (1 << k)]);
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	int n, k;
	std::cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		std::cin >> a[i];
	stb_t min_stb(a, [](int i, int j) { return i < j ? i : j; });
	stb_t max_stb(a, [](int i, int j) { return i < j ? j : i; });
	int ans = 1;
	for (int i = k; i < n; i++) {
		if (a[i] < max_stb.query(i - k + 1, i)) {
			ans++;
			continue;
		}
		int val = a[i - k];
		if (min_stb.query(i - k + 1, i + 1) < val)
			ans++;
	}
	int cnt = 0;
	for (int i = 0, j = 1; i < n; i = j++) {
		while (j < n && a[j - 1] < a[j])j++;
		if (k <= j - i) cnt++;
	}
	if (cnt == 0) cnt = 1;
	std::cout << ans - cnt + 1 << "\n";
	return 0;
}

Measured memory_bytes: 27264
#include<bits/stdc++.h>
#define int long long
#define rank Gacho
#define N 100005
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P2;

class UF{
public:
  int V;
  vector<int> par,rank;
  UF(){}
  UF(int V):V(V),par(V),rank(V,0){for(int i=0;i<V;i++)par[i]=i;}
  
  int find(int x){
    assert(x < V);
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }
  
  void unite(int x,int y){
    x=find(x), y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])par[x]=y;
    else{
      par[y]=x;
      if(rank[x]==rank[y])rank[x]++;
    }
  }

  bool same(int x,int y){return find(x)==find(y);}
};

int n, c[N];
vector<int> G[N];
vector<P> S[N];
int used[N];
UF uf;
vector<int> S2[N];
priority_queue<P2,vector<P2>,greater<P2> > q;
int C[N];

int sim(){
  
  int res=0;

  memset(used,0,sizeof(used));
  
  while(!q.empty()){
    
    P2 t = q.top(); q.pop();
    
    int node = t.second;
    int nC=t.first.first;
    
    if(used[uf.find(node)]) continue;
    used[uf.find(node)]=1;
    
    node=uf.find(node);
    
    int cost = 1;
    
    for(int i=0;i<S2[node].size();i++){
      
      int ni=S2[node][i];
      
      for(int j=0;j<G[ni].size();j++){
	int nnode=G[ni][j];
	cost=max(cost,C[nnode]+1);
      }

      cost=max(cost,C[ni]+1);
    }
    
    for(int i=0;i<S2[node].size();i++){
      
      int ni=S2[node][i];
      
      for(int j=0;j<G[ni].size();j++){
	int nnode=G[ni][j];
	C[nnode]=max(C[nnode],cost);
	q.push(P2(P(c[nnode],-C[nnode]),nnode));
      }
      
      C[ni]=max(C[ni],cost);
      q.push(P2(P(c[ni],-C[ni]),ni));
    }
    
    res+=cost*S2[node].size();
    
  }
  
  return res;
}

main(){
  
  cin>>n;

  for(int i=0;i<n;i++) scanf("%d", &c[i]);
  
  int m, a, b;

  cin>>m;
  
  for(int i=0;i<m;i++){
    scanf("%d %d", &a, &b);
    G[a-1].push_back(b-1);
    G[b-1].push_back(a-1);
  }

  uf=UF(n);
  
  for(int i=0;i<n;i++){

    S[i].push_back(P(c[i],i));
    
    for(int j=0;j<G[i].size();j++)
      S[i].push_back(P(c[G[i][j]],G[i][j]));

    sort(S[i].begin(),S[i].end());

    for(int j=0;j<S[i].size()-1;j++)
      if(S[i][j].first==S[i][j+1].first)
	uf.unite(S[i][j].second,S[i][j+1].second);
    
  }
  
  for(int i=0;i<n;i++){
    
    int par=uf.find(i);
    
    if(!used[par]){
      used[par]=1;
      q.push(P2(P(c[par],0),i));
    }
    
    S2[par].push_back(i);
    
  }

  cout<<sim()<<endl;  

}

Measured memory_bytes: 39844
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<stack>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<sstream>
#include<climits>
#include<cassert>
#include<time.h>

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define pb push_back
#define ss second
#define ff first
#define vi vector<int>
#define vl vector<ll>
#define s(n) scanf("%d",&n)
#define ll long long
#define mp make_pair
#define PII pair <int ,int >
#define PLL pair<ll,ll>
#define inf 1000*1000*1000+5
#define v(a,size,value) vi a(size,value)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define tri pair < int , PII >
#define TRI(a,b,c) mp(a,mp(b,c))
#define xx ff
#define yy ss.ff
#define zz ss.ss
#define in(n) n = inp()
#define vii vector < PII >
#define vll vector< PLL >
#define viii vector < tri >
#define vs vector<string>
#define DREP(a) sort(all(a)); a.erase(unique(all(a)),a.end());
#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
#define ok if(debug)
#define trace1(x) ok cerr << #x << ": " << x << endl;
#define trace2(x, y) ok cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)    ok      cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)  ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
                                << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
                                     << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
                                    << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#define read(a) freopen(a,"r",stdin)
#define write(a) freopen(a,"w",stdout)
ll MOD = int(1e9) + 7;

int debug = 1;
const int N = int(1e6) + 5;
using namespace std;
int main()
{
        int i,j,n,t;
        ios::sync_with_stdio(false);
        string a;
        cin>>a;
        int len = 0,cur = 0;
        rep(i,sz(a))
        {
                if(a[i] == 'T')
                {
                        if(cur > 0)
                                cur--;
                        else
                                len++;
                }
                else
                        cur++;
        }
        cout<<cur+len;
}


Measured memory_bytes: 720
/*
 * ex 4_1
 * kamecha
 */
#include<stdio.h>

int main(void){
    int num, dis;
    scanf("%d %d", &num, &dis);
    int ans = num/(2*dis + 1);
    //切り上げ処理
    if(num%(2*dis+1))   ans++;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto d = readln.chomp.split.to!(int[]);
  if (d[0] == d[1] && d[1] == d[2]) writeln("Yes");
  else writeln("No");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
#include<set>
#define ll long long int
#define mod 1000000007
#define MAX 10000003
#define pb push_back
#define mem(x,y) memset(x,y,sizeof(x))
#define loop(i,x,y) for(ll i=x;i<y;i++)
#define rloop(i,x,y) for(ll i=x-1;i>=y;i--)
using namespace std;
vector<vector<ll> > vec2d;
vector<pair<ll, ll> > vec_pair;
multiset<ll> node[200003];
// vector<pair<ll, ll> > vec_pair;
int main()
{
    ll n;
    cin>>n;
    ll arr[n+5];
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    ll cnt[n+5];
    for(ll i=0;i<n;i++)
        cnt[i]=0;
    ll t=0,p,q;
    cnt[0]=0;
    for(ll i=1;i<n;i++)
    {
        p=i;
        q=n-i;
        if(p==q)
        {
            cnt[i]=arr[i]-arr[i-1];
        }
    }
    for(ll i=0;i<n;i++)
        t+=cnt[i];
    cout << t << endl;
    return 0;
}

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

int main() {
    char b;
    cin >> b;
    if (b == 'A')
        cout << 'T' << endl;
    else if (b == 'T')
        cout << 'A' << endl;
    else if (b == 'G')
        cout << 'C' << endl;
    else
        cout << 'G' << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iomanip>
#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
  double r; cin >> r;
  
  cout << fixed << setprecision(6) << r*r*M_PI << ' ' << r*2*M_PI << endl;
  return 0;
}

Measured memory_bytes: 1284
#include<stdio.h>
int main(){

  int i,j,n,q,A[21],m[201];
  int S[2000000] = { 0 };

  scanf("%d", &n );

  for ( i = 0; i < n; i++ ){
    scanf("%d", &A[i] );
  }

  scanf("%d", &q );

  for ( i = 0; i < q; i++ ){
    scanf("%d", &m[i] );
  }

  int cnt,num,key;
  cnt = 1;

  for ( i = 0; i < n; i++ ){
    cnt *= 2;
  }

  for ( i = 0; i < cnt; i++ ){
    num = i;
    
    for ( j = 0; j < n; j++ ){
      if ( num % 2 == 1 ) S[i] = S[i] + A[j];
      num /= 2;
    }
  }

  for ( i = 0; i < q; i++ ){
    key = m[i];
    for ( j = 0; j <= cnt; j++ ){

      if ( j == cnt ){
	printf("no\n");
	break;
      }

      if ( S[j] == key ){
	printf("yes\n");
	break;
      } 

    }
  }

  return 0;

}

Measured memory_bytes: 8400
import sys

import math

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

ball_arr = [0] * N

for i in range(math.floor(N/2), N):
    ball_arr[i] = a[i]
    
# print(ball_arr)

for i in reversed(range(math.floor(N/2))):
    # print(i)
    # print(i+1)
    # print(sum(ball_arr[i-1::i+1]))
    # print(sum(ball_arr[i-1::i+1]) != a[i])
    mul_arr = ball_arr[i::i+1]
    # print(mul_arr)
    if sum(mul_arr) % 2 != a[i]:
        # print((mull_arr.index(0)+1)*i)
        if 0 in mul_arr: 
            ball_arr[(mul_arr.index(0)+1)*i] = 1
        else:
            print(-1)
            sys.exit()
    # print(ball_arr)
    # print('---')
# print(ball_arr)

M = sum(ball_arr)
print(M)
for i, v in enumerate(ball_arr):
    if v == 1:
        print(i+1, end=' ')

Measured memory_bytes: 10064
c=[list(map(int,input().split())) for _ in range(3)]
for i in range(2):
    if not (c[i+1][0]-c[i][0]==c[i+1][1]-c[i][1] and c[i+1][1]-c[i][1]==c[i+1][2]-c[i][2]):
        print("No")
        break
    if not (c[0][i+1]-c[0][i]==c[1][i+1]-c[1][i] and c[1][i+1]-c[1][i]==c[2][i+1]-c[2][i]):
        print("No")
        break
else:
    print("Yes")


Measured memory_bytes: 9216
#include<bits/stdc++.h>
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)
const int N = 2e5 + 5;
int a[N] , n , k;

int c(int n , int k){
   return (n + k - 1) / k;
}
bool valid(int mid){
   long long used = 0;
   for(int i = 0 ; i < n ; ++i)
      used += (c(a[i] , mid) - 1);
   return used <= k;
}
int main() {
#ifndef ONLINE_JUDGE
#endif
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> n >> k;
   for(int i = 0 ; i < n ; ++i)
      cin >> a[i];
   int l = 1 , r = *max_element(a , a + n) , ans = inf;
   while(l <= r){
      int mid = (l + r) / 2;
      if(valid(mid))
         r = mid - 1 ,ans = mid;
      else l = mid + 1;
   }
   cout << ans << "\n";
}

Measured memory_bytes: 4392
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;

static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Console.WriteLine(Enumerable.Range(1, n).Zip(Console.ReadLine().Split().Select(int.Parse).ToArray(), (x, y) => x != y).Count(x => x) <= 2 ? "YES" : "NO");
    }
}


Measured memory_bytes: 13396
#include <iostream>

using namespace std;

int main(void){

  int a,b;
  bool f = false;
  while( cin >> a >> b && a && b ){

    if(f) cout << endl;
    else f = true;

    bool flag = false;
    for( int i = a ; i <= b ; i++ ){
      if( i % 4 == 0 ){
	if( i % 400 == 0 ) cout << i << endl;
	else if( i % 100 == 0 ) continue;
	else cout << i << endl;
	flag = true;
      }
    }
    if(flag == false ) cout << "NA" << endl;
  }
  return 0;
}

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

int main(int argc, char **argv)
{
	string str; ll k; cin >> str >> k; --k;

	ll i{0};
	while (str[i] == '1') {++i;}
	std::cout << str[min(k, i)]<< std::endl;
}

Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0]*(N-1)
    d = [[0]*N for i in range(N)]

    for i in range(N-1):
        for j in range(i+1, N):
            if (i<X and j<X) or (Y<i and Y<j):
                d[i][j] = j-i
            elif X<=i and j<=Y:
                d[i][j] = min(j-i, (Y-X+1)-(j-i))
            elif i<X and Y<j:
                d[i][j] = j-Y+X-i+1
            elif i<X and X<=j<=Y:
                d[i][j] = X-i+min(j-X, Y-j+1)
            elif X<=i<=Y and Y<j:
                d[i][j] = min(Y-i, i-X+1)+j-Y

    for i in range(N-1):
        for j in range(i+1, N):
            ans[d[i][j]-1] += 1
        
    for i in ans:
        print(i)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 83228
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void){
  int K;
  string S;

  cin >> K >> S;

  if(S.size() > K){
    cout << S.substr(0,K) << "...";
  }else{
    cout << S;
  }


  return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
  string s;cin >> s;
  string ans = "No";
  if(s[0]=='9' || s[1]== '9')ans = "Yes";
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
template<typename T> T gcd(T a,T b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;

int n, a[300009];
string s;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> s;
  int u = 0;
  FOR(i, 0, n){
    a[i] += u;
    if(s[i] == 'W') u++;
  }
  u = 0;
  int ans = iinf;
  FORR(i, n-1, 0){
    mins(ans, a[i] + u);
    if(s[i] == 'E') u++;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n;
  cin >> n;
  vector<set<pair<string,int>>> dp(n);
  set<pair<string,int>> first;
  first.insert(make_pair("a",1));
  dp[0] = first;
  FOR(i,1,n){
    set<pair<string,int>> new_set;
    for(auto p : dp[i-1]){
      string str = p.first;
      int count = p.second;
      for(int i=0;i<(int)str.length();i++){
        //
        new_set.insert(make_pair(str+str[i],count));
      }
      new_set.insert(make_pair(str+(char)('a'+count),count+1));
    }
    dp[i] = new_set;
  }
  for(auto s : dp[n-1]){
    cout << s.first << endl;
  }
  return 0;
}


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

       
   
   int main(){
 int  t,count=0;
 cin>>t;
 while(t--){
     int a,b;
     cin>>a>>b;
     if(a==b){
         count++;
      if(count==3){
             cout<<"Yes"<<endl;
             return 0;
         }
     }
     else{
         count=0;
     }
 }
 cout<<"No"<<endl;
return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;


int main() {
	complex<long double>cmpmp;
	const long long int mod = 1000000007;
	map<long long int, long long int>mp;
	//cout << fixed << setprecision(10);
	long long int N, A, B, h[200] = {}, left = 0, right = 1000000000, num = 0, sum[15] = {},memo;
	long long int ten[20] = { 1 }, ketawa = 1,key=0;

	string str;
	cin >> N;
	for (int i = 1; i <= 18; i++) {
		ten[i] = ten[i - 1] * 10;
	}
	for (int i = 0; i < 18; i++) {
		num = ten[i];
		ketawa = 1;
		while (num != ten[i + 1] - 1) {
			for (int j = 0; j <= i; j++) {
			next:
				while (num / ten[j] % 10 != 9) {
					
					if (ketawa * ten[j] - num >= 0) {
						memo = num;
						cout << num << endl;
						N--;
						key = 1;
						if (N == 0) { return 0; }
					}
					num += ten[j];
					ketawa++;
				}
				if (ketawa * ten[j] - num >= 0&&memo!=num) {
					memo = num;
					cout << num << endl;
					N--;
					key = 1;
					if (N == 0) { return 0; }
				}
				if (key == 1&& num / ten[i] % 10 != 9) {

					num+=ten[max(j-3,0)];
					j=max(j-3,0);
					ketawa = 0;
					for (int k = 0; k <= 16; k++) {
						ketawa += num / ten[k] % 10;
					}
					key = 0;
					goto next;
				}
				else if (key == 1) { key = 0; }


			}
		}

	}
}


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

int main() { 
  int a,b;
  cin>>a>>b;
  if(a>=13){
    cout<<b<<endl;
  }
  else if(a>=6){
    cout<<b/2<<endl;
  }
  else {
    cout<<0<<endl;
  }
}


Measured memory_bytes: 256
def Eratosthene(n):
    prime = [1]*(n+1)
    prime[0] = 0
    prime[1] = 0

    for i in range(2, int(n**0.5)+1, 1):
        if prime[i]==0:
            continue
        for j in range(i+1, n+1, 1):
            if prime[j]==0:
                continue
            if j%i==0:
                prime[j] = 0
    return prime


Q = int(input())
L = []
R = []

for _ in range(Q):
    l,r = map(int, input().split())
    R.append(r)
    L.append(l)
Query = list(zip(L,R))
A = [0]*(10**5+1)
prime_list = Eratosthene(10**5)

for i in range(1, 10**5+1, 1):
    if i%2==0:
        continue
    if prime_list[i]==1:
        if (i+1)%2==0:
            if prime_list[(i+1)//2]==1:
                A[i] = 1

S = [0]*(len(A)+1)

for i in range(len(A)):
    S[i+1] = S[i] + A[i]

for l,r in Query:
    print(S[r+1]-S[l])

Measured memory_bytes: 23460
#include <stdio.h>
  
int main(void)
{
	int sum,SINA,a,b,c,d,e,f,A,B,C,D,E,F;
	START:
	scanf("%d",&SINA);
	if(0<SINA){
		sum=1000-SINA;
		a=sum/500;
		A=sum%500;
		b=A/100;
		B=A%100;
		c=B/50;
		C=B%50;
		d=C/10;
		D=C%10;
		e=D/5;
		E=D%5;
		f=E/1;
		F=E%1;
		printf("%d\n",SINA=a+b+c+d+e+f);
		goto START;
	}
	else if(SINA==0){
	}
	return 0;
}


Measured memory_bytes: 2060
from itertools import accumulate
L = int(input())
p2 = [2 ** i for i in range(20)]
p2acc = list(accumulate(p2))

for i in range(19, -1, -1):
    if L >= p2[i]:
        N = i + 1
        break

ans = []
for i in range(N - 1):
    ans.append((i, i + 1, 0))
    ans.append((i, i + 1, 2 ** i))

# 表現できてないパスの数
remain = L - 2 ** (N - 1)
# 次のバイパスの長さ
bypass = 2 ** (N - 1)

while remain:
    for i in range(19, -1, -1):
        if remain >= p2[i]:
            ans.append((i, N - 1, bypass))
            remain -= p2[i]
            bypass += p2acc[i - 1] + 1

print(N, len(ans))
for u, v, w in ans:
    print(u + 1, v + 1, w)


Measured memory_bytes: 3064
N, K = map(int, input().split())
d = {}
key = set([])
for _ in range(N):
  a, b = map(int, input().split())
  if a in key:
    d[str(a)] += b
  else:
    key.add(a)
    d[str(a)] = b
key = sorted(list(key))
for k in key:
  if d[str(k)] < K:
    K -= d[str(k)]
  else:
    print(k)
    break

Measured memory_bytes: 22396
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

bool dt[200000][3];
ll dp[200000][3];
int n;
ll A[200000];

ll f(int i, int j) {
    if(i >= n) return (n & 1) * (j ? 0 : -1e10);
    if(dt[i][j]) return dp[i][j];
    dt[i][j] = 1;
    if(j == 2) return dp[i][j] = A[i] + f(i + 2, 2);
    return dp[i][j] = max(A[i] + f(i + 2, j), f(i + 1, j + 1));
}

int main() {
    cin >> n;
    memset(dt, 0, sizeof dt);
    for(int i = 0; i < n; ++i)
        cin >> A[i];
        
    cout << f(0, n % 2 == 0);
    
    return 0;
}

Measured memory_bytes: 16680
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func solve() {
	n, k := getInt(), getInt()
	hs := getIntSlice(n)
	sort.Ints(hs)

	ans := 0
	for i := 0; i < n-k; i++ {
		ans += hs[i]
	}
	fmt.Fprintln(wr, ans)
}

// -----------------------------------------

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() (ret int) {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return
}

func getIntSlice(n int) (ret []int) {
	ret = make([]int, n)
	for i := range ret {
		ret[i] = getInt()
	}
	return
}

func getString() (ret string) {
	sc.Scan()
	ret = sc.Text()
	return
}

func getRunes() (ret []rune) {
	ret = []rune(getString())
	return
}


Measured memory_bytes: 6208
def resolve():
    import sys
    input = sys.stdin.readline
    n, q = map(int, input().split())
    childs = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        childs[b - 1].append(a - 1)
        childs[a - 1].append(b - 1)
    counter = [0] * n
    for _ in range(q):
        p, x = list(map(int, input().split()))
        counter[p - 1] += x
    ans = [-1] * n
    ans[0] = counter[0]
    q = [(0, x) for x in childs[0]]
    while q:
        p, i = q.pop()
        if ans[i] >= 0:
            continue
        ans[i] = ans[p] + counter[i]
        for j in childs[i]:
            q.append((i, j))
    print(*ans)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 67436
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    def ok(m):
        cnt=0
        for a in aa:
            if a+m<=n-1:continue
            cnt+=(a+m+1)//(n+1)
            if cnt>m:return False
        return True

    n=II()
    aa=LI()
    mx=max(aa)
    cur=0
    b=0
    while 1:
        cur=0
        for i in range(n):
            c=(aa[i]+b+1)//(n+1)
            c=max(c,0)
            aa[i]-=(n+1)*c
            cur+=c
        if cur==0:break
        b+=cur
    for m in range(b,b+10**5):
        if ok(m):break
    print(m)

main()


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

int main() {
  int N, l , r, result;
  
  cin >> N;
  
  for (int i=0; i<N; i++) {
    cin >> l >> r;
    result += (r - l) + 1;
  }
  cout << result << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int a[3],k;
int main() {
    scanf("%d %d %d",a,a+1,a+2);
    for(int i=0;i<3;i++)
        if(a[i]%2==0) {
            printf("0");
            return 0;
        }
    for(int i=0;i<2;i++) //내림차순 정렬
        for(int j=i+1;j<3;j++)
            if(a[i]<a[j]) {
                int t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        printf("%lld\n",(long long int)a[1]*a[2]);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
#define MAX LONG_MAX
long aray[4000000];
int n,p=2;

int right(int k){
  return 2*k+2;
}
int left(int k){
  return 2*k+1;
}
int parent(int k){
  return (k-1)/2;
}
long query(int a,int b,int k,int l,int r){
  long res;
  //if (n==1)res = aray[0];
  if(r<=a || b<=l)res = MAX;
  else if(a<=l && r<=b){
      res = aray[k];
      //cout<<"k:"<<k<<" res:"<<res<<endl;
  }
  else {
      res = min(query(a,b,left(k),l,(l+r)/2),query(a,b,right(k),(l+r)/2,r));
      //cout<<"res"<< res<<" l:"<<l<<" r:"<<r<<endl;
  }
  return res;   
}
long findmin(int a,int b){
    return query(a,b,0,0,p);
}
void update(int k,long x){
  k = k+p-1;
  aray[k] =x;
  while(k>0){
    k=parent(k);
    aray[k]=min(aray[left(k)],aray[right(k)]);
  }
}
void check(){
    int k=1,c=1;
    cout<<"---------------"<<endl;
  for(int i=0;i<2*p-1;i++){
      cout<<aray[i]<<" ";
      k++;
      if(k%c==0){
          cout<<endl;
          k=0;
          c*=2;
      }
  }
  cout<<endl;
}
int main(){
  int l,i=0,j;
  long tmp;
  cin>>n>>l;
  while(n>pow(p,i))i++;
  p= pow(p,i);
  for(i=0;i<p*2+1;i++)aray[i]=MAX;
  for(i=0;i<n;i++){
      cin>>tmp;
      update(i,tmp);
  }
  for(i=0;i<n-l+1;i++){
    //cout<<"---------------"<<endl;
    cout<<findmin(i,i+l);
    if(i!=n-l)cout<<" ";
  }
  cout<<endl;
      //cout<<"---------------"<<endl;
      //check();
  return 0;
}



Measured memory_bytes: 19668
w = ""
try:
    for _ in range(5):
        w += input().lower()
except EOFError:
    pass

ch = ["a", "b", "c", "d", "e", "f", "g", "h", "i",
      "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
      "u", "v", "w", "x", "y", "z"]

for chkspell in ch:
    print("{} : {}".format(chkspell, w.count(chkspell)))



Measured memory_bytes: 5556
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef vector <int> vi;
typedef vector <vi> vvi;

class blanch{
	public:
		int weight;
		int total;
		int from;
		int to;
		blanch():
			weight(0), from(0), to(0){};
		blanch(int newweight, int newfrom, int newto):
			weight(newweight), from(newfrom), to(newto){};
};
typedef vector <blanch> vb;


bool operator<( const blanch &blanch1, const blanch &blanch2){
	return (blanch1.weight > blanch2.weight);
	}

bool operator>( const blanch &blanch1, const blanch &blanch2){
	return (blanch1.weight < blanch2.weight);
	}

int make_graph(vvi &graph, vi &stamp){
	int n=graph.size();
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			graph[i][j]=0;
		}
	}

	for (int j=0; j<n; j++){
		int i2,n2;
		cin>>i2;
		cin>>n2;
		for (int i=0; i<n2; i++){
			int j2;
			cin>>j2;
			cin>>graph[i2][j2];
		}
		stamp[i2] = -1;
	}
	return 0;
}

int Shortest_Path(vvi &graph, vi &stamp){

	priority_queue<blanch, vb, less<vb::value_type> > pq;
	int n = graph.size(), p1=0;
	stamp[p1] = 0;

	while (p1!=-1){
		for (int p2=0; p2<n; p2++){
			int *tmp = &graph[p1][p2];
			if (*tmp!=0 && stamp[p2]==-1){
				pq.push(blanch(*tmp+stamp[p1], p1, p2));
			}
		}
		p1 = -1;
		while (! pq.empty()){
			blanch tmp = pq.top();
			if (stamp[tmp.from]!=-1 && stamp[tmp.to]==-1){
				p1 = tmp.to;
				stamp[p1] = tmp.weight;
				pq.pop();
				break;
			} else
				pq.pop();
		}
	}
	return 0;
}

int resultout(vi &stamp){
	int n = stamp.size();
	for (int i=0; i<n; i++){
		cout<<i<<" "<<stamp[i]<<endl;
	}
	return 0;
}

int main(void){

	int n;
	cin>>n;
	vvi G(n, vi(n));
	vi stamp(n);

	make_graph(G, stamp);

	Shortest_Path(G, stamp);

	resultout(stamp);

	return 0;
} 

Measured memory_bytes: 1344
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 100010;
vector<int> adj[N];
int n, tk, ao, dt[N], da[N], vis[N];

void dfs1 (int u, int d) {
	dt[u] = d;
	for (int v : adj[u]) if (dt[v] == -1)
		dfs1(v, d + 1);
}

void dfs2 (int u, int d) {
	da[u] = d;
	for (int v : adj[u]) if (da[v] == -1)
		dfs2(v, d + 1);
}

int main() {
	int u, v;
	scanf("%d", &n);
	scanf("%d%d", &tk, &ao);
	for (int i = 0; i < n - 1; i++) {
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(dt, -1, sizeof dt);
	memset(da, -1, sizeof da);
	dfs1(tk, 0);
	dfs2(ao, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++) fprintf(stderr, "%d, %d\n", da[i], dt[i]);
	for (int i = 1; i <= n; i++) if (da[i] > dt[i]) {
		ans = max(ans, da[i] - 1);
	}
	printf("%d\n", ans);
}



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

using namespace std;

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);
  int n;
  cin >> n;
  vector <int64_t> a;
  for (auto i = 0; i < n; ++ i)
  {
    int64_t x;
    cin >> x;
    a.emplace_back (x);
  }
  vector <int64_t> ans (n);
  ans [0] = 0;
  for (auto i = 0; i < n; ++ i)
  {
    if (i % 2 == 0)
    {
      ans [0] += a [i];
    }
    else
    {
      ans [0] -= a [i];
    }
  }
  ans [0] /= 2;
  for (auto i = 1; i < n; ++ i)
  {
    ans [i] = a [i - 1] - ans [i - 1];
  }
  for (auto && elem : ans)
  {
    elem *= 2;
  }
  copy (ans.begin (), ans.end (), ostream_iterator <int64_t> (cout, " "));
  cout << endl;
}


Measured memory_bytes: 3060