akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FR first
#define SE second
#define inf 0x3f3f3f3f

using namespace std;

typedef pair<int,int> pr;

namespace SGT {

const int Maxn=5000000;

int ch[Maxn][2],tot;
int max1[Maxn],max2[Maxn];

inline int cpynode(int o) {
  tot++;
  ch[tot][0]=ch[o][0];ch[tot][1]=ch[o][1];
  max1[tot]=max1[o];max2[tot]=max2[o];
  return tot;
}

inline void pushup(int o) {
  max1[o]=max(max1[ch[o][0]],max1[ch[o][1]]);
  max2[o]=max(max2[ch[o][0]],max2[ch[o][1]]);
}

int update(int l,int r,int o,int p,pr q) {
  o=cpynode(o);
  if (l==r) {
  	max1[o]=q.FR;max2[o]=q.SE;
  }
  else {
  	int m=((l+r)>>1);
  	if (m>=p) ch[o][0]=update(l,m,ch[o][0],p,q);
  	else ch[o][1]=update(m+1,r,ch[o][1],p,q);
  	pushup(o);
  }
  return o;
}

int query(int l,int r,int o,int p,bool q) {
  if (!o) return (!q)?0:-inf;
  if (l==r) return (!q)?max1[o]:max2[o];
  else {
  	int m=((l+r)>>1);
  	if (m<p) return query(m+1,r,ch[o][1],p,q);
  	else {
  		int t=query(l,m,ch[o][0],p,q);
  		return (!q)?max(t,max1[ch[o][1]]):max(t,max2[ch[o][1]]);
	  }
  }
}

}

int root[200005],num[200005];
bool tag[200005];

int pre(int n) {
  int s=0,maxn=0;
  for(int i=1;i<=n;i++)
    if (num[i]>maxn) {
    	maxn=num[i];
    	s++;
    	tag[i]=1;
	}
  for(int i=n;i>0;i--)
    if (tag[i]) {
    	int t1=SGT::query(1,n+1,root[i+1],num[i]+1,0),t2=SGT::query(1,n+1,root[i+1],num[i]+1,1);
    	root[i]=SGT::update(1,n+1,root[i+1],num[i],pr(t1+2,t2+2));
	}
	else {
		int t=SGT::query(1,n+1,root[i+1],num[i]+1,0);
		root[i]=SGT::update(1,n+1,root[i+1],num[i],pr(t+1,t+1));
	}
  return s;
}

int main() {
  SGT::max1[0]=0;SGT::max2[0]=-inf;
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&num[i]);
  int s=pre(n);
  if ((s&1)&&SGT::query(1,n+1,root[1],1,1)<s) {
  	puts("-1");
  	return 0;
  }
  int r1=0,r2=0,d=0;
  for(int i=1;i<=n;i++) {
  	s-=tag[i];
  	int t=d+(num[i]>r1),c=max(r1,num[i]);
  	bool ok=1;
  	if ((t^s)&1) {
  		if (t>=0) {
  			if (SGT::query(1,n+1,root[i+1],r2+1,1)<s+t&&(t>s||SGT::query(1,n+1,root[i+1],c+1,1)<s-t)) ok=0;
		  }
		else {
			if (SGT::query(1,n+1,root[i+1],c+1,1)<s-t&&(-t>s||SGT::query(1,n+1,root[i+1],r2+1,1)<s+t)) ok=0;
		}
	  }
	else {
		if (t>=0) {
			if (SGT::query(1,n+1,root[i+1],r2+1,0)<s+t) ok=0;
		}
		else {
			if (SGT::query(1,n+1,root[i+1],c+1,0)<s-t) ok=0;
		}
	}
	if (ok) {
		putchar('0');
		d+=(num[i]>r1);
		r1=max(r1,num[i]);
	}
	else {
		putchar('1');
		d-=(num[i]>r2);
		r2=max(r2,num[i]);
	}
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 65920
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));
int lcs(string X, string Y)
{
	int m = X.size(), n = Y.size();
	X = ' ' + X, Y = ' ' + Y;
	V2(C, 1001, 1001);
	for(int i = 1; i <= m; ++i){
		for(int j = 1; j <= n; ++j){
			if(X[i] == Y[j]){
				C[i][j] = C[i-1][j-1] + 1;
			}else{
				C[i][j] = max(C[i][j-1], C[i-1][j]);
			}
		}
	}
	return C[m][n];
}
int main(){
	int q; cin >> q;
	REP(i, q){
		string X, Y;
		cin >> X >> Y;
		cout << lcs(X, Y) << endl; 
	}
}



Measured memory_bytes: 6908
N = int(input())
arr1 = list(map(int,input().split()))
arr2 = [0 for _ in range(N)]
sum = 0
for i in range(N):
    arr2[i] = sum+arr1[i]
    sum = arr2[i]

k = 10**9+7

count = 0
for i in range(N-1):
    count += arr2[i]*arr1[i+1]
    count %= k

print(count)


Measured memory_bytes: 102088
A= int(input())
if 400<=A<600:
   print(8)
if 600<=A<800:
   print(7)
if 800<=A<1000:
   print(6)
if 1000<=A<1200:
   print(5)
if 1200<=A<1400:
   print(4)
if 1400<=A<1600:
   print(3)
