akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env pypy3

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(10000000)

#import numpy as np
#import scipy as sp

# Python 3 modules: https://docs.python.org/3/library/

import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce, lru_cache
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5.  Import from math after it.
from fractions import gcd
from fractions import Fraction as Frac

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(func = input, sep = None, conv = int):
    return list(map(conv, func().split(sep = sep)))

################################################################################

N, M = list(map(int, input().split()))
A = [None for i in range(M)]
for i in range(M):
    A[i] = int(input())
#A = list(map(int, stdin.read().split()))

BROKEN = [False for i in range(N)]
for a in A:
    BROKEN[a] = True

@lru_cache(maxsize = None)
def dp(cur):
    if cur > N:
        return 0
    if cur == N:
        return 1
    if BROKEN[cur]:
        return 0
    return dp(cur + 1) + dp(cur + 2)

print(dp(0) % 1000000007)


Measured memory_bytes: 649716
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

/*nCk*/
ll nckused[1000][1000];
ll nckreached[1000][1000];
ll comb(ll n,ll k){
    if(n>1000) return (k==0 || k==n)?1:comb(n-1,k-1)+comb(n-1,k);
    if(nckreached[n][k]==1) return nckused[n][k];
    nckreached[n][k] = 1;
    nckused[n][k] = (n==1 || (k==0 || k==n) )?1:comb(n-1,k-1)+comb(n-1,k);
    return (n==1 || (k==0 || k==n) )?1:comb(n-1,k-1)+comb(n-1,k);
}

