akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    VI h(n);
    rep(i, n)
    {
        cin >> h[i];
    }
    reverse(ALL(h));
    rep(i, 1, n)
    {
        if (h[i - 1] < h[i])
        {
            h[i]--;
        }
        if (h[i - 1] < h[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;


int main(){
	fast;
	ll n; cin >> n;
	ll a[n], ans = 0;
	for(int i = 0; i < n; ++i) cin >> a[i];
	for(int i = 0; i < n; ++i){
		for(int j = i + 1; j < n; ++j){
			for(int k = j + 1; k < n; ++k){
				if((a[i] + a[j]) > a[k] && a[k] + a[i] > a[j] && a[j] + a[k] > a[i] && a[i] != a[j] && a[i] != a[k] && a[j] != a[k]) ++ans;
			}
		}
	}
	cout << ans;
	return 0;
}


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

int main(void){
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    vector<int> cnt(2019);
    int x = 1, tot = 0;
    ll ans = 0;
    rep(i, s.size()){
        cnt[tot]++;
        tot = (tot + (s[i] - '0') * x) % 2019;
        ans += cnt[tot];
        x = x * 10 % 2019;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3704
#include<iostream>
using namespace std;
int main(){
  int a,b;
 while(cin>>a>>b){
   if(a==0&&b==0){
     break;
   }
   else{
    if(a<b){
      cout<<a<<" "<<b<<endl;
    }
     else{
       cout<<b<<" "<<a<<endl;
     }
   }
   
 }
  
  return 0;
}


Measured memory_bytes: 3004
def main():
    n = int(input())
    flg = 0
    val=0
    ans=0
    ns = str(n)
    nl = len(ns)
    tmp = [[0]*10 for i in range(11)]
    for i in range(1,n+1):
        s = str(i)
        top = int(s[0])
        btm = int(s[-1])
        tmp[top][btm] += 1

    for i,a in enumerate(tmp):
        for j,b in enumerate(a):
            if b != 0:
                ans += b*tmp[j][i]
    print(ans)





if __name__=='__main__':
    main()


Measured memory_bytes: 40940
//#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;

#define boost ios::sync_with_stdio(0); cin.tie(0)

#define fi first
#define se second

typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;

const int N = 1e6 + 5;

/***************************************************************************/

int P[N];
int par[N];

int Find(int i) {
	if(par[i] != i) par[i] = Find(par[i]);
	return par[i];
}

void Union(int a, int b) {
	a = Find(a), b = Find(b);
	if(a == b) return;
	par[a] = b;
}

int main() {

	boost;

	int n, m; cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>P[i];
		par[i] = i;
	}

	for(int i=1; i<=m; i++) {
		int x, y; cin>>x>>y;
		Union(x, y);
	}

	int ans = 0;
	for(int i=1; i<=n; i++) {
		if(Find(i) == Find(P[i])) ans++; 
	}

	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 4736
# coding: utf-8
# Your code here!
a = int(input())
b = int(input())
c = int(input())
money = int(input())
count = 0

for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            total = i * 500 + j * 100 + k * 50
            if total == money:
                count += 1
                
            
                
print(count)
    

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

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

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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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


	vector<int> vec(5);
	for (int i = 0; i < vec.size(); i++) {
		cin >> vec[i];
	}

	sort(begin(vec), end(vec));

	int ans = INT_MAX;
	do {
		int score = 0;
		for (int i = 0; i < 5; i++) {
			while (score % 10 != 0) {
				score++;
			}
			score += vec[i];
		}

		ans = min(ans, score);
	} while (std::next_permutation(vec.begin(), vec.end()));

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b){
    if(a<b) return b;
    return a;
}

int gcd(int a, int b) {
  if(a < b) return gcd(b, a);
  int r;
  if(b == 0)return a;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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

    int ans = 0;
    for(int i = 0; i < N ; i++){
        ans = max(ans,gcd(L[i],R[i+1]));
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[5],ans=1<<30;
int jg()
{
	register int num=0;
	num+=a[0];
	for(;num%10;++num);
	num+=a[1];
	for(;num%10;++num);
	num+=a[2];
	for(;num%10;++num);
	num+=a[3];
	for(;num%10;++num);
	num+=a[4];
	return num;
}
main()
{
	scanf("%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4]);
	sort(a,a+5);
	do{ans=min(ans,jg());}
	while(next_permutation(a,a+5));
	printf("%d",ans);
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
 
int main(void)
{
  int a, b, c;
  
  cin >> a >> b >> c;
  
  if((a + b + c == 17) && ((a == 5 && b == 5) || (a==5 && c == 5) || (b==5 && c==5)))
  {
    cout << "YES" << endl;
  }
  else
  {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int N, D, X;
int dp[16][100005];
int p[16][16];

int main()
{
  cin >> N >> D >> X;
  rep(i, D) rep(j, N) cin >> p[i][j];

  for(int d=0;d<D-1;d++){
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<N;i++){
      for(int j=0;j<=X;j++){
	if(j < p[d][i])
	  dp[i+1][j] = dp[i][j];
	else
	  dp[i+1][j] = max(dp[i][j], dp[i+1][j-p[d][i]] + p[d+1][i]);
      }
    }

    //    rep(i, N) rep(j, X+1) cout << dp[i+1][j] << " "; cout  << endl;
    int x = 0;
    rep(i, X+1) x = max(x, dp[N][i] + (X-i));
    X = x;
    //    cout << X << endl;    
  }
  cout << X << endl;
  return 0;
}

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

using namespace std;

int main(){
	int n;
	cin >> n;
	int p[n];
	int max_p = 0;
	int max_p2 = 0;
	int sum = 0;
	for(int i=0; i<n; i++) cin >> p[i];

	for(int i=0; i<n; i++){
		if(max_p < p[i]){
			max_p = p[i];
			max_p2 = i;
		}
	}
	for(int i=0; i<n; i++){
		if(i == max_p2) sum += p[i]/2;
		else sum += p[i];
	}
	cout << sum << endl;
}

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

#define ll long long int
#define pb push_back
#define f(i,x,y) for(i=x;i<y;i++)
#define vll vector<ll>
#define fast    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

void solve()
{
    string s;
    cin>>s;
    ll n=s.length();
    if(s[n-1]!='s')
        s+='s';
    else
    {
        s+='e';
        s+='s';
    }
    cout<<s<<endl;
}

int main()
{
    fast;
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 3664
#include<stdio.h>
int main(void) {
	int a, b, k;
	int jo;
	int cnt = 0;

	scanf("%d %d %d", &a, &b, &k);
	
	jo = 100;
	while (jo > 0) {
		if (a % jo == 0 && b % jo == 0) {
			
			cnt++;
		}
		if (cnt == k) {
			break;
		}
		jo--;
	}
	printf("%d\n", jo);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 44;
int n;char S[N][N];ll dp[N][N][N],res;bool ok[N][N];
int main() {
	read(n);n*=2;rep(i,1,n)scanf("%s",S[i]+1);
	rep(i,1,n)rep(j,1,n)ok[i][j]=S[i][j]=='1';
	if(n==2){
		printf("%d\n",ok[1][2]);
		return 0;
	}
	rep(i,1,n)dp[i][i][i]=1;
	per(l,n,1)rep(r,l,n)rep(mid,l+1,r-1)if(!(r-l&1)){
		/*rep(x,l+1,mid-1)rep(y,mid+1,r-1)rep(p1,x+1,mid-1)if(!(p1-l&1))rep(p2,mid+1,y-1)
			dp[l][r][mid]+=dp[l][p1][x]*dp[p2][r][y]*dp[p1+1][p2-1][mid];
		rep(x,l+1,mid-1)rep(p,x+1,mid-1)dp[l][r][mid]+=dp[l][p][x]*dp[p+1][r][mid];
		rep(y,mid+1,r-1)rep(p,mid+1,y-1)dp[l][r][mid]+=dp[l][p][mid]*dp[p+1][r][y];
		dp[l][r][mid]+=dp[l+1][r-1][mid];*/
		rep(x,l,mid-1)rep(y,mid+1,r)if(ok[x][y])rep(p1,x,mid-1)if(!(p1-l&1))rep(p2,mid+1,y)
			dp[l][r][mid]+=dp[l][p1][x]*dp[p2][r][y]*dp[p1+1][p2-1][mid];
	}
	rep(i,2,n)rep(j,2,i-1)rep(k,i+1,n)if(ok[1][i]&&ok[j][k])
		rep(x,j,i-1)rep(y,i+1,k)res+=dp[2][x][j]*dp[x+1][y-1][i]*dp[y][n][k];
	cout<<res;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <math.h>
using namespace std;

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

typedef long long ll;


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

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

  ll a[n] = { 0 };
  rep(i, n) {
      cin >> a[i];
  }
  
  ll max_diff = 0;
  rep(i, n) {
    for (int j = i + 1; j < n; j++)
    {
        /* code */
        max_diff = max(max_diff, abs(a[i] - a[j]));
    }
  }
  cout << max_diff << endl;
  return 0;
}

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

int main(){
  int N, M, X;
  cin >> N >> M >> X;

  vector<int> A(M);

  for (int i = 0; i < M; i++)
  {
    cin >> A.at(i);
  }
  

  int left = 0;
  int right = 0;

  for (int i = 0; i < M; i++)
  {
    if (A.at(i) < X)
    {
      left += 1;
    }
    else
    {
      right += 1;
    }
    
    
  }
  
  
  cout << min(left, right) << endl;
}

Measured memory_bytes: 3600
#ACB138 C1

N=int(input())

V=list(map(int,input().split()))


def merge(mylist):
	mylist=sorted(mylist)
	curval=0
	if len(mylist)<=1:
		return mylist[0]

	curval = mylist[0]+mylist[1]
	mylist.pop(1)
	mylist.pop(0)
	mylist.append(curval/2)
	return merge(mylist)

print(merge(V))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long N;
    cin >> N;
    char C[N];
    for (int i = 0; i < N; i++)
    {
        cin >> C[i];
    }
    long left_w[N], right_r[N];
    left_w[0] = 0;
    right_r[N - 1] = 0;
    for (int i = 1; i < N; i++)
    {
        left_w[i] = left_w[i - 1] + (C[i - 1] == 'W' ? 1 : 0);
    }
    for (int i = N - 2; i >= 0; i--)
    {
        right_r[i] = right_r[i + 1] + (C[i + 1] == 'R' ? 1 : 0);
    }
    long ans = LONG_MAX;
    for (int i = 0; i < N; i++)
    {
        ans = min(ans, max(left_w[i], right_r[i]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 6940
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

int n, m, h[100001];
vector<int> adj[100001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> h[i];
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		adj[a].push_back(h[b]);
		adj[b].push_back(h[a]);
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		bool val = true;
		for(auto &j : adj[i])
			if(h[i] <= j) val = false;
		cnt += val;
	}
	cout << cnt << "\n";
	return 0;
}

Measured memory_bytes: 9184
#include<bits/stdc++.h>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define endl  "\n"
#define ll long long
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cin.exceptions(cin.failbit);cout.tie(NULL);
using namespace std;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6)
    {
        if ((n % i == 0) || (n % (i + 2) == 0))
            return false;
    }
    return true;
}

int32_t main()
{
	string s,t;
	cin >> s >> t;
	int cnt=0;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]!=t[i])
		cnt++;
	}
	cout << cnt;
}



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

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}

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


int main() {
    int N, K;
    std::cin >> N >> K;

    COMinit();
    for (int i = 1; i <= K; i++) {
        std::cout << COM(N - K + 1, i) * COM(K - 1, i - 1) % MOD << std::endl;
    }
}


Measured memory_bytes: 15472
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, c[33], d[33]; string s;
int main() {
	cin >> n;
	fill(c, c + 26, 999999999);
	for (int i = 0; i < n; i++) {
		cin >> s;
		fill(d, d + 26, 0);
		for (int j = 0; j < s.size(); j++) d[s[j] - 97]++;
		for (int j = 0; j < 26; j++) c[j] = min(c[j], d[j]);
	}
	for (int j = 0; j < 26; j++) {
		for (int k = 0; k < c[j]; k++) cout << (char)(j + 97);
	}
	cout << endl;
	return 0;
}

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

using namespace std;

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

	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; ++i) {
		int x;
		cin >> x;
		n -= x;
	}

	if(n < 0) {
		cout << -1 << '\n';
	} else {
		cout << n << '\n';
	}

	return 0;
}


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

#define INF 2000000005

int hsize;
int A[500005];

void modheap(int i){
  int l=i*2+1;
  int r=i*2+2;
  int larger = i;
  if (l<hsize&&A[larger]<A[l])larger=l;
  if (r<hsize&&A[larger]<A[r])larger=r;
  if (larger!=i){
    swap(A[larger],A[i]);
    modheap(larger);
  }
}

void buildheap(){
  for (int i=hsize/2-1;i>=0;i--)
    modheap(i);
}

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

  buildheap();
  
  for (int i=0;i<hsize;i++) cout <<" "<<A[i];
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 5048
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define F first
#define S second

const ll P = 1000000007;
const int N = (1<<18);

using namespace std;

int n;
ll f[N+1], h[N], a[N];

void add(int i, ll o){for(; i<=N; i+=i&-i) f[i] = max(f[i], o);}

ll msum(int i){
	ll s = 0;
	for(; i>0; i-=i&-i) s = max(f[i], s);
	return s;
}

int main(){

	cin >> n;
	for(int i=0; i<n; i++) cin >> h[i];
	for(int i=0; i<n; i++) cin >> a[i];

	ll ans = 0;

	for(int i=0; i<n; i++){
		ll s = msum(h[i]-1);
		ans = max(ans, s+a[i]);
		add(h[i], s+a[i]);
	}

	cout << ans << endl;

	return 0;
}


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

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int partition(vector<int>&a,int l,int r) {
	int pivot = a[r];
	int i(l - 1);
	rep(j, l, r)if (a[j] <= pivot)swap(a[++i], a[j]);
	swap(a[++i], a[r]);
	return i;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> a(N); rep(i, 0, N) { cin >> a[i]; }
	int x = partition(a, 0, N - 1);
	rep(i, 0, N) {
		if (i == x)cout << "[" << a[i] << "]" << (i == N - 1 ? '\n' : ' ');
		else cout << a[i] << (i == N - 1 ? '\n' : ' ');
	}
	return 0;
}

Measured memory_bytes: 3156
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

// 累積xorは i 1 (i+2)+1 0 の周期となる
lint culXOR(lint x) { return ((x + 1) % 2) * x + ((x + 1) % 4) / 2;}

int main() {

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

	lint A, B;
	cin >> A >> B;
	cout << (culXOR(A-1) ^ culXOR(B));

	return 0;
}

Measured memory_bytes: 256
####################################### Define
mod = int(1e9 + 7)
maxN = int(2e5 + 100)
pow = [1] * maxN
cost = []

####################################### Functions
def add(x, y) : return (x + y) % mod
def mul(x, y) : return x % mod * (y % mod) % mod
def prepare() :
    for i in range(1, maxN):
        pow[i] = mul(pow[i - 1], 2)
####################################### Main
prepare()
n = int(input())
inp = input().split()
for i in range(0, n) :
    cost.append( int(inp[i]))
cost.sort()

ans = 0
for i in range(1, n + 1) :
    cur = mul(pow[i - 1], mul(int(cost[i - 1]), pow[n - i]))
    if i < n : cur = add(cur, pow[i - 1] * pow[n - i - 1] % mod * int(cost[i - 1])
                          % mod * (n - i) % mod)
    ans = add(ans, cur)
print(mul(ans, pow[n]))
''' test
6
623 77 177 26 865 192
'''


Measured memory_bytes: 34156
# 点数計算
def scoring(last_, c, s, t, d, score):
    score = s[d][t]
    for i in range(len(c)):
        score -= c[i] * (d + 1 - last_[i])
    return score

# input
score = 0
D = int(input())
c = [int(i) for i in input().split()]
s = []
for i in range(D):
    s.append([int(i) for i in input().split()])
last = [[0 for i in range(len(c))] for j in range(D+1)] # last[d][i]

ans = []
for d in range(D):
    last_dummy = last[d][:]
    score = -float("inf")
    t_d = 0
    for t in range(len(c)):
        last_dummy2 = last_dummy[:]
        last_dummy2[t] = d+1
        if score < scoring(last_dummy2, c, s, t, d, score):
            score = scoring(last_dummy2, c, s, t, d, score)
            t_d = t
    ans.append(t_d)
    last[d][t_d] = d+1


    # last更新
    for i in range(len(c)):
        last[d+1][i] = last[d][i]


[print(ans[i]+1) for i in range(D)]





Measured memory_bytes: 9676
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    a, b, n = MII()
    f = lambda x: divf(a*x,b) - a*divf(x,b)
    print(f(min(b-1, n)))
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9440
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int main()
{
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        ll c = n / i;
        ll now = (c * (c + 1)) / 2;
        ans += (now * i);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3580
/* 実装例　Atcoder Beginers Contest 174-F Range Set query */
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n,q;
    cin >> n >> q;
    int sq=2*sqrt(n);
    vector<int> c(n);
    rep(i,n){
        cin >> c[i];
        c[i]--;
    }
    vector<int> l(q),r(q);
    rep(i,q){
        cin >> l[i] >> r[i];
        l[i]--;
    }
    
    vector<int> qu(q);
    rep(i,q) qu[i]=i;
    sort(ALL(qu),[&](int i,int j){if(l[i]/sq!=l[j]/sq) return l[i]<l[j]; else return r[i]<r[j];});
    
    vector<int> ans(q);
    vector<int> cnt(n,0);
    int nl=0,nr=0;
    int res=0;
    for(int i:qu){
        while(nl>l[i]){
            nl--;
            if(cnt[c[nl]]++==0) res++;
        }
        while(nl< l[i]){
            if(--cnt[c[nl]]==0) res--;
            nl++;
        }
        while(nr< r[i]){
            if(cnt[c[nr]]++==0) res++;
            nr++;
        }
        while(nr> r[i]){
            nr--;
            if(--cnt[c[nr]]==0) res--;
        }
        /* ここから結果 */
        ans[i]=res;
    }
    rep(i,q) cout << ans[i] << "\n";
}


Measured memory_bytes: 15480
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <cassert>

using namespace std;

/*
  問題文

  いろはちゃんはこだわりもので、嫌いな数字が K個あり、それぞれ D1, D2,
  ..., DK です。

  いろはちゃんはお店でお買い物をしていて、N円の品物を買おうとしていま
  す。 もちろん、この品物は N円以上のお金を支払えば買うことができます。
  しかし、先ほど述べたようにいろはちゃんは強いこだわりがあるので、自分
  がお店に支払う金額の 10進表記にいろはちゃんの嫌いな数字が出現しない
  ような最も少ない金額を支払おうとします。

  いろはちゃんが支払う金額を求めてください。
*/

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

    int k;
    cin >> k;

    string d;
    for (int i = 0; i < k; i++) {
        char c;
        cin >> c;
        d += c;
    }

    for (int i = n; ; i++) {
        string s = to_string(i);
        bool accept = true;
        for (int j = 0; j < d.size(); j++) {
            if (s.find(d[j]) != string::npos) {
                accept = false;
                break;
            }
        }
        if (accept) {
            cout << i << endl;
            break;
        }
    }

    return 0;
}

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

int main(){
  long long N, P;
  string s;
  cin >> N >> P >> s;
  reverse(s.begin(), s.end());
  if(10%P == 0){
    long long ans = 0;
    for(int i = 0; i < N; ++i){
      int c = s[i] - '0';
      if(c%P) continue;
      ans += N-i;
    }
    cout << ans << endl;
    return 0;
  }

  vector<long long> T(N);
  long long t = 1;
  for(int i = 0; i < N; ++i){
    T[i] = (t*(s[i]-'0'))%P;
    t *= 10;
    t %= P;
  }
  vector<long long> C(P);
  long long ans = 0;
  long long p = 0;
  ++C[0];
  for(auto e : T){
    p += e;
    p %= P;
    ans += C[p];
    ++C[p];
  }
  cout << ans << endl;
}


Measured memory_bytes: 2180
#include <stdio.h>
#include <string.h>

#define MAX_N (2000010)

int k;
int S[MAX_N];
int num;

void swap( int i, int j ) {
    int tmp = S[i];
    S[i] = S[j];
    S[j] = tmp;
}

void insert( int v ) {
    int cur, parent;
    num++;
    S[num] = v;

    cur = num;
    parent = ( cur >> 1 );

    while ( parent > 0 ) {
	if ( S[parent] < S[cur] ) {
	    swap( parent, cur );
	    cur = parent;
	    parent = (cur >> 1);
	}
	else break;
    }
}

void maxHeapify( int i )
{
    int l = (i<<1);
    int r = (l + 1);
    int max_i = i;
    int max_v = S[i];
    if ( l <= num && max_v < S[l] ) {
	max_i = l;
	max_v = S[l];
    }
    if ( r <= num && max_v < S[r] ) {
	max_i = r;
	max_v = S[r];
    }
    
    if ( max_i != i ) {
	swap( i, max_i );
	maxHeapify( max_i );
    }

    return;
}

int extractMax()
{
    int max_v = S[1];
    S[1] = -1;

    maxHeapify( 1 );

    return max_v;
}

int main()
{
    char str[40];
    
    while ( true ) {
	scanf("%s", str);
	if ( !strcmp( str, "end" ) ) break;
	if ( !strcmp( str, "insert" ) ) {	// insert
	    int v;
	    scanf("%d", &v);
	    insert( v );
	}
	else {			// extract
	    int max_v = extractMax();
	    printf("%d\n", max_v);
	}
    }
    
    return 0;
}

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

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>>abcd(q, vector<int>(4));
	for (int i = 0; i < q; i++) {
		cin >> abcd.at(i).at(0) >> abcd.at(i).at(1) >> abcd.at(i).at(2) >> abcd.at(i).at(3);
		abcd.at(i).at(0)--;
		abcd.at(i).at(1)--;
	}
	ll ans = 0;
	vector<int>a(n,1);
	bool cyc = true;
	while (cyc) {
		//for (int i = 0; i < n; i++)cout << a.at(i) << " ";
		//cout << endl;
		ll res = 0;
		for (int i = 0; i < q; i++) {
			if (a.at(abcd.at(i).at(1)) - a.at(abcd.at(i).at(0)) == abcd.at(i).at(2)) res += abcd.at(i).at(3);
		}
		ans = max(ans, res);
		bool up = false;
		for (int i = 1; i <= n; i++) {
			if (up == false && a.at(n - i) < m) {
				a.at(n - i)++;
				break;
			}
			else if (up == false && a.at(n - i) == m) {
				up = true;
			}
			else if (up == true && a.at(n - i) < m) {
				a.at(n - i)++;
				for (int j = n - i; j < n; j++)	a.at(j) = a.at(n - i);
				up = false;
				break;
			}
			else if (up == true && i == n && a.at(n - 1) == m)cyc = false;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3628
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
dq = deque()
for i in range(n):
    if i%2:
        dq.appendleft(A[i])
    else:
        dq.append(A[i])
if n%2:
    dq = list(dq)[::-1]
print(*dq)


Measured memory_bytes: 32356
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<tuple<string, int,int>> p(n);
	rep(i, n) {
		int a;
		string b;
		cin >> b >> a;
		p.at(i) = make_tuple(b, -a, i + 1);
	}
	sort(p.begin(), p.end());
	rep(i, n) {
		int s;
		tie(ignore, ignore, s) = p.at(i);
		cout << s << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 666666, mo = 998244353;
int n,a[N],b[N],cnt[N],res=1;
void GG(){puts("0");exit(0);}
Pii seg[N];

/*int lzy[N<<1],val[N<<1];
void update(int k){val[k]=val[k<<1]+val[k<<1|1];}
void pushdown(int k,int l,int r){
	if(lzy[k]){
		lzy[k<<1]=lzy[k<<1|1]=1;lzy[k]=0;
		int mid=(l+r)>>1;
		val[k<<1]=mid-l+1;val[k<<1|1]=r-mid;
	}
}
void cover(int k, int l, int r, int L, int R){
	if(r<L||l>R)return;
	if(l<=L&&r>=R){lzy[k]=1;val[k]=R-L+1;return;}
	int mid=(L+R)>>1;pushdown(k,L,R);
	cover(k<<1,l,r,L,mid);cover(k<<1|1,l,r,mid+1,R);update(k);
}
int query(int k,int l,int r, int L, int R){
	if(r<L||l>R)return 0;
	if(l<=L&&r>=R)return val[k];
	pushdown(k,L,R);int mid=(L+R)>>1;
	return query(k<<1,l,r,L,mid)+query(k<<1|1,l,r,mid+1,R);
}
void shrink(int &l, int &r){
	per(i,18,0)if(l+(1<<i)<=r&&query(1,l,l+(1<<i)-1,1,n)==(1<<i))l+=1<<i;
	per(i,18,0)if(r-(1<<i)>=l&&query(1,r-(1<<i)+1,r,1,n)==(1<<i))r-=1<<i;
}*/
bool c[N];
inline void cover(int l, int r){rep(i,l,r)c[i]=1;}
inline void shrink(int &l, int &r){
	if(c[l])per(i,18,0)if(l+(1<<i)-1<=r&&c[l+(1<<i)-1])l+=1<<i;
	if(c[r])per(i,18,0)if(r-(1<<i)+1>=l&&c[r-(1<<i)+1])r-=1<<i;
}
int main() {
	read(n);rep(i,1,n)read(a[i]);
	rep(s,1,n)if(a[s]==1&&a[s-1>=1?s-1:n]!=1){//WA
		for(int i=1;i<=n;i++)b[i]=a[s+i-1<=n?s+i-1:s+i-1-n];
		memcpy(a,b,sizeof(b));break;
	}
	if(a[1]!=1)GG();
	rep(i,1,n){
		int j;for(j=i;j<=n;j++)if(a[j]!=a[i])break;
		seg[a[i]]=Pii(i,j-1);//printf("G %d\n",a[i]);
		if(cnt[a[i]])GG();cnt[a[i]]=1;i=j-1;
	}
	int x;for(x=1;x<=n;x++)if(a[x]!=1)break;x--;
//	printf("x = %d\n",x);
	int now=1;for(int i=n;i>=2;i--,now++)if(seg[i].fi){//WA
		int l=seg[i].fi-x+1,r=seg[i].se,L=seg[i].se-x+1,R=seg[i].fi;
		shrink(l,r);shrink(L,R);
	//	printf("%d : %d %d %d %d\n",i,l,r,L,R);
		if(L>R)GG();res=1LL*res*(R-L+1)%mo;now--;
		rep(t,l,r-1)res=1LL*res*now%mo,now--;
		cover(l,r);
	}
	if(a[n]==1){res=1;rep(i,1,n)res=1LL*res*i%mo;cout<<res;return 0;}//TEPAN
	rep(i,1,now)res=1LL*res*i%mo;cout<<res;
	return 0;
}



Measured memory_bytes: 13568
import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int[][] n = new int[r + 1][c + 1];

        for (int[] i : n) {
            for (int j : i) {
                j = 0;
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                n[i][j] = sc.nextInt();
                n[i][c] += n[i][j];
                n[r][j] += n[i][j];
            }
        }
        for (int j = 0; j < c; j++) {
            n[r][c] += n[r][j];
        }

        for (int i = 0; i < r + 1; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(n[i][j] + " ");
            }
            System.out.println(n[i][c]);
        }

    }

}


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

int n;

int main(void){
    cin >> n;
    unordered_map<string, int> m;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        m[s]++;
    }
    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n", m["AC"], m["WA"], m["TLE"], m["RE"]);
    return 0;
}


Measured memory_bytes: 3720
N = int(input())
A = [int(input()) for _ in range(N)]
B = []
for i, a in enumerate(A):
    B.append((i, a))
B.sort(key=lambda x: x[1], reverse=True)
for i in range(N):
    if i==B[0][0]:
        print(B[1][1])
    else:
        print(B[0][1])

Measured memory_bytes: 35020
/*
    Name: Attention
*/
#include "stdio.h"
bool debug=false;
int main()
{
    bool isstarteast=false,isbuffeast,iscureast;//west = false east = true
    int numamong[300010]={};
    int N,numberofdiffer=0;
    char buffer;
    scanf("%d",&N);
    scanf(" %c",&buffer);
    if(buffer=='E') isstarteast=true;
    else{
        numamong[1]=1;
        numberofdiffer++;
        iscureast=false;
    }
    //numberofdiffer is divisible by 2 when it is currently east
    for(int i=1;i<N;i++)
    {
        scanf(" %c",&buffer);
        if(buffer=='E') isbuffeast=true;
        else            isbuffeast=false;
        if(numberofdiffer==0)
        {
            if(!isbuffeast)
            {
                numamong[1]=1;
                numberofdiffer++;
                iscureast=false;
            }
            continue;
        }
        if(isbuffeast==iscureast)
        {
            numamong[numberofdiffer]++;
            continue;
            printf("hi");
        }
        numberofdiffer++;
        numamong[numberofdiffer]=1;
        iscureast=!iscureast;
    }
    if(numberofdiffer%2) numberofdiffer--;
    if(debug)
    {
        for(int i=1;i<=numberofdiffer;i++)
        {
            if(i%2==0)  printf("E ");
            else        printf("W ");
            printf("%d\n",numamong[i]);
        }
    }
    int mins,caseallW=0;
    for(int i=2;i<=numberofdiffer;i+=2)
    {
        caseallW+=numamong[i];
    }
    mins=caseallW;
    int curcase=caseallW;
    for(int i=1;i<numberofdiffer;i+=2)
    {
        curcase+=numamong[i];
        curcase-=numamong[i+1];
        if(debug)
            printf("curcase of %d = %d\n",i,curcase);
        if(mins>curcase)
        {
            mins=curcase;
        }
    }
    printf("%d",mins);
}



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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
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; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end



int main(){
    int n; scanf("%d",&n);
    double p=(n/2)*1.0/n;
    printf("%.12f\n",1-p);
    return 0;
}

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

int main(){ 
    int n;
    cin>>n;
    for(int i=0;i<25;i++){
    for(int j=0;j<15;j++){
        if(4*i+7*j==n){
            cout<<"Yes";
            return 0;
        }
    }
    }
    cout<<"No";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const int inf = 1e5;
//typedef long double ld;
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; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
int main(){
  int n;  cin >> n;
  vector<ll> v(n),sums(n+1,0);
  rep(i,0,n){
    cin >> v[i];
  }
  sort(all(v));
  bool ok[n];
  rep(i,0,n){
    ok[i] = false;
    sums[i+1] = sums[i] + v[i];
  }
  ok[n-1] = true;
  int cnt = 1;
  for(int i=n-2 ; i>=0 ; i--){
    auto ind = upper_bound(all(v), 2*(sums[i+1]))-v.begin();
    if(ok[ind-1]){
      cnt++;
      ok[i] = true;
    }
  }
  cout << cnt << endl;
  return 0;
}


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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int a, b;
  cin >> a >> b;
  bool ok = false;
  for (int i = min(a, b); i <= max(a, b); i++) {
  	if ((a * b * i) % 2 == 1) {
    	cout << "Yes" << '\n';
      ok = true;
      break;
      
    }
  }
  if (!ok) {
  	cout << "No" << '\n';
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_N 41
 
const double Pi = acos(-1);
 
double getAngle(double p, double q) {
  // assert(p < q);
   
  return (p-q)*2*Pi;
}
 
#define eps 1e-8
 
double getArea(double p, double q) {
  //cout<<getAngle(p,q)<<endl;
  //if(getAngle(p,q) > 0.5) return fabs(sin(1-getAngle(p, q))/2);
  return (sin(getAngle(p, q))/2);
}
 
int n, m;
double p[MAX_N];
 
double dp[MAX_N][MAX_N][MAX_N];
 
double solve(int idx, int curr, int start) {
  if(idx == m) {
    //if((1+p[start]-p[curr])-0.5 > 0) return -getArea(p[curr], p[start]);
    return getArea(p[start], p[curr]);
  }
  if(curr+1 == n) return -1e9;
  double &res = dp[idx][curr][start];
  if(res != -1) return res;
  for(int i = curr+1; i < n; i++) {
    res = max(res, solve(idx+1, i, start) + getArea(p[i], p[curr]));
  }
  return res;
}
 
int main() {
  while(cin >> n >> m, n || m) {
    for(int i = 0; i < n; i++) cin >> p[i];
 
    double ans = 0;
    for(int i = 0; i < MAX_N; i++)
      for(int j = 0; j < MAX_N; j++)
    for(int k = 0; k < MAX_N; k++)
      dp[i][j][k] = -1;
     
    for(int i = 0; i < n; i++) {
      ans = max(ans, solve(1, i, i));
    }
    printf("%.6f\n", ans);
  }
   
  return 0;
}

Measured memory_bytes: 4004
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int main()
{
	int n,a,sum=0;
	vector<int>v,w;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		v.pb(a);
	}
	for(int i=1;i<=100;i++)
	{
		for(int j=0;j<n;j++)
		{
			sum+=(i-v[j])*(i-v[j]);
		}
		w.pb(sum);
		sum=0;
	}
	sort(w.begin(),w.end());
	cout<<w[0]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void err() {
  cout << -1 << endl;
  exit(0);
}
int main() {
  int m, k;
  cin >> m >> k;
  int M = 1 << m;
  if (k >= M) err();
  if (m == 1 && k == 1) err();
  if (m == 1 && k == 0) {
    vector<int> ret = {0, 0, 1, 1};
    for (int i = 0; i < 4; i++) {
      cout << ret[i];
      if (i < 3) cout << " ";
    }
    cout << endl;
    return 0;
  }
  vector<int> a;
  a.push_back(k);
  for (int i = 0; i < M; i++) {
    if (i != k) a.push_back(i);
  }
  vector<int> ret = a;
  ret.push_back(a[0]);
  for (int i = M - 1; i >= 1; i--) {
    ret.push_back(a[i]);
  }
  for (int i = 0; i < 2 * M; i++) {
    cout << ret[i];
    if (i < 2 * M - 1) cout << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3444
import java.util.Arrays;
import java.util.Scanner;
import java.util.LinkedList;

public class Main {
	public static void main(String args[]){
		run();
	}
	static void run(){
		Scanner scan = new Scanner(System.in);
		
		int height, width, number;
		
		String tmp;
		
		int nowX, nowY;
		
		int timeTmp;
		
		int ans;
		
		int checkX, checkY;
		
		int health = 1;
		
		int nestX = 0;
		int nestY = 0;
		
		height = scan.nextInt();
		width = scan.nextInt();
		number = scan.nextInt();
		
		char[][] map = new char[height + 2][width + 2];
		String[] mapTmp = new String[height + 2];
		int[][] timeMap = new int[height + 2][width + 2];
		int[][] timeMapTmp = new int[height + 2][width + 2];
		
		for(int i = 0; i < height + 2; i++){
			for(int j = 0; j < width + 2; j++){
				map[i][j] = 'X';
				timeMap[i][j] = -1;
			}
		}
		timeMapTmp = timeMap;
		
		for(int i = 1; i <= height; i++){
			tmp = scan.next();
			mapTmp[i - 1] = tmp;
			for(int j = 0; j < width; j++){
				map[i][j + 1] = tmp.charAt(j);
				if(map[i][j + 1] == 'S'){
					nestX = i;
					nestY = j + 1;
					timeMap[i][j + 1] = 0;
				}
			}
		}
		
		
		
		LinkedList<Integer> queueX = new LinkedList<Integer>();
		LinkedList<Integer> queueY = new LinkedList<Integer>();
		
		
		queueX.offer(nestX);
		queueY.offer(nestY);
		
		for(;;){
			
			nowX = queueX.poll();
			nowY = queueY.poll();
			
			if(map[nowX][nowY] == (char)('0' + health)){
				if(health == number){
					ans = timeMap[nowX][nowY];
					break;
				}
				
				while(!queueX.isEmpty() && !queueY.isEmpty()){
					queueX.remove();
					queueY.remove();
				}
			
				health++;
				timeTmp = timeMap[nowX][nowY];
				timeMap = timeMapTmp;
				timeMap[nowX][nowY] = timeTmp;
				
				for(int i = 1; i <= height; i++){
					for(int j = 0; j < width; j++){
						map[i][j + 1] = mapTmp[i - 1].charAt(j);
					}
				}
				
				queueX.offer(nowX);
				queueY.offer(nowY);
				continue;
			}
			
			if(map[nowX + 1][nowY] == 'X'){
			}else{
				queueX.offer(nowX + 1);
				queueY.offer(nowY);
				timeMap[nowX + 1][nowY] = timeMap[nowX][nowY] + 1;
			}
			
			if(map[nowX][nowY + 1] == 'X'){
			}else{
				queueX.offer(nowX);
				queueY.offer(nowY + 1);
				timeMap[nowX][nowY + 1] = timeMap[nowX][nowY] + 1;
			}
			
			if(map[nowX - 1][nowY] == 'X'){
			}else{
				queueX.offer(nowX - 1);
				queueY.offer(nowY);
				timeMap[nowX - 1][nowY] = timeMap[nowX][nowY] + 1;
			}
			
			if(map[nowX][nowY - 1] == 'X'){
			}else{
				queueX.offer(nowX);
				queueY.offer(nowY - 1);
				timeMap[nowX][nowY - 1] = timeMap[nowX][nowY] + 1;
			}
			
			map[nowX][nowY] = 'X';
			
			check(queueX, queueY);
		}
		System.out.println(ans);
	}
	static void check(LinkedList<Integer> queueX, LinkedList<Integer> queueY){
		for(int i = 0; i < queueX.size(); i++){
			int checkX = queueX.get(i);
			int checkY = queueY.get(i);
			for(int j = i + 1; j < queueX.size(); j++){
				if(checkX == queueX.get(j) && checkY == queueY.get(j)){
					queueX.remove(j);
					queueY.remove(j);
					check(queueX, queueY);
				}
			}
		}
	}
}

Measured memory_bytes: 118520
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 1e5 + 10 ;
int main(){
    fastio
    int n ;
    cin >> n ; 
    string s ;
    cin >> s ;
    int cnt = 0 ;
    int nix = 0 ;
    for(int i = 0; i < n; i++){
        if ( s[i] == ')' ) cnt--;
        else if ( s[i] == '(' ) cnt++ ;
        nix = min(nix, cnt) ;
    }
    string ans = "" ;
    for(int i = 0; i < abs(nix); i++){
        ans.push_back('(') ;
    }
    for(int i = 0; i < n; i++){
        ans.push_back(s[i]) ;
    }
    int nax = 0 ;
    cnt = 0 ;
    for(int i = 0; i < ans.size(); i++){
        if ( ans[i] == ')' ) cnt--;
        else if ( ans[i] == '(' ) cnt++;
    }
    for(int i = 0; i < cnt; i++){
        ans.push_back(')') ;
    }
    cout << ans << endl ;
    return 0 ;
}

Measured memory_bytes: 3656
#include<stdio.h>
#include<math.h>
int main()
{
long long int n,a,b,c;  
scanf("%lld",&n);
a=pow(10,18);
b=1;
  c=0;
long long int d[n];  
  
  for(int i=0;i<n;++i)
  {
  scanf("%lld",&d[i]);
  
  if(b!=0)  
   {if(a/b>=d[i]) {b=b*d[i];}
    
    else{c++;}
   }  
  
  }
  
if(c==0) printf("%lld",b);
else if(b==0) printf("0");
else printf("-1");  
  
return 0;
}


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

using namespace std;

static string ln = "\n";
static string sp = " ";

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

  long a, b, k;
  cin >> a >> b >> k;

  long _a = max(0L, a - k);
  long diff = k - (a - _a);
  long _b = max(0L, b - diff);

  cout << _a << sp << _b << ln;
  return 0;
}


Measured memory_bytes: 256