akhauriyash/Code-Regression huggingface dataset:
// Template
#include <bits/stdc++.h>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003;
template <typename T> inline bool chmin(T& x, const T& y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T& x, const T& y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Mod-Int
constexpr int MOD = 1000000007;
struct ModInt {
    ll val;
    ModInt() = default;
    ModInt(ll x) : val(x % MOD + (x < 0 ? MOD : 0)) {}
    ModInt &operator+= (const ModInt &x) {if ((val += x.val) >= MOD) val -= MOD; return *this;}
    ModInt &operator-= (const ModInt &x) {if ((val -= x.val) < 0) val += MOD; return *this;}
    ModInt &operator*= (const ModInt &x) {(val *= x.val) %= MOD; return *this;}
    ModInt operator+ (const ModInt &x) const {return ModInt(*this) += x;}
    ModInt operator- (const ModInt &x) const {return ModInt(*this) -= x;}
    ModInt operator* (const ModInt &x) const {return ModInt(*this) *= x;}
    ModInt pow(ll t) const {
        if (!t) return ModInt(1);
        ModInt m = pow(t / 2);
        m *= m;
        if (t & 1) m *= *this;
        return m;
    }
    ModInt inv() const {return pow(MOD - 2);}
    ModInt &operator/= (const ModInt &x) {return *this *= x.inv();}
    ModInt operator/ (const ModInt &x) const {return ModInt(*this) /= x;}
    friend istream &operator>> (istream &is, ModInt &x) {is >> x.val; return is;}
    friend ostream &operator<< (ostream &os, const ModInt &x) {os << x.val; return os;}
};

// Main
int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        g[x].push_back(y); g[y].push_back(x);
    }
    
    auto dfs = [&](auto f, int v, int p) -> pair<ModInt, ModInt> {
        pair<ModInt, ModInt> res(ModInt(1), ModInt(1));
        for (int u: g[v]) {
            if (u == p) continue;
            pair<ModInt, ModInt> x = f(f, u, v);
            res.first *= (x.first + x.second);
            res.second *= x.first;
        }
        return res;
    };
    pair<ModInt, ModInt> ans = dfs(dfs, 0, -1);
    cout << ans.first + ans.second << "\n";
}


