akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<stdlib.h>
using namespace std;
long long euclid(long long x, long long y);
int main(){
   long long A,B,C,D;
    cin>>A>>B>>C>>D;
    long long E,F,G,H,I,J;
 
    E=B/C;
    F=B/D;
    G=B/(C*D/euclid(C,D));
    H=(A-1)/C;
    I=(A-1)/D;
    J=(A-1)/(C*D/euclid(C,D));
    cout<<(B-A+1)-(((E+F)-G)-((H+I)-J));
}

long long euclid(long long x,long long y){
    if(y>x){
        long long  tmp=x;
        x=y;
        y=tmp;
    }
    long long r=x%y;
    while(r!=0){
        x=y;
        y=r;
        r=x%y;
    }
    return y;
}



/*int main(){
    long long a,b;
    cin>>a>>b;
    cout<<euclid(a,b)<<endl;
}
    */



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

using namespace std;
using ll = long long;
#define int ll

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

int MOD = 1000000007;

//二分累乗法 xのe乗
ll binpow(ll x, ll e, ll mo=MOD) {
  ll a = 1, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = (p*p) % mo; e /= 2;}
    else {a = (a*p) % mo; e--;}
  }
  return a;
}

ll combi(ll N_, ll C_, ll mo=MOD) {
  const int NUM_=1e5+10;
  static ll fact[NUM_+1]={},factr[NUM_+1]={},inv[NUM_+1]={};
  auto binpow = [&](ll x, ll e) -> ll{
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % mo; e /= 2;}
      else {a = (a*p) % mo; e--;}
    }
    return a;
  };
  if (fact[0]==0) {
    fact[0] = factr[0] = inv[0] = 1;
    FOR(i, 1, NUM_+1) fact[i] = fact[i-1] * i % MOD;
    factr[NUM_] = binpow(fact[NUM_], mo-2);
    for(int i=NUM_-1; i>=0; --i) factr[i] = factr[i+1] * (i+1) % MOD;
  }
  if(C_<0 || C_>N_) return 0;
  // 前計算 O(max(N,K)log(mod)) クエリ O(1)
  return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;
}

int dp1[3010], dp2[3010][3010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n >> MOD;

  REP(i, n+1) {
    dp2[i][0] = 1;
    FOR(j, 1, i+1) {
      dp2[i][j] = (dp2[i-1][j]*(j+1) + dp2[i-1][j-1]) % MOD;
    }
  }

  REP(i, n+1) {
    REP(j, i+1) {
      (dp1[i] += dp2[i][j] * binpow(2, (n-i)*j)) %= MOD;
    }
    (dp1[i] *= binpow(2, binpow(2, n-i, MOD-1))) %= MOD;
  }

  int ans = 0;
  REP(i, n+1) {
    (ans += (i%2?-1:1) * combi(n, i) * dp1[i]) %= MOD;
  }
  cout << (ans%MOD+MOD)%MOD << endl;

  return 0;
}


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

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

int n,a[110],ma,cnt[110];

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

	cin>>n;
	REP(i,n) {
		cin>>a[i];
		ma=max(ma,a[i]);
		cnt[a[i]]++;
	}
	FOR(i,1,(ma+1)/2) {
		if(cnt[i]!=0) {
			cout<<"Impossible"<<endl;
			return 0;
		}
	}
	if(cnt[(ma+1)/2]!=(ma&1?2:1)) {
		cout<<"Impossible"<<endl;
		return 0;
	}
	FOR(i,(ma+1)/2+1,ma+1) {
		if(cnt[i]<2) {
			cout<<"Impossible"<<endl;
			return 0;
		}
	}
	cout<<"Possible"<<endl;

	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1LL<<59)

#define int ll

vector<int> makeLeft(int n, vector<int> v){
    vector<int> ret(2*n+1,0);
    
    priority_queue<int,vector<int>, greater<int>> pq;
    int sum = 0;
    rep(i,n){
        pq.push(v[i]);
        sum+=v[i];
    }
    
    ret[n] = sum;
    
    for(int i=n;i<2*n;i++){
        pq.push(v[i]);
        sum+=v[i];
        sum-=pq.top();
        pq.pop();
        ret[i+1] = sum;
    }
    return ret;
}

vector<int> makeRight(int n, vector<int> v){
    vector<int> ret(3*n,0);
    
    priority_queue<int> pq;
    int sum = 0;
    for(int i=2*n;i<3*n;i++){
        pq.push(v[i]);
        sum+=v[i];
    }
    
    ret[2*n] = sum;
    
    for(int i=2*n-1;i>=n;i--){
        pq.push(v[i]);
        sum+=v[i];
        sum-=pq.top();
        pq.pop();
        ret[i] = sum;
    }
    return ret;
}


