akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <bitset>

using namespace std;
using ll = long long;
using ld = long double;
const ll mod =  998244353;
const ll inf = 1e18;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int bsearch(const vector<ll>& a, ll x){
  int lft = 0;
  int rgt = a.size();
  while (rgt - lft > 1) {
    int mid = (lft + rgt) / 2;
    if(a[mid] < x) {
      lft = mid;
    }
    else {
      rgt = mid;
    }
  }
  return lft;
}

ll count(ll i, ll n, const vector<ll>& a) {
  // cout << i << endl;
    vector<ll> tmp = a;    
    REP(j, n) {
      tmp[j] = tmp[j] % i;
    }
    sort(all(tmp));
    // REP(k, n) cout << tmp[k] << " "; cout << endl;
    ll cnt = 0;
    int lft = 0;
    int rgt = n - 1;
    while(lft < rgt) {
      cnt += tmp[lft];
      tmp[rgt] += tmp[lft];
      tmp[lft] = 0;
      while(i <= tmp[rgt]  && rgt > 0) {
        tmp[rgt-1] += tmp[rgt] - i;
        rgt--;
      }
      lft++;
      // REP(k, n) cout << tmp[k] << " "; cout << endl;
    }
    // cout << cnt << endl;
    // cout << "======" << endl;
    return cnt;
}

using Node = pair<ll, int>;
vector<vector<Node>> to;
vector<bool> ans;
vector<bool> used;
void dfs(int c, bool color) {
  if(used[c]) return;
  used[c] = true;
  ans[c] = color;
  for(const auto next: to[c]) {
    dfs(next.second, color ^ (next.first % 2 == 1));
  }
}
signed main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  to.resize(n);
  REP(i, n-1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;b--;
    to[a].emplace_back(c, b);
    to[b].emplace_back(c, a);
  }

  ans.resize(n);
  used.resize(n, false);
  dfs(0, 0);
  if(set<bool>(all(ans)).size() == 1) {
    ans[0] = 1 ^ ans[0];
  }
  REP(i, n) {
    cout << ans[i] << endl;
  }
  return 0; 
}


Measured memory_bytes: 8576
//“Make it work, make it right, make it fast.” – Kent Beck
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dd;
const int siz = 1e6 + 5;
const int MOD = 1e9 + 7;
#define endl '\n'
#define deb(x) cout << #x << " = " << x << endl;


void solve() {
  int n;
  cin >> n;
  ll a[n], sum = 0, pre[n+1];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    sum = (sum + a[i]) % MOD;
    pre[i+1] = sum;
  }
  pre[0] = 0;
  ll ans = 0;
  for(int i = 0; i < n; i++) {
    ans += a[i] * pre[i] % MOD;
    ans %= MOD;
  }
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << fixed << setprecision(10);
  int t = 1;
  //cin >> t;
  for(int tt = 1; tt <= t; tt++) {
    //cout << "Case #" << tt << ": ";
    solve();
  }
  return 0;
}  

Measured memory_bytes: 6716
#include <bits/stdc++.h>
using namespace std; 
  
typedef long long int ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pll> vll; 
typedef vector<ll> vl; 
typedef vector<vl> vvl; 
typedef priority_queue <ll> pqb;
typedef priority_queue <ll, vector<ll>, greater<ll>> pqs;
double EPS = 1e-9; 
long long INF = 1000000000000000005ll; 
double PI = acos(-1); 
#define M 1000000007ll
#define D 998244353ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound  
#define SQR(x) ((LL)(x) * (x)) 
#define RESET(a, b) memset(a, b, sizeof(a))
#define GCD(a,b) __gcd(a,b)
#define setbits(x)   __builtin_popcountll(x)
#define zerobits(x)  __builtin_ctzll(x) 
#define ps(x,y)  fixed<<setprecision(y)<<x
#define endl '\n'
#define ff first 
#define ss second 
#define mp make_pair  
#define ALL(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz 
#define SIZE(v) (int)v.size() 
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v)) 
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) 
#define PERMUTE next_permutation 
  
inline string IntToString(ll a) 
{ 
    char x[100]; 
    sprintf(x, "%lld", a); 
    string s = x; 
    return s; 
} 
  
inline ll StringToInt(string a) 
{ 
    char x[100]; 
    ll res; 
    strcpy(x, a.c_str()); 
    sscanf(x, "%lld", &res); 
    return res; 
} 
  
 
inline string uppercase(string s) 
{ 
    int n = SIZE(s); 
    for(ll i=0;i<n;i++) 
    if (s[i] >= 'a' && s[i] <= 'z') 
        s[i] = s[i] - 'a' + 'A'; 
    return s; 
} 
  
