akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }


void solve(long long X){
    for(ll S = 1; S*S <= X; S++){
        if(X % S) continue;
        ll Amax = sqrt(sqrt(X/S));
        for(ll A = Amax; A >= -Amax; A--){
            ll B = A-S;
            if( A*A*A*A*A - B*B*B*B*B == X){
                cout<< A <<" "<<B <<endl;
                return;
            }
        }
    }
}

int main(){
    long long X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3248
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<queue>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
typedef double lf;
typedef unsigned un;
typedef int in;
#define mian main
#define maxn 10000+10
#define maxm 10000+10
#define _(a) read(a)
#define non void
#define inf 2147483647
#define bre break
#define con continue
#define prq priority_queue
#define re register
#define bu bool
#define cz char
#define cst const
#define ope operator
#define inl inline
#define upp upper_bound
#define low lower_bound
#define next_per next_permutation
inl cz gc(){static cz buf[100000],*L=buf,*R=buf;return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;}
template<typename T>inl T Max(T a,T b){return a>b?a:b;}
template<typename T>inl T Min(T a,T b){return a<b?a:b;}
template<typename T>inl T Abs(T a){return a<0?-a:a;}
template<typename T>inl non read(T &a){a=0;T k=1;char c=gc();while(c<'0'||c>'9')k=c=='-'?-1:k,c=gc();while(c>='0'&&c<='9')a=a*10+(c^48),c=gc();if(c!='.'){a*=k;return;}T t=0.1;while(c<'0'||c>'9')c=gc();while(c>='0'&&c<='9')a+=t*(c^48),c=gc(),t*=0.1;a*=k;}
template<typename T>non write(T a,cz t=' '){if(a==0){putc(48,stdout),putc(t,stdout);return;}if(a<0){a=-a;putc('-',stdout);}cz c[30];in le=0;while(a){c[++le]=a%10+48;a/=10;}for(re in i=le;i>=1;--i)putc(c[i],stdout);putc(t,stdout);}
in n,k,a,s,m[300000];
in main()
{
	read(n),read(k);
	for(re in i=1;i<=n;++i){read(a);++m[a];}
	sort(m+1,m+1+n);
	for(in i=n;i>n-k;--i)s+=m[i];
	write(n-s);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
}


Measured memory_bytes: 1152
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF (int)1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
	
}

signed main(){
	ll n,m;
	cin >> n >> m;
	if(n == m) cout << "Yes" << endl;
	else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
//ΔAGC022D
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 666666;
int n,a[N],t[N],b[N],l[N],r[N],f[N];
int z,s[N];
LL ans;
set<pair<int,int> > L,R;
int main()
{
	int i,j;
	scanf("%d%d",&n,&z);
	a[n+1]=z;
	z=z+z;
	for(i=1;i<=n;i=i+1){
		scanf("%d",a+i);
		l[i]=a[i]+a[i];
		r[i]=z-l[i];
	}
	for(i=1;i<=n;i=i+1){
		scanf("%d",t+i);
		ans+=t[i]/z;
		t[i]%=z;
		if(!t[i])
			continue;
		if(l[i]>=t[i]){
			if(r[i]>=t[i])
				s[i]++,s[n+1]--,f[i]=1;
			else
				s[0]++,s[i]--;
		}
		else{
			if(r[i]>=t[i])
				s[i]++,s[n+1]--;
			else
				ans++;
		}
	}
	for(i=1;i<=n+1;i=i+1)
		s[i]+=s[i-1],R.insert(make_pair(s[i-1],i));//,cout<<s[i]<<endl;
	j=0;
	for(i=1;i<=n;i=i+1){
		L.insert(make_pair(s[i-1]-j-j,i-1));
		R.erase(make_pair(s[i-1],i-1));
		if(f[i]){
			if((*L.rbegin()).first+j+1<(*R.rbegin()).first-j){
				j++;
			}
		}
	}
	ans+=(*L.rbegin()).first+j+1;
	cout<<(LL)ans*z;
	return 0;
}
/*
2 100
20 40
160 120

*/

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> board(h);
    for (string& row : board) {
        cin >> row;
    }
    vector<vector<int>> dists(h, vector<int>(w, -1));
    queue<tuple<int, int, int>> q;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (board[i][j] == '#') {
                q.push(make_tuple(i, j, 0));
            }
        }
    }
    int max_dist = 0;
    while (!q.empty()) {
        auto p = q.front();
        int i = get<0>(p), j = get<1>(p), dist = get<2>(p);
        q.pop();
        if (dists[i][j] != -1) {
            continue;
        }
        dists[i][j] = dist;
        max_dist = dist;
        if (i > 0) {
            q.push(make_tuple(i - 1, j, dist + 1));
        }
        if (i + 1 < h) {
            q.push(make_tuple(i + 1, j, dist + 1));
        }
        if (j > 0) {
            q.push(make_tuple(i, j - 1, dist + 1));
        }
        if (j + 1 < w) {
            q.push(make_tuple(i, j + 1, dist + 1));
        }
    }
    cout << max_dist << endl;
    return 0;
}


