akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX:usize = 100006;
#[allow(dead_code)]
const INF_U32:u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32:i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64:u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64:i64 = 1 << 62;


fn main() {
    let n:usize = read();
    let mut a:Vec<u32> = (0..n).map(|_| read()).collect();
    a.sort();

    println!("{}", a[n-1]-a[0]);

}


Measured memory_bytes: 4476
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long ll;



int main()
{
    int a,b,c,k;
    scanf("%d %d %d %d",&a,&b,&c,&k);
    
    while(b<=a)
    {
        b=2*b;
        k=k-1;
    }
    while(c<=b)
    {
        c=2*c;
        k=k-1;
    }

    if(k<0)
    {
        printf("No\n");
    }
    else
    {
        printf("Yes\n");
    }
    
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,j,k,c,d[101][101],a,b,n,m;
	pair<int,pair<int,int> >  v[100005];
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		if(i==j)
		d[i][j]=0;
		else
		d[i][j]=1000000;
	}
	for(i=0;i<m;i++)
	scanf("%d %d %d",&a,&b,&c),d[a][b]=c,d[b][a]=c,v[i]=make_pair(a,make_pair(b,c));
	c=0;
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	}
	//printf("%d\n",c);
	c=0;
	//printf("%d\n",d[2][3]);
	for(i=0;i<m;i++)
	{
	//	printf("%d %d %d\n",v[i].first,v[i].second.first,d[v[i].first][v[i].second.first]);
		if(d[v[i].first][v[i].second.first]<v[i].second.second)
		c++;
	}
	printf("%d",c);
}


Measured memory_bytes: 1408
module Main where

import Data.Functor
import Data.List

main :: IO ()
main = do
  { [ss] <- getInts
  ; let (mm,s) = ss `divMod` 60
  ; let (h,m)  = mm `divMod` 60
  ; putStrLn (intercalate ":" (map show [h,m,s]))
  }

getInts :: IO [Int]
getInts = do
  { line <- getLine
  ; let ints = map readInt (words line)
  ; return ints
  }

getInts' :: IO [Int]
getInts' = do
  { line <- getLine
  ; return (map readInt (words line))
  }

getInts'' :: IO [Int]
getInts'' = map readInt . words <$> getLine


readInt :: String -> Int
readInt = read

Measured memory_bytes: 3540
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    [n, a, b, c, d] = li()
    s = input()
    if c < d:
        route = s[a:d - 1]
        # print(route)
        possible = True
        before = "."
        for si in route:
            if before == si == "#":
                possible = False
                break
            before = si
    elif d < c:
        route = s[a:d - 1]
        # print(route)
        possible = True
        before = "."
        for si in route:
            if before == si == "#":
                possible = False
                break
            before = si

        cross_possible = False
        route = s[b:d + 1]
        # print(route)
        before = [s[b - 2], s[b - 1]]
        for si in route:
            before.append(si)
            before = before[-3:]
            if before[0] == before[1] == before[2] == ".":
                cross_possible = True
        possible = possible and cross_possible

    if possible:
        print("Yes")
    else:
        print("No")

# C<Dの場合
# 目的地までの間に岩が２連続で存在しなければ可能
# D<Cの場合
# BとCの間に岩がないマスが３連続で存在すれば可能


Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n,v;
    cin>>n;
    vector<pair<ll,ll>> vo(1e5+1),ve(1e5+1);
    for(ll i=0;i<n;i++){
        cin>>v;
        if(i%2){
            vo[v].first++;
            vo[v].second=v;
        }else{
            ve[v].first++;
            ve[v].second=v;
        }
    }
    sort(all(vo),greater<pair<ll,ll>>());
    sort(all(ve),greater<pair<ll,ll>>());
    if(vo[0].second!=ve[0].second) cout<<n-(vo[0].first+ve[0].first)<<endl;
    else cout<<n-max(vo[0].first+ve[1].first,vo[1].first+ve[0].first)<<endl;
    return 0;
}

