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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:

const int limit = 500010;
int dp[limit][3];

using pii = pair<int, int>;
vector<int> pos;
vector<pii> ones;

int main(void) {
	int n;
	string s;
	cin >> n >> s;

	string tmp(n, '.');

	rep(i, 1, n - 1) {
		if (s[i - 1] == '1' and s[i] == '0' and s[i + 1] == '1') {
			tmp[i] = '*';
			pos.push_back(i);

			pii in;

			{
				int cur = i - 1;
				while (cur >= 0) {
					if (s[cur] == '0') break;
					cur--;
					in.first++;
				}
			}

			{
				int cur = i + 1;
				while (cur < n) {
					if (s[cur] == '0') break;
					cur++;
					in.second++;
				}
			}

			ones.push_back(in);
			//cerr << pos.back() << " " << ones.back().first << " " << ones.back().second << endl;
		}
	}


	const int m = ones.size();
	if (m == 0) {
		cout << 0 << endl;
		return 0;
	}


	dp[0][0] = 0, dp[0][1] = ones[0].first , dp[0][2] = ones[0].second;

	rep(i, 1, m) {
		chmax(dp[i][0], max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}));
		pii in = ones[i];
		const int total = pos[i] - pos[i - 1] - 1;

		chmax(dp[i][1], dp[i - 1][0] + in.first);
		if (in.first != total)
			chmax(dp[i][1], dp[i - 1][1] + in.first);
		else
			chmax(dp[i][1], dp[i - 1][1] + in.first - 1);

		if (in.first != total)
			chmax(dp[i][1], dp[i - 1][2] + in.first);
		else
			chmax(dp[i][1], dp[i - 1][2]);

		chmax(dp[i][2], dp[i - 1][0] + in.second);
		if (in.first != total or in.first != 1) chmax(dp[i][2], dp[i - 1][1] + in.second);

		if (in.first != total)
			chmax(dp[i][2], dp[i - 1][2] + in.second);
		else
			chmax(dp[i][2], dp[i - 1][2] + in.second - 1);
	}


	int ans = max({dp[m - 1][0], dp[m - 1][1], dp[m - 1][2]});
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3324
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::cin;