signed main(){
    int n;
    cin>>n;
    vector<int> a(3*n);
    
    rep(i,3*n)cin>>a[i];
    
    
    vector<int> left = makeLeft(n,a);
    vector<int> right = makeRight(n,a);
    
    
    int ans = -INF;
    for(int i=n;i<=2*n;i++){
        ans = max(left[i] - right[i],ans);
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 10692
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 1e6+5;
ll a[N];
ll da[N];
ll b[N];
ll db[N];
ll c[N];
ll dc[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	dc[n] = 1;
	for(int i=n-1;i>=1;i--){
		dc[i] = 1;
	}
	int j = n;
	for(int i=n;i>=1;i--){
		db[i] = db[i+1];
		while(1){
			if(j<=0)break;
			if(b[i]>=c[j])break;
			db[i]+=dc[j];
			j--;
		}
	}
	j =n;
	ll ans = 0;
	for(int i=n;i>=1;i--){
		da[i] = da[i+1];
		while(1){
			if(j<=0)break;
			if(a[i]>=b[j])break;

			da[i]+=db[j];
			j--;
		}
		ans+=da[i];
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}
/// 11000
/// 11000
/// 00111


Measured memory_bytes: 8340
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1;
#define cni cin
#define asn ans

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
//typedef unsigned int uint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

int w,h,n,ans;

main(){
    cin>>w>>h>>n;
    int e[h][w]={};
    rep(i,n){
        int x,y,a;
        cin>>x>>y>>a;
        if(a==2){
            for(int i=0;i<h;i++){
                for(int j=x;j<w;j++){
                    e[i][j]++;
                }
            }
        }else if(a==1){
            for(int i=0;i<h;i++){
                for(int j=0;j<x;j++){
                    e[i][j]++;
                }
            }
        }else if(a==4){
            for(int i=y;i<h;i++){
                for(int j=0;j<w;j++){
                    e[i][j]++;
                }
            }
        }else if(a==3){
            for(int i=0;i<y;i++){
                for(int j=0;j<w;j++){
                    e[i][j]++;
                }
            }
        }
    }
    rep(i,h){
        rep(j,w){
            //cout<<e[i][j]<<' ';
            if(e[i][j]==0)ans++;
        }
        //cout<<endl;
    }
    dans;
}



Measured memory_bytes: 384
//by tzupengwang™
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<iostream>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

ll x, y;
void init() {
  scanf("%lld%lld", &x, &y);

  if (x % y == 0) {
    printf("-1\n");
  } else printf("%lld\n", x);
}

void process() {
}

int main() {
/*
#ifdef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
  int Cases;
  scanf( "%d" , &Cases ) ;
  for ( int cases = 1 ; cases <= Cases ; cases ++ ) {
*/
    init() ;
    process() ;
/*
  }
*/
  return 0 ;
}

Measured memory_bytes: 384
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <math.h>
#include <cmath>
#include <set>   
#include <bitset>
//#include <boost/math/common_factor_rt.hpp>

#define ll long long
#define MAX 100000
using namespace std;
ll L = 1000000007;

int main()
{
	ll x, y;
	cin >> x >> y;
	cout << x + (y / 2) << endl;
}

int dsum(ll a) {
	int ans = 0;
	while (a != 0) {
		ans += a % 10;
		a /= 10;
	}
	return ans;
}


Measured memory_bytes: 256
import java.util.*;
public class Main { 

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();

        long gcd = gcd(a, b);
        System.out.println(factorize(gcd) + 1);
    }

    private static int factorize(long num) {
        int cnt = 0;
        for(long i = 2; i * i <= num; i++) {
            if(num % i != 0)
                continue;
            cnt++;
            while(num % i == 0) {
                num /= i;
            }
        }
        if(num != 1)
            cnt++;
        return cnt;
    }
    private static long gcd(long a, long b) {
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }

}

Measured memory_bytes: 22612
#include <iostream>
#include <string>

using namespace std;

int main(int argc, const char *argv[]) {
  string s;
  cin >> s;
  if (s == "Sunny") {
    cout << "Cloudy\n";
  } else if (s == "Cloudy") {
    cout << "Rainy\n";
  } else {
    cout << "Sunny\n";
  }

  return 0;
}

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

int main(){
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  int u = min(x, y);
  int v = max(x, y);
  int p = u * 2 * c + (x - u) * a + (y - u) * b;
  int q = v * 2 * c;
  int r = a * x + b * y;
  cout << min(p, min(q, r)) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

typedef long long int lld;
typedef unsigned long long int ulld;
const int mod = 1000000007;

using namespace std;

int Njc[10];
int n, a, b, inp[10];
char used[10];

void init() {
	int i = 1, j = 1;
	Njc[0] = 1;
	for (; j < 10; j++) {
		i *= j;
		Njc[j] = i;
	}
}

int indexof(int num) {
	int re = 0;
	for (int i = 0; i < num; i++) {
		if (!used[i])
			re++;
	}
	return re;
}

int number() {
	int re = 0;
	for (int i = 0; i < 10; i++)
		used[i] = 0;
	for (int i = 0; i < n; i++) {
		//int idxof = indexof(inp[i]);
		re += (indexof(inp[i]) - 1) * Njc[n - 1 - i];
		used[inp[i]] = 1;

		//cout << "  " << inp[i] << ":\t" << idxof << "\t" << re << endl;
	}
	return re;
}

int main(void) {
	ios::sync_with_stdio(false);
	init();
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> inp[i];
	}
	a = number();

	for (int i = 0; i < n; i++) {
		cin >> inp[i];
	}
	b = number();

	//cout << "a:" << a << endl;
	//cout << "b:" << b << endl;
	cout << abs (a - b) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
        using namespace std;
        #define ll long long int   
        # define pi 3.141592653589793238
     
     
     
          int main()
            {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

             
            ios_base::sync_with_stdio(false);
     
              cin.tie(NULL);
     
     
  
ll n,i,ans=0,d,x=0,y=0,g=0,h=0;
cin>>n;
string s,s1;
cin>>s;
for(i=0;i<n;i++)
{
if(s[i]=='W')
s1+='W';
else
s1='R'+s1;
}
for(i=0;i<n;i++)
{
if(s1[i]=='W')
{
if(s[i]!=s1[i])
x++;
}
else
{
if(s[i]!=s1[i])
y++;
}
}


cout<<min(x,y)<<"\n";


return 0;
}



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

int main() {
	string X;
	cin >> X;
	int tmp1 = 0, tmp2 = 0;
	for (char& i : X) {
		if (i == 'S') ++tmp1;
		else {
			if (tmp1 == 0) ++tmp2;
			else --tmp1;
		}
	}
	cout << tmp1 + tmp2;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define range(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, b) for (int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x) cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
	rep(i, v.size()) { os << v[i] << (i == v.size() - 1 ? "" : " "); }
	return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
	for (T& x : v) { is >> x; }
	return is;
}

const int M = 1000000007;

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

	int ans = 1;
	int f = 0;
	rep(i, n - 1) {
		int a;
		cin >> a;
		//cout << (a + 1) / 2 << ' ' << f << endl;
		if ((a + 1) / 2 <= f)
			(ans *= f + 1)%=M;
		else
			f++;
	}
	f++;

	rep(i, f) {
		ans *= i + 1;
		ans %= M;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 100005;

int p[N];
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x = find(x), y = find(y);
        if (x != y) p[x] = y;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (find(i) == i) cnt++;
    }
    cout << cnt - 1 << endl;
    return 0;
}


Measured memory_bytes: 3936
#include <bits/stdc++.h>
using namespace std;
const int N=405;
int dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
int n,m,ans=0;
char a[25][25];
int dis[N][N],id[25][25],cnt=0;
int main (){
	scanf ("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf ("%s",a[i]+1);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			id[i][j]=++cnt;
	memset (dis,0x3f,sizeof(dis));
	for (int i=1;i<=cnt;i++) dis[i][i]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (a[i][j]=='.')
				for (int k=0;k<4;k++){
					int x=i+dx[k],y=j+dy[k];
					if (x<1||y<1||x>n||y>m||a[x][y]=='#') continue;
					dis[id[i][j]][id[x][y]]=1;
				}
	for (int k=1;k<=cnt;k++)
		for (int i=1;i<=cnt;i++)
			for (int j=1;j<=cnt;j++)
				if (i==j||j==k||i==k) continue;
				else dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			if (a[i][j]=='#') continue;
			for (int x=1;x<=n;x++){
				for (int y=1;y<=m;y++){
					if (a[x][y]=='#') continue;
					ans=max(ans,dis[id[i][j]][id[x][y]]);
				}
			}
		}
	printf ("%d",ans);
	return 0;
}


Measured memory_bytes: 896
#include<stdio.h>
int main(void)
{
	int x,cnt1,cnt0;
	cnt0=0;
	cnt1=1;
	scanf("%d",&x);
	if(x==0)printf("%d\n",cnt1);
	if(x==1)printf("%d\n",cnt0);
	return 0;
}	

Measured memory_bytes: 1688
#include <iostream>
int main() {
	int S;
	std::cin >> S;
	int h = S / 60 / 60;
	int m = S / 60 - h * 60;
	int s = S - m * 60 - h * 60 * 60;
	std::cout << h << ":" << m << ":" << s << "\n";
	return 0;
}


Measured memory_bytes: 3092
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int main(){

  int a,b,c,s;
  scanf("%d %d %d",&a,&b,&c);
  
  s=a*b;
  if(s>a*c)
    s=a*c;
  if(s>b*c)
    s=b*c;
  

  printf("%d",s/2);
  
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pri 1000000007 
using namespace std;
ll power(ll x,ll y,ll p) 
		{   ll res = 1; 
		    x = x % p;    
		    while (y > 0) 
		    { 
		            if (y & 1) 
		            res = (res*x) % p; 
		        y = y>>1; // y = y/2 
		        x = (x*x) % p;   
		    } 
		    return res; 
		} 
ll nCr(ll n, ll r, ll p) 
		{  ll ze=1;
		    if(r>n)return 0;
		   for(ll i=n-r+1;i<=n;i++){
		   	ze=(ze*i)%pri;
		   	
		   }
		   for(ll j=2;j<=r;j++){
		   	ze=(ze*power(j,pri-2,pri))%pri;
		   }
		   return ze;
		} 
		 
int main() {
	ll n,m,k;
	cin>>n>>m>>k;
	ll ans=nCr(n*m-2,k-2,pri);
	ll  ans1=(ans*m)%pri;
	  ans1=(ans1*m)%pri;
	  ans1=(ans1*n)%pri;
	  ans1=(ans1*(n+1))%pri;
	  ans1=(ans1*(n-1))%pri;
	ll  ans2=(ans*n)%pri;
	  ans2=(ans2*n)%pri;
	  ans2=(ans2*m)%pri;
	  ans2=(ans2*(m+1))%pri;
	  ans2=(ans2*(m-1))%pri;
ll z= power(6,pri-2,pri);
ans1=(ans1*z)%pri;
ans2=(ans2*z)%pri;
cout<<(ans1+ans2)%pri<<endl;

	// your code goes here
	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            out.println(n * n * n);

        }

    }
}



Measured memory_bytes: 21588
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
int gcd(int a,int b){if(a<b)swap(a,b);int c=a%b;while(c!=0){a=b;b=c;c=a%b;}return b;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};


int main(){
  int k; cin>>k;
  ll ans=0;

  rep(i,k){
    rep(j,k){
      int a=gcd(i+1,j+1);
      rep(l,k){
        ans+=gcd(a,l+1);
      }
    }
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 3636
from math import sqrt as r
from itertools import combinations as C

N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

L = list(C(list(range(N)), 2))


def dis(a, b):
    ans = 0
    for i in range(D):
        ans += (X[a][i] - X[b][i])**2
    return r(ans)


ans = 0

for l in L:
    ans_ = dis(l[0], l[1])
    if str(ans_)[-1] == "0":
        ans += 1

print(ans)


Measured memory_bytes: 9096
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    int N,K;
    cin >> N >> K;
    vec<bool> s(N,false);
    rep(i,K){
        int d;
        cin >> d;
        rep(i2,d){
            int a;
            cin >> a;
            --a; 
            s[a] = true;
        }
    }
    int ans = 0;
    rep(i,N){
        if(!s[i]) ++ ans;
    }
    cout << ans << endl;
}


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

int main(){
  int n;
  cin >> n;
  int a = 0, b = 0, c = 0, d = 0;
  for(int i = 0; i < n; i++){
    char p;
    cin >> p;
    if(p == 'W') a = 1;
    if(p == 'P') b = 1;
    if(p == 'G') c = 1;
    if(p == 'Y') d = 1;
  }
  if(a + b + c + d == 4) cout << "Four" << endl;
  else cout << "Three" << endl;
}

Measured memory_bytes: 3616
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	var sum int
	for i := 1; i <= n; i++{
		if i  % 3  == 0 || i % 5 == 0{
			continue
		}
		sum += i
	}

	fmt.Println(sum)
}


Measured memory_bytes: 1752
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
using namespace std;

int main()
{
	long long int n,k,ans;cin>>n>>k;
	if(k>n)
	{
	    ans=min(k-n,n);
	    cout<<ans<<endl;
	}
	else
	{
	    if(n%k==0){cout<<0<<endl;}
	    else
	    {
	        n=n%k;
	        ans=min(k-n,n);
	        cout<<ans<<endl;
	    }
	}
}

Measured memory_bytes: 256
/*
 * atcoder/abc120/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const int MAX = 100100;
string S;
int N, counter[2] = {0};

void solve() {
  cin >> S;
  N = S.size();
  loop(n,0,N) {
    counter[S[n]-'0']++;
  }

  cout << min(counter[0], counter[1]) * 2 << endl;
}
int main() {
  // cout.precision(15);
  // cout << fixed << double

  solve();

  return 0;
}


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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;

ll fact(ll n)
{
	ll ans = 1;
	for(int i = 2; i <= n; i++)
	{
		ans = ans * i;
		ans %= mod;
	}

	return ans%mod;
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, m;
	cin >> n >> m;

	if(abs(n-m) > 1)
	{
		cout << 0 << endl;
		return 0;
	}

	if(n == m)
	{
		cout << (2*fact(n) * fact(m))%mod << endl;
		return 0;
	}

	cout << (fact(n) * fact(m))%mod << endl;
	return 0;	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll lcm(ll a, ll b){
  return a*b/gcd(a,b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

class Factrial{
public:
  vl Fac;
  Factrial(int MAX){
    Fac = vl(MAX+1);
    rep(i,MAX) {
      if(i == 0) Fac[i+1] = 1;
      else Fac[i+1] = ((i+1)*Fac[i])%MOD;
    }
  }
};

int main(){
  int n,m; cin >> n >> m;
  vl a(n);
  rep(i, n) cin >> a[i];
  rep(i,n) a[i] /= 2;

  ll X = a[0];
  rep(i,n) X = lcm(X,a[i]);

  rep(i,n) {
    if(X/a[i]%2 == 0){
      cout << 0 << endl;
      return 0;
    }
  }

  ll ans = m/X;
  ans = ans - ans/2;

  cout << ans << endl;

}

Measured memory_bytes: 1024
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
namespace fio {
	streambuf* in = cin.rdbuf();
	char bb[1000000], * s = bb, * t = bb;
#define gc() (s==t&&(t=(s=bb)+in->sgetn(bb,1000000),s==t)?EOF:*s++)
	inline int read() {
		int x = 0;
		char ch = gc();
		while (ch < 48)ch = gc();
		while (ch >= 48)x = x * 10 + ch - 48, ch = gc();
		return x;
	}
}using fio::read;
int sst[100005];
int k;
queue<int>ygy;
int main() {
	cin >> k;
	ygy.push(1), memset(sst, 0x3f, sizeof(sst)), sst[1] = 1;
	while (ygy.size()) {
		int thx = ygy.front(); ygy.pop();
		if (sst[thx] > sst[0])continue;
		if (sst[(thx + 1) % k] > sst[thx] + 1)sst[(thx + 1) % k] = sst[thx] + 1, ygy.push((thx + 1) % k);
		if (sst[thx * 10 % k] > sst[thx])sst[thx * 10 % k] = sst[thx], ygy.push(thx * 10 % k);
	}
	cout << sst[0];
}

Measured memory_bytes: 768
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String s = sc.next();

		int min = Integer.MAX_VALUE;
		int tmp;
		for (int i = 0; i < s.length() - 2; i++) {
			tmp = 0;
			tmp += Character.getNumericValue(s.charAt(i)) * 100;
			tmp += Character.getNumericValue(s.charAt(i + 1)) * 10;
			tmp += Character.getNumericValue(s.charAt(i + 2)) * 1;

			min = Math.min(min, Math.abs(753 - tmp));
		}

		System.out.println(min);
	}
}

Measured memory_bytes: 21844
S = input()

head = 0
back = 0

key = 'keyence'

for i in range(len(key)):
    if S[:i+1] == key[:i+1]:
        head = i+1

for i in range(len(key)):
    if S[len(S)-i-1:] == key[len(key)-i-1:]:
        back = i+1

if head + back >= len(key):
    print("YES")
else:
    print("NO")


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

using namespace std;

int main(void)
{
    int n, W;
    cin >> n >> W;

    int  w[n], v[n];
    int  maxv = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
        maxv += v[i];
    }

    long long dp[n + 1][maxv + 1] = {};

    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= maxv; j++)
            dp[i][j] = 2000000000;


    dp[0][0] = 0;
    long long maxtn = 0;
    for(int i = 1; i <= n; i++)
    {
        maxtn += v[i - 1];
        for(int j = 0; j <= maxtn; j++)
        {
            dp[i][j] = min(dp[i - 1][j], dp[i][j]);
            if(j >= v[i - 1])
            {
                dp[i][j] = min(dp[i - 1][j - v[i - 1]] + w[i - 1], dp[i][j]);
            }
        }
    }

    int ans = 0;

    for(int i = 0; i <= maxv; i++)
        if(dp[n][i] <= W)
            ans = max(ans, i);

    cout << ans << endl;

    /*for(int i = 0; i < n; i++)
        for(int j = 0; j <= maxv; j++)
            cout << i << " : " << j << " : " << dp[i][j] << endl;*/

    return 0;
}