if 1600<=A<1800:
   print(2)
if 1800<=A<2000:
   print(1)

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

int main() {
  int n, m;
  cin >> n >> m;
  int num[n];
  bool red[n];
  rep(i,n) {
    num[i]=1; red[i]=false;
  }
  red[0]=true;
  rep(i,m) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    num[x]--; num[y]++;
    if(red[x]) red[y]=true;
    if(num[x]==0) red[x]=false;
  }
  int ans=0;
  rep(i,n) {
    if(red[i]) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 768
#include <cstdio>
#include <cstdint>
#include <cinttypes>
#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <numeric>
using namespace std;
using i8t = std::int64_t;
using u8t = std::uint64_t;
using vi8t = std::vector<i8t>;
using vvi8t = std::vector<std::vector<i8t>>;
using vu8t = std::vector<u8t>;
#include <limits>
static const i8t i8t_max=numeric_limits<i8t>::max();
static const i8t i8t_min=numeric_limits<i8t>::min();
#include <unordered_map>
#include <unordered_set>
template<typename Key,typename Value> using map_t=std::unordered_map<Key, Value>;
template<typename Key> using set_t=std::unordered_set<Key>;
#define F3(i,i0,iN,step) for(i8t i=i0,i##_N=iN;i<i##_N;i+=step)
#define F2(i,i0,iN) F3(i,i0,iN,1)
#define F(i,N) F3(i,0,N,1)
#define FR(i,N) for(i8t i=N;i--;)
#define R(V) i8t V;std::cin>>V;
#define RV(V,N) std::vector<i8t> V;F(_i,N){R(_x)V.push_back(_x);}
#define RL1(line) std::getline(std::cin,line);
#define RL(line) std::string line;RL1(line)
#define RM(V,L,C) std::vector<char> V;F(_i,L){RL(_l)F(_j,C)V.push_back(_l[_j]);}
#define P(X) std::cout<<(X)<<std::endl;
template<typename T> T umax(T& ans,T const& value) {if(value>ans)ans=value;return ans;}
template<typename T> T umin(T& ans,T const& value) {if(value<ans)ans=value;return ans;}
template<typename T> struct identity { using type = T; };

int main() {
  R(K)R(N)RV(A,N);
  A.push_back(A[0]+K);

  i8t mxd=0;
  F(i,N)umax(mxd,A[i+1]-A[i]);
  P(K-mxd);
  return 0;
}


Measured memory_bytes: 2420
n = int(input())
d = list(map(int, input().split()))

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

d.sort()
import collections
c = collections.Counter(d)

if c[0] != 1:
    print(0)
    exit()
ans=1
for i in range(1,d[-1]+1):
    if c[i] == 0:
        print(0)
        exit()
    ans*=(c[i-1]**c[i])
    ans%=998244353

print(ans)

Measured memory_bytes: 62004
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <vector>

using namespace std;
typedef long long ll;


ll ans,mx,mn=1e8,sum,cnt;
ll odd,even;
ll b[2000000];
int main(){
	ll n,k;
	cin>>n>>k;
	ll a[n];
	for(ll i=0; i<n; i++){
		cin>>a[i];
	}
	sort(a,a+n);
	sum = 0;
	ll idx=0;
	for(ll i= 0; i<n; i++){
		cnt++;
		if(a[i]!=a[i+1]){
			sum++;
			b[idx++] = cnt;
			cnt = 0;
		}
	}
	sort(b,b+sum);
	for(ll i=0; i<sum-k; i++){
		ans+=b[i];
	}
	cout<<ans<<endl;
	
}


Measured memory_bytes: 3328
# abc106_c.py
# https://atcoder.jp/contests/abc106/tasks/abc106_c

# C - To Infinity /
# 実行時間制限: 2 sec / メモリ制限: 1000 MB
# 配点: 300点

# 問題文
# Mr. Infinity は, 1 から 9 までの数字からなる文字列 Sを持っている. この文字列は, 日付が変わるたびに次のように変化する.
#     文字列 S    に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666666, 7 が 7777777, 8 が 88888888, 9 が 999999999 に置き換わる. 1 は 1 のまま残る.
#     例えば, Sが 1324 の場合, 翌日には 1333224444 になり, 翌々日には 133333333322224444444444444444 になる.

# あなたは 5000 兆日後に文字列がどのようになっているか知りたい. 5000 兆日後の文字列の左から K文字目は何か？

# 制約
#     Sは 1 文字以上 100文字以下の文字列.
#     Kは 1 以上 1018以下の整数.
#     5000兆日後の文字列の長さは K文字以上である.

# 入力
# 入力は以下の形式で標準入力から与えられる.
# S
# K

# 出力
# 5000兆日後に Mr. Infinity が持っている文字列の K文字目の数字を出力しなさい.

# 入力例 1
# 1214
# 4

# 出力例 1
# 2

# 文字列 Sは次のように変化していく.

#     現在: 1214
#     1日後: 12214444
#     2日後: 1222214444444444444444
#     3日後: 12222222214444444444444444444444444444444444444444444444444444444444444444

# 5000兆日後の文字列の最初 5 文字は 12222 となる. K=4 なので, 4文字目の 2 を出力すればよい.

# 入力例 2
# 3
# 157

# 出力例 2
# 3

# 文字列ははじめ 3 である. 5000兆日経ったとき, 文字列は 3 だけで構成される.

# 入力例 3
# 299792458
# 9460730472580800

# 出力例 3
# 2


def calculation(lines):
    # A, B = list(map(int, lines[0].split()))
    S = lines[0]
    K = int(lines[1])
    n_seq1 = get_n_seq1(S)
    if n_seq1 >= K:
        return [1]
    else:
        return [S.replace('1', '')[0]]
    return [cnt]


def get_n_seq1(S):
    ret = 0
    for i in range(len(S)):
        if S[i] == '1':
            ret += 1
        else:
            return ret
    return ret


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['1214', '4']
        lines_export = ['2']
    if pattern == 2:
        lines_input = ['3', '157']
        lines_export = ['3']
    if pattern == 3:
        lines_input = ['299792458', '9460730472580800']
        lines_export = ['2']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()


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

#define MAX_N 100001
bool is_prime[MAX_N];
int nums[MAX_N];

void generate_prime() {
    for (int i=0; i<MAX_N; i++) is_prime[i] = true;
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i=2; i*i<=MAX_N; i++) {
        for (int j=i*2; j<MAX_N; j+=i) {
            is_prime[j] = false;
        }
    }
}

