akhauriyash/Code-Regression huggingface dataset:
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1

//{
#pragma GCC optimize ("O3","unroll-loops")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
#define hi cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define ins insert
#define aer(v) (v).erase((v).begin(),(v).end()) 

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

int h,w,n,px,py,dy[]={1,0,-1,0},dx[]={0,1,0,-1};
int f[111][111];
int d;

bool cango(int y,int x){
	return y>=0&&y<h&&x>=0&&x<w&&f[y][x]==0;
}

void walk(int cn,int v){
	if(v==0)return;
	f[py][px]=cn;
	/*bool test=cango(py+dy[d%4],px+dx[d%4]);
	cout<<test<<endl;
	rep(i,h+5){
		rep(j,w+5){
			cerr<<f[i][j];
		}
		cout<<endl;
	}
	cout<<endl;*/
	v--;
	if(cango(py+dy[d%4],px+dx[d%4])==0)d++;
	py+=dy[d%4];px+=dx[d%4];
	walk(cn,v);
}

main(){
	cin>>h>>w>>n;
	
	for(int c=1;c<n+1;c++){
		int a;
		cin>>a;
		walk(c,a);
		
	}
	rep(i,h){
		rep(j,w){
			cout<<f[i][j]<<(j+1==w?'\n':' ');
		}
	}
}


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

int main(){
  ll n;
  while(cin>>n,n){
    bool a[50][30]={};
    ll g[50]={};
    ll m;
    for(ll i=0;i<n;i++){
      cin>>m;
      for(ll j=0,x;j<m;j++){
	cin>>x,x--;
	a[i][x]=1;
	g[x]|=1LL<<i;
      }
    }

    ll ans=-1,f=1,c[50]={};
    
    for(ll i=0;i<30&&f;i++)

      for(ll j=0;j<n;j++){
	if(a[j][i])
	  for(ll k=0;k<n;k++)
	    if(a[k][i])c[j]|=c[k]|g[i];

	if(c[j]+1==(1LL<<n))f=0,ans=i+1;
      }
    cout<<ans<<endl;
  }
  return 0;
}

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

#define rep(i, n) for(int i=0; i<n; ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
#define ll long long int

int main(){
   int n, k;
   cin>>n>>k;
   int a[200000];
   rep(i, n) cin>>a[i];

   rep(l, k){
      int se[200000]={0};
      rep(i, n){
         int st=max(0, i-a[i]);
         int en=i+a[i]+1;
         se[st]+=1;
         if(en<n) se[en]-=1;
      }
      int b=0;
      rep(i, n){
         b+=se[i];
         a[i]=b;
      }

      bool allmax=true;
      rep(i, n) if(a[i]!=n) allmax=false;
      if(allmax) break;
   }

   rep(i, n) cout<<a[i]<<" ";
   cout << endl;
   return 0;
}


Measured memory_bytes: 5140
n = int(input())
a = list(map(int, input().split()))
b = [i for i in range(1,n+1)]
ab = dict(zip(a, b))
ab2 = sorted(ab.items())
m = []

for i in range(n):
    m.append(str(ab2[i][1]))
else:
    print(" ".join(m))

