akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())
if abs(n-m)>1:
    print(0)
elif abs(n-m)==0:
    cnt=1
    for i in range(n,0,-1):
        cnt*=i
        cnt%=10**9+7
    for i in range(n,0,-1):
        cnt*=i
        cnt%=10**9+7
    cnt*=2
    cnt%=10**9+7
    print(cnt)
else:
    cnt=1
    for i in range(n,0,-1):
        cnt*=i
        cnt%=10**9+7
    for i in range(m,0,-1):
        cnt*=i
        cnt%=10**9+7
    print(cnt)


Measured memory_bytes: 9140
#15 B - KEYENCE String
S = list(input())

result = 'NO'
for i in range(len(S)):
    Scpy = S.copy()
    for j in range(i,len(S)):
        Scond = Scpy[:i]+Scpy[j:]
        if (''.join(Scond)) == ('keyence'):
            result = 'YES'
            break
    else:
        continue
    break
print(result)

Measured memory_bytes: 9096
import sys
import math
import itertools as it
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
x = intl()
m = []
s = 0
for i in range(-max(x),max(x)+1):
    for j in range(n):
        s += (x[j]-i)**2
    m.append(s)
    s = 0
print(min(m))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main()
{
    char t[1010][111],h[1010][111];
    int n,ta = 0,ha = 0,len;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> t[i] >> h[i];
    }
    for(int i = 0;i < n;i++){
        len = max(strlen(t[i]),strlen(h[i]));
        for(int j = 0;j < len;j++){
            if(t[i][j] != h[i][j]){
                if(t[i][j] - '0' > h[i][j] - '0'){
                    ta += 3;
                    //cout << i << "ta win" << endl;
                    break;
                }
                else if(t[i][j] - '0' < h[i][j] - '0'){
                    ha += 3;
                    //cout << i << "ha win" << endl;
                    break;
                }
            }
            else if(j == len - 1 && t[i][j] - '0' == h[i][j] - '0'){
                ta++;
                ha++;
                //cout << i << "draw" << endl;
                break;
            }
        }
    }
    cout << ta << " " << ha << endl;

    return 0;
}



Measured memory_bytes: 3320
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K,A=0;
  string S;
  cin >> N >> K >> S;
  int count=1;
  for(int i = 1; i < N; i++){
    if(S[i] != S[i-1]){
      count ++;
    }
  }
  int ans = N-count+2*K;
  cout <<min(N-1,ans)<<endl;
}

Measured memory_bytes: 512
<?php

function input() {
    return trim(fgets(STDIN));
}
function input_array() {
    return explode(' ', input());
}
function swap(&$a, &$b) {
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}
function selection_sort($A) {
    $swap_count = 0;
    for ($i = 0, $count = count($A); $i < $count; $i++) {
        $minj = $i;
        for ($j = $i; $j < $count; $j++) {
            if ($A[$j] < $A[$minj]) {
                $minj = $j;
            }
        }
        if ($i !== $minj) {
            swap($A[$i], $A[$minj]);
            $swap_count++;
        }
    }
    return [$A, $swap_count];
}

input();
$A = array_map(function($numeric_string) {
    return (int)$numeric_string;
}, input_array());

list($A, $swap_count) = selection_sort($A);

echo implode(' ', $A) . "\n";
echo "{$swap_count}\n";


Measured memory_bytes: 9360
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<numeric>
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; }
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main()
{
    int x,a,b;
    cin >> x >> a >> b;
    if(a>=b) cout << "delicious" << endl;
    else if (x+a>=b) cout << "safe" << endl;
    else cout << "dangerous" << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())

ans = 0
tmp = 10
for i in range(1, n):
    tmp *= 10
    tmp %= 1000000007
ans += tmp
tmp = 18
for i in range(1, n):
    tmp *= 9
    tmp %= 1000000007
ans -= tmp
tmp = 8
for i in range(1, n):
    tmp *= 8
    tmp %= 1000000007
ans += tmp
if ans < 0:
    ans += 1000000007
print(ans)


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

#define MAX 200000
#define SENTINEL 2000000000

int L[MAX / 2 + 2], R[MAX / 2 + 2];

long long merge(int A[], int n, int left, int mid, int right) {
	int i, j, k;
	long long cnt = 0;
	int n1 = mid - left;
	int n2 = right - mid;
	for (i = 0; i < n1; i++) L[i] = A[left + i];
	for (i = 0; i < n2; i++) R[i] = A[mid + i];
	L[n1] = R[n2] = SENTINEL;
	i = j = 0;
	for ( k = left; k < right; k++) {
		if (L[i] <= R[j]) {
			A[k] = L[i++];
		} else {
			A[k] = R[j++];
			cnt += n1 - i;
		}
	}
	return cnt;
}

long long mergeSort(int A[], int n, int left, int right) {
	int mid;
	long long v1, v2, v3;
	if (left + 1 < right) {
		mid = (left + right) / 2;
		v1 = mergeSort(A, n, left, mid);
		v2 = mergeSort(A, n, mid, right);
		v3 = merge(A, n, left, mid, right);
		return v1 + v2 + v3;
	} else return 0;
}

int main(void) {
	int A[MAX], n, i;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> A[i];
	}

	long long ans = mergeSort(A, n, 0, n);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2716
num = int(input())
nums = input().split()

zero_flag = False
for item in nums:
  if item == '0':
    zero_flag = True
    break
    
if zero_flag:
  seki = 0
else:
  seki = 1
  for item in nums:
    seki *= int(item)
    if seki > 10**18:
      seki = -1
      break

print(seki)

Measured memory_bytes: 19312
list=[]

for i in range(5):
    x=int(input())
    list.append([(x-1)%10, x])

