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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef complex<double> cd;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

const ll P = 200003;

long long n;
long long g[P];
long long inq2[P];

const int LG = 19;
const int SZ = (1 << 19);
const double PI = acos(-1);

int bitreverse[SZ];

int BitReverse(int x)
{
    int y = 0;
    for (int i = 0; i < LG; i++)
    {
        y = 2 * y + ((x & (1 << i)) > 0);
    }
    return y;
}

vector<cd> dft(vector<cd> a, int fl)
{
    vector<cd> b(SZ);
    for (int i = 0; i < SZ; i++)
    {
        b[i] = a[bitreverse[i]];
    }
    for (int len = 2; len <= SZ; len <<= 1)
    {
        double ang = 2 * PI / len * fl;
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < SZ; i += len)
        {
            cd w(1, 0);
            for (int j = 0; j < len / 2; j++)
            {
                cd v = b[i + j], u = b[i + j + len / 2] * w;
                b[i + j] = v + u;
                b[i + j + len / 2] = v - u;
                w *= wlen;
            }
        }
    }
    return b;
}

vector<ll> fft(vector<ll> a0, vector<ll> b0)
{
    vector<cd> a(SZ), b(SZ);
    for (int i = 0; i < a0.size(); i++) a[i].real(a0[i]);
    for (int i = 0; i < a0.size(); i++) b[i].real(b0[i]);
    a = dft(a, 1);
    b = dft(b, 1);
    forn(i, SZ) a[i] *= b[i];
    a = dft(a, -1);
    vector<ll> r(SZ);
    forn(i, SZ)
    {
        r[i] = round(a[i].real() / SZ);
    }
    return r;
}