Measured memory_bytes: 54856
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;


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

  ll n,q;cin>>n>>q;
  string s;cin>>s;
  vector<pair<char,char>>pll(q);
  for(int i=0;i<q;i++){
    cin>>pll[i].F>>pll[i].S;
  }
  ll right;
  bool flfl=false;
  ll le=-1,ri=n;
  while(ri-le>1){
    ll mid=(le+ri)/2;
    ll now=mid;
    if(now>=n||now<0){flfl=true;break;}
    bool can=false;
    for(int i=0;i<q;i++){
      if(s[now]==pll[i].F){
	if(pll[i].S=='R')now++;
	else now--;
      }
      if(now<0)break;
      if(now==n){can=true;break;}
    }
    if(can){
      ri=mid;
    }else{
      le=mid;
    }
  }
  if(flfl){
    right=n;
  }else right=ri;
  ll left;
  flfl=false;
  le=-1;ri=n;
  while(ri-le>1){
    ll mid=(le+ri)/2;
    ll now=mid;
    if(now>=n||now<0){flfl=true;break;}
    bool can=false;
    for(int i=0;i<q;i++){
      if(s[now]==pll[i].F){
	if(pll[i].S=='R')now++;
	else now--;
      }
      if(now>=n)break;
      if(now==-1){can=true;break;}
    }
    if(can){
      le=mid;
    }else{
      ri=mid;
    }
  }
  if(flfl)left=-1;
  else
    left=le;
  if(left==-1&&right==n){cout<<n<<endl;}
  else if(left==-1){
    cout<<n-(n-right)<<endl;
  } else if(right==n){cout<<(n-(left+1))<<endl;
  }else{
    ll ans=(left+1+(n-right))-max(0LL,left-right+1);
    cout<<n-ans<<endl;
  }
  return 0;
}


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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;
#define N 2005

typedef long long int ll;
typedef vector<pair<int, int>> vpi;
typedef unordered_map<int, unordered_map<int, int>> ump;

ll dp[N][N];

bool present(int l, int r) {
	return dp[l][r] != -1;
}

ll maxHappiness(vpi &v, int n, int cur, int l, int r) {

	if (l > r)
		return 0;

	if (present(l, r))
		return dp[l][r];

	ll put_in_left = (ll)v[cur].first * abs(v[cur].second-l) + maxHappiness(v, n, cur+1, l+1, r);
	ll put_in_right = (ll)v[cur].first * abs(v[cur].second-r) + maxHappiness(v, n, cur+1, l, r-1);

	dp[l][r] = max(dp[l][r], max(put_in_left, put_in_right));

	return dp[l][r];
}

int main() {

	int n;
	cin >> n;
	
	vpi v;
	int ip;

	for (int i = 0; i < n; i++) {
		cin >> ip;
		v.push_back({ip, i});
	}

	sort(v.begin(), v.end(), greater<pair<int,int>>());
	memset(dp, -1, sizeof(dp));

	cout << maxHappiness(v, n, 0, 0, n-1);

	return 0;
}

Measured memory_bytes: 35192
//SAIKH SERAJ FAHIM, CSE-19-HSTU, BANGLADESH.