list=sorted(list)
#print(list)

time=0

for r in range(len(list)):
    if r==0:
        time+=list[0][1]
    else:
        x=list[r][1]
        if x%10==0:
            time+= x
        else:
            time+= (((x-x%10)/10)+1)*10

print(int(time))

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int N;
    cin >> N;
    int B[N-1];
    for(int i=0; i<N-1; i++)    cin >> B[i];
    int ans = 0; 
    ans += B[0]+B[N-2];
    for(int i =0; i<N-2; i++){
        ans += min(B[i], B[i+1]);
    }

    cout <<ans <<endl;

    return 0;
}

Measured memory_bytes: 256
from math import sin,cos,radians
a,b,c=map(int,input().split())
c=radians(c)
s=a*b*sin(c)*0.5
for i in[s,a+b+(a*a+b*b-2*a*b*cos(c))**0.5,s/a*2]:print('%5f'%i)



Measured memory_bytes: 5724
n = gets.to_i
n.times do
    r = gets.to_i
    i = 0
    while r >= 10
        max = 0
        (r.to_s.length - 1).times do |l|
            str = r.to_s
            a = str[0..l].to_i
            b = str[(l + 1)...str.length].to_i
            max = a * b if a * b > max
        end
        r = max
        i += 1
    end
    puts i
end

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

#define mp(x, y) make_pair((x), (y))

typedef long long ll;

int n;
int a[100005];

int main()
{
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a+n);
	int best=a[0];
	for(int i=0; i<n-2; i++) {
		if(min(a[i], a[n-1]-a[i])>min(best, a[n-1]-best)) best=a[i];
	}
	printf("%d %d\n", a[n-1], best);

	return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    
    int s = 0;
    for (int i = 0; i < N; i++) {
      s += i%2 == 0 ? A[i] : -A[i];
    }

    int[] x = new int[N];
    x[0] = s/2;
    for (int i = 1; i < N; i++) {
      x[i] = A[i-1]-x[i-1];
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < N; i++) {
      ans.append(2*x[i]).append(" ");
    }
    
    System.out.println(ans.toString());
  }
}

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

int main(int argc, const char * argv[]) {
    int N,K;
    cin>>N>>K;
    int *A=new int[N];
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    for(int i=K;i<N;++i){
        cout<<((A[i-K]<A[i])?"Yes":"No")<<endl;
    }
    delete[] A;
    return 0;
}

Measured memory_bytes: 3584
#include<stdio.h>
int main()
{
    int a,b,i,j,r=0,c=0,t=0;
    scanf("%d %d",&a,&b);
    int x[a][b],y[a+1][b+1];
    for(i=0;i<a;i++)
    {
        for(j=0;j<b;j++)
        {
            scanf("%d",&x[i][j]);
            y[i][j]=x[i][j];
            r=r+x[i][j];
        }
        y[i][b]=r;
        t=t+y[i][b];
        r=0;
    }
    y[a][b]=t;
    for(i=0;i<b;i++)
    {
        for(j=0;j<a;j++)
        {
            c=c+x[j][i];
        }
        y[a][i]=c;
        c=0;
    }
    for(i=0;i<a+1;i++)
    {
        for(j=0;j<b;j++)
        {
            printf("%d ",y[i][j]);
        }
        printf("%d\n",y[i][b]);
    }
    return 0;
}


Measured memory_bytes: 2072
use proconio::input;
use std::cmp::Reverse;

fn main() {
    input! {
        n: usize,
        m: usize,
        mut a: [i64; n],
        mut bc: [(usize, i64); m],
    }
    a.sort();
    bc.sort_by_key(|k| Reverse(k.1));

    let mut i = 0;

    for a in a.iter_mut() {
        if i < bc.len() && *a < bc[i].1 {
            *a = bc[i].1;
            bc[i].0 -= 1;

            if bc[i].0 == 0 {
                i += 1;
            }
        }
    }

    let ans: i64 = a.iter().sum();

    println!("{}", ans);
}


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

int main() {

	int n; cin >> n;
	string s; cin >> s;
	int need_left = 0;
	int pointer = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') ++pointer;
		else {
			if (pointer == 0) ++need_left;
			else --pointer;
		}
	}
	int need_right = pointer;
	string ans = "";
	for (int i = 0; i < need_left; i++) {
		ans += '(';
	}
	ans += s;
	for (int i = 0; i < need_right; i++) {
		ans += ')';
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3620
local N = io.read("*n")
local M = io.read("*n")
local X = io.read("*n")
local Y = io.read("*n")

local xmax = X
local ymin = Y
local endend = false
for i = 1, N do
	local xi = io.read("*n")
	xmax = math.max(xmax, xi)
	if ymin <= xmax then
		endend = true
		break
	end
end
if not endend then
	for i = 1, M do
		local yi = io.read("*n")
		ymin = math.min(ymin, yi)
		if ymin <= xmax then
			endend = true
			break
		end
	end
end
if endend then
	print("War")
else
	print("No War")
end

Measured memory_bytes: 1012
#include<stdio.h>
  
int n,pos;
int a[40],b[40];
  
void solve(int l,int r){
  if(l>r)return;
  if(l==r){
    if(b[l]==a[0])printf("%d",b[l]);
    else printf("%d ",b[l]);
    pos++;
    return;
  }
  
  int x=a[pos],i;
  pos++;
  for(i=l;i<=r;i++){
    if(b[i]==x)break;
  }
  solve(l,i-1);
  solve(i+1,r);
    
  if(x==a[0])printf("%d",x);
  else printf("%d ",x);
}
  
int main(){
  int i;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&a[i]);
  for(i=0;i<n;i++)scanf("%d",&b[i]);
  pos=0;
  solve(0,n-1);
  printf("\n");
  return 0;
}

