akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

const ll mod = 1000000007;

template<typename T>
static inline void chmin(T & ref, const T  value) {
	if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
	if (ref < value) ref = value;
}


vector<ll> pow3() {
	vector<ll> ans;
	ll b = 1;
	for (int i = 0; i <= 15; i++) {
		ans.push_back(b);
		b *= 3;
	}
	return ans;
}

inline int pop3(ll j) {
	int a = 0;
	while (j) {
		if (j % 3) a++;
		j /= 3;
	}
	return a;
}

int main() {
	ll n;
	cin >> n;
	vector<ll> xs(n), ys(n), ps(n);
	rep(i, n) {
		cin >> xs[i] >> ys[i] >> ps[i];
	}
	vector<vector<ll>> dxs(n, vector<ll>(n));
	vector<vector<ll>> dys(n, vector<ll>(n));
	rep(i, n) {
		rep(j, n) {
			dxs[i][j] = min(abs(xs[i] - xs[j]), abs(xs[i]));
			dys[i][j] = min(abs(ys[i] - ys[j]), abs(ys[i]));
		}
	}
	const auto table = pow3();
	vector<int> popcounts(table[n]);
	for (ll j = 0; j < table[n]; j++){
		popcounts[j] = pop3(j);
	}
	vector<ll> nxs(table[n],0);
	vector<ll> nys(table[n],0);
	for (ll j = 0; j < table[n]; j++) {
		ll c = j;
		for(int a = 0; a < n && c > 0; a++) {
			if (c % 3 == 1) {
				nxs[j] |= (1LL << a);
			}
			else if (c % 3 == 2) {
				nys[j] |= (1LL << a);
			}
			c /= 3;
		}
	}
	vector<vector<ll>> xss(n, vector<ll>(1LL << n, 0));
	vector<vector<ll>> yss(n, vector<ll>(1LL << n, 0));
	rep(j, 1LL << n) {
		rep(k, n) {
			ll dx = abs(xs[k]);
			ll dy = abs(ys[k]);							
			rep(i, n) {
				if (j & (1LL << i)) {
					dx = min(dx, dxs[k][i]);
					dy = min(dy, dys[k][i]);
				}
			}
			xss[k][j] = dx;
			yss[k][j] = dy;
		}
	}
	vector<ll> memo(table[n]);
	for (ll j = 0; j < table[n]; j++) {
		ll d = 0;
		for (int k = 0; k < n; k++) {
			ll dx = xss[k][nxs[j]];
			ll dy = yss[k][nys[j]];
			d += min(dx, dy) * ps[k];
		}
		memo[j] = d;
	}
	vector<ll> ans(n + 1, INF);
	for (ll j = 0; j < table[n]; j++) {
		ans[popcounts[j]] = min(ans[popcounts[j]], memo[j]);
	}
	for (int i = 0; i <= n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    int N;
    cin>>N;

    int ans=0;
    vector<int>X;
    rep(i,N){
        int a,b;cin>>a>>b;
        X.pb(a+b);
        ans+=a-b;
    }
    sort(all(X));reverse(all(X));
    rep(i,N){
        if(i&1)ans-=X[i];
        else ans+=X[i];
    }
    cout<<ans/2<<endl;
    return 0;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int n;
    cin >> n;
    vector<int> vec(0),p(n),q(n);
    rep(i,n)vec.push_back(i+1);
    rep(i,n)cin >> p.at(i);
    rep(i,n)cin >> q.at(i);
    map<vector<int>,int> mp;
    int i=0;
  	mp[vec]=i;
    while(next_permutation(vec.begin(),vec.end())){
		i++;
        mp[vec]=i;
    }
    cout << abs(mp[p]-mp[q]) << endl;
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int a[101];
int main(){
    int n,m;
    cin>>n>>m;
    rep(i,n) cin>>a[i];
    FOR(i,1,m+1){
        rep(j,n-1){
            if(a[j]%i>a[j+1]%i) swap(a[j],a[j+1]);
        }
    }
    rep(i,n) cout<<a[i]<<endl;
    return 0;
}


Measured memory_bytes: 3104
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<numeric>
#include<algorithm>
#include<complex>
#include<queue>
#include<stdlib.h>
#include<map>
#include<cmath>
#include<stdio.h>
#include<stdlib.h>
#include<set>

#define ll long long

using namespace std;

int main(){
    string N;
    cin >> N;
    if(N[0]==N[2]){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

/*ll gcd(ll a, ll b) {
    if(a*b == 0)return max(a, b);
    if (a < b) {
        ll tmp = a;
        a = b;
        b = tmp;
    }
    if (a%b == 0)return b;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main(){
    int N;
    cin >> N;
    vector<ll> T(N,0);
    for(int i=0;i<N;i++){
        cin >> T[i];
    }
    ll ans=T[0];
    for(int i=1;i<N;i++){
        ans = lcm(ans,T[1]);
    }
    return 0;
}*/


Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>


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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

LL N, S;

bool isS(LL x,LL p) {

	
	LL pow = 1;
	while (pow*p <= x) {
		pow *= p;
	}

	LL sum = 0;
	while (x > 0) {
		sum += x / pow;
		x = x % pow;

		pow /= p;
	}


	return S == sum;
}

int main() {
	cin >> N >> S;

	if (N < S) {
		cout << "-1" << endl;
		return 0;
	}
	
	if (N == S) {
		cout << N + 1 << endl;
		return 0;
	}

	LL ans = INF2;
	for (LL i = 2; i*i <=N; i++) {
		if (isS(N, i)) {
			ans = min(ans, i);
		}
	}

	for (LL i = 1; i*i < N && i <= S; i++) {
		LL m = S - i;

		if (N - m >= 0 && (N - m) % i == 0) {
			LL b = (N - m) / i;

			if (b > i && b > m) {
				ans = min(ans, (N - m) / i);
			}
		}
	}

	if (ans == INF2) {
		cout << "-1" << endl;
		return 0;
	}

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int A, B, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;

    if (C <= A + B) printf("Yes\n");
    else printf("No\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
  int x,y;
  cin >> x >> y;
  cout << (a[x] == a[y] ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc146/tasks/abc146_b
//
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, [ next / $t:tt ]) => {
        {
            let len = read_value!($iter, usize);
            (0..len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
        }
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! dvec {
    ($t:expr ; $len:expr) => {
        vec![$t; $len]
    };

    ($t:expr ; $len:expr, $($rest:expr),*) => {
        vec![dvec!($t; $($rest),*); $len]
    };
}

#[allow(unused_macros)]
macro_rules! ifv {
    ($t:expr, $a:expr, $b: expr) => {
        if $t { $a } else { $b }
    }
}

#[allow(unused_macros)]
macro_rules! fill {
    ($t:expr, $v:expr) => {
        for i in 0..$t.len() {
            $t[i] = $v;
        }
    };
}

#[allow(unused_macros)]
macro_rules! join {
    ($t:expr, $glue:expr) => {
        $t.into_iter().map(|w| w.to_string()).collect::<Vec<_>>().join($glue)
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn rot(c: char, n: i32) -> char {
    let mut w = (c as u8 - 'A' as u8) as i32;
    w += n;
    w %= 26;
    ((w as u8) + ('A' as u8)) as char
}

fn main() {
    input! {
        n: i32, s: chars
    };

    let s = s.into_iter().map(|c| rot(c, n)).collect::<Vec<_>>();
    println!("{}", join!(s, ""));
}


Measured memory_bytes: 4352
S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
tenfactor = 1

for i in range(N):
    s = int(S[-i-1])
    now = (now + s*tenfactor)%2019
    tenfactor = tenfactor*10%2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)



Measured memory_bytes: 68300
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;

const int INF = 1001001001;

int main(){
    int N, K, A;
    cin >> N ;
   
    cout << N/2 + N%2<< endl;
}

Measured memory_bytes: 256
// ボール: 区別あり, 箱：区別あり, 入れ方: 1 つ以上
#include <iostream>
using namespace std;
const int MOD = 1000000007;
const long long MAXN = 1001024;

// 繰り返し 2 乗法
long long modpow(long long a, long long n) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return res;
}

long long fac[MAXN], finv[MAXN], inv[MAXN];

// 前処理 O(n)
void comb_init(){
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(long long i = 2; i < MAXN; 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;
  }
}

// 二項係数計算 O(1)
long long COM(long long n, long long 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() {
  
  int n, k; cin >> n >> k;
  long long ans = 0;
  comb_init();
  for(int i = 0; i < k; i++) {
    // i 個の箱を選んで, 絶対ボールを入れないことにする
    // 残りの箱に自由に入れる
    int rest = k - i;
    long long add = COM(k, i) * modpow(rest, n) % MOD;
    
    if(i % 2 == 0) ans = (ans + add      ) % MOD;
    else           ans = (ans - add + MOD) % MOD;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 26568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define maxn 200005
const int mod=1e9+7;
#define eps 1e-5
#define pi acos(-1.0)

ll quickpow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*a;
        }
        a=a*a;
        b>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

ll a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=i;
        //sum+=a[i];
    }
    sort(a+1,a+1+n);
    int b=a[(n+1)>>1];
    for(int i=1;i<=n;i++){
        sum+=abs(a[i]-b);
    }
    cout<<sum<<endl;
    return 0;
}





Measured memory_bytes: 1792
import math
N,K=map(int,input().split()[:2])
modp=10**9+7

def combinations_count(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(K):
    ret=0
    if i==0:
        print(N-K+1)
        continue
    tmp=combinations_count(K-1,i) % modp
    tmp2=combinations_count(N-K+1,i+1) % modp
    ret=(tmp*tmp2)%modp
    print(ret)

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

using namespace std;

int N;
int Distance[10], Speed[10];
unsigned long long Lcm[10][10];


unsigned long long findLcm(unsigned long long nowA, unsigned long long nowB) {
	unsigned long long a, b;

	a = nowA;
	b = nowB;
	while (b ^= a ^= b ^= (a %= b));
	
	return (nowA / a) * nowB;
}

void solve() {
	int k;
	unsigned long long nowLcm;

	for (int i = 0; i < N; ++i) {
		k = 0;
		for (int j = 0; j < N; ++j) {
			if (i == j) {
				continue;
			}
			nowLcm = findLcm(Distance[i] * Speed[j], Distance[j] * Speed[i]);
			Lcm[i][k++] = nowLcm / (Distance[i] * Speed[j]);
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 1; j < N - 1; ++j) {
			Lcm[i][0] = findLcm(Lcm[i][0], Lcm[i][j]);
		}
	}

	for (int i = 0; i < N; ++i) {
		cout << Lcm[i][0] << endl;
	}
}

int main() {

	while (cin >> N, N) {
		memset(Distance, 0, sizeof(Distance));
		memset(Speed, 0, sizeof(Speed));
		memset(Lcm, 0, sizeof(Lcm));
		for (int i = 0; i < N; ++i) {
			cin >> Distance[i] >> Speed[i];
		}
		////show:
		//for (int i = 0; i < N; ++i) {
		//	cout << Distance[i] << " " << Speed[i] << endl;
		//}
		solve();
	}

	return 0;
}


Measured memory_bytes: 3000
#ABC128B

N = int(input())

restaurant = []
for i in range(1,N+1):
    S, P = input().split()
    restaurant.append((i, S, int(P)))

# score
restaurant.sort(key = lambda store: -1 * store[2])
# city
restaurant.sort(key = lambda store: store[1])

for r in restaurant:
    print(r[0])
    

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define rrep(i,a,b) for(ll i=a;i>b;i-=1)
#define vi vector<ll>
#define vii vector<vector<ll> >
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define sz(a) int((a).size())
#define tr(c,i) for( typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mp make_pair
#define hell 1000000007
#define F first
#define S second
//debug
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
ll t=1;
void solve()
{
    int n;
    cin>>n;
    int k;
    cin>>k;
    vector<int> v(n);
    int dp[n];
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    dp[0]=0;
    int t=1;
    int gg=INT_MAX;
    for(int i=1;i<n;i++)
    {
        while(t<=k)
        {
           if(i-t<0) break;
           gg=min(gg,abs(v[i]-v[i-t])+dp[i-t]);
           t++;
        }
        dp[i]=gg;
        gg=INT_MAX;
        t=1;
    }
    cout<<dp[n-1];
}
int main()
{
    int i;
  	ios_base::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
  	//cin>>t;
  	while(t--)
	solve();
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



// range sum query using fenwick tree
// note index starts at 1

class fenwick_tree {
	vector<long> t;
	long size;
public:
	fenwick_tree(long n) {
		t.assign(n + 1, 0);
		size = n + 1;
	}

	long LSOne(long k) {	// least significant 1-bit
		return k & (-k);
	}

	void update(long index, long val) {	// can go up or go down
		for (; index < size; index += LSOne(index)) t[index] += val;
	}

	long query_full(long a, long b) {		// range query
		return query(b) - ((a <= 1) ? 0 : query(a - 1));
	}

	long query(long b) {	// range query 1..b
		if (b < 1) return 0;

		long sum = 0;
		for (; b; b -= LSOne(b)) sum += t[b];
		return sum;
	}
};


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

	int n, q, i, j, k, id, l, r, x, ans;
	string s;
	char ch;

	cin >> n >> s >> q;
	vector<fenwick_tree> ft(26, fenwick_tree(n + 1));
	for (i = 0; i < n; i++) {
		x = s[i] - 'a';
		ft[x].update(i + 1, 1);
	}

	while (q--) {
		cin >> id;
		if (id == 1) {
			cin >> id >> ch;
			x = s[id - 1] - 'a';
			ft[x].update(id, -1);
			s[id - 1] = ch;
			x = s[id - 1] - 'a';
			ft[x].update(id, 1);
		}
		else {
			cin >> l >> r;
			ans = 0;
			for (i = 0; i < 26; i++) {
				if (ft[i].query_full(l, r) > 0) ans++;
			}
			cout << ans << "\n";
		}
	}


	return 0;
}


Measured memory_bytes: 106360
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		a: usize,
		b: usize,
		c: usize,
		d: usize,
	}

	if a+b < c+d {
		println!("Right");
	}
	else if a+b > c+d {
		println!("Left");
	}
	else {
		println!("Balanced");
	}
}



Measured memory_bytes: 2096
#include <stdio.h>
int main()
{
  int count[26] = {};
  int n, i;
  char ch;
  while( scanf("%c", &ch) != EOF ){
    if(ch >= 'a' && ch <= 'z'){  
  n = ch - 'a';
  count[n]++;
    }
    else if(ch >= 'A' && ch <= 'Z'){
      n = ch - 'A';
      count[n]++;
    }
  }
  for(i = 0; i < 26; i++){
    printf("%c : %d\n",'a'+i, count[i]);
  } 
  return 0;
}

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

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

  int a_4multi = 0, a_2num = 0, a_odd = 0;
  for (int i = 0; i < N; ++i) {
    int a; cin >> a;
    if (a % 4 == 0) a_4multi++;
    else if (a % 2 == 0) a_2num++;
    else a_odd++;
  }

  if ((a_2num == 0 and a_4multi+1>=a_odd) or
      (a_2num > 0 and a_4multi+1>=a_odd+1)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

int main() {
    int K, S;
    cin >> K >> S;
    int ans = 0;

    for(int i = 0; i <= K; i++) {
        for(int j = 0; j <= K; j++) {
            if(S-K <= i+j && i+j <= S) {
                ans++;
            }
        }
    }
    
    cout << ans;
    
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void p(vector<int> A){rep(i,A.size()){cout << A[i] << " ";}cout << "\n";}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    bool flag = false;
    int ans = 0;
    rep(i,n){
        if(a[i] == 1)flag = true;
    }
    if(!flag)cout << "-1" << endl;
    else{
        int i = 0,j = 1,cnt = 0;
        while(i < n){
            if(a[i] == j){
                cnt++;
                j++;
            }
            ans = max(cnt,ans);
            i++;
        }
    }
    if(flag)cout << n-ans;
}

Measured memory_bytes: 4040
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
  char s; cin>>s;
  if(s>='a' && s<='z') cout<<'a'<<endl;
  else cout<<'A'<<endl;
}

Measured memory_bytes: 3564
k,a,b = map(int,input().split())
counter = k
x = 1
s = 0

if a >= b or (a < b and b - a <= 2) or counter < a - 1:
    x = 1+k
elif a < b and b - a > 2:
    counter -= a-1
    x += a-1
    if counter > 1 and counter % 2 == 0:
        z = int(counter/2)
        x += int((b-a)*z)
    elif counter > 1 and counter % 2 == 1:
        z = int(counter/2)
        x += int((b-a)*z + 1)
    elif counter == 1:
        x += 1


print(x)

Measured memory_bytes: 3064
def comb(n, r):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
    return x // y

n, a, b = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse = True)
c = b - a + 1
s = [0] * c
for i in range(c):
    s[i] = sum(v[0 : a + i]) / (a + i)
m = max(s)
ans = 0
for i in range(c):
    if s[i] == m:
        r = v[0 : a + i].count(v[a + i - 1])
        l = v.count(v[a + i - 1])
        ans += comb(l, min(r, l - r))
print(m)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;


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

  int n; cin >> n;

  ll tsum = 1;
  ll asum = 1;

  rep(i, n) {
    ll t, a; cin >> t >> a;
    while (tsum%t != 0) {
      tsum++;
    }
    while(asum%a != 0) {
      asum++;
    }
    //debug(tsum);debugln(asum);
    ll ma = max(tsum/t, asum/a);
    tsum = ma*t;
    asum = ma*a;
  }

  cout << tsum + asum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int dp[1010][1010];
int bingo[3][3];
bool flag[3][3];
int cnt[2][105];

int main() {
	int n, m;
	cin >> n >> m;
	int ans = n * (n - 1) / 2 + m * (m - 1) / 2;
	cout << ans << endl;
	return 0;
}


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

using namespace std;

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

    string t = s;
    auto h = s.length() / 2;
    reverse(s.begin(), s.end());
    if (s == t and s.substr(0, h) == s.substr(h + 1, h)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<vector>

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

using namespace std;

const double EPS=1e-8;
const double PI=acos(-1);

struct point{
	double x,y;
	point():x(0),y(0){}
	point(double x,double y):x(x),y(y){}
	point &operator*=(double c){ x*=c; y*=c; return *this; }
	point operator+(const point &a)const{ return point(x+a.x,y+a.y); }
	point operator-(const point &a)const{ return point(x-a.x,y-a.y); }
};

point operator*(double c,const point &a){ return point(c*a.x,c*a.y); }

double cross(const point &a,const point &b){ return a.x*b.y-a.y*b.x; }

double abs(const point &a){ return sqrt(a.x*a.x+a.y*a.y); }

point rot(const point &a,double theta){ return point(a.x*cos(theta)-a.y*sin(theta),a.x*sin(theta)+a.y*cos(theta)); }

struct line{
	point a,b;
	line(const point &a,const point &b):a(a),b(b){}
};

struct circle{
	point c;
	double r;
	circle(const point &c,double r):c(c),r(r){}
};

double dist(const point &a,const point &b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double dist(const line &L,const point &p){
	return abs(cross(L.b-L.a,p-L.a))/dist(L.a,L.b);
}

bool intersect(const line &L1,const line &L2){
	return abs(cross(L1.b-L1.a,L2.b-L2.a))>EPS
		|| abs(cross(L1.b-L1.a,L2.a-L1.a))<EPS;
}

point get_intersect(const line &L1,const line &L2){
	double a1=cross(L1.b-L1.a,L2.b-L2.a);
	double a2=cross(L1.b-L1.a,L1.b-L2.a);
	if(abs(a1)<EPS) return L1.a;
	return L2.a+a2/a1*(L2.b-L2.a);
}

void get_circle_llr(const line &L1,const line &L2,double r,vector<circle> &res){
	point v1=rot(L1.b-L1.a,PI/2); v1*=r/abs(v1);
	point v2=rot(L2.b-L2.a,PI/2); v2*=r/abs(v2);
	rep(i,2){
		rep(j,2){
			line M1(L1.a+v1,L1.b+v1);
			line M2(L2.a+v2,L2.b+v2);
			if(intersect(M1,M2)) res.push_back(circle(get_intersect(M1,M2),r));
			v2*=-1;
		}
		v1*=-1;
	}
}

// 円とビームの共通部分が面積正かどうか
bool intersect(const circle &C,double x1,double y1,double x2,double y2,double t){
	line M(point(x1,y1),point(x2,y2));
	return dist(M,C.c)<C.r+t-EPS;
}

int main(){
	for(int w,h,n,r;scanf("%d%d%d%d",&w,&h,&n,&r),w;){
		int x1[100],y1[100],x2[100],y2[100],t[100];
		rep(i,n) scanf("%d%d%d%d%d",x1+i,y1+i,x2+i,y2+i,t+i);

		vector<line> L; // 興味ある直線全体
		L.push_back(line(point(0,0),point(w,0)));
		L.push_back(line(point(w,0),point(w,h)));
		L.push_back(line(point(w,h),point(0,h)));
		L.push_back(line(point(0,h),point(0,0)));
		rep(i,n){
			line M(point(x1[i],y1[i]),point(x2[i],y2[i]));
			point v=rot(M.b-M.a,PI/2);
			v*=t[i]/abs(v);
			L.push_back(line(M.a+v,M.b+v));
			L.push_back(line(M.a-v,M.b-v));
		}

		vector<circle> C; // 答えの候補
		rep(i,L.size()) rep(j,i) get_circle_llr(L[i],L[j],r,C);

		bool ok=false;
		rep(i,C.size()){
			if(C[i].c.x-r<-EPS || w+EPS<C[i].c.x+r || C[i].c.y-r<-EPS || h+EPS<C[i].c.y+r) continue;
			int j;
			for(j=0;j<n;j++) if(intersect(C[i],x1[j],y1[j],x2[j],y2[j],t[j])) break;
			if(j==n){ ok=true; break; }
		}
		puts(ok?"Yes":"No");
	}

	return 0;
}

Measured memory_bytes: 5908
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <deque>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main() {
  int N, K, Q; cin >> N >> K >> Q;
  vector<int> ans(N, 0);
  rep(i, Q) {
    int a; cin >> a; a--;
    ans[a]++;
  }

  rep(i, N) {
    int point = K - (Q-ans[i]);
    if(point > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i,n) cin >> v[i];
    vector<int> c(n);
    rep(i,n) cin >> c[i];
    int ans = 0;
    rep(i,n){
        if(v[i]-c[i] > 0) ans += v[i]-c[i];
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int h,w,k;
	cin>>h>>w>>k;
	int square[h+1][w+1];
	char ch;
	int num=0;
	int choices=0;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>ch;
			if(ch=='.')square[i][j]=0;
			else square[i][j]=1;
		}
	}
	int choose[h+w+1];
	for(int i=0;i<=h+w;i++){
		choose[i]=0;
	}
	while(choose[0]==0){
		num=0;
		int square1[h+1][w+1];
		for(int i=1;i<=h;i++){
			for(int j=1;j<=w;j++){
				square1[i][j]=square[i][j];
			}
		}
		for(int i=1;i<=h;i++){
			if(choose[i]==1){
				for(int x=1;x<=w;x++){
					square1[i][x]=0;
				}
			}
		}
		for(int i=h+1;i<=h+w;i++){
			if(choose[i]==1){
				for(int x=1;x<=h;x++){
					square1[x][i-h]=0;
				}
			}
		}
		for(int i=1;i<=h;i++){
			for(int j=1;j<=w;j++){
				if(square1[i][j]==1)num++;
			}
		}
		if(num==k)choices++;
		
		int i=h+w;
		while(choose[i]==1){
			i--;
		}
		if(i==0){
			cout<<choices;
			return 0;
		}
		choose[i]=1;
		for(int j=i+1;j<=h+w;j++){
			choose[j]=0;
		}
	}
	cout<<choices;
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <queue>
#include <vector>
#include <map>

using namespace std;

#define INF 1e+9

struct Edge{
    int to;
    int weight;
};


vector<int> dijkstra(vector<vector<Edge>>& G, int start) {

    const int V = G.size();
    vector<int> res(V,INF);
    
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> >  pq; // TODO
    pq.push( make_pair(0,start) );

    while( !pq.empty() ){
       
	int s = pq.top().first;
	int v = pq.top().second;
	pq.pop();
	
	// ????????¢?´¢?????????????????????
	if( res[v] != INF ) continue;
	
	// ????????????????????¢?´¢????????°????????????????¢???????
	res[v] = s;
	// v ??????????????????????????????????????????
	// ??????????????¢?´¢???????????\????????????
	for(int i=0; i<G[v].size(); i++) {
	    int tgt = G[v][i].to; // ?????????
	    int sco = s + G[v][i].weight;
	    if( res[tgt] == INF )
		pq.push( make_pair(sco,tgt) );
	}
    }
    return res;
}



int main () {
    int V,E,r;
    cin >> V >> E >> r;
    
    vector<vector<Edge>> AdjList(V);

    for(int i=0; i<E; i++) {
	int s,t,w;
	cin >> s >> t >> w;
	AdjList[s].push_back( Edge{t,w} );
    }

    vector<int> sp = dijkstra(AdjList,r);
    for(auto res : sp) {
	if( res == INF )
	    cout << "INF" << endl;
	else
	    cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 14016
///who is the king ??? *** << t.mohammad >> *** ///
/*
                  00                                                                                                            00
                 00                               00                                                                           00
            0000000000                           00                                                                           00
           0000000000   000       000           00                        000       000  000       000                       00
              00       0000     0000           00         000000         0000     0000  0000     0000   000000              00
             00       00 00   00 00    000    00        00000000        00 00   00 00  00 00   00 00  00000000       00000000
            00       00  00 00  00   00000   000000    00    000       00  00 00  00  00  00 00  00  00    000     0000000000
           00       00   000   00  00   00  00000000  00    0000      00   000   00  00   000   00  00    0000    00     0000
          00       00         00  00   00  00    00  00    00 00     00         00  00         00  00    00 00   00     00 00
         00  00   00         00   00000   00    00  00000000  00    00         00  00         00  00000000  00  000000000  00
        00  00   00         00    000    00    00   000000    00   00         00  00         00   000000    00  0000000    00
*/
#include <bits/stdc++.h>
using namespace std ;
typedef long long int ll;
typedef long double dou ;
typedef pair<ll , ll> pii;
typedef map<ll, bool> mib;
typedef pair<ll, bool> pib;
typedef map<ll , ll> mii;
#define wh while
#define str string
#define vec vector
#define fori(a1 , a2 , a3) for(ll i = a1 ; i < a2 ; i = i + a3)
#define for_i(b1 , b2 , b3) for(ll i = b1 ; i >= b2 ; i = i - b3)
#define forj(c1 , c2 , c3) for(ll j = c1 ; j < c2 ; j = j + c3)
#define for_j(d1 , d2 , d3) for(ll j = d1 ; j >= d2 ; j = j - d3)
#define fore(e1 , e2 , e3) for(ll e = e1 ; e < e2 ; e = e + e3)
#define for_e(f1 , f2 , f3) for(ll e = f1 ; e >= f2 ; e = e - f3)
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
#define setp(t) cout << setprecision(t) << fixed ;
int main(){
	fast ;
	ll n , a , b ;
	cin >> n >> a >> b ;
	cout << min(a , b) << " " ;
	ll c = a + b ;
	if (n - c < 0)
	{
		cout << abs(n - c) ;
		return 0 ;
	}
	cout << 0 ;
	
}




Measured memory_bytes: 256
inp = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')
l = inp.shift().split(' ')
H = l.shift() * 1
W = l.shift() * 1
a = []
for (i=0; i<H; i++) {
    b = inp[i].split('')
    if (b.indexOf('#') >= 0) {
        a.push(b)
    }
}
for (i=a[0].length-1; i>=0; i--) {
    b = 0
    for (j=a.length-1; j>=0; j--) {
        if (a[j][i] == '#') {
            b = 1
            break;
        }
    }
    if (!b) {
        for (k=a.length-1; k>=0; k--) {
            a[k].splice(i, 1)
        }
    }
}

console.log(a.map(x => x.join('')).join("\n"))

Measured memory_bytes: 21192
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int cnt = 0;
  for(int i = 0;i < n;i++){
    if(i + 1 < n && s[i] != s[i+1]){
      cnt++;
      i++;
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3340
#include <iostream>

using namespace std;

int main ()
{
	long n,m,s[100],a[100][100],K[100];

	cin >> n >> m;/*i = 4
					j = 3*/

	for (int i = 0; i < m; i++)
	{
		s[i] = 0;
		cin >> s[i];
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			a[i][j] = 0;
			cin >> a[i][j];

			if (a[i][j] == s[i])
			{
				K[j] += 1;
			}
			else if (a[i][j] != s[i])
			{
				K[s[i] - 1] += 1;
			}
		}

	}

	for (int j = 0; j < n; j++)
	{
		cout << K[j] << endl;
	}
	return 0;
}

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

using namespace std;

#define fo(i, n) for(int i = 1; i <= n; ++i)
#define pb push_back

typedef long long ll;

const int N = 5000500;
const int mod = 1e9 + 7;
const ll inf = 2e18;

int n, k;
inline double s(ll x) {
    double y = x;
    ll res = 0;
    while(x > 0) res += x % 10, x /= 10;
    return y / res;
}
ll pw[20];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll k;
    cin >> k;
    ll val = 1000000000000000ll;
    val--;
    vector<ll> res;
    pw[0] = 1;
    for(int i =1 ; i<= 15;++i)
        pw[i] = pw[i-1]*10;
    set<ll> q;
    q.insert(val);
    set<ll> was;
    was.insert(val);
    while(q.size()) {
        ll val = *q.rbegin(), v = val;
        q.erase(v);
        double t = s(v);
        vector<ll> dig;
        while(v) {
            dig.pb(v % 10);
            v /= 10;
        }
        for(int j = 0; j < dig.size(); ++j) {
            ll nv = val - dig[j] * pw[j];
            nv += (dig[j] - 1) * pw[j];
            if(was.find(nv) != was.end()) continue;
            auto it = was.lower_bound(nv);
            if(it == was.end() || s(nv) <= s(*it)) q.insert(nv), was.insert(nv);
        }
    }

    for(auto &v : was) {
        if(k--) cout << v << '\n';
        else break;
    }
return 0;
    cin >> n;

    fo(i, n) {
        int fail = 0;
        for(int j = i + 1; !fail && j <= i + 100000; ++j)
            if(s(j) < s(i)) fail = 1;
        if(!fail) cout << i << endl;
    }
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<long long> A(N);
  vector<long long> B(N);
  for(int i = 0; i < N; i++) {
    cin >> A.at(i) >> B.at(i);
  }
  sort(A.begin(), A.end()); 
  sort(B.begin(), B.end()); 
  cout << A.at(N-1) + B.at(0);
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const ll INF = 1e15;
const bool debug = false;

void out_map(vector<vector<ll>> ls){
    rep(i,ls.size()){
        rep(j,ls.at(i).size()){
            if(ls.at(i).at(j) == INF) cout << "- ";
            else cout << ls.at(i).at(j) << " ";
        }
        cout << endl;
    }
}

int main(){
    int n,m,s;
    cin >> n >> m >> s;
    vector<vector<ll>> mc(n, vector<ll>(n)), tc(n, vector<ll>(n));
    
    rep(i,n){
        rep(j,n){
            mc.at(i).at(j) = INF;
            tc.at(i).at(j) = INF;
        }
    }
    
    ll maxa = 0;
    rep(i,m){
        ll u,v,a,b;
        cin >> u >> v >> a >> b;
        mc.at(u-1).at(v-1) = a;
        mc.at(v-1).at(u-1) = a;
        tc.at(u-1).at(v-1) = b;
        tc.at(v-1).at(u-1) = b;
        maxa = max(maxa,a);
    }

    rep(i,n){
        ll a,b;
        cin >> a >> b;
        mc.at(i).at(i) = -a;
        tc.at(i).at(i) = b;
    }
    
    if(debug){
        out_map(mc);
        cout << endl;
        out_map(tc);
        cout << endl;
    }

    ll mnmax = maxa*(n-1);
    if(debug) cout << "mnmax:" << mnmax << endl;
    vector<vector<ll>> dp(n,vector<ll>(mnmax+1));
    vector<vector<bool>> visited(n,vector<bool>(mnmax+1));
    rep(i,dp.size()){
        rep(j,dp.at(i).size()){
            dp.at(i).at(j) = INF;
            visited.at(i).at(j) = false;
        }
    }

    // {cost, {top, money}}
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq;
    rep(i,dp.at(0).size()){
        if(i<=s){
            dp.at(0).at(i) = 0;
            pq.push({0,{0,i}});
        }
    }
    
    if(debug){
        cout << "initial dp" << endl;
        out_map(dp);
        cout << endl;
    }

    while(pq.size()){
        auto pp = pq.top(); pq.pop();
        auto p = pp.second;
        // if(debug) cout << "p:" << p.first << " " << p.second << endl;
        if(visited.at(p.first).at(p.second)) continue;
        rep(i,n) {
            ll y = min(mnmax, p.second - mc.at(p.first).at(i));
            ll c = dp.at(p.first).at(p.second) + tc.at(p.first).at(i);
            // cout << i << " " << y << " " << c << endl;
            if(y<0) continue;
            dp.at(i).at(y) = min(dp.at(i).at(y), c);
            if(!visited.at(i).at(y)){
                pq.push({dp.at(i).at(y),{i, y}});
            }
        }
        visited.at(p.first).at(p.second) = true;
    }

    if(debug){
        cout << "dp" << endl;
        out_map(dp);
    }

    rep(i,n){
        if(i==0) continue;

        ll minval = INF;
        for(ll x : dp.at(i)){
            minval = min(minval, x);
        }
        cout << minval << endl;
    }

    return 0;
}

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

int main(){
	int R;
	cin >> R;
	if(R < 1200){
		cout << "ABC" << endl;
	}else if(R < 2800){
		cout << "ARC" << endl;
	}else{
		cout << "AGC" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a > b) {
		cout << "a > b\n";
	}
	if (a == b){
		cout << "a == b\n";
	}
	if (a < b){
		cout << "a < b\n";
	}
	cin >> a;
}

Measured memory_bytes: 2924
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
ll n,m;
map<ll,ll> mp;
ll dp[100005];
ll maxval(ll i){
	if(i>n) return 0;
	if(i==n){
		return 1;
	}
	if(mp.find(i)!=mp.end()){
		return 0;
	}
	if(dp[i]!=-1){
		return dp[i];
	}

	ll a,b;
	a=maxval(i+1)%mod;
	b=maxval(i+2)%mod;
	return dp[i]=(a+b)%mod;
}
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l;
	cin>>n>>m;
	memset(dp,-1,sizeof(dp));
	for(i=1;i<=m;i++){
		cin>>k;
		mp[k]=1;
	}
	if(mp.find(n)!=mp.end()){
		cout<<"0\n";
		return 0;
	}

	k=maxval(0)%mod;
	cout<<k;
	return 0;
}


Measured memory_bytes: 7296
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MAX 100000
typedef long long ll;
typedef pair<ll,int> P;

int check[110000];
ll dp[110000];

int main(){
  int N,M,temp;
  cin>>N>>M;
  for(int i=0;i<M;i++){
    cin>>temp;
    check[temp]++;
  }
  dp[0]=1;
  for(int i=0;i<N;i++){
    for(int j=1;j!=3;j++){
      if(check[i+j]==0){
        dp[i+j]+=dp[i];
        dp[i+j]%=1000000007;
      } 
    }
  }
  cout<<dp[N]<<endl;
}


Measured memory_bytes: 1408
S=input()

F=int(S[:2])
A=int(S[2:])

if F>12 or F==0:
    if A>12 or A==0:
        print('NA')
    else:
        print('YYMM')
elif A>12 or A==0:
    print('MMYY')
else:
    print('AMBIGUOUS')
        

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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    if (s == "Sunny") cout << "Cloudy";
    if (s == "Cloudy") cout << "Rainy";
    if (s == "Rainy") cout << "Sunny";

    return 0;
}

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

typedef long long i64;

struct BIT {
	vector<int> dat;
	int size;
	void init(int n) {
		size = n;
		dat.resize(size + 1);
		fill(dat.begin(), dat.end(), 0);
	}
	void add(int pos, int val) {
		for(int x = pos + 1; x <= size; x += x & -x) {
			dat[x] += val;
		}
	}
	int sum(int right) {
		int s = 0;
		for(int x = right; x > 0; x -= x & -x) {
			s += dat[x];
		}
		return s;
	}
};

int find_minlen(int pos, int n, BIT& remains)
{
	int a = remains.sum(pos);
	int b = remains.sum(n) - (a + 1);
	return min(a, b);
}

int main()
{
	int n;
	vector<int> vs;

	scanf("%d", &n);
	vs.resize(n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &vs[i]);
	}

	map<int,deque<int>> nums;
	BIT remains;

	remains.init(n);
	for(int i = 0; i < n; ++i) {
		remains.add(i, 1);
	}

	for(int i = 0; i < n; ++i) {
		nums[vs[i]].push_back(i);
	}

	i64 ans = 0;

	for(auto& pa : nums) {

		int v = pa.first;
		auto& pos_list = pa.second;

		while(pos_list.size() > 0) {
			int f = pos_list.front();
			int b = pos_list.back();
			int fv = find_minlen(f, n, remains);
			int bv = find_minlen(b, n, remains);
			if(fv < bv) {
				pos_list.pop_front();
				ans += fv;
				remains.add(f, -1);
			} else {
				pos_list.pop_back();
				ans += bv;
				remains.add(b, -1);
			}
		}
	}

	printf("%lld\n", ans);

	return 0;
}



Measured memory_bytes: 74944
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
#include<queue>
#include<map>
#include<math.h>

#define ll long long
#define dd double
#define scl(n)        scanf("%lld",&n)
#define scd(n)        scanf("%lf",&n)
#define scc(n)        scanf("%c",&n)
#define scs(n)        scanf("%s",&n)
#define ptl(n)        printf("%lld",n)
#define ptd(n)        printf("%f",n)
#define ptc(n)        printf("%c",n)
#define pts(n)        printf("%s",n)
#define nline         printf("\n")
#define pb            push_back
#define FOR(i,n)      for(ll i=0;i<n;i++)
#define FOR1(i,n)     for(ll i=1;i<=n;i++)
#define FORran(i,a,b) for(ll i=a;i<=b;i++)
#define pi            2*acos(0.0)
#define pii           pair<ll,ll>
#define uu            first
#define vv            second
#define mod   1000000007
using namespace std;
ll a[200005],cum[200005];
int main()
{
    ll n,sum=0;
    scl(n);
    FOR(i,n)
    {
        scl(a[i]);
        if(i>0)
            cum[i]=cum[i-1]+a[i];
        else
            cum[i]=a[i];
    }
    FOR1(i,n)
    {
        sum=(sum%mod)+(((a[i]%mod)*(cum[i-1]%mod))%mod);
    }
    ptl(sum);
    return 0;
}


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

signed main() {
  int N;
  cin >> N;
  int ga, sa, ba, gb, sb, bb;
  cin >> ga >> sa >> ba >> gb >> sb >> bb;

  auto f = [&](int N, int ga, int sa, int ba, int gb, int sb, int bb) {
    if (gb < ga) gb = ga;
    if (sb < sa) sb = sa;
    if (bb < ba) bb = ba;

    vector<int> dp(N + 1, -1e18);
    dp[0] = 0;

    for (int i = 0; i < N; i++) {
      if (i + ga <= N) dp[i + ga] = max(dp[i + ga], dp[i] + gb);
      if (i + sa <= N) dp[i + sa] = max(dp[i + sa], dp[i] + sb);
      if (i + ba <= N) dp[i + ba] = max(dp[i + ba], dp[i] + bb);
    }

    int res = 0;
    for (int i = 0; i <= N; i++) {
      res = max(res, dp[i] + (N - i));
    }

    return res;
  };

  int ans = f(N, ga, sa, ba, gb, sb, bb);
  ans = f(ans, gb, sb, bb, ga, sa, ba);

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


Measured memory_bytes: 195584
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(sc.next());
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i != 0) {
               System.out.print(nums[i] + " ");
            } else {
                System.out.println(nums[i]);
            }
        }
    }
}


Measured memory_bytes: 26152
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long int n,weight,i,maxi,j,w,v;
   long long int dp[1000000]={0};
   cin>>n>>weight;
   
   for(i=0;i<n;i++)
   {
       cin>>w>>v;
      for(j=weight;j>=w;j--)
      {
          dp[j]=max(dp[j],dp[j-w]+v);
      }
   }
   maxi=dp[0];
   for(i=0;i<=weight;i++)
   maxi=max(maxi,dp[i]);
   cout<<maxi<<endl;

    return 0;
}


Measured memory_bytes: 8064