akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define INF (1LL << 31 - 1)
#define MOD int(1e9+7)
#define repi(i,j,n) for(int i = (j); i < (n); ++i)
#define rep(i,n) repi(i,0,n)
#define fi first
#define se second

inline void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int dp[41][410][410], n, Ma, Mb;
int a[41], b[41], c[41];
 
int dfs(int x, int A, int B) {
    int ret = INF;
 
    if (dp[x][A][B] != 0) return dp[x][A][B];
 
    if ((double)A == (double)B * ((double)Ma / (double)Mb)) {
        return c[x];
    }
 
    for (int i = x+1; i < n; ++i) {
        ret = min(ret, dfs(i, A+a[i], B+b[i]) + c[x]);
    }
 
    return dp[x][A][B] = ret;
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n >> Ma >> Mb;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }
 
    int ans = INF;
 
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dfs(i, a[i], b[i]));
    }
 
    if (ans != INF) cout << ans << endl;
    else cout << -1 << endl;
 
    return 0;
}

Measured memory_bytes: 24832
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
signed main(void) {
    int n,m;cin>>n>>m;
    priority_queue<int>p;
    int x;
    rep(i,n){
        cin>>x;p.push(x);
    }
    
    while(!p.empty()&&m>0){
        x=p.top();p.pop();
        x/=2;p.push(x);
        m--;
    }
    
    int ans=0;
    while(!p.empty()){
        //cout<<p.top()<<' ';
        ans+=p.top();p.pop();
    }
    cout<<ans<<endl;
    
} 

Measured memory_bytes: 1400
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#define mod 998244353
#define pb push_back
using namespace std;
long long comb[300009]; // c(n,s)
long long inv(long long s){
	long long ans,b,x,u,q,tmp;
	b=mod;
	x=1;
	u=0;
	while(b>0){
		q=s/b;
		tmp = u; u=x-q*u; x=tmp;
		tmp = b; b=s-q*b; s=tmp;
	}
	if(x>0) return x;
	else return x+mod;
}
int main(){
	long long n;
	long long a,b,k;
	long long ans=0;
	cin>>n>>a>>b>>k;
	comb[0]=1;
	for(int i=1;i<=n;i++){
		comb[i] = comb[i-1]*(n-i+1);
		comb[i] = comb[i]%mod;
		comb[i] = comb[i]*inv(i) ;
		comb[i] = comb[i]%mod;
	}
	for(int i=0;i<=n;i++){
		if( (k-a*i)>=0 && (k-a*i)%b==0 && ( (k-a*i)/b )<=n){
			long long red=i;
			long long blue=(k-a*i)/b;
			ans += (comb[red]%mod) * (comb[blue]%mod);
			ans = ans%mod;
		}
	}
	cout<<ans%mod<<endl;
	return 0;
}

Measured memory_bytes: 2560
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <string.h>
using namespace std;

char str[123456];
int length;

bool f(int i)
{
	if (length < i)return false;
	if (length == i)return true;
	if (length - i < 5)return false;
	if (length - i >= 7 && str[i] == 'd' && str[i + 1] == 'r' &&str[i + 2] == 'e' &&str[i + 3] == 'a' &&str[i + 4] == 'm' &&str[i + 5] == 'e' &&str[i + 6] == 'r')
	{
		if (f(i + 7))return true;
	}
	if (length - i >= 6 && str[i] == 'e' && str[i + 1] == 'r' &&str[i + 2] == 'a' &&str[i + 3] == 's' &&str[i + 4] == 'e' &&str[i + 5] == 'r')
	{
		if (f(i + 6))return true;
	}
	if (str[i] == 'd' && str[i + 1] == 'r' &&str[i + 2] == 'e' &&str[i + 3] == 'a' &&str[i + 4] == 'm')
	{
		if (f(i + 5))return true;
	}
	if (str[i] == 'e' && str[i + 1] == 'r' &&str[i + 2] == 'a' &&str[i + 3] == 's' &&str[i + 4] == 'e')
	{
		if (f(i + 5))return true;
	}
	return false;
}

int main(void)
{
	scanf("%s", str);
	length = strlen(str);
	if (f(0))
	{
		printf("YES");
	}
	else
	{
		printf("NO");
	}
	return 0;
}


Measured memory_bytes: 1408
<?php 
  
  $a =explode(" ",fgets(STDIN));

  $m1hp = (int)$a[0];
  $m1pow = (int)$a[1];

  $m2hp = (int)$a[2];
  $m2pow = (int)$a[3];

  $ans = "";
  $count = 1;

  while(true){
    
    if($count % 2 === 0){
      $m1hp = $m1hp - $m2pow;
    	if($m1hp <= 0){
         	$ans = "No"; 
          
          break; 
        }
      
    }else {
    	$m2hp = $m2hp - $m1pow;
    	if($m2hp <= 0){
         	$ans = "Yes"; 
          break; 
        }
    }
    $count++;
  }

echo $ans;

