akhauriyash/Code-Regression huggingface dataset:
from string import ascii_lowercase

def main():
    s = list(input())
    K = int(input())
    for i, c in enumerate(s):
        num = ord(c) - ord("a")

        if num > 0 and K - (26-num) >= 0:
            s[i] = "a"
            K -= (26-num)

    num = ord(s[-1]) - ord("a")
    last = (num + K)%26
    s[-1] = ascii_lowercase[last]
    print("".join(s))

        
if __name__ == "__main__":
    main()

Measured memory_bytes: 10812
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <cassert>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;
using VVI = vector<vector<long long int> >;


int main(void) {
    Int k, a, b;
    cin >> k >> a >> b;
    Int aModK = a % k;
    Int bModK = b % k;
    if (b - a >= k) {
        cout << "OK" << endl;
    } else if (aModK == 0 || bModK == 0) {
        cout << "OK" << endl;
    } else if (aModK > bModK) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }
    return 0;
}


Measured memory_bytes: 3596
#C
inf = float("inf")
N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(N)]

A = [0]*M
for ca in CA:
    for i in range(1,M+1):
        a = ca[i]
        A[i-1]+=a
        
if min(A) < X:
    print(-1)
else:
    K = 2**N
    ans = inf
    for i in range(K):
        b = bin(i)
        b = b.lstrip("0b")
        while (len(b)) < N:
            b = "0"+b
            
        A = [0]*M
        cost = 0
        for j in range(N):
            if b[j] == "1":
                ca = CA[j]
                for k in range(M+1):
                    if k == 0:
                        cost+=ca[k]
                    else:
                        A[k-1] += ca[k]
                        
        if min(A) >= X:
            ans = min(ans,cost)
            
    print(ans)
        
    




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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descsort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main(void)
{
    int d,t,s;
    cin>>d>>t>>s;
    if(t*s>=d)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3580
N = int(input())
num = {}
for i in range(N):
    A = int(input())
    if A in num.keys():
        num[A] += 1
    else:
        num[A] = 1
ans = 0
for i, j in num.items():
    if j%2 == 1:
        ans += 1
print(ans)


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

int main(){
    int a0, l, pos, pos_j, big, sma, tmp, pwr;
    bool fin;
    while(1){
        int a[21];
        cin >> a[0] >> l;
        if(l == 0)
            break;

        vector<int> list(l);
        pos = 0;
        fin = false;
        while(true){
            tmp = a[pos];
            pwr = pow(10, l-1);
            for(int i=0; i<l; i++){
                list[i] = tmp / pwr;
                tmp -= list[i] * pwr;
                pwr /= 10;
            }
            sort(list.begin(), list.end());

            big = 0;
            sma = 0;
            pwr = pow(10, l-1);
            for(int i=0; i<l; i++){
                big += list[l-i-1] * pwr;
                sma += list[i] * pwr;
                pwr /= 10;
            }
            a[++pos] = big - sma;

            for(int i=0; i<pos; i++){
                if(a[i] == a[pos]){
                    pos_j = i;
                    fin = true;
                    break;
                }
            }
            if(fin){
                cout << pos_j << ' ' << a[pos] << ' ' << pos - pos_j << endl;
                break;
            }
        }
    }
  
    return 0;
}

Measured memory_bytes: 3268
import numpy as np
import sys 
read = sys.stdin.buffer.read
read = sys.stdin.buffer.readline
read = sys.stdin.buffer.readlines

n , A , B = map(int,input().split())
S = input()
a , b = 0 , 0
for s in S:
    if s == "a":
        if  a + 1 + b <= A + B:
            print("Yes")
            a += 1
            continue
    
    if s == "b":
        if  a + 1 + b <= A + B and b + 1 <= B:
            print("Yes")
            b += 1
            continue
    
    print("No")




Measured memory_bytes: 13440
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
	int x;
	cin>>x;
	for(int i=1;i<=1000;i++)
		for(int j=-1000;j<=i;j++)
		{
			if(pow(i,5)+pow(j,5)==x)
			{
				printf("%d %d",i,-j);
				return 0;
			}
		}
}

Measured memory_bytes: 4136
#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)

