akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i].fi)
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i].fi)
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
pair<pii,int> a[MAXN], hull[MAXN];
double ans[MAXN];

pii operator-(pii lhs, pii rhs) {
	return mp(lhs.fi-rhs.fi,lhs.se-rhs.se);
}

int ccw(pll x, pll y) {
	ll v = x.fi * y.se - x.se * y.fi;
	return v == 0 ? 0 : v / abs(v);
}

double hyp(pll x) {
	return hypot(x.fi,x.se);
}

double scal(pll x, pll y) {
	return x.fi * y.fi + x.se * y.se;
}

int main() {
	int n, m=2; ni(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].fi.fi, &a[i].fi.se);
		a[i].se = i;
		if (a[i].fi.se < a[0].fi.se || (a[i].fi.se == a[0].fi.se && a[i].fi.fi < a[0].fi.fi))
			swap(a[i], a[0]);
	}
	if (n == 2) return !printf("0.5\n0.5\n");
	sort(a+1, a+n, [](pair<pii,int> lhs, pair<pii,int> rhs) {
		int o = ccw(lhs.fi-a[0].fi,rhs.fi-a[0].fi);
		if (o == 0)
			return abs(lhs.fi.fi-a[0].fi.fi) + abs(lhs.fi.se-a[0].fi.se) < abs(rhs.fi.fi-a[0].fi.fi) + abs(rhs.fi.se-a[0].fi.se);
		return o > 0 ? true : false;
	});
	hull[0] = a[0], hull[1] = a[1];
	for (int i = 2; i < n; i++) {
		while (m >= 2 && ccw(hull[m-1].fi-hull[m-2].fi,a[i].fi-hull[m-2].fi) < 0)
			m--;
		hull[m++] = a[i];
	}
	while (m >= 2 && ccw(hull[m-1].fi-hull[m-2].fi,hull[0].fi-hull[m-2].fi) < 0)
		m--;
	for (int i = 0; i < m; i++) {
		int k = (i-1+m)%m;
		int j = (i+1)%m;
		double alp = scal(hull[k].fi-hull[i].fi,hull[j].fi-hull[i].fi) / (hyp(hull[k].fi-hull[i].fi)*hyp(hull[j].fi-hull[i].fi));
		ans[hull[i].se] = (pi - acos(alp)) / (2. * pi);
		if (abs(ans[hull[i].se]) < eps)
			ans[hull[i].se] = 0;
	}
	for (int i = 0; i < n; i++)
		printf("%.10f\n", ans[i]);
	return 0;
}


Measured memory_bytes: 4480
# 371 ms, 27032 KB
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []

def solve():
    for _ in range(q):
        bi, ci = list(map(int, input().split()))
        b.append(bi)
        c.append(ci)

    dic = {}
    for aa in a:
        dic[aa] = dic.get(aa, 0) + 1

    s = sum(a)
    for i in range(q):
        if b[i] not in dic:
            print (str(s))
            continue
        s += (c[i]-b[i]) * dic[b[i]]
        dic[c[i]] = dic.get(c[i], 0) + dic[b[i]]
        del dic[b[i]]
        print(s)

def main():
    solve()

if __name__ == "__main__":
    main()

Measured memory_bytes: 26840
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String firstInput[] = str.split("[\\s]+");
        int a = Integer.parseInt(firstInput[0]);
        int aPos = 0;
        int b = Integer.parseInt(firstInput[1]);
        int bPos = 0;
        int[] builds = new int [999];
        builds[0] = 1;
        for(int i = 1; i < builds.length; i++) {
          builds[i] = builds[i-1] + (i+1);
        }
        bPos = b - a - 1;
        aPos = bPos - 1;
        System.out.println(builds[aPos] - a);
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
	long long  j,k,n,t=0;
	cin>>j>>k>>n;
	if ((k-j)<2*n)
	    for (long long i=j;i<=k;++i) cout<<i<<endl;
	    else
	    {
	    	if ((j+n-1)!=(k-n+1))
	    	{
	    	for (long long i=j;i<=j+n-1;++i)
	    	       cout<<i<<endl;
	    	for (long long i=k-n+1;i<=k;++i)
	    	      cout<<i<<endl;
	    	  }
	    	else
	    	{
	    		for (long long i=j;i<=j+n-1;++i)
	    	       cout<<i<<endl;
	    	    for (long long i=k-n+2;i<=k;++i)
	    	      cout<<i<<endl;
			}
		}
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N, K;
    cin >> N >> K;
    vl A(N);
    rep(i, N) cin >> A[i];

    ld ok = *max_element(all(A)), ng = 0;
    rep(_, 100){
        ld mid = (ok + ng) / 2;
        ll cnt = 0;
        rep(i, N){
            cnt += floor(A[i] / mid - EPS);
        }
        (cnt <= K ? ok : ng) = mid;
    }
    cout << (ll)ceil(ok-EPS) << endl;
}

