akhauriyash/Code-Regression huggingface dataset:
use std::fmt::{Debug, Display};
use std::io::{self, Read};
use std::str::{self, FromStr};


fn solve(s: String) -> String {
    let mut dict = [false; 26];
    for c in s.as_bytes() {
        dict[(c - 'a' as u8) as usize] = true;
    }
    for (i, &b) in dict.into_iter().enumerate() {
        if !b {
            return format!("{}", (i as u8 + ('a' as u8)) as char);
        }
    }
    "None".to_owned()
}


fn main() {
    let stdin = io::stdin();
    let mut sc = Scanner::new(stdin.lock().bytes());
    println!("{}", solve(sc.next()));
}


struct Scanner<R: Read> {
    buf: Vec<u8>,
    bytes: io::Bytes<R>,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(bytes: io::Bytes<R>) -> Self {
        Scanner {
            buf: Vec::with_capacity(256),
            bytes: bytes,
        }
    }

    fn next<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        self.buf.clear();
        for c in self.bytes
            .by_ref()
            .map(|c| c.unwrap())
            .skip_while(|&c| c == ' ' as u8 || c == '\n' as u8)
            .take_while(|&c| !(c == ' ' as u8 || c == '\n' as u8))
        {
            self.buf.push(c);
        }
        str::from_utf8(&self.buf).unwrap().parse().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..n).map(|_| self.next()).collect()
    }

    fn pairs<A: FromStr, B: FromStr>(&mut self, n: usize) -> Vec<(A, B)>
    where
        <A as FromStr>::Err: Debug,
        <B as FromStr>::Err: Debug,
    {
        (0..n).map(|_| (self.next(), self.next())).collect()
    }

    fn trios<A: FromStr, B: FromStr, C: FromStr>(&mut self, n: usize) -> Vec<(A, B, C)>
    where
        <A as FromStr>::Err: Debug,
        <B as FromStr>::Err: Debug,
        <C as FromStr>::Err: Debug,
    {
        (0..n)
            .map(|_| (self.next(), self.next(), self.next()))
            .collect()
    }

    fn mat<T: FromStr>(&mut self, m: usize, n: usize) -> Vec<Vec<T>>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..n).map(|_| self.vec(m)).collect()
    }
}


#[allow(dead_code)]
fn print_foreach<T: Display>(answer: &[T]) {
    for x in answer {
        println!("{}", x);
    }
}


#[allow(dead_code)]
fn print_yn(answer: bool, yes: &str, no: &str) {
    println!("{}", if answer { yes } else { no });
}


#[allow(dead_code)]
fn print_or<T: Display>(answer: &Option<T>, or: &T) {
    match *answer {
        Some(ref x) => println!("{}", x),
        None => println!("{}", or),
    }
}


