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

using namespace std;
typedef long long ll;
#define sz(x) (ll)((x).size())
#define pb push_back
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)

vector<ll> pw2(51,1);ll high_order_bit(ll n){ll tmp=1,i=-1;while(tmp<=n){tmp*=2;i++;}if(n==0) return 0;else return i;}
vector<ll> binary_expansion(ll n){vector<ll> B(high_order_bit(n)+1);ll tmp=n;for(ll i=high_order_bit(n);i>=0;i--){B[i]=tmp/pw2[i];tmp%=pw2[i];}return B;}

ll value[41];
ll rec(ll rem,ll n,ll point){
    if(rem>=pw2[n+1]-1){
        rrep(i,n+1) point+=value[i];
        return point;
    }
    else{
        if(value[n]>0){
            if(rem>=pw2[n]) return max(rec(rem,n-1,point),rec(rem-pw2[n],n-1,point+value[n])); //0 or 1
            else return rec(rem,n-1,point); //0
        }
        else return rec(rem,n-1,point); //0
    }
}

int main(){
	rep1(i,50) pw2[i]=2*pw2[i-1];

	ll N,K; cin>>N>>K;
	vector<ll> A(N);
    rep(i,N) cin>>A[i];

    ll bitcnt[41]; //1の数、[0]~[40]まで用意
    rep(i,41) bitcnt[i]=0;
    rep(i,N){
        vector<ll> V=binary_expansion(A[i]);
        rep(i,sz(V)) if(V[i]==1) bitcnt[i]++;
    }
    
    //valueの計算
    rep(i,41){
        value[i]=max(N-2*bitcnt[i],0ll)*pw2[i];
    }

    ll H=high_order_bit(K);

    ll ans=rec(K,H,0ll);
    rep(i,N) ans+=A[i];

    cout<<ans;
}

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

int main() {
  int a[3];
  int ans = 0, sum = 0;
  
  for(int i=0; i<3; i++) {
    cin >> a[i];
    sum += a[i];
    if(a[i] == 5 || a[i] == 7) {
      ans++;
    }
  }
  if(sum == 17 && ans == 3) {
    cout << "YES" <<endl;
  } else {
    cout << "NO" <<endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int binarySearch(int* ,int);

int n;

int main(){
  int q,i,j;
  int s[100000],t[50000];
  int cnt=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&s[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&t[i]);
  }

  for(i=0;i<q;i++){
    j=binarySearch(s,t[i]);
    if(j==1)
      cnt++;
  }


  printf("%d\n",cnt);


  return 0;
}

int binarySearch(int *s,int t){
  int l=0;
  int r=n;
  int m;
  while(l<r){
    m=(l+r)/2;
    if(s[m]==t)
      return 1;
    else if(t<s[m])
      r=m;
    else
      l=m+1;
  }
  return 0;
}

Measured memory_bytes: 3200
from collections import deque

def solve(n, m, AB):
    g = [[] for _ in range(n)]
    for a, b in AB:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    count = 0
    for a, b in AB:
        q = deque(maxlen=m)
        q.append(0)
        used = {0}
        while len(q) > 0:
            node = q.popleft()
            for to in g[node]:
                if to in used \
                    or node == a - 1 and to == b - 1 \
                    or node == b - 1 and to == a - 1:
                    continue
                q.append(to)
                used.add(to)
        if len(used) < n:
            count += 1

    return count

_n, _m = map(int, input().split())
_AB = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _AB))


Measured memory_bytes: 39920
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		int cnt = 0;
		boolean b = true;
		for(int i = 2;b; i *= 2) {
			b = false;
			for(int j = 0; j < n; j++) {
				if(a[j] % i == 0) {
					b = true;
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}

}


Measured memory_bytes: 34324
#include "bits/stdc++.h"
using namespace std;
const int N = 5e3 + 3;
const int M = 205;
int n , m;
int a[N];
int b[N][M];
long long ans;
int bst[M];
int nxt[N][M];
int v[N][M];
int sz[N];
int main(){
    scanf("%d %d" , &n , &m);
    for(int i = 1 ; i < n ; ++i){
        scanf("%d" , a + i);
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= m ; ++j){
            scanf("%d" , &b[i][j]);
        }
    }
    for(int j = 1 ; j <= m ; ++j){
        stack < int > s;
        while(!s.empty()){
            s.pop();
        }
        for(int i = n ; i >= 1 ; --i){
            while(!s.empty() && b[s.top()][j] <= b[i][j]){
                s.pop();
            }
            if(s.empty()){
                nxt[i][j] = n + 1;
            }
            else{
                nxt[i][j] = s.top();
            }
            s.push(i);
        }
    }
    ans = 0;
    for(int i = 1 ; i <= n ; ++i){
        long long sum = 0;
        for(int j = i ; j <= n ; ++j){
            sz[j] = 0;
        }
        for(int j = 1 ; j <= m ; ++j){
            bst[j] = b[i][j];
            sum += bst[j];
            if(nxt[i][j] <= n){
                v[nxt[i][j]][sz[nxt[i][j]]++] = j;
            }
        }
        ans = max(ans , sum);
        long long dist = 0;
        for(int r = i + 1 ; r <= n ; ++r){
            dist += a[r - 1];
            for(int j = 0 ; j < sz[r] ; ++j){
                int idx = v[r][j];
                sum -= bst[idx];
                bst[idx] = b[r][idx];
                sum += bst[idx];
                int nx = nxt[r][idx];
                if(nx <= n){
                    v[nx][sz[nx]++] = idx;
                }
            }
            ans = max(ans , sum - dist);
        }
    }
    printf("%lld\n" , ans);
}

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