bool is_2017like_number(int n) {
    return is_prime[n] && is_prime[(n+1)/2];
}

int main() {
    generate_prime();

    for (int i=1; i<MAX_N; i++) {
        nums[i] = nums[i-1] + (is_2017like_number(i) ? 1 : 0);
    }

    int Q;
    cin >> Q;

    for (int i=0; i<Q; i++) {
        int l,r;
        cin >> l >> r;
        cout << nums[r] - nums[l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1152
#include"bits/stdc++.h"
using namespace std;

void Main() {
  string s;
  cin >> s;

  if (s.length() % 2 == 0 && s[0] == s[s.length() - 1]) cout << "First" << endl;
  else if (s.length() % 2 == 1 && s[0] != s[s.length() - 1]) cout << "First" << endl;
  else cout << "Second" << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}



Measured memory_bytes: 3756
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [10 ** 10] * n
ans = 10 ** 18
for i in range(n):
    for j in range(n):
        b[j] = min(b[j], a[(j - i) % n])
    ans = min(ans, sum(b) + x * i)
print(ans)


Measured memory_bytes: 3188
import java.util.Scanner;
 
class Main {
 
public static void main(String[] args) {
 
Scanner inp = new Scanner(System.in);
 
double r = inp.nextDouble();

System.out.printf("%.10f %.10f\n", Math.PI*Math.pow(r, 2), Math.PI*2*r );
 
}
}


Measured memory_bytes: 28292
#include <iostream>
using namespace std;
int main(){
  int n,q,idx=0,a,b;
  cin>>n>>q;
  while(q--){
    cin>>a>>b;
    if(a==1)idx=(idx+b)%n;
    else cout<<((idx+b-1)%n)+1<<endl;
  }
}


Measured memory_bytes: 3136
/*
 * Author:  vawait
 * Created Time:  2015/8/22 15:02:09
 * Problem: test.cpp
 */
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define red(i, a, b) for (int i = (a); i >= (b); --i)
#define clr( x , y ) memset(x,y,sizeof(x))
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define sqr(x) ((x) * (x))
typedef long long lint;
const int maxn = 101000;
const lint mod = 1e9 + 7;
lint fn[maxn] , f[maxn] , f2[maxn];
int l1 , l2 , m , a[maxn] , b[maxn] , c[maxn];
char sa[maxn] , sb[maxn] , sc[maxn];

void init()
{
    clr( a , 0 );
    clr( b , 0 );
    scanf("%s",sb+1);
    scanf("%s",sc+1);
    l1 = strlen( sa + 1 );
    rep(i,1,l1) a[i] = sa[l1+1-i] - '0';
    l2 = strlen( sb + 1 );
    rep(i,1,l2) b[i] = sb[l2+1-i] - '0';
    m = strlen( sc + 1 );
    rep(i,1,m) c[i] = sc[m+1-i] - '0';
    fn[0] = 1;
    rep(i,1,100000) fn[i] = fn[i-1] * 10 % mod;
    a[1] --;
    rep(i,1,l1) if ( a[i] < 0 ) a[i+1] -- , a[i] += 9;
}

int big(int *a,int n)
{
    red(i,m,1) {
        if ( a[n] > c[i] ) return 1;
        if ( a[n] < c[i] ) return -1;
        n --;
    }
    return 0;
}

lint calc(int *a,int n)
{
    if ( a[n] < 0 || a[n+1] < 0 ) return 0;
    
    int zero = ( m == 1 && !c[m] );
    lint ans = 0;
    while ( n > 1 && !a[n] ) n --;
    f2[0] = f[n+1] = 0;
    red(i,n,1) f[i] = ( f[i+1] * 10 + a[i] ) % mod;
    rep(i,1,n) f2[i] = ( a[i] * fn[i-1] + f2[i-1] ) % mod;
    
    red(i,n,m) {
        ( ans += f[i+1] * fn[i-m] ) %= mod;
        //printf("%d %lld\n",i,ans);
        if ( zero && i != n && i != 1 ) ans -= fn[i-m];
        if ( zero && i != 1 && i == n ) continue;
        int x = big( a , i );
        //printf("%d %lld\n",i,ans);
        if ( x == 0 ) ans += f2[i-m] + 1;
        if ( x == 1 ) ans += fn[i-m];
    }
    
    ans %= mod;
    ( ans += mod ) %= mod;
    return ans;
}

void work()
{
    int ans = calc( b , l2 ) - calc( a , l1 );
    ( ans += mod ) %= mod;
    printf("%d\n",ans);
}

int main()
{
    while ( scanf("%s",sa+1) != EOF ) {
        init();
        work();
    }
    return 0;
}

Measured memory_bytes: 2920
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String data = sc.next();
		int count = 0;
		char charX = 'x';

		for(char x: data.toCharArray()){
			if(x == charX){
				count++;
			}
		}

		if (count >= 8) {
			System.out.println("NO");
		} else {
			System.out.println("YES");
		}
	}


}


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

int main() 
{
    int a, b, c;
    cin >> a >> b >> c;
    vector<int> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    sort(v.begin(), v.end());
    cout << v[2]-v[0];
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vll2 = vector<vector<ll>>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vll a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(all(a));
    ll res = 0;
    for (int i = 0; i < n - k; i++) {
        res += a[i];
    }
    cout << res << endl;
}


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

using namespace std;

#define int long long
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define Endl '\n'
#define cont continue
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/__gcd(a,b)
#define pb push_back
#define mp make_pair
#define mem(x) memset(x, 0, sizeof(x))

const ll inf=1e18;
const int mod=1e9+7;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}
const int mxn = 1e5+10;

