akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e15;

struct SegmentTree {
private:
  long long n;
  vector< long long > node;//min,max
public:
  SegmentTree(vector<long long> v, vector<long long> u){
    long long sz = v.size();
    n = 1;
    while(n < sz) n *= 2;
    node.resize(2*n-1,INF);
    for(int i = 0; i < sz; ++i){
      node[i+n-1] = v[i] + u[i];
      //if(i > 0) node[i+n-1] += u[i-1];
    }
    for(int i = n-2; i >= 0; --i)
      node[i] = min(node[2*i+1],node[2*i+2]);
  }
  long long get_min(long long a, long long b, long long k=0, long long l=0, long long r=-1){
    if(r < 0) r = n;
    if(r <= a or b <= l) return INF;
    if(a <= l and r <= b) return node[k];
    long long vl = get_min(a,b,2*k+1,l,(l+r)/2);
    long long vr = get_min(a,b,2*k+2,(l+r)/2,r);
    return min(vl,vr);
  }
};

int main(){
  long long L;
  cin >> L;
  vector<long long> A(L,0), F(L+1,0), B(L+1,0), C(L+1,0), O(L+1,0);
  for(int i = 0; i < L; ++i) cin >> A[i];
  for(int i = 0; i < L; ++i) C[i+1] += A[i] + C[i];
  for(int i = 0; i < L; ++i) O[i+1] += 1-(A[i]%2) + O[i];
  for(int i = 0; i < L; ++i){
    long long t = A[i]%2;
    if(A[i] < 2) t = 2-A[i];
    F[i+1] = min(F[i]+t,C[i+1]);
  }
  for(int i = L-1; i >= 0; --i){
    long long t = A[i]%2;
    if(A[i] < 2) t = 2-A[i];
    B[i] = min(B[i+1]+t,C[L]-C[i]);
  }
  // fprintf(stderr,"F : "); for(int i = 0; i <= L; ++i) cerr << F[i] << " "; cerr << endl;
  // fprintf(stderr,"B : "); for(int i = 0; i <= L; ++i) cerr << B[i] << " "; cerr << endl;
  // fprintf(stderr,"O : "); for(int i = 0; i <= L; ++i) cerr << O[i] << " "; cerr << endl;
  SegmentTree st(B,O);
  long long ans = min({F[L],O[L],B[0],C[L],st.get_min(0,L+1)});
  for(int i = 0; i <= L; ++i){
    long long t = F[i] + st.get_min(i,L+1) - O[i];
    // if(i > 0) t -= O[i-1];
    // fprintf(stderr,"F[%d] = %lld, st.get_min(%d) = %lld\n",i,F[i],i+1,st.get_min(i+1,L+1));
    // fprintf(stderr,"O[%d] = %lld\n",i-1,O[i-1]);
    // cerr << i << " " << t << endl;
    ans = min(ans,t);
  }
  cout << ans << endl;
}


Measured memory_bytes: 15232
q, h, s, d = gets.chomp.split(" ").map(&:to_i)
n = gets.chomp.to_i
p1 = [q * 4, h * 2, s].min
p2 = [p1 * 2, d].min
if n == 1 then
  puts p1
else
  puts (n / 2) * p2 + (n % 2) * p1
end


Measured memory_bytes: 1788
n,a,b=map(int,input().split())
c,d=0,0
s=input()
for i in s:
    f=0
    if i=='a':
        if c<a+b:
            c+=1
            print('Yes')
            f=1
    elif i=='b':
        if c<a+b and d<b:
            c+=1
            d+=1
            print('Yes')
            f=1
    if f==0:
        print('No')

Measured memory_bytes: 9236
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define lcm( a, b ) ((a)/__gcd(a,b)*(b))
#define MP make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> i_P;
typedef pair< LL, LL > L_P;

const int INF = INT_MAX;
const int MIN = INT_MIN;
const LL LINF = LLONG_MAX;
const int MOD = 1000000000 + 7;
const int SIZE = 100005;

LL gcd( LL a, LL b );

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

    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    LL lc = lcm( (LL)n, (LL)m );
    map< LL, int > mp;
    bool flg = true;
    mp[1] = s[0];
    for( int i = 1; i < s.size(); ++i ) {
        mp[lc / n * i] = s[i];

    }

    if( s[0] != t[0] ) {
        cout << -1 << endl;
        return 0;

    }

    for( int i = 1; i < t.size(); ++i ) {
        if( mp[lc / m * i] != 0 ) {
            if( mp[lc / m * i] != t[i] ) {
                flg = false;
                break;

            }
        }
    }

    if( !flg ) cout << -1;
    else cout << lc;
    cout << endl;

    return 0;
}