Measured memory_bytes: 16124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b:i--)

int main() {
    // your code goes here
    ll n,memo=1,mx=0;
    string s[200005];
    vector<string> ans;
    cin >> n;
    rep(i,0,n-1){
        cin >> s[i];
    }
    sort(s,s+n);
    rep(i,1,n-1){
        if(s[i-1]==s[i]) memo++;
        if(s[i-1]!=s[i]) {
            if(memo==mx) ans.push_back(s[i-1]);
            else if(memo>mx){
                mx=memo;
                ans.clear();
                ans.push_back(s[i-1]);
            }
            memo=1;
        }
    }
    if(memo==mx) ans.push_back(s[n-1]);
    else if(memo>mx){
        mx=memo;
        ans.clear();
        ans.push_back(s[n-1]);
    }
    sort(ans.begin(),ans.end());
    for(auto it : ans) cout << it << endl;
    return 0;
}

Measured memory_bytes: 15988
#include <bits/stdc++.h>
using namespace std;
long long a , b , c , d , ans;
int main(){
	cin>> a>> b >> c >> d;
	ans=max(a * c, a * d);
    ans=max( ans , b * c);
    ans=max( ans , b * d);
	cout << ans << '\n'  ;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int main() {
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    int ans = 0;
    if(K <= A)
        ans = K;
    else if(K <= A + B)
        ans = A;
    else
        ans = A - (K - A - B);
    cout << ans;
    return 0;
}


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

int w(long long x)
{
	int ans;
	ans=0;
	while (x!=0)
	{
		ans+=x%10;
		x/=10;
	}
	return ans;
}

int main()
{
	int n;
	cin>>n;
	int i,x[n+1],ans=0;
	cin>>x[1];
	for (i=2;i<=n;i++)
	{
		cin>>x[i];
		if (x[i]==x[i-1])
		{
			ans++;
			x[i]=-1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  int res = 1;
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      res *= k;
    } else {
      res *= k - 1;
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int A, B;
  cin >> A >> B;
  int ans = -1;
  rep(i, 1000000)
  {
    double nA = (double)i * 0.08;
    double nB = (double)i * 0.1;
    if ((int)floor(nA) == A && (int)floor(nB) == B)
    {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

typedef long long int ll;

bool check(string s)
{
    int p=0,q=s.length()-1;

    while(p<=q)
    {
        if(s[p]==s[q])
        {
            p++;
            q--;
        }
        else
            return 0;
    }
    return 1;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s;
    cin >> s;
    string s1="",s2="";

    int n = s.length();
    for(int i=0 ; i<(n-1)/2 ; i++)
    {
        s1+=s[i];
    }

    for(int i=(n-1)/2 + 1 ; i<(n-1)/2 ; i++)
    {
        s2+=s[i];
    }
    if(check(s1) && check(s2) && check(s))
    {
        cout << "Yes";
    }
    else
        cout << "No";


    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 REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
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; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

ll mss2(vector<vector<ll> > a) {
  int w = a.size();
  int h = a[0].size();
  vector<vector<ll>> sum(h+1,vector<ll>(w));
  REP(x,w) {
    REP(y,h) sum[y+1][x] = sum[y][x] + a[y][x];
  }
  ll res = -(1LL<<60);
  REP(y2,h+1) REP(y1,y2) {
    ll d = -(1LL<<60);
    REP(x, w) {
      ll t = sum[y2][x] - sum[y1][x];
      d = max(d+t, t);
      chmax(res, d);
    }
  }
  return res;
}

int main() {
  int n;
  while(input(n)) {
    vector<vector<ll> > a(n,vector<ll>(n));
    REP(i,n) {
      REP(j,n) input(a[i][j]);
    }
    cout << mss2(a) << endl;
  }
}

Measured memory_bytes: 1384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int h, w;
	cin >> h >> w;
	vector<vector<char>> a(h, vector<char>(w));
	vector<vector<char>> x(h, vector<char>(w));
	vector<vector<char>> y(h, vector<char>(w));
	rep(i, h) {
		rep(j, w) {
			cin >> a[i][j];
			if (j == 0) {
				x[i][j] = '#'; y[i][j] = '.';
			}
			else if (j == w - 1) {
				x[i][j] = '.'; y[i][j] = '#';
			}
			else if (i % 2 == 0) {
				x[i][j] = '#'; y[i][j] = '.';
			}
			else {
				x[i][j] = '.'; y[i][j] = '#';
			}
			if (a[i][j] == '#') {
				x[i][j] = '#'; y[i][j] = '#';
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			cout << x[i][j];
		}
		cout << endl;
	}
	cout << endl;
	rep(i, h) {
		rep(j, w) {
			cout << y[i][j];
		}
		cout << endl;
	}
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
class DisjointSets
{
public:
    DisjointSets(const int v) : parent(v), rank(v, 0) { iota(parent.begin(), parent.end(), 0); }
    bool same(const int a, const int b) { return find(a) == find(b); }
    int find(const int a) { return parent[a] == a ? a : parent[a] = find(parent[a]); }
    void unite(int a, int b)
    {
        a = find(a), b = find(b);
        if (a == b) { return; }
        if (rank[a] < rank[b]) { swap(a, b); }
        if (rank[a] == rank[b]) { rank[a]++; }
        parent[b] = a;
    }

private:
    vector<int> parent, rank;
};
int main()
{
    int N, W, H;
    cin >> N >> W >> H;
    vector<vector<int>> h(H), v(W);
    bool w = false;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        if (x == 1 or x == W or y == 1 or y == H) { w = true; }
        h[y - 1].push_back(i), v[x - 1].push_back(i);
    }
    DisjointSets uf(N);
    for (int y = 0; y < H; y++) {
        for (int i = 1; i < h[y].size(); i++) { uf.unite(h[y][0], h[y][i]); }
    }
    for (int x = 0; x < W; x++) {
        for (int i = 1; i < v[x].size(); i++) { uf.unite(v[x][0], v[x][i]); }
    }
    vector<bool> used(N, false);
    int c = 0;
    for (int i = 0; i < N; i++) {
        if (used[uf.find(i)]) { continue; }
        used[uf.find(i)] = true, c++;
    }
    cout << (c == 1 ? N - 1 : w ? N + c - 2 : N + c - 1) << endl;
    return 0;
}



Measured memory_bytes: 9980
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    int n,c;
    cin >> n >> c;
    const int max_t = 2e5+1;
    vector<vector<int>> shows(c,vector<int>(max_t, 0));
    rep(i,n)
    {
        int si,ti,ci;
        cin >> si >> ti >> ci;
        si = si*2-1;
        ti = ti*2;
        rep2(j,si,ti)
            shows[ci-1][j] = 1;
    }

    int max_cnt = 0;
    rep(i,max_t)
    {
        int tmp_cnt = 0;
        rep(j,c)
            tmp_cnt += shows[j][i];
        max_cnt = max(max_cnt,tmp_cnt);
    }

    cout << max_cnt << endl;
    return 0;
}

Measured memory_bytes: 24576
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 3010;

bool dp[N][N];
int a, b, c, d, e, n;

int dx[4], dy[4];

int main(){
	scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &n);
	int X = a * 100, Y = 0;
	dx[0] = a, dx[1] = b;
	dy[2] = c, dy[3] = d;
	dp[0][0] = true;
	For(i, 0, n / 100) For(j, 0, n){
		For(u, 0, 3) if(i >= dx[u] && j >= dy[u])
			dp[i][j] |= dp[i - dx[u]][j - dy[u]];
		if(dp[i][j] && i * 100 + j <= n && i * e >= j && Y * (i * 100 + j) < (X + Y) * j) X = i * 100, Y = j;
	}
	printf("%d %d\n", X + Y, Y);
	return 0;
}

Measured memory_bytes: 384
/*Author - Shubham Gupta (@shubham107)*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;		typedef vector<int> vi;
typedef vector<vl> vvl;	  	typedef vector<vi> vvi;
typedef pair<ll, ll> pll;	typedef pair<int, int> pii;
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define MOD 998244353
#define F first
#define S second
#define pb push_back
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define INF	ll(1e18)
#ifdef SHUBHAM107
#include "../code-pieces/trace.h"
#else
#define trace(args...)
#endif

ll modpow(ll a, ll b, ll m = MOD) {
	a %= m; ll res = 1; while (b) {if (b & 1)res = res * a % m; a = a * a % m; b >>= 1;}
	return res;
}
ll bpow(ll a, ll b) {ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a) {return modpow(a, MOD - 2, MOD);}
void graph(vvi &adj, int m) {int x, y; forn(i, m) {cin >> x >> y; adj[x - 1].pb(y - 1); adj[y - 1].pb(x - 1);}}

const int mxN = 2e5;
ll fac[mxN+5], inv[mxN+5];
void pre(){
	fac[0] = 1;
	forne(i, mxN) fac[i] = (fac[i-1] * i) % MOD;
	inv[mxN] = modinv(fac[mxN]);
	rforn(i, mxN) inv[i] = (inv[i+1] * (i + 1)) % MOD;
	assert(inv[0] == 1 && inv[1] == 1);
}
ll ncr(ll n,ll r){
	if(r < 0 || r > n) return 0;
	ll ans = fac[n];
	ans = ans * inv[n-r] % MOD;
	ans = ans * inv[r] % MOD;
	return ans;
}

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	ll ans = 0;
	forn(i, k+1) ans += (ncr(n-1, i) * m) % MOD * modpow(m-1, n-1-i) % MOD, ans %= MOD;
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef SHUBHAM107
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
#endif
	int t = 1;
	pre();
	// cin >> t;
	while (t--) {
		solve();
	}
}


Measured memory_bytes: 6780
#include <bits/stdc++.h>//所有库
#define LL long long
using namespace std;
string s;
int a[11];
LL ans;
void dfs(int x,int y,LL k){
	LL q=0;
	for (int j=y;j<=x;j++){
		q=q*10+a[j];
		//cout<<a[j]<<" ";
		//cout<<q<<endl;		
	}
		if (x==s.length()-1){
		//	cout<<ans<<endl;
			ans+=q+k;return;	
		}
	for (int j=x+1;j<=s.length()-1;j++) dfs(j,x+1,k+q);
	return;
}
int main(){
	cin>>s;
	for (int i=0;i<=s.length()-1;i++) a[i]=((int)s[i])-48;
	for (int i=0;i<=s.length()-1;i++) dfs(i,0,0);	
	cout<<ans;
	
	return 0;
} 




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

int main(){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<int> s(N+1,0);
  for (int i = 1; i < N; i++){
    s[i+1] = s[i] + (S[i-1] == 'A' && S[i] == 'C');
  }
  for (int i = 0; i < Q; i++) {
    int l,r;
    cin >> l >> r;
    cout << s[r] - s[l] << endl;
  }
}
  

Measured memory_bytes: 1408
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var s = ReadLine();
        var k = ToInt32(ReadLine());
        var list = new List<string>();
        for(var i = 1; i <= k; i++)
        {
            for (var j = 0; j < s.Length - i + 1; j++)
            {
                var sub = s.Substring(j, i);
                if (!list.Contains(sub))
                    list.Add(sub);
            }
        }
        list.Sort();
        WriteLine(list[k-1]);
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


Measured memory_bytes: 13664
/** 
If comrades that you trust gather around you, hope can take physical form and become visible. That’s what I believe.
*/
#include <bits/stdc++.h>
using namespace std;
/**
(▀̿Ĺ̯▀̿ ̿) (ง ͠° ͟ل͜ ͡°)ง
*/
const int N = 2e5 + 7;
int g[N];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    int tt = clock();
    int n; cin >> n;
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        g[p]++;
    }
    for (int i = 1; i <= n; ++i) cout << g[i] << '\n';


    cerr << "TIME = " << (double) 1.0 * (clock() - tt) / CLOCKS_PER_SEC << " seconds" << endl;
	return 0;
}


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

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

    int count=0;

    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            count++;
        }
    }

    for(int i=0; i<m; i++){
        for(int j=i+1; j<m; j++){
            count++;
        }
    }

    cout<<count;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[100001], dp[100001];
int main(){
cin >> n;
for(int i = 0; i < n ;i++) cin >> a[i];
dp[1] = abs(a[0] - a[1]);
for(int i = 2; i < n; i++){
    dp[i] = min(abs(a[i] - a[i - 1]) + dp[i - 1], abs(a[i] - a[i - 2]) + dp[i - 2]);
}
cout << dp[n - 1];
}



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

int main() {
	int k, i, a[22], p, j, h=0;
	cin >> k;
	for (i = 0; i < 22;i++)
		a[i] = 0;
	for (i = 0; i < k; i++){
		p = 0;
		while (a[p] == 9 || (a[p] > a[p + 1] && p != h))
			p++;
		a[p]++;
		h = max(p, h);
		for (j = p - 1; j >= 0; j--)
			a[j] = max(0, a[j + 1] - 1);
	}
	p = 20;
	while(a[p]==0)
		p--;
	for (j = p; j >= 0;j--)
		cout << a[j];
	cout << endl;
}

Measured memory_bytes: 256
import math
import fractions
import collections
import itertools
N,K=map(int,input().split())
snu=[0]*N
for i in range(K):
    d=int(input())
    l=list(map(int,input().split()))
    for i in range(d):
        snu[l[i]-1]=snu[l[i]-1]+1
#print(snu)
cnt=0
for i in snu:
    if i==0:
        cnt=cnt+1
print(cnt)

Measured memory_bytes: 72892
#pragma region
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=1e9+7; constexpr int NIL = -1;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#pragma endregion
//-------------------
const int N = 50;
vector<ll> A(N+1);

int main(){
    cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15);
    
    ll k; cin >> k;

    ll cur = 1;
    for(int i=N-2; i>=0; i-=2) {
        A[i] = 49;
        A[i+1] = 49;
    }
        ll all =  k/N;
        ll part = k%N;
        rep(i,N) {
            A[i] += all;
        }
    rep(i,part) {
        A[i] += 50;
        rep(j,N) {
            if(j!=i) A[j] -= 1; 
        }
    }
    cout << N << endl;
    rep(i,N) cout << A[i] << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 3644
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>

#define int long long
#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define showp(n) cerr<<n.fs<<", "<<n.sc<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showsp(n) for(auto z:n){cerr<<z.fs<<" "<<z.sc<<", "}cerr<<endl

#define yes printf("Yes\n")
#define no printf("No\n")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using ull=unsigned long long;
using vi=vector<int>;
using pint=pair<int,int>;

const int INF=1LL<<55;

int a,b,c;
int x,y;

int kane = 0;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>a>>b>>c>>x>>y;
    c *= 2;

    if(x > y){
        //small=y, b
        if(c<a+b){
            if(c<a){ kane+=c*x; }
            else {
                kane+=c*y;
                kane+=a*(x-y);
            }
        }else{
            kane+=a*x;
            kane+=b*y;
        }
    }else if(x < y){
        //x,a
        if(c<a+b){
            if(c<b){ kane+=c*y; }
            else {
                kane+=c*x;
                kane+=b*(y-x);
            }
        }else{
            kane+=a*x;
            kane+=b*y;
        }
    }else{
        if(c<=a+b){
            kane=c*x;
        }else{
            kane+=a*x;
            kane+=b*y;
        }
    }
    cout<<kane<<endl;
    
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll h,d,a;
	cin>>h>>d>>a;
	d*=2;
	vector<pair<ll,ll>>ch;
	for(ll i=0;i<h;i++){
		ll x,y;
		cin>>x>>y;
		ch.push_back(make_pair(x,y));
	}
	sort(ch.begin(),ch.end());
	queue<pair<ll,ll>>q;
	ll at=0;
	ll cnt=0;
	for(ll i=0;i<h;i++){
		ll nowx=ch[i].first;
		if(q.size()!=0){
			ll nexx=q.front().first;
			while(nowx>nexx&&q.size()!=0){
				ll nexa=q.front().second;
				at-=nexa;
				q.pop();
				if(q.size()!=0){
					nexx=q.front().first;
				}
			}
		}
		ll nowh=ch[i].second;
		if(at<nowh){
			ll tu=(nowh-at+a-1)/a;
			cnt+=tu;
			at+=tu*a;
			q.push(make_pair(nowx+d,tu*a));
		}
	}
	cout <<cnt;
}

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

