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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

int N;
int A[222222];
int ans[222222];

signed main(){
	cin>>N;
	rep(i,N)cin>>A[i+1];
	for(int i=N;i>0;i--){
		int cnt=0;
		for(int j=i+i;j<=N;j+=i)cnt+=ans[j];
		if(cnt%2!=A[i])ans[i]=1;
	}
	vint lis;
	for(int i=1;i<=N;i++)if(ans[i])lis.pb(i);
	cout<<lis.size()<<endl;
	if(lis.size()){
		rep(i,lis.size()){
			if(i)cout<<" ";
			cout<<lis[i];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 4852
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a<b?b:a)
#define F(i,L,R) for (int i = L; i < R; i++)
#define FE(i,L,R) for (int i = L; i <= R; i++)
#define RF(i,L,R) for (int i = L; i > R; i--)
#define RFE(i,L,R) for (int i = L; i >= R; i--)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define ll long long
#define INF 2000000000
#define nINF -2000000000
#define MOD 1e9+7
#define PI 3.1415926535897932384626
int arr[15][15];
int main(){
	int n,d;
	while(~getII(n,d)){
		F(i,0,n) F(j,0,d) getI(arr[i][j]);
		int ans=0;
		F(i,0,n) F(j,i+1,n){
			int sum=0;
			F(k,0,d) sum+=(arr[i][k]-arr[j][k])*(arr[i][k]-arr[j][k]);
			if((int)(sqrt(sum))*(int)(sqrt(sum))==sum) ans++;
		}
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 256
S = list(input())
T = list(input())
ls = len(S)
lt = len(T)
ans = lt
for i in range(ls):
    temp = 0
    if i+lt > ls:
        break
    subS = S[i:i+lt]
    for ss, st in zip(subS, T):
        if ss != st:
            temp += 1
    ans = min(ans, temp)
print(ans)

Measured memory_bytes: 9032
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

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

  ll a,b;
  cin >> a >> b;
  cout << (100*(a-b)+1900*b)*pow(2,b) << endl;

  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


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

using ll = long long;
#define int long long

// [a -> b-1]
#define reps(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
// [0 -> a-1]
#define rep(i, a) reps(i, 0, (a))
// [a-1 -> b]
#define rreps(i, a, b) for (int i = (int)((a)-1); i >= (int)(b); i--)
// [a-1 -> 0]
#define rrep(i, a) rreps(i, a, 0)
#define all(v) (v).begin(), (v).end()
// next_permutation(all(v))
#define PERM(v) next_permutation(all(v))
/*sort(all(v));
 * (v).erase(unique(all(v)), v.end())*/
#define UNIQUE(v)\
	sort(all(v));\
	(v).erase(unique(all(v)), v.end())
#define MINV(v) min_element(all(v))
#define MAXV(v) max_element(all(v))
#define MIN3(a, b, c) min(min(a, b), c)
#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)
#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)
#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)
#define MAX3(a, b, c) max(max(a, b), c)
#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)
#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)
#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)
// b is [a, c)
#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))
// c is [a, e) && d is [b, f)
#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))
#define chmin(a, b) a = min(a, (b))
#define chmin3(a, b, c) a = MIN3(a, (b), (c))
#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))
#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))
#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))
#define chmax(a, b) a = max(a, (b))
#define chmax3(a, b, c) a = MAX3(a, (b), (c))
#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))
#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))
#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))
#define fcout cout << fixed << setprecision(15)
#define YES(f) cout << ((f) ?G YES_STR : NO_STR) << endl;


void solve(long long A, long long B) {
	cout << max({A + B, A * B, A - B}) << endl;
}

signed main() {
	long long A;
	scanf("%lld",&A);
	long long B;
	scanf("%lld",&B);
	solve(A, B);
	return 0;
}


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

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

    rep(i, s.size()/2) {
        // cout << s[i] << s[s.size()-1-i] << endl;
        if (s[i] != s[s.size()-i-1]) {
            ans += 1;
        }
    }

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

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

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

    int ans = 0, a = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            a++; 
        } else {
            a = 0;
        }
        ans = max(ans, a);
    }

    cout << ans << endl;
} 

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

#define FOR(i,n)    for(lli i=0;i<(lli)(n);++i)
#define FORU(i,j,k) for(lli i=(j);i<=(lli)(k);++i)
#define FORD(i,j,k) for(lli i=(j);i>=(lli)(k);--i)

#define pb push_back
#define mt make_tuple

using namespace std;

using lli = long long int;
using pll = pair<lli, lli>;

using vi = vector<lli>;
using vvi = vector<vi>;
using pii = tuple<lli, lli>;
using vii = vector<pii>;
using vvii = vector<vii>;

#define X(a) get<0>(a)
#define Y(a) get<1>(a)
#define Z(a) get<2>(a)

string TYPE(const int*)          { return "%d";   }
string TYPE(const lli*)          { return "%lld"; }
string TYPE(const char*)         { return "%c";   }
string TYPE(const char**)        { return "%s";   }
string TYPE(const unsigned int*) { return "%u";   }

const int MAX_BUF = 100*1000+42;
char buf[MAX_BUF];

void RD() {}
template<typename T, typename... Args> 
void RD(T* v, Args... args)
{
    scanf((" " + TYPE(v)).c_str(), v);
    RD(args...);
}
template<typename... Args> 
void RD(string* v, Args... args)
{
    scanf(" %s", buf);
    (*v) = buf;
    RD(args...);
}

void PR(bool nl = true)
{ if(nl) printf("\n"); }
template<typename T, typename... Args> 
void PR(bool nl, T v, Args... args)
{
    printf((TYPE(&v) + " ").c_str(), v);
    PR(nl, args...);
}
template<typename... Args> 
void PR(bool nl, string& v, Args... args)
{
    printf("%s", v.c_str());
    PR(nl, args...);
}
template<typename... Args> 
void PR(Args... args)
{ PR(true, args...); }

const long long int oo = 1000*1000*1000;

struct Coord {
    int x, y;
    Coord(int x = 0, int y = 0) : x(x), y(y) {}
    Coord operator + (const Coord& droite) const
    { return Coord(x + droite.x, y + droite.y); }
};

struct AB {
    int k; vector<lli> arbre;
    AB(int _k = 20, lli def = 0) { k = _k;
        FOR(i, 1 << k)
            arbre.push_back(i < (1 << (k-1)) ? 0LL : def);
        FORD(i, ((1 << (k-1)) - 1), 1)
            arbre[i] = arbre[i << 1] + arbre[(i << 1) ^ 1];
    }
    void set(int i, lli x) { int feuille = i + (1 << (k-1));
        arbre[feuille] = x;
        iset(feuille >> 1);
    }
    void iset(int noeud) {
        if(noeud) {
            arbre[noeud] = arbre[noeud << 1] + arbre[(noeud << 1)  ^ 1];
            iset(noeud >> 1);
    }   }
    lli sum(int deb, int fin, int noeud = 1, int p = 0, int q = -1) {
        if(q < p) q = 1 << (k-1);
        if(deb <= p && q <= fin) return arbre[noeud];
        if(deb >= q || fin <= p) return 0LL;
        int mil = (p + q) / 2;
        return sum(deb, fin, noeud << 1, p, mil) + sum(deb, fin, (noeud << 1) ^ 1, mil, q);
    }
};

int T[100*1000+42];

int main()
{
    int n;
    int r = 1;
    RD(&n);
    FOR(i, n)
        RD(T+i);
    T[n] = T[n-1];
    int sens = 0;
    FORU(i, 0, n-2)
    {
        if(sens == 0)
        {
            if(T[i] < T[i+1])
                sens = 1;
            if(T[i] > T[i+1])
                sens = -1;
        }
        else if(sens * T[i] > sens * T[i+1])
        {
            ++r;
            sens = 0;
        }
    }
    PR(r);
    return 0;
}


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


using ll = long long;


int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    sort(h.begin(), h.end(), greater<int>());
    ll ans = 0;
    for (int i = k; i < n; i++) ans += h[i];
    cout << ans << endl;
    return 0;
}


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