Measured memory_bytes: 15456
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
int num[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
bool uru(int checkyear){if(checkyear%4==0){if(checkyear%100!=0||checkyear%400==0)return true;}return false;}
int gcd( int x, int y ){return y ? gcd(y, x%y) : x;}
bool pairCompare(const pairint& firstElof, const pairint& secondElof)
{
  if(firstElof.second!= secondElof.second)    return firstElof.second> secondElof.second;
  else return firstElof.first< secondElof.first;
}
signed main() {
int x=0,y=0,z=0,w=0,n=0,m=0;
string s;
std::cin >> x;
std::vector<int> v(x);
std::vector<int> v1(x);
std::vector<int> v2(x-1);

rep(i,2){
  Rep(j,x){
    if(i==0)std::cin >> v[j];
    else if(i==1){
      std::cin >> y;
      z+=y;
    }
  }
}
rep(i,x-1)std::cin >> v2[i];
rep(i,x-1){
  if(v[i+1]==v[i]+1)z+=v2[v[i]-1];
}
std::cout << z << '\n';
}


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

int main()
{

    char aa[100100];
    char bb[100100];
    int dp[100100];
    int dp1[100100];
    int a1,a2,a3,a4;
    char ans1,ans2;
    scanf("%s%s",&aa,&bb);
    dp[0]=0;
    for(int i=0;aa[i];i++)
    {
        if(dp[i]==0)
        {
            dp[i+1]=aa[i]-'A'+1;
        }
        else if(dp[i]==1)
        {
            if(aa[i]=='B')
            {
                dp[i+1]=0;
            }
            else
            {
                 dp[i+1]=2;
            }
        }
        else
        {
             if(aa[i]=='B')
            {
                dp[i+1]=1;
            }
            else
            {
                 dp[i+1]=0;
            }
        }
    }
     dp1[0]=0;
    for(int i=0;bb[i];i++)
    {
        if(dp1[i]==0)
        {
            dp1[i+1]=bb[i]-'A'+1;
        }
        else if(dp1[i]==1)
        {
            if(bb[i]=='B')
            {
                dp1[i+1]=0;
            }
            else
            {
                 dp1[i+1]=2;
            }
        }
        else
        {
             if(bb[i]=='B')
            {
                dp1[i+1]=1;
            }
            else
            {
                 dp1[i+1]=0;
            }
        }
    }
    int n;
    scanf("%d",&n);
    int flag=0;
    for(int ii=0; ii<n; ii++)
    {
        scanf("%d%d%d%d",&a1,&a2,&a3,&a4);
       if(dp[a1-1]==dp[a2])
       {
           ans1='e';
          // flag=1;
       }
       else if(dp[a1-1]==0&&dp[a2]!=0)
       {
           ans1=dp[a2]-1+'A';
          // flag=2;
       }
       else if(dp[a2]==0)
       {
           if(dp[a1-1]==1)
           {
               ans1='B';
            //   flag=3;
           }
           else
           {
              ans1='A';
              //flag=4;
           }
       }
       else
       {
           ans1=dp[a1-1]-1+'A';
         //  flag=5;
       }
        if(dp1[a3-1]==dp1[a4])
       {
           ans2='e';
           flag=2;
       }
       else if(dp1[a3-1]==0&&dp1[a4]!=0)
       {
           ans2=dp1[a4]-1+'A';
           flag=3;
       }
       else if(dp1[a4]==0)
       {
           if(dp1[a3-1]==1)
           {
               ans2='B';
               flag=4;
           }
           else
           {
               ans2='A';
               flag=5;
           }
       }
       else
       {
           ans2=dp1[a3-1]-1+'A';
           flag=6;
       }
     //  printf("%d\n",flag);
       //printf("%c %c\n",ans1,ans2);
              if(ans1==ans2)
       {
           printf("YES\n");
       }
       else
       {
           printf("NO\n");
       }
    }
    return 0;
}


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

int main()
{
    int k, a, b;
    cin >> k >> a >> b;
    if (b / k > (a-1) / k)
    {
        cout << "OK" << endl;
    }
    else
    {
        cout << "NG" << endl;
    }
    return 0;
}

Measured memory_bytes: 3568
#include <iostream>

int main(){
   int N, L;
   std::cin >> N >> L;

   int ans = 0;
   int min = 100000000;
   int index = -1;
   for(int i=1; i<=N; ++i){
      ans += L + i - 1;
      if(min>abs(L+i-1)){
	 min = abs(L+i-1);
	 index = i;
      }
   }
   std::cout << ans - (L+index-1) << std::endl;

   return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  AC
//
//  Created by makinofuya on 2019/07/08.
//  Copyright © 2019 makinofuya. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

typedef long long ll;
using namespace std;
#define mod 1000000007

int main(){
    int n;cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int max1=0,max2=0;
    int m_num1=-1,m_num2=-1;
    for(int i=0;i<n;i++){
        if(max1<a[i]){
            max2=max1;
            max1=a[i];
            m_num2=m_num1;
            m_num1=i;
        }
        else if(max2<a[i]){
            max2=a[i];
            m_num2=i;
        }
    }
    int max;
    for(int i=0;i<n;i++){
        if(m_num1==i){
            max=max2;
        }
        else{
            max=max1;
        }
        cout << max << endl;
    }
    return 0;
}



Measured memory_bytes: 2432
#include<iostream>
#include<climits>
#include<cassert>
#include<algorithm>
#include<cassert>
#include<map>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

int solve(vector<int> &a,int st,vector<int> &b){
  int p = 0;
  int cnt = 0;
  while(p < a.size() && st < b.size()){
    if (a[p] == b[st])cnt++,p++,st++;
    else p++;
  }
  return cnt;
}

main(){
  int n,m;
  while(cin>>n>>m && n){
    vector<int> a(n),b(m);
    rep(i,n)cin>>a[i];
    rep(i,m)cin>>b[i];
    int ans = 0;
    rep(i,m){
      ans = max(ans,solve(a,i,b));
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 904
#include <iostream>
#include <set>
using namespace std;
int cnt;
long long bsum, lsum = 0, rsum = 0;
bool isodd = true;
multiset<int> lft, rit;
void lins(int x){
    lft.insert(x);
    lsum += x;
}
void rins(int x){
    rit.insert(x);
    rsum += x;
}
void update(int a, int b){
    if(isodd){
        if(a < cnt){
            lins(a);
            rins(cnt);
        }else{
            lins(cnt);
            rins(a);
        }
    }else{
        auto lmax = lft.end(); lmax--;
        auto rmin = rit.begin();
        if(a < *lmax){
            lins(a);
            auto itr = lft.end(); itr--;
            lsum -= *itr;
            cnt = *itr;
            lft.erase(itr);
        }else{
            rins(a);
            auto itr = rit.begin();
            rsum -= *itr;
            cnt = *itr;
            rit.erase(itr);
        }
    }
    isodd = !isodd;
    bsum += b;
}
void ans(int &x, long long &fmin){
    if(isodd){
        x = cnt;
        fmin = bsum - lsum + rsum;
    }else{
        auto itr = lft.end(); itr--;
        x = *itr;
        fmin = bsum - lsum + rsum;
    }
}
int main() {
    int q, a, b, c;
    cin >> q;
    cin >> c >> cnt >> bsum; // 
    lft.insert(-1e9);
    rit.insert(1e9);
    for(int i=1;i<q;i++){
        cin >> c;
        if(c == 1){
            cin >> a >> b;
            update(a, b);
        }else{
            int x;
            long long fmin;
            ans(x, fmin);
            cout << x << " " << fmin << endl;
        }
    }
	return 0;
}

Measured memory_bytes: 9600
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int d = in.nextInt();
        System.out.println(a * b > c * d ? a * b : c * d);
    }
}


Measured memory_bytes: 23252
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
typedef pair<int, int> P;
int a[214514];
int rwa[214514];
signed main() {
	int n; cin >> n; rep(i, n)cin >> a[i];

	for (int i = 0; i < n; i++) {
		rwa[i + 1] = a[i];
	}
	rep(i, n)rwa[i + 1] += rwa[i];
	map<int, int>M;
	rep(i, n+1)M[rwa[i]]++;
	int ans = 0;
	for (auto itr = M.begin(); itr != M.end(); itr++) {
		int b = itr->second;
		ans += b*(b - 1)/2;
	}
	cout << ans << endl;
}

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

#define int long long

int n,m,a[200005],b[200005];
int ans;

bool cmp(int x,int y)
{
	return x>y;
}

bool legal(int mx)
{
	int s=0;
	for(int i=1;i<=n;i++)
	{
		int x=a[i]*b[i];
		if(x>mx)
			s += a[i]-mx/b[i];
	}
	return s<=m;
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;cin>>a[i++]);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;cin>>b[i++]);
	sort(b+1,b+1+n);
	int l=0,r=a[1]*b[n];
	while(l<=r)
	{
		int mid=l+r>>1;
		if(legal(mid))
		{
			ans = mid;
			r = mid-1;
		}
		else
			l = mid+1;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
int N,M,Q;
int q[55][5];
int a[15];
ll int fn(int p,int val)
{
    if(val<=0)
    return 0;
    if(p<0)
    return 0;
    int x,y,i,b,c,d,mn;
    x=0;
    y=0;
    if(val>1)
    x=fn(p,val-1);
    if(p>0)
    y=fn(p-1,val);
    a[p]=val;
    int flag=1;
    for(i=0;i<N-1;i++)
    {
        if(a[i]>a[i+1])
        {
            flag=0;
            break;
        }
    }
    if(flag==1)
    {
        ll int sum=0;
        for(i=0;i<Q;i++)
        {
            mn=q[i][0];
            b=q[i][1];
            c=q[i][2];
            d=q[i][3];
            mn-=1;
            b-=1;
            if((a[b]-a[mn])==c)
            {
                sum+=d;                    
            }
        }
        return (x>=y?x:y)>=(sum>=fn(p-1,val-1)?sum:fn(p-1,val-1))?(x>=y?x:y):(sum>=fn(p-1,val-1)?sum:fn(p-1,val-1));
    }
    else
    {
        return (x>=y?x:y)>=(fn(p-1,val-1))?(x>=y?x:y):(fn(p-1,val-1));
    }
}
int main()
{
    int i,j;
    cin>>N>>M>>Q;
    for(i=0;i<Q;i++)
    {
        for(j=0;j<4;j++)
        cin>>q[i][j];
    }
    for(i=0;i<N;i++)
    a[i]=M;
    cout<<fn(N-1,M)<<endl;
    return 0;
}

Measured memory_bytes: 3612
#include <math.h>
#include <stdio.h>
typedef long long ll;
ll max(ll x, ll y) { return x > y ? x : y; }
ll dig(ll n) { return log10(n) + 1; }
ll f(ll a, ll b) { return max(dig(a), dig(b)); }
int main() {
	ll n, ans, min = 10;
	scanf("%lld", &n);
	for (ll i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			// printf("%lld %lld\n", i, n / i);
			ans = f(i, n / i);
		}
		if (ans < min) {
			min = ans;
		}
	}
	printf("%lld\n", min);
	return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var n = long.Parse(Console.ReadLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = long.Parse(Console.ReadLine());
        }

        var ans = a.Sum();
        if (ans % 10 == 0)
        {
            ans = 0;
            Array.Sort(a);
            for (int i = 0; i < n; i++)
            {
                if ((a.Sum() - a[i]) % 10 != 0)
                {
                    ans = Math.Max(ans, a.Sum() - a[i]);
                }

            }
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13396
function Main(input){
  var N = input.split("\n")[0];
  N = parseInt(N,10);
  var d = input.split("\n")[1].split(" ");
  var d = d.sort((a,b)=>{
    return b - a; 
  });

  var stnNum = (d.length/2)-1;
  var stn = d[stnNum];
  var stnadd = d[stnNum+1];
  stn = parseInt(stn,10);

  console.log(Math.abs(stn-stnadd));

}  

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 18108
N, M = map(int, input().split())
A = list(map(int, input().split()))

total = sum(A)

ans = 0
for i in range(N):
    tmp = total * (1 / (4 * M))
    if A[i] >= tmp:
        ans += 1

if ans >= M:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)	
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define double long double
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = pow(10,18);
ll modulo = 998244353  ;
#define MAX (int)(pow(10,6)+ 10)

ll   arr[MAX];
ll  last[MAX]; // last time we saw number i
ll    nd[MAX]; // if we start at this index what number is going to be in the start of sequence at the end

void deal(){
	ll n,k;
	cin>>n>>k;
	fori(MAX)
		last[i] = -1;
	fori(n)
		cin>>arr[i];
	nd[n]  = -1;
	for(ll i = n-1; i>-1; i--){
		ll hd = arr[i];
		if(last[hd] == -1)
			nd[i] = hd;
		else
			nd[i] = nd[last[hd]+1];
		last[hd] = i;
//		cout<<"if we start at "<<i<<" we ll  end up with "<<nd[i]<<endl;
	}
	
	vector<ll> starts;
	ll st = 0;
	while(1){
		starts.pb(st);
		ll el = nd[st];
//		cout<<st<<" "<<el<<endl;
		if(el == -1)
			break;
		st = last[el]+1;
		if(st == n){
			starts.pb(n);
			break;
		}
	}
/*	cout<<"starts "<<starts.size()<<endl;
	for(auto el : starts)
		cout<<el<<" ";
	cout<<endl; */ 
	--k;
	k %= ((ll)starts.size());
	vector<bool> seen(MAX,0 );
	deque<ll> all;
	st = starts[k];
	for(st; st<n; ++st){
		if(seen[arr[st]]){
			while(all.back() != arr[st])
				seen[all.back()] = 0, all.pop_back();
			seen[all.back()] = 0;
			all.pop_back();
		}
		else
			all.pb(arr[st]), seen[arr[st]] = 1;
	}
	fori(all.size())
		cout<<all[i]<<' ';
	cout<<'\n';
	
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

/*

4 6
4 8 7 8
1 2 4
2 1 2 2
1 3 4
2 1 1 8
1 1 3
1 1 4

acacabbbbbbbacc

cccbbbaaa
*/

Measured memory_bytes: 18672
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rrep(i,n) for(int i=1; i<=(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller(char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int H,W;
    cin>>H>>W;
    vector<vc> a(H,vc(W));
    rep(i,H) {
        rep(j,W) {
            cin>>a[i][j];
        }
    }
    vector<vector<bool>> ok(H,vector<bool>(W,true));
    rep(i,W) {
        bool check=true;
        rep(j,H) {
            if(a[j][i]=='#') check=false;
        }
        if(check) {
            rep(j,H) ok[j][i]=false;
        }
        check=true;
    }
    int n=0;
    rep(i,W) {
        if(ok[0][i]==true) n++;
    }
    rep(i,H) {
        bool check=true;
        rep(j,W) {
            if(a[i][j]=='#') check=false;
        }
        if(check) {
            rep(j,W) ok[i][j]=false;
        }
        check=true;
    }
    vc ans;
    rep(i,H) {
        bool check=true;
        rep(j,W) {
            if(ok[i][j]==false) {
                check=false;
                continue;
            }
            char c=a[i][j];
            ans.pb(c);
        }
        check=true;
    }
    rep(i,ans.size()) {
        if(i!=0&&i%n==0) cout<<endl;
        cout<<ans[i];
    }
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d", $n);
$m = floor(log($n + 0.1, 9));
for ($p = 0; $p <= $m; $p++) {
	$es[] = 9 ** $p;
}
$m = floor(log($n + 0.1, 6));
for ($p = 1; $p <= $m; $p++) {
	$es[] = 6 ** $p;
}
rsort($es);
$q[0] = 0;
while (1) {
	foreach ($q as $i => $t) {
		$t++;
		foreach ($es as $e) {
			$x = $i + $e;
			if ($x > $n || isset($f[$x])) continue;
			if ($x == $n) exit("$t");
			$q[$x] = $t;
			$f[$x] = 1;
		}
		unset($q[$i]);
	}
}

Measured memory_bytes: 13048
// Marcin Knapik
#include<bits/stdc++.h>
 
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
//#include <ext/pb_ds/assoc_container.hpp> // order_of_key
//#include <ext/pb_ds/tree_policy.hpp> // find by order
//using namespace __gnu_pbds; 
//#define ordered_set tree< int , null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>  
 
// const ll MAX_LL = 0xFFFFFFFFFFFFFFFF;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<ull>(a, b)(rng)
#define losuj_real(a, b) uniform_real_distribution<long double>(a, b)(rng)
 
typedef long double             ld;
typedef long long               ll;
typedef unsigned long long      ull;
typedef pair<ll, ll>            pll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vector<ii>>      vvii;
typedef vector< ll >            vll;
typedef vector< pll >           vpll;
 
#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define f                       first
#define s                       second
#define rr "\e[31m "
#define bb "\e[m "
 
template <class T> inline bool setmin(T &a, T b){if (a > b)return a = b, 1;return 0;}
template <class T> inline bool setmax(T &a, T b){if (a < b)return a = b, 1;return 0;}
 
template<class T> inline  T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> inline  T russian(T a, T b, T mod) {ll res = 0; while(b){if(b&1) res = (res + a)%mod; a = (a+a)%mod; b>>=1;}return res;}
template<class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<class T> inline  T gcd(T a, T b) { while (b)swap(a %= b, b); return a; }
 
const ll INF = 1e9 + 7;
const ll mod = 998244353;
const ll N = 1e6+7;
const ll T = 1<<20;
const ll BIG_INF = 1e18 + 7;
 
ll n, m, k;

ll dp[1007][20007];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	#define PIII pair < pair <int, int>, int >
	vector < PIII > tab;
	cin >> n;
	tab.pb({{0, 0}, 0});
	 
	for(int i = 0; i < n; i++){
		int a, b, c;
		cin >> a >> b >> c;

		tab.pb({{a, b}, c});
	}

	sort(tab.begin()+1, tab.end(), [](const PIII & a, const PIII & b) {
		return a.f.f + a.f.s < b.f.f + b.f.s;
	});


	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= 20000; j++){
			if(j >= tab[i].f.f)
				dp[i][j] = max({dp[i][j-1], dp[i-1][j], dp[i-1][min(j - tab[i].f.f, tab[i].f.s)] + tab[i].s});
			else
				dp[i][j] = max(dp[i][max(j-1, 0)], dp[i-1][j]);
		}
	cout << dp[n][20000] << '\n';
}	

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    int alice = 0, bob = 0;
    rep(i, n) {
        if (i%2==0) alice += a[n-i-1];
        else bob += a[n-i-1];
    }
    cout << alice - bob << endl;
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}


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

    ll N, C;
    cin >> N >> C;
    vector<vector<pll>> R(C);
    REP(i, N){
    	ll s, t, c;
    	cin >> s >> t >> c;
    	c--;
    	R[c].push_back({s, t});
    }
    vector<vector<ll>> T(C, vector<ll>(202020, 0));

    REP(i, C){
    	REP(j, R[i].size()){
    		ll s = R[i][j].first;
    		ll t = R[i][j].second;
	    	T[i][2*s-1]++;
	    	T[i][2*t]--;
	    }
	    REP(j, 202020-1) T[i][j+1] += T[i][j];
    }
    ll ma = 0;
    REP(i, 202020){
    	ll tmp = 0;
    	REP(j, C) tmp += min(T[j][i], 1ll);
    	chmax(ma, tmp);
    }
    cout << ma << endl;
    return 0;
}

Measured memory_bytes: 51840
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  //入力部開始
  int N, D;
  cin >>N >>D;
  vector<vector<int>> X(N,vector<int>(D));
  for(int i = 0;i<N;i++){
    for(int t = 0;t<D;t++){
      cin >>X.at(i).at(t);
    }
  }
  //入力部終了
  int ans = 0;
  for(int i = 0;i<=N-1;i++){
    for(int t = i+1;t<N;t++){
      int distance = 0;
      for(int k = 0;k<D;k++){
        distance +=(X.at(i).at(k)-X.at(t).at(k))*(X.at(i).at(k)-X.at(t).at(k));
      }
      for(int k = 0;k<127;k++){
        if(k*k==distance){
          ans++;
          break;
        }
      }
    }
  }
  cout <<ans <<endl;

}
      
    
  

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int num[n];
    for (int i = 0;i < n;i++){
        cin >> num[i];
    }
    for (int j = (n-1);j >= 0;j--){
        if(j != n - 1){
            cout << " ";
        }
        cout << num[j];
    }
    cout << endl;
    
    return 0;
}

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

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);

    char s;
    int ans = 0;
    for(int i = 0; i < 3; i++) {
        cin >> s;
        if(s == '7') ans = 1;
    }

    if(ans) cout << "Yes\n";
    else cout << "No\n";


    return 0;
}

