akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define mod (ll)(1e9+7)
#define d(x) cerr<<#x<<"="<<x<<endl;
#define p(x) cout<<(x)<<endl
#define ps(x) cout<<(x);
#define pk(x) cout<<(x)<<" ";
#define pfix(d,x) cout << fixed << setprecision(d) << x << endl;
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define minel(v) *min_element(all(v))
#define minind(v) distance((v).begin(), min_element(all(v)))
#define maxel(v) *max_element(all(v))
#define maxind(v) distance((v).begin(), max_element(all(v)))
#define p2d(v,n,m) rep(i,n){rep(j,m){pk(v[i][j]);}p("");}
#define fi first
#define se second
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll d,n,m,x,y,z,h,w,k,mi=inf,ma=-inf,ans,s,t,l,r,res,tmp,itr,p,q;
bool flag;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dx8[8]={1,1,0,-1,-1,-1,0,1},dy8[8]={0,1,1,1,0,-1,-1,-1};
char cha;
string st;
typedef map<ll, ll> imap;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<pair<ll,ll> > VP;
P pa;


// mod_tools
ll fact[500000];

ll mpow(ll x, ll y){
    //d(x)
    if(y==0) return 1;
    if(y%2==0){
        return mpow(x*x%mod,y/2)%mod;
    }
    else{
        return x*mpow(x,y-1)%mod;
    }
}

ll minv(ll x){
    // only available for mod=10^9+7
    return mpow(x,mod-2);
}

// Please run this func for preparation
void mfact(){
    //prepare fact-array
    fact[0]=1;
    rep(i,1,500000){
        fact[i]=fact[i-1]*i%mod;
    }
}

//combiの呼び出しが大きいときはこれを使う
ll combi(ll n, ll k){
    return (fact[n]*minv(fact[k])%mod)*minv(fact[n-k])%mod;
}

//combiを一回呼び出すだけなら直接計算

ll a[1000000];

int main(void){
    cin>>n;
    VL v;
    imap M;
    rep(i,n){
        cin>>tmp;
        M[tmp]++;
    }
    ll cnt;
    priority_queue<ll> Q;
    priority_queue<ll> SQ;
    for(auto itr=M.begin();itr!=M.end();++itr){
        tmp=itr->first;
        cnt=itr->second;
        if(cnt>=2){
            Q.push(tmp);
        }
        if(cnt>=4){
            SQ.push(tmp);
        }
    }
    if(Q.size()<2){
        p(0);
        return 0;
    }
    if(SQ.size()==0){
        tmp=Q.top();
        Q.pop();
        p(tmp*Q.top());
    }
    else{
        tmp=Q.top();
        Q.pop();
        p(max(tmp*Q.top(),SQ.top()*SQ.top()));
    }
    return 0;
}


Measured memory_bytes: 6528
/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 1e5 + 10;

int n;
ll a[MAXN], b[MAXN], ans;

