akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
using ull = unsigned long long;

int main(){
    unsigned N, mx = 0, tmp;
    ull answer = 0;
    scanf("%u", &N);
    for (unsigned i = 0; i < N; i++){
        scanf("%u", &tmp);
        if(tmp > mx) mx = tmp;
        else answer += mx - tmp;
    }
    printf("%llu\n", answer);
	return 0;
}

Measured memory_bytes: 1696
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int H,N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];

    vector<int> dp(H+1, INF);
    dp[0] = 0;

    REP(i, H){
        REP(j, N){
            if(i+A[j] >= H){
                chmin(dp[H], dp[i]+B[j]);
            }else{
                chmin(dp[i+A[j]], dp[i]+B[j]);
            }
        }
    }

    pr(dp[H]);
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
	int a;
	long long sum = 0;
	cin >> a;
	for (int i = 1; i <= a; i++) {
		if (i % 3 == 0 || i % 5 == 0) {
			continue;
		}
		else {
			sum += i;
		}
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
string ac="AC",wa="WA";
int main()
{
  string S;
  cin>>S;
  bool flag=true;
  int c=0;
  if(S[0]!='A') flag=false;
  if(flag){
    for(int i=2;i<S.size()-1;i++){
      if(S[i]=='C') {
        c=i; 
        break;
      }
    }
    if(c==0) flag=false;
  }
  if(flag){
    S.erase(S.begin()+c);
    S.erase(S.begin());
    
    for(int i=0;i<S.size();i++){
      if(!(bool)islower(S[i])) {
        flag=false;
        break;
      }
    }
  }
  
  cout<<( (flag)? ac:wa );
}

  

Measured memory_bytes: 256
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#include <math.h>
#include <numeric>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int main()
{
string s;
cin>>s;
ll n=s.size();
ll i;
string p="";
for(i=0;i<n;i++)
{
	if(s[i]=='0')
	p=p+'0';
	else if(s[i]=='1')
	p=p+'1';
	else if(p.size()>0)
	p.erase(p.end()-1,p.end());
}
cout<<p;
return 0;
}

Measured memory_bytes: 256
#これ計算量一次やけどACにならんかった

n,q = map(int, input().split())
point_array = [list(map(int,input().split())) for i in range(n-1)]
action_array = [list(map(int,input().split())) for i in range(q)]

point_array.sort()
solution = [0]*n

for i in range(q):
    solution[action_array[i][0]-1] += action_array[i][1]

for i in range(n-1):
    solution[point_array[i][1]-1] += solution[point_array[i][0]-1]
    
print(*solution)

Measured memory_bytes: 113536
A = int(input())
B = int(input())
C = int(input())
X = int(input())
a = X // 500
b = (X - 500*a) // 100
c = (X - 500*a - 100*b) //50 

count = 0
i = a 
while i >= 0:
  j = b
  k = c
  while j >= 0:
    if i <= A and j <= B and k <= C:
      count += 1 
    j -= 1
    k += 2
  i -= 1
  b += 5
  
print(count)

Measured memory_bytes: 9140
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;


__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}



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

	ll N, K;
	
	cin >> N >> K;

	ll a[N];
	ll sum[41];
	ll d[41];

	ll k = K;
	memset(sum, 0, sizeof(sum));
	memset(d, 0, sizeof(d));

	/*
	int cnt = 0;

	while(k)
	{
		d[cnt++] = k & 1;
		k >>= 1;
	}
	*/
	rep(i, N)
	{
		cin >> a[i];

		rep(j, 40)
		{
			sum[j] += (1 & (a[i] >> j));
		}
	}
	
	/*
	ll f[41][2];
	memset(f, 0, sizeof(f));
	f[40][1] = 0;

	for(int i = 39; i >= 0; i--)
	{
		
		if (d[i])
		{
			// when i-1 bit is 0 
			f[i][0] = f[i+1][0] + (max(sum[i], (N-sum[i])) << (i));
			f[i][0] = max(f[i][0], f[i+1][1] + ((N-sum[i]) << (i)));
		}
		
		f[i][1] = f[i+1][1] + ((d[i]? N-sum[i]: sum[i]) << i);
		
	}

	cout << max(f[0][1], f[0][0]) << endl;
	*/
	ll x = 0;
	for(int i = 40; i >= 0 ; i--)
	{
		int tmp = (sum[i] > N-sum[i]) ? 0 : 1;
		if (tmp)
		{
			ll t = (1ll << i) | x;
			if (t <= K)
			{
				x = t;
			}
		}
	}
	
	ll total = 0;

	rep(i, N)
	{
		total += (x ^ a[i]);
	}

	cout << total << endl;
	return 0;
}


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

using namespace std;