inline string lowercase(string s) 
{ 
    int n = SIZE(s); 
    for(ll i=0;i<n;i++) 
    if (s[i] >= 'A' && s[i] <= 'Z') 
        s[i] = s[i] - 'A' + 'a'; 
    return s; 
}

bool cmp(pll a,pll b)
{
  ll as=a.ff-a.ss;
  ll bs=b.ff-b.ss;
    return (as>bs);
}

ll dx[]={-1,0,1,0};
ll dy[]={0,1,0,-1};

vl v[100005];
bool vis[100005];

int main() {
    FAST
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ll n;
    cin>>n;
    ll a[n+1]={0};
    for(ll i=1;i<=n;i++){
    	cin>>a[i];
    }
    ll dp[n+1]={0};
    dp[2]=abs(a[2]-a[1]);
    for(ll i=3;i<=n;i++){
    	dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    	//cout<<dp[i]<<endl;
    }
    cout<<dp[n]<<endl;
    return 0; 
}

Measured memory_bytes: 7452
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using pll=pair<ll,ll>;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define MOD 1000000007

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
	int N;
	cin >> N;
	map<int, int> mp;
	int t;
	rep(i,N) {
		cin >> t;
		mp[t]++;
	}
	int ans = 0;
	for(auto k : mp) {
		if(k.second % 2) ans++;
	}
	cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4864
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int t, h, s;
	while (cin >> t >> h >> s, t+h+s!=-3) {
		int cnt = t * 3600 + h * 60 + s;
		cnt = 7200 - cnt;
		int cnt3 = cnt * 3;
		int a = cnt / 3600; cnt %= 3600;
		int b = cnt / 60; cnt %= 60;
		int c = cnt3 / 3600; cnt3 %= 3600;
		int d = cnt3 / 60; cnt3 %= 60;
		printf("%02d:%02d:%02d\n%02d:%02d:%02d\n", a, b, cnt, c, d, cnt3);
	}
	return 0;
} 


Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll a,b,c,i,j,k,l,m,n,ans,tmp,hoge,fuga,piyo;
ll x[10010],y[10010];
string s,str;
int main(){
  cin>>a>>b;
  if(a>b)cout<<"safe";
  else cout<<"unsafe";
  return 0;
}

Measured memory_bytes: 3628
N, K = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))

AB = sorted(AB, key=lambda x: x[0])
for i in range(N):
    if i > 0:
        AB[i][1] += AB[i-1][1]
    if K <= AB[i][1]:
        print(AB[i][0])
        break


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

int main(){
    using namespace std;
    int N; cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++ ) cin >> v[i];

    sort(v.begin(), v.end());
    int r = v.size()/2;
    cout << v[r] - v[r-1] << endl;    
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace         std;
#define                 int long long
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<endl
#define                 real signed
#define                 endl '\n'              
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 314159
#define  vi vector<int>
#define  v  vector

int weight[N],val[N];
int n,W,d;

int dp[101][500][101];

int get(int ind,int weg,int taken)
{
    if(weg+taken*d > W)return -MOD*MOD;
    if(ind == n+1)return 0;
    int&ans=dp[ind][weg][taken];
    if(ans!=-1)return ans;
    
    return ans=max(val[ind]+get(ind+1,weg+weight[ind],taken+1),get(ind+1,weg,taken));
    
}


signed main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
    cin>>n>>W;
    forn(i,1,n)cin>>weight[i]>>val[i];
    
    d = *min_element(weight+1,weight+n+1);
    
    forn(i,1,n)weight[i]-=d;
    forn(i,0,100)forn(j,0,499)forn(k,0,100)dp[i][j][k]=-1;
    cout<<get(1,0,0);
     return 0;

}

//       g++ -g c.cpp ; ./a.exe

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

#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;

ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}

ll mod(ll a, ll b) {return (a % b + b) % b;}

ll powerm(ll base,ll exp,ll mod) 
{ll ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}

using namespace std;