Measured memory_bytes: 4728
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

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

int main()
{
  int N;
  cin >> N;
  int cnt = 0;
  FOR(i,1,N+1){
    if(i%2==1){
      vector<ll> vec=divisor(i);
      if(vec.size()==8){
        cnt++;
      }
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
int main(void){
	int w[9<<14]={};
	int k;
	int max=0;
    int i=0;
	scanf("%d",&k);
	for(;~scanf("%d",&k);)w[k]++;
	for(;++i<1e5;){
        max=fmax(w[i-1]+w[i]+w[i+1],max); 		
	}
	printf("%d",max);
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define int ll
//#define int __int128
//#define ll __int128
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;
typedef complex<double> base;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define SZ(a) ((int)((a).size()))
#define triple(T) tuple<T, T, T>
#define quad(T) tuple<T, T, T, T>
#define watch(x) cerr << (#x) << " = " << (x) << endl;

const double PI = 2 * acos(0.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";

template <class T0, class T1>
inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
    return out << "{" << a.first << ", " << a.second << "}";
}

template <class T0, class T1, class T2>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
}

template <class T0, class T1, class T2, class T3>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
}

template<class T>
inline ostream & operator << (ostream &out, vector<T> &a) {
    out << "[";
    fori (i, a.size())
        out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
    return out;
}

void smain();

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

#ifdef RUS_HOME
    freopen("input.txt", "r", stdin);
    clock_t start = clock();
#endif
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cout << setprecision(12) << fixed;
    smain();
#ifdef RUS_HOME
    cout << "\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
#endif
}
const int oo = 1e9;
const int N = 51;
int MOD = 1e9 + 7;



void smain() {

    int n;
    cin >> n;
    vector <pii> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].second >> v[i].first;
    }
    sort(ALL(v));

    int cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur + v[i].second > v[i].first)
        {
            cout << "No";
            return;
        }
        cur += v[i].second;
    }
    cout << "Yes";

}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
//cout << fixed << setprecision(17) << res << endl;

map<ll,ll> m;
ll n, a, b, c, d;

ll dfs(ll v) {
    if (v == 0) return 0;
    if (v == 1) return d;
    if (m.find(v) != m.end()) return m[v];

    ll res = LONG_LONG_MAX;

    if (v >= 5) {
        res = min(res, dfs(v/5) + c + d * (v%5));
        if (v > 5)
        res = min(res, dfs(v/5+1) + c + d * (5-(v%5)));
    }
    if (v >= 3) {
        res = min(res, dfs(v/3) + b + d * (v%3));
        if (v > 3)
        res = min(res, dfs(v/3+1) + b + d * (3-(v%3)));
    }
    if (v >= 2) {
        res = min(res, dfs(v/2) + a + d * (v%2));
        if (v > 2)
        res = min(res, dfs(v/2+1) + a + d * (2-(v%2)));
    }
    if (v/d < res) {
        res = min(res, v * d);
    }

    m[v] = res;
    return res;
}

void solve() {
    cin >> n >> a >> b >> c >> d;
    m.clear();
    ll res = dfs(n);
    cout << res << endl;
}

int main() {
    ll t;
    cin >> t;
    for (ll i = 0; i < t; ++i) solve();
}


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

using namespace std;


int main() {
  int n;
  scanf("%d", &n);
  set<int> s;
  for (long long y = 1; y <= n; y *= 6) {
    s.insert(y);
  }
  for (long long y = 1; y <= n; y *= 9) {
    s.insert(y);
  }
  constexpr int inf = 1000000000;
  vector<int> dp(n + 5);
  fill(dp.begin(), dp.end(), inf);
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int c : s) {
      if (c <= i) {
        dp[i] = min(dp[i], dp[i - c] + 1);
      }
    }
  }
  printf("%d\n", dp[n]);
  return 0;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;
typedef  unsigned long long ll;
ll a[100005];
ll res;
int main() {
  ll n;
  ll k;
  cin >> n >> k;

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

  for(int i = 0; i < n; i++) {
    res += (k ^ a[i]);
  }
  
  for(int i = 50; i >= 0; i--) {
    if(!(k & (1ll << i))) continue;

    ll tmp = 0;

    for(int j = 50; j >= 0; j--) {
      ll mask = (1ll << j);
      ll num = 0;

      for(int l = 0; l < n; l++) if(a[l] & (1ll << j)) num++;

      if(j > i) {
	if(k & mask) tmp += (n - num) * mask;
	else tmp += num * mask;
      }
      else if(i == j) {
	tmp += num * mask;
      }

      else {
	tmp += mask * max(n - num, num);
      }
    }
    res = max(res,tmp);
  }

  cout << res << endl;
}
  
      
 
  
  
  


