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

using namespace std;

using ll = long long;

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

struct RangeMaximumQuery {
  using type = int;
  static type id() { return 0; }
  static type op(const type &l, const type &r) { return std::max(l, r); }
};

template <typename M>
class SegmentTree {
  using T = typename M::type;
  int n;
  std::vector<T> node;

 public:
  // Monoid::id 初期化
  SegmentTree(int _n) {
    n = 1;
    while (n < _n) n *= 2;
    node.resize(2 * n, M::id());
  }
  // x 番目を val に更新
  void update(int x, T val) {
    x += n;
    node[x] = val;
    while (x >>= 1) {
      node[x] = M::op(node[2 * x], node[2 * x + 1]);
    }
  }
  // [a, b) の op
  T query(int l, int r) {
    l += n;
    r += n;
    T retl = M::id(), retr = M::id();
    while (l < r) {
      if (l & 1) retl = M::op(retl, node[l++]);
      if (r & 1) retr = M::op(node[--r], retr);
      l >>= 1;
      r >>= 1;
    }
    return M::op(retl, retr);
  }
};

template <typename T>
void coordinateCompression(std::vector<T> &a) {
  int N = a.size();
  std::vector<T> xs = a;
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < N; i++) {
    a[i] = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
  }
}

const int MAX_N = 200010;
vector<vector<int>> g(MAX_N);
vector<ll> a(MAX_N, 0);
SegmentTree<RangeMaximumQuery> seg(MAX_N);
vector<int> ret(MAX_N);

void dfs(int cur, int pre) {
  auto now = seg.query(a[cur], a[cur] + 1);
  auto ma = seg.query(0, a[cur]);
  seg.update(a[cur], max({1, now, ma + 1}));
  ret[cur] = seg.query(0, MAX_N - 5);
  for (auto nxt : g[cur]) {
    if (nxt == pre) continue;
    dfs(nxt, cur);
  }
  seg.update(a[cur], now);
}

const int MIN_A = 1;
const int MAX_A = 1000000000;

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

  int n;
  cin >> n;
  assert(2 <= n && n <= MAX_N - 10);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    assert(MIN_A <= a[i] && a[i] <= MAX_A);
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    assert(u != v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  coordinateCompression(a);
  dfs(0, -1);
  for (int i = 0; i < n; i++) {
    cout << ret[i] << '\n';
  }
  // printv(a);
}


Measured memory_bytes: 35720
#include <map>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <tr1/unordered_map>
#define num(x) (x>='0' && x<='9')
typedef unsigned long long ull;
typedef long long ll;
using namespace std::tr1;
using namespace std;
int read(){
    int p=0, q=1;
    char ch=getchar();
    while (!num(ch))
        (ch=='-'?q=-1:0),
        ch=getchar();
    while (num(ch)) p=p*10+ch-'0', ch=getchar();
    return p*q;
}
#define N 55
#define M 25
#define ND 60000000
#define EDGE 90000000
int n, l[N], c[N], pre[N];
char s[N][M], res[N][M];
int nex[EDGE], nu[EDGE];
ll dist[ND], va[EDGE];
bool flag[ND];
int st, cnt;
ll INF=1ll*1999999999*1999999999;
struct node{
	int n;
	ll dist;
	node (int n, ll dist): n(n), dist(dist){}
	bool operator <(const node &o) const {return this->dist<o.dist;}
	bool operator >(const node &o) const {return this->dist>o.dist;} 
};
priority_queue<node, vector<node>, greater<node> > q;
void add(int u, int v, int w){
	nex[++cnt]=nex[u];nex[u]=cnt;nu[cnt]=v;va[cnt]=w;
}
void dijkstra(){
	for (int i=1;i<=st;i++) dist[i]=INF, flag[i]=0;
	dist[st]=0;
	q.push(node(st,0));
	while (!q.empty()){
		node curNode=q.top();
		q.pop();
		int u=curNode.n;
		flag[u]=1;
		for (int j=nex[u];j;j=nex[j]){
			int v=nu[j];
			if (!flag[v] && dist[u]+va[j]<dist[v])
				dist[v]=dist[u]+va[j],
				q.push(node(v,dist[v]));
		}
		while (!q.empty() && flag[q.top().n]) q.pop();
	}
}
int main(){
	n=read();
	for (int i=1;i<=n;i++){
		scanf("%s", &s[i]);
		c[i]=read();
		l[i]=strlen(s[i]);
		pre[i]=pre[i-1]+l[i];
		for (int j=0;j<l[i];j++) res[i][j]=s[i][l[i]-1-j];
	}
	#define get(i,j,x,y) (pre[i-1]+j+1)*1010+pre[x-1]+y+1
	ll ans=INF;
	for (int beg=1;beg<=n;beg++){
		st=1005*1010, cnt=st;
		for (int i=1;i<=cnt;i++) nex[i]=0;
		for (int y=1;y<=n;y++)
			if (s[beg][0]==res[y][0])
				add(st,get(beg,0,y,0),c[beg]+c[y]);
		for (int i=1;i<=n;i++)
			for (int k=1;k<=n;k++)
				for (int j=0;j<l[i];j++)
					for (int p=0;p<l[k];p++){
						if (j && j<l[i]-1 && p && p<l[k]-1) continue;
						int u=get(i,j,k,p);
						if (j<l[i]-1 && p<l[k]-1){
							if (s[i][j+1]==res[k][p+1]){
								int tj=j, tp=p;
								while (tj<l[i]-1 && tp<l[k]-1 && s[i][tj+1]==res[k][tp+1]) 
									tj++, tp++;
								add(u,get(i,tj,k,tp),0);
							}
						}
						else if (j<l[i]-1){
							for (int x=1;x<=n;x++)
								if (s[i][j+1]==res[x][0]) 
									add(u,get(i,j+1,x,0),c[x]);
						}
						else if (p<l[k]-1){
							for (int x=1;x<=n;x++)
								if (s[x][0]==res[k][p+1]) 
									add(u,get(x,0,k,p+1),c[x]);
						}
						else{
							for (int x=1;x<=n;x++)
								for (int y=1;y<=n;y++)
									if (s[x][0]==res[y][0])
										add(u,get(x,0,y,0),c[x]+c[y]);
						}
					}
		dijkstra();
		ll res=INF;
		for (int x=1;x<=n;x++)
			res=min(res,dist[get(x,l[x]-1,beg,l[beg]-1)]);
		ans=min(ans,res);
	}
	if (ans==INF) ans=-2;
	cout<<ans/2<<endl;
    return 0;
}

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