Measured memory_bytes: 3328
int main(void)
{
  int a,b,sum=0;
  scanf("%d %d",&a,&b);
  if(a>=0&&b>=0)
  {
    if(a<=1||b<=1) sum=a+b;
    else sum=a*b;
  }
  else if(a<0&&b<0) sum=a*b;
  else
  {
    if(a>b) sum=a-b;
    else sum=a+b;
  }
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 128
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    P = map(int, input().split())

    min = 2 * (10 ** 5) + 10
    c = 0
    for i in P:
        if i <= min:
            c += 1
            min = i
    print(c)

if __name__ == '__main__':
    main()

Measured memory_bytes: 17780
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
#define dcml(n) fixed<<setprecision(n)
//CONST
//------------------------------------------
const ll INF=1010000000000000017LL;
const ll MOD=1000000007LL;
const ld EPS=1e-12;
const ld PI=3.14159265358979323846;
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define  FORS(i,m,n) for(ll (i)=(m);   (i)<=(n); (i)++)
#define  RFOR(i,m,n) for(ll (i)=(n)-1; (i)>=(n); (i)--)
#define RFORS(i,m,n) for(ll (i)=(n);   (i)>(n);  (i)--)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
#define WREPS(i,in,j,jn) REPS(i,in)REPS(j,jn)
//-----------------------------------------
//namespace
using namespace std;
//ライブラリはここに
//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
vi dx8={-1,-1,-1,0,0,1,1,1};
vi dy8={-1,0,1,-1,1,-1,0,1};
//-----------------------------------------
ll w,h;
int c[50][50];
bool is;
void dfs(int x,int y){
    if(c[x][y]==0)return;
    c[x][y]=0;
    //cout<<x<<y<<"->";
    is=true;
    REP(i,8){
        int X=x+dx8[i],Y=y+dy8[i];
        if(0<=X&&X<h and 0<=Y&&Y<w){
            if(c[X][Y]==0)continue;
            dfs(X,Y);
        }
    }
}
int main(void){
    while(cin>>w>>h and !(w==0&&h==0) ){
        //cout<<"w:"<<w<<"h:"<<h<<"\n";
        int cnt=0;
        REP(i,h)REP(j,w)cin>>c[i][j];
        REP(i,h)REP(j,w){
            is=false;
            dfs(i,j);//cout<<"\n";
            if(is)cnt++;
        }
        cout<<cnt<<"\n";
    }
}


Measured memory_bytes: 3224
#include <iostream>
#include<math.h>
#include<string>
#include<iomanip>
#include <limits>
using namespace std;

int main()
{
int a,b,c; cin>>a>>b>>c;
if(a!=b&&a!=c&&b!=c)
    cout<<"3";
else if(a==b&&b!=c)
    cout<<"2";
else if(b==c&&c!=a)
    cout<<"2";
else if(c==a&&b!=a)
    cout<<"2";
else
    cout<<"1";
}

Measured memory_bytes: 3616
#include <stdio.h>
int main(){
    long long a,b = 0;
    scanf("%lld",&a);
    scanf("%lld",&b);
    long long aanswer = a%2;
    long long banswer = b%2;
  if(a != 1 && b != 1){
    if(aanswer == 0 && banswer == 0){
        printf("%lld",a*b/2);
    }
    else if(aanswer == 0 || banswer == 0){
        printf("%lld",a*b/2);
    }else if(aanswer != 0 && banswer != 0){
        long long answer = (a*b+1)/2;
        printf("%lld",answer);
    }
  }else{
    printf("%lld",1);
  }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n%10==2||n%10==4||n%10==5||n%10==7||n%10==9)cout<<"hon";
    else if(n%10==3)cout<<"bon";
    else cout<<"pon";
    return 0;
}


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

float l[10], sum[11];
int main() {
	int v1, v2;
	while (scanf("%f,%f,%f,%f,%f,%f,%f,%f,%f,%f,%d,%d", &l[0], &l[1], &l[2], &l[3], &l[4], &l[5], &l[6], &l[7], &l[8], &l[9], &v1, &v2) != EOF) {
		float cnt = 0;
		rep(i, 10) {
			sum[i] = cnt;
			cnt += l[i];
		}
		sum[10] = cnt;
		cout << lower_bound(sum, sum + 11, (sum[10] / (v1 + v2))*v1) - sum << endl;
	}
	return 0;
}

Measured memory_bytes: 3232
// doot diddly donger cuckerino Hahahahahah


#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vi = vector<int>;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = acos(-1);

template <typename T> inline T mini(T& x, T y) { return x = min(x, y); }
template <typename T> inline T maxi(T& x, T y) { return x = max(x, y); }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template <typename T, typename U>
std::ostream& operator<<(std::ostream& stream, const pair<T, U>& p) {
  return stream << p.first << " " << p.second;
}
template <typename T>
std::ostream& operator<<(std::ostream& out, const vector<T>& vec) {
  for (const T& x: vec) out << x << ' ';
  return out;
}
template <typename T>
std::istream& operator>>(std::istream& in, vector<T>& vec) {
  for(auto& x: vec) in >> x;
  return in;
}
// @formatter:on


class EDoubleFactorial {
public:
  
  void solve(std::istream& cin, std::ostream& cout) {
    ll n;
    cin >> n;
    if (n & 1) {
      cout << 0 << endl;
      return;
    }
    ll five = 5;
    long long fives = 0;
    while (n / 2 / five) {
      fives += n / 2 / five;
      five *= 5;
    }
    cout << fives << endl;
  }
};

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
	EDoubleFactorial solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3656
#include<stdio.h>

int main()
{
	int a[4][3][10];

	for(int i = 0; i < 4; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			for(int k = 0; k < 10; k++)
			{
				
				a[i][j][k] = 0;
				
			}
		}
	}
	int n;
	scanf("%d", &n);
	while(n--)
	{
		int b, f, r, v;
		scanf("%d %d %d %d", &b, &f, &r, &v);
		a[b-1][f-1][r-1] += v;
		
	}
	for(int i = 0; i < 4; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			for(int k = 0; k < 10; k++)
			{
				printf(" %d", a[i][j][k]);
			
				
			}
			printf("\n");
		}
	
		if(i != 3)
		printf("####################\n");
	}
	
	return 0;
}