Measured memory_bytes: 1024
program main

  implicit none
  character(99) :: s
  integer :: n,nn ,i

  
  read(*,*) s
  n = len_trim( s )
  
  nn = 0
  do i = 1, n/2
    if( s(i:i) == s(n-i+1:n-i+1)) then
    else
      nn = nn + 1
      exit
    end if
  end do
  do i = 1, (n-1)/2/2
    if( s(i:i) == s((n-1)/2-i+1:(n-1)/2-i+1)) then
    else
      nn = nn + 1
      exit
    end if
  end do
  do i = (n+3)/2, (n-(n+3)/2)/2
    if( s(i:i) == s(n-i+1:n-i+1)) then
    else
      nn = nn + 1
      exit
    end if
  end do
  
  if( nn == 0 ) then 
    print*, "Yes" 
  else
    print*, "No" 
  end if

end program main


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

int main() {
  int N;
  string S;
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> S;
    
    if (S == "Y") {
      cout << "Four" << endl;
      break;
    }
    if (i == N - 1 && S != "Y") {
      cout << "Three" << endl;
    }
  }
}

Measured memory_bytes: 256
N, M = map(int, input().split())
t_ans = []
for _ in range(M):
  t_ans.append(list(map(str,input().split())))

ans_num = [0]*(N+1)
ans_pe = [0]*(N+1)

for i in range(M):
  result = t_ans[i][1]
  question = int(t_ans[i][0])
  if result == 'AC' and ans_num[question] == 0:
    ans_num[question] = 1
  elif result == 'WA' and ans_num[question] == 0:
    ans_pe[question] += 1

for i in range(N+1):
  if ans_num[i] != 1:
    ans_pe[i] = 0

print(f'{sum(ans_num)} {sum(ans_pe)}')

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

int pow(int x, int n) {
    int ret = 1;
    while (n) {
        if (n % 2 == 1) {
            ret *= x;
        }
        x *= x;
        n /= 2;
    }
    return ret;
}

int calc(vector<int>& l, int target) {
    if (l.size() == 0) return 1e8;

    set<pair<int, int>> st[l.size()];
    st[0].insert(make_pair(l[0], 0));
    for (int i = 1; i < l.size(); i++) {
        st[i] = st[i - 1];
        st[i].insert(make_pair(l[i], 0));
        for (auto p: st[i - 1]) {
            st[i].insert(make_pair(p.first + l[i], p.second + 10));
        }
    }
    int ret = 1e8;
    for (auto p: st[l.size() - 1]) {
        ret = min(ret, abs(p.first - target) + p.second);
    }
    return ret;
}

