akhauriyash/Code-Regression huggingface dataset:
# Range Sum Query
# https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B
"""
Binary Indexed Tree (Fenwick Tree)

References:
    http://hos.ac/slides/20140319_bit.pdf

Verified:
    https://judge.yosupo.jp/problem/point_add_range_sum
    https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b
"""
from typing import Optional, Sequence


class BinaryIndexedTree:
    __slots__ = ["_size", "_tree", "_is_zero_indexed"]

    def __init__(self, size: int, initial_values: Optional[Sequence[int]] = None, is_zero_indexed: bool = True):
        self._size = size
        self._tree = [0] * (self._size + 1)
        self._is_zero_indexed = is_zero_indexed
        if initial_values:
            self._build(initial_values)

    def _build(self, initial_values: Sequence[int]):
        for i, a in enumerate(initial_values):
            self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self._is_zero_indexed:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index], O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right], O(logN)."""
        if not self._is_zero_indexed:
            left -= 1
        return self.sum(right) - self.sum(left)


def main():
    N, Q, *queries = map(int, open(0).read().split())
    tree = BinaryIndexedTree(N, is_zero_indexed=False)
    result = []
    for com, x, y in zip(*[iter(queries)] * 3):
        if com:
            result.append(tree.range_sum(x, y))
        else:
            tree.add(x, y)
    print(*result, sep="\n")


if __name__ == "__main__":
    main()



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

using namespace std;

int main()
{
    int A,B,C,D,area1,area2;
    scanf("%d%d%d%d",&A,&B,&C,&D);
    area1=A*B;
    area2=C*D;
    if(area1>area2)
    {
        printf("%d",area1);
    }
    else if(area1<area2)
    {
        printf("%d",area2);
    }
    else
    {
        printf("%d",area1);
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int box[1000];
	int i;
	int n,q;
	int d,a,b;
	int cnt;
	cin>>n;
	for(i=0;i<n;i++)	cin>>box[i];
	cin>>q;
	for(i=0;i<q;i++){
		cin>>a>>b>>d;
		cnt=count(box+a,box+b,d);
		cout<<cnt<<endl;
	}
	return 0;
}



Measured memory_bytes: 3124
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define nn '\n'
#define YES {cout<<"YES"<<'\n';}
#define NO {cout<<"NO"<<'\n';}
#define Yes {cout<<"Yes"<<'\n';}
#define No {cout<<"No"<<'\n';}
#define yes {cout<<"yes"<<'\n';}
#define no {cout<<"no"<<'\n';}
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) {cout << n << '\n';}
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int a; cin >> a;
    int l = a/100;
    int r = a%100;
    if(1<=l&&l<=12){
        if(1<=r&&r<=12){out("AMBIGUOUS");}
        else out("MMYY");
    }else{
        if(1<=r&&r<=12){out("YYMM");}
        else out("NA");
    }

    return 0;
}

Measured memory_bytes: 256
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(ll)(n);++i)
#define _repe3(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define _rrepe2(i,n) for(ll i=(ll)(n);i>=0;i--)
#define _rrepe3(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)
#define rrepe(...) _overload3(__VA_ARGS__,_rrepe3,_rrepe2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
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(b<a){a=b;return 1;}return 0;}

ll L;
ll R;
ll d;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> L;
    cin >> R;
    cin >> d;
    solve();
}

// 与えられる入力は全て整数
// 1 <= L <= R <= 100
// 1 <= d <= 100

// ll L, ll R, ll d
// L 以上 R 以下の整数のうち、d の倍数であるような整数の個数を出力せよ。
void solve(){
    ll ans=0;
    repe(i,L,R){
        if(i%d==0)ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3620
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define PI acos(-1)
#define Mod (int)1000000007
#define INFTY (int)INT_MAX
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Count(vec, x) count(vec.begin(), vec.end(), x)
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define Find(S, s) S.find(s) != string::npos

int main() {
	int q;
	cin >> q;
	deque<int> D;
	Rep(i, q) {
		int n;
		cin >> n;
		if (n == 0) {
			int d, x;
			cin >> d >> x;
			if (d == 0) {
				D.push_front(x);
			}
			else if (d == 1) {
				D.push_back(x);
			}
		}
		else if (n == 1) {
			int i;
			cin >> i;
			cout << D[i] << endl;
		}
		else if (n == 2) {
			int d;
			cin >> d;
			if (d == 0) {
				D.pop_front();
			}
			else if (d == 1) {
				D.pop_back();
			}
		}
	}
	return 0;
}


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

using namespace std;

#define ll long long
#define PI 3.14159265358979323846264338327950L

int n;
pair<int,int> a[1000001];
pair<int,int> sub[1000001];
pair<int,int>nsub[1000001];
string s;

void solve(){

    cin >> n;

    int insub = 0;
    int ninsub = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> s;

        a[i].first = 0;
        a[i].second = 0;

        bool leftc = true;
        int right = 0;
        for(char c: s){
            if(leftc){
                if(c == ')'){
                    a[i].first++;
                } 
                else{
                    leftc = false;
                    right++;
                }
            }
            else{
                if(c == ')'){
                    right--;
                } 
                else right++;

                if(right == 0){
                    leftc = true;
                } 
            }
        }
        a[i].second = right;

        int tmp = a[i].second-a[i].first;
        if(tmp > 0){
            sub[insub].first = a[i].first;
            sub[insub].second = a[i].second;
            insub++;
        }
        else{
            nsub[ninsub].first = a[i].first;
            nsub[ninsub].second = a[i].second;
            ninsub++;
        }
    }
    
    sort(sub,sub+insub, [](auto &left, auto &right) {
        return left.first < right.first;
    });

    sort(nsub,nsub+ninsub, [](auto &left, auto &right) {
        return left.second > right.second;
    });

    int ans = 0;
    for (int i = 0; i < insub; i++)
    {
        //cout << a[i].first << " " << a[i].second << endl;
        ans -= sub[i].first;
        if(ans <0){
            cout << "No" << endl;
            return;
        }
        ans+= sub[i].second;
    }
    for (int i = 0; i < ninsub; i++)
    {
        ans -= nsub[i].first;
        if(ans <0){
            cout << "No" << endl;
            return;
        }
        ans+= nsub[i].second;
    }
    
    
    if(ans == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No"<< endl;
    }

}





int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Measured memory_bytes: 19104
#include<iostream>
#include<algorithm>
using namespace std;
int main (void)
{

  int a,b,ans;
  cin>>a;
  if(a==1){cout<<"1.000000000"<<endl;}
  else if(a%2==0)cout<<"0.5000000000"<<endl;
  else
  {
    b=a/2+1;
 
    b=b*10000000;
    ans=b/a;
    
    
  
 
   cout<<"0."<<ans;
    
    
  }
}

Measured memory_bytes: 3604
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

DATA DIVISION.
WORKING-STORAGE SECTION.
01 ln         PIC X(30).
01 K          PIC S9(10).
01 X          PIC S9(10).
01 i          PIC S9(10).
01 nl         PIC 9(10) VALUE ZERO.
01 sp         PIC 9(10) VALUE ZERO.
01 st         PIC S9(10).
01 ed         PIC S9(10).
01 ans        PIC X(30).
01 zs         PIC -Z(9)9.

PROCEDURE DIVISION.
  ACCEPT ln.
  UNSTRING ln DELIMITED BY SPACE INTO K X.
  COMPUTE st = X - K + 1.
  COMPUTE ed = X + K - 1.
  MOVE st TO i.
  IF K = 1
    MOVE 1 TO nl
    PERFORM DISP
    STOP RUN
  ELSE
    PERFORM DISP
  END-IF.
  MOVE 1 TO sp.
  ADD 1 TO st.
  PERFORM VARYING i FROM st BY 1 UNTIL ed <= i
    PERFORM DISP
  END-PERFORM.
  MOVE 1 TO nl.
  PERFORM DISP.
  STOP RUN.

DISP SECTION.
    MOVE i TO zs.
    IF ZERO <> sp
      DISPLAY SPACE WITH NO ADVANCING
    END-IF.
    IF ZERO <> i
      IF ZERO <> nl
        DISPLAY FUNCTION TRIM(zs)
      ELSE
        DISPLAY FUNCTION TRIM(zs) WITH NO ADVANCING
      END-IF
    ELSE
      IF ZERO <> nl
        DISPLAY ZERO
      ELSE
        DISPLAY ZERO WITH NO ADVANCING
      END-IF
    END-IF.


Measured memory_bytes: 3760
#include <stdio.h>

int main(void){
  int n;
  scanf("%d", &n);
  double odd, even;
  if(n % 2 == 0) printf("%f\n", 1.0/2.0);
  if(n % 2 != 0){
    odd = (n+1) / 2;
    printf("%f\n", odd / n);
  }
  
  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
int dp1[160][160];
int rev[160][160];
int dp2[160][160];
int g[160][160];
int dp3[160][160];
int sg[160][160];
int cost[310][160];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)for(int j=0;j<a;j++){
		g[i][j]=-99999999;
	}
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		if(!~g[p][q]||g[p][q]<r){
			g[p][q]=r;
		}
	}
	for(int i=0;i<160;i++)for(int j=0;j<160;j++){
		dp1[i][j]=dp2[i][j]=-999999999;
	}
	for(int i=0;i<a;i++)dp1[0][i]=dp2[0][i]=0;
	for(int i=0;i<155;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<a;k++){
				if(dp1[i][j]>=0){
					if(dp1[i+1][k]<dp1[i][j]+g[j][k]){
						dp1[i+1][k]=dp1[i][j]+g[j][k];
						rev[i+1][k]=j;
					}
				}
				if(dp2[i][j]>=0){
					dp2[i+1][k]=max(dp2[i+1][k],dp2[i][j]+g[k][j]);
				}
			}
		}
	}
	for(int i=1;i<=100;i++){
		int ms=0;
		int at=0;
		for(int j=0;j<a;j++){
			if(ms<dp1[i][j]){
				ms=dp1[i][j];
				at=j;
			}
		}
		if(ms>=c){
			printf("%d\n",i);
			stack<int>S;
			for(int j=i;j>=0;j--){
				S.push(at);
				at=rev[j][at];
			}
			for(int j=0;j<=i;j++){
				if(j)printf(" ");
				printf("%d",S.top());
				S.pop();
			}
			printf("\n");
			return 0;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<160;j++)for(int k=0;k<160;k++)sg[j][k]=-999999999;
		sg[0][i]=0;
		for(int j=0;j<a;j++){
			for(int k=0;k<a;k++){
				if(sg[j][k]<0)continue;
				for(int l=0;l<a;l++){
					sg[j+1][l]=max(sg[j+1][l],sg[j][k]+g[k][l]);
				}
			}
		}
		for(int j=0;j<=a;j++)dp3[i][j]=sg[j][i];
	}
	int ret=99999999;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<a;k++){
				for(int l=0;l<=a;l++){
					int t=dp1[i][j]+dp2[k][j];
					if(c<=t){
						ret=min(ret,i+k);
						continue;
					}
					if(dp3[j][l]<=0)continue;
					ret=min(ret,i+k+((c-t)+dp3[j][l]-1)/dp3[j][l]*l);
				}
			}
		}
	}
	if(ret>9999999){
		ret=-1;
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 1636
fun main(arg: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map(String::toInt)
    val po = readLine()!!.split(' ').map(String::toInt)
    val score = (0..k).map { left ->
        (0..Math.min(k - left, n - left)).map { right ->
            val meu = (po.take(left) + po.drop(n - right)).sorted()
            val minus = meu.take(k - left - right).takeWhile { it < 0 }
            meu.sum() - minus.sum()
        }.max() ?: 0
    }.max() ?: 0
    println(score)
}


Measured memory_bytes: 41416
#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a=n%10;
    if(a==2||a==5||a==7||a==9||a==4)
    printf("hon");
    if(a==0||a==1||a==6||a==8)
    printf("pon");
    if(a==3)
    printf("bon");
}


Measured memory_bytes: 1732
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
    long long W, H, x, y;
    while(cin >> W >> H >> x >> y){
        printf("%.9lf %d\n", 0.5*W*H, (2*x == W && 2*y == H ? 1 : 0));
    }   
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;

void file_put() {
    freopen("filename.in", "r", stdin);
    freopen("filename.out", "w", stdout);
}

ll s,x[4],y[4],t;

int main() {
//	file_put();
	
	scanf("%lld",&s);
	for (t=(ll)sqrt(s); t*t<s; t++);
	x[3]=t*t-s,y[2]=1;
	x[2]=y[3]=t;
	rep(i,1,4) printf("%lld %lld ",x[i],y[i]);
	printf("\n"); 
	
	return 0;
}



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

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) cerr << #x << " "; for (auto & el : (x)) {cerr << (el) << " ";} cerr << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define debug(x)
#define itrdebug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

bool overflowAdd(ll a, ll b) {
    return LLONG_MAX - b < a;
}

bool overflowProduct(ll a, ll b) {
    if (a == 0 || b == 0) return false;
    return a > LLONG_MAX / b;
}

ll dfs(ll N, ll A, ll B, ll C, ll D, unordered_map<ll, ll>& memo) {
    if (memo.find(N) != memo.end()) return memo[N];
    ll cost = LLONG_MAX;
    vector<pair<ll, ll>> pairList{{2, A}, {3, B}, {5, C}};
    for (const auto& p : pairList) {
        for (const ll diff : {1, -1}) {
            ll n = N;
            while (n % p.first != 0) n += diff;
            if (n / p.first >= N) continue;
            ll newCost = abs(N-n) * D + p.second;
            if (overflowAdd(newCost, dfs(n/p.first, A, B, C, D, memo))) continue;
            newCost += dfs(n/p.first, A, B, C, D, memo);
            cost = min(cost, newCost);
        }
    }
    if (!overflowProduct(N, D)) {
        cost = min(cost, N*D);
    }
    memo[N] = cost;
    return cost;
}

signed main(){
    int T;
    cin >> T;
    rep(ti,0,T) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;
        unordered_map<ll, ll> memo;
        memo[0] = 0; memo[1] = D;
        cout << dfs(N, A, B, C, D, memo) << endl;
    }
    return 0;
}


Measured memory_bytes: 4112
import sys
import numpy as np
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    connect_to_1_set = set([])
    connect_to_N_set = set([])
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        if a == 1:
            connect_to_1_set.add(b)
        elif b == 1:
            connect_to_1_set.add(a)

        if a == N:
            connect_to_N_set.add(b)
        elif b == N:
            connect_to_N_set.add(a)

    if len(connect_to_1_set & connect_to_N_set) == 0:
        print "IMPOSSIBLE"
    else:
        print "POSSIBLE"



if __name__ == '__main__':
    main()

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

int main(void)
{
    int x[5];
    int ans;
    for (int i = 0; i < 5; i++)
    {
        cin >> x[i];
        if(x[i]==0)
        {
            ans = i + 1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3552
N,M = map(int, input().split())

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

set1=set()
set2=set()

for tmp in S:
    if tmp[0]==1:
        set1.add(tmp[1])
    if tmp[1]==N:
        set2.add(tmp[0])

if len(set1&set2) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Measured memory_bytes: 58916
#include <bits/stdc++.h>
#define mod 1000000007
#define int long long
using namespace std;
const int N=2*1e5+100;
int n,k,fac[N*2],inv[N*2];
int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int C(int n,int m)
{
	return (fac[n]*inv[m]%mod)*inv[n-m]%mod;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	fac[1]=1;
	for (int i=2;i<=2*n;i++) fac[i]=(fac[i-1]*i)%mod;
	inv[2*n]=m_pow(fac[2*n],mod-2);
	for (int i=2*n-1;i>=1;i--) inv[i]=(i+1)*inv[i+1]%mod;
	if (k>=n-1)
	{
		printf("%lld\n",C(2*n-1,n-1));
		return 0;
	}
	else
	{
		int ans=1;
		for (int i=1;i<=k;i++)
		  ans=(ans+C(n-1,n-i-1)*C(n,i)%mod)%mod;
		printf("%lld\n",ans);
	}
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int n;
vector<int> a;
int dp[500001];

int f(int i){
	if(i==n-1){
		return 0;
	}
	if(dp[i]!=-1) return dp[i];

	dp[i] = INT_MAX;
	if(i+2 < n){
		dp[i] = f(i+2)+abs(a[i+2]-a[i]);
	}
	dp[i] = min(dp[i],f(i+1)+abs(a[i+1]-a[i]));
	return dp[i];
}

int main(){
	cin>>n;
	memset(dp,-1,sizeof(dp));
	a.resize(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cout<<f(0)<<endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, t[50];
string s[50], x;
int ans;
bool bl = false;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> s[i] >> t[i];
	cin >> x;
	for (int i = 0; i < n; i++) {
		if (bl)ans += t[i];
		if (s[i] == x)bl = true;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
//  LINK ZADATKA: http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_b

#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <complex>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>

using namespace std;

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;

#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define INF 999999999
#define INFLONG 1000000000000000000
#define MOD 1000000007
#define MAX 100
#define ITERS 100
#define MAXM 200000
#define MAXN 1000000
#define _gcd __gcd
#define eps 1e-9

vector<ll> v, polje;

ll n, m, sol;
int main(){

	slld(n);

	ll a;
	REP(i, n){
		slld(a);
		v.PB(a);	
	}
	
	slld(m);	
	
	REP(i, m) {
		slld(a);
		polje.PB(a);
	}
		
	sort(v.begin(), v.end());
	sort(polje.begin(), polje.end());
	int point = 0;
	
	REP(i, polje.size()){
		while(v[point] < polje[i]) point++;
		if(v[point] == polje[i]) sol++;			
		else break;
		point++;
	}
	if(sol == m) printf("YES\n");
	else printf("NO\n");
	return 0;
}


Measured memory_bytes: 4848
#include <algorithm>
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

#define M_PI 3.14159265358979
#define deg_to_rad(deg) (((deg)/360)*2*M_PI)

int main()
{
	long double A, B, H, M;
	long double hx, hy, mx, my;
	long double ret = 0;

	cin >> A >> B >> H >> M;

	hx = cos(deg_to_rad(360 / 12.0 * ((long double)H + (long double)M/60.0))) * A;
	hy = sin(deg_to_rad(360 / 12.0 * ((long double)H + (long double)M/60.0))) * A;
	mx = cos(deg_to_rad(360 / 60.0 * (long double)M)) * B;
	my = sin(deg_to_rad(360 / 60.0 * (long double)M)) * B;
	ret = sqrt((hx - mx)*(hx - mx) + (hy - my)*(hy - my));

	printf("%20.20Lf\n", ret);

	return 0;
}

Measured memory_bytes: 4132
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := makeWordScanner()
	h := eGetInt(scanner)
	a := eGetInt(scanner)
	count := 0
	for h > 0 {
		h = h - a
		count++
	}
	fmt.Println(count)
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeCharScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanRunes)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func pow(a, n int) int {
	return int(math.Pow(float64(a), float64(n)))
}
func countBitOfOn(i, numbits int) int {
	count := 0
	var bit uint64
	for bit = 0; bit < uint64(numbits); bit++ {
		t := 1 << bit
		if i&t > 0 {
			count++
		}
	}
	return count
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

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

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

struct edge{int to,cost;};
	
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);

	string s;
	cin >> s;

	int len=s.size(),head;
	ll ans=0;
	ll tmp;
	ll bit;
	for(int i=0;i<(1<<len-1);i++){
		bit = i|(1LL<<len-1);
		head=0;
//		printf("--------%d--------\n",i);
		for(int j=0;j<len;j++){
			if((bit>>j) & 1){
				
				ans += stoll(s.substr(head,j+1-head));
				
//				printf("head:%d  j:%d\n",head,j);
//				printf("%dから%d個    %d\n",head,j+1-head,atoi(s.substr(head,j+1-head).c_str()));
				head=j+1;
			}
		}
	}
	cout << ans << "\n";
	
	return 0;
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<P> v(m);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        v[i] = P(b, a);
    }
    sort(v.begin(), v.end());
    int ans = 0;
    v.emplace_back(1e8, 1e8);
    int cur = v[0].first;
    rep(i, m+1) {
        if (cur > v[i].second) continue;
        else {
            ans++;
            cur = v[i].first;
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main(){
    int A[9];
    while(cin >> A[0]){
        for(int i=1;i<9;i++) cin >> A[i];
        int N; cin >> N;
        for(int i=0;i<N;i++){
            int b; cin >> b;
            for(auto& t : A) if(t == b) t = 0;
        }
        bool ok = false;
        for(int i=0;i<3;i++){
            bool b = true;
            for(int j=0;j<3;j++){
                if(A[3*i+j]) b = false;
            }
            if(b) ok = true;
        }
        for(int i=0;i<3;i++){
            bool b = true;
            for(int j=0;j<3;j++){
                if(A[3*j+i]) b = false;
            }
            if(b) ok = true;
        }
        for(int i=0;i<1;i++){
            bool b = true;
            for(int j=0;j<3;j++){
                if(A[4*j]) b = false;
            }
            if(b) ok = true;
        }
        for(int i=2;i<3;i++){
            bool b = true;
            for(int j=0;j<3;j++){
                if(A[2*j+i]) b = false;
            }
            if(b) ok = true;
        }
        cout << (ok ? "Yes" : "No") << endl;
    }
}

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

int L;

int query(string S) {
    static int cnt_query = 0;
    assert(cnt_query++ < 800);
    cout << "? " << S << endl;
    int ans;
    cin >> ans;
    return ans;
}

bool is_subsequence(string S) {
    int ans = query(S);
    return ans + (int)S.size() == L;
}

int main() {
    string alphabet = "";
    for (int i = 0; i < 26; i++) alphabet += 'a'+i;
    for (int i = 0; i < 26; i++) alphabet += 'A'+i;
    for (int i = 0; i < 10; i++) alphabet += '0'+i;

    L = 0;
    vector<string> sub(alphabet.size());
    for (int i = 0; i < (int)alphabet.size(); i++) {
        int c = query(string(128, alphabet[i]));
        c = 128-c;
        L += c;
        sub[i] = "";
        for (int j = 0; j < c; j++) sub[i] += alphabet[i];
    }
    while (sub.size() >= 2) {
        sort(sub.begin(), sub.end(), [&](string A, string B) { return A.size() > B.size(); });
        if (sub.back().empty()) {
            sub.pop_back();
            continue;
        }
        string X = sub.back();
        string Y = sub[sub.size()-2];
        sub.pop_back();
        sub.pop_back();
        string XY;

        while (!X.empty() and !Y.empty()) {
            string S = XY + Y[0] + X;
            if (is_subsequence(S)) {
                XY += Y[0];
                Y.erase(Y.begin());
            } else {
                XY += X[0];
                X.erase(X.begin());
            }
        }
        XY += X, XY += Y;

        sub.push_back(XY);
    }
    cout << "! " << sub[0] << "\n";
}


Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define forn(b) for(int i = 0; i < b; i++)
#define rforn(b) for(int i = b - 1 ;i >= 0; i--)
#define It(m) for(auto it = m.begin(); it != m.end(); it++)
#define N 500500
#define PI 3.14159265358979323846264338327950L
#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
const ll mod = (ll)1e9 + 7;
    
int main(){
    speed;
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) {
        string s; cin >> s;
        cout << s << endl << s << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
         
int main(void){
int x1, x2, x3, x4, x5;
          
scanf("%d %d %d %d %d", &x1, &x2, &x3, &x4, &x5);
          
  if(x1 == 0){
    printf("1\n");
  }else if(x2 == 0){
    printf("2\n");
  }else if(x3 == 0){
    printf("3\n");
  }else if(x4 == 0){
    printf("4\n");
  }else if(x5 == 0){
    printf("5\n");
  }
    return 0;
}

Measured memory_bytes: 1616
#include <bits/stdc++.h>
using namespace std;
#define reps(i, a, n) for (int i = (a); i < (n); ++i)
#define rep(i, n) reps(i, 0, n)
#define deps(i, a, n) for (int i = (a); i >= (n); --i)
#define dep(i, n) deps(i, n, 0)
#define inf 2147483647
#define int long long

signed main(void)
{
	int k; cin >> k;
	string s; cin >> s;
	int sl = s.length();
	if (k >= sl) cout << s << endl;
	else cout << s.substr(0, k) << "..." << endl;
}


Measured memory_bytes: 3624
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    int n;
    cin>>n;
    int n2 = 1<<n;
    vector<int> A(n2);
    for(int i = 0;i < n2;i++) {
        cin>>A[i];
    }
    sort(A.begin(),A.end());
    vector<int> s;
    s.push_back(A.back());
    A.back() = -1;
    for(int i = 0;i < n;i++) {
        vector<int> p = s;
        sort(p.begin(),p.end());
        int ai = n2-1;
        while(p.size() > 0 && ai >= 0) {
            if(A[ai] == -1) {
                ai--;
                continue;
            }
            if(A[ai] < p.back()) {
                s.push_back(A[ai]);
                p.pop_back();
                A[ai] = -1;
            }
            --ai;
        }
        if(p.size() > 0) {
            cout<<"No"<<endl;

            return 0;
        }
    }

    cout<<"Yes"<<endl;


    return 0;
}


Measured memory_bytes: 2932
#pragma G++ optimize (2)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
#define INF 0x3f3f3f3f
#define NO 30005
#define MO 100005
typedef long long ll;
//by Oliver
using namespace std;
inline ll read()
{
	char ch = ' ', last;
	ll ans = 0;
	while (ch < '0' || ch > '9')
		last = ch, ch = getchar();
	while (ch >= '0' && ch <= '9')
		ans = ans * 10 + int(ch - '0'), ch = getchar();
	if (last == '-')
		return -ans;
	return ans;
}
void write(ll x)
{
	if (x >= 10)
		write(x / 10);
	putchar(x % 10 + '0');
}
//head

int cnt1, cnt2, cnt3, a, b, n;
//variable

void init()
{
	n = read(), a = read(), b = read();
	while (n--)
	{
		int x = read();
		cnt1 += x <= a, cnt2 += x > a && x <= b, cnt3 += x > b;
	}
}
//functions

int main()
{
	init();
	cout << min(cnt1, min(cnt2, cnt3)) << endl;
	return 0;
}
//main


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <numeric>
#include <iomanip>


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

	std::cin >> a >> b >> c;

	int count = 0;
	std::vector<int> v;
	for (size_t i = 1; i <= std::min(a, b); i++) {
		if (a % i == 0 && b % i == 0) {
			v.push_back(i);
		}
	}

	std::cout << v[v.size() - c] << std::endl;

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// #include <boost\version.hpp>
#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define INF 1145141919
#define MINF -1145141919

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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



int main() {
	int N;
	cin >> N;
	int tmp;
	int over = 0;
	int cnt = 0;
	vector<bool> a(8);
	FOR(i, 0, N) {
		cin >> tmp;
		if(tmp >= 3200) {
			over++;
		} else {
			if(!a[tmp / 400]) {
				a[tmp / 400] = true;
				cnt++;
			}
		}
	}
	cout << max(1, cnt) << endl;
	cout << over + cnt << endl;
	return	0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

	for ( int w, h; cin >> w >> h, w | h; )
	{
		VS board( h );
		FOR( line, board )
		{
			cin >> line;
		}

		vector<VS> dp( h, VS( w, string( 72, '0' ) ) );
		string res;
		REP( i, 0, h )
		{
			REP( j, 0, w )
			{
				if ( isdigit( board[i][j] ) )
				{
					if ( i && isdigit( board[ i - 1 ][j] ) )
					{
						dp[i][j] = max( dp[i][j], dp[ i - 1 ][j] );
					}
					if ( j && isdigit( board[i][ j - 1 ] ) )
					{
						dp[i][j] = max( dp[i][j], dp[i][ j - 1 ] );
					}
					( dp[i][j].erase( 0, 1 ) ) += board[i][j];
				}
				res = max( res, dp[i][j] );
			}
		}

		res.erase( 0, find_if( ALL( res ), bind1st( not_equal_to<char>(), '0' ) ) - res.begin() );
		cout << res << endl;
	}

	return 0;
}

Measured memory_bytes: 1368
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include<numeric>
#include<cmath>
#include<map>
#include<iomanip>
#include<set>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<double,double>;
using vvi = vector<vector<int> >;
using vvll =  vector<vector<ll> >;

int main(){
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
    int N; cin >> N;
    vector<pll> Perm(N);
    REP(i,N){
        ll p; cin >> p;
        Perm[i] = P(p,i+1);
    }
    sort(ALL(Perm));
    reverse(ALL(Perm));
    multiset<ll> st;
    st.insert(0);
    st.insert(0);
    st.insert(N+1);
    st.insert(N+1);

    ll ans = 0;
    REP(i,N){
        ll fi = Perm[i].first;
        ll se = Perm[i].second;
        //st.insert(se);
        auto itr = st.lower_bound(se);
        //auto itrminus = itr--;
        ll w = *prev(itr,2);
        ll x = *prev(itr,1);
        ll y = *itr;
        ll z = *next(itr,1);
        ans += fi * ((z-y)*(se-x) + (y-se)*(x-w));
        st.insert(se);
    }
    cout << ans << endl;
}



Measured memory_bytes: 9472
/*
    Problem 6
    https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    for (char i = '0'; i <= '9'; i++) for (char j = '0'; j <= '9'; j++) for (char k = '0'; k <= '9'; k++) {
        vector<char> v{i, j, k};
        int t = 0;
        for (int s = 0; s < N; s++) {
            if (S[s] == v[t]) t++;
            if (t >= 3) {
                ans++;
                // cout << i << j << k << '\n';
                break;
            }
        }
    }
    cout << ans << '\n';
}

Measured memory_bytes: 3676
ans = []
while 1:
    n, m = map(int, input().split())
    if n+m == 0:
        break
    C = {0: 0}
    for i in range(n):
        b = int(input(), 2)
        for k, v in dict(C).items():
            if C.get(k^b, 0) < v+1:
                C[k^b] = v+1
    ans.append(C[0])
print(*ans, sep="\n")

Measured memory_bytes: 193612
n,k = map(int,input().split())

a = list(map(int,input().split()))

a.sort()

max_tree = max(a)

min_tree = 0

while min_tree+1 != max_tree:
    mid_tree = (max_tree+min_tree)//2
    tmp_count = 0
    for i in range(n-1,-1,-1):
        if a[i] < mid_tree:
            break
        
        if a[i]%mid_tree == 0:
            tmp_count += a[i]//mid_tree-1
        else:
            tmp_count += a[i]//mid_tree

    if k < tmp_count:
        min_tree = mid_tree
    else:
        max_tree = mid_tree
    #print(max_tree, min_tree,tmp_count)
print(max_tree)

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	ll a, b, c, d;
	cin>>a>>b>>c>>d; a--;
	ll e = c*d/__gcd(c, d);
	ll ans = b - a;
	ans -= b/c - a/c;
	ans -= b/d - a/d;
	ans += b/e - a/e;
	cout<<ans<<endl;

	return 0;
}

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

#define IOS cin.tie(0);ios::sync_with_stdio(false)

#define ll      long long
#define Fi      first
#define Se      second
#define Pb      push_back
#define vi      vector<int>
#define vp      vector<pair<int,int>>
#define vvi     vector<vector<int>>
#define vvp     vector<vector<pair<int,int>>>

const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>; //Caution!! Segmentation Fault!! Don't forget to add +1!

#define all(v) v.begin(),v.end()
#define output_s(s) printf("%s\n",(s).c_str())

#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++)
#define RepS(i,n,m)     for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m)    for(int i=(int)(n);i>=(int)(m);i--)
#define RepA(x)         for(auto &item:(x))

void CINT(){} //@shibh308's template
template <class Head,class... Tail> void CINT(Head&& head,Tail&&... tail){cin>>head; CINT(move(tail)...);}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

void OUT(){}
template<class Head,class...Tail> void OUT(Head&& head,Tail&&...tail){cout<<head<<(sizeof...(tail)?' ':'\n'); OUT(move(tail)...);}
#define COUT(...) OUT(__VA_ARGS__)

template<typename TypeInt>TypeInt GCD(TypeInt a,TypeInt b){return a%b==0?b:GCD(b,a%b);} //最大公約数
template<typename TypeInt>TypeInt LCM(TypeInt a,TypeInt b){return a*b/GCD(a,b);}//最小公倍数

void YES(bool f){printf(f?"YES\n":"NO\n");}
void Yes(bool f){printf(f?"Yes\n":"No\n");}
void Possible(bool f){printf(f?"Possible\n":"Impossible\n");}
void POSSIBLE(bool f){printf(f?"POSSIBLE\n":"IMPOSSIBLE\n");}

//void print(){}

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

//const int dx[4]={1,0,-1,0};
//const int dy[4]={0,1,0,-1};
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

const int NMAX = 200;
bool flag;

bool comp(int x,int y){
    return abs(0-x)<abs(0-y);
}

int make_num(char a,char b,char c){
    int num=(a-'0')*100+(b-'0')*10+(c-'0');
    return num;
}

signed main(){
//    IOS;
    SCIN(s);
    int N=s.size()-3;
    int ans=INF;
    RepS(i,0,N){
        int num=make_num(s[i],s[i+1],s[i+2]);
        ans=min(ans,abs(753-num));
    }
    printf("%d\n",ans);
    
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    ll N;
    cin >> N;

    vll A(N);
    REP(i, N) cin >> A[i];

    ll mx = *max_element(ALL(A)), mi = *min_element(ALL(A));

    if ( mx - mi >= 2) {
        print("No");
        return 0;
    }

    if (mx - mi == 0) {
        if (mx == N - 1 || 2 * mx <= N) {
            print("Yes");
        } else {
            print("No");
        }
        return 0;
    }

    ll cnt = 0;
    REP(i, N) if (A[i] == mi) cnt++;

    if (cnt < mx && 2 * (mx - cnt) <= N - cnt) {
        print("Yes");
    } else {
        print("No");
    }


    
}


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

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
const int N = 100005;

int n, m;
bitset<N> spoken;

int gsz[N], parent[N];
void make_set(int v) {
	parent[v] = v;
	gsz[v] = 1;
}

int find_set(int v) {
	if (v == parent[v]) return v;
	return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
	a = find_set(a);
	b = find_set(b);
	if (a != b) {
		if (gsz[a] < gsz[b])
			swap(a, b);
		parent[b] = a;
		gsz[a] += gsz[b];
	}
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	spoken.reset();
	for (int i = 0; i < n; ++i) {
		int k, last = -1; cin >> k;
		for (int j = 0; j < k; ++j) {
			int l; cin >> l;
			if (!gsz[l]) make_set(l);
			spoken[l] = 1;
			if (last != -1) union_sets(l, last);
			last = l;
		}
	}
	
	bool val = true;
	int base = -1;
	for (int i = 1; i <= m; ++i) {
		if (spoken[i]) {
			if (base == -1) base = find_set(i);
			else if (base != find_set(i)) {
				val = false;
				break;
			}
		}
	}
	
	if (val) cout << "YES";
	else cout << "NO";
}


Measured memory_bytes: 4448
#include <iostream>

int main()
{
    int s;
    std::cin >> s;
    int hour = s / 3600;
    s -= hour * 3600;
    int min = s / 60;
    s -= min * 60;
    std::cout << hour << ":" << min << ":" << s << std::endl;
    return 0;
}

Measured memory_bytes: 1164