int Mod(int a) {
	if(a < 0)
		return (a+mod)%mod;
	else return a % mod;
}
int Mul(int a, int b) {
	return Mod(Mod(a) * Mod(b));
}
int Add(int a, int b) {
	return Mod(Mod(a) + Mod(b));
}
//ll fact[mxn];
//ll in_fact[mxn];
//fact[0] = 1;
//for(ll i = 1; i < mxn; i++) {
	//fact[i] = (i*fact[i-1])%mod;
//}
//in_fact[mxn-1] = bigmod(fact[mxn-1],mod-2);
//for(ll i = mxn-2; i >= 0; i--) {
	//in_fact[i] = (in_fact[i+1] * (i+1))%mod;
//}
//ll c(ll n,ll r) {
	//ll ans = (fact[n] * (in_fact[r] * in_fact[n-r]%mod))%mod;
	//return ans;
//}
vector<int>adj[mxn];
int vis[mxn];
void dfs(int n) {
	vis[n] = 1;
	for(int i:adj[n]) {
		if(!vis[i]) dfs(i);
	}
}

signed main(){
    fast;
	//freopen ("input.txt", "r", stdin);
	//freopen ("output.txt", "w", stdout);
    int tt = 1;
    //cin>>tt;
    for(int tc = 1; tc <= tt; tc++) {
        int n,m,ans = 0;
        cin>>n>>m;
        for(int i = 0; i< m; i++) {
			int u,v;
			cin>>u>>v;
			//--u,--v;
			adj[u].pb(v);
			adj[v].pb(u);
		}
		for(int i = 1; i <= n; i++) {
			if(!vis[i]) {
				//cout<<i<<' ';
				ans++;
				dfs(i);
			}
		}
		cout<<ans-1<<endl;
			
        
        
    }



return 0;
}


Measured memory_bytes: 11104
from sys import stdin

n, y = [int(x) for x in stdin.readline().rstrip().split()]


for i in range(n+1):
    for j in range(n-i+1):
        if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
            print(i, j, n - i - j)
            exit()

print("-1 -1 -1")

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

int main()
{
	int a, b;
	int sum = 0;
	
	cin >> a >> b;
	
	for ( a ; a <= b ; a++)
	{
		if ( (a % 10 == ((a) / 10000) )&& (((a) / 1000) % 10 == ((a) / 10) % 10) )
			sum ++;
	}
	cout << sum;
}

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

using namespace std;

int dap[100000];

int main()
{
    int i,j,k,n,x;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            for(k=1;k<=n;k++){
                x = i*i+j*j+k*k+i*j+i*k+j*k;
                if(x>n) break;
                dap[x]++;
            }
        }
    }

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