int main(){
	
	int a,b,c;cin>>a>>b>>c;
	if(a<=c && a+b>=c)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

//cout << ans << endl;

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll modpow(ll x, ll n){
    ll res = 1;
    ll mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

struct Combination
{
    int maxn;
    vector<ll> fmemo;
    vector<ll> imemo;
    vector<ll> ifmemo;
    
    Combination(int maxn) : maxn(maxn){
        fmemo.resize(maxn + 1);
        imemo.resize(maxn + 1);
        ifmemo.resize(maxn + 1);
        for(ll i = 1; i <= maxn; i++){
            imemo[i] = modpow(i, MOD - 2);
        }
    }

    ll fact(ll n){
        if(n == 0) return 1;
        if(fmemo[n]) return fmemo[n];
        return fmemo[n] = n * fact(n - 1) % MOD;
    }

    ll ifact(ll n){
        if(n == 0) return 1;
        if(ifmemo[n]) return ifmemo[n];
        return ifmemo[n] = imemo[n] * ifact(n - 1) % MOD;
    }

    ll com(ll n, ll k){
        if(k > n) return 0;
        if(k == n || k == 0) return 1;
        return (fact(n) * ifact(k) % MOD) * ifact(n - k) % MOD;
    }
};

ll f[500005];

int main()
{
    int n, m;
    cin >> n >> m;
    f[0] = 1;
    for(int i = 1; i <= 500000; i++) f[i] = f[i - 1] * i % MOD;
    Combination com(n + m);
    ll ans = 0;
    for(int i = 0; i <= n; i++){
        if(i % 2){
            ans = (ans + MOD - com.com(n, i) % MOD *
                   f[m - i] % MOD * modpow(f[m - n], MOD - 2) % MOD) % MOD;
        }
        else{
            ans = (ans + com.com(n, i) % MOD *
                   f[m - i] % MOD * modpow(f[m - n], MOD - 2) % MOD) % MOD;
        }
    }
    cout << ans * f[m] % MOD * modpow(f[m - n], MOD - 2) % MOD << endl;
}


Measured memory_bytes: 46200
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x,y;
  cin>>x>>y;
  if(y-2*x>=0 && (y-2*x)%2==0 && (4*x-y)>=0 && (4*x-y)%2==0)
  {
    cout<<"Yes"<<"\n";
  }
  else
  {
    cout<<"No"<<"\n";
  }
  return 0;
}


Measured memory_bytes: 3596
inf = 10 ** 18
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
edge = [tuple(map(int, input().split())) for _ in range(m)]

for i in range(n):
    d[i][i] = 0
for a, b, c in edge:
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for a, b, c in edge:
    if d[a-1][b-1] != c:
        ans += 1
print(ans)

Measured memory_bytes: 42604
n,t = map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(n)]
#print(l)

l = sorted(l)
#print(l)

for j in range(n):
    if l[j][1] <= t:
        print(l[j][0])
        break
else:
    print('TLE')



Measured memory_bytes: 3060
#include<stdio.h>

