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

#define I inline
#define fi first
#define se second
#define R register
#define LL long long
#define mp make_pair
#define reg register int
#define pii pair<int,int>
#define fo(i, a, b) for(reg i = a; i <= b; i++)
#define fd(i, a, b) for(reg i = a; i >= b; i--)
#define cr const reg&
using namespace std;

I int _max(cr x, cr y) {return x > y ? x : y;}
I int _min(cr x, cr y) {return x < y ? x : y;}
I int read() {
	reg x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return x * f;
}
I void ptt(LL x) {if(x >= 10) ptt(x / 10); putchar(x % 10 + '0');}
I void put(LL x) {x < 0 ? putchar('-'), ptt(-x) : ptt(x);}
I void pr1(LL x) {put(x), putchar(' ');}
I void pr2(LL x) {put(x), puts("");}

char ss[101];
int s[26];

int main() {
	reg n = read(), m = read();
	fo(i, 1, n) {
		scanf("%s", ss + 1);
		fo(j, 1, m) s[ss[j] - 'a']++;
	} reg s1 = 0, s2 = 0, s3 = 0;
	s1 = (n / 2) * (m / 2);
	if(n & 1) s2 += m / 2;
	if(m & 1) s2 += n / 2;
	if((n & 1) && (m & 1)) s3++;
	reg tt = 0;
	fo(i, 0, 25) {
		if(s[i] & 1) s[i]--, tt++;
	} if(s3 == 0 && tt > 0) {puts("No"); return 0;}
	if(s3 == 1 && tt > 1) {puts("No"); return 0;}
	tt = 0;
	fo(i, 0, 25) {
		if(s[i] % 4 == 2) tt++, s[i] -= 2;
	} if(tt > s2) {puts("No"); return 0;}
	s2 -= tt; if(s2 & 1) {puts("No"); return 0;}
	puts("Yes");
	return 0;
}



Measured memory_bytes: 384
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    ni = i + 1
    ruiseki = [0] * (k + 1)
    pre = 0
    for j in range(k + 1):
        ruiseki[j] += pre
        ruiseki[j] += dp[i][j]
        pre = ruiseki[j]
        dp[ni][j] += ruiseki[j]
        if j - A[i] > 0:
            dp[ni][j] -= ruiseki[j - A[i] - 1]
        dp[ni][j] %= mod
print(dp[n][k])


Measured memory_bytes: 135768
#include <cmath>
#include <iostream>

using namespace std;

#define list_zero(p, n)                                                        \
    for(int i = 0; i < n; i++)                                                 \
        p[i] = 0;

#define hbreak(input) (int)(input / 100);
#define digit(input) (int)(1 + log10(input));

int list_sum(int *p, int n) {
    int sum;
    for(int i = 0; i < n; i++)
        sum = p[i];
    return sum;
}

int main() {
    int h[6] = {0, 0, 0, 0, 0, 0};
    int input;
    int sum, list_sum_temp;
    cin >> input;

    int max = input / 100;

    for(h[0] = 0, list_sum_temp = list_sum(h, 6);
        h[0] <= (1 + max - list_sum_temp); h[0]++) {
        for(h[1] = 0, list_sum_temp = list_sum(h, 6);
            h[1] <= (1 + max - list_sum_temp); h[1]++) {
            for(h[2] = 0, list_sum_temp = list_sum(h, 6);
                h[2] <= (1 + max - list_sum_temp); h[2]++) {
                for(h[3] = 0, list_sum_temp = list_sum(h, 6);
                    h[3] <= (1 + max - list_sum_temp); h[3]++) {
                    for(h[4] = 0, list_sum_temp = list_sum(h, 6);
                        h[4] <= (1 + max - list_sum_temp); h[4]++) {
                        for(h[5] = 0, list_sum_temp = list_sum(h, 6);
                            h[5] <= (1 + max - list_sum_temp); h[5]++) {
                            sum = h[0] * 100 + h[1] * 101 + h[2] * 102 +
                                  h[3] * 103 + h[4] * 104 + h[5] * 105;
                            // cout << h[0] << h[1] << h[2] << h[3] << h[4] <<
                            // h[5]
                            //      << endl;
                            // cout << summ << endl;
                            if(input == sum) {
                                // cout << h[0] << ',' << h[1] << ',' << h[2]
                                //      << ',' << h[3] << ',' << h[4] << ','
                                //      << h[5] << endl;
                                cout << '1' << endl;
                                return 0;
                            }
                        }
                        h[5] = 0;
                    }
                    h[4] = 0;
                }
                h[3] = 0;
            }
            h[2] = 0;
        }
        h[1] = 0;
    }
    cout << '0' << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class A implements Comparable<A>{
    long v;
    int l,r;
    A(long v,int l,int r){
        this.v=v;
        this.l=l;
        this.r=r;
    }
    @Override
    public int compareTo(A o){
        return Long.compare(v,o.v);
    }
    @Override
    public String toString(){
        return v+":"+l+"-"+r;
    }
}

class Main {
    static final boolean DEBUG=false;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int[]p=new int[n];
        for(int i=0;i<n;++i)p[i]=Integer.parseInt(scan.next());
        MinSegmentTree m0=new MinSegmentTree();
        MinSegmentTree m1=new MinSegmentTree();
        Queue<A> q=new PriorityQueue<A>();
        for(int i=0;i<n/2;++i){
            m0.update(i,(long)p[2*i]<<32|i);
            m1.update(i,(long)p[2*i+1]<<32|i);
        }
        long[]ans=new long[n];
        int ansp=0;
        q.add(new A(m0.query(0,n/2),0,n));
        while(q.size()>0){
            if (DEBUG){
                System.err.println("que="+q);
            }
            A t=q.poll();
            long v=t.v;
            int l=t.l;
            int r=t.r;
            int fi=(int)v;
            if(l%2==0)
                fi=fi*2;
            else
                fi=fi*2+1;
            if(l>=r)continue;
            long s;
            if(l%2==0)
                s=m1.query(fi/2,r/2);
            else
                s=m0.query(fi/2+1,r/2+1);
            ans[ansp]=v>>>32;
            ans[ansp+1]=s>>>32;
            ansp+=2;
            int si=(int)s;
            if(l%2==0){
                si=si*2+1;
            }else{
                si=si*2;
            }
            if(DEBUG){
                System.err.println("ans:"+ans[ansp-2]+" "+ans[ansp-1]);
                System.err.println("fi="+fi+" si="+si);
            }
            if(l<fi)
                q.add(new A((l%2==0?m0:m1).query(l/2,fi/2),l,fi));
            if(fi+1<si)
                q.add(new A((l%2==0?m1:m0).query((fi+1)/2,si/2),fi+1,si));
            if(si+1<r)
                q.add(new A((l%2==0?m0:m1).query((si+1)/2,r/2),si+1,r));
        }
        for(int i=0;i<n;++i)
            System.out.print(ans[i]+(i==n-1?"\n":" "));
    }
}
class MinSegmentTree {
    static final int SIZE = 1 << 18;
    static final long INFINITY = (1L << 62) - 1;
    long[] seg;
    MinSegmentTree() {
	this.seg = new long[2 * SIZE];
    }
    void update(int x, long value) {
	x += SIZE - 1;
	this.seg[x] = value;
	while (x > 0) {
	    x = (x - 1) / 2;
	    this.seg[x] = Math.min(this.seg[2 * x + 1], this.seg[2 * x + 2]);
	}
    }
    long query(int l, int r) {
	l += SIZE - 1;
	r += SIZE - 1;
        long y = INFINITY;
	while (l < r) {
	    if ((l & 1) == 0) {
		y = Math.min(y, this.seg[l]);
	    }
	    if ((r & 1) == 0) {
		y = Math.min(y, this.seg[r - 1]);
	    }
	    l /= 2;
	    r = (r - 1) / 2;
	}
	return y;
    }
}


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