Measured memory_bytes: 2752
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define re(i,n,a) for(int i=a;i<n;i++)
using namespace std;
typedef pair<int,int>P;
int w,h,a[16][16],md=14,b[16][16],s1,s2;
bool used[16][16];
string s[16];
int dx[]={-1,-1,-1,0,0,0,1,1,1};
int dy[]={-1,0,1,-1,0,1,-1,0,1};
vector<P>v;
map<int,int>m;
int greedy(){
  int res=0,sum=0;
  memset(a,0,sizeof(a));
  memset(used,0,sizeof(used));
  r(i,h){
      r(j,w){
        if(s[i][j]=='0'){
        r(k,9){
          int y=i+dy[k];
          int x=j+dx[k];
          if(y<0||x<0||y>=h||w>=x)continue;
          used[y][x]=1;
        }
      }
      else if(s[i][j]=='.')used[i][j]=1;
      else if(isdigit(s[i][j]))a[i][j]=s[i][j]-'0',res+=a[i][j];
      }
    }
    while(res>0){
      memset(b,0,sizeof(b));
      int f=0;
      r(i,h)r(j,w)if(!used[i][j]){
        int p=0;
        r(k,9){
          int y=i+dy[k];
          int x=j+dx[k];
          if(y<0||x<0||y>=h||x>=w)continue;
          if(a[y][x])p++;
        }
        b[i][j]=p;
        f=max(p,f);
      }
      int i=0,j=0;
      r(kk,h*w){
        i=(i+1)%h;
        j=(j+1)%w;
        if((unsigned int)rand()%5==0)i=(unsigned int)rand()%h;
        if((unsigned int)rand()%5==0)j=(unsigned int)rand()%w;
        if(used[i][j])continue;
        if(b[i][j]==f){
          int p=0;
          r(k,9){
          int y=i+dy[k];
          int x=j+dx[k];
          if(y<0||x<0||y>=h||x>=w)continue;
          if(a[y][x])p++;
        }
        if(p==f){
          r(k,9){
            int y=i+dy[k];
            int x=j+dx[k];
            if(y<0||x<0||y>=h||x>=w)continue;
            if(used[y][x])continue;
            if(a[y][x])a[y][x]--;
          }
          sum++;
          res-=f;
          used[i][j]=1;
        }
      } 
    }}
    m[sum]++;
    return sum;
}
int main(){
  while(cin>>h>>w,w){
    int ans=1e9;
    r(i,h)cin>>s[i];
    r(t1,2){
      r(i,h/2)swap(s[i],s[h-1-i]);
      r(t2,2){
        r(i,h)reverse(s[i].begin(),s[i].end());
        r(t3,2){
          string t[16];
          r(i,16)t[i]="";
          r(i,w)r(j,h)t[i]+=s[j][i];
          swap(h,w);
          r(i,w)s[i]="";
          r(i,h)s[i]=t[i];
          int pp;
          set<int>st;
          m.clear();
          r(t4,120){
            //srand((unsigned int)time(NULL));
            pp=greedy();
            st.insert(pp);
            ans=min(ans,pp);
          }
          //cout<<m[ans]<<endl;
          if(st.count(ans)&&ans%md==0)
            if(rand()%2&&ans&&m[ans]>=0&&m[ans]<=100)ans--;
        }
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 3036
N, K = map(int, input().split())

h = list(map(int, input().split()))

dp = [-1] * N

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        if i+j >= N:
            break
        cost = abs(h[i] - h[i+j]) + dp[i]
        if dp[i+j] == -1 or cost < dp[i+j]:
            dp[i+j] = cost

print(dp[N-1])


Measured memory_bytes: 52448
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int n, m, q;
vector<int> a, b, c, d;
int ans;
void dfs(vector<int> A, int n, int m)
{
    if (A.size() == n + 1) {
        int now = 0;
        for (int i = 0; i < q; i++) {
            if (A[b[i]] - A[a[i]] == c[i]) now += d[i];
        }
        ans = max(ans, now);
        return;
    }
    A.push_back(A.back());
    while (A.back() <= m) {
        dfs(A, n, m);
        A.back()++;
    }
}
int main()
{
    cin >> n >> m >> q;
    a = b = c = d = vector<int>(q);
    for (int i = 0; i < q; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; }
    dfs(vector<int>(1, 1), n, m);
    cout << ans << endl;
    return 0;
}

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

 
int main() {
   
   ll n,m,i,j;
   cin>>n>>m;
   char o[n][m];
   ll dp[n][m];
   for(i=0;i<n;i++)
   {
       for(j=0;j<m;j++)
       {
           cin>>o[i][j];
       }
   }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(o[i][j]=='#')
                {
                    dp[i][j]=0;
                    continue;
                }
                if(i==0 && j==0 )
                    dp[i][j]=1;
                if(i==0 && j>0 && dp[i][j-1]>0)
                    dp[i][j]=1;
                else if(i==0 && j>0 && dp[i][j-1]==0)
                    dp[i][j]=0;
                if(j==0 && i>0 && dp[i-1][j]>0)
                 dp[i][j]=1;
                else if(j==0 && i>0 && dp[i-1][j]==0)
                 dp[i][j]=0;
              
            }
        }
        for(i=1;i<n;i++)
        {
            for(j=1;j<m;j++)
            {
                if(o[i][j]=='#')
                    dp[i][j]=0;
                else if(dp[i-1][j]==0 || dp[i][j-1]==0 )
                        dp[i][j]=(max(dp[i-1][j]%1000000007,dp[i][j-1]%1000000007))%1000000007;
                else
                    dp[i][j]=(dp[i-1][j]%1000000007+dp[i][j-1]%1000000007)%1000000007;
            }
        }
       cout<<dp[n-1][m-1]%1000000007<<endl;
    
}

Measured memory_bytes: 12324
import bisect
import math

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

As.sort()
a = As[-1]
j = bisect.bisect_left(As, a/2)

if j == 0 or a - As[j] > As[j-1]:
  print("{} {}".format(a, As[j]))
else:
  print("{} {}".format(a, As[j-1]))

Measured memory_bytes: 62704
n = int(open(0).read())

for i in range(1, n+1):
    x = i
    if (x % 3) == 0:
        print(" {}".format(i), end="")
        continue
    while True:
        if (x % 10) == 3:
            print(" {}".format(i), end="")
            break
        x //= 10
        if not x:
            break
print()



Measured memory_bytes: 5872
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int

struct Union{
  vector<ll> par;
  Union(ll a){
  par=vector<ll>(a,-1);
  }
  ll find(ll a){
    if(par[a]<0){
      return a;
    }
    else{
      return par[a]=find(par[a]);
    }
  }
  bool same(ll a,ll b){
    return (find(a)==find(b));
  }
  ll size(ll a){
    return -par[find(a)];
  }
  void unite(ll a,ll b){
    ll c=find(a),d=find(b);
    if(c==d)
      return;
    if(size(c)<size(d)){
      swap(c,d);
    }
    par[c]+=par[d];
    par[d]=c;
  }
};
ll Nagaemon1;
void swap(ll i,ll j){
  Nagaemon1=i;
  i=j;
  j=Nagaemon1;
}
int main(){
  ll a,b,c,k;
  cin >> a >> b >> c >> k;
  if(k<a)cout << k;
  else if(k<=a+b)cout << a;
  else cout << a-(k-a-b);
}

Measured memory_bytes: 3628
N,M=gets.split.map(&:to_i)

idxs = [0]
arr = [0]
M.times do
  a = gets.to_i
  c = gets.split.inject(0) {|n,i| n + (1 << (i.to_i-1)) }

  idxs.length.times do |i|
    idx = idxs[i]
    n = arr[idx|c]
    if n.nil?
      idxs << (idx|c)
      arr[idx|c] = arr[idx]+a
    elsif arr[idx]+a < n
      arr[idx|c] = arr[idx]+a
    end
  end
end

puts(arr[2**N-1]||-1)


Measured memory_bytes: 1916
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    int A[N];
    map<int, int> cnt;
    for (int i = 0; i < N; i++) { 
        cin >> A[i];
        cnt[A[i]]++;
    }
    if (cnt[0] == N) {
        cout << "Yes" << endl;
        return 0;
    }
    if (N % 3 != 0) {
        cout << "No" << endl;
        return 0;
    }
    vector<int> all;
    for (auto p : cnt) {
        for (int i = 0; i < p.second / (N / 3); i++) {
            all.push_back(p.first);
        }
    }
    if (all.size() == 3 && (all[0] ^ all[1] ^ all[2]) == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 4224
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <bitset>
#include <limits>

using ll = long long int;
using ul = unsigned long long int;

namespace lamlib
{
	// EPSITON
	constexpr double epsilon = std::numeric_limits<double>::epsilon();
	// Absolute
	template<class T> inline T abs(const T &a){ return (a>0) ? a : -a; }
	// Digit
	ul inline digit(const ul &num){ return static_cast<ul>(std::log10(num+epsilon))+1; }
	// GCD: a > b
	ul gcd(ul a,ul b) { return (!b) ? a : gcd(b,a%b); }
	
	/* string */
	inline ul same_char_count(const std::string s,const char &ch){ return std::count(std::cbegin(s),std::cend(s),ch); }
}

int main(int argc,char *argv[])
{
	ul n;
	std::cin >> n;
	
	std::vector<std::string> s(n);
	for(ll i = 0;i < n;++i) std::cin >> s[i];

	ul ans = 0;
	std::unordered_map<std::string, ll> m;
	for(ll i = 0;i < n;++i)
	{
		std::sort(s[i].begin(),s[i].end());
		if(m[s[i]] > 0) ans += m[s[i]];
		++m[s[i]];
	}

	std::cout << ans << std::endl;

	return 0;
}

Measured memory_bytes: 17700
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 200005;
const ll MOD = 998244353;

int n,tot;
int d[MAXN];

ll ans;
ll cnt[MAXN];

string s;

int main()
{
	cin >> n >> s;
	int pw2 = 1,N = n;
	while (~N & 1)
	{
		pw2 <<= 1;
		N >>= 1;
	}
	for (int i = 1;i <= N;i++)
		if (N % i == 0)
		{
			d[++tot] = pw2 * i;
			for (int j = 0;j < d[tot];j++)
				cnt[tot] = (cnt[tot] * 2 + s[j] - '0') % MOD;
			cnt[tot]++;
			for (int j = 0;j < s.size();j++)
				if (s[j] != ((s[j % d[tot]] - '0') ^ ((j / d[tot]) & 1)) + '0')
				{
					if (s[j] < ((s[j % d[tot]] - '0') ^ ((j / d[tot]) & 1)) + '0')
						cnt[tot]--;
					break;
				}
		}
	for (int i = 1;i <= tot;i++)
		for (int j = i - 1;j >= 1;j--)
			if (d[i] % d[j] == 0)
				(cnt[i] -= cnt[j]) %= MOD;
	for (int i = 1;i <= tot;i++)
		(ans += d[i] * 2 * cnt[i]) %= MOD;
	printf("%lld\n",(ans + MOD) % MOD);
	return 0;
}

Measured memory_bytes: 640
import math
n=int(input())
nn=str(n)
# c=int(math.log10(n)//1)+1

a=list(range(1,n+1))


# b=[[[] for _ in range(10)] for __ in range(10)]
b=[[[0] for _ in range(10)] for __ in range(10)]


# for i in range(1,10):
#     for j in range(1,10):
#         box=0
#         for h in a:
#             if str(h)[0]==str(i) and str(h)[-1]==str(j):
# #                 box.append(h)
#                 box+=1
#         b[i][j]=box
        
        
        
for h in a:
    x=int(str(h)[0])
#     print(x)
    y=int(str(h)[-1])
    b[x][y][0]+=1



# b=[[[] for _ in range(10)] for __ in range(9)]

ans=0
for i in range(1,10):
    for j in range(1,10):
        ans+=(b[i][j][0])*(b[j][i][0])
print(ans)

Measured memory_bytes: 10868
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*) array, (T*) (array + N), val);
}
pii Dir[8] = { //?§????
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};
#define int ll
#define pii pll