Measured memory_bytes: 4352
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    counter = Counter(A)
    if N % 2 == 0:
        for n in range(1, N, 2):
            if counter[n] != 2:
                print(0)
                return
    else:
        if counter[0] != 1:
            print(0)
            return
        for n in range(2, N, 2):
            if counter[n] != 2:
                print(0)
                return
    print(pow(2, N // 2, MOD))


if __name__ == '__main__':
    solve()


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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int n;
vector<int> a;

// mid進法で+1する関数 可能ならばtrueを返し、不可能ならばfalseを返す
bool add(map<int, lint> &mp, lint mid, int d){
    mp.erase(mp.upper_bound(d), mp.end()); // 字数を減らす

    // mp[d]を生成すると同時にd文字目を足せるかどうか判定
    if(mp[d] < mid - 1){
        ++mp[d];
        return true;
    }

    // 後ろから順番に見る
    auto it1 = mp.end();
    --it1;
    while(it1 != mp.begin()){
        auto it2 = it1--; // it2は今いる桁 it1はそれより上の桁で0でないものが入っているところ、あるいは一番上の桁

        // 見ているところに足せればそれでok
        if((*it2).second < mid - 1){
            ++mp[(*it2).first];
            return true;

        // 見ているところと1個前の差が1より大きければ、見ているところの1つ上の桁を1として繰り上がりが終了
        }else if((*it1).first + 1 < (*it2).first){
            ++mp[(*it2).first - 1];
            mp.erase(it2);
            return true;

        // どちらにも当てはまらなければ見ているところの桁を0とし、繰り上がりを続ける
        }else{
            mp.erase(it2);
        }
    }

    // 一番上の桁まで来たら、その桁を足せるか判定
    if((*mp.begin()).second < mid - 1){
        ++(*mp.begin()).second;
        return true;
    }
    return false;
}

bool check(lint mid){
    map<int, lint> mp; // 0番目の文字以外が入るところを記録しておく
    mp[1] = 0; // 一番上の桁を番兵にしておく
    REP(i, 1, n){
        /* 字数が増えるときは0番目の文字を増える分だけ付け足せばよい
        字数が等しいあるいは減るときにmid進法内で辞書順を保てるか判定 */
        if(a[i - 1] >= a[i]){

            // 1種類のときは辞書順を保てない
            if(mid <= 1 || !add(mp, mid, a[i])){
                return false;
            }
        }
    }
    return true;
}

// 何種類文字があれば条件を満たせるか二分探索
lint meguruSearch(lint ok, lint ng){
    while(abs(ok - ng) > 1){
        lint mid = (ok + ng) / 2;
        if(check(mid)){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return ok;
}

int main(){
    cin >> n;
    a.resize(n);
    rep(i, n){
        cin >> a[i];
    }
    lint ans = meguruSearch(1e15, 0);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
n = int(input())
h = list(map(int,input().split()))
flag = True
for i in range(n-2, 0, -1):
  if h[i]-h[i+1]==1:
    h[i]-=1
  elif h[i]-h[i+1]>=2:
    flag=False
    break

print('Yes' if flag else 'No')


Measured memory_bytes: 14396
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
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()
{
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b && b == c)co("Yes");
	else co("No");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const std::string ans[2] = {"No\n", "Yes\n"};

int main() {
    using namespace std;
    string S;
    cin >> S;
    bool isKaibun = true;

    int n = S.length();  // n は奇数
    for (int i = 0; i < n / 2 && isKaibun; i++) {
        if (S[i] != S[n - i - 1]) isKaibun = false;
    }
    n /= 2;
    for (int i = 0; i < n && isKaibun; i++) {
        if (S[i] != S[n - i - 1]) isKaibun = false;
    }
    for (int i = 0; i < n && isKaibun; i++) {
        if (S[n + 1 + i] != S[S.length() - 1 - i]) isKaibun = false;
    }

    cout << ans[isKaibun];
    return 0;
}

Measured memory_bytes: 256
a,b = input().split(' ')
 
c = []
for i in range(int(a)):
  c.append(input().split(' '))

ans = 0
count = 0
for j in range(int(a)):
  for k in range(int(a)):
    if j > k:
        ans = 0
        for l in range(int(b)):
            ans = ans + (int(c[j][l]) - int(c[k][l])) ** 2
        if ans ** 0.5 == round(ans ** 0.5):
            count = count + 1

print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define im 2147483647
#define lm 9223372036854775807
#define ll long long
#define vb vector<bool>
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define ii pair<int, int>
#define lower_str(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define upper_str(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define debug(index, num) cout << "Case #" << index << ": " << num << endl
#define mx(an, na) an = max(an, na)
#define mn(an, na) an = min(an, na)
#define rep(i, a, b) for (long long i = a; i < b; i++)
#define rep2(i, a, b) for (long long i = a; i <= b; i++)
#define repp(i, a, b) for (long long i = a; i >= b; i--)
#define repp2(i, a, b) for (long long i = a - 1; i >= b; i--)
#define be(x) x.begin(), x.end()
#define rbe(x) x.rbegin(), x.rend()
#define pb push_back
vector<ll> v;
ll maxSum(int n) {
    int tempMax = v[0];
    int currentMax = tempMax;
    for (int i = 1; i < n-1; i++ ) { \
      currentMax = max(v[i], currentMax+v[i]);
      tempMax = max(tempMax, currentMax);
    }
    int f = tempMax;
    tempMax = v[1];
    currentMax = tempMax;
    for (int i = 2; i < n; i++ ) {
      currentMax = max(v[i], currentMax+v[i]);
      tempMax = max(tempMax, currentMax);
    }
   return max(f, tempMax);
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    char a;
    cin >> a;
    cout << (char)(a+1);
    return 0;
} 

Measured memory_bytes: 256
#include<stdio.h>
int n,k,a,i=-1,t[2];
int main(void){
	scanf("%d%d",&n,&k);
	while(++i<k){
		scanf("%d%d",t,t+1);
		if(t[0]>=n/2)t[0]=n-t[0]+1;
		if(t[1]>=n/2)t[1]=n-t[1]+1;
		if(t[0]>t[1])t[0]=t[1];
		a=t[0]%3;
		printf("%d\n",((a)?a:3));
	}
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

int main (void) {
    int N,K;
    cin>>N>>K;
    string S;
    cin>>S;
    vector<pair<int,int>> R;
    if (S.size() == 1) {
        cout<<1<<endl;
        return 0;
    }

    int temp = 1;
    for (int i=1;i<N;i++) {
        if (S[i] == S[i-1]) temp++;
        else {
            if (S[i] == '0') {
                R.pb(make_pair(temp,1));
            }
            else {
                R.pb(make_pair(temp,0));
            }
            temp = 1;
        }
    }
    if (S[N -1] == '1') {
        R.pb(make_pair(temp,1));
    }
    else {
        R.pb(make_pair(temp,0));
    }

    if (R[R.size()-1].se == 0) R.pb(make_pair(0,1));
    if (R[0].se == 0) R.insert(R.begin(),make_pair(0,1));
    int ans = 0;
    int M = R.size();
    int Znum = 0;

    vector<int> RS(M+5,0);
    REP(i,M) {
        RS[i + 1] = R[i].fi + RS[i];
    }
    
    int add = 2 * K + 1;
    for (int i=0;i<M;i+=2) {
        int left = i;
        int right = min(i + add, M);
        int sum = RS[right] - RS[left];
        ans = max(sum,ans);
    }

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

Measured memory_bytes: 1652
N,M = map(int,input().split())
chk = [-1] * N  #チェックコード
ans=0

#それぞれの値を配列に入れる
for m in range(M):
    s,c = map(int,input().split())
    if s==1 and c==0 and N!=1: # 2桁以上(N=2以上)かつ、左の桁が0の場合
        print(-1)
        exit()
    if chk[s-1] == -1: #初期値-1の場合s桁にcをいれる
        chk[s-1]=c
    elif chk[s-1] != -1: #初期値-1以外の場合
        if chk[s-1] != c: #s桁にすでに代入されている値以外が導入されている場合
            print(-1)
            exit()

for i in range(N):
    if chk[i] == -1: #初期値(-1)が残っているものは0に変える
        if i==0 and N!=1:
            chk[i] = 1
        else:
            chk[i] = 0
    #print(ans,(N-(i+1)))
    ans += chk[i]*(10**(N-(i+1)))
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

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

    int n; cin >> n;
    ll c; cin >> c;
    vector<ll> x(n+2, 0), v(n+2, 0);
    for(int i=1; i<=n; ++i) cin >> x[i] >> v[i];
    x[n+1] = c;

    vector<ll> cum(n+2, 0), f(n+2, 0), g(n+2, 0);
    for(int i=1; i<n+2; ++i) cum[i] = cum[i-1] + v[i];

    for(int i=2; i<n+2; ++i){
        f[i] = max(f[i-1], cum[i-1]-x[i-1]);
        g[i] = max(g[i-1], cum[i-1]-2*x[i-1]);
    }

    ll ans = 0;
    for(int i=0; i<n+2; ++i){
        chmax(ans, cum[n] - (i==0? 0:cum[i-1]) - 2*(c-x[i]) + f[i]);
        chmax(ans, cum[n] - (i==0? 0:cum[i-1]) - (c-x[i]) + g[i]);
    }

    cout << ans << endl;


	return 0;
}


Measured memory_bytes: 4224
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
const int MAX_N = 100100;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<ll> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    vector<ll> sum(n + 1, 0);
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + v[i - 1];
    sort(sum.begin(), sum.end());
    map<ll, ll> mp;
    for(int i = 0; i < sum.size(); i++) mp[sum[i]]++;
    ll res = 0;
    for(auto x : mp)
    { 
       res += x.second * (x.second - 1) / 2;
    }
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 15872
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 510000;
const int MOD = 1000000007;

  
        signed main() {
     int n;
     cin>>n;
     
     int t=n,k=1,d[n]={};
     string s(n,'a'),s2;
     cout<<s<<endl;
        while(t){
                if(t==n){t--;}
                else{
                        if(d[t-1]==(s[t]-'a')){
                                d[t]=d[t-1]+1;
                                for(int j=t;j<n;j++){d[j]=d[t];}
                                s[t]++;t=n-1;cout<<s<<endl;
                                continue;}
                        
                        if(d[t-1]<(s[t]-'a')){s[t]='a';t--;for(int j=t;j<n;j++){d[j]=d[t];}continue;}
                        s[t]++;
                        cout<<s<<endl;
                        t=n-1;
                }
        }
   
     
     
    

      
        


      }


        


Measured memory_bytes: 1536
s=input()
n=len(s)
i=1
c=1
r=s[0]
while(i<n):
    j=i
    t=''
    while(j<n):
        t+=s[j]
        if(t!=r):
            r=t
            c+=1
            break
        j+=1
    i=j+1
print(c)


Measured memory_bytes: 73248
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x,n,a,b,x1,x2;
	cin>>n>>a>>b;
	x1=n*a;x2=b;
	x=x1>x2?x2:x1;
	cout<<x;
	return 0;
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(LL (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(LL (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(LL (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;
using Pll = P<LL,LL>;
using Pdd = P<double,double>;
using Psi = P<string,double>;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T1,typename T2> using M = map< T1, T2>;
using Mii = M<int, int>;

template<typename T>
T count_nonzero(V<T> v){return count_if(ALL(v),[](int x){return x != 0;});}

const LL INFLL = 1LL<<40;

int main(){
    LL n,k;
    cin>>n>>k;
    V<Vll> sushi(n);
    REP(i,n){
        LL t,d;
        cin>>t>>d;
        t--;
        sushi[t].pb(d);
    }
    
    for(auto &v : sushi){
        sort(ALL(v),greater<LL>());
        if(v.empty()) v.pb(-INFLL);
    }

    sort(ALL(sushi),[&](Vll a, Vll b){return a[0]>b[0];});

    LL oishisa = 0;
    priority_queue<LL> q;
    REP(i,k){
        oishisa += sushi[i][0];
        REP2(j,1,sushi[i].size()) q.push(sushi[i][j]);
    }
    REP2(i,k,n){
        REP(j,sushi[i].size()) q.push(sushi[i][j]);
    }

    LL manzoku = oishisa + k*k;
    REPD2(x,k-1,1){
        LL v = sushi[x][0];
        LL w = q.top();
        if(v<w){
            q.pop();
            oishisa += w;
            q.push(v);
            oishisa -= v;
        }
        manzoku = max(manzoku, oishisa + x*x);
    }

    cout<<manzoku<<endl;

    return 0;
}



Measured memory_bytes: 8696
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

ll calc(ll N, ll div) {
    if (N < div) return N;
    return N%div + calc(N/div, div);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, S;
    cin >> N >> S;
    //for (int i = 2; i <= N; i++) {
    //    cout << i << " " << calc(N, i) << endl;
    //}
    ll last = -1;
    for (ll i = 2; i*i <= N; i++) {
        last = i;
        if (calc(N, i) == S) {
            cout << i << endl;
            return 0;
        }
    }
    for (ll i = last; i > 1; i--) {
        ll start = N/i+1;
        ll last = N/(i-1);
        ll tmp = calc(N, start);
        if (tmp >= S && (tmp-S)%(i-1) == 0) {
            ll o = (tmp-S)/(i-1);
            if (start+o > last) continue;
            cout << start+o << endl;
            return 0;
        }
    }
    if (S == N) cout << N+1 << endl;
    else if (S == 1) cout << N << endl;
    else cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
    class Program
    {
        static void Main(string[] args)
        {
            int w = int.Parse(Console.ReadLine());
            int n = int.Parse(Console.ReadLine());
            int[] a = new int[n + 1];
            int[] b = new int[n + 1];
            for (int i = 1; i < n + 1; i++)
            {
                string []str = Console.ReadLine().Split(',');
                a[i] = int.Parse(str[0]);
                b[i] = int.Parse(str[1]);
            }
            int []wans=new int[w+1];
            for (int i = 1; i < w + 1; i++)
            {
                wans[i] = i;
                for (int j = n; j > 0; j--)
                {
                    if (wans[i] == a[j])
                    {
                        wans[i] = b[j];
                    }
                    else if (wans[i] == b[j])
                    {
                        wans[i] = a[j];
                    }
                }
                Console.WriteLine(wans[i]);
            }
        }
    }

Measured memory_bytes: 5592
/*-----lusar98-----*/
#include<bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define mod 1000000007
#define eps 1e-9
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
using namespace std;
int main()
{
    //fast();
    ll n;
    cin>>n;
    ll arr[n][3];
    for(ll i=0;i<n;i++)
    	cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    ll dp[n+2][3];
    dp[n-1][0]=arr[n-1][0];
    dp[n-1][1]=arr[n-1][1];
    dp[n-1][2]=arr[n-1][2];
    for(ll i=n-2;i>=0;i--)
    {
    	dp[i][0]=max(dp[i+1][1] , dp[i+1][2]) + arr[i][0];
    	dp[i][1]=max(dp[i+1][0] , dp[i+1][2]) + arr[i][1];
    	dp[i][2]=max(dp[i+1][1] , dp[i+1][0]) + arr[i][2];
    }
    cout<< max(dp[0][0], max( dp[0][1], dp[0][2] ) )<<endl;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define mset(s, _) memset(s, _, sizeof s)
#define ALL(a) (a).begin(), (a).end()
using namespace std;

int main(void) {
  ll W, H;
  cin >> W >> H;
  ll x, y;
  cin >> x >> y;

  double area = W * H / 2.0;
  printf("%.10f", area);
  if (W / 2.0 == x && H / 2.0 == y) {
    cout << " 1";
  } else {
    cout << " 0";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3768
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}

func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	m := iScan()
	x := 0
	y := -1
	for i := 0; i < m; i++ {
		d, c := iScan(), iScan()
		x += d * c
		y += c
	}
	fmt.Println(y + (x-1)/9)
}


Measured memory_bytes: 5008
import heapq
N = int(input())
V = list(map(int, input().split()))
heapq.heapify(V)
for i in range(N-1):
  v1 = heapq.heappop(V)
  v2 = heapq.heappop(V)
  heapq.heappush(V, (v1 + v2) / 2)
print(heapq.heappop(V))

Measured memory_bytes: 62292
using System;
using System.Text;

namespace ALDS1_9_C {
    class Problem {
        private int _H;
        private int[] _A;

        public Problem() {
            _A = new int[2000001];
        }

        public void Insert(int key) {
            int i = ++_H;
            _A[i] = key;
            while (i > 1 && _A[i / 2] < _A[i]) {
                Swap(i, i / 2);
                i /= 2;
            }
        }

        public int Extract() {
            int ret = _A[1];
            _A[1] = _A[_H--];
            MaxHeapify(1);
            return ret;
        }
        
        private void MaxHeapify(int i) {
            int l = 2 * i;
            int r = 2 * i + 1;
            int largest = (l <= _H && _A[l] > _A[i]) ? l : i;
            if (r <= _H && _A[r] > _A[largest])
                largest = r;

            if (largest != i) {
                Swap(i, largest);
                MaxHeapify(largest);
            }
        }

        private void Swap(int a, int b) {
            int temp = _A[a];
            _A[a] = _A[b];
            _A[b] = temp;
        }
    }

    class Program {
        static void Main(string[] args) {
            Problem p = new Problem();
            StringBuilder sb = new StringBuilder();
            bool inputEnd = false;
            while (!inputEnd) {
                string[] input = Console.ReadLine().Split(' ');
                switch (input[0]) {
                    case "insert":
                        p.Insert(int.Parse(input[1]));
                        break;
                    case "extract":
                        sb.AppendLine(p.Extract().ToString());
                        break;
                    case "end":
                        inputEnd = true;
                        break;
                }
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 38560
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using ll = long long;
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 long long INF = 1LL << 60;

ll gcd(ll a, ll b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

uintmax_t combination(unsigned int n, unsigned int r) {
  if ( r * 2 > n ) r = n - r;
  uintmax_t dividend = 1;
  uintmax_t divisor  = 1;
  for ( unsigned int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}

int modPow(long long a, long long n, long long p) {
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  long long t = modPow(a, n / 2, p);
  return (t * t) % p;
}

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

int main()
{
    ll n,m;
    cin >> n >> m;
    if(n == 1 && m == 1) cout << 1 << endl;
    else if(n == 1 && m != 1) cout << m-2 << endl;
    else if(n != 1 && m == 1) cout << n-2 << endl;
    else cout << (n-2)*(m-2) << endl;  
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAX = 510000;
const double pi=acos(-1);

int main(){
  int alf[26]={};
    string s;
    while(getline(cin,s)){
      rep(j,s.size()){
        if('a'<=s[j] && s[j]<='z') alf[s[j]-'a']++;
        else if('A'<=s[j] && s[j]<='Z') alf[s[j]-'A']++;
      }
    }
    rep(i,26){
      cout << char('a'+i) << " : " << alf[i] << endl;
    }
    return 0;  
}



Measured memory_bytes: 3164
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val A = Array.fill(N+1)(sc.nextInt())
    val B = Array.fill(N)(sc.nextInt())

    // 倒せる分だけ倒す
    var i = 0
    var score = 0L
    while (i < N) {
      val at = A(i) min B(i) // aiで倒した数
      B(i) -= at // 倒した数で残り数を更新
      val att = A(i+1) min B(i) // ai+1で倒した数
      A(i+1) -= att
      score += at + att
      i += 1
    }
    println(score)
  }

}


Measured memory_bytes: 68508
#include <bits/stdc++.h>
//一括include
using namespace std;
int main()
{
    string a;
    cin >> a;
    int ctr = 0;
    if (a[0] == '1')
        ++ctr;
    if (a[1] == '1')
        ++ctr;
    if (a[2] == '1')
        ++ctr;

    cout << ctr << endl;
}


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

signed main(void)
{
	int n;
	cin >> n;
	vector<int> out;
	if (n == 0) out.push_back(0);
	while (n != 0) 
	{
		if (n % 2 != 0)
		{
			out.push_back(1);
			n--;
		}
		else
			out.push_back(0);
		n /= -2; 
	}
	reverse(out.begin(), out.end());
	rep(i, out.size()) cout << out[i];
	cout << endl;
	return 0;
}


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

constexpr int MAX_N = 100000;
constexpr long long MAX_T = 1000000000000000000;

long long N, T, Q;

long long pos[MAX_N], target[MAX_N];
int dir[MAX_N];
std::vector<long long> stops;

void solve();

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

	std::cin >> N >> T >> Q;

	for(int i = 0; i < N; ++i){
		std::cin >> pos[i] >> dir[i];
	}

	for(int i = 0; i < N - 1; ++i){
		if(dir[i] == 1 && dir[i + 1] == 2 && (pos[i + 1] - pos[i]) <= (T * 2)){
			stops.push_back((pos[i + 1] + pos[i]) / 2);
		}
	}

	for(int i = 0; i < Q; ++i){
		int input;
		std::cin >> input;
		--input;

		long long res = MAX_T;
		if(dir[input] == 1){ //When a citizen heads east.
			auto itr = std::lower_bound(stops.begin(), stops.end(), pos[input]);
			if(itr != stops.end() && *itr <= pos[input] + T){
				res = *itr;
			}
		}
		else{ //When a citizen heade west.
			auto itr = std::lower_bound(stops.begin(), stops.end(), pos[input] - T);
			while(itr != stops.end() && *itr <= pos[input]){
				res = *itr;
				++itr;
			}
		}

		if(res == MAX_T){
			if(dir[input] == 1){
				std::cout << pos[input] + T << std::endl;
			}
			else{
				std::cout << pos[input] - T << std::endl;
			}
		}
		else{
			std::cout << res <<  std::endl;
		}
	}

	return 0;
}



Measured memory_bytes: 4384
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  int m;
  cin >> m;
  cout << 48-m << endl;
  return 0;
}

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

int main()
{
    int a, b, c, d;
    cin  >> a >> b;
    if (a % 3 == 0 || b % 3 == 0 || (a+b)%3 == 0)
        cout << "Possible" << endl;
    else
        cout << "Impossible" << endl;
    return 0;
}

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

using namespace std;

void __print(int x) {cerr << x;}; void __print(long x) {cerr << x;}; void __print(long long x) {cerr << x;}; void __print(unsigned x) {cerr << x;}; void __print(unsigned long x) {cerr << x;}; void __print(unsigned long long x) {cerr << x;}; void __print(float x) {cerr << x;}; void __print(double x) {cerr << x;}; void __print(long double x) {cerr << x;}; void __print(char x) {cerr << '\'' << x << '\'';}; void __print(const char *x) {cerr << '\"' << x << '\"';}; void __print(const string &x) {cerr << '\"' << x << '\"';}; void __print(bool x) {cerr << (x ? "true" : "false");}

#define int             long long
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)     __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define endl            '\n'
#define pb              push_back
#define all(x)          x.begin(),x.end()
#define ff              first
#define ss              second
#define in(arr)         for(int i=0;i<(int)(sizeof(arr)/sizeof(int));i++) cin >> arr[i];
#define out(arr)        for(int i=0;i<(int)(sizeof(arr)/sizeof(int));i++) cout << arr[i];

//Some Helpful Function
int powmod(int a, int b) {int res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % mod; a = a * a % mod;} return res;}
int string_to_int(string s) {int ans = 0; int p = 1; for (int i = s.size() - 1; i >= 0; i--) {ans += (s[i] - '0') * p; p *= 10;} return ans;}
int fast_pow(int a, int b) {if (b == 1) return a; if (b == 0) return 1; int x = fast_pow(a, b / 2); x *= x; if (b & 1) x *= a; return x;}

//DEBUGGING-LINES
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

void t_c_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("inp.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif*/
	int k;
	cin >> k;
	int c = 7;
	for (int i = 0; i < 1e6; i++) {
		// dbg(c, c % k);
		if (c % k == 0) {
			cout << i + 1 << endl;
			return;
		}
		c = (c * 10 + 7) % k;
	}
	cout << -1 << endl;
}

int32_t main()
{
	t_c_c();
	return 0;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

int main(){
	int N;
	cin >> N;
	vector<int> X(N);
	for(int i=0; i<N; i++){
		cin >> X[i];
	}

	ll ans = 1e9;
	for(int x=1; x<=100; x++){
		ll sum = 0;
		for(int i=0; i<N; i++) sum += (X[i]-x)*(X[i]-x);
		ans = min(ans, sum);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
//		double x = Math.log(n/100) / Math.log(1.01);
//		System.out.println(Math.round(x));
		double sum = 100;
		for (int i = 0; i < 10000; i++) {
			sum = Math.floor(sum * 1.01);
			if (sum >= n) {
				System.out.println(i+1);
				return;
			}
		}

	}

}


Measured memory_bytes: 35800
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        s: String,
        t: String,
    };

    let mut dp = vec![vec![0; t.len()+1]; s.len()+1];
    let mut prev = vec![vec![[0, 0]; t.len()+1]; s.len()+1];

    for (i, ss) in s.chars().enumerate() {
        for (j, tt) in t.chars().enumerate() {
            if ss == tt {
                dp[i+1][j+1] = dp[i][j] + 1;
                prev[i+1][j+1] = [i, j];
            } else {
                if dp[i+1][j+1] > dp[i][j+1] {
                    prev[i+1][j+1] = [i+1, j+1];
                } else {
                    dp[i+1][j+1] = dp[i][j+1];
                    prev[i+1][j+1] = [i, j+1];
                }

                if dp[i+1][j+1] < dp[i+1][j] {
                    dp[i+1][j+1] = dp[i+1][j];
                    prev[i+1][j+1] = [i+1, j];
                }
            }
        }
    }

    let mut ans = String::new();
    let s = s.chars().collect::<Vec<char>>();
    let t = t.chars().collect::<Vec<char>>();
    let mut i = s.len();
    let mut j = t.len();
    if s[s.len()-1] == t[t.len()-1] {
        ans.insert(0, s[s.len()-1]);
    }
    loop {
        let [si, ti] = prev[i][j];

        if si == 0 || ti == 0 {
            break;
        }

        if s[si-1] == t[ti-1] {
            ans.insert(0, s[si-1]);
        }
        i = si;
        j = ti;
    }

    println!("{}", ans);
}


Measured memory_bytes: 178028
A,B,C,D,E,F = map(int,input().split())

def sol(i):
	solmax = min((i*E)//100,F-i)
	s = []
	for i in range((solmax//C)+1):
		for j in range((solmax//D)+1):
			if C*i+D*j <= solmax:
				s.append(C*i+D*j)
	s = sorted(s)
	return s[-1]

water = []
for i in range(F//(A*100)+1):
	for j in range(F//(B*100)+1):
		if 0 < 100*A*i+100*B*j < F:
			water.append(100*A*i+100*B*j)

water = list(set(water))
suger = []
for i in range(len(water)):
	suger.append(sol(water[i]))

con = 0
ws = 0
s = 0
for k in range(len(water)):
	if con <= suger[k]/(water[k]+suger[k]):
		con = suger[k]/(water[k]+suger[k])
		ws = (water[k]+suger[k])
		s = suger[k]

print(ws,s)

Measured memory_bytes: 5780
#include<bits/stdc++.h>
using namespace std;
string t="qazwsxedcrfvtgb";
int tp(string s){
  int rl=0,cnt=0;
  if(t.find(s[0])!=string::npos) rl=1;
  for(int i=1;i<s.size();++i)
    if(t.find(s[i])==string::npos && rl==1) cnt++, rl=0;
    else if(t.find(s[i])!=string::npos && rl==0) cnt++, rl=1;
  return cnt;
}
int main(){
  string s;
  while(cin>>s, s!="#")
    cout<<tp(s)<<endl;
  return 0;
}

Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>F,R;void setF(int n,int mod){F=R=V<ll>(++n);F[0]=1;FOR(i,1,n)F[i]=F[i-1]*i%mod;R[n-1]=modInv(F[n-1],mod);FORR(i,n-1,1)R[i-1]=R[i]*i%mod;}
//ll comb(int a,int b,int m){return a<b||b<0?0:F[a]*R[b]%m*R[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7; //998244353;
const int N = 1e5;
typedef P<int, int> pii;
int n, m;
set<int> e[N];
bool z[N];
priority_queue<pii, V<pii>, greater<pii>> q;
void draw(int a, int b){
  e[a].erase(b); if(sz(e[a])) q.push(mp(sz(e[a]), a));
  e[b].erase(a); if(sz(e[b])) q.push(mp(sz(e[b]), b));
  printf("%d %d\n", a+1, b+1);
  z[a] ^= true;
}
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  if(m%2){
    cout << -1 << endl;
    return 0;
  }
  FOR(i, 0, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    e[a].insert(b);
    e[b].insert(a);
  }
  FOR(i, 0, n) q.push(mp(sz(e[i]), i));
  FOR(i, 0, m){
    pii t;
    while(true){
      t = q.top();
      q.pop();
      if(sz(e[t.se]) == t.fi) break;
    }
    int s = *e[t.se].begin();
    if(z[t.se]){
      draw(t.se, s);
    }else{
      draw(s, t.se);
    }
  }
}

Measured memory_bytes: 16500
#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#pragma comment(linker, "/STACK:1000000000")
#define forn(i, p, n) for(int i = p; i < n; ++i)

using namespace std;
typedef long long LL;
typedef double D;

int main()
{
	ios::sync_with_stdio(0);
	int A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;
	if (C * 2 > A + B)
		cout << X * A + Y * B;
	else
		if (X > Y)
			cout << Y * C * 2 + (X - Y) * min(C * 2, A);
		else
			cout << X * C * 2 + (Y - X) * min(C * 2, B);
}









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


int main() {
    int k,a,b;
    cin>>k>>a>>b;
    if(a%k==0 || b%k==0){
    	cout<<"OK";
    	return 0;
	}
	if(a/k !=b/k) cout<<"OK";
	else cout<<"NG";
    return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, w;
  cin >> n >> w;
  int mx = n * 1000;
  vector<long long> dp(mx + 1, w + 1);
  dp[0] = 0;
  while (n--) {
    int x, y;
    cin >> x >> y;
    for (int i = mx; i >= y; i--) {
      dp[i] = min(dp[i], dp[i - y] + x);
    }
  }
  for (int i = mx; ~i; i--) {
    if (dp[i] <= w) {
      cout << i << '\n';
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 3992
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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) {
    vector<int> as(3);
    for (int i = 0; i < 3; i++) {
        cin >> as[i];
    }
    sort(as.begin(), as.end());

    int ans = 0;
    ans += as[2] - as[1];
    ans += as[1] - as[0];

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main(){
  int N;
  cin>>N;
  string S[N],SS[N];
  int P[N],PP[N];
  for(int i=0;i<N;i++){
    cin>>S[i]>>P[i];
    SS[i]=S[i];
    PP[i]=P[i];
  }
  
  for(int i=0;i<N-1;i++){
    if(S[i]>S[i+1]){
      string s;
      s=S[i];
      S[i]=S[i+1];
      S[i+1]=s;
      int p;
      p=P[i];
      P[i]=P[i+1];
      P[i+1]=p;
      i=-1;
    }if(S[i]==S[i+1]&&P[i]<P[i+1]){
      int pp;
      pp=P[i];
      P[i]=P[i+1];
      P[i+1]=pp;
      i=-1;
    }
  }
  
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(S[i]==SS[j]&&P[i]==PP[j]) cout<<j+1<<endl;
    }
  }
  
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static void Main(string[] args)
        {
            int[] V = ReadInts();
            var C = new int[10];
            foreach (int v in V) { ++C[v]; }
            Console.WriteLine(C[1] == 1 && C[9] == 1 && C[7] == 1 && C[4] == 1 ? "YES" : "NO");
        }
    }
}


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

using namespace std;

using ll = long long;

int main() {
    int N; cin>>N;
    string S,T; cin>>S>>T;

    for (int i=0;i<S.length();i++) {
        cout << S[i] << T[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <sstream>
#include <iomanip>
#include <time.h>
#include <fstream>

using namespace std;

int main(){
	string s1,s2,s3;
	cin>>s1>>s2>>s3;
	string x;
	x="A";
	x+=string(1,s2[0]);
	x+=string(1,'C');
	cout<<x<<endl;
	return 0;
}

Measured memory_bytes: 256
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;
static import std.ascii;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long N, M;
    scan(N, M);
    auto cnt = new long[](N + 1);
    foreach (_; 0 .. M)
    {
        long a, b;
        scan(a, b);
        cnt[a]++;
        cnt[b]++;
    }
    writeln(cnt.all!"a%2==0"() ? "YES" : "NO");
}


Measured memory_bytes: 3836
program ABC154A
    implicit none
    character(10)::S,T,U
    integer(8)::A,B
    read(5,*)S,T,A,B,U
    if(U(1:len_trim(U))==S(1:len_trim(S)))then
        print'(i0,1x,i0)',A-1,B
    else
        print'(i0,1x,i0)',A,B-1
    end if
end program ABC154A

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

int insertionSort(int a[1000010],int n, int g){
  int count = 0;
  for(int i = g; i < n; i++){
    int v = a[i];
    int j = i - g;  
    while(j >= 0 && a[j] > v){
      a[j + g] = a[j];
      j = j - g;
      count++;
    }
    a[j + g] = v;  
  }
  return count;
}

int main(void){
  int a[1000010],n,m,i,g[1000010],count = 0;
  int arr[] = {0,3,12,39,120,363,1092,3279,9840,29523,88572,265719,797160};
  scanf("%d",&n);
  for(i = 0; i < n; i++)scanf("%d",&a[i]);
  for(i = 1; i < 13; i++){
    if(arr[i - 1] < n && n <= arr[i])break;
  }
  m = i;
  printf("%d\n",m);
  for(i = 0; i < n; i++){
    g[i] = arr[i] + 1;
  }
  for(i = m - 1; i >= 0; i--){
    if(i != m - 1)printf(" ");
    printf("%d",g[i]);
  }
  for(i = m - 1; i >= 0; i--){
    count += insertionSort(a,n,g[i]);
  }
  printf("\n%d",count);

  for(i = 0; i < n; i++)printf("\n%d",a[i]);
  printf("\n");
  return 0;
}


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

int main(){
    string s;
    cin >> s;
    string ans = "";
    for(char c: s){
        if(c=='A' and (ans.empty() or ans.back()=='Z')){
            ans += c;
        }
        if(c=='Z' and !ans.empty() and ans.back()=='A'){
            ans += c;
        }
    }
    if(!ans.empty() and ans.back()=='A'){
        ans.pop_back();
    }
    if(ans == ""){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    return 0;
}



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

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N-1);
    for(int i=0; i<N; i++)
    {
        cin >> A[i];
        A[i] -= 1;
    }
    for(int i=0; i<N; i++)
    {
        cin >> B[i];
    }
    for(int i=0; i<N-1; i++)
    {
        cin >> C[i];
    }

    int s = B[A[N-1]];
    for(int i=0; i<N-1; i++)
    {
        s += B[A[i]];
        if(A[i+1] == A[i]+1)
        {
            s += C[A[i]];
        }
    }

    cout << s << endl;

    return 0;
}

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

using namespace std;
int main(){
  vector<int> a;
  int x;
  cin >> x;
  a.push_back(x);
  cin >> x;
  a.push_back(x);
  cin >> x;
  a.push_back(x);
  sort(a.begin(), a.end());
  cout << a[0] << " " << a[1] << " " << a[2] << endl;
  return 0;
}


Measured memory_bytes: 3148
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;
string s;
int main(int argc, char** argv) {
	cin >> s;
	int id = 0;
	int n = s.length();
	if(n %2 == 0) {
		for(int i = 0; i< n; i+=2) {
			if(s.substr(i,2) == "hi") id++;
		}
	}
	if(n == 1) cout << "No";
	else if(id == n/2) cout << "Yes";
	else cout << "No";
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll 				long long
#define ld 				long double
#define fastio 			ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) 		cerr<<#x<<" "<<x<<endl
#define cina(a,n) 		for(ll i = 0;i<n;i++)	cin>>a[i];
#define couta(a,n) 		for(ll i = 0;i<n;i++) cout<<a[i]<<" ";
#define mod 			1000000007
#define siz 			105
#define f 				first
#define s 				second
#define pb 				push_back
#define endl 			"\n"
#define ci 				cin.ignore()
using namespace std;
int main()
{
	ll n,m,i,j;
	cin>>n>>m;
	
	char grid[n][m];
	
	for(i = 0;i<n;i++)
		for(j = 0;j<m;j++)
			cin>>grid[i][j];
	
	ll dp[n][m];
	memset(dp,0,sizeof(dp));
	
	dp[0][0] = 1;
	for(i = 1;i<n;i++)
	{
		if(grid[i][0] == '#')	break;
		dp[i][0] = 1;
	}
	
	for(i = 1;i<m;i++)
	{
		if(grid[0][i] == '#')	break;
		dp[0][i] = 1;
	}
	
	for(i = 1;i<n;i++)
	{
		for(j = 1;j<m;j++)
		{
			if(grid[i][j] == '#')
			continue;
			
			dp[i][j] = dp[i-1][j] + dp[i][j-1];
			dp[i][j] %= mod;
		}
	}
	
	
	cout<<dp[n-1][m-1]<<endl;
	
	
	
	
	
}

Measured memory_bytes: 9088