Measured memory_bytes: 79104
##想定解

n=int(input())
*a,=map(int, input().split( ))

from collections import Counter

ca=Counter(a)

nn=[0]*(10**6+1)


for ai in ca:
    nn[ai]=ca[ai]

ans=0
for i in range(10**6+1):
    if nn[i]==1:
        ans+=1
    if nn[i]:
        for j in range(2*i,10**6+1,i):
            nn[j]=0
print(ans)


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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef vector<int> vi;

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

	int n, m, c;
	cin >> n >> m >> c;

	int a[30][30], b[30];
	rep(i, m){
		cin >> b[i];
	}

	rep(i, n){
		rep(j, m){
			cin >> a[i][j];
		}
	}

	int ans = 0, sum = 0;
	rep(i, n){
	sum = 0;
		rep(j, m){
			sum += a[i][j] * b[j];
		}
		if(sum+c > 0){
			ans ++;
		}
	}

	cout << ans << endl;



    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
#define N 2505
#define M 5005
int n, m, p;
int ex[N], h, t, Q[13000005], vis[N], cnt[N];
long long dis[N];
struct Graph{
	int edge, to[M], pr[M], tw[M], hd[N], vis[N];
	void addedge(int u, int v, int w){
		to[++edge] = v, tw[edge] = w, pr[edge] = hd[u], hd[u] = edge;
	}
	void dfs(int u){
		vis[u] = 1;
		for (register int i = hd[u]; i; i = pr[i])
			if (!vis[to[i]]) dfs(to[i]);
	}
}G, Gv;
int spfa(int s){
	memset(vis, 0, sizeof vis);
	memset(cnt, 0, sizeof cnt);
	memset(dis, -0x3f, sizeof dis);
	dis[s] = 0, h = 0, t = 1, Q[t] = s, vis[s] = 1, cnt[1] = 1;
	while (h < t){
		int u = Q[++h];
		vis[u] = 0;
		for (register int i = G.hd[u], v, w; i; i = G.pr[i])
			if (dis[v = G.to[i]] < dis[u] + (w = G.tw[i]) && ex[v]){
				dis[v] = dis[u] + w;
				if (!vis[v]){
					++cnt[v];
					if (cnt[v] > n) return 0;
					Q[++t] = v, vis[v] = 1;
				}
			}
	}
	return 1;
}
int main()
{
	n = read(), m = read(), p = read();
	for (register int i = 1; i <= m; ++i){
		int u = read(), v = read(), w = read() - p;
		G.addedge(u, v, w), Gv.addedge(v, u, w);
	}
	G.dfs(1), Gv.dfs(n);
	for (register int i = 1; i <= n; ++i) ex[i] = G.vis[i] && Gv.vis[i];
	if (!ex[1] || !ex[n]) return printf("0\n"), 0;
	if (!spfa(1)) printf("-1\n"); else printf("%lld\n", std :: max(0ll, dis[n]));
}


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