int main(){
    string s,t;
    cin >> s >> t;
    if(s == t.substr(0,s.size())){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
    return 0;
}

Measured memory_bytes: 3624
import sys
from math import sqrt

inf = 1<<30

def solve():
    while 1:
        h, w = map(int, sys.stdin.readline().split())

        if h == w == 0:
            return

        L = h**2 + w**2

        ansx, ansy = zentansaku(h, w, L)

        print(ansx, ansy)

def zentansaku(h, w, L):
    ansx = ansy = maxL = inf

    for x in range(1, 150 + 1):
            for y in range(x + 1, 150 + 1):
                if x**2 + y**2 == L:
                    if h < x:
                        return x, y
                elif L < x**2 + y**2 < maxL:
                    maxL = x**2 + y**2
                    ansx = x
                    ansy = y

    return ansx, ansy

if __name__ == '__main__':
    solve()

Measured memory_bytes: 7692
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
x = sum(a)
count = Counter(a)

q = int(input())
b,c = [],[]

for i in range(q):
    bi,ci = map(int,input().split())
    b.append(bi),c.append(ci)
for i in range(q):
    bi,ci = b[i],c[i]
    x -= bi*count[bi]
    x += ci*count[bi]
    count[ci]+=count[bi]
    count[bi] = 0
    print(x)

Measured memory_bytes: 30308
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll N, M, K;
  cin>>N>>M>>K;
  vector<ll> A(N+1);
  vector<ll> B(M+1);
  for(int i=1;i<=N;++i) cin>>A[i];
  for(int i=1;i<=N;++i) A[i] += A[i-1];
  for(int i=1;i<=M;++i) cin>>B[i];
  for(int i=1;i<=M;++i) B[i] += B[i-1];
  int ans = 0;
  ll tmp;
  int index;
  for(int i=0;i<=N;++i){
    tmp = A[i];
    if(tmp>K) break;
    index = upper_bound(B.begin(), B.end(), K-tmp)-B.begin();
    if(ans<i+index) ans = i+index-1;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 6368
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <assert.h>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

#define MAX_V 2000010
#define INF 1000000000

ll n;
ll h,w,k;

struct edge{int to, cost;};
typedef pair<int,int> P;

vector<edge> G[MAX_V];
int mn[MAX_V];

void ae(int from, int to, int cost){
  edge e = {to,cost};
  G[from].push_back(e);
}

void dijk(int start, int V){
  priority_queue<pair<P,P>, vector<pair<P,P> >, greater<pair<P,P> > > que;
  for(int i = 0; i < V; i++)mn[i] = INF;
  mn[start] = 0;
  que.push(pair<P,P>(P(0,start),P(0,0)));
  while(!que.empty()){
    pair<P,P> p = que.top(); que.pop();
    int v = p.first.second;
    if(mn[v]<p.first.first)continue;
    P a = p.second;
    ll q = k-(p.first.first%k);
    if(a.first==0){
      ae(v,n+v,q%k);
    }
    else{
      ae(v,v-n,q%k);
    }
    for(int i = 0; i < G[v].size(); i++){
      edge e = G[v][i];
      ll g;
      if(e.to>=n)g=1;
      else g = 0;
      if(mn[e.to] > mn[v]+e.cost){
        mn[e.to] = mn[v]+e.cost;
        que.push(pair<P,P>(P(mn[e.to],e.to),P(g,0)));
      }
    }
  }
}

int main(){
  cin>>h>>w>>k;
  n = h*w;
  ll x1,y1,x2,y2;
  cin>>y1>>x1>>y2>>x2;
  x1--;x2--;y1--;y2--;
  vector<string> vs;
  rep(y,0,h){
    string s;
    cin>>s;
    vs.pb(s);
  }
  rep(y,0,vs.sz){
    rep(x,0,vs[y].sz){
      if(x!=vs[y].sz-1&&vs[y][x+1]!='@')ae(y*w+x,y*w+x+1,1);
      if(x!=0&&vs[y][x-1]!='@')ae(y*w+x,y*w+x-1,1);
      if(y!=vs.sz-1&&vs[y+1][x]!='@')ae(n+y*w+x,n+(y+1)*w+x,1);
      if(y!=0&&vs[y-1][x]!='@')ae(n+y*w+x,n+(y-1)*w+x,1);
    }
  }
  ae(y1*w+x1,n+y1*w+x1,0);
  ae(n+y1*w+x1,y1*w+x1,0);
  ae(y2*w+x2,n+y2*w+x2,0);
  ae(n+y2*w+x2,y2*w+x2,0);
  dijk(y1*w+x1,n*2);
  ll ans = mn[y2*w+x2];
  if(ans==INF){
    cout << -1 << endl;
  }
  else{
    if(ans%k!=0)ans = (ans+(k-1))/k*k;
    cout << ans/k << endl;
  }
  return 0;
}

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

int main(void){
	int N, X, T;
	cin >> N >> X >> T;
	int ans = T*(N/X) + T*(N%X!=0);
	cout << ans << endl;
return 0;
}


Measured memory_bytes: 3628
import numpy as np
import itertools

N, M, X, B = *map(int, input().split()), np.array([])

class book:
    def __init__(self, price, *understanding):
        self.price = price
        self.understanding = np.array(understanding)
    def __add__(self, other):
        return book(self.price+other.price , *self.understanding+other.understanding)

for _ in range(N):
    B = np.append(B, book(*map(int, input().split())))

P = []
for i in range(2**N):
    temp = book(0, *[0]*M)
    for j in range(N):
        if ((i >> j) & 1):
            temp += B[j]
    P.append(temp)

P = np.array(list(filter(lambda x: all(X<=x.understanding),P)))
P = np.array(list(sorted(P, key=lambda x: x.price)))
try:
    print(P[0].price)
except IndexError:
    print(-1)

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

/*
提出前に確認!
- setとmultisetを間違えない
*/

int	main(void)
{
	int n;
	cin >> n;
	cout << (1000 - n % 1000) % 1000 << endl;
	return (0);
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int N;
  cin >> N;
  if(N%10 == 7 || N%100/10 == 7 || N/100 == 7){
  	cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}

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

int main() {
  int N;
  cin >> N;
  int P = 0;
    for(int i = 0 ; i < N ; i++) {
      int l,r;
      cin >> l >> r;
      
      P += r - l + 1;
    }
  cout << P << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

S = input().rstrip('\r')
count = [0, 0]
for s in S:
    if (s == 'A'): count[0] = 1
    if (s == 'B'): count[1] = 1
if count[0] == 1 and count[1] == 1:
    print('Yes')
else:
    print('No')

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

unsigned GetDigit(unsigned num) {
    return to_string(num).length();
}

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

    for(int i=1; i<=n; i++) {
        int tmp = GetDigit(i)%2;
        if (tmp == 1) {
            ans++;
        };
    };

    cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int N; 
    cin >> N;
    vector<int> vec_X(N);
    for(int i = 0; i < N; i ++)
    {
        cin >> vec_X[i];
    }
    //for(int i = 0; i < N; i ++)
    //{
    //    cout << vec_X[i] << endl ;
    //}
    int temp = vec_X[0];
    int flag_up = 0; //0 neutral, 1 up , 2 down;
    int cnt = 1;
    for(int i = 1; i < N; i ++)
    {
        int temp_flag = flag_up; 

        if(temp < vec_X[i])
        {
            flag_up = 1;
        }else if(temp > vec_X[i])
        {
            flag_up = 2;
        }
        //cout << "flag_up" << flag_up << endl;
        if ((temp_flag == 1 && flag_up == 2) || (temp_flag == 2 && flag_up == 1))
        {
            cnt++;
            flag_up = 0;
        }
        temp = vec_X[i];
    }
    cout << cnt << endl;


}


Measured memory_bytes: 640
extern crate core;

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = run(input.trim().to_string());
    println!("{}", output);
}

fn run(input: String) -> String {
    let mut m = 0;
    let mut a = 0;
    let mut r = 0;
    let mut c = 0;
    let mut h = 0;
    for x in input.split("\n").skip(1).map(|x| x.to_string()) {
        if x.find("M") == Some(0) {
            m += 1;
        } else if x.find("A") == Some(0) {
            a += 1;
        } else if x.find("R") == Some(0) {
            r += 1;
        } else if x.find("C") == Some(0) {
            c += 1;
        } else if x.find("H") == Some(0) {
            h += 1;
        }
    }

    let mut list: Vec<i64> = vec![];
    if m != 0 {
        list.push(m);
    }
    if a != 0 {
        list.push(a);
    }
    if r != 0 {
        list.push(r);
    }
    if c != 0 {
        list.push(c);
    }
    if h != 0 {
        list.push(h);
    }

    //グループの数
    let n = list.len();
    if n == 3 {
        list[0] * list[1] * list[2]
    } else if n == 4 {
        list[0] * list[1] * list[2] + list[0] * list[1] * list[3] + list[0] * list[2] * list[3]
            + list[1] * list[2] * list[3]
    } else if n == 5 {
        list[0] * list[1] * list[2] + list[0] * list[1] * list[3] + list[0] * list[1] * list[4]
            + list[0] * list[2] * list[3] + list[0] * list[2] * list[4]
            + list[0] * list[3] * list[4] + list[1] * list[2] * list[3]
            + list[1] * list[2] * list[4] + list[1] * list[3] * list[4]
            + list[2] * list[3] * list[4]
    } else {
        0
    }.to_string()
}

#[test]
fn test() {
    let tests = vec![
        (
            "5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI",
            "2",
        ),
        (
            "4
ZZ
ZZZ
Z
ZZZZZZZZZZ",
            "0",
        ),
        (
            "5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO",
            "7",
        ),
    ];
    for (i, (input, output)) in tests.into_iter().enumerate() {
        println!("test:{}", i);
        assert_eq!(run(input.to_string()), output.to_string());
    }
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a;
	cin>>a;
	LL sum=0;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=a;j++){
			for(int k=1;k<=a;k++){
				sum+=(__gcd(i,__gcd(j,k)));
			}
		}
	}	
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3636
K, N = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    if A[i+1]-A[i]>ans:
        ans = A[i+1]-A[i]
if ans> K-A[N-1]+A[0]:
    print(K-ans)
else:
    print(A[N-1]-A[0])

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

main() {
    int N,M,X; cin >> X >> M >> X;
    int ans=0,ans2=0;
    rep(i,M){
        int a; cin >> a;
        if(a<X) ans++;
        else ans2++;
    }
    cout << min(ans,ans2) << endl;

    return 0;
}

Measured memory_bytes: 256
import unittest
from io import StringIO
import sys
from math import factorial
from scipy.misc import comb
import math


def resolve():
    N = int(input())
    d = {}
    count = 0
    for i in range(N):
        s = list(input())
        s.sort()
        s = ''.join(s)
        if s not in d.keys():
            d[s] = 1
        else:
            count += d[s]
            d[s] += 1

    print(count)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
acornistnt
peanutbomb
constraint"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
oneplustwo
ninemodsix"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa"""
        output = """4"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


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

int main(){
    int n,k;
    int r,s,p;
    string t;
    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> t;
    map<char, int> mp;
    mp['p'] = s;
    mp['r'] = p;
    mp['s'] = r;
    vector<bool> ngfl_r(n+k),ngfl_s(n+k),ngfl_p(n+k);
    map<char,vector<bool>> ngmp;
    ngmp['p'] = ngfl_p;
    ngmp['r'] = ngfl_r;
    ngmp['s'] = ngfl_s;

    ll total=0;
    rep(i,n){
        char c = t.at(i);
        if(ngmp[c].at(i)) continue;
        total += mp[c];
        // cout << "i: " << i << " " << mp[c]<< endl;
        ngmp[c][i+k]=true;
    }
    cout << total << endl;
    return 0;
}

Measured memory_bytes: 512
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n+1)

    def sum(self, i):  # sum in [0, i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # i > 0
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, Q = map(int, input().split())
a = list(map(int, input().split()))

bit = Bit(N)

for i, v in enumerate(a):
    bit.add(i+1, v)

for i in range(Q):
    b, c, d = map(int, input().split())

    if b == 0:
        bit.add(c+1, d)
    else:
        print(bit.sum(d) - bit.sum(c))


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

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'

int n;
VI h(100010);

signed main()
{
    cin >> n;
    REP(i, n){
        cin >> h[i];
    }
    h.resize(n);

    VI dp(n, 1000000001);
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);


    FOR(i, 2, n){
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
    }

    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1792
n=int(input())
match=[]
for i in range(n):
    a=list(map(int, input().split()))
    match.append(a)

select=[list(range(n))]

day=0
mat=0
for _ in range(int(n*(n-1)/2)):
    nex=[]
    for x in select[day]:
        if len(match[x]) != 0 and not x in nex and not match[x][0]-1 in nex and match[match[x][0]-1][0] == (x+1):
            nex.append(x)
            nex.append(match[x][0]-1)
            match[match[x][0]-1].pop(0)
            match[x].pop(0)
            mat+=1

    if len(nex) == 0 and mat==int(n*(n-1)/2):
        break
    
    if len(nex) == 0:
        print(-1)
        exit()

    select.append(nex)
    day+=1

print(day)

Measured memory_bytes: 127764
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
typedef long long int ll;
typedef long double ld;
#define PI 3.141592653589793
#define MOD 1000000007
#define ALL(obj) (obj).begin(),(obj).end()
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 = 1LL << 60;

//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}

int main() {
    ll n;
    cin >> n;
    vector<pair<ll,ll> > p;
    for (ll i=0;i<n;i++){
        ll a;
        cin >> a;
        p.push_back(make_pair(a,i));
    }
    sort(ALL(p),pairCompare);
    for (ll i=0;i<n;i++){
        cout << p[i].second+1 << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 5304
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define mes(a,b) memset((a),(b),sizeof((a)))
#define syio std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
#define lson l, mid, rt << 1
#define rson mid+1, r, rt << 1 | 1
typedef long long ll;
typedef long double real;
typedef pair<int, int> pii;

const int oo = ~0u >> 2;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int mxn = 200033;
inline int read(){
    int x = 0,f = 1;char c = getchar();
    while(!isdigit(c))f = c == '-' ? -1 : 1,c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x * f;
}
int n, m, f[mxn], cnt[mxn];
void init()
{
    for (int i = 1; i <= n; ++ i)
    f[i] = i, cnt[i] = 1;
}
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
void join(int u, int v)
{
    int fu = find(u), fv = find(v);
    if (fu != fv)
    {
        f[fu] = f[fv]; 
        cnt[fv] += cnt[fu];
    }
}
int main()
{
    syio;
    cin>>n>>m;
    init();
    int a, b;
    while (m --)
    {
        cin>>a>>b;
        join(a, b);
    }
    int mx = 0;
    for (int i = 1; i <= n; ++ i)
    if (find(i) == i) mx = max(mx, cnt[i]);
    cout<<mx<<endl;
    return 0;
}


Measured memory_bytes: 11428
#include <iostream>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	int mn = 105;
	int res = 0;
	if (N >= mn) {
		++res;
		for (int i = mn+2; i < N+1; i+=2) {
			int nd = 2;
			for (int j = 3; j < i; j+=2) {
				if (i%j == 0) {
					++nd;
				}
			}
			if (nd == 8) {
				++res;
			}
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(int X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end() 
#define CERR if(false) cerr

using namespace std;

int main(){

    int n,m;
    cin >> n >> m;

    vector<vector<pair<int, ll>>> v;
    vector<pair<int, ll>> tmpv;

    rep(i,n + 1){
        v.pback(tmpv);
    }

    rep(i,m){
        int l,r,d;
        cin >> l >> r >> d;

        v[l].pback(mpair(r, d));
        v[r].pback(mpair(l, -1 * d));
    }

    vector<bool> traversed(n + 1, false);
    vector<ll>   dist(n + 1, 0);
    bool ans = true;

    for(int i = 1; i <= n; i++){

        if(!traversed[i]){
            queue<pair<int,ll>> q;
            traversed[i] = true;

            rep(j, v[i].size()){
                q.push(mpair(v[i][j].first, v[i][j].second));
            }

            while(!q.empty()){

                int index = q.front().first;
                int tmpd = q.front().second;

                if(traversed[index]){

                    if(tmpd != dist[index]){
                        ans = false;
                        break;
                    }

                }else{
                    traversed[index] = true;
                    dist[index] = tmpd;

                    rep(j, v[index].size()){
                        q.push(mpair(v[index][j].first, v[index][j].second + tmpd));
                    }
                }

                q.pop();

            }

        }

        if(!ans) break;
    }

    cout << (ans ? "Yes" : "No") << endl;
    return 0; 
}

Measured memory_bytes: 17776
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100000 + 1000;
int N;
struct node
{
	int val, id;
}A[Maxn];
inline int cmp (node a, node b)
{
	return a.val < b.val;
}
inline int cmp1 (node a, node b)
{
	return a.id < b.id;
}
int main()
{
#ifdef hk_cnyali
	freopen("C.in", "r", stdin);
	freopen("C.out", "w", stdout);
#endif
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i].val), A[i].id = i;
	sort(A + 1, A + N + 1, cmp);
	for (int i = 1; i <= N; ++i) A[i].val = i;
	sort(A + 1, A + N + 1, cmp1);
	int Ans = 0;
	for (int i = 1; i <= N; ++i)
		if (((i & 1) && !(A[i].val & 1)) || (!(i & 1) && (A[i].val & 1)))
			++Ans;
	Ans /= 2;
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }




void solve() {
    int k, x;
    cin >> k >> x;
    cout << ((500 * k >= x) ? "Yes" : "No") << endl;
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int T;
    // cin >> T;
    T = 1;
    
    while (T--) {
        solve();
    }
}




Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
using namespace std;
int n,t,ans,q;
long long a[10001];
int main()
{
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		if (a[i]%2==1) t++;
	}
	if (t==n)
	{
		cout<<"0";
		//system("pause");
    	return 0;
	}
	for (int i=1; ;i++)
	{
		q=1;
		for (int j=0;j<n;j++)
		{
			if (a[j]%2==0 && q==1) {a[j]/=2,q=0; break;}
			else if (a[j]%2==0) a[j]*=3;
		}
		if (q==1) break;
		else ans++;
	}
	cout<<ans;
	//system("pause");
    return 0;
}

Measured memory_bytes: 384
const main = (input) =>  {
    const n = parseInt(input,10)
    const lst = Array.from({length:10},(v,k) => k)
    
    const kuku = []
    lst.map(i => {
        for(var j = 1;j<10;j++) {
            kuku.push(i*lst[j])
        }
    })
    
    if (kuku.indexOf(n) !== -1) {
        console.log("Yes")
    }else{
        console.log("No")
    }
}

const input = require("fs").readFileSync("/dev/stdin","utf8").split("\n")[0]
main(input)

Measured memory_bytes: 7372
#include<stdio.h>
#define MAX 2000000
int H,A[MAX+1];
void maxHeapify(int i){
  int l,r,largest,c;
  l = 2*i;
  r = 2*i+1;
  if(l <= H && A[l] > A[i])largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r;
  if(largest != i){
    c=A[i];
    A[i]=A[largest];
    A[largest]=c;
    maxHeapify(largest);
  }
}

int main(){
  int i;
  scanf("%d",&H);
  for(i=1;i<=H;i++){
    scanf("%d",&A[i]);
  }
  for(i=H/2;i>=1;i--)maxHeapify(i);
  for(i=1;i<=H;i++){
    printf(" %d",A[i]);
  }
  printf("\n");
  return 0;
}



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

int main() {
  int n; cin >> n; int d[n];
  for(int i=0; i<n; i++) {
    cin >> d[i];
  }
  int an = 0;
  for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
      an += d[i] * d[j];
    }
  }
  cout << an << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a,n1=0,n=0,k=0;
    
    scanf("%d",&a);
    
    n1=a;
    while(n1!=0)
    {
        n=n1%10;
        if(n==2)
        {
            k++;
        }
        n1=n1/10;
    }
    printf("%d",k);

    return 0;
}


Measured memory_bytes: 128
N = int(input())
A = list(map(int, input().split()))
c = 0
A = [0] + A + [0]
for i in range(N + 1):
  c += abs(A[i + 1] - A[i])

for i in range(1, N + 1):
  d = abs(A[i + 1] - A[i - 1]) - abs(A[i] - A[i - 1]) - abs(A[i + 1] - A[i])
  print(c + d)



Measured memory_bytes: 65516
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#define pi 3.14159265358979323846264338327950

int main() {
	std::vector<std::vector<int>> A(3, std::vector<int>(3));
	std::vector<std::vector<int>> BOOL(3, std::vector<int>(3));
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			std::cin >> A[i][j];
	int N; std::cin >> N;
	std::vector<int> B(N);
	for (auto& r : B) std::cin >> r;
	for (int n = 0; n < N; ++n) {
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j) {
				if (B[n] == A[i][j])
					BOOL[i][j] = 1;
			}
	}
	if((BOOL[0][0] == 1 && BOOL[0][1] == 1 && BOOL[0][2] == 1)
		|| (BOOL[1][0] == 1 && BOOL[1][1] == 1 && BOOL[1][2] == 1)
		|| (BOOL[2][0] == 1 && BOOL[2][1] == 1 && BOOL[2][2] == 1)
		|| (BOOL[0][0] == 1 && BOOL[1][0] == 1 && BOOL[2][0] == 1)
		|| (BOOL[0][1] == 1 && BOOL[1][1] == 1 && BOOL[2][1] == 1)
		|| (BOOL[0][2] == 1 && BOOL[1][2] == 1 && BOOL[2][2] == 1)
		|| (BOOL[0][0] == 1 && BOOL[1][1] == 1 && BOOL[2][2] == 1)
		|| (BOOL[2][0] == 1 && BOOL[1][1] == 1 && BOOL[0][2] == 1))
		std::cout << "Yes" << std::endl;
	else
		std::cout << "No" << std::endl;
	return 0;
}

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

long long N;
long long x;
long long a[100010];

int main()
{
    cin >> N;
    cin >> x;
    for(long long i = 1;i <= N;i++)
    {
        cin >> a[i];
    }

    long long result = 0;

    for(long long i = 1;i <= N;i++)
    {
        long long sum = a[i - 1] + a[i];

        long long r = max(0LL,min(a[i],sum - x));

        a[i] -= r;
        sum -= r;

        result += r;

        if(sum > x)
        {
            long long l = max(0LL,sum - x);
            a[i - 1] -= l;

            result += l;
        }
    }

    cout << result << endl;
    return 0;
}

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

using namespace std;

const int N = 1e5 + 20;
int a[N][4], dp[N][4];

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

	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}
	dp[0][0] = a[0][0], dp[0][1] = a[0][1], dp[0][2] = a[0][2];
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < 3; j++) {
			if(j == 0) {
				dp[i][j] = max(a[i][j] + dp[i - 1][1], a[i][j] + dp[i - 1][2]);
			} else if(j == 1) {	
				dp[i][j] = max(a[i][j] + dp[i - 1][0], a[i][j] + dp[i - 1][2]);			
			} else {	
				dp[i][j] = max(a[i][j] + dp[i - 1][0], a[i][j] + dp[i - 1][1]);
			}
		}
	}
	cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << "\n";

	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define re return
#define ll long long
#define ld long double
#define f first
#define s second
#define pi acos(-1)
#define oo (int)1e9
#define OO (ll)1e18
#define EPS 1e-7
#define FX(n) fixed<<setprecision(n)
#define mm(o,k) memset(o,k,sizeof o)
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int maxn=105;

int main()
{
    IO;
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i)
        cin >> a[i];
    sort(a.rbegin(),a.rend());
    int ans=0;
    for(int i=0;i<n;++i)
        if(i%2)ans-=a[i];
        else ans+=a[i];
    cout<<ans<<endl;
    re 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
const int inf = 1000000000; // 10^9

int main(){
   int a,b;scanf("%d%d",&a,&b);
   int ans=0;
   ans += a-1;
   if(b>=a)ans++;
   printf("%d",ans);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define MAXN 200010
int vs[MAXN];
int balls[MAXN];

int main(){
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; ++i) 
		scanf("%d", &vs[i]);

	int w = 0;
	for(int i=n; i>0; --i){
		int x = 0;
		for(int j=i+i; j<=n; j+=i)
			x+=balls[j];
		if(x%2!=vs[i]) balls[i] = 1, ++w;
	}
	cout << w << endl;
	for(int i=1; i<=n; ++i){
		if(balls[i])
			cout << i << (--w == 0 ? '\n':' ');
	}
}


Measured memory_bytes: 2432
package main

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

var sc = bufio.NewScanner(os.Stdin)


func next() int {
  sc.Scan()
  text, err := strconv.Atoi(sc.Text())
  if err != nil {
    panic(err)
  }
  return text
}

func main() {
  sc.Split(bufio.ScanWords)
  h := next()
  n := next()
  maxAttackPoint := 0

  for i := 0; i < n; i++ {
    maxAttackPoint += next()
  }
  
  if h <= maxAttackPoint {
    fmt.Println("Yes")
  } else {
    fmt.Println("No")
  }
}

Measured memory_bytes: 1152
#include "bits/stdc++.h"
using namespace std;
const int N = 105;
int n;
int arr[N];
void rekt(){
    cout << "Impossible\n";
    exit(0);
}
void notrekt(){
    cout << "Possible\n";
    exit(0);
}
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> arr[i];
    }
    if(n == 2){
        notrekt();
    }
    sort(arr + 1 , arr + 1 + n);
    int diam = arr[n];
    int cent = arr[n] + 1 >> 1;
    if(arr[1] != cent){
        rekt();
    }
    map < int , bool > mp;
    mp.clear();
    int start;
    if(diam & 1){
        if(arr[2] != cent){
            rekt();
        }
        if(arr[3] == cent){
            rekt();
        }
        start = 3;
        for(int i = 2 ; i <= n ; ++i){
            mp[arr[i]] = 1;
        }
    }
    else{
        if(arr[2] == cent){
            rekt();
        }
        start = 2;
        for(int i = 1 ; i <= n ; ++i){
            mp[arr[i]] = 1;
        }
    }
    for(int i = start ; i <= n ; ++i){
        if(mp.find(arr[i] - 1) == mp.end()){
            rekt();
        }
    }
    notrekt();
}

Measured memory_bytes: 384
N = int(input())

first_idx = 1
last_idx = 26
cnt = 1
while N > last_idx:
    first_idx = last_idx + 1
    last_idx = 26 * (1 + last_idx)
    cnt += 1
# print("1st = {}, last = {}, dgt = {}".format(first_idx, last_idx, cnt))

idx = N - first_idx
# print("index = ", idx)
ans = ""
for i in range(cnt):
    rem = idx % 26
    idx = idx // 26
    ans = chr(97 + rem) + ans

print(ans)


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

int main() {
  vector<int> v(3);
  rep(i,3)cin>>v[i];
  sort(v.begin(),v.end());
  int x = v[2]-v[0];
  int y = v[2]-v[1];
  int sum;
  if(x%2==0&&y%2==0)sum = x/2 + y/2;
  else if(x%2!=0&&y%2!=0)sum = x/2 + y/2 + 1;
  else sum = x/2 + y/2 + 2;
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
n, x, m = map(int, input().split())
idx = [-1] * m
a = []
leng = 0
tot = 0

while idx[x] == -1:
    a.append(x)
    idx[x] = leng
    leng += 1
    tot += x
    x = (x*x)%m

c = leng - idx[x]
s = 0
for i in range(idx[x], leng):
    s += a[i]

ans = 0
if n<=leng:
    for i in range(n):
        ans += a[i]
else:
    ans += tot
    n -= leng
    ans += s*(n//c)
    n %= c
    for i in range(n):
        ans += a[idx[x]+i]

print(ans)


Measured memory_bytes: 13320
#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

const double EPS = 1e-10;
bool equals(double a, double b){ return (fabs(a) - fabs(b)) < EPS;};

class Point{
public:
	double x, y;
	
	Point(double x = 0, double y = 0): x(x), y(y) {}
	Point(const Point &p) { x = p.x; y = p.y;};
	
	Point operator + (const Point &p) { return Point(x + p.x, y + p.y); }
	Point operator - (const Point &p) { return Point(x - p.x, y - p.y); }
	Point operator * (const double &a) { return Point(x * a, y * a); }
	Point operator / (const double &a) { return Point(x / a, y / a); }
	
	Point & operator = (const Point& p) {x = p.x; y = p.y; return *this;};
	Point & operator += (const Point& p) {x += p.x; y += p.y; return *this;};
	Point & operator -= (const Point& p) {x -= p.x; y -= p.y; return *this;};
	Point & operator *= (const Point& p) {x *= p.x; y *= p.y; return *this;};
	Point & operator /= (const Point& p) {x /= p.x; y /= p.y; return *this;};
	
	bool operator < (const Point &p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
	
	bool operator > (const Point &p) const {
		return x != p.x ? x > p.x : y > p.y;
	}
	
	bool operator == (const Point &p) const {
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
	
	double abs() { return sqrt(norm()); };
	double norm() { return x * x + y * y;};
};

typedef Point Vector;


double norm(Vector a){
	return a.x * a.x + a.y * a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

double dot(Vector a, Vector b){
	return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b){
	return a.x * b.y - a.y * b.x;
}

struct Segment{
	Point p1, p2;
};

typedef Segment Line;


bool isOrthogonal(Vector a, Vector b){
	return equals(dot(a,b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2){
	return isOrthogonal(a1 - a2, b1 - b2);
}

bool isOrthogonal(Segment s1, Segment s2){
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}


bool isParallel(Vector a, Vector b){
	return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2){
	return isParallel(a1 - a2, b1 - b2);
}

bool isPrallel(Segment s1, Segment s2){
	return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}


Point project(Segment s, Point p){
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / norm(base);
	return s.p1 + base * r;
}

Point reflect(Segment s, Point p){
	return p + (project(s, p) - p) * 2.0;
}

class Circle {
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0): c(c), r(r) {}
};

typedef vector<Point> Polygon;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int q;
	Segment s;
	
	
	cin>>s.p1.x>>s.p1.y>>s.p2.x>>s.p2.y;
	
	cin>>q;
	
	for(int i = 0; i < q; i++){
		Point p, ans;
		
		cin>>p.x>>p.y;
		
		ans = reflect(s, p);
		
		cout<<ans.x<<" "<<ans.y<<endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 3288
N = int(input())
l = [-1 for i in range(N)]
for i in range(N):
  A = int(input())
  ok = N-1
  ng = -1
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if l[mid] < A:
      ok = mid
    else:
      ng = mid  
  l[ok] = A
###
for i in range(N):
  if l[i] == -1:
    ans = i
    break
  #出会わなかったパターンを忘れ気味
  if i == N-1:
    ans = N  
print(ans)    

Measured memory_bytes: 7032
//omajinai
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//omajinai

int main(){

    // omajinai
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    // omajinai

    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0;i < n;i ++){
        cin >> a.at(i);
    }

    int ans = (n-1) / (k-1);
    if((n-1) % (k-1) != 0){
        ans ++;
    }

    cout << ans << endl;

}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

int main(){
	string s;
	cin >>s;
	int l=0,r=0,ans=0;
	while(l<s.size()){
		if (s[r]=='A' || s[r]=='C' || s[r]=='G' || s[r]=='T'){
			r++;
		}
		else{
			ans=max(ans,r-l);
			r++;
			l=r;
		}
	}
	cout <<ans<<endl;
}

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

int main() {
    ll n;
    cin >> n;
    ll dp[n][3] = {};
    for(int i = 0; i<n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        if(i == 0) {
            dp[i][0] = a;
            dp[i][1] = b;
            dp[i][2] = c;
        }
        else {
            dp[i][0] = a + max(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = b + max(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = c + max(dp[i-1][0], dp[i-1][1]);
        }
    }
    cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
}

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

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;

typedef long long int ll;

void solve(){
	int N;
	cin >> N;
	vector<double> p(N);
	for(int i = 0; i < N; i++) cin >> p[i];
	
	vector<vector<double> > dp(N+1,vector<double>(N+1,0.0));
	dp[0][0] = 1.0;
	
	double pr = 1.0;
	for(int i = 1; i <= N; i++){
		pr *= (1.0-p[i-1]);
		dp[0][i] = pr;
	}
	
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			dp[i][j] = dp[i][j-1]*(1.0-p[j-1]) + dp[i-1][j-1]*p[j-1];
			//cout << dp[i][j] << " ";
		}
		//cout << endl;
	}
//	for(int i = 0; i <= N; i++){
//		for(int j = 0; j <= N; j++){
//			cout << dp[i][j] << " ";
//		}
//		cout << endl;
//	}
	double ans = 0;
	for(int i = (N/2)+1; i <= N; i++) ans += dp[i][N];
	cout << setprecision(10) << ans << endl;
}

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

	int T;
	//cin >> T;
	T = 1;
	while(T--){
		solve();
	}
	return 0;
}




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

#define rep(i, n) for(int (i) = 0; i < (n); ++(i))

typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
  int a;
  std::string s;
  std::cin >> a >> s;

  std::cout << (a >= 3200 ? s : "red") << '\n';
}


Measured memory_bytes: 256
H, N = map(int, input().split())

A = []
B = []

for _ in range(N):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)

X = []

for i in range(H):
	Y = []
	for j in range(N):
		if i+1 <= A[j]:
			Y.append(B[j])
		else:
			Y.append(X[i-A[j]] + B[j])
	
	X.append(min(Y))

print(X[H-1])

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

int main(){
    string S, T;
    cin >> S >> T;
    if(S.size() + 1  != T.size()){
        cout << "No" << endl;
        return 0;
    }
    T.erase(T.size()-1);
    if(S == T) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3600
from itertools import accumulate,chain,product
N,K = map(int,input().split())

V = tuple(map(int,input().split()))

av = tuple(chain((0,),accumulate(V)))


def left():
    for i in range(N+1):
        tmp = sorted(min(0, v) for v in V[:i])
        yield tuple(chain((0,), accumulate(tmp)))

left_cost = tuple(left())


def right():
    for i in reversed(range(N+1)):
        tmp = sorted(min(0, v) for v in V[i:])
        yield tuple(chain((0,), accumulate(tmp)))

right_cost = tuple(right())

def helper():
    for i in range(N+1):
        for j in range(N-i+1):
            d = K - i - j
            if d < 0:
                continue
            rev = av[i]+(av[N]-av[N-j])
            l,r = left_cost[i], right_cost[j]
            for k in range(d+1):
                yield rev - l[min(i,k)] - r[min(j,d-k)]
print(max(helper()))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
#define itn int
#define all(c) c.begin(),c.end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
#define ll long long
#define pll pair<ll, ll>
#define mp(x, y) make_pair(x, y)
using namespace std;

const ll N = 3e5 + 5, inf = 1e18, mod = 1e9 + 7;
const double PI = 3.1415926536;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_prime(ll n) {
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

vector<pll> fact(ll n) {
    n = abs(n);
    ll t = 0;
    vector<pll> ans;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            pll cur = {i, 0};
            while (n % i == 0) {
                cur.second++;
                n /= i;
            }
            ans.push_back(cur);
        }
    }
    if (n > 1) {
        ans.push_back({n, 1});
    }
    return ans;
}

inline ll getPow(ll a,ll b) {
    ll res = 1ll, tp = a;
    while (b){
       if (b&1ll) {
           res *= tp;
       }
       tp *= tp;
       //tp %= mod; res %= mod;
       b >>= 1ll;
    }
    return res;
}

ll vec_mult(const pll & t1, const pll & t2, const pll & t3) {
   const ll & x1 = t1.first, y1 = t1.second;
   const ll & x2 = t2.first, y2 = t2.second;
   const ll & x3 = t3.first, y3 = t3.second;
   return abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
}

void ok() {
   cout << "YES" << endl;
   exit(0);
}

void no() {
   cout << "NO" << endl;
   exit(0);
}

inline ll nxt() {
    ll x;
    cin >> x;
    return x;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n = nxt(), k = nxt();
    vector<ll> mas(n);
    for (int i = 0; i < n; i++) {
        mas[i] = nxt();
    }
    vector<ll> dp(n, inf);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j > i) break;
            dp[i] = min(dp[i], abs(mas[i] - mas[i - j]) + dp[i - j]);
        }
    }
    cout << dp[n - 1];
    return 0;
}


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

using namespace std;

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<lli, int> pi;

lli lcm(lli a, lli b) {return (a*b)/__gcd(a, b);}

int main()
{
    int n;
    cin >> n;
    map<int, int> mp;
    while(n--){
        int x;
        cin >> x;
        mp[x]++;
    }
    if(mp.size() == 1 && mp.begin()->first == 0){
        printf("Yes\n");
        return 0;
    }
    auto xx = mp.begin();
    auto y = mp.begin();
    y++;
    if(mp.size() == 2 && xx->second*2 == y->second && xx->first == 0){
        printf("Yes\n");
        return 0;
    }
    bool fl = mp.size()==3;

    int x = mp.begin()->second;
    for(auto it: mp){
        if(it.second != x){
            fl = false;
        }
    }

    if(mp.size() == 3){
        auto it = mp.begin();
        x = it->first;
        it++;
        int y = it->first;
        it++;
        int z = it->first;
        x = x^y;
        if(x != z){
            fl = false;
        }
    }
    cout << (fl? "Yes\n": "No\n");

    return 0;
}


Measured memory_bytes: 3840
import sys
N,A,B = map(int,input().split())
array = list(map(int,input().split()))

if not ( 2 <= N <= 10**5 and 1 <= A <= 10**9 and 1 <= B <= 10**9 ): sys.exit()
for I in range(len(array)):
    if not ( 1 <= array[I] <= 10**9 ): sys.exit()
    if array[I] != array[-1]:
       if not ( array[I] < array[I+1] ): sys.exit()

cost = 0
for J in range(len(array)):
    if array[J] != array[-1]:
        walk_cost = (array[J+1] - array[J])*A
        if walk_cost < B:
            cost += walk_cost
        else:
            cost += B
print(cost) 

Measured memory_bytes: 20352
#include <cstdio>
#include <cstring>

using namespace std;

int main(void)
{
    char s[101], t[101];
    scanf("%s%s", s, t);

    int n = strlen(s);
    int tl = n;
    while (tl--) {
        int f = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != t[i]) {
                f = 1;
                break;
            }
        }
        if (f) {
            char tmp = s[n-1];
            for (int j = n-1; j >= 1; j--) {
            s[j] = s[j-1];
            }
            s[0] = tmp;
        }
        else {
            puts("Yes");
            return 0;
        }
    }
    puts("No");
    return 0;
}

Measured memory_bytes: 888
type Scanner() = class
    let mutable hold = [||]
    let mutable index = 0
    member public this.Next() =
        if hold.Length > index
        then 
            index <- index + 1
            hold.[index - 1]
        else
            let mutable st = stdin.ReadLine()
            while st = "" do st <- stdin.ReadLine()
            hold <- st.Split(' ')
            if hold.Length = 0
            then
                this.Next()
            else
                index <- 1
                hold.[index - 1]
            
    member public this.NextI32() =
        this.Next() |> int

    member public this.ArrayI32(n: int) =
        [for _ in 0 .. n - 1 -> this.NextI32()]

    member public this.NextI64() =
        this.Next() |> int64
    
    member public this.ArrayI64(n: int) =
        [for _ in 0 .. n - 1 -> this.NextI64()]

    member public this.NextF32() =
        this.Next() |> float32
    
    member public this.ArrayF32(n: int) =
        [for _ in 0 .. n - 1 -> this.NextF32()]

    member public this.NextF64() =
        this.Next() |> double
    
    member public this.ArrayF64(n: int) =
        [for _ in 0 .. n - 1 -> this.NextF64()]
end

[<EntryPoint>]
let main args =
    let rec atoz flg list = 
        flg |> function 
        | true -> list |> function
            | head :: _ when head = 'A' -> List.rev list |> atoz false
            | _ :: tail -> atoz true tail
            | [] -> 0
        | false -> list |> function
            | head :: _ when head = 'Z' -> list.Length
            | _ :: tail -> atoz false tail
            | [] -> 0
    let s = Scanner().Next() |> Seq.toList
    
    atoz true s |> printfn "%i"
    0


Measured memory_bytes: 32080