int main(void){
    // char ;
    ll n,p,ans=0;
    scanf("%lld%lld",&n,&p);
    ll a[n],odd=0,even=0;
    rep(i,0,n){
        scanf("%lld",&a[i]);
        if(a[i]%2) odd++;
        else even++;
    }
    if(p){
        rep(i,1,odd+1){
            if(i%2){
                ans+=comb(odd,i);
            }
        }
        ans*=POW(2,even);
    }else{
        rep(i,0,odd+1){
            if(i%2==0){
                ans+=comb(odd,i);
            }
        }
        ans*=POW(2,even);
    }
    
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define lli unsigned long long int 
#define pb push_back
using namespace std;

const int INF= 1e9 +5;
typedef std::vector<lli> vi;
typedef pair<int,int> ii;


int main() {

	//freopen("input.txt", "r", stdin); 
  	//freopen("output.txt", "w", stdout); 


  	lli n;
  	cin>>n;

  	n=(n*(n-1))/2;
	printf("%lld\n",n );

	
	return 0;
}

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

using namespace std;

class DisjointSet {
  public:
    vector<int> rank, p;

    DisjointSet() {}
    DisjointSet(int size) {
      rank.resize(size, 0);
      p.resize(size, 0);
      for( int i = 0; i < size; i++ ) makeSet(i);
    }

    void makeSet(int x) {
      p[x] = x;
      rank[x] = 0;
    }

    bool same(int x, int y) {
      return findSet(x) == findSet(y);
    }

    void unite(int x, int y) {
      link(findSet(x), findSet(y));
    }

    void link(int x, int y) {
      if ( rank[x] > rank[y] ) {
        p[y] = x;
      } else {
        p[x] = y;
        if ( rank [x] == rank[y] )
          rank[y]++;
      }
    }

    int findSet(int x) {
      if ( x != p[x] )
        p[x] = findSet(p[x]);
      return p[x];
    }
};

int main() {
  int n, a, b, q;
  int t;

  cin >> n >> q;
  DisjointSet ds = DisjointSet(n);

  for ( int i = 0; i < q; i++ ) {
    cin >> t >> a >> b;
    if ( t == 0 ) ds.unite(a, b);
    else if ( t == 1 ) {
      if ( ds.same(a, b) ) cout << 1 << endl;
      else cout << 0 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3152
(function main() {
  const n = Number(require('fs').readFileSync('/dev/stdin', 'utf8'));

  const cache = [1, 1];
  const fib = function fib(n) {
    if (cache[n]) return cache[n];
    cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n]
  };
  console.log(fib(n));
})();



Measured memory_bytes: 15372
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define PI 3.1415


int main() {
    
    int s,w;
    cin >> s >> w;

    if(w>=s)    cout<<"unsafe"<<endl;
    else    cout<<"safe"<<endl;


 return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define REP(i,j) for(int i=0;i<j;i++)
#define FORN(i,j,k) for(int i=j;i<k;i++)
#define vi vector<int>
#define vvi vector<vi >
#define pii pair<int,int>
#define vpii vector<pii >
using namespace std;
ll n,k;
int main(void){
	cin>>n>>k;
	cout<<min(n%k,k-n%k);
	return 0;
}

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
a = [A, B, C, D, E]
a.sort(key=lambda x: (x+9) % 10, reverse=True)
print(sum((i + 9) // 10 * 10 for i in a[:4]) + a[4])


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int sum = 0;
    if (2 * C < A + B ) {
        int nC = min(X, Y) * 2;
        sum += nC * C;
        X = max<int>(X - nC / 2, 0);
        Y = max<int>(Y - nC / 2, 0);
    }
    if (2 * C < A) {
        int nC = X * 2;
        sum += nC * C;
        X = max<int>(X - nC / 2, 0);
        Y = max<int>(Y - nC / 2, 0);
    }
    if (2 * C < B) {
        int nC = Y * 2;
        sum += nC * C;
        X = max<int>(X - nC / 2, 0);
        Y = max<int>(Y - nC / 2, 0);
    }
    sum += X * A + Y * B;

    cout << sum << "\n";

}


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

using namespace std;


int n;
#define MAX 100002

vector<int> v;
map<int, int> mp;
#define MOD 1000000007
vector<int> vv;
int main(){
	cin >> n;
	{
		int lef = 0;
		int rig = n;
		for (int i = 0; i < n; i++){
			rig--;
			vv.push_back(abs(lef - rig));
			lef++;
		}
	}
	for (int i = 0; i < n; i++){
		int a;
		scanf("%d", &a);
		mp[a]++;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	sort(vv.begin(), vv.end());
	if (v == vv){
		long long int ans = 1;
		for (auto it = mp.begin(); it != mp.end(); it++){
			ans *= (long long int)(*it).second;
			ans %= MOD;
		}
		printf("%lld\n", ans);
	}
	else{
		puts("0");
	}
	return 0;
}

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

int main(){
    string S;
    cin >> S;
    int s=S.size();
    char c='a';
    bool flag=1;
    while(c<='z'){
        for(int i=0;i<s;i++){
            if(S[i]==c){
                flag=0;
            }
        }
        if(flag){
            cout << c << endl;
            return 0;
        }
        flag=1;
        c++;
    }
    cout << "None" << endl;
}

Measured memory_bytes: 512
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
// https://atcoder.jp/contests/abc167/tasks/abc167_a
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string ans[2] = {"No","Yes"};
    bool isAnswer = true;
    string s,t;
    cin >> s >> t;
    for(int i=0;i<s.length();i++){
        if(s[i] != t[i]){
            isAnswer = false;
            break;
        }
    }
    cout << ans[isAnswer];

	return 0;

}

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

int main() {
  int n, k, x, y;
  cin >> n >> k >> x >> y;
  ll ans = 0;
  rep(i,n){
    if(i >= k){
      ans += y;
    }else {
      ans += x;
    }
  }
  cout << ans << endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  
  string dummy;
  for (int j = 0; j < W; j++){
    dummy += '.';
  }
  
  string S_0,S_1,S_2;
  for (int i = 0; i < H; i++){
    if (i == 0){
      S_0 = dummy;
      cin >> S_1;
      if (H == 1)
        S_2 = dummy;
      else
        cin >> S_2;
      S_0 = '.' + S_0 + '.';
      S_1 = '.' + S_1 + '.';
    } else if (i != H-1){
      S_0 = S_1;
      S_1 = S_2;
      cin >> S_2;
    } else {
      S_0 = S_1;
      S_1 = S_2;
      S_2 = dummy;
    }
    S_2 = '.' + S_2 + '.';
      
    for (int j = 1; j < W+1; j++) {
//      cout << S_1 << endl;
//      cout << " i:" << i << " j:" << j << " ";
      if (S_1.at(j) == '#')
        cout << '#';
      else
        cout << ((S_0.at(j-1) == '#') + (S_0.at(j) == '#') + (S_0.at(j+1) == '#') + (S_1.at(j-1) == '#') + (S_1.at(j) == '#') + (S_1.at(j+1) == '#') + (S_2.at(j-1) == '#') + (S_2.at(j) == '#') + (S_2.at(j+1) == '#'));   
    }
    cout << endl;
      
  }
}


Measured memory_bytes: 256
def main():
  H, W = list(map(int, input().split()))

  count = 0

  for i in range(H):
    row = input()
    for j in range(W):
      if(row[j] == '#'):
        count += 1

  print("Possible" if W + H - 1 == count else "Impossible")

if __name__ == "__main__":
  main()

Measured memory_bytes: 2940
n=int(input())
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
dp[0][0][0][0]=1
MOD=10**9+7
# 0,1,2,3
# T,A,C,G
# NG
# AGC:132
# GAC:312
# ACG:123
# A?GC:1?32
# AG?C:13?2

for i in range(n):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4): # nxt
                    if b==1 and c==3 and d==2: # AGC
                        continue
                    if b==3 and c==1 and d==2: # GAC
                        continue
                    if b==1 and c==2 and d==3:  # ACG
                        continue
                    if a==1 and c==3 and d==2:  # ACG
                        continue
                    if a==1 and b==3 and d==2:  # ACG
                        continue

                    dp[i+1][b][c][d] += dp[i][a][b][c]
                    dp[i+1][b][c][d]%=MOD
ans=0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans+=dp[-1][a][b][c]
print(ans%MOD)

Measured memory_bytes: 49136
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=55;
ll f[N][2];int a[N],n,p;
int main(){
	scanf("%d%d",&n,&p);
	fp(i,1,n)scanf("%d",&a[i]),a[i]&=1;
	f[0][0]=1;
	fp(i,1,n){
		f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];
		if(a[i]&1)f[i][0]+=f[i-1][1],f[i][1]+=f[i-1][0];
			else f[i][0]+=f[i-1][0],f[i][1]+=f[i-1][1];
	}
	printf("%lld\n",f[n][p]);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define LL long long int
int main(){
 string s, t;cin>> s>> t;
  long int ans =0;
  
  for(unsigned long int i=0; i<s.size();++i){
    if(s[i]!= t[i]){ans ++;}
  }
    cout<< ans<< endl;
  
}

Measured memory_bytes: 3784
#include <iostream>
using namespace std;
int main(void){
    int num[101][3]={0};
    int n,m,kotani;
    cin>>n;
    for(int i=0;i<3;i++){
        cin>>m;
        for(int j=0;j<m;j++){
            cin>>kotani;
            num[kotani][i]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(num[i][0]==0&&num[i][2]==1||num[i][1]==1&&num[i][2]==1){
            ans++;
        }
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,a[MAXN];
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d",&a[i]);}
	for (int i=n-1;i>=1;i--) {
		if (a[i]>a[i+1]+1) {printf("No\n");return 0;}
		else if (a[i]==a[i+1]+1) {a[i]--;}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 640
using System;

namespace abc144_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int num1 = int.Parse(input[0]);
            int num2 = int.Parse(input[1]);

            if(num1 > 9 || num2 > 9)
            {
                Console.WriteLine("-1");
            }
            else
            {
                Console.WriteLine(num1 * num2);
            }
        }
    }
}


Measured memory_bytes: 13140
L,A,B,mod=map(int,input().split())
def f(l):
  return max(0,(10**l-A-1)//B+1)

def m(a,b):
  r=[[0]*len(b[0]) for i in range(len(a))]
  for i in range(len(a)):
    for k in range(len(b)):
      for j in range(len(b[0])):
        r[i][j]=(r[i][j]+a[i][k]*b[k][j])%mod
  return r

def p(a,n):
  r=[[0]*len(a) for i in range(len(a))]
  b=[]
  for i in range(len(a)):
    r[i][i]=1
    b.append(a[i][:])
  l=n
  while l>0:
    if l&1:
      r=m(b,r)
    b=m(b,b)
    l>>=1
  return r

'''
100   001
B10 * 00s
01l   00P
'''

X=[[0,0,1],[0,0,A],[0,0,0]]
Y,R,Z=0,1,0
while L:
  Y=[[1,0,0],[B,1,0],[0,1,pow(10,R,mod)]]
  Z=min(L,f(R)-f(R-1))
  L-=Z
  Y=p(Y,Z)
  X=m(Y,X)
  R+=1
print(X[2][2]%mod)

Measured memory_bytes: 73708
#!/usr/bin/env python3
import numpy as np


def main():
    N, X = map(int, input().split())
    L_list = list(map(int, input().split()))
    L_sum = np.cumsum(L_list)
    print(np.where(L_sum <= X)[0][-1] + 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 12484
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    a,b = mi()
    cnt = 0
    a1 = a-1
    fin = 1
    for i in range(50):
        if fin >= b:
            break
        else:
            fin+=a1
            cnt+=1
    print(cnt)


main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 1000
 
int N, K;
long long a[MAXN];
 
long long A[MAXN][MAXN];
 
long long power( long long x, int n )
{
	if( n == 0 ) {
		return 1;
	}
	if( n % 2 ) {
		return x * power( x, n - 1 );
	}
	else {
		return power( x * x, n / 2 );
	}
}
 
int main()
{
	cin >> N >> K;
	for( int i = 0; i < N; i++ ) {
		cin >> a[i];
		A[i][0] = a[i];
	}
 
	int n1 = N * (N + 1) / 2;
	for( int i = 0; i < N; i++ ) {
		int k = 1;
		for( int j = i + 1; j < N; j++ ) {
			A[i][k] = A[i][k - 1] + a[j];
			k++;
		}
	}
	long long ans = 0;
	long long t = power( 2, 40 - 1 );
	for( int l = 40; l > 0; l-- ) {
		int n = 0;
		for( int i = 0; i < N; i++ ) {
			int k = 1;
			for( int j = i + 1; j < N; j++ ) {
				if( ( ( ans + t) & A[i][k] ) == (ans + t) ) {
					n++;
					if( n == K ) {
						ans += t;
					}
				}
				k++;
			}
		}
		t /= 2;
	}
 
	cout << ans << endl;
 
	return 0;
}

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

int main(void) {
	int N[3];
	int a = 0;
	cin >> N[0] >> N[1] >> N[2];
	sort(N,N+3);
	a = abs(N[2] - N[0]) + abs(N[2]-N[1]);
	if (a % 2 == 0)
		cout << a / 2 << endl;
	else
		cout << a  / 2 + 2 << endl;
	return 0;
}

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

using namespace std;
using LL = long long;
using P = pair<int, int>;
using Tapris = tuple<int, int, int>;

#define REP(i, n) for(LL i = 0; i < n; ++i)
#define FOR(i, a, n) for(LL i = a; i < n; ++i)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

//#define int long long

/*************** using variables ***************/
int n;
vector<int> t;
double ans = 0;
vector<double> v, max_v(40005, INF);
/**********************************************/

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> n;
    t.resize(n);
    v.resize(n);
    REP(i, n){ cin >> t[i]; t[i] *= 2; }
    REP(i, n) cin >> v[i];
    
    int cur = 0;
    REP(i, n){
        for(int cur_time = cur; cur_time <= cur + t[i]; cur_time++){
            max_v[cur_time] = min(max_v[cur_time], v[i]);
        }
        cur += t[i];
    }

    max_v[0] = 0; max_v[cur] = 0;

    REP(i, cur){
        max_v[i+1] = min(max_v[i+1], max_v[i] + 0.5);
    }
    for(int i = cur - 1; i >= 0; i--){
        max_v[i] = min(max_v[i], max_v[i+1] + 0.5);
    }

    REP(i, cur){
        ans += (max_v[i] + max_v[i+1]);
    }

    printf("%.5lf\n", ans / 4);
}


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

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; string s;
    cin >> n >> s;
    int cnt = 0;
    rep(i,n-2){
        if(s.substr(i,3) == "ABC") cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

using namespace std;

#define ll long long
#define inf numeric_limits<ll>::max()/2

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> seq;
    for(int i = 0; i < n; i++){
        int ai;
        cin >> ai;
        seq.push_back(ai);
    }

    int inx0 = upper_bound(seq.begin(),seq.end(),0) - seq.begin();
    inx0--;

    if(inx0 >= 0 && seq[inx0] == 0){
        k--;
        seq.erase(find(seq.begin(),seq.end(),0));
        inx0--;
        if(k == 0){
            cout << 0 << endl;
            return 0;
        }
    }

    vector<ll> litl, litr;

    if(inx0 >= 0){
        litl.push_back(abs(seq[inx0]));
    }

    for(int i = inx0-1; i >= 0; i--){
        litl.push_back(litl.back() + seq[i+1] - seq[i]);
    }

    if(inx0+1 < seq.size()){
        litr.push_back(seq[inx0+1]);
    }

    for(int i = inx0+2; i < seq.size(); i++){
        litr.push_back(litr.back() + seq[i] - seq[i-1]);
    }

    ll sol = inf;
    sol = min(sol, (litr.size() >= k ? litr[k-1] : inf));
    sol = min(sol, (litl.size() >= k ? litl[k-1] : inf));

    for(int div = 1; div < k-1; div++){
        int oth = k - div;
        if(div > litl.size() || oth > litr.size()){
            continue;
        }

        sol = min(sol, 2*litl[div-1] + litr[oth-1]);
        sol = min(sol, litl[div-1] + 2*litr[oth-1]);
    }

    cout << sol << endl;

    return 0;
}

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

using namespace std;

long long solve (long long b, long long n) {
    if (n < b) return n;

    return solve(b, n / b) + n % b;
}

int main(){
    long long n, s;
    scanf("%lld %lld", &n, &s);

    long long m = n - s;
    if (n == s) return !printf("%lld", n + 1);

    long long ans = 1e18;
    for (long long i = 1; i * i <= m; i++) {
        if (m % i == 0) {
            long long res = solve(i + 1, n);
            long long cur = solve(m / i + 1, n);

            if (res == s) ans = min(ans, i + 1);
            if (cur == s) ans = min(ans, m / i + 1);
        }
    }

    if (ans > 5e17) printf("-1");
    else printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <cmath>
#include <deque>

intmax_t diffmax(std::deque<intmax_t> a) {
  size_t n=a.size();
  std::vector<intmax_t> b;

  std::vector<intmax_t> mae, ush;
  while (!a.empty()) {
    mae.push_back(a.front());
    a.pop_front();
    if (a.empty()) break;
    ush.push_back(a.back());
    a.pop_back();
  }
  b.push_back(mae.back());
  mae.pop_back();
  std::reverse(mae.begin(), mae.end());
  std::reverse(ush.begin(), ush.end());

  while (!mae.empty() && !ush.empty()) {
    b.push_back(ush.back());
    ush.pop_back();
    b.push_back(mae.back());
    mae.pop_back();
  }
  if (!ush.empty())
    b.push_back(ush.back());
  if (!mae.empty())
    b.push_back(mae.back());

  for (size_t i=0; i<n; ++i)
    fprintf(stderr, "%jd%c", b[i], i+1<n? ' ':'\n');

  intmax_t res=0;
  for (size_t i=1; i<n; ++i) {
    intmax_t d=b[i]-b[i-1];
    res += (d>0? d:-d);
  }
  return res;
}

int main() {
  size_t N;
  scanf("%zu", &N);

  std::deque<intmax_t> A(N);
  for (size_t i=0; i<N; ++i)
    scanf("%jd", &A[i]);

  std::sort(A.begin(), A.end());

  intmax_t res=0;
  res = diffmax(A);
  std::reverse(A.begin(), A.end());
  res = std::max(res, diffmax(A));
  printf("%jd\n", res);
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) (vec).begin(),(vec).end()
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
int n,node;
const int MAXN=1000100;
vector<int> pth[200100];
string s[200100];
struct Trie{
	int son[MAXN][26],dat[MAXN],tot;
	Trie(){
		dat[1]=0;
		for(int j=0;j<26;j++) son[1][j]=0;
		tot=1;
	}
	void insert(string s,int idx){
		int len=s.size(),p=1,ch;
		for(int k=0;k<len;k++){
			ch=s[k]-'a';
			if(son[p][ch]==0) son[p][ch]=++tot;
			p=son[p][ch];
			pth[idx].push_back(p);
		}
		dat[p]++;
	}
}trie;
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		reverse(s[i].begin(),s[i].end());
		trie.insert(s[i],i);
	}
	set<char> suf;
	int ans=0;
	for(int i=1;i<=n;i++){
		suf.clear();
		for(int j=s[i].size()-1;j>=0;j--){
			node=pth[i][j];
			for(char c:suf)
				ans+=trie.dat[trie.son[node][c-'a']];
			suf.insert(s[i][j]);
		}
		node=1;
		for(char c:suf)
			ans+=trie.dat[trie.son[node][c-'a']];
	}
	cout<<ans-n<<endl;
	return 0;
}


Measured memory_bytes: 125788
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        final int mod = 1_000_000_007;
        
        long[][][][] dp = new long[110][5][5][5];
        dp[0][0][0][0] = 1;
        for (int i = 0 ; i < n ; i++) {
            for (int a = 0 ; a < 5 ; a++) {
                for (int b = 0 ; b < 5 ; b++) {
                    for (int c = 0 ; c < 5 ; c++) {
                        for (int d = 1 ; d <= 4; d++) {
                            if (b == 1 && c == 3 && d == 2) continue;
                            if (a == 1 && c == 3 && d == 2) continue;
                            if (b == 3 && c == 1 && d == 2) continue;
                            if (b == 1 && c == 2 && d == 3) continue;
                            if (a == 1 && b == 3 && d == 2) continue;
                            dp[i+1][b][c][d] = (dp[i+1][b][c][d] + dp[i][a][b][c]) % mod;
                        }
                    }
                }
            }
        }
        long ans = 0;
        for (int a = 0; a < 5; a++) {
            for (int b = 0; b < 5; b++) {
                for (int c = 0; c < 5; c++) {
                    ans = (ans + dp[n][a][b][c]) % mod;
                }
            }
        }
        System.out.println(ans);
    }


}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
#include <string>
using namespace std;
#include<chrono>
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define foo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define min3(a,b,c)         min(a,min(b,c))
#define max3(a,b,c)         max(a,max(b,c))
#define min4(a,b,c,d)       min(a,min(b,min(c,d)))
#define max4(a,b,c,d)       max(a,max(b,max(c,d)))
#define max5(a,b,c,d,e)     max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e)     min(min3(a,b,c),min(d,e))
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pl;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pl>    vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;
int mpow(int base, int exp); 
void ipgraph(int m);
void DFS(int n);
bool isprime(ll n);
int gcd(int a,int b);
void rstgraph(int n);

const int mod = pow(10,9)+7;
const int N = 3e5, M = N;

//=======================================================================================
vi g[N];
int vis[N];
int nodes=0;
// ll ans=0;
void iluzn() {
int n;
cin>>n;
vl a(n);
int i,j;
ll sum=0;
fo(i,n)  {cin>>a[i];sum+=a[i];}
ll pro=0;
fo(i,n-1){
  sum=sum-a[i];
 pro+=a[i]*(sum%mod);
 pro%=mod;
}
pro%=mod;
cout<<pro;
}

 
int main() {
  #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  #endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1,i;
    // cin>>t;
     while(t--) iluzn();
    return 0;
}
int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}
bool isprime(ll n){
    if(n<=1)
        return false;
    if(n==2)
        return true;
    if(n%2==0)
        return false;
    ll rt = sqrt(n);
    for(ll i=3;i<rt;i+=2){
        if(n%i==0)
            return false;
    }
    return true;
}
int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
} 
void ipgraph(int m){
  int u, v;
  while(m--){
    cin>>u>>v;
    g[u].pb(v);
    // g[v].pb(u);
  }
}

void DFS(int n)
{  ++nodes;
    vis[n] = 1;
    for(vector<int>::iterator i = g[n].begin(); i != g[n].end() ; i++)
    {
        if(!vis[*i])
            DFS(*i);
    }
}
void rstgraph(int n){
  int i;
  fo(i,n+1){
    g[i].clear();
    vis[i]=0;
  }
  nodes=0;
}

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

count = 0
for i in range(N):
  if A[i] >= B[i]:
    count += B[i]
  elif A[i] < B[i]:
    count += A[i]
    B[i] -= A[i]
    A[i] = 0
    if A[i+1] >= B[i]:
      count += B[i]
      A[i+1] -= B[i]
    else:
      count += A[i+1]
      A[i+1] = 0
print(count)

Measured memory_bytes: 24172
#include <stdio.h>

#define LEN 100000

int n;
int S[LEN];

int binarySearch(int target) {
    int left = 0;
    int right = n;
    int mid;

    while (left < right) {
        mid = (left + right) / 2;
        if (target == S[mid]) return 1;
        if (target > S[mid]) left = mid + 1;
        if (target < S[mid]) right = mid;
    }

    return 0;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &S[i]);

    int q;
    scanf("%d", &q);

    int k;
    int cnt = 0;
    for (int i = 0; i < q; i++) {
        scanf("%d", &k);
        if (binarySearch(k)) cnt++;
    }

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

    return 0;
}