#define int long long

signed main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int ans = 0;
    while(true) {
        if(a%2!=0||b%2!=0||c%2!=0) break;
        if(ans==1000000) {
            cout << -1 << endl;
            return 0;
        }
        ans++;
        int tmp_a = a/2;
        int tmp_b = b/2;
        int tmp_c = c/2;
        a = 0;
        b = 0;
        c = 0;
        a += tmp_b+tmp_c;
        b += tmp_a+tmp_c;
        c += tmp_a+tmp_b;
    }
    cout << ans << endl;
    return 0;
}



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

int main() {
  int K, X;
  cin >> K >> X;
  
  int ans;
  if (K==1) {
    ans = X;
    cout << ans << endl;
    return 0;
  }
  
  for (int i=K-1; i<(K-1)*2; i--) {
    int ans = X-i;
    if (ans == X+(K-1)) {
    	cout << ans << endl;
      	break;
    } else {
    	cout << ans << " ";
    }
  }
}

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

using namespace std;

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


ll a, b;
int main() {
	cin >> a >> b;
	cout << max({ a * 2 - 1, b * 2 - 1, a + b }) << endl;
}

Measured memory_bytes: 256
n,s,_,*t=open(0).read().split()
n=int(n)
d=[0]*n+[1<<ord(c)-97for c in s]
for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
for q,a,b in zip(*[iter(t)]*3):
  i,s=int(a)+n-1,0
  if'2'>q:
    d[i]=1<<ord(b)-97
    while i>1:
      i//=2
      d[i]=d[i+i]|d[i-~i]
    continue
  j=int(b)+n
  while i<j:
    if i&1:
      s|=d[i]
      i+=1
    if j&1:
      j-=1
      s|=d[j]
    i//=2
    j//=2
  print(bin(s).count('1'))