int main() 
{	
	fast;
	ll n,m,x; cin>>n>>m>>x;
	vector<pair<vector<ll>,ll>>v;
	for(ll i = 0; i < n; i++)
	{
		ll c; cin>>c;
		v.push_back(make_pair(vector<ll>(),c));
		for(ll j = 0; j < m; j++)
		{
			ll t; cin>>t;
			v[i].first.push_back(t);
		}
	} 
	ll arr[m];
	memset(arr,0,sizeof(arr));
	ll ans = LLONG_MAX; ll flag = 0;
	for(ll bit = 0; bit < (1 << n); bit++)
	{
		memset(arr,0,sizeof(arr));
		ll sum = 0;
		for(ll i = 0; i < n; i++)
		{
			if(bit & (1 << i))
			{
				sum += v[i].second;
				for(ll j = 0; j < m; j++) {arr[j] += v[i].first[j];}
			}
			flag = 0;
			for(ll j = 0; j < m; j++)
			{
				if(arr[j] < x)
				{
					flag = 1;
					break;	
				}	
			}
			if(flag == 0)
			{
				ans = min(ans,sum);
			}
		} 
	}
	if(ans == LLONG_MAX) cout << -1 << endl; 
	else cout << ans << endl;
 	return 0;
}

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

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

	set<string> u;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;

		u.insert(s);
	}

	cout << u.size();
	
	return 0;
}
	

Measured memory_bytes: 19256
package main

import "fmt"

const N = 86

func main() {
	var n int
	fmt.Scan(&n)

	l := make([]int, N+1)
	l[0] = 2
	l[1] = 1
	for i := 2; i <= N; i++ {
		l[i] = l[i-2] + l[i-1]
	}

	fmt.Println(l[n])
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
#define int long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	vector<string> v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i];
	sort(begin(v), end(v));
	int ans = 0;
	for (int i = 0; i < n;) {
		++ans;
		int j = i;
		while (j < n and v[j] == v[i]) ++j;
		i = j;
	}
	cout << ans;
}

Measured memory_bytes: 9532
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;

int n,a,nxt=1;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a;
        if( a == nxt ) nxt++;
    }

    if( nxt==1 ){
        cout << -1;
        return 0;
    }

    cout << n-nxt+1;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

string S;

int main(){
    cin>>S;
    if(S[0]==S[1]||S[1]==S[2]||S[2]==S[3])out("Bad");
    else out("Good");
    
    
}


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

int main(){
    int N, M;
    cin >> N >> M;
    vector<string> A(N);
    vector<string> B(M);
    rep(i, N){
        cin >> A[i];
    }
    rep(i, M){
        cin >> B[i];
    }

    rep(i, N-M+1){
        rep(j, N-M+1){
            bool flag = true;
            rep(k, M){
                rep(l, M){
                    if(A[i+k][j+l]!=B[k][l]){
                        flag=false;
                        break;
                    }
                }
            }
            if(flag){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)

long long int n,cnt=0,ans=0,a,b,c,cmp[100000],data[100000],m;

string s,w;

int main(void){
      cin >> n >> m;
      rep(i,m){
          cin >> a >> b;
          cmp[a]++;
          cmp[b]++;
      }
      
      rrep(i,1,n+1){
          cout << cmp[i] << endl;
      }
return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) for (auto i = mp.begin(); i != mp.end(); ++i) { cout << i->first <<":"<<i->second << endl;}
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<" ";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    string ans="";
    ans = t+s;
    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n, x;
	cin >> n >> x;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int p=0;
	int c = 1;
	for (int i = 0; i < n; i++) {
		p += v[i];
		if(p<=x){
			c++;
		}
	}
	cout << c;
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vi32> g(n);
  rep(i, m) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  vi32 dist(n, 1e9);
  auto dfs = [&](auto dfs, int u, int d) -> bool {
    if (dist[u] != 1e9) {
      return dist[u] % 2 == d % 2;
    }
    dist[u] = d;
    for (auto v : g[u]) {
      if (!dfs(dfs, v, d + 1)) return false;
    }
    return true;
  };
  if (dfs(dfs, 0, 0)) {
    int a = 0;
    rep(i, n) a += dist[i] % 2 == 0;
    int b = n - a;
    cout << (i64) a * b - m << endl;
  } else {
    cout << (i64) n * (n - 1) / 2 - m << endl;
  }
}

Measured memory_bytes: 6400
#!/usr/bin/env python3
import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    diff = sum(A) - sum(B)
    if diff < 0:
        print(-1)
    else:
        C = []
        for i in range(N):
            tmp = A[i] - B[i]
            if tmp >= 0:
                C.append(tmp)
        C.sort()
        # print(C,diff)
        j = 0
        while C[j] <= diff:
            diff -= C[j]
            j += 1
            if j == N:
                break
        print(N-j)

if __name__ == '__main__':
    main()


Measured memory_bytes: 18524
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) {
        ll tmp_a;
        cin >> tmp_a;
        a[i] = tmp_a - (i + 1LL);
    }
    sort(a.begin(), a.end());
    ll med;
    if (n % 2 == 1) med = a[n/2];
    else            med = min(a[n/2], a[n/2+1]);
    ll ans = 0;
    rep(i, n) {
        ans += abs(a[i] - med);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4780
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BGridCompression solver = new BGridCompression();
        solver.solve(1, in, out);
        out.close();
    }

    static class BGridCompression {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int h = in.nextInt(), w = in.nextInt();
            String[] s = new String[h];
            boolean[] x = new boolean[w];
            Arrays.fill(x, true);
            for (int i = 0; i < h; i++) {
                s[i] = in.next();
                for (int j = 0; j < w; j++) {
                    if (s[i].charAt(j) == '#') {
                        x[j] = false;
                    }
                }
            }
            for (int i = 0; i < h; i++) {
                if (s[i].indexOf('#') < 0) {
                    continue;
                }
                for (int j = 0; j < w; j++) {
                    if (!x[j]) {
                        out.print(s[i].charAt(j));
                    }
                }
                out.println();
            }
        }

    }
}



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