Measured memory_bytes: 2160
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;

    cout << c - min(c, a - b) << endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
n = len(s)
c = False
for e,i in enumerate(s):
    if e == 0:
        if not i == "A":
            print("WA")
            break
    elif 1 < e < n-1 and i == "C":
        if not c:
            c = True
        else:
            print("WA")
            break
    else:
        if not i in "abcdefghijklmnopqrstuvwxyz":
            print("WA")
            break
else:
    if c:
        print("AC")
    else:
        print("WA")

Measured memory_bytes: 3064
// In The Name Of GOD
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2 * 100 * 1000 + 100;

int LCIS(const vector <int> &vec);

int main() {
	int n;
	cin >> n;
	vector <int> vec(n);
	for(int i = 0; i < n; i++)
		cin >> vec[i];
	cout << n - LCIS(vec);
}

int LCIS(const vector <int> &vec) {
	int dp[MAXN] = {}, maxi = 0;
	for (int i: vec) {
		dp[i] = dp[i - 1] + 1;
//      cerr << i - 1 << ' ' << dp[i] << endl;
    }
	for (int i: vec) {
		maxi = max(maxi, dp[i]);
//      cerr << maxi << endl;
    }
  	return maxi;
}

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

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

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

	int ans = 0;
	rep(i,n){
		int sum = 0;
		rep(j,n){
			if(i >= j){
				sum += a[j];
			}
			if(i <= j){
				sum += b[j];
			}
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
}


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

int main() {
  int n, i;
  string s, t;
  cin >> n >> s >> t;
  for(i = 0; i < n; i++) {
    int f = 1;
    for(int j = i; j < n; j++)
      if(s[j] != t[j - i]) f = 0;
    if(f) break;
  }
  cout << n * 2 - (n - i) << "\n";
}

Measured memory_bytes: 256
#include <iostream>

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

const int INF = 10000000;
using namespace std;
typedef long long  ll;
const int MAX = 10000;

/** Problem0566 : Soccer **/
int main()
{
	int team[100]={0};
	int n, a, b, as, bs;
	
	cin >> n;
	rep(i, n*(n-1)/2) {
		cin >> a >> b >> as >> bs;
		a--; b--;
		if (as > bs) {
			team[a]+=3;
		} else if (bs > as) {
			team[b]+=3;
		} else {
			team[a]++; team[b]++;
		}
	}
	rep(i, n) {
		int myS = team[i];
		int rank=1;
		rep(j, n) {
			if (i!=j && myS<team[j])
				rank++;
		}
		cout << rank << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
int a[101];
int main(void)
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n,greater<int>());
	int x=0,y=0;
	for(int i=0;i<n;i++){
		if(i%2==0){
			x+=a[i];
		}
		else{
			y+=a[i];
		}
	}
	x=x-y;
	cout<<x<<endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i

rest = []
n.times do
  a, b = gets.chomp.split.map(&:to_i)
  rest << [b, (a + b - 1) / b * b - a]
end

res = 0
while !rest.empty?
  b, r = rest.pop
  res += (r - res) % b
end
puts res

Measured memory_bytes: 20980
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
typedef long long ll;

using ipair = pair<int, int>;

ll INF = 1e16+7;

bool operator>(const ipair a,const ipair b){return a.first > b.first;}


int dp[(int)1e5+1][13];

int MOD = 1e9+7;

vector<vector<int>> cnt_chars;

vector<int> count_char(string& str){
  vector<int> ret(26, 0);
  rep(i, 10){
    ret[str[i]-'a']++;
  }
  return ret;
}

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

  vector<string> strs;
  rep(i, N){
    string tmp;
    cin >> tmp;
    strs.push_back(tmp);
  }
  
  map<vector<int>, ll> mp;

  rep(i, N){
    mp[count_char(strs[i])]++;
  }

  ll ans = 0;

  for(auto p: mp){
    ll value = p.second;
    if(value >= 2){
      ans += (value*(value-1))/2;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 25972
#include<bits/stdc++.h>
#define PROB "a"
using namespace std;
int k;
void init()
{
    freopen(PROB".inp","r",stdin);
    freopen(PROB".out","w",stdout);
}

void Nhap()
{
    scanf("%d",&k);
}

void XuLi()
{
    int dem=0;
    for(int i=1; i<=k; i++) {
        for(int j=1; j<=k; j++) {
            if(i==j) continue;
            if((i%2==0 && j%2==1)|| (i%2==1 && j%2==0)) dem++;
        }
    }
    printf("%d",dem/2);
}

int main()
{
    Nhap();
    XuLi();
}


Measured memory_bytes: 256
dp = [[0]*8 for i in range(1001)]
dp[0][1] = 1
n = input()
s = raw_input()
for i in range(n):
    b = 1 if s[i] == "J" else 2 if s[i] == "O" else 4
    for j in range(8):
        for k in range(8):
            if (k & b) and (j & k):
                dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % 10007
print reduce(lambda x, a: (x + a) % 10007, dp[n])

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	int n;cin>>n;
	vl a(n),b(n),c(n);
	rep(i,n){
		cin>>a[i];
	}
	rep(i,n){
		cin>>b[i];
	}
	rep(i,n){
		c[i]=a[i]-b[i];
	}
	sort(all(c));
	ll sum1=0,cnt1=0,sum2=0,cnt2=0;
	rep(i,n){
		if(c[i]<0){
			sum1+=c[i];
			cnt1++;
		}
	}
	rep(i,n){
		if(abs(sum1)<=sum2){
			cout<<cnt1+cnt2<<endl;
			return 0;
		}
		if(c[n-1-i]>0){
			sum2+=c[n-1-i];
			cnt2++;
		}	
	}
    if(abs(sum1)<=sum2){
		cout<<cnt1+cnt2<<endl;
	    return 0;
	}
	cout<<-1<<endl;
}


Measured memory_bytes: 2560
import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        Solution task = new Solution(in, out);
        task.solve();
        out.close();
	}

	static class Solution {
		
		private InputReader in;
		private PrintWriter out;

		public Solution(InputReader in, PrintWriter out) {
			this.in = in;
			this.out = out;
		}

		public void solve() {
            String s = in.next();
            out.println(s.substring(0, s.length() - 8));
		}
	}

	static class InputReader {
        
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
	
}


Measured memory_bytes: 21588
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Supplier<String> sc) {
		char[] S = sc.get().toCharArray();
		int count = 0;
		for (int i = 1; i < S.length; i++) {
			if (S[i - 1] != S[i]) count += 1;
		}
		System.out.println(count);
	}
}