int main(){
    int N,i;
    int fx=0;
    int n;

    cin >> N;
    n=N;
    for(i=0;i<100000000;i++){
        fx+=(N%10);
        N/=10;
        if(N<0){
            break;
        }
    }

    if(n%fx==0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

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

int main() {
    double ans = 0;
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for(int i = 0; i < N; i++) {
        cin >> x.at(i) >> y.at(i);
    }
    vector<int> v(N);
    iota(v.begin(), v.end(), 1); // v に 1, 2, ... N を設定
    int count = 0;
    do {
        count++;
        for(int i = 1; i < N; i++) {
            int length = pow(x.at(v.at(i - 1) - 1) - x.at(v.at(i) - 1), 2) +
                         pow(y.at(v.at(i - 1) - 1) - y.at(v.at(i) - 1), 2);
            ans += sqrt(length);
        }
    } while(next_permutation(v.begin(), v.end())); // 次の順列を生成
    ans /= count;
    cout << fixed << setprecision(15) << ans << endl;
}

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

vector<vector<int>> g;

bool dfs(int v, int p, int &c) {
    int cnt = 0;
    for (int u : g[v]) {
        if (u == p) continue;
        int c;
        if (dfs(u, v, c)) return true;
        if (c == 0) cnt++;
    }
    if (cnt >= 2) return true;
    else c = cnt;
    return false;
}

int main() {
    int n; cin >> n;
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int c;
    if (dfs(0, -1, c) || c == 0) puts("First");
    else puts("Second");
    return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        long N = GetInputLong();

        int[] A = GetInputsInt();
        int[] B = GetInputsInt();
        int[] C = GetInputsInt();

        int sum = 0;

        for (int i = 0; i < N-1;i++)
        {
            sum += B[A[i]-1];
            if(A[i] + 1 == A[i + 1])
            {
                sum += C[A[i]-1];
            }
        }
        sum += B[A[N-1] - 1];

        Console.WriteLine(sum);

        Console.ReadKey();
    }



    public static int GetInputInt()
    {
        return int.Parse(Console.ReadLine());
    }
    public static int[] GetInputsInt()
    {
        return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    }
    public static List<int> GetInputsIntList()
    {
        return Console.ReadLine().Split(' ').Select(int.Parse).ToList();
    }
    public static List<float> GetInputsFloatList()
    {
        return Console.ReadLine().Split(' ').Select(float.Parse).ToList();
    }

    public static long GetInputLong()
    {
        return long.Parse(Console.ReadLine());
    }
    public static long[] GetInputsLong()
    {
        return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
    }

}


Measured memory_bytes: 13268
import java.util.*;

class Main {
	//????????¢?´¢?????¬???
	public static int binarySearch(int[] A, int n, int key) {
		int left = 0;
		int right = n ;
		int mid = 0;
		while(left < right) {
			 mid = (left + right) / 2;
			if ( key == A[mid] ) return mid;
			else if ( key > A[mid] ) left = mid + 1;
			else if ( key < A[mid] ) right = mid;
		}
	return -1;
	}

	public static void main(String args[]) {

		Scanner scan = new Scanner(System.in);
		int[] arrayS = new int[100000]; //??°???S
		int[] arrayT = new int[50000];   //??°???T
		int count = 0;						 //?????°????¨???????????????°

		//????´??????°???????????????ArrayS?????°???S???????????????
		int sNum = scan.nextInt();
		for (int i = 0; i < sNum; i++)
			arrayS[i] = scan.nextInt();

		//????´??????°???????????????ArrayT?????°???T???????????????
		int tNum = scan.nextInt();
		for (int j = 0; j < tNum; j++)
			arrayT[j] = scan.nextInt();

		//??°???T???????´??????°???A????????????????????????????????????
		for (int j = 0; j < tNum; j++)
			if(binarySearch(arrayS, sNum, arrayT[j]) >= 0) count++;

		System.out.println(count);
	}
}

Measured memory_bytes: 67428
from math import sqrt
from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（ダイクストラ法）
def Dijkstra(barriers, vSt):
    numV = len(barriers)
    rests = set(range(numV))
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))

    while PQ:
        c, vNow = heappop(PQ)
        if c > costs[vNow]: continue

        rests.remove(vNow)
        if not rests: break

        costNow = c
        xi, yi, ri = barriers[vNow]
        for v2 in rests:
            xj, yj, rj = barriers[v2]
            wt = sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj
            if wt < 0: wt = 0
            c2 = costNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))

    return costs


