akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
int n,m;
int tl[3100005],tr[3100005];
ll val[3100005],tag[3100005];
void build(int x,int l,int r){
	tl[x]=l,tr[x]=r;
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build((x<<1)|1,mid+1,r);
}
void pushdown(int x){
	if(tag[x]){
		tag[x<<1]+=tag[x];
		val[x<<1]+=tag[x];
		tag[(x<<1)|1]+=tag[x];
		val[(x<<1)|1]+=tag[x];
		tag[x]=0;
	}
}
void modify(int x,int l,int r,ll v){
	int lc=tl[x],rc=tr[x],mid=(lc+rc)>>1;
	if(lc>=l&&rc<=r){
		tag[x]+=v;
		val[x]+=v;
		return ;
	}
	pushdown(x);
	if(l<=mid){
		modify(x<<1,l,r,v);
	}
	if(r>mid){
		modify((x<<1)|1,l,r,v);
	}
	val[x]=max(val[x<<1],val[(x<<1)|1]);
}
ll query(int x,int p){
	int lc=tl[x],rc=tr[x],mid=(lc+rc)>>1;
	if(rc==p){
		return val[x];
	}
	pushdown(x);
	if(p<=mid){
		return query(x<<1,p);
	}
	else{
		return max(val[x<<1],query((x<<1)|1,p));
	}
}
struct node{
	int l,r;
	ll v;
}b[3100005];
bool cmp(node a,node b){
	return a.r<b.r;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>b[i].l>>b[i].r>>b[i].v;
	}
	sort(b+1,b+1+m,cmp);
	build(1,1,n);
	int cnt=1;
	for(int i=1;i<=n;++i){
		modify(1,i,i,query(1,i));
		while(b[cnt].r==i){
			modify(1,b[cnt].l,b[cnt].r,b[cnt].v);
			cnt++;
		}
	}
	cout<<max(0ll,val[1])<<'\n';
	return 0;
}