int main(void) {
	int N;
	int a, b, c;
	scanf("%d", &N);

	a = N / 1000;
	b = (a + 1) * 1000;
	c = b - N;
	if (c == 1000) {
		c = 0;
	}
	printf("%d", c);

	return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int pw(int n,int k){
  int res=1;
  while(k){
    if(k&1)res*=n;res%=MOD;
    n*=n;n%=MOD;
    k>>=1;
  }
  return res;
}
std::vector<int> v(1e6,0);
int Z=pw(2,18);
void update(int a,int b,int k,int l,int r){
  if(r<=a||b<=l)return;
  if(a<=l&&r<=b)v[k]++;
  else{
    update(a,b,k*2+1,l,(l+r)/2);
    update(a,b,k*2+2,(l+r)/2,r);
  }
}
void pl(int a){
  update(a,Z,0,0,Z);
}
int find(int a){
  int k=a+Z-1;
  int res=v[k];
  while(k){
    k=(k-1)/2;
    res+=v[k];
  }
  return res;
}
//main
signed main(){
  string s;cin>>s;
  std::vector<int> v(26,0);
  for(char p:s)v[p-'a']++;
  int odd=0;
  int ans=0;
  for(int i=0;i<26;i++)odd+=v[i]&1;
  if(odd>1){cout<<-1<<endl;return 0;}
  int N=s.size();
  std::vector<int> po[26];
  for(int i=0;i<N;i++)po[s[i]-'a'].push_back(i);
  std::vector<int> now(26);
  for(int i=0;i<26;i++)now[i]=po[i].size()-1;
  int q=0;
  int opo=-1;
  if(odd==1)for(int i=0;i<26;i++)if(v[i]&1)opo=i;
  opo=po[opo][v[opo]/2];
  if(odd){
    for(int i=0;i<N;i++){
      int a=s[i]-'a';
      if(v[a]==1){v[a]--;continue;}
      if(v[a]==0)continue;v[a]-=2;
      if(q>=opo-find(opo)){ans++;opo++;}
      ans+=abs(N-1-q++-(po[a][now[a]]-find(po[a][now[a]])));
      //cout<<q<<" "<<po[a][now[a]]<<" "<<find(po[a][now[a]])<<endl;
      pl(po[a][now[a]--]);
      //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
  }
  for(int i=0;i<N;i++){
    int a=s[i]-'a';
    if(v[a]==1){v[a]--;continue;}
    if(v[a]==0)continue;v[a]-=2;
    ans+=abs(N-1-q++-(po[a][now[a]]-find(po[a][now[a]])));
    //cout<<q<<" "<<po[a][now[a]]<<" "<<find(po[a][now[a]])<<endl;
    pl(po[a][now[a]--]);
    //cout<<ans<<endl;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 11000
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cctype>
#include <map>
#include <set>

using namespace std;

int main()
{
    long long n, k;
    cin >> n >> k;
    vector<long long> v(n + 1);
    vector<long long> num(200500, 0);
    map<long long, long long> m;
    for (long long i = 1; i <= n; i++)
    {
        cin >> v[i];
    }

    long long now = 1;
    m[1] = 1;
    num[1] = 0;
    long long count = 0;
    for (long long i = 0; i < k; i++)
    {
        count++;
        now = v[now];

        if (m[now] == 1)
        {
            long long rev = count - num[now];
            long long ans = (k - num[now]) % rev;
            for (long long j = 0; j < ans; j++)
            {
                now = v[now];
            }
            break;
        }
        else
        {
            num[now] = count;
            m[now] = 1;
        }
    }

    cout << now << endl;

    return 0;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll r;
    cin >> r;

    cout << r*r*3 << endl;
    return 0;
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
// #define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int x, y; cin >> x >> y;
    vec a = {1, 3, 5, 7, 8, 10, 12};
    vec b = {4, 6, 9, 11};
    if(count(all(a), x) && count(all(a), y)){
        cout << "Yes" << endl;
        return;
    }
    if(count(all(b), x) && count(all(b), y)){
        cout << "Yes" << endl;
        return;
    }
    cout << "No" << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 7692
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pf push_front
#define f first
#define s second
#define mk make_pair
#define MOD 1000000007
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	ll a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	ll n;
	cin>>n;
	cout<<a[n-1];
  return 0;
}


Measured memory_bytes: 256
def solve():
    g, list_of_p_and_c = read()
    result = think(g, list_of_p_and_c)
    write(result)


def read():
    d, g = read_int(2)
    list_of_p_and_c = []
    for i in range(d):
        list_of_p_and_c.append(read_int(2))
    return g, list_of_p_and_c


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(g, list_of_p_and_c):
    complete_bonus = []
    list_of_question_remained = []
    for p, c in list_of_p_and_c:
        list_of_question_remained.append(p)
        complete_bonus.append(c)

    return recursive_call(g, complete_bonus, list_of_question_remained, 0, 0, False, -1, {})


def recursive_call(g, complete_bonus, list_of_question_remained, questions_solved, subsum, in_halfway, what_of_halfway, cache):
    key = generate_key_for(list_of_question_remained)
    if key in cache:
        return cache[key]

    if subsum >= g:
        return questions_solved

    max_p = 100
    max_d = 10

    invalid = max_p * max_d + 1
    minimum_questions_to_be_solved = invalid

    local_list_of_question_remained = list(list_of_question_remained)

    if in_halfway:
        if list_of_question_remained[what_of_halfway] == 0:
            return invalid
        local_list_of_question_remained[what_of_halfway] -= 1
        return recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + 1, subsum + 100 * (what_of_halfway + 1), True, what_of_halfway, cache)
    else:
        for i in range(len(list_of_question_remained)):
            if list_of_question_remained[i] == 0:
                continue  # already greedyed

            # case 1. greedy
            new_subsum = subsum + 100 * (i + 1) * list_of_question_remained[i] + complete_bonus[i]
            local_list_of_question_remained = list(list_of_question_remained)
            buf = local_list_of_question_remained[i]
            local_list_of_question_remained[i] = 0
            buf_2 = recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + buf, new_subsum, False, -1, cache)

            minimum_questions_to_be_solved = min(minimum_questions_to_be_solved, buf_2)

            # case 2. not greedy, halfway
            new_subsum = subsum + 100 * (i + 1)
            local_list_of_question_remained = list(list_of_question_remained)
            local_list_of_question_remained[i] -= 1
            buf_2 = recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + 1, new_subsum, True, i, cache)

            minimum_questions_to_be_solved = min(minimum_questions_to_be_solved, buf_2)

    cache[key] = minimum_questions_to_be_solved
    return minimum_questions_to_be_solved


def generate_key_for(list_of_question_remained):
    return ','.join(map(str, list_of_question_remained))


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 56536
#include<iostream> 
using namespace std; 
int t[6][6],dp[6][6],ph[6][6],pw[6][6],n,mx,mnh,lmx; 
void init(){ 
  for(int j=1;j<6;j++){ 
    for(int k=1;k<6;k++){ 
      cin>>t[j][k]; 
    } 
  } 
  mx=0; 
  for(int i=0;i<6;i++){ 
    t[i][0]=t[0][i]=0; 
    for(int j=0;j<6;j++){ 
      dp[i][j]=ph[i][j]=pw[i][j]=0; 
    } 
  } 
} 
int main(){ 
  cin>>n; 
  for(int N=0;N<n;N++){ 
    init(); 
    for(int i=1;i<6;i++){ 
      for(int j=1;j<6;j++){ 
    if(t[i][j]==0){dp[i][j]=ph[i][j]=pw[i][j]=0;continue;} 
    ph[i][j]=ph[i-1][j]+1;   pw[i][j]=pw[i][j-1]+1; 
  
    lmx=0;mnh=10; 
    for(int k=0;k<pw[i][j];k++){ 
      if(mnh>=ph[i][j-k])mnh=ph[i][j-k]; 
      if(lmx<mnh*(k+1))lmx=mnh*(k+1); 
    } 
    dp[i][j]=lmx; 
      
  
    if(mx<dp[i][j])mx=dp[i][j]; 
      } 
    } 
    /* 
    for(int x=1;x<6;x++){ 
      for(int y=1;y<6;y++){ 
        cout<<dp[x][y]; 
      } 
      cout<<endl; 
      }*/
    cout<<mx<<endl; 
  } 
  return 0; 
}

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

#define FOR(i, a, b) for (int i = (a); i < static_cast<int>(b); i++)
#define FORR(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) FOR (i, 0, n)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
template <typename T>
void print(const vector<vector<T>> matrix);
template <typename T>
void print(const vector<T> vec);
template <typename Arg>
void print(const Arg arg);
template <typename Head, typename... Args>
void print(const Head head, const Args... args);
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;

int h, w;
bool in(int x, int y) { return x >= 0 and x < h and y >= 0 and y < w; }
int dh[] = {-1, 0, 0, 1};
int dw[] = {0, -1, 1, 0};

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

    cin >> h >> w;
    vector<vector<char>> pic;
    char c;
    rep (i, h) {
        vector<char> v;
        rep (j, w) {
            cin >> c;
            v.pb(c);
        }
        pic.pb(v);
    }

    rep (i, h) {
        rep (j, w) {
            if (pic[i][j] == '.') continue;
            bool bocchi = true;
            rep (k, 4) {
                int x = i + dh[k], y = j + dw[k];
                if (in(x, y) and pic[x][y] == '#') bocchi = false;
            }
            if (bocchi) {
                print("No");
                return 0;
            }
        }
    }

    print("Yes");

    return 0;
}

