akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr ll mod = 1e9 + 7;
int n, k;
vector<int> s, inv;
int main() {
	scanf("%d %d", &n, &k);
	int rt = 1;
	for (; rt * rt <= n; rt++)
		s.emplace_back(rt);
	for (rt--; 1 <= rt; rt--)
		s.emplace_back(n / rt);
	vector<ll> dp(s.size()+1, 1);
	for (int j = 1; j < k; j++) {
		vector<ll> dp2(s.size()+1, 0);
		for (int i = 0; i < s.size(); i++) {
			dp2[0] += (0 < i ? s[i] - s[i - 1] : s[i]) * dp[i] % mod;
			dp2[s.size() - i] = -(0 < i ? s[i] - s[i - 1] : s[i]) * dp[i] % mod;
		}
		for (int i = 1; i < s.size(); i++)
			dp2[i] = (dp2[i - 1] + dp2[i]) % mod;
		dp.swap(dp2);
	}
	ll count = 0;
	for (int i = 0; i < s.size(); i++) {
		count += (0 < i ? s[i] - s[i - 1] : s[i]) * dp[i] % mod;
		count %= mod;
	}
	if (count < 0)
		count += mod;
	printf("%lld\n", count);
}

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

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

int main(void){
    int N;
    ll W;
    vector<ll> weight(110);
    vector<ll> value(110);
    cin >> N >> W;
    
    for(int i = 0 ; i < N ; i++){
        cin >> weight[i] >> value[i];
    }
    
    vector< vector<ll> > dp(110,vector<ll>(100100,INF));
    dp[0][0] = 0;
    
    for (int i = 0; i < N; ++i) {
        for (int sum_v = 0; sum_v <= 100100; ++sum_v) {
            
            if (sum_v - value[i] >= 0) {
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);
            }
            
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }
    
    ll res = 0;
    for(int sum_v = 0; sum_v < 100100; sum_v++){
        if(dp[N][sum_v] <= W){
            res = sum_v;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 90316
#include <iostream>
#include <string.h>
#include <set>
#include <vector>
#include <map>
#include <math.h>

using namespace std;
// #define ll long long
typedef long long ll;

int main () {
  ll  H, W, D;
  cin >> H >> W >> D;
  ll A[H][W];
  map <ll, ll> x;
  map <ll, ll> y;
  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      cin >> A[i][j];
      x[A[i][j]] = i;
      y[A[i][j]] = j;  
    }  
  }  
  ll Q;
  cin >> Q;
  ll L[Q], R[Q];
  
  // ここでDの剰余を計算しておく
  set<ll> mod;
  for (ll i = 0; i < Q; i++) {
    cin >> L[i] >> R[i];
    mod.insert(L[i] % D);  
  }
  vector<vector<ll> > ans;
  ans.resize(D);
  for (auto d : mod) {
    // dについて記入していく
    ll start = (ll) d;
    // ans[start]
    ans[start].push_back(0);
    ll end = start;
    while (end <= H * W) {
      ll before = end;
      end = end + D;
      if (end > H * W) {
        break;  
      }
      ll before_i = x[before];
      ll before_j = y[before];
      ll end_i = x[end];
      ll end_j = y[end];
      ll sub = ans[start][ans[start].size() - 1];
      ans[start].push_back(sub + abs(end_i - before_i) + abs(end_j - before_j));
    } 
  }
  /*
  for (int i = 0; i < D; i++) {
    for (int j = 0; j <= H * W; j++) {
      cout << ans[i][j] << " ";  
    }  
    cout << endl;
  }
  cout << endl;
  */
  for (ll i = 0; i < Q; i++) {
    ll sub = L[i] % D;
    R[i] = (R[i] - sub)/D;
    L[i] = (L[i] -sub )/D;
    cout << ans[sub][R[i]] - 
            ans[sub][L[i]] << endl;    
  }
  
}

Measured memory_bytes: 20736
#!/usr/bin/env python3
import sys
# import numpy as np

MOD = 1000000007  # type: int


def solve(S: str):
    # dp = np.zeros((len(S) + 1, 13))
    dp = [[0 for j in range(13)] for i in range(len(S) + 1)]
    dp[0][0] = 1
    for i in range(len(S)):
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
        else:
            j = int(S[i])
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
    print(int(dp[-1][5]) % MOD)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 66140
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector< vector< vector<int> > > G(N+1);
	vector<int> S(N+1);
	for(int i = 3; i <= N; i++) G[i].resize(i+1);
	G[3] = {{}, {3}, {3}, {1, 2}};
	S[3] = 3;
	for(int i = 4; i <= N; i++) {
		for(int j = 1; j < i; j++) ALL_THE(G[i-1][j], it) {
			if(i%2 == 0) G[i][j+1].push_back(*it+1);
			else G[i][j].push_back(*it);
		}
		if(i%2 == 0) for(int j = 2; j < i; j++) {
			G[i][1].push_back(j);
			G[i][j].push_back(1);
			S[i] += j;
		}
		else for(int j = 1; j < i; j++) {
			G[i][i].push_back(j);
			G[i][j].push_back(i);
			S[i] += j;
		}
		for(int j = 1; j <= i; j++) {
			int s = 0;
			ALL_THE(G[i][j], it) s += *it;
		}
	}
	vector< pair<int, int> > E;
	for(int i = 0; i < N; i++) ALL_THE(G[N][i+1], it) if(*it < i+1) E.push_back({i+1, *it});
	cout << E.size() << "\n";
	for(int i = 0; i < (int)E.size(); i++) cout << E[i].ff << " " << E[i].ss << "\n";
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 2432
#include<bits/stdc++.h>
#define N 100005
#define M 1000000007
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define rep(i, begin, end) for( __typeof(end) i = (begin) -((begin) > (end)); i!=(end)-((begin) > (end));i+= 1-2*((begin) >(end)))
#define all(x) (x).begin(),(x).end()
#define Min(...) min({__VA_ARGS__})
#define Max(...) max({__VA_ARGS__})

using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(0);
    int n,ch=0,tw=0,a;
    cin>>n;
    rep(i,0,n){
        cin>>a;
        if(a%2==0 && a%4==0)
            ch++;
        else if(a%2==0)
            tw++;
    }
    //cout<<tw<<' '<<ch<<endl;
    if(tw) 
        n = n -tw+1;
    if(ch >= n/2)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N;
  cin>>N;
  vector<double> vec(N);
  for(ll i=0;i<N;i++) {
cin>>vec[i];
  }
  vector<vector<double>> dp(N+1,vector<double>(N+1,0));
  dp[0][0]=1;
for(ll i=1;i<=N;i++) {
dp[i][0]=dp[i-1][0]*(1-vec[i-1]);
}
  
for(ll i=1;i<=N;i++) {
  for(ll j=1;j<=N;j++) {
    dp[i][j]=dp[i-1][j]*(1-vec[i-1])+dp[i-1][j-1]*vec[i-1];
  }
}
  
  double ans=0;
  for(ll i=N/2+1;i<=N;i++) {
ans+=dp[N][i];
  }
  cout<<fixed<<setprecision(10);
cout<<ans<<endl;
}

  