int main(void){
    int M, N;
    cin >> N >> M;

    int sum = 0;
    for(int i = 0; i < M; i++){
        int tmp;
        cin >> tmp;
        sum += tmp;
    }

    if(sum <= N){
        cout << N - sum << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3620
s = []

while True:
     n = int(input())
     num = []

     if n == 0:
          break
     else:
          while True:
               if n == 0:
                    break
               else:
                    num.append(n % 10)
                    n = n // 10

          s.append(sum(num))

c = len(s)

for i in range(c):
     print(s[i])


Measured memory_bytes: 5612
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int n, k;
bool dp[2002][10001];
bool good[2002][10001];
string s[2002];

vector <int> which;
vector <int> pos;

vector <int> next_which;
vector <int> next_pos;


char getBest()
{
	char ret = 'z';
	for(int i = 0; i < which.size(); i++)
	{
		ret = min(ret, s[which[i]][pos[i]]);
	}
	return ret;
}

void updateNext(char c, int remain)
{
	next_which.clear();
	next_pos.clear();
	int firstFinish = n+1;
	int rate = which.size() / 4000;
	for(int i = 0; i < which.size(); i += (rate + 1))
		if(s[which[i]][pos[i]] == c)
		{
			if(pos[i] == s[which[i]].length()-1)
				firstFinish = min(firstFinish, which[i]);
			else
			{
				next_which.push_back(which[i]);
				next_pos.push_back(pos[i]+1);
			}
		}
	for(int i = firstFinish + 1; i <= n; i++)
		if(good[i][remain])
		{
			next_which.push_back(i);
			next_pos.push_back(0);
		}
	which = next_which;
	pos = next_pos;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> s[i];
	memset(dp, 0, sizeof(dp));
	dp[n+1][0] = true;
	for(int i = n; i >= 1; i--)
		for(int j = 0; j <= k; j++)
		{
			if(dp[i+1][j] == true)
				dp[i][j] = true;
			if(j - (int)s[i].length() >= 0 && dp[i+1][j-(int)s[i].length()])
				dp[i][j] = true;
		}
	memset(good, false, sizeof(good));
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= k; j++)
			if(s[i].length() <= j && dp[i+1][j - (int)s[i].length()])
				good[i][j] = true;

	int remain = k;
	for(int i = 1; i <= n; i++)
		if(good[i][remain])
		{
			which.push_back(i);
			pos.push_back(0);
		}
	string ret;
	for(int i = 1; i <= k; i++)
	{
		char c = getBest();
		remain --;
		updateNext(c, remain);
		ret += c;
	}
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 40704
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

    for i in A:
        C[i] += 1

    for i in range(1, 10001):
        C[i] = C[i] + C[i - 1]

    B = [0 for i in range(n + 1)]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))

countingSort(A, n)

Measured memory_bytes: 233676
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 string c;
 cin >> c;
 if(c.at(0) == 'a' || c.at(0) == 'i' || c.at(0) == 'u' || c.at(0) == 'e' || c.at(0) == 'o'){
   cout << "vowel" << endl;
 }
 else{
   cout << "consonant" << endl;
 }
 
}
  

Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

const int MAX_N=100000;
int h[MAX_N+1];
int dp[MAX_N+1];
int n;

void solve(){
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    FOR(i,2,n){
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout << dp[n-1] << endl;
}

int main(void){
    cin >> n;
    REP(i,n)
        cin >> h[i];
    solve();
    return 0;
}

Measured memory_bytes: 4348
def solve(s):
    if int(s) > N:
        return 0

    ret = 0
    if all(s.count(c) >= 1 for c in '753'):
        ret = 1
    for c in '753':
        ret += solve(s + c)
    return ret

if __name__ == "__main__":
    N = int(input())
    print(solve('0'))

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

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

Measured memory_bytes: 256
import sys
from operator import itemgetter, attrgetter
from itertools import starmap
import cmath
from math import isinf, sqrt, acos, atan2
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Circle(object):
    __slots__ = ('c', 'r')
    def __init__(self, c, r):
        self.c = c
        self.r = r
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
Line = Segment
def cross(a, b):
    return a.real * b.imag - a.imag * b.real
def dot(a, b):
    return a.real * b.real + a.imag * b.imag
def norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(p1, p2, p3, p4):
    return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and
			ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)
def intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
def getCrossPoint(s1, s2):
	base = s2.se - s2.fi
	d1 = abs(cross(base, s1.fi - s2.fi))
	d2 = abs(cross(base, s1.se - s2.fi))
	t = d1 / (d1 + d2)
	return s1.fi + (s1.se - s1.fi) * t
def getCrossPointsCL(c, l):
    pr = project(l, c.c)
    e = (l.se - l.fi) / abs(l.se - l.fi)
    base = sqrt(c.r * c.r - norm(pr - c.c))
    return Segment(*sorted((pr + e * base, pr - e * base)), key=attrgetter('real', 'imag'))
def getCrossPointsCC(c1, c2):
    d = abs(c1.c - c2.c)
    a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2.0 * c1.r * d))
    t = cmath.phase(c2.c - c1.c)
    return Segment(*sorted((c1.c + cmath.rect(c1.r, t + a), c1.c + cmath.rect(c1.r, t - a)), key=attrgetter('real', 'imag')))
def contains(g, p):
    n = len(g)
    x = False
    for i in range(n):
        a = g[i] - p
        b = g[(i + 1) % n] - p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS: return 1
        if a.imag > b.imag: a, b = b, a
        if a.imag < EPS and EPS < b.imag and cross(a, b) > EPS: x = not x
    return 2 if x else 0
n = int(readline())
pg = tuple(complex(*map(int, readline().split())) for _ in [0] * n)
q = int(readline())
for _ in [0] * q:
    print(contains(pg, complex(*map(int, readline().split()))))

Measured memory_bytes: 8260
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int bubble_sort (vector<int> & a )
{
	int n = a.size();
	int res = 0;
	rep (i, n ){
		for (int j = n-1; j >= i + 1; j-- ){
			if (a[j] < a[j-1] ){
				swap (a[j], a[j-1] );
				res++;
			} // end if
		} // end for
	} // end rep

	return res;
}

int main()
{
	int n;
	scanf ("%d", &n );
	vector<int> a (n, 0 );
	rep (i, n ) scanf ("%d", &a[i] );
	int cnt = bubble_sort (a );
	rep (i, n ){
		printf ("%d", a[i] );
		i != n - 1 ? printf (" " ) : printf ("\n" );
	} // end rep
	printf ("%d\n", cnt );
	
	return 0;
}

Measured memory_bytes: 1192
s = input()
q = int(input())
 
right = []
left = []
 
reverse = 0
 