signed main()
{
    for (int i = 0; i < SZ; i++) bitreverse[i] = BitReverse(i);
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    forn(i, P) g[i] = -1;
    for (int i = 1, j = 0; g[i] == -1; i = i * 2 % P, j++) g[i] = j, inq2[j] = i;
    vector<ll> poly(P);
    cin >> n;
    long long ans = 0;
    long long ch = 0;
    forn(i, n)
    {
        long long a;
        cin >> a;
        ans -= a * a % P;
        if (a != 0)
        {
            poly[g[a]]++;
        }
    }
    poly = fft(poly, poly);
    for (int i = 0; i < poly.size(); i++)
    {
        ans += poly[i] * inq2[i % (P - 1)];
    }
    cout << ans / 2;
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


Measured memory_bytes: 46428
def main():
    N = int(input())

    def to_bin(n):
        """
        n:10進数 -> 2進数
        """
        if n == 0:
            return 0
        digits = []
        i = 0
        base = 1
        while n != 0:
            if n % (base*2) == 0:
                digits.append("0")
            else:
                digits.append("1")
                n -= base
            i += 1
            base *= -2
        return "".join(digits[::-1])

    print(to_bin(N))


if __name__ == '__main__':
    main()


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

using namespace std;

const long long MOD = 1000000007;

int main (void) {
    int N;
    string S1, S2;
    cin >> N >> S1 >> S2;

    long long ans;
    int idx = 0;
    bool is_prev_ver;

    if ( S1.at(0) == S2.at(0) ) {
        ans = 3;
        is_prev_ver = true;
        idx++;
    }
    else {
        ans = 6;
        is_prev_ver = false;
        idx += 2;
    }

    while ( idx < N ) {
        if ( S1.at(idx) == S2.at(idx) ) {
            if ( is_prev_ver ) ans *= 2;
            is_prev_ver = true;
            idx++;
        }
        else {
            if ( is_prev_ver ) ans *= 2;
            else ans *= 3;
            is_prev_ver = false;
            idx += 2;
        }
        if ( ans >= MOD ) ans %= MOD;
    }

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


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007

using namespace std;

int n, m, r, a[10], x, y, z, d[201][201];

int main() {
    cin >> n >> m >> r;
    for (int i = 0; i < r; i++)
        cin >> a[i];
    memset(d, 63, sizeof(d));
    while(m--) {
        cin >> x >> y >> z;
        if (z < d[x][y])
            d[x][y] = z,
            d[y][x] = z;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][j] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];
    int ans = 1 << 30;
    sort(a, a + r);
    do {
        int c = 0;
        for (int i = 0; i < r - 1; i++)
            c += d[a[i]][a[i + 1]];
        ans = min(ans, c);
    }while(next_permutation(a, a + r));
    cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;cin>>s;
    bool key=false;
    int small=0;
    if(s[0]=='A'){
        for(int i=2;i<s.length()-1;i++){
            if(s[i]=='C'&&key==false){
                key=true;
            }
            else if(s[i]=='C'&&key==true){
                key=false;
                break;
            }
        }
        for(int i=0;i<s.length();i++){
            if(s[i]>='a'){
                small++;
            }
        }
        if(small!=s.length()-2){
            key=false;
        }
    }
    if(key){cout<<"AC"<<endl;}
    else{cout<<"WA"<<endl;}
}

Measured memory_bytes: 256
N = list(map(int, input().split()))
S = [0 for i in range(N[0])]
for i in range(N[1]):
    d = int(input())
    A = list(map(int, input().split()))
    for k in range(d):
        S[A[k]-1] += 1

out = 0
for i in range(N[0]):
    if S[i] == 0:
        out += 1

print(out)

Measured memory_bytes: 9184
n = int(input())
lis = []
for i in range(2, 10000, 5):
    now = 2
    flag = True
    while(now**2<=i):
        if i % now == 0:
            flag = False
            break
        now += 1
    if flag:
        lis.append(i)
for i in range(n):
    print(lis[i],end="")
    if i != n-1:
        print(" ", end="")
print("")


Measured memory_bytes: 3060
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(A v) {
bool first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


void rec(int digits, vector<ll> &nums, string &n) {
	if (SZ(nums) > 100009) return;
	if (digits == 0) {
		if (SZ(n) > 0) {
			nums.pb(stoll(n));
		}
	} else {
		for (int i = 0; i < 10; i++) {
			if (SZ(n) == 0) {
				if (i > 0) {
					n.pb('0' + i);
				}
				rec(digits - 1, nums, n);
				n.pop_back();
			} else if (abs(*(prev(n.end())) - ('0' + i)) <= 1) {
				n.pb('0' + i);
				rec(digits - 1, nums, n);
				n.pop_back();
			}
		}
	}
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int K;
    cin >> K;
    string n = "";
	vector<ll> nums;
    rec(10, nums, n);
    cout << nums[K - 1] << endl;
}

Measured memory_bytes: 2032
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

ans = 'Yes'
n, m = map(int, input().split())
if n != m:
    ans = 'No'

print(ans)

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

int main()
{
	long long  N, M, cnt = 0;
	cin >> N >> M;

	if (N * 2 >= M)
		cnt = M / 2;
	else 
		cnt = N + (M - 2 * N) / 4;
	
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Stack, Queue, PriorityQueue, Set}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N, K = in.next().toInt
  val A = new Array[Int](N+1)
  for (i <- 1 to N) {
    A(i) = in.next().toInt
  }

  //
  val S = A.sum
  var B = new Array[Int](N+1)

  var ans = 1L
  var n = 1
  while (n * n <= S) {
    if (S % n == 0) {
      for (i <- 1 to N) {
        B(i) = A(i) % n
      }
      B = B.sorted

      var fu = 0L
      var sei = 0L
      var l = 1
      var r = N
      while (l <= r) {
        if (fu < sei) {
          fu += B(l)
          l += 1
        }
        else {
          sei += n - B(r)
          r -= 1
        }
      }

      if (fu == sei && sei <= K)
        ans = ans max n
    }

    val m = S / n
    if (S % m == 0) {
      for (i <- 1 to N) {
        B(i) = A(i) % m
      }
      B = B.sorted

      var fu = 0L
      var sei = 0L
      var l = 1
      var r = N
      while (l <= r) {
        if (fu < sei) {
          fu += B(l)
          l += 1
        }
        else {
          sei += m - B(r)
          r -= 1
        }
      }

      if (fu == sei && sei <= K)
        ans = ans max m
    }


    n += 1
  }

  println(ans)
}

object Sub {
  def print2DimArray[A](mat: Array[Array[A]]): Unit = {
    mat.foreach(lin => println(lin.deep))
  }
}

class InputReader(stream: InputStream) {
  private[this] val reader = new BufferedReader(new InputStreamReader(stream))
  private[this] var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


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

using namespace std;
using ll = long long;

//container util
#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)

const int INF = 1e9;

int main(void){

	ll N, A, B; cin >> N >> A >> B;
	
	ll ans = 0;
	ans = (N/(A+B))*A + min(A, N%(A+B));

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    string s;
    cin >> n >> m;
    while (n--) cin >> s, cout << s << '\n' << s << '\n';
}


Measured memory_bytes: 256
//#include "stdc++.h"
#include<bits/stdc++.h>
#include<iostream>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define pb push_back
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0) return 1;ll p=power(a,n/2,m);p=(p*p)%m;if(n%2) return (p*a)%m;else return p; }
#define flush fflush(stdout)
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
ll m[51][51];ll p[51][51];
void multiply1()
{
    ll c[51][51];
    memset(c,0,sizeof(c));
    for(int i=0;i<51;i++)
    {
        for(int j=0;j<51;j++)
        {
            for(int k=0;k<51;k++)
            {
                c[i][j]=(c[i][j]%MOD+(p[i][k]*p[k][j])%MOD)%MOD;
            }
        }
    }
    for(int i=0;i<51;i++)
        for(int j=0;j<51;j++)
            p[i][j]=c[i][j];
}
void multiply2()
{
    ll c[51][51];
    memset(c,0,sizeof(c));
    for(int i=0;i<51;i++)
    {
        for(int j=0;j<51;j++)
        {
            for(int k=0;k<51;k++)
            {
                c[i][j]=(c[i][j]%MOD+(p[i][k]*m[k][j])%MOD)%MOD;
            }
        }
    }
    for(int i=0;i<51;i++)
        for(int j=0;j<51;j++)
            p[i][j]=c[i][j];
}
void Power(ll n)
{
    if(n==1)
    {
        for(int i=0;i<51;i++)
            for(int j=0;j<51;j++)
                p[i][j]=m[i][j];
        return;
    }
    Power(n/2);
    multiply1();
    if(n%2)
        multiply2();
}
int main()
{
    IOS;//ifstream fin("input.txt");ofstream fout("output.txt");
    int n;ll k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cin>>m[i][j];
    }
    Power(k);ll ans=0;
    for(int i=0;i<51;i++)
        for(int j=0;j<51;j++)
        {
            ans=(ans%MOD+p[i][j]%MOD)%MOD;
        }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 384
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    limit = 10**18

    if 0 in A:
        print(0)
        return

    _mul = 1
    for a in A:
        _mul *= a
        if _mul > limit:
            print(-1)
            return

    print(_mul)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 21768
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