Measured memory_bytes: 73804
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

const int bound = 200100;
ll fact[bound], fact_inv[bound];

ll power( ll a, ll b ){
	ll res = 1;
	while( b > 0 ){
		if( b & 1 ) res = res*a % mod;
		a = a*a % mod;
		b >>= 1;
	}
	return res;
}

void init(){
	fact[0] = 1;
	int b = bound-10;
	for( int i = 0; i < b; ++i ){
		fact[i+1] = fact[i]*(i+1) % mod;
	}
	fact_inv[b] = power(fact[b], mod-2);
	for( int i = b-1; i >= 0; --i ){
		fact_inv[i] = fact_inv[i+1]*(i+1) % mod;
	}
}

ll comb( ll n, ll r ){
	if( n < r ) return 0;
	return ( fact[n]*fact_inv[r] ) % mod * fact_inv[n-r] % mod;
}

int main(){
	init();
	ll n, k;
	cin >> n >> k;
	vector<ll> a(n);
	vector<ll> b(n);
	for( int i = 0; i < n; ++i ){
		ll t; cin >> t;
		a[i] = b[i] = t;
	}
	sort( a.begin(), a.end() );
	sort( b.begin(), b.end(), greater<ll>() );
	ll mx = 0, mn = 0;
	for( int i = 0; i < n; ++i ){
		mx += (a[i]+mod) * comb(i, k-1); mx %= mod;
		mn += (b[i]+mod) * comb(i, k-1); mn %= mod;
	}
	cout << (mx-mn+mod+mod)%mod << endl;
}

Measured memory_bytes: 4992
#include<stdio.h>
int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	if (a != 1 && b != 1)printf("1\n");
	else if (a != 2 && b != 2)printf("2\n");
	else printf("3\n");
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#define WHITE 1
#define BLACK 2
//#define GRAY 3
#define INF 10000000

int n,A[100][100];
void dijkstra(void);