Measured memory_bytes: 3652
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func isPrime(n int) bool {
	if n == 1 {
		return false
	}
	if n == 2 {
		return true
	}
	if n%2 == 0 {
		return false
	}

	max := int(math.Sqrt(float64(n)))
	for i := 3; i <= max; i += 2 {
		if n%i == 0 {
			return false
		}
	}
	return true
}

func main() {
	n := scanInt()

	cnt := 0
	for i := 0; i < n; i++ {
		if isPrime(scanInt()) {
			cnt++
		}
	}

	fmt.Println(cnt)
}



Measured memory_bytes: 1148
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
struct Palace {
  int n,H;
  double temp,dist;
  Palace(int n, int H): n(n), H(H) {}
  bool operator<(const Palace& p) { return dist < p.dist; }
};
int N,T,A;
vector<Palace> palaces;
int main() {
  cin>>N>>T>>A;
  for(int n=1;n<=N;++n) {
    int H;cin>>H;
    palaces.push_back(Palace(n, H));
  }
  for(auto& p:palaces) {
    p.temp = T - p.H * 0.006;
    p.dist = fabs(p.temp - A);
  }
  sort(palaces.begin(), palaces.end());
  printf("%d\n", palaces.front().n);
}

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

int main() {
    int N;
    cin >> N;
    vector<int> data(N);
    for(int i=0; i<N; i++)  cin >> data.at(i);

    sort(data.begin(),data.end());
    reverse(data.begin(),data.end());

    if(data.at(0) != data.at(N-1)){
        cout << data.at(0) - data.at(N-1) <<endl;
    }
       else cout << 0 <<endl;
    }
    


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;