using namespace std;

const int mod =1e9+7;

const int nax=2e5+5;

long long int dp[nax];
long long int suma[nax];

int main()
{
    int n; cin>>n;
    vector<int> xxx;
    for(int i=0;i<n;i++)
    {
        int x; cin>>x;
        xxx.push_back(x);
    }
    vector<int> a;
    a.push_back(-666);
    a.push_back(xxx[0]);
    for(int i=1;i<n;i++)
    {
        if(xxx[i]!=a[a.size()-1]) a.push_back(xxx[i]);
    }
    n=a.size();
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        long long int res=suma[a[i]];
        dp[i]=dp[i-1];
        dp[i]+=res;
        dp[i]%=mod;
        suma[a[i]]+=dp[i-1];
        suma[a[i]]%=mod;
    }
    cout<<dp[n];
    return 0;
}


Measured memory_bytes: 5108
N = int(input())
G = [[] for i in range(200)]
U = [0]*200
for i in range(N):
    u, r, v = input().split(); u = int(u)-1; v = int(v)-1
    U[u] = U[v+100] = 1
    if r == 'lock':
        G[u].append(v+100)
    else:
        G[v+100].append(u)

used = [0]*200
hold = [0]*200
def dfs(v):
    if used[v]:
        return 0
    r = 0
    hold[v] = 1
    for w in G[v]:
        if hold[w]:
            r = 1
            continue
        r |= dfs(w)
    hold[v] = 0
    used[v] = 1
    return r
for i in range(200):
    if not U[i]:
        continue
    if dfs(i):
        print(1)
        break
else:
    print(0)



Measured memory_bytes: 5648
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX
#define INFL LLONG_MAX
typedef long long ll;
using namespace std;


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

  std::vector<ll> t(n);
  rep(i,n){
    cin >> t.at(i);
  }
sort(all(t));

ll a=t.at(0),pa=1,bus=0,time;
bool ne=false;
for(auto i=1;i<n;i++){
  if(ne){
    a=t.at(i-1);
    ne=false;
  }


  time=t.at(i)-a;
  pa++;

  if(time>k || pa>c){
    bus++;
    ne=true;
    pa=1;
  }


}

  cout << bus+1 << endl ;


  }


Measured memory_bytes: 4044
def b(al , n , nl):

    ans = "No"

    n = [[False]*3 for i in range(3)]

    for i in range(3):
        for w in range(3):
            if al[i][w] in nl:
                n[i][w] = True
    
    for i in range(3):
        if n[i][0] == True and n[i][1] == True and n[i][2] == True:
            ans = "Yes"
    
    for i in range(3):
        if n[0][i] == True and n[1][i] == True and n[2][i] == True:
            ans = "Yes"
    
    if n[0][0] == True and n[1][1] == True and n[2][2] == True:
        ans = "Yes"
    if n[0][2] == True and n[1][1] == True and n[2][0] == True:
        ans = "Yes"

    return ans

def main():
    al = [list(map(int , input().split())) for i in range(3)]
    n = int(input())
    nl = [int(input()) for i in range(n)]
    print(b(al , n , nl))

if __name__ == '__main__':
    main()


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

int main(void){
  char str[1000];
  scanf("%s", str);
  long i, len;
  len = strlen(str);
  for(i=0;i<len;i++){
    if(str[i] == 'A' && str[++i] == 'C'){
      printf("Yes");
      return 0;
    }
  }
  printf("No");
  return 0;
}

Measured memory_bytes: 128
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

# bit all search
pattern = []
for i in range(2 ** n):
    bit_set = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_set.append(A[j])    
    pattern.append(sum(bit_set))

#print(pattern)  

for m in m:
    if m in pattern:
        print('yes')
    else:
        print('no')



Measured memory_bytes: 43076
using System;
using System.Linq;