Measured memory_bytes: 3716
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};


  
int main(){
  int n;
  cin>>n;
  bool flag = false;
  int k;
  REPP(i,1000){
    if(n==i*(i-1)/2){
      flag = true;
      k = i;
      break;
    }
  }
  if(!flag){
    cout<<"No"<<endl;
    return 0;
  }
  
  vector<int> s[k];
  int target=1;
  REP(i,k){
    for(int j=i+1;j<k;j++){
      s[i].push_back(target);
      s[j].push_back(target);
      target++;
      if(target==n+1){
        flag = false;
        break;
      }
    }
    if(!flag){
      break;
    }
  }
  
  cout<<"Yes"<<endl;
  cout<<k<<endl;
  REP(i,k){
    cout<<k-1<<' ';
    REP(j,k-1){
      cout<<s[i][j]<<' ';
    }
    cout<<endl;
  }
  return 0;
}


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

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

  int p1; 
  int p2;
  int p3;
  int ans = 0;
  for(char i = '0'; i <= '9'; i++) {
    for(char j = '0'; j <= '9'; j++) {
      for(char k = '0'; k <= '9'; k++) {
      p1 = -1;
      p2 = -1;
      p3 = -1;
        for(int l = 0; l < N; l++) {
          if(S[l] == i && p1 == -1) p1 = l; 
          if(S[l] == j && p1 != -1 && p1 < l && p1 > p2) p2 = l;
          if(S[l] == k && p1 < p2 && p2 < l) p3 = l;      
        }
        if(p1 < p2 && p2 < p3 && p1 != -1) ans++;
      }
    }
  }

  cout << ans;
  
    return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  for (int i = 0; K + i < N; i++) {
    if (A.at(K + i) > A.at(i)) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 4048
#include <set>
#include <map>
#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>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x,y,z,count=0;
  cin>>x>>y>>z;
  while(true){
    if(x-(z+y+z)<0){
      cout<<count<<'\n';
      break;
    }
    count++;
    x-=(z+y);
  }
  return(0);
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    from scipy.sparse.csgraph import connected_components  # https://note.nkmk.me/python-scipy-connected-components/
    from scipy.sparse import csr_matrix
    
    N, M = map(int, input().split())  # 頂点数、辺数
    A, B, C = [0] * M, [0] * M, [1] * M  # A[i]からB[i]へコストC[i]の有向辺。
    # ただし、connected_components()では有向グラフも無向グラフとして扱われる
    for i in range(M):
        A[i], B[i] ,_= map(int, input().split())
        A[i] -= 1  # indexを調整
        B[i] -= 1
    
    csr = csr_matrix((C, (A, B)), shape=(N, N))
    # nは連結成分の個数。labelは各頂点が属する連結成分のラベル
    n, labels = connected_components(csr)
    print(n)

    
resolve()

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



struct Wall{
	int r, c;
	bool operator <(const Wall& b) const {
		return r + c < b.r + b.c;
	}
};

const ll mod = 1000000007;

ll mul (ll a, ll b) { return (a * b) % mod; }; 
ll pow (ll a, ll b) {
	if (b == 0) return 1;
	ll res = pow(a, b/2);
	res = mul(res, res);
	if (b & 1) res = mul(res, a);
	return res;
}
ll inv(ll a) { return pow(a, mod-2); };

ll sub(ll a, ll b) { return (a - b + mod) % mod; }

ll add(ll a, ll b) { return (a + b) % mod; }


ll fact[300005];
ll invfact[300005];

ll binom(ll n, ll k)
{
	return mul(mul(fact[n], invfact[k]), invfact[n-k]);
}


int main()
{	
	int w, h, n;
	cin >> h >> w >> n;
	
	fact[0] = 1;
	invfact[0] = inv(fact[0]);
	for (ll i = 1; i < (w + h + 5); i++)
	{
		fact[i] = mul(fact[i-1], i);
		invfact[i] = inv(fact[i]);
	}
		
	//cout << inv(5) << endl;
	//cout << binom(5, 5) << endl;
	//cout << pow(2, 5) << endl;
	
	vector <Wall> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].r >> a[i].c;
		a[i].r--; a[i].c--;
	}
	a.push_back({h-1, w-1});
	
	vector <ll> dp(n+1);
	sort(a.begin(), a.end());
	for (int i = 0; i <= n; i++)
	{
		dp[i] = binom(a[i].r + a[i].c, a[i].r); 
		for (int j = 0; j < i; j++)
		{
			if (a[j].r <= a[i].r && a[j].c <= a[i].c) 
				dp[i] = sub(dp[i], mul(dp[j], binom(a[i].r - a[j].r + a[i].c - a[j].c, a[i].r - a[j].r)));
		}
	}
	
	cout << dp[n];
	return 0;
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

ll a, b, c;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b >> c;
    if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0) cout << 0 << endl;
    else cout << min(min(a * b, a * c), b * c) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