int main() {
  ll H,W; cin >> H >> W;
  ll ans,ans1 = INF,ans2 = INF,ans3 = INF,ans4 = INF;
  rep(i,1,H) {
    ll area1 = W * i;
    ll area2 = (H-i)/2 * W;
    ll area3 = (H-i-(H-i)/2) * W;
    ans1 = min(ans1,max(max(abs(area1-area2),abs(area2-area3)),abs(area3-area1)));
  }
  rep(i,1,H) {
    ll area1 = W * i;
    ll area2 = (W/2) * (H-i);
    ll area3 = (W- W/2) * (H-i);
    ans2 = min(ans2,max(max(abs(area1-area2),abs(area2-area3)),abs(area3-area1)));
  }
  rep(i,1,W) {
    ll area1 = H * i;
    ll area2 = (W-i)/2 * H;
    ll area3 = (W-i-(W-i)/2) * H;
    ans3 = min(ans3,max(max(abs(area1-area2),abs(area2-area3)),abs(area3-area1)));
  }
  rep(i,1,W) {
    ll area1 = H * i;
    ll area2 = (H/2) * (W-i);
    ll area3 = (H-H/2) * (W-i);
    ans4 = min(ans4,max(max(abs(area1-area2),abs(area2-area3)),abs(area3-area1)));
  }
    
  ans = min(min(ans1,ans2),min(ans3,ans4));
  cout << ans << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

const int mod = 998244353;
struct mint {
  long long x;
  mint(long long 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(long long 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;
}

// combination mod prime
struct Combination {
  vector<mint> fact, ifact;
  Combination(int n) : fact(n+1), ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} comb(200009);

int main(){
  int n,m,k;
  cin>>n>>m>>k;
  mint sum=0;
  rep2(i,k+1,n){
    sum+=comb(n-1,i)*m*mint(m-1).pow(n-i-1);
  }
  mint ans=mint(m).pow(n)-sum;
  cout<<ans<<endl;
}


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

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b){
  return a/gcd(a,b) * b;
}
ll func2(ll n){
  ll res = 0;
  while(n%2 == 0){
    n /= 2;
    res++;
  }
  return res;
}

ll zyou(ll a,ll b){//a＾b
  ll res = 1;
  for(int i = 1;i<=b;i++){
    res *= a;
  }
  return res;
}
struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t),weight(w){ }
};