int main(){
  ll n;
  cin >> n;
  if(n % 2 == 0){
    vector<ll> a(n/2);
    vector<ll> b(n/2);
    rep(i,n){
      if(i % 2 == 0) cin >> a[i/2];
      else cin >> b[i/2];
    }
    reverse(b.begin(),b.end());
    rep(i,n/2){
      cout << b[i] << " ";
    }
    rep(i,n/2){
      cout << a[i] << " ";
    }
    cout << endl;
  }
  else{
    vector<ll> a((n+1)/2);
    vector<ll> b(n/2);
    rep(i,n){
      if(i % 2 == 0) cin >> a[i/2];
      else cin >> b[i/2];
    }
    reverse(a.begin(),a.end());
    rep(i,(n+1)/2){
      cout << a[i] << " ";
    }
    rep(i,n/2){
      cout << b[i] << " ";
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    ll n,k,d;
    cin>>n>>k>>d;
    n=llabs(n);
    ll req=n/d;
    if(n%d)
        req++;
    if(req>k)
    {
        n=llabs(n);
        n-=(d*k);
    }
    else{
        n-=(d*req);
        k-=req;
        ll x=llabs(n);
        ll y=llabs(n+d);
        if(k%2)
            n=y;
        else
            n=x;
    }



    cout<<n<<endl;


    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N, X;
        cin >> N >> X;
        vll m(N);
        rep(i, 0, N) cin >> m[i];
        X -= accumulate(all(m), 0LL);
        ll ans = N;
        ans += X / *min_element(all(m));
        cout << ans << endl;
}

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

int main(){
 ll n,a,b,ans;
 cin >> n >> a >> b;
 if(a == 0){
   cout << "0" << endl;
   return 0;
 }
 ans = (n/(a+b))*a;
 if(n%(a+b) < a) ans += n%(a+b);
 else ans += a;
 cout << ans << endl;
 return 0;
}


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

    signed main() {
        int h,w,k;
        cin>>h>>w>>k;
        string s[h];
        for(int i=0;i<h;i++)cin>>s[i];
        int p[h][w],si,sj;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(s[i][j]=='S'){
                    si=i;sj=j;
                }
            }
        }
        queue<pair<int,int>> que1,que2;
        que1.push(make_pair(si,sj));
        int ans=min(min(si,sj),min(h-1-si,w-1-sj));
        for(int i=0;i<=k;i++){
            while(!que1.empty()){
                if(s[que1.front().first][que1.front().second]=='#'){
                    que1.pop();
                    continue;
                }
                s[que1.front().first][que1.front().second]='#';
                si=que1.front().first;sj=que1.front().second;
                ans=min(ans,min(min(si,sj),min(h-1-si,w-1-sj)));
                if(si>0)que2.push(make_pair(si-1,sj));
                if(si<h-1) que2.push(make_pair(si+1,sj));
                if(sj>0)que2.push(make_pair(si,sj-1));
                if(sj<w-1)que2.push(make_pair(si,sj+1));
                que1.pop();
            }
            swap(que1,que2);
        }
       // cerr<<ans;
        if(ans==0)cout<<1;
        else cout<<1+(ans-1)/k +1;
    }


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()
#define vprint(v) for(auto e:v){cout<<e<<" ";};cout<<endl;
#define vvprint(vv) for(auto v:vv)vprint(v);

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);

    ll N, M;
    cin >> N >> M;

    vll A(M), B(M);
    rep(i, M) cin >> A[i] >> B[i];

    vector<unordered_set<ll>> e(N);
    rep(i, M){
        e[A[i]-1].insert(B[i]-1);
        e[B[i]-1].insert(A[i]-1);
    }
    vll c(N, -1);

    queue<ll> q;
    q.push(0);
    while(!q.empty()){
        ll v = q.front();
        q.pop();
        for(ll nv : e[v]){
            if(c[nv]<0){
                q.push(nv);
                c[nv] = v;
            }
        }
    }

    cout << "Yes" << endl;
    REP(i, 1, N){
        cout << c[i]+1 << endl;
    }
}