const long long INF = 1001001001;
const long long MOD = 1000000007;
const double EPS = 1e-10;
struct Edge { int from, to; long long cost; };
using Graph = vector<vector<Edge>>;

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

    int n,k;
    while(cin>>n>>k&&!(n==0&&k==0)){
        ll c_sum[n+1]={};
        for(int i=0;i<n;i++){
            ll a;
            cin>>a;
            c_sum[i+1]=c_sum[i]+a;
        }
        ll ans=0;
        for(int i=k;i<=n;i++){
            ans=max(ans,c_sum[i]-c_sum[i-k]);
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 3880
# Kruskal's Algorithm

def kruskal():
    '''
    最小全域木のコストを求める
    '''
    cost = 0
    edge.sort()

    for c, u, v in edge:
        if same(u, v):
            continue
        union(u, v)
        cost += c

    return cost


def find(x):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    '''
    xとyの属する集合を併合する
    '''
    x = find(x)
    y = find(y)
    
    if x == y:
        return False

    if par[x] > par[y]:
        x, y = y, x

    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


################################
n, w = map(int, input().split())  # n:頂点数　w:辺の数

par = [-1] * n  # 根: -size, 葉: 親の頂点
edge = []       # edge[i]:iから出る辺の[重み,行先]の配列
for _ in range(w):
    x, y, z = map(int, input().split())
    edge.append([z, x, y])

print(kruskal())


Measured memory_bytes: 24844
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

ll mod = 1e9 + 7;

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, k; cin >> n >> k;

    ll a[n + 1] = {};
    rep(i, n + 1){
        a[i] = i;
    }

    ll sumf = k*(k - 1)/2;
    ll sumb = n*(n + 1)/2 - (n - k)*(n - k + 1)/2;

    ll ans = sumb - sumf + 1;;

    reps(i, k, n + 1){
        sumf += i;
        sumb += n - i;

        ans = (ans + sumb - sumf + 1) % mod;
    } 

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5100
n, m = map(int, input().split())
c = list(map(int, input().split()))
INF = float('inf')
dp =[0] + [INF for _ in range(n)]

#print(c)

for i in range(m):
    for j in range(n+1):
        if j - c[i] >= 0:
            dp[j] = min(dp[j], dp[j-c[i]] + 1)
        pass
    #print(dp, c[i])
print(dp[n])



Measured memory_bytes: 7648
#include<stdio.h>

int main(){
  int r,c;
  int i,j;
  scanf("%d %d",&r,&c);

  int sheet[r+1][c+1];

  for(i=0; i<=r; i++){
    for(j=0; j<=c; j++){
      sheet[i][j]=0;
    }
  }
  
  for(i=0; i<r; i++){
    for(j=0; j<c; j++){
	scanf("%d",&sheet[i][j]);
    }
  } 
  
  for(i=0; i<r; i++){
    for(j=0; j<c; j++){
      sheet[i][c]+=sheet[i][j];
      sheet[r][j]+=sheet[i][j];
    }
    if(i==r-1){
      for(j=0; j<c; j++){
	sheet[r][c]+=sheet[r][j];
      }
    }
  }

  for(i=0; i<r+1; i++){
    for(j=0; j<c+1; j++){
      if(j!=c)
	printf("%d ",sheet[i][j]);
      else
	printf("%d",sheet[i][j]);
    }
    puts("");
  }
  
  return 0;
}



Measured memory_bytes: 2132
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

const ll MOD = 1e9+7;


signed main(){
    ll h,w;
    cin >> h >> w;
    char c[h][w] = {};
    ll cnt = 0;
    rep(i,0,h){
        rep(j,0,w){
            cin >> c[i][j];
            if(c[i][j] == '#') cnt++;
        }
    }

    if(cnt == h+w-1) cout << "Possible" << endl;
    else cout << "Impossible" << endl;

    return 0;
}


Measured memory_bytes: 3592
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    if(str[0].equals("H"))
      if(str[1].equals("H"))
        System.out.println("H");
      else
        System.out.println("D");
    else
      if(str[1].equals("H"))
        System.out.println("D");
      else
        System.out.println("H");
  }
}

Measured memory_bytes: 32632
#include<bits/stdc++.h>
using namespace std ;
 
#define int long long
 
#define IOS ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
 
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vp vector<pii>
#define vs vector<string>
#define all(v) v.begin(),v.end()
 
#define lb  lower_bound
#define ub  upper_bound
#define bs  binary_search
#define ff  first
#define ss  second
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
 
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
     
#define pi 3.14159265358979323846//20 decimals
#define MOD 1000000007

int32_t main(){
 
   
     IOS
    //  #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    int n,k;
    cin>>n>>k;
    vi h(n);
    for(int& x : h) {
       cin>>x;
    }
   vi dp(n,INT_MAX);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j =i+1;j<=i+k;++j) {
            if(j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    
    cout<< dp[n-1];
return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

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

const int64_t MOD = 1e9 + 7;

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

    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }

    vector<int> cnt(3, 0);
    int64_t result = 1;
    rep(i, n)
    {
        int k = upper_bound(cnt.begin(), cnt.end(), a[i]) - lower_bound(cnt.begin(), cnt.end(), a[i]);
        if (k == 0) {
            cout << 0 << endl;
            return 0;
        }
        result *= k;
        result %= MOD;

        *(upper_bound(cnt.begin(), cnt.end(), a[i]) - 1) += 1;
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;


public class Main {
    private static int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();

        if (s.equals("AAA") || s.equals("BBB")) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}


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

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

  struct Job {
    int a, b;
    bool operator<( const Job& right ) const {
      return b < right.b;
    }
  };

  vector<Job> jobs(n);
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    jobs[i] = (Job){a,b};
  }

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

  ll now = 0;
  rep(i, n) {
    now += jobs[i].a;
    if(now > jobs[i].b) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))

typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;
vector<ll> A(10);