def dijkstra1(V, source):
    # O(ElogV)

    n = len(V)
    inf = float("inf")
    dist = [inf] * n
    dist[source] = 0
    q = [(0, source)]

    while q:
        cost, u = heappop(q)
        if dist[u] < cost:
            continue
        for c, v in V[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heappush(q, (dist[v], v))

    return dist

def dijkstra2(V, source):
    # O(V^2)

    n = len(V)
    inf = float("inf")
    used = [False] * n
    dist = [inf] * n
    dist[0] = 0
    
    for _ in range(n):
        c1, u = min([(dist[i], i) for i in range(n) if not used[i]])
        used[u] = True
        for c2, v in V[u]:
            if v==u: continue
            dist[v] = min(dist[v], c1+c2)
    return dist


if __name__ == "__main__":
    V, E, r = map(int, input().split())
    inf = float("inf")
    costs = {i:[] for i in range(V)}
    
    for _ in range(E):
        s, t, d = map(int, input().split())
        costs[s].append((d, t))

    for i in dijkstra1(costs, r):
        print(i if i!=inf else "INF")


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

typedef long long ll;

const ll MOD = 1000000007;
ll dp[5005][5005], n, x;
string soal;

ll pgt(ll x, ll p){
	if(p==0) return 1;
	if(p==1) return x;
	ll a= pgt(x, p/2);
	if(p%2==1) return (((a*a)%MOD)*x)%MOD;
	return (a*a)%MOD;
}

ll f(ll l, ll step){
	if(step==0){
		if(l==x) return 1;
		else return 0;
	}
	
	ll &ret = dp[l][step];
	
	if(ret==-1){
		ret=(2*f(l+1, step-1))%MOD;
		if(l==0) ret=(ret+f(l, step-1))%MOD;
		else	 ret=(ret+f(l-1, step-1))%MOD;
	}
	
	return ret; 
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dp, -1, sizeof(dp));
	cin>>n;
	cin>>soal;
	x=soal.length();
	cout<<(f(0, n)*pgt(pgt(2, x), MOD-2))%MOD<<"\n";
}

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

#ifdef _MSC_VER
#define __typeof__ decltype
#endif

#define ITER(c)         __typeof__((c).begin())
#define FOREACH(it, c)  for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define MAX(p1,p2)      (((p1)>(p2))?(p1):(p2))

map<int,int> m;

int main(){
    int n, max = 0;
    while(cin >> n) m[n]++;
    FOREACH(it,m) max = MAX(max, it->second);
    FOREACH(it,m) if(it->second == max) cout << it->first << endl;
    return 0;
}

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

typedef struct Node{
    int x;
    struct Node *prev;
    struct Node *next;
} node;
  
node noth;
node *nil=&noth;
  
node* find(int);
  
void insert(int key){
    node *n=(node *)malloc(sizeof(node));
    if(nil->next==nil) nil->prev=n;
    n->x=key;
    n->next=nil->next;
    nil->next->prev=n;
    nil->next=n;
    n->prev=nil;
}
  
void delete(int key){
    node *it=find(key);
      
    if(it!=nil){
        it->next->prev=it->prev;
        it->prev->next=it->next;
        free(it);
    }
}
  
void deletef(void){
    node *it=nil->next;
    if(it!=nil){
        it->next->prev=it->prev;
        it->prev->next=it->next;
        free(it);
    }
}
  
