akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#define last(x, y) (x)[(x).size() - (y)]
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define in(X) ((X) - '0')
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199;
//const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

int n, x, k, ans = 0;
vector<int> a;
map<int, int> m;

int main() {
	fast;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> x, m[x]++;
	for (auto &i : m) a.push_back(i.second);
	sort(a.begin(), a.end());
	for (int i = 0; i + k < a.size(); i++)
		ans += a[i];
	cout << ans << endl;
}

Measured memory_bytes: 10744
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  int n=s.length(),a=0,b=0,c=0;
  for(int i=0;i<n;i++){
    if(s[i]=='a')a++;
    if(s[i]=='b')b++;
    if(s[i]=='c')c++;
  }
  if(max({a,b,c})-min({a,b,c})<=1){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
	
map<string,int> mp;
long long sum=0;
int n; 
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		string ss;
		cin>>ss;
		sort(ss.begin(),ss.end());
		sum+=mp[ss]++; 
	}
	printf("%lld",sum);
	return 0;
} 

Measured memory_bytes: 11136
N, A, B = [int(i) for i in input().split()]
if (B-A) % 2 == 0:
    print((B- A) // 2)
else:
    if A - 1 <= N - B:
        print(A + (B - A) // 2)
    else:
        print(N - B + 1 + (B - A) // 2)

Measured memory_bytes: 2940
N,L=tuple(map(int,input().split(" ")))

x=[L+i-1 for i in range(1,N+1)]

temp1=list(map(lambda x2:abs(x2),x))
temp2=min(temp1)

I=temp1.index(temp2)

x.remove(x[I])

print(sum(x))





Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(){
    
    int ans = 0, mxTmp = 0;
    for(int i = 0; i < 5; i++){
        int m;
        cin >> m;
        ans += m;
        if(m % 10){
            int tmp = 10 - m % 10;
            ans += tmp;
            mxTmp = max(mxTmp, tmp);
        }
    }
    cout << ans - mxTmp << endl;

    return 0;
}

Measured memory_bytes: 256
/*▄███████▀▀▀▀▀▀███████▄
░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
░▐██▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄█████████████  █▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define DEBUG
#define fi first
#define se second
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long
#define mk(a, b) make_pair(a, b)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<int, int, int> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector< vector<int> > vvi;
typedef vector<char> vc;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1000000007;
// const int MAXN = 3e5;
const ld eps = 1e-6;
const ld eps2 = 1e-9;
const int MOD2 = 998244353;
const int dosz = 5e5;
const int SZ = (1<<18);
const ld PI = atan2l(0, -1);


void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
        // freopen("a.in", "r",stdin);
#else
       // freopen("mxnl.in", "r", stdin);
       // freopen("mxnl.out", "w", stdout);
#endif
}


void solve(){
    int n;
    cin >> n;
    vi nums(n);
    for(int &i:nums)
        cin >> i;
    for(int i:nums){
        if(i&1)
            continue;
        if(min(i%3, i%5)!=0){
            cout << "DENIED" << endl;
            return;
        }
    }
    cout << "APPROVED" << endl;

}

signed main() {
    fast_io();
    int q = 1;
    // cout << fixed << setprecision(6);
    // cin >> q;
    // cout << 1 << endl;
    while(q--){
        solve();
    }
    return 0;
}



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

int main(){
  string s;
  cin>>s;
  int a,b,c,d;
  a=s[0]-'0';
  b=s[1]-'0';
  c=s[2]-'0';
  d=s[3]-'0';

  if(a+b+c+d==7){
    cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
    return 0;
  }
  if(a-b+c+d==7){
    cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
    return 0;
  }
  if(a+b-c+d==7){
    cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7"<<endl;
    return 0;
  }
  if(a+b+c-d==7){
    cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7"<<endl;
    return 0;
  }
  if(a+b-c-d==7){
    cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7"<<endl;
    return 0;
  }
  if(a-b-c+d==7){
    cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7"<<endl;
    return 0;
  }
  if(a-b+c-d==7){
    cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7"<<endl;
    return 0;
  }
  if(a-b-c-d==7){
    cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7"<<endl;
    return 0;
  }



  return 0;
}


Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>
//#include <deque>
//#include <bitset>
#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}
void chmax(ll &a,ll b){	if(a<b) a = b ;}
void chmin(ll &a,ll b){ if(a>b) a = b ;}

int main(){
    string s,t ;
    cin >> s >> t ;
    ll ans = INF ;
    for(int i=0;i<s.size();i++){
        if(i+t.size()>s.size()){
            break ;
        }
        ll cnt = 0 ;
        for(int j=0;j<t.size();j++){
            cnt += (t[j]!=s[i+j]) ;
        }
        chmin(ans,cnt) ;
    }
    cout << ans << endl ;
}

Measured memory_bytes: 3604
#include<stdio.h>
#include<ctype.h>
#define P(c) putchar(c)
int F(char*s)
{
	int r=0,a;
	for(;*s;++s)
	{
		if(isdigit(*s))a=*s++-'0';
		else a=1;
		if(*s=='m')r+=a*1000;
		if(*s=='c')r+=a*100;
		if(*s=='x')r+=a*10;
		if(*s=='i')r+=a;
	}
	return r;
}
int main()
{
	int n,a,k,i;
	char s[9],u[9],x[]="mcxi";
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s%s",s,u);
		a=F(s)+F(u);
		for(i=0,k=1000;i<4;++i,k/=10)
			if(a>=k){if(a>=2*k)P(a/k+'0');P(x[i]),a%=k;}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 0
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        int[] hw = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var h = hw[0];
        var w = hw[1];
        var n = int.Parse(Console.ReadLine());
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var list = new List<int>();


        int[,] ans = new int[h, w];
        int i = 0;
        int j = 0;
        int index = 0;
        var flag = true;
        while (true)
        {
            if (a[index] > 0) ans[j, i] = index + 1;
            else
            {
                index++;
                ans[j, i] = index + 1;
            }
            a[index]--;

            if (flag)
            {
                if (i == w - 1)
                {
                    j++;
                    flag = false;
                }
                else
                {
                    i++;
                }
            }
            else
            {
                if (i == 0)
                {
                    j++;
                    flag = true;
                }
                else
                {
                    i--;
                }
            }

            if (j >= h) break;
        }

        for (int x = 0; x < h; x++)
        {
            for (int y = 0; y < w; y++)
            {
                Console.Write(ans[x, y] + " ");
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 29492
module Main where

import Control.Applicative
import Control.Monad
import Data.List
import qualified Data.IntMap.Strict as M

f k v acc
    | k == v = acc
    | k >  v = v + acc
    | k <  v = (v - k) + acc

main :: IO ()
main = do
    getLine
    im <- M.fromListWith (+) . flip zip (repeat (1 :: Int))
            . fmap read . words <$> getLine
    let ans = M.foldrWithKey f 0 im
    print ans

Measured memory_bytes: 51580
n, m = map(int, input().split())
x = [0] * m
y = [0] * m
r = [0] * n
t = [0] * n
for i in range(m):
    x[i], y[i] = map(int, input().split())
    if t[x[i] - 1] == 0:
        r[x[i] - 1] = y[i]
        t[x[i] - 1] = 1
    else:
        if r[x[i] - 1] != y[i]:
            print(-1)
            exit()
if n>1 and r[0] == 0 and t[0] == 0:
    r[0] = 1
elif n > 1 and r[0] == 0 and t[0] != 0:
    print(-1)
    exit()
print(*r, sep='')


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            double ave = 0;
            double bun = 0;
            double bunm = 0;
            if(n == 0){
                break;
            }
            int[] ten = new int[n];
            for(int i = 0; i < ten.length;i++){
                ten[i] = sc.nextInt();
            }
            for(int i = 0;i <ten.length; i++){
                ave += ten[i];
            }
            ave = ave/ten.length;

            for(int i = 0;i < ten.length;i++){
                bunm = ten[i] - ave;
                bun += bunm*bunm;
            }
            bun = bun/ten.length;
            System.out.println(Math.sqrt(bun));
        }
        sc.close();
    }
}


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

using namespace std;

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

    string s, s2, s3;
    cin >> s >> s2 >> s3;
    cout << s[0] << s2[1] << s3[2];

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define fi first
#define se second
#define  pb push_back
#define  pob pop_back
#define W while
#define fn(i,x) for(int i=0;i<x;i++)
#define fs(i,s,x) for(int i=s;i<x;i++)
#define fr(i,x) for(int i=x;i>=0;i--)
#define fit(it,s) for(auto it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mod 1000000007
#define MAX 1005
using namespace std;
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);

    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    
    ll n,m;
    cin >> n >> m;
    
    ll k = pow(2,n);
    ll b[k][n];
    fn(i,k){
        ll o =i+1;
       fn(l,n){

         b[i][l] = o%2;
         o/=2;
       //  cout << b[i][l];
       }
       //cout << endl;
    }
    
   
    set<ll> s[m];
    fn(i,m){
       ll d;
       cin >> d;
       
       fn(j,d) {
         ll u;
         cin >> u;
         s[i].insert(u-1);
       }

    }

    ll p[m];
    fn(i,m) cin >> p[i];
  

    ll ans = 0;

    fn(i,k){
      
      ll x[m]={0};

      fn(j,n){

         if(b[i][j] == 1){

            fn(u,m){
               if(s[u].find(j) != s[u].end()) x[u]++;
            }

         }

      }

      ll f =1;
      fn(j,m) if(p[j]!=(x[j]%2)) f=0;
      if(f==1) ans++;
    }
    cout << ans;
    return 0;

}

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

int main(){
    using namespace std;

    unsigned long N, H;
    cin >> N >> H;

    vector<unsigned long> B(N);
    unsigned long A{0};
    for(auto&& i : B){
        unsigned long a;
        cin >> a >> i;
        A = max(a, A);
    }
    auto it = partition(begin(B), end(B), [&A](const auto& i){return i > A;});
    const auto& sum = accumulate(begin(B), it, 0UL);
    if(sum < H)cout << it - begin(B) + (H - sum + A - 1) / A << endl;
    else{
        sort(begin(B), it, greater<>());
        partial_sum(begin(B), it, begin(B));
        cout << lower_bound(begin(B), it, H) - begin(B) + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
import collections

def list_count(l):
    return collections.Counter(l)


n=int(input())
a=list(map(int,input().split()))
a_val_list=list_count(a)
a_sum=sum(a)

q=int(input())

for i in range(q):
    b,c=map(int,input().split())
    b_val=a_val_list.get(b, 0)
    a_val_list[b]=0
    a_sum-=b*b_val

    a_val_list[c]=a_val_list.get(c,0)+b_val
    a_sum+=c*b_val

    print(a_sum)




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

typedef long long LL;

int a[200005], b[10005], n;
char s[200005];
LL ans;

int work() {
    scanf("%s", s);
    n = strlen(s);
    int  t = 1;
    b[0]++;
    for (int i = n-1; i >= 0; --i) {
        a[i] = (a[i+1] + (s[i]-'0')*t) % 2019;
        t = t * 10 % 2019;
        ans += b[a[i]];
        b[a[i]]++;
    }

    printf("%lld\n", ans);
    return 0;
}

int main() {
    work();
    //while (~scanf("%d", &n)) work();
    //scanf("%d", &T); while (T--) work();

    return 0;
}


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

int main (){
	int N;cin>>N;
	vector<int> L(2*N);
	for(int i=0;i<(2*N);++i){
		int l;cin>>l;
		L[i]=l;
	}
	sort(L.begin(),L.end());
	int ans=0;

	for(int i=0;i<(2*N);i+=2){
		//cout<<L[i]<<endl;
		ans+=L[i];
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

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

  P(2*b - a);
  ret 0;
}

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define FORR(i,a,b) for(ll i=b-1;i>=a;i--)

#define vl vector<ll>
#define pll pair<ll,ll>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;
/*}}}*/

ll MOD = 1e9+7;
int main() {
  ll n,k;
  cin >> n >> k;
  vl pos,neg;
  REP(i,n){
    ll a;
    cin >> a;
    if(a>0) pos.push_back(a);
    if(a<0) neg.push_back(-a);
  }
  bool exists0 = pos.size()+neg.size()<n;
  // sort by abs decending
  sort(pos.begin(),pos.end());
  reverse(pos.begin(),pos.end());
  sort(neg.begin(),neg.end());
  reverse(neg.begin(),neg.end());

  // when answer is 0
  if(pos.size() + neg.size() < k){
    // always contains 0
    cout << 0 << endl;
    return 0;
  }
  if(exists0 && pos.size()==0 && k%2==1){
    // contains 0, otherwise ans is negative
    cout << 0 << endl;
    return 0;
  }

  // when answer is negative
  if(!exists0 && pos.size()==0 && k%2==1){
    reverse(neg.begin(),neg.end());
    ll ans = 1;
    REP(i,k){
      ans *= neg[i];
      ans %= MOD;
    }
    ans = MOD - ans;
    cout << ans << endl;
    return 0;
  }
  if(!exists0 && k==n && neg.size()%2==1){
    // select all non-zero variables
    ll ans = 1;
    REP(i,neg.size()){
      ans *= neg[i];
      ans %= MOD;
    }
    REP(i,pos.size()){
      ans *= pos[i];
      ans %= MOD;
    }
    ans = MOD - ans;
    cout << ans << endl;
    return 0;
  }

  // when answer is positive
  ll cp = 0;
  ll cn = 0;
  if(pos.size()==0) cn = k;
  else if(neg.size()==0) cp = k;
  else REP(i,k){
    if(cn < neg.size() && pos[cp] < neg[cn]){
      cn++;
    }else{
      cp++;
    }
  }
  // num of employed negative is odd
  if(cn%2!=0){
    if(cp==0 && pos.size()>0){
      cp++;
      cn--;
    }
    else if(cp < pos.size() && cn < neg.size()){
      ll candp = pos[cp-1] * pos[cp];
      ll candn = neg[cn-1] * neg[cn];
      if(candp>candn) {
        cp = cp+1;
        cn = cn-1;
      } else {
        cp = cp-1;
        cn = cn+1;
      }
    } else if (cn == neg.size()){
      cp = cp+1;
      cn = cn-1;
    } else if (cp == pos.size()){
      cp = cp-1;
      cn = cn+1;
    }
  }

  ll ans = 1;
  REP(i,cp){
    ans *= pos[i];
    ans %= MOD;
  }
  REP(i,cn){
    ans *= neg[i];
    ans %= MOD;
  }

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


Measured memory_bytes: 5428
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main()
{
	std::string s;
	unsigned long long cnt = 0, k, tmp;
	std::cin >> s >> k;
	int a = 1;
	for (int i= 0; i<k; i++)
	{
		if( s[i]!= '1' ){
			a = (int)(s[i] - '0');
			break;
		}		
	}

	std::cout << a << std::endl;
	return 0;
}

Measured memory_bytes: 256
import java.lang.Math.cbrt
import java.lang.Math.sqrt
fun cbrt(value:Int):Int {
    return cbrt(value.toDouble()).toInt()
}
fun sqrt(value:Int):Int {
    return sqrt(value.toDouble()).toInt()
}
fun main(args:Array<String>):Unit{
    while (true){
        val e = readLine()!!.toInt()
        if (e == 0) return
        var minM = Int.MAX_VALUE
        for (z in 0 .. cbrt(e)){
            val y = sqrt(e - z * z * z)
            val m = z + y + (e - z * z * z - y * y)
            if (minM > m)
                minM = m
        }
        println(minM)
    }
}


Measured memory_bytes: 35260
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    string s;
    cin >> s;
    int n = s.size();
    if(s[0] == s[n-1]){
        if(n % 2 == 1) cout << "Second" << endl;
        else cout << "First" << endl;
    }
    else{
        if(n % 2 == 0) cout << "Second" << endl;
        else cout << "First" << endl;        
    }
}

Measured memory_bytes: 512
from itertools import accumulate

n, k = list(map(int,input().split(" ")))
s = input()


def solve():
    cnt=0
    l=[]
    prev = '1'

    for i in s:
        if prev ==i:
            cnt+=1
        else:
            l.append(cnt)
            cnt = 1
        prev=i
    l.append(cnt)
    if prev=='0':
        l.append(0)

    w = 2*k+1

    if len(l)<=w:
        return n

    acc = [0]+list(accumulate(l))
    ans = 0
    for i in range(0, len(l)-w+1,2):
        ans = max(ans,acc[i+w]-acc[i])
    return ans
print(solve())


Measured memory_bytes: 8700
#include <iostream>
#include <string>
#include <limits.h>
#include <numeric>
#include <math.h>
#include <bits/stdc++.h>
#define rep(i,c) for (int i=0;i<c;i++)
using namespace std;
typedef long long ll;

    
    

int main(){
    ll A,B,C,K;
    cin >> A>> B >> C >> K;
    int point = 0;
    int count = 0;

    rep(i,A){
        if(count !=K){
            point++;
            count++;
        }
        else break;
    }
    rep(i,B){
        if(count!=K) count++;
        else break;
        
    }
    rep(i,C){
        if(count !=K){
            point--;
            count++;
        }
        else break;
    }

    cout << point << endl;
}

Measured memory_bytes: 3672
import bisect
import sys


N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v


def dfs(v):
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        pos = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u)
    if pos == -1:
        dp.pop()
    else:
        dp[pos] = back


ans = [-1] * N
sys.setrecursionlimit(10 ** 6)
dp = []
dfs(0)


for an in ans:
    print(an)


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

ll F(ll num)
{
	ll c{0};
	while (num % 2 == 0)
	{
		c++;
		num /= 2;
	}
	return c;
}

int main(int argc, char **argv)
{
	ll N; cin >> N;
	ll res{0};
	for (ll _ = 0; _ < N; _++)
	{
		ll a; cin >> a;
		res += F(a);
	}
	std::cout << res << std::endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + x[i]
mincost = 2 * n * m + 5 * cum[n]
for k in range(1,n):
    cost = m * (n + k)
    for i in range(n//k):
        cost += (cum[(i+1)*k] - cum[i*k]) * max(5, 3 + i*2)
    cost += (cum[n] - cum[n//k * k]) * max(5, 3 + n//k*2)
    mincost = min(mincost, cost)
print(mincost)

Measured memory_bytes: 89552
import java.util.Scanner;

public class Main {
    public static void main(String s[]){
        Scanner sc=new Scanner(System.in);
        int n=0;
        if(sc.hasNextInt())
            n=sc.nextInt();
        int cnt=0;
        boolean res=false;
        while(n--!=0){
            byte x=sc.nextByte();
            byte y=sc.nextByte();
            if(x==y)
                cnt++;
            else
                cnt=0;
            if(cnt==3)
                res=true;
        }
        if(res)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


Measured memory_bytes: 27276
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define all(a) a.begin(),a.end()
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*pi*/const double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll i,fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
/*桁数*/ll dig(ll n){ll d=0,i=0;while(n/10>0){i++;d++;}return d;}
/*迷路移動*/const int dx[4]={1,0,-1,0};const int dy[4]={0,1,0,-1};
llfor;//ll ans=0;////////////////////////////////////////////////////////////
int main(){
 ll n,m;
 cin>>n>>m;
 ll ans=1,tmp=m;
 bool end=prime(m);
 if(m%n==0){
  pr(m/n);
  return 0;
 }
 for(i=2;i*n<=m;i++){
  if(m%i==0&&m/i>=n){
   ans=max(ans,i);
  }
 }
 pr(ans);
 return 0;}

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

const int MAXN = 21;
const int MAXS = 1<<14;
int N, S;
int M[MAXN];
int mem[MAXS][MAXN];

int rec(int s, int k) {
  int &res = mem[s][k];
  if(res != -1) return res;
  if(s == 0) return res = 1;
  for(int i = 1; i <= M[k] && s-i >= 0; ++i) {
    if(rec(s-i, (k+1)%N) == 0) {
      return res = 1;
    }
  }
  return res = 0;
}

int main() {
  while(cin >> N && N) {
    N *= 2;
    cin >> S;
    for(int i = 0; i < N; ++i) cin >> M[i];
    fill(mem[0], mem[MAXS], -1);
    cout << rec(S, 0) << endl;
  }
  return 0;
}

Measured memory_bytes: 2756
#include <bits/stdc++.h>
using namespace std;
void init()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
}
long long n, w;
long long arr[109][100005];
vector<long long> val;
vector<long long>wt;
long long knap(int indx, long long cap)
{
    if(indx==n||cap==0)
        return 0;
     if(arr[indx][cap]!=-1)
    {return  arr[indx][cap];}
    return arr[indx][cap]=max(knap(indx+1,cap),cap-wt[indx]>=0?val[indx]+knap(indx+1,cap-wt[indx]):-1000000000);
}
int main()
{
    init();
    cin>>n>>w;
    val.resize(n);
    wt.resize(n);
      for(int i=0; i<n; i++)
        cin>>wt[i]>>val[i];
        memset(arr,-1,sizeof(arr));
    cout<<knap(0,w);
    return 0;
}


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

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define CEVCOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define P pair<int , int>
#define V vector<int>
#define M map<int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
	int r, D , x;		cin >> r >> D >> x;
	for(int i = 0 ; i < 10 ; i++){
	 	int keep = r * x - D;
		SCOUT(keep) << endl;
      	x = keep;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
/// ye tec khaphan ke yadam bemone : age jayi didi soale masir hamiltoni mikhad rasasho bokon yal oilery;
/// age ye ja mikhasti to dp az ozv i k ta entekhab koni bejash ye log bezan (nominal) hamoon 2**k va o 1 ent kon

///\\\///\\\///\\\\\\\\\\\\\\\\\///\\\///\\\///

const int N=2e5,mod=1e9+7;
ll a[N];

int32_t main(){
    ll n;
    cin >> n;
    ll ans=0;
    for (int i=0;i<n;i++){
        ll x;
        cin >> x;
        if (x%2){
            ans++;
        }
    }
    if (ans%2){
        cout << "NO";
    }
    else{
        cout << "YES";
    }
}
















Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}

const int inf = 1e9 + 10;

int H, W;
string S[2010];

bool done[2005][2005];
int tate[2005][2005], yoko[2005][2005];

signed main()
{
	cin >> H >> W;

	rep(i, H) cin >> S[i];

	rep(i, H) rep(j, W) {
		if (S[i][j] == '#') {
			tate[i][j] = -1;
			yoko[i][j] = -1;
		}
	}

	rep(i, H) rep(j, W) {
		if (S[i][j] == '.') {
			if  (tate[i][j] == 0) {
				int cur = 0;
				int y;
				for (y = i; y < H; ++y) {
					if (S[y][j] == '#') break;
					done[y][j] = true;
					cur++;
				}
				for (; y > i; --y) {
					tate[y - 1][j] = cur;
				}
			}
			if (yoko[i][j] == 0) {
				int cur = 0;
				int x;
				for (x = j; x < W; ++x) {
					if (S[i][x] == '#') break;
					done[i][x] = true;
					cur++;
					yoko[i][x] = cur;
				}
				for (; x > j; --x) {
					yoko[i][x - 1] = cur;
				}
			}

			done[i][j] = true;
		}
	}

	int mx = 0;

	rep(i, H) rep(j, W) chmax(mx, tate[i][j] + yoko[i][j] - 1);

	cout << mx << endl;
}




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

using namespace std;

typedef long long ll;
typedef vector<int> pi;
typedef pair<int,int> vi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(vi c, vi d){
	return c.S < d.S;
}

int main() {
	int A, B, M;
	cin >> A >> B >> M;
	int ref[A], mic[B], mina=10000001, minb=10000001;
	
	REP(i, 0, A){
		cin >> ref[i];
		mina = min(ref[i], mina);
	}
	REP(i, 0, B){
		cin >> mic[i];
		minb = min(mic[i], minb);
	}
	
	int minv = mina + minb;
	int a, b, d;
	REP(i, 0, M){
		cin >> a >> b >> d;
		if(ref[a-1]+mic[b-1]-d < minv) minv = ref[a-1]+mic[b-1]-d;
	}
	cout << minv;
}


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const int MX = 1000006;
const ll IV3 = 333333336;

ll inv[MX], kth[MX], pw3[MX], ans;
int n;

int main()
{
	scanf("%d", &n);
	inv[1] = 1, pw3[0] = 1;
	for(int i=2; i<=n; i++) inv[i] = (MOD*MOD - (MOD/i)*inv[MOD%i]) % MOD;
	for(int i=1; i<=n; i++) kth[i] = (kth[i-1] + inv[n]*inv[n-i+1]) % MOD;
	for(int i=1; i<=n; i++) pw3[i] = pw3[i-1] * IV3 % MOD;
	for(int i=1; i<=n; i++) ans = (ans + pw3[i]*2*kth[i]) % MOD;
	ans = (ans + pw3[n]*kth[n]) % MOD * IV3 % MOD;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 23680
// template version 1.11
using namespace std;
#include <iostream>
#include <bits/stdc++.h>

// varibable settings {{{
#define infile "../test/sample-1.in"
#define int long long
const int INF=1e18;
const int MOD=1e9+7;
// }}}

// define basic macro {{{
#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 _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

int solve(){
  int N,Q;cin>>N>>Q;
  map<int, vector<pii>> E;
  rep(i, N){
    int s,t,x;cin>>s>>t>>x;
    E[x].pb(mp(s-x, t-1-x));
  }
  // dump(E);

  vector<int> D(Q);
  vector<int> OD(Q);
  rep(i, Q) {
    cin>>D[i];
  }
  // dump(D);
  OD = D;
  sort(all(D));

  vvi imosp(Q+1, vi());
  vvi imosm(Q+1, vi());

  each(e, E){
    int x = e.first;
    each(el, e.second){
      int l = el.first;
      int r = el.second;
      int lidx = lower_bound(all(D), l) - D.begin();
      int ridx = upper_bound(all(D), r) - D.begin();
      imosp[lidx].pb(x);
      imosm[ridx].pb(x);
    }
  }

  map<int, int> ans;
  multiset<int> S;
  rep(i, Q){
    int d = D[i];
    each(x, imosp[i]){
      S.insert(x);
    }
    each(x, imosm[i]){
      multiset<int>::iterator hit(S.find(x));
      if (hit!=S.end()) S.erase(hit);
    }
    if (!S.empty()){
      int y = *S.begin();
      ans[d] = y;
    }
  }

  rep(i, Q){
    int d = OD[i];
    if (ans.find(d)!=ans.end()){
      cout << ans[d] << endl;
    }
    else{
      cout << -1 << endl;
    }
  }

  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


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

int main() {
  int a, b;
  cin >> a >> b;
  if (a % 2 == 1 && b % 2 == 1){
    cout << (a + b) / 2 << endl;
  }
  else if (a % 2 == 0 && b % 2 == 0){
    cout << (a + b) / 2 << endl;
  }
  else {
    cout << ((a + b) / 2) + 1 << endl;
  }
}


Measured memory_bytes: 256
// template {

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

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

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

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

// }}}

const int tb[][8] = {
	{3, 0, 1, 2, 7, 4, 5, 6},
	{4, 0, 3, 7, 5, 1, 2, 6},
	{4, 5, 1, 0, 7, 6, 2, 3}
};

map<string, int> cv;
set<int> dn;
int a[8];

int main()
{
	while (true){
		cv.clear();
		dn.clear();

		string s;
		rep(i, 8){
			if (!(cin >> s)) return 0;
			int t = cv.size();
			if (cv.count(s)) a[i] = cv[s];
			else cv[s] = a[i] = t;
		}

		int res = 0;
		int perm[8];
		int c[64];
		iota(perm, perm + 8, 0);
		do {
			array<int, 8> b;
			rep(i, 8) b[i] = a[perm[i]];
			bool f = true;
			rep(i, 64){
				c[i] = 0;
				rep(j, 8) c[i] = c[i] * 8 + b[j];
				if (dn.count(c[i])) f = false;
				array<int, 8> dst;
				rep(j, 8){
					dst[j] = b[tb[0][j]];
				}
				if (i % 4 == 3){
					rep(j, 8){
						dst[j] = b[tb[1][j]];
					}
				}
				if (i % 16 == 15){
					rep(j, 8){
						dst[j] = b[tb[2][j]];
					}
				}
				b = dst;
			}
			if (f) res++;
			rep(i, 64) dn.insert(c[i]);
		} while (next_permutation(perm, perm + 8));
		
		cout << res << endl;
	}
}

Measured memory_bytes: 5052
n,x=map(int,input().split())
a=list(map(int,input().split()))
eat=0
for i in range(1,n):
  s=a[i-1]+a[i]-x
  if(s>0):
    eat+=min(s,a[i])
    a[i]-=min(s,a[i])
s=a[1]+a[0]-x
eat+=max(s,0)
print(eat)

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

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

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

const int N = (int)2e5 + 123, inf = 1e9;
const ll INF = 1e18;
int n, a[N];
bool check(int k){
	stack< pii > st;
	st.push({1, 1});
	for(int i = 1; i < n; i++){
		if(a[i] > a[i - 1])
			continue;
		while(!st.empty() && st.top().f > a[i])
			st.pop();	
		int last = a[i];
		while(!st.empty()){
			auto it = st.top();
			if(it.f < last && k > 1){
				st.push({last, 2});
				break;
			}
			if(it.s == k){
				last = it.f - 1;
				st.pop();
				continue;
			}
			st.pop();
			it.s++;
			st.push(it);
			break;
		}
		if(st.empty())
			return 0;
	}
	return 1;
}
int main(){
	scanf("%d", &n);         
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	int l = 1, r = n;
	while(l <= r){
		int m = (l + r) / 2;
		if(check(m))
			r = m - 1;
		else
			l = m + 1;
	}
	printf("%d", l);
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define mod 1000000007LL
#define FOR(i,m,n) for(int i = (m); i < (n); i++)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) v.begin(),v.end()
#define sz(v) int(v.size())
 
 
typedef long long ll;
typedef vector<int> vi; 
typedef pair<int,int> ii;

ll power(ll a, ll b){
    int ans = 1;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
 

int main(){
	fastio;

    int n; cin>>n;
    vector<ll> v(n);
    vector<ll> p(n);
    FOR(i,0,n) cin>>v[i];
    p[0]=v[0];
    FOR(i,1,n) p[i]=p[i-1]+v[i];
    
    
    int x, y, z;
    ll ans, ans_=1e15;
    FOR(i,1,n-2){
        int pos=lower_bound(all(p),(p[i]+1)/2)-p.begin();
        if(pos-1>=0 && abs(2LL*p[pos]-p[i])>abs(2LL*p[pos-1]-p[i])) x=pos-1;
        else x=pos;
        pos=lower_bound(all(p), p[i]+(p[n-1]-p[i]+1)/2)-p.begin();
        ll xd=p[pos]-p[i], xdd=p[pos-1]-p[i];
        if(pos-1> i && abs(xd-p[n-1]+p[pos])>abs(xdd-p[n-1]+p[pos-1])) z=pos-1;
        else z=pos;
        
        ll sum1=p[x], sum2=p[i]-p[x], sum3=p[z]-p[i] ,sum4=p[n-1]-p[z];
        ans=max({abs(sum1-sum2), abs(sum1-sum3), abs(sum1-sum4), abs(sum2-sum3), abs(sum2-sum4), abs(sum3-sum4)});
        // cout<<"ans="<<ans<<endl;
        // cout<<x<<" "<<i<<" "<<z<<endl;
        ans_=min(ans, ans_);
    }

    cout<<ans_<<endl;

	return 0;
}

Measured memory_bytes: 6352
#include<cstdio>

#define ran 202202

int f[ran], s[ran];

int main() {
	for(int i=2;i<ran;i++) {
		if (f[i]) continue;
		for(int j=i+i;j<ran;j+=i)
			f[j] = true;
	}
	
	for(int i=3;i<ran;i++) {
		s[i] = s[i-1];
		if (!f[i] && !f[(i+1)/2]) s[i]++;
	}
	
	int n; scanf("%d", &n);
	for(int i=0;i<n;i++) {
		int l, r; scanf("%d%d", &l, &r);
		printf("%d\n", s[r] - s[l-1]);
	}
	
	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int main() {
	int k,n;
	cin>>k>>n;
	int minv=k+1;
	int a[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		int kkkk=(i+n-2)%n+1;
		int kkk=(a[kkkk]+k-a[i])%k;
		if(minv>kkk){
			minv=kkk;
		}
	}
	cout<<minv;

	return 0;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    ArrayList<Integer> arr = new ArrayList<Integer>();
    for (int i =0;i<n;i++){
    	arr.add(sc.nextInt());
    }
    Collections.sort(arr);

    long ans = 0l;
    for (int i = 0; i < n-k;i++) {
    	ans+=arr.get(i);
    }
    System.out.println(ans);
  }
}




Measured memory_bytes: 91020
eps = 1e-10

def add(a, b):
    return 0 if abs(a + b) < eps * (abs(a) + abs(b)) else a + b

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(add(self.x, p.x), add(self.y, p.y))

    def __sub__(self, p):
        return Point(add(self.x, -p.x), add(self.y, -p.y))

    def __mul__(self, d):
        return Point(self.x * d, self.y * d)

    def dot(self, p):
        return add(self.x * p.x, self.y * p.y)

    def det(self, p):
        return add(self.x * p.y, -self.y * p.x)

    def __str__(self):
        return "({}, {})".format(self.x, self.y)




def convex_hull(ps):
    ps = [Point(x, y) for x, y in sorted([(p.x, p.y) for p in ps])]
    upper_hull = get_bounds(ps)
    ps.reverse()
    lower_hull = get_bounds(ps)
    del upper_hull[-1]
    del lower_hull[-1]
    upper_hull.extend(lower_hull)
    return upper_hull

def get_bounds(ps):
    qs = [ps[0], ps[1]]
    for p in ps[2:]:
        while len(qs) > 1 and (qs[-1] - qs[-2]).det(p - qs[-1]) <= 0:
            del qs[-1]
        qs.append(p)
    return qs
    
while True:
    n = int(input())
    if n == 0: break
    points = []
    for i in range(n):
        x, y = map(float, input().split(','))
        points.append(Point(x, y))
    print(len(points) - len(convex_hull(points)))
    

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

using namespace std;
int main(){
    int N, x;
    int a[105];
    cin >> N >> x;
    for (int i = 0; i < N; i++){
        cin >> a[i];
    }
    sort(a, a+N);

////a 1 2 3 3 3  
////R0 1 3 6 9 12

//   10  20  30
//  0

    int R=0; //累積和
    int j=0; //満足している人の数
    while(R < x){
        if(R+a[j] > x){
            break;
        }
        else if( (R+a[j]) == x){
            j++; break;
        }
        else if (j!=N-1){
            R=R+a[j];
            j++;
        }
        else{
            break;
        }
    }

    cout << j << endl;

}

Measured memory_bytes: 256
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int Y = sc.nextInt();
    
    for(int i = 0; i <= N; i++){
      for(int j = 0; j <= N-i; j++){
        int k = N-i-j;
        if(10000*i + 5000*j + 1000*k == Y){
          System.out.println(i+" "+j+" "+k);
          return;
        }
      }
    }
    
    System.out.println("-1 -1 -1");
  }
}

Measured memory_bytes: 23636
MOD = 10**9 + 7


def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a, MOD)

print(ans)


Measured memory_bytes: 16192
#include <iostream>

int main(){
    int a,b,k;
    std::cin >> a >> b >>k;
    int sum=0;
    int s,m;
    if(a>b){
        s=b;
        m=a;
    } else {
        s=a;
        m=b;
    }
    int h[m];
    for(int i=1;i<=s;++i){
        if(a%i==0&&b%i==0){
            h[sum]=i;
            sum++;
        }
    }
    std::cout << h[sum-k] << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
// online submission
#endif
	string s,t;
	cin>>s>>t;
	int count=0;
	for(int i=0;i<s.size();i++){
		if(s[i]!=t[i]){
			count++;
		}
	}
	
	cout<<count;

}

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

int main(){
  int n;
  long a[100000];
  int p2 = 0, p4 = 0;
  std::cin >> n;
  for(int i = 0; i < n; i++) std::cin >> a[i];

  for(int i = 0; i < n; i++) if(!(a[i] % 2)) p2++;
  for(int i = 0; i < n; i++) if(!(a[i] % 4)) p4++;
  int q4 = p4;
  int q2 = p2 - q4;
  int q1 = n - p2;

  if((q1 == q4 + 1 && q2 == 0) || q1 < q4 + 1) std::cout << "Yes";
  else std::cout << "No";

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<string, int> P;

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

	string str;
	getline(cin, str);

	vector<P> vec;
	int m = 0;
	string longest;
	for(size_t i = 0; i < str.size(); ++i){
		if(i == 0 || str[i - 1] == ' '){
			int end = 0;
			for(size_t j = 0; i + j < str.size(); ++j){
				if(i + j == str.size() - 1 || str[i + j + 1] == ' '){
					end = j + 1;
					break;
				}
			}

			string s = str.substr(i, end);

			if(end > m){
				m = end;
				longest = s;
			}

			bool check = true;
			for(size_t i = 0; i < vec.size(); ++i){
				if(vec[i].first == s){
					vec[i].second ++;
					check = false;
					break;
				}
			}

			if(check){
				vec.push_back(P(s, 1));
			}
		}
	}

	int m2 = 0;
	string most;
	for(size_t i = 0; i < vec.size(); ++i){
		//cout << vec[i].first << endl;
		if(vec[i].second > m2){
			m2 = vec[i].second;
			most = vec[i].first;
		}
	}

	cout << most << " " << longest << endl;

	return 0;
}

Measured memory_bytes: 1188
local h, w = io.read("*n", "*n")

local function getindex(i_h, i_w)
  return i_w + (i_h - 1) * w
end

local map = {}
for i = 1, h * w do map[i] = 0 end
for i_h = 1, h do
  for i_w = 1, w do
    local idx = getindex(i_h, i_w)
    map[idx] = io.read("*n")
  end
end

local command = {}

for i_h = 1, h do
  local inc = i_h % 2 == 1 and 1 or -1
  local bg = i_h % 2 == 1 and 1 or w
  local ed = i_h % 2 == 1 and w or 1
  for i_w = bg, ed, inc do
    local src = getindex(i_h, i_w)
    if i_w == ed then
      if i_h ~= h then
        if map[src] % 2 == 1 then
          local dst = getindex(i_h + 1, i_w)
          local tmp = {i_h, i_w, i_h + 1, i_w}
          table.insert(command, tmp)
          map[src], map[dst] = map[src] - 1, map[dst] + 1
        end
      end
    else
      local dst = getindex(i_h, i_w + inc)
      if map[src] % 2 == 1 then
        local tmp = {i_h, i_w, i_h, i_w + inc}
        table.insert(command, tmp)
        map[src], map[dst] = map[src] - 1, map[dst] + 1
      end
    end
  end
end
print(#command)
for i = 1, #command do
  print(table.concat(command[i], " "))
end


Measured memory_bytes: 32888