struct point {
  long double x, y;
};

int main() {
  point p1, p2, p, x;
  int q;
  cin >> p1.x >> p1.y >> p2.x >> p2.y >> q;
  p2.x -= p1.x;
  p2.y -= p1.y;
  rep(i, q) {
    cin >> p.x >> p.y;
    p.x -= p1.x;
    p.y -= p1.y;
    x.x = (p.x * p2.x + p.y * p2.y) * p2.x / (p2.x * p2.x + p2.y * p2.y) + p1.x;
    x.y = (p.x * p2.x + p.y * p2.y) * p2.y / (p2.x * p2.x + p2.y * p2.y) + p1.y;
    cout << setprecision(15) << x.x << " " << x.y << endl;
  }


  
  return 0;
}


Measured memory_bytes: 3296
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main() {
    ll a, b, pa, pb;
    cin >> a >> b;
    a--;
    pa = 64 -__builtin_clzll(a);
    pb = 64 -__builtin_clzll(b);

    map<ll, ll> mp, mp2;
    if (a >= 0) {
        for (ll i = pa; i >= 0; i--) {
            ll t = (1LL << (i + 1));
            mp[i] = ((a + 1) / t) * (t / 2) + max(0LL, ((a + 1) % t) - (t / 2));
        }
    }

    for (ll i = pb; i >= 0; i--) {
        ll t = (1LL << (i + 1));
        mp2[i] = ((b + 1) / t) * (t / 2) + max(0LL, ((b + 1) % t) - (t / 2));
    }

    ll ans = 0LL;
    for (int i = pb; i >= 0; i--) {
        if ((mp2[i] - ((a < 0) ? 0 : mp[i])) % 2 == 1)ans += (1LL << i);
    }
    cout << ans << endl;

    return 0;
}

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


