akhauriyash/Code-Regression huggingface dataset:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


N = int(input())
X = list(map(int, input().split()))

modFacts, invs = prepare(N)

ans = 0
var = modFacts[N - 1]
p = 0
for i in range(N - 1):
    j = i + 1
    d = X[i + 1] - X[i]
    p += modFacts[N - 1] * modFacts[j - 1] * invs[j]
    ans += (d * p) % MOD
    ans %= MOD

print(ans)


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

int main()
{
    string s;
    cin >> s;
    if(s=="Sunny")
        cout << "Cloudy" << endl;
    if(s=="Cloudy")
        cout << "Rainy" << endl;
    if(s=="Rainy")
        cout << "Sunny" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int 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*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

struct node{int to,nxt;}sq[N<<1];
int all=0,head[N];
void addedge(int u,int v)
{
    all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}

int n,fa[N],dep[N],ans[2][N],d[N];
vi chain;
bool vis[N];

int dfs(int u,int fu)
{
    fa[u]=fu;dep[u]=dep[fu]+1;
    go(u,i)
    {
        if (v==fu) continue;
        dfs(v,u);
    }
}

void work(int op)
{
    int now=0,len=chain.size();
    rep(j,0,len-1)
    {
        int u=chain[j];
        rep(i,1,d[u]) ans[op][now+i]=now+i+1;
        ans[op][now+d[u]+1]=now+1;now+=(d[u]+1);
    }
}

void out(int op)
{
    rep(i,1,n) printf("%d ",ans[op][i]);
}

void chk()
{
    rep(i,1,n) 
    {
        if (ans[0][i]<ans[1][i]) {out(0);return;}
        else if (ans[1][i]<ans[0][i]) {out(1);return;}
    }
    out(0);
}

int main()
{
    n=read();
    rep(i,1,n-1)
    {
        int u=read(),v=read();
        addedge(u,v);addedge(v,u);
    }
    dfs(1,0);
    int p1=0,p2=0;
    rep(i,1,n) if (dep[i]>dep[p1]) p1=i;
    dep[p1]=0;dfs(p1,0);
    rep(i,1,n) if (dep[i]>dep[p2]) p2=i;
    int now=p2;
    while (now)
    {
        vis[now]=1;chain.pb(now);now=fa[now];
    }
    int len=chain.size();
    //rep(i,1,n) cout << vis[i] << " ";cout << endl;
    rep(u,1,n)
    {
        go(u,i)
        {
            if ((!vis[u]) && (!vis[v]))
            {
                puts("-1");return 0;
            }
            if ((vis[u]) && (!vis[v])) d[u]++;
        }
    }
    work(0);
    reverse(chain.begin(),chain.end());
    work(1);
    chk();
    return 0;
}

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

int main(){
  int S; cin >> S;
  int L,R;
  L = S/100;
  R = S%100;
  if(1<=L && L<=12){
    if(1<=R && R<=12) cout << "AMBIGUOUS" << endl;
    else cout << "MMYY" << endl;
  }else{
    if(1<=R && R<=12) cout << "YYMM" << endl;
    else cout << "NA" << endl;
  }
}

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

using namespace std;
typedef long long ll;
const int maxn=2e3+10;
const ll mod=1e9+7;
ll dp[maxn];//n  la_num;
int vis[maxn];
int main(){
	ll n;
	cin>>n;
	memset(dp,0,sizeof(dp));
	memset(vis,1,sizeof(vis));
	for(int i=3;i<=n;i++){
		dp[i]=1;
	}
	for(int i=3;i<=n;i++){
		for(int j=3;j+i<=n;j++){
			dp[i+j]=(dp[i+j]+dp[i])%mod;
		}
	}
	cout<<dp[n]<<endl;
	return 0 ;
}
 

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



int main(void){
	
	int n,k;

	scanf("%d %d",&n,&k);

	int d,g;
	int list[110]={0};

	int count=0;

	for(int i=0;i<k;i++)
	{
		scanf("%d",&d);//お菓子を持つ人数
		
		for(int j=0;j<d;j++)
		{
			scanf("%d",&g);
			list[g]++;
		}
	
	}
	
	for(int i=1;i<n+1;i++)
	{
		if(list[i]==0){count++;}
	}

	printf("%d",count);


	return 0;
	}


Measured memory_bytes: 1728
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include<algorithm>

using namespace std;

int main() {
	int n,k;
	cin >> n >> k;
	vector<int> v(n+2);

	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	
	int lim = k;
	if (lim > n+1) {
		lim = n+1;
	}

	long long max = 0;
	for (int i = 0; i <= lim; i++) {
		for (int j = 0; j <= lim - i; j++) {
			int res = k - j - i;
			vector<int> v_copy(v);
			//cout << i << " " << j << " " << res << endl;
			long long sum = 0;
			priority_queue<int> pq;
			
			for (int l = 0; l <= i; l++) {
				sum += v_copy[l];
				
				if (v_copy[l] < 0) {
					pq.push(-v_copy[l]);
				}
				v_copy[l] = 0;
			}

			for (int l = n+1; l >=n+1- j; l--) {
				sum += v_copy[l];
				
				if (v_copy[l] < 0) {
					pq.push(-v_copy[l]);
				}
				v_copy[l] = 0;
			}

			while (res > 0 && !pq.empty()) {
				sum += pq.top();
				//cout << pq.top() <<" " << sum<< endl;
				pq.pop();
				res--;
			}


			if (max< sum) {
				//cout << i << " " << j << endl;
				max = sum;
			}
		}
	}

	cout << max << endl;

}

Measured memory_bytes: 256
#line 1 "/workspaces/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "tmp.cpp"

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

  char s;
  cin >> s;

  if (0 <= s - 'A' && s - 'A' < 26) {
    cout << "A" << endl;
  } else {
    cout << 'a' << endl;
  }
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <stdio.h>
using namespace std;
int tmp,D[100]={};
void north(){
    tmp=D[0];
    D[0]=D[1];
    D[1]=D[5];
    D[5]=D[4];
    D[4]=tmp;
}
void south(){
    tmp=D[0];
    D[0]=D[4];
    D[4]=D[5];
    D[5]=D[1];
    D[1]=tmp;
}
void east(){
    tmp=D[0];
    D[0]=D[3];
    D[3]=D[5];
    D[5]=D[2];
    D[2]=tmp;
}
void west(){
    tmp=D[0];
    D[0]=D[2];
    D[2]=D[5];
    D[5]=D[3];
    D[3]=tmp;
}
int main(){
    char ch;
    for(int i=0;i<6;i++){
        cin>>D[i];
    }
    while(cin>>ch){
        if(ch=='N'){
            north();
        }
        else if(ch=='S'){
            south();
        }
        else if(ch=='E'){
            east();
        }
        else{
            west();
        }
    }
    cout<<D[0]<<endl;
    return 0;
}


Measured memory_bytes: 3120
#include<stdio.h>

void dfs_init(int);
void dfs(int,int);

int a[100][100],c[100],d[100],f[100],t;

int main(){
  int n,u,k,v,i,j;

  scanf("%d",&n);

  for(i=0;i<=n-1;i++){
    for(j=0;j<=n-1;j++){
      a[i][j]=0;
    }
  }
  
  for(j=0;j<=n-1;j++){
    scanf("%d%d",&u,&k);
    u--;
    for(i=0;i<=k-1;i++){
      scanf("%d",&v);
      v--;
      a[u][v]=1;
    }
  }
  dfs_init(n);
  return 0;
}

  void  dfs_init(int n){
    int i;

    for(i=0;i<=n-1;i++){
      c[i]=-1;
      t=0;
    }

    for(i=0;i<=n-1;i++){
      if(c[i]==-1)dfs(i,n);
    }

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

  void dfs(int u,int n){
    int i;
    c[u]=0;
    d[u]=++t;
    for(i=0;i<=n-1;i++){
      if(a[u][i]&&c[i]==-1)dfs(i,n);
    }
    c[u]=1;
    f[u]=++t;
  }





















Measured memory_bytes: 2132
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner scan = new Scanner(System.in);
    double[] P = new double[scan.nextInt()];
    for (int i = 0; i < P.length; i++)
      P[i] = scan.nextDouble();
    scan.close();

    System.out.println(headsOverTailsProbability(P));
  }

  private static double headsOverTailsProbability(double[] P) {
    if (P.length == 0) return 0;

    int N = P.length;
    double[][] dp = new double[N + 1][N + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= N; i++) {
      double headProbability = P[i - 1];
      double tailProbability = 1 - headProbability;
      dp[i][0] = tailProbability * dp[i-1][0];
      for (int j = 1; j <= N; j++)
        dp[i][j] = dp[i-1][j-1] * headProbability + dp[i-1][j] * tailProbability;
    }

    double result = 0;
    for (int i = N/2 + 1; i <= N; i++)
      result += dp[N][i];

    return result;
  }
}