int main(){
    #ifndef SAKO
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    #endif // SAKO
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i];

    for (int i = n; i >= 1; --i){
        a[i] += ans;
        ans += ((a[i] + b[i] - 1) / b[i]) * b[i] - a[i];
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> S(N);
  REP(i, M) {
    int k;
    cin >> k;
    REP(j, k) {
      int x;
      cin >> x;
      x--;
      S[x] |= 1 << i;
    }
  }
  int p = 0;
  for (int i = 0; i < M; i++) {
    int x;
    cin >> x;
    p |= x << i;
  }
  int ans = 0;
  REP(i, 1 << N) {
    int s = p;
    REP(j, N) if (i >> j & 1) s ^= S[j];
    if (s == 0) ans++;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

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

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

ll N;
ll a[5];

int main(){
    cin >> N;
    REP(i,5) cin >> a[i];
    sort(a,a+5);
    ll ans = 0;
    ans = (N + a[0] - 1) / a[0] + 4;
    
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-
def main():
  S=input()
  count = 0
  if len(S) % 2:	#kisuu
    for i in range(len(S) // 2):
      if S[i] == S[len(S)-i-1]:
        a=0
      else:
        count = count + 1
  else:
    for i in range(len(S) // 2):
      if S[i] == S[len(S)-i-1]:
        a=0
      else:
        count = count + 1
  print(count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <iostream>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<fstream>
#include<queue>
using namespace std;
void ll(){
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(0);
}
int main()
{
	ll();

	vector<int> v;
	int arr[1000];
	int n,d=0,t=0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		v.push_back(arr[i]);
	}

		sort(v.begin(), v.end());

		d = v[n - 1] - v[0];
	cout << d << endl;
}

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

#define ll long long
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll mod=1000000007;

using namespace std;

ll d[1010][1010];
char c[1010][1010];
ll n,m;

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


    memset(d,0,sizeof(d));
    for (ll i=1;i<=n;i++){
        for (ll j=1;j<=m;j++){
            cin>>c[i][j];
        }
    }
    d[1][0]=1;
    for (ll i=1;i<=n;i++){
        for (ll j=1;j<=m;j++){
            d[i][j]=d[i][j-1]+d[i-1][j];
            d[i][j]%=mod;
            if (c[i][j]=='#')d[i][j]=0;
        }
    }
    cout<<d[n][m]%mod;
	return 0;
}


Measured memory_bytes: 9216
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <functional>

using namespace std;
using ll = long long;

#define FOR(i, m, n) for(int i = (m);i < (n);i++)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;


int main() {
	int A, B;
	cin >> A >> B;
	string S;
	cin >> S;
	REP(i, A) {
		if (S[i] == '0' || S[i] == '1' || S[i] == '2' || S[i] == '3' || S[i] == '4' || S[i] == '5' || S[i] == '6' || S[i] == '7' || S[i] == '8' || S[i] == '9') continue;
		cout << "No" << endl;
		return 0;
	}

	if (S[A] != '-') {
		cout << "No" << endl;
		return 0;
	}
	FOR(i, A+1, S.size()) {
		if (S[i] == '0' || S[i] == '1' || S[i] == '2' || S[i] == '3' || S[i] == '4' || S[i] == '5' || S[i] == '6' || S[i] == '7' || S[i] == '8' || S[i] == '9') continue;
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
static const double pi = 3.141592653589793;



int main(){
    ll N, A;
    cin>>N>>A;
    Yes(N%500<=A);
}

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

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999999;
	
	
	public static void Main(string[] args)
	{
		var p = Input().ToInt();
		
		
		var j = GetPt(p[0])+GetPt(p[1]);
		if(p[0]==p[1]&&p[0]==1)
			j+=400000;
		Console.WriteLine(j);
	}
	
	
	static int GetPt(int rank)
	{
			if(rank==1)
				return 300000;
			if(rank == 2)
				return 200000;
			if(rank == 3)
			return 100000;
			return 0;
			}
			

	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str, int offset = 0)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt() + offset;
		return r;
	}
}

Measured memory_bytes: 13140
#include <stdio.h>
#include <string.h>
int main(void){
	char s[1026];
	char ans[500][7];
	int i,j,k,c;
	fgets(s,1026,stdin);
	for(i=0,j=0,c=0;i<strlen(s);i++){
		if(s[i]==' '||s[i]==','||s[i]=='.'){
			if(3<=c&&c<=6){
				for(k=0;k<c;k++){
					ans[j][k]=s[i-c+k];
				}
				ans[j][k]=0;
				j++;
			}
			c=0;
		}
		else
			c++;
	}
	for(i=0;i<j;i++){
		if(i>0)
			putchar(' ');
		printf("%s",ans[i]);
	}
	puts("");
	return 0;
}

Measured memory_bytes: 528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

ll n,m;
vector<ll> a(100010);
vector<ll> dp(100010);

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    rep(i,m){
      cin>>a[i];
      dp[a[i]]=-1;
    }
    dp[0]=1;
    if(dp[1]==0) dp[1]=1;
    FOR(i,2,n+1){
      if(dp[i]<0) continue;
      if(dp[i-1]>=0){
        dp[i]+=dp[i-1];
        dp[i]%=mod;
      }
      if(dp[i-2]>=0){
        dp[i]+=dp[i-2];
        dp[i]%=mod;
      }
    }
    cout<<dp[n]<<endl;
}

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

using namespace std;

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

    vector<long long> a(k);
    for(int i=1;i<=n;i++){
        a[i%k]++;
    }
    long long res=0;
    for(int i=0;i<k;i++){
        int b=(k-i)%k;
        int c=(k-i)%k;
        if((b+c)%k!=0)continue;
        res+=a[i]*a[b]*a[c];
    }
    cout<<res;
}


Measured memory_bytes: 1792
import math

def main():
    N = int(input())
    ans = [0]*(N)
    n = int(math.sqrt(N))
    for x in range(1, n+1):
        for y in range(1, n+1):
            for z in range(1, n+1):
                s =x**2 + y**2 + z**2 + x*y + y*z + z*x
                if s < N+1:
                    ans[s - 1] += 1
    for i in ans:
        print(i)
    
if __name__ == '__main__':
    main()

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

int main(){
  int N, Y;
  cin >> N >> Y;

  int Yukichi = -1, Ichiyou = -1, Hideyo = -1;
  for (int a = 0; a <= N; a++) {
    for (int b = 0; b + a <= N; b++) {
      int c = N - a - b;
      int total = 10000*a + 5000*b + 1000*c;
      if (total == Y) {
        Yukichi = a;
        Ichiyou = b;
        Hideyo = c;
      }
    }
  }
  
  cout << Yukichi << ' ' << Ichiyou << ' ' << Hideyo << endl;
}


Measured memory_bytes: 256
//Harjot Singh Student NIT JALANDHAR	

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

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long int ll;
ll dp[3001][3001][2];

ll solve(ll *arr,int i,int j,int state)
{

	if(i>j) return 0;

	if(dp[i][j][state]!=-1) return dp[i][j][state];

	if(state==1)
		return dp[i][j][state]=max(arr[i]+solve(arr,i+1,j,0),arr[j]+solve(arr,i,j-1,0));
	else
		return 	dp[i][j][state]=min(solve(arr,i+1,j,1),solve(arr,i,j-1,1));

}

int main()
{
    
    int  n;
    cin>>n;
    ll arr[n+1];ll sum=0;
    for(int i=1;i<=n;i++)
    {
    	cin>>arr[i];sum+=arr[i];
    }
    memset(dp,-1,sizeof(dp));
    ll x=solve(arr,1,n,1);
    ll y=sum-x;

    cout<<x-y<<endl;


	return 0;
}

Measured memory_bytes: 141184
/**
 *    author:  morato
 *    created: 15.09.2020 09:02:33
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int64_t x;
  cin >> x;
  map<int64_t, int> mp;
  for (int64_t i = 2; i * i <= x; i++) {
    while (x % i == 0) {
      mp[i]++;
      x /= i;
    }
  }
  if (x > 1) mp[x]++;
  int ans = 0;
  for (auto it = mp.begin(); it != mp.end(); it++) {
    int cnt = 1;
    while (cnt <= it->second) {
      it->second -= cnt;
      cnt++;
      ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3588
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#define re(i,a,b) for(int i=a;i<=b;i++)
#define _re(i,a,b) for(int i=a;i>=b;i--)
#define for_edge(x) for(int i=head[x];i;i=e[i].nxt)
#define ll long long
#define maxn 100005
#define inf 1e9
using namespace std;
inline int read(){char c = getchar();int ans = 0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){ans = ans*10 + c - '0';c = getchar();}return f*ans;}
//____________________________________________________________________________________________________________________________________________________________________
struct edge
{
	int nxt,to;
	edge(int nxt=0,int to=0)
	:nxt(nxt),to(to){};
}e[maxn*2];
int head[maxn],TOT=1,n,sg[maxn];
inline void add(int x,int y)
{
	e[++TOT] = edge(head[x],y) ; head[x] = TOT;
}
void dfs(int x,int fa)
{
	for_edge(x)
	{
		int y = e[i].to ;
		if(y==fa)
			continue;
		dfs(y,x);
		sg[x]^=sg[y]+1;
	}
}
int main()
{
	n = read();
	re(i,1,n-1)
	{
		int x = read() , y= read();
		add(x,y);add(y,x);
	}
	dfs(1,0);
	if(sg[1])
		printf("Alice\n");
	else printf("Bob\n");
}

Measured memory_bytes: 7168
import java.util.Scanner;

/**
 * B - Count ABC
 * 英大文字のみからなる長さ N の文字列 S があります。
 * S の連続する部分列 (入出力例をご覧ください) として ABC がいくつ含まれるかを求めてください。
 */
public class Main {

    public static void main( String[] args ) {

        Scanner sc = new Scanner( System.in );
        // 入力値
        int n = sc.nextInt();   // 文字列Sの長さ
        String s = sc.next();   // 英大文字のみからなる文字列

        String replaceStr = s.replaceAll( "ABC", "" );
        System.out.println( ( n - replaceStr.length() ) / 3 );

        sc.close();
    }
}

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

def main():
    while True:
        height,width=map(int,input().split())
        if height==0 and width==0:
            break
        for i in range(height):
            sharp=""
            for j in range(width):
                sharp+="#"
            print(sharp)
        print("")
            
if __name__=="__main__":
    main()


Measured memory_bytes: 5624
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N,K;
    cin >> N >> K;
    vector<int> l(N);
    for(int i = 0 ; i < N ; i++){
        cin >> l.at(i);
    }
    sort(l.begin(), l.end(), greater<int>());
    int answer = 0;
    for(int i = 0 ; i < K ; i++){
        answer += l.at(i);
    }
    printf("%d\n",answer);
    

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > piii;
#define pb push_back
#define NeedForSpeed ios_base::sync_with_stdio(0), cin.tie(0)
#define PI acos(-1)
#define all(c) c.begin(), c.end()
#define SET(x, y) memset((x), y, sizeof(x))
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const ll INF64 = 1e18;

template <typename T>
string to_string(const vector<T> &v) {
  string ret = "<";
  for (auto it : v)
    ret += to_string(it) + ", ";
  ret.pop_back(); ret.pop_back();
  ret += ">";
  return ret;
}

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_print() { cerr << endl; }

template <typename T, typename ...U>
void debug_print(T t, U... u) {
  cerr << " " << to_string(t);
  debug_print(u...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_print(__VA_ARGS__)
const int N = 1e5 + 5;

int main() {
  ll d, t, s;
  cin >> d >> t >> s;
  cout << (t * s >= d ? "Yes" : "No") << '\n';
  //If you dont need Flush Stream, dont use endl
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
using namespace std;
int main(void){
  int n,m,r,ans=-1000000001;
  cin>>n;
  cin>>m;
  for(int i=1;i<n;i++){
    cin>>r;
    ans=max(ans,r-m);
    m=min(m,r);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int inf = 1000000;

ll f (ll b, ll n) {
  ll ans = 0;
  while(n) {
    ans += n % b;
    n /= b;
  }
  return ans;
}

ll solve(ll n, ll s) {
  if (n < s) {
    return -1;
  }
  
  if (n == s) {
    return n + 1;
  }
  
  ll b = 2;
  for (; b * b <= n; b++) {
    if (f(b, n) == s) {
      return b;
    }
  }
  
  for (ll p = b - 1; p >= 1; p--) {
    b = (n - s) / p + 1;
    if (b <= 1) {
      continue;
    }
    if (f(b, n) == s) {
      return b;
    }
  }
  return -1;
}

int main(int argc, const char * argv[]) {
  ll n, s;
  cin >> n >> s;
  cout << solve(n, s) << endl;
  return 0;
}


Measured memory_bytes: 256
import math


nums = list(map(int, [input() for _ in range(5)]))
s = sum(math.ceil(num / 10) * 10 for num in nums)
m = min([int(str(num)[-1]) for num in nums if num % 10 != 0], default=0)
if m != 0:
  s -= (10-m)
print(s)

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

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
 	int N,K;
 	cin>>N>>K;
 	unordered_map<int,int>mp;
 	for(int i=0; i<N; i++){
 		int A;
 		cin>>A;
 		mp[A]++;
 	}
 	vector<int>v;
 	for(auto p:mp){
 		v.push_back(p.second);
 	}
 	sort(v.begin(),v.end());
 	int sum=0;
 	if(v.size()<=K){
 		cout<<0<<endl;
 	}
 	else{
 		for(int i=0; i<v.size()-K; i++){
 			sum+=v[i];
 		}
 		cout<<sum<<endl;
 	}
 }

Measured memory_bytes: 10312
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define n_p(v) next_permutation(v.begin(),v.end())
#define to_ll(b) stoll(b)
#define MOD 1000000007
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp

signed main(){
	ll n,m; cin>>n>>m;
	vvl vec(n,vl(0));
	rep(i,0,m){
		ll a,b; cin>>a>>b;
		--a; --b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	vl dist(n,-1);
	dist[0]=0;
	vl fro(n,-1);
	fro[0]=0;
	queue<ll> q;
	q.push(0);
	while(!q.empty()){
		ll v=q.front(); q.pop();
		for(ll c:vec[v]){
			if(dist[c]!=-1) continue;
			dist[c]=dist[v]+1;
			fro[c]=v;
			q.push(c);
		}
	}
	cout<<"Yes"<<endl;
	rep(i,0,n){
		if(i==0) continue;
		ll ans=fro[i];
		++ans;
		cout<<ans<<endl;
	}
		
	return 0;
}

Measured memory_bytes: 13784
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const double PI = acos(-1.0);

ll lcm(ll a, ll b)
{
    ll x = __gcd(a, b);
    return ((a/x)*b);
}

int main()
{
    int n, m;
    cin >> n >> m;
    int sum = 0, a[m];
    for(int i = 0; i < m; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    if(sum <= n)
    {
        cout << n-sum << endl;
    }
    else
    {
        cout << "-1" << endl;
    }
    cout << endl;
    return 0;
}



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

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define sz size()
#define mp make_pair
#define pii pair<int,int>

const ll mod = 1e9+7;

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

	string ans;

	for(int i = 0;i < s.sz;i+=w)ans += s[i];

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
//#define _GRIBCXX_DEBUG
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;


// ?????¬???????????¬??????
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<double> vd;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<long, long> pil;


// Effective std
template<typename C, typename T>
constexpr int count(C& c, T t) { return count(ALL(c), t); }

template<typename C, typename F>
constexpr int count_if(C& c, F f) { return count_if(ALL(c), f); }

template<typename C, typename T, typename U>
constexpr void replace(C& c, T t, U u) { replace(ALL(c), t, u); }

template<typename C, typename F, typename U>
constexpr void replace_if(C& c, F f, U u) { (ALL(c), f, u); }

template<typename C>
constexpr void sort(C& c) { sort(ALL(c)); }

template<typename C, typename Pred>
constexpr void sort(C& c, Pred p) { sort(ALL(c), p); }


// ??°?????????????????¬??????
typedef int Weight;

struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) {}
};

bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight :
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

int gcd(int a, int b) {
  while(b) {
    int tmp;
    tmp = a;
    a = b;
    b = tmp%b;
  }
  return a;
}

int main() {
  int a, b;
  cin >> a >> b;

  cout << gcd(a, b) << endl;
  return 0;
}

Measured memory_bytes: 3056
from sys import stdin
from itertools import groupby

n = int(stdin.readline().rstrip())

li = list(map(int,stdin.readline().rstrip().split()))

li1 = []
li2 = []

for i in range(n):
    if i % 2 == 0:
        li1.append(li[i])
    else:
        li2.append(li[i])

li1.sort()
li2.sort()

lin = []
lin2 = []

for key, value in groupby(li1):
    lin.append((key,len(list(value))))
for key, value in groupby(li2):
    lin2.append((key,len(list(value))))

lin.sort(key=lambda x:(x[1]))
lin2.sort(key=lambda x:(x[1]))

point = 0

if lin[-1][0] == lin2[-1][0] and lin[-1][1] == lin2[-1][1]:
    if len(lin) == 1:
        print(n//2)
    else:
        if lin[-2][1] >= lin2[-2][1]:
            print(n-lin[-2][1]-lin2[-1][1])
        else:
            print(n-lin[-1][1]-lin2[-2][1])

elif lin[-1][0] == lin2[-1][0]:
    if len(lin) == 1:
        print(n//2-lin2[-2][1])
    elif len(lin2) == 1:
        print(n//2-lin[-2][1])
    else:
        if lin[-2][1] >= lin2[-2][1]:
            print(n-lin[-2][1]-lin2[-1][1])
        else:
            print(n-lin[-1][1]-lin2[-2][1])
else:
    print(n-lin[-1][1]-lin2[-1][1])

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

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int INF = int (1e9) + int (1e5);
const ll INFL = ll(2e18) + ll(1e10);
const ui MOD = 1E9 + 7;
const double EPS = 1e-9;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define ROF(i,x) for(int i = (x) ; i >= 0 ; --i)
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ODD(x) ( ((x)&1)==0?0:1 )
#define SIGN(x) ( ((x) > 0) - ((x) < 0)  )
#define dbg(x) cerr << #x"= " << x << endl

std::mt19937_64  generator(std::chrono::system_clock::now().time_since_epoch().count());

inline ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a, ll b) { return a ? gcd(b%a, a): b; }
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }


void READ(bool _local){
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
    if (_local)
        freopen ("in.txt", "r", stdin);
#endif
}

int main() {
    READ(0);
    int n,r;cin>>n>>r;
    if (n>=10) cout << r;
    else{
        cout << r + 100*(10-n);
    }


    return 0;
}



Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define pb push_back
#define f first
#define s second
#define endl "\n"
#define F(i,n) for(ll i=0;i<n;i++)
#define mem(x,val) memset(x,val,sizeof(x))
#define mod 1000000007
#define crap ios::sync_with_stdio(false);cin.tie(NULL);cerr.tie(NULL)
 
int main()
{
    crap;
    ll T = 1;
    //cin>>T;
    while(T--){
    	ll h,a; cin>>h>>a;
    	cout<<h/a + (h%a!=0);
        //ll n; cin>>n;
        //vector<ll> a(n); F(i,n) cin>>a[i];
    }
}

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

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  string ans = "No";
  while (n) {
    if (n%10==9) ans = "Yes";
    n /= 10;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

A, B, H, M = map(int,input().split())
ji = 30*H+M/2
hun = 6*M
ans = 0

if(ji==hun):
    print(abs(A-B))
elif(ji<hun):
    kaku = hun-ji
    sink = A*math.sin(math.radians(kaku))
    cosk = A*math.cos(math.radians(kaku))
    ans = math.sqrt((B-cosk)**2+sink**2)
    print(ans)
else:
    kaku = hun-ji
    sink = B*math.sin(math.radians(kaku))
    cosk = B*math.cos(math.radians(kaku))
    ans = math.sqrt((A-cosk)**2+sink**2)
    print(ans)





#print(ans)


Measured memory_bytes: 75348
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc =  new Scanner(System.in);
  int n = sc.nextInt();
  int w[] =new int[n];
    for(int count=0;count<n;count++){
      w[count]=sc.nextInt();
    }
  int min= 0;
  int min2=100;
    for(int t=1;t<=n;t++){
      int upn=0;
      int dun=0;
  for(int count=0;count<n;count++){
   if((t-1)<=count) dun+=w[count];
    else upn+=w[count];
    }min=upn-dun;
    if(min<0) min*=-1;
      if(min2>min) min2=min;
    }System.out.println(min2);
}
}

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

int main(){
    
    int l, r, d;
    cin >> l >> r >> d;
    
    int res = 0;
    for(;l <= r; l++){
        if(l%d == 0){
            //cout << l << " ";
            res += 1;
        }
    }
    
    cout << res << endl;
    
}


Measured memory_bytes: 3684
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    let s = read::<String>();
    if s == "Sunny" {
        println!("Cloudy");
    } else if s == "Cloudy" {
        println!("Rainy");
    } else if s == "Rainy" {
        println!("Sunny");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define dbg(x) cout<<"( "<<#x<<" -> "<<x<<" )"<<endl;
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int mini=INT_MAX;
    for (int i=0;i<=(s.length()-t.length());i++)
    {
        string s1=s.substr(i,t.length());
        int cnt=0;
        for (int j=0;j<t.length();j++)
        {
            if (s1.at(j)!=t.at(j))
            cnt++;
        }
        mini=min(mini,cnt);
    }
    printf("%d\n",mini);
    return 0;
}

Measured memory_bytes: 3720
// u -> v same: ban u -> v, u is reachable from v ^ vice versa = 0
// Problem : F - Two Faced Edges
// Contest : AtCoder Regular Contest 092
// URL : https://atcoder.jp/contests/arc092/tasks/arc092_d
// Memory Limit : 256 MB
// Time Limit : 5000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define cerr if(1)cerr
#define size(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define sort(a, n) sort(a + 1, a + n + 1)
#define temptts template <class T, class... Ts>

const int N = 1001, M = 2e5 + 2, mod = 1e9 + 7, inf = 2e9;

struct edge_list {
	int u, v;
} edge[M];

bool vis[N];
vector<int> adj[N], radj[N];
int n, m, ban, ans[M], cur[M];

void dfs(int v) {
	vis[v] = 1;
	for (auto id : adj[v]) {
		int u = edge[id].v;
		if (u == ban || vis[u]) continue;
		dfs(u);
	}
}

int main() { cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		edge[i] = {u, v};
		adj[u].push_back(i);
		radj[v].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof vis);
		ban = 0;
		dfs(i);
		for (auto id : radj[i]) {
			ans[id] ^= vis[edge[id].u];
		}
		ban = i;
		memset(vis, 0, sizeof vis);
		for (auto id : adj[i]) {
			int u = edge[id].v;
			cur[id] |= vis[u];
			dfs(u);
		}
		memset(vis, 0, sizeof vis);
		for (int k = size(adj[i]) - 1; k >= 0; k--) {
			int id = adj[i][k], u = edge[id].v;
			ans[id] ^= cur[id] | vis[u];
			dfs(u);
		}
	}
	for (int i = 1; i <= m; i++) {
		puts(ans[i] ? "diff" : "same");
	}
}


Measured memory_bytes: 7936
#include<stdio.h>
int main(void)
{
	int a,b,c,i,m;
	scanf("%d %d %d", &a, &b, &c);
	i = 1;
	m = 0;
	while (i <= 10000){
		if (c%i == 0 && a <= c / i&&c / i <= b)
			m = m + 1;
		i++;
	}
	printf("%d\n", m);
	

	return 0;
}

Measured memory_bytes: 1024
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
import statistics
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
l=[lmp() for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(n):
    a[i]=l[i][0]
    b[i]=l[i][1]
ma=statistics.median(a)
mb=statistics.median(b)
if n%2==0:
    print(int((mb-ma)*2+1))
else:
    print(int((mb-ma)+1))

Measured memory_bytes: 52632
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(998244353)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(10)
#define highest(x) (63 - __builtin_clzl(x))

int main(){
    int N;
    cin >> N;
    string back;
    cin >> back;
    map<string, int> W;
    W[back]++;
    for(int i = 1; i < N; i++){
        string this_W;
        cin >> this_W;
        if(back.back() != this_W[0] || W[this_W]){
            cout << "No" << endl;
            return 0;
        }
        back = this_W;
        
        W[this_W]++;
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
    int n,m;
    cin >>n >>m;
    vector<ll> a(n),b(m);
    rep(i,n) cin >>a[i];
    rep(i,m) cin >>b[i];

    ll g = a[0];
    rep(i,n) g = __gcd(g,a[i]);

    ll ans = 0;

    auto check = [&](ll x){
        rep(i,m)if(x%b[i] != 0) return;
        ++ans;
    };

    for(ll i=1; i*i<=g; ++i){
        if(g%i == 0){
            check(i);
            if(g/i != i) check(g/i);
        }
    }

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



Measured memory_bytes: 3116
mod = 10**9+7
N = int(input())

a=[[1]]
for i in range(1,N):
    tmp=[1]
    if i >1:
        for j in range(1,i):
            tmp.append(a[i-1][j-1]+a[i-1][j])
    tmp.append(1)
    a.append(tmp)

res = 0
for i in range(N//3):
  res += a[N-3-2*i][i] % mod

print(res % mod)

Measured memory_bytes: 480972
s = input()
t = input()
length_t = len(t)
counts = []
for i in range(len(s)-len(t)+1):
    tmp_s = s[i:i+length_t]
    counts.append(sum([False if tmp_s[j] == t[j] else True for j in range(length_t)]))
print(min(counts))

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

using namespace std;

const int NMAX = 2e5;

long long n;
pair<pair<long long,long long >,long long> segm[NMAX + 5];
pair<long long,long long> sect;
pair<long long,long long> suff_sect[NMAX + 5];

int main() {

    long long ans = 0;

    scanf("%lld",&n);

    sect = {0,1e9 + 5};

    for(int i = 1;i <= n;i++){
        scanf("%lld %lld",&segm[i].first.first,&segm[i].first.second);
        sect.first = max(sect.first,segm[i].first.first);
        sect.second = min(sect.second,segm[i].first.second);
    }

    if(sect.first <= sect.second){
        ans += 2 * (sect.second - sect.first + 1);
        long long max_len = 0;
        for(int i = 1;i <= n;i++){
            max_len = max(max_len,segm[i].first.second - segm[i].first.first + 1);
        }
        for(int i = 1;i <= n;i++){
            segm[i].first.second -= (sect.second - sect.first + 1);
            if(segm[i].first.second < segm[i].first.first){
                printf("%lld\n",ans - (sect.second - sect.first + 1) + max_len);
                return 0;
            }
        }
    }

    vector<long long> posx;
    pair<long long,long long> fst = {1e9 + 5,1e9 + 5};

    for(int i = 1;i <= n;i++){
        posx.push_back(segm[i].first.first);
        posx.push_back(segm[i].first.second);
        fst.first = min(fst.first,segm[i].first.first);
        fst.second = min(fst.second,segm[i].first.second);
    }

    sort(posx.begin(),posx.end());
    posx.resize(unique(posx.begin(),posx.end()) - posx.begin());

    for(int i = 0;i < (int)posx.size();i++){
        segm[++n] = {{posx[i],fst.second},1};
        if(posx[i] == fst.second){
            break;
        }
    }

    sort(segm + 1,segm + 1 + n,
        [&](pair<pair<long long,long long>,long long> &a,pair<pair<long long,long long>,long long> &b){
            if(a.first.first != b.first.first){
                return a.first.first < b.first.first;
            }
            if(a.first.second != b.first.second){
                return a.first.second > b.first.second;
            }
            return a.second < b.second;
        });

    suff_sect[n + 1] = {0,1e9 + 5};

    for(int i = n;i;i--){
        if(segm[i].second == 1){
            suff_sect[i] = suff_sect[i + 1];
            continue;
        }
        suff_sect[i].first = max(suff_sect[i + 1].first,segm[i].first.first);
        suff_sect[i].second = min(suff_sect[i + 1].second,segm[i].first.second);
    }

    long long max_len = 0;
    for(int i = 1;i <= n;i++){
        max_len = max(max_len,segm[i].first.second - segm[i].first.first + 1);
    }

    long long tmp_ans = max_len;
    for(int i = 1;i <= n;i++){
        if(segm[i].second == 1 && (suff_sect[i + 1].first != 0 || suff_sect[i + 1].second != 1e9 + 5)){
            tmp_ans = max(tmp_ans,segm[i].first.second - segm[i].first.first + 1 + max(0LL,suff_sect[i + 1].second - suff_sect[i + 1].first + 1));
        }
    }

    ans += tmp_ans;

    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 9712
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll N=100005;
inline ll mult(ll x,ll y){x%=hell;y%=hell;return (1LL*x*y)%hell;}
inline ll add(ll x,ll y){x+=y;return x%hell;}
inline ll powMod(ll base,ll expo){
	if(base==0)return 0;
	ll ans=1;
	while(expo){
		if(expo&1)ans=mult(ans,base);
		base=mult(base,base); 
		expo>>=1;
	}
	return ans;
}
void solve(){
	ll n;
	cin>>n;
	ld dp[2][3005];
	vector<ld> v(n+1);
	rep(i,1,n+1)
		cin>>v[i];
	dp[0][0]=(ld)(1.0);
	rep(i,1,n+1){
		ll x=i&1;
		rep(j,0,n+1)dp[x][j]=0;
		rep(j,0,i){
			dp[x][j+1]+=dp[x^1][j]*v[i];
			dp[x][j]+=dp[x^1][j]*(1.0-v[i]);
		}
	}
	ld ans=0;
	rep(i,1,n+1){
		if(n-i<i)ans+=dp[n&1][i];
	}
	cout<<fixed<<setprecision(10)<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 384
#[allow(unused_imports)]
use {
    proconio::{fastout, input, marker::*},
    std::cmp::*,
    std::collections::*,
    std::ops::*,
};

trait Monoid {
    fn id() -> Self;
    fn f(a: Self, b: Self) -> Self;
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum MinInt {
    Val(i64),
    Maximal,
}
impl MinInt {
    fn unwrap(self) -> i64 {
        if let Self::Val(x) = self {
            x
        } else {
            panic!();
        }
    }
}
impl std::ops::MulAssign for MinInt {
    fn mul_assign(&mut self, other: Self) {
        if other < *self {
            *self = other
        };
    }
}
impl std::ops::Mul for MinInt {
    type Output = Self;
    fn mul(self, other: Self) -> Self {
        if self < other {
            self
        } else {
            other
        }
    }
}
impl Monoid for MinInt {
    fn id() -> Self {
        MinInt::Maximal
    }
    fn f(a: Self, b: Self) -> Self {
        a * b
    }
}
use MinInt::*;

#[fastout]
fn main() {
    input! {
        mut h: usize,
        mut w: usize,
        mut c: (usize, usize),
        mut d: (usize, usize),
        mut s: [Bytes; h]
    }

    for i in 0..h {
        s[i].insert(0, b'#');
        s[i].insert(0, b'#');
        s[i].push(b'#');
        s[i].push(b'#');
    }
    w += 4;
    h += 4;
    s.insert(0, vec![b'#'; w]);
    s.insert(0, vec![b'#'; w]);
    s.push(vec![b'#'; w]);
    s.push(vec![b'#'; w]);
    c = (c.0 + 1, c.1 + 1);
    d = (d.0 + 1, d.1 + 1);

    let mut dex = vec![vec![Maximal; w]; h];
    dex[c.0][c.1] = Val(0);
    let mut node = vec![];
    node.push(c);
    let mut q = VecDeque::new();
    q.push_back(c);
    loop {
        while let Some((x, y)) = q.pop_front() {
            for &(dx, dy) in [(1, 0), (0, 1), (!0, 0), (0, !0)].iter() {
                let xn = x + dx;
                let yn = y + dy;
                if s[xn][yn] != b'#' && dex[xn][yn] == Maximal {
                    dex[xn][yn] = dex[x][y];
                    q.push_back((xn, yn));
                    node.push((xn, yn));
                }
            }
        }
        let mut next = vec![];
        for &(x, y) in node.iter() {
            for dx in 0..=4 {
                for dy in 0..=4 {
                    let xn = x + dx - 2;
                    let yn = y + dy - 2;
                    if s[xn][yn] != b'#' && dex[xn][yn] == Maximal {
                        dex[xn][yn] = Val(dex[x][y].unwrap() + 1);
                        q.push_back((xn, yn));
                        next.push((xn, yn));
                    }
                }
            }
        }
        node = next;
        if q.is_empty() {
            break;
        }
    }

    if let Val(ans) = dex[d.0][d.1] {
        println!("{}", ans);
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 21344
#include<stdio.h>
int main()
{
    int n,k,all[100005]={0};
    scanf("%d %d",&n,&k);
    int ans=0;
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&all[i]);
        if(all[i]>=k)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a //大きいのが前
#define PQmin(a, n) priority_queue< int, std::vector<int>, std::greater<int> >a //小さいのが前

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n,m;
    cin>>n>>m;
    priority_queue< int, std::vector<int>, std::greater<int> >a;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.push(x);
    }
    vector<pair<int, int> > cb(m);
    for(int i=0;i<m;i++){
        int b,c;
        cin>>b>>c;
        cb.at(i).first=c;
        cb.at(i).second=b;
    }
    sort(cb.begin(), cb.end());
    reverse(cb.begin(), cb.end());
    bool flag=true;
    for(int i=0;i<m;i++){
        for(int j=0;j<cb.at(i).second;j++){
            if(a.top()<cb.at(i).first){
                a.pop();
                a.push(cb.at(i).first);
            }
            else{
                flag=false;
                break;
            }
        }
        if(flag==false)break;
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=a.top();
        a.pop();
    }
    cout<<ans<<endl;






    return 0;
}

Measured memory_bytes: 1528
class UnionFind():
    def __init__(self,n):
        self.n=n
        # 自身の数で親がいないことを示す
        self.parents = [i for i in range(n+1)]
        # unionの大きさ
        self.size = [1]*(n+1)

    def find(self,x):
        # 
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def unite(self,x,y):
        
        xRoot = self.find(x)
        yRoot = self.find(y)

        if xRoot == yRoot:
            return

        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

N,M = map(int,input().split())
tree = UnionFind(N)

for _ in range(M):
    a,b = map(int,input().split())
    tree.unite(a,b)

print(max(tree.size))


Measured memory_bytes: 88612
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10, MOD = 1e9 + 7;

ll dp[SIZE][2][2];

int main()
{
    fastInp;

        int n;
        cin >> n;
        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    dp[i][j][k] = 0;
        }
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            dp[i][0][0] = (8 * dp[i - 1][0][0]) % MOD;
            dp[i][0][1] = (dp[i - 1][0][1] * 9 + dp[i - 1][0][0]) % MOD;
            dp[i][1][0] = (dp[i - 1][1][0] * 9 + dp[i - 1][0][0]) % MOD;
            dp[i][1][1] = (dp[i - 1][1][1] * 10 + dp[i - 1][0][1] + dp[i - 1][1][0]) % MOD;            
        }
     
        cout << dp[n][1][1] << '\n';

    return 0;
}

Measured memory_bytes: 34824
import math
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

            else:

                flg = 0
    finally:

        return array_result

def round(x):
    return (x*2+1)//2

arr_data = getinputdata()

n = int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]


if len(set(arr))==1:
    
    print(0)

else:

    target=sum(arr)//len(arr) if sum(arr)%len(arr)==0 else round(sum(arr)/len(arr))

    mysum=0

    for v in arr:

        mysum+=(v-int(target))**2

    print(mysum)

Measured memory_bytes: 3064