#include<iostream>
using namespace std;
int main()
{
    long long int x1,x2,x3,x4,x5;
    cin>>x1>>x2>>x3>>x4>>x5;
    if(x1==0)
        cout<<"1"<<endl;
    else if(x2==0)
        cout<<"2"<<endl;
    else if(x3==0)
        cout<<"3"<<endl;
    else if(x4==0)
        cout<<"4"<<endl;
    else if(x5==0)
        cout<<"5"<<endl;
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

struct sec{
	int from;
	int to;
};

typedef pair<sec, int> P;

int main(){
	
	int n;
	
	vector<P> v;
	
	while(true){
		
		cin >> n;
		
		if(n == 0){
			break;
		}
		
		int num;
		P p1;
		
		cin >> num;
		
		p1.first.from = 0;
		p1.first.to = 0;
		p1.second = num;
		v.push_back(p1);
		
		for(int i = 1; i < n; i++){
			cin >> num;
			if(v.at(v.size() - 1).second == num){
				v.at(v.size() - 1).first.to = i;
			}else if(i % 2 == 0){
				p1.first.from = i;
				p1.first.to = i;
				p1.second = num;
				v.push_back(p1);
			}else{
				if(v.size() > 1){
					v.at(v.size() - 2).first.to = i;
					v.pop_back();
				}else{
					v.at(v.size() - 1).first.to = i;
					v.at(v.size() - 1).second = num;
				}
			}
		}
		
		int ans = 0;
		
		for(int i = 0; i < v.size(); i++){
			if(v.at(i).second == 0){
				ans += v.at(i).first.to - v.at(i).first.from + 1;
			}
		}
		
		printf("%d\n", ans);
		
		v.erase(v.begin(), v.end());
	}
	return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;
LL F[101][12];
LL P[101][12];
LL ans=-1e10;
LL c[101];

int main(){
    cin>>N;
    REP(i,N){
        REP(j,10){
            cin>>F[i][j];
        }
    }
    REP(i,N){
        REP(j,11){
            cin>>P[i][j];
            //cout<<i<<" "<<j<<" "<<P[i][j]<<endl;
        }
    }
    //cout<<P[1][1]<<endl;
    
    for(int i=1;i<(1<<10);i++){
        REP(j,N){
            c[j]=0;
        }
        REP(j,10){
            if((i>>j)&1){
                REP(k,N){
                    if(F[k][j]==1){
                       c[k]++;
                    }
                }
            }
        }
        LL t=0;
        REP(j,N){
            t+=P[j][c[j]];
        }
        /*if(ans<t){
           cout<<i<<" "<<t<<endl;
        }*/
        ans=max(ans,t);
    }
    cout<<ans<<endl;
    return(0);
}

Measured memory_bytes: 256
/*

*/
#include<bits/stdc++.h>

using namespace std;
using ll=long long;
#define rep2(i, a, n) for(int i = (a); i < (n); i++)
#define rep(i, n) rep2(i,0,n)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  //N 蜀翫・蜿り・嶌
  //蟄ｦ縺ｳ縺溘＞繧｢繝ｫ繧ｴ繝ｪ繧ｺ繝縺・M 蛟・
  int n,m,x;cin>>n>>m>>x;
  //i 逡ｪ逶ｮ縺ｮ蜿り・嶌縺ｯ Ci蜀・
  //j 逡ｪ逶ｮ縺ｮ繧｢繝ｫ繧ｴ繝ｪ繧ｺ繝縺ｮ逅・ｧ｣蠎ｦ縺・Ai,j
  vector<vector<int>> a(n, vector<int>(m));
  vector<int> c(n);
  for(int i = 0; i < n; i++){
    cin >> c[i];
    for(int j = 0; j < m; j++)cin >> a[i][j];
  }
  int ans=1e9,cost;
  bool ok;
  for(int i=0;i<(1<<n);i++){
    vector<int> level(m);
    cost=0;
    for(int j=0;j<n;j++){
      if((i>>j)&1){
        cost+=c[j];
        for(int k=0;k<m;k++)level[k]+=a[j][k];
      }
    }
    ok=true;
    for(int j=0;j<m;j++)if(level[j]<x)ok=false;
    if(ok)ans=min(ans,cost);
  }
  cout<<(ans!=1e9?ans:-1)<<endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll d, g;
    cin >> d >> g;
 
    vl p(d), c(d);
    rep(i, d) {
        cin >> p[i] >> c[i];
    }
 
    ll ans = INF;
    rep(b, 1<<d) {  // bのiビット目が1のとき問題iを全て解く
        ll now = 0;  // いま解いた問題数
        ll point = 0;  // いまのポイント
        rep(i, d) {
            if(b & 1<<i) {
                now += p[i];
                point += 100*(i+1)*p[i] + c[i];
            }
        }
        for(ll i = d-1; i >= 0; i--) {
            if(b & 1<<i) {
                continue;
            }
            rep(j, p[i]-1) {
                if(point >= g) {
                    break;
                }
                point += 100*(i+1);
                now++;
            }
            break;
        }
        if(point >= g) {
            chmin(ans, now);
        }
    }
 
    out(ans);
    re0;
}

Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif

int main_A() {
    cin.tie(0);
    ios::sync_with_stdio(false);
     
    int N = 3;
    vi A(N); REP(i, N) cin >> A[i];

    
    int ans = INF;
    vb used(N, false);
    REP(i,N){
        used[i] = true;
        REP(j,N){
            if (used[j]) continue;
            used[j] = true;
            REP(k,N){
                if (used[k]) continue;
                used[k] = true;

                int sum = abs(A[j]-A[i]) + abs(A[k] -A[j]);
                ans = min(ans, sum);

                used[k] = false;
            }
            used[j] = false;
        }
        used[i] = false;
    }    
    
    cout << ans << endl;

    return 0;
}


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

int main() {
  int H, W;
  cin >> H >> W;
  int r = 0;
  string a;
  for (int i = 0; i < H; i++) {
    cin >> a;
    for (int j = 0; j < W; j++) {
      if (j < r && a[j] == '#') {
        cout << "Impossible" << endl;
        return 0;
      } else if (a[j] == '#') {
        r = j;
      }
    }
  }
  cout << "Possible" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int a,b,i;
	i = 0;
	while(1) {
		scanf("%d %d", &a, &b);
		if(a == 0 && b == 0) break;
		for(; a > 0; a--) {
			for(i = 0; i < b; i++) {
				printf("#");
			}
			printf("\n");
		}
                printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 572
#include<iostream>
#include<vector>
using LL = long long;
using namespace std;

int main() {
	LL N, X, M;
	cin >> N >> X >> M;
	LL an = X, sum = 0;
	vector<LL> Sum;
	Sum.push_back(0);
	vector<LL> exsists(100010, -1);
	for(int i = 1; i<= N; i++){
		sum += an;
		Sum.push_back(sum);
		if (exsists[an] == -1) {
			exsists[an] = i;
		}
		else {
			LL l = exsists[an];
			LL r = i;
			LL Sdiff = Sum[r] - Sum[l];
			LL diff = r - l;

			LL shuki = (N - r) / diff;
			LL amari = (N - r) % diff;
			sum = sum + Sdiff * shuki + Sum[l + amari] - Sum[l];
			break;
		}
		//cout << i << "\t" << an << "\t" << sum << endl;
		an = an * an % M;
	}

	cout << sum << endl;


	return 0;
}


Measured memory_bytes: 4708
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define modbig (10*10*10*10*10*10*10*10*10+7)
using namespace std;

int main(){
  int n,x,ans=0;
  cin>>n>>x;
  int l[n],d[n+1];
  d[0]=0;
  rep(i,n){
    cin>>l[i];
    d[i+1]=l[i]+d[i];
  }
  rep(i,n+1){
    if(d[i]<=x){
      ans++;
    }
  }
  cout<<ans;
}

Measured memory_bytes: 256
n=int(input())
member = [0]*(10**5+1)
 
li = list(map(int,input().split()))
total = sum(li)
for i in range(n):
  member[li[i]] +=1
 
q = int(input())
for j in range(q):
  x,y = input().split()
  x=int(x)
  y=int(y)
  total += (y-x)*member[x]
  print(total)
  member[y]+=member[x]
  member[x]=0

Measured memory_bytes: 84292
#include <iostream>
using namespace std;
int main()
{
	int K, A, B;
	int x = 0;
	cin >> K >> A >> B;
	if (A == B) {
		if (A % K == 0)
			cout << "OK" << "\n";
		else
			cout << "NG" << "\n";
	}
	else {
		int i = A;
		while (i <= B) {
			if (i % K == 0)
				x += 1;
			i++;
		}
		if (x == 0)
			cout << "NG" << "\n";
		else
			cout << "OK" << "\n";
	}
}

Measured memory_bytes: 3640
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int Hissatu = scanner.nextInt();

        ArrayList<BigInteger> monsters = new ArrayList<>();
        for(int i=0;i<N;i++) {
            monsters.add(scanner.nextBigInteger());
        }

        //except
        if(Hissatu >= N){
            System.out.println(0);
            return;
        }

        PriorityQueue<BigInteger> queue = new PriorityQueue<>(Collections.reverseOrder());
        for(BigInteger h : monsters){
            queue.add(h);
        }

        for(int i=0;i<Hissatu;i++){
            queue.poll();
        }

        BigInteger answer = BigInteger.ZERO;
        for(BigInteger health : queue){
            answer = answer.add(health);
        }

        System.out.println(answer);
    }
}

Measured memory_bytes: 104220
def main():
    a, b, c, d = map(int, input().split())
    dx, dy = (c - a), (d - b)
    p1 = "L" + "U" * (dy + 1) + "R" * (dx + 1) + "D" + "L" * dx + "D" * dy
    p2 = "D" + "R" * (dx + 1) + "U" * (dy + 1) + "L" + "D" * dy + "L" * dx
    print(p1 + p2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
n=int(input())
alice=[]
bob=[]
l=list(map(int,input().split()))
while len(l)>0:
    alice.append(max(l))
    l.remove(max(l))
    if len(l)>0:
        bob.append(max(l))
        l.remove(max(l))

print(sum(alice)-sum(bob))


Measured memory_bytes: 38384
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n;
struct work{
	int a,b;
}c[200001];
bool operator<(work a1,work a2){
	re a1.b<a2.b;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n){
		cin>>c[i].a>>c[i].b;
	}
	sort(c,c+n);
	ll sum=0;
	rep(i,n){
		sum+=c[i].a;
		if(sum>c[i].b){
			cout<<"No";
			re 0;
		}
	}
	cout<<"Yes";
	re 0;
}


Measured memory_bytes: 1792
//============================================================================
// Name        : hoba.cpp :)
// Author      : (O_O Diab) (Why_not) (el 3AQ)
// Version     :
// Copyright   : please, Don't touch me :(
// Description : problem in C++
// MAIN IDEA   : combinatorics NCR
//============================================================================
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define rw freopen("graphs_as_a_service.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace __gnu_pbds;
using namespace std;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int N = 1e5 + 10, mod = (int) 1e9 + 7, INF = 0x3f3f3f3f;
int n, dp[N] = { };
vi v[N], vv;
void dfs(int node, int par) {
	dp[node] = 1;
	for (auto u : v[node]) {
		if (u == par)
			continue;
		dfs(u, node);
		dp[node] += dp[u];
	}
}
int p1, p2;
void dfs2(int node, int par) {
	vv.pb(node);
	if (node == n) {
//		for (auto u : vv)
//			cout << u;
//		cout<<"\n";
		if (vv.size() & 1) {
			p1 = vv[vv.size() / 2];
			p2 = vv[vv.size() / 2 + 1];
		} else {
			p1 = vv[vv.size() / 2 - 1];
			p2 = vv[vv.size() / 2];
		}
	}
	for (auto u : v[node]) {
		if (u == par)
			continue;
		dfs2(u, node);
	}
	vv.pop_back();
}
int main() {
#ifdef ONLINE_JUDGE
	FAST
#endif
	cin >> n;
	lp(i,1,n-1)
	{
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	dfs2(1, 0);
//	p(p1);
//	p(p2);
	dfs(1, 0);
	int subtreen = dp[p2];
	clr(dp, 0);
	dfs(n, 0);
	int subtree1 = dp[p1];
//	p(subtree1);
//	p(subtreen);
	if (subtree1 > subtreen)
		f("Fennec");
	f("Snuke");
	return 0;
}

Measured memory_bytes: 12920
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

void solve()
{
  string a;
  cin>>a;
   int l=a.length(),cnt=0;
  for(int i=0;i<l;i++){
    if(a[i]=='A'){
        break;
    }
    else{cnt++;}
  }
  for(int i=l-1;i>=0;i--){
    if(a[i]=='Z'){break;}
    else{cnt++;}
  }
  cout<<l-cnt<<endl;
}

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

        solve();

    return 0;
}



Measured memory_bytes: 3772
# Problem - 選択ソート

def selection_sort(A, N):
    sort_count = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j]<A[minj]:
                minj = j
        if not minj==i:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp
            sort_count += 1
    return A, sort_count

# input
N = int(input())
a_nums = list(map(int, input().split()))

# initialization
ans_list, ans_count = selection_sort(a_nums, N)
print(" ".join(list(map(str, ans_list))))
print(ans_count)



Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
void input()
{ 
  #ifndef ONLINE_JUDGE 
  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  #endif
}
typedef long long int ll;
#define rep(i,a,b) for( ll i=a;i<b;i++)
#define rrep(i,a,b)for(ll i=a;i>=b;i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define f first
#define s second
#define mod 1000000007
bool compare(pair<int,int>a,pair<int,int>b)
{
  return a.f<b.f;
}
int main()
{
  //input();
  ios_base::sync_with_stdio(0);
    cin.tie(0);
 ll n,W,ans=INT_MIN;
 cin>>n>>W;
 ll profit[n][2],dp[n+1][W+1]={};
 rep(i,0,n)cin>>profit[i][0]>>profit[i][1];

 rep(i,1,n+1)
 {
  rep(w,1,W+1)
  {
    if(w-profit[i-1][0]>=0)
    {
      dp[i][w]=max(profit[i-1][1]+dp[i-1][w-profit[i-1][0]],dp[i-1][w]);
    }
    else dp[i][w]=dp[i-1][w];
    //cout<<dp[i][w]<<" ";
  }
  //cout<<endl;
 }

cout<<dp[n][W]<<endl;
}

///shubham gupta/


Measured memory_bytes: 79232
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  dead_code
)]
use proconio::fastout;
use proconio::input;
use proconio::marker::*;
use std::cmp::*;
use std::collections::*;
//use std::collections::VecDeque;