signed main() {
	int n, m;

	scnaf("%lld %lld", &n, &m);
	vector<int> h(n);
	REP(i, n) {
		scanf("%lld", &h[i]);
	}
	vector<vector<int>> g(n);
	vector<int> inc(n);
	REP(i, n - 1) {
		if (h[i] > h[i + 1]) {
			g[i].push_back(i+1);
			inc[i + 1]++;
		}
	}
	rep(i, 1, n) {
		if (h[i] > h[i - 1]) {
			g[i].push_back(i - 1);
			inc[i - 1]++;
		}
	}
	priority_queue<pii,vector<pii>, greater<pii>> que;
	REP(i, n) {
		if (!inc[i])
			que.push({m-h[i], i });
	}
	int ans = 0;
	while (que.size()) {
		pii cur = que.top();
		ans = cur.first;
		que.pop();

		for (auto itr : g[cur.second]) {
			inc[itr]--;
			if (!inc[itr]) {
				que.push({cur.first + m-h[itr], itr});
			}
		}
	}

	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 9916
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();

    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut g = vec![vec![0; n]; n];

    for i in 0..n {
        for j in 0..n {
            g[i][j] = itr.next().unwrap().parse().unwrap();
        }
    }
    let mut ok = true;
    let mut need = vec![vec![true; n]; n];
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if i == j || j == k || k == i {
                    continue;
                }
                if g[i][j] > g[i][k] + g[k][j] {
                    ok = false;
                }
                if g[i][j] == g[i][k] + g[k][j] {
                    need[i][j] = false;
                }
            }
        }
    }
    if ok {
        let mut ans = 0i64;
        for i in 0..n {
            for j in 0..i {
                ans += if need[i][j] { g[i][j] } else { 0 };
            }
        }
        println!("{}", ans);
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 3708
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  int i,j,n=1000000,x;
  vector<int> a(1000010,1);
  for(i=2;i<=n;i++){
    if(a[i]==0){
      continue;
    }
    for(j=i*2;j<=n;j=j+i){
      a[j]=0;
    }
  }
  vector<int> y;
  for(i=2;i<=n;i++){
    if(a[i]==1){
      y.push_back(i);
    }
  }
  while(1){
    cin >> n >> x;
    if(n==0 && x==0){
      return 0;
    }
    int b[35];
    vector<int> dp(1000100,0);
    for(i=0;i<n;i++){
      cin >> b[i];
    }
    dp[0]=1;
    for(i=1;i<=n;i++){
      for(j=0;j<=x;j++){
        if(j-b[i-1]>=0){
          dp[j]=max(dp[j],dp[j-b[i-1]]);
        }
        else{
          dp[j]=dp[j];
        }
      }
    }
    int ans=-1;
    for(i=0;i<y.size();i++){
      if(y[i]>x){
        break;
      }
      if(dp[y[i]]==1){
        ans=y[i];
      }
    }
    if(ans==-1){
      cout << "NA" << endl;
    }
    else{
      cout << ans << endl;
    }
  }
  return 0;
}


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