typedef pair<int,int> P;
using Graph = vector<vector<Edge>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}



bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}
int dfs(int x,int y,int H,int W,vector<vector<char>> &masu){
  if(masu[x][y] == '#'){

  }
}
bool palin(string S){
  int n = S.size();
  bool flag = true;
  if(n%2 == 0){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  else if(n%2 == 1){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  return flag;
}
int main(){
  int N,K;
  cin >> N >> K;
  vector<int> l(N);
  rep(i,N){
    cin >> l[i];
  }
  sort(l.begin(),l.end());
  reverse(l.begin(),l.end());
  int sum = 0;
  for(int i = 0;i<=K-1;i++){
    sum += l[i];
  }
  cout << sum << endl;
}

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

typedef long long ll;

static const int MAX = 1e6;
static const int NIL = -1;
static const ll INF = 1<<21;
static const ll MOD = 1e9 + 7;

bool compPair(const pair<int, int>& arg1, const pair<int, int>& arg2) {
    return arg1.first > arg2.first;
}

int main(void) {
    ll x, y;
    cin >> x >> y;

    ll cnt = 3e9;

    if(x<=y) cnt = min(cnt, y-x);
    if(-1*x<=y) cnt = min(cnt, y+x+1);
    if(x<=-1*y) cnt = min(cnt, -1*y-x+1);
    if(x>=y) cnt = min(cnt, x-y+2);

    cout << cnt;

    return (0);
}


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

int main() {
  int N;
  cin >>N;
  vector<int> vec(N+1);
  for(int i=1;i<N+1;i++){
    cin >> vec.at(i);
  }

  int ans =0;
  int bottan=1;

  while(!(bottan==2)&&ans<N+1){
    bottan=vec.at(bottan);
    ans++;
  }
  if(bottan==2){
    cout << ans <<endl;
  }
  else{
    cout << -1 <<endl;
  }
}
 

Measured memory_bytes: 640
#include <cstdio>


int l, sum, m, n, j;
bool f;

int main(){
    while(scanf("%d", &l) != EOF){
        if(l == 0) break;
        sum = 0;
        f = false;
        for(int i = 0; i < 12; i++){
            scanf("%d %d", &m, &n);
            sum += m - n;

            if(sum >= l && !f){
                j = i + 1;
                f = true;
            }
        }

        if(!f) printf("NA\n");
        else printf("%d\n", j);
    }

    return 0;
}

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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int N;
  cin>>N;
  map<string,int> m;
  for(int i(0);i<N;i++){
    string s;
    cin>>s;
    m[s]++;
  }
  cout << m.size() << endl;
  return 0;
}



Measured memory_bytes: 19256
#ABC129-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[S() for i in range(h)]
V=[[0]*w for i in range(h)]
H=[[0]*w for i in range(h)]
c=0
for i in range(h):
    for j in range(w):
        if G[i][j]=="#":
            for k in range(c):
                H[i][j-k-1]=c
            c=0
        elif j==w-1:
            c+=1
            for k in range(c):
                H[i][j-k-1]=c
            c=0
        else:
            c+=1
            
for i in range(w):
    for j in range(h):
        if G[j][i]=="#":
            for k in range(c):
                V[j-k-1][i]=c
            c=0
        elif j==h-1:
            c+=1
            for k in range(c):
                V[j-k-1][i]=c
            c=0
        else:
            c+=1

ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,V[i][j]+H[i][j]-1)
print(ans)