macro_rules! debug {
  ($($a:expr),* $(,)*) => {
      #[cfg(debug_assertions)]
      eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
  };
}
#[fastout]
fn main() {
  input! {
    R:usize,C:usize,K:usize,
    RCV:[(usize,usize,i64);K]
  }
  let mut RCV: Vec<(usize, usize, i64)> = RCV;
  // dp[r,c,n]位置(r,c)にいるときに、その行でn個以下のアイテムを拾っているときのtotal
  // r,cのスタートは(1,1)から、(R,C)に移動するまで。
  // つまり、r+cがR+C-2になるまで。
  let mut v = vec![vec![0; C + 1]; R + 1];
  for &(r, c, x) in RCV.iter() {
    v[r][c] = x;
  }
  debug!(v);
  let mut dp = vec![vec![vec![0; 4]; C + 1]; R + 1];
  for r in 1..=R {
    for c in 1..=C {
      debug!(r, c);
      // 移動のみ
      dp[r][c][0] = max(dp[r - 1][c][3], dp[r][c - 1][0]);
      dp[r][c][1] = max(dp[r - 1][c][3], dp[r][c - 1][1]);
      dp[r][c][2] = max(dp[r - 1][c][3], dp[r][c - 1][2]);
      dp[r][c][3] = max(dp[r - 1][c][3], dp[r][c - 1][3]);
      debug!(r, c, dp[r]);
      // 拾う。
      if v[r][c] > 0 {
        dp[r][c][3] = max(dp[r][c][3], dp[r][c][2] + v[r][c]);
        dp[r][c][2] = max(dp[r][c][2], dp[r][c][1] + v[r][c]);
        dp[r][c][1] = max(dp[r][c][1], dp[r][c][0] + v[r][c]);
        debug!(r, c, dp[r]);
      }
    }
  }
  println!("{}", dp[R][C][3])
}


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