using namespace std;
using ll = long long;

vector<ll> divisor(ll n){
    std::vector<ll> res;
    for(ll i = 1LL; i * i <= n; i++){
        if(n % i == 0){
            res.push_back(i);
            ll j = n / i;
            if(i != j)res.push_back(j);
        }
    }
    std::sort(res.begin(),res.end());
    return res;
}

int main()
{
	ll n; cin >> n;
	vector<ll> div = divisor(n);
	ll sum = 0;
	for(auto i : div) {
		ll m = i - 1;
		if(m == 0)continue;
		if(n % m == n / m) sum += m;
	}
	cout << sum << endl;
}

Measured memory_bytes: 384
#!/usr/bin/env python3
import collections as cl
import math
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def find_target(x, c, d):
    num_c = x // c
    num_d = x // d
    lcm_cd = lcm(c, d)
    num_dip = x // lcm_cd
    return x - (num_c + num_d - num_dip)


def main():
    a, b, c, d = MI()
    target_in_a = find_target(a - 1, c, d)
    target_in_b = find_target(b, c, d)
    print(target_in_b - target_in_a)


main()


Measured memory_bytes: 65304
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

const ll INF=1e9+7;


int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n){
        cin >> a[i];
    }
    ll ans=INF;
    for(ll i=-100;i<=100;i++){
        ll sum=0;
        rep(j,n){
            sum+=(a[j]-i)*(a[j]-i);
        }
        ans=min(ans,sum);
    }
    cout << ans << endl;
    return 0;
} 


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

int dx[]{0, 1, 0, -1};
int dy[]{-1, 0, 1, 0};
int field[1001][1001] = {0};

int main() {
    int h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; ++i) cin >> v[i];

    int cx = 0;
    int cy = 0;
    for(int i=0; i<n; ++i) {
        int a = i+1;
        int a_num = v[i];
        int c = 0;
        stack<pair<int, int>> que;
        que.push(make_pair(cx, cy));
        while(!que.empty()) {
            auto p = que.top();
            que.pop();
            int x = p.first;
            int y = p.second;
            if(c>=a_num) {
                cx = x;
                cy = y;
                break;
            }
            field[x][y] = a;
            c++;
            for(int l=0; l<4; ++l) {
                int nx = x + dx[l];
                int ny = y + dy[l];
                if(nx>=0&&nx<h&&ny>=0&&ny<w&&field[nx][ny]==0) {
                    que.push(make_pair(nx, ny));
                }
            }
        }
    }

    for(int i=0; i<h; ++i) {
        for(int j=0; j<w; ++j) {
            if(j==0) cout << field[i][j];
            else cout << " " << field[i][j];
        }
        cout << endl;
    }
    return 0;
}



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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

void ABC144C()
{
	ll N;
	cin >> N;

	ll a = 1;
	ll b = N;
	for(ll i = 1; i * i <= N; ++i)
	{
		if (N % i == 0)
		{
			a = i;
			b = N / i;
		}
	}
	ll c = a + b - 2;
	cout << c << endl;
}


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


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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int N;
  cin>>N;
  if(N%10 == 2 || N%10 == 4 || N%10 == 5 || N%10 == 7|| N%10 == 9){
    cout << "hon" << endl;
  }else if(N%10 == 0 || N%10 == 1 || N%10 == 6 || N%10 == 8){
    cout << "pon" << endl;
  }else{
    cout << "bon" << endl;
  }
  return 0;
}