public class A
{
    public static void Main(string[] args)
    {
        int t = 1;
        while (t > 0)
        {
            int n = int.Parse(Console.ReadLine());
            var mm = new int[n, n];
            for(int i = 0; i < n; i++)
            {
                int tt = int.Parse(Console.ReadLine());
                for(int j = 0; j < tt; j++)
                {
                    var arr = Console.ReadLine().Trim().Split().Select(x => int.Parse(x)).ToArray();
                    mm[i, arr[0] - 1] = (arr[1] == 1 ? 1 : -1);
                }
            }
            int max = 0;
            for(int i = 0; i <= Math.Pow(2,n); i++)
            {
                int honestCount = 0;
                bool ok = true;
                for(int j = 0; j < n; j++)
                {
                    if(((1 << j) & i) != 0)
                    {
                        honestCount++;
                        for(int k = 0; k < n; k++)
                        {
                            if(mm[j,k] == 1 && ((1 << k) & i) == 0)
                            {
                                ok = false;
                                break;
                            }
                            if(mm[j,k] == -1 && ((1 << k) & i) > 0)
                            {
                                ok = false;
                                break;
                            }
                        }
                    }
                }
                if (ok)
                    max = Math.Max(honestCount, max);
            }
            Console.WriteLine(max);
            t--;
        }
    }
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> PA;
typedef priority_queue<int, vector<int>, greater<int> > PQG;
#define REP(i, a, n) for(ll i = (ll) a;i < (ll) n;i++)
#define fi first
#define se second
#define pb push_back
#define INF 1000000009
#define MOD 1000000007
#define MAXN 56
#define MAXC 100000000000014
#define MAXV 1000000009

int n;
queue<int> que;

int fun(int m){
    for(int i = 2;i <= sqrt(m);i++){
        if(m % i == 0){
            return 0;
        }
    }
    que.push(m);
    return 1;
}

int main()
{
    cin >> n;
    int i = 2;
    while(que.size() < n){
        if(fun(i * 5 + 1))printf("%d ",i * 5 + 1);
        i++;
    }
    printf("\n");

    return 0;
}













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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

//↓0-originか1-originでn回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)      //0-origin昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++)    //1-origin昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-origin降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-origin降順
//rep2 -> 第二引数 m から n 回繰り返し ex) m=5 n=3 なら i=5,i=6,i=7 まで
#define rep2(i,m,n) for(int i = ((int)(m)); i < ((int)(n))+((int)(m)); i++)
#define SIZE(x) ((int)((x).size()))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int,int> PII;
template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

/* 円周率は M_PI を使おうね */
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;

/*FUNCs=================================================*/
vi move1 = {0,0,1,-1};
vi move2 = {1,-1,0,0};

/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    //cout << fixed << setprecision(10);
    
    int n; cin >> n;
    int cnt = 0;
    vector<vector<PII>> xy(n);
    rep(i,n) {
        int a; cin >> a;
        rep(j,a) {
            PII p;
            cin >> p.first >> p.second;
            p.first--;
            xy[i].push_back(p);
        }
    }

    for(int bit = 0; bit < (1<<n); ++bit) {
        bool can = 1;
        for(int i = 0; i < n; ++i) {
            if(!(bit&(1<<i))) continue;
            for(auto p : xy[i]) {
                if(bit&(1<<p.first)) {
                    if(p.second==0) {can=0; break;}
                } 
                else {
                    if(p.second==1) {can=0; break;}
                }
            }
        }
        if(can) {
            int c = 0;
            for(int i = 0; i < n; ++i) {
                if(bit&(1<<i)) c++;
            }
            chmax(cnt, c);
        }
        //debug(bit);
        //debug(cnt);
    }

