akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int N=2e5+20;  
int n,m,a[N];  
vector<int> e[N];  
int vis[N];  
int f[N][15];  
struct node{  
    int v,d,c;  
}q[N];  
void fun(int u,int d,int c)  
{  
    if(f[u][d]!=-1)  
        return;  
    if(!a[u])//已经被编号大的上过色   
    a[u]=c;  
    if(d==0)//边界   
        return;  
    for(int i=0;i<e[u].size();i++)  
    {  
        int v=e[u][i];  
        fun(v,d-1,c);  
    }  
    f[u][d]=1;  
}  
int main()  
{  
    while(cin>>n>>m)  
    {  
        int u,v;  
        for(int i=1;i<=n;i++)  
            e[i].clear();  
        memset(a,0,sizeof(a));  
        memset(f,-1,sizeof(f));  
        for(int i=0;i<m;i++)  
        {  
            scanf("%d%d",&u,&v);  
            e[u].push_back(v);  
            e[v].push_back(u);  
        }  
        int Q;  
        cin>>Q;  
        for(int i=0;i<Q;i++)  
            scanf("%d%d%d",&q[i].v,&q[i].d,&q[i].c);  
        for(int i=Q-1;i>=0;i--)  
        {  
            fun(q[i].v,q[i].d,q[i].c);  
        }  
        for(int i=1;i<=n;i++)  
            cout<<a[i]<<endl;  
    }  
    return 0;  
}  

Measured memory_bytes: 23544
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const ll mod=1000000007;
const ll INF=1e15;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define U_ERASE(V) V.erase(unique(ALL(V)), V.end())
#define pb push_back
#define mp make_pair
#define MODP(A,B) A=(A+B)%mod
typedef pair<ll,ll> P;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

const ll MAXN=100001;

ll d[MAXN][20];

int main(){
    ll N; cin>>N;
    vec x(N);
    rep(i,N) cin>>x.at(i);
    
    ll Le; cin>>Le;
    rep(i,MAXN) rep(j,20) d[i][j]=INF;
    rep(i,N) d[i][0]=(upper_bound(ALL(x),x.at(i)+Le)-x.begin())-1;
   
    
    
    rep(k,19){
        if(d[0][k]==N-1) break;
        rep(i,N) {
            if(d[i][k]>=N-1) break;
            d[i][k+1]=d[d[i][k]][k];
        }
    }
   
   
    
    ll Q; cin>>Q;
    vec ans;
    rep(i,Q){
        ll L,R; cin>>L>>R;
        L--; R--;
        if(L>R) swap(L,R);
        ll A=0;
        while(true){
            if(d[L][0]>R) {A++; break;}
            ll* x=upper_bound(d[L],d[L]+20,R);
            ll X=(ll)(x-d[L])-1;
            A+=(1<<X);
            L=d[L][X];
            if(L==R) break;
        }
        ans.pb(A);
    }
    /*rep(i,N){
        cout<<i<<':';
        rep(k,19){
            if(d[i][k]>N) break;
            cout<<d[i][k]<<' ';
        }
        cout<<endl;
    }*/
    rep(i,Q) cout<<ans.at(i)<<endl;
}

Measured memory_bytes: 18164
#include <iostream>
#include <string>
#include <map>
#include <cmath>

using namespace std;