Measured memory_bytes: 3640
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      String[] nyu=sc.nextLine().split(" ");
   //  String nyu=sc.nextLine();


int num=Integer.parseInt(nyu[0]);
int numnext=Integer.parseInt(nyu[1]);
int numend=Integer.parseInt(nyu[2]);

//numend-(num-numnext)

//int num2=Integer.parseInt(sn[1]);

int count=0;

if(numend-(num-numnext)<0){
count=0;
}else{
count=numend-(num-numnext);
}



System.out.println(count);

//System.out.println(a/b);


	}
}

Measured memory_bytes: 22868
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

string S[2000];
int total[2000][2000];

int main()
{
	int H, W;
	cin >> H >> W;
	for (auto i = 0; i < H; ++i)
	{
		cin >> S[i];
	}

	memset(total, 0, sizeof(total));
	for (auto i = 0; i < H; ++i)
	{
		for(auto left = 0; left < W; ++left)
		{
			while (left < W && S[i][left] == '#')
			{
				++left;
			}

			if (left >= W)
			{
				break;
			}

			auto right = left;
			while (right < W && S[i][right] == '.')
			{
				++right;
			}

			for (auto j = left; j < right; ++j)
			{
				total[i][j] += right - left;
			}
			left = right;
		}
	}

	for (auto i = 0; i < W; ++i)
	{
		for (auto left = 0; left < H; ++left)
		{
			while (left < H && S[left][i] == '#')
			{
				++left;
			}

			if (left >= H)
			{
				break;
			}

			auto right = left;
			while (right < H && S[right][i] == '.')
			{
				++right;
			}

			for (auto j = left; j < right; ++j)
			{
				total[j][i] += right - left;
			}
			left = right;
		}
	}

	auto result = 0;
	for (auto i = 0; i < H; ++i)
	{
		for (auto j = 0; j < W; ++j)
		{
			result = max(result, total[i][j]);
		}
	}

	cout << result - 1 << endl;

	return 0;
}

Measured memory_bytes: 19968
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
	int A = 0;
	int B = 0;
	int AB = 0;
	int O = 0;
	string str, waste, data;
	while (cin >> str) {
		replace(str.begin(), str.end(), ',', ' ');
		istringstream iss(str);
		iss >> waste >> data;
		if (data == "A") A++;
		if (data == "B") B++;
		if (data == "AB") AB++;
		if (data == "O") O++;
	}
	cout << A << endl << B << endl << AB << endl << O << endl;
	return 0;
}


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

int main() {
	int N;
	cin >> N;
	int a[100000];
	for (int i = 0;i<N;i++) cin >> a[i];

	//jに対しA[i]=jなるiの個数をカウント
	//ただN以上だと結局全部消すので無視
	int c[100001];
	for (int j = 1;j <= N;j++) c[j] = 0;
	for (int i = 0;i<N;i++) {
		if (a[i] <= N) {
			c[a[i]] += 1;
		}
	}

	//c[j]についてj以上ならjに,j未満なら0にそろえる
	for (int j = 1;j <= N;j++) {
		if (c[j] >= j) c[j] = j;
		else c[j] = 0;
	}
	//Nまで総和.それが残る数なので,Nから引いて答え
	int res;
	for (int j = 1;j <= N;j++) res += c[j];
	cout << N - res;

}

Measured memory_bytes: 1024
# chokudaiブログの典型力の話を意識しつつ考えたら思いついた!

# 「ある集合の部分集合の中で、〜〜〜の値が最小になるものを求めよ」のパターン
# 愚直にやると2^Nを調べねばならず無理。
# したがって「一部を調べればよい」に帰着するのが多いだろう。
# 何らかの形でソートしておいて、空集合から1つずつ付け加えるとか。全体集合から1つずつ取り去るとか。

# 今回は全体集合から1つずつ取り去るのを考えるとできる。
# 全体集合である競技m0が最多の人数p0人を集めたとする。
# すると、全ての部分集合のうち「m0を含む集合」を考えると、競技m0は必ずp0人以上集まるので解もp0以上。
# ここで「m0を含む集合」について一気に計算できていることに注意! 一撃で多数の集合について計算が終わる。
# 次に全体集合からm0を取り去ったものを考える。
# ここである競技m1が最多の人数p1人を集めたとする。すると……以下同様。
# なお複数種目の競技が同率1位になった場合は全て一度に取り除いて良い。
# これで空集合までやって、最大が最小のものを出力すればOK! 