class Main {
	public static void main(String... args) {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<String>() {
			private StringTokenizer tokenizer;

			public String get() {
				try {
					return (tokenizer = tokenizer != null && tokenizer.hasMoreTokens() ? tokenizer : new StringTokenizer(reader.readLine())).nextToken();
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
		});
	}
}

Measured memory_bytes: 23124
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
using namespace std;
inline void read(int &x)
{
    int s=0,w=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
    while(isdigit(c)){s=(s<<3)+(s<<1)+c-'0',c=getchar();}
    x=s*w;
}
const int N=200010;
typedef long long ll;
#define rg register int
#define pb push_back
struct data
{
    ll x,y;
    data(){};
    data(ll _x,ll _y):x(_x),y(_y){}
};
inline bool cmpx(const data &A,const data &B){return A.x<B.x;}
inline bool cmpy(const data &A,const data &B){return A.y<B.y;}
vector<data>f[N];
ll d[N],mn[N];
inline void solve(vector<data>a,vector<data>b,vector<data>&c,ll e,ll mid)
{
    if(!a.size()||!b.size())return ;
    if(a.size()>b.size())
        swap(a,b);
    sort(a.begin(),a.end(),cmpy),sort(b.begin(),b.end(),cmpx);
    int sb=b.size();
    for(rg i=0;i<sb;i++)
        if(!i)mn[i]=b[i].y;
        else mn[i]=min(mn[i-1],b[i].y);
    for(rg i=0,j=sb-1;i<a.size();i++)
    {
        while(j>=0&&a[i].y+b[j].x-2*e>mid)j--;
        if(~j)c.pb(data(a[i].x,mn[j]));
    }
    sort(a.begin(),a.end(),cmpx),sort(b.begin(),b.end(),cmpy);
    for(rg i=0;i<sb;i++)
        if(!i)mn[i]=b[i].x;
        else mn[i]=min(mn[i-1],b[i].x);
    for(rg i=0,j=sb-1;i<a.size();i++)
    {
        while(j>=0&&a[i].x+b[j].y-2*e>mid)j--;
        if(~j)
            c.pb(data(mn[j],a[i].y));
    }
}
int ls[N],rs[N];
bool cao;
inline void dfs(int u,ll mid)
{
    f[u].clear();
    if(!ls[u])
    {
        f[u].pb(data(d[u],d[u]));
        return ;
    }
    if(cao)return ;
    dfs(ls[u],mid),dfs(rs[u],mid);
    if(cao)return ;
    solve(f[ls[u]],f[rs[u]],f[u],d[u],mid);
    f[ls[u]].clear(),f[rs[u]].clear();
    if(!f[u].size())cao=1;
}
int n;
ll L,R,ans;
int main()
{
    //freopen("cc.in","r",stdin);
    //freopen("cc.out","w",stdout);
    read(n);
    for(rg i=2,x,y;i<=n;i++)
    {
        read(x),read(y);
        d[i]=d[x]+y,R=max(R,d[i]);
        if(ls[x])rs[x]=i;
        else ls[x]=i;
    }
    R<<=1;
    while(L<=R)
    {
        ll mid=(L+R)>>1;
        cao=0;
        dfs(1,mid);
        if(!cao)ans=mid,R=mid-1;
        else L=mid+1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 30568
#include <iostream>
#include <vector>
#define llint long long
#define inf 1e18

using namespace std;

llint n, m;
llint a[100005];
llint cnt[55];
llint dp[55][2];

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

  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i];

  for(int i = 0; i < 40; i++){
    for(int j = 1; j <= n; j++){
      if(a[j] & (1LL<<i)) cnt[i]++;
    }
  }

  for(int i = 40; i >= 0; i--){
    for(int j = 0; j < 2; j++){
      dp[i][j] = -inf;
    }
  }
  dp[40][0] = 0;

  for(int i = 40; i > 0; i--){
    for(int j = 0; j < 2; j++){
      for(int k = 0; k < 2; k++){
        if(j == 0 && k == 1 && (m&(1LL<<(i-1))) == 0) continue;
        int nj = j;
        if(k == 0 && (m&(1LL<<(i-1)))) nj = 1;
        if(k == 0) dp[i-1][nj] = max(dp[i-1][nj], dp[i][j] + cnt[i-1] * (1LL<<(i-1)));
        else dp[i-1][nj] = max(dp[i-1][nj], dp[i][j] + (n-cnt[i-1]) * (1LL<<(i-1)));
      }
    }
  }

  llint ans = max(dp[0][0], dp[0][1]);
  cout << ans << endl;

  return 0;
}


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

int main(){
   string s;
   cin>>s;
   int n= s.size();
    if(n%2!=0){
        cout<<"No"<<endl;
        return 0;
    }
   rep(i,s.size()){
       if(s[i]=='h'&&s[i+1]=='i'){
           i+=1;
       }else{
           cout<<"No"<<endl;
           return 0;
       }
   }
   cout<<"Yes"<<endl;

   return 0; 
}

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

int toSec(int h,int m,int s){
	return h*3600+m*60+s;
}

void printTime(int sec){
	printf("%02d:%02d:%02d\n",sec/3600,sec%3600/60,sec%60);
}

int main(void){
	int h,m,s;

	while(cin>>h>>m>>s && !(h==-1 || m==-1 || s==-1)){
		int sec = toSec(h,m,s);

		printTime(7200 - sec);
		printTime((7200 - sec) * 3);
	}

	return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int x,a,b;
	scanf("%d%d%d",&x,&a,&b);
	if(abs(x-a)<abs(x-b))
	{
		printf("A");
	}else
	{
		printf("B");
	}
	return 0;
}


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

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

#define in(s) cin >> s
#define out(s) cout << s << endl
#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define pcnt __builtin_popcount
#define pcntll(x) __builtin_popcountll(x)
#define DMAX DBL_MAX;
#define IMIN INT_MIN;
#define IMAX INT_MAX;

//const ll MOD = 1e9+7;
//const ll MOD = 998244353;
//const ll MAX = 3e5+1;
//const ll INF = 1e18;
//const ld PI = acos(-1L);

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int N;
    in(N);
    vector<ll> A(N);
    rep(i, N) in(A[i]);
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    priority_queue<ll> space;
    space.push(A[0]);
    ll ans = 0;
    rept(i, 1, N) {
        ans += space.top();
        space.pop();
        space.push(A[i]);
        space.push(A[i]);
    }
    out(ans);