using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;

const int mn = 2e5 + 5;
const int mod = 2019;

int l, r;

int main() {
#ifdef trote
    freopen("../1.txt", "r", stdin);
#endif
    scanf("%d%d", &l, &r);
    ll ans = 1e9;
    if (r - l >= 2018) {
        ans = 0;
    } else {
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                ans = min(i % mod * (ll) j % mod, ans);
            }
        }
    }
    printf("%d\n", ans);


    return 0;
}

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


int main(){

  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: 2692
S = list(input())
K = int(input())

ans = [0] * 3
for i in (0, 1, 2):
    # print("#", ans)
    ans_tmp = 0
    S_tmp = S * (i + 1)
    cnt = 0
    for j, Sj in enumerate(S_tmp):
        if j == 0:
            cnt = 1
        else:
            if Sj == Sj_prev:
                cnt += 1
            else:
                ans_tmp += cnt // 2
                cnt = 1
        #
        Sj_prev = Sj
    else:
        ans_tmp += cnt // 2
    #
    ans[i] = ans_tmp

print(ans[0] + (K // 2) * (ans[1] - ans[0]) + ((K - 1) // 2) * (ans[2] - ans[1]))

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

#define int long long
struct Edge{
    int from, to, cap, flow, index;
    Edge(int f, int t, int c, int ff, int i):
        from(f), to(t), cap(c), flow(ff), index(i){}
};

const int inf = 1e11;
struct MaxFlow{
    int N;
    vector<vector<Edge>>G;
    vector<Edge*> dad;
    vector<int> Q;

    MaxFlow(int n):N(n), G(n), dad(n), Q(n){}

    void AddEdge(int from, int to, int cap){
        G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
        if(from == to) G[from].back().index++;
        G[to].push_back(Edge(to, from, 0, 0, G[from].size()-1));
    }

    long long BlockingFlow(int s, int t){
        fill(dad.begin(), dad.end(), (Edge*)nullptr);
        //dad[s] = &G[0][0]-1;
        dad[s] = &G[s][0]-1;
        int head = 0, tail = 0;
        Q[tail++] = s;
        while(head<tail){
            int x = Q[head++];
            for(int i=0;i<G[x].size(); ++i){
                Edge &e = G[x][i];
                if(!dad[e.to] && e.cap-e.flow>0){
                    dad[e.to] = &G[x][i];
                    Q[tail++] = e.to;
                }
            }
        }
        if(!dad[t]) return 0;
        long long totflow = 0;
        for(int i=0;i<G[t].size();++i){
            Edge*start = &G[G[t][i].to][G[t][i].index];
            int amt = inf;
            for(Edge*e = start; amt&&e!=dad[s];e=dad[e->from]){
                if(!e){
                    amt = 0;
                    break;
                }
                amt = min(amt, e->cap-e->flow);
            }
            if(amt == 0) continue;
            //cerr << "path: ";
            for(Edge*e = start; amt && e!=dad[s]; e = dad[e->from]){
                //cerr << e->to << " -- " << e->from <<"   ";
                e->flow+=amt;
                G[e->to][e->index].flow-=amt;
            }
            //cerr << " : " << amt << "\n";
            totflow+=amt;
        }
        return totflow;
    }
    long long get_max_flow(int s, int t){
        long long ret = 0;
        while(long long flow = BlockingFlow(s, t)){
            ret+=flow;
        }
        return ret;
    }

};

using ll = long long;

signed main()
{
    #ifdef LOCAL_RUN
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int TTT; cin >>TTT;
    while(TTT--){
    #endif // LOCAL_RUN

    //CODE
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &e:a) cin >> e;
    MaxFlow fl(n+3);
    const int s = n+1, t = n+2;
    ll out = 0;
    for(int i=0;i<n;++i){
        if(a[i]>0){
            out+=a[i];
            fl.AddEdge(s, i, a[i]);
        } else {
            fl.AddEdge(i, t, -a[i]);
        }
        for(int j=i+2;j<=n;++j){
            if(j%(i+1) == 0){
                fl.AddEdge(j-1, i, inf);
            }
        }
    }
    ll flo = fl.get_max_flow(s, t);
    cout << out - flo << "\n";


    #ifdef LOCAL_RUN
    }
    #endif // LOCAL_RUN
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }

using ll = long long;
const ll mod = LLONG_MAX;

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

  while(1){
    if(a+1!=b)a++;
    else a--;

    if(a==0){
      cout<<"Borys"<<endl;
      return 0;
    }

    if(b-1!=a)b--;
    else b++;

    if(b==n+1){
      cout<<"Alice"<<endl;
      return 0;
    }

  }


}


Measured memory_bytes: 256
S = input()

flg = 0
while flg==0:
    if S[len(S)-5:]=="dream":
        S = S[:len(S)-5]
    elif S[len(S)-7:]=="dreamer":
        S = S[:len(S)-7]
    elif S[len(S)-5:]=="erase":
        S = S[:len(S)-5]
    elif S[len(S)-6:]=="eraser":
        S = S[:len(S)-6]
    else:
        flg = 1
    if len(S)==0:
        flg = 0
        break
if flg==0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3188
def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    count = 1
    tmp_min = p_list[0]
    for i in range(1, len(p_list)):
        tmp_min = min(tmp_min, p_list[i])
        if tmp_min == p_list[i]:
            count += 1

    print(count)

if __name__ == '__main__':
    main()


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

int gcd(int x, int y);

const int INF = 1001001001;

//mint�p�̕ϐ� (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) {
        int num;
        cin >> num;
        a[i] = num - 1;
    }
    vector<vector<int> > love(n, vector<int> (0));
    int ans = 0;
    rep(i, n) {
        bool capple = find(love[i].begin(), love[i].end(), a[i]) != love[i].end();
        if (capple)
            ans++;
        else
            love[a[i]].emplace_back(i);
    }
    
    cout << ans << endl;
    return 0;
}
/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
vector<int> vec; // int型の配列変数vecを宣言
 
  
 long int num1=0;
 long int num2=0;
 cin >> num1 >> num2;
 if(num1==1){
     cout << 1 << endl;
 }
 else if(num2==1){
      cout << 1 << endl;
 }
 else if(num1*num2%2==0){
     cout << num1*num2/2 << endl; // 1つめである25を出
 }
 else{
  cout << num1*num2/2+1 << endl; // 1つめである25を出力
 }
  
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<ll, II> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 100010;
const int MAXM = 100010;
const int MAXK = 510;