Measured memory_bytes: 248328
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 100005
int a[maxn];
int n;

long long cal(int positive)
{
	int i;
	long long sum=0,cnt=0;
	for(i=1;i<=n;i++){
		sum+=a[i];
		if(positive){
			cnt+=sum>0?0:-sum+1;
			sum=max(sum,1ll);
		}
		else {
			cnt+=sum<0?0:sum+1;
			sum=min(sum,-1ll);
		}
		positive=!positive;
	}
	return cnt;
}

int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",a+i);
	printf("%lld",min(cal(1),cal(0)));
	return 0;
}


Measured memory_bytes: 640
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String t = sc.next();
    sc.close();
    //-97(int)
    int[] listS = new int[26];
    int[] listT = new int[26];
    boolean ans = true;
    for(int i = 0;i<s.length();i++){
      if((listS[C(s,i)] == C(t,i) || listS[C(s,i)] == 0) && (listT[C(t,i)] == C(s,i) || listT[C(t,i)] == 0)){
        listS[C(s,i)] = C(t,i);
        listT[C(t,i)] = C(s,i);
      }else{
        ans = false;
        break;
      }
    }
    System.out.println(ans ? "Yes" : "No");
  }
  
  public static int C(String s,int i){
    return (int)s.charAt(i)-97;
  }
}