Measured memory_bytes: 32284
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include<deque>
#include <regex>
#include <list> 
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef long long ll;
const ll MOD = 1000000007;
ll getDigit(ll n) {
	ll cnt = 0;
	while (n != 0) {
		n /= 10;
		cnt++;
	}
	return cnt;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
typedef pair<double, long long> pair_t;
bool comp(const pair_t& a, const pair_t& b) {
	if (a.first == b.first)return  a.second > b.second;
	else {
		return a.first > b.first;
	}
}

int main() {
	ll a, b;
	ll cnt = 0;
	cin >> a >> b;
	while (!(floor(cnt*0.08) == a && floor(cnt*0.10) == b)) {
		if (floor(cnt * 0.08) > a && floor(cnt * 0.10) > b)return cout << -1 << endl,0;
		cnt++;
	}
	cout << cnt << endl;
}


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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

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

//ａをbで割る
long long mod_div(long long a,long long b){
	if(a % b == 0)return a/b;
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}

void mod_add(long long &a,long long &b){
	a += b;
	if(a >= MOD)a -= MOD;
}
 
ll mp[111111];
ll kaijo = 1,n;

int main(){

	int n;cin >> n;
	vector<ll> v(n);
	REP(i,n)cin >> v[i];
	ll ans = 0;
	
	for(int i = 1;i < 111111;i++)mp[i] = mod_div(1, 1+i);
	REP(i,111110)mod_add(mp[i+1],mp[i]);
	REP(i,n)kaijo *= (i+1),kaijo %= MOD;

	REP(i,n){
		ll tmp = (((1 + mp[i] + mp[n-1-i]) % MOD) * kaijo) % MOD;
		ans += (tmp * v[i]) % MOD;
		ans %= MOD;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1920
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
const int mod = 1000000007;
int main() {
	int H, W, K;
	cin >> H >> W >> K;
	vector<vector<int> > dp(H + 1, vector<int>(W, 0)); dp[0][0] = 1;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			for (int k = 0; k < 1 << (W - 1); ++k) {
				// Check if two horizontal lines are connecting
				// 2 つの横線がつながっていないか調べる
				bool ok = true;
				for (int l = 0; l < W - 2; ++l) {
					if (((k >> l) & 1) && ((k >> (l + 1)) & 1)) {
						ok = false;
					}
				}
				if (ok) {
					if (j >= 1 && ((k >> (j - 1)) & 1)) {
						// The case which goes left
						// 左方向に横線をたどるケース
						dp[i + 1][j - 1] += dp[i][j];
						dp[i + 1][j - 1] %= mod;
					}
					else if (j <= W - 2 && ((k >> j) & 1)) {
						// The case which goes right
						// 右方向に横線をたどるケース
						dp[i + 1][j + 1] += dp[i][j];
						dp[i + 1][j + 1] %= mod;
					}
					else {
						// The case which goes straight
						// 横線をたどらないケース
						dp[i + 1][j] += dp[i][j];
						dp[i + 1][j] %= mod;
					}
				}
			}
		}
	}
	cout << dp[H][K - 1] << '\n';
	return 0;
}

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

#define ll long long
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)

//library----------------------------------------------