int main(){
  int i,j,u,k,c,v;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      A[i][j]=INF;
    }
  }

  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d %d",&v,&c);
      A[u][v]=c;
    }

  }
  dijkstra();
  return 0;
  
}


 
void dijkstra(){
  int i,j,u,v,mincost;
  int d[100],p[100],color[100];
  for(u=0;u<n;u++){
    d[u]=INF;
    p[u]=-1;
    color[u]=WHITE;
  }

  d[0]=0;

  while(1){
    mincost=INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK&&d[i]<mincost){
	mincost=d[i];
	u=i;
      }
    }  
    if(mincost==INF)break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if((color[v]!=BLACK)&&(d[v]>A[u][v]+d[u])){

	  p[v]=u;
	  d[v]=A[u][v]+d[u];
	  // color[v]=GRAY;
	
      }
    }
  }
  
  for(j=0;j<n;j++){
    printf("%d ",j);
    if(d[j]!=INF){
      printf("%d\n",d[j]);
    }
  }

}



Measured memory_bytes: 2108
#include <stdio.h>
int main(){
  long	n, a, div0=0, div1=0, div2=0;
  scanf("%ld", &n);
  
  for(int i=0; i<n; i++){
    scanf("%ld", &a);
    if	   ( a%4==0 ){ div2++; }
    else if( a%2==0 ){ div1++; }
  }
  div0 = n - (div1 + div2);
  
  if( div1 ){
    if( div0 <= div2   ){ printf("Yes\n"); return 0; }
  }else{
    if( div0 <= div2+1 ){ printf("Yes\n"); return 0; }
  }
  printf("No\n");
  return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;

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

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

    cout << A[N-1] - A[0] << endl;

    return 0;
}

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

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

template<class T> using v = std::vector<T>;
template<class T> using vv = v<v<T>>;

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


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

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

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll A, B, K; cin >> A >> B >> K;

    if (A > 0) {
        if (A > K) {
            A -= K;
            K = 0;
        } else {
            K -= A;
            A = 0;
        }
    }
    if (B > 0) {
        if (B > K) {
            B -= K;
            K = 0;
        } else {
            K -= B;
            B = 0;
        }
        K -= B;
    }

    cout << A << ' ' << B << endl;
    return 0;
}


Measured memory_bytes: 256
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b){
  ll r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


ll LCM(ll a,ll b){
  ll c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

vector<pair<char,ll>> runlength(string s,vector<pair<char,ll>> p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
    return p;
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
  return p;
}


ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}







/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  vector<ll> v(10);
  rep(i,10) cin>>v[i];
  sort(ALL(v),greater<ll>());
  cout<<v[0]<<endl;
  cout<<v[1]<<endl;
  cout<<v[2]<<endl;
  
}


Measured memory_bytes: 3116
#include<stdio.h>
int main()
{
  int a[3];
  for(int i=0;i<3;i++)
    scanf("%d",&a[i]);
    int swap=a[1];
    a[1]=a[0];
    a[0]=swap;
     swap=a[2];
    a[2]=a[0];
    a[0]=swap;
    
    for(int i=0;i<3;i++)
    printf("%d ",a[i]);
    
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    long long m = 0, a = 0, r = 0, c = 0, h = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        if(s[0] == 'M'){m++;}
        if(s[0] == 'A'){a++;}
        if(s[0] == 'R'){r++;}
        if(s[0] == 'C'){c++;}
        if(s[0] == 'H'){h++;}
        
    }
    long long ans = m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h + a*r*c + a*r*h + a*c*h + r*c*h;
    cout << ans;
    
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,c;
    scanf("%d",&n);
    char s[n+3];
    scanf("%s",&s);
    i=0;
    j=n-1;
    c=0;
    while(i<j){
        if(s[i]=='W'&&s[j]=='R'){
           c++;
           i++;
           j--;
        }
        else if(s[i]=='W'&&s[j]=='W'){
           j--;
        }
        else if(s[i]=='R'&&s[j]=='R'){
           i++;
        }
        else{
            i++;
            j--;
        }
    }
    printf("%d\n",c);
    return 0;
}


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

const int N = 2e5 + 10 , inf = 1e9;

int n;
int num[N] , Map[N] , val[2][N*4];

void build(int x , int l , int r)
{
	if(l == r)
	{
		val[l & 1][x] = num[l];
		val[(l & 1)^1][x] = inf;
		return;
	}
	int mid = l + r >> 1;
	build(x<<1 , l  , mid);
	build(x<<1|1 , mid + 1 , r);
	val[0][x] = min(val[0][x<<1] , val[0][x<<1|1]);
	val[1][x] = min(val[1][x<<1] , val[1][x<<1|1]);
} 
void Build(){build(1 , 1 , n);}

int ask(int x , int l , int r , int L , int R , bool o)
{
	if(l >= L && r <= R)
		return val[o][x];
	int mid = l + r >> 1 , ans = inf;
	if(L <= mid) ans = min(ans , ask(x<<1 , l , mid , L , R , o));
	if(R > mid) ans = min(ans , ask(x<<1|1 , mid + 1 , r , L , R , o));
	return ans;
}
int Ask(int l , int r , bool o) {return ask(1 , 1 , n , l , r , o);}