int f[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    FOR(i,1,m) {
        int u, v;
        cin >> u >> v;
        f[u]++;
        f[v+1]--;
    }
    FOR(i,1,n) f[i] += f[i-1];
    int res = 0;
    FOR(i,1,n)
        if (f[i] == m) res++;
    cout << res;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

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; }

// s = "112223" -> [[1,2],[2,3],[3,1]]
vector<pair<int,int>> rle (vector<int> x) {
  vector<pair<int,int>> res;
  int n = (int)x.size();
  for (int i = 0; i < n;) {
    int j = i;
    int cnt = 0;
    while (j < n && x[j] == x[i]) {
      ++j;
      ++cnt;
    }
    //res.emplace_back(x[i], cnt);
    res.emplace_back(cnt, x[i]);
    i = j;
  }
  return res;
}

int main () {
  int n;
  cin >> n;
  vi v(n);
  rep(i,n) cin >> v[i];
  
  if (count(rng(v),v[0]) == v.size()) {
    cout << n/2 << endl;
    return 0;
  }

  vi ve, vo;
  rep(i,n) {
    if (i%2 == 0) ve.pb(v[i]);
    else vo.pb(v[i]); 
  }

  sort(ve.begin(), ve.end());
  sort(vo.begin(), vo.end());

  auto pe = rle(ve);
  auto po = rle(vo);

  sort(pe.rbegin(), pe.rend());
  sort(po.rbegin(), po.rend());

  int ne;
  int no;

  if (pe[0].se != po[0].se) {
    ne = pe[0].fi;
    no = po[0].fi;
  }
  else {
    if (pe[1].fi >= po[1].fi) {
      ne = pe[1].fi;
      no = po[0].fi;
    }
    else {
      ne = pe[0].fi;
      no = po[1].fi;
    }
  }

  int ans = n - (ne + no);
  cout << ans << endl;
  return 0;
}

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

