akhauriyash/Code-Regression huggingface dataset:
while True:
    n, m = map(int, input().split())
    if n == 0:break
    h = [input().split() for _ in range(n)]
    t = [input() for _ in range(m)]
    c = 0
    for kuji in t:
        for atari in h:
            for i in range(len(kuji)):
                if atari[0][i] != "*" and kuji[i] != atari[0][i]:
                    break
            else:
                c += int(atari[1])
                break
    print(c)


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

int main()
{
long long a,b,c,d,x=0;
  cin>>a>>b>>c>>d;
x=0;
if(d>a)
{x=x+a;
 d=d-a;
}
  else {
  x= x+d;
    d=0;
    cout<<x;
    return 0;
  }
if(d>=b)
{
 d=d-b;
}
  else {
    d=0;
    cout<<x;
    return 0;
  }
  if(d>=c)
  {
    x=x-c;
  }
  else { x=x-d;
  
  cout<<x;
       return 0;}
  
  cout<<x;
 
    return 0;
}


Measured memory_bytes: 3632
# coding: utf-8
# Your code here!
s=input()

can1=""
can2=""

match1=0
match2=0

for i in range(len(s)):
    if i%2:
        can1=can1+"0"
        can2=can2+"1"
    else:
        can1=can1+"1"
        can2=can2+"0"
    if can1[i]==s[i]:
        match1=match1+1
    else:
        match2=match2+1

if match1>match2:
    print(match2)
else:
    print(match1)
    

Measured memory_bytes: 3316
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

plus = []
minus = []
zero = []
for i in range(n):
    if a[i] < 0:
        minus.append(abs(a[i]))
    elif a[i] > 0:
        plus.append(a[i])
    else:
        zero.append(0)


len_p = len(plus)
len_m = len(minus)
len_z = len(zero)

is_z = False
is_p = False
if len_z != 0:
    is_z = True