int main(){
  int a,b; cin>>a>>b;
  if(a%2==1&&b%2==1){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 //10^9+7
#define INF 1000000000000 //10^12
#define F first
#define S second
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()
//library begin
int gcd(int a,int b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
int log(int a){
    int b=a;
    int cnt=0;
    while(b%2==0){
        b/=2;
        cnt++;
    }
    return cnt;
}
//library end
int n;
int a[400000];
int minv=INF;
int ans=0;
signed main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n){
        if(a[i]<minv){
            minv=a[i];
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int main()
{
	int n;
	cin >> n;
	vector<int> s(n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		sum += s[i];
	}
	sort(s.begin(), s.end());
	if (sum % 10 != 0) {
		cout << sum << endl;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		if (s[i] % 10 != 0) {
			cout << sum - s[i] << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	
	return 0;
}



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

const int N_MAX = 1005;
const int MOD = 1000000007;

int divin[N_MAX][N_MAX];

int main(){
    int n;
    scanf("%d", &n);

    for(int i = 2; i <= n; i++)divin[0][i] = 1;


    for(int i = 2; i <= n; i++){
        if (divin[0][i] == -1) continue;

        for(int k = 2 * i; k <= n; k += i) divin[0][k] = -1;
        for(int j = i; j <= n; j++){
            int copj = j;
            int sisu = 0;
            while(copj % i == 0){
                sisu++;
                copj /= i;
            }
            divin[j][i] = sisu;
        }
    }

    long long int ans = 1;
    for(int i = 2; i <= n; i++){
        if (divin[0][i] == -1) continue;
        int total = 0;
        for(int j = i; j <= n; j++) total += divin[j][i];
        ans *= total + 1;
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

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

int main(){
  int N;
  cin>>N;
  
  vector<int> dp(N+1,100000);
  dp.at(0)=0;
  for(int i=1;i<=N;i++){
    dp.at(i)=i;
  }
  int b=6;
  for(int i=b;i<=N;i*=b){
    for(int j=i;j<=N;j++){
      dp.at(j)=min(dp.at(j),dp.at(j-i)+1);
    }
  }
  int a=9;
  for(int i=1;i<=N;i*=a){
    for(int j=i;j<=N;j++){
      dp.at(j)=min(dp.at(j),dp.at(j-i)+1);
    }
  }
  
  cout<<dp.at(N)<<endl;
}

Measured memory_bytes: 640
n = int(input())
h = [int(_) for _ in input().split()]
dp = [0] * n
dp[1] = abs(h[0] - h[1])

for i in range(n - 2):
    dp[i + 2] = min(dp[i] + abs(h[i] - h[i + 2]),
                    dp[i + 1] + abs(h[i + 1] - h[i + 2]))

print(dp[n - 1])


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

#define ll long long
int n;
ll a[200], cnt = 0;
bool f = true;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i] % 2 != 0)
			f = false;
	}
	int i = 0;
	while(f){
		if(i < n && a[i] % 2 == 0){
			cnt++;
			a[i] /= 2;
			i++;
		}
		else if(i >= n)
			i = 0;
		else
			break;
	}
	cout<<cnt/n;
	return 0;
}

Measured memory_bytes: 256
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            sum += s;
            if(s % 10 != 0) pq.add(s);
        }
        while(sum % 10 == 0){
            if(pq.isEmpty()){
                sum = 0;
                break;
            }
            sum -= pq.poll();
        }

        System.out.println(sum);
        sc.close();
    }

}


Measured memory_bytes: 22868
// #include <boost/multiprecision/cpp_int.hpp>
// using boost::multiprecision::cpp_int;
#include <bits/stdc++.h>
using namespace std;
// ¯\_(ツ)_/¯
#define f first
#define s second
#define p push
#define mp make_pair
#define pb push_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(), v.end()
#define sz(x) ((int)(x).size())
#define endl " \n"
#define newl cout<<"\n"
#define MAXN 100005
#define MOD 1000000007LL
#define EPS 1e-13
#define INFI 1000000000             // 10^9
#define INFLL 1000000000000000000ll //10^18
// ¯\_(ツ)_/¯
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define vll vector<long long>
#define vvll vector<vll>
//vector<vector<int>> v(10, vector<int>(20,500)); 2d vector initialization. of 10 rows and 20 columns, with value 500.
#define pll pair<long long, long long>

#define fast_io()                   \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);

ll tc, n, m, k;


int main()
{
    fast_io();
#ifndef ONLINE_JUDGE
    //freopen("../input.txt", "r", stdin);
    //freopen("../output.txt", "w", stdout);
#endif

    cin>>n;
    vvll mat(n, vll(n, 0));
    rep(i, 0, n) rep(j, 0, n) cin>>mat[i][j];

    vll dp(1<<n, 0);
    dp[0] = 1;

    rep(mask, 0, (1<<n) -1) {
        ll k = __builtin_popcount(mask);
        rep(i, 0, n) {
            if(mat[k][i] && !(mask&(1<<i))) {
                ll compound_mask  = mask | (1<<i);
                dp[compound_mask] += dp[mask];
                dp[compound_mask] %= MOD;
            }
        }
    }
    cout<<(dp[(1<<n) -1]);

    return 0;
}

/*
2
4
0 1 0 1
5
0 0 1 0 0
*/

Measured memory_bytes: 16640
#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 <random>

using namespace std;

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

    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (auto &t : a) {
    	cin >> t;
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (auto t : a) {
    	if (t <= x) {
    		x -= t;
    		ans++;
    	}
    }
    if (ans == n && x > 0) ans--;
    cout << ans << endl;
}   


Measured memory_bytes: 256
import sys

input = sys.stdin.readline


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

    ans = 0
    for i, a in enumerate(A, start=1):
        if i % 2 == 1 and a % 2 == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;

vector<int> topological(vector<vector<int>> E)
{
    int n = (int)E.size();
    
    vector<int> C(n);
    for (int i=0; i<n; i++)
        for (int e: E[i])
            C[e]++;

    vector<int> V;
    vector<int> S;
    for (int i=0; i<n; i++)
        if (C[i]==0)
            S.push_back(i);

    while (!S.empty())
    {
        int v = S.back();
        S.pop_back();
        V.push_back(v);
        for (int e: E[v])
            if (--C[e]==0)
                S.push_back(e);
    }

    return (int)V.size()==n ? V : vector<int>();
}

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

    vector<vector<int>> E(N);
    for (int i=0; i<N+M-1; i++)
    {
        int A, B;
        cin>>A>>B;
        E[A-1].push_back(B-1);
    }

    vector<int> T = topological(E);

    vector<int> ans(N, -1);
    for (int i=0; i<N; i++)
        for (int e: E[T[i]])
            ans[e] = T[i];
    for (int a: ans)
        cout<<a+1<<endl;
}


Measured memory_bytes: 12540
#include <cstdio>
#include <cstring>

int singlehit(char *base, int score);
int homerun(char *base, int score);

int main(void)
{
    int number;
    scanf("%d", &number);
    
    char event[10];
    int out_num;
    char base[4];
    while (number != 0){
        int score = 0;
        for (int i = 0; i < 4; i++){
            base[i] = '0';
        }
        for (out_num = 0; out_num != 3;){
            scanf("%s", event);
            if (strcmp(event, "HIT") == 0){
                score = singlehit(base, score);
            }
            else if (strcmp(event, "HOMERUN") == 0){
                score = homerun(base, score);
            }
            else {
                out_num++;
            }
        }
        printf("%d\n", score);
        number--;
    }
    
    return (0);
}