Measured memory_bytes: 121676
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int,int> P;

int n, m;
int b, w;
char d[55][55];
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};

void bfs (int x, int y, char s) {
    queue<P> q;
    q.push(P(x,y));

    while (q.size()) {
        P p = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            x = p.first + dx[i], y = p.second + dy[i];
            if (0 <= x && x < n && 0 <= y && y < m) {
                if (d[x][y] == '.') {
                    d[x][y] = (s == 'W') ? '*' : '@';
                    q.push(P(x,y));
                    s == 'W' ? w++ : b++;
                } else if (s == 'B' && d[x][y] == '*') {
                    w--;
                    q.push(P(x,y));
                    d[x][y] = '@';
                }
            }
        }
    }
}

int main ()
{
    while (cin >> m >> n, (n || m)) {
        for (int i = 0; i < n; i++) {
            cin >> d[i];
        }
        b = w = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (d[i][j] == 'W') {
                    bfs (i, j, 'W');
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (d[i][j] == 'B') {
                    bfs (i, j, 'B');
                }
            }
        }

        cout << b << " " << w << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <climits>
#include <vector>


#define N_MAX 100
#define M_MAX 100
#define HP_MAX 100000
using namespace std;

int N,M;
int HP[N_MAX];
long long int dp[2][HP_MAX+1];
long long int A_dp[HP_MAX+1];//HP??????????????????MP???????°?????????????
long long int S_dp[HP_MAX+1];

typedef pair<int,int> P;

int main(){
    string s;
    vector<P> A,S; //<MP,Damage>
    while(cin>>N,N!=0){
        A.clear();
        S.clear();
        for(int i=0;i<N;i++) cin>>HP[i];
        cin>>M;

        for(int i=0;i<M;i++){
            int m,d;
            cin>>s>>m>>s>>d;
            if(s[0]=='A'){
                A.emplace_back(m,d);
            }else{
                S.emplace_back(m,d);
            }
        }

        fill_n(dp[0],2*(HP_MAX+1),INT_MAX);
        dp[1][0]=dp[0][0]=0;
        for(int i=0;i<A.size();i++){
            for(int hp=1;hp<=HP_MAX;hp++){
                if(i==0){
                    dp[0][hp]=A[0].first+(hp-A[0].second>=0?dp[0][hp-A[0].second]:0);
                }else{
                    dp[i%2][hp]=min(dp[(i+1)%2][hp],((hp-A[i].second)>=0?dp[i%2][hp-A[i].second]:0)+A[i].first);
                }
            }
        }
        for(int i=0;i<=HP_MAX;i++) A_dp[i]=dp[(A.size()+1)%2][i];

        fill_n(dp[0],2*(HP_MAX+1),INT_MAX);
        dp[1][0]=dp[0][0]=0;
        for(int i=0;i<S.size();i++){
            for(int hp=1;hp<=HP_MAX;hp++){
                if(i==0){
                    dp[0][hp]=S[0].first+(hp-S[0].second>=0?dp[0][hp-S[0].second]:0);
                }else{
                    dp[i%2][hp]=min(dp[(i+1)%2][hp],((hp-S[i].second)>=0?dp[i%2][hp-S[i].second]:0)+S[i].first);
                }
            }
        }
        for(int i=0;i<=HP_MAX;i++) S_dp[i]=dp[(S.size()+1)%2][i];

        long long int MP_min=LLONG_MAX;
        for(int alldamage=0;alldamage<=HP_MAX;alldamage++){
            long long int mp=A_dp[alldamage];
            if(mp==INT_MAX) continue;
            for(int i=0;i<N;i++){
                int hp=HP[i]-alldamage;
                if(hp>0){
                    mp+=S_dp[hp];
                }
            }
            MP_min=min(MP_min,mp);
        }
        cout << MP_min << endl;
    }
}

Measured memory_bytes: 6252
def solve():
    s = input()
    n = len(s)
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp = s[i:j]
            tmp = tmp.replace('A','').replace('T','').replace('G','').replace('C','')
            if len(tmp)==0:
                ans = max(ans,j-i)
    print(ans)
if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define F first
#define S second

ll n,ma,r,a[100005];

 
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>a[i];
}
	for(int i =0;i<n;i++){
		if(a[i]>ma)
			ma=a[i];
		if(ma-a[i]>1){
			cout<<"No\n";
			return 0;
		}
	}
	cout<<"Yes\n";
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define sz size()
#define pb push_back
#define mp make_pair
#define ALL(X) (X).begin(),(X).end()