void deletel(void){
    node *it=nil->prev;
    if(it!=nil){
        it->next->prev=it->prev;
        it->prev->next=it->next;
        free(it);
    }
}
  
node* find(int key){
    node *it;
    for(it=nil->next;it!=nil;it=it->next){
        if(it->x==key) return it;
    }
    return nil;
}

int main(void){
    node *it;
    int n;
    int k;
    char a[20];
    nil->x=999;
    nil->prev=nil;
    nil->next=nil;
      
    scanf("%d",&n);
  
    while(n--){
        scanf("%s",a);
        if(a[0]=='i'){
            scanf("%d",&k);
            insert(k);
        }else if(a[0]=='d'){
            if(strlen(a)>8){
                if(a[6]=='F') deletef();
                else if(a[6]=='L') deletel();
            }else{
                scanf("%d",&k);
                delete(k);
            }
        }
    }
      
    for(it=nil->next;it!=nil;it=it->next){
        if(it->next!=nil)printf("%d ",it->x);
	else printf("%d",it->x);
    }
	printf("\n");
    return 0;
}

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

#define MAX_H 50
#define MAX_W 50
#define INF 0xffff

int h, w;
char s[MAX_H][MAX_W];
int dis[MAX_H][MAX_W];
pair<int, int> pre[MAX_H][MAX_W];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool judge(int x, int y)
{
    return 0 <= x && x < h && 0 <= y && y < w
        && s[x][y] != '#' && dis[x][y] == INF;
}

void bfs(void)
{
    queue<pair<int, int> > q;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            dis[i][j] = INF;
        }
    }
    q.push(make_pair(0, 0));
    dis[0][0] = 0;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        int x = p.first, y = p.second;
        if (x == h - 1 && y == w - 1) break;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (judge(nx, ny)) {
                q.push(make_pair(nx, ny));
                dis[nx][ny] = dis[x][y] + 1;
                pre[nx][ny] = make_pair(x, y);
            }
        }
    }
}

int main(void)
{
    scanf("%d%d", &h, &w);
    for (int i = 0; i < h; i++) {
        getchar();
        for (int j = 0; j < w; j++)
            s[i][j] = getchar();
    }
    bfs();
    if (dis[h - 1][w - 1] == INF) {
        printf("-1\n");
        return 0;
    }
    int x = h - 1, y = w - 1;
    while (x != 0 || y != 0) {
        s[x][y] = '*';
        pair<int, int> tmp = pre[x][y];
        x = tmp.first;
        y = tmp.second;

    }
    s[0][0] = '*';
    int cnt = 0;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (s[i][j] == '.') cnt++;
    printf("%d\n", cnt);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define mod 1e18+10
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
int a[100005],r[100005],g[100005],b[100005];
int32_t main() {
	int n,i,j;
	cin>>n;
	string s;
	cin>>s;
	s=" "+s;
	for(i=1;i<=n;i++)
	{
		r[i]=r[i-1];
		g[i]=g[i-1];
		b[i]=b[i-1];
		if(s[i]=='R')
			r[i]++;
		else if(s[i]=='G')
			g[i]++;
		else b[i]++;
	}
	int ans=0;
	for(i=1;i<=n;i++)
	{
		if(s[i]=='R')
		{
			ans+=b[i]*(g[n]-g[i])+g[i]*(b[n]-b[i]);
			for(j=1;;j++)
			{
				if(i+j>n || i-j<1)
					break;
				if(s[i+j]=='G' && s[i-j]=='B' || s[i+j]=='B' && s[i-j]=='G')
					ans--;
			}
			
		}
		else if(s[i]=='G')
		{
			
			ans+=b[i]*(r[n]-r[i])+r[i]*(b[n]-b[i]);
			for(j=1;;j++)
			{
				if(i+j>n || i-j<1)
					break;
				if(s[i+j]=='R' && s[i-j]=='B' || s[i+j]=='B' && s[i-j]=='R')
					ans--;
			}
		}
		else 
		{
			
			ans+=r[i]*(g[n]-g[i])+g[i]*(r[n]-r[i]);
			for(j=1;;j++)
			{
				if(i+j>n || i-j<1)
					break;
				if(s[i+j]=='G' && s[i-j]=='R' || s[i+j]=='R' && s[i-j]=='G')
					ans--;
			}
		}
	}
	cout<<ans;
	
	
	
	
	
}


Measured memory_bytes: 3708
#include <algorithm>
#include <complex>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

int eval(int x) {
    int cnt = 0;
    while (x % 2 == 0) {
        cnt++;
        x /= 2;
    }
    return cnt;
}

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

    int ans = 1;
    for(int i = 1; i <= n; i++){
        if(eval(i) > eval(ans)){
            ans = i;
        }
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
    string s;cin>>s;
    int n=s.length();
    for(int i=2;i<n;++i){
        if(s[i]==s[i-2]){
            cout<<i-1<<" "<<i+1<<endl;
            return 0;
        }
    }
    rep1(i,n-1){
        if(s[i]==s[i-1]){
            cout<<i<<" "<<i+1<<endl;
            return 0;
        }
    }
    cout<<"-1 -1"<<endl;
    return 0;
}

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = __INT_MAX__;               // 2^31 - 1
const long long INFLL = __LONG_LONG_MAX__; // 2^61 - 1
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

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

int dp[100005];
bool used[100005];

int dfs(int i, vii &edge) {
    if (used[i]) return dp[i];
    used[i] = true;
    for (auto e : edge[i]) {
        chmax(dp[i], dfs(e, edge) + 1);
        used[e] = true;
    }
    return dp[i];
}

int main() {
    int n, m;
    cin >> n >> m;
    vii edge(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edge[a].push_back(b);
    }
    int ans = 0;
    rep(i, n) {
        chmax(ans, dfs(i, edge));
    }
    out(ans);
    return 0;
}


Measured memory_bytes: 8192
N = int(input())
A = list(map(int, input().split()))

c = 0
for i in range(N):
    minj = i
    for j in range(i, N):
        if A[j] < A[minj]:
            minj = j
    if A[i] != A[minj]:
        A[i], A[minj] = A[minj], A[i]
        c += 1

print(" ".join([str(a) for a in A]))
print(c)



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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll a, b, result = 0;
  cin >> a >> b;
  FOR(i, a, b + 1) {
    int l2 = i / 10000;
    int l1 = i / 1000 % 10;
    int r1 = i % 100 / 10;
    int r2 = i % 10;
    if (l2 == r2 && l1 == r1) result++;
  }
  cout << result << endl;

}