struct Seg
{
	int l , r , val;
	bool operator< (const Seg &t) const
	{
		return val > t.val;
	}
	Seg(){}
	Seg(int l, int r) :l(l) , r(r)
	{
		val = Ask(l , r , l&1);
	}
};

priority_queue<Seg> q;

int main()
{
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; i ++)
	{
		scanf("%d" , num + i);
		Map[num[i]] = i;
	}
	Build();
	q.push(Seg(1 , n));
	while(!q.empty())
	{
		Seg now = q.top();
		q.pop();
		int l = Map[now.val];
		bool id = l & 1; 
		int r = Map[Ask(l + 1 , now.r , id^1)];
		printf("%d %d " , num[l] , num[r]);
		if(l != now.l)
			q.push(Seg(now.l , l - 1));
		if(r - l >= 2)
			q.push(Seg(l + 1 , r - 1));
		if(now.r != r)
			q.push(Seg(r + 1 , now.r));
	}
	puts("");
}

Measured memory_bytes: 9848
#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<string, int>;
const int INF = 1000000007;

int main() {
  int l, r, d;
  cin >> l >> r >> d;
  int cnt = 0;
  for (int i = l; i <= r; i++) {
    if (i % d == 0) cnt++;
  }
  cout << cnt << endl;
}


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

using ll = long long;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

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

ll mod_pow(ll a, ll n, ll m) {
    ll res = 1;
    while (n > 0) {
        if (n % 2 == 1) (res *= a) %= m;
        (a *= a) %= m;
        n /= 2;
    }
    return res;
}

map<int, int> factorize(int x) {
    map<int, int> res;
    for (int d = 2; d * d <= x; ++d) {
        int count = 0;
        while (x % d == 0) {
            ++count;
            x /= d;
        }
        if (count > 0) res[d] = count;
    }
    if (x > 1) res[x] = 1;
    return res;
}

int euler_totient(int x) {
    int res = x;
    for (int y = 2; y * y <= x; ++y) {
        if (x % y == 0) {
            res -= res / y;
            while (x % y == 0) x /= y;
        }
    }
    if (x > 1) res -= res / x;
    return res;
}

int N;

int main(void) {
    cin >> N;

    auto n_factors = factorize(N);
    ll L = 1;
    for (auto& itr : n_factors) {
        if (itr.second > 1) {
            cout << -1 << endl;
            exit(0);
        }
        L = lcm(L, itr.first - 1);
    }

    if (gcd(N, L) > 1) {
        cout << -1 << endl;
        exit(0);
    }

    const int el = euler_totient(L);
    int ans = el;
    for (int x = 1; x * x <= el; ++x) {
        if (el % x == 0) {
            if (mod_pow(N, x, L) == 1)
                ans = min(ans, x);
            if (mod_pow(N, el / x, L) == 1)
                ans = min(ans, el / x);
        }
    }

    cout << ans << endl;


    return 0;
}



Measured memory_bytes: 3120
#include<stdio.h>
int main(void)
{
   int a,b,d,r;
   double f=0;
   scanf("%d",&a);
   scanf("%d",&b);
   d=a/b;
   r=a%b;
   f=(double)a/(double)b;
   printf("%d %d %lf\n",d,r,f);
   return 0;
}

Measured memory_bytes: 636
#include <iostream>
#include <stdio.h>
using namespace std;

const int MX = 200005, MOD = 1E9 + 7;

int m, n, k;
long long ans = 0;
long long ngt[MX]; // tinh n giai thua
long long ive[MX]; // tinh nghich dao modulo cua ive[i]
long long kgt[MX]; // tinh nghich dao modulo cua k giai thua (tinh tich nghich dao modolu tu 1 -> k)
long long d[MX];   // tong do "chenh lech" cua (1, 1) -> (1, max(n, m))
long long c[MX];   // mang tong (de hieu :]]] )

void gener()
{
    ngt[0] = kgt[0] = 1;
    ngt[1] = kgt[1] = ive[1] = 1;
    for (int i = 2; i <= m * n; i++)
    {
        ngt[i] = ngt[i - 1] * i % MOD;
        ive[i] = MOD - MOD / i * ive[MOD % i] % MOD;
        kgt[i] = kgt[i - 1] * ive[i] % MOD;
    }
}