LL gcd( LL a, LL b ) {
    if( a > b ) swap( a, b );

    LL r = a % b;
    while( r != 0 ) {
        a = b;
        b = r;
        r = a % b;

    }

    return b;

}



Measured memory_bytes: 10880
import numba
from numba import jit
import numpy as np
 
#(i,j)→(i+1,j)のように動くときはアイテムを入手できる回数がリセットされる
#dp[列][今、何個アイテムを取ったか]でdpテーブルを作る
@jit
def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])
 
R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k
 
print(main(R, C))

Measured memory_bytes: 227924
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int A, B;
            var word = Console.ReadLine().Split(' ');
            A = int.Parse(word[0]);
            B = int.Parse(word[1]);

            if (A <= 8 && B <= 8)
                Console.WriteLine("Yay!");
            else
                Console.WriteLine(":(");

            Console.ReadKey();

        }
    }
}

Measured memory_bytes: 11092
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let (h,n) = get!(usize, usize);
    let ab = get!(usize, usize; n);
    const INF: usize = 1_000_000_000_000_000;
    let mut dp = vec![INF; h+1];
    dp[0] = 0;
    for (a,b) in ab {
        for j in 0..h+1 {
            let nj = min!(j+a, h);
            dp[nj] = min!(dp[nj], dp[j]+b);
        }
    }
    println!("{}", dp[h]);
}


Measured memory_bytes: 8572
#include <bits/stdc++.h>
#define smax(a, b) ((a) < (b) ? ((a)=(b), true) : false)
#define smin(a, b) ((a) > (b) ? ((a)=(b), true) : false)
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using namespace std;

int n, k;
int rem[100];
bool dp[1000001];

int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> rem[i];
    }

    sort(rem, rem+n);

    for(int i = rem[0]-1; i <= k; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if((i - rem[j]) < 0) continue;

            //false = that person wins
            //true = that persno loses

            if(!dp[i - rem[j]])
            {
                dp[i] = true;
                break;
            }

            if(j == n-1)
            {
                dp[i] = false;
            }
        }
    }

    if(dp[k]) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
}

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

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h,"");
    for(int i = 0; i < h; i++){
        cin >> s[i];
    }
    for(int i = 0; i < h; i++){
        cout << s[i] << endl;
        cout << s[i] << endl;
    }
}

Measured memory_bytes: 256
# encoding: UTF-8
s = gets.chomp.to_s
k = gets.chomp.to_i

def count str, opts={}
  first = opts[:first] || 0
  last = opts[:last] || -1
  replaced = str.gsub(/([a-z])(\1)/, '\1A')
  return 0 unless replaced
  replaced[first..last].count('A')
end

if s.match(/^([a-z])\1*$/)
  puts ((s.length * k) / 2).to_i
  exit
end

if k == 1
  puts count(s)
  exit
end

if s[0] != s[-1]
  puts count(s) * k
  exit
end

first = s.match(/^([a-z])\1*/)[0]
last = s.match(/([a-z])\1*$/)[0]

first_count = count(s + first, last: (- first.length - 1))
last_count = count(last + s, first: last.length)

if k == 2
  puts first_count + last_count
  exit
end

puts first_count + last_count +
  (count(
   last + s + first,
   first: last.length,
   last: (- first.length - 1) 
  ) * (k-2))

Measured memory_bytes: 1916
import itertools

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

# (1,2,...,M)からN個選ぶ重複組み合わせを生成
# ex. N=3, M=4
# [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4),
# (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), (3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]

# (1,2,...,M)のリスト
l = range(1, M + 1)
nCr = list(itertools.combinations_with_replacement(l, N))
# print(nCr)

# 最終的な答え
ans = 0
for A in nCr:
    # 各組み合わせで得られる点数
    tmp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 21460
import heapq
import numpy as np

N, M = [int(a) for a in input().split()]

jobs = [[] for _ in range(M)]

for _ in range(N):
    a, b = map(lambda x: int(x), input().split())
    if a > M:
      continue
    jobs[M-a].append(b)

heap = []
ans = 0
for i in range(M-1, -1, -1):
    for b in jobs[i]:
        # 降順にするためにマイナスをつけて入れる
        heapq.heappush(heap, -b)
    if len(heap) != 0:
        # 取り出した値にマイナスをつけて元に戻す
        ans += -heapq.heappop(heap)
print(ans)