long long fact(long long x, int life) {
  if (life == 0)
    return 1;
  else if (x == 1)
    return 1;
  else
    return (x * fact(x - 1, life - 1)) % 1000000007;
}

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  string s;
  cin >> s;

  map<char, int> m;
  for (int i = 0; i < N; ++i) {
    if (m.find(s[i]) == m.end())
      m[s[i]] = 0;
    ++m[s[i]];
  }

  long long ret = 1;
  for (map<char, int>::iterator i = m.begin(); i != m.end(); ++i) {
    ret *= i->second + 1;
    ret %= 1000000007;
  }

  cout << ret - 1 << endl;

  return 0;
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
	int a,b[200001],min,ans=0;
	cin>>a;
	for(int i=1;i<=a;i++){
		cin>>b[i];
		if(i==1){
			min=b[i];
			ans++;
		}
		else if(b[i]<=min){
			min=b[i];
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#define ll long long
using namespace std;
int gcd(int a,int b) {
    while (a ^= b ^= a ^= b %= a);
    return b;
}
int T;
int main() {
//    for (cin >> T; T; T--) {
//
//    }
    unsigned long long int x,num=100;
    scanf("%llu",&x);
    for(int i=1;num<=x;i++)
    {
        num*=1.01;
        num=(unsigned long long int) num;
        if(num>=x)
        {
            printf("%d",i);
            break;
        }
    }
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

struct Queue {
    Queue() {
        mBack = 0;
        mFront = 0;
    }

    void enqueue(ll x) {
        Q[mBack++] = x;
    }

    ll front() {
        if (mBack == mFront) {
            return INF;
        }
        return Q[mFront];
    }

    void dequeue() {
        if (mFront == mBack)
            return;
        mFront++;
    }

    ll Q[200005];
    ll mBack;
    ll mFront;
};

Queue Queues[1005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, Q;
    cin >> N >> Q;
    REP(_, Q) {
        ll q;
        cin >> q;
        if (q == 0) {
            ll t, x;
            cin >> t >> x;
            Queues[t].enqueue(x);
        }
        else if (q == 1) {
            ll t;
            cin >> t;
            ll front = Queues[t].front();
            if (front == INF)
                continue;
            cout << Queues[t].front() << endl;
        }
        else {
            ll t;
            cin >> t;
            Queues[t].dequeue();
        }
    }

    return 0;
}


Measured memory_bytes: 8680
N = int(input())
S = input().strip()
dmin = 0
for i in range(N):
    if S[i]=="#":
        dmin += 1
d = dmin
for i in range(N-1,-1,-1):
    if S[i]=="#":
        d = d-1
    else:
        d = d+1
    dmin = min(dmin,d)
print(dmin)

Measured memory_bytes: 3500
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const ll MOD = 1000000007;
string s;
ll dp[100010][4];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> s;
  for (int i = 0; i < 4; i++) {
    dp[0][i] = (i == 0);
  }
  for (int i = 0; i < s.size(); i++) {
    dp[i + 1][0] = dp[i][0] * (s[i] == '?' ? 3 : 1) % MOD;
    for (int j = 0; j + 1 < 4; j++) {
      dp[i + 1][j + 1] += dp[i][j + 1] * (s[i] == '?' ? 3 : 1) % MOD;
      dp[i + 1][j + 1] %= MOD;
      dp[i + 1][j + 1] += dp[i][j] * (s[i] == '?' || s[i] == "ABC"[j] ? 1 : 0);
      dp[i + 1][j + 1] %= MOD;
    }
  }
  cout << dp[s.size()][3] << endl;

  return 0;
}

Measured memory_bytes: 3664
# include "iostream"
# include "cstdio"

using namespace std;

const int maxm=1e5+10;
const int M=26;
const int Mod=1e9+7;

int N,Cnt[M];
char S[maxm]; 

int main(){
	register int i,j;
	register long long Ans=1; 
	scanf("%d",&N);
	scanf("%s",S+1);
	for(i=1;i<=N;i++) Cnt[S[i]-'a']++;
	for(i=0;i<M;i++) Ans=(Ans*(Cnt[i]+1))%Mod;
	Ans--;
	if(Ans<0) Ans+=Mod;
	printf("%lld",Ans);
	return 0; 
} 

Measured memory_bytes: 384
import math

n = int(input()) - 1
l = [list(map(int, input().split())) for i in range(n)]

for i in range(n):
    time = l[i][0] + l[i][1]

    for j in range(i + 1, n):
        if time <= l[j][1]:
            time = l[j][1]
        elif time % l[j][2] != 0:
            time = int(math.ceil(time / l[j][2]) * l[j][2])
        
        time += l[j][0]
    
    print(time)

print(0)

Measured memory_bytes: 3188
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char x[10001];
    struct node *next;
} node;

int main(void) {
    int i;

    node *head = NULL, *cur = NULL;
    while( 1 ){
        node *new = (node *)malloc(sizeof(node));
        if( new == NULL ) exit(-1);
        scanf("%s", new->x);
        new->next = NULL;
        if( new->x[0] == '0' ) break;
        if( head == NULL ) head = new;
        else cur->next = new;
        cur = new;
    }

    int sum;
    cur = head;
    while( cur ){
        sum = 0;
        for( i = 0; cur->x[i]; ++i ){
            sum += cur->x[i] - '0';
        }
        printf("%d\n", sum);
        cur = cur->next;
    }
  
    return 0;
}

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

#define rep(x, y) for (int i = (x); i < (y); i++)

typedef long long ll;

using namespace std;

void solve() {
    int r, d, x[11];
    cin >> r >> d >> x[0];

    rep(1, 11) {
        x[i] = r * x[i-1] - d;
    }

    rep(1, 11) {
        cout << x[i] << endl;
    }
}

int main() {
    solve();

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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


int main() {

    int N;
    cin >> N;
    int h, tmp = 0, count = 0, m = 0;
    REP(i, N){
        cin >> h;
        if (h > tmp){
            count = 0;
            tmp = h;
        }else{
            count++;
            m = max(count, m);
            tmp = h;
        }
        //cout << count << endl;
    }
    cout << m << endl;
    return 0;
}


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

int main(){
  ll h, n;
  ll INF = 10e9;
  cin >> h >> n;
  vector<ll> a(n), b(n);
  rep(i, n){
    cin >> a[i] >> b[i];
  }
  vector<ll> dp(h+1, INF);
  dp[0] = 0;
  rep(i, h){
    rep(j, n){
      ll aa = a[j];
      ll bb = b[j];
      ll dh = (i+1) - aa;
      if(dh <= 0){
        if(dp[i+1] > bb) dp[i+1] = bb;
      }else{
        if(dp[i+1] > bb + dp[dh]) dp[i+1] = bb + dp[dh];
      }
  //    cout << dp[i+1] << " ";
    }
//    cout << endl;
  }
  cout << dp[h] << endl;
}


Measured memory_bytes: 384
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
H = map(int, raw_input().split())
num = ans = 0
for i in range(N):
    if H[i] >= num:
        ans += 1
    num = max(num, H[i])
print ans

Measured memory_bytes: 2812
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>

typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	ll s = a + b;
	cout << (n / s) * a + min(a, n % s) << endl;

	return 0;
}


Measured memory_bytes: 3604
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, u, v = [int(i) for i in input().split()]
u -= 1
v -= 1
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

uu = [0] * n
vv = [0] * n


def dfs(ve, r=u, d=0, rr=-1):
    ve[r] = d
    for i in e[r]:
        if i == rr:
            continue
        dfs(ve, i, d + 1, r)


dfs(uu, u)
dfs(vv, v)


ans = 0
for i, j in zip(uu, vv):
    if i <= j:
        ans = max(ans, j)
print(ans-1)


Measured memory_bytes: 117036
import sys
input = sys.stdin.readline

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
l = p[:X]+q[:Y]
l.sort()
s = sum(l)
ans = s
pre = s

for i in range(min(len(l), C)):
    ans = max(ans, pre-l[i]+r[i])
    pre = pre-l[i]+r[i]

print(ans)

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

int main() {
	int n;
	cin >> n;
	ll V = 0, E = 0;
	rep(i,n) V += ll(i+1)*(n-i);
	rep(i,n-1) {
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a,b);
		E += ll(a)*(n - b + 1);
	}
	cout << V - E << endl;
	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define s(x) (x).begin(),(x).end();
using namespace std;
typedef long long 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 ll INF = 1LL<<60;

int main(){

    int  N,W;
    cin >> N>>W;

    ll weight[110],varue[110];
    rep(i,N)cin >> weight[i] >> varue[i];
    ll max_v=110000;

    ll dp[110][max_v];
    rep(i,110){
        rep(j,max_v)dp[i][j]=INF;
    }
    
    dp[0][0]=0;

    rep(i,N){
        rep(j,max_v){
            if(j>=varue[i]) chmin(dp[i+1][j], dp[i][j-varue[i]] + weight[i]);
            
            chmin(dp[i+1][j],dp[i][j]);
        }
    }   
    ll ans = 0;
    rep(i,max_v){
        if(dp[N][i]<=W)ans = i;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 94848
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
#define FOR(i,k,n) for(int i=(k);i<(n);++i)

int main(){
    int N ;ll K;cin >> N >> K;
    vector<ll> a(N);
    vector<ll> f(N);
    FOR(i,0,N) cin >> a[i];
    FOR(i,0,N) cin >> f[i];
    sort(a.begin(),a.end());
    sort(f.begin(),f.end(),greater<ll>());
    ll ub=INF,mid,lb=-1;
    while(ub-lb>1){
        mid = (ub+lb)/2;
        ll x = 0;
        FOR(j,0,N){
            x += max(a[j]-(mid/f[j]),0LL);
        }
        if (x<=K) ub=mid;
        if (x>K) lb=mid;
    }
    cout << ub << endl;
    return 0; 
}

Measured memory_bytes: 3328
x, y = gets.split().map(&:to_i)
S = gets.split().map(&:to_i)
T = gets.split().map(&:to_i)
MOD = 10 ** 9 + 7
array = Array.new(x + 1) { Array.new(y + 1, 1) }

x.times do |n|
  y.times do |m|
    if S[n] == T[m]
      array[n+1][m+1] = (array[n][m+1] + array [n+1][m]) % MOD
    else
      array[n+1][m+1] = (array[n][m+1] + array [n+1][m] - array[n][m]) % MOD
    end
  end
end

puts array[-1][-1]

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()

ll N, M;
vii drink;

int main() {
    cin >> N >> M;
    REP (i, N) {
        int a, b;
        cin >> a >> b;
        drink.PB(MP(a,b));
    }
    sort(ALL(drink));
    int i = 0;
    ll ans = 0;
    while (M) {
        ll a = drink[i].first, b = drink[i].second;
        i++;
        ans += a * min(M, b);
        M -= min(M, b);
    }
    cout << ans << endl;
}

Measured memory_bytes: 2420
#include <iostream>
#include <algorithm>

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

typedef long long int ll;

using namespace std;

ll h[100000];
int N;
ll A,B;

bool enough(ll T){
    ll d = T*B;
    int n=0;
    int i=0;
    while(h[i]-d>0){
        n += (h[i]-d)/(A-B);
        if((h[i]-d)%(A-B))
            n++;
        i++;
        if(n>T)
            return false;
    }
    return true;
}

int main(){
    cin >> N >> A >> B;
    rep(i,N){
        cin >> h[i];
    }

    sort(h,h+N,greater<ll>());
    ll right=0,left=1000000000;
    while(left-right>1){
        ll T = (left+right)/2;
        if(enough(T)){
            left = T;
        }else{
            right = T;
        }
    }
    cout << left << endl;
}

Measured memory_bytes: 1024
#include<cstdio>

/* 配列の要素を順番に出力 */
void trace(int A[], int N) {
  int i;
  for ( i = 0; i < N; i++ ) {
    if ( i > 0 ) printf(" ");  /* 隣接する要素の間に１つの空白を出力 */
    printf("%d", A[i]);
  }
  printf("\n");
}

/* 挿入ソート（0オリジン配列） */
void insertionSort(int A[], int N) {
  int i, v, j;
  for ( i = 1; i < N; i++ ) {
    v = A[i];
    j = i - 1;
    while ( j >= 0 && A[j] > v ) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    trace(A, N);
  }
}

int main() {
  int N, i, j;
  int A[100];

  scanf("%d", &N);
  for ( i = 0; i < N; i++ ) scanf("%d", &A[i]);

  trace(A, N);
  insertionSort(A, N);

  return 0;
}


Measured memory_bytes: 2732
#include<bits/stdc++.h>
using namespace std;                                                            
#define pb push_back                                                            
#define mp make_pair                                                                                                                                
#define sqr(a) ((a) * (a))                                                      
#define io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);   
#define co() cout.precision(10);                                                
#define F for(li i=0;i<n;i++)
#define fo(i,a,n) for(i=a;i<n;i++)
#define ne cout<<"\n"; 
#define test int t;cin>>t;while(t--)
//#define oj #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif

typedef long long li;
typedef long double ld;

const li mod = 1000000007;
int main() 
{
    io();
    li n,k;
    cin>>n;
    li a[n],c=0,i;map<li,li>m;
    F {cin>>a[i];m[a[i]]++;c=c^a[i];}
   F 
   {
   	cout<<(li)(c^a[i])<<" ";
   	
   }
}

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

if A[0] == 1 and N == 0:
    print(1)
    exit()

if A[0] >= 1:
    print(-1)
    exit()

# 根から見たときにあり得る各層最大の要素数
max_leaf = [0] * (N + 1)
max_leaf[0] = 1
leaf = 1
for i in range(N):
    leaf = 2 * (leaf - A[i]) 
    if leaf < 0:
        print(-1)
        exit()
    max_leaf[i+1] = leaf

result = [0] * (N+1)
result[N] = A[N]
for i in reversed(range(N)):
    if result[i+1] + A[i] <= max_leaf[i]:
        result[i] = result[i+1] + A[i]
    elif -(-result[i+1] // 2) > max_leaf[i]:
        print(-1)
        exit()
    else:
        result[i] = max_leaf[i]

print(sum(result))


Measured memory_bytes: 701628
N, K = map(int,input().split( ))
H = [int(i) for i in input().split( )]

H = sorted(H)
def binary_search(arr, x):
    start = 0
    end = len(arr)-1
    while(end >= start):
        mid = int(start + (end-start)/2)
        if x > arr[mid]:
            start = mid+1
        elif x < arr[mid]:
            end = mid -1
        else:
            for i in range(mid-start):
                if arr[mid-i-1] < x:
                    start = mid - i
                    break
            break
    return (N-start)
print(binary_search(H, K))

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

int main(){
    int r, c;
    cin >> r >> c;
    int mat[r+1][c+1];
    for(int i=0; i<r+1; i++){
        for(int j=0; j<c+1; j++){
            if(i==r){
                mat[i][j] = 0;
            }else if(j==c){
                mat[i][j] = 0;
            }else{
                cin >> mat[i][j];
            }
            
        }
    }
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            mat[r][j] += mat[i][j];
            mat[i][c] += mat[i][j];
            
        }
    }
    for(int i=0; i<c; i++){
        mat[r][c] += mat[r][i];
    }
    
    for(int i=0; i<r+1; i++){
        for(int j=0; j<c+1; j++){
            
            if(j==c){
                cout << mat[i][j];
            }else{
                cout << mat[i][j] << ' ';
            }
        }
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3000
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int n;
int main(){
    cin>>n;
    vector<ll> a(n);
    rep(i,n)    cin>>a[i];
    ll sum=0,ans1=0,ans2=0;
    bool flag=true;
    rep(i,n){
        ll tmp;
        if(i==0)    tmp=-1;
        else    tmp=sum;    
        sum+=a[i];
        if((tmp<0&&sum<=0)){
            ans1+=abs(sum)+1;
            sum=1;
        }
        else if((tmp>0&&sum>=0)){
            ans1+=abs(sum)+1;
            sum=-1;
        }
    }    
    sum=0;
    rep(i,n){
        ll tmp;
        if(i==0)    tmp=1;
        else    tmp=sum;
        sum+=a[i];
        if((tmp<0&&sum<=0)){
            ans2+=abs(sum)+1;
            sum=1;
        }
        else if((tmp>0&&sum>=0)){
            ans2+=abs(sum)+1;
            sum=-1;
        }
    }    
    cout<<min(ans1,ans2)<<endl;
    return 0;
}


Measured memory_bytes: 1024
// ABC082A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	int x;
	x = (a + b) / 2;
	if (((a+b) % 2) == 0) cout << x << endl;
	else cout << x + 1 << endl;
	return 0;
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


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

typedef long long ll;
typedef int keytype;

int gcd(int a, int b){ return (a % b) ? gcd(b, a % b) : b;}
int lcm(int a, int b){ return (a / gcd(a, b)) * b;}

/* a[0], ..., a[n-1] の数の最大公約数 */
int ngcd(int n, int a[])
{
    int i, d;

    d = a[0];
    for (i = 1; i < n && d != 1; i++)
        d = gcd(a[i], d);
    return d;
}

void quicksort(keytype a[], int first, int last)
{
    int i, j;
    keytype x, t;

    x = a[(first + last) / 2];
    i = first;  j = last;
    for ( ; ; ) {
        while (a[i] < x) i++;
        while (x < a[j]) j--;
        if (i >= j) break;
        t = a[i];  a[i] = a[j];  a[j] = t;
        i++;  j--;
    }
    if (first  < i - 1) quicksort(a, first , i - 1);
    if (j + 1 < last) quicksort(a, j + 1, last);
}

int is_prime(int x){
    if(x <= 1) return 0;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) return 0;
    }
    return 1;
}

int is_substr(char s[], char t[], int i){
    int flag = 1;

    if(s[i] == '\0') flag = 0;

    for(int j = 0; j < strlen(t); ++j, ++i){
        if(s[i] != t[j]){
            flag = 0;
            break;
        }
    }
    return flag;
}

// factor list, number of factors, natural number
void factorize(int ftr[], int *num, int n){
    int a = 2, cnt = 0;

    while(n >= a){
        if(n % a == 0){
            n = n / a;
            ftr[cnt++] = a;
        }else{
            a++;
        }
    }
    *num = cnt;
}

//#define N 5
//int p[N + 1];
int nextperm(int p[], int N)  /* 辞書式順序で次の順列 */
{
    int i, j, t;

    i = N - 1;
    p[0] = 0;  /* 番人 */
    while (p[i] >= p[i + 1]) i--;
    if (i == 0) return 0;  /* 完了 */
    j = N;
    while (p[i] >= p[j]) j--;
    t = p[i];  p[i] = p[j];  p[j] = t;
    i++;  j = N;
    while (i < j) {
        t = p[i];  p[i] = p[j];  p[j] = t;  i++;  j--;
    }
    return 1;  /* 未了 */
}

void comb(int size1, int size2, int v[size1][size2]){
  for(int i = 0; i < size1; i++){
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for(int k = 1; k < size1; k++){
    for(int j = 1; j < k; j++){
      v[k][j] = (v[k-1][j-1] + v[k-1][j]);
    }
  }
}

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

const int inf = 1012345678;
int main(){
    int index[6] = {0, 1, 2, 3, 4, 5};
    int p[5];

    scanf("%d %d %d %d %d", &p[1], &p[2], &p[3], &p[4], &p[5]);

    //quicksort(p, 1, 5);
    int min = inf;
    do {
        int ans = 0;
        for(int i = 1; i <= 5; ++i){
            while((ans % 10) != 0){
                ans++;
            }
            ans += p[index[i]];
        }
        if(min > ans) min = ans;
    } while (nextperm(index, 5));

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

    return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <math.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <climits>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ve vector
#define umap unordered_map
#define iter iterator

void solve() {
    int n;cin>>n;
    int c=0;
    for(int i=0;i<n;i++) {
        int x;cin>>x;
        if(x%2 == 0) c++;
        if(x%4 == 0) c++;
    }
    if(c/2 >= n/2) cout<<"Yes\n";
    else cout<<"No\n";
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 384
/*input
3
abc
arc
agc
*/
#include<bits/stdc++.h>
using namespace std;

#define int long long



signed main(){
  int n;
  cin >> n;
  vector<string> a;
  for(int i = 0;i < n;i++){
  	string b;
  	cin >> b;
  	for(int j= 0;j < a.size();j++){
  		if(a[j] == b){
  			cout << "No";
  			return 0;
  		}
  	}
  	a.push_back(b);
  }
  for(int i = 1;i < n;i++){
     int x = a[i-1].size();
     if(a[i-1][x-1] != a[i][0]){
     	cout << "No";
  		return 0;
     }
  }
  cout << "Yes";
  return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  ervb
//
//  Created by Kanak Gautam on 21/04/20.
//  Copyright © 2020 Kanak Gautam. All rights reserved.
//
 
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <utility>
#define pb push_back
#define mk make_pair
#define endl "\n"
#define mod 1000000007
using namespace std;
typedef long long int lli;
typedef long double ld;
priority_queue <lli, vector<lli>, greater<lli> > ti;
vector <lli> p[200005],h,b(200005,0),f(200005,0);
lli vis[200005];
map <pair<lli,lli>,lli> mp;
set<pair<lli, lli> > s;
set<lli> st;
map<lli,lli> np,v;
queue<lli> qy;
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
      
}
lli bpow(lli a, lli b) {
    lli res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%mod;
        a = (a * a)%mod;
        b >>= 1;
    }
    return res%mod;
}
lli fact(lli i)
{
    f[0]=1;
    for(lli k=1;k<=i;k++)
    {
        (f[k]=f[k-1]*k)%=mod;
    }
    return f[i];
}
lli isprime(lli n)
{
    if(n==1)
        return 0;
    for(lli i=2;i<=sqrt(n);i++)
        if(n%i==0)
            return 0;
    return 1;
}
bool cmp(lli i,lli j)
{
    return p[i].size()<p[j].size();
}
/*void sieve()
{
    for(lli i=2;i<=5000000;i++)
    {
        if(b[i]==0)
        {
        for(lli j=2;i*j<=5000000;j++)
        {
            b[i*j]=1;
        }
        }
    }
}*/
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    string s;
    cin>>s;
    lli sum=0;
    for(lli i=0;i<s.size();i++)
    {
        sum+=s[i]-'0';
    }
    if(sum%9==0)
    {
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}



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

int main(){
    string s; cin >> s;
    for(int i = 0; i < 2; i++){
        if(s[i] != s[(i+1)%3]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
/*#include <iostream>
using namespace std;
int main(){
	
	int a,b,c,d,e;
	cin >> a >> b >> c >> d >> e;
	int answer = -a * c + d + b * e;
	if (a < 0) {
		answer = -a *c + d + b * e;
	}
	if (a>0) {
		answer = ( b - a )* e;
	}
	cout << answer << endl;
	
}*/

#include <iostream>
using namespace std;
int main(){
	
	int a, b, c, d, e;
	cin >> a >>b >>c >>d >>e;
	if (a <=40) {
		a= 40;

	}
	if (b <= 40) {
		b=40;
	}
	if (c<= 40 ) {
	c= 40;
	}
	if ( d <= 40 ) {
		d=40;
	}
	if (e<= 40 ) {
	e= 40;
	}
	int answer = (a+b +c +d + e)/ 5;
	cout << answer << endl;

	return 0;

}


Measured memory_bytes: 3088
import java.io.*;
import java.nio.CharBuffer;
import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        SimpleScanner scanner = new SimpleScanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);

        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int ans = 0;
        ans += x == 1 ? 300000 : x == 2 ? 200000 : x == 3 ? 100000 : 0;
        ans += y == 1 ? 300000 : y == 2 ? 200000 : y == 3 ? 100000 : 0;
        ans += x == 1 && y == 1 ? 400000 : 0;
        writer.println(ans);

        writer.close();
    }

    private static class SimpleScanner {

        private static final int BUFFER_SIZE = 10240;

        private Readable in;
        private CharBuffer buffer;
        private boolean eof;

        SimpleScanner(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
            buffer = CharBuffer.allocate(BUFFER_SIZE);
            buffer.limit(0);
            eof = false;
        }


        private char read() {
            if (!buffer.hasRemaining()) {
                buffer.clear();
                int n;
                try {
                    n = in.read(buffer);
                } catch (IOException e) {
                    n = -1;
                }
                if (n <= 0) {
                    eof = true;
                    return '\0';
                }
                buffer.flip();
            }
            return buffer.get();
        }

        private void checkEof() {
            if (eof)
                throw new NoSuchElementException();
        }

        private char nextChar() {
            checkEof();
            char b = read();
            checkEof();
            return b;
        }

        private String next() {
            char b;
            do {
                b = read();
                checkEof();
            } while (Character.isWhitespace(b));
            StringBuilder sb = new StringBuilder();
            do {
                sb.append(b);
                b = read();
            } while (!eof && !Character.isWhitespace(b));
            return sb.toString();
        }

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

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

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

Measured memory_bytes: 22612
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    s=input()
    k=int(input())
    l=[]
    for i in range(n):
        if s[i]==s[k-1]:
            l.append(s[k-1])
        else:
            l.append('*')
    print(''.join(l))
resolve()

Measured memory_bytes: 3060
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(input())
    G = [[i, INF] for i in range(n)]
    G[0][1] = 0
    m = {}
    for _ in range(n):
        A = list(map(int, input().split()))
        m[A[0]] = {}
        for i in range(2, len(A), 2):
            m[A[0]][A[i]] = A[i + 1]
    dp = [(0, 0)]
    while dp:
        cost, u = heappop(dp)
        for v, c in m[u].items():
            if G[v][1] > G[u][1] + c:
                G[v][1] = G[u][1] + c
                heappush(dp, (G[v][1], v))
    print("\n".join(" ".join(map(str, a)) for a in G))
MAIN()



Measured memory_bytes: 6072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,a[100000],s=0;
  cin>>n;
  for(ll i=0;i<n;i++)cin>>a[i],s+=a[i];
  if(s%(n*(n+1)/2))cout<<"NO"<<endl;
  else{
    s/=n*(n+1)/2;
    ll ans=1,ss=0;
    for(ll i=0;i<n;i++){
      ll r=-a[(i+1)%n]+a[i]+s;
      if(r>=0&&r%n==0)ss+=(-a[(i+1)%n]+a[i]+s)/n;
      else ans=0;
    }
    if(ans&&ss==s)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
  return 0;
}


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

int main(){
  int n, x, t;
  cin >> n >> x >> t;
  int ans = (n+x-1)/x*t;
  cout << ans << endl;
}


Measured memory_bytes: 3588
q = int(input())
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)//2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    if l == r:
        if is_prime(l) and is_prime((l+1)//2):
            print(1)
        else:
          print(ls[r]-ls[l-1])  
    else:
        print(ls[r]-ls[l-1])  

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

const Int inf = 1LL<<55;

Int n;
Int p[111];
vector<Int> graph[111];

map<Int, Int> mp;

using Pi = pair<Int, Int>;

Pi val[111][222][222];
Int dp_min[111][222][222];
Int dp_max[111][222][222];
bool visited[111][222][222];

Pi dfs(Int v, Int a, Int b) {
  if(visited[v][mp[a]][mp[b]]) return val[v][mp[a]][mp[b]];
  visited[v][mp[a]][mp[b]] = true;  
  if(graph[v].empty()) {
    dp_min[v][mp[a]][mp[b]] = 1;
    dp_max[v][mp[a]][mp[b]] = 1;
    val[v][mp[a]][mp[b]] = Pi(p[v], p[v]);
    //cout<<v<<" "<<val[v][mp[a]][mp[b]].first<<" "<<val[v][mp[a]][mp[b]].second<<endl;
    return val[v][mp[a]][mp[b]];
  }
  val[v][mp[a]][mp[b]] = Pi(-inf, inf);
  dp_min[v][mp[a]][mp[b]] = inf;
  dp_max[v][mp[a]][mp[b]] = -inf;  
  do {
    Pi a_tmp = Pi(a, a), b_tmp = Pi(b, b);
    Int mn = 0, mx = 0;
    bool f_mn = true, f_mx = true;
    for(Int u : graph[v]) {
      if(f_mn) {
	Int x = -dfs(u, -b_tmp.first, -a_tmp.first).first;
	mn += dp_min[u][mp[-b_tmp.first]][mp[-a_tmp.first]];
	if(x >= b_tmp.first) {
	  a_tmp.first = x;
	  f_mn = false;
	} else if(x > a_tmp.first) {
	  a_tmp.first = x;
	}
      }
      if(f_mx) {
	Int x = -dfs(u, -b_tmp.second, -a_tmp.second).second;
	mx += dp_max[u][mp[-b_tmp.second]][mp[-a_tmp.second]];	
	if(x >= b_tmp.second) {
	  a_tmp.second = x;
	  f_mx = false;
	} else if(x > a_tmp.second) {
	  a_tmp.second = x;
	}
      }
    }
    if(dp_min[v][mp[a]][mp[b]] >= mn) {
      dp_min[v][mp[a]][mp[b]] = mn;
      val[v][mp[a]][mp[b]].first = max(val[v][mp[a]][mp[b]].first, a_tmp.first);
    }
    if(dp_max[v][mp[a]][mp[b]] <= mx) {
      dp_max[v][mp[a]][mp[b]] = mx;
      val[v][mp[a]][mp[b]].second = min(val[v][mp[a]][mp[b]].second, a_tmp.second);
    }
  }while(next_permutation(graph[v].begin(), graph[v].end()));
  //cout<<v<<" "<<val[v][mp[a]][mp[b]].first << " " << val[v][mp[a]][mp[b]].second << endl;
  //assert(val[v][mp[a]][mp[b]].first == val[v][mp[a]][mp[b]].second); 
  return val[v][mp[a]][mp[b]];
}

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

  cin >> n;
  for(Int i = 0; i < n; ++i) cin >> p[i];
  for(Int i = 0; i < n; ++i) {
    Int k; cin >> k;
    for(Int j = 0; j < k; ++j) {
      Int t; cin >> t; --t;
      graph[i].push_back(t);
    }
    sort(graph[i].begin(), graph[i].end());
  }
  vector<Int> vec;
  vec.push_back(-inf);
  vec.push_back(inf);
  for(Int i = 0; i < n; ++i) {
    vec.push_back(p[i]);
    vec.push_back(-p[i]);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for(Int i = 0; i < n; ++i) {
    mp[p[i]] = lower_bound(vec.begin(), vec.end(), p[i])-vec.begin();
    mp[-p[i]] = lower_bound(vec.begin(), vec.end(), -p[i])-vec.begin();
  }
  memset(visited, false, sizeof(visited));
  dfs(0, -inf, inf);
  cout << dp_min[0][mp[-inf]][mp[inf]] << " " << dp_max[0][mp[-inf]][mp[inf]] << endl;
  
  return 0;
}



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

using namespace std;
using ll = long long;
constexpr ll BASE = 1000000000;

int main() {
	ll S; scanf("%lld", &S);
	ll cont1 = S / BASE + (S % BASE == 0 ? 0 : 1);
	ll cont2 = cont1 * BASE - S;
	printf("0 0 %lld %lld 1 %lld\n", BASE, cont2, cont1);
}


Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
const int mod=1e9+7;


int main(){
    while(true){
        int n,m;cin>>n>>m;
        if(n==0)break;
        int h[n+1],w[m+1];
        h[0]=w[0]=0;
        rep(i,n){
            cin>>h[i+1];h[i+1]+=h[i];
        }
        rep(i,m){
            cin>>w[i+1];w[i+1]+=w[i];
        }
        map<int,int> p;
        rep(i,n){
            rep(j,i+1,n+1){
                p[h[j]-h[i]]++;
            }
        }
        int ans=0;
        rep(i,m){
            rep(j,i+1,m+1){
                if(p[w[j]-w[i]])ans+=p[w[j]-w[i]];
            }
        }
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 20876
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)

int main() {
	ll a, b, x; cin >> a >> b >> x;
	ll sum = b / x - a / x;
	ll add = ((a % x == 0) ? 1 : 0);
	cout << sum + add << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N;
int r[200][200];
int b[200][200];


int main(){
    cin >> N;
    int x,y;
    for(int i=0;i<200;i++){
        for(int j=0;j<200;j++){
            r[i][j] = b[i][j] = 0;
        }
    }
    for(int i=0;i<N;i++){
        cin >> x >> y;
        r[x][y]++;
    }
    for(int i=0;i<N;i++){
        cin >> x >> y;
        b[x][y]++;
    }
    int count = 0;
    for(int i=0;i<200;i++){
        for(int j=0;j<200;j++){
            if(b[i][j] == 0) continue;
            for(int jj=j-1;jj>=0;jj--){
                for(int ii=i-1;ii>=0;ii--){
                    if(r[ii][jj] > 0){
                        b[i][j]--;
                        r[ii][jj]--;
                        count++;
                    }
                    if(b[i][j] == 0) break;
                }
                if(b[i][j] == 0) break;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 512
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) # (cost, 探索候補ノード)
        v = collections.defaultdict(bool) # 確定済かどうか
        while len(q):
            # ノードuにおけるコストはk
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: # cost is ud from u to uv
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev
n, m = inpl()
graph=Dijkstra()
for i in range(m):
    u, v = inpl()
    graph.add(u,v+n,1,directed=True)
    graph.add(u+n,v+n+n,1,directed=True)
    graph.add(u+n+n,v,1,directed=True)
s,t=inpl()
ans = 0
d, _ = graph.Dijkstra_search(s)
ans = d[t] if d[t] != INF else - 1
# print(d)
print(ans//3)

Measured memory_bytes: 151940
#include <bits/stdc++.h>
using namespace std;
int a[201],ans,n;
int main()
{
    cin>>n;
    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+2*n+1);
    for(int i=1;i<=2*n;i+=2)
    {
        ans+=a[i];
    } 
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  int N, M; cin >> N >> M;
  vector<int> data(M);
  for(int i=0; i<M; i++){
    cin >> data.at(i);
  }
  
  int day = 0;
  for(int i=0; i<M; i++){
    day += data.at(i);
  }
  
  if(N - day >= 0) cout << N - day << endl;
  else cout << "-1" << endl;
  
}

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


int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n;i++)
        cin >> a[i];
    for (int i = 0; i < n;i++)
        cin >> b[i];
    reverse(b.begin(), b.end());

    vector<int> c, d;
    int v = -1;
    int cnt = 0;
    for (int i = 0; i < n;i++){
        if(a[i] == b[i]){
            cnt++;
            v = b[i];
            c.push_back(i);
        }
    }
    for (int i = 0; i < n && cnt;i++){
        if(a[i] != b[i] && a[i]!=v && b[i]!=v){
            d.push_back(i);
            cnt--;
        }
    }
    if(cnt)
        cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        for (int i = 0; i < (int)d.size();i++)
            swap(b[c[i]], b[d[i]]);
        for (int i = 0; i < n;i++)
            cout << b[i] << ' ';
    }


    return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a, b) a = min((a),(b))
#define CHMAX(a, b) a = max((a),(b))
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main() {
    int r, g;
    cin >> r >> g;
    cout << 2 * g - r << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
string s, s1, s2;
int ans = 0;
int main()
{
	int num = 1;
	cin >> s;
	int len = s.length();
	s1 += s[0];
	for(int i = 0; i < len; i++){
		for(int j = i + 1; j < len; j++){
			s2 += s[j];
			if(s2 != s1){
				i = j;
				num++;
				s1 = s2;
				s2.clear();
			}
		}
	}
	cout << num;
	return 0;
}

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

int main(){
  vector<vector<char>> c(2, vector<char>(3));
  for (int i=0 ; i<2 ; i++){
    for (int j=0 ; j<3 ; j++)
      cin >> c.at(i).at(j);
  }
  
  int n = 0;
  for (int i=0 ; i<3 ; i++){
    if (c.at(0).at(i) == c.at(1).at(2-i))
      n++;
  }
  
  if (n == 3)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

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

int main() {
	string s, t;
	cin >> s >> t;
	bool y;
	int p = s.length();
	int a1 = -1;
	char b1;
	for (int i = s.length() - t.length();i >= 0;i --) { // このiの位置に部分文字列を置いた時を考える
		y = true;
		int a2 = s.length();
		char b2;
		for (int j = i;j < i + t.length();j ++) { // 部分文字列が置けるか判定
			if (s[j] == '?') { // もし?が出てきたなら
				if (a2 == s.length()) { // もし最初の?なら
					a2 = j; // その位置と、
					b2 = t[j - i]; // 置き換える記号を覚える
				}
			} else if (s[j] != t[j - i]) y = false; // もし一致しない→つまり部分文字列を置けないなら無視
		}
		if (y) { // 部分文字列を置けたとき
			if (a1 < a2 || (a2 == a1 && b2 < b1)) { // iの位置に部分文字列を置いた方が辞書順で小さくなるなら
				p = i; // 更新
				a1 = a2;
				b1 = b2;
			}
		}
	}
	
	if (a1 == -1) { // どこにも置けなかった時
		cout << "UNRESTORABLE";
		return 0;
	}
	for (int i = 0;i < p;i ++) cout << (s[i] == '?' ? 'a' : s[i]);
	for (int i = 0;i < t.length();i ++) cout << t[i];
	for (int i = p + t.length();i < s.length();i ++) cout << (s[i] == '?' ? 'a' : s[i]);
	return 0;
}
// 辞書順最小であるのだから、部分文字列を入れたところ以外の?は全てaにすべき
// 部分文字列はより後に置いた方が基本的には辞書順が早くなる
// そこで、ある場所に部分文字列を置いた時に辞書順最小かを順に考えていく
// O(ST)だからなんとかなる

Measured memory_bytes: 256
/************************************
/ AUTHOR : YATHARTH GOSWAMI         /  
/ ALIAS : hacker_yg                 /
/ INSTITUTE : IIT Kanpur            /
************************************/
//          TEMPLATE                //

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;

int main(){
    int n;
    cin >> n;
    vector <int> v(n);
    map <int, int> m;
    for (int i = 0; i < n-1; i++){
        cin >> v[i];
        m[v[i]]++;
    }
    for (int i = 1; i<= n; i++) cout << m[i] << endl;
    return 0;
}




Measured memory_bytes: 13556
#include <bits/stdc++.h>
    using namespace std;
    typedef long long int ll;
    #define mod 1000000007
    #define all(v)  v.begin(),v.end()
    #define pb push_back
    ll power(ll a,ll x){if(x==0) return 1;ll y=power(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
    ll inv(ll a){return power(a,mod-2);}
     
    #define N 100005
    vector< pair<ll,ll> > adj[N];
    ll color[N];
     int main(){
     
     ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
      
     ll n;
     cin>>n;
     for(int i=1;i<n;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
     } 
     
     queue<ll> q;
     ll vis[n+1];
     for(int i=1;i<=n;i++) vis[i]=-1;
     vis[1]=0;
     color[1]=0;
     q.push(1);
     while(!q.empty()){
        ll k=q.front();
        ll u=k;
        q.pop();
        for(auto i: adj[u]){
            ll v=i.first;
            ll w=i.second;
            if(vis[v]==-1){
              vis[v]=vis[u]+w;
              if(w%2==0){color[v]=color[u];}
              else color[v]=1-color[u];
              q.push(v);
          }  
        }
     }
     
     for(int i=1;i<=n;i++){
     //  cout<<vis[i]<<endl;
       cout<<color[i]<<endl;
     }
     
     
    }

Measured memory_bytes: 10496
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define repk(i,k, n) for (int i = k; i < (int)(n); ++i)
#define MAX 500010
typedef long long int ll;

using namespace std;


int main() {
	int N;
	cin >> N;

	cout << pow(N, 3) << endl;

	return 0;
}

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

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

    vector<ll> S(13);
    vector<ll> H(13);
    vector<ll> C(13);
    vector<ll> D(13);
    for (size_t i = 0; i < n; i++)
    {
        char egara;
        int temp;
        cin >> egara >> temp;

        if (egara == 'S')
        {
            S[temp - 1] = 1;
        }
        if (egara == 'H')
        {
            H[temp - 1] = 1;
        }
        if (egara == 'C')
        {
            C[temp - 1] = 1;
        }
        if (egara == 'D')
        {
            D[temp - 1] = 1;
        }
    }

    for (size_t i = 0; i < 13; i++)
    {
        if (S[i] == 0)
        {
            cout << "S " << (i + 1) << endl;
        }
    }
    for (size_t i = 0; i < 13; i++)
    {
        if (H[i] == 0)
        {
            cout << "H " << (i + 1) << endl;
        }
    }
    for (size_t i = 0; i < 13; i++)
    {
        if (C[i] == 0)
        {
            cout << "C " << (i + 1) << endl;
        }
    }
    for (size_t i = 0; i < 13; i++)
    {
        if (D[i] == 0)
        {
            cout << "D " << (i + 1) << endl;
        }
    }
}



Measured memory_bytes: 3096