Measured memory_bytes: 27132
n = int(input())
st = input()
m = ["A","B","C"]
c = 0
t = 0
for i in range(n-2):
  if st[i] == "A" and st[i+1] == "B" and st[i+2] == "C":
    c += 1
    
 
print(c)
    

Measured memory_bytes: 38488
#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
ll inf=LLONG_MAX,mod=1000000007,BS,k;

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
        #endif
        string s;cin>>s;
        ll sum=0,ma=0;
        for(ll i=0;i<3;i++){
            if(s[i]=='R')
            sum++;
            else
            ma=max(ma,sum),sum=0;
        }
        ma=max(ma,sum);
        cout<<ma;

}


Measured memory_bytes: 3644
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  Scanner sc;

  String retro(String str) {
    char[] arr = str.toCharArray();
    int len = str.length();
    for ( int i = 0; i < len / 2; ++i ) {
      char tmp = arr[ i ];
      arr[ i ] = arr[ len - 1 - i ];
      arr[ len - 1 - i ] = tmp;
    }
    return new String( arr );
  }

  void solve(String str) {
    HashSet<String> set_ = new HashSet<String>();

    for ( int i = 1; i < str.length(); ++i ) {
      String l = str.substring( 0, i );
      String r = str.substring( i, str.length() );

      HashSet<String> set = new HashSet<String>();

      set.add( l + r );
      set.add( retro( l ) + r );
      set.add( l + retro( r ) );
      set.add( retro( l ) + retro( r ) );

      set.add( r + l );
      set.add( retro( r ) + l );
      set.add( r + retro( l ) );
      set.add( retro( r ) + retro( l ) );

      set_.addAll( set );

      // debug( set );
    }

    // debug( set_ );

    System.out.println( set_.size() );
  }

  void run() {
    int m = ni();
    for ( int i = 0; i < m; ++i ) {
      solve( sc.next() );
    }
  }

  Main() {
    sc = new Scanner( System.in );
  }

  int ni() {
    return sc.nextInt();
  }

  public static void main(String[] args) {
    new Main().run();
  }

  void debug(Object... os) {
    System.err.println( Arrays.deepToString( os ) );
  }
}