r = 2
for _ in range(q):
    Q = list(input().split())
    if int(Q[0]) == 1:
        if r == 2:
            r = 1
        else:
            r = 2
        reverse += 1
    else:
        if r == 2:
            if int(Q[1]) == 2:
                right.append(Q[2])
            else:
                left.append(Q[2])
        else:
            if int(Q[1]) == 2:
                left.append(Q[2])
            else:
                right.append(Q[2])
                
                
if reverse%2 == 0:
    print(''.join(left[::-1]) + s + ''.join(right))
else:
    print(''.join(right[::-1]) + s[::-1] + ''.join(left))

Measured memory_bytes: 6272
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
 
def input():
    return sys.stdin.readline().strip()
 
# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]
 
# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]
 
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())
 
def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
INF = 999999999999999999999999
MOD = 10**9+7
 
n,*A = get_all_int()
 
if min(A) == 0:
    print(0)
    exit()
 
ans = 1
for a in A:
    ans *= a
 
    if ans > 10**18:
        print(-1)
        exit()
 
print(ans)

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

class BigInt {
public:
	BigInt() {}

	BigInt(long long n) {
		a[0] = n;
		normalize();
	}

	BigInt &operator+=(const BigInt &r) {
		for (int i = 0; i < N; i++) {
			a[i] += r.a[i];
		}
		normalize();
		return *this;
	}

	BigInt operator+(BigInt r) {
		return r += *this;
	}

	BigInt &operator*=(const BigInt &r) {
		for (int i = N - 1; i >= 0; i--) {
			long long s = 0;
			for (int j = 0; j <= i; j++) {
				s += a[j] * r.a[i - j];
			}
			a[i] = s;
		}
		normalize();
		return *this;
	}

	BigInt operator*(BigInt r) {
		return r *= *this;
	}

	bool operator<(const BigInt &r) const {
		for (int i = N - 1; i >= 0; i--) {
			if (a[i] != r.a[i]) {
				return a[i] < r.a[i];
			}
		}
		return false;
	}

	bool operator<=(const BigInt &r) const {
		for (int i = N - 1; i >= 0; i--) {
			if (a[i] != r.a[i]) {
				return a[i] < r.a[i];
			}
		}
		return true;
	}

	bool operator==(const BigInt &r) const {
		for (int i = 0; i < N; i++) {
			if (a[i] != r.a[i]) return false;
		}
		return true;
	}

	bool operator>(const BigInt &r) const {
		return !(*this <= r);
	}

	bool operator>=(const BigInt &r) const {
		return !(*this < r);
	}

	string to_string() const {
		int i = N - 1;
		while (i > 0 && a[i] == 0) i--;
		string s = std::to_string(a[i--]);
		for (; i >= 0; i--) {
			string t = std::to_string(a[i]);
			s += string(L - t.length(), '0') + t;
		}
		return s;
	}

private:
	static const int N = 3;
	static const int L = 8;
	static const long long B = 100000000;
	long long a[N] = {};

	void normalize() {
		long long carry = 0;
		for (int i = 0; i < N; i++) {
			a[i] += carry;
			carry = a[i] / B;
			a[i] %= B;
		}
	}
};

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

	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
	}

	vector<bool> is_prime(101010, true);
	vector<long long> ps;
	map<long long, long long> rt;

	for (long long i = 2; i < 101010; i++) {
		if (is_prime[i]) {
			ps.push_back(i);
			rt[i * i] = i;
			for (int j = i * 2; j < 101010; j += i) {
				is_prime[j] = false;
			}
		}
	}

	map<BigInt, BigInt> inv;
	map<BigInt, int> cnt;

	for (int i = 0; i < n; i++) {
		BigInt p = 1, q = 1;
		for (int j = 0; ps[j] <= 2500; j++) {
			int c = 0;
			while (a[i] % ps[j] == 0) a[i] /= ps[j], c++;
			c %= 3;
			if (c > 0) {
				for (int i = 0; i < c; i++) p *= ps[j];
				for (int i = 0; i < 3 - c; i++) q *= ps[j];
			}
		}
		p *= a[i];
		if (a[i] != 1) {
			if (rt.count(a[i])) {
				q *= rt[a[i]];
			} else {
				q *= a[i];
				q *= a[i];
			}
		}
		inv[p] = q;
		inv[q] = p;
		cnt[p]++;
	}

	int ans = 0;
	for (auto &kv : inv) {
		auto &x = kv.first;
		auto &y = kv.second;

		if (x == y) {
			ans++;
		} else if (x < y) {
			ans += max(cnt[x], cnt[y]);
		}
	}
	cout << ans << endl;
}

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


typedef long long ll;
typedef unsigned long long ull;


const int maxn = 1e5+1;
ll w[maxn], d[maxn];
ll n, k;
inline bool valid(ull mid)
{
  ull tot = 0;
  for (int i = 1; i <= n; ++i)
    if (mid>=w[i])
    {
      tot += (mid-w[i])/d[i]+1;
      if (tot >= k)
	return true;
    }
  return false;
}

int main()
{
  scanf("%lld %lld", &n, &k);
  for (int i = 1; i <= n; ++i)
    scanf("%lld %lld", w+i, d+i);
  ull l = 1, r = 2e18, mid, ans;
  while (l <= r)
    {
      mid = (l+r)>>1;
      if (valid(mid))
	{
	  ans = mid;
	  r = mid-1;
	}
      else
	l = mid+1;
    }
  printf("%llu\n", ans);
}


Measured memory_bytes: 1792
import java.util.*;

public class Main
{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			String string = sc.nextLine();
			
			string = string.replaceAll("apple", "dammy1");
			string = string.replaceAll("peach", "dammy2");
			string = string.replaceAll("dammy1", "peach");
			string = string.replaceAll("dammy2", "apple");
			