xs, ys, xt, yt = map(int, input().split())
N = int(input())
barriers = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)]

costs = Dijkstra(barriers, 0)
print(costs[1])


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

int N;

int main() {
    scanf("%d", &N);
    for(int i=1; i<=3500; i++) {
        for(int j=i; j<=3500; j++) {
            if(4 * i * j - N * i - N * j == 0) continue;
            int z = 1LL * N * i * j / (4LL * i * j - N * i - N * j);
            if(4LL * i * j * z == 1LL * N * (i * j + j * z + z * i) && z > 0) {
                printf("%d %d %d\n", i, j, z);
                return 0;
            }
        }
    }
}


Measured memory_bytes: 384
N = int(input())
l = list(map(int, input().split()))
a = [0] * (N+1)
for k in reversed(range(1, N+1)):
    num = sum([a[k*i] for i in range(1, N//k+1)])
    if num % 2 != l[k-1]:
        a[k] = 1
M = sum(a)
ans = [i for i in range(1, N+1) if a[i] > 0]
 
print(M)
print(' '.join(map(str, ans)))

Measured memory_bytes: 19892
X, N = map(int, input().split())
p = list(map(int, input().split()))

if not (X in p):
    print(X)
else:
    i = 1
    while(1):
        if not (X-i in p):
            print(X-i)
            break
        elif not (X+i in p):
            print(X+i)
            break
        i+=1

Measured memory_bytes: 9188
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;

int main(){
    int h,w; cin >> h >> w;
    int g[h][w];
    rep(i,h)rep(j,w) cin >> g[i][j];

    vector<PP> ans;
    int n=0;

    rep(i,h){
        rep(j,w){
            if(i==h-1 && j==w-1) break;
            if(g[i][j]%2==1){
                n++;
                if(j==w-1 && i!=h-1){
                    ans.push_back(PP(P(i+1,j+1),P(i+2,j+1)));
                    g[i+1][j]++;
                }
                else{
                    ans.push_back(PP(P(i+1,j+1),P(i+1,j+2)));
                    g[i][j+1]++;
                }
            }
        }
    }

    cout << n << endl;
    rep(i,ans.size()) cout << ans[i].first.first << ' ' <<  ans[i].first.second << ' ' << ans[i].second.first << ' ' << ans[i].second.second << endl;
return 0;
}

Measured memory_bytes: 6324
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const double PI = acos(-1.0);
const double EPS = 1e-10;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b;
    cin>>n>>a>>b;
    cout<<min(n*a,b)<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main(){
	ll n,k;
	cin>>n>>k;
	vector<ll> v;
	rep(i,0,n){
		ll a;
		cin>>a;
		v.pb(a);
	}
	ll mn = 1000000000000000000LL;
	rep(i,0,1<<n){
		ll mx = 0;
		ll c = 0;
		ll cost = 0;
		rep(j,0,n){
			ll b = v[j];
			if(((i>>j)&1)==1){
				b = max(mx+1,b);	
			}
			cost += b-v[j];
			if(b>mx)c++;
			mx = max(mx,b);
		}
		if(c>=k){
			mn = min(mn,cost);
		}
	}
	printf("%lld\n",mn);
	return 0;
}




Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void)
{
  int a,b,x; cin>>a>>b>>x;
  int sum=0;
  
  for(int i=0;i<=b;i++){
    if((a+i)==x){puts("YES"); return 0;}
  }
  
  puts("NO");
  return 0;
}

Measured memory_bytes: 256
using namespace std;
#include<bits/stdc++.h>
#define int long long
#define pb push_back 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define repa(i,a,b) for (int i=a; i<=b; i++)
#define repd(i,b,a) for (int i=b; i>=a; i--)
#define endl "\n"
//debugging
#define debug1(a) cout<<#a<<" = "<<(a)<<endl;
#define debug2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<", "<<#d<<" = "<<(d)<<endl;

const int N = 1e+6+5;
int big = 1e+18+3;
int mod = 1e+9+7;

int raisefive(int val)
{
    return ( val*val*val*val*val );
}

signed main()
{
    IOS;
        
    int x; cin>>x;

    repa(i,-122,122)
        repa(j,-122,122)
            if ( raisefive(i) - raisefive(j) == x )
            {
                cout<<i<<" "<<j<<endl;
                return 0;
            }
}

Measured memory_bytes: 3612
//#define _USE_MATH_DEFINES
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
#define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
inline int safe_mul(const int x, const int y) __attribute__ ((warn_unused_result));

int main()
{
//    freopen("in.txt","r", stdin);
//    freopen("out.txt", "w", stdout);
//    cin.tie(0);
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    --a, --b, --c, --d;

    string s;
    cin >> s;

    for (int i = b; i < d; ++i)
            if (s[i] == '#' && s[i + 1] == '#')
                FINAL_OUT("No");
    for (int i = a; i < c; ++i)
        if (s[i] == '#' && s[i + 1] == '#')
            FINAL_OUT("No");

    if (c > d) {
        bool good = false;
        for (int i = b; i <= d; ++i) {
            if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.')
                good = true;
        }
        if (!good)
            FINAL_OUT("No");
    }

    FINAL_OUT("Yes");
}


Measured memory_bytes: 892
from math import gcd

n=int(input())
mod=10**9+7

z = 0
za = 0
zb = 0
d = {}

for _ in range(n):
    a,b = map(int,input().split())
    if a == 0 and b ==0:
        z += 1
    elif a == 0:
        za += 1
    elif b == 0:
        zb += 1
    else:
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        if b > 0:
            if (a,b) in d:
                d[(a,b)][0] += 1
            else:
                d[(a,b)] = [1,0]
        else:
            if (-b,a) in d:
                d[(-b,a)][1] += 1
            else:
                d[(-b,a)] = [0,1]

ans = 1
for key in d:
    ans *= (pow(2,d[key][0],mod) + pow(2,d[key][1],mod) - 1) % mod
    ans %= mod
ans *= (pow(2,za,mod) + pow(2,zb,mod) - 1) % mod
ans %= mod
print((ans + z - 1)%mod)

Measured memory_bytes: 133972
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = 99999999;
const ll linf = 999999999999999999;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

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

int main(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    
    int s = a[0] + a[1] + a[2];
    sort(a,a+3);
  //  P(a[0]);
    P(s - a[2]);

	return  0;
}

Measured memory_bytes: 764
#include<iostream>
#include<algorithm>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int n;
int c[2][9];

int main(){
  cin >> n;
  while(n--){
    const int sum = 171;
    rep(i,9)cin >> c[0][i];
    rep(i,9)cin >> c[1][i];

    int perm[9];
    rep(i,9)perm[i] = i;

    int win = 0, lose = 0;
    do{
      int mine = 0;
      rep(i,9){
	if(c[0][i] > c[1][perm[i]])mine += c[0][i] + c[1][perm[i]];
      }

      if(mine*2 > sum)win++;
      else lose++;
    }while(next_permutation(perm,perm+9));

    cout << fixed << setprecision(5) << (double)win/(win+lose) << " " << (double)lose/(win+lose) << endl;
  }
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;


int main(){
  
  int X;
  cin>>X;
  if(X%7==0){
    cout<<"thu"<<endl;
  }
  if(X%7==1){
    cout<<"fri"<<endl;
  }
  if(X%7==2){
    cout<<"sat"<<endl;
  }
  if(X%7==3){
    cout<<"sun"<<endl;
  }
  if(X%7==4){
    cout<<"mon"<<endl;
  }
  if(X%7==5){
    cout<<"tue"<<endl;
  }
  if(X%7==6){
    cout<<"wed"<<endl;
  }
  
	
	/*int m,f,b;
	cin>>m>>f>>b;
	if(b-m<=0){
		cout<<0<<endl;
	}
	if(b-m>0 && b-m<=f){
		cout<<b-m<<endl;
	}
	if(b-m>0 && b-m>f){
		cout<<"NA"<<endl;
	}*/
	/*int a,b;
	cin>>a>>b;
	cout<<(a+b)/2<<endl;*/
	
	/*random_device rnd;
	mt19937 mt(rnd());
	uniform_int_distribution<> rnd3(1, 3);
	
	string p1, p2, p3, p4;
	cin >> p1 >> p2 >> p3 >> p4;
	
	int t = rnd()%3;
	
	if(t == 0){
		cout << "1:" << p1 << ',' << p2 << endl;
		cout << "2:" << p3 << ',' << p4 << endl;
	}
	if(t == 1){
		cout << "1:" << p1 << ',' << p3 << endl;
		cout << "2:" << p2 << ',' << p4 << endl;
	}
	if(t == 2){
		cout << "1:" << p1 << ',' << p4 << endl;
		cout << "2:" << p2 << ',' << p3 << endl;
	}*/
	
	/*
	switch(type){
		case 0:
			cout << "1:" << p1 << ',' << p2 << endl;
			cout << "2:" << p3 << ',' << p4 << endl;
			break;
		case 1:
			cout << "1:" << p1 << ',' << p3 << endl;
			cout << "2:" << p2 << ',' << p4 << endl;
			break;
		case 2:
			cout << "1:" << p1 << ',' << p4 << endl;
			cout << "2:" << p2 << ',' << p3 << endl;
			break;
	}
	*/
	
	
	return 0;
}



Measured memory_bytes: 3112
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int N, M;
  cin >> N >> M;
  
  if( N >= M ){
    cout << 0 << endl;
    return 0;
  }
  
  vector<int> X(M);
  for( int i = 0; i < M; i++ ) cin >> X.at(i);
  sort(X.begin(), X.end());
  
  vector<int> kyori(M, 0);
  int ans = 0;
  for( int i = 1; i < M; i++ ){
    kyori.at(i) = abs(X.at(i) - X.at(i-1));
    ans += kyori.at(i);
  }
  sort(kyori.begin(), kyori.end());
  
  for( int i = 1; i <= N-1; i++ ){
    ans -= kyori.at(M-i);
  }
  cout << ans << endl;
  
  
  
    
}




Measured memory_bytes: 1792
num=int(input())
max=0
maxnum=1
for ii in range(num):
    i=ii+1
    div=0
    while True:
        if i%2==0:
            i//=2
            div+=1
        else:
            break
    if(div>max):
        max=div
        maxnum=ii+1
print(maxnum)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        if (a.length() != b.length()) {
            if (a.length() > b.length()) {
                System.out.println("GREATER");
            } else {
                System.out.println("LESS");
            }
        } else {
            for (int i = 0; i < a.length(); i++) {
                int aa = Character.getNumericValue(a.charAt(i));
                int bb = Character.getNumericValue(b.charAt(i));
                if (aa > bb) {
                    System.out.println("GREATER");
                    return;
                } else if (aa < bb) {
                    System.out.println("LESS");
                    return;
                }
            }
            System.out.println("EQUAL");
        }
    }
}