Measured memory_bytes: 54656
/**
 * @brief  : c++ code for AtCoder
 * @author : rk222
 * @created: 2019.06.29 20:58:50
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

#define disp(x) cout << #x << ": " << x << endl
#define disp_vec(v)                                                                           \
    cout << #v << ":";                                                                        \
    rep(i, v.size()) cout << " " << v[i];                                                     \
    cout << endl

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/* ------------------------------------- */

vector<int> G[100010];
int ret[100010][3];

void dfs(int u, int step, int time) {
    step = (step + 1) % 3;
    if (step == 0) {
        time++;
    }
    rep(i, G[u].size()) {
        if (ret[G[u][i]][step] > time) {
            ret[G[u][i]][step] = time;
            dfs(G[u][i], step, time);
        }
    }
    return;
}

int main() {
    int n, m, s, t;
    scanf("%d%d", &n, &m);
    int ut, vt;
    rep(i, m) {
        scanf("%d%d", &ut, &vt);
        G[ut - 1].pb(vt - 1);
    }
    scanf("%d%d", &s, &t);
    s--;
    t--;

    rep(i, 3) rep(j, 100010) {
        ret[j][i] = INF;
    }

    ret[s][0] = 0;

    queue<P1> que;
    que.push(P1(s, P(0, 0)));

    int u, step, time;
    while (que.size()) {
        P1 p = que.front();
        que.pop();

        u = p.fr;
        step = p.sc.fr;
        time = p.sc.sc;

        step = (step + 1) % 3;
        if (step == 0) {
            time++;
        }
        rep(i, G[u].size()) {
            if (ret[G[u][i]][step] > time) {
                ret[G[u][i]][step] = time;
                que.push(P1(G[u][i], P(step, time)));
            }
        }
    }

    if (ret[t][0] != INF) {
        printf("%d\n", ret[t][0]);
    } else {
        printf("%d\n", -1);
    }

    /* --------------------------------- */
    return 0;
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,i;
cin>>a>>b;
for(i=0;i<=20000;i++)
{
 if(((i*8)/(100))==a&&(i/10)==b)
  break;
}
if(i==20001)
cout<<"-1";
else
cout<<i;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int n, k; cin >> n >> k;
    vector<long long> h(n), dp(n+k, 1e16);
    for(int i = 0; i < n; ++i){
        cin >> h[i];
    }
    dp[0] = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 1; j <= k; ++j){
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]));
        }
    }
    cout << dp[n-1] << endl;
}


Measured memory_bytes: 1792
/* Priyansh Agarwal*/
#include<bits/stdc++.h>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<unordered_set>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define nline "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define debug(x) cout << #x << " " << x <<endl;
#define set_bits __builtin_popcount
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod)
{ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
bool revsort(ll a, ll b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
ll combination(ll n, ll r, ll m, ll* fact) {ll val1 = fact[n]; ll val2 = mminvprime(fact[r], m); ll val3 = mminvprime(fact[n - r], m); return ((val1 * val2) % m * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
/*--------------------------------------------------------------------------------------------------------------------------*/
int main()
{
	fastio();
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
	freopen("Error.txt", "w", stderr);
#endif
	cout << setprecision(10);
	cout << fixed;
	lld a, b, x;
	cin >> a >> b >> x;
	if (2 * x >= a * a * b)
	{
		lld p = 2 * x / a / a - b;
		lld hi = b - p;
		lld ba = a;
		lld angle = atan(hi / ba);
		lld angle1 = ((angle * 180) / PI);
		cout << angle1 << endl;
	}
	else
	{
		lld h = 2 * x / b / a;
		lld angle = atan(b / h);
		lld angle1 = ((angle * 180) / PI);
		cout << angle1 << endl;
	}
	return 0;
}


Measured memory_bytes: 3848