Measured memory_bytes: 256
import sys
import math
import collections
from collections import deque
#n = int(input())
n, m = map(int, sys.stdin.readline().split())
#s = input()
#x = list(map(int, sys.stdin.readline().split()))

if n <= 1:
    a = 0
else:
    a = math.factorial(n) // (math.factorial(n - 2) * 2)

if m <= 1:
    b = 0
else:
    b = math.factorial(m) // (math.factorial(m - 2) * 2)

print(a+b)


Measured memory_bytes: 3440
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define x first
#define y second
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //assert(freopen("input.txt","r",stdin));
    //assert(freopen("output.txt","w",stdout));
    ll a;
    cin>>a;
    cout<<(a+(a*a)+(a*a*a));
    return 0;
}

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

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

int main() {
  int X, a, b;
  cin >> X;
  a = X / 500;
  X = X - 500 * a;
  b = X / 5;
  int ans;
  ans = 1000 * a + 5 * b;
  cout << ans << endl;
  return 0;
}

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

#define int long long
#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
template <class T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> using V = vector<T>;
using P = pair<int, int>;

/*
 *  */


signed main() {
  string s;
  cin >> s;
  int n = sz(s);

  V<V<int>> dp(n+1, V<int>(2, 1e9));
  dp[0][0] = 0;
  rep(i, 0, n){
    int d = s[i]-'0';
    chmin(dp[i+1][0], dp[i][0] + d);
    chmin(dp[i+1][0], dp[i][1] + d);
    chmin(dp[i+1][1], dp[i][0] + (11-d));
    chmin(dp[i+1][1], dp[i][1] + (9-d));
  }

  int ans = min(dp[n][0], dp[n][1]);
  cout << ans << endl;
//  rep(i, 0, n+1) cout << dp[i][0] << " " << dp[i][1] << endl;

  return 0;
}


Measured memory_bytes: 55940
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
        return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
        var tmp = ReadIntArray();
        int a = tmp[0], b = tmp[1];

        int ans = a + b;
        ans = Math.Max(ans, a - b);
        ans = Math.Max(ans, a * b);

        WriteLine(ans);
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <map>
#include <fstream>
#include <sstream>
#include <iterator>
#include <complex>
using namespace std;

long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcd(long long a,long long b){return a*b / gcd(a,b) / gcd(a,b);}
int main()
{
	long long X;
	cin>>X;
	long long charge=100;
	int year = 0;
	while(charge < X)
	{
		charge *=1.01;
		year++;
	}
	cout<<year<<endl;
}

Measured memory_bytes: 3644
n,m = gets.split.map{|n| n.to_i}
mat = Array.new(n).map{Array.new(m)}
vec = Array.new(m)
for i in 1..n
  a = gets.split.map {|s| s.to_i}
  mat[i-1] = a
end
for i in 1..m
  j = gets.to_i
  vec[i-1] = j
end
for i in 1..n
   s = 0
   for j in 1..m
    s += mat[i-1][j-1] * vec[j-1]
  end
  puts s