using namespace std;

string lcs(string const& s, string const& t) {
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] + 1
                                            : max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    string ans;
    int i = n, j = m;
    while (i != 0 && j != 0) {
        if (s[i - 1] == t[j - 1]) {
            ans.push_back(s[i - 1]);
            --i, --j;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    reverse(ans.begin(), ans.end());

    return ans;
}

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

    string s, t;
    cin >> s >> t;

    cout << lcs(s, t) << endl;

    return 0;
}


Measured memory_bytes: 35584
#!/usr/bin/env python3
#AGC15 A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,a,b = LI()
if a > b or (n == 1 and a != b):
    print(0)
else:
    print(b*(n-1)+a - (a*(n-1)+b)+1)


Measured memory_bytes: 38384
n = int(input())
s = list(input())
import copy
M = 0
for i in range(n):
    count = 0
    l1 = copy.copy(s[0 : i + 1])
    l2 = copy.copy(s[i + 1 : n])
    l1 = list(set(l1))
    l2 = list(set(l2))
    for j in range(len(l1)):
        if l1[j] in l2:
            count += 1
    if count > M:
        M = count
print(int(M))

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

const int MAXN = 200010;

int n, val[MAXN];
vector<int> G[MAXN];
vector<int> ks[3];
vector<int> ids[3];
int num, pos[3], vis[MAXN];