#define all(v)           ((v).begin()), ((v).end())
#define sz size()
#define clr(v,d)         memset(v,d,sizeof(v))
#define lp(i, n)         for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)     for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)     for(int i=(j);i>=(int)(n);--i)
#define sci(a)	scanf("%d",&a)
#define scll(a)	scanf("%lld",&a)
#define scii(a, b)	scanf("%d%d",&a, &b)
#define pri(a)	printf("%d\n",a)
#define prll(a)	printf("%lld\n",a)
	

const int maxn = 300500;

typedef long long ll;

typedef pair<int, int> pii;

int dp[maxn][3];
int a[maxn][3];


int main() {
	//freopen("in.in", "r", stdin);	
	int n; sci(n);
	lp(i, n) lp(j, 3) sci(a[i+1][j]);
	lpi(i, 1, n + 1) lp(j, 3) lp(k, 3) if (k != j) {
		dp[i][k] = max(dp[i][k], dp[i - 1][j] + a[i][k]);
	}
	pri(max(dp[n][0], max(dp[n][1], dp[n][2])));
}

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli t;
lli a,b,c,d;

lli gcd(lli x,lli y){
  lli z;
  while(true){
    z = x%y;
    if(z == 0) return y;
    x = y;
    y = z;
  }
}

bool solve(lli a,lli b,lli c,lli d){
  if(a < b) return false;
  if(d < b) return false;
  if(c >= b) return true;
  lli g = gcd(d,b);
  lli alpha;
  if((b-a+(a/b)*b)%g == 0) alpha = (b-a-1+(a/b)*b)/g;
  else alpha = (b-a+(a/b)*b)/g;
  if(alpha*g > (c-a+(a/b)*b)) return false;
  else return true;
}