    cout << cnt << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
long long int gcd(long long int x, long long int y){
  return y!=0 ? gcd(y, x%y) : x;
}
long long int lcm(long long int x, long long int y){
  return x*y/gcd(x, y);
}
int main(){
  int i, j, n, ct=2;
  long long ans=1, con=1000000007;
  cin >> n;
  char s[n+1];
  cin >> s;
  sort(s, s+n);
  for(i=1; i<n; i++){
    if(s[i-1]==s[i]) ct++;
    else{
      ans=ans*ct%con;
      ct=2;
    }
  }
  ans=ans*ct%con-1;
  cout << ans;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
int n,s,x,a[100];
bool c;
int main(){
    scanf("%d",&n);
    rep(i,n){ scanf("%d",&x); a[x]++; s = max(s, x); }
    rep(i,s+1){
        if(i < (s+1)/2){ if(a[i]) c = 1; }
        else if(i == (s+1)/2 && s%2){ if(a[i]-2) c = 1; }
        else if(i == (s+1)/2){ if(a[i]-1) c = 1; }
        else { if(a[i] < 2) c = 1; }
    }
    cout << (c ? "Impossible" : "Possible") << endl;
}

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

// pbds
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
// gp_hash_table<int, int> table;

using namespace std;

#define vec vector
#define ALL(x) begin(x), end(x)

typedef unsigned long long ull;
typedef unsigned int ui;
typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;

const int inf = 1000 * 1000 * 1000;
const ll inf64 = 1e18;

int main() {

#ifdef debug
    freopen("input.txt", "r", stdin);
#endif

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

    ll n, h, w;

    cin >> n >> h >> w;

    cout << (n - h + 1) * (n - w + 1) << "\n";

    return 0;
}


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

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

int main()
{
    long long N, M, X;
    cin >> N >> M >> X;
    vector<long> C(N);
    vector<vector<long long>> A(N, vector<long long>(M));
    rep(i, N){
        cin >> C.at(i);
        rep(j, M){
            cin >> A.at(i).at(j);
        }
    }

    long long ans = __LONG_LONG_MAX__;
    for (int i = 0; i < 2 << N;i++){
        long long money = 0;
        vector<long long> check(M);
        for (int j = 0; j < N;j++){
            if(i & (1 << j)){
                money += C.at(j);
                for (int k = 0; k < M;k++){
                    check.at(k) += A.at(j).at(k);
                }
            }
        }
        bool is_ok = true;
        for (int j = 0; j < M;j++){
            if(check.at(j) < X){
                is_ok = false;
                break;
            }
        }
        if(is_ok){
            if(ans > money && money != 0){
                ans = money;
            }
        }
    }

    if(ans == __LONG_LONG_MAX__){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1e9+10)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))


int main() {
  ll n, k;
  cin >> n >> k;
  ll c = 0;

  for (int i = k; i < n + 2; i++){
    c = c + n + 2 - i;
    c = c + (n+1-i)*(i-1);
    c %= MOD;
  }
  cout << c << endl;

  return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll a[225816];
std::map<ll, ll> mp;

int main(void){
	int n,i;
	ll ans = 0ll;
	std::cin >> n;
	for(i=0; i<n; ++i){
		std::cin >> a[i];
		ans += mp[i-a[i]];
		++mp[a[i]+i];
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 27808
from fractions import gcd
a,b,c,d=map(int,input().split())
startC=(a-1)//c*c+c
startD=(a-1)//d*d+d
n=b-a+1
clength=b-startC
dlength=b-startD
cdnum=0
if clength>=0:
    cdnum+=1+clength//c
if dlength>=0:
    cdnum+=1+dlength//d
cd=c*d//gcd(c,d)
startCD=(a-1)//cd*cd+cd
cdlength=b-startCD
if cdlength>=0:
    cdnum-=1+cdlength//cd
print(n-cdnum)

Measured memory_bytes: 5076
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const int mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

const int V = 100000;
vector<int> graph[200005];
bool visited[200005];
vector<int> cnt(2);

void dfs(int u){
    visited[u] = true;
    ++cnt[u / V];
    for(int v : graph[u]){
        if(visited[v])  continue;
        dfs(v);
    }
}

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

    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        y += V;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    ll res = 0;
    for(int i = 0; i < V * 2; ++i){
        if(visited[i])  continue;
        if(graph[i].size() == 0)    continue;

        cnt[0] = 0, cnt[1] = 0;
        dfs(i);
        res += (ll)cnt[0] * cnt[1];
    }
    res -= n;
    cout << res << endl;
}

Measured memory_bytes: 13560
#include<iostream>
using namespace std;
int main(){
  int n,i,b,count;
  cin >> n;
  int a[n];
  for(i=0;i<n;i++) cin >> a[i];
  b = 1;
  count = 0;
  while(true){
    count += 1;
    b = a[b-1];
    if (count == 200000){
      count = -1;
      break;
    }
    if (b == 2) break;
  }
  cout << count << endl;
}

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

int main() {
  int N,A; //N:支払い額、A:持ってる1円硬貨の枚数
  cin >> N >> A;
  int amari;
  
  amari = N % 500;
  if(amari <= A){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

int main() {
	string s,t;
	bool f = true;
	cin >> s >> t;
	int u = s.size();
	for (int i = 0;i < u;++i) {
		for (int j = 0;j < u;++j) {
			if (s[j] != t[(j+i)%u]) f = false;
		}
		if (f) {
			cout << "Yes" << "\n";
			exit(0);
		}
		f = true;
	}
	cout << "No" << "\n";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int K = sc.nextInt();

		if(A == B){
		    System.out.println(A);
		}else{

		    if(K > B){
			K = B - A;
		    }

		    for(int i = A; i < A + K; i++){
			if(i > B){break;}
			System.out.println(i);
		    }

		    int l = B - A + 1;
		    if (K * 2 > l){
			K = l - K;
		    }
		    
		    for(int j = B - K + 1; j < B + 1; j++){	    
			System.out.println(j);
		    }

		}
	}
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>
int n,a,b,ans;
inline int sg(int a,int b){
	if(a % b == 0) return a / b;
	const int dt = a / b + 1;
	return sg(a - (a % b + dt - 1) / dt * dt,b);
}
int main()
{
	std::ios::sync_with_stdio(false),std::cin.tie(0);
	std::cin >> n;
	for(;n--;) std::cin >> a >> b,ans ^= sg(a,b);
	std::cout << (ans ? "Takahashi" : "Aoki") << '\n';
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp> // Include for built in treap
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//const int MOD = 1e9 + 7;
#define ll long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define eb emplace_back
#define in insert
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define si set<int>
#define mpii map<int, int>
#define prq priority_queue
#define sz(s) (int) s.size()
#define pf(a) printf("%d ",a)
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define si3(a,b,c) scanf("%d%d%d",&a,&b,&c)
//#define scan(v) for(int i = 0; i<n; i++){int x;cin>>x;v.pb(x);}
#define pi 2 * acos (0.0)
#define inf 1e9
#define co cout
#define en '\n'
#define re return
#define con continue
#define dbg cout<<"___________ok____________"<<endl;
#define yes() printf("YES\n");
#define no() puts("NO");
#define FOR(i, j, k) for(int i=(j); i<(k); i++)
#define REV(i, j, k) for(int i=(j-1); i>=k; i--)
#define all(v) v.begin(), v.end()
#define rnd(a, b) ((((rand()<<15)^rand())%((b)-(a) + 1))+(a))
#define FAST_IO ios_base::sync_with_stdio(false),cin.tie(NULL)
#define mem(x, y) memset(x, y, sizeof(x))
#define prn(v) for(auto x: v)cout<<x<<" ";
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pb_ds;
const double EPS = 1e-9;
const int MXX = 1e5 + 5;

bool vis[MXX];
int main()
{

    FAST_IO;
    int n, m;
    cin>>n>>m;
    int a = 0, p = 0;
    map<int, int>mp;
    FOR(i, 0, m)
    {
        int x;
        cin>>x;
        string s;
        cin>>s;
        if(s == "WA")
        {
            if(!vis[x])
            {
                //p++;
                mp[x]++;
            }
        }
        else
        {
            if(vis[x])con;
            vis[x] = true;
            p+=mp[x];
            a++;
        }
    }
    co<<a<<" "<<p<<en;
    return 0;
}


Measured memory_bytes: 4992
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#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 mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  string S, T;
  cin>>S>>T;
  for(int i=0;i<2*N;++i) {
    if(i%2==0) cout<<S[i/2];
    else cout<<T[(i-1)/2];
  }
  cout<<endl;
}



Measured memory_bytes: 3628
A,B,C = map(int,input().split())
b_5 = 0
b_7 = 0
if A == 5:
  b_5 += 1
elif A == 7:
  b_7 += 1
if B == 5:
  b_5 +=1
elif B==7:
  b_7 += 1
if C==5:
  b_5 +=1
elif C==7:
  b_7 += 1

if b_5 == 2 and b_7 == 1:
  print("YES")
else:
  print("NO")

Measured memory_bytes: 61968
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;

signed main(){
  lint N, K; cin >> N >> K;
  vector<lint> a(N);
  for(int i = 0; i < N; i++) cin >> a[i];
  vector<vector<lint> > dp(50, vector<lint> (2, -1));
  dp[40][0] = 0;
  for(lint d = 39; d >= 0; d--){
    lint mask = (1LL << d), num = 0;
    for(lint i = 0; i < N; i++) if(mask & a[i]) num++;
    if(dp[d + 1][1] != -1) dp[d][1] = max(dp[d][1], dp[d + 1][1] + mask * max(num, N - num));
    if(dp[d + 1][0] != -1){
      if(K & mask){
        dp[d][1] = max(dp[d][1], dp[d + 1][0] + mask * num);
        dp[d][0] = max(dp[d][0], dp[d + 1][0] + mask * (N - num));
      }
      else{
        dp[d][0] = max(dp[d][0], dp[d + 1][0] + mask * num);
      }
    }
  }
  cout << max(dp[0][0], dp[0][1]) << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int w[n];
  for(int i=0; i<n; i++) {
    cin >> w[i];
  }
  int min = 0;
  
  for(int i=0; i<n; i++) {
    int s1 = 0;
    int s2 = 0;
    int sub;
    for(int j=0; j<=i; j++) {
      s1 += w[j];
    }
    for(int k=1; i+k<n; k++) {
      s2 += w[i+k];
    }
    sub = abs(s1 - s2);
    if(i==0) {
      min = sub;
    }
    else {
      if(min > sub) {
        min = sub;
      }
    }  
  }
  cout << min << endl;
}

Measured memory_bytes: 256
// finish date: 2018/07/25
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


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

    FOR(i, 1, N + 1) {
        if (i * (i + 1)/2 >= N) {
            int diff = i*(i+1)/2-N;
            FOR(j,1,i+1){
                if(j!=diff){
                    cout<<j<<endl;
                }
            }
            return 0;
        }
    }


    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char ch[100];
int a,b;
int main()
{
	gets(ch);
	for(int i=0;i<strlen(ch);i++)
	{
		if(ch[i]=='C') a=1;
		if(ch[i]=='F'&&a==1) b=1;
	}
	if(b) cout<<"Yes";
	else cout<<"No";
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <tuple>
#include <string.h>
#include <map>
#include <iomanip>
#include <time.h>
#include <complex>
using namespace std;
typedef long long ll;
#define _ << " " <<
#define all(X) (X).begin(), (X).end()
#define len(X) (X).size()
#define Pii pair<int, int>
#define Pll pair<ll, ll>

int main() {
    ll x, y;
    cin >> x >> y;

    if (abs(x - y) <= 1) {
        cout << "Brown" << endl;
    }
    else cout << "Alice" << endl;

}


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

signed main() {
  int N;
  cin >> N;
  static int s[101010];
  for (int i = 0; i < N - 1; i++) cin >> s[i];

  int ans = 0;
  for (int d = 1; d < N; d++) {
    int sum = 0;
    int L = 0, R = N - 1;

    //割り切れるとき、ＬとＲは途中で等しくなる。等しくなったときに足すのをやめる。
    if ((N - 1) % d == 0) {
      while (L < R) {
        sum += s[L] + s[R];
        L += d;
        R -= d;
        ans = max(ans, sum);
      }

      //割り切れないとき、ＬとＲは全て異なる。Ｌ+dがＮ－１を越えない範囲で足し続ける。
      //L==N-1を含めないことに注意。含めてしまうとＲ＝Ｎ－１と同じマスを踏むことになる。
    } else {
      while (L + d < N - 1) {
        sum += s[L] + s[R];
        L += d;
        R -= d;
        ans = max(ans, sum);
      }
    }
  }

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


Measured memory_bytes: 1152
import java.util.*;

public class Main {
    public static void main(String[] args){
        HashMap <String, Boolean> dict = new HashMap <String, Boolean>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i<n; i++){
            String dir = sc.next();
            if(dir.equals("insert")){
                String S = sc.next();
                dict.put(S, true);
            }else{
                String S = sc.next();
                if(dict.containsKey(S)){
                    System.out.printf("yes\n");
                }else{
                    System.out.printf("no\n");
                }
            }
        }
        sc.close();
    }
}


Measured memory_bytes: 335128
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main(){
    int R[MAX], n;
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> R[i];
    
    int maxv = R[1] - R[0];
    int minv = R[0];
    
    for(int i = 1; i < n; i++){
        maxv = max(maxv, R[i] - minv);
        minv = min(minv, R[i]);
    }
    cout << maxv << endl;
    return 0;
}


Measured memory_bytes: 3864
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define MOD 1000000007ULL;
#define rep(i,n) for(int i=0;i<n;i++)


int main() {
	int H,W,K;
  	cin>>H>>W>>K;
  	int count=0;
  	int ans=0;
  	char c[H][W];
  	char C[H][W];
  
  	rep(i,H){
     	rep(j,W){
         	 cin>>c[i][j];
        }
    }
  
  	for(int hbit=0;hbit<(1<<H);++hbit){
     	for(int wbit=0;wbit<(1<<W);++wbit){
          	count=0;
          	rep(i,H){
             	rep(j,W){
                 	C[i][j]=c[i][j];
                }
            }
          
          
        	rep(i,H){
             	if(hbit & (1<<i)){
                 	 rep(j,W){
                      	C[i][j]='.';
                     }
                }
            }
          	
          	rep(j,W){
             	if(wbit & (1<<j)){
                 	rep(i,H){
                     	C[i][j]='.';
                    }
                }
            }
         	
          	rep(i,H){
             	rep(j,W){
                 	if(C[i][j]=='#') count++;
                }
            }
          	if(count==K) ans++;
          
        }
    }
  
  	cout<<ans<<endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;
long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
const int MAXN=10000002;
int main(){
    ll N;cin >> N;
    ll ans = 0;
    Rep(i,N){
        ll num = N/i;
        ll first = i;
        ll last = i * num;
        ans += ((first + last)*num) / 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
//priority_queue<long long, vector<long long>, greater<long long>> pq;

const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long

const int inf = 1e9;
int n;
string s;
int a[1000005], c[1000005];
 
int main() {
  //auto start_clock = clock();
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d", &n);
  cin >> s;

  c[0] = c[1] = 0;
  for(int i = 2; i <= 1000000; i++) {
    int x = 0, y = i;
    while(y % 2 == 0) {
      x += 1;
      y /= 2;
    }
    c[i] = c[i - 1] + x;
  }


  int c0 = 0, c1 = 0, c2 = 0;
  for(int i = 0; i < n - 1; i++) {
    a[i] = abs(s[i] - s[i + 1]);
    if(a[i] == 1) {
      c1 += 1;
    } else if (a[i] == 2) {
      c2 += 1;
    } else {
      c0 += 1;
    }
  }

  if(c1 == 0 && c2 == 0) {
    puts("0");
    return 0;
  }

  int ans = 1;
  if(c1 == 0) {
    ans = 2;
  }
  for(int i = 0; i < n - 1; i++) {
    if(a[i] == 2) {
      if(c1 > 0) a[i] = 0;
      else a[i] = 1;
    }
    //printf("%d\n", a[i]);
  }


  int flag = 0;
  for(int i = 0; i < n - 1; i++) {
    int has = c[n - 2] - c[i] - c[n - 2 - i];
    if(has == 0) {
      flag += a[i];
    }
  }
  if(flag % 2 == 0) printf("0");
  else printf("%d\n", ans);

  //for(int k = 0; k < 64; k++) {
  //  sraw = "";
  //  for(int j = 0; j < 6; j++) sraw += ((k >> j) & 1) + '0';
  //  s = sraw;
  //  while(s.size() > 1) {
  //    string t;
  //    for(int i = 0; i < (int)s.size() - 1; i++) {
  //      t += abs(s[i] - s[i + 1]) + '0';
  //    }
  //    s = t;
  //  }
  //  cout << sraw << " " << s << endl;
  //}

  return 0;
}

Measured memory_bytes: 9220
/* 
*	
*	AUTHOR :- @soham01 
*		// "WORK HARD AND NEVER GIVE UP" //
*
*/
#include "bits/stdc++.h"
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long int a,b;
  cin>>a>>b;
  if(a<10)
  {
    cout<<b+(10-a)*100<<endl;
  }
  else if(a>=10)
  {
    cout<<b<<endl;
  }
	return 0;
}



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

using  namespace std;

#define FOR(x,z,y) for(int x = z; x < y; x++)
typedef long long ll;
typedef pair<int,int> iPair;




int removeDuplicates(vector<int>& nums){
    int size = nums.size();
    sort(nums.begin(),nums.end());
    FOR(i,0,nums.size()+1){
        if(nums[i] == nums[i+1]){
            size -=1;
        }
    }
    return 0;
}

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

    int n;
    cin >> n;
    FOR(i,0,3){
        if(n%10 == 7){
            cout << "Yes";
            break;
        }
        n/=10;
        if(n<1){
            cout << "No";
            break;
        }
    }


}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int inv[100500];
int N;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 1; i <= N; i++) {
        int a;
        cin >> a;
        inv[a] = i;
    }
    for(int i = 1; i <= N; i++) cout << inv[i] << endl;
    return 0;
}


Measured memory_bytes: 1280
N=int(input())
A=list(map(int,input().split()))
B=map(int,input().split())
cnt=0
for i,b in enumerate(B):
    if A[i]<b:
        cnt+=A[i]
        cnt+=min(b-A[i],A[i+1])
        A[i+1]-=min(b-A[i],A[i+1])
    else:
        cnt+=b
print(cnt)

Measured memory_bytes: 16212
//## MohK
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int sum=0;
    sum=(a*c)-b;
    cout<<sum<<endl;
    int x=(a*sum)-b;
    cout<<x<<endl;
    sum=x;
    int y=(a*sum)-b;
    cout<<y<<endl;
    sum=y;
    int z=(a*sum)-b;
    cout<<z<<endl;
    sum=z;
    int v=(a*sum)-b;
    cout<<v<<endl;
    sum=v;
    int m=(a*sum)-b;
    cout<<m<<endl;
    sum=m;
    int n=(a*sum)-b;
    cout<<n<<endl;
    sum=n;
    int l=(a*sum)-b;
    cout<<l<<endl;
    sum=l;
    int h=(a*sum)-b;
    cout<<h<<endl;
    sum=h;
    int q=(a*sum)-b;
    cout<<q<<endl;
    sum=q;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>
#include <functional>

using namespace std;
#define ALL(x)              (x).begin(),(x).end()
#define REP(i, n)           for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)       for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF                 (int)2e9
#define MOD                 (1000 * 1000 * 1000 + 7)
#define Ceil(x, n)          (((((x))+((n)-1))/n))
#define CeilN(x, n)         (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)        ((x)-(x)%(n))
#define IsOdd(x)            (((x)&0x01UL) == 0x01UL)
#define IsEven(x)           (!IsOdd((x)))
#define M_PI                3.14159265358979323846
typedef long long           ll;
typedef pair<ll, ll>        P;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
// 枝定義
struct Edge
{
	int	to;
	ll	dist;
	Edge(){}
	Edge(int to, ll dist) : to(to), dist(dist){}
};

template <class E>
using Graph = vector<vector<E>>;

// dfs
Graph<Edge>		G;
vector<int>		color;
bool dfs(int from, int fromCol)
{
	color[from] = fromCol;
	for (auto next : G[from]) {
		if (color[next.to] == 0) {
			if (!dfs(next.to, fromCol * (-1))) {
				return false;
			}
		} else if (color[next.to] == fromCol) {
			return false;
		} else {
			// すでに塗ってる
		}
	}

	return true;
}

// メイン
int main()
{
	int N;
	cin >> N;
	G.resize(N);
	color.resize(N, 0);
	REP(i, N - 1) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		G[a].emplace_back(Edge(b, 1));
		G[b].emplace_back(Edge(a, 1));
	}

	if (!dfs(0, 1)) {
		cout << -1 << endl;
		return 0;
	}

	ll white = 0;
	ll block = 0;
	REP(i, N) {
		if (color[i] == 1) {
			white++;
		} else {
			block++;
		}
	}

	int nowVal;
	vector<int> ans(N, -1);
	vector<int> isUsed(N, false);
	if (N / 3 < white && N / 3 < block) {
		nowVal = 1;
		REP(i, N) {
			if (color[i] == 1) {
				ans[i] = nowVal;
				nowVal += 3;
				if (N < nowVal) {
					break;
				}
			}
		}

		nowVal = 2;
		REP(i, N) {
			if (color[i] == -1) {
				ans[i] = nowVal;
				nowVal += 3;
				if (N < nowVal) {
					break;
				}
			}
		}
		
		nowVal = 3;
		REP(i, N) {
			if (ans[i] == -1) {
				ans[i] = nowVal;
				nowVal += 3;
			}
		}
	} else {
		int col = (white <= N / 3) ? 1 : -1;
		nowVal = 3;
		REP(i, N) {
			if (color[i] == col) {
				isUsed[nowVal - 1] = true;
				ans[i] = nowVal;
				nowVal += 3;
			}
		}

		int usedCnt = 0;
		REP(i, N) {
			if (ans[i] == -1) {
				while (isUsed[usedCnt]) {
					usedCnt++;
				}
				ans[i] = usedCnt + 1;
				isUsed[usedCnt] = true;
			}
		}
	}

	REP(i, N) {
		cout << ans[i]<< " ";
	}
	cout << endl;
	return 0;
}


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

typedef long long ll;

#define F first 
#define S second 
#define PB push_back
#define MP make_pair 
#define rep(i,a,b) for (ll i=a;i<b;i++)
const ll INF = 1LL << 60;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;


int main()
{

    int n;
    cin>>n;
    vector<double> p(n+1);

    p[0]=1;
    rep(i,1,n+1) cin>>p[i];

    vector<vector<double>> dp(n+1,vector<double>(n+1));

    dp[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            if(j-1>=0)
            dp[i][j] = dp[i-1][j-1]*p[i] + (1-p[i])*dp[i-1][j];
            else {
                dp[i][j] = dp[i-1][j]*(1-p[i]);
            }
            //cout<<dp[i][j]<<" ";
        }
        //cout<<endl;
    }

    double res=0;
    for(int i=n/2+1;i<=n;i++) {
        
        res +=dp[n][i];
    }
    cout<<fixed<< setprecision(10)<<res<<endl;
    return 0; 
}



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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

const int limit = 100010;
struct edge{
    int to;
    ll cost;
};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
    depth[v] = d;
    for(auto &e : tree[v]){
        if(e.to == p) continue;
        dfs(e.to, v, d + e.cost);
    }
}

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

    int n;
    cin >> n;
    
    for(int i = 0; i < n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }

    int q, k;
    cin >> q >> k;
    k--;

    dfs(k, -1, 0);
    for(int i = 0; i < q; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << depth[x] + depth[y] << endl;
    }

    return 0;
}

Measured memory_bytes: 14336
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <functional>
#include <ios>
#include <iomanip>
#include <cmath>
using namespace std;

typedef long long ll;
const ll InF = 1e15;

int main() {
  int N,t;
  cin>>N;
  vector<int> x(N),y(N);
  vector<ll> h(N);
  for (int i = 0; i < N; i++) {
    cin>>x[i]>>y[i]>>h[i];
    if (h[i] > 0) t = i;
  }
  int CX,CY;
  bool ok = false;
  for (int cx = 0; cx <= 100; cx++) {
    for (int cy = 0; cy <= 100; cy++) {
      bool flag = true;
      ll res = h[t] + (ll)abs(cx - x[t]) + (ll)abs(cy - y[t]);
      for (int j = 0; j < N; j++) {
        ll res2 = h[j] + (ll)abs(cx - x[j]) + (ll)abs(cy - y[j]);
        if (h[j] > 0 && res != res2) {
          flag = false;
          break;
        } else if (res - res2 > 0) {
          flag = false;
          break;
        }
      }
      if(flag) {
        CX = cx;
        CY = cy;
        ok = true;
        break;
      }
    }
  }
  if(ok) {
    int t;
    for (int i = 0; i < N; i++) {
      if (h[i] > 0) {
        t = i;
        break;
      }
    }
    ll H = h[t] + (ll)abs(CX - x[t]) + (ll)abs(CY - y[t]);
    cout<<CX<<" "<<CY<<" "<<H<<endl;
  }
  return 0;
}

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

int main(){
    int n;
    cin >> n;
    int a,b;
    int ma=0,ans;
    for(int i=0;i<n;i++){
    cin >> a >> b;
        if(ma<a){
            ma = a;
            ans=a+b;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int r, c;
  cin >> r >> c;
  int sheet[101][101] = {};
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> sheet[i][j];
    }
  }

  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      sheet[i][c] += sheet[i][j];
    }
  }
  for (int i = 0; i < c; i++) {
    for (int j = 0; j < r; j++) {
      sheet[r][i] += sheet[j][i];
    }
  }
  for (int i = 0; i < c; i++) {
    sheet[r][c] += sheet[r][i];
  }

  for (int i = 0; i <= r; i++) {
    for (int j = 0; j <= c; j++) {
      if (j == c) {
        cout << sheet[i][j] << endl;
      } else {
        cout << sheet[i][j] << " ";
      }
    }
  }

  return 0;
}