int main() {
	ll N;
	cin>>N;
	rep(i,5)cin>>A[i];
	ll ans = 5;
	ll mina = A[0];
	rep(i,5)mina = min(mina,A[i]);
	if(mina == 1)ans+=N-1;
	else ans+= N/mina;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cassert>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<valarray>

using namespace std;

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

int calc(string s) {
  return s[0] * 600 + s[1] * 60 + s[3] * 10 + s[4];
}

int calc(string a, string b) {
  return calc(b) - calc(a);
}

bool solve() {
  int n;
  cin >> n;
  if (n == 0) return false;
  int sum[1000];
  string in[1000];
  rep (i, 1000) sum[i] = 0;
  bool exist = false;
  set<int> now;
  rep (i, n) {
    string a, b, c;
    int d;
    cin >> a >> b >> c >> d;
    if (d == 0) {
      exist = !exist;
      if (c == "I") {
	rep (i, 1000) in[i] = b;
      } else {
	for (set<int>::iterator itr = now.begin(); itr != now.end(); ++itr) {
	  sum[*itr] += calc(in[*itr], b);
	}
      }
    } else {
      if (exist) {
	if (c == "I") {
	  now.insert(d);
	  in[d] = b;
	} else {
	  now.erase(d);
	  sum[d] += calc(in[d], b);
	}
      } else {
	if (c == "I") {
	  now.insert(d);
	} else {
	  now.erase(d);
	}
      }
    }
  }
  int res = 0;
  rep (i, 1000) res = max(res, sum[i]);
  cout << res << endl;
  return true;
}

int main() {
  while (solve());
  return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
#define dum(x) cout<<#x<<'='<<x<<endl
#define ll long long
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  cout << v[n - 1] - v[0] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

string s;

int n, ans;

map <char, int> mp;

main ()
{
//    freopen("contest.in", "r", stdin);
//    freopen("contest.out", "w", stdout);
    cin >> s;
    n = s.size();
    s = ' ' + s;
    for (int i = 1; i <= n; i++)
    {
        mp[ s[i] ]++;
    }
    for (int i = 'a';  i <= 'z'; i++)
    {
        ans += mp[i] * (mp[i] - 1) >> 1;
    }
    cout << n * (n - 1) / 2 - ans + 1   ;
}


Measured memory_bytes: 772
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if (a*500) + (b*100) + (c*50) == X:
                count += 1
print(count)


Measured memory_bytes: 3060
//https://beta.atcoder.jp/contests/agc029/tasks/agc029_c
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

int N;
int a[212345];
inline bool solve(const int d){
    vector<pair<int,int>> ret;
    ret.push_back({a[0],1});
    int len = a[0];
    for(int i:range(1,N)){
        if(len<a[i]){
            ret.push_back({a[i]-len,1});
            len=a[i];
        }
        else{
            while(len-ret.back().first>=a[i]){
                len-=ret.back().first;
                ret.pop_back();
            }
            ret.back().first-=len-a[i];
            len=a[i];
            while(ret.size()>1&&ret[ret.size()-1].second==ret[ret.size()-2].second){
                ret[ret.size()-2].first+=ret[ret.size()-1].first;
                ret.pop_back();
            }
            if(ret.size()==1&&ret.back().second==d)return false;
            if(ret.back().second==d){
                auto p = ret.back();
                p.second=1;
                ret.pop_back();
                int k = ret.back().second;
                ret.back().first--;
                if(ret.back().first==0)ret.pop_back();
                ret.push_back({1,k+1});
                ret.push_back(p);
            }
            else{
                int k = ret.back().second;
                ret.back().first--;
                if(ret.back().first==0)ret.pop_back();
                ret.push_back({1,k+1});
            }
        }
    }
    /*
    cout<<d<<" ";
    for(auto &it:ret){
        cout<<"("<<it.first;
        cout<<","<<it.second;
        cout<<")"<<" ";
    }
    cout<<endl;*/
    return true;
}
int main(){
    cin>>N;
    for(int i:range(N))cin>>a[i];
    int lb = 0;
    int ub = N;
    while(ub-lb>1){
        const int mid = (lb+ub)/2;
        if(solve(mid)){
            ub=mid;
        }
        else{
            lb=mid;
        }
    }
    cout<<ub<<endl;
    return 0;
}

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

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

typedef long long ll;
typedef pair<int,int> p;

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

int n, m;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    vector<ll> x(n);
    vector<ll> y(m);
    
    REP(i,n) cin >> x[i];
    REP(i,m) cin >> y[i];
    
    sort(all(x));
    sort(all(y));
    
    ll sumX = 0;
    ll sumY = 0;
    REP(i, n) {
        ll tmp = - (i * x[i] % INF) + ( (n - (i+1)) * x[i] % INF);
        while(tmp < 0) {
            tmp += INF;
        }
        sumX += tmp % INF;
        sumX %= INF;
    }
    REP(i, m){
        ll tmp = - (i * y[i] % INF) + ( (m - (i+1)) * y[i] % INF);
        while(tmp < 0) {
            tmp += INF;
        }
        sumY += tmp % INF;
        sumY %= INF;
    }
    
    cout << sumX * sumY % INF << endl;
    
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

class Main {

    static int[] makePrimes( final int lim ) {
	
	BitSet isPrime = new BitSet( lim + 1 );
	isPrime.set( 0, lim + 1, true );
	isPrime.set( 0, 2, false );
	final int limIndex = ( int )sqrt( lim );
	for ( int index = 2; index <= limIndex; index++ ) {
	    if ( isPrime.get( index ) ) {
	   	for ( int i = index * index; i <= lim; i += index ) {
		    isPrime.set( i, false );
		}
	    }
	}
	final int count = isPrime.cardinality();
	int[] ans = new int[count];
	int index = 0;
	for ( int i = 0; i <= lim; i++ ) {
	    if ( isPrime.get( i ) ) {
		ans[index++] = i;
	    }
	}
	return ans;
    }
    
    public static void main( final String[] args ) {

	final Scanner stdin = new Scanner( System.in );

	final int[] primeList = makePrimes( 1 << 15 );
	
	while ( true ) {

	    final int n = stdin.nextInt();
	    if ( n == 0 ) {
		break;
	    }

	    System.out.println( solve( n, primeList ) );
	    
	}
    }

    static int solve( final int n, final int[] primeList ) {

	int count = 0;
	
	int index = 0;
	while ( index < primeList.length && primeList[ index ] <= n - primeList[ index ] ) {
	    if ( Arrays.binarySearch( primeList, n - primeList[ index ] ) >= 0 ) {
		count++;
	    }
	    index++;
	}
	return count;
    }
}

Measured memory_bytes: 19872
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <memory>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i]
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion




int32_t main() {
    make(int, a, b, n);
    cout << a * min(b - 1, n) / b;
    return 0;
}

Measured memory_bytes: 3608
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

while True:
    W, H = map(int, input().split())
    if W == 0 and H == 0:
        break
    W = W + 2
    H = H + 2
    A = [0] * H
    for i in range(H):
        if i == 0 or i == H - 1:
            A[i] = ['#'] * W
        else:
            A[i] = ['#'] + list(map(int, input().split())) + ['#']
    checked = [[False] * W for _ in range(H)]

    def dfs(s):
        dirs = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]
        x, y = s
        if checked[x][y]:
            return False
        if A[x][y] == 0:
            return False

        checked[x][y] = True
        for d in dirs:
            dx, dy = d
            if A[x + dx][y + dy] == '#':
                continue
            if checked[x + dx][y + dy]:
                continue
            if A[x + dx][y + dy] == 1:
                dfs((x + dx, y + dy))
        return True

    ans = 0
    for i in range(1, H - 1):
        for j in range(1, W - 1):
            if dfs((i, j)):
                ans += 1
    print(ans)