    return 0;
}


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

const int maxn = 1e5 + 5;

int n, k, a, b, v, p, reqparity[2][maxn];
vector<int> adj[maxn];
vector<pii> mivals[maxn], mavals[maxn]; // {mi / ma, from}

void up(int x, int p)
{
    for(auto v : adj[x])
        if(v != p)
        {
            up(v, x);
            mivals[x].push_back({mivals[v][0].first - 1, v});
            mavals[x].push_back({mavals[v][0].first + 1, v});
            for(int j = 0; j < 2; j++)
                reqparity[j][x] |= reqparity[j ^ 1][v];
        }
    sort(mivals[x].begin(), mivals[x].end(), greater<pii>());
    sort(mavals[x].begin(), mavals[x].end());
}

void down(int x, int p, int parmi, int parma)
{
    if(p != -1)
    {
        mivals[x].push_back({parmi - 1, p});
        mavals[x].push_back({parma + 1, p});
        for(int j = 0; j < 2; j++)
            reqparity[j][x] |= reqparity[j ^ 1][p];
        sort(mivals[x].begin(), mivals[x].end(), greater<pii>());
        sort(mavals[x].begin(), mavals[x].end());
    }
    for(auto v : adj[x])
        if(v != p)
        {
            int takemi = -2e9, takema = 2e9;
            for(auto y : mivals[x])
                if(y.second != v)
                {
                    takemi = y.first;
                    break;
                }
            for(auto y : mavals[x])
                if(y.second != v)
                {
                    takema = y.first;
                    break;
                }
            down(v, x, takemi, takema);
        }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 2; j++)
            reqparity[j][i] = 0;
        mivals[i].push_back({-2e9, i});
        mavals[i].push_back({2e9, i});
    }
    for(int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin >> k;
    for(int i = 0; i < k; i++)
    {
        cin >> v >> p;
        v--;
        reqparity[p & 1][v] = 1;
        mivals[v].push_back({p, v});
        mavals[v].push_back({p, v});
    }
    up(0, -1);
    down(0, -1, -2e9, 2e9);
    int bad = 0;
    for(int i = 0; i < n; i++)
        if((reqparity[0][i] && reqparity[1][i]) || mivals[i][0].first > mavals[i][0].first)
            bad = 1;
    if(bad)
        cout << "No\n";
    else
    {
        cout << "Yes\n";
        for(int i = 0; i < n; i++)
            cout << mivals[i][0].first << "\n";
    }
    return 0;
}