int main(){
  cin >> t;
  for(lli i = 0;i < t;i++){
    cin >> a >> b >> c >> d;
    cout << (solve(a,b,c,d) ? "Yes" : "No") << endl;
  }
}


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

long long divide(long long a){
  long long div = 0;
  while(a % 2 == 0){
    div++;
    a /= 2;
  }
  return div;
}

int main(void){
  int N;
  long long sum = 0;
  cin >> N;
  vector<long long> a(N);
  for(int i = 0; i < N; i++){
    cin >> a[i];
    sum += divide(a[i]);
  }
  cout << sum;
  return 0; 
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    mp[a] += b;
  }
  long long ans = 0;
  for (auto e : mp) {
    int u = min(m, e.second);
    m -= u;
    ans += (long long)u * e.first;
  }
  cout << ans << endl;
}

Measured memory_bytes: 5632
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

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

	cin >> N;
	set<string>st;
	while (N--) {
		string s;
		cin >> s;
		st.insert(s);
	}
	cout << st.size() << endl;
}

Measured memory_bytes: 19276
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    rrep(i, n - 1) {
        rrep(j, k) {
            if(i - j < 0) break;
            chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
        }
    }
   
    cout << dp[n - 1] << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <chrono>
#include <sstream>
#include <iomanip>
#define INF 1 << 30
#define MOD 1000000007;
#define pi 3.14159265358979
#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define D(x) cout << x << endl
#define d(x) cout << x
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x, y) make_pair((x), (y))
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
static const int dx[] = {0, 0, 1, -1};
static const int dy[] = {-1, 1, 0, 0};

int main() { 
  ll n, c, k;
  cin >> n >> c >> k;
  ll t[101010];
  for (int i = 0; i < n; i++) {
    cin >> t[i];
  }

  sort(t, t + n);

  ll ans = 0;
  bool flag = true;
  int limit, cnt;
  for (int i = 0; i < n; i++) {
    if (flag) {
      int ft = t[i];
      limit = ft + k;
      cnt = 1;
      ans++;
      flag = false;
    } else {
      cnt++;
      if (cnt > c || t[i] > limit) {
        flag = true;
        i--;
      }
    }
  }

  D(ans);
  return 0;
}


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