void dfs(int x, int fa, int dep)
{
	if(dep & 1) ids[1].push_back(x);
	else ids[2].push_back(x);
	for(int i = 0; i < G[x].size(); ++i)
		if(G[x][i] != fa) dfs(G[x][i], x, dep + 1);
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; ++i)
	{
		int u, v; scanf("%d %d", &u, &v);
		G[u].push_back(v); G[v].push_back(u);
	}
	dfs(1, 0, 1);
	if(ids[1].size() <= n / 3)
	{
		int now = 1;
		for(int i = 0; i < ids[1].size(); ++i) val[ids[1][i]] = now * 3, vis[now * 3] = 1, ++now;
		now = 1;
		for(int i = 0; i < ids[2].size(); ++i)
		{
			while(vis[now]) ++now;
			val[ids[2][i]] = now, vis[now] = 1;
		}
	}
	else if(ids[2].size() <= n / 3)
	{
		int now = 1;
		for(int i = 0; i < ids[2].size(); ++i) val[ids[2][i]] = now * 3, vis[now * 3] = 1, ++now;
		now = 1;
		for(int i = 0; i < ids[1].size(); ++i)
		{
			while(vis[now]) ++now;
			val[ids[1][i]] = now, vis[now] = 1;
		}
	}
	else
	{
		for(int i = 0; 3 * i <= n; ++i)
		{
			if(3 * i + 1 <= n) ks[1].push_back(3 * i + 1);
			if(3 * i + 2 <= n) ks[2].push_back(3 * i + 2);
		}
		for(int i = 0; i < ids[1].size(); ++i)
		{
			if(pos[1] < ks[1].size()) val[ids[1][i]] = ks[1][pos[1]], ++pos[1];
			else break;
		}
		for(int i = 0; i < ids[2].size(); ++i)
		{
			if(pos[2] < ks[2].size()) val[ids[2][i]] = ks[2][pos[2]], ++pos[2];
			else break;
		}
		int now = 1;
		for(int i = 1; i <= n; ++i) if(!val[i]) val[i] = now * 3, ++now;
	}
	for(int i = 1; i <= n; ++i) printf("%d ", val[i]);
	return puts(""), 0;
}

Measured memory_bytes: 19828
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e16;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll N; cin >> N;
    bool firstWin = false;
    REP(i, N){
        ll a; cin >> a;
        if(a%2 == 1){
            firstWin = true; break;
        }
    }
    cout << (firstWin ? "first" : "second") << endl;
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)

using ll = long long;

constexpr ll mod = 1000000007;

ll n, m;
ll x[100001], y[100001];