Measured memory_bytes: 3128
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
using namespace std;

int main (void) {
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a, a+3);
  int ans=0;
  int ok=1;
  while (ok){
    if ((2*a[2]-a[1]-a[0])%2==0) {
      ans=ans+(2*a[2]-a[1]-a[0])/2;
      cout << ans;
      return 0;
    }
    if ((2*a[2]-a[1]-a[0])%2 !=0) {
      a[1]=a[1]+1;
      ans=ans+2;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
   int a[100],b[100],n,c=0,v=0;
   cin>>n;
   for(int i=0;i<n;i++)
   {
     cin>>a[i];
   }
   copy(a,a+n,b);
   sort(b,b+n);
   for(int i=0;i<n;i++)
   {
       if(a[i]!=b[i])
       {
         c++;
         swap (a[i],b[i]);

       }
   }
   if(c<=2)
   {
      for(int i=0;i<n;i++)
      {
         if(a[i]<a[i+1])
         {
            v++;
         }
      }
      if(v==n)
      {
         cout<<"YES";
      }
      else
      {
         cout<<"NO";
      }
   }
   else
   {
      cout<<"NO";
   }

}




Measured memory_bytes: 3532
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N = ni()
    val A = 1 to 9 map (a => 100*a + 10*a + a)
    val ans = A.dropWhile(_ < N).head
    out.println(ans)
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int): Array[Int] = map(n)(_ => ni())
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def rep(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def rep_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  def sumL(as: Array[Int]): Long = {
    var s = 0L
    rep(as.length)(i => s += as(i))
    s
  }
}

Measured memory_bytes: 25420
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left
 
 
n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()
 
bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])
 
i = 0
d = []
for b, c in bc:
    d.extend([c]*b)
    if len(d) >= n:
        break
 
a=a+d
a.sort(reverse=True)
print(sum(a[:n]))

#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)



    




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

int32_t main()
{
	string s;
	cin>> s;
	int len = s.length();
	if(s[2]==s[3] & s[4]==s[5])
	{
		cout<<"Yes";
	}
	else
		cout<<"No";


	
}

Measured memory_bytes: 256