ll power(ll x, ll y, ll p)  
{  
    ll res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  

void solve(){
    ll n;
    cin >> n;
    if(n == 1){
        cout << 0 << "\n";
        return;
    }
    ll a1 = power(10,n,M);
    ll a2 = (2*power(9,n,M))%M;
    ll b1 = power(8,n,M);
    ll ans;
    if(a1 - a2 + b1 < 0) ans = (M + a1 - a2 + b1)%M;
    else ans = (a1 - a2 + b1)%M;
    cout << ans << "\n";

    

}


int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ll q;
    q=1;
    // cin>>q;
    while(q--) solve();


    return 0;
}


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

int N;
int MOD = 1.0e9 + 7;

int main() {
    cin >> N;
    
    ll fib[N+1];
    fib[0] = 1;
    for (int i = 1; i <= N; i++) {
        fib[i] = (fib[i-1] * i) % MOD;
    }

    cout << fib[N] << endl;

    return 0;
}


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

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

const int MAX = 2000000 ;

//宣言するときはstaticをつけて静的変数にするかグローバル変数として宣言
class SGT{
public :
	int n ;
//	d変数は単位元、計算の邪魔をしない値に設定する、INFや0など
	ll d = INF ;
	ll num[MAX] ;

	void init(vector<ll> &a){
		n = 1 ;
		while(a.size()>n) n *= 2 ;
		for(int i=0;i<n;i++){
			if(i<a.size()) num[n-1+i] = a.at(i) ;
			else num[n-1+i] = d ;
		}
		for(int i=n-2;i>=0;i--){
			num[i] = min(num[i*2+1],num[i*2+2]) ;
		}
	}

//	内容次第でwhile内の計算式を書き換える
	void update(int i,ll a){
		i += n-1 ;
		num[i] = a ;
		while(i>0){
			i = (i-1)/2 ;
			num[i] = min(num[i*2+1],num[i*2+2]) ;
		}
	}

	ll query(int a,int b,int l,int r,int now){
		if(r<=a||b<=l) return d ;
		if(a<=l&&r<=b) return num[now] ;
		ll r1 = query(a,b,l,(l+r)/2,now*2+1) ;
		ll r2 = query(a,b,(l+r)/2,r,now*2+2) ;
		return min(r1,r2) ;
	}
};

int main(){
	ll n,m ;
	cin >> n >> m ;
	vector<pair<pair<ll,ll>,ll>> q(m) ;
	for(int i=0;i<m;i++){
		ll l,r,c ;
		cin >> l >> r >> c ;
		l-- ; r-- ;
		q.at(i).first.first = r ;
		q.at(i).first.second = l ;
		q.at(i).second = c ;
	}
	sort(all(q)) ;
	static SGT sgt ;
	vll def(n,INF) ;
	def.at(0) = 0 ;
	sgt.init(def) ;
	int pos = 0 ;
	for(int i=1;i<n;i++){
		ll mn = INF ;
		while(pos<m&&q.at(pos).first.first==i){
			mn = min(mn,sgt.query(q.at(pos).first.second,q.at(pos).first.first+1,0,sgt.n,0)+q.at(pos).second) ;
			pos++ ;
		}
		sgt.update(i,mn) ;
	}
	cout << (sgt.num[n-1+sgt.n-1]==INF?-1:sgt.num[n-1+sgt.n-1]) << endl ;
//	for(int i=0;i<n;i++) cout << sgt.num[i+sgt.n-1] << endl ;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int M, W;
int A[15], B[15];
int dp[12][1<<12];

int f(int x, int y){
    int diff = std::abs(x - y);

    return diff * (diff - 30) * (diff - 30);
}

int rec(int idx, int s){
    if(idx == M){
        return 0;
    }

    if(dp[idx][s] != -1){
        return dp[idx][s];
    }

    int mx = 0;

    for(int i=0;i<W;++i){
        if(s >> i & 1){
            continue;
        }

        mx = std::max(mx, f(A[idx], B[i]) + rec(idx + 1, s | (1 << i)));
    }

    return dp[idx][s] = mx;
}

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

    while(true){
        std::cin >> M >> W;

        if(M == 0){
            break;
        }

        for(int i=0;i<M;++i){
            std::cin >> A[i];
        }

        for(int i=0;i<W;++i){
            std::cin >> B[i];
        }

        if(M > W){
            std::swap(M, W);
            std::swap(A, B);
        }
    
        memset(dp, -1, sizeof(dp));

        int mx = rec(0, 0);
        std::cout << mx << std::endl;
    }
}



Measured memory_bytes: 3332
#include <stdio.h>