int main()
{
	scanf("%lld%lld", &n, &m);
	rep(i, n)
		scanf("%lld", x + i);
	rep(i, m)
		scanf("%lld", y + i);

	ll w = 0;
	rep(i, n)
		w = (w + (i - (n-1 - i))*x[i]) % mod;

	ll h = 0;
	rep( i, m )
		h = (h + (i - (m-1 - i))*y[i]) % mod;

	printf("%lld\n", w*h%mod);

	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define ll long long
#define eps 1e-8

using namespace std;

int main()
{
	cin.tie(0),ios::sync_with_stdio(0);
	ll n,m,c,ans=0,sum;
	cin>>n>>m>>c;
	vector<ll> a(m),b(m);
	for(auto &i:b)
	 	cin>>i;
	for(int i=0;i<n;i++)
	{
		for(auto &i:a)
			cin>>i;
		sum=0;
		for(int i=0;i<m;i++)
			sum+=a[i]*b[i];
		sum+=c;
		ans+=(sum>0);
	}
	cout<<ans<<'\n';
	return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define loop(i,L,R) for(int i=(L);i<=(R);i++)
#define rept(i,L,R) for(int i=(L);i<(R);i++)
#define isc(n) scanf("%d",&n)
#define llsc(n) scanf("%lld",&n)
#define dsc(n) scanf("%lf",&n)
#define enl cout<<endl
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define xx first
#define yy second
typedef long long ll;
typedef pair<int,int>PI;
typedef pair<pair<int,int>,int>PII;

const int mx=111;
int arr[2][mx];
int main()
{
	int n;
	cin>>n;
	rept(k,0,2)
	{
		loop(i,1,n)
		{
			cin>>arr[k][i];
			arr[k][i]+=arr[k][i-1];
		}
	}
	int ans=0;
	loop(i,1,n)
	{
		int cur=arr[0][i]+arr[1][n]-arr[1][i-1];
		ans=max(ans,cur);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

vector<ll> dijkstra(const vector<vector<pair<int,int>>> &graph,int s,vector<ll> &cnt){
    int n=(int)graph.size();
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    vector<ll> dist(n,linf);
    dist[s]=0;
    cnt.assign(n,0);
    cnt[s]=1;
    pq.push({0,s});
    while(pq.size()){
        auto p=pq.top();
        pq.pop();
        int v=p.second;
        if(dist[v]<p.first)continue;
        for(auto edge:graph[v]){
            int u=edge.first;
            int w=edge.second;
            if(dist[v]+w<dist[u]){
                dist[u]=dist[v]+w;
                cnt[u]=cnt[v];
                pq.push({dist[u],u});
            }
            else if(dist[v]+w==dist[u]){
                cnt[u]=(cnt[u]+cnt[v])%mod;
            }
        }
    }
    return dist;
}

int main(){
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    --s,--t;
    vector<vector<pair<int,int>>> g(n);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    vector<ll> cnt_t,cnt_a;
    vector<ll> d_t=dijkstra(g,s,cnt_t);
    vector<ll> d_a=dijkstra(g,t,cnt_a);
    vector<ll> path;
    rep(i,n){
        if(d_t[i]==d_a[i]&&d_t[i]+d_a[i]==d_t[t]){
            path.push_back((cnt_t[i]*cnt_a[i])%mod);
        }
        rep(j,g[i].size()){
            ll w=g[i][j].second;
            int to=g[i][j].first;
            if(d_t[i]+w+d_a[to]!=d_t[t])continue;
            if(d_t[i]<d_a[i]&&d_t[to]>d_a[to]){
                path.push_back((cnt_t[i]*cnt_a[to])%mod);
            }
        }
    }
    ll ans=(cnt_t[t]*cnt_t[t])%mod;
    for(ll e:path){
        ans=(ans-e*e)%mod;
    }
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
}


Measured memory_bytes: 15060
use std::io::*;
use std::str::FromStr;
use std::cmp::{Ordering, min};

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let x: i64 = read();
    let mut ret = 0;
    let mut s = 0;
    for _ in 0..n {
        let a: i64 = read();
        s += a;
        ret += 1;
        if x < s {
            println!("{}", ret);
            return;
        }
    }
    ret += 1;
    println!("{}", ret);
}


Measured memory_bytes: 4352
#include <utility>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define INTINF 2147483647
#define LLINF 9223372036854775807
typedef long long ll;
using namespace std;

void printVector(std::vector<int> &A) {
  for (size_t i = 0; i < A.size(); i++) {
    std::cout << A[i];
    if (i<A.size()-1) {
      std::cout << " ";
    }
  }
  std::cout << " " << '\n';
}

void CountingSort(std::vector<int> &A, std::vector<int> &B, int k) {
  std::vector<int> C(k+1, 0);
  int n = A.size();

  for (size_t i = 0; i < n; i++) {
    C[A[i]]++;
  }

  for (size_t i = 1; i <= k; i++) {
    C[i] += C[i-1];
  }

  for (int i = n-1; i >= 0; i--) {
    B[C[A[i]]-1] = A[i];
    C[A[i]]--;
  }
}



int main(int argc, char const *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n; std::cin >> n;

  std::vector<int> A, B;
  A.reserve(n); B.reserve(n);

  int tmp, k=0;
  for (size_t i = 0; i < n; i++) {
    std::cin >> tmp;
    k = max(k,tmp);
    A.push_back(tmp);
  }

  CountingSort(A, B, k);

  for (size_t i = 0; i < n; i++) {
    std::cout << B[i];
    if (i<n-1) {
      std::cout << " ";
    }
  }
  std::cout << '\n';

  return 0;
}



Measured memory_bytes: 18424
N=int(input())
l=[i for i in range(100010)]
p=[6**i for i in range(1,7)]+[9**j for j in range(1,6)]
p.sort()

for c in p:
  if c>N:break
  for i in range(c, N+1):
    l[i] = min(l[i],l[i-c]+1)
print(l[N])

Measured memory_bytes: 7064
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;
static const long k10E7 = 1000000007;

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

    vector<long> an(n);
    for(long& a : an){
        cin >> a;
    }

    sort(an.begin(), an.end());
    vector<pair<long, long>> xylist(0);
    pair<long, long> xy;

    while(an.size() > 2){    
        if(an[1] < 0){
            xy.first = an.back();
            xy.second = an[1];
            an.back() -= an[1];
        } else {
            xy.first = an.front();
            xy.second = an[1];
            an.front() -= an[1];
        }
        xylist.push_back(xy);
        an.erase(an.begin() + 1);
    }

    xy.first = an[1];
    xy.second = an[0];
    xylist.push_back(xy);
    
    long last = xy.first - xy.second;
    cout << last << endl;

    for(pair<long, long>& xy : xylist){
        cout << xy.first << " " << xy.second << endl;
    }

    return 0;
}

Measured memory_bytes: 4336
readline = open(0).readline
N, W = map(int, readline().split())
R = []
for i in range(N):
    v, w = map(int, readline().split())
    R.append((v/w, v, w))
R.sort(reverse=1)
ans = 0
for _, v, w in R:
    c = min(w, W)
    W -= c
    ans += c * v / w
open(1, 'w').write("%.010f\n" % ans)


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

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

    std::unordered_set<int> f;
    std::unordered_set<int> s;
    int a, b;
    for (int i = 0; i < M; ++i) {
        std::cin >> a >> b;
        --a;
        --b;

        if (a == 0) {
            f.insert(b);
        } else if (b == (N - 1)) {
            s.insert(a);
        }
    }

    for (int v : f) {
        if (s.count(v) != 0) {
            std::cout << "POSSIBLE\n";
            return 0;
        }
    }
    
    std::cout << "IMPOSSIBLE\n";

    return 0;
}


Measured memory_bytes: 8520
#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 forn(i, n) for (ll i = 0; i < int(n); i++)
#define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define M_PI 3.14159265358979323846
#define EPS 1e-7

int cnt = 0;


void solve()
{
	int n, d; cin >> n >> d;
	vector<vector<int>> x(n);
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < d; ++j)
		{
			int c; cin >> c;
			x[i].pb(c);
		}
	}
	set<int> sqr;
	for (int i = 0; i < 405; ++i)
	{
		sqr.insert(i * i);
	}
	ll res = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			ll check = 0;
			for (int k = 0; k < d; ++k)
			{
				check += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
			}
			if (sqr.find(check) != sqr.end()) res++;
		}
	}
	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}


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