n, m = list(map(int, input().split()))
preference = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)] # 1-index → 0-index

ans = n
held_sports = set(range(m))

while held_sports:
    # 各競技に参加する人数を求める
    parti = [0] * m
    for pref in preference:
        for s in range(m):
            if pref[s] in held_sports:
                parti[pref[s]] += 1
                break
    
    temp = max(parti)
    ans = min(ans, temp)
    # 集合から最大人数を取った要素を除外
    for idx, par in enumerate(parti):
        if par == temp:
            held_sports.remove(idx)

print(ans)

Measured memory_bytes: 10272
data = list(map(int, input().split()))
n = data[0]
m = data[1]
li = list(map(int, input().split()))
S = sum(li)
count=0
for i in li:
  if i < S*(1 / 4 / m):
    count+=1

if n-count < m:
  print('No')
else:
  print('Yes')

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

int main(){

    int N;
    cin >> N;
    vector<int> C(N - 1), S(N - 1), F(N - 1);
    for(int i = 0; i < N - 1; i++) cin >> C[i] >> S[i] >> F[i];

    for(int i = 0; i < N - 1; i++){
        int ans = 0;
        for(int j = i; j < N - 1; j++){
            if(ans < S[j]){
                ans = S[j] + C[j];
            }
            else if(ans % F[j]){
                ans += F[j] - (ans % F[j]) + C[j];
            }else{
                ans += C[j];
            }
        }
        cout << ans << endl;
    }

    cout << 0 << endl;

    return 0;
}

Measured memory_bytes: 764
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;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;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(int x){write(x);putchar('\n');}
const int MAXN=20;
const int MAXMASK=(1<<18);
int n,mx[MAXMASK][2],a[MAXMASK],g[5];
void down(int x,int y)
{
	g[1]=mx[x][0];g[2]=mx[x][1];
	g[3]=mx[y][0];g[4]=mx[y][1];
	sort(g+1,g+1+4);
	mx[x][0]=g[4];mx[x][1]=g[3];
}
int bin[25];
int main()
{
	bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;
	n=read();
	for(int i=0;i<bin[n];i++)a[i]=mx[i][0]=read();
	for(int i=n-1;i>=0;i--)
		for(int j=bin[n]-1;j>=0;j--)if(!(j&bin[i]))down(j|bin[i],j);
	int sum=0;
	for(int i=1;i<bin[n];i++)pr2(sum=max(sum,mx[i][0]+mx[i][1]));
	return 0;
}


Measured memory_bytes: 6016
n = int(input())
num_array = [int(i) for i in input().split()]

three_nums = [0,0,0]

ans = 0

for i in range(len(num_array)-2):
	three_nums[0] = num_array[i]
	three_nums[1] = num_array[i+1]
	three_nums[2] = num_array[i+2]
	
	if three_nums[0] < three_nums[1] < three_nums[2] or three_nums[2] < three_nums[1] < three_nums[0]:
		ans += 1
		
print(ans)

Measured memory_bytes: 3064
n=int(input())
b=list(map(int,input().split()))
a1,a2=[0]*n,[0]*n
a1[0]=b[0]
a1[-1]=b[-1]
for i in range(1,n-1):
    if b[i-1]<b[i]:
        a1[i]=b[i-1]
    else:
        a1[i]=b[i]
a2[0]=b[0]
a2[-1]=b[-1]
for i in range(n-2,0,-1):
    if b[i-1]>b[i]:
        a2[i]=b[i]
    else:
        a2[i]=b[i-1]
ans=0
for i,j in zip(a1,a2):
    ans+=min(i,j)
print(ans)

Measured memory_bytes: 9240
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define YES cout << "YES" << endl
#define NO  cout << "NO"  << endl
#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 1000000
using namespace std;
typedef long long ll;



int main(){
  int on=0, en=0;
  string o, e;  cin >> o >> e;
  string pass = "";
  rep(i, 0, o.length()+e.length()){
    if(i+1&1){
      pass += o[on];
      on++;
    }else{
      pass += e[en];
      en++;
    }
  }
  cout << pass << endl;
}


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

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

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