int main()
{
	char A[101], B[101];
	scanf("%s", A);
	scanf("%s", B);
	
	int la, lb, i, flag = 3;
	for (la = 0; A[la] != 0; la++);
	for (lb = 0; B[lb] != 0; lb++);
	
	if (la > lb) flag = 1;
	else if (la < lb) flag = 2;
	else {
		for (i = 0; i < la; i++) {
			if (A[i] > B[i]) {
				flag = 1;
				break;
			} else if (A[i] < B[i]) {
				flag = 2;
				break;
			}
		}
	}
	
	if (flag == 1) printf("GREATER\n");
	else if (flag == 2) printf("LESS\n");
	else printf("EQUAL\n");
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define moder (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/

int n, m;
string s;
pair<char, char>p[214514];
int ans;
signed main() {
	cin >> n >> m >> s;
	rep(i, m) {
		cin >> p[i].first >> p[i].second;
	}
	int memo1 = -1;
	for (int i = m - 1; i >= 0; i--) {
		if (s[memo1 + 1] == p[i].first&&p[i].second == 'L') {
			memo1++;
		}
		if (memo1 != -1 && s[memo1] == p[i].first&&p[i].second == 'R') {
			memo1--;
		}
	}
	int memo = n;
	for (int i = m - 1; i >= 0; i--) {
		if (s[memo - 1] == p[i].first&&p[i].second == 'R') {
			memo--;
		}
		if (memo != n && s[memo] == p[i].first&&p[i].second == 'L') {
			memo++;
		}
	}
	cout << memo - memo1 - 1 << endl;
}


Measured memory_bytes: 900
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include <cmath>
using namespace std;

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

static const int MAX = 100005;
static const int INFTY = (1 << 20);

int K;
vector<pair<int, int>> adj[MAX];
int dist[MAX];
int ans;

void dijkstra(int s) {
	priority_queue<pair<int, int>> PQ;
	int color[MAX];

	REP(i, K) {
		color[i] = 0;
	}

	dist[s] = 0;
	PQ.push(make_pair(0, s));
	color[s] = 1;

	while (!PQ.empty()) {
		pair<int, int> f = PQ.top(); PQ.pop();
		int u = f.second;
		color[u] = 2;

		//最小値を取り出し，それが最短でなければ無視
		if (dist[u] < f.first*(-1)) continue;

		REP(j, adj[u].size()) {
			int v = adj[u][j].first;
			if (color[v] == 2) continue;
			if (dist[v] > dist[u] + adj[u][j].second) {
				dist[v] = dist[u] + adj[u][j].second;
				PQ.push(make_pair(dist[v] * (-1), v));
				color[v] = 1;
			}
		}
	}
}

signed main() {
	cin >> K;

	//1足す操作は桁和も+1
	for (int i = 0; i < K; i++) {
		adj[i].push_back(make_pair((i + 1) % K, 1));
	}
	//10倍する操作は桁和+0
	for (int i = 0; i < K; i++) {
		adj[i].push_back(make_pair((i * 10) % K, 0));
	}

	REP(i, K) dist[i] = INFTY;
	
	dijkstra(1);
	ans = dist[0] + 1;

	//REP(i, K) {
	//	cout << i << " " << (dist[i] == INFTY ? -1 : dist[i]) << endl;
	//}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7164
#include<bits/stdc++.h>
#define ll long long
const ll P=1e9+7;
const ll N=200010,M=4010,maxn=40010;
ll n,a[N],b[N],dp[M][M];
ll fac[maxn],inv[maxn];
ll pow(ll x,ll y){
    x%=P;
    ll ans=1;
    while(y){
        if (y&1) ans=ans*x%P;
        x=x*x%P;
        y>>=1;
    }
    return ans%P;
}
void Get_fac(ll n){
    fac[1]=1;
    for(ll i=2; i<=n; i++)
        fac[i]=i*fac[i-1]%P;
}
void Get_inv(ll n){
    inv[n]=pow(fac[n],P-2);
    for (ll i=n-1; i>=0; i--)
        inv[i]=inv[i+1]*(i+1)%P;
}
ll C(ll x,ll y){
    return fac[x]*inv[y]%P*inv[x-y]%P;
}
int main(){
    Get_fac(maxn-10);
    Get_inv(maxn-10);
    scanf("%lld",&n);
    for (ll i=1; i<=n; i++){
        scanf("%lld%lld",&a[i],&b[i]);
        dp[2001-a[i]][2001-b[i]]++;
    }
    for (ll i=1; i<=4001; i++)
        for (ll j=1; j<=4001; j++){
            dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i][j-1])%P;
        }
    ll ans=0;
    for (ll i=1; i<=n; i++)
        ans=(ans+dp[2001+a[i]][2001+b[i]])%P;
    for (ll i=1; i<=n; i++)
        ans=(ans-C(a[i]+a[i]+b[i]+b[i],a[i]+a[i])+P)%P;
    printf("%lld\n",ans*inv[2]%P);
}


Measured memory_bytes: 132864
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int a,b,c;
 cin>>a>>b>>c;
 
 if(abs(a-b) < abs(a-c)){
 	cout<<"A"<<endl;
 }
 else {
 	cout<<"B"<<endl;
 }
  
 return 0;
 }

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);

    i32 n; cin >> n;
    vl a(n); rep(i,n) cin >> a[i];

    i32 length = 0;
    for(auto val : a) length += val;
    i64 ans = infll, forward = 0, backward = length;
    for(i32 i = 0; i < n-1; ++i) {
        forward += a[i];
        backward -= a[i];
        chmin(ans, abs<i64>(forward - backward));
    }

    cout << ans << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 1792