Measured memory_bytes: 600
import sys

def prime(n):
    a = [0] * (n + 1)
    a[0] = 1
    a[1] = 1
    i = 2
    while n // i >= i:
        if a[i] != 0:
            i += 1
            continue
        j = 2 * i
        while j <= n:
            a[j] = 1
            j += i
        i += 1
    return [i for i, ai in enumerate(a) if ai == 0]

for i in sys.stdin:
    print(len(prime(int(i))))
    



Measured memory_bytes: 16760
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ll A, B;
    ll result = max(A, B);
    cin >> A >> B;
    // Pretty much Least Common Multiple
    for (int i = 1; i <= B; i++) {
        // If we multiply up to any number that is divisble by B, we've found our LCM
        if ((A * i) % B == 0) {
            result = A * i;
            break;
        }
    }
    cout << result << endl;
    return 0;
}

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

int main()
{
    int n, m, tmp;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> tmp;
        n -= tmp;
        if(n < 0){
            n = -1;
            break;
        }
    }

    cout << n << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(a);i<=(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(b);i>=(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

void solve(){
    ll n,W;cin>>n>>W;
    vl dp(W+1);
    rep(i,n){
        ll v,w;cin>>v>>w;
        fore(j,w,W)chmax(dp[j],dp[j-w]+v);
    }
    cout<<dp[W]<<endl;
}

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



Measured memory_bytes: 3296
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=100005;
struct edge{int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int sg[MAXN];
void dfs(int x,int fa)
{
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)dfs(y,x),sg[x]^=(sg[y]+1);
	}
}
int n;
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);
	}dfs(1,0);
	puts(sg[1]?"Alice":"Bob");
	return 0;
}


Measured memory_bytes: 7936
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int inf = 1001001001;
int main(){
  int a,b,c,x,y;
  cin >> a >> b >> c >> x >> y;
  int ans = inf;
  rep(i,max(x,y)+1){
    int nc = 2*i;
    int na = max(0,x-i);
    int nb = max(0,y-i);
    ans = min(ans,nc*c+na*a+nb*b);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import collections
N = int(input())
List=[input() for i in range(N)]
 
c = collections.Counter(List)
c_sorted = sorted(c.items(), key=lambda x:x[1],reverse=True)
 
maxCount = c_sorted[0][1]
keys = [k for k, v in c.items() if v ==maxCount]
keys.sort()
for s in keys:
    print(s)

Measured memory_bytes: 47632
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, d, s = 0; 
    float sum = 0;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        sum += a[i];
    }
    sum /= n;
    if (sum - floor(sum) <= 0.5) d = floor(sum);
    else d = ceil(sum);
    for (int i = 0; i < n; ++i)
        s += (a[i] - d) * (a[i] - d);
    cout << s;
}

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