using namespace std;
int sum(int x)
{
    int s = 0;
    while(x)
    {
        s += x % 10;
        x /= 10;
    }
    return s;
}
int  main()
{
    int n;
    int mi = 9999999999;
    cin >> n;
    for(int i = 1; i <= n / 2; i++)
    {
        if(mi > sum(i) + sum(n - i))
        {
            mi = sum(i) + sum(n - i);
        }
    }
    cout << mi << endl;
}

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

using i32 = int_fast32_t;
using i64 = int_fast64_t;

int main() {
    i64 n;
    cin >> n;
    vector<i64> a(n);
    map<i64, i64> c;
    for (auto& e : a) {
        cin >> e;
        c[e]++;
    }

    i64 ans = 0;
    for (auto& e : c) {
        ans += e.second * (e.second - 1) / 2;
    }

    for (auto& e : a) {
        cout << ans - (c[e] * (c[e]-1) / 2) + ((c[e]-1) * (c[e]-2) / 2) << endl;
    }
}


Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll mod = 1e9 + 7;

int n;
vector<ll> a;


ll cost(bool sign) {
  ll cst = 0, rs = 0;
  for (int i = 0; i < n; i++) {
    rs += a[i];
    if (rs == 0) {
      ll x = sign ? 1 : -1;
      cst += 1;
      rs += x;
    } else {
      if ((rs > 0) == true && !sign) {
        cst += rs + 1;
        rs = -1;
      } else if ((rs > 0) == false && sign) {
        cst += abs(rs) + 1;
        rs = 1;
      }
    }
    sign = !sign;
  }
  return cst;
}