void solve()
{
    for (int i = 1; i <= max(m, n); i++)
    {
        c[i] = (c[i - 1] + (i - 1)) % MOD;
        d[i] = (c[i] + d[i - 1]) % MOD;
    }
    ans += d[m] * n % MOD * n % MOD;
    ans += d[n] * m % MOD * m % MOD;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    gener();
    solve();
    cout << ans * ngt[m * n - 2] % MOD * kgt[k - 2] % MOD * kgt[m * n - k] % MOD;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main(){
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  for(int i=n; i>=0; i--){
    bool same = true;
    for(int j=0; j<i; j++){
      if(s[n-i+j] != t[j]) same = false;
    }
    if(same){
      cout << n+n-i << endl;
      return 0;
    }
  }
}

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

ll gcd(ll a, ll b) { if (!b)return a; return gcd(b, a%b); }
ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
int main() {
	ll a;
	while (scanf("%lld", &a), a) {
		vector<ll>v;
		for (ll i = 1; i*i <= a; i++) {
			if (a%i == 0) {
				v.push_back(i);
				if (i != a / i)v.push_back(a / i);
			}
		}
		sort(v.begin(), v.end());
		int cnt = 0;
		rep(i, v.size())for (int j = i; j < v.size(); j++) {
			if (lcm(v[i], v[j]) == a)cnt++;
		}
		printf("%d\n", cnt);
	}
}

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

using namespace std;



int num_dig(int N, int K) {
	int qtd = 0;
	while(N) {
		++qtd;
		N /= K;
	}
	return qtd;
}

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

	int N, K;
	cin >> N >> K;

	cout << num_dig(N, K) << '\n';

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <tuple>
#include <string>

using namespace std;

#define D(x) x
#define REP(i,a,b) for (int i = (a); i < (b); ++i)

int main() {
    ios_base::sync_with_stdio(false);
    cout << setprecision(12) << fixed;

    string s; cin >> s;

    long long result = 0;

    for (int x = 0; x < (1 << (s.length() - 1)); ++x) {
     //   cout << "x: " << x << endl;
        int l = 0, r = 0;
        do {
            while (r < s.length() - 1 && (((x >> r) & 1) != 1)) {
                r++;
            }
   //         cout << "l: " << l << ", r: " << r << endl;
            result += atoll(s.substr(l, r-l+1).c_str());
            r++;
            l = r;
        } while (r < s.length());
    }

    cout << result << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int A, B;
    cin >> A >> B;

    cout << max(A - 2 * B, 0 ) << endl;
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = []
for i in range(H):
    S.append(list(input()))

visited = [[0 for j in range(W)] for i in range(H)]
seen = [[0 for j in range(W)] for i in range(H)]
done = set()

def bfs(u, done):
    stack = deque([u])
    seen[u[0]][u[1]] = 1

    while len(stack) > 0:
        v = stack.popleft()
        done.add(v)
        visited[v[0]][v[1]] = 1
        ###
        w1 = (v[0] + 1, v[1])
        w2 = (v[0] , v[1] + 1)
        w3 = (v[0] - 1, v[1])
        w4 = (v[0] , v[1] -1)
        ###

        ws = [w1,w2,w3,w4]

        for w in ws:
            if w[0] >= 0 and w[0] < H and w[1] >= 0 and w[1] < W:
                if S[w[0]][w[1]] == ".":
                    if seen[w[0]][w[1]] == 0:
                        stack.append(w)
                        seen[w[0]][w[1]] = 1

bfs((Ch-1,Cw-1), done)

count = 0
# print("d",done)
# for i in range(H):
#     print(visited[i])

while True:
    if visited[Dh-1][Dw-1] == 1:
        print(count)
        sys.exit()
    else:
        count += 1
        pp = deque([])
        for d in list(done):
            i = d[0]
            j = d[1]
            for k in range(-2,3):
                for l in range(-2,3):
                    if i+k >= 0 and i+k < H and j+l >= 0 and j+l < W:
                        if S[i+k][j+l] == ".":
                            if visited[i+k][j+l] == 0:
                                pp.append((i+k,j+l))

        if len(pp) == 0:
            print(-1)
            break

        done = set()
        for ppp in pp:
            bfs(ppp, done)












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

using namespace std;

#define F first

#define S second

#define pb push_back

#define Pi pair<int,int>

#define Pii pair<Pi,int>

int main(){

  vector<Pii>v;

  int d[3];

  int N;cin >> N;

  for(int i = 0;i < N;i++){

    cin >> d[0] >> d[1] >> d[2];

    sort(d,d + 3);

    Pii t;

    t.F.F = d[0];t.F.S = d[1],t.S = d[2];

    v.pb(t);

  }

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

  int a = v.size();

  v.erase(unique(v.begin(),v.end()),v.end());

  int b = v.size();

  cout << a - b << endl;

  return 0;

}

Measured memory_bytes: 3144
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;
ll n, m;

int main(){
	scanf("%lld%lld", &n, &m);
	ll sum = 0;
	if(n >= m / 2){
		printf("%lld\n", m / 2);
		return 0;
	}
	sum = n;
	m = m - 2 * n;
	sum += m / 4;
	printf("%lld\n", sum);
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int main(void)
{
	int n;
	vector<int>a, ans;
	set<int>se;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int aa;
		cin >> aa;
		a.push_back(aa);
	}
	for (int i = n - 1; i >= 0; i -= 2)
	{
		ans.push_back(a[i]);
		se.insert(i);
	}
	for (int i = 0; i < n; ++i)
	{
		if (!se.count(i))
		{
			ans.push_back(a[i]);
		}
	}
	assert(n == ans.size());
	for (int i = 0; i < n; ++i)
	{
		cout << ans[i] << " \n"[i == n - 1];
	}
	return 0;
}


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

string s;
set<string> subs;
int k;
int main(){
    cin >> s >> k;
    for(int i = 0; i < s.size(); i++){
        for(int j = i+1; j <= s.size(); j++){
            if(j-i > k) break;
            subs.insert(s.substr(i, j-i));
        }
    }
    set<string>::iterator it = subs.begin();
    advance(it, k-1);
    cout << *it;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
#define maxs(x,y) x = max(x, y)
#define mins(x,y) x = min(x, y)
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int a, b;
    cin >> a >> b;
    
    if (a > b) {
        REP(i, a) {
            cout << b;
        }
        cout << endl;
    } else {
        REP(i, b) {
            cout << a;
        }
        cout << endl;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int tmp=0,N=0,M=0,a=0,ans=0,b=0,c=0,count=0;
    string str;
    vector<int> vec;
    vector<int> rei;
    scanf("%d",&N);
    

    for(int i=0;i<N;i++){
        scanf("%d",&tmp);
        vec.push_back(tmp);
    }

    rei=vec;
    sort(rei.begin(),rei.end());
    a=rei[N/2];
    b=rei[N/2-1];

    for(int i=0;i<N;i++){
        if(vec[i]<a){
            cout<<a<<endl;
        }else{
            cout<<b<<endl;
        }
    }

}

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

#define f first
#define s second
#define p pair<int,int>
#define pb push_back
#define ll long long
#define db double

const int inf=1e9+10;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    string s1,s2;
    cin>>s1;
    cout<<"ABC"<<s1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
class Edge{
public:
    int from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};

int main(){
    int N;cin >> N;
    map<map<char, int>,LL> vec;
    for(int i = 0;i < N;i++){
        string s;cin >> s;
        map<char,int> mp;
        for(auto a : s)mp[a]++;
        vec[mp]++;
    }
    LL ans = 0;
    for(auto a : vec){
        ans += (a.second*(a.second-1))/2;
    }
    cout<<ans<<endl;
}


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

int main(){


    map<int, int> cnt;

    int n; 
    cin >> n;

    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        if (cnt.count(temp)){
            cnt[temp]++;
        } else {
            cnt[temp] = 1;
        }
    }

    int res = 0;
    map<int, int>::iterator it;

    for ( it = cnt.begin(); it != cnt.end(); it++ )
    {
        if (it->second < it->first){
            res += it->second;
        } else if (it->second > it->first){
            res += (it->second - it->first);
        }
    }

    cout << res;
    return 0;
}

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

int main() {
  long N, D, X, a, ans = 0;
  cin >> N >> D >> X;
  
  for (int i = 0; i < N; i++) {
    cin >> a;   
    ans += (D-1)/a+1;
  }
  
  cout << ans+X << endl;
}

Measured memory_bytes: 3572
//file_name:ABC55_A.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


int main() {
    int n;
    scanf("%d",&n);


    ll ans = 800*n - (n/15)*200;

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



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define size(a) int((a).size())
#define present(c, x) (c.find(x) != c.end()) 
#define printVerdict(verdict) cout << (verdict ? "Yes": "No") << '\n'
#define printDecimal(d) printf("%.9f\n", d)
#define inrange(val, start, end) (val >= start && val <= end)
 
const int mod = 1e9 + 7; 
 
template <class T1, class T2, class T3> 
void printTuple(tuple<T1, T2, T3> t) { cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << '\n'; }
template <class T1, class T2>
void printPair(pair<T1, T2> p) { cout << p.first << " " << p.second  << '\n'; }
template <class T>
void printArray(vector<T> arr) { for (int i = 0; i<size(arr); i++) {cout << arr[i] << " ";} cout << '\n'; } 

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	int d,t,s; cin >> d >> t >> s;
	printVerdict(t*s >= d);
}


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

struct cell {
  string str;
  int x;
  int y;
};

int main(){
  int n;
  cin >> n;
  cell c[n];
  for (int i=0;i<n;i++){
    cin >> c[i].str >> c[i].x;
    c[i].y=i+1;
  }
  for (int i=0;i<n-1;i++){
    for (int j=0;j<n-i-1;j++){
      if (c[j].str == c[j+1].str){
        if (c[j].x < c[j+1].x){
          cell p;
          p=c[j+1];
          c[j+1]=c[j];
          c[j]=p;
        }
      }else if (c[j].str > c[j+1].str){
        cell p;
        p=c[j+1];
        c[j+1]=c[j];
        c[j]=p;
      }
    }
  }
  for (int i=0;i<n;i++){
    cout << c[i].y << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e7+7;
int lp[N];
void sieve(){
	for(int i=2; i<N; i++) {
		if(!lp[i]) {
			lp[i]=i;
			for(int j=i+i; j<N; j+=i) {
				lp[j]=i;
			}
		}
	}
}
int dcmp(int m){
	map<int,int> mp;
	while(m!=1) {
		mp[lp[m]]++;
		m/=lp[m];
	}
	ll ans=1;
	for(auto m:mp) {
		ans=ans*(m.second+1);
	}
	return ans;
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	int n; cin>>n;
	sieve();
	ll ans=0;
	for(int i=1; i<=n; i++) {
		ans= ans+ i*1ll*dcmp(i);
	}
	cout<<ans<<endl;


	return 0;
}


Measured memory_bytes: 42700
import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
A = [int(input()) for _ in range(N)]

p1 = 0
p2 = 0
P1 = [0]
P2 = [0]
for a in A:
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1.append(p1)
    P2.append(p2)

dp = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[0] = max(dp[0], P1[i])
    dp[1] = max(dp[1], P2[i]+dp[0])
    dp[2] = min(dp[2], P2[i]-dp[1])
    dp[3] = min(dp[3], P1[i]+dp[2])

print(dp[3]+sum(A))


Measured memory_bytes: 37464
#include <stdio.h>
#define MAX 2000000

void swap(int *, int *);
void maxHeapify(int);

int H,A[MAX+1];

void swap(int *a, int *b){
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
  return;
}

void maxHeapify(int i){
  int l, r, largest;
  l = 2 * i;
  r = 2 * i + 1;

  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r;

  if(largest != i){
    swap(&A[i], &A[largest]);
    maxHeapify(largest);
  }
}

int main(){
  scanf("%d",&H);

  for(int i=1; i<=H; i++) scanf("%d", &A[i]);

  for(int i=H/2; i>=1; i--) maxHeapify(i);

  for(int i=1; i<=H; i++){
    printf(" %d", A[i]);
  }
  printf("\n");

  return 0;
}



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

int main() {
  string s;
  int flag1 = 0;
  int flag2 = 0;
  int flag3 = 0;

  cin >> s;

  if(s.size() < 6) {
    cout << "INVALID" << endl;
    return 0;
  }
  for(int i = 0; i < s.size(); i++) {
    if(s[i] > 96 && s[i] < 123)
      flag1 = 1;
    else if(s[i] > 64 && s[i] < 91)
      flag2 = 1;
    else if(s[i] > 47 && s[i] < 58)
      flag3 = 1;
  }
  if(flag1 == 1 && flag2 == 1 && flag3 == 1)
    cout << "VALID" << endl;
  else
    cout << "INVALID" << endl;
  return 0;
}



Measured memory_bytes: 3200
# coding: utf-8
# Your code here!

n = int(input())
al = list(map(int,input().split()))

sum_a = sum(al)

odd = 0
for i in range(n):
    if i % 2 == 1:
        odd += al[i]
        
ans_l = []
ans_l.append(sum_a - 2*odd)
his = sum_a - 2*odd
for i in range(n-1):
    his = al[i]*2 - his
    ans_l.append(his)

for i in ans_l:
    print(i)

Measured memory_bytes: 65636
fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    val S = readInputLine().toCharArray()

    var ans = 0

    for (i in 2 until N) {
        if (S[i - 2] == 'A' && S[i - 1] == 'B' && S[i] == 'C') ans++
    }

    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 33560
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int main() {
    int n; cin >> n;
    for (int i = 1; i <= 9; ++i) {
        for (int j = 1; j <= 9; ++j) {
            if (i * j == n) {
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
}


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

#define int long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define all(c) (c).begin(),(c).end()
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;
const ld PI = acos(-1.0);

int32_t main(){
	fast;
	int k,s,ans =0;
	cin >> k >> s;
	for(int i=0 ; i<=k ; i++)
	{
		for(int j=0 ; j<=k ; j++)
			if(s - i - j >= 0 && s - i - j <= k)
				ans++;
	}
	cout << ans;
}



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

bool isMonth(int n){
    return n>=1 and n<=12;
}

int main(void){
    string s;
    cin>>s;
    int u=stoi(s.substr(0,2));
    int l=stoi(s.substr(2,2));
    if(isMonth(u)){
        if(isMonth(l)){
            cout << "AMBIGUOUS";
        }else{
            cout << "MMYY";
        }
    }else{
        if(isMonth(l)){
            cout << "YYMM";
        }else{
            cout << "NA";
        }  
    }
    return 0;
}


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

typedef long long ll;
using namespace std;
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define out(s) cout << s << endl


int main(){
    int n;cin >> n;
    vector<int>a(n);
    rep(i,n)cin >> a[i];
    int c=0;
    int x=0;
    while(1){
        if(x==1){
            cout << c << endl;
            break;
        }
        if(c>=n){
            cout << -1 << endl;
            break;
        }
        c++;
        
        x=a[x];
        x--;
    }
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>
//#include <functional>


int main(){
    int32_t N;
    std::cin >> N;
    int32_t cur = 0;
    int32_t peak = 0;
    for(int32_t i = 0; i < N; i++){
        std::cin >> cur;
        if(peak - cur >= 2){
            std::cout << "No";
            return 0;
        }
        peak = std::max(cur, peak);
    }
    std::cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i+=1)
#define reps(i,a,b) for(int i=a;i>=b;i-=1)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define in1(x) int x; cin>>x;
#define in2(x, y) int x, y; cin>>x>>y;
#define in3(x, y, z) int x, y, z; cin>>x>>y>>z;
#define in4(x, y, z, w) int x, y, z, w; cin>>x>>y>>z>>w;
#define mi unordered_map<int,int>
#define mem(x) memset(x, 0, sizeof(x))
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
using namespace std;

//bool primes[1000001];vi prime;
//void seive(){memset(primes, true, sizeof(primes));primes[0] = primes[1] = false;for(int i = 2; i*i<=1000000;i += 1){
//if(primes[i]){for(int j = i*i; j <= 1000000;j += i) primes[j] = false;}}rep(i, 2, 1000001){if(primes[i]) prime.pb(i);}}

//int gcd(int a, int b){return b==0 ? a : gcd(b, a%b);}

int32_t main(void){
	IOS;
	
	in1(n);
	int arr[n];
	rep(i, 0 ,n) cin>>arr[i];
	sort(arr, arr+n);
	if(arr[0] == 0) cout<<0<<endl;
	else
	{
		int ans = 1;
		int tmp = 1000000000000000000;
		rep(i, 0, n)
		{
			if(tmp/ans >= arr[i]) ans *= arr[i];
			else
			{
				cout<<-1<<endl;
				return 0;
			}
		}
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 4444
#include<cstdio>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
using namespace std;
int main(){
    int a, b, maxx,minn;
    cin >> a >> b;
    maxx = max(a, b);
    minn = min(a, b);
    for (int i = 1; i <= maxx;i++)
    {
        cout << minn;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]
import math
A,B,N = read_int_map()

if N < B:
    print(math.floor(A*N/B)-A*math.floor(N/B))
else:
    print(math.floor(A*(B-1)/B)-A*math.floor((B-1)/B))

'''
for i in range(1,N+1):
    print(i, math.floor(A*i/B)-A*math.floor(i/B))
'''

Measured memory_bytes: 61992
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n + 1);
    h[0] = 0;
    rep(i, n) {
        cin >> h[i + 1];
    }
    ll dp[330][330];
    rep(i, 330) rep(j, 330) dp[i][j] = 1e+14;
    dp[0][0] = 0;
    rep(x, n + 1) {
        rep(y, x + 1) {
            for(int i = x + 1; i <= n; ++i) {
                chmin(dp[i][y + i - 1 - x], dp[x][y] + max(0LL, h[i] - h[x]));
            }
        }
    }
    ll res = INF;
    for(int i = n; i >= n - k; i--) {
        for(int j = 0; j <= k - (n - i); ++j) {
            chmin(res, dp[i][j]);
        }
    }
    cout << res << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
#define for1(i,n) for (ll i=0;i<(n);(i)++)
#define for2(i,m,n) for (ll (i)=(m);(i)<(n);(i)++)
#define for3(i,m,n,d) for (ll (i)=(m);(i)<(n);(i)+=(d))
#define INF (1LL << 60)

void solve()
{
    string S,T;
    ll N;
    cin >> N;
    cin >> S;
    cin >> T;
    for (ll i = N; i >= 0; --i) {
        if (S.substr(N-i,i) == T.substr(0,i)) {
            cout << N * 2 - i << endl;
            return;
        }
    }
    cout << 0 << endl;
}

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


Measured memory_bytes: 256