using namespace std;

const int INF = 1000000000;
const double eps = 1e-8;

int main(void) {
	int n;
	cin>>n;
	REP(i,n)
	{
		int h,w;
		cin>>h>>w;
		vector<string> table(h);
		set<char> s;
		REP(j,h)
		{
			cin>>table[j];
			REP(k,w)
			{
				s.insert(table[j][k]);
			}
		}
		s.erase('.');
		vector<char> mats;
		FORIT(j,s)
			mats.push_back(*j);
		if(mats.size())
		{
			bool flg = true;
			do
			{
				flg = true;
				vector<string> cp(h);
				REP(k,h)cp[k]=string(table[k]);
				REP(j,mats.size())
				{
					int top=h,bottom=0,left=w,right=0;
					REP(k,h)REP(l,w)
					{
						if(cp[k][l] == mats[j])
						{
							top=min(top,k);
							bottom=max(bottom,k);
							left=min(left,l);
							right=max(right,l);
						}
					}
					FOR(k,top,bottom+1)
					{
						FOR(l,left,right+1)
						{
							if(cp[k][l]=='.')
							{
								flg = false;
								break;
							}
							else if(cp[k][l]==mats[j])
							{
								cp[k][l] = '.';
							}
						}
						if(!flg)break;
					}
					if(!flg)break;
				}
				if(flg)break;
			}while(next_permutation(ALL(mats)));
			if(flg)
				cout << "SAFE" << endl;
			else
				cout << "SUSPICIOUS" << endl;
		}
		else
			cout << "SAFE"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
ll dp[55];
int main() {
  int n;
  cin >> n;
  dp[0] = 1;
  dp[1] = 1;
  for (int i = 2; i < 50; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 3092
#include <stdio.h>

#define M 2000000

void Sort(int[], int);
int B[M];
int num;

int main()
{
	int array[M],i,k=0;
	
	scanf("%d", &num);

	for(i = 1; i <=num; i++){
		scanf("%d", &array[i]);
	}
	k=array[1];
	
  	for(i=2; i<=num; i++){
      	if(k < array[i]) k = array[i];
  	}
 	Sort(array, k+1);

	for(i = 1; i <= num; i++){
		printf("%d", B[i]);
		if(i!=num) printf(" ");
		if(i==num)printf("\n"); 
	}
	return 0;
}

void Sort(int A[], int k)
{
	int i,j;
	int cau[k];
	for(i =k; i >= 0; i--){
		cau[i] = 0;
	}
	for(i = 1; i <= num; i++){
		cau[A[i]]++;
	}
	 for(i=1; i<k; i++) cau[i] += cau[i-1];
	 
  	for(i=num; i>=1; i--){
    	B[cau[A[i]]] = A[i];
    	cau[A[i]]--;
	}
}

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

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

    long long int res = 0,n;

    cin >> n;

    if(n%2==0)
    {
    	n/=2;
    	long long int val = 5;
    	while(1)
    	{
    		if(n/val==0)
    		{
    			break;
    		}
    		res += (n/val);
    		val*=5;
    	}
    	cout << res << '\n';
    }
    else
    {
    	cout << 0 << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#define CO(a, b, c) ((a)?(b):(c))

using namespace std;

int func(int a, int b){
	return (powl(a, 5) - powl(b, 5));
}

int main(void)
{
	
	int x, tmp;
	cin >> x;

	for(int b = -119; b < 119; b++)
	{
		for (int a = b + 1; a < 120; a++)
		{
			if(func(a, b)==x)
			{
				cout << a << ' ' << b << endl;
				return 0;
			}
		}
	}

	return 0;
	
}

Measured memory_bytes: 3708
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pi pair<int, int>
#define F first
#define S second
#define PB push_back
#define EPB emplace_back
#define MP make_pair
#define d(x) cerr << #x << ":" << x << endl;
#define da(x) cerr << #x << endl; for (auto a : x) cerr << a << " "; cerr << endl;
const int MOD = 1000000007;

int main() {
	fastio();
	char c;
	cin >> c;
	if(c <= 90)
		cout << "A\n";
	else
		cout << "a\n";
	return 0;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
const ll MOD = 1000000007;
//const ll MOD = 998244353;

int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll> H(N);
	for (int i = 0;i < N;i++) {
		cin >> H[i];
	}
	sort(all(H));
	ll ans = 0;
	for (int i = 0;i < N - K;i++) {
		ans += H[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
import math
S = input()
RL = []
LR = []
p = 'L'
pl = -1
for i in S:
    if i == 'L':
        if p == 'R':
            RL.append(pl)
    else:
        if p == 'L':
            LR.append(pl)
    p = i
    pl += 1
LR.append(len(S)-1)
c = [0 for j in range(len(S))]
W = len(RL)
for k in range(W):
    s = RL[k] - LR[k] + 1
    c[RL[k]] += s//2
    c[RL[k]+1] += math.ceil(s/2)
for l in range(W):
    t = LR[l+1] - RL[l] -1
    c[RL[l]] += math.ceil(t/2)
    c[RL[l]+1] += t//2
c=[str(a) for a in c]
c = ' '.join(c)
print(c)

Measured memory_bytes: 14276
def bsearch(a, i, j, x)
    return 0 if i > j
    c = (i + j) / 2
    if a[c] < x
        1 + bsearch(a, c+1 , j, x)
    elsif x < a[c]
        1 + bsearch(a, i, c-1, x)
    else
        return 1
    end
end

loop do
    n = gets.to_i
    break if n == 0
    a = (1..n).map { gets.to_i }
    p bsearch(a, 0, a.size-1, gets.to_i)
end

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

int main() {
	int X;
	cin >> X;
	int result = 0;
	if (X == 2) {
		cout << 2 << endl;
		exit(0);
	}
	while (result == 0) {
		for (int i = 2; i < X; i++) {
			if (X % i == 0) {
				break;
			}
			else if (X % i != 0 && i + 1 == X) {
				result = X;
			}
		}
		X++;
	}
	cout << result << endl;
}

Measured memory_bytes: 3612
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
pp = p[:x]
qq = q[:y]

m = pp + qq + r
m.sort(reverse=True)

print(sum(m[:x+y]))


Measured memory_bytes: 23328
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
//cout << std::fixed << std::setprecision(15) << y << endl;


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

    ll L[n];
    rep(i, n){
        cin >> L[i];
    }
    sort(L, L + n);

    ll ans = 0;
    for(ll i = 0; i < n - 2; i++){
        for(ll j = i + 1; j < n - 1; j++){
            if(L[i] == L[j]){
                continue;
            }
            for(ll k = j + 1; k < n; k++){
                if(L[k] != L[j] && L[k] < L[i] + L[j]){
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		StringBuilder ans = new StringBuilder();
		if(a >= b) {
			while(a != 0) {
				ans.append(b);
				a--;
			}
			System.out.println(Integer.parseInt(ans.toString()));
		} else {
			while(b != 0) {
				ans.append(a);
				b--;
			}
			System.out.println(Integer.parseInt(ans.toString()));
		}
	}
	
	
	
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define COUT(x) cout<<x<<endl

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double PI = acos(-1.0);
const LL MOD = 1e9 + 7;
const ULL INF = 1e18;
const int dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };

//function
//--------------------------------------------
LL gcd(LL, LL);
bool isEven(LL);
void coutY();
void coutN();
LL ave(LL, LL);

int main() {
	int x, a, b; cin >> x >> a >> b;
	x -= a;
	cout << x % b;
}

LL gcd(LL a, LL b) {
	if (a == 0 || b == 0)return 0;
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	else gcd(b, a % b);
}
bool isEven(LL a) {
	return !((bool)(a % 2));
}
void coutY() {
	cout << "Yes" << endl;
	return;
}
void coutN() {
	cout << "No" << endl;
	return;
}
LL ave(LL a, LL b) {
	return (a + b) / 2;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b,c,x;
	scanf("%d %d %d",&a,&b,&c);
	
	if((1<=a<=10000)&&(1<=b<=10000)&&(1<=c<=10000))
	{
		if(b<a){
			x = a;
			a = b;
			b = x;
		}if(c<b){
			x = c;
			c = b;
			b = x;
		}if(b<a){
			x = a;
			a = b;
			b = x;
		}
	}
	printf("%d %d %d\n",a,b,c);
	return 0;
}

Measured memory_bytes: 596
import java.util.*;


/**
 * Created by santa on 2016/10/16.
 */

public class Main {

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

        int[] a = {399,799,1199,1599,1999,2399,2799,3199};
        int[] map = new int[9];

        int N = scanner.nextInt();


        for (int i = 0; i < N; i++) {
            int temp = scanner.nextInt();
            int color = -1;
            if(temp < 400)color = 0;
            for (int j = 1; j < a.length; j++) {
                if(temp > a[j - 1] && temp <= a[j]){
                    color = j;
                }
            }
            if(color == -1)color = 8;
            map[color]++;
        }
        int ans = 0;
        for (int i = 0; i < 8; i++) {
            if(map[i] > 0)ans++;
        }
        if(ans == 0){
            System.out.println(1 + " " + map[8]);
        }else{
            System.out.println(ans + " " + (ans + map[8]));
        }
        
        

    }// mainMethod




} // MainClass


Measured memory_bytes: 22100
#include <stdio.h>

int calc(int x,int y){
	if(y == 0){
		return x;
	}else{
		return calc(y,x%y);
	}
}

int main(){
	int x,y;
	scanf("%d %d",&x,&y);
	if(x >= y)
		printf("%d\n",calc(x,y));
	else{
		printf("%d\n",calc(y,x));
	}
}



Measured memory_bytes: 2752
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip> 
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(j, a, b) for (int j = a; j >= b; j--)
using namespace std;
const int MAX = 1e5 + 5; 
const int MOD = 1e9 + 7;
int n;
vector <vector<int> > edges(MAX);
int add(int& a, int b){
    a = a+b;
    if(a>=MOD){
        a-=MOD;
    }
    return a;
}
int mul(int& a, int b){
    //cout<< a << " " << b << endl;
    a= (long long) a*b%MOD;
    return a;
}
pair <int, int> count (int parent, int curr){
    int white = 1, black = 1;
    for(int i: edges[curr]){
        if(i==parent)continue;
        auto h = count(curr, i);
        // cout << curr << " " << h.first << " " << h.second << " ";
        // cout << white << " " << black << endl;
        mul(black, h.first);
        mul(white, add(h.first, h.second));
    }
    //cout << curr << " " << white << " " << black<< endl;
    return {white, black};
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    rep(i,0,n-1){
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    auto x = count(-1, 1);
    auto t = add(x.first, x.second);
    cout << t << endl;
}


Measured memory_bytes: 12672
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
	int n;
	cin >> n;
	cout << n * 800 - n / 15 * 200 << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProgramingStudying2
{
    class Program
    {

        static void Main(string[] args)
        {
            var nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var n = nm[0];
            var m = nm[1];

            var number = new int[n];
            var visited = new bool[n];

            for(int i = 0; i < m; i++)
            {
                var sc = Console.ReadLine().Split();
                var s = int.Parse(sc[0]);
                var c = int.Parse(sc[1]);

                if (visited[s - 1] && number[s - 1] != c)
                {
                    Console.WriteLine(-1);
                    return;
                }
                else if(n > 1 && s == 1 && c == 0)
                {
                    Console.WriteLine(-1);
                    return;
                }
                else
                {
                    visited[s - 1] = true;
                    number[s - 1] = c;
                }
            }

            var ans = 0;
            if(n > 1 && number[0] == 0)
            {
                number[0] = 1;
            }
            for(int i = 0; i < n; i++)
            {
                ans += number[i] * (int)Math.Pow(10, n - i - 1);
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 28308
from collections import defaultdict
from itertools import product, combinations

def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return None
        Otherwise return dist: the table of the minimum cost between arbitrary vertex u, v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    path = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; path[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; path[v][u] = v;
    for k, i, j in product(V, repeat=3):
        if dist[i][j] > dist[i][k] + dist[k][j]:
            dist[i][j] = dist[i][k] + dist[k][j]
            path[i][j] = path[k][j]
    for v in V:
        if dist[v][v] < 0: return None, None
    return dist, path


N, M = map(int, input().split())
E = defaultdict(dict)
cand = set()
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
    cand |= {(min(a-1, b-1), max(a-1, b-1))}
V = list(range(N))
_, path = floyd_warshall(V, E)
for i, j in combinations(V, 2):
    temp = set()
    while path[i][j] != -1:
        temp |= {(path[i][j], j)} if path[i][j] < j else {(j, path[i][j])}
        j = path[i][j]
    cand -= temp
print(len(cand))

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

int main() {
  int n,k,q;
  cin >> n >> k >> q;
  vector<int> point(n,k-1*q);
  for(int i=0;i<q;i++) {
    int temp;
    cin >> temp;
    temp--;
    point.at(temp)++;
  }
  for(int i=0;i<n;i++) {
    if(point.at(i)>0) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 100000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N;
int a[100100];
int b[100100];
int main(){
	cin >> N;
	for(int i=0;i<N;i++)cin >> a[i];
	sort(a,a+N);
	ll ans = 0ll;
	ll res = 0ll;
	if(N==2){
		cout << abs(a[0]-a[1]) << endl;
		return 0;
	}
	if(N==3){
		swap(a[1],a[2]);
		chmax(ans,(ll)abs(a[0]-a[1])+(ll)abs(a[1]-a[2]));
		swap(a[1],a[2]);
		swap(a[0],a[1]);
		chmax(ans,(ll)abs(a[0]-a[1])+(ll)abs(a[1]-a[2]));
		cout << ans << endl;
		return 0;
	}
	int p = (N+1)/2;
	for(int i=0;i<(N+1)/2;i++){
		res-=a[i]*2ll;
	}
	for(int i=0;i<(N/2);i++){
		res+=a[N-1-i]*2ll;
	}
	if(N%2==1){
		chmax(ans,res+a[p-1]+a[p-2]);
	}else{
		chmax(ans,res-a[p]+a[p-1]);
	}
	if(N%2==1){
		res += a[p-1]*4ll;
		chmax(ans,res-a[p]-a[p-1]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
object Main {
  def main (args: Array[String]) {
    val Array(width, height, x, y, r) = scala.io.StdIn.readLine().split(" ").map(_.toInt)
 
    width match{   
      case w if (x-r < 0) || (y-r < 0) || (x+r > width) || (y+r > height)  => println("No")
      case _     => println("Yes") 
    }
  }
}

Measured memory_bytes: 43904
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

mod = 10 ** 9 + 7
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

ans = 0

def comb(n, r):
  if n >= r:
    return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
  else:
    return 0
 
for i in range(2, N + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

if K == 1:
  print(0)
else:
  for i, x in enumerate(A):
    cnt = x * ( comb(i, K-1) - comb(N-1-i, K-1) ) % mod
    ans += cnt
    ans %= mod
  print(ans)

Measured memory_bytes: 25936
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [i+x for i, x in enumerate(A)]
R = [i-x for i, x in enumerate(A)]
cnt_R = Counter(R)

ans = 0
for l in L:
	ans += cnt_R[l]
print(ans)


Measured memory_bytes: 138200
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		tree = new int [N];
		Arrays.fill(tree, -1);
		for (int i = 0; i < M; i++) {
			union(sc.nextInt() - 1, sc.nextInt() - 1);
		}
		int max = 0;
		for (int i = 0; i < N; i++) {
			max = Math.max(max, size(i));
		}
		System.out.println(max);
	}
	
	static int[] tree;
	static void union(int x, int y) {
		x = root(x);
		y = root(y);
		if(x != y) {
			if(tree[x] < tree[y]) {
				x ^= y; y ^= x; x^= y;
			}
			tree[x] += tree[y];
			tree[y] = x;
		}
	}
	static boolean find(int x, int y) {
		return root(x) == root(y);
	}
	static int root(int x) {
		return tree[x] < 0 ? x : (tree[x] = root(tree[x]));
	}
	static int size(int x) {
		return -tree[root(x)];
	}
}


Measured memory_bytes: 63788
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

bool func(string s) {
  for (int i = 0; i < s.size() / 2; i++) {
    if (s[i] != s[s.size() - i - 1]) {
      return false;
    }
  }
  return true;
}

int main() {
  string s;
  cin >> s;
  int n = s.size();
  string t = s.substr(0, (n - 1) / 2);
  string r = s.substr((n + 3) / 2 - 1, n - 1);
  if (func(s) && func(t) && func(r)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <complex>
#define full(c) c.begin(), c.end()
#define vector2d(name,type,h,w,init) vector<vector<type>> name(h,vector<type>(w,init)) 
const int PRIME = 1000000007;
const int INT_INF = 2147483647;
const long long int LL_INF = 9223372036854775807;
const double PI = acos(-1);
const double EPS = 0.000000001;
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;

int main() {
	int i, n, l = 0, r = 0;
	string s;
	cin >> n;
	cin >> s;
	i = 0;
	while (s[i] == '<') i++, l++;
	i = n - 1;
	while (s[i] == '>') i--, r++;
	cout << n - min(l, r) << endl;
	return 0;
}



Measured memory_bytes: 3304
N = int(input())
S = input()
l1 = length = 0
l2 = 1

while (l2 + length < N):
    if S[l1:l2] in S[l2:]:
        length = l2 - l1
        l2 += 1
    else:
        l1 += 1
        l2 = l1 + length + 1
print(length)


Measured memory_bytes: 3060
from collections import Counter
import itertools
N = int(input())
S = []
for i in range(N):
    tmp = list(input())
    S.append(tmp[0])
Ini = Counter(S)
seq = ['M','A','R','C','H']
COMB = list(itertools.combinations(seq, 3))
sum = 0
for i in range(len(COMB)):
    sum += Ini[str(COMB[i][0])] * Ini[str(COMB[i][1])] * Ini[str(COMB[i][2])]
print(sum)


Measured memory_bytes: 4224
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;
#define MOD 1000000007
#define EPS 10e-8
ll dp[1000000][3];


int main(){
    int N;
    cin >> N ;
    ll a[100007],b[100007],c[100007];
    rep(i,N){
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[0][0]=dp[0][1]=dp[0][2]=0;
    for(int i=1;i<=N;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i-1];
        dp[i][1]=max(dp[i-1][2],dp[i-1][0])+b[i-1];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i-1];
    }
    cout << max(dp[N][0],max(dp[N][1],dp[N][2])) << endl;
}

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

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

// template starts
typedef long long int ll;

// template ends here
const ll mx = 1e7 + 1;
ll arr[mx];

void solve(){
	// code starts from here
	ll N;
	cin >> N;
	
	
	for(int i = 1; i <= N; i++){
		for(int j = i; j <= N; j+= i){
			arr[j]++;
		}
	}
	
	ll ans = 0;
	for(ll i = 1; i <= N; i++) ans += (i*arr[i]);
	cout << ans << endl;
}

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

	int T;
	T = 1;
	while(T--){
		solve();
	}

	return 0;
}


Measured memory_bytes: 81724
import java.util.*;



public class Main {

    static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
    static long mod = 1000000007;

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

        int point =0;
        int rCount =0;
        int lCount =0;
        boolean rCounting = true;
        int[] ans = new int[S.length];
        for(int i=0;i<S.length;i++){

            if(i>0 && S[i] == 'R' && S[i-1] == 'L'){
                ans[point-1] = (rCount +1)/2 + lCount/2;
                ans[point] = (lCount+1)/2 + rCount/2;
                rCounting = true;
                rCount = 1;
                lCount = 0;

            } else if(i>0 && S[i] == 'L' && S[i-1] == 'R'){
                point = i;
                rCounting = false;
                lCount = 1;


            } else {
                if(rCounting){
                    rCount++;
                } else {
                    lCount++;
                }

            }

            if(i == S.length-1) {
                ans[point-1] = (rCount +1)/2 + lCount/2;
                ans[point] = (lCount+1)/2 + rCount/2;
            }

        }

        for(int a: ans){
            System.out.print(a + " ");

        }


    }

}




Measured memory_bytes: 54068
#include <stdio.h>
#include <cassert>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <iomanip>
 
#ifdef LOCAL_CODE
	#define DEBUG(x) cerr << "[" << #x << '=' << x << "]" << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int i = (N)-1; i >= 0; i--)
#define REP(i, N) for(int i = 0; i < (int)(N); i++)
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.first >> p.second; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.first << ' ' << p.second; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

int n,m;
void solve(istream& cin, ostream& cout) {
	cin >>n;
	string S;
	cin >> S;
	if(S.size() <= n) cout << S;
	else {
		cout <<S.substr(0, n)<<"...";
	}
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
double dp[3001][3001]; // dp[Nth coin][count of heads]
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<double> P(N);
    for (double & p : P) cin >> p;
    dp[0][0] = 1.0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i+1][j] += dp[i][j]*(1.0-P[i]);
            dp[i+1][j+1] = dp[i][j]*P[i];
        }
    }
    double ans = 0.0;
    for (int i = (N+1)/2; i <= N; ++i) {
        ans += dp[N][i];
    }
    printf("%.10lf\n", ans);
    return 0;
}

Measured memory_bytes: 70656
import numpy as np
N=int(input())
a = sorted(map(int, input().split()),reverse=True)

pA=[]
pB=[]
  
for i in range(N):
  m=a[i]
  if i%2==0:
    pA.append(m)
  else:
    pB.append(m)
print(sum(pA)-sum(pB))

Measured memory_bytes: 12508
#include <bits/stdc++.h>
using namespace std;
//cin.ignore();	// better to use 2 times getline(cin,s);
// g++ iterator.cpp -std=c++17
//cout << (A + B == C ? "YES" : "NO") << endl;
//__gcd(a,b)
#define pb push_back
#define mk make_pair
#define vll vector<ll>
#define mll map<ll,ll >
#define mlli map<ll,ll>::iterator
#define size size()
#define endl "\n"
#define ll long long int
#define ld long double
void fast(){ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);}


int main(void)
{
	fast();
	int p,q,r;
	cin>>p>>q>>r;
	int a[p];
	int b[q];
	int mina = INT_MAX;
	int minb = INT_MAX;
	for(int i=0;i<p;i++)
	{
	    cin>>a[i];
	    mina = min(mina,a[i]);
	}
	for(int i=0;i<q;i++)
	{
	    cin>>b[i];
	    minb = min(minb,b[i]);
	}
	int minc = INT_MAX;
	for(int i=0;i<r;i++)
	{
	    int x,y,z;
	    cin>>x>>y>>z;
	    minc = min(minc,a[x-1]+b[y-1]-z);
	}
	cout<<min(minc,mina+minb)<<endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <cmath>
#include <iomanip>
#include <iostream>

 using namespace std;

int main(){

 long long a,b,c;
 cin>>a>>b>>c;

 long long ans = c-a-b;

 if(ans < 0){
    cout<<"No"<<endl;
   return 0;
 }

 ans *= ans;
 long long y = 4*a*b;


 if(y< ans)
    cout<<"Yes"<<endl;
 else
    cout<<"No"<<endl;

return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().strip().split(' ')))

def gcd(x, y): 
  
   while(y): 
       x, y = y, x % y 
  
   return x 
  

GG=[0]*N
GG[0]=A[0]
for i in range(1,N):
    GG[i]=gcd(GG[i-1],A[i])

GG2=[0]*N
GG2[-1]=A[-1]

for i in range(2,N+1):
    GG2[-i]=gcd(GG2[-(i-1)],A[-i])

ans=[0]*N

ans[0]=GG2[1]
ans[-1]=GG[N-2]
#print(GG)
#print(GG2)
#print(ans)


temp=ans[0]
for i in range(1,N-1):
    ans[i]=gcd(GG[i-1],GG2[i+1])
    if ans[i]>temp:
        temp=ans[i]
if ans[-1]>temp:
    temp=ans[-1]


print(temp)    

Measured memory_bytes: 14076
#include <stdio.h>
#include <stdlib.h>

const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
 
int calculateHeuristic(int board[3][3]) {
    int res = 0;
    int a, i, j;
    
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++) {
            if (board[i][j] == 0) continue;
            a = board[i][j] - 1;
            res += abs(a / 3 - i) + abs(a % 3 - j);
        }
    
    return res;
}

void swap(int * a, int * b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int check(int board[3][3], int limit, int depth, int prev, int py, int px) {
    int heuriScore = calculateHeuristic(board);
    
    if (heuriScore + depth > limit) return 0;
    
    // same board!! success!
    if (heuriScore == 0) return 1;
    
    for (int i = 0; i < 4; i++) {
        if (abs(i - prev) == 2) 
            continue;
        
        // new position
        int ny = py + dy[i];
        int nx = px + dx[i];
        
        // skip if swapping is out of boundary
        if (ny <  0 || nx <  0 || ny >= 3 || nx >= 3) 
            continue;
        
        // try swapping
        swap(&board[ny][nx], &board[py][px]);
        
        // return if success
        if (check(board, limit, depth + 1, i, ny, nx))
            return 1;
        
        // not work, swap back
        swap(&board[ny][nx], &board[py][px]);
    }
    
    return 0;
}
 
void solve(int board[3][3], int py, int px) {
    int limit = 0;
    
    while (1) {
        if (check(board, limit, 0, 99, py, px)) {
            printf("%d\n", limit);
            return;
        }
        limit++;
    }
}
 
int main(int argc, char** argv) {
    int py, px, i, j;
    int board[3][3];
    
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++) {
            scanf("%d", &board[i][j]);
            
            if (board[i][j] == 0) {
                py = i;
                px = j;
            }
        }

    solve(board, py, px);
    
    return (EXIT_SUCCESS);
}





Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    int x = (int)log2(n);
    cout << (int)pow(2,x) << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define vi vector<int>
#define Vi vector<vector<int>>
#define ll long long
#define P pair<int,int>
#define vp  vector<P>
#define mod 1000000009
using namespace std;
int main(){
	ll n,a,b;
	cin>>n>>a>>b;
	ll ans=(n/(a+b));
	ll rem=n-ans*(a+b);
	ans*=a;
	ans+=(rem<=a?rem:a);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map(String::toInt)
    val hList = readLine()!!.split(' ').map(String::toInt)
    val dp = Array(n) { Long.MAX_VALUE }
    dp[0] = 0L
    for (ni in 1 until n) {
        for (ki in 1..Math.min(k, ni)) {
            dp[ni] = Math.min(
                    dp[ni],
                    dp[ni - ki] + Math.abs(hList[ni] - hList[ni - ki])
            )
        }
    }
    println(dp.last())
}


Measured memory_bytes: 121568
#include<vector>
#include<map>
#include<algorithm>
#include<set>
#include<iostream>
#include<string>
#include<set>
#include<queue>
#include<random>
#include<unordered_set>

using namespace std;

/*

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

tree<pair<long long, long long>, null_type, less<pair<long long, long long>>, rb_tree_tag, tree_order_statistics_node_update> st;

*/
/*

st.find_by_order();
st.order_of_key();

*/

#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")

#define pb push_back
#define ld long double
#define int long long

mt19937 rnd(51);

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    cout << n + n * n + n * n * n;
    return 0;
}


Measured memory_bytes: 3196
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>

#pragma comment(linker, "/STACK:336777216")  

using namespace std;

const int MAXN = 200 + 10;

int N, M;

void Work()
{
	multiset <int> S;
	scanf("%d", &N);
	for (int i = 0; i < N; i ++)
	{
		int t;
		scanf("%d", &t);
		S.insert(t);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i ++)
	{
		int t;
		scanf("%d", &t);
		auto it = S.find(t);
		if (it == S.end())
		{
			printf("NO\n");
			return;
		}
		S.erase(it);
	}
	printf("YES\n");
}

int main()
{
	Work();
	return 0;
}

Measured memory_bytes: 9600