Measured memory_bytes: 24832
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<(n); i++)
#define int long long
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;
signed main(void){
    int h,w;cin>>h>>w;
    vector<string>G(h+1);rep(i,h){cin>>G[i];G[i]+='#';}
    string s="";
    rep(i,w+1)s+='#';
    G[h]=s;
    int W[h+1][w+1],H[h+1][w+1];
    //W
    int count=0;
    rep(i,h)rep(j,w+1){
        if(G[i][j]=='.')count++;
        else{
            W[i][j]=0;
            int x=j-1;
            while(x>=0){
                if(G[i][x]=='#')break;
                W[i][x]=count;
                x--;
            }
            count=0;
        }
        
    }
    //H
    count=0;
    rep(j,w)rep(i,h+1){
        if(G[i][j]=='.')count++;
        else{
            H[i][j]=0;
            int x=i-1;
            while(x>=0){
                if(G[x][j]=='#')break;
                H[x][j]=count;
                x--;
            }
            count=0;
        }
    }
    //rep(i,h){
      //  rep(j,w)cout<<H[i][j]<<' ';
        //cout<<endl;
    //}
    int ans=0;
    rep(i,h)rep(j,w){
        ans=max(ans,W[i][j]+H[i][j]-1);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 66944
#include <iostream>

using namespace std;
int ans,s,x[101],n,i,j,mn,mx;
int main()
{
    cin >> n;
    for (i=1; i<=n; i++)
    {
    cin >> x[i];
    mn=min(mn,x[i]);
    mx=max(x[i],mx);
    }
    
    for (i=mn; i<=mx; i++)
    {
        for (j=1; j<=n; j++)
        s+=(max(i,x[j])-min(i,x[j]))*(max(i,x[j])-min(i,x[j]));
        if (i==mn) ans=s;
        else
        ans=min(ans,s);
        s=0;
    }
    cout<<ans<<endl;
    
    
}


Measured memory_bytes: 3632
A, B=map(int, input().split())
if A==B:
    print(A)
    exit()

if B - A<=1000:
    ans=A
    for i in range(A+1, B+1):
        ans=ans^i
    print(ans)
else:
    lis=[]
    for i in range(A, B+1):
        if i%4==0:
            break
        else:
            lis.append(i)
    for j in range(B, A-1, -1):
        if j%4==0:
            lis.append(j)
            break
        else:
            lis.append(j)
    for i in range(len(lis)):
        if i==0:
            ans=lis[i]
        else:
            ans=ans^lis[i]
    print(ans)


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

int main() {
    int64_t N; cin >> N;
    string ans = "";
    while(N) {
        int n = N % 26;
        if(n == 0) n = 26;
        n--;
        ans += char('a' + n);
        N /= 26;
        if(n == 25) N--;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1LL << 60;

template <typename T>
void print(const T &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        if (a == b)
        {
            ++cnt;
            if (cnt >= 3)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
        else
        {
            cnt = 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3636
def examD():
    K = I()
    N = 50
    A = [i for i in range(N)]
    for i in range(N):
        A[-1-i] +=((K-i+49)//N)
    print(N); print(" ".join(map(str,A)))

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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

int main() {
 int H,W,N;
 cin >> H >> W >> N;
 int ans = 0;
 int k = 1;
 while(true){
     if(max(H,W)*k >= N){
         break;
     }
     k++;
 }

 cout << k << endl;


}


Measured memory_bytes: 256
#include <cstdio>
#include <map>
typedef long long int64;
static const int MODULUS = 1e9 + 7;
#define _  %  MODULUS
#define __ %= MODULUS
static const int INV2 = 5e8 + 4;

int n, k;

inline int fpow(int base, int exp)
{
    int64 ans = 1;
    for (; exp; exp >>= 1, base = (int64)base * base _) if (exp & 1) (ans *= base)__;
    return ans;
}

std::map<int, int> calc_mem;
int calc(int n)
{
    if (n == 1) return k;
    auto itr = calc_mem.find(n);
    if (itr != calc_mem.end()) return itr->second;

    int ret = fpow(k, (n + 1) / 2);
    for (int i = 1; i * i <= n; ++i) if (n % i == 0) {
        (ret -= calc(i))__;
        if (i != 1 && i * i != n) (ret -= calc(n / i))__;
    }
    (ret += MODULUS)__;
    return (calc_mem[n] = ret);
}

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

    int64 ans;
    for (int i = 1; i * i <= n; ++i) if (n % i == 0) {
        (ans += (int64)calc(i) * (i % 2 ? i : (i / 2)))__;
        if (i * i != n)
            (ans += (int64)calc(n / i) * ((n / i) % 2 ? (n / i) : (n / i / 2)))__;
    }
    printf("%lld\n", ans);

    return 0;
}


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

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, M = 1e6 + 10;
const int mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;

int t;

ll a[N * 2];

ll n, k;

bool check(ll mid)
{
    ll cnt = 0;
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (mid == 0)
        {
            if (a[i] <= 0)
            {
                while ((j <= i || a[j] < 0) && j < n)
                {
                    j++;
                }
                cnt += n - j;
            }
        }
        else if (mid > 0)
        {
            if (a[i] == 0)
            {
                cnt += n - i - 1;
            }
            else
            {
                int id = lower_bound(a + i + 1, a + n, mid / a[i]) - a;
                if(id == n)
                    id--;
                if (id != i)
                {
                    if(a[i] < 0)
                    {
                        cnt += n - id;
                    }
                    else
                    {
                        if(a[id] * a[i] <= mid)
                            cnt += id - i;
                        else if(a[id - 1] * a[i] <= mid)
                            cnt += id - i - 1;
                    }                 
                }
            }
        }
        else//小于0
        {
            if(a[i] >= 0)
                continue;
            else//小于0
            {
                while ((j <= i || a[j] * 1ll * a[i] > mid) && j < n)
                {
                    j++;
                }
                cnt += n - j;
            }     
        }
    }
    return cnt >= k;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a + n);
    ll l = -1e18, r = 1e18;
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
            r = mid - 1;
        else
        {
            l = mid + 1;
        }
    }
    cout << r + 1 << endl;
    return 0;
}


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

/*
int N;
vector<vector<int>> dp;
void solve(int i, int j, ll x, vector<vector<int>> dp){
    if (i>N || j>N) return;
    if(dp.at(N+i).at(N+j) == 0) dp.at(N+i).at(N+j)=1;
    else return;
    //cout << i<<j << endl;
    ll tmp;
    tmp = (ll)pow(i,5)-(ll)pow(j,5) - x;
    if (tmp==0){
        cout << i << j << endl;
        return;
    }else{
        solve(i+1, j, x, dp);
        solve(i, j+1, x, dp);
    }
   return;
}
int main(){
    N=5;
    vector<vector<int> > dp(2*N+1, vector<int>(2*N+1, 0));
    ll x;
    cin >> x;
    solve(-N,-N,x,dp);
}
*/

int N;
vector<vector<int>> dp;
void solve(ll x){
    ll diff;
    for(int i=-N; i<N; i++){
        for(int j=-N; j<N; j++){
            diff = pow(i,5)-pow(j,5)-x;
            //cout << i<<j << endl;
            if(diff==0){
                cout<< i << ' ' <<j<< endl;                
                break;
                }
        }
        if(diff==0) break;
    }
}

int main(){
    N=200;
    ll x;
    cin >> x;
    solve(x);
}

Measured memory_bytes: 4032
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int N = stdIn.nextInt();
        int[] X =new int[N];
        for (int i = 0; i < N; i++) {
            X[i] = stdIn.nextInt();
        }
        stdIn.close();

        Arrays.sort(X);

        int[] sum = new int[X[N-1] - X[0] + 1];
        for (int i = 0; i <= X[N-1] - X[0]; i++) {
            for (int j = 0; j < N; j++) {
                sum[i] += Math.pow(X[j] - (X[0] + i), 2);
            }
        }

        Arrays.sort(sum);
        System.out.println(sum[0]);
    }
}

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

int main() {

	int N, M;
	cin >> N >> M;

	vector<int> a(M);
	vector<int> b(M);

	for (int i = 0;i < M;i++) 
		cin >> a.at(i) >> b.at(i);

	vector<int> pas(N);

	for (int i = 0;i < M;i++) {
		pas.at(a.at(i) - 1)++;
		pas.at(b.at(i) - 1)++;
	}
	for (int i = 0;i < N;i++) 
		cout << pas.at(i) << endl;
	

	
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <random>
#include <set>
#include <stack>

//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater<int>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#include <time.h>
typedef std::pair<int,int> pii;
using namespace std;
using ll = long long;
#define PI 3.14159265358979323846264338327950L
const int mod =  998244353;



void solve(){
    
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    SORT(a);
    int ans = 0;
    rep(i,k) ans += a[i];
    cout << ans;
}



int main(){
    solve();
}




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

int main(){
  string s;cin>>s;
  string a;
  rep(i,s.size()){
    a.append("x");
  }
  
  cout<<a<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;
#define rep(i, n)  for (int i = 0; i <  (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
const ll INF = ll(1e18)+1;

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

    ll x,y;
    cin >> x >> y;

    bool result = false;

    rep(i,x+1){
        if(i*2+(x-i)*4 == y){
            result = true;
        }
    }
    if(result){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
}

Measured memory_bytes: 3664
//
//  main.cpp
//  Problem Code
//
//  Created by Algo张伯威 on 2020/4/24.
//  Copyright © 2020 Algo张伯威. All rights reserved.
//

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int main() {
    int a, b, c, d;
    scanf("%d%d%d%d", &a,&b, &c, &d);
    while(1) {
        c -= b;
        if(c <= 0) {
            printf("Yes\n");
            break;
        }
        a -= d;
        if(a <= 0) {
            printf("No\n");
            break;
        }
    }
        
    return 0;
}
























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

using namespace std;

/*int main(){
    int a,b,c;

    cin>>a>>b>>c;

    if(c==clamp(c,a,b)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

}*/

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

    cin>>a>>b>>c;

    if(a<=c&&b>=c){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

def main():
    X, Y=list(map(int,input().split()))
    coin=0
    for _ in range(2):
        if X>Y:
            coin+=X
            X-=1
        else:
            coin+=Y
            Y-=1
    print(coin)
    
if __name__ == "__main__":
    main()

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

using vs = vector<string>;

int main(){
  int N, M;

  vs s(110), t(110);
  map<string, int> score;

  cin >> N;
  for(int i=0; i<N; i++){
    cin >> s[i];
    if(score.count(s[i])){
      score[s[i]]++;
    } else {
      score[s[i]] = 1;
    }
  }

  cin >> M;
  for(int i=0; i<M; i++){
    cin >> t[i];
    if(score.count(t[i])){
      score[t[i]]--;
    } else {
      score[t[i]] = -1;
    }
  }

  int ans = 0;
  for(int i=0; i<N; i++){ ans = max(ans, score[s[i]]);}

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<functional>
#include<set>
using namespace std;

#define INF 1<<21
#define DIV 1000000007
#define MAX 100005


int main(){
  int N;
  while (cin >> N,N) {
	int x[201],y[201];
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
	x[0] = 0, y[0] = 0;
	int n, d;
	int maxx = 0, minx = 205, maxy = 0, miny = 205;

	for (int i = 1; i < N; i++) {
	  cin >> n >> d;
	  x[i] = x[n] + dx[d];
	  y[i] = y[n] + dy[d];
	}
	for (int i = 0; i < N; i++) {
	  maxx = max(maxx, x[i]);
	  maxy = max(maxy, y[i]);
	  minx = min(minx, x[i]);
	  miny = min(miny, y[i]);
	}

	cout << maxx - minx +1 << " " << maxy - miny  +1 << endl;
  }
}

Measured memory_bytes: 3012
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define INF 100000000000000
#define MOD 1000000007LL
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
// input vector
template<typename T>
void invec(vector<T> &A){for(T& a : A) cin >> a;}

#define MAX 10000
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

i64 N, K; cin >> N >> K;
int R = N - K;
COMinit();

// (Kをi分割する方法数)*COM(R+1, i)
rep(i, 1, K+1){
    if (R+1 < i) cout << "0\n";
    else cout << COM(K-1, i-1) * COM(R+1, i) % MOD << "\n";
}


}
// 書いて考える．場合分け
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 512
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>

using namespace std;
#define ALL(x)			(x).begin(),(x).end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF				(int)2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<ll, string>	P;
typedef vector<ll>		VLL;
typedef vector<VLL>		VVLL;
typedef vector<VVLL>	VVVLL;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
/* N進数の文字列取得(負にも対応) */
template<class T>
string getNumberBaseStr(T val, T base)
{
	string binStr;

	while (val != 0) {
		T amari = val % base;
		amari = abs(amari);
		binStr.push_back('0' + (int)amari);
		val -= amari;
		val /= base;
	}
	if (0 < binStr.size()) {
		reverse(binStr.begin(), binStr.end());
	} else {
		binStr.push_back('0');
	}
	return binStr;
}


int main()
{
	ll N, K;
	cin >> N >> K;

	string str = getNumberBaseStr<ll>(N, K);
	cout << str.size() << endl;
	return 0;
}


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

int main(void){
    int  a, b, c, d;
    scanf("%d""%d""%d""%d", &a, &b, &c, &d);
    if(abs(a - c) <= d|| (abs(a - b) <= d && abs(b - c) <= d)){
        printf("Yes\n");
        return 0;
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
a, b, c, x, y = list(map(int, input().split(' ')))

result = a * x + b * y

mx = max([x, y])

for i in range(1, mx + 1):
    tmp = a * max([(x - i), 0]) + b * max([(y - i), 0]) + c * 2 * i

    if result > tmp:
        result = tmp

print(result)



Measured memory_bytes: 40540
import java.util.*;
 import java.math.BigInteger;
public class Main
{
	public static  void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		// String h[]=sc.nextLine().split(" ");
		long n=Long.parseLong(sc.nextLine());
		long a=100;
		int k=0;
		while(a<n)
		{
			a=(long)((double)a*1.01);
			k+=1;
		}
		System.out.println(k);
	}

}



	


Measured memory_bytes: 35556
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <queue>

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

int cnt, h, w, N;
vector<int> a;


int main()
{
	cin >> h >> w;
  cin >> N;
  a.resize(N);

  rep(i, N){
    cin >> a[i];
  }
  int c[h][w];

  int k = 1;
	for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      c[i][j] = k;
      a[k-1]--;
      if(a[k-1] == 0) k++;
    }
    i++;
    if(i == h) break;
    for(int j = w-1; j >=0; j--){
      c[i][j] = k;
      a[k-1]--;
      if(a[k-1] == 0) k++;
    }
  }
	
  rep(i, h){
    rep(j, w){
      cout << c[i][j] << " ";
    }
    cout << endl;
  }
			  	
	return 0;
}


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

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

using namespace std;

int main(){
	int n; scanf("%d",&n);
	int ans=INT_MAX;
	rep(i,n){
		int a,b; scanf("%d%d",&a,&b);
		ans=min(ans,a+b);
	}
	printf("%d\n",ans);
	return 0;
}


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	for(ll i=m/n; i>=1; i--){
		if(m%i==0 and n*i<=m){
			cout<<i<<endl;
			return 0;
		}
	}
}


Measured memory_bytes: 256
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <iostream>

using namespace std;

int ans;
int limit;

void recurse(long long num, int mask) {
    if (num > limit)
        return;
    if ((mask & 7) == 7)
        ans++;
    recurse(num * 10 + 3, mask | 1);
    recurse(num * 10 + 5, mask | 2);
    recurse(num * 10 + 7, mask | 4);
}

int main(void) {
	cin >> limit;
	
	recurse(0, 0);
	cout << ans << "\n";
	
	return 0;
}


Measured memory_bytes: 256
s = input()
def YY(s):
    if 0<= int(s) <= 99:
        return True
    return False

def MM(s):
    if 1<=int(s)<=12:
        return True
    return False

if YY(s[:2]) and MM(s[2:]) and MM(s[:2]) and YY(s[2:]):
        print("AMBIGUOUS")

elif YY(s[:2]) and MM(s[2:]):
     print("YYMM")
        
elif MM(s[:2])  and YY(s[2:]):
    print("MMYY")
        
else:
    print("NA")

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <numeric>
#include <cmath>
#include <cctype>

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,x); REP(i,sizeof(a)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}


int main(){
  int N,M,Q; cin>>N>>M>>Q;
  int mat[N+1][N+1]; FILL2(mat,N+1,N+1,0);
  REP(i,M){
    int l,r; cin>>l>>r;
    ++mat[l][r];
  }
  int cumu[N+1][N+1];
  for(int i=0;i<=N;++i){
    for(int j=0;j<=N;++j){
      if(j==0){ cumu[i][j] = 0; }
      else if(i==0){ cumu[i][j] = mat[i][j] + cumu[i][j-1]; }
      else{ cumu[i][j] = mat[i][j] + cumu[i-1][j] + cumu[i][j-1] - cumu[i-1][j-1]; }
    }
  }
  REP(count,Q){
    int p,q; cin>>p>>q;
    cout << cumu[q][q] - cumu[q][p-1] - cumu[p-1][q] + cumu[p-1][p-1] <<"\n";
  }
}

Measured memory_bytes: 2944
#include<iostream>
#include<vector>
using namespace std;
int main() {
  int N;
  vector<int> v;
  int v1;

  cin >> N;
  for(int i=0; i<N; i++) {
    cin >> v1;
    v.push_back(v1);
  }

  int x = 1;
  int count = 0;
  int one = 0;
  for(int i=0; i<N; i++) {
    if(v[i] == x) {
      count++;
      x++;
    }

    if(v[i] == 1) one = 1;
  }

  if(one == 1) {
    cout << N-count << endl;
  }else {
    cout << -1 << endl;
  }
}

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


int main() {
  int N; cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  
  vector<int> ans(N, 0);
  
  rep(i, N-1) ans[A[i]-1]++;
  
  rep(i, N) cout << ans[i] << endl;
  
}


Measured memory_bytes: 4840
a,b,c=gets.chomp.split(" ").map(&:to_i)
k = gets.to_i
d = true

while a >= b || b >= c
  while a >= b do
    b *= 2
    k -= 1
  end

  while b >= c do
    c *= 2
    k -= 1
  end
end

if k >= 0
  print('Yes')
else
  print('No')
end

Measured memory_bytes: 14344
#include <iostream>
using namespace std;
int main(){
    int people=0;
    cin>>people;
    int score[people];
    for(int i=0;i<people;i++){
        score[i]=0;
    }
    int countmi=0,countma=0;
    int countgr=0;
    int countch=0;
    int countg=0;
    int countw=0;
    int countb=0;
    int county=0;
    int counto=0;
    int countr=0;
    int countfree=0;
    int sum=0;
    for(int i=0;i<people;i++){
        cin>>score[i];
        if(score[i]<=399&&score[i]>=1){
            countgr=1;
        }else if(score[i]<=799&&score[i]>=400){
            countch=1;
        }else if(score[i]<=1199&&score[i]>=800){
            countg=1;
        }else if(score[i]<=1599&&score[i]>=1200){
            countw=1;
        }else if(score[i]<=1999&&score[i]>=1600){
            countb=1;
        }else if(score[i]<=2399&&score[i]>=2000){
            county=1;
        }else if(score[i]<=2799&&score[i]>=2400){
            counto=1;
        }else if(score[i]<=3199&&score[i]>=2800){
            countr=1;
        }else if(score[i]>=3200){
            countfree+=1;
        }
    }
  
    countmi=countgr+countch+countg+countw+countb+county+counto+countr;
    int a=0;
    a=countmi;
    if(countmi==0){
        countmi=1;
    }
    sum=8-countmi;
    /*if(sum<=countfree){
        countma=8;
    }else */
    //if(sum>=countfree){
        countma=countmi+countfree;
        if(a==0){
            countma-=1;
        }
    //}
    //cout<<"countma"<<countma<<endl;
    cout<<countmi<<" ";
    cout<<countma<<endl;
    return 0;
}





Measured memory_bytes: 256
def aaa(m,s):
    if m[s]:
        new_s = m[s][0]
        m[s] = m[s][1:]
        aaa(m, new_s)
    else:
        print(s.upper())
        exit(0)

aaa({'a': input(), 'b':input(), 'c':input()}, 'a')

Measured memory_bytes: 3188
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
//#define int long long

using namespace std;

// conversion
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();}

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define eprintf(...)
#define dump(x)
#define debug(x)
#endif

typedef long long ll;

const ll MOD = 1e9 + 7;

class ESequenceDecomposing {
public:
void solve(std::istream& in, std::ostream& out) {
    int N;
    in >> N;
    vector<int> A(N);
    REP(i,0,N) in >> A[i];
    int minA = INT_MAX;
    int answer = 1;
    vector<int> mins;
    mins.emplace_back(A.back());
    RREP(i,0,N-1) {
        const auto itr = upper_bound(all(mins), A[i]);
        if (itr == mins.end()) {
            mins.emplace_back(A[i]);
            answer++;
        } else {
            *itr = A[i];
        }
    }
    out << answer << "\n";
}
};


int main() {
	ESequenceDecomposing solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main(){
	int n;
	vector<int> a,b,c;
	cin>>n;
	for(int i=0;i<n;i++){
		int t;
		cin>>t;
		a.push_back(t);
	}
	for(int i=0;i<n;i+=2){
		b.push_back(a[i]);
	}
	for(int i=1 ;i<n;i+=2){
		c.push_back(a[i]);
	}
	reverse(c.begin(),c.end());
	for(int i=0;i<b.size();i++){
		c.push_back(b[i]);
	}
	if((n-1)%2==0)reverse(c.begin(),c.end());
	for(int i=0;i<c.size()-1;i++){
		cout<<c[i]<<' ';
	}
	cout<<c.back()<<endl;
	return 0;
}

Measured memory_bytes: 5108
#include <iostream>
#include <math.h>
#include <list>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <climits>
#include <string>
#include <vector>

using namespace std;

#define endl '\n'
#define int long long
#define mod 1000000007

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

int32_t main() {

		int n,k; cin>>n>>k;

		vector<int> v(n+1);

		for(int i=1;i<=n;i++) {
			cin>>v[i];
		}

		vector<int> cost(n+1, INT_MAX);

		cost[0]=cost[1]=0;

		for(int i=2;i<=n;i++) {

			for(int j=1;j<=k && (i-j)>0;j++) {
				cost[i] = min(cost[i], cost[i-j] + abs(v[i] - v[i-j]));
			}
		}

		cout<<cost[n]<<endl;
		
	return 0;
}

Measured memory_bytes: 1792
import math
while 1:
    n = int(input())
    if n == 0:
        break
    s = list(map(int,input().split()))
    m = sum(s) / len(s)
    x = 0
    for i in range(n):
        x += (s[i] -m )**2 / n
    a = math.sqrt(x)
    print(a)

Measured memory_bytes: 7636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
const ll MAX = 510000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//重複組合せ計算
ll MULTICOM(ll n, ll k){
    return COM(n+k-1,k);
}

void Main(){
    COMinit();
    ll n;cin>>n;
    ll k;cin>>k;
    For(i,0,min(k+1,n)){
        ans+=(COM(n,i)*MULTICOM(n-i,i)%MOD);
        ans%=MOD;
    }
    cout<<ans<<endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Measured memory_bytes: 12160
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < N; i++)
using namespace std;

int main()
{
    int N;
    long long sum = 0;
    cin >> N;
    rep(i, N)
    {
        int a;
        cin >> a;
        sum += (a - 1);
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll mod=1e9+7;
const ll MAXN = 1e7+10;


  
int spf[MAXN];

void solve(){
    
    int ans=0,n=0;
    cin>>n;
    if(n%1000==0){
        cout<<0<<"\n";
        return;
    }
    cout<<(((n/1000)+1)*1000)-n<<"\n";
    
}
  
        

int main(){
   
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    #endif */
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int T=1;
        //cin>>T;
        while(T--){
            solve();
        }
            
            
        return 0;
}
 

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// typedef pair<ll,ll> Pair;
// ll mod=1000000007;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    ll t,i,j,k,temp,temp2,n,m,x,y,sum=0;
    cin >> n >> k;
    cout << min(n%k,abs((n%k)-k));
}

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


int main(){
  int N, M, X, Y;
  cin >> N >> M >> X >> Y;
  vector<int> x(N);
  vector<int> y(M);
  for(auto& xi : x){
    cin >> xi;
  }
  for(auto& yi : y){
    cin >> yi;
  }
  
  int max_xi = *max_element(x.begin(), x.end());
  int min_yi = *min_element(y.begin(), y.end());
  
  if((min_yi <= X) ||(min_yi <= max_xi) || (Y <= max_xi)){
    cout << "War" << endl;
    return 0;
  }
  cout << "No War" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF (1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)

const int MAX_N = int(1e5);
ll N, M, A[MAX_N];


void solve() {
    unordered_map<ll, ll> mp;
    ll ans = 0;
    ll dp[MAX_N + 1];
    REP(i, N) {
        dp[i + 1] = (dp[i] + A[i]) % M;
        mp[dp[i + 1]] = mp[dp[i + 1]] + 1;
    }
    each(mod, mp) {
        ans += mod.second * (mod.second - 1) / 2;
        if (mod.first == 0) ans += mod.second;
    }
    cout << ans << endl;
}

int main() {
    cin >> N >> M;
    REP(i, N) cin >> A[i];
    solve();
    return 0;
}

Measured memory_bytes: 4876
fn main() {
    let mut seq = read_vec::<i32>();
    seq.sort();
    seq.reverse();
    println!("{:?}", seq[0] * 10 + seq[1] + seq[2]);
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}



Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vpii         vector<pair<int,int>>
#define gph          map<int, vector<int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define FORS(i, n) for(; i < (int)(n); i++)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define printArr(A,n) { cout << #A << " = "; FOR(i,n) cout << A[i] << ' '; cout << endl; }
using namespace std;
#define int long long int

const int mod = (int)1e9 + 7;
long long inv(long long a, long long b = mod){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
int cum[(int)2e5 + 10] = {0};
vi fac;
int choose(int a, int b){
    assert(b >= 0 && b <= a);

    int ans = fac[a] * inv(fac[b]);
    ans %= mod;
    ans *= inv(fac[a - b]);
    ans %= mod;
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    int b, w;cin >> b >> w;
    int pow = 1;
    fac.resize(b+w*2);
    fac[0] = 1;
    FOR1(i, b+w)fac[i] = fac[i-1] *i, fac[i] %= mod;





    FOR(i, b)pow *=2, pow %= mod;
    pow = inv(pow);
    int mult = inv(2);
    for(int be = b; be < b+w; be++){
    
        // no blacks left after black end
        // b blacks up until be
        // p = b-1/be-1
        // probability = .5^be
        
        int num = choose(be-1, b-1);
        int temp = (b-1)*inv(be -1);
        temp %= mod;
        temp *= pow;
        temp %= mod;
        temp *= num;
        temp %= mod;
        //debug(be);
        //cout << num << " " << temp << " " << pow <<endl;
        cum[1] += temp;
        cum[1] %= mod;
        cum[be] -= temp; 
        cum[be] %= mod;
        cum[be] += num * pow;
        cum[be] %= mod;
        cum[be+1] -= num * pow;
        cum[be + 1] %= mod;
        pow *= mult;
        pow %= mod;
    }
    pow = 1;
    FOR(i, w)pow *= 2, pow %= mod;
    pow = inv(pow);
    for(int we = w; we < b+w; we++){

        int num = choose(we-1, w-1);
        // p = (we - w)/(we-1)
        int temp = (we-w) * inv(we -1);
        temp %= mod;
        temp *= pow;
        temp %= mod;
        temp *= num;
        temp %= mod;
        //debug(we);
        //cout << num << " " << temp << " " << pow <<endl;
        cum[1] += temp;
        cum[1] %= mod;
        cum[we] -= temp;
        cum[we] %= mod;

        cum[we + 1] += num * pow; 
        cum[we + 1] %= mod;
        pow *= mult;
        pow %= mod;
    }
    int tot = 0;
    FOR1(i, b+w){
        tot += cum[i];
        tot %= mod;
        while(tot < 0)tot += mod;
        cout <<tot << endl;
    }
}




Measured memory_bytes: 5376
# https://atcoder.jp/contests/abc093/tasks/abc093_b
a, b, k = [int(x) for x in input().split()]
s = list(range(a, b + 1)[:k])
t = list(range(a, b + 1)[-k:])
for v in sorted(set(s + t)):
    print(v)


Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
//#define INF 1145141919
#define MOD 1000000007
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }
inline int mul(int x, int y) { return (1LL*x*y)%MOD; }

int N;
int A[100];
int dp[101][102];
int modpow(int x, int k) {
  int a = 1;
  while (k) {
    if (k&1) a = mul(a, x);
    x = mul(x, x);
    k>>=1;
  }
  return a;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N) cin >> A[i];
  vector<int> xs;
  rep(i, N) xs.pb(A[i]);
  sort(all(xs)); uniq(xs);
  int inf = xs.size();

  //dp[0][inf] = 1;
  add(dp[1][inf], 2);
  int e = 2;
  for (int k=index(xs, A[0]); k>0; k--) {
    int w = xs[k]-(k>0?xs[k-1]:0);
    add(dp[1][k], mul(e, (modpow(2, w)+MOD-1)%MOD));
    e = mul(e, modpow(2, w));
  }
  // k=0
  int w = xs[0];
  add(dp[1][0], mul(e, (modpow(2, w-1)+MOD-1)%MOD));

  int prev = A[0];
  for (int i=1; i<N; i++) {
    int vpos = index(xs, A[i]);
    if (prev >= A[i]) {
      rep(j, xs.size()) {
        // j->inf
        if (xs[j] > A[i]) add(dp[i+1][inf], mul(2, dp[i][j]));
        // j->j
        else add(dp[i+1][j], dp[i][j]);
      }
      // inf->inf
      add(dp[i+1][inf], mul(2, dp[i][inf]));
    }
    else {
      // j->j
      int e = modpow(2, A[i]-prev);
      rep(j, xs.size()) add(dp[i+1][j], mul(e, dp[i][j]));
      // inf->inf
      add(dp[i+1][inf], mul(2, dp[i][inf]));
      // inf->k
      e = 2;
      for (int k=index(xs, A[i]); k>=0 && xs[k]>prev; k--) {
        int w = xs[k]-(k>0?xs[k-1]:0);
        add(dp[i+1][k], mul(mul(e, (modpow(2, w)+MOD-1)%MOD), dp[i][inf]));
        e = mul(e, modpow(2, w));
      }
    }
    prev = A[i];
  }

  int s = 0;
  rep(i, xs.size()+1) add(s, dp[N][i]);
  cout << s << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int x[100001],f[100001],su[100001];
int main(void)
{
	int n,m,i,j,y,a,b,c;
	long long sum,nn,mm;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)	scanf("%d",&x[i]);
	for(i=1;i<=n;i++){
		f[i]=0;	su[i]=0;
	}	
	for(i=1;i<m;i++){
		if(x[i-1]<x[i]){
			f[x[i-1]]++;	f[x[i]]--;
		}
		else{
			f[x[i]]++;	f[x[i-1]]--;
		}
	}
	//for(i=0;i<m;i++) printf("%d\n",f[i]);
	y=0;
	su[0]=0;
	for(i=1;i<=n;i++){
		y+=f[i];	su[i]=y;
	}
	//for(i=1;i<=n;i++) printf("%d\n",su[i]);
	sum=0;
	for(i=1;i<n;i++){
		scanf("%d %d %d",&a,&b,&c);
		nn=(long long)a*su[i];
		mm=(long long)b*su[i]+c;
		if(nn<mm) sum+=nn;
		else sum+=mm;
	}	
	printf("%lld\n",sum);	
	return 0;
}

Measured memory_bytes: 3892
#include<cstdio>
const int MAXN = 100000;
const int MOD = int(1E9) + 7;
int fact[MAXN + 5], inv[MAXN + 5];
int S[MAXN + 5], A[MAXN + 5], g[MAXN + 5], h[MAXN + 5];
int pow_mod(int b, int p) {
	int ret = 1;
	while( p ) {
		if( p & 1 ) ret = 1LL*ret*b%MOD;
		b = 1LL*b*b%MOD;
		p >>= 1;
	}
	return ret;
}
void init() {
	fact[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fact[i] = 1LL*fact[i-1]*i%MOD;
	inv[MAXN] = pow_mod(fact[MAXN], MOD-2);
	for(int i=MAXN-1;i>=0;i--)
		inv[i] = 1LL*inv[i+1]*(i+1)%MOD;
	g[0] = inv[0]*0; h[0] = inv[0];
	for(int i=1;i<=MAXN;i++) {
		g[i] = (g[i-1] + 1LL*inv[i]*i%MOD) % MOD;
		h[i] = (h[i-1] + inv[i]) % MOD;
	}
}
int C(int n, int m) {
	return 1LL*fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main() {
	init(); int N;
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		scanf("%d", &A[i]);
		S[i] = (S[i-1] + A[i]) % MOD;
	}
	int ans = 1LL*fact[N-1]*S[N]%MOD*N%MOD;
	for(int d=1;d<N;d++) {
		int f = 1LL*fact[N-d-1]*(((S[N]+MOD-S[d])%MOD+S[N-d])%MOD)%MOD;
		ans = (ans + 1LL*f*fact[N]%MOD*inv[N-d-1]%MOD*pow_mod(d+1, MOD-2)) % MOD;
	}
	/*for(int d=1;d<N;d++) {
		int f = 1LL*fact[N-d-1]*(((S[N]+MOD-S[d])%MOD+S[N-d])%MOD)%MOD;
		for(int k=0;k<=N-d-1;k++) {
			ans = (ans + 1LL*f*inv[N-d-1-k]%MOD*fact[N-k-1]%MOD) % MOD;
		}
	}*/
	/*for(int j=1;j<=N;j++) {
		for(int i=j+1;i<=N;i++)
			for(int k=0;k<=N-i+j-1;k++) {
				ans = (ans + 1LL*fact[N-i+j-1]*inv[N-i+j-1-k]%MOD*fact[N-k-1]%MOD*A[i]%MOD) % MOD;
			}
		for(int i=1;i<=j;i++)
			for(int k=0;k<=N-j+i-1;k++) {
				ans = (ans + 1LL*fact[N-j+i-1]*inv[N-j+i-1-k]%MOD*fact[N-k-1]%MOD*A[i]%MOD) % MOD;
			}
	}*/
	printf("%d\n", ans);
}

Measured memory_bytes: 2560
x=int(input())
a=1
t=0
while t==0:
	if x-26**a>0:
		x=x-26**a
		a=a+1
	else:
		t=1
y=a-1
x=x-1
ans=[]
for i in range(a):
	ans.extend(chr((x//26**y)+97))
	x=x-(x//26**y)*26**y
	y=y-1

print(*ans,sep='')

Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

void dfs(vector<vector<int> >& G, vector<ll>& P, int tmp, int par) {
  if(par != -1)
    P[tmp] += P[par];
  for(auto ne: G[tmp]) {
    if(ne != par)
      dfs(G, P, ne, tmp);
  }
}

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<vector<int> > G(N);
  rep(i, N-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<ll> P(N);
  rep(i, Q) {
    int p, x;
    cin >> p >> x;
    p--;
    P[p] += x;
  }
  dfs(G, P, 0, -1);
  rep(i, N)
    cout << P[i] << ' ';
  cout << endl;
  return 0;
}



Measured memory_bytes: 27392
#![allow(unused_imports)]
#![allow(dead_code)]
use proconio::input;
use proconio::fastout;
use proconio::marker::*;

fn type_of<T>(_: T) -> String{
    let a = std::any::type_name::<T>();
    return a.to_string();
}

#[fastout]
fn main() {
    input! {
        x:i32,a:i32,b:i32,
    }
    println!("{}",(x-a)%b);
}

Measured memory_bytes: 2200
package main

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

func main() {
	// scan_init()
	// c := make([]string, n)
	readLine()
	redcount := 0
	take := readLine()
	c := strings.Split(take,"")
	//　左側に赤い石を集めるかもしくは全てを白い/赤い石にする
	// フェイズとして、
	ts := make([]int,len(take))
	for i:= 0; i<len(take); i++ {
		if take[i] == 'R' {
			redcount ++
			ts[i] = 1
		} else {
			ts[i] = 0
		}
	}
	hidari := 0
	migi := len(c)-1
	output := 0
	for hidari != migi {
		hidarichange := false
		migichange := false
		// fmt.Println("next", hidari,migi, redcount)
		for ; hidari<redcount; hidari++ {
			if ts[hidari] == 0 {
				hidarichange = true
				break
			}
		}
		for ;migi>=redcount; migi-- {
			if ts[migi] == 1 {
				migichange = true
				break
			}
		}
		if !hidarichange || !migichange {
			// fmt.Println(hidari,migi,"last")
			break
		}
		ts[hidari] = 1
		ts[migi] = 0
		output ++
	}
	fmt.Println(output)
}

var sc = bufio.NewScanner(os.Stdin)
var rdr = bufio.NewReaderSize(os.Stdin, 200000)
func readLine() string {
	buf := make([]byte, 0, 200000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}
func scan_init() {
	sc.Split(bufio.ScanWords)
}
func scanInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func scan() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 7280
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    N = i_input()
    k = len(str(N))
    ans = 0
    l = []
    def rec(n,k):
        k += 1
        if int(n) > N:
            return
        if "3" in n and "5" in n and "7" in n:
            l.append(int(n))
        rec(n+"3",k)
        rec(n+"5",k)
        rec(n+"7",k)
    rec("0",0)
    print(len(l))





if __name__=="__main__":
    main()


Measured memory_bytes: 10872
Public Class Program
  Shared Sub Main()
    Dim nw As Long() = Array.ConvertAll(Of String, Long)(Console.ReadLine().Split(" "), AddressOf Long.Parse)
    Dim n As Long = nw(0)
    Dim maxW As Long = nw(1)
    Dim dp(0 To n, 0 To 100000) As Long
    Dim weight(0 To n - 1) As Long
    Dim value(0 To n - 1) As Long
    For i As Long = 0 To n - 1
      Dim wv As Long() = Array.ConvertAll(Of String, Long)(Console.ReadLine().Split(" "), AddressOf Long.Parse)
      weight(i) = wv(0)
      value(i) = wv(1)
    Next
    For i As Long = 1 To n
      For j As Long = 0 To maxW
        dp(0, j) = 0
        If j >= weight(i - 1) Then
          dp(i, j) = Math.Max(value(i - 1), dp(i - 1, j - weight(i - 1)) + value(i - 1))
        End If
        dp(i, j) = Math.Max(dp(i - 1, j), dp(i, j))
      Next
    Next
    Console.WriteLine(dp(n, maxW).ToString())
  End Sub
End Class

Measured memory_bytes: 93936
/*   --------------------
    |       LOSER        |
    |     ~NOOBOSS~      |
     --------------------
*/
#include <bits/stdc++.h>
using namespace std;
#define      mxx                 LLONG_MAX
#define      mnn                 LLONG_MIN
#define      Y()                 cout<< "YES" <<endl
#define      N()                 cout << "NO"<<endl
#define      endl                "\n"
#define      max_3(a,b,c)        max(a, max(b,c))
#define      min_3(a,b,c)        min(a, min(b,c))
#define      gcd(a,b)            __gcd(a,b)
#define      lcm(a,b)           (a*b)/gcd(a,b)
#define      loser               return 0
#define      ll                  long long
#define      PI                  acos(-1)
#define      mem(a,v)            memset(a,v,sizeof(a))
#define      SORT(v)             sort(v.begin(),v.end())
#define      REV(v)              reverse(v.begin(),v.end())
#define      B                   begin()
#define      E                   end()
#define      V                   vector
#define      F                   first
#define      S                   second
#define      PSB                 push_back
#define      MP                  make_pair
#define      flash               cout.flush()
#define      InTheNameOfGod      ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll MOD = 998244353;
constexpr ll mod = 1e9  + 7;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*-----*/
#define bug1(a)  cerr<<a<<endl;
#define bug2(a,b)  cerr<<a<<" "<<b<<endl;
#define bug3(a,b,c)  cerr<<a<<" "<<b<<" "<<c<<endl;
/*----*/
const ll N=2e5+5;
vector<ll> adj[N];
ll power(ll n,ll p){if(p==0) return 1;if(p==1)return n;if(p%2)return power(n,p-1)*n;else{ll x=power(n,p/2);return x*x;}}
ll modpow(ll a,ll b,ll m){ll ans=1;while(b){if(b&1)ans=(ans*a)%m;b/=2;a=(a*a)%m;}return ans;}
ll nsum(ll num){return (num*(num+1))/2;}
void edge (ll u,ll v) {adj[u].PSB(v) ;adj[v].PSB(u);}
/*------------------START---------------------*/


/*-----*/
void solve(){
   ll n;
   string s;
   cin>>s;
   cout<<s;
   ll len=s.length();
   if(s[len-1]=='s') cout<<"es";
   else cout<<"s";



}
/*-----*/
int main(){
   InTheNameOfGod

   ll Test=1;
   //cin>>Test;
   while(Test--){
     solve();
    }
  loser;
}
///////   C O D I N G  I S  L I F E   ///////


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

int main()  
{  
    int h, n;
    cin>>h>>n;
    for(int i=0; i<n; i++) {
        int x;
        cin>>x;
        h-=x;
    }
    if(h<=0) {
        cout<<"Yes";
    } else 
        cout<<"No";
}  

Measured memory_bytes: 256