inline ll popcnt(ll x){return __builtin_popcountll((unsigned long long)x);};
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
//friend bool operator<(const stc& lhs, const stc& rhs){
//    return std::tie(lhs.l, lhs.r) < std::tie(rhs.l, rhs.r);
//}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N; cin >> N;
    if(N == 2){
        cout << 0 << endstr; return 0;
    }
    
    vpl e(100100, {0,0}), o(100100,{0,0});
    rep(i, N){
        ll v; cin >> v;
        if(i%2 == 0){
            e[v].ss = v; e[v].ff++;
        }
        else{
            o[v].ss = v; o[v].ff++;
        }
    }
    sort(ALL(e), greater<PL>());
    sort(ALL(o), greater<PL>());
    
    if(o.front().ss == e.front().ss){
        ll res1 = o.front().ff + e[1].ff;
        ll res2 = o[1].ff + e.front().ff;
        cout << N - max(res1, res2) << endstr;
    }
    else{
        cout << N - o.front().ff - e.front().ff << endstr;
    }
}


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

int main(){
    int n, l;
    cin >> n >> l;
    vector<int> fla(n);
    int min_abs=100000000, index, sum=0;

    for (auto i = 0; i < n; i++)
    {
        fla[i] = i + l;
    }

    for (auto i = 0; i < n; i++)
    {
        if (min_abs > abs(fla[i])){
            min_abs = abs(fla[i]);
            index = i;
        }
    }

    for (auto i = 0; i < n; i++)
    {
        if(i == index){
            continue;
        }else{
            sum += fla[i];
        }
    }
    cout << sum << endl;
}

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

int ChangeToNumber(string Word)
{
	int Number = 0;
	int Keta = 1;
	int Kurai = 0;
	while(Kurai < Word.size()){
		
		if(Word[Word.size() - Kurai - 1] == 'A') Number += Keta * 1;
		if(Word[Word.size() - Kurai - 1] == 'C') Number += Keta * 2;
		if(Word[Word.size() - Kurai - 1] == 'G') Number += Keta * 3;
		if(Word[Word.size() - Kurai - 1] == 'T') Number += Keta * 4;
		Keta *= 4;
		Kurai ++;
	}
	return Number;
}