int a[20];

int main(){
	int n;
	scanf("%d", &n);
	int maxj = 0;
	int sum = 0;
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		maxj = max(maxj, a[i]);
		sum += a[i];
	}
	sum -= maxj;
	printf(sum > maxj ? "Yes" : "No");
	return 0;
}


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

int main() {
    long long N;
    cin >> N;
    long long ans = 0;

    for (int i = 1; i < (N + 1); i++) {
        int b = N / i;
        if (N % i == 0) {
            ans = ans + b - 1;
        }
        else {
            ans = ans + b;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

int n,Ans;
inline int dig(int X)
{
	int sum=0;
	while(X) sum+=X%10,X/=10;
	return sum;
}
int main()
{
	Ans=0x3fffffff;
	cin >> n;
	for(int i=1;i<n;i++)
		Ans=min(Ans,dig(i)+dig(n-i));
	cout << Ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
    #include <filesystem>
    namespace fs = std::filesystem;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;
using ll = long long int;

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N;
vector<string> S;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path __p = __FILE__;
        fs::path __input, __output;
        __input = __output = __p.parent_path();
        __input += string("/input/") + string(__p.stem()) + string(".txt");
        __output += string("/output/") + string(__p.stem()) + string(".txt");
        freopen(__input.c_str(), "r", stdin);
        freopen(__output.c_str(), "w", stdout);
    #endif
    cin >> N;
    for (int i = 0; i < N; i++)
    {
      string s; cin >> s;
      S.push_back(s);
    }   
}

int count_AB(string t){
  int ret=0;
  for (int i = 0; i < t.length()-1; i++) if(t[i]=='A' && t[i+1]=='B') ret++;
  return ret;  
}

int solve(){
  int ans=0;
  int cntA=0,cntB=0;
  int cnt=0;
  for (int i = 0; i < N; i++)
  {
    ans+=count_AB(S[i]);
    cnt  += (S[i][S[i].length()-1]=='A') && (S[i][0]=='B');
    cntA += (S[i][S[i].length()-1]=='A') && !(S[i][0]=='B');
    cntB += !(S[i][S[i].length()-1]=='A') && (S[i][0]=='B');
  }
  ans += max(cnt-1,0);
  if(cnt>0) {
    if(cntA>0) {ans++; cntA--;}
    if(cntB>0) {ans++; cntB--;}
  }
  ans += max(0,min(cntA,cntB));
  cout << ans << endl;
  

  return 0;
}   

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


Measured memory_bytes: 768
def in_rectangle(w,h,x,y,r):
    if (0<=x-r<=w) and (0<=y-r<=h) and (0<=x+r<=w) and (0<=y+r<=h):
        return True
    else:
        return False
w,h,x,y,r=map(int,input().split())
if (in_rectangle(w,h,x,y,r)==True):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 5600
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
	    
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int count = 0;
		
		while(a <= b){
			if(c % a == 0){
				count++;
			}
			a++;
		}
		System.out.println(count);
	}
}


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

int main() {
   char s[20], t[20];
   
   scanf("%s %s", s, t);

   int x = strlen(s);
   
   for(int i = 0; i < x; i++){
       if(s[i] != t[i]){
          printf("No\n");
          return 0;
       }
   }
   printf("Yes\n");
}


Measured memory_bytes: 1628
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep1(i, n) for(int i=1; i<=(int)(n); i++)
#define reprange(i, a) for(int i : vector<int>a)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> wi;
typedef vector<ll> vl;
const ll inf=1LL << 60;
const ll mod=1e9+7;

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

  int n;
  cin >> n;

  int ans=0;
  rep1(a, n){
    int b=n/a;
    if(n%a==0)ans--;
    ans+=b;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3624
# 2019/10/10

class unionfind():
    def __init__(self,n):
        self.par=list(range(n+1))
        self.rank=[0]*(n+1)
        self.groups=n
    
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def is_same(self,x,y):
        return self.find(x)==self.find(y)
    
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
        if x!=y:self.groups-=1

n,m=map(int,input().split())

uf=unionfind(n)

for i in range(m):
    x,y,z=map(int,input().split())
    uf.unite(x,y)
print(uf.groups)

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

using namespace std;

const int mod = 1e9 + 7;

int main()
{
  int n;
  cin >> n;
  map<int, int> m;
  for (int i = 0; i < n; i++)
  {
    int a;
    cin >> a;
    m[a]++;
  }
  bool ok = true;
  if (n % 2 == 1 && m[0] != 1)
    ok = false;
  for (pair<int, int> t : m)
    if ((n - 1 - t.first) % 2 != 0 || (t.first != 0 && t.second != 2))
      ok = false;
  long long ans = 1;
  for (int i = 0; i < n / 2; i++)
  {
    ans *= 2;
    ans %= mod;
  }
  cout << (ok ? ans : 0) << endl;

  return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int main(int argc, char* argv[])
{
  int n;
  cin >> n;
  vector<vector<int>> tree(n, vector<int>());
  vector<pair<int, int>> edges(n-1);
  rep(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
    edges[i] = make_pair(a, b);
  }

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

  vector<int> nodes(n, -1);
  queue<int> que;

  nodes[0] = c.back(); c.pop_back();
  que.push(0);

  while (!que.empty()) {
    int v = que.front(); que.pop();
    for (int nv : tree[v]) {
      if (nodes[nv] != -1) continue;
      nodes[nv] = c.back(); c.pop_back();
      que.push(nv);
    }
  }

  int ans = 0;
  rep(i, n-1) {
    auto p = edges[i];
    ans += min(nodes[p.first], nodes[p.second]);
  }

  cout << ans << endl;

  rep(i, n) {
    cout << nodes[i] << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 1152
from math import cos, pi
a, b, h, m = map(int, input().split())
t = h*60+m

a_rad = ((t/(60*12)) - int(t/(60*12))) * (2*pi)
b_rad = ((t/(60)) - int(t/(60))) * (2*pi)
rad = abs(a_rad-b_rad)
ans = a**2+b**2 - 2*a*b*cos(rad)
print(ans**0.5)

Measured memory_bytes: 9528
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define fr1(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vii vector <pair<ll,ll> >
#define viii vector <pair<ll,pair<ll,ll> > >
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define mp(i,j) make_pair(i,j)
#define fi first
#define se second
#define input(a,n) fr(i,0,n)cin>>a[i]
#define output(a,n) fr(i,0,n)cout<<a[i]<<endl
#define dbg cout<<"hurr"<<endl;
#define dbg2 cout<<"hurr2"<<endl;
#define md 1000000007
#define inf 999999999999999999
#define sp << " " <<
#define endl "\n"
#define pi 3.14159265358979323846
#define fixd(x) cout << fixed << setprecision(x);
#define sz size()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
bool compare(pair<ll,ll> p1,pair<ll,ll> p2){
return p1.se>p2.se;
}
ll nc2(ll n){
return (n*(n-1))/2;
}
void solve(){
ll n,m;
cin>>n>>m;
cout<<nc2(n)+nc2(m)<<endl;
}
int main()
{   fast;
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 256
#include <stdint.h>

#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

struct Entry {
  int weight;
  int value;
};

int max_value_with_capacity[10000 + 2];

int main(int argc, char *argv[]) {
  int N, W;
  std::cin >> N >> W;
  std::vector<Entry> list;

  for (int i = 0; i < N; i++) {
    int v, w;
    std::cin >> v >> w;
    list.push_back({w, v});
  }
  int value_sum = 0;
  for(int i = 1; i <= W; i++){
    max_value_with_capacity[i] = max_value_with_capacity[i - 1];
    for (auto &e : list) {
      if(i < e.weight) continue;
      max_value_with_capacity[i] = std::max(max_value_with_capacity[i - e.weight] + e.value, max_value_with_capacity[i]);
    }
  }
  std::cout << max_value_with_capacity[W] << std::endl;

  return 0;
}



Measured memory_bytes: 3168
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using vi = vector<int>;

#define in(v) v; cin >> v;
void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rrep(i,n) for(long long i=(n);i>=0;--i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

// ========== debug ==========
template<class T>ostream& operator<<(ostream& os,const vector<T>& vec){os<<"{";for(size_t i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
ostream& operator<<(ostream& os,const vector<char>&v){for(size_t i=0;i<v.size();++i)os<<v[i];return os;}
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>& rhs){os<<"("<<rhs.first<<", "<<rhs.second<<")";return os;}

#ifdef LOCAL
void debug() {cerr << "\n";}
template<class First> void debug(const First& first) {cerr<<first<<"\n";}
template<class First, class... Rest> void debug(const First& first, const Rest&... rest) {cerr<<first<<",";debug(rest...);}
void debug2() {cerr << "\n";}
template<class First> void debug2(const First& first) {cerr<<first<<" ";}
template<class First, class... Rest> void debug2(const First& first, const Rest&... rest) {cerr<<first<<" ";debug2(rest...);}
#else
#define debug(...) 42
#define debug2(...) 42
#endif
// ===========================

int main() {
  int N;
  ins(N);

  vi A(N), B(N);
  rep(i, N) {
    cin >> A[i] >> B[i];
  }
  all(sort, A);
  all(sort, B);
  if (N % 2 == 1) {
    cout << B[N/2] - A[N / 2] + 1 << endl;
  } else {
    cout << ((B[N/2-1] + B[N/2]) - (A[N / 2-1] + A[N / 2])) + 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
using namespace std;
long long oddsolve(long long a){return (a+1)/2%2;}
long long    solve(long long a){if(a%2==0){ return
          oddsolve(a+1)^(a+1);}
          else return oddsolve(a);}
int main(){
long long a, b;
cin>>a>>b;
cout<<(solve(b)^solve(a-1))<<endl;}


Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007&lang=jp
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <numeric>
#include <functional>

#define rep(i,n) for(int i=0;i<n;i++)
#define scanInt(i) scanf("%d", &i)

using namespace std;


int main(){

	int init = 100000;
	double r = 1.05;

	int n;
	scanInt(n);
	rep(i,n){
		init *= r;
		if(init % 1000 != 0){
			int a = init / 1000;
			a+=1;
			init = a*1000;
		}
	}
	printf("%d\n", init);

	return 0;
}

Measured memory_bytes: 3140
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = [-i for i in LIST()]
heapify(a)
for i in range(m):
    b = heappop(a)
    b = - (- b // 2)
    heappush(a, b)
print(-sum(a))

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

#include <bits/stdc++.h>
using namespace std;

constexpr ll INF = 1e15;

constexpr ll mod = 1e9 + 7;

template<typename T>
void cmpmax(T& reference, T value) {
	reference = max(reference, value);
}

template<typename T>
void cmpmin(T& reference, T value) {
	reference = min(reference, value);
}

int main() {
	int n;
	cin >> n;
	vector<int> as(n);
	vector<int> counts(4, 0);
	rep(i, n) {
		cin >> as[i];
		counts[as[i]]++;
	}

	vector<vector<vector<double>>> dp(n + 10, vector<vector<double>>(n + 10, vector<double>(n+10, 0)));
	
	//dp[i][j][k]...1枚の皿がi個、2枚の皿がj個、3枚の皿がk個のときに、必要な手数の期待値
	//dp[i][j][k] = (n-i-j-k) / n * dp[i][j][k] + i / n * dp[i-1][j][k] + j / n * dp[i+1][j-1][k] + k / n * dp[i][j+1][k-1] + 1
	//(i+j+k)/n * dp[i][j][k] = i / n * dp[i-1][j][k] + j / n * dp[i+1][j-1][k] + k / n * dp[i][j+1][k-1] + 1

	dp[0][0][0] = 0;
	const double dn = n;
	rep(k, counts[3] + 1) {
		rep(j, n + 1) {
			if (k + j> n) continue;
			rep(i, n + 1) {
				if (i == 0 && j == 0 && k == 0) continue;
				if (i + j + k > n) continue;
				double right = dn;
				if (i > 0) right += i * dp[i - 1][j][k];
				if (j > 0) right += j * dp[i + 1][j - 1][k];
				if (k > 0) right += k * dp[i][j + 1][k - 1];
				right /= (i + j + k);
				dp[i][j][k] = right;
			}
		}
	}
	cout << setprecision(10) << dp[counts[1]][counts[2]][counts[3]] << endl;
	return 0;
}


Measured memory_bytes: 237696
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int INF = 1e9 + 7;
int main()
{
	SPEED
	int n, k;
	cin >> n >> k;
	int ht[n];
	for (int i = 0; i < n; ++i)
		cin >> ht[i];
	int dp[n];		//keeps track of cost
	for (int i = 1; i < n; ++i)
		dp[i] = INF;
	dp[0] = 0;
	for (int i = 0; i < n; ++i)
	{
		int j = 1;
		while(j<=k && i+j<n)
		{
			dp[i+j] = min(dp[i+j], dp[i] + abs(ht[i]-ht[i+j]));
			j++;
		}
	}
	cout << dp[n-1];
	return 0;
}

Measured memory_bytes: 1024
package main

import (
	"fmt"
	"strings"
)

func main() {
	var h, w int
	fmt.Scan(&h, &w)
	ss := make([]string, h)
	for i := range ss {
		fmt.Scan(&ss[i])
	}
	fmt.Println(strings.Repeat("#", w+2))
	for _, s := range ss {
		fmt.Printf("#%s#\n", s)
	}
	fmt.Println(strings.Repeat("#", w+2))
}


Measured memory_bytes: 640
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-03-17 13:16:17
*/

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)
#define MOD 1000000007

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

LL modpower(LL n, LL m, LL mod) {
    if (m == 0) {
        return 1;
    } else if (m % 2 == 0) {
        LL p = modpower(n, m/2, mod);
        return p*p % mod;
    } else {
        return n*modpower(n, m-1, mod) % mod;
    }
}

LL modinv(LL n, LL mod) {
    return modpower(n, mod-2, mod);
}

LL modcombination(LL n, LL r, LL mod) {
    LL ret = 1;

    for (int i = 0; i < r; i++) {
        ret *= (n-i);
        ret %= mod;
        ret *= modinv(i+1, mod);
        ret % mod;
    }

    return ret % mod;
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    string s;
    cin >> s;

    int n = s.length();
    char c[4] = {'A', 'C', 'G', 'T'};
    int m, temp;
    m = temp = 0;
    for (int i = 0; i < n; i++) {
        int found = 0;
        for (int j = 0; j < 4; j++) {
            if (s[i] == c[j]) {
                found = 1;
            }
        }

        if (found) {
            temp++;
        } else {
            if (m < temp) {
                m = temp;
            }

            temp = 0;
        }
    }

    if (m < temp) m = temp;

    cout << m << endl;

    return 0;
}


Measured memory_bytes: 256
/* {{{ Shinobu kawaii */
/*
  ______   __        _                  __                 
.' ____ \ [  |      (_)                [  |                
| (___ \_| | |--.   __   _ .--.   .--.  | |.--.   __   _   
 _.____`.  | .-. | [  | [ `.-. |/ .'`\ \| '/'`\ \[  | | |  
| \____) | | | | |  | |  | | | || \__. ||  \__/ | | \_/ |, 
 \______.'[___]|__][___][___||__]'.__.'[__;.__.'  '.__.'_/ 

*/
/* }}} */

#include <bits/stdc++.h>
using namespace std;

// #define int long long

/* cpp template {{{ */

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;
typedef double D;
typedef complex<D> P;

/* const */
const int INF = 999999999;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; std::cin >> x; return x;}
template <typename T> void print(T x) { std::cout << x << '\n'; }
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << '\n';
}

/* }}} */

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n = in();
  int ans = 0;
  RREP(i, n) ans += i;
  print(ans);

  return 0;
}



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

int main(){
	int n, in;
	ll calcNumOfCombination(ll n, int r);
	cin >> n;
	vector<ll> add(n, 0);
	map<ll, ll> m;
	m[0]++;
	rep(i, n){
		cin >> in;
		add.at(i) = in;
		if(i != 0) add.at(i) += add.at(i-1);
		m[add.at(i)]++;
	}
	
	ll ans = 0;
	for(auto p : m){
		if(p.second > 1){
			ans += calcNumOfCombination(p.second, 2);
		}
	}
	cout << ans << endl;
	
	return 0;
}


ll calcNumOfCombination(ll n, int r){
	ll num = 1;
	for(int i = 1; i <= r; i++){
		num = num * (n - i + 1) / i;
	}
	return num;
}

Measured memory_bytes: 14336
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  GI(N);
  vector<int> dp(3);
  FOR(i, N) {
    vector<int> new_dp(3);
    GI3(a, b, c);
    new_dp[0] = max(dp[1], dp[2]) + a;
    new_dp[1] = max(dp[0], dp[2]) + b;
    new_dp[2] = max(dp[0], dp[1]) + c;
    dp = new_dp;
  }
  print(*max_element(ALL(dp)));
  return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

#define U1 unsigned char
#define S1 char
#define	S4 int
#define DU double

S4 main()
{
	S4 s4_t_scanfRtn;
	S4 s4_t_studentNum;
	DU du_t_weight;
	DU du_t_height;
	DU du_t_BMI;

	U1 u1_t_delimiter;
	
	while (1)
	{
		s4_t_scanfRtn = scanf("%d,%lf,%lf%c", &s4_t_studentNum, &du_t_weight, &du_t_height, &u1_t_delimiter);
		
		/* 終了条件 */
		if (s4_t_scanfRtn == (S4)EOF)
		{
			break;
		}

		/* BMIの計算 */
		du_t_BMI = du_t_weight / (du_t_height * du_t_height);

		if (du_t_BMI >= (DU)25.0)
		{
			printf("%d\n", s4_t_studentNum);
		}
	}
	return((S4)0);
}



Measured memory_bytes: 2036