int main(void) {
    int n;
    vector<int> a(3);
    cin >> n;
    for (int i = 0; i < 3; i++) {
        cin >> a[i];
    }
    vector<int> l(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }

    int ans = 1e8;
    for (int i = 0; i < pow(3, n); i++) {
        int sum = 0;
        vector<int> st;
        for (int j = 0; j < 3; j++) {
            vector<int> b;
            int x = i;
            for (int k = 0; k < n; k++) {
                if (x % 3 == j) {
                    b.push_back(l[k]);
                    st.push_back(l[k]);
                }
                x /= 3;
            }
            sum += calc(b, a[j]);
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;
 
ll mod = 1e9 + 7;
 
int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  int ans = a * b / 2;
  printf("%d\n", ans);
  return 0;
}

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

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

  int a, b, c;
  cin >> a >> b >> c;
  swap(a, b);
  swap(a, c);
  cout << a << " " << b << " " << c << endl;
}


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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N;
    cin >> N;
    vector<int> v;
    v.resize(N);
    REP(i, N) {
        cin >> v[i];
    }
    sort(ALL(v));
    double s;
    s = v[0];
    FOR(i, 1, N) {
        s = (s + v[i])/2;
    }
    cout << s << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100005,INF=1<<30;

int f(int a,int b){
    if(a<b) return 0;
    if(a%b==0) return a/b;
    ll can=(a-a/b*b)/(a/b+1)+1,can2=INF;
    ll c=a/b+1,d=a%b;
    if(d%c==0) can2=d/c;
    return f(a-(a/b+1)*min(can,can2),b);
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    int grundy=0;
    
    while(N--){
        int a,b;cin>>a>>b;
        grundy^=f(a,b);
    }
    
    if(!grundy) cout<<"Aoki"<<endl;
    else cout<<"Takahashi"<<endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a, b;
    cin >> a >> b;
    ll nr = __gcd(a, b);
    int ans = 1;
    for(ll i = 2; i * i <= nr; ++i)
    {
        if(nr % i == 0)
        {
            ++ans;
            while(nr % i == 0)
                nr /= i;
        }
    }
    if(nr > 1)
        ++ans;
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
L, R = map(int, input().split())

MOD = 2019

if R - L >= MOD or L%MOD == 0 or R%MOD == 0:
    print(0)
else:
    LR = list(range(L, R+1))
    minimum = 2*10**9
    for i in range(len(LR)):
        l = LR[i]
        for r in LR[i+1:]:
            minimum = min(l*r%MOD, minimum)
    print(minimum)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
using namespace std;

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

	long a,b,c,i,j;
	vector<long> v;
	cin>>a;
	v.push_back(a);
	c=0;
	while(1){
		c++;
		if(a==1)
			break;
		else
			a/=2;
	}

	j=0;
	for(i=1;i<c+1;i++){
		j+=pow(2,i-1);
	}
	cout<<j;

    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
s_list = []
for i in range(H):
    s_list.append(input())
check = [[False for _ in range(W)] for _ in range(H)]
move_x = [1, 0, -1, 0]
move_y = [0, 1, 0, -1]


def dfs(i, j):
    check[i][j] = True

    if s_list[i][j] == "#":
        cnt[0] += 1
    else:
        cnt[1] += 1

    for m in range(4):
        next_i = i + move_y[m]
        next_j = j + move_x[m]
        if 0 <= next_i < H and 0 <= next_j < W and s_list[i][j] != s_list[next_i][next_j] \
                and not check[next_i][next_j]:
            dfs(next_i, next_j)


ans = 0
for i in range(H):
    for j in range(W):
        cnt = [0] * 2
        dfs(i, j)
        ans += cnt[0] * cnt[1]
print(ans)


Measured memory_bytes: 148172
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;


int main(void){
  int a,b,m,i,ap[100005],bp[100005],amin,bmin,x,y,c;
  
  cin >> a >> b >> m;
  for (i=0;i<a;i++) cin >> ap[i];
  for (i=0;i<b;i++) cin >> bp[i];
  
  amin=bmin=1e9;
  for (i=0;i<a;i++) amin=min(amin,ap[i]);
  for (i=0;i<b;i++) bmin=min(bmin,bp[i]);
  
  int pmin=amin+bmin;
  for (i=0;i<m;i++){
    cin >> x >> y >> c;
    pmin=min(pmin,ap[x-1]+bp[y-1]-c);
  }
  
  cout << pmin << endl;
  
  return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<ll, P> E;
#define MOD (1000000007ll)
#define l_ength size
#define PI 3.14159265358979
 
void mul_mod(ll& a, ll b){
    a *= b;
    a %= MOD;
}
 
void add_mod(ll& a, ll b){
    b += MOD;
    a += b;
    a %= MOD;
}

int main(void){
	int n,i,k;
	ll a[123456],mx=0ll,kmx=-1ll;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a[i];
		mx = max(mx,a[i]);
	}
	for(i=0; i<n; ++i){
		if(mx == a[i]){
			continue;
		}
		if(kmx < min(a[i],mx-a[i])){
			kmx = min(a[i],mx-a[i]);
			k = i;	
		}
	}
	cout << mx << " " << a[k] << endl;
    return 0;
}

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

int keta_sum(string C){
  int sum=0;
  for(int i=0;i<C.size();i++){
    int c=C[i] - '0';
    sum +=c;
  }
  return sum;
}

int main(){
  int N,a,b;
  cin >>N;
  int sum;
  int result=10000;
  for(int i=1;i<N/2+1;i++){
    a=i;
    b=N-a;
    string A=to_string(a);
    string B=to_string(b);
    sum=keta_sum(A)+keta_sum(B);
    if(result>=sum){
      result=sum;
    }
  }
  cout << result << endl;
}

Measured memory_bytes: 256
// Aizu Vol-1 0106: Discounts of Buckwheat 
// 2017.8.12 bal4u@uu

#include <stdio.h>

int tbl[60];
int a[3] = { 2, 3, 5 };
int s[3] = { 380, 550, 850 };
int c[3] = { 10, 12, 15 };
int f[3] = { 1520, 1870, 2244 };

void combi(int i, int v, int cost)
{
	int j, cc;

	if (i == 3) {
		if (v <= 50 && tbl[v] == 0 || tbl[v] > cost) tbl[v] = cost;
		return;
	}
	for (j = 0; v+j <= 50; j += a[i]) {
		cc = j / c[i] * f[i] + (j % c[i]) / a[i] * s[i];
		combi(i + 1, v + j, cost + cc);
	}
}

int main()
{
	int n;

	combi(0, 0, 0);
	while (1) {
		scanf("%d", &n); if (!n) break;
		printf("%d\n", tbl[n / 100]);
	}
	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=998244353;
#define N 510100
ll int n,m;
ll int a[N],b[N];
int used[N];
vec G[N];
main(){
    n=in();m=in();
    rep(i,m){
        int a=in(),b=in();
        G[a].pb(b);
        G[b].pb(a);
    }
    used[1]=1;
    vec v1,v2;
    int now=1;
    while(1){
        bool flag=false;
        int a=G[now].size();
        rep(i,a){
            int t=G[now][a-1-i];
            if(used[t]){
                G[now].pop_back();
                continue;
            }
            v1.pb(t);
            used[t]=1;
            now=t;
            flag=true;
            break;
        }
        if(!flag)break;

    }
    now=1;
    while(1){
        bool flag=true;
        int a=G[now].size();
        rep(i,a){
            int t=G[now][a-1-i];
            if(used[t]){
                G[now].pop_back();
                continue;
            }
            v2.pb(t);
            used[t]=1;
            now=t;
            flag=false;
            break;
        }
        if(flag)break;

    }
    cout<<v1.size()+v2.size()+1<<endl;
    rep(i,v2.size()){
        cout<<v2[v2.size()-1-i]<<" ";
    }
    cout<<1<<" ";
    for(auto e:v1){
        cout<<e<<" ";
    }
    return 0;
}

Measured memory_bytes: 18680
n = int(input())
s = ""
for i in range(1, n+1):
    x = i
    if (x % 3 == 0):
        s = s + " " + str(i)
    else:
        while x % 10 != 3 and x > 0:
            x = x // 10
        if x % 10 == 3:
            s = s + " " + str(i)
print(s)


Measured memory_bytes: 5624
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    a, b = map(int, sys.stdin.readline().split())
    if a % 2 == 0 or b % 2 == 0:
        print('Even')
    else:
        print('Odd')

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
H,W,N = map(int,input().split())
Nli=[0 for j in range(9*N)]
q=0
for k in range(N):
    a,b=map(int,input().split())
    for n in range(-1,2):
        for m in range(-1,2):
            if 0<=a-2-m<H-2 and 0<=b-2-n<W-2:
                Nli[q]=(b-n)*(H)+(a-m)
                q+=1
del Nli[q:]
import collections
s = collections.Counter(Nli)
v = list(s.values())
print((H-2)*(W-2)-len(set(Nli)))
for k in range(1,10):
    print(v.count(k))

Measured memory_bytes: 185584
#include<stdio.h>
#define WHITE 0
#define BLACK 1
#define inf 2000000
#define NIL -1
int main()
{
  int n,i,j,mincost,u,v,a=0;
  int graph[101][101];
  int d[101], pi[101];
  int color[101];

scanf("%d",&n);
for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
      {
	scanf("%d",&graph[i][j]);
      }
  }

for(u=1;u<=n;u++)
  {
    d[u] = inf;
    pi[u] = NIL;
    color[u] = WHITE;
  }
 d[1] = 0;

 while(1)
   {
     mincost =inf;
     for(i=1;i<=n;i++)
       {
	 if(color[i]!=BLACK && d[i]<mincost)
	   {
	     mincost = d[i];
	     u=i;
	   }
       }
	 if(mincost ==inf)break;

	 color[u]=BLACK;


	     for(v=1;v<=n;v++)
	       {
		 if(graph[u][v] == -1) continue;
		else if(color[v]!=BLACK && graph[u][v]<d[v])
		   {
		     pi[v] =u;
		     d[v] = graph[u][v];
		   }
	       }
	   }
       

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

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
 
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef complex<double> base;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) { 
    return os << '(' << pai.first << ' ' << pai.second << ')';
}
 
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    cout << '[';
    for (auto p : v) cout << p << ",";
    cout << "]";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif
 
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}

int N, K;
int A[100];
int W[100001];

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

    cin >> N >> K;
    rep(i, N) cin >> A[i];
    W[0] = false;

    repp(i, 1, K+1) {
        bool f = false;
        rep(j, N) if (A[j] <= i) f |= (W[i-A[j]] == 0);
        if (f) W[i] = 1;
    }

    cout << (W[K]?"First":"Second") << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long  k,x;bool f=0;
    cin>>k>>x;
    for (long long i=x-k+1;i<=x+k-1;i++)
        if (i>=-1000000&&i<=1000000)
            if (f==0)cout<<i,f=1;
            else cout<<" "<<i;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = 1e9 + 7;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fr first
#define sc second




int main() {
	double a, b, c, n, d[100000];
	string s, t;
	cin >> a >> b;
	cout << b * 2 - a << endl;
	return 0;
}

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

int main(){
    ll N;
    int K;
    cin>>N>>K;
    vector<ll>A(N);
    rep(i,N){
        cin>>A[i];
    }
    for(int i=0;i<min(K,100);i++){
        vector<ll>B(N,0);
        for(ll j=0;j<N;j++){
            if(j-A[j]<=0){
                B[0]+=1;
            }
            else{
                B[j-A[j]]+=1;
            }
            if(j+A[j]+1<N){
                B[j+A[j]+1]-=1;
            }
        }
        A[0]=B[0];
        for(int j=1;j<N;j++){
            A[j]=A[j-1]+B[j];
        }
    }
    for(int j=0;j<N;j++){
        cout<<A[j]<<" ";
    }
    cout<<""<<endl;
}

Measured memory_bytes: 6424
n,m=map(int,input().split())
l=[]
for i in range(m):
    s,c=map(int,input().split())
    l.append((s,c))

ans=-1
for i in range(1000):
    k=str(i)
    cnt=0
    if len(k)==n:
        for j in range(m):
            if int(k[l[j][0]-1])==l[j][1]:
                cnt+=1
        if cnt==m:
            ans=i
            break
if ans==-1:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 3064
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		String[] a = new String[h];
		for(int i = 0;i< h ;i++) {
			a[i] = sc.next();
		}
		for(int i = 0;i < w+2;i++) {
			System.out.print("#");
		}
		System.out.println();
		for(int i = 0;i < h;i++) {
			System.out.println("#"+a[i]+"#");
		}
		for(int i = 0;i < w+2;i++) {
			System.out.print("#");
		}
		System.out.println();
	}

}