Measured memory_bytes: 23636
while True:
  inputHeight,inputWeight = input().split()
  inputHeight,inputWeight = int(inputHeight),int(inputWeight)
  if(inputHeight == 0 and inputWeight == 0):
    break
  for i in range(inputHeight):
    for j in range(inputWeight):
      if((i+j) % 2 == 0):
          print('#',end='')
      else:
          print('.',end='')
    print()
  print()


Measured memory_bytes: 7004
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000
#define MAX_M 100000
#define vec vector<int>
#define vecst vector<string>
#define vecch vector<char>
#define vecf vector<float>
#define vecvec vector<vector<int>>
#define vecHvec vector<vector<char>>
using ll=int long long;
const int INF = 1e9;
#define PI 3.141592653589793
// cout << setprecision(15) << std::fixed;

int main(){
  int n,s,ans=0;
  cin>>n>>s;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      int z=(s-(i*10000+j*5000))/1000;
      if(z+i+j==n&&z>=0){
        cout<<i<<" "<<j<<" "<<z<<endl;
        exit(0);
      }
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a,b;

	scanf("%d %d", &a, &b);
	if(a<b){
		printf("a < b\n");
	}
	else if(a>b){
		printf("a > b\n");
	}
	else{
	printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 202;

const int m = 60;
ll u[m];

void ave(ll x)
{
    for (int i = m - 1; i >= 0; --i)
    {
        if ((x & (1LL << i)))
        {
            if (!u[i])
            {
                u[i] = x;
                return;
            }
            x ^= u[i];
        }
    }
}

bool stg(ll x)
{
    for (int i = m - 1; i >= 0; --i)
    {
        if ((x & (1LL << i)))
            x ^= u[i];
    }
    return (x == 0);
}

int n;
ll a[N];
char s[N];

void solv()
{
    for (int i = 0; i < m; ++i)
        u[i] = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    scanf(" %s", s);
    for (int i = n - 1; i >= 0; --i)
    {
        if (s[i] == '1')
        {
            if (!stg(a[i]))
            {
                printf("1\n");
                return;
            }
        }
        else
        {
            ave(a[i]);
        }
    }
    printf("0\n");
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    int tt;
    scanf("%d", &tt);
    while (tt--)
        solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/
int f[114][11];
ll p[114][12];

int main(){
    int N; cin >> N;
    rep(i,N) rep(j,5) rep(k,2){
        int ff;cin>>ff;
        f[i][j*2+k]+=ff;
    }

    rep(i,N)rep(j,11) cin >> p[i][j];

    ll ans = -LINF;
    for(int mask=1;mask<(1<<10);mask++){
        ll cost = 0;
        vi poi(10,0);
        for(int i=0;i<N;i++){   // shop i
            int cnt = 0;
            rep(j,5) rep(k,2){
                if(f[i][j*2+k] and (mask & (1<<(j*2+k)))) cnt++;
            }

            cost += p[i][cnt];
        }

        ans = max(ans,cost);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 10000
#define NIL -1

typedef struct {
  int pr,left,right;
} node;

node T[MAX];
int n,D[MAX],H[MAX];

void setdepth(int u,int d){
  if(u == NIL) return;
  D[u] = d;
  setdepth(T[u].left,d+1); setdepth(T[u].right,d+1);
}

int setheight(int u){
  int h1=0,h2=0;
  if(T[u].left != NIL) h1 = setheight(T[u].left)+1;
  if(T[u].right != NIL) h2 = setheight(T[u].right)+1;
  if(h1 >= h2) return H[u] = h1;
  else return H[u] = h2;
}

int getsib(int u){
  if(T[u].pr == NIL) return NIL;
  if(T[T[u].pr].left != u && T[T[u].pr].left != NIL) return T[T[u].pr].left;
  if(T[T[u].pr].right != u && T[T[u].pr].right != NIL) return T[T[u].pr].right;
  return NIL;
}

void print(int u){
  int deg=0;
  printf("node %d: parent = %d, sibling = %d, ",u,T[u].pr,getsib(u));
  if(T[u].left != NIL) deg++; if(T[u].right != NIL) deg++;
  printf("degree = %d, depth = %d, height = %d, ",deg,D[u],H[u]);

  if(T[u].pr == NIL) printf("root\n");
  else if(T[u].left == NIL && T[u].right == NIL) printf("leaf\n");
  else printf("internal node\n");
}

int main(){
  int i=0,id,l,r,root=0;
  scanf("%d",&n);

  for(i=0;i<n;i++) T[i].pr = NIL;
  for(i=0;i<n;i++){
    scanf("%d %d %d",&id,&l,&r);
    T[id].left = l; T[id].right = r;
    if(l != NIL) T[l].pr = id; if(r != NIL) T[r].pr = id;
  }

  for(i=0;i<n;i++) if(T[i].pr == NIL) root = i;

  setdepth(root,0);
  setheight(root);

  for(i=0;i<n;i++) print(i);

  return 0;
}



Measured memory_bytes: 1984
import itertools
j_shop = list(set(itertools.product(*[[0, 1]]*10)) - set([tuple([0]*10)]))

n = int(input())

D = [[] for _ in range(10)]
from collections import defaultdict
profit = defaultdict(int)


for i in range(n):
    f = list(map(int, input().split()))
    for j in range(10):
        if f[j] == 1:
            D[j].append(i)
            
for i in range(n):
    p = list(map(int, input().split()))
    for j in range(11):
        profit[(i, j)] = p[j]
        
ans = float('-INF')
for js in j_shop:
    temp = [0]*n
    for i in range(10):
        if js[i] == 1:
            for d in D[i]:
                temp[d] += 1
    p = 0
    for k, v in enumerate(temp):
        p += profit[(k, v)]
    ans = max(ans, p)
print(ans)

Measured memory_bytes: 3700
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<list>
#include<queue>
#include<string.h>
#include<functional>
#include<stack>
#include<deque>
#include<limits.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
using namespace std;

int t[200000];
int c[200001];
int S[200000];
int ans;
signed main() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int k; cin >> k;
		t[i] = k;
		c[k]++;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = max(i - c[i], 0); j < i; j++) {
			S[j]++;
		}
	}
	for (int i = 0; i < n; i++) {
		if (S[i])ans++;
	}
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y; x--;
		if (t[x] == y)goto l;
		if (t[x] - c[t[x]] >= 0) {
			S[t[x] - c[t[x]]]--;
			if (S[t[x] - c[t[x]]] == 0) {
				ans--;
			}
		}
		if (y - c[y] - 1 >= 0) {
			S[y - c[y] - 1]++;
			if (S[y - c[y] - 1] == 1) {
				ans++;
			}
		}
		c[t[x]]--; c[y]++;
		t[x] = y;
	l:;
		cout << n-ans << endl;
	}
}

Measured memory_bytes: 3712
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: u64,
    }
    let ans = (n - 1) * n / 2;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	long double sum = 0;
	for (size_t i = 0; i < N; i++)
	{
		long double x;
		std::string s;
		in >> x >> s;
		if (s == "JPY") {
			sum += x;
		}
		else {
			sum += x * 380000.0;
		}
	}
	out
		<< std::fixed << std::setprecision(9)
		<< sum << endl;

	return 0;
}
#endif


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)
#define INF 10000000