Measured memory_bytes: 8816
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define sortrev(x)       sort(all(x), greater<int>())
#define debug(x)         cout << '>' << #x << ':' << x << endl;
#define int              long long
#define ld               long double
#define endl 			 "\n";
#define mp 				 make_pair
#define pii 			 <int, int>
#define lb 				 lower_bound
#define ub				 upper_bound
#define len(a)           int((a).size())
#define prec(n)          fixed<<setprecision(n)
#define cnt(n)           __builtin_popcountll(n)
#define pi               pair<int, int>
const int mod = 1000000007;
using namespace std;
// const int N = 1e5 + 5; 
// int n;
// int a[N];



int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = 1;
// cin >>t;
while(t--){

int n,m;cin>>n>>m;
int h[n];
for (int i = 0; i < n; ++i)
{
	cin>>h[i];
}
set<int>bad;
for (int i = 0; i < m; ++i)
{	int a;int b;
	cin >>a >>b;
	a--;
	b--;
	if(h[a] > h[b]){
		bad.insert(b);
	}
	else if(h[a] == h[b]){
		bad.insert(a);
		bad.insert(b);
	}
	else if(h[a]<h[b]){
		bad.insert(a);
	}
}


cout << n - bad.size() <<endl;







}
return 0;
}

Measured memory_bytes: 6992
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Program {

    static void Main(string[] args) {
        var inp = Console.ReadLine().Split();
        var n = int.Parse(inp[0]);
        var k = int.Parse(inp[1]);
        var h = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var dp = new long[100010];
        for (var i = 0; i < 100010; i++) {
            dp[i] = long.MaxValue;
        }
        dp[0] = 0;
        for (var i = 0; i < n; i++) {
            for (var j = 1; j <= k; j++) {
                if (i + j >= n) continue;
                dp[i + j] = Math.Min(dp[i + j], dp[i] + Math.Abs(h[i] - h[i + j]));
            }
        }
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Console.WriteLine(dp[n - 1]);
        Console.Out.Flush();
    }
}

Measured memory_bytes: 22112
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int PT[10] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 2};
int QT[10] = {1, 1, 1, 2, 2, 3, 2, 2, 3, 3};
int RT[10] = {2, 3, 4, 3, 4, 4, 3, 4, 4, 4};

int main()
{
    ll int N;
    string name;
    cin >> N;
    ll int M = 0, A = 0, R = 0, C = 0, H = 0;
    REP(i,N)
    {
        cin >> name;
        if(name[0] == 'M') ++M;
        if(name[0] == 'A') ++A;
        if(name[0] == 'R') ++R;
        if(name[0] == 'C') ++C;
        if(name[0] == 'H') ++H;
    }
    ll int temp[5];
    temp[0] = M;
    temp[1] = A;
    temp[2] = R;
    temp[3] = C;
    temp[4] = H;

    ll int ans = 0;
    REP(i,10) ans += temp[PT[i]] * temp[QT[i]] * temp[RT[i]];

    cout << ans << endl;

}

Measured memory_bytes: 256
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
for i in range(M):
    x, y, c = map(int, input().split())
    price = a[x-1] + b[y-1] - c
    if ans > price:
        ans = price
print(ans)


Measured memory_bytes: 18736