Measured memory_bytes: 21844
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[最小包含円]
中心座標(x,y)をx座標,y座標それぞれについて三分探索.
"""
n = I()
xy = [LI() for _ in range(n)]

def d(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

def f(x,y):
    res = 0
    for x1,y1 in xy:
        res = max(res,d(x,y,x1,y1))
    return res

def g(x):
    l,r = 0,1000
    for _ in range(80):
        a = (l*2+r)/3
        b = (l+r*2)/3
        if f(x,a) > f(x,b):
            l = a
        else:
            r = b
    return f(x,l)

l,r = 0,1000
for _ in range(80):
    a = (l*2+r)/3
    b = (l+r*2)/3
    if g(a) > g(b):
        l = a
    else:
        r = b
print(g(l))




Measured memory_bytes: 47596
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 998244353;
#define SIZE 1100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
int main()
{
	invinit();
	int x, y;
	scanf("%d%d", &x, &y);
	ll sum = 0;
	ll now = com(x + y, x);
	for (int i = 1; i <= x + y; i++)
	{
		//printf("%lld\n", now);
		sum += now;
		if (i & 1)
		{
			int a = i / 2, b = a + 1;
			ll t = com(a + b, a)*com(x + y - a - b - 1, y - b) % mod*b%mod*inv[a + b] % mod;
			ll s = com(b + b, b)*com(x + y - b - b, y - b) % mod*inv[2] % mod;
			now = (now + mod + s - t * 2 % mod) % mod;
		}
	}
	printf("%lld\n", sum % mod*kai[x] % mod*kai[y] % mod*invkai[x + y] % mod);
}

Measured memory_bytes: 25984
#include<bits/stdc++.h>
#define int long long
#define maxn 100005
using namespace std;
int n,m,dp[maxn];
bool f[maxn];
main()
{
	memset(dp,0,sizeof(dp));
	memset(f,true,sizeof(f));
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x;
		cin>>x;
		f[x]=false;
	}
	if(f[1])
		dp[1]++,dp[2]++;
	if(f[2])
		dp[2]++;
	else
		dp[2]=0;
	for(int i=3;i<=n;i++)
	{
		if(f[i])
			dp[i]=(dp[i-1]+dp[i-2])%1000000007;
	}
	cout<<dp[n]%1000000007LL<<endl;
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

ll N,K;

int main(){
    cin >> N >> K;
    vector<pii> v(N);
    rep(i,N){
        ll t,d;
        cin >> t >> d;
        t--;
        v[i] = make_pair(d,t);
    }
    sort(all(v),greater<pii>());

    vector<pii> v1;
    vector<pii> v2;
    set<int> used;
    for(int i=0;i<N;i++){
        if(!used.count(v[i].second)){
            used.insert(v[i].second);
            v1.push_back(v[i]);
        }else{
            v2.push_back(v[i]);
        }
    }

    int k = 0;
    used.clear();
    for(int i=0;i<K;i++){
        if(used.count(v[i].second)) continue;
        else{
            used.insert(v[i].second);
            k++;
        }
    }

    vector<ll> v1sum(v1.size()+1,0);
    for(int i=0;i<v1.size();i++) v1sum[i+1] = v1sum[i] + v1[i].first;
    vector<ll> v2sum(v2.size()+1,0);
    for(int i=0;i<v2.size();i++) v2sum[i+1] = v2sum[i] + v2[i].first;


    ll ans = 0;
    for(ll x=k;x<=K;x++){
        ll cnt = x * x;
        if(!(x<v1sum.size())) continue;
        cnt += v1sum[x];
        if(!(K-x<v2sum.size())) continue;
        cnt += v2sum[K-x];
        ans = max(ans,cnt);
    }
    cout << ans << endl;
}


Measured memory_bytes: 8816
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

struct unionFind {
    vector<int> par; // 親を指すvector,-par[親]は木のサイズ
    unionFind(int n):par(n, -1) {} // 自分で親を埋め込んでいく必要あり
    int root(int x) { // 親をたどる&データの整理
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    bool unite(int x, int y) { // データの結合
        x = root(x);
        y = root(y);
        if(x == y) return false;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    bool same(int x, int y) {return root(x) == root(y);} // 所属判定
    int size(int x) {return -par[root(x)];} // 木のサイズ
} uft(100000);

vvi G;
vvi G_;
vi wa;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    G.resize(n);
    G_.resize(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].push_back(b);
        G[b].push_back(a);
        uft.unite(a, b);
    }
    wa.resize(n);
    rep(i, k) {
        int c, d;
        cin >> c >> d;
        --c;
        --d;
        G_[c].push_back(d);
        G_[d].push_back(c);
        if(uft.same(c, d)) {
            wa[c]--;
            wa[d]--;
        }
    }

    rep(i, n-1) {
        cout << uft.size(i) - 1 - (int)G[i].size()+wa[i] << ' ';
    }
    cout << uft.size(n-1) - 1 - (int)G[n-1].size()+wa[n-1] << endl;
}

Measured memory_bytes: 12664
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define vi vector<ll>
#define vb vector<bool>
#define pii pair<ll,ll>
#define mod 1000000007
#define pll pair<ll,ll>
#define rep(i,n) for(ll i=0;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define per1(i,n) for(ll i=n;i>0;i--)
#define prll(a,n) for(ll i=0;i<n;i++){ cout<<a[i]<<" "; }
#define ain(a) for(auto &i:a) cin>>i
#define mms(a) memset(a,0,sizeof(a))
// cout << fixed << setprecision(0) << pi <<" "<<npi<<endl; 


ll max_ll(ll a,ll b,ll c){
	return max(a,max(b,c));
}

ll min_ll(ll a,ll b,ll c){
	return min(a,min(b,c));
}


bool sortBySec(pair<ll,ll> a,pair<ll,ll> b){
    if(a.second==b.second)
		return a.first<b.first;
    return (a.second < b.second); 
}

long long binexpmod(long long a, long long b){
    long long res =1;
    while(b>0){
        if(b&1){
            res = res * a % mod;
        }
        a = a * a % mod;
        b>>=1;
    }
    return(res);
}


ll lcm(ll a,ll b){
	ll x=__gcd(a,b);
	a/=x;
	b/=x;
	ll sum=a*b*x;
	return sum;
}
void solve(){
    ll n;
    double res=0.0;
	cin>>n;
    vector<double> dp(n+1,0.0);
    //i is the probability that it is i heads till now
    dp[0]=1;
    rep1(i,n){
        double pro;
        cin>> pro;
        for(ll j=i;j>=0;--j){
            dp[j] = (j==0?0:dp[j-1]*pro) + dp[j]*(1-pro);
        }
    }
    for (ll i=n/2+1;i<=n;i++){
        res+=dp[i];
    }
	cout<< fixed << setprecision(10)<<res<<endl;
	return;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let n = get!(usize);
    let s = get!(String).chars().collect::<Vec<_>>();

    let mut whites = vec![0; n+1];
    for i in 0..n {
        whites[i+1] = if s[i] == '.' {
            whites[i] + 1
        } else {
            whites[i]
        };
    }

    let  mut mn = std::usize::MAX;
    for i in 0..(n+1) {
        mn = min!(mn, (i-whites[i]) + (whites[n]-whites[i]));
    }
    println!("{}", mn);
}


Measured memory_bytes: 10620
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16000000")
using namespace std;

typedef pair <int, int> ii;

const int Maxn = 100005;
const int Maxm = 20;

int n, m;
int cnt[Maxn];
vector <int> neigh[Maxn];
int par[Maxn], siz[Maxn];
vector <ii> E;
int has;
int L[Maxn], P[Maxn][Maxm], V[Maxn];

int getPar(int x) { return par[x] == x? x: par[x] = getPar(par[x]); }

bool unionSet(int a, int b)
{
    a = getPar(a), b = getPar(b);
    if (a == b) return false;
    if (siz[a] < siz[b]) swap(a, b);
    siz[a] += siz[b]; par[b] = a;
    return true;
}

void Traverse(int v)
{
    V[v] += cnt[v] >= 4;
    for (int i = 0; i < neigh[v].size(); i++) {
        int u = neigh[v][i];
        if (P[v][0] == u) continue;
        L[u] = L[v] + 1; P[u][0] = v; V[u] = V[v];
        Traverse(u);
    }
}

int getLCA(int a, int b)
{
    if (L[a] < L[b]) swap(a, b);
    for (int i = Maxm - 1; i >= 0; i--)
        if (L[a] - (1 << i) >= L[b])
            a = P[a][i];
    if (a == b) return a;
    for (int i = Maxm - 1; i >= 0; i--)
        if (P[a][i] != P[b][i])
            a = P[a][i], b = P[b][i];
    return P[a][0];
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        par[i] = i, siz[i] = 1;
    for (int i = 0; i < m; i++) {
        int a, b; scanf("%d %d", &a, &b);
        cnt[a]++; cnt[b]++;
        if (unionSet(a, b)) {
            neigh[a].push_back(b);
            neigh[b].push_back(a);
        } else E.push_back(ii(a, b));
    }
    for (int i = 1; i <= n; i++)
        if (cnt[i] % 2) { printf("No\n"); return 0; }
    for (int i = 1; i <= n; i++)
        if (cnt[i] >= 6) { printf("Yes\n"); return 0; }
        else if (cnt[i] >= 4) has++;
    Traverse(1);
    for (int j = 1; j < Maxm; j++)
        for (int i = 1; i <= n; i++)
            P[i][j] = P[P[i][j - 1]][j - 1];
    for (int i = 0; i < E.size(); i++) {
        int a = E[i].first, b = E[i].second;
        int lca = getLCA(a, b);
        int cur = V[a] + V[b] - V[lca] - V[P[lca][0]];
        if (cur < has) { printf("Yes\n"); return 0; }
    }
    printf("No\n");
    return 0;
}


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

#define mp make_pair
#define pb push_back
#define REP(i,a,n) for(int i = a;i < (n);i++)
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define range(x,min,max) ((min) <= (x) && (x) <= (max))
#define xyrange(x, minX, maxX, y, minY, maxY) (range(x, minX, maxX) && range(y, minY, maxY))

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef pair<int,int> PII;
typedef vector<PII> VPII;


const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};
const int INF = INT_MAX / 2;

string S;

string solve() {
	reverse(all(S));
	int i = 0;
	string s;
	while (i < S.size()) {
		if (S[i] == 'm') {
			s += "maerd";
			i += 5;
		} else if (S[i] == 'e') {
			s += "esare";
			i += 5;
		} else if (S[i] == 'r') {
			if (i + 6 < S.size() && S[i + 6] == 'd') {
				s += "remaerd";
				i += 7;
			} else {
				s += "resare";
				i += 6;
			}
		} else {
			return "NO";
		}
	}
	return (s == S? "YES" : "NO");
}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	cin >> S;
	cout << solve() << endl;
	return 0;
}



Measured memory_bytes: 592
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
#define FOR(i,a,n) for(int i=a;i<n;++i)
#define eFOR(i,a,n) for(int i=a;i<=n;++i)
#define rFOR(i,a,n) for(int i=n-1;a<=i;--i)
#define erFOR(i,a,n) for(int i=n;a<=i;--i)

ll dp[102][2][5];
int main() {
	string t; cin >> t;
	int n = t.length();
	vector<int> s(n);
	FOR(i, 0, n)s[i] = t[i] - '0';
	int k; cin >> k;

	dp[0][0][0] = 1;
	FOR(i, 0, n)FOR(small, 0, 2)eFOR(j, 0, k)eFOR(x, 0, (small ? 9 : min(9, s[i]))) {
		dp[i + 1][small | (x < s[i])][j + (x != 0)] += dp[i][small][j];
	}

	cout << dp[n][0][k] + dp[n][1][k] << endl;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) (x.begin(),x.end())
#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 ms(x,a) memset((x),a,sizeof(x))
#define fi first
#define se second 
using namespace std;
const int maxn=1e5+5;
const int maxl=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
 
int a,b;
int main(){
	while(cin>>a>>b)
	cout<<a*b-a-b+1<<endl;
} 

Measured memory_bytes: 256