Measured memory_bytes: 83876
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int h, w, far[1111][1111];
char c[1111][1111];
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
signed main() {
	cin >> h >> w;
	queue<P>que;
	rep(i, h)rep(j, w) {
		far[i][j] = inf;
		cin >> c[i][j];
		if (c[i][j] == '#') {
			que.push({ i,j });
			far[i][j] = 0;
		}
	}
	int ans = 0;
	while (que.size()) {
		P p = que.front(); que.pop();
		rep(i, 4) {
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if (far[nx][ny] == inf) {
				far[nx][ny] = far[p.first][p.second] + 1;
				ans = max(ans, far[nx][ny]);
				que.push({ nx,ny });
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 26676
object Main extends App {
 
  val sc = new java.util.Scanner(System.in) 
  val n, m = sc.nextInt()
  val g = Array.fill(m)((sc.nextInt(), sc.nextInt()))
  val max = g.map{ case (x, y) => x}.max
  val min = g.map{ case (x, y) => y}.min
  if (min < max) {
    println(0)
  } else {
    println(min - max + 1)
  }
}

Measured memory_bytes: 62644
#include <cstdio>
#include <cstring>
char s[110];
char t[110];

int main(){
    scanf("%s%s", s, t);
    int len1 = strlen(s);
    int len2 = strlen(t);
    if(len1 != len2){
        printf("No\n");
        return 0;
    }
    else{
        for(int i = 1; i <= len1; ++i){
            char temp[110];
            char right[110];
            char left[110];
            strcpy(temp, s);
            strcpy(left, temp + len1 - i);
            temp[len1-i] = '\0';
            strcpy(right, temp);
            strcat(left, right);
            if(strcmp(left, t) == 0){
                printf("Yes\n");
                return 0;
            }
        }
    }
    printf("No\n");

}


Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
 
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpi;
typedef vector<pair<ll, ll> > vpl;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vi v(2*n);
  rep(i,2*n) cin >> v[i];
  sort(v.rbegin(),v.rend());

  int ans = 0;
  for(int i=1;i < 2*n;i+=2){
    ans += v[i];
  }
  cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
ar = gets.chomp.split.map(&:to_i)
flg = 1

if ar[0] < ar[2] + ar[4]
    flg = 0
end

if ar[2] - ar[4] < 0  
    flg = 0
end

if ar[1] < ar[3] + ar[4]
    flg = 0
end

if ar[3] - ar[4] < 0 
    flg = 0
end

if flg == 1
    puts "Yes"
else
    puts "No"
end

Measured memory_bytes: 8632
#include <bits/stdc++.h>
#define rep(i, n) for (ll 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;
    cin >> n;
    
    vec<string> S(n);
    vec<int> ans(26);
    rep(i, n) {
        vec<int> mp(26);
        cin >> S[i];
        for(auto e:S[i]){
            ++mp[e-'a'];
        }
        if(i==0) ans = mp;
        else {
            rep(i,26){
                ans[i] = min(ans[i],mp[i]);
            }
        }
    }

    for(int i=0;i<26;++i){
        rep(_,ans[i]){
            cout << (char)('a'+i);
        }
    }
    cout << '\n';
}


Measured memory_bytes: 3580
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    int H, W;
    cin >> H >> W;

    int c[10][10];
    FOR(i, 0, 10){
        FOR(j, 0, 10){
            cin >> c[i][j];
        }
    }

    FOR(k, 0, 10){
        FOR(i, 0, 10){
            FOR(j, 0, 10){
                // i -> j -> k
                if ( c [ i ][ j ] > c [ i ][ k ]+ c [ k ][ j ]) c [ i ][ j ]= c [ i ][ k ]+ c [ k ][ j ];
            }
        }
    }

    ll cost = 0;
    FOR(i, 0, H){
        FOR(j, 0, W){
            int a;
            cin >> a;
            if(a>=0){
                cost += c[a][1];
            }
        }
    }

    p(cost);
    
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        MyScanner scan = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        int n = scan.nextInt();
        int[][] vals = new int[n][2];
        for (int i = 0; i < n; i++) {
            vals[i][0] = scan.nextInt();
            vals[i][1] = scan.nextInt();
        }

        Arrays.sort(vals, (o1, o2) -> {
            return (o1[1]) - (o2[1]);
        });
        int time = 0;
        for (int i = 0; i < n; i++) {
            if (time + vals[i][0] <= vals[i][1]) {
                time += vals[i][0];
            } else {
                out.println("No");
                out.close();
                return;
            }
        }
        out.println("Yes");
        out.close();
    }


    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;

    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------

}

Measured memory_bytes: 55220
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	int ans = 0;
	for (int i = 0; i < n; i++) {
		char my;
		if (i%2==0) {
			my = 'g';
		}
		else {
			my = 'p';
		}
		if(s[i] != my && my == 'g') {
			ans--;
		}
		else if (s[i] != my && my == 'p') {
			ans++;
		}
		dump(ans);
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(a)			(a).begin(),(a).end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF				2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<ll, ll>	P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	int N;
	cin >> N;
	map<int, int> mp;
	REP(i, N) {
		int a;
		cin >> a;
		mp[a]++;
	}

	ll ans = 0;
	for (auto it = mp.begin(); it != mp.end(); it++) {
		if (it->first <= it->second) {
			ans += it->second - it->first;
		} else {
			ans += it->second;
		}
 	}

	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 4736
#include <stack>
#include <string>
#include <iostream>
#include <utility>
using namespace std;
int main(void){
    string c;
    cin >> c;
    int length = c.length();
    int depth[length+10];
    for(int i = 0;i < length + 10; i++)
        depth[i] = 0;
     
    stack<pair<int,int> > S;
    for(int i = 0;i<length;i++){
        if(c[i] == '\\'){
            S.push(make_pair(0,i));
        }
         
        else if(c[i] == '_'){
            S.push(make_pair(1,i));
        }
        else if(c[i] == '/'){
            while(!S.empty() && S.top().first != 0 ){
                S.pop();
            }
            if(!S.empty()){
                for(int j=S.top().second;j < i;j++){
                    depth[j+1]++;
                }
                S.pop();
            }
        }
    }
    float amounts[length+10] = {};
    float sum = 0.0;
    int cnt = 0;
    int start = 0;
    for(int i = start;i < length+1;i++){
        if(depth[i] == 0 && amounts[cnt] >= 1.0){
            cnt++;
        }
        amounts[cnt] += (depth[i] + depth[i+1])*0.50;
        sum += (depth[i] + depth[i+1])*0.50;
         
    }
     
    cout << (int)sum << endl;
    cout << cnt;
    if(cnt>0)
        cout << ' ';
    else cout << endl;
    for(int i = 0;i < cnt-1;i++){
        cout << amounts[i] << ' ';
    }
    if(cnt > 0)
        cout << (int)amounts[cnt-1] << endl;
    return 0;
}

Measured memory_bytes: 3532
from itertools import combinations

N=int(input())
P={"M","A","R","C","H"}
X={x:0 for x in P}

for _ in range(N):
    S=input()
    if S[0] in P:
        X[S[0]]+=1

K=0
for (a,b,c) in combinations(P,3):
    K+=X[a]*X[b]*X[c]
print(K)


Measured memory_bytes: 74084
S = input()

cnt =1
okflg = True

for s in S:
    
    if cnt%2==0:
        if s!="L"and  s!="U" and s!="D":
            okflg = False
            break
    else:
        if s!="R" and s!="U" and s!="D":
            okflg = False
            break
            
    cnt = cnt+1

if okflg ==True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main (){
  int n;
  cin >> n;
  vector<ll> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  ll total=a[0],ans=0,ans1 =0,ans2 = 0;
  bool flg1 = false,flg2 = false;
  if(total <= 0){
    ans1 += abs(total-1);
    total = 1;
  }
  for(int i=1;i<n;i++){
    if(total<0){
      flg1 = false;
    }else{
      flg1 = true;
    }
    if(flg1){
      total += a[i];
      if(total>=0){
        ans1 += total+1;
        total = -1;
      }
    }else{
      total += a[i];
      if(total<=0){
        ans1 += abs(total-1);
        total = 1;
      }
    }
  }
  total = a[0];
  if(total >= 0){
    ans2 += abs(total+1);
    total = -1;
  }
  for(int i=1;i<n;i++){
    if(total<0){
      flg1 = false;
    }else{
      flg1 = true;
    }
    if(flg1){
      total += a[i];
      if(total>=0){
        ans2 += total+1;
        total = -1;
      }
    }else{
      total += a[i];
      if(total<=0){
        ans2 += abs(total-1);
        total = 1;
      }
    }
  }
  //cout<<ans1<<" "<<ans2<<endl;
  cout << min(ans1,ans2) <<endl;
  return 0;
}


Measured memory_bytes: 1024
/* *Your Love Makes me STRONG,
   You'r Hate Makes Me UNSTOPABBLE.*

  *HOPE is a good thing,Maybe The BEST of Things.
   And No Good Things Ever Dies.*

  *Keep calm,Be patient And Chase Your DREAM*

*/


#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MN7 ios::sync_with_stdio(0);cin.tie(nullptr);
using namespace std;
ll t, n, i, j, k, a, b, c, d, p, q, r, x, y, z, m, cnt, flag, ans;
string s1,s2,s3;
void nahid()
{	
  cin>>s1>>s2>>s3;
  cout<<s1[0]<<s2[1]<<s3[2]<<endl;
}
int main()
{	MN7 //cin >> t; while (t--)
		nahid();
}


Measured memory_bytes: 3596
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[0]*(k+1)
    dp[k]=1
    for i in range(n):
        ndp=[0]*(k+1)
        # dpの累積和を取っておく
        S=[0]*(k+2)
        for j in range(k+1):
            S[j+1]=S[j]+dp[j]
            S[j+1]%=MOD
        # iterete
        for j in range(k+1):
            ndp[j]=S[min(j+A[i]+1,k+1)]-S[j]
            ndp[j]%=MOD
        dp=ndp
    print(dp[0])
resolve()

Measured memory_bytes: 117676
s = input().rstrip()

ans = 0
anum = 0
prev = "x"
for c in s:
    if c == "A":
        if prev != "B":
            anum += 1
        else:
            anum = 1
    elif c == "B":
        if prev == "B":
            anum = 0
    elif c == "C":
        if prev == "B":
            ans += anum
        else:
            anum = 0
    prev = c
print(ans)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int s, w;
    cin >> s >> w;
    if(s > w) {
        cout << "safe";
    } else {
        cout << "unsafe";
    }
    return 0;
}


Measured memory_bytes: 3652
#include<stdio.h>
int main(){
  char c[1000];
  int i,x;
  int sum;
  int co;
  while(1){
    co=0;
    sum=0;
    scanf("%s",&c);
    for(i=0;;i++){
      if(c[i]=='\0'){
    co=i;
    break;
      }
    }
    if(c[0]=='0')break;
     
    for(i=0;i<co;i++){
      x =c[i]-'0';
      sum+=x;
 
    }
    printf("%d\n",sum);
  }
   
  return 0;
}

Measured memory_bytes: 536
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  int a[n];
  vector<int> dp(n,1000000000);
  for(int i=0;i<n;i++) cin>>a[i];
  dp[0]=0;
  for(int i=0;i<n-1;i++){
    for(int j=1;j<=k;j++){
      if(i+j==n) break;
      dp[i+j]=min(dp[i+j],dp[i]+abs(a[i+j]-a[i]));
    }
  }
  cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1024
#include<iostream>
#define M 100000007
using namespace std;

int main(){
  string str;
  long long int ans;
  char prv;
  long long int t1[100001],t2[100001];

  t1[1] = 1;
  t1[2] = 2;
  t1[3] = 4;
  for(int i=4;i<=100000;i++){
    t1[i] = 1;
    for(int j=1;j<=3;j++){
      t1[i] += (t1[i-j])%M;
    }
  }

  t2[1] = 1;
  t2[2] = 2;
  t2[3] = 4;
  t2[4] = 8;
  t2[5] = 16;
  for(int i=6;i<=100000;i++){
    t2[i] = 1;
    for(int j=1;j<=5;j++){
      t2[i] += (t2[i-j])%M;
    }
  }

  //for(int i=1;i<=12;i++)cout <<t2[i] << endl;
  while(1){
    cin >> str;
    if(str == "#")break;

    ans = 1;
    int pos = 1;
    prv = str[0];
    int times = 1;
    while(pos<(int)str.size()){
      if(str[pos]!=prv){
	if(prv == '8' || prv == '0'){
	  ans *= t1[times];
	}else{
	  ans *= t2[times];
	}
	ans = ans % M;
	prv = str[pos];
	times = 1;
      }else times++;
      pos++;
    }
    if(prv == '8' || prv == '0'){
      ans *= t1[times];
    }else{
      ans *= t2[times];
    }
    ans = ans%M;
    
    cout << ans << endl;
  }
}

Measured memory_bytes: 2704
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, K = ds_in()
A_list = ds_in()

if K == 0:
    print(sum(A_list))
    exit()

max_A = max(A_list)

bit_K = bin(K)[2:][::-1]
n_bitK = len(bit_K)

bit_list = [0] * (len(bin(max(max_A, K))) - 2)


for a in A_list:
    bit_a = bin(a)[2:][::-1]
    for i, bit in enumerate(bit_a):
        if bit == '1':
            bit_list[i] += 1


ans = 0
for i in range(n_bitK, len(bit_list)):
    ans += 2**i * bit_list[i]

dp = [[0, 0] for _ in range(n_bitK)]
dp[n_bitK-1][1] = 2**(n_bitK-1) * (N - bit_list[n_bitK-1])
dp[n_bitK-1][0] = 2**(n_bitK-1) * bit_list[n_bitK-1]
for i in range(n_bitK-2, -1, -1):
    if bit_K[i] == '1':
        dp[i][1] = dp[i+1][1] + 2**i * (N - bit_list[i])
        dp[i][0] = max(dp[i+1][0] + 2**i * max(bit_list[i], N - bit_list[i]),
                       dp[i+1][1] + 2**i * bit_list[i])
    else:
        dp[i][1] = dp[i+1][1] + 2**i * bit_list[i]
        dp[i][0] = dp[i+1][0] + 2**i * max(bit_list[i], N - bit_list[i])

print(ans + max(dp[0]))


Measured memory_bytes: 14748
#include <bits/stdc++.h>
#define ll long long
#define nl '\n'

using namespace std;
void solve() {
    int n, m;
    cin >> n >> m;
    cout << (n * (n - 1) / 2) + (m * (m - 1) / 2) << nl;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	ll n;
	ll ans=log10(n)+1;
	cin >>n;
	for(ll i =sqrt(n) ;i>0;i--){
		if(n%i==0){
			ans=log10(n/i)+1;
			break;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 512
N=int(input())
a=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
	B[i],C[i]=map(int,input().split())
import collections
A=collections.Counter(a)
S=0
for j in range(N):
	S=S+a[j]
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	else:
		f=0
	S=S+f*(C[i]-B[i])
	print(S)

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

string t;

void solve()
{
	const int n = t.length();
	if(n==1){
		cout<<"YES\n";
		return;
	}
	int ac=0,bc=0,cc=0;
	for(int i=0;i<n;++i){
		if(t[i]=='a')ac++;
		else if(t[i]=='b')bc++;
		else cc++;
	}
	if(n==2){
		if((ac && bc) || (ac && cc) || (bc && cc)) cout<<"YES\n";
		else cout<<"NO\n";
	}else{
		if(max(max(ac,bc),cc)-min(min(ac,bc),cc)<=1)cout<<"YES\n";
		else cout<<"NO\n";
	}
}

int main()
{
	cin >> t;
	solve();
	return 0;
}

Measured memory_bytes: 3740
N,M = map(int,input().split())
ab = [[int(i) for i in input().split()] for _ in range(N)]
cd = [[int(i) for i in input().split()] for _ in range(M)]
 
for a,b in ab:
    num = 0
    d = 10**10
    for i in range(M):
        if abs(a-cd[i][0])+abs(b-cd[i][1])<d:
            num = i+1
            d = abs(a-cd[i][0])+abs(b-cd[i][1])
    print(num)


Measured memory_bytes: 3064
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0)
//#define MULTI_TEST
//#define GOOGLE
#ifdef LOCAL
#include "debugger.h"
#else
#define db(...)
#endif
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
const ll MOD = 1e9 + 7;
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }

const int N = 1e6 + 1;
int nat[N];

void solve(int tc)
{
	int n;
	cin >> n;
	unordered_map<int, int> pres;
	for (int i = 0; i < n; i++)
	{
		int item;
		cin >> item;
		pres[item]++;
	}
	int ans = 0;
	for (int i = 1; i < N; i++)
	{
		if (pres[i])
		{
			if (nat[i] == 0 && pres[i] == 1)
				ans++;
			for (int j = 2 * i; j < N; j += i)
				nat[j]++;
		}
	}
	cout << ans << ln;
	return;
}

int main()
{
#ifndef LOCAL
	FASTIO;
#endif
	int t = 1;
#ifdef LOCAL
	clock_t start, stop;
	start = clock();
#endif
#ifdef MULTI_TEST
	cin >> t;
#endif
	for (int tc = 1; tc < t + 1; tc++)
	{
#ifdef GOOGLE
		cout << "Case #" << tc << ": ";
#endif
		solve(tc);
	}
#ifdef LOCAL
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 46552
import java.util.*;
import java.io.*;
import java.math.BigInteger;
 
public class Main {
	
	public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
	int K = s.nextInt();
	int X = s.nextInt();

	if(K*500 >= X){
		System.out.println("Yes");
	}else{
		System.out.println("No");
	}
	
    
  }
}

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

using namespace std;

int main()
{
    int H, W;
    string C[110];

    cin >> H >> W;

    for (int i = 0; i < H; i++)
    {
        cin >> C[i];
    }

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

    return 0;
}

Measured memory_bytes: 256
n = int(input())
temparr = input()
temparr = temparr.split()
arr = []
dicts = {}
for i in temparr:
    i = int(i)
    arr.append(int(i))
    if i not in dicts:
        dicts[i] = 1 
    else:
        dicts[i] += 1 
arr = sorted(arr)
#print(dicts)
#print(arr)
keys = []
for key, value in dicts.items():
    keys.append(key)
keys = sorted(keys)
freq = []
total = 0 
nn = len(keys)
#print(keys)
for i in range(nn - 2):
    for j in range(i + 1 , nn - 1):
            for k in range(j + 1, nn ):
                #print("i " + str(i) + " j " + str(j) + " k " + str(k))
                if keys[i] + keys[j] <= keys[k]:
                    break 
                total += dicts[keys[i]] * dicts[keys[j]] * dicts[keys[k]]
            #print(total)
print(total)




Measured memory_bytes: 67988
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#define maxn 200005
#define lson (now<<1)
#define rson ((now<<1)|1)
#define mid ((nl+nr)>>1)
using namespace std;
typedef long long ll;
int main()
{
	int x,y;
	cin>>x>>y;
	if(y-2*x<0)
		printf("No\n");
	else if((y-2*x)&1)
		printf("No\n");
	else if((x-(y-2*x)/2)<0)
		printf("No\n");
	else
		printf("Yes\n");
}

Measured memory_bytes: 3624
N = int(input())
h = list(map(int, input().split()))
dp = [0] * (N)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
  dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
print(dp[N-1])


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

namespace ziyuutyou
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = int.Parse(Console.ReadLine());

            if(str < 1200)
            {
                Console.WriteLine("ABC");

            }
            else
            {
                Console.WriteLine("ARC");
            }
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main(){
    Hello
    int n;
    cin >> n;
    int arr[n + 5], ans = 1e9;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    for(int i = 1; i < n; i++){
        int sum1 = 0, sum2 = 0;
        for(int j = 0; j < i; j++)
            sum1 += arr[j];
        for(int j = i; j < n; j++)
            sum2 += arr[j];
        ans = min(ans, abs(sum1 - sum2));
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3640
#include <stdio.h>

int main()
{
	int n;
	int i;
	int debt = 100000;
	scanf("%d",&n);
	for(i = 0; i < n; i++){
		debt = (int)(debt * 1.05);
		if(debt % 1000 != 0){
			debt = (int)(debt / 1000) * 1000 + 1000;
		}
	}
	printf("%d\n",debt);
	return 0;
}

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

int main(){
  int N;
  int ACnum = 0,WAnum = 0,TLEnum = 0,REnum = 0;
  string ans;
  
  cin >> N;
  
  for(int i = 0; i < N; i++){
    cin >> ans;
    if(ans == "AC")
      ACnum++;
    else if(ans == "WA")
      WAnum++;
    else if(ans == "TLE")
      TLEnum++;
    else if(ans == "RE")
      REnum++;
  }
  
  cout << "AC x " << ACnum << endl; 
  cout << "WA x " << WAnum << endl; 
  cout << "TLE x " << TLEnum << endl; 
  cout << "RE x " << REnum << endl; 
}

Measured memory_bytes: 3632
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

const string YES = "Yes";
const string NO = "No";

int main()
{
  int H, W;
  cin >> H >> W;
  vector<string> a(H);
  vector<int> cnt(26, 0);
  for (auto &e : a)
  {
    cin >> e;
    for (auto &t : e)
    {
      cnt[t - 'a']++;
    }
  }
  vector<int> g(3, 0);
  g[0] = (W % 2) * (H % 2);
  g[1] = (H % 2) * (W / 2) + (W % 2) * (H / 2);
  g[2] = (W / 2) * (H / 2);
  for (auto &e : cnt)
  {
    while (e)
    {
      if (e % 4 == 1 || e % 4 == 3)
      {
        e--;
        g[0]--;
      }
      else if (e % 4 == 2 || (e % 4 == 0 && g[2] == 0))
      {
        e -= 2;
        g[1]--;
      }
      else if (e % 4 == 0 && e > 0)
      {
        e -= 4;
        g[2]--;
      }
    }
  }
  if (g[0] == 0 && g[1] == 0 && g[2] == 0)
    cout << YES << endl;
  else
    cout << NO << endl;

  return 0;
}


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

struct TNode
{
	int Id;
	TNode* Parent;
	TNode* LChild;
	TNode* RChild;
};

struct TTree
{
private:
	TNode* Root;
	void Delete(const TNode* Node)
	{
		if(Node == NULL) return;
		Delete(Node->LChild);
		Delete(Node->RChild);
		delete Node;
	}
	void InorderOutput(const TNode* Node)
	{
		if(Node == NULL) return;
		InorderOutput(Node->LChild);
		cout << ' ' << Node->Id;
		InorderOutput(Node->RChild);
	}
	void PreorderOutput(const TNode* Node)
	{
	    if(Node == NULL) return;
	    cout << ' ' << Node->Id;
	    PreorderOutput(Node->LChild);
	    PreorderOutput(Node->RChild);
	}
	void MakeTree(TNode* z)
	{
	    assert(z != NULL);
		TNode* y = NULL;
		TNode* x = Root;
		while(x != NULL){
			y = x;
			if(z->Id < x->Id){
				x = x->LChild;
			}else{
				x = x->RChild;
			}
		}
		z->Parent = y;
		if(y == NULL){
			Root = z;
		}else if(z->Id < y->Id){
			y->LChild = z;
		}else{
			y->RChild = z;
		}
	}
public:
	TTree()
	{
		Root = NULL;
	}
	~TTree()
	{
		Delete(Root);
	}
	void Insert(int Id)
	{
		TNode* Node;
		Node = new TNode;
		*Node = {Id, NULL, NULL, NULL};
		MakeTree(Node);
	}
	void Print()
	{
		InorderOutput(Root);
		cout << endl;
		PreorderOutput(Root);
		cout << endl;
	}
};

int main()
{
	int n;
	cin >> n;
	TTree Tree;
	for(int i = 0; i < n; i++){
		string Command;
		cin >> Command;
		if(Command == "insert"){
			int Id;
			cin >> Id;
			Tree.Insert(Id);
		}else{
			Tree.Print();
		}
	}
    return 0;
}

Measured memory_bytes: 26588
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#define ll long long
using namespace std;

const int N=200005;

int n;
ll ans;
ll a[N];
map<ll,int> mp;

int main(){
	int i;
	scanf("%d",&n);
	mp[0]=1;
	for (i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
		ans+=mp[a[i]];
		mp[a[i]]++;
	}
	printf("%lld\n",ans);
	return 0;
}

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

int getDist(int fx, int fy, int tx, int ty) {
  return abs(fx-tx) + abs(fy-ty);
}

int main() {
  int n,m;
  cin>>n>>m;
  
  vector<int> a(n),b(n);
  for(int i=0;i<n;++i) cin>>a[i]>>b[i];
  vector<int> c(m),d(m);
  for(int i=0;i<m;++i) cin>>c[i]>>d[i];
  
  for(int i=0;i<n;++i) {
    int x=a[i], y=b[i];
    int ans=0,dist=1e9+1;
    for(int j=0;j<m;++j){
      if (getDist(x,y,c[j],d[j]) < dist) {
        dist = getDist(x,y,c[j],d[j]);
        ans=j;
      }
    }
    cout<<ans+1<<endl;
  }
  return 0;
}


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

int main() {
  int n; cin >> n;
  string ans = "Yes";
  vector<string> w(n);
  vector<int> wn(n);
  set<string> ws;
  rep(i,n) {
    cin >> w[i];
    wn[i] = w[i].size();
    if (i!=0 && w[i-1][wn[i-1]-1] != w[i][0] ||
        ws.count(w[i]) != 0) {
      ans = "No";
      break;
    }
    ws.insert(w[i]);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;

vector<long long int> inverse;
vector<long long int> f, f_inverse;

void factorial_Initialize(int max){
    vector<long long int> a(max+1,1);
    inverse = a;
    f = a;
    f_inverse = a;

    for (int i=2; i<=max; i++){
        inverse[i]   = MOD - inverse[MOD % i] * (MOD / i) % MOD;
        f[i]         = f[i-1]         * i          % MOD;
        f_inverse[i] = f_inverse[i-1] * inverse[i] % MOD;
    }
}

long long int nCr(int n, int r){
    if(n < r || r < 0) return 0;
    if (n >= f.size()){
        factorial_Initialize(n);
    }
    return f[n] * f_inverse[r] % MOD * f_inverse[n-r] % MOD;
}

long long int modpow(int b, int p){
    long long int num = 1, power = b;
    for(int i=0; i<=30; i++){
        if((p>>i) & 1) num *= power;

        num %= MOD;
        power *= power;
        power %= MOD;
    }
    return num;
}

int main(){
    long long int n, m, k;
    cin >> n >> m >> k;

    long long int x = 0, y = 0;
    for(long long int i=1; i<n; i++){
        long long int add = i * (n-i) * m * m;
        add %= MOD;
        add *= nCr(n*m-2, k-2);
        add %= MOD;

        x += add;
        x %= MOD;
    }
    for(long long int i=1; i<m; i++){
        long long int add = i * (m-i) * n * n;
        add %= MOD;
        add *= nCr(n*m-2, k-2);
        add %= MOD;
        
        y += add;
        y %= MOD;
    }

    long long int ans = x + y;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9600
'''
ITP-1_7-C
 ??¨?¨????
??¨?¨??????????????°???????????????°???????????????????????????
??¨????????°r??¨?????°c???r ?? c ???????´????????????¨?????????????????§???????????¨??????????¨?????????\????????°????????¨???????????????
????????°?????????????????????????????????
???Input
???????????????r??¨c????????????????????§??????????????????????¶????r??????????????????c????????´??°????????????????????§?????????????????????
???Output
(r+1) ?? (c+1) ?????°????????¨??????????????????????????????????????£???????????´??°????????????????????§????????£???????????????
???????????????????????¨??????????????????????¨?????????????????????????????????¨??????????????????????¨??????????
???????????????????????¨??¨??????????¨????????????\??????????????????
'''
# inputData
r, c = map(int, input().split())
data = [list(map(int, input().split())) for i in range(r)]

for row in data:
    row.append(sum(row))
    print(*row)

# zip ????´?????????????????????????????????¨?????§????????????????????§??????
columnSum = [sum(Column) for Column in zip(*data)]
print(*columnSum)

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

int main(void){
  int x, y;
  cin >> x >> y;
  string ans = "No";
  
  if(x == 1 && y == 2 )ans = "Yes";
  if(x == 1 && y == 4 )ans = "Yes";
  
  rep(i, x){
    if((i * 2 + (x - i) * 4) == y){
      ans = "Yes";
    }
  }  
  
  cout << ans << endl;
    
  return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include<iomanip>

using namespace std;

int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
    vector<long double> prob(N);
    for (int i = 0; i < N; i++) {
        cin >> prob[i];
    }
    vector<vector<long double>> values(N + 1, vector<long double>(N + 1));
    // use coin 1 - i
    for (int i = 1; i <= N; i++) {
        // num of front
        for (int j = 0; j <= i; j++) {
            if (i == 1 && j == 1) {
                values[i][j] = prob[i-1];
            } else if (i == 1 && j == 0) {
                values[i][j] = 1.0L - prob[i-1];
            } else if (j == 0) {
              values[i][j] = (1.0L - prob[i-1]) * values[i-1][j];
            } else if (j > i) {
                values[i][j] = 0.0L;
            } else {
                values[i][j] = prob[i-1] * values[i-1][j-1] + (1.0L - prob[i-1]) * values[i-1][j];
            }
        }
    }
    // for (int i = 1; i <= N; i++) {
    //     cout << i << ": ";
    //     for (auto v: values[i]) {
    //         cout << v << ", ";
    //     }
    //     cout << endl;
    // }

    // 0, 1, 2, 3 => 2, 3
    // 0, 1, 2 => 2
    cout << setprecision(10) << accumulate(values[N].begin() + (N/2 + 1), values[N].end(), 0.0L) << endl;
    return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;





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

    int m1,d1;
    int m2,d2;

    cin>>m1>>d1;
    cin>>m2>>d2;
    cout<<(m1<m2)<<endl;
    
    
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
//#include "h.h"
using namespace std;

#define ll long long
#define pint pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(VECTOR) (VECTOR).begin(),(VECTOR).end()

int N, M;
vector<int> A, B;
vector<ll> ans;
vector<int> parent;

int root(int X){
	if(parent[X] < 0)return X;
	return parent[X] = root(parent[X]);
}
int size(int X){
	return -parent[root(X)];
}
bool connect(int X, int Y){
	X = root(X);
	Y = root(Y);
	if(X == Y){
		return false;
	}
	if(size(X) < size(Y))swap(X, Y);
	parent[X] += parent[Y];
	parent[Y] = X;
	return true;
}

int main(){

	cin >> N >> M;
	A = vector<int>(M);
	B = vector<int>(M);
	for(int i = 0; i < M; i ++){
		cin >> A[i] >> B[i];
		A[i] --;
		B[i] --;
	}
	ans = vector<ll>(M);
	ans[M - 1] = (ll)N * (N - 1) / 2;

	parent = vector<int>(N, -1);
	for(int i = M - 1; i >= 1; i --){
		ans[i - 1] = ans[i];
		if(root(A[i]) != root(B[i])){
			ans[i - 1] -= (ll)size(A[i]) * size(B[i]);
			connect(A[i], B[i]);
		}
	}
	for(int i = 0; i < M; i ++){
		cout << ans[i] << endl;
	}

	return 0;
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)
#define mod 1000000007
typedef long long ll;

int main() {
    int n;cin>>n;
    vector<int>d(n);
    rep(i,n){
        cin>>d[i];
    }

    int sum=0;

    for (int i=0;i<n-1;i++) {
        for(int j=i+1;j<n;j++){
            sum+=d[i]*d[j];
        }
    }
    cout<<sum<<endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

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

        String str = sc.next();
        
        str = str.replace("1", "2");
        
        str = str.replace("9", "1");
        
        str = str.replace("2", "9");
        
        System.out.println(str);
    }
}


Measured memory_bytes: 21972
s = input()

oddFirst = 0
evenFirst = 0

for i in range(len(s)):
    if i % 2 == 0:
        if int(s[i]) % 2 == 0:
            oddFirst += 1
        else:
            evenFirst += 1
    else:
        if int(s[i]) % 2 == 0:
            evenFirst += 1
        else:
            oddFirst += 1

print(min(oddFirst, evenFirst))


Measured memory_bytes: 3188
import numpy as np
import math
N =int(input())
c=list(map(int, input().split())) 
a = np.arange(1,N+1)
#print(sorted(c-a))
d = sorted(c-a)
if (abs(d[0])-abs(d[N-1])==0) and (np.count_nonzero(d)==2):
    print('YES')
elif (np.count_nonzero(d)==0):
    print('YES')
else:
    print('NO')



Measured memory_bytes: 12508
from collections import deque
import sys
#input = sys.stdin.readline

Q = deque()

n = int(input())

for _ in range(n):
    command = input()
    if command == "deleteLast":
        Q.pop()
    elif command == "deleteFirst":
        Q.popleft()
    else:
        if command[0] == "i":
            Q.appendleft(command[7:])
        else:
            try:
                Q.remove(command[7:])
            except:
                pass

print(" ".join(Q))


Measured memory_bytes: 69736