cnt = 2 * (len_m // 2) + len_p
if cnt >= k:
    is_p = True
if len_p == 0 and k % 2 == 1:
    is_p = False

if is_p:
    minus = sorted(minus, reverse=True)
    plus = sorted(plus, reverse=True)
    ans = 1
    if k % 2 == 1:
        k -= 1
        ans = plus[0]
        del plus[0]
    tmp = []
    for i in range(len(minus) // 2):
        tmp.append(minus[2 * i] * minus[2 * i + 1])
    for i in range(len(plus) // 2):
        tmp.append(plus[2 * i] * plus[2 * i + 1])
    tmp = sorted(tmp, reverse=True)
    for i in range(k // 2):
        ans *= tmp[i]
        ans %= MOD
    print(ans)
    exit()

elif is_z:
    print(0)
    exit()

else:
    for i in plus:
        minus.append(i)
    minus = sorted(minus)
    ans = -1
    for i in range(k):
        ans *= minus[i]
        ans %= MOD
    print(ans)
    exit()


Measured memory_bytes: 113240
// An efficient C++ program to compute
// sum of bitwise OR of all pairs
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
ll power(ll x,ll y)
{
    ll res=1;
    while(y>0)
    {
        if(y%2==1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y=y/2;
    }
    return res;
}
// Returns sum of bitwise OR
// of all pairs
long long int sumXOR(ll arr[], int n)
{
	long long int sum = 0;
	for (long long i = 0; i < 61; i++)
	{
		// Count of zeros and ones
		long long zc = 0, oc = 0;

		// Individual sum at each bit position
		long long int idsum = 0;
		for (ll j = 0; j < n; j++)
		{
			if (arr[j] % 2 == 0)
				zc++;
			else
				oc++;
			arr[j] /= 2;
		}

		// calculating individual bit sum
		idsum = (oc * zc %mod) * power(2,i)%mod;

		// final sum
		sum = (sum+idsum)%mod;
	}
	return sum;
}

int main()
{
	long long int sum = 0;
	long long n,i;
	cin>>n;
	ll arr[n];
	for(i=0;i<n;i++)
        cin>>arr[i];
	sum = sumXOR(arr, n);
	cout << sum;
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>

using namespace std;
int main()
{
  unsigned long long div = 1000000007;
  string s;
  cin >> s;
  size_t n = s.size();

  vector<vector<unsigned long long>> dp(n+1, vector<unsigned long long>(4, 0));
  dp[0][0] = 1;


  for(auto i = 0; i < n; i++) {
    dp[i+1][0] = dp[i][0] * (s[i] == '?'? 3 : 1); // epsilon
    dp[i+1][1] = dp[i][1] * (s[i] == '?'? 3 : 1) + dp[i][0] * ((s[i] == '?' | s[i] == 'A') ? 1 : 0);
    dp[i+1][2] = dp[i][2] * (s[i] == '?'? 3 : 1) + dp[i][1] * ((s[i] == '?' | s[i] == 'B') ? 1 : 0);
    dp[i+1][3] = dp[i][3] * (s[i] == '?'? 3 : 1) + dp[i][2] * ((s[i] == '?' | s[i] == 'C') ? 1 : 0);
    for (auto k = 0; k < 4; k++) dp[i+1][k] %= div;
  }
  cout << dp[n][3] << endl;

  return 0;
}


Measured memory_bytes: 7424
char W[9],V[9];Z[7*24*60],S,N,T,P,M;main(){
	int i,j,k,l,r,d;
	for(;scanf("%d%d%d%s%s%d%d",&S,&N,&T,W,V,&P,&M),S;printf("%.9f\n",1-pow(1-1.0/P,N*r))){
		memset(Z,0,sizeof(Z));
		l=*W=='A'?7:1;
		if(*V=='A')for(i=0;i<l;i++)for(j=0;j<24*60;j++)Z[i*24*60+j]=1;
		if(*V=='D')for(i=0;i<l;i++)for(j=0;j<12*60;j++)Z[(i*24+6)*60+j]=1;
		if(*V=='N')for(i=0;i<l;i++)for(j=0;j<6*60;j++)Z[i*24*60+j]=Z[(i*24+18)*60+j]=1;
		for(r=j=0;j<24*60;r=r>l?r:l,j++)for(k=j,l=i=0;i<M;i++){
			l+=Z[(k+S)%(7*24*60)]&Z[k];
			k=(k+T)%(7*24*60);
		}
}exit(0);}

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

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#define _GLIBCXX_DEBUG
#else
#define debug(_) 0
#endif // LOCAL

int main(){
    int N, K;
    vector<int> hs;

    cin >> N >> K;
    hs.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> hs[i];
    }

    sort(hs.begin(), hs.end());
    K--;
    int ans = 1001001001;
    for (int i = K; i < N; i++) {
        ans = min(ans, hs[i] - hs[i-K]);
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 3792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};
constexpr ll mod = 1000000007;

int main(){
    ll n;
    cin >> n;
    vector<ll> ans(n+1, 0);
    rep(x, 1, 110){
        rep(y, 1, 110){
            rep(z, 1, 110){
                ll f = x*x + y*y + z*z + x*y + y*z + z*x;
                if(f <= n) ans[f]++;
            }
        }
    }
    rep(i, 1, n+1) cout << ans[i] << endl;
    return 0;
}

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

#define INF_LL (int64_t)1e18
#define INF (int32_t)1e9

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

int main() {
  int N;
  cin >> N;
  vector<int> a(N);

  for (auto &&e : a) {
    cin >> e;
  }
  sort(a.begin(), a.end());

  cout << a.back() - a.front() << endl;
}


Measured memory_bytes: 256
use std::io;


/// https://beta.atcoder.jp/contests/tenka1-2017-beginner/tasks/tenka1_2017_b
fn main() {
    let n = read_one::<usize>();
    let mut ab = Vec::new();
    for _ in 0..n {
        let i = read::<usize>();
        ab.push((i[0], i[1]));
    }
    ab.sort();
    ab.reverse();
    println!("{}", ab[0].0 + ab[0].1);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 6396
#include <bits/stdc++.h>
#define inf INFINITY
#define file freopen( "input.txt" , "r" , stdin) ; freopen( "output.txt" , "w" , stdout) ;
#define Gamed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define _3102_ main()
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int N = 1e5 + 100;
const ll MX = 1e18;
const ll mod = 1e9 + 7;
const double eps = 1e-9 ;
int n , m , dp[N] ;
vector < int > adj[N] ; 

int solve( int node ){
    //cout << node << endl ; 
    if ( dp[node] != -1 ) return dp[node] ;
    int maxi = 0 ; 
    for ( auto j : adj[node]){
        maxi = max ( maxi , solve(j) + 1 ) ;
    }
    return dp[node] = maxi ; 
} 

int _3102_{
	Gamed
    cin >> n >> m ; 
    for ( int i = 0 ; i < m ; i ++){
        int u , v ; 
        cin >> u >> v ;
        adj[v].push_back(u) ; 
    }
    //for ( int i = 1 ; i <= n ; i ++){
    //    cout << i << ": " ; 
    //    for ( auto j : adj[i] ){
    //        cout << j << " " ;
    //    }
    //    cout << endl ; 
    //}
    memset ( dp , -1 , sizeof dp ) ;
 
    for ( int i = 1 ; i <= n ; i ++){
        if ( dp[i] == -1 ){
            //cout << "--" << i << "--" << endl  ;
            solve (i) ;
            //cout << "------\n";
            //for ( int j = 1 ; j <= n ; j ++ ) cout << dp[j] << " " ;
            //cout << "\n------\n" ;  
        }  
    }
    int ans= 0 ; 
    for ( int i = 1 ; i <= n ; i ++ ){
        ans = max ( ans , dp[i]) ;
    }
    cout << ans << endl ; 
    return 0;
}



Measured memory_bytes: 14008
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  for(int i=1; i<=1000; i++) {
    if(i*a%b==c) {
      cout << "YES" << endl;
      break;
    }
    if(i==1000) {
      cout << "NO" << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define endl '\n';

typedef long long ll;

using namespace std;

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

    const string YES = "YES";
    const string NO  = "NO";
    int r, g, b;

    cin >> r >> g >> b;

    r *= 10;
    r += g;
    r *= 10;
    r += b;

    if (r % 4 == 0) {
        cout << YES;
    } else {
        cout << NO;
    }
    cout << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <stdlib.h>
#include <stdio.h>

using namespace std;

int my_abs_A(int num) {
    if (num > 0)
        return num;
    else
        return -num;
}

int my_abs_B(long long num,long long numb) {
    if (num - numb >= 0)
        return num - numb;
    else
        return -1 * (num - numb);
}

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

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

int main() {
    long long A;
    cin >> A;
    long long B = A;
    long long waru = 2;
    long long count = 0;
    while (true) {

        if (B / waru != 0) {
            count++;
            waru = waru * 2;
        }
        else {
            break;
        }
    }
    long long tasu = 1;
    long long ans = 0;
    for (long long i = 0; i <= count; i++) {
        ans = ans + tasu;
        tasu = tasu * 2;
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p) pom(a,p-2,p)

////////////////////////////////////////////////////////////////////////////////////////
int main(){
    ll n; cin >> n;
    ll a[n];
    vector<vector<ll>> x(n), y(n);
    rep(i,0,n){
        cin >> a[i];
        rep(j,0,a[i]){
            ll t1, t2; cin >> t1 >> t2;
            t1--;
            x[i].pb(t1); y[i].pb(t2);
        }
    }
    ll res = 0;
    rep(i,0,(1<<n)){
        vector<int> v;
        rep(j,0,n){
            if((i >> j) & 1){
                v.pb(j);
                //cout << j << ednl;
            }
        }
        int uso[n]; rep(j,0,n) uso[j] = 0; //未定義
        rep(j,0,v.size()) uso[v[j]] = 1;
        bool flag = true;
        rep(j,0,v.size()){
            rep(k,0,a[v[j]]){
                if(uso[x[v[j]][k]] == y[v[j]][k]){
                    continue;
                }else{
                    flag = false;
                    break;
                }
            }
        }
        if(flag){
            res = max(res, v.size());
        }
    }
    cout << res << ednl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main() {
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size() - 1] == b[0] && b[b.size() - 1]==c[0]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	}

Measured memory_bytes: 256
//状态:
//题号:
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#include <cassert>
#include <complex>
#include <functional>
#include <list>
#include <cmath>
using namespace std;
typedef long long ll;
int n;
int a[200005];
ll sum[200005],x[200005];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int i=0;i<n;i++)sum[i+1]=sum[i]+a[i],x[i+1]=x[i]^a[i];
	ll ans=0;
	for(int i=0;i<n;i++){
		int lb=i+1,rb=n+1;
		while(rb-lb>1){
			int m=(rb+lb)>>1;
			if((sum[m]-sum[i])==(x[m]^x[i]))lb=m;
			else rb=m;
		}
	//	cout<<lb<<" "<<rb<<endl;
		ans+=lb-i;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main(){
  int a,b,c,d,e;
  cin>>a>>b>>c>>d>>e;
  int k;
  cin>>k;
  int t=0;
  vector<int>vec={a,b,c,d,e};
  for(int i=1;i<5;i++){
    for(int j=0;j<i;j++){
      int l=vec[i]-vec[j];
      if(l>k){
        t+=1;
      }
    }
  }
  if(t==0){
    cout<<"Yay!"<<endl;
  }

  else if(t>0){
    cout<<":("<<endl;
  }
}

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

int main() {
  string s;
  cin >> s;
  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]){
    cout << "Bad" << endl;
  }
  else{
    cout << "Good" << endl;
  }
}

Measured memory_bytes: 3636
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = list(map(int, input().split()))

        sum_all = sum(A)
        min_diff = sum_all
        left = 0
        right = sum_all
        for i in range(N):
            left += A[i]
            right -= A[i]
            tmp_diff = abs(right - left)
            min_diff = min(min_diff, tmp_diff)

        print(min_diff)


# Run main
if __name__ == '__main__':
    AtCoder().main()


Measured memory_bytes: 81104
#include <bits/stdc++.h>
#define vsort(v) sort(v.begin(), v.end())
#define MOD 1000000007
typedef long long ll;
using namespace std;
int main()
{
	ll N, K, i, j, x = 0, c, r = 0; 
  	cin >> N >> K;
  	vector<ll> A(N);
  	for (i = 0; i < N; i++){
    	cin >> A[i];
    }
  	for (i = 40; i >= 0; i--) {
    	c = 0;
      	for (j = 0; j < N; j++) {
        	c += (A[j] >> i) & 1;
        }
        if (2 * c < N && (x | (1L << i)) <= K) {
           	x |= 1L << i;
        }
    }
  	for (i = 0; i < N; i++) {
    	r += x ^ A[i];
    }
  	cout << r << endl;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void output_vector(const vector<T> &v, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());

    for (int i = start; i < end; i++)
        cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}


int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    int N, K;
    cin >> N >> K;
    vector<int> A(N);

    for (auto &a : A)
        cin >> a;

    auto &&simulate = [&] {
        vector<int> change(N + 1, 0);

        for (int i = 0; i < N; i++) {
            int start = max(i - A[i], 0);
            int end = min(i + A[i] + 1, N);
            change[start]++;
            change[end]--;
        }

        vector<int> cover(N, 0);
        int sum = 0;

        for (int i = 0; i < N; i++) {
            sum += change[i];
            cover[i] = sum;
        }

        return cover;
    };

    for (int iter = 0; iter < K && *min_element(A.begin(), A.end()) < N; iter++)
        A = simulate();

    output_vector(A);
}


Measured memory_bytes: 5576
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
// typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
// S以下の非負整数
void keta1() {
  // i桁目
  // S未満確定か
  int dp[20][2] = {};
  string S;
  cin >> S;
  dp[0][0] = 0;
  rep(i, 0, S.size()) rep(j, 0, 2) {
    if (i == 0 and j == 1)
      continue;
    int lim = j ? 9 : S[i] - '0';
    dump(lim);
    rep(d, 0, lim + 1) {
      //すでに未満確定||未満確定
      dump(i, j, d);
      dump(dp[i + 1][j || d != lim], d + dp[i][j]);
      chmax(dp[i + 1][j || d != lim], d + dp[i][j]);
    }
  }
  dump(dp);
  int ans = max(dp[S.size()][0], dp[S.size()][1]);
  cout << ans << endl;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  keta1();

  return 0;
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N,M;
    Scd2(N,M);
    int S = 0;
    vi a(N);
    Rep(i,N) Scd(a[i]), S += a[i];

    int s = (S+4*M-1)/4/M;

    int cnt = 0;
    Rep(i,N) if( a[i] >= s ) cnt++;

    YesNo(cnt>=M);

    return 0;
}



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

int main(){
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> h[i];
		if (i > 0){
			if (h[i] > h[i - 1]){
				h[i]--;
			}
			else if (h[i] < h[i - 1]){
				cout << "No";
				return 0;
			}
		}
	}
	cout << "Yes";
	return 0;
}

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

void solve(long long N, std::vector<long long> A){
    multiset<ll> s;
    for(int i=0;i<N;i++){
        auto itr = s.lower_bound(A[i]);
        if(itr == s.begin()){
            // cerr <<"*itr=" << *itr<< endl;
            s.insert(A[i]);
        }else{
            --itr;
            s.erase(itr);
            s.insert(A[i]);
        }
    }
    cout << s.size() << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 5760
#include <iostream>
using namespace std;
int main()
{
    string s,t,u;
    int a,b;
    cin>>s>>t;
    cin>>a>>b;
    cin>>u;
    if(u==s)
        a-=1;
    else b-=1;
    cout<<a<<' '<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
ans = 0
n = []
for i in range(N):
  n.append(int(input()))
n.sort()
i=0
cnt = 1
while(i<N-1):
  if n[i] == n[i+1]:
    cnt+=1
  else:
    if cnt%2==1:
      ans+=1
    cnt = 1
    
  i+=1
if cnt%2==1:
  ans+=1

print(ans)

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

int main()
{
	int leg[2] = {2,4};
	int x,y;
	cin >> x >> y;

	vector<int> p(x,leg[0]);
	bool flg = false;
	for (int i = 0; i <= x; i++)
	{
		int sum = 0;
		for (int j = 0; j < x; j++)
		{
			sum += p[j];
		}
		if (sum == y)
		{
			flg = true;
			break;
		}
		if(i!=x)
		{ 
			p[i] = leg[1];
		}
	}

	if (flg)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
}




Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
  int X, Y;
  while(cin >> X >> Y){
    if(X == 0 && Y == 0) break;
    if(X < Y) swap(X, Y);
    int cnt = 0;
    while(Y != 0){
      cnt++;
      X %= Y;
      swap(X, Y);
    }

    cout << X << ' ' << cnt << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld long double
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    vector<pair<int,int>> v[n][n];
    for(int i=0;i<n;i++){
        vector<pair<int,int>> v1;
        for(int j=0;j<n-1;j++){
            int x; cin>>x; x--;
            v1.push_back({min(i,x),max(i,x)});
        }
        for(int k=0;k<(int)v1.size()-1;k++){
            v[v1[k].first][v1[k].second].push_back(v1[k+1]);
        }
    }
    int indeg[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            indeg[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(auto x : v[i][j]){
                indeg[x.first][x.second]++;
            }
        }
    }
    set<pair<int,pair<int,int>>> s; 
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            s.insert({indeg[i][j],{i,j}});
        }
    }
    int ans=0;
    while(s.size() > 0){
        vector<pair<int,int>> v1;
        while(s.size() > 0){
            if(s.begin()->first==0) v1.push_back(s.begin()->second);
            else break;
            s.erase(s.begin());
        }
        if(v1.size()==0){
            cout<<"-1"; return 0;
        }
        ans++;
        for(auto x : v1){
            for(auto  y : v[x.first][x.second]){
                s.erase({indeg[y.first][y.second],y});
                indeg[y.first][y.second]--;
                s.insert({indeg[y.first][y.second],y});
            }
        }
    }
    cout<<ans;
}

Measured memory_bytes: 76288
def hypot2(x, y):
    return x**2 + y**2


while True:
    h, w = map(int, input().split())
    if h == 0:
        exit()
    lb = hypot2(h, w)
    ans = []
    for y in range(1, 151):
        for x in range(y + 1, 151):
            if lb < hypot2(x, y) or (lb == hypot2(x, y) and h < y):
                ans.append([hypot2(x, y), y, x])
    d, h, w = sorted(ans)[0]
    print(h, w)



Measured memory_bytes: 7104
from heapq import *
n,m=map(int,input().split())
ab=[]
ans=[[] for i in range(m)]
aa=0
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b*=-1
    ab.append((a,b))
ab.sort()
t=[]
heapify(t)
for a,b in ab:
    if a<m:
        ans[a].append(b)
for i in range(m):
    for j in ans[i]:
        heappush(t,j)
    if len(t)>0:
        tt=heappop(t)*(-1)
        aa+=tt
print(aa)

Measured memory_bytes: 32148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////

int main(){
    ll n;cin>>n;
    ll a[n];
    ll sum=0;
    rep(i,0,n-1){
        cin>>a[i];
        sum+=a[i];
        sum-=(i+1);
    }
    cout<<sum<<endl;
    
    
    
    return 0;
}



Measured memory_bytes: 3880
#include<bits/stdc++.h>
using namespace std;
#define nn 65536*4
#define ll long long
#define mod 998244353

ll k,a,b;
int main()
{
	cin>>k>>a>>b;
	if(b-a>2)
	{
		if(k+1>=a)
		{
			k-=a-1;
			if(k%2==0)
			{
				cout<<(b-a)*(k/2)+a;
			}
			else
			{
				cout<<(b-a)*(k/2)+a+1;
			}
		}
		else cout<<1+k;
		exit(0);
	}
	cout<<1+k;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

count = 0
for i, x in enumerate(A):
	if x < 0:
		count += 1
		A[i] *= -1
# print(count)
if count % 2 == 0:
	print(sum(A))
else:
	# print(A)
	print(sum(A)-2*min(A))


Measured memory_bytes: 15144
import numpy as np

N,M,C=map(int, input().split())

b=list(map(int, input().split()))
b=np.array(b)
count=0
for _ in range(N):
    a=list(map(int, input().split()))
    a=np.array(a)
    e=a*b
    d=np.sum(e,axis=0)+C
    if d>0:
        count+=1
print(count)

Measured memory_bytes: 12472
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int N,mx=0,r=0;
	cin>>N;
	for(int i=0;i<N;i++)
	{
		int a;
		cin>>a;
		if(mx<a)
		{
			r+=mx;
			mx=a;
		}
		else
		{
			r+=a;
		}
	}
	cout<<(r+mx/2)<<endl;
}


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

int main(){
  int n,c,ans=0;
  string s,x;
  map<string,int>a;
  cin >> n >> s;
  for(int i=0;i<1000;i++){
    x=to_string(i);
    while(x.size()!=3) x='0'+x;
    c=0;
    for(int j=0;j<n;j++){
      if(s.at(j)==x.at(c)) c++;
      if(c==3) break;
    }
    if(c==3) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3716
import sys
n = int(input())
d = list(map(int, input().split()))
m = {}
ans = 1

if d[0] != 0:
    print(0)
    sys.exit()

if d.count(0) > 1:
    print(0)
    sys.exit()

for i in range(n):
    num = d[i]
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

# if len(m) < n:
#     print(0)
#     sys.exit()

#print(m)
#print(max(m))
maxV = max(m.keys())

#for i in range(1, max(m)+1):
#for i in range(0, max(m)):
for i in range(0, maxV):
    if i not in m or i + 1 not in m:
        print(0)
        sys.exit()
    prevCnt = m[i]
    curCnt = m[i+1]
    # prevCnt = m[i] % 998244353
    #curCnt = m[i+1] % 998244353
    ans *= prevCnt ** curCnt
    #ans *= (prevCnt ** curCnt) % 998244353

print(ans % 998244353)







Measured memory_bytes: 62380
# coding=utf-8

###
### for atcorder program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

def get_input():
    N = []
    while True:
        try:
            #N.append(input())
            #N.append(int(input()))
            N.append(float(input()))
        except EOFError:
            break
    return N

N = get_input()

for i in N:
    if i <= 48.00 :
        print("light fly")
    elif 48.00 < i <= 51.00:
        print("fly")
    elif 51.00 < i <= 54.00:
        print("bantam")
    elif 54.00 < i <= 57.00:
        print("feather")
    elif 57.00 < i <= 60.00:
        print("light")
    elif 60.00 < i <= 64.00:
        print("light welter")
    elif 64.00 < i <= 69.00:
        print("welter")
    elif 69.00 < i <= 75.00:
        print("light middle")
    elif 75.00 < i <= 81.00:
        print("middle")
    elif 81.00 < i <= 91.00:
        print("light heavy")
    elif 91.00 < i :
        print("heavy")




Measured memory_bytes: 5652
#include <stdio.h>
int main(void){
	int n,m,l;
	scanf("%d %d %d\n",&n,&m,&l);
	int a[n][m];
	int b[m][l];
	long long int c[n][l];
	int add_n,add_m,add_l;
	for(add_n=0;add_n<n;add_n++){
		for(add_m=0;add_m<m;add_m++){
			a[add_n][add_m] = 0;
		}
	}
	for(add_m=0;add_m<m;add_m++){
		for(add_l=0;add_l<l;add_l++){
			b[add_m][add_l] = 0;
		}
	}
	for(add_n=0;add_n<n;add_n++){
		for(add_l=0;add_l<l;add_l++){
			c[add_n][add_l] = 0;
		}
	}
	int p,q;
	for(p=0;p<n;p++){
		for(q=0;q<m;q++){
			if(q==m-1){
				scanf("%d\n",&a[p][q]);
			}else{
				scanf("%d ",&a[p][q]);
			}
		}
	}
	for(p=0;p<m;p++){
		for(q=0;q<l;q++){
			if(q==l-1){
				scanf("%d\n",&b[p][q]);
			}else{
				scanf("%d ",&b[p][q]);
			}
		}
	}
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<l;j++){
			int count;
			for(count=0;count<m;count++){
				c[i][j] = c[i][j] + (a[i][count]*b[count][j]);
			}
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<l;j++){
			if(j==l-1){
				printf("%lld\n",c[i][j]);
			}else{
				printf("%lld ",c[i][j]);
			}
		}
	}
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<char> s(n);
  rep(i,n) cin >> s[i];
  int count = 0;
  for(int i = 2; i < n; ++i){
    if(s[i-2]=='A' && s[i-1]=='B' && s[i]=='C'){
      count++;
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
# encoding:utf-8


def main():
	n = int(input())
	nums = [int(x) for x in list(str(n))]
	x = [10 ** i for i in range(7)]
	for i1 in x:
		if n == i1:
			print(10)
			#print("a1")
			break
		else:
			for i2 in range(2, 10):
				if n == x * i2:
					print(i2)
					#print("a2")
					break

	else:
		print(sum(nums))
		#print("a3")

		

if __name__ == '__main__':
	main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using lint = long;
using ll = long long;
#define rep(i,n) for(lint (i) = 0;(i) < (lint)(n);(i)++)
#define repInRange(i,start,end) for(lint (i) = (start);(i) < (end);++(i))
using lpair = pair<lint,lint>;
using vl = vector<lint>;
using vll = vector<long long>;
using Llist = list<lint>;
using vs = vector<string>;
#define all(v) (v).begin(),(v).end()
#define out1(x) cout << (x) << '\n';

ll pow(ll k,ll l) {
	ll ret = 1;
	rep(i,l) {
		ret *= k;
	}
	return ret;
}

template <typename T>
T sum(vector<T> vec) {
	ll ret = 0;
	rep(i,vec.size()) {
		ret += vec.at(i);
	}
	return ret;
}

void Main() {
	string o,e,ope;
	cin >> o >> e;
	rep(i,e.size()) {
		cout << o[i] << e[i];
    }
  	if (o.size() - e.size())
		cout << o[o.size()-1] << '\n';
}

signed main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	Main();
	return 0;
}


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

#define equals(a, b) (fabs((a)-(b)) < EPS)
const double EPS = (1e-10);

class Point {
public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) {
        return Point(x+p.x, y+p.y);
    }
    Point operator - (Point p) {
        return Point(x-p.x, y-p.y);
    }
    Point operator * (double a) {
        return Point(x*a, y*a);
    }
    Point operator / (double a) {
        return Point(x/a, y/a);
    }

    double abs() {
        return sqrt(norm());
    }
    double norm() {
        return x*x + y*y;
    }

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == (const Point &p) const {
        return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
    }
};

typedef Point Vector;
// 内積
double dot(Vector a, Vector b) {
    return a.x*b.x + a.y*b.y;
}
// 外積
double cross(Vector a, Vector b) {
    return a.x*b.y - a.y*b.x;
}

typedef vector<Point> Polygon;  // 多角形

int contains(Polygon g, Point p) {
    int n = g.size();
    bool x = false;
    for (int i = 0; i < n; i++) {
        Point a = g[i] - p, b = g[(i+1)%n] - p;
        if (abs(cross(a, b)) < EPS && dot(a, b) < EPS) return 1;
        if (a.y > b.y) swap(a, b);
        if (a.y < EPS && EPS < b.y && cross(a, b) > EPS) x = !x;
    }
    return (x ? 2 : 0);
}

int main(void) {
    int n; cin >> n;
    int x, y;

    Polygon g;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        g.push_back(Point(x, y));
    }

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        cout << contains(g, Point(x, y)) << endl;
    }

    return 0;
}

Measured memory_bytes: 1204
#include <cstdio>
#include <cstdlib>
int main() {
    char a;
    int s = 0;
    for(int i = 1; i < 4; i++) {
        a = getchar();
        if(a == '1') s++;
    }
    printf("%d\n", s);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int a[200010];
int main() {
	int n,k;
	cin>>n>>k;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n-k; i++) {
		if(a[i]<a[i+k]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Measured memory_bytes: 4412
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include<cmath>
#include<vector>
#include<map>
#include<algorithm>
#include<numeric>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0])
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

using namespace std;
typedef long long ll;



int main(void) {
	int n,alice=0,bob=0;
	int a;
	cin >> n;
	vector<int> vec(n);
	rep(i, n) {
		cin >> a;
		vec[i] = a;
	}
	sort(vec.begin(), vec.end(), greater<int>());

	for(int i=0;i<n;i++){
		if (i % 2 == 0) {
			alice = alice + vec[i];
		}
		else
			bob = bob + vec[i];

	}
	int ans = alice - bob;

	cout << ans;



	return 0;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n;
  cin >> n;
  vec a(n);
  for(ll i=0;i<n;i++) {
    cin >> a[i];
  }
  ll l=0,r=n;
  while(l+1<r) {
    ll m=(l+r)>>1;
    map<ll,ll> cnt;
    cnt[a[0]]=0;
    ll f=1;
    ll zl=0,zr=0;
    for(ll i=1;i<n;i++) {
      if(a[i]>a[i-1]) {
        cnt[a[i]]=0;
        zr=a[i];
        if(a[i-1]) {
          zl=a[i-1]+1;
        }
      }
      else {
        if(m==1) {
          f=0;
          break;
        }
        ll id=a[i];
        while(id) {
          if(zl<=id&&id<=zr) {
            cnt[id]=1;
            zr=id-1;
            break;
          }
          cnt[id]++;
          if(cnt[id]>=m) {
            cnt[id]=0;
            id--;
          }
          else break;
        }
        if(id==0) f=0;
      }
      if(!f) break;
    }
    if(f) r=m;
    else l=m;
  }
  cout << r << endl;
}

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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;


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

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int h,w,d;
    cin>>h>>w>>d;

    vector<vector<int>> mgp(d);
    vector<P> pos(h*w);

    rep(i,h){
        rep(j,w){
            int ai;
            cin>>ai;--ai;
            pos[ai] = P(i,j);
        }
    }

    rep(i,d){
        int p=i;
        mgp[i].eb(0);

        while(p+d < h*w){
            p += d;

            int cost = abs(pos[p-d].fi - pos[p].fi) + abs(pos[p-d].se - pos[p].se);
            mgp[i].eb( mgp[i].back() + cost );
        }
    }

    /*
    rep(i,d){
        cout<<"mod :"<<i<<"  ";
        for(int num :mgp[i])cout<<num<<" ";
        ln;
    }
    */

    int q;
    cin>>q;

    rep(i,q){
        int l,r;
        cin>>l>>r;
        --l;--r;

        int md = l%d;
        int st = (l-md)/d;
        int ed = (r-md)/d;

        cout << mgp[md][ed] - mgp[md][st]<<endl;
    }
    //cout <<fixed<<setprecision(16)<< << endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 6016
n, y = [int(item) for item in input().split()]
a, b, c = 0, 0, 0
bills = y // 1000
a = bills

while a >= 0:
    if (bills - n) % 4 == 0: 
        b = (bills - n) // 4
        check_a = a-(b*5)
        if check_a+b+c == n and b>=0 and check_a>=0:
            print(c, b, check_a)
            exit()
    c += 1
    a -= 10
    bills -= 9
print(-1, -1, -1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int R;
  cin >> R;

  if (R < 1200) {
    cout << "ABC" << endl;
  } else if (1200 <= R && R < 2800) {
    cout << "ARC" << endl;
  } else {
    cout << "AGC" << endl;
  }
 
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
f=1
for i in range(m):
  if sum(a)/(4*m)>a[-i-1]:
    f*=0
  else:
    f*=1
if f==1:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 38384
use std::io;
use std::cmp;

// read a line(without line feed)
fn read_line() -> String {
    let mut in_str = String::new();
    io::stdin().read_line(&mut in_str).unwrap();
    return in_str.trim().to_string();
}

// read wods on a line
pub fn read_words_in_line() -> Vec<String> {
    let s = read_line();
    return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>()
}

// read type t on a line
pub fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for e in read_words_in_line().iter().map(|x| x.parse::<T>()) {
        if let Ok(r) = e {
            v.push(r);
        }
        else{
            return Vec::new();
        }
    }
    return v;
}

// sort slice
pub fn sort<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort();
}
// sort slice by reverse order
pub fn sort_rev<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort_by(|x, y| y.cmp(x));
}

pub fn min<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::min(a, b);
}

pub fn max<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::max(a, b);
}

fn main() {

    let s = read_line().into_bytes();
    let mut ary = [0 ; 26];

    for b in s {
        ary[(b - 'a' as u8) as usize] += 1;
    }
    
    let mut ans = -1 as i32;
    for i in 0..26 {
        if ary[i] == 0{
            ans = i as i32;
            break;
        }
    }
    if ans == -1 {
        println!("None");
    }
    else{
        println!("{}", ((ans as u8) + ('a' as u8)) as char);
    }
    
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


int main() {
    int x, y; cin >> x >> y;

    if(y & 1){
        cout << "No" << endl;
        return 0;
    }

    int a = x * 2;
    if(a == y){
        cout << "Yes" << endl;
    }else{
        int b = y - a;
        if(b < 0){
            cout << "No" << endl;
            return 0;
        }
        int c = b / 2;
        int d = x - c;
        if(0 <= d){
            cout << "Yes" << endl;
        }else {
            cout << "No" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3624
from collections import deque

s=input()
n=int(input())
q=deque()
q.append(s)
f=1
for i in range(n):
    t=list(input().split())
    if int(t[0])==1:
        f*=-1
    else:
        if f==1:
            if t[1]=='1' :
                q.appendleft(t[2])
            else:
                q.append(t[2])
        else:
            if t[1]=='2':
                q.appendleft(t[2])
            else:    
                q.append(t[2])
ans=''.join(q)
if f==-1:
    ans=ans[::-1]


print(ans)   

Measured memory_bytes: 6900
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

void c_h_and_v(void) {
	int h, w, k;
	char c[6][6];
	char c_copy[6][6];
	cin >> h >> w >> k;
	for (int j = 0; j < h; j++) {
		for (int i = 0; i < w; i++) {
			cin >> c[j][i];
		}
	}
	int print_h = int(pow(2.0, h));
	int print_w = int(pow(2.0, w));
	int black_cnt = 0;
	int ans = 0;

	for (int j = 0; j < print_h; j++) {
		for (int i = 0; i < print_w; i++) {
			black_cnt = 0;
			for (int a = 0; a < h; a++) {
				for (int b = 0; b < w; b++) {
					if ((((j >> a) & 0x1) == 0x0) && (((i >> b) & 0x1) == 0x0)) {
						if (c[a][b] == '#') black_cnt++;
					}
				}
			}
			if (black_cnt == k) ans++;

		}
	}
	cout << ans << endl;
}

int main()
{
	c_h_and_v();
    return 0;
}

Measured memory_bytes: 3952
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) begin(v), end(v)
#define allg(v) begin(v), end(v), greater<int>()



int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  long double n;
  cin >> n;
  
  n /= 3;
  
  cout << fixed << setprecision(10) << pow(n, 3.0) << "\n";

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<long long> h(N);
    for (int i = 0; i < h.size(); ++i) cin >> h[i];

    sort(h.begin(), h.end());

    long long dp[100010];
    for (int i = 0; i < 100010; ++i) dp[i]= INF;
    for (int i = 0; i < h.size() - (K - 1); ++i) dp[i] = h[i+(K-1)] - h[i];
    
    long long ans = INF;
    for (int i = 0; i < 100010; ++i) ans = min(ans, dp[i]);

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

Measured memory_bytes: 1792