Measured memory_bytes: 44220
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define FOR(i, s, n) for(int i=(int)(s); i<(int)(n); ++i)
#define ALL(n) (n).begin(), (n).end()
#define pb push_back

using namespace std;

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

const ll MAX_V = 100000;
const ll INF = 1e9;
const ll MOD = 998244353;

int main(){
    int n; cin >> n;
    vi a(n);
    REP(i, n) cin >> a[i];
    vector<ll> s;
    ll sum = 0;
    REP(i, n){
        // sum += a[i] - (i+1);
        s.pb(a[i]-(i+1));
    }
    sort(ALL(s));
    if (n % 2 == 0){
        vector<ll> ans;
        ll sum = 0;
        REP(k, 2){
            REP(i, n){
                sum += abs(a[i]-s[(n/2)+k]-(i+1));
            }
            ans.pb(sum);
        }
        cout << min(ans[0], ans[1]) << endl;
    }else{
        ll sum = 0;
        REP(i, n){
            sum += abs(a[i]-s[(n/2)]-(i+1));
        }
        cout << sum << endl;
    }
}

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



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

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



int main(void){

	vector<vector<int>>	c(3, vector<int>(3));
	REP(i,3) REP(j,3) cin >> c[i][j];

	vector<int> x(3);
	vector<int> y(3);

	x[0] = 0;
	REP(i,3){
		y[i] = c[0][i] - x[0];
	}

	REP(i,3){
		x[i] = c[i][0] - y[0];
	}

	bool ans = true;
	REP(i,3){
		REP(j,3){
			if(c[i][j] != x[i]+y[j]) ans = false;
		}
	}

	cout << (ans ? "Yes" : "No") << endl;



	return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    long r = 0;
    long g = 0;
    long b = 0;
    for(int i=0;i<n;i++){
        if(s[i]=='R')r++;
        else if(s[i] == 'G')g++;
        else b++;
    }
    long ans = r*g*b;
    for(int space = 1;space <n;space++){
        for(int i=0;i+2*space<n;i++){
        if(s[i]!=s[i+space] && s[i+space] != s[i+space*2] && s[i] != s[i+2*space])ans--;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3636