end

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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int N, A, B;

int main() {
    cin >> N >> A >> B;
    if((B - A) % 2) {
        cout << "Borys"
             << "\n";
    } else {
        cout << "Alice"
             << "\n";
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<map>
#define int long long
using namespace std;

signed main() {
	string S;
	cin >> S;
  	vector<int> answer(S.size());
    S = S + 'R';
	int R = 0;
	int L = 0;
	int count = 0;
	int count2;
	for(int i = 0;i < S.size() - 1;i++) {
		if(S.at(i) == 'R') {
			R++;
		}
		else {
			L++;
		}
		if(S.at(i) == 'R' && S.at(i + 1) == 'L') {
			count = i;
		}
		if(S.at(i) == 'L' && S.at(i + 1) == 'R') {
			int A = 0;
			int B = 0;
			B += R / 2;
          	A += R - R / 2;
			A += L / 2;
			B += L - L / 2;
			answer.at(count) = A;
			answer.at(count + 1) = B;
          	R = 0;
          	L = 0;
		}
	}
	for(int i = 0;i < S.size() - 1;i++) {
		cout << answer.at(i) << " ";
	}
}

Measured memory_bytes: 1404
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char a[200+5];
int n,t;
int ans=0;
int solve(int x)
{
	int tot=0;
	char s1[100+5]={},s2[100+5]={};
	int vis1[100+5]={},vis2[100+5]={};
	for(int i=0;i<=x;i++)
		s1[i]=a[i];
	for(int i=x+1;i<=n-1;i++)
		s2[i]=a[i];
	for(int i=0;i<=x;i++)
		if(!vis1[s1[i]-'a'])
			vis1[s1[i]-'a']=1;
	for(int i=x+1;i<=n-1;i++)
		if(vis1[s2[i]-'a']&&!vis2[s2[i]-'a'])
		{
			tot++;
			vis2[s2[i]-'a']=1;
		}
	return tot;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",a);
	for(int i=0;i<=n-2;i++)
	{
		t=solve(i);
		ans=max(ans,t);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
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; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
        a[i] -= i + 1;
    }

    sort(a.begin(), a.end());
    ll d;
    if (n % 2 == 1) {
        d = a[n / 2];
    }
    else {
        d = (a[n / 2 - 1] + a[n / 2]) / 2;
    }

    ll res  = 0;
    rep(i, n) {
        res += abs(a[i] - d);
    }

    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0; i<N; i++) cin >> a[i];
  int sum = accumulate(a.begin(), a.end(), 0);
  double ave = (double)sum/N;
  int ans = 0;
  double dist=abs(a[0]-ave);
  for (int i=1; i<N; i++) {
    if (abs(a[i]-ave)<dist) {
      dist = abs(a[i]-ave);
      ans = i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import math

MOD = 10**9 + 7
n = int(input())
mp = {}
ans1 = 0


def process(lst):
	a = lst[0]
	b = lst[1]
	gcd = math.gcd(a, b)
	a //= gcd
	b //= gcd
	if b < 0:
		a *= -1
		b *= -1
	a = abs(a) if b == 0 else a
	b = abs(b) if a == 0 else b
	lst[0] = a
	lst[1] = b
	return lst


for _ in range(n):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ans1 += 1
		continue

	a, b = process([a, b])
	mp.setdefault((a, b), 0)
	mp[(a, b)] += 1

	a, b = process([-b, a])
	y = mp.setdefault( (a, b), 0)

ans = 1

taken = {}

for a, b in mp:
	if taken.get((a, b), 0):
		continue
	taken.setdefault((a, b), 0)
	taken[(a, b)] = 1

	x = mp.get( (a, b), 0)

	# print(a, b, x, end=" + ")
	a, b = process([-b, a])
	y = mp.get( (a, b), 0)

	taken.setdefault((a, b), 0)
	taken[(a, b)] = 1

	# print(a, b, y)
	ans = (ans * ( pow(2, x, MOD) + pow(2, y, MOD) - 1 + MOD) % MOD ) % MOD
	# print(ans)


ans = ( ans - 1 + ans1 + MOD ) % MOD
print(ans)






Measured memory_bytes: 176328
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

def main():
    n,k = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(k,n):
        if A[i-k]<A[i]:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 93636
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;

int main() {
    int a, b, k;
    int count = 0;
    int ans;
    cin >> a >> b >> k;
    for (int i = min(a, b); i > 0; i--) {
        if (a % i == 0 && b % i == 0) {
            count++;
        }
        if (count == k) {
            ans = i;
            goto last;
        }
    }
    last:
    cout << ans << endl;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int N=1e6;
const LL mod=998244353;
int a[N];
LL quickpow(LL a,LL b){
    if(b<0)return 0;
    LL ret=1;
    a%=mod;
    while(b){
    	//cout<<a<<"  "<<b<<endl;
        if(b&1)ret=(ret*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ret;
}
int main(){
	int n;
	cin>>n;
	int x;
	scanf("%d",&x);
	a[x]++;
	if(x!=0){
		cout<<0<<endl;
		return 0;
	}
	LL ans=1;
	int maxn=0;
	for(int i=2;i<=n;i++){
		scanf("%d",&x);
		//cout<<x<<endl;
		a[x]++;
		maxn=max(maxn,x);
	}
	if(a[0]!=1){
		cout<<0<<endl;
		return 0;
	}
	
	for(int i=1;i<=maxn;i++){
		if(a[i]==0){
			cout<<0<<endl;
			return 0;
		}
	}
	for(int i=1;i<=maxn;i++){
		//cout<<a[i-1]<<" "<<a[i]<<endl;
		ans*=quickpow(a[i-1],a[i]);
		ans%=mod;
	}
	cout<<ans<<endl;
	
	
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define MOD 1000000007
#define pb push_back
#define cy cout<<"Yes\n"
#define cn cout<<"No\n"
typedef unsigned long long int ull;
typedef long long int ll;

int a[500005];
int main()
{
    int n,odd=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i&1 && a[i]&1)
            odd++;
    }
    cout<<odd<<endl;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define KOZYUN(a) sort(all(a),greater<int>())
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,a,b; IN(n >> a >> b);
    int ans = min(n*a,b);
    ANS;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
class Edge{
public:
    int from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};

int main(){
    int N;cin >> N;
    if(N == 1){
        cout<<1<<endl;
        return 0;
    }
    vector<pair<LL,LL>> vec,pairs;
    //vector<int> x,y;
    for(int a = 0;a < N;a++){
        LL b,c;cin>> b >> c;
        vec.push_back({b,c});
    }
    for(int a = 0;a < N;a++){
        for(int b = 0;b < N;b++){
            if(a != b)pairs.push_back({vec.at(a).first-vec.at(b).first, vec.at(a).second-vec.at(b).second});
        }
    }
    map<pair<LL,LL>,LL> p;
    for(int a = 0;a < pairs.size();a++)p[pairs.at(a)]++;
    LL ans = 0;
    for(auto a : p)ans = max(ans, a.second);
    cout<<N-ans<<endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#define int long long

using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector <int> num(n);
    for (int i = 0; i < n; i++)
        cin >> num[i];
    int need = 1, ans = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] == need)
            need++;
        else
            ans++;
    }
    if (ans == n)
        cout << "-1\n";
    else
        cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1792
// ------------------------------------
// Date:2018/ 3/15
// Problem:ARC 072 Sequence c.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

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

  ll N;
  cin >> N;
  vector< ll > a(N);
  REP(i, N) cin >> a[i];

  ll opSum, epSum, opCnt, epCnt;
  opSum = epSum = opCnt = epCnt = 0ll;
  REP(i, N) {
    opSum += a[i];
    epSum += a[i];
    if (i % 2 == 0) {
      // opSum < 0 / epSum > 0
      if (opSum >= 0) {
	opCnt += abs(opSum) + 1;
	opSum = -1;
      }
      if (epSum <= 0) {
	epCnt += abs(epSum) + 1;
	epSum = 1;
      }
    } else {
      // opSum > 0 / epSum < 0
      if (opSum <= 0) {
	opCnt += abs(opSum) + 1;
	opSum = 1;
      }
      if (epSum >= 0) {
	epCnt += abs(epSum) + 1;
	epSum = -1;
      }
    }
    //  debug(opSum);
    // debug(opCnt);
    // debug(epSum);
    // debug(epCnt);
  }

  ll ans = min(opCnt, epCnt);

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



Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  ll A, B;
  cin >> A >> B;
  map<ll,int> mp;
  for(ll i=1;i*i<=A;i++){
    if(A%i==0){
      if(B%i==0) mp[i]++;
      if(i*i!=A && B%(A/i)==0){
        mp[A/i]++;
      }
    }
  }
  vector<ll> yakusu;
  for(auto y:mp){
    yakusu.pb(y.first);
  }
  int ysize = (int)yakusu.size();
  //cout << ysize << endl;
  vector<ll> ans;
  rep(i,ysize){
    bool ok = true;
    rep(j,(int)ans.size()){
      if(j==0) continue;
      if(yakusu[i] % ans[j] == 0){
        ok = false;
        break;
      }
    }
    if(ok){
      ans.pb(yakusu[i]);
    }
  }
  cout << (int)ans.size() << endl;
  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i <b; i++)
using pii = pair<int,int>;
#define all(a) a.begin(), a.end()

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

int main(){
    string a, b; cin >> a >> b;
    string s1 = "", s2 = "";

    rep(i, 0, b[0] - '0') s1 += a;
    rep(i, 0, a[0] - '0') s2 += b;

    if(s1 < s2) cout << s1 << endl;
    else cout << s2 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
	int ans = 700;
	char s[4];
	scanf("%s", s);
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'o') ans += 100;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
N,A,B,K=gets.split.map &:to_i
M=998244353;I=[1,1];*F=I;*R=I
2.upto(N){|i|I<<z=(M-M/i)*I[M%i]%M;F<<i*F[-1]%M;R<<z*R[-1]%M}
r=0;0.upto(N){|a|
	b,_=(K-A*a).divmod B
	0<=b&&b<=N&&_<1&&r=(r+F[N]**2*R[a]*R[N-a]*R[b]*R[N-b])%M
}
p r

Measured memory_bytes: 9084
#include<cstdio>
const int MAXN = 100;
int a[MAXN + 5];
int main() {
	int N;
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int x;
		scanf("%d", &x);
		a[x]++;
	}
	int mx;
	for(int i=N-1;;i--)
		if( a[i] ) {
			mx = i;
			break;
		}
	for(int i=mx;i>=mx/2+1;i--) {
		if( a[i] < 2 ) {
			puts("Impossible");
			return 0;
		}
		a[i] -= 2;
	}
	if( mx % 2 == 0 ) {
		if( a[mx/2] < 1 ) {
			puts("Impossible");
			return 0;
		}
		a[mx/2]--;
	}
	for(int i=1;i<=(mx+1)/2;i++) {
		if( a[i] ) {
			puts("Impossible");
			return 0;
		}
	}
	puts("Possible");
}

Measured memory_bytes: 128
#20131115

gets.to_i.times{
	days = 1
	y,m,d = gets.split(" ").map{|e|e.to_i}
	#y
	999.downto(y+1){|n|
		days+=20*5+19*5 if n%3!=0
		days+=20*10 if n%3==0
	}
	#m,d
	if y%3 == 0
		days+=20*(10-m)
		days+=20-d
	else
		m=10-m
		days+=20*(m/2)
		days+=19*(m/2+m%2)
		days+=20-d if m%2!=0
		days+=19-d if m%2==0
	end
	

	p days
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n;

int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    set<ll> incl;
    incl.insert(2), incl.insert(3), incl.insert(25);
    int cnt = 3;
    ll sum = 30;
    for (int i = 4; i < 15000; ++i) {
        if (cnt + 2 > n) break;
        int other = 30000 - i;
        if (incl.find(i) == incl.end() && incl.find(other) == incl.end()) {
            if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0) {
                if (other % 2 == 0 || other % 3 == 0 || other % 5 == 0) {
                    incl.insert(i), incl.insert(30000 - i);
                    cnt += 2;
                    sum += 30000;
                }
            }
        }
    }
    if (cnt < n) {
        incl.insert(15000);
        sum += 15000;
        ++cnt;
    }

    for (auto i : incl) {
        cout << i << ' ';
    }
}


Measured memory_bytes: 4580
import math
A,B,L,M=list(map(int,input().split()))
minkakudo=6*M
jikankakudo=(L*60+M)*360/(12*60)
kakudo=abs(jikankakudo-minkakudo)
if kakudo>180:
    kakudo=360-kakudo
kakudo=math.radians(kakudo)
ans=A**2+B**2-(2*A*B*math.cos(kakudo))
print(ans**(0.5))

Measured memory_bytes: 9516
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000

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

    int a;
    cin >> a;
    cout << a + a * a + a * a * a << endl;
}

Measured memory_bytes: 3644
#include <cstdio>

#include <iostream>

using namespace std;

int main()
{
  int n;
  cin>>n;
  int l[n+1];
  int sum=0;
  for(int i=1;i<=n;i++)
  {
    cin>>l[i];
    sum+=l[i];
  }
  
  bool answer=true;
  for(int i=1;i<=n;i++)
  {
  //	cout<<sum-l[i]<<l[i]<<"\n";
    if(sum-l[i]<=l[i])
       {
       	
       	//cout<<i;
       answer= false;
       break;
       }
   }
       if(answer)
       cout<<"Yes";
       else
       cout<<"No";
       
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e9+7

using namespace std;

ll n,m,ans=1;
pair < ll,ll > ar[N];

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> m;

    rep(i,0,m)
    {
        cin >> ar[i].second >> ar[i].first;
    }

    sort(ar,ar+m);

    ll i = 1;
    ll lastdeleted = ar[0].first-1;

    while(i < m)
    {
       // cout << ar[i].second << " " << ar[i].first << endl;

        if(ar[i].second <= lastdeleted && ar[i].first >= lastdeleted)
        {

        }
        else
        {
            lastdeleted = ar[i].first-1;
            ans++;
        }

        i++;
    }

    cout << ans;

    return 0;
}





Measured memory_bytes: 1792