void Judge(vector<bool>& Exist, string& Command, string& Word)
{
	if(Command == "insert"){
		Exist[ChangeToNumber(Word)] = true;
	}else{
		if(Exist[ChangeToNumber(Word)]){
		    cout << "yes" << endl;
		}else{
		    cout << "no" << endl;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<bool> Exist;
	Exist.resize(16777216);
	for(int i = 0; i < 16777216; i++){
		Exist[i] = false;
	}
	for(int i = 0; i < n; i++){
		string Command;
		string Word;
		cin >> Command;
		cin >> Word;
		Judge(Exist, Command, Word);
	}
	return 0;
}

Measured memory_bytes: 3116
#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;
typedef long double ld;
const int INF = 1e9;
const ll MOD = 1000000007;
ld dp[4000][4000];
int main() {
  int N;
  cin >> N;
  vector<ld> p(N);
  REP(i, N) cin >> p[i];
  dp[0][0] = 1;
  REP(i, N) REP(j, N) {
    dp[i + 1][j] += dp[i][j] * (1 - p[i]);
    dp[i + 1][j + 1] += dp[i][j] * p[i];
  }
  ld ans = 0;
  for (int i = (N / 2 + 1); i <= N; i++) {
    ans += dp[N][i];
  }
  cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 155328
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n, m; cin >> n >> m;
  cout << n * (n - 1) / 2 + m * (m - 1) / 2 << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
int n, m;
main()
{ 
  cin >> n;
  map<string, int> box;
  for (int i = 0; i < n; i++){
    string tmp;
    cin >> tmp;
    box[tmp]++;
  }
  cin >> m;
  for (int i = 0; i < m; i++){
    string tmp;
    cin >> tmp;
    box[tmp]--;
  }
  int ans = 0;
  for (auto it=begin(box); it!=end(box); it++)
  {
    ans = max(ans, it->second);
  }
  cout << ans << endl;
}


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

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(X) (X).begin(), (X).end()
#define sz(X) (int)X.size()

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

int main()
{ _
    int k; cin >> k;
    for (int i = 0; i < k; ++i)
        cout << "ACL";
    cout << endl;
    exit(0);
}



Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

// ABC060D Simple Knapsack

ll solve(int N, int W, vector<ll> &ws, vector<ll> &vs);

int main() {
    ios::sync_with_stdio(false);
    int N, W;
    vector<ll> ws(100, 0);
    vector<ll> vs(100, 0);

    cin >> N >> W;
    for (int i = 0; i < N; ++i) cin >> ws[i] >> vs[i];

    cout << solve(N, W, ws, vs) << endl;
    return 0;
}

ll solve(int N, int W, vector<ll> &ws, vector<ll> &vs)
{
    auto min_w = ws[0];
    vector<vector<ll>> vv(4, vector<ll>(0));
    for (int i = 0; i < N; ++i) vv[ws[i] - min_w].push_back(vs[i]);
    for (int i = 0; i < 4; ++i) sort(vv[i].begin(), vv[i].end(), greater<ll>());
    vector<vector<ll>> cumvs(4, vector<ll>(1, 0));
    int i = 0;
    for (auto vec: vv){
        for (auto v: vec) cumvs[i].push_back(cumvs[i].back() + v);
        ++i;
    }

    ll record = 0;
    ll cum_w0 = 0;
    for (auto cum_v0: cumvs[0]){
        if (cum_w0 > W) break;
        ll cum_w1 = cum_w0;
        cum_w0 += min_w;
        for (auto cum_v1: cumvs[1]){
            if (cum_w1 > W) break;
            ll cum_w2 = cum_w1;
            cum_w1 += min_w + 1;
            for (auto cum_v2: cumvs[2]){
                if (cum_w2 > W) break;
                ll cum_w3 = cum_w2;
                cum_w2 += min_w + 2;
                for (auto cum_v3: cumvs[3]){
                    if (cum_w3 > W) break;
                    cum_w3 += min_w + 3;
                    record = max(cum_v0 + cum_v1 + cum_v2 + cum_v3, record);
                }
            }
        }
    }
    return record;
}

Measured memory_bytes: 256
n=int(input())
l=[]
for i in range(n):
	l.append(input())
dct={}
for i in range(n):
	if l[i] in dct:
		dct[l[i]]+=1
	else:
		dct[l[i]]=1
m=max(dct.values())
ans=[]
for i in dct:
	if dct[i]==m:
		ans.append(i)
ans.sort()
for i in ans:
	print(i)

Measured memory_bytes: 35216
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<u32 M = 1000000007>
struct modint{
    u32 val;
    modint(): val(0){}
    template<typename T>
    modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}

    modint pow(ll k) const {
        modint res(1), x(val);
        while(k){
            if(k&1) res *= x;
            x *= x;
            k >>= 1;
        }
        return res;
    }
    template<typename T>
    modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}
    modint inv() const {return pow(M-2);}
    modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}
    modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}
    modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}
    modint& operator/=(modint a){return (*this) *= a.inv();}
    modint operator+(modint a) const {return modint(val) +=a;}
    modint operator-(modint a) const {return modint(val) -=a;}
    modint operator*(modint a) const {return modint(val) *=a;}
    modint operator/(modint a) const {return modint(val) /=a;}
    modint operator-(){return modint(M-val);}
    bool operator==(const modint a) const {return val == a.val;}
    bool operator!=(const modint a) const {return val != a.val;}
    bool operator<(const modint a) const {return val < a.val;}
};
using mint = modint<MOD>;


template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "{";
    for (int i = 0; i < v.size(); ++i) {
        if(i) os << ", ";
        os << v[i];
    }
    return os << "}";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
    return os << "{" << p.first << ", " << p.second << "}";
}


int main() {
    int n;
    cin >> n;
    vector<mint> pow2(n+1, 1);
    for (int i = 0; i < n; ++i) {
        pow2[i+1] = pow2[i]+pow2[i];
    }
    map<pair<ll, ll>, pair<int, int>> m;
    int zz = 0;
    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;
        if(a == 0 && b == 0) zz++;
        else if(a == 0 || b == 0){
            if(a == 0) m[{1, 0}].first++;
            else m[{1, 0}].second++;
        } else {
            ll g = __gcd(a, b);
            a /= g; b /= g;
            if(a < 0 || (a == 0 && b < 0)) a = -a, b = -b;
            if(b < 0) m[{-b, a}].second++;
            else m[{a, b}].first++;
        }
    }
    mint ans = 1;
    for (auto &&i : m) {
        ans *= (pow2[i.second.first]+pow2[i.second.second]-mint(1)).val;
    }
    ans += mint(zz-1);
    cout << ans.val << "\n";
    return 0;
}

Measured memory_bytes: 16292