//---------------------------------------------
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    repall (i, vec)
        cout << i << ' ';
    cout << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <functional>

struct edge{
	int to,cost;
	edge()=default;
	edge(int _t,int _c) : to(_t), cost(_c) {}
};

constexpr int MAX_N=100,INF=(int)1e9;

using P=std::pair<int,int>;

int n,k;

std::vector<edge> G[MAX_N];

int d[MAX_N];

int dijkstra(int s,int g){

	std::priority_queue<P,std::vector<P>,std::greater<P>> que;
	std::fill(d,d+n,INF);
	d[s]=0;
	que.emplace(d[s],s);

	while(!que.empty()) {
		P p=que.top();
		que.pop();
		int v=p.second;
		if(v==g)
			return d[g];
		if(p.first>d[v])
			continue;
		for(int i=0;i<G[v].size();++i){
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				que.emplace(d[e.to],e.to);
			}
		}
	}
	return -1;
}

int main() {
	while(1){
		std::cin>>n>>k;
		if(n+k==0)
			break;
		for(int i=0;i<n;++i)
			G[i].clear();
		int filter;
		for(int i=0;i<k;++i){
			std::cin>>filter;
			if(filter){
				int a,b,c;
				std::cin>>a>>b>>c;
				--a;
				--b;
				G[a].emplace_back(b,c);
				G[b].emplace_back(a,c);
			}
			else{
				int a,b;
				std::cin>>a>>b;
				--a;
				--b;
				std::cout<<dijkstra(a,b)<<std::endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long int;
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; }
const ll INF = 1e11;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
int main(){
    ll dp[1005][1005];
    string grid[1005],s;
    int h,w;
    cin >> h >> w;
    rep(i,h){
        cin >> s;
        grid[i+1] = '#'+s+'#';
    }
    s = "";
    rep(i,w+2) s+='#';
    grid[0] = s;
    grid[h+1] = s;
    ll a = 0,b = 0;
    rep(i,h+1){
        rep(j,w+1){
            if (grid[i][j] == '#') dp[i][j] = 0;
            else if (i == 1 && j == 1) dp[i][j] = 1;
            else dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
        }
    }
    PRINT(dp[h][w]);
}

Measured memory_bytes: 10112
import java.util.*;
 
class Main{
    public static void main(String[] args){
		
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int l = scan.nextInt();

		long[][] a = new long[n][m];
		long[][] b = new long[m][l];
		long[][] c = new long[n][l];
		long sum = 0;
		//a???????????????
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				a[i][j] = scan.nextLong();
			}
		}
		//b???????????????
		for(int i=0; i<m; i++){
			for(int j=0; j<l; j++){
				b[i][j] = scan.nextLong();
			}
		}
		//??????c?????????????´?
		for(int i=0; i<n; i++){
			for(int j=0; j<l; j++){
				sum = 0;
				for(int k=0; k<m; k++){
					sum += a[i][k] * b[k][j];
				}
				c[i][j] = sum;
			}
		}
		//???????????????
		for(int i=0; i<n; i++){
			for(int j=0; j<l; j++){
				System.out.print(c[i][j]);
				if(j < l-1){
				System.out.print(" ");
				}
			}
			System.out.println("");
		}
    }
}

Measured memory_bytes: 53964
/*  -*- coding: utf-8 -*-
 *
 * a.cc: C: Chocolate Bar
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

typedef long long ll;
const ll LINF = 1LL << 60;

/* typedef */

/* global variables */

/* subroutines */

ll diff(ll a0, ll a1, ll a2) {
  //printf("a0=%lld, a1=%lld, a2=%lld\n", a0, a1, a2);
  ll mina = min(a0, min(a1, a2));
  ll maxa = max(a0, max(a1, a2));
  return maxa - mina;
}

inline void setmin(ll &a, ll b) { if (a > b) a = b; }

/* main */

int main() {
  ll h, w;
  cin >> h >> w;

  ll hw = h * w, hwt = hw / 3;
  if (hwt * 3 == hw) {
    puts("0");
    return 0;
  }
  //printf("%lld x %lld = %lld (%lld)\n", h, w, hw, hwt);

  ll mind = LINF;
  for (int i = 0; i < 2; i++) {
    ll ht = h / 3, wt = h / 3;
    for (int h0 = hwt / w; h0 <= hwt / w + 1; h0++) {
      ll h1 = h - h0, s0 = h0 * w;
      if (h0 == 0 || h1 == 0) continue;

      setmin(mind, diff(s0, (h1 / 2) * w, (h1 - h1 / 2) * w));
      setmin(mind, diff(s0, h1 * (w / 2), h1 * (w - w / 2)));
    }
    swap(h, w);
  }

  printf("%lld\n", mind);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin >> N >> K;
  int h[N];
  for(int i=0; i < N; i++){
    cin >> h[i];
  }
  int ans = 0;
  for(int i=0; i < N; i++){
    if(h[i] >= K)  ans++;
  }
  cout << ans <<endl;
}

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

int main(int argc, char *argv[])
{
  int W,a,b;
  cin>>W>>a>>b;
  int d=abs(a-b);
  if(d<=W){
    cout << 0 << "\n";
  }else{
    cout << d-W  << "\n";
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    int A[1005]={};
    cin>>N>>M;
    int s;
    for(int i=0;i<M;i++){
        cin>>s;
        A[s]=1;
    }
    int cnt=0;
    for(int i=1;i<=M;i++){
        if(A[i]==0) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}



Measured memory_bytes: 3100
#if 0
date +%Y.%m.%d
 
题解先咕着。
#endif
#include <cstdio>
#include <set>
#include <queue>
#define debug(...) fprintf(stderr, __VA_ARGS__)
 
inline int input() { int x; scanf("%d", &x); return x; }
 
const int maxn = 100005;
int fa[maxn];
std::multiset<int> A[maxn], B[maxn];
 
int find(int x) {
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
 
int main() {
	int n = input();
	for(int i = 1; i <= n; i ++)
		fa[i] = i;
	for(int i = 1; i < n; i ++) {
		int x = input(), y = input();
		A[x].insert(y);
		A[y].insert(x);
	}
	std::queue<int> q1, q2;
	for(int i = 1; i < n; i ++) {
		int x = input(), y = input();
		if(A[x].count(y)) {
			q1.push(x);
			q2.push(y);
		}
		B[y].insert(x);
		B[x].insert(y);
	}
	int tot = 0;
	while(not q1.empty()) {
		tot ++;
		int x = find(q1.front()), y = find(q2.front());
#if 0
		debug("%d %d\n", x, y);
		for(int z : A[x])
			debug("%d in A[%d]\n", z, x);
		for(int z : A[y])
			debug("%d in A[%d]\n", z, y);
		for(int z : B[x])
			debug("%d in B[%d]\n", z, x);
		for(int z : B[y])
			debug("%d in B[%d]\n", z, y);
#endif
		q1.pop();
		q2.pop();
		A[x].erase(y);
		A[y].erase(x);
		B[x].erase(y);
		B[y].erase(x);
		bool rev = A[x].size() + B[x].size() > A[y].size() + B[y].size();
		if(rev)
			std::swap(x, y);
		fa[x] = y;
#if 0
		debug("%d %d\n", x, y);
		for(int z : A[x])
			debug("%d in A[%d]\n", z, x);
		for(int z : A[y])
			debug("%d in A[%d]\n", z, y);
		for(int z : B[x])
			debug("%d in B[%d]\n", z, x);
		for(int z : B[y])
			debug("%d in B[%d]\n", z, y);
#endif
		for(int z : A[x])
			if(B[y].count(z)) {
				q1.push(y);
				q2.push(z);
			}
		for(int z : B[x])
			if(A[y].count(z)) {
				q1.push(y);
				q2.push(z);
			}
		for(int z : A[x]) {
			A[y].insert(z);
			while(A[z].count(rev ? x : x)) {
				A[z].erase(A[z].find(x));
				A[z].insert(y);
			}
		}
		for(int z : B[x]) {
			B[y].insert(z);
			while(B[z].count(rev ? x : x)) {
				B[z].erase(B[z].find(x));
				B[z].insert(y);
			}
		}
	}
	if(tot == n - 1)
		puts("YES");
	else
		puts("NO");
}


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

struct edge {
    int from, to, cost;
};
struct graph {
    int n;
    vector<vector<edge>> G;
    vector<bool> visited;
    graph(int n_) {
        n = n_;
        G.resize(n);
        visited.resize(n, false);
    }
    void add_edge(int from, int to, int cost) {
        G[from].push_back({from, to, cost});
    }
    void dfs(int s, int i, int _n) { // 深さ制限探索
        visited[s] = true;
        if (i == _n) return;
        for (edge e : G[s]) {
            if (visited[e.to]) continue;
            dfs(e.to, i + 1, _n);
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    graph G(n);
    rep(i, m) {
        int from, to, cost = 0;
        cin >> from >> to;
        from--; to--;
        G.add_edge(from, to, cost);
    }
    G.dfs(0, 0, 2);
    cout << (G.visited[n-1] ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

Measured memory_bytes: 12184
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
	for(int i=0; i<3; ++i){
		int a[3], b[3];
		long c[2]={0};
	
		for(int j=0; j<3; ++j){
			scanf(" %d", &a[j]);
			c[0] += a[j]*(int)pow(60, 2-j);
		}	
		for(int j=0; j<3; ++j){
			scanf(" %d", &b[j]);
			c[1] += b[j]*(int)pow(60, 2-j);
		}
		
		long diff=c[1]-c[0];
		long h, m;
		
		h=diff/3600;
		diff-=3600*h;
		m=diff/60;
		diff-=60*m;
		
		printf("%ld %ld %ld\n", h, m, diff);
	}
	return 0;
}

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

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

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

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

int main(void){
    int A,B,K; cin >> A >> B >> K;
    int t = 0;
    RFOR(i,max(A,B)+1,0){
        if(A%i==0 && B%i==0) t++;
        if(K == t){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

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

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

//     int sum_1 = 0;
//     for (int i = 1; i < n; i++){
//         if (s[i] == 'E') sum_1 ++;
//     }

//     int currentmin = sum_1;

//     for (int i = 1; i < n; i++){
//         if(s[i - 1] == 'W') sum_1 ++;
//         if(s[i] == 'E') sum_1 --;
//         if (sum_1 < currentmin) currentmin = sum_1;
//     }
 
//     cout << currentmin << endl;
//     return 0;
// }

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

    //累積和
    // int sum[n];
    // for (int i = 0; i < n; i++) sum[i] = 0;

    // for (int i = 0; i < n; i++){
    //     for (int j = 0; j <= i; j++){
    //         if(s[j] == 'W') sum[i] += 1;
    //     }
    // }

    int counter = 0;
    int sum[n];
    for (int i = 0; i < n; i++) sum[i] = 0;

    for (int i = 0; i < n; i++){
        if (s[i] == 'W') counter ++;
        sum[i] = counter;
        // cout << sum[i] << endl;
    }

    int currentmin = 0;
    // int counter = 0;
    counter = 0;

    for (int i = 0; i < n; i++){
        if (i == 0) {
            counter = n - sum[n-1];
            currentmin = counter;
        }else{
            counter = sum[i - 1] + ( ( n - ( i + 1 )) - (sum[n-1] - sum[i]) );
            if (counter < currentmin) currentmin = counter;
        }
        // cout << counter << currentmin << endl;
    }
    cout << currentmin << endl;
    
    return 0;
}

Measured memory_bytes: 1796
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define MEM(a,b) memset(a,b,sizeof(a))
#define ALL(x) (x).begin(),(x).end()
#define LMAX 9223372036854775807
#define LMIN -9223372036854775808

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ull, ull> UP;
typedef tuple<int, int, int> T;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int gcd(int a, int b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
int digisum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}

ll cnt[502][502];

int main() {
	int a, b;
	cin >> a >> b;
	string ans;
	if (a < 9 && b < 9)ans = "Yay!";
	else ans = ":(";
	cout << ans << endl;
}



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

typedef long long ll;
double w,h,x,y;

int main()
{
    scanf("%lf %lf %lf %lf",&w,&h,&x,&y);
    double t = w*h;
    double ans = t*1.0/2;
    printf("%.6f ",ans);
    if(x*2==w && y*2==h)
        printf("1\n");
    else
        printf("0\n");
    return 0;
}


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL MOD = 1e9+7;

int main() {
    string s;
    cin >> s;
    int y = stoi(s.substr(0, 4));
    int m = stoi(s.substr(5, 2));
    int d = stoi(s.substr(8, 2));
    if(2019 < y) {
        cout << "TBD" << endl;
    }else if(4 < m) {
        cout << "TBD" << endl;
    }else{
        cout << "Heisei" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <math.h>
#include <string>
typedef long long ll;

using namespace std;

int main(){
    int N;
    cin >> N;
    int res[210] = {0};
    for (int i = 0; i < N; i++){
	int a;
	int cnt = 0;
	cin >> a;
	while (a%2 == 0){
	    cnt++;
	    a /= 2;
	}
	res[i] = cnt;
    }

    sort(res, res+N);
    cout << res[0] << endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.*;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();
        int k = in.nextInt();
        int[] h = new int[n];
        for (int i=0; i < n; i++)
            h[i] = in.nextInt();

        int[] dp = new int[n];
        // i = target
        for (int i=1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            // j = from
            for (int j=i-1; j >= Math.max(0, i-k); j--) {
                min = Math.min(min, dp[j] + Math.abs(h[j] - h[i]));
            }
            dp[i] = min;
        }

        out.println(dp[n-1]);
    }

}


Measured memory_bytes: 48724
from pprint import pprint


n = int(input())

points = [list(map(int,input().split())) for _ in range(n)]

dp_table = [[-float("inf")]*(n+1) for _ in range(3)]

#0日目は幸福度0
dp_table[0][0] = 0
dp_table[1][0] = 0
dp_table[2][0] = 0

for i in range(1,n+1):
    for abc in range(3):
        for before_abc in range(3):
            if abc != before_abc:
                dp_table[abc][i] = max(dp_table[abc][i],dp_table[before_abc][i-1] + points[i-1][abc])
            else:
                continue

pprint(max(dp_table[0][-1],dp_table[1][-1],dp_table[2][-1]))


Measured memory_bytes: 75992
#include<stdio.h>

int main (void){

	int x[3000],y[3000];
	int i;
	int a,b,c;
	x[3000] >= 0;
	y[3000] <= 10000;

for(i = 0;i <3000; i++){

	scanf("%d %d" ,&x[i] ,&y[i]);
	
	if(x[i] == 0 && y[i] == 0){
	break;
	}
	c++;
}

for(i = 0; i < c; i++){

	
	if (x[i] <= y[i]){
	a = x[i];
	b = y[i];
	}else{
	a = y[i];
	b = x[i];
	}
	
	printf("%d %d\n", a, b);
}

return 0;
}

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

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

const int N = 200005;
int val[N], pw[N];

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

	int n, p;
	string s;
	cin>>n>>p>>s;
	if(p == 2 || p == 5){
		ll ans = 0;
		for(int i = 0; i < n; i++){
			int x = s[i] - '0';
			if(x%p == 0)ans += i + 1;
		}
		cout<<ans<<endl;
		exit(0);
	}
	pw[0] = 1;
	for(int i = 1; i <= n; i++){
		pw[i] = (pw[i-1]*1LL*10)%p;
	}
	ll ans = 0;
	map<int, int> arr;
	arr[0]++;
	ll tmp = 0;
	for(int i = 0; i < n; i++){
		tmp = 10*tmp + s[i] - '0';
		tmp %= p;
		ll tmp2 = (tmp*pw[n-i])%p;
		ans += arr[tmp2];
		arr[tmp2]++;
		// cout<<tmp<<" "<<pw[n-i]<<" "<<tmp2<<endl;;
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 1684
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
#define lb lower_bound
#define ub upper_bound
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);ios::sync_with_stdio(false);



signed main(){
  ll n,l;cin>>n>>l;
  vector<ll> v(n);
  rep(i,n)cin>>v[i];

  ll ind=0;
  rep(i,n-1){
    if(v[i]+v[i+1]>=l){
      ind=i+1;
    }
  }

  if(!ind){
    cout<<"Impossible"<<endl;
  }else{
    cout<<"Possible"<<endl;

    for(int i=1;i<ind;i++){
      cout<<i<<endl;
    }
    for(int i=n-1;ind<=i;i--){
      cout<<i<<endl;
    }
  }
}

Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define SEG (1 << 18)

const long long inf = 2e18;

struct segtree {
    pair<long long, int> dat[SEG * 2];

    void update(int k, long long v, int id) {
        k += SEG;
        dat[k] = {v, id};
        while (k > 1) {
            k >>= 1;
            dat[k] = min(dat[k * 2], dat[k * 2 + 1]);
        }
    }

    pair<long long, int> query(int l, int r) {
        l += SEG;
        r += SEG;
        pair<long long, int> res(inf, -1);
        while (l < r) {
            if (l & 1) res = min(res, dat[l++]);
            if (r & 1) res = min(res, dat[--r]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

segtree L, R;

vector<int> dat[200000];
int par[200000];

int find(int u) {
    if (par[u] == u) return u;
    return par[u] = find(par[u]);
}

void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (dat[u].size() < dat[v].size()) {
        swap(u, v);
    }
    dat[u].insert(dat[u].end(), dat[v].begin(), dat[v].end());
    par[v] = u;
}

int N;
long long D;
long long A[200000];

int main() {
    scanf("%d %lld", &N, &D);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
        par[i] = i;
        dat[i].push_back(i);
    }
    int c = N;
    long long ans = 0;
    while (c >= 2) {
        for (int i = 0; i < N; i++) {
            L.update(i, A[i] - i * D, find(i));
            R.update(i, A[i] + i * D, find(i));
        }
        vector<long long> cost;
        vector<int> from;
        vector<int> to;
        for (int i = 0; i < N; i++) {
            if (find(i) != i) continue;
            pair<long long, int> mn(inf, -1);
            for (int j : dat[i]) {
                L.update(j, inf, find(j));
                R.update(j, inf, find(j));
            }
            for (int j : dat[i]) {
                auto x = L.query(0, j);
                auto y = R.query(j, N);
                x.first += A[j] + j * D;
                y.first += A[j] - j * D;
                mn = min(mn, x);
                mn = min(mn, y);
            }
            for (int j : dat[i]) {
                L.update(j, A[j] - j * D, find(j));
                R.update(j, A[j] + j * D, find(j));
            }
            cost.push_back(mn.first);
            from.push_back(i);
            to.push_back(mn.second);
        }
        for (int i = 0; i < cost.size(); i++) {
            if (find(from[i]) == find(to[i])) continue;
            unite(from[i], to[i]);
            ans += cost[i];
            c--;
        }
    }
    printf("%lld\n", ans);
    return 0;
}



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

char tbl1[26],tbl2[26];

int main(){
	string s,t;
	cin>>s>>t;
	for(int i=0;i<26;i++){
		tbl1[i]='Z';
		tbl2[i]='Z';
	}
	string ans="Yes";
	for(int i=0;i<s.size();i++){
		if(tbl1[s[i]-'a']=='Z'){
			tbl1[s[i]-'a']=t[i];
		}else{
			if(tbl1[s[i]-'a']!=t[i])ans="No";
		}
	}
	for(int i=0;i<t.size();i++){
		if(tbl2[t[i]-'a']=='Z'){
			tbl2[t[i]-'a']=s[i];
		}else{
			if(tbl2[t[i]-'a']!=s[i])ans="No";
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 776
from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                if dpr[k][a] < b:
                    a = dpr[k][a]
                    ans += 2**k
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] > b:
                    a = dpl[k][a]
                    ans += 2**k
        print(ans+1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 96288
n, m = map(int, input().split())

N=[1]*n
D=[]
for i in range(m):
    p, y = map(int, input().split())
    D.append([i,p,y])

D.sort(key= lambda x:x[2] )
for i in range(m):
    D[i].append(N[D[i][1]-1])
    N[D[i][1]-1]+=1

D.sort()
for d in D:
    print("{:0>6}{:0>6}".format(d[1],d[3]))


Measured memory_bytes: 31892
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

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

int main(){
    int n, k;
    int l[60];
    cin >> n >> k;
    rep(i, n) cin >> l[i];
    sort(l, l+n);
    int i;
    int ans = 0;
    for(i = n-1; i >= n - k; i--){
        ans = ans + l[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
counter = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            counter += 1

counter2 = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            counter2 += 1

ans = 0
ans += counter * K
ans += counter2 * (K * (K - 1) // 2)
print(ans % mod)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mpr make_pair
#define MX 100010
#define ui unsigned int
#define ll long long
#define ld long double 
#define fi first
#define se second
#define endl '\n'
#define debug(bug) cout<<"akshat"<<" "<<bug<<endl
#define printarray(Aneveruse,neverusen) for(int neveruse=0;neveruse<neverusen;neveruse++) cout<<Aneveruse[neveruse]<<" "; cout<<endl
#define printvector(Aneveruse,neverusen) for(int neveruse=0;neveruse<neverusen;neveruse++) cout<<Aneveruse[neveruse]<<" "; cout<<endl
#define dd long double 
#define timetaken cerr<<clock()/double(CLOCKS_PER_SEC)<<endl
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL)
const ll inf=1000000000000;
const int mod=1000000007;
// priority_queue <int, vector<int>, greater<int> > pq; //minimum priority queue
int n,w1;
int w[MX];
int v[MX];
ll dp[MX][101];
ll solve(int W,int i)
{
   if(W<0)
   {
    return -inf;
   }
   if(i==n || W==0)
   {
    return 0;
   }
   if(dp[W][i]!=-1)
   {
    return dp[W][i];
   }

   return dp[W][i]=max(v[i]+solve(W-w[i],i+1),solve(W,i+1));
}


int main()
{
  fast_io;
  memset(dp,-1,sizeof(dp));
  cin>>n>>w1;
  for(int i=0;i<n;i++)
  {
    cin>>w[i];cin>>v[i];
  }

  cout<<solve(w1,0)<<endl;


 
  return 0;
}


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

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

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

int main() {
  long long a, b, c, t;
  cin >> a >> b >> c;
  t = c - a - b;
  if (t > 0 && t * t > 4 * a * b) cout << "Yes\n";
  else cout << "No\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

ll gcd(ll x, ll y){ return y ? gcd(y, x%y) : x;}

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 main(){
    ll a, b;
    cin >> a >> b;
    ll g = gcd(a,b);
    auto f = factorize(g);
    int ans = f.size() + 1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize n;
    std::cin >> n;
    std::cout << (n<1200 ? "ABC" : "ARC") << '\n';
}


Measured memory_bytes: 256