int main() {
  cin >> n;
  a.resize(n);
  for (ll &i : a) cin >> i;
  ll ans = cost(true);
  ans = min(ans, cost(false));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4004
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

template<typename T> vector<T> make_vector(size_t sz){
	return vector<T>(sz);
}

template<typename T,typename... Ts> 
auto make_vector(size_t sz, Ts... ts){
	return vector<decltype(make_vector<T>(ts...))>(sz, make_vector<T>(ts...));
}

template<typename T,typename U,typename... V> 
typename enable_if<is_same<T, U>::value!=0>::type 
fill_value(U &u, const V... v){
	u=U(v...);
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_value(U &u, const V... v){
	for(auto &e:u){
		fill_value<T>(e,v...);
	}
}

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 pid_t pid = getpid();
// Problem Specific Parameter:


vector<int> ans;

string compress(const string &t) {
	string ret = "";

	for(auto &elem: t) {
		if (elem == 'R') {
			ret += elem;
		} else {
			if(ret.size() and ret.back() == 'S') {
				ret.pop_back();
			} else {
				ret += elem;
			}
		}
	}

	return ret; 
}

int n, fd[12], td[12];

void rec(int digit, string t) {
	if(digit == n) {
		int from = 0, to = 0;
		rrep(i, n) {
			from = 3 * from + fd[i];
			to = 3 * to + td[i];
		}
		ans[from] = to;
		return;
	}


	rep(d, 3) {
		int cur_d = d;

		string nxt_t = "";
		for(auto &elem: t) {
			if(elem == 'S') {
				cur_d = (3 - cur_d) % 3;
				nxt_t += elem;
			} else {
				cur_d++;
				if(cur_d == 3) {
					nxt_t += elem;
					cur_d = 0;
				}
			}
		}

		fd[digit] = d;
		td[digit] = cur_d;
		rec(digit + 1, compress(nxt_t));
	}
}

int main(void){
	cin >> n;
	int all = 1;
	rep(loop, n) all *= 3;

	ans = vector<int>(all);

	string t;
	cin >> t;

	rec(0, compress(t));

	rep(i, all) cout << (i?" ":"") << ans[i];
	cout << endl;

	return 0;
}

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

int main() {
  int n;
  cin >> n;
  int vec[32] = {1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51};
  cout << vec[n-1] << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Abc163B
    {
        public static void Main()
        {
            var nm = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var n = nm[0];
            var m = nm[1];
            var sum = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).Sum();
            Console.WriteLine(n < sum ? -1 : n - sum);
        }
    }
}


Measured memory_bytes: 20408
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define ld long double
#define FOR(i,a,n) for (int i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (int i=(n);i>=(a);--i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define MINUS(a) memset((a),-1,sizeof((a)))
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// I am questioning life and universe and 
// everything else after looking at this

void solve(){
    ll N,K; cin>>N>>K;

    cout<<N-K+1<<endl;
}  

signed main(){

   FastRead;    

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


    ll t;
    t = 1; 
    // cin>>t;
    FOR(i,1,t){
        solve();
    }
}




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

int main(){
    int N, X, T;
    cin >> N >> X >> T;

    if(N%X==0){
        cout << (N/X)*T << endl;
    }else{
        cout << (N/X + 1)*T << endl;    
    }
    
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define double long double
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define rsort(a) sort(all(a),greater<>())
#define debg(a) cout<<#a<<" "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> V;
const long long MOD=1000000007;
const long long INF = 1e18;
clock_t time_ini = clock();
double time_diff(){
  ll time_tmp = clock();
  const double time = static_cast<double>(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0;
  return time;
}
#define saiaku if(time_diff() > 1990)
vector <ll> dp;

// const long long MOD = 2;

void solve(long long N, std::vector<long long> A){
  ll cnt=0, cnt_min=INF;
  for (ll i = 0; i < N; i++) {
    while (A[i]%2 == 0)
    {
      cnt++;
      A[i] /= 2;
    }
    if (cnt < cnt_min) { cnt_min = cnt; }
    cnt = 0;
  }
  cout << cnt_min << "\n";
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 256
import collections as c
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
n,l = ip()
ans = 0
k=abs(l)
for i in range(l,l+n):
    ans+=i
    if abs(i) < abs(k):
        k = i
ans -= k
print(ans)

Measured memory_bytes: 3316
// -- 霊長類の競プロ
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <numeric>

using namespace std;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    double ans = 0;
    
    cin >> N;
    
    vector<double> v(N);
    
    for(int i=0;i<N;i++){
        cin >> v.at(i);
    }
    
    sort(v.begin(),v.end());
    
    // evaluate
    ans = (v[0] + v[1]) / 2;
    for(int i=2;i<N;i++){
        ans = (ans+v[i]) / 2;
    }
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256