Measured memory_bytes: 27556
//whose bmi is more than or equal to 25
#include<iostream>
using namespace std;
int main() {
    int s; double w, h; //s is identity number
    char c1, c2;
    while (cin >> s >> c1 >> w >> c2 >> h) {
        //cout << w / h / h << endl;
        if (w / h / h >= 25) {
            cout << s << endl;
        }
    }
}



Measured memory_bytes: 3176
#define _CRT_SECURE_NO_WARNINGS

#include<fstream>
#include<iostream>
#include<string>
#include<iomanip>
#include<list>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;
#define no_way 100000000;


int d[400][400];


int main(int argc, char **argv){
	int n;
	int m, a, b;
	vector<pair<int, int> > v;
	

	while (cin >> n && n != 0) {
		v.clear();
		bool flag = true;
		int in_cnt = 0;
		for (int i = 0; i < n; i++) {
			cin >> m >> a >> b;
			v.push_back(make_pair(a, m));
			v.push_back(make_pair(b, -1 * m));
		}
		sort(v.begin(), v.end());

		int value = 0;
		for (int i = 0; i < v.size(); i++) {
			value += v[i].second;
			if (value > 150) {
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << "OK" << endl;
		} else {
			cout << "NG" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1196
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//cout<<setprecision(20)
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int LBI(vector<llint>&ar,llint in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
int UBI(vector<llint>&ar,llint in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
static int val[869120]={0};//最小値が親+何段か
static int dco[869120]={0};//最小値のうち右端はどこか
class seg{
public:
	
	//524288
	//(1<<19)+300000 以上
	//奇数場所優先
	void cha(int bas,int num){
		bas+=(1<<19);
		while(bas>1){
			if(bas%2==1){
				val[bas-1]+=num;
				int hen=min(val[bas],val[bas-1]);
				val[bas]-=hen;
				val[bas-1]-=hen;
				val[bas/2]+=hen;
				if(val[bas]==0){dco[bas/2]=dco[bas];}
				else{dco[bas/2]=dco[bas-1];}
			}else{
				int hen=min(val[bas],val[bas+1]);
				val[bas]-=hen;
				val[bas+1]-=hen;
				val[bas/2]+=hen;
				if(val[bas+1]==0){dco[bas/2]=dco[bas+1];}
				else{dco[bas/2]=dco[bas];}
			}
			bas/=2;
		}
	}
	int que(int bas){
		int ans=-2;
		bas+=(1<<19);
		while(bas>1){
			if(val[bas]>0){ans=-2;}
			if(bas%2==1){maxeq(ans,dco[bas-1]);}
			bas/=2;
		}
		return ans;
	}
};
int main(void){
	int n,Q,i;cin>>n>>Q;
	string str;cin>>str;
	//最小値右端+1
	set<int>clo;
	seg ki;
	for(i=0;i<n;i++){
		dco[(i+1)/2+(1<<19)]=i+1;
		if(str[i]=='('){ki.cha((i+1)/2,-1);}
		else{ki.cha((i+1)/2,1);clo.ins(i);}
	}
	dco[(1<<19)]=0;
	while(Q--){
		int q;cin>>q;q--;
		if(str[q]=='('){
			str[q]=')';
			clo.ins(q);
			ki.cha((q+1)/2,2);
			int ter=*clo.begin();
			cout<<ter+1<<endl;
			ki.cha((ter+1)/2,-2);
			clo.era(ter);
			str[ter]='(';
		}else{
			//cerr<<"de";
			str[q]='(';
			clo.era(q);
			ki.cha((q+1)/2,-2);
			int ter=ki.que((q+2)/2);
			if(ter==0){ter++;}
			cout<<ter+1<<endl;
			ki.cha((ter+1)/2,2);
			clo.ins(ter);
			str[ter]=')';
		}
		//cerr<<str<<endl;
	}
	return 0;
}


Measured memory_bytes: 12640
#include <stdio.h>

int imax(int a, int b){
  if(a>b) return a;
  else return b;
}

int main()
{
  int i,n,k;
  char str[100001];
  int b[100];
  int trans=0;
  scanf("%d%d", &n, &k);
  scanf("%s", str);
  for (i = 1; i < n; i++){
    if(str[i]!=str[i-1]) trans++;
  }
  trans=imax(trans-2*k, 0);
  int pts;
  pts=n-1-trans;
  printf("%d\n",pts);  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int main(){
	int n;
	string s, t;
	cin>>n>>s>>t;
	int ans = 0;
	for(int i = 0; i <= n; i++){
		string ss = s.substr(i);
		if(ss == t.substr(0,ss.size())){
			ans = 2*n-ss.size();
			break;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define eps 1e-7
#pragma GCC optimize ("unroll-loops")

string s;
int transition[10][10101], n, p;
ll ans;
int dp[2][10101];
ll modpow(ll x, ll y)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

int32_t main()
{
    usecppio
    cin >> n >> p >> s;
    int inv = modpow(10, p-2);
    if (p < 10)
    {
        for (int j = 0; j<10; j++)
            for (int i = 0; i<p; i++)
                transition[j][i] = ((i*10)+j)%p;
        int r = 0;
        for (int i = 0; i<n; i++)
        {
            int u = s[i]-'0';
            r = 1-r;
            memset(dp[r],0,sizeof(dp[r]));
            for (int j = 0; j<p; j++)
            {
                int k = transition[u][j];
                dp[r][k] += dp[1-r][j];
            }
            dp[r][transition[u][0]]++;
            ans += dp[r][0];
        }
        cout << ans << '\n';
    }
    else
    {
        for (int j = 0; j<10; j++)
            for (int i = 0; i<p; i++)
                transition[j][i] = (((i-j+p)%p)*(inv))%p;
        int r = 0;
        for (int i = 0; i<n; i++)
        {
            register int u = s[i]-'0';
            r = 1-r;
            for (int j = 0; j<p; j++)
            {
                int k = transition[u][j];
                dp[r][j] = dp[1-r][k];
            }
            dp[r][u]++;
            ans += dp[r][0];
        }
        cout << ans << '\n';
    }
}

Measured memory_bytes: 1044
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define INF 1000000000000000
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct edge{int to,cost;};
typedef pair<int,int> P;
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
int kaijo(int n){
	int ans=1;
	for(int i=2;i<=n;i++){
		ans*=i;
		ans%=MOD;
	}
	return ans;
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int comb(int a,int b){
	return kaijo(a)*modpow(kaijo(a-b),MOD-2)%MOD*modpow(kaijo(b),MOD-2)%MOD;
}
int n,m,a[114514],memo[114514],cnt[114514],sum;
P p[114514];
signed main(){
	cin>>n>>m;
	rep(i,n)cin>>a[i];
	sort(a,a+n);
	rep(i,m)cin>>p[i].second>>p[i].first;
	sort(p,p+m,greater<P>());
	int now=0;
	rep(i,m){
		rep(j,p[i].second){
			if(now>=n)goto no;
			if(a[now]<p[i].first){
				a[now]=p[i].first;
				now++;
			}
			else goto no;
		}
	}
	no:;
	rep(i,n){
		sum+=a[i];
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
long long a[200005],sum[200005],f[200005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=(i>=2?sum[i-2]:0)+a[i];
    }
    for(int i=2;i<=n;i++)
    {
        if(i&1)
        {
            f[i]=max(f[i-2]+a[i],f[i-1]);
        }
        else f[i]=max(f[i-2]+a[i],sum[i-1]);
    }
    cout<<f[n];
}


Measured memory_bytes: 8384
#include <cstdio>

using namespace std;

int main() {
    int h, w, a, b, i, j;
    
    scanf("%d %d %d %d", &h, &w, &a, &b);
    
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if ((i < b && j < a) || (i >= b && j >= a)) {
                putchar('0');
            } else {
                putchar('1');
            }
        }
        puts("");
    }
    
    return 0;
}


Measured memory_bytes: 1152
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
#include  <map>
#include  <new>
#include <cstdint>
#include <cctype>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

using ll = long long;
using ld = long double;
using Vii = vector<vector<int> >;
using Gjudge = vector<vector<bool>>;
using Vi = vector<int>;
using Vl = vector<ll>;
using Vd = vector<double>;
using Vld = vector<long double>;
using Vll = vector<vector<ll> >;
using Vldd = vector<vector<ld> >;
using Vs = vector<string>;
using Vb = vector<bool>;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Pli = pair<ll, int>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

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 int Mod = static_cast<int>(1e9 + 7);
const int INF = INT_MAX;
const ll LINF = LLONG_MAX / 10000;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

int main()
{
	int k;
	cin >> k;
	queue<ll> Q;
	lrep(i, 1, 10) Q.push(i);
	ll ans = 0;
	rep(i, k) {
		ll x = Q.front();
		Q.pop();
		if (i == k - 1) ans = x;
		if (x % 10 != 0) Q.push(x * 10 + (x % 10) - 1);
		Q.push(x * 10 + x % 10);
		if (x % 10 != 9) Q.push(x * 10 + (x % 10) + 1);
	}
	cout << ans << endl;
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    string c;
    cin >> c;
    int count = 0;
    for(int i=0; i<c.length(); i++){
        if(c[i]=='1') count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
using namespace std;

int n;
int W,H;
int check(int x,int y){
	if((0<=x)&&(0<=y)&&(x<=W)&&(y<=H)) return 1;
	return 0;
}

int main(){
	int x,y,r;
	cin >> W >> H >> x >> y >> r;
	int t;
	if(check(x-r,y-r)&&(check(x+r,y-r)&&check(x-r,y+r)&&check(x+r,y+r))) t = 1;
	else t = 0;
	if(t) cout << "Yes" << endl;
	else cout << "No" <<endl;

	return 0;
}

Measured memory_bytes: 1156
#include <iostream>

using namespace std;

static const int N_MAX = 100000;

int binarySearch(int S[], int n, int t);

int main(){
	int i, n, q, t, c = 0;

	int S[N_MAX] = {0};

	cin >> n;
	for (i = 0; i < n; i++)
		cin >> S[i];

	cin >> q;
	for (i = 0; i < q; i++) {
		cin >> t;
		c += binarySearch(S, n, t);
	}

	cout << c << endl;

	return 0;
}

int binarySearch(int S[], int n, int t){
	int m = 0;
	int left = 0;
	int right = n - 1;

	while ( m != ((left + right) / 2) ) {
		m = (left + right) / 2;
		if ( S[m] == t )
			return 1;
		else if ( S[m] < t )
			left = m + 1;
		else if ( S[m] > t )
			right = m;
	}

	return 0;
}

Measured memory_bytes: 3472
int main(void)
{
  int n,count;
  scanf("%d",&n);
  while(n!=0)
    {
      count = 0;
      while(n!=1)
	{
	  if(n%2==0)
	    n /=2;
	  else 
	    n = 3*n +1;
	  count++;
	}
      printf("%d\n",count);
      scanf("%d",&n);
    }
  return 0;
}

Measured memory_bytes: 600
import java.util.*

fun main(args: Array<String>) {
    val (N, M, P) = readLine()!!.split(" ").map{it.toInt()}

    val g = Graph(N + 1, 0L, 1e15.toLong()) { a, b -> a + b }

    for (i in 1..M) {
        val (A, B, C) = readLine()!!.split(" ").map{it.toInt()}

        g.edges[A].add(Edge(A, B, P.toLong() - C))
    }

    val (dist, prev, hasNegativeLoop) = bellmanFord(g, 1, N)

    println(if (hasNegativeLoop) -1 else Math.max(0, -dist[N]))
}

data class Edge<T: Comparable<T>>(val from: Int, val to: Int, val weight: T): Comparable<Edge<T>> {
    constructor(from: Long, to: Long, weight: T) : this(from.toInt(), to.toInt(), weight)

    override fun compareTo(other: Edge<T>) = weight.compareTo(other.weight)
}

class Graph<T: Comparable<T>>(val n: Int, val zero: T, val inf: T, val plus: (T, T) -> T) {
    val edges = Array(n) { ArrayList<Edge<T>>() }
}

inline fun <reified T: Comparable<T>>bellmanFord(g: Graph<T>, s: Int): Triple<Array<T>, Array<Int>, Boolean> {
    val N = g.n
    val dist = Array(N) { g.inf }
    val prev = Array(N) {-1}
    var hasNegativeLoop = false

    dist[s] = g.zero

    for (k in 1 .. N + 1) {
        for (v in 0 until N) {
            for (e in g.edges[v]) {
                if (dist[e.from] != g.inf && dist[e.to] > g.plus(dist[e.from], e.weight)) {
                    dist[e.to] = g.plus(dist[e.from], e.weight)
                    prev[e.to] = e.from
                    hasNegativeLoop = k == N + 1
                }
            }
        }
    }

    return Triple(dist, prev, hasNegativeLoop)
}

fun <T : Comparable<T>>listVertices(g: Graph<T>, s: Int, t: Int): Array<Boolean> {
    fun listReachable(g: Graph<T>, s: Int): Array<Boolean> {
        val reachable = Array(g.n) { false }
        val Q = ArrayDeque<Int>()

        reachable[s] = true
        Q.addLast(s)

        while (Q.isNotEmpty()) {
            val v = Q.pollFirst()

            for (e in g.edges[v]) {
                if (reachable[e.to]) continue
                reachable[e.to] = true
                Q.addLast(e.to)
            }
        }

        return reachable
    }

    val rG = Graph(g.n, g.zero, g.inf, g.plus)
    for (v in 0 until g.n) {
        for (e in g.edges[v]) {
            rG.edges[e.to].add(Edge(e.to, e.from, e.weight))
        }
    }

    val reachable = listReachable(g, s)
    val reverseReachable = listReachable(rG, t)

    return reachable.indices.map { reachable[it] && reverseReachable[it] }.toTypedArray()
}

inline fun <reified T : Comparable<T>>bellmanFord(g: Graph<T>, s: Int, t: Int): Triple<Array<T>, Array<Int>, Boolean> {
    val vs = listVertices(g, s, t)

    val refinedGraph = Graph(g.n, g.zero, g.inf, g.plus)

    for (v in 0 until g.n) {
        for (e in g.edges[v]) {
            if (vs[e.from] && vs[e.to]) {
                refinedGraph.edges[e.from].add(e)
            }
        }
    }

    return bellmanFord(refinedGraph, s)
}


Measured memory_bytes: 121204
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    int ans;
    ans = max(a+b, a-b);
    ans = max(ans, a*b);
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
 	int C = sc.nextInt();
 
      if(A==B && B==C){
    System.out.println("No");
      } else if(A!=B && B!=C && C!=A){
    System.out.println("No");    
      }else{
	System.out.println("Yes");
      }
      }
}



Measured memory_bytes: 22740
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

class Solver{

    private final int N;
    private final int[] B;

    Solver(Scanner in){
        N = in.nextInt();
        B = new int[N];
        for(int i = 0; i < B.length; i++){
            B[i] = in.nextInt();
        }
    }

    void solve(){
        int[] result = new int[N];
        for(int i = result.length - 1; i >= 0; i--){
            int max = -1;
            int idx = 0;
            int mi = B.length;
            for(int j = 0; j < B.length; j++){
                int b = B[j];
                if(b < 0)continue;
                if(b - 1 != idx++) continue;
                mi = j;
                max = b;
            }
            if(max < 0) {
                System.out.println(-1);
                return;
            }
            if(mi < B.length) B[mi] = -1;
            result[i] = max;
        }
        System.out.println(Arrays.stream(result).mapToObj(String::valueOf).collect(Collectors.joining("\n")));
    }
}

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

        new Solver(in).solve();

        in.close();
    }
}

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

int main(){
  string W; cin >> W;
  transform(W.begin(), W.end(), W.begin(), ::toupper);  
  string T;
  int ans = 0;
  while(cin >> T, T!="END_OF_TEXT"){
    transform(T.begin(), T.end(), T.begin(), ::toupper);  
    if(W==T) ans++;
  }
  cout << ans << endl;
}



Measured memory_bytes: 3172
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-06-22 17:09
# @url:https://atcoder.jp/contests/abc171/tasks/abc171_c
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    n=int(input())
    ans=""
    while n>=1:
        m=n%26
        if m>0:
            ans+=(chr(ord('a')+m-1))
            n=n//26
        else:
            ans+="z"
            n=n//26-1
    print (ans[::-1])
if __name__ == "__main__":
    main()

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

int main(){
  int X,Y;
  cin >> X >> Y;
  bool flag = false;
  for(int i=0;i<=X;i++){
    if(i*2 + (X-i)*4 == Y){
      flag = true;
      false;
    }
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3548
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    A=[*pin()]

    mon=1000
    stocks=0
    final=0
    for i in range(N-1):

        if A[i]>A[i+1]:# sell
            if stocks>0:
                #print("yaa")
                mon+=stocks*A[i]
                stocks=0
            final=0
            
        elif A[i]<A[i+1]: #buy

            stocks+=mon//A[i]
            mon=mon%A[i]
            final=1
        #print(mon,stocks)
    print(mon+stocks*A[-1])
            
#%%submit!
resolve()


Measured memory_bytes: 61880
C = Array.new(3){gets.split.map(&:to_i)}

Y = [0]
X = C[0]
Y[1] = C[1][0] - X[0]
Y[2] = C[2][0] - X[0]

answer = true
for i in 1..2
    for j in 1..2
        if C[i][j] != X[j] + Y[i]
            answer = false
        end
    end
end

puts answer ? "Yes" : "No"

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cctype>
#include <map>
#include <vector>
#include <queue>

#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
	ll n, m;
	cin >> n >> m;
	vector<pair<ll,ll>> p(n);
	rep(i, 0, n) {
		int a, b;
		cin >> a >> b;
		p[i]=make_pair(a,b);
	}
	sort(p.begin(), p.end());
	ll ans = 0;
	for (int i = 0;m > 0;i++) {
		 ll num = min(m, p[i].second);
		 m -= num;
		 ans += num * p[i].first;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#define ll long long
using namespace std;
int main() {
	ll n;
	cin >> n;
	if (n % 2 == 0) {
		cout << n << endl;
	}
	else {
		cout << n * 2 << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll t,n,i,j,k,x;
    cin>>n;
    vector<ll>vi;
    for(i = 0 ;i<n ;i++)
    {
        cin>>x;
        vi.push_back(x);
    }
    if(n%2 ==0)
    {
        for(i = n-1 ;i>=0 ;i-=2)
            cout<<vi[i]<<" ";
        for(i = 0 ;i<n ;i+=2)
            cout<<vi[i]<<" ";
        cout<<endl;
    }
    else
    { for(i = n-1 ;i>=0 ;i-=2)
            cout<<vi[i]<<" ";
             for(i = 1 ;i<n ;i+=2)
            cout<<vi[i]<<" ";
            cout<<endl;

    }
    return 0 ;
}



Measured memory_bytes: 3824
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>

using namespace std;

int main()
{
  int64_t a, b, c;

  cin >> a >> b >> c;

  if (c - a - b > 0 && 4 * a * b < (c - a - b) * (c - a - b)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int count = 0;
    vector<int> check(n);
    bool bool_check;
    int d1, d2;
    bool_check = false;
    for (int i = 0; i < n; i++){
        scanf("%d %d", &d1, &d2);
        check[i] = (d1 == d2);
    }
    for (int i = 0; i < n; i++){
        if (check[i]){
            count++;
        }else{
            count = 0;
        }
        if (count == 3){
            bool_check = true;
        }
    }

    cout << ((bool_check) ? "Yes" : "No");
}

Measured memory_bytes: 3684
#![allow(unused_macros)]

macro_rules! line {
    () => {{
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        buf
    }};
}
macro_rules! line_as_vec {
    ( $t:ty ) => {
        line!()
            .trim()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect::<Vec<$t>>()
    };
}
macro_rules! line_parse {
    ( $( $i:ident : $t:ty ),* ) => {
        let ( $( $i ),* ) = match &line!().split_whitespace().collect::<Vec<_>>()[..] {
            &[ $( $i ),* ] => ( $( $i.parse::<$t>().unwrap() ),* ),
            _ => panic!(),
        };
    };
}

fn main() {
    line!();
    let a_vec = line_as_vec!(usize);

    let mut var = 0;
    let mut state = std::collections::HashSet::<usize>::new();

    for a in a_vec {
        if a >= 3200 {
            var += 1;
        } else {
            state.insert(a / 400);
        }
    }

    let mut ans = (state.len(), state.len());
    if var > 0 {
        ans.0 = std::cmp::max(1, ans.0);
        ans.1 += var;
    }

    println!("{} {}", ans.0, ans.1)
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define all(z) (z).begin(),(z).end() 
#define MOD 1000000007
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll isprime(ll n)
{
	for(int i=2;i<n;i++)
		if(n%i==0)
		return 0;
		
	return 1;	
}
ll gcd(ll a,ll b)
{ 
    if(a==0) 
        return b;  
    return gcd(b%a,a);  
 } 
ll lcm(ll a,ll b)
{
	return (a*b)/gcd(a,b);
}
int main()
{ 
    FAST;
    ll a,b;
    cin>>a>>b;
    cout<<lcm(a,b);
    
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
main()
{
	int a,b,c,d,e,f=0;
	cin>>a>>b>>c>>d>>e;
	if(a+b<=c*2) f=f+a*d+b*e;
	if(a+b>c*2)
	{
		if(d<=e) 
		{
			if(c*2>=b) f=d*2*c+f+b*(e-d);
			if(c*2<b) f=e*2*c;
		}
		if(d>e) 
		{
			if(c*2>=a) f=e*2*c+f+a*(d-e);
			if(c*2<a) f=d*2*c;
		}
	}
	cout<<f;
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

long long num_counter[100100];
//int num_counter[101];

int main(){
    long long N;
    cin >> N;
    for(long long i=1; i<=N; ++i){
        long long j;
        cin >> j;
        num_counter[j]++;
    }

    long long ans = 0;
    for(long long i=1; i<=100100; ++i){
        long long tmp = (i * num_counter[i]);
        ans += tmp;
    }

    long long Q;
    cin >> Q;
    for(long long i=0; i<Q; ++i){
        long long B, C;
        cin >> B >> C;


        long long tmp = num_counter[B];
        num_counter[C] += tmp;
        num_counter[B] = 0;

        ans -= (B * tmp);
        ans += (C * tmp);

        cout << ans << endl;
    }

}

Measured memory_bytes: 4372
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main (){
    int n;
    cin>>n;
    vector<ll> v(n);
    rep(i,0,n)cin>>v[i];
    ll sum=0;
    ll ans1=0;
    rep(i,0,n){
        sum+=v[i];
        if(i%2==0){//purasu
            if(sum<=0){
                ans1+=abs(sum)+1;
                sum=1;
            }
        }else {
            if(sum>=0){
                ans1+=abs(sum)+1;
                sum=-1;
            }
        }
    }
    ll ans2=0;
    sum=0;
    rep(i,0,n){
        sum+=v[i];
        if(i%2==0){//mainasu
            if(sum>=0){
                ans2+=abs(sum)+1;
                sum=-1;
            }
        }else {
            if(sum<=0){
                ans2+=abs(sum)+1;
                sum=1;
            }
        }
    }
    cout<<min(ans1,ans2)<<endl;
}


/*

*/


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=998244353;
const LL LINF=1LL<<62;
const int INF=1<<20;

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  int n;
  F f;
  G g;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int n_,F f,G g,T ti):
    f(f),g(g),ti(ti){
    init(n_);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.assign(2*n-1,ti);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(int a,int b){
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }
 
  int find(int a,int b,function<bool(T)> &check,int k,int l,int r){
    if(!check(dat[k])||r<=a||b<=l) return -1;
    if(k>=n-1) return k-(n-1);
    int m=(l+r)>>1;
    int vl=find(a,b,check,k*2+1,l,m);
    if(~vl) return vl;
    return find(a,b,check,k*2+2,m,r);
  }
   
  int find(int a,int b,function<bool(T)> &check){
    return find(a,b,check,0,0,n);
  }
   
};

int main(){
    int N;cin >> N;
    vector<int> b(N);
    int sum=0;
    for (int i = 0; i < N; i++) {
        cin >> b[i];
        if(!b[i]) sum++;
    }
    int Q;cin >> Q;
    vector<int> v[N+1];
    for (int i = 0; i < Q; i++) {
        int l,r;cin >> l >> r;
        l--;r--;
        v[l].pb(r);
    }
    SegmentTree<int,int> rmq(N,
                [](int a,int b){return min(a,b);},
                [](int a,int b){return b;},
                INF);
    rmq.update(0,0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            int to = v[i][j],from = i;
            rmq.update(to+1,rmq.query(from,to+2));
        }
        rmq.update(i+1,min(rmq.query(i,i+1)+(b[i]?1:-1),rmq.query(i+1,i+2)));
    }
    cout << sum+rmq.query(N,N+1) << endl;
    return 0;
}


Measured memory_bytes: 11776
#pragma region RegionDefs
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "boost/multi_array.hpp"
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T=int> using P  = pair<T, T>;
template<class T=int> using V  = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) int __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
#pragma endregion RegionDefs

void solve()
{
    IN(n);
    int dp[100005];
    auto can = {1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049};
    reps(i, 1, n+1)
    {
        int m = INF;
        for (auto&& j: can)
        {
            if (i < j) continue;
            m = min(m, dp[i-j]+1);
        }
        dp[i] = m;
    }
    cout << dp[n] << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int64_t solution(int64_t a,int64_t b)
{
	int64_t key,target=a*b;
	for (int64_t i=sqrt(static_cast<long double>(target -1));i<std::max({a,b});++i)
	{
		if (target>i*i)
		key=i;
		else
		break;
	}
	int64_t ans=2*key;
	if (a<=key)
		ans-=1;
	if (b<=key)
		ans-=1;
	if (key*(key+1)>=target)
		ans-=1;
	return ans;
}
 
int main()
{
	int q;
	std::cin>>q;
	for (int i=0;i<q;++i)
	{
		int64_t a,b;
		std::cin>>a>>b;
		std::cout<<solution(a,b)<<std::endl;
	}
}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong();
        long time = 0;
        while(true) {
            if(time*(time+1)/2 >= x) {
                System.out.println(time);
                return;
            } else {
                time++;
            }
        }
    }
}


Measured memory_bytes: 21844