typedef long long ll;
typedef pair<ll, ll> P;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z


int dx4[4]={1,0,-1,0};
int dy4[4]={0,1,0,-1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

void solve(void){
    int n;
    cin >> n;
    ll accsum = 0; //累積和
    ll as[n];
    rep(n, i) scanf("%lld ", &as[i]);
    //even(0-indexed) > 0
    ll ans1 = 0;
    rep(n, i) {
        accsum += as[i];
        if (i % 2 == 0) {
            ll diff = max(0LL, 1LL - accsum);
            ans1 += diff;
            accsum += diff;
        }
        else {
            ll diff = max(0LL, 1LL + accsum);
            ans1 += diff;
            accsum -= diff;
        }
    }
    //even(0-indexed) < 0
    accsum = 0;
    ll ans2 = 0;
    rep(n, i) {
        accsum += as[i];
        if (i % 2 != 0) {
            ll diff = max(0LL, 1LL - accsum);
            ans2 += diff;
            accsum += diff;
        }
        else {
            ll diff = max(0LL, 1LL + accsum);
            ans2 += diff;
            accsum -= diff;
        }
    }
    cout << min(ans1, ans2) << '\n';
}

int main(void){
  solve();
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<bool>vis(n + 1, false);
	bool ans = false;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		if (a == 1) {
			if (vis[b]) {
				ans = true;
			}
			vis[b] = true;
		}
		else if (b == n) {
			if (vis[a]) {
				ans = true;
			}
			vis[a] = true;
		}
	}
	if (!ans)cout << "IM";
	cout << "POSSIBLE" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
 
const long long MAX = -1e18;
const long long MAXN = 3e5 + 5;
long long dp_f[MAXN],dp_e[MAXN],a[MAXN];
 
priority_queue<long long , vector<long long> , greater<long long> > que;
priority_queue<long long>pque;
 
void Slove_f(int n){
	long long sum_f = 0;
	for(int i = 1;i <= 3 * n;i++){
		que.push(a[i]);
		sum_f += a[i];
		dp_f[i] = sum_f;
		if(que.size() > n){
			sum_f -= que.top();
			que.pop();
			dp_f[i] = sum_f;
		}
	}
 
}
 
void Slove_e(int n){
	long long sum_e = 0;
	for(int i = 3 * n;i >= 1;i--){
		pque.push(a[i]);
		sum_e += a[i];
		dp_e[i] = sum_e;
		if(pque.size() > n){
			sum_e -= pque.top();
			pque.pop();
			dp_e[i] = sum_e;
		}
	}
 
}
 
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= 3 * n;i++) scanf("%lld",&a[i]);
 
	Slove_f(n);	
	Slove_e(n);
 
	long long ans = MAX;
	for(int i = n;i <= 2 * n;i++){
		ans = max(ans,dp_f[i] - dp_e[i + 1]);
	}
	printf("%lld",ans);
}


Measured memory_bytes: 9588
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def isok(num,val):##適宜変更
    return num<=val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

n = ni()
s = input()
idxs =[[] for i in range(10)]
for i in range(n):
    num= int(s[i])
    idxs[num].append(i)
ans = 0
for i in range(10):
    if not idxs[i]:
        continue
    i0 = idxs[i][0]
    for j in range(10):
        t1 = bisect(idxs[j],i0)
        if t1==len(idxs[j])-1:
            continue
        i1 = idxs[j][t1+1]
        for k in range(10):
            t2 = bisect(idxs[k],i1)
            if t2==len(idxs[k])-1:
                continue
            else:
                ans+=1
                #print(i,j,k)
print(ans)


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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string s; cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != s[s.size()-1-i]) {
            s[s.size()-1-i] = s[i];
            ans++;
        }
    }
    cout << ans << '\n';
}



Measured memory_bytes: 764
#include<iostream>
#include<math.h>
//#include<vector>

int main(){
	int x;
	std::cin>>x;

	bool flag;

	if (x == 2) {
		std::cout << x << std::endl;
		exit(0);
	}
	
	//std::cout << 1 << std::endl;
	
	for (int i = x;; x++) {
		
		flag = true;

		if (x % 2 == 0) {
			continue;
		}
		
		double sqrtNum = sqrt(x);
		for (int j = 3; j <= sqrtNum; j += 2){
			if (x % j == 0){
				flag=false;
			}
		}

		if (!flag) {
			continue;
		}

		std::cout << x << std::endl;
		exit(0);
	}

	
	return 0;
}

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