int main() {
    int n;
    cin >> n;
    double cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 != 0) {
            cnt++;
        }
    }
    double ans;
    ans = cnt / n;
    cout << ans << endl;
    return 0;
    }

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main
{
	private void solve()throws IOException
	{
		int n=nextInt();
		int m=nextInt();
		Fenwick ans=new Fenwick(m);
		Pair list[]=new Pair[n+1];
		for(int i=1;i<=n;i++)
		{
			int l=nextInt();
			int r=nextInt();
			list[i]=new Pair(l,r);
			ans.update(1,r-l+1,1);
		}
		Arrays.sort(list,1,n+1,new Comparator<Pair>(){
			public int compare(Pair a,Pair b){
				return a.size-b.size;
			}
		});
		Fenwick dp=new Fenwick(m);
		for(int i=1,j=1;i<=m;i++)
		{
			while(j<=n && list[j].size<i)
			{
				dp.update(list[j].l,list[j].r,1);
				j++;
			}
			for(int k=i;k<=m;k+=i)
				ans.update(i,i,dp.read(k));
		}
		for(int i=1;i<=m;i++)
			out.println(ans.read(i));
	}
	class Pair{
	    int l,r,size;
	    Pair(int a,int b){
	        l=a;
	        r=b;
	        size=r-l+1;
	    }
	}
	class Fenwick
	{
		int tree[],n;
		Fenwick(int n)
		{
			tree=new int[n+1];
			this.n=n;
		}
		int read(int i){
			int ret=0;
			while(i>0){
				ret+=tree[i];
				i-=i&(-i);
			}
			return ret;
		}
		
		void update(int i,int diff){
			while(i<=n){
				tree[i]+=diff;
				i+=i&(-i);
			}
		}
		void update(int l,int r,int diff)
		{
			update(l,diff);
			update(r+1,-diff);
		}
	}

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

	public void run()throws IOException
	{
		br=new BufferedReader(new InputStreamReader(System.in));
		st=null;
		out=new PrintWriter(System.out);

		solve();
		
		br.close();
		out.close();
	}
	public static void main(String args[])throws IOException{
		new Main().run();
	}
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	String nextToken()throws IOException{
		while(st==null || !st.hasMoreTokens())
		st=new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	String nextLine()throws IOException{
		return br.readLine();
	}
	int nextInt()throws IOException{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws IOException{
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws IOException{
		return Double.parseDouble(nextToken());
	}
}

Measured memory_bytes: 69260
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool lessPair(const pair<int, int>& l, const pair<int, int>& r)
{
    return l.second < r.second;
}

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

    vector<pair<int, int>> A(N);
    for (int i = 0; i < N; i++) {
        A[i].first = i + 1;
        cin >> A[i].second;
    }

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

    for (int i = 0; i < N-1; i++) {
        cout << A[i].first << " ";
    }
    cout << A[N-1].first << endl;
}

Measured memory_bytes: 1664
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,W = map(int,input().split())

# v に対する min(w) を持つ
max_v = 0
INF = 10 ** 18
dp = np.full(1000 * N + 1, INF, dtype=np.int64)
dp[0] = 0
for _ in range(N):
    w,v = map(int,input().split())
    np.minimum(dp[v:max_v + v + 1], dp[:max_v + 1]+w, out = dp[v:max_v + v + 1])
    max_v += v

answer = np.where(dp <= W)[0].max()
print(answer)

Measured memory_bytes: 21272
n = int(input())
A = list(map(int,input().split()))

CumSum = [0] * n
c = 0
for i,a in enumerate(A):
    c += a
    CumSum[i] = c
# 最初が正の場合
total_cost = 0
c_sum = 0
for i,a in enumerate(A):
    c_sum += a
    if i % 2 ==0:
        if c_sum > 0:
            continue
        total_cost += abs(c_sum)+ 1
        c_sum = 1
        continue

    if c_sum < 0:
        continue
    total_cost += abs(c_sum)+ 1
    c_sum = -1
# 最初が負の場合
total_cost2 = 0
c_sum = 0
for i,a in enumerate(A):
    c_sum += a
    if i % 2 ==0:
        if c_sum < 0:
            continue
        total_cost2 += abs(c_sum)+ 1
        c_sum = -1
        continue

    if c_sum > 0:
        continue
    total_cost2 += abs(c_sum)+ 1
    c_sum = 1
print(min(total_cost,total_cost2))



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

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> P(N);
    rep(i,N) cin >> P[i];
    vector<long double> D(N);
    rep(i,N){
            long long d = P[i] * (P[i] + 1) / 2;
            D[i] = d / (long double)P[i];
    }
    long double sum = 0;
    rep(i,K) sum += D[i];
    long double res = sum;
    rep(i,N-K){
        sum += D[i+K];
        sum -= D[i];
        res = max(res,sum);
    }
    cout << setprecision(12) << res << endl;
    
    return 0;
}

Measured memory_bytes: 4096
// nanika.cpp : テ」ツつウテ」ツδウテ」ツつステ」ツδシテ」ツδォ テ」ツつ「テ」ツδ療」ツδェテ」ツつアテ」ツδシテ」ツつキテ」ツδァテ」ツδウテ」ツ?ョテ」ツつィテ」ツδウテ」ツδ暗」ツδェ テ」ツδ敕」ツつ、テ」ツδウテ」ツδ暗」ツつ津・ツョツ堙ァツセツゥテ」ツ?療」ツ?セテ」ツ?凖」ツ??
//

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main()
{
	deque<int> nums;
	int N,A,B,C,D[100];
	cin>>N>>A>>B>>C;
	for(int i=0; i<N;i++){
		cin >> D[i];
		nums.push_back(D[i]);
	}
	sort(nums.begin(),nums.end());
	deque<int>::iterator it = nums.begin();
	int l=0;
	while( it != nums.end() )
	{
		
		//cout << *it << endl;
		D[N-l-1]=*it;
		++it;
		l++;
	}
	int nPc,nPri;
	nPc=C;
	nPri=A;
	
	//cout << nPc/nPri << endl;
	for(int i=0;i<N;i++){
	if( 1.0*nPc/nPri<=1.0*(nPc+D[i])/(nPri+B))
	{
		nPc+=D[i];
		nPri+=B;
	}
	}
	cout << nPc/nPri << endl;
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vector<vi> a(2,vi(n));
    rep(i,2)rep(j,n){
        cin>>a[i][j];
    }
    int ans=0;
    rep(i,n){
        int sum=0;
        rep(j,n){
            if (j<=i) sum+=a[0][j];
            if (j>=i) sum+=a[1][j];
        }
        chmax(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}


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

string str;
int p;

int negate_(int f) { return 2 - f; }

int add(int a, int b) {
  if (a == 2 || b == 2) {
    return 2;
  } else if (a == 0 && b == 0) {
    return 0;
  } else {
    return 1;
  }
}
int mult(int a, int b) {
  if (a * b == 0) {
    return 0;
  } else if (a * b == 4) {
    return 2;
  } else {
    return 1;
  }
}

int P, Q, R;

int term(char c) {
  switch (c) {
    case 'P':
     return P;
    case 'Q':
      return Q;
    case 'R':
      return R;
  }
}

int formula() {
  if (str[p] == '-') {
    p++; // read -
    int f = formula();
    return negate_(f);
  } else if (isdigit(str[p])) {
    int f = str[p] - '0';
    p++; // read [0-2]
    return f;
  } else if (isalpha(str[p])) {
    int f = term(str[p]);
    p++; // read [P-R]
    return f;
  } else {
    p++; // read (
    int a = formula();
    if (str[p] == '*') {
      p++; // read *
      int b = formula();
      p++; // read )
      return mult(a, b);
    } else {
      p++; // read +
      int b = formula();
      p++; // read )
      return add(a, b);
    }
  }
}

int main() {
  while (cin >> str and str != ".") {
    p = 0;
    int ans = 0;
    for (P = 0; P < 3; P++) 
      for (Q = 0; Q < 3; Q++)
        for (R = 0; R < 3; R++)
          if (p = 0, formula() == 2) 
            ans++;
    cout << ans << endl;
  }
}

Measured memory_bytes: 1196
y,n=gets.split

y=y.to_i
n=n.to_i
b=-1

nn=n/1000

key=nn-y

i=key/9

loop{
  if i<0
    puts "-1 -1 -1"
    exit
end
  
   if key-9*i>=0 &&   (key-9*i)%4==0
       b=(key-9*i)/4
       break
    else 
        i=i-1
    end
    
    
    
}

if y-i-b>=0 
    puts "#{i} #{b} #{y-i-b}"
else
     puts "-1 -1 -1"
end
    






Measured memory_bytes: 3836
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


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


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


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


n = I()
a = list(MI())

if 0 in a:
    print("0")
    exit()
else:
    ans = 1
    for i in a:
        if i == 1:
            continue
        ans *= i
        if ans > 10 ** 18:
            print("-1")
            exit()

print(ans)


Measured memory_bytes: 40188
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
bool is_prime(long long n)
{
    for (long long i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return n != 1;
}
int main()
{
    ll x;
    cin >> x;
    rp(i, x, 1000000)
    {
        if (is_prime(i))
        {
            cout << i;
            break;
        }
    }
}

Measured memory_bytes: 256
using System;

class sample
{
		public static void Main()
		{
				double H = Convert.ToDouble(Console.ReadLine());
				double W = Convert.ToDouble(Console.ReadLine());
				double N = Convert.ToDouble(Console.ReadLine());

				if(H<=W)
				{
						Console.WriteLine(Math.Ceiling(Convert.ToDouble(N/W)));
				}
				else
				{
						Console.WriteLine(Math.Ceiling(Convert.ToDouble(N/H)));
				}
		}
}





Measured memory_bytes: 11220
#include <stdio.h>

int min(int x, int y)
{
  if (x < y) {
    return x;
  } else {
    return y;
  }
}

int main(void)
{
  int a, b, c, d;
  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  scanf("%d", &d);

  printf("%d\n", min(a, b) + min(c, d));
}

Measured memory_bytes: 128
while 1:
	N = int(raw_input())
	if N == 0:
		break
	x = [0]
	y = [0]
	put = [(-1,0),(0,-1),(1,0),(0,1)]
	for i in range(1, N):
		n,d = map(int, raw_input().split(" "))
		x.append(x[n]+put[d][0])
		y.append(y[n]+put[d][1])
	print max(x)-min(x)+1, max(y)-min(y)+1

Measured memory_bytes: 4228
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <math.h>

int main(int argc, char* argv[]){
  int n;
  std::vector<long long> a;
  std::ios::sync_with_stdio(false);
  std::cin >> n;

  long long x = 1;
  for (int i = 0; i < n; i++){
    long long a_i;
    std::cin >> a_i;
    a.push_back(a_i);
    x *= a_i; 
  }
  long long sum = 0;
  for (auto& a_i : a){
//    sum += (x - 1) % a_i;
    sum += a_i - 1;
  }
  std::cout << sum << std::endl;
  return 0;  
}


Measured memory_bytes: 888
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = II()
s,t = Line(M,2)

pt = edges_to_pt(s,t,N,True)

dp = [0]*N

for i in range(N-1)[::-1]:
    val_all = 0
    for p in pt[i]:
        val_all += dp[p]+1
    if len(pt[i])==0:
        continue
    else:
        dp[i] = val_all/len(pt[i])

ans = dp[0]

for i in range(N-1)[::-1]:
    if len(pt[i])==1:
        continue
    dp2 = [0]*N
    max_val = -1
    for p in pt[i]:
        if dp[p]>max_val:
            max_val = dp[p]
            max_p = p
    for j in range(i+1,N):
        dp2[j] = dp[j]
    for j in range(i+1)[::-1]:
        val_all = 0
        for p in pt[j]:
            if j==i and p==max_p:
                continue
            else:
                val_all += dp2[p]+1
        if len(pt[j])==0:
            continue
        else:
            if j!=i:
                dp2[j] = val_all/len(pt[j])
            else:
                dp2[j] = val_all/(len(pt[j])-1)
    if dp2[0]<ans and dp2[0]!=0.0:
        ans = dp2[0]

print(ans)

Measured memory_bytes: 89984
#include<cstdio>
#include<cstring>

int a,b,c,n;
int I[1000],J[1000],K[1000],R[1000];
int dat[300];

int main(){
    while(scanf("%d%d%d",&a,&b,&c),a||b||c){
        memset(dat,0,sizeof(dat));
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            int x,y,z,w;
            scanf("%d%d%d%d",&x,&y,&z,&w);
            I[i]=x-1;
            J[i]=y-1;
            K[i]=z-1;
            R[i]=w;
        }
        for(int i=0;i<n;i++){
            if(R[i]==1){
                dat[I[i]]=dat[J[i]]=dat[K[i]]=1;
            }
        }
        for(int i=0;i<n;i++){
            if(R[i]==0){
                if(dat[I[i]]+dat[J[i]]+dat[K[i]]==2){
                    if(dat[I[i]]==0)dat[I[i]]=-1;
                    if(dat[J[i]]==0)dat[J[i]]=-1;
                    if(dat[K[i]]==0)dat[K[i]]=-1;
                }
            }
        }
        for(int i=0;i<a+b+c;i++){
            if(dat[i]==0)puts("2");
            if(dat[i]==1)puts("1");
            if(dat[i]==-1)puts("0");
        }
    }
}
    

Measured memory_bytes: 0
/*
ID: jerrywcy
LINK: https://atcoder.jp/contests/abc126/tasks/abc126_e
LANG: C++
STATUS:
*/
#include <bits/stdc++.h>

#define init(array,x) memset(array,x,sizeof(array))
#define pb push_back

using namespace std;

const int inf=0x3f3f3f3f;

int n,m;
int fa[100010];
bool mk[100010];
int ans;

int find(int x){
	if (fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}

void join(int x,int y){
	x=find(x);y=find(y);
	if (x==y)return ;
	fa[x]=y;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=n;i++)fa[i]=i;
	for (int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		join(x,y);
	}
	
	for (int i=1;i<=n;i++){
		int f=find(i);
		if (!mk[f]){
			ans++;
			mk[f]=1;
		}
	}
	cout<<ans<<endl;

	return 0;
}



Measured memory_bytes: 1152
N = int(input())
S = list(input())
R = []
G = []
B = []
Reval = {}
Geval = {}
Beval = {}
for i in range(N):
    if S[i] == "R":
        R.append(i)
        Reval[2*i] = 2*i
    elif S[i] == "G":
        G.append(i)
        Geval[2*i] = 2*i
    elif S[i] == "B":
        B.append(i)
        Beval[2*i] = 2*i
count = len(R)*len(G)*len(B)

for a in R:
    for b in G:
        if (a + b) in Beval:
            count -= 1
for a in G:
    for b in B:
        if (a + b) in Reval:
            count -= 1
for a in B:
    for b in R:
        if (a + b) in Geval:
            count -= 1
print(count)

Measured memory_bytes: 9492
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <list>
#include <stack>
#include <queue>
#include <utility>

using namespace std;

#define ll long long
#define ld long double
#define MOD 1000000007
#define rep(i, n) for(int i = 0;i < n;i++)
#define PI 3.14159265358979323846


int main()
{

    ld a,b;
    ld x;
    cin >> a >> b >> x;
    ld v;//体積
    v = a*a*b;
    ld margin;
    ld height;
    ld rad;
    ld ans;
    if (x>=v/2)
    {
        margin = v-x;
        height = (margin/(a*a))*2;
        rad = atan(height/a);
        ans = 180.000000000*rad/PI;
    }else
    {
        height = (x/(a*b))*2;
        rad = atan(height/b);
        ans = 180*rad/PI;
        ans = 90-ans;
        //ans = ((0.5000000000-rad)/PI)*180.000000000;
    }
    //cout << height/a << endl;
    //cout << rad << endl;
    cout << setprecision(11)<< ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fly ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define ll long long
#define inf 100000000000
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;
  cin >> n;
  ll ara[n][3];
  for(int i = 0;i<n;i++){
    for(int j = 0;j<3;j++){
      cin >> ara[i][j];
    }
  }

  ll dp[n+1][3] {inf};
  dp[0][0] = ara[0][0];
  dp[0][1] = ara[0][1];
  dp[0][2] = ara[0][2];
  for(int i = 1;i<n;i++){
    dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + ara[i][0];
    dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + ara[i][1];
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + ara[i][2];
  }
  cout << max(dp[n-1][0], max(dp[n-1][1],dp[n-1][2])) << endl;

  return 0;
}


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

int main() {
  int H, W;
  cin >> H >> W;
  rep(i, W+2){
    cout << '#';
  }
  cout << endl;
  rep(i, H){
    cout << '#';
    rep(j, W){
      char a;
      cin >> a;
      cout << a;      
    }
    cout << '#' << endl;
  }
  rep(i, W+2){
    cout << '#';
  }
  cout << endl;
}


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

int gcd(long a,long b){
	long v0=a,v1=b,v2=a%b;
	while(v2!=0){
		v0=v1;
		v1=v2;
		v2=v0%v1;
	}
	return v1;
}

int main(){
	int N;
	long X;
	cin>>N>>X;
	vector<long>x;
	x.push_back(X);
	long tmp;
	for(int i=0;i<N;++i){
		cin>>tmp;
		x.push_back(tmp);
	}
	sort(x.begin(),x.end());
	vector<long>x_sa;
	for(int i=1;i<x.size();++i){
		x_sa.push_back(x[i]-x[i-1]);
	}
	//x_saの最大公約数を求める
	long ans=x_sa[0];
	for(int i=1;i<x_sa.size();++i){
		ans=gcd(ans,x_sa[i]);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 2548
while True:
    a, op, b = (input().split())
    x = int(a)
    y = int(b)
    if op == "?":
        break
    elif op == "-":
        print(x - y)
    elif op == "+":
        print(x + y)
    elif op =="*":
        print (x * y)
    elif op == "/":
        print (x // y)

Measured memory_bytes: 7588
#include<stdio.h>

int main() {
    long long t1, t2;
    long long a1, a2;
    long long b1, b2;

    scanf("%lld %lld", &t1, &t2);
    scanf("%lld %lld", &a1, &a2);
    scanf("%lld %lld", &b1, &b2);

    if (a1 < b1) {
        long long p;
        p = a1; a1 = b1; b1 = p;
        p = a2; a2 = b2; b2 = p;
    }

    long long da = t1 * a1 + t2 * a2;
    long long db = t1 * b1 + t2 * b2;
    if (da == db) {
        puts("infinity");
        return 0;
    }
    else if (da > db) {
        puts("0");
        return 0;
    }

    long long maxd = t1 * (a1 - b1);
    printf("%lld\n", 1 + (long long) ((maxd - 1) / (db - da)) * 2 + (maxd % (db - da) == 0 ? 1 : 0));
    return 0;
}


Measured memory_bytes: 128
let dfs t n k =
  let p = Array.make n false in
  let d = Array.make n (-1) in
  let rec doit x z =
    if p.(x) then ()
    else begin
      p.(x) <- true;
      d.(x) <- z;
      List.iter (fun (y, c) -> doit y (z + c)) t.(x);
    end in
  doit k 0;
  d

let () =
  let n = Scanf.scanf "%d " (fun i -> i) in
  let t = Array.make n [] in
  for _ = 1 to n - 1 do
    let a, b, c = Scanf.scanf "%d %d %d " (fun a b c -> a, b, c) in
    let a, b = a - 1, b - 1 in
    t.(a) <- (b, c) :: t.(a);
    t.(b) <- (a, c) :: t.(b);
  done;
  let q, k = Scanf.scanf "%d %d " (fun q k -> q, k) in
  let k = k - 1 in
  let d = dfs t n k in
  for _ = 0 to q - 1 do
    let x, y = Scanf.scanf "%d %d " (fun x y -> x, y) in
    let x, y = x - 1, y - 1 in
    Printf.printf "%d\n" (d.(x) + d.(y))
  done

Measured memory_bytes: 23552
X,N=map(int,input().split())
if N==0:
  print(X)
  exit()
p=list(map(int,input().split()))
ans=0
check=100
for i in range(101+1):
  if i in p:
    continue
  if abs(X-i)<check:
    check=abs(X-i)
    ans=i
print(ans)


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

int main(){
   int n;
   cin >> n;
   set<string> box;
   rep(i,n) {
      string s;
      cin >> s;
      box.insert(s);
   }



   cout << box.size() << endl;
   return 0;  
}

Measured memory_bytes: 19264
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define append push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> h(n);
  rep(i,0,n) cin >> h[i];
  sort(all(h));
  int ans = 1000000000;
  rep(i,0,n-k+1) {
    ans = min(h[i+k-1] - h[i],ans);
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
    ll N;
    cin >> N;
    if(N % 2 == 1){
        cout << 0 << "\n";
        return 0;
    }
    N /= 2;
    ll ans = 0;
    while (N){
        N /= 5;
        ans += N;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
n=int(input())
T=[int(input()) for i in range(n)]
def gcd(a,b):
    if b==0:
        return(a)
    else:
        return(gcd(b,a%b))
def lgm(a,b):
    return(a*b//(gcd(a,b)))
if n==1:
    print(T[0])
else:
    ans=T[0]
    for i in range(1,n):
        ans=lgm(ans,T[i])
    print(ans)

Measured memory_bytes: 3064
#include<stdio.h>

#define max 500001

int heap[max],heapsize;

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i+1;
}

void maxheapify(int A[],int i){
  int largest,leftN,rightN,tmp;
  leftN=left(i);
  rightN=right(i);
  if(leftN<=heapsize && A[leftN]>A[i]){
    largest=leftN;
  }
  else {
    largest=i;
  }
  if(rightN<=heapsize && A[rightN]>A[largest]){
    largest=rightN;
  }
  if(largest!=i){
    tmp=A[largest];
    A[largest]=A[i];
    A[i]=tmp;
    maxheapify(A,largest);
  }
}

void Buildmaxheap(int A[]){
  int i;
  for(i=heapsize/2;i>=1;i--){
    maxheapify(A,i);
  }
}

int main(){
  int i;
  
  scanf("%d",&heapsize);
  for(i=1;i<=heapsize;i++){
    scanf("%d",&heap[i]);
  }
  
  Buildmaxheap(heap);
  
  for(i=1;i<=heapsize;i++){
    printf(" %d",heap[i]);
  }
  printf("\n");
  
  return 0;
}

Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std; void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); }
template <typename Type> void print_collection(Type coll) { cout << "{ "; for (auto e : coll) cout << e << ' '; cout << "}\n"; }
void solve() {
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    int m = 0, l = 0, r = 0, used = 0;
    while (r < n) {
        //cout << l << ' ' << r << ' ' << m << '\n';
        if (s[r] == '0' and (r == 0 or s[r-1] == '1')) {
            if (used < k) {
                ++used;
            } else {
                while (s[l] == '1') ++l;
                while (s[l] == '0') ++l;
            }
        }
        ++r;
        m = max(m, r - l);
    }
    cout << m << '\n';
}
/*
11101010110011
i      j
*/


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<char,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n-1){
        int x;
        cin >> x;

        a[x-1]++;
    }

    for (int i = 0; i < n; ++i) {
        cout << a[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3988
# by the authority of GOD
import os,sys
from io import BytesIO, IOBase


def main():
    mod=10**9+7
    s=int(input())
    if s<3:
        print(0)
    else:

        dp=[0]*(s+1)
        dp[0]=1

        for i in range(2,s+1):
            for j in range(i):
                if abs(j-i)>=3:
                    dp[i]=(dp[i]+dp[j])%mod
        print(dp[s])

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Measured memory_bytes: 67156
from math import atan2, degrees

a, b, x = map(int, input().split())

s = x/a
if s >= a*b/2:
    z = 2*b - 2*x/a**2
    ans = degrees(atan2(z, a))
else:
    z = 2*x/(a*b)
    ans = 90-degrees(atan2(z, b))
print(ans)


Measured memory_bytes: 2940
import qualified Data.Vector         as V
import qualified Data.Vector.Mutable as VM
import Control.Applicative
import Control.Monad
import Data.IORef
import Data.Char
import Data.List

-- 1 BubbleSort(C, N)
-- 2   for i = 0 to N-1
-- 3     for j = N-1 downto i+1
-- 4       if C[j].value < C[j-1].value
-- 5         C[j] と C[j-1] を交換
-- 6
-- 7 SelectionSort(C, N)
-- 8   for i = 0 to N-1
-- 9     minj = i
-- 10    for j = i to N-1
-- 11      if C[j].value < C[minj].value
-- 12        minj = j
-- 13    C[i] と C[minj] を交換

bubbleSort :: [(Char, Int)] -> IO [(Char, Int)]
bubbleSort xs = do
  aVec <- V.thaw $ V.fromList xs
  let len = length xs - 1
  forM_ [0 .. len] $ \i -> do
    forM_ [len, len - 1 .. (i + 1)] $ \j -> do
      (_, v1) <- VM.read aVec j
      (_, v2) <- VM.read aVec (j - 1)
      when (v1 < v2) $ VM.swap aVec j (j - 1)
  V.toList <$> V.freeze aVec

selectionSort :: [(Char, Int)] -> IO [(Char, Int)]
selectionSort xs = do
  aVec <- V.thaw $ V.fromList xs
  let len = length xs - 1
  forM_ [0 .. len] $ \i -> do
    minj <- newIORef i
    forM_ [i .. len] $ \j -> do
      (_, v1) <- VM.read aVec j
      k  <- readIORef minj
      (_, v2) <- VM.read aVec k
      when (v1 < v2) $ writeIORef minj j
    k <- readIORef minj
    VM.swap aVec i k
  V.toList <$> V.freeze aVec

test :: [(Char, Int)] -> [(Char, Int)]
test xs = sortBy (\ (_, a) (_, b) -> compare a b) xs

main :: IO ()
main = do
  _  <- getLine
  xs <- map (\[a, b] -> (a, digitToInt b)) . words <$> getLine
  let tl = test xs
  bl <- bubbleSort xs
  display bl tl
  sl <- selectionSort xs
  display sl tl
    where
      display xs ys = do
        putStrLn $ unwords $ map (\(a, b) -> (a : show b)) xs
        putStrLn $ if xs == ys
          then "Stable"
          else "Not stable"



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

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

using namespace std;

const int inf = 1e9 + 7;

int main() {
	int n,w;
	int dp[101][10001];
	cin >> n >> w;
	int val[n],wei[n];
	for(int i=0;i<n;i++){
		cin >> val[i] >> wei[i];
	}
	for(int j=0;j<=w;j++){
		dp[n][j] = 0;
	}
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<=w;j++){
			if(j<wei[i]){
				dp[i][j] = dp[i+1][j];
			}
			else{
				dp[i][j] = max(dp[i+1][j],dp[i+1][j-wei[i]] + val[i]);
			}
		}
	}
	cout << dp[0][w] << endl;
}


Measured memory_bytes: 7020
//Daniel Grzegorzewski
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

const int N = (int)1e5 + 10;
const int MOD = (int)1e9 + 7;

int n, dp[N][2];
VI child[N];
bool vis[N];

void dfs(int v) {
  vis[v] = true;
  int sum[2] = {1, 1};
  for (int x: child[v])
    if (!vis[x]) {
      dfs(x);
      sum[0] = (sum[0]*(dp[x][0]+dp[x][1]))%MOD;
      sum[1] = (sum[1]*dp[x][0])%MOD;
    }
  dp[v][0] = sum[0];
  dp[v][1] = sum[1];
}

signed main() {
  init_ios();
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    child[x].PB(y);
    child[y].PB(x);
  }
  dfs(1);
  cout<<(dp[1][0]+dp[1][1])%MOD<<"\n";
}

Measured memory_bytes: 11264
#include<stdio.h>
struct Node {
  int p,l,r;
};
void print(int);
#define NIL -1
struct Node T[100005];
int rec(int,int);
int n,F[100005];
int main(){
  scanf("%d",&n);
  int i,j,k,s,v,h,m;
  for(i=0;i<n;i++){
    T[i].p=NIL;
    T[i].l=NIL;
    T[i].r=NIL;
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&k,&s);
    for(j=0;j<s;j++){
      scanf("%d",&v);
      if(j==0){
	T[k].l=v;
      }else{
	T[h].r=v;
      }
      h=v;
      T[v].p=k;
    }
  }
  for(i=0;i<n;i++){
    if(T[i].p==NIL)m=i;
  }
  rec(m,0);
  for(i=0;i<n;i++){
    print(i);
  }
  return 0;
}
int rec(int u,int s){
  F[u]=s;
  if(T[u].r!=NIL) rec(T[u].r,s);
  if(T[u].l!=NIL) rec(T[u].l,s+1);
}
void print(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",F[u]);
  if(T[u].p==NIL)printf("root, ");
  else if(T[u].l==NIL)printf("leaf, ");
  else printf("internal node, ");
  printf("[");
  for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
    if(i)printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}		    



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

int n;
int a[201010];
vector<vector<int>> to;
vector<bool> visited;
vector<int> LIS;
int ans[201010];

const int INF = 1LL << 60;

void dfs(int pos){
  visited[pos] = true;
  // LIS更新
  int itr = lower_bound(LIS.begin(),LIS.end(),a[pos] ) - LIS.begin();
  int origin = LIS[itr];
  LIS[itr] = a[pos];
  
  int res = lower_bound( LIS.begin(),LIS.end(),INF) - LIS.begin();
  res--;
  
  ans[pos] = res;
  
  
  if(false){ //ここ間違い
    ans[pos] = itr;
  }
  
  for(auto r : to[pos] ){
    if( visited[r] ){ continue; } 
    
    dfs(r);
  }
  
  LIS[itr] = origin; //巻き戻し
  
  return ;
}
    

signed main(void){
  cin >> n;
  for(int i = 0; i < n; i++){ 
    cin >> a[i];
  }
  to.resize(n);
  
  visited = vector<bool> ( n, false );
  
  for(int i = 0; i < n-1; i++){ 
    int u,v; cin >> u >> v; u--; v--;
    to[u].push_back(v);
    to[v].push_back(u);
  }
  
  LIS = vector<int> (n,INF);
  
  dfs( 0 );
  
  for(int i = 0; i < n; i++){ 
    cout << ans[i]+1 << endl;
  }
  
  return 0;
} 

Measured memory_bytes: 27556
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

int main(){
  int A, B;
  cin >> A >> B;
  if(A + B < 10)
    cout << A + B << endl;
  else
    cout << "error" << endl;
  return 0;
}


Measured memory_bytes: 256