int singlehit(char *base, int score)
{
    base[1]++;
    if (base[1] == '2'){
        base[2]++;
        base[1]--;
    }
    if (base[2] == '2'){
        base[3]++;
        base[2]--;
    }
    if (base[3] == '2'){
        score++;
        base[3]--;
    }
    
    return (score);
}

int homerun(char base[], int score)
{
    for (int i = 0; i < 4; i++){
        if (base[i] == '1'){
            score++;
            base[i] = '0';
        }
    }
    score++;
    return (score);
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>

using namespace std;

#define INF 1010001000
#define EPS 1e-10
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef pair<int, int> i_i;
typedef long long int llong;
typedef pair<llong, llong> ll_ll;
typedef struct edge {int f, t;}Edge;
typedef pair<i_i, string> era;


int main()
{
    int n, m;
    while(cin >> n >> m, n) {
        vector<era> data;
        rep(i, n) {
            era tmp;
            cin >> tmp.second >> tmp.first.second >> tmp.first.first;
            data.pb(tmp);
            if (tmp.first.second != 1) {
                tmp.first.first -= tmp.first.second - 1;
                tmp.first.second = 1;
                data.pb(tmp);
            }
        }
        sort(data.begin(), data.end());
        int pt = 1;
        for (int i = 1; i < data.size(); i++) {
            if (data[i-1] != data[i]) {
                data[pt++] = data[i];
            } else {
                data[pt] = data[i];
            }
        }
        rep(i, m) {
            int tmp;
            bool fl = false;
            cin >> tmp;
            if (pt != 1) {
                if (data[0].first.first == tmp) {
                    cout << data[0].second << " " 
                        << data[0].first.second << endl;
                    fl = true;
                } else {
                    for (int j = 1; j < pt; j++) {
                        if (data[j].first.first == tmp) {
                            cout << data[j].second << " " 
                                << data[j].first.second << endl;
                            fl = true;
                            break;
                        }
                        if (data[j-1].first.first <= tmp && 
                                tmp <= data[j].first.first) {  
                            if (data[j-1].second == data[j].second) {
                                cout << data[j].second << " ";
                                cout << data[j-1].first.second + tmp 
                                    - data[j-1].first.first << endl;
                            } else {
                                cout << "Unknown" << endl;
                            }
                            fl = true;
                            break;
                        }
                    }
                }
            } else {
                if (data[0].first.first == tmp) {
                    cout << data[0].second << " 1" << endl;
                    fl = true;
                }
            }
            if (!fl) {
                cout << "Unknown" << endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3184
#include <bits/stdc++.h>
#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 FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

const string a = "keyence";

int main() {
  string s;
  cin >> s;

  int n = s.length();
  rep(i, n - 6) {
    if (s.substr(i, 7) == a) {
      cout << "YES" << endl;
      return 0;
    }
  }
  FOR(i, 1, 7) {
    if (s.substr(0, i) + s.substr(n - 7 + i) == a) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;


  
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380


int d[20][20];
char m[20][21];
int h, w;

void dist(int x, int y, int n)
{
	if (d[y][x] <= n)return;
	chmin(d[y][x], n);

	if (0 < x && m[y][x - 1] == '.')dist(x - 1, y, n + 1);
	if (x < w - 1 && m[y][x + 1] == '.')dist(x + 1, y, n + 1);
	if (0 < y && m[y - 1][x] == '.')dist(x, y - 1, n + 1);
	if (y < h - 1 && m[y + 1][x] == '.')dist(x, y + 1, n + 1);
}

int main()
{
	cout << fixed << setprecision(10);
	cin >> h >> w;
	REP(i, h)
	{
		cin >> m[i];
	}
	int ans = 0;
	REP(y, h)
	{
		REP(x, w)
		{
			REP(y2, h)REP(x2, w)d[y2][x2] = INF;
			if (m[y][x] == '.')
			{
				dist(x, y, 0);
				REP(y2, h)REP(x2, w)
				{
					if (d[y2][x2] == INF)continue;
					chmax(ans, d[y2][x2]);
				}
			}
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n;
main()
{
	cin>>n;
	int cnt=0;
	for(;n--;)
	{
		long a;cin>>a;
		bool ok=0;
		for(long x=1;x*(x+1)*2<=a;x++)
		{
			if((a-x)%(2*x+1)<1)
			{
				ok=1;
				break;
			}
		}
		if(!ok)cnt++;
	}
	cout<<cnt<<endl;
}



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

int find(const string& word) {
  int count = 0;
  for (string::size_type pos = 0; (pos = word.find("AB", pos)) != string::npos; pos += 1) {
    ++count;
  }
  return count;
}

int main(){

	int N;
	cin >> N;
	string s[N];
	
	for(int i=0; i<N; i++)
		cin >> s[i];

  	int ans=0;
	int a=0, b=0, ba=0;
  	for(int i=0; i<N; i++){
		ans += find(s[i]);
      	if(s[i][0]=='B' && s[i][s[i].size()-1]=='A'){
        	a++; b++; ba++; 
        }
      	else if(s[i][0]=='B') b++;
      	else if(s[i][s[i].size()-1]=='A') a++;
    }
	ans += min(a, b);
  	if(max(a,b) == ba && ba!= 0) ans--;
  
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	long long A, B, C;
	cin >> A >> B >> C;
	if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) 
		cout << "0" << endl;
	else {
		cout << min(min(A * B, A * C), B * C) << endl;
	}return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<int ,P> P3;
typedef pair<P ,P> PP;
const ll MOD = ll(1e9+7);
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    int n, m, sum=0;
    cin >> n >> m;
    REP(i,m){
        int c;
        cin >> c;
        sum += c;
    }
    cout << (sum-1)/(n+1)+1 << endl;
    return 0;
}



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

int main() {
	int N, counter, counter2 = 0;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}
    for (int j = 0; j < 1; j = 0) {
		counter = 0;
	    for (int  i = 0; i < N; i++) {
		    if (A.at(i) % 2 == 0) {
				A.at(i) = A.at(i) / 2;
			}
			else {
				counter = 1;
			}
		}
		if (counter != 0) {
			break;
		}
	counter2++;
	}
	cout << counter2 << endl;
}	

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
const int dm = 1 << 20;
char dn[dm], * di = dn;
inline void putint(ll X) {
	if (!X) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	int keta = 0;
	char C[20];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}
void pakuri_sort(int N, int A[]) {
	const int b = 8;
	int tmp[100001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}
int A[100000];
ll B[100001];
int C[100001];
int MA[100001], MI[100001];
int saidai, k = 1;
ll kotae[100001];

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


	int N = getint();
	int k3 = 0;
	rep(i, N) {
		int a = getint();
		if (a > saidai) {
			MA[k] = a;
			MI[k] = i;
			B[k] += a - saidai;
			C[k++]++;
			saidai = a;
		}
		else A[k3++] = a;
	}
	if (k == 2) {
		rep(i, k3) B[1] += A[i];
		putint(B[1]);
		rep(i, N - 1) {
			*di++ = '0';
			*di++ = '\n';
		}
		fwrite_unlocked(dn, di - dn, 1, stdout);
		return 0;
	}
	pakuri_sort(k3, A);
	int k2 = 1;
	rep(i, k3) {
		while (MA[k2] < A[i]) k2++;
		B[k2] += A[i] - MA[k2 - 1];
		C[k2]++;
	}

	ll cnt = 0;
	for (int i = k - 1; i >= 1; i--) {
		kotae[MI[i]] = B[i] + (MA[i] - MA[i - 1]) * cnt;
		cnt += C[i];
	}

	rep(i, N) putint(kotae[i]);

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 5248
object Main extends App {
  val ha = scala.io.StdIn.readLine()
  val haArray = ha.split(" ").map(_.toInt).toVector
  val h = haArray(0)
  val a = haArray(1)

  val amari = h % a
  println(if(amari > 0) h/a + 1 else h/a)
}

Measured memory_bytes: 27304
#include <iostream>
using ll = long long;
using namespace std;

/* initialize */
int temp, n;
/* main */
int partition(int A[],int p,int r){
    int x = A[r];
    int i = p-1;
    for (int j = p; j < r; j++) {
        if (A[j] <= x){
            i++;
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    temp = A[i+1];
    A[i+1] = A[r];
    A[r] = temp;
    return i+1;
}

int main() {
    int q;
    cin >> n;
    int A[100000];
    for (int j = 0; j < n; ++j) {
        scanf("%d", &A[j]);
    }
    q = partition(A, 0, n-1);
    for (int k = 0; k < n; k++) {
        if(k) printf(" ");
        if (k == q) printf("[%d]", A[k]);
        else printf("%d", A[k]);
    }
    cout << "\n";
    return 0;
}


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

ll N, ans=0;
string str;

signed main(){
    cin >> N >> str;
    for(int i=0;i<str.size()-2;i++) {
        if(str[i]=='A'&&str[i+1]=='B'&&str[i+2]=='C') ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
 
using namespace std;
 
#define f(i,a,b) for(int i=a;i<b;i++)
#define fll(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define vvi vector<vector<int> >
#define ss second
#define ff first
#define ll long long
#define lld long double
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pq priority_queue< int >
#define pqll priority_queue< ll >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define INF 1000000000
#define NINF -1000000000
#define endl '\n'
 
// void print_vi(vi a){
//     for (int i: a){
//         cout << i << " " ;
//     }
//     cout << endl;
// }
 
void solve(){

    int n ;
    cin >> n;
    vector <double> dp(n+1);
    dp[0] = 1;
    for (int i = 0 ; i < n ; i++){
        double head;
        cin >> head;
        for (int j = i+1 ; j >= 0 ; j--){
            dp[j] = (j==0 ? 0 : dp[j-1]*head) + dp[j]*(1-head);
            // cout << dp[j] << " " << j << endl;
        }
    }
    double ans = 0;
    for (int heads = 0 ; heads <= n ; heads++){
        int tails = n - heads;
        if ( heads > tails ){
            ans += dp[heads];
        }
    }
    printf("%.10lf" , ans);
    
    // dp[i] = probability that there are i heads so far
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
 
 
    int t = 1;
    // cin >> t;
    
    while(t--){ 
        solve();
        cout << endl;
    }
}

Measured memory_bytes: 3880
#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const int N = 100000;

int vertexid[N];
int L[N], R[N];
int fl;
vector<int> graph[N];

void build(int v, int l, int r)
{
  L[v] = l, R[v] = r;
  if (l + 1 == r)
  {
    vertexid[v] = l;
    return;
  }
  int m = (l + r) / 2;
  vertexid[v] = fl++;
  build(2 * v + 1, l, m);
  build(2 * v + 2, m, r);
  graph[vertexid[v]].push_back(vertexid[2 * v + 1]);
  graph[vertexid[v]].push_back(vertexid[2 * v + 2]);
}

void connect(int from, int l, int r, int v)
{
  if (r <= L[v] || R[v] <= l) return;
  if (l <= L[v] && R[v] <= r)
  {
    graph[from].push_back(vertexid[v]);
    return;
  }
  connect(from, l, r, 2 * v + 1);
  connect(from, l, r, 2 * v + 2);
}

int main()
{
  int n, d;
  cin >> n >> d;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++)
  {
    cin >> x[i] >> y[i];
  }
  vector<pair<int, int> > f;
  for (int i = 0; i < n; i++)
  {
    f.push_back({y[i], 2 * i + 1});
    f.push_back({x[i], 2 * i});
  }
  vector<int> pos(2 * n);
  sort(f.begin(), f.end());
  for (int i = 0; i < 2 * n; i++)
  {
    pos[f[i].second] = i;
  }
  fl = 2 * n;
  build(0, 0, 2 * n);
  for (int i = 0; i < 2 * n; i++)
  {
    int c = x[f[i].second / 2] + y[f[i].second / 2] - f[i].first;
    int mirror = pos[f[i].second ^ 1];
    int L = 0;
    while (f[L].first <= c - d) L++;
    int R = 2 * n - 1;
    while (f[R].first >= c + d) R--;
    if (L <= mirror - 1)
    {
      connect(i, L, mirror, 0);
    }
    if (mirror + 1 <= R)
    {
      connect(i, mirror + 1, R + 1, 0);
    }
  }
  scc_graph G(fl);
  for (int i = 0; i < fl; i++)
  {
    for (auto u : graph[i])
    {
      G.add_edge(i, u);
    }
  }
  vector<vector<int> > scc = G.scc();
  vector<int> wh(fl);
  for (int i = 0; i < scc.size(); i++)
  {
    for (int j = 0; j < scc[i].size(); j++)
    {
      wh[scc[i][j]] = i;
    }
  }
  vector<int> ans(n);
  for (int i = 0; i < n; i++)
  {
    if (wh[pos[2 * i]] == wh[pos[2 * i + 1]])
    {
      cout << "No\n";
      return 0;
    }
    ans[i] = wh[pos[2 * i]] > wh[pos[2 * i + 1]];
  }
  cout << "Yes\n";
  for (int i = 0; i < n; i++)
  {
    if (ans[i]) cout << y[i] << "\n";
    else cout << x[i] << "\n";
  }
}

Measured memory_bytes: 6468
#include<bits/stdc++.h>
using namespace std;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V))

vector<string> split(string,string);

//template<typename T>
//void swap(T*,T*);
//char ToUpper (char cX) { return toupper(cX); }

int main()
{
    int N;
    cin >> N;
    int w = N*N;
    int A;
    cin >> A;
    cout << w - A;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2> void sortTwoVecter(vector<T1> &f, vector<T2> &s, bool isReverse = false){
    vector<pair<T1, T2>> p;
    rep(i, f.size()) p.emplace_back(make_pair(f[i], s[i]));
    if (!isReverse) sort(p.begin(), p.end());
    else sort(p.rbegin(), p.rend());
    rep(i, f.size()) tie(f[i], s[i]) = p[i];
    return;
}

int main(){
    string al = "abcdefghijklmnopqrstuvwxyz";
    ll N; cin >> N;
    vector<string> s(N);
    rep(i, N) cin >> s[i];
    map<char, ll> d;
    rep(i, 26){
        d[al[i]] = INF;
        rep(j, N){
            ll cnt = 0;
            rep(k, s[j].size()){
                if (s[j][k] == al[i]) cnt++;
            }
            chmin(d[al[i]], cnt);
        }
        if (d[al[i]] == INF) d[al[i]] = 0;
    }
    string ans = "";
    eachdo(d, e){
        rep(i, e.second) ans += e.first;
    }
    pt(ans);
 
}

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

using namespace std;

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

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

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

ll R, G, B, N;

int main() {
    cin >> R >> G >> B >> N;
    ll ans = 0;
    REP(i, N / R + 1) REP(j, (N - i * R) / G + 1) {
        if((N - i * R - j * G) % B == 0) {
            // cout << i << " " << j << " " << (N - i * R - j * G) % B << "\n";
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}


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

int gcd(int x, int y) {
  while (y > 0) {
    int c = x;
    x = y;
    y = c % y;
  }
  return x;
}

int main() {
  int n, x; cin >> n >> x;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    int xi; cin >> xi;
    arr[i] = abs(xi - x);
  }

  int total_gcd = arr[0];
  for (int a: arr) {
    total_gcd = gcd(total_gcd, a);
  }
  cout << total_gcd << endl;
}


Measured memory_bytes: 640
sub nCk{my($n,$k)=@_;
my$r=1;
	$r*=$n+1-$_,$r/=$_ for 1..$k;
	$r
}
($N,$A,$B)=glob<>;
@v=sort{$b<=>$a}glob<>;
$s+=$_ for@v[0..$A-1];
$l=$r=$A-1;
$l--while$l-1>=0&&$v[$l-1]==$v[$A-1];
$r++while$r+1<$N&&$v[$r+1]==$v[$A-1];
$p+=nCk($r-$l+1,$_-$l)for$A..($l?$A:$B);
printf"%f\n%d",$s/$A,$p


Measured memory_bytes: 768
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <random>
#include <stack>
#include <iomanip>

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

using Int = unsigned int;
using llong = long long;
using Llong = unsigned long long;
using ldouble = long double;
using intV = vector<int>;
using llongV = vector<long long>;
using llongVV = vector<vector<long long>>;
using Graph = vector<vector<long long>>;
using costGraph = vector<vector<pair<long long, long long>>>;

const llong INF = 1e17;

#define FOR(i, n) for (llong i = 0LL; i < llong(n); i++)
#define FORS(i, a, b) for (llong i = llong(a); i < llong(b); i++)

// 0-indexed, [l, r)
class SegmentTree {
    public :
        llongV __data;
        llong __size;

        SegmentTree (llong size) {
            this->init(size);
        };

        void init (llong size) {
            // 完全二分木にする
            llong binSize = 0;
            while((1 << binSize) < size) {
                binSize++;
            }
            this->__size = (1 << binSize);

            this->__data.resize(this->__size * 2);
            for(llong i = 0; i < this->__size * 2; i++) {
                this->__data[i] = INF;
            }
        };

        /* メソッド */
        void update(llong index, llong value) {
            index += this->__size - 1;
            this->__data[index] = value;
            while(index > 0) {
                index = (index - 1) / 2;
                this->__data[index] = min(this->__data[index * 2 + 1], this->__data[index * 2 + 2]);
            }
        };

        llong __query(llong qLeft, llong qRight, llong node, llong left, llong right) {
            if(right <= qLeft || qRight <= left) return INF;
            if(qLeft <= left && right <= qRight) return this->__data[node];

            llong leftVal = this->__query(qLeft, qRight, node * 2 + 1, left, (left + right) / 2);
            llong rightVal = this->__query(qLeft, qRight, node * 2 + 2, (left + right) / 2, right);
            return min(leftVal, rightVal);
        }

        // wrapper
        llong query(llong left, llong right) {
            return this->__query(left, right, 0, 0, this->__size);
        };
};

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

    llong N, M;
    cin >> N >> M;

    SegmentTree tree(N + 1);
    tree.update(1, 0);
    vector<tuple<llong, llong, llong>> edges(M);

    FOR(i, M) cin >> get<0>(edges[i]) >> get<1>(edges[i]) >> get<2>(edges[i]);
    sort(edges.begin(), edges.end());

    FOR(i, 2) {
        for(auto a : edges) {
            llong L, R, C;
            tie(L, R, C) = a;
            llong cost = tree.query(L, R + 1) + C;
            tree.update(R, min(cost, tree.query(R, R + 1)));
        }
    }

    llong ans = tree.query(N, N + 1);
    if(ans == INF) ans = -1;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <random>
#include <cstdint>
#include <bitset>
#include <iomanip>
#include <utility>
#include<map>
#include<functional>
#include<climits>
using namespace std;
using ll = long long;
const int mod = 1000000007;

int main() {
	int n, l[10],sum=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> l[i];
		sum += l[i];
	}
	bool ans = true;
	for (int i = 0; i < n; i++) {
		if (sum - l[i] <= l[i])ans = false;
	}
	if (ans)cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
int main(){
	while (true) {
		int n; std::cin >> n; if (n == 0) return 0;
		std::string order; std::cin >> order;
		std::vector<int> state(n + 1, 0);
		std::vector<std::vector<int>> locking_thread(10);
		for (auto i = 0; i < n; ++i) {
			if (order[i] != 'u') {
				for (auto m = 0; m < 10; ++m) {
					if ((state[i] & (1 << m)) != 0) locking_thread[m].push_back(i);
				}
				state[i + 1] = state[i] | (1 << (order[i] - '0'));
			}
		}
		std::vector<std::vector<bool>> memo(n, std::vector<bool>(1 << 10, false));
		auto has_dead_lock = false;
		std::queue<std::pair<int, int>> queue;
		for (auto i = 0; i < n && !has_dead_lock; ++i) if (order[i] != 'u') {
			queue.emplace(i, state[i]);
			memo[i][state[i]] = true;
			while (!queue.empty()) {
				auto front = queue.front(); queue.pop();
				if ((front.second & (1 << (order[front.first] - '0'))) != 0) {
					has_dead_lock = true;
					break;
				}
				for (const auto other : locking_thread[order[front.first] - '0']) {
					if ((front.second & state[other]) == 0 && !memo[other][front.second | state[other]]) {
						memo[other][front.second | state[other]] = true;
						queue.emplace(other, front.second | state[other]);
					}
				}
			}
		}
		if (has_dead_lock) std::cout << "UNSAFE" << std::endl;
		else std::cout << "SAFE" << std::endl;
	}
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

pair<int, int> A[300*300+100];
int main(){
    int H,W,D;
    cin >> H >> W >> D;
    REP(i,H){
        REP(j,W){
            int a;
            cin >> a;
            A[a] = make_pair(i,j);
        }
    }

    vector<vector<int> > X(D+1);
    for(int d = 1; d <= D; d++){
        int lastx;
        int lasty;
        int lastc;
        for(int t = d; t <= H*W; t += D){
            int x = A[t].first;
            int y = A[t].second;
            int cost = 0;
            if(t != d){
                cost = abs(x-lastx) + abs(y-lasty);
                cost += lastc;
            }
            lastx = x;
            lasty = y;
            lastc = cost;
            X[d].push_back(cost);
        }
    }

    int Q;
    cin >> Q;
    REP(i,Q){
        int l, r;
        cin >> l >> r;
        int idxh = (r-(r%D))/D;
        int idxl = (l-(l%D))/D;
        if(l%D==0) idxl--, idxh--;
        int s = (l%D==0) ? D : l%D;
        ll ans = X[s][idxh] - X[s][idxl];
        cout << ans << endl;
    }
    return 0;
}


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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int x,n; cin >> x >> n;
	vector<bool>a(201,1); 
	int mn = 100001;
	int m;
	for(int i=0; i<n; i++){
		cin >> m;
		a[m]=0;
	}
	int ptr = 100;
	for(int i=-3; i<=0; i++){
		if(mn>abs(x-i)){
			mn = abs(x-i);
			ptr = i;
		}
	}
	for(int i=1; i<=200; i++){
		if(a[i]){
			if(mn>abs(x-i)){
				mn = abs(x-i);
				ptr = i;
			}
		}
	}
	cout << ptr << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 3604