Measured memory_bytes: 31084
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
/*
using ll = long long;
using P = pair<int, int>;
*/
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1e9;

int a[205];
int dp[1000005];
int dp2[1000005];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> odd;
    rep(i,200){
        a[i] = i*(i+1)*(i+2)/6;
        if(a[i]%2 == 1) odd.push_back(a[i]);
    }
    rep(i,1000001){
        dp[i] = INF;
        dp2[i] = INF;
    }
    dp[0] = 0;
    dp2[0] = 0;
    rep(i,200)rep(j,1000001){
        if(j+a[i] > 1000000) break;
        chmin(dp[j+a[i]], dp[j]+1);
    }
    rep(i,odd.size())rep(j,1000001){
        if(j+odd[i] > 1000000) break;
        chmin(dp2[j+odd[i]], dp2[j]+1);
    }
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;
        cout << dp[n] << " " << dp2[n] << endl;
    }
    return 0;
}


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

int main(void)
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    int x{0};
    int max{0};
    for(int i{0}; i<N; ++i){
        if(S[i]=='I')
            ++x;
        else
            --x;
        if(x>max)
            max = x;
    }
    cout << max << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1e9 + 1;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793;

int main(){
  int n;
  cin >> n;
  int ans;
  rep(i, 8){
    ans = pow(2, i);
    if(ans > n){
      ans = ans/2;
      break;
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
int a[MAX],N;

int main(){
  int N,M,a,b;
  set<int> Sa,Sb;
  cin >> N >> M;
  for(int i=0;i<M;i++){
    cin >> a >> b;
    if(a==1)Sb.insert(b);
    if(b==N)Sa.insert(a);
  }
  for(set<int>::iterator it = Sa.begin();it!=Sa.end();it++){
    if(Sb.end()!=Sb.find(*it)){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
		using namespace std;
		#define ll long long
		#define endl "\n"
		void solve();
		int main()
		{
			ios_base::sync_with_stdio(false);
			cin.tie(NULL);

		/*#ifndef ONLINE_JUDGE
			freopen("input.txt","r",stdin);
			freopen("output.txt","w",stdout);
		#endif*/
		
			int t=1;
			//cin>>t;
			while(t--){
			solve();
			cout << endl;
			}

			cerr << "time taken : "	<< (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
			return 0;		
		}
		void solve(){
			int k,s,ans=0;
			cin>>k>>s;
			for(int x=0;x<=k;x++){
				for(int y=0;y<=k;y++){
					int z=s-x-y;
					if(z>=0 && z<=k){
						ans++;
					}	
				}
			}
			cout<<ans;
		}
	

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

int main()
{
    ll n, m;
    cin >> n >> m;
    priority_queue<ll> A;
    rep(i, n)
    {
        ll a;
        cin >> a;
        A.push(a);
    }
    while (m--) {
        ll buf = A.top() / 2;
        A.pop();
        A.push(buf);
    }
    ll sum = 0;

    rep(i, n)
    {
        sum += A.top();
        A.pop();
    }
    cout << sum << endl;
}



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

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


Measured memory_bytes: 3112
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> PA;
int main(){
  int w,h,maze[61][61];
  while(1){
    scanf("%d %d",&w,&h);
    if(w==0&&h==0) break;
    fill_n(*maze,61*61,0);
    for(int i=0;i<h*2-1;i++){
      for(int j=0;j<w*2-1;j++){
	if( (i+j)%2 == 1) scanf(" %d",&maze[i][j]);
      }
    }
    queue<PA> que;
    int dx[4] = {2,-2,0,0};
    int dy[4] = {0,0,2,-2};
    que.push(PA(0,0));
    maze[0][0] = 1;
    while(!que.empty()){
      PA p = que.front();
      que.pop();
      for(int i=0;i<4;i++){
	int y = p.first + dy[i];
	int x = p.second + dx[i];
	int wy = p.first + dy[i]/2;
	int wx = p.second + dx[i]/2;
	if(x<0||y<0||x>=w*2-1||y>=h*2-1||maze[y][x]!=0||maze[wy][wx]==1)
	  continue;
	maze[y][x] = maze[p.first][p.second]+1;
	que.push(PA(y,x));
      }
    }
    printf("%d\n",maze[h*2-2][w*2-2]);
  }
  return (0);
}

Measured memory_bytes: 2760
#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x)      x.begin(), x.end()
#define rep(i,n)    for (i64 i = 0; i < (n); ++i)
#define reps(i,s,t) for (i64 i = (s); i <= (t); ++i)
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? (a=b,1) : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? (a=b,1) : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}}

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

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

    const int N = s.length();

    bool ok = (s == t);
    rep(i, N) {
        if (ok) break;

        const auto tmp = s.front();
        rep(i, N-1) {
            s[i] = s[i+1];
        }
        s.back() = tmp;

        ok |= (s == t);
    }

    puts(ok ? "Yes" : "No");

    return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]

for i in range(N-2):
    if D[i][0] == D[i][1]:
        if D[i+1][0] == D[i+1][1]:
            if D[i+2][0] == D[i+2][1]:
                print("Yes")
                exit()

print("No")


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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	
	int M, K;
	cin >> M >> K;
	int n = 1<<M;
	if(K >= n || K == 1 && M == 1) {
		cout << "-1";
	} else if(K == 0) {
		for(int i = 0; i < n; i++) {
			cout << i << " " << i << " ";
		}
	} else {
		cout << "0 " << K << " 0 ";
		for(int i = 1; i < n; i++) {
			if(i == K) continue;
			cout << i << " ";
		}
		cout << K << " ";
		for(int i = n-1; i > 0; i--) {
			if(i == K) continue;
			cout << i << " ";
		}
	}
	cout << "\n";
	return 0;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<pair<int,int>> arms;
    for (int i=0;i<m;++i){
        int x,y; cin >> x >> y;
        arms.emplace_back(x,--y);
    }
    sort(arms.begin(),arms.end());
    vector<int> L(n),R(n);
    iota(L.begin(),L.end(),0);
    iota(R.begin(),R.end(),0);
    for (int i=0;i<m;++i){
        int y=arms[i].second;
        L[y+1]=L[y]; R[y]=R[y+1];
    }
    for (int i=0;i<n;++i) cout << R[i]-L[i]+1 << (i+1==n?'\n':' ');
}


Measured memory_bytes: 5488
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

while True:
    N, S = raw_input().split()
    if N == "0" and S == "0":
        break
    N = int(N)
    m = {}
    def func(index, num, lst):
        if index == len(S):
            if num in m:
                m[num] = ["rejected"]
            else:
                m[num] = list(lst)
            return
        for i in range(index + 1, len(S) + 1):
            p = int(S[index:i])
            lst.append(str(p))
            func(i, num + p, lst)
            lst.pop()
    func(0, 0, [])
    score = -1
    ans = []
    for key in m:
        if score < key and key <= N:
            score = key
            ans = " ".join(m[key])
    if score == -1:
        print "error"
    elif ans == "rejected":
        print ans
    else:
        print str(score) + " " + ans
    pass


Measured memory_bytes: 5036
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define INF 2147483647
vector<pair<int,int> > a(300000,pair<int,int>(INF,0));
int n,si;
int find(int);
void update(int,int,int,int,int,int,int);

int main(){
  int q,f;
  si = 1;
  cin >> n >> q;
  for(int i = 0;;i++){
    si*=2;
    if(si >= n)break;
  }
  for(int i = 0;i<q;i++){
    cin >> f;
    if(f == 1){
      int po,dat;
      cin >> po;
      dat = find(po);
      cout << dat << endl;
    }
    else{
      int st,go,d;
      cin >> st >> go>>d;
      update(st,go+1,0,0,si,d,i+1);
    }
  }
  return 0;
}
int find(int p){
  int ca = si-1+p;
  pair<int,int> ma = a[ca];
  while(ca>0){
    ca=(ca-1)/2;
    if(ma.second<a[ca].second){
      ma=a[ca];
    }
  }
  return ma.first;
}

void update (int s,int t,int k,int l,int r,int d,int ti){
  int m=(l+r)/2;
  if(s<=l&&r<=t){
    a[k].first=d;
    a[k].second=ti;
    return;
  }
  else if(r<=s||t<=l)return;

  else{
    update(s,t,k*2+1,l,m,d,ti);
    update(s,t,k*2+2,m,r,d,ti);
  }
}



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

int main(){
  int a,b,n;
  
  while(true){
    cin>>a;
    cin>>b;
    if(a==0 && b==0) break;
    if(a>b){
      n = a;
      a = b;
      b = n;
    }
  cout<<a<<" "<<b<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define endl "\n"
  #define all(v) v.begin(),v.end()
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<< ": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
const int mod = 1000000007;


int32_t main()
{





    int n;
    cin >> n;

    int x = n%10;


    if(x == 2 or x == 4 or x == 5 or x == 7 or x == 9)
    {
      cout << "hon";
    }
    else if(x == 0 or x == 1 or x == 6 or x == 8)
    {
      cout << "pon";
    }
    else
    {
      cout << "bon";
    }

    



    return 0;
}



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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

const string YES = "Yes";
const string NO = "No";

void solve(long long K, long long X){
    cout << (K*500 >= X ? YES : NO) << endl;
}

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


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

using namespace std;

int main() {
  char N[4];
  cin >> N;
  
  if (N[0] == N[1] && N[1] == N[2] && N[2] != N[3]) {
	cout << "Yes" << endl;
  } else if (N[1] == N[2] && N[2] == N[3] && N[3] !=N[0]) {
    cout << "Yes" << endl;
  } else if (N[0] == N[1] && N[1] == N[2] && N[2] == N[3]) {
	cout << "Yes" << endl;
  } else {
	cout << "No" <<endl;
  }
}

Measured memory_bytes: 256
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

int n,a[105];
signed main(){
    FastIO;
    cin>>n;
    rep(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    int ans=0;
    rep(i,1,n) rep(j,i+1,n) rep(k,j+1,n){
        if(a[i]!=a[j] and a[j]!=a[k]){
            if(a[i]+a[j]>a[k]) ans++;
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
#include <complex>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

typedef long long ll;
typedef vector<int> vi;

// geometry library start

const double EPS = 1.0e-10;

class P {
public:
	double x, y;
	P() {}
	P(int x_, int y_) : x(x_), y(y_) {}
	P(double x_, double y_) : x(x_), y(y_) {}
	P(const P& p) : x(p.x), y(p.y) {}
	P operator+(const P& p) const { return P(x+p.x, y+p.y); } 
	P operator-(const P& p) const { return P(x-p.x, y-p.y); }
	P operator-() const { return P(-x, -y); }
	P operator*(double s) const { return P(x*s, y*s); }
	P operator/(double s) const { return P(x/s, y/s); }
	P& operator=(const P& p) { x=p.x; y=p.y; return (*this); }
	double dot(const P& p) const { return x*p.x + y*p.y; }
	double det(const P& p) const { return x*p.y - y*p.x; }
	double norm() const { return sqrt(x*x + y*y); }
	double norm2() const { return x*x + y*y; }
	P proj(const P& p) const { double k=det(p)/norm2(); return P(x*k, y*k); }
};

double tri(P a, P b, P c) { return (b - a).det(c - a); }
int sign(double r) { return r < -EPS ? -1 : r > EPS ? 1 : 0; }

class L {
public:
	P s, t;
	L() {}
	L(P s_, P t_) : s(s_), t(t_) {}
	L(const L& l) : s(l.s), t(l.t) {}
	L& operator=(const L& l) { s=l.s; t=l.t; return (*this); }
	double length() { return (s - t).norm(); }
	P vec() const { return t - s; }
	P proj(const P& p) { return s + vec().proj(p - s); }
	int iLL(const L& l) const {
		if(sign(vec().det(l.vec()))) return 1;
		if(sign(vec().det(l.s - s))) return 0;
		return -1;
	}
	bool iLS(const L& l) const { return sign(tri(s, t, l.s)) * sign(tri(s, t, l.t)) <= 0; } 
	bool iSS(const L& l) const { return iLS(l) && l.iLS(*this); }
	P pLL(const L& l) const { return s + vec() * (l.s - s).det(l.vec()) / vec().det(l.vec()); }
	double dLP(const P& p) const { return abs(tri(s, t, p)) / vec().norm(); }
	double dSP(const P& p) const {
		if(sign(vec().dot(p - s)) <= 0) return (p - s).norm();
		if(sign(vec().dot(p - t)) >= 0) return (p - t).norm();
		return dLP(p);
	}
};

class C {
public:
	P p;
	double r;
	C() {}
	C(P p_, double r_) : p(p_), r(r_) {}
	C(const C& c) : p(c.p), r(c.r) {}
	C& operator=(const C& c) { p=c.p; r=c.r; return (*this); }
};

// geometry library end

int main() {
	int n;
	double x1,y1,x2,y2,x3,y3,x4,y4;
	scanf("%d", &n);
	rep(i,n) {
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
		P p1(x1,y1);
		P p2(x2,y2);
		P p3(x3,y3);
		P p4(x4,y4);
		if(sign((p2-p1).det(p4-p3)) == 0) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
}

Measured memory_bytes: 1204
N = int(input())
A = list(map(int,input().split()))
R = [0]*9

for a in A:
  if a<400:
    R[0]+=1
  elif a<800:
    R[1]+=1
  elif a<1200:
    R[2]+=1
  elif a<1600:
    R[3]+=1
  elif a<2000:
    R[4]+=1
  elif a<2400:
    R[5]+=1
  elif a<2800:
    R[6]+=1
  elif a<3200:
    R[7]+=1
  else:
    R[8]+=1

if sum(R[:-1])!=0:
  M = 8-R[:-1].count(0)+R[-1]
  m = 8-R[:-1].count(0)
  print(m,M)
else:
  print(1,R[-1])

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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  int ans=0;
  for(int i=0;i<B;i++){
     ans=ans+C;
  }
  if(A>B){
  	cout << ans+(D*(A-B)) << endl;
  }
  else{
    cout <<A*C << endl;
  }
}

Measured memory_bytes: 256
using System;
namespace ABC085C_Otoshidama
{
    public class MainClass
    {
        public static void Main(string[] args)
        {
            string[] inp = Console.ReadLine().Split(' ');
            int n = int.Parse(inp[0]);
            int y = int.Parse(inp[1]);

            bool flag = false;
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= n - i; j++)
                {
                    int k = n - (i + j);
                    if (10000 * i + 5000 * j + 1000 * k == y)
                    {
                        flag = true;
                        Console.WriteLine($"{i} {j} {k}");
                        break;
                    }
                }
                if (flag)
                {
                    break;
                }
            }
            if (!flag)
            {
                Console.WriteLine("-1 -1 -1");
            }
        }
    }
}


Measured memory_bytes: 13268
#include<stdio.h>
#include<algorithm>
using namespace std;
int size[3];
int dat[3][15];
int val[3];
int now[3][15];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a+b){
		for(int i=0;i<3;i++){
			int c;
			scanf("%d",&c);
			size[i]=c;
			for(int j=0;j<c;j++)scanf("%d",dat[i]+j);
		}
		int ret=999999999;
		if(size[0]==a||size[2]==a)ret=0;
		for(int m=0;m<2;m++){
			int last=m;
			for(int i=0;i<3;i++){
				val[i]=size[i];
				for(int j=0;j<size[i];j++)now[i][j]=dat[i][j];
			}
			int k=0;
			while(k<b&&val[0]!=a&&val[2]!=a){
				if(val[last+1]&&(val[last]==0||now[last][val[last]-1]<now[last+1][val[last+1]-1])){
					now[last][val[last]++]=now[last+1][--val[last+1]];
				}else{
					now[last+1][val[last+1]++]=now[last][--val[last]];
				}
				last=!last;
				k++;
		//		printf("%d %d %d\n",val[0],val[1],val[2]);
			}
			if(val[0]==a||val[2]==a)ret=min(ret,k);
		}
		if(ret==999999999)printf("-1\n");
		else printf("%d\n",ret);
	}
}

Measured memory_bytes: 760
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int MOD = 1000000007;
const int MOD1 = 998244353;
const int maxn = 100010;
const int lim = (int)1e9;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	vector<int> a(3);
	vector<int> b(3);
	cin >> a[0] >> a[1] >> a[2];
	sort(a.begin(), a.end());
	if (a[0] == a[2])
		cout << ((a[0] & 1) ? "0" : "-1");
	else
	{
		int res = 0;
		while (true)
		{
			if ((a[0] & 1) || (a[1] & 1) || (a[2] & 1))
				break;
			++res;
			b[0] = (a[0] + a[1]) / 2; b[1] = (a[1] + a[2]) / 2; b[2] = (a[0] + a[2]) / 2;
			sort(b.begin(), b.end());
			a = b;
		}
		cout << res;
	}
	cout << endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  int a,b;
  cin>>a>>b;
  if(a==0)cout<<"Zero";
  else if(a<0&&b>=0)cout<<"Zero";
  else if(a>0||(b-a)%2==1)cout<<"Positive";
  else cout<<"Negative";
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	int table[100]={0};
	cin >> n;
	for(int i = 0 ; i < n * (n-1) / 2 ; i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a--,b--;
		if(c==d){
			table[a]++;
			table[b]++;
		}else if(c>d){
			table[a]+=3;
		}else{
			table[b]+=3;
		}
	}
	for(int i = 0 ; i < n ; i++){
		int weakness = 0;
		for(int j = 0 ; j < n ; j++){
			if(i != j && table[j] > table[i]){
				weakness++;
			}
		}
		cout << weakness + 1 << endl;
	}
	
}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
using System.IO;
using System.IO.Compression;
using System.Linq;
using System.Text;

namespace AOJ
{
	class Program
	{
		static void Main(string[] args)
		{
			while(true)
			{
				int m = int.Parse(Console.ReadLine());
				if (m == 0) break;

				var kv = new List<KeyValuePair<int, int>>();

				while(m--!=0)
				{
					var s = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
					var scores = s.Skip(1).ToArray();
					var num = s[0];
					int score = 0, index = 0;

					for (int i = 0; i < 10; i++)
					{
						int t = scores[index];
						if(t == 10)
						{
							score += t + scores[index + 1] + scores[index + 2];
							index++;
							continue;
						}

						t += scores[index + 1];
						if (t == 10)
						{
							score += t + scores[index + 2];
						}
						else
						{
							score += t;
						}
						index += 2;
					}
					kv.Add(new KeyValuePair<int,int>(num, score));
				}

				foreach(var r in kv.OrderByDescending(a => a.Value).ThenBy(a => a.Key))
				{
					Console.WriteLine("{0} {1}", r.Key, r.Value);
				}
			}
		}
	}
}

Measured memory_bytes: 6700
import java.io.*
import java.lang.RuntimeException

val pw = PrintWriter(System.out)
const val MOD = 1000000007L
const val INF = 2147483647
const val LINF = 9223372036854775807L

fun main(args: Array<String>) {
    solve()
    pw.flush()
}

fun solve() {
    val (n, t) = nextIntList()
    val ab = intAry2(n, 2)
    repeat(n) {
        val (x, y) = nextIntList()
        ab[it][0] = x
        ab[it][1] = y
    }
    ab.sortBy { it[0] }
    val dp = intAry(6010)

    for (i in ab.indices){
        for (j in t - 1 downTo 0){
            dp[j + ab[i][0]] = max(dp[j + ab[i][0]], dp[j] + ab[i][1])
        }
    }

    println(dp.max())

}


fun println(v: String) {
    pw.println(v)
}

fun print(v: String) {
    pw.print(v)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ").toMutableList()
fun nextIntList(index: Int = 0) = next().split(" ").map { it.toInt() + index }.toMutableList()
fun nextLongList(index: Long = 0L) = next().split(" ").map { it.toLong() + index }.toMutableList()
fun nextDoubleList() = next().split(" ").map { it.toDouble() }.toMutableList()

fun ary(n: Int, init: String = "") = Array(n) { init }
fun intAry(n: Int, init: Int = 0) = IntArray(n) { init }
fun longAry(n: Int, init: Long = 0L) = LongArray(n) { init }
fun doubleAry(n: Int, init: Double = 0.0) = DoubleArray(n) { init }
fun ary2(n: Int, m: Int, init: String = "") = Array(n) { Array(m) { init } }
fun intAry2(n: Int, m: Int, init: Int = 0) = Array(n) { IntArray(m) { init } }
fun longAry2(n: Int, m: Int, init: Long = 0) = Array(n) { LongArray(m) { init } }
fun doubleAry2(n: Int, m: Int, init: Double = 0.0) = Array(n) { DoubleArray(m) { init } }
fun ary3(n: Int, m: Int, k: Int, init: String = "") = Array(n) { Array(m) { Array(k) { init } } }
fun intAry3(n: Int, m: Int, k: Int, init: Int = 0) = Array(n) { Array(m) { IntArray(k) { init } } }
fun longAry3(n: Int, m: Int, k: Int, init: Long = 0L) = Array(n) { Array(m) { LongArray(k) { init } } }
fun doubleAry3(n: Int, m: Int, k: Int, init: Double = 0.0) = Array(n) { Array(m) { DoubleArray(k) { init } } }

fun abs(n: Int): Int = Math.abs(n)
fun abs(n: Long): Long = Math.abs(n)
fun abs(n: Double): Double = Math.abs(n)
fun max(vararg values: Int) = if (values.isEmpty()) -INF else values.max()!!
fun max(vararg values: Long) = if (values.isEmpty()) -LINF else values.max()!!
fun min(vararg values: Int) = if (values.isEmpty()) INF else values.min()!!
fun min(vararg values: Long) = if (values.isEmpty()) LINF else values.min()!!
fun swap(a: String, b: String) = Pair<String, String>(b, a)
fun swap(a: Int, b: Int) = Pair<Int, Int>(b, a)
fun swap(a: Long, b: Long) = Pair<Long, Long>(b, a)
fun swap(a: Double, b: Double) = Pair<Double, Double>(b, a)

Measured memory_bytes: 39600
def main():
  import sys
  n,s,_,*t=sys.stdin.buffer.read().split()
  n=int(n)
  d=[0]*n+[1<<c-97for c in s]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  for q,a,b in zip(*[iter(t)]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=1<<ord(b)-97
      while i>1:
        i//=2
        d[i]=d[i+i]|d[i-~i]
      continue
    j=int(b)+n
    while i<j:
      if i&1:
        s|=d[i]
        i+=1
      if j&1:
        j-=1
        s|=d[j]
      i//=2
      j//=2
    print(bin(s).count('1'))
main()

Measured memory_bytes: 95728
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include <vector>
#include<numeric>

using namespace std;

long long int gcd(long int a, long int b)
{
	long long int r, x, tmp;
  x = a * b;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return x / b;
}

int main()
{
    long int a, b, c, d, div_c, div_d, div_gcd, div, ans;
    cin >> a >> b >> c >> d;
    div_c = b / c - (a - 1) / c;
    div_d = b / d - (a - 1) / d;
    div_gcd = b / gcd(c, d) - (a - 1) / gcd(c, d);
    div = div_c + div_d - div_gcd;
    ans = b - (a - 1) - div;
    cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	p := make([]float64, N)

	for i := 0; i < N; i++ {
		p[i] = getF()
	}

	var dp [3000][3000]float64

	dp[0][0] = 1
	for i := 1; i <= N; i++ {
		for j := 0; j <= N; j++ {
			if j != 0 {
				dp[i][j] = (1-p[i-1])*dp[i-1][j] + p[i-1]*dp[i-1][j-1]
			} else {
				dp[i][j] = (1 - p[i-1]) * dp[i-1][j]
			}
		}
	}

	ans := float64(0)
	for i := (N + 1) / 2; i <= N; i++ {
		ans += dp[N][i]
	}
	out(ans)

}


Measured memory_bytes: 73216
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
#define fi first
#define se second
#define all(a) a.begin(),a.end()
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
set<int>st;
int ans;
int a,b,c,k;
void dfs(int d){
	if(d==k){
		ans=max(ans,a+b+c);
		return;
	}
	a*=2;
	dfs(d+1);
	a/=2;
	b*=2;
	dfs(d+1);
	b/=2;
	c*=2;
	dfs(d+1);
	c/=2;
}
signed main(){
	cin>>a>>b>>c>>k;
	dfs(0);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#define rep(i,n) for(int i=0;i<(n);++i)
#include <algorithm>
using namespace std;
int main(){
    int n,k;
    int p[1002];
    cin >> n >> k;
    rep(i,n) cin >> p[i];

    std::sort(p,p+n);
    long ans = 0;
    rep(i,k)ans+= p[i];
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}

using namespace std;
int main()
{
  int N, M;
  cin >> N >> M;
  vector <unsigned int> sw_ptn(M);
	for (int i = 0; i < M; i++) {
		int k;
		cin >> k;
		sw_ptn[i] = 0u;
		for (int j = 0; j < k; j++) {
			unsigned int s;
			cin >> s;
			sw_ptn[i] |= (1 << (s-1));
		}
	}
	vector <unsigned int> onoff(M);
	for (int i = 0; i < M; i++) cin >> onoff[i];

	unsigned int ptn_max = (1 << N);

	int ans = 0;
	for (unsigned int i = 0; i < ptn_max; i++) {
		int light_on_cnt = 0;
		for (int j = 0; j < M; j++) {
			unsigned int p = countbit(i & sw_ptn[j]);
			if (p%2==onoff[j]) {
				light_on_cnt++;
			} else {
				break;
			}
		}
		if (light_on_cnt==M) ans++;
	}

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

Measured memory_bytes: 256
#include<stdio.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define abs(a) ((a)>0 ? (a):-(a))

int main(){
	int n,m,man[50][2],point[50][2];
	int ans[50];
	scanf("%d %d",&n,&m);
	FOR(i,0,n) scanf("%d %d",&man[i][0],&man[i][1]);
	FOR(j,0,m) scanf("%d %d",&point[j][0],&point[j][1]);

	FOR(i,0,n){
		int distmin = 1000000000;
		FOR(j,0,m){
			int dist = abs(man[i][0] - point[j][0]) + abs(man[i][1] - point[j][1]);
			if(distmin > dist){
				distmin = dist;
				ans[i] = j+1;
			}
		}
	}

	FOR(i,0,n) printf("%d\n",ans[i]);
}

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

bool should_be_swaped_with_the_next(vector<tuple<string, int, int>> list, int index){
  if(get<0>(list.at(index)) < get<0>(list.at(index + 1))){
    return false;
  }else if(get<0>(list.at(index)) > get<0>(list.at(index + 1))){
    return true;
  }else if(get<1>(list.at(index)) < get<1>(list.at(index + 1))){
    return true;
  }else{
    return false;
  }
}

int main(){
  int N;
  cin >> N;
  string city; 
  int score, index;
  bool is_end = false;
  vector<tuple<string, int, int>> list;
  tuple<string, int, int> temp;
  
  for(int i = 0; i < N; i++){
    index = i + 1;
    cin >> city >> score;
    list.push_back(make_tuple(city, score, index));
  }
  
  while(!is_end){
    bool swaped = false;
    for(int i = 0; i < N - 1; i++){
      if(should_be_swaped_with_the_next(list, i)){
        temp = list.at(i);
        list.at(i) = list.at(i + 1);
        list.at(i + 1) = temp;
        swaped = true;
      }
    }
      
    if(!swaped){
      is_end = true;
    }
  }
 
  for(int i = 0; i < N; i++){
    cout << get<2>(list.at(i)) << endl;
  }
}

Measured memory_bytes: 3612
package main

import (
	"fmt"
)

func main() {

	var N,M int

	fmt.Scan(&N,&M)

	H := SliceInt(N)
	A:= SliceInt(M)
	B:= SliceInt(M)

	all := SliceInt(N)

	for i:=0;i<N;i++{

		fmt.Scan(&H[i])

		all[i] = 1

	}

	for i:=0;i<M;i++{

		fmt.Scan(&A[i],&B[i])
	}


	for i:=0;i<M;i++{

		a := A[i]
		b:=  B[i]

		if H[a-1] >= H[b-1]{
			all[b-1] = 0
		}

		if H[b-1] >= H[a-1]{
			all[a-1] =0
		}
	}
  
	cnt :=0

	for _,val := range all{

		if val ==1 {
			cnt++
		}
	}


	fmt.Println(cnt)
}

//SliceInt 引数サイズのSliceを返す
func SliceInt(a int) []int {

	IntSample := make([]int, a)

	return IntSample

}

Measured memory_bytes: 8560
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
using namespace std;
#define loop(i,a,b) for(int i = a; i < b; i++)
#define rep(i,a) loop(i,0,a)
#define shosu(x) fixed<<setprecision(x)
typedef long long ll;

int main()
{
	
	int h,w;
	cin>>h>>w;
	char a[9][9]={};
	rep(i,h)
		rep(j,w)
			cin>>a[i][j];
	
	int flg=1;
	rep(i,h-1)
		rep(j,w-1)
			if(a[i][j]=='#'&&a[i+1][j]=='#'&&a[i][j+1]=='#')
				flg=0;
	loop(i,1,h)
		loop(j,1,w)
			if(a[i][j]=='#'&&a[i-1][j]=='.'&&a[i][j-1]=='.')
				flg=0;
			
				
	if(flg)
		cout<<"Possible"<<endl;
	else
		cout<<"Impossible"<<endl;
		
	


        return 0;
}


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

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

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

#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

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

const int N = 1e5 + 5;

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

vector<int> adj[N];
int dp[N];

int fun(int v) {
	int &memo = dp[v];
	if(memo != -1) return memo;
	memo = 0;
	for(auto it : adj[v]) {
		memo = max(memo, fun(it));
	}
	memo++;
	return memo;
}

int main() {

	boost;
	int n, m; cin>>n>>m;
	for(int i=1; i<=m; i++) {
		int a, b; cin>>a>>b;
		adj[a].pb(b);
	}
	memset(dp, -1, sizeof dp);
	int ans = 0;
	for(int i=1; i<=n; i++) {
		ans = max(ans, fun(i)-1);
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 7552
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define PI 3.141592653589793
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){ 
    ll X;
    cin >> X;
    ll ans=0;
    while(X>=500){
        ans+=1000;
        X-=500;
    }
    while(X>=5){
        ans+=5;
        X-=5;
    }
    cout << ans << endl;
    

}

Measured memory_bytes: 256
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::HashSet;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
    n: i64,
    mut mon: [i64; n+1],
    mut yuu: [i64; n]
    }

    let mut  sum = 0;

    for i in 0..n {
      let minv = min!(mon[i as usize], yuu[i as usize]);
      sum += minv;
      if yuu[i as usize] > minv{
        let next = yuu[i as usize] - minv;
        sum +=  min!( mon[(i + 1) as usize],next);
        mon[(i + 1) as usize] = mon[(i + 1) as usize] - min!( mon[(i + 1) as usize],next);
      }

    }


     println!("{}", sum);
}


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

ll A, B;
int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A >> B;
    ll C = (B + A - 1) / A;
    if(C < C * A - B + 1) cout << C * A << endl;
    else cout << -1 << endl;
    return 0;
}



Measured memory_bytes: 3200
while True:
    q = int(input())
    
    if q == -1:
        break
    
    x = q / 2

    while abs(x ** 3 - q) >= q * 0.00001:
        x = (2 * x ** 3 + q) / (3 * x ** 2)
    print("{:.6f}".format(x))


Measured memory_bytes: 5660