#define int long long int

int32_t main()
{
  int n, m;
  cin>>n>>m;

  vector< vector<int> > arr(n+1, vector<int> (2, 0));
  for(int i=1;i<m+1;i++)
  {
      int p;
      string s;
      cin>>p>>s;
      if(arr[p][0] != 1)
      {
          if(s == "WA")
          {
              arr[p][1]++;
          }
          else
          {
              arr[p][0] = 1;
          }
      }
  }
  int c = 0;
  int p = 0;
  for(int i=1;i<n+1;i++)
  {
      if(arr[i][0] == 1)
      {
          c++;
          p = p + arr[i][1];
      }
  }
  cout<<c<<" "<<p;
  return 0;
}



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

int main() {
  int m1,d1,m2,d2;
  cin >> m1 >> d1 >> m2 >> d2;
  if(m1 != m2) cout << 1 << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define rrdebug(i, j, x) rep(i, alength(x))rep(j, alength(x[i]))cout << #x << "[" << i << "][" << j << "]:" << x[i][j] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld EPS = 1.0e-14;//-9
const ld PI = acos(-1);
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) {a = b; return true;} return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) {a = b; return true;} return false; }
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){ if(!b)return a; return gcd(b, a % b); }
intl lcm(intl a,intl b){ return a / gcd(a, b) * b; }
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
//-------------------------------------------------------------------------------

intl a,b,c,k;

void input_var(){
    cin >> a >> b >> c >> k;
}
//-------------------------------------------------------------------------------

signed main(){
    cout << fixed << setprecision(10);
    input_var();
    intl cnt = 0;
    if(a > k){
        cout << k << endl;
    }
    else {
        cnt += a;
        k -= a;
        if(k > 0){
            k -= b;
            if(k > 0){
                cnt -= k;
            }
        }
        cout << cnt << endl;
    }
    
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#define INF 1234567890
#define MIN -1

int N, Z, W;
vector<int> v;
int dp[2005][2];

int dfs(int pos, int turn){

  if(turn == 0){
    if(dp[pos][turn]!=-1) return dp[pos][turn];
    int mx = MIN;
    REP(i,pos+1,N){
      int tmp;
      if(i == N-1){
        tmp = abs(v[pos]-v[i]);
      }else{
        tmp = dfs(i,1-turn);
      }
      if(tmp > mx){
        mx = tmp;
      }
    }
    return dp[pos][turn] = mx;
  }else{
    if(dp[pos][turn]!=-1) return dp[pos][turn];    
    int mn = INF;
    REP(i,pos+1,N){
      int tmp;
      if(i == N-1){
        tmp = abs(v[pos]-v[i]);
      }else{
        tmp = dfs(i,1-turn);
      }
      if(tmp < mn){
        mn = tmp;
      }
    }
    return dp[pos][turn] = mn;
  }
}


int main(){
  cin >> N >> Z >> W;
  v.push_back(Z);
  v.push_back(W);
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);
  }
  
  N += 2;

  rep(i,2005){
    rep(j,2){
      dp[i][j] = -1;
    }
  }
  
  cout << dfs(1,0) << endl;
  return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
using namespace std;
typedef long long LL;
const int maxn=5e5+5;
int a[maxn],c[maxn];
int sum[maxn];
int n;
LL tmp;
int lowbit(int x) {
    return x&(-x);
}
int getsum(int x) {
    int sum=0;
    while(x>0) {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void add(int x) {
    while(x<maxn) {
        c[x]+=1;
        x+=lowbit(x);
    }
}
bool check(int x) {
    memset(c,0,sizeof(c));
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        if(a[i]>=x)sum[i]=1;
        else sum[i]=-1;
        sum[i]=sum[i-1]+sum[i];
    }
    for(int i=0;i<=n;i++) {
        sum[i]+=n+1;
    }
    LL ans=0;
    for(int i=0;i<=n;i++) {
        ans+=getsum(sum[i]);
        add(sum[i]);
    }
    if(ans>=tmp)return true;
    else return false;
}
int main() {
    read(n);
    int minn=1e9,maxx=0;
    for(int i=1;i<=n;i++) {
        read(a[i]);
        minn=min(minn,a[i]);
        maxx=max(maxx,a[i]);
    }
    int l=minn,r=maxx;
    int ans=l;
    tmp=1LL*(n+1)*n/4;
    while(l<=r) {
        int mid=(l+r)/2;
        if(check(mid)) {
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 2944