			System.out.println(string);
		}
	}
}

Measured memory_bytes: 17280
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n = int(input())
    l = []
    for i in range(n):
        s = sorted(input())
        l.append(''.join(s))
    l_cnt = Counter(l)
    ans = 0
    for i in l_cnt.values():
        ans += i*(i-1) // 2
    print(ans)


    print()
if __name__ == '__main__':
    main()

Measured memory_bytes: 19812
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B;
  cin >> A >>B;
  
  if(B == 1){
    cout << 0;
    return 0;
  }
  
  int add = A -1;
  int ans = 1;
  while(B > A){
    ans++;
    A += add;
  }
  cout << ans;
  return 0;
}


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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;

ll const MOD = 1e6 + 3;

ll fact[MOD];

ll exp(ll a, ll b){
    if(b==1) return a;
    if(b&1) return (a*exp(a,b-1))%MOD;
    return exp(a*a%MOD,b/2)%MOD;
}

ll inv(ll x){
    return exp(x,MOD-2);
}

int main(){
    fact[0] = 1;
    for(int i=1;i<MOD;++i) fact[i] = i*fact[i-1]%MOD;
    int q;
    cin >> q;
    while(q--){
        ll x,d,n;
        cin >> x >> d >> n;
        ll ans;
        if(x==0) ans = 0;
        else if(d==0) ans = exp(x,n);
        else{
            x = (x*inv(d))%MOD;
            if(x+n-1LL >= MOD) ans = 0;
            else{
                ans = (fact[x+n-1])*(inv(fact[x-1]))%MOD;
                ans = ans*exp(d,n)%MOD;
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 8704
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n, sx, sy, gx, gy;
double d[110000]; // 結果
struct edge { ll to; double cost; };
vector<edge> g[110000]; //隣接リスト to, cost
void dijkstra(ll a) {
	priority_queue<P, vector<P>, greater<P> > q;
	fill(d, d + n + 2, INF);
	d[a] = 0;
	q.push(P(0, a));
	while (!q.empty()) {
		P p = q.top();
		q.pop();
		ll v = p.second;
		if (d[v] < p.first) continue;
		REP(i, g[v].size()) {
			edge e = g[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				q.push(P(d[e.to], e.to));
			}
		}
	}
}

double dist(ll a, ll b, ll c, ll d, ll e, ll f) {
	ll na = abs(a - c), nb = abs(b - d);
	double res = sqrt((double)na * na + nb * nb) - e - f;
	return max((double)0, res);
}
// 0,1~n,n+1
ll x[1100], y[1100], r[1100];
int main() {
	cin >> sx >> sy >> gx >> gy >> n;
	REP(i, n) cin >> x[i] >> y[i] >> r[i];
	REP(i, n) {
		g[0].push_back({ i + 1, dist(sx, sy, x[i], y[i], 0, r[i]) });
		g[i + 1].push_back({ 0, dist(sx, sy, x[i], y[i], 0, r[i]) });
		g[n + 1].push_back({ i + 1, dist(gx, gy, x[i], y[i], 0, r[i]) });
		g[i + 1].push_back({ n + 1, dist(gx, gy, x[i], y[i], 0, r[i]) });
	}
	REP(i, n) {
		REP(j, n) {
			if (i != j) {
				g[i + 1].push_back({ j + 1, dist(x[i], y[i], x[j], y[j], r[i], r[j]) });
				g[j + 1].push_back({ i + 1, dist(x[i], y[i], x[j], y[j], r[i], r[j]) });
			}
		}
	}
	g[0].push_back({ n + 1, dist(sx, sy, gx, gy, 0, 0) });
	g[n + 1].push_back({ 0, dist(sx, sy, gx, gy, 0, 0) });
	dijkstra(0);
	cout << fixed << setprecision(20) << d[n + 1] << endl;
}


Measured memory_bytes: 41328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; cin >> n;
    int d[n+1][2];
    for(int i=0; i<n; ++i){
        for(int j=0; j<2; ++j){cin >> d[i][j];}
    }
  
    int cnt = 0;
    for(int i=0; i<n; ++i){
        if(d[i][0]==d[i][1]){cnt++;}
        else{cnt = 0;}
        if(cnt==3){cout << "Yes" << endl; return 0;}
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
 
using namespace std;
 
#define INF 1 << 29
#define LL long long int
 
LL const MOD = 1000000007;
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    LL n;
    cin >> n;
    vector<LL> a(n);
    for(auto &x:a){
        cin >> x;
    }
 
    LL absmax = -1;
    LL idx = 0;
    bool pos = true;
    for(int i = 0; i < n; i++){
        if(absmax < abs(a[i])){
            idx = i;
            absmax = abs(a[i]);
            pos = a[i] >= 0;
        }
    }
 
    vector<pair<LL,LL>> ans;
 
    if(pos){
        for(int i = 0; i < n; i++){
            if(a[i] < 0){
                a[i] += absmax;
                ans.push_back(make_pair(idx+1,i+1));
            }
        }
        for(int i = 1; i < n; i++){
            ans.push_back(make_pair(i,i+1));
        }
    }else{
        for(int i = 0; i < n; i++){
            if(a[i] > 0){
                a[i] -= absmax;
                ans.push_back(make_pair(idx+1,i+1));
            }
        }
        for(int i = n; i > 1; i--){
            ans.push_back(make_pair(i,i-1));
        }
    }
 
    cout << ans.size() << endl;
    for(auto x: ans){
        cout << x.first << " ";
        cout << x.second << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
A,B,K = (int(x) for x in input().split())
i = 1
n = 0
NUM = [0]*min(A,B)

for i in range(1,min(A,B)+1):
    if A%i ==0 and B%i ==0:
        NUM[n] = i
        n+=1
NUM.sort(reverse = 1)

print(NUM[K-1])

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

int main() {
    int N,f=0,b=0;
    string S;
    cin >> N >> S;

    rep(i,N) {
        char c = S.at(i);
        if(c == '(') {
            f++;
        } else {
            if(f > 0)
                f--;
            else
                b++; 
        }
    }

    rep(i,b)
        cout << '(';
    cout << S;
    rep(i,f)
        cout << ')';
    cout << endl;
}

Measured memory_bytes: 256
L, R = map(int, input().split())
if R - L >= 2019:
  ans = 0
elif L % 2019 > R % 2019:
  ans = 0
else:
  ans = 2019
  for i in range(L % 2019, R % 2019):
    for j in range(i + 1, R % 2019 + 1):
      ans = min(ans, (i * j) % 2019)
      if ans == 0:
        break
    if ans == 0:
       break
print(ans)

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

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

int match[510];
bool used[510];
vector<int> g[510];

int gcd(int x, int y)
{
    return y != 0 ? gcd(y, x % y) : x;
}

bool dfs(int v)
{
    for(int i = 0; i < g[v].size(); ++i)
    {
        int t = g[v][i];
        if(used[t]) continue;
        used[t] = true;
        if(match[t] == -1 || dfs(match[t])) {
            match[t] = v;
            return true;
        }
    }
    return false;
}

int main()
{
    int m, n, blue[510], red;
    while(cin >> m >> n && m)
    {
        rep(i, m)
            cin >> blue[i], g[i].clear();
        rep(i, n) {
            cin >> red;
            for(int j = 0; j < m; ++j)
                if(gcd(blue[j], red) > 1)
                    g[j].push_back(i);
        }
    	int res = 0;
        fill_n(match, n, -1);
        rep(i, m) {
            fill_n(used, n, false);
            if(dfs(i)) ++res;
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 1984
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstdio>
#include <queue>
using namespace std;

class Doublylist{
public:
  Doublylist(int size) : 
  front(0), back(0){
    allocate_array = new int[size];
  }
  ~Doublylist(){
    delete[] allocate_array;
  }
  void delite(int val);
  void print();
  void insert(int val){
    allocate_array[front++] = val;
  }
  void delite_first(){
    front--;
  }
  void delite_last(){
    back++;
  }

private:
  int front, back;
  int *allocate_array;
};

void Doublylist::delite(int val){
  for(int i=front-1;i>=back;i--){
    if(val == allocate_array[i]){
      for(int j=i;j<front;j++){
        allocate_array[j] = allocate_array[j+1];
      }
      front--;
      return;
    }
  }
}

void Doublylist::print(){
  for(int i=front-1;i>=back;i--){
    cout << allocate_array[i];
    if(i == back) cout << "\n";
    else cout << " ";
  }
}

int main(void){
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  Doublylist li(n);
  for(int i=0;i<n;i++){
    string str;
    int val;
    cin >> str;

    if(str == "insert"){
      cin >> val;
      li.insert(val);
    }else if(str == "delete"){
      cin >> val;
      li.delite(val);
    }else if(str == "deleteFirst"){
      li.delite_first();
    }else if(str == "deleteLast"){
      li.delite_last();
    }
  }

  li.print();
  return 0;
}

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

main() {
  int N, a, b, c, d;
  cin >> N;
  a = N%10;
  N -= a;
  b = (N%100)/10;
  N -= b*10;
  c = (N%1000)/100;
  N -= c*100;
  d = N/1000;
  if (a == b && a == c){
    cout << "Yes" << endl;
  }
  else if(b == c && b == d){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


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

int main(){
  int n , i , j, s , c = 0,f = 1;
  scanf("%d",  &n);
  for ( i = 0; i < n ;i++ ){
    scanf("%d", &s);
    f = 1;
    /*
    for ( j = 2 ; j < s; j++){
      if ( s % j  == 0) {f = 0 ;break;}
    }
    if ( f == 1 ){c++;}
    f = 1;
  }
    */

    /*

if x == 2
    return true

  if x < 2 または x が偶数
    return false

  i = 3
  while i <= x の平方根
    if x が i で割り切れる
      return false
    i = i + 2

 return true

    */

    if ( s == 2){  c++; continue;}
    else{
      if ( s < 2 || s%2 == 0){ continue;}
      else{
	j =3;
	while ( j <= sqrt(s)){
	  if ( s%j == 0){ f = 0;break;}
	  j += 2;
	}
	if ( f == 0){ continue;}
	else if ( f == 1){ c++;continue;}
      }
    }
  }
  printf("%d\n", c);
  
  return 0;
  
}


Measured memory_bytes: 2144
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int main(){
int n;
cin>>n;
vector <int>v(n);
for(int i=0;i<n;i++)
    cin>>v[i];
//vector <int >m(n,-1);
vector <int >f(n,-1);
f[0]=0,f[1]=abs(v[1]-v[0]);
if(n>2)
{
    for(int i=2;i<n;i++)
    {
        if(f[i]!=-1)
            return f[i];
        f[i]=min(abs(v[i]-v[i-2])+f[i-2],f[i-1]+abs(v[i]-v[i-1]));

    }
    cout<< f[n-1];
}
else
{
    cout<< f[n-1];
}
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int main()
{
	for(int h,w;cin>>h>>w;){
		vvi grid(h,vi(w));
		rep(i,h) rep(j,w) cin>>grid[i][j];
		
		vvi hgrid(h,vi(w+1)),vgrid(h+1,vi(w));
		rep(i,h) rep(j,w) if(!grid[i][j]){
			hgrid[i][0]++; hgrid[i][w]--;
			hgrid[i][j]--; hgrid[i][j+1]++;
			vgrid[0][j]++; vgrid[h][j]--;
		}
		rep(i,h) rep(j,w){
			hgrid[i][j+1]+=hgrid[i][j];
			vgrid[i+1][j]+=vgrid[i][j];
		}
		
		vvi res(h,vi(w));
		rep(i,h) rep(j,w)
			res[i][j]=hgrid[i][j]+vgrid[i][j]&1;
		
		rep(i,h) rep(j,w)
			cout<<res[i][j]<<(j==w-1?'\n':' ');
	}
	
	return 0;
}

Measured memory_bytes: 16844
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;

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


int main(){
    int N;
    cin >> N;
    int x[110];

    int NN = N;
    if(N % 2 == 1){
        N--;
    }

    for(int i = 1; i <= N; i++){
        x[i] = N-i+1;
    }

    vector<P> e;
    for(int i = 1; i <= N; i++){
        for(int j = i+1; j <= N; j++){
            if(x[i] != j){
                e.emplace_back(P(i, j));
            }
        }
    }

    if(NN > N){
        for(int i = 1; i <= N; i++){
            e.emplace_back(P(i, NN));
        }
    }

    cout << e.size() << endl;
    for(auto ee: e){
        cout << ee.fs << " " << ee.sc << endl;
    }


    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  vector<int> T(N);
  for(int i=0;i<N;i++){
	cin >> T.at(i);
  }
  
  int M;
  cin >> M;
  vector<int> P(M);
  vector<int> X(M);
  for(int k=0;k<M;k++){
  cin >> P.at(k) >> X.at(k);
  }
  
  for(int j=0;j<M;j++){
    int sum = 0;
    for(int h=0;h<N;h++){
      if((P.at(j)-1) == h){
        sum += X.at(j);
      }else{
        sum += T.at(h);
      }
    }
    cout << sum <<endl;
    
  }

}


Measured memory_bytes: 256
#include<iostream>

using namespace std;


static const int MAX = 100;
static const int inf = (1 << 21);
static const int white = 0;
static const int gray = 1;
static const int black = 2;

int n, m[MAX][MAX];
int sht[MAX];


void dijkstra() {

	int u, minv;
	int d[MAX], p[MAX], color[MAX];

	for (int i = 0; i < n; i++)
	{
		sht[i] = d[i] = inf;
		p[i] = -1;
		color[i] = white;
	}

	d[0] = 0;
	color[0] = gray;

	while (1)
	{
		minv = inf;
		u = -1;

		for (int i = 0; i < n; i++) {
			if (minv > d[i] && color[i] != black) {
				u = i;
				minv = d[i];
			}
		}

		if (u == -1) break;
		color[u] = black;

		for (int v = 0; v < n; v++) {
			if (color[v] != black && m[u][v] != inf) {
				if (d[v] > d[u] + m[u][v]) {
					d[v] = d[u] + m[u][v];
					color[v] = gray;
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		cout << i << " " << (d[i] == inf ? -1 : d[i]) << endl;

	}
}


int main() {


	cin >> n;

	for (int i = 0;i < n;i++) {
		for (int k = 0; k < n; k++)
		{
			m[i][k] = inf;
		}
	}

	int nm, c, u, v;
	for (int i = 0;i < n;i++) {
		cin >> u >> nm;
		for (int k = 0; k < nm; k++)
		{
			cin >> v >> c;
			m[u][v] = c;
		}
	}

	dijkstra();

	return 0;
}



Measured memory_bytes: 3144
from heapq import heappush, heappop
def solve():
    N = int(input())
    *A, = map(int, input().split())
    M = 2*10**5
    INF = 10**18
    dist = [[INF]*(M+1) for i in range(N+1)]
    que = [(0, 0, 1)]
    while que:
        cost, i, p = heappop(que)
        if i == N:
            break
        if dist[i][p] + 1e-10 < cost:
            continue
        a = A[i]
        for k in range(p, M+1, p):
            d = max(cost, abs(k - a)/a)
            if d < dist[i+1][k]:
                dist[i+1][k] = d
                heappush(que, (d, i+1, k))
    return min(dist[N])
print("%.16f" % solve())


Measured memory_bytes: 121180
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> ans(n);
  for(int i=0;i<n;i++) cin >> a[i];

  for(int i=0;i<n;i++) ans[a[i]-1]=i+1;
  for(int i=0;i<n;i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}


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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000000
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
  int n;
  cin >> n;
  int freq[2][100010] = { };
  REP(i, n){
    int v;
    cin >> v;
    freq[i%2][v]++;
  }
  int umax = 0, umaxi = -1, dmax = 0, dmaxi = -1;
  REP(i, 100010){
    if(freq[0][i] > umax){
      umax = freq[0][i];
      umaxi = i;
    }
    if(freq[1][i] > dmax){
      dmax = freq[1][i];
      dmaxi = i;
    }
  }
  if(umaxi != dmaxi){
    cout << n - umax - dmax << endl;
  }
  else{
    sort(freq[0], freq[0] + 100010);
    sort(freq[1], freq[1] + 100010);
    int d = max(umax + freq[1][100008], dmax + freq[0][100008]);
    cout << n-d << endl;
  }
	return 0;
}

Measured memory_bytes: 1024
void main()
{
    int n = readln.chomp.to!int;
    int[] a = readln.split.to!(int[]);

    int[] odd = new int[n];
    foreach (i, x; a)
    {
        if (x & 1)
        {
            odd[i] = 1;
        }
        else
        {
            odd[i] = 2;
        }
    }

    writeln(3 ^^ n - odd.reduce!((x, y) => x * y));
}

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: 256
#include <bits/stdc++.h>
using namespace std;



#define rep(i, x)   for (__typeof(x) i = 0; i < x; i++)
#define mp             make_pair
#define pb             push_back
#define fi             first
#define se             second
#define sz(x)          (int)((x).size())
#define all(x)         (x).begin(), (x).end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define eprintf(...)   fprintf(stderr, __VA_ARGS__)
#define debug(x)       if(DEBUG){ cerr << #x << " = " << x << endl; }
#define repi(i, x)  for (__typeof(x) i = x-1; i >= 0; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;
typedef vector<vector<int>> vvi;
typedef vector<ll>     vl;
typedef vector<vector<ll>> vll;
const   int            infi = numeric_limits<int>::max();
const ll               infl = numeric_limits<ll>::max();

const   double         eps = 0;
const   int            ms  = 0;
const bool DEBUG = 0;


vl S;
ll sum(int i) {
    return S[i];
}
ll sum(int l, int r){
    ll L;
    if(l==0)return S[r];
    return S[r] - S[l-1];
}


int nib(int l, int r){
    int ok = r;
    int ng = l-1;
    ll s = sum(l, r+1);
    while (abs(ok - ng) > 1){
        int mid = (ok + ng)/ 2;
        ll sum1 = sum(l, mid);
        ll sum2 = s - sum1;
        if(sum1 >= sum2){
            ok = mid;
        }
        else{
            ng = mid;
        }
        debug(ok);debug(ng);debug(mid);
    }
    
    ll sum1 = sum(l, ok);
    ll sum2 = s - sum1;
    ll a = abs(sum1-sum2);
    debug(sum1);debug(sum2);
    if(ok!=l){
        ll ta = abs(sum(ok, r+1) - sum(l, ok-1));
        if(ta < a){
           ok--;
        }
    }
    debug(sum1);debug(sum2);

    return ok;
}

int main(){
    int N;
    cin >> N;
    vi A(N);
    rep(i , N)cin >> A[i];
    S = vl(N);
    S[0] = A[0];
    for(int i=1; i < N; i++)S[i] = S[i-1]+A[i];

    ll ans = numeric_limits<ll>::max();
    for(int i=1; i<N-2; i++){
        debug(i);

        int m1 = nib(0, i-1);
        int m2 = nib(i+1, N-2);
        ll sum1 = sum(0, m1), sum2 = sum(m1+1, i);
        ll sum3 = sum(i+1, m2), sum4 = sum(m2+1, N-1);

        debug(m1);debug(m2);
        debug(sum1);debug(sum2);debug(sum3);debug(sum4);
        ll ma = max(sum1, max(sum2, max(sum3, sum4)));
        ll mi = min(sum1, min(sum2, min(sum3, sum4)));
        debug(ma-mi);
        ans = min(ans, ma-mi);
        
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
long long n;
int main()
{
	cin>>n;
	cout<<(n-1)*n/2<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> X(n, vector<int>(d, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < d; j++) {
      cin >> X[i][j];
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      double t = 0;
      for (int k = 0; k < d; k++) {
        t += pow((X[i][k] - X[j][k]), 2);
      }
      for (int k = 0; k * k <= t; k++) {
        if (k * k == t) {
          ans++;
          break;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

int main (void) {

  int N; std::cin >> N;
  std::vector<std::pair<int,int>> p(N);
  for(int i=0; i<N; i++) {
    int x, y; std::cin >> x >> y;
    p[i] = { x, y };
  }

  std::unordered_map<int, std::unordered_map<int,int>> S;
  for(int i=0; i<N; i++) {
    for(int j=i+1; j<N; j++) {
      int xdiff = p[i].first  - p[j].first;
      int ydiff = p[i].second - p[j].second;
      if ( !(S.count(xdiff) != 0 && S[xdiff].count(ydiff) != 0) ) S[xdiff][ydiff] = 1;
    }
  }

  int ans = std::numeric_limits<int>::max();
  for(auto itr = S.begin(); itr != S.end(); ++itr) {
    for(auto itr2 = itr->second.begin(); itr2 != itr->second.end(); ++itr2) {
      int pp = itr->first, qq = itr2->first, vec = 0;
      for(int i=0; i<N; i++) for(int j=0; j<N; j++) if ( p[i].first + pp == p[j].first && p[i].second + qq == p[j].second ) vec++;
      ans = std::min(ans, N-vec);
    }
  }
  if ( N == 1 ) std::cout << 1 << std::endl;
  else std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 384
// ayy
// ' lamo
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld; //CARE
typedef complex<ld> pt;
#define fi first
#define se second
#define pb push_back
const ld eps=1e-8;
const int inf=1e9+99;
const ll linf=1e18+99;
// const int P=1e9+7;
const int P=998244353; // = 119 * 2**23 + 1







const int N=100<<10;
bitset<N> A,B,C,D;
int n,m;
int F[N*4],iF[N*4],pow2[N*4];
int I4,I2;

int powq(int x,int e) {
	if(!e) return 1;
	if(e&1) return int(1LL*x*powq(x,e-1)%P);
	x=powq(x,e>>1);
	return int(1LL*x*x%P);
}
void add(int &x,int y) {
	x+=y;
	if(x>=P) x-=P;
}

void init_math(int n) {
	F[0]=1;
	for(int i=1;i<=n;i++) F[i]=int(1LL*F[i-1]*i%P);
	iF[n]=powq(F[n],P-2);
	for(int i=n;--i>=0;) iF[i]=int(1LL*iF[i+1]*(i+1)%P);

	pow2[0]=1;
	for(int i=1;i<=n;i++) pow2[i]=pow2[i-1]*2%P;

	I4=powq(4,P-2);
	I2=powq(2,P-2);
}

void read(bitset<N> &bs) {
	string s; cin>>s;
	for(int i=0;i<(int)s.size();i++) bs[i]=(s[i]=='1');
}

int CC(int n,int k) {
	assert(0<=k && k<=n);
	assert(n>=0);
	return int(1LL*F[n]*iF[k]%P*iF[n-k]%P);
}
int f1(int n,int a,int b,int ec) {
	// cerr<<"f1("<<n<<","<<a<<","<<b<<","<<ec<<") = "<<(n ? CC(n-1+a+b,a+b) : pow2[ec])<<endl;
	return n ? CC(n-1+a+b,a+b) : pow2[ec];
}



int go() {
	vector<int> L,R,q;

	int a=0,b=0,ec=0;
	int lc=(int)C.count();
	int rc=(int)D.count();

	int tc=0;
	for(int i=0;i<n;i++) if(A[i] && B[i]) ++tc;

	for(int i=0;i<n;i++) {
		if(!A[i] && !B[i]) continue;
		L.pb(f1(lc,a,b,ec));
		// if(A[i] && B[i]) L.back()*=2, L.back()%=P, ++ec;
		L.back() = int(1LL*L.back()*powq(I2,ec)%P);
		if(A[i] && B[i]) ++ec;
		if(A[i]) ++a;
		if(B[i]) ++b;
		q.pb(i);

		if(!lc && L.size()>1u) L.back()=0;
	}

	a=b=ec=0;
	for(int i=n;--i>=0;) {
		if(!A[i] && !B[i]) continue;
		R.pb(f1(rc,a,b,ec));
		// if(A[i] && B[i]) R.back()*=2, R.back()%=P, ++ec;
		R.back() = int(1LL*R.back()*powq(2,tc-ec)%P);
		if(A[i] && B[i]) ++ec;
		if(A[i]) ++a;
		if(B[i]) ++b;

		if(!rc && R.size()>1u) R.back()=0;
	}

	reverse(R.begin(),R.end());

	assert(L.size()==R.size());
	int w=(int)L.size();

	int RS=0;
	int Z=0;
	for(int i=w;--i>=0;) {
		add(RS,R[i]);
		add(Z,int(1LL*RS*L[i]%P));
		// if(A[q[i]] && B[q[i]]) {
		// 	add(Z,int(1LL*RS*L[i]%P));
		// 	// add(Z,int(P-1LL*L[i]*R[i]%P*I4*2%P));
		// 	add(RS,R[i]);
		// }
	}
	// cerr<<"got Z="<<Z<<" via L={";
	// for(int x:L) cerr<<x<<",";
	// cerr<<"} and R={";
	// for(int x:R) cerr<<x<<",";
	// cerr<<"}"<<endl;
	return Z;
}



int32_t main() {
	cin>>n>>m;
	init_math(max(n+m+n+m,N*3)+17);
	read(A),read(B),read(C),read(D);

	int z1=go();
	swap(n,m);
	swap(A,C);
	swap(B,D);
	int z2=go();

	cerr<<z1<<" "<<z2<<endl;
	if(!A.count() && !B.count() && !C.count() && !D.count())
		assert(!z1&&!z2), cout<<1<<endl;
	else cout<<(z1+z2)%P<<endl;
}













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

using namespace std;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)


int main(void){

	int N, X; cin >> N >> X;
	vector<int> L(N);
	vector<int> D(N, 0);
	REP(i,N) cin >> L[i];

	int ans = 1;
	FOR(i,1,N+1){
		int d = D[i-1] + L[i-1];
		D[i] = d;
		if(d <= X) ans++;
	}
	
	cout << ans << endl;


	return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T>
T totient(T n){
  T res=n;
  for(T i=2;i*i<=n;i++){
    if(n%i==0){
      res=res/i*(i-1);
      for(;n%i==0;n/=i);
    }
  }
  if(n!=1) res=res/n*(n-1);
  return res;
}
//END CUT HERE

signed AOJ_NTL1D(){
  Int n;
  cin>>n;
  cout<<totient(n)<<endl;
  return 0;
}
/*
  verified on 2017/12/31
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_D&lang=jp
*/
signed main(){
  AOJ_NTL1D();
  return 0;
}



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

int main() {
	int i, n, node[252];
	cin >> n;
	for (i = 1; i <= n; i++) cin >> node[i];
	
	for (i = 1; i <= n; i++) {
		cout << "node " << i << ": key = " << node[i];
		if (i != 1)cout << ", parent key = " << node[i / 2];
		if (2 * i <= n)cout << ", left key = " << node[2 * i];
		if (2 * i + 1 <= n)cout << ", right key = " << node[2 * i + 1];
		cout << ", \n";
	}

	return 0;
}

Measured memory_bytes: 3084
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long int ll;

int N;
int num[5];

int main(){
	scanf("%d", &N);
	map<int, int> mpa;
	for(int i = 1; i <= N; i++){
		int n = i;
		for(int j = 2; j * j <= n; j++){
			while(n % j == 0){
				mpa[j]++;
				n /= j;
			}
		}
		if(n != 1) mpa[n]++;
	}
	map<int, int>::iterator itr;
	for(itr = mpa.begin(); itr != mpa.end(); itr++){
		if(itr->second >= 74) num[4]++;
		if(itr->second >= 24) num[3]++;
		if(itr->second >= 14) num[2]++;
		if(itr->second >= 4) num[1]++;
		if(itr->second >= 2) num[0]++;
	}
	int res = 0;
	res += num[4];
	res += num[3] * max(0, num[0] - 1);
	res += num[2] * max(0, num[1] - 1);
	res += max(0, num[0] - 2) * (max(0, num[1] - 1) * num[1] / 2);
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 256