int main() {
    string str, ans = "";
    cin >> str;
    rep(i, str.length()) {
        if(str.at(i) == 'B' && ans.length() != 0) ans.pop_back();
        else if(str.at(i) == '0' || str.at(i) == '1') ans += str.at(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
from sys import stdin

s = int(stdin.readline().strip())
mem = []
a = s

for i in range(1000000):
  if a in mem:
    print(i+1)
    exit()
  mem.append(a)
  if a % 2 == 0: a = a // 2
  else: a = 3 * a + 1

Measured memory_bytes: 9140
import java.io.InputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */
    int n = sc.nextInt();
    int k = sc.nextInt();

    long[] x = new long[n];

    for (int i = 0; i < n; i++) {
      x[i] = sc.nextInt();
    }

    long min = Long.MAX_VALUE;
    for (int i = 0; i <= n - k; i++) {
      long len;
      int l = i;
      int r = i + k - 1;
      if (x[r] < 0) { // x[l] < x[r] < 0
        len = Math.abs(x[l]);
      } else if (x[l] <= 0 && 0 <= x[r]) {
        len = 0;
        len += Math.min(Math.abs(x[l]), Math.abs(x[r])) * 2;
        len += Math.max(Math.abs(x[l]), Math.abs(x[r]));
      } else { // 0 < x[l] < x[r]
        len = Math.abs(x[r]);
      }
      min = Math.min(min, len);
    }
    os.println(min);
  }

  private static class Scanner {

    private final InputStream is;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    Scanner(InputStream is) {
      this.is = is;
    }

    private boolean hasNextByte() {
      if (ptr < buflen) {
        return true;
      } else {
        ptr = 0;
        try {
          buflen = is.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (buflen <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) {
        return buffer[ptr++];
      } else {
        return -1;
      }
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
        ptr++;
      }
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    public long nextLong() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    public int nextInt() {
      long nl = nextLong();
      if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
        throw new NumberFormatException();
      }
      return (int) nl;
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }
  }
}


Measured memory_bytes: 22604