akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////




int main() {

	ll N, M;
	cin >> N >> M;

	ll f[MAX];
	f[0] = 1;

	repn(i, MAX - 1) {
		f[i] = f[i - 1] * i%MOD;
	}

	if (N == M) { cout << 2 * f[N] * f[M] % MOD; }
	else if (abs(N - M) == 1) { cout << f[N] * f[M] % MOD; }
	else { cout << 0; }

	system("PAUSE");
}


Measured memory_bytes: 8312
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fst first
#define snd second

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

vector<vector<int>> g;

pair<int, int> dfs(int u, int p)
{
    auto res = MP(1, u);
    for (auto v : g[u])
    {
        if (v != p)
        {
            auto x = dfs(v, u);
            x.fst++;
            res = max(res, x);
        }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    g.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].PB(v);
        g[v].PB(u);
    }
    auto v1 = dfs(0, -1);
    auto v2 = dfs(v1.snd, -1);
    int d = v2.fst;
    vector<char> ans(d + 1);
    ans[1] = true;
    ans[2] = false;
    for (int i = 3; i <= d; i++)
    {
        if (!ans[i - 1] || !ans[i - 2])
            ans[i] = true;
    }
    if (ans[d])
        cout << "First";
    else
        cout << "Second";
    return 0;
}

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

		// 文字列の入力
		String s = sc.next();
		String[] S = s.split("");

		boolean flg = false;

		for(int i=1;i<4;i++){
			if(S[0].equals(S[i])){
				for(int j=1;j<3;j++){
					for(int k=j+1;k<4;k++){
						if(S[j].equals(S[k])&&!S[k].equals(S[0]))flg=true;
					}
				}
			}
		}

		// 出力
		System.out.println(flg?"Yes":"No");
	}
}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int mn = 0, cnt = 0;
  for (char c : s) {
    if (c == '(') {
      ++cnt;
    } else {
      --cnt;
    }
    mn = min(mn, cnt);
  }
  cout << string(-mn, '(') << s << string(cnt - mn, ')') << endl;
}


Measured memory_bytes: 256
#参考　https://atcoder.jp/contests/abc124/submissions/4948803
from itertools import accumulate

def f():
     n, k = map(int,input().split())
     p = list(input())
     a = [] 
     pre = '1'
     cnt = 0
     for i in p:
          if pre != i:
               a.append(cnt)
               cnt = 1
               pre = i
          else:
               cnt += 1
     a.append(cnt)
     if pre == '0':
          a.append(0)

     w = 2*k+1

     if w >= len(a):
          return n
     else:
          acc = [0] + list(accumulate(a))
          ans = 0
          for i in range(0,len(a)-w+1,2):
               ans = max(ans,acc[i+w]-acc[i])
          return ans
          
print(f())

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;

int main() {
    string s;
    cin >> s;
    if (s == "Sunny") cout << "Cloudy";
    if (s == "Cloudy") cout << "Rainy";
    if (s == "Rainy") cout << "Sunny";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int64_t N, M, Q, ans = 0;
vector<int64_t> A1(100), B(100), C(100), D(100);

int64_t calc(vector<int64_t> &A)
{
  int64_t ret = 0;
  for (int i = 0; i < Q; i++)
  {
    if (A[B[i]] - A[A1[i]] == C[i])
      ret += D[i];
  }
  return ret;
}

void dfs(vector<int64_t> &A, int64_t &ans)
{
  if (A.size() == N + 1)
  {
    int64_t tmp = calc(A);
    ans = max(ans, tmp);
    return;
  }
  int64_t ba = A.back();
  for (int i = ba; i <= M; i++)
  {
    A.push_back(i);
    dfs(A, ans);
    A.pop_back();
  }
}

int main()
{
  cin >> N >> M >> Q;
  for (int i = 0; i < Q; i++)
  {
    cin >> A1[i] >> B[i] >> C[i] >> D[i];
  }
  vector<int64_t> A(1, 1);
  dfs(A, ans);
  cout << ans << endl;
}


Measured memory_bytes: 3636
//write for s26

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	int q=n%10;
	if(q==2||q==4||q==5||q==7||q==9) {
		cout<<"hon"<<endl;
	}
	if(q==0||q==1||q==6||q==8) {
		cout<<"pon"<<endl;
	}
	if(q==3) {
		cout<<"bon"<<endl;
	}
	return 0;
}


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

using namespace std;

typedef long long ll;

vector< vector<int> > G;

void dfs(int cur, int par, vector<int>& col, bool& flag) {
	for (int nex : G[cur]) {
		if (nex == par) continue;
		if (col[nex] != -1) {
			if (col[nex] == col[cur]) flag = false;
			continue;
		}
		col[nex] = !col[cur];
		dfs(nex, cur, col, flag);
	}
}

struct Union_Find {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    
    Union_Find(int size) : data(size, -1) {}
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }
    int Find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int size(int x) {
        return -data[Find(x)];
    }
};


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> u(m), v(m);
	Union_Find uf(n);
	G.resize(n);
	for (int i = 0; i < m; i++) {
		cin >> u[i] >> v[i];
		u[i]--;
		v[i]--;
		uf.Union(u[i], v[i]);
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}

	int cnt1 = 0, cnt2 = n;
	for (int i = 0; i < n; i++) {
		if (uf.Find(i) == i) {
			if (uf.size(i) > 1) cnt1++;
			else cnt2--;
		}
	}

	int cnt3 = cnt1;
	for (int i = 0; i < n; i++) {
		if (uf.Find(i) != i || uf.size(i) == 1) continue;
		bool flag = true;
		vector<int> col(n, -1);
		col[i] = 0;
		dfs(i, -1, col, flag);
		cnt3 -= !flag;
	}

	cout << (ll)n * n - (ll)cnt2 * cnt2 + (ll)cnt1 * cnt1 + (ll)cnt3 * cnt3 << endl;
	return 0;
}


Measured memory_bytes: 13816
use std::collections::VecDeque;

fn main() {
    let mut n = read::<u64>();
    let mut ret: VecDeque<char> = VecDeque::new();
    while n != 0 {
        let mut m = (n % 26) as u8;
        if m == 0 {
            m = 26;
        }
        let c = (m + 96) as char;
        ret.push_front(c);
        if m == 26 {
            n /= 26;
            n -= 1;
        } else {
            n /= 26;
        }
    }
    println!("{}", ret.into_iter().collect::<String>());
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}


Measured memory_bytes: 2108
N, L = map(int,input().split())
i = 0
apple_taste = []
pi_taste = 0
while N > i:
    apple_taste.append(L + i)
    if(L>0):
        if i>0:
            pi_taste += apple_taste[i]
    elif(L+(N-1)>=0):
            pi_taste += apple_taste[i]
    elif(L<0):
        if i>0:
            pi_taste += apple_taste[i-1]
    i += 1 
print(pi_taste)

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

bool c[MAX],x[MAX*2-1],y[MAX*2-1];
int r[MAX];

void init(){
  for(int i=0;i<MAX;i++){
    r[i]=-1;
    c[i]=false;
  }
  for(int i=0;i<MAX*2-1;i++){
    x[i]=false;
    y[i]=false;
  }
}

void print(){
  for(int i=0;i<MAX;i++){
    for(int j=0;j<MAX;j++){
      if(r[i]==j)cout<<'Q';
      else cout<<'.';
    }
    cout<<endl;
  }
}

void rec(int n){
  if(n==MAX)print();
  else if(r[n]!=-1)rec(n+1);
  else {
    for(int i=0;i<MAX;i++){
      if(!c[i] && !x[MAX-1-n+i] && !y[n+i]){
	r[n]=i;
	c[i]=true;
	x[MAX-1-n+i]=true;
	y[n+i]=true;
	rec(n+1);
	r[n]=-1;
	c[i]=false;
	x[MAX-1-n+i]=false;
	y[n+i]=false;
      }
    }
  }
}

int main()
{
  int n,a,b;

  init();

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a>>b;
    r[a]=b;
    c[b]=true;
    x[MAX-1-a+b]=true;
    y[a+b]=true;
  }

  rec(0);

  return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 5;
typedef long long ll;
ll power(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1){
            res = res * a;
        }
        a = a * a; 
        b/=2;
    }
    return res;
}
int main(){
    ll x,y;
    scanf("%lld %lld",&x,&y);
    ll r = y / x;
    ll l=0, h=(int)65;
    while(h - l > 1){
        ll m = (h + l) / 2;
        if(power(2,m) <= r){
            l=m;
        } else{
            h=m;
        }
    }
    printf("%lld\n",l+1);
    return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    C = list(map(int, readline().split()))

    ans = -INF
    for i in range(N):
        score = []
        total = 0
        x = i
        while True:
            x = P[x]
            score.append(C[x])
            total += C[x]
            if x == i:
                break

        l = len(score)
        csum = 0
        for i in range(l):
            if i + 1 > K:
                break
            csum += score[i]
            res = csum
            if total > 0:
                res += (K - (i + 1)) // l * total

            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 83180
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

x,t = inpl()
print(max(x-t,0))

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

#define INF 1001001001
#define MAX 1e18

const int mod = 998244353;

int main() {
  int n, d;
  cin >> n >> d;
  vector<int> x(n), y(n);
  rep(i,n) cin >> x[i] >> y[i];

  two_sat ts(n);
  rep(i,n) for (int j = i+1; j < n; j++) {
    if (abs(x[i]-x[j]) < d) ts.add_clause(i,false,j,false);
    if (abs(x[i]-y[j]) < d) ts.add_clause(i,false,j,true);
    if (abs(y[i]-x[j]) < d) ts.add_clause(i,true,j,false);
    if (abs(y[i]-y[j]) < d) ts.add_clause(i,true,j,true);
  }
  if (!ts.satisfiable()) {
    cout << "No" << endl;
    return 0;
  }
  vector<bool> res = ts.answer();
  cout << "Yes" << endl;
  rep(i,n) cout << (res[i]?x[i]:y[i]) << endl;

  return 0;
}


Measured memory_bytes: 3732
s = input()

a_idx = -1
for i in range(len(s)):
    if s[i] == 'A':
        a_idx = i
        break

z_idx = len(s)
for j in range(len(s)-1, -1, -1):
    if s[j] == 'Z':
        z_idx = j
        break

print(z_idx-a_idx+1)


Measured memory_bytes: 3516
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1e18;

int main() {
  ll n,m;
  cin >> n >> m;
  vec x(n+1),y(m+1);
  cin >> x[0] >> y[0];
  for(ll i=1;i<=n;i++) cin >> x[i];
  for(ll i=1;i<=m;i++) cin >> y[i];
  sort(x.rbegin(),x.rend());
  sort(y.begin(),y.end());
  if(x[0]<y[0]) cout << "No War" << endl;
  else cout << "War" << endl;
}

Measured memory_bytes: 256
import sys
from collections import Counter
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

N = INT()
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
for i in range(N):
    a = float(input())
    # ここint()だと切り捨てでバグる
    A[i] = round(a * K)
    C[gcd(A[i], L)] += 1

ans = 0
for k1, v1 in C.items():
    for k2, v2 in C.items():
        if k1 == k2:
            if k1*k2 % L == 0:
                ans += v1*(v1-1) // 2
        elif k1 < k2:
            if k1*k2 % L == 0:
                ans += v1 * v2
print(ans)


Measured memory_bytes: 17164
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); i++)

using namespace std;

int main() {
  string s;
  cin >> s;
  if (s == "SUN") {
    cout << 7;
  } else if (s == "MON") {
    cout << 6;
  } else if (s == "TUE") {
    cout << 5;
  } else if (s == "WED") {
    cout << 4;
  } else if (s == "THU") {
    cout << 3;
  } else if (s == "FRI") {
    cout << 2;
  } else if (s == "SAT") {
    cout << 1;
  }
  cout << endl;
}


Measured memory_bytes: 504
#include <stdio.h>
int main(){
    int n,ans,temp;
    scanf("%d",&n);
    ans=n;
    while(n--){
        scanf("%d",&temp);
        for(int i=1;i*i<temp;i++)if((temp-i)%(i*2+1)==0){
            ans--;
            break;
        }
    }
    printf("%d\n",ans);
}


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

typedef long long ll;

#define        optimize           ios::sync_with_stdio(0); cin.tie(0);
#define PI    acos(-1.0)
#define pb push_back
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define RESET(a, b) memset(a, b, sizeof(a))
#define pii pair <int, int>
#define gcd(a, b) __gcd(a, b)
#define min3(a, b, c) min(c, min(a, b))
#define max3(a, b, c) max(c, max(a, b))

#define        MX        200005

int main()
{
    optimize
    string str;
    cin>>str;

    int ans = 0, c = 0;
    for(int i = 0; i < str.size(); i++){
        if(str[i] == 'R'){
            c++;
        }
        else{
            ans = max(ans, c);
            c = 0;
        }
    }

    ans = max(ans, c);
    cout<<ans<<endl;
}


Measured memory_bytes: 3648
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        k: i64,
        mut a: [i64; n],
        mut f: [i64; n],
    }

    a.sort();
    f.sort();
    f.reverse();

    let mut lo = -1;
    let mut hi = 1_000_000_000_000_000_000;

    while hi - lo > 1 {
        let mi = (lo + hi) / 2;

        let mut need = 0;
        for i in 0..n {
            if a[i] * f[i] > mi {
                need += (a[i] * f[i] - mi + f[i] - 1) / f[i];
            }
        }

        if need <= k {
            hi = mi;
        } else {
            lo = mi;
        }
    }

    let ans = hi;

    println!("{}", ans);
}


Measured memory_bytes: 10492
use proconio::input;

const MOD: u64 = 1_000_000_007;

fn main() {
    input!(s: usize);

    let mut dp = vec![0; s + 1];
    dp[0] = 1;
    for i in 3..=s {
        dp[i] = dp[i - 1] + dp[i - 3];
        dp[i] %= MOD;
    }
    let ans = dp[s];

    println!("{}", ans);
}


Measured memory_bytes: 2160
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[-1] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    wark = collections.deque([[Ch - 1, Cw - 1]])
    warp = collections.deque([])

    visited[Ch - 1][Cw - 1] = 0
    while wark:
        h, w = wark.popleft()
        warp.append((h, w))
        for mh, mw in move:
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                visited[ch][cw] = visited[h][w]
                wark.append([ch, cw])
        if len(wark) == 0:
            while warp:
                h, w = warp.popleft()
                for wh in range(-2, 3):  # 移動B: ワープ魔法
                    for ww in range(-2, 3):
                        ch, cw = h + wh, w + ww
                        if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '#' and visited[ch][cw] == -1:
                            visited[ch][cw] = visited[h][w] + 1
                            wark.append([ch, cw])

    ret = visited[Dh - 1][Dw - 1]
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 104812
//Author Name - Mohammad Shehar Yaar Tausif
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;

typedef long long int lld;
double DP[3010][3010];

int main(){
	int n,i,j;
	double arr[3010];
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>arr[i];
	}
	DP[0][0] = 0;
	DP[0][1] = 0;
	DP[1][0] = 1-arr[1];
	DP[1][1] = arr[1];
	for(i=2;i<n;i++){
		DP[i][0] = (1-arr[i])*DP[i-1][0];
	}
	for(i=2;i<=n;i++){
		for(j=1;j<=i;j++){
			DP[i][j] = (DP[i-1][j]*(1-arr[i])) + (DP[i-1][j-1]*arr[i]);
		}
	}
	int mid = n/2;
	double sum=0;
	 for(i=mid+1;i<=n;i++){
		sum += DP[n][i];
	}
	cout<<setprecision(10)<<sum<<endl;
	return 0;
}


Measured memory_bytes: 69120
n = int(input())
S = [input() for _ in range(n)]

note = [[0]*26 for _ in range(n)]
for i,line in enumerate(S):
    for s in line:
        note[i][ord(s)-97] += 1

option = []

for i, column in enumerate(zip(*note)):
    for _ in range(min(column)):
        option.append(chr(i+97))

option.sort()

print("".join(option))

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			String s = scanner.next();
			int n = s.length();
			System.out.println((isPalindromic(s) && isPalindromic(s.substring(0, n / 2))
					&& isPalindromic(s.substring((n + 2) / 2))) ? "Yes" : "No");
		}
	}

	private static boolean isPalindromic(String string) {
		char[] s = string.toCharArray();
		for (int i = 0; i < s.length; i++) {
			if (s[i] != s[s.length - 1 - i]) {
				return false;
			}
		}
		return true;
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)
using P =pair<int,int>;

ll ketasu(ll a){
   ll num=1;
   while(a/10){
       num++;
       a/=10;
   }
   return num;
}

ll gcd(ll a,ll b){return b ? gcd(b,a%b) :a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

ll kosuu(ll a){
    ll sum=0;
    for(ll i=1;i*i<=a;i++){
        if(a%i==0){
            if(a!=1&&i*i!=a){
            sum+=2;
            }else{
             sum++;   
            }
        }
    }
    return sum;
}




const int m =2019;
int main()
{
string s;
cin>>s;
if(s=="RRS"||s=="SRR"){
    cout<<2<<endl;
}else if(s=="RRR"){
    cout<<3<<endl;
}else if(s=="SSS"){
    cout<<0<<endl;
}else{
    cout<<1<<endl;
}

}



Measured memory_bytes: 3628
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn vec<T, F: FnMut(usize) -> T>(n: usize, mut f: F) -> Vec<T> {
    (0..n).map(|i| f(i)).collect()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let a: Vec<i64> = vec(n, |_| scan(tokens));
    if n % 2 == 0 {
        let mut dp0 = a[0];
        let mut dp1 = 0;
        for i in 1..n {
            if i % 2 == 0 {
                dp0 = dp0 + a[i];
            } else {
                dp1 = std::cmp::max(dp0, dp1 + a[i]);
            }
        }
        println!("{}", dp1);
    } else {
        let mut dp0 = a[0];
        let mut dp1 = 0;
        let mut dp2 = 0;
        for i in 1..n {
            if i % 2 == 0 {
                dp0 = dp0 + a[i];
                dp2 = std::cmp::max(dp1, dp2 + a[i]);
            } else {
                dp1 = std::cmp::max(dp0, dp1 + a[i]);
            }
        }
        println!("{}", dp2);
    }
}


Measured memory_bytes: 5704
#include <bits/stdc++.h>
 
using namespace std;
 
const long long MOD=1e9+7;
const double PI=3.14159265359;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, y;
    cin>>n>>y;
    
    for(long long i=0; i<=n; i++){
        for(long long j=0; i+j<=n; j++){
            long long k=n-i-j;
            if(i*10000+j*5000+k*1000==y){
                cout<<i<<" "<<j<<" "<<k;
                return 0;
            }
        }
    }
    cout<<"-1 -1 -1";
    
    
    
    
    return 0;
}

Measured memory_bytes: 256
S = input()

def check(s):
    a = len(s)//2
    s1 = s[:a]
    s2 = s[a:]
    if s1==s2:
        return 0
    else:
        return 1

if len(S)%2==0:
    S = S[:-2]
else:
    S = S[:-1]

while  True:
    ans = check(S)
    if ans==0:
        print(len(S))
        break;
    else:
        S = S[:-2]


Measured memory_bytes: 2940
#include <string>
#include <iostream>
#include <stdio.h>
#include <list>
#include <cmath>

using namespace std;

int main() {
  ios::sync_with_stdio(false);

  list<int> lst;
  auto itr = lst.begin();

  int length;
  int cmd, val;

  cin >> length;

  for (int i = 0; i < length; i++) {
    cin >> cmd;
    switch (cmd) {
      // insert
      case 0:
        cin >> val;
        itr = lst.insert(itr, val);

        break;

      // move
      case 1:
        cin >> val;
        for (int j = 0; j < abs(val); j++) {
          if (val > 0) {
            itr++;
          } else {
            itr--;
          }
        }
        break;

      // erase
      case 2:
        itr = lst.erase(itr);
        break;
    }
  }

  for (auto itr = lst.begin(); itr != lst.end(); itr++) {
    cout << *itr << endl;
  }
}




Measured memory_bytes: 18652
p = 1000000007
def modPow(a, n, m):
    ans = 1
    while n > 0:
        if (n & 1): ans = (ans * a) % m
        a = (a * a) % m
        n = n >> 1
    return ans

n, m = map(int, input().split())
print(modPow(n, m, p))


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

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

  ll x = min(b - 1, n);
  cout << a * x / b - a * (x / b);
}


Measured memory_bytes: 3532
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
past = -10
for i in range(n):
    ans += B[A[i] - 1]
    if past == A[i] - 1 - 1:
        ans += C[A[i] - 1 - 1]
    past = A[i] - 1

print(ans)

Measured memory_bytes: 38504
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))


Measured memory_bytes: 149640
INT_MAX=10**18+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#################################################################################
a,b,c=INPUT()
string=""
string+=str(a)
string+=str(b)
string+=str(c)
if string=='557' or string=="575" or string=="755":
    print("YES")
else:
    print("NO")


Measured memory_bytes: 38256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw3(15,1);vector<ll> pw10(19,1);


int main(){
    {rep1(i,14) pw3[i]=3*pw3[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N,M; cin>>N>>M;
    vector<ll> X(M);
    rep(i,M) cin>>X[i];
    sort(all(X));
    
    if(N>=M){
        cout<<0<<endl;
        return 0;
    }
    
    //N<M
    //N-1<M-1
    
    vector<ll> T;
    rep(i,M-1){
        T.pb(X[i+1]-X[i]);
    }
    sort(all(T));
    
    ll ans=0;
    rep(i,M-N) ans+=T[i];
    cout<<ans<<endl;
}


Measured memory_bytes: 5016
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
string S;
cin >> S;
  
int S_size = 0;

  S_size = S.size();
  
  for (int i =0; i < S_size; i++){
   cout << "x"; 
  
    // 出力
    //cout << A << " " << B << endl;
  }
  cout << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split())) 
B = list(map(int,input().split()))[::-1]
#print(A)
#print(B)


l = []

for i in range(N):
    l.append(sum(A[:N-i])+sum(B[:i+1]))
    
#print(l)
print(max(l))




Measured memory_bytes: 8988
#include <iostream>
int main(){
  int N,temp,count=0;
  std::cin>>N;
  for (int i=1;i<=N;i++){
    std::cin>>temp;
    if(temp!=i){
      count++;
    }
  }
  if(count==0||count==2){
    std::cout<<"YES"<<std::endl;
  }else{
    std::cout<<"NO"<<std::endl;
  }
}


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

int f(int n, int k)
{
	if(n < k) return 1;
	return f(n / k, k) + 1;
}

int main() 
{
	int n, k;
	
	scanf("%d%d", &n, &k);
	printf("%d\n", f(n, k));	
			
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b){
    if(a < b) swap(a, b);
    int r;
    while(r=a%b){
        a = b;
        b = r;
    }
    return b;
}

int main(){
    int n, x;
    cin >> n >> x;
    vector<int> v(n+1);
    vector<int> sub;
    v[0] = x;
    int min = x;
    for(int i = 1; i < n+1; i++){
        cin >> v[i];
        //cout << v[i] << endl;
        if(v[i] < min) min = v[i];
    }
    //cout << min << endl;
    for(int i = 0; i < n+1; i++){
        if(v[i]-min != 0){
            sub.push_back(v[i]-min);
        }
    }
    if(sub.size() == 1) cout << sub[0] << endl;
    else{
        int ans = gcd(sub[0], sub[1]);
        for(int i = 2; i < n; i++){
            ans = gcd(ans, sub[i]);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 4316
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		Set<String>used=new HashSet<String>();

		String s = sc.next();
		used.add(s);
		for (int i = 1; i < N; i++) {
			String t = sc.next();
			if (used.contains(t)) {
				System.out.println("No");
				break;
			}else {
				used.add(t);
			}
			if (s.charAt(s.length()-1) != t.charAt(0)) {
				System.out.println("No");
				break;
			}
			if (i == N-1) {
				System.out.println("Yes");
			}
			s=t;
		}

	}
}



Measured memory_bytes: 35676
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> 
#define ff first 
#define endl "\n"
#define ss second 
#define li list<int>
#define vi vector<int>
#define ll long long int
#define pii pair<int,int>
#define vii vector<pair<int,int> >
#define mp make_pair
#define pb push_back
#define setbits(x) __builtin_popcountll(x)
#define custom  pair<int,pair<int,int> >
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> pbds; 
#define mod 1000000007
int dp[100001];
vector<int> graph[100001];
int solve(int node){
    if(dp[node]!=-1){
        return dp[node];
    }
    bool flag=true;
    int bestans=0;
    for(auto child:graph[node]){
        flag=false;
        bestans=max(bestans,solve(child));
    }
    return dp[node]=flag?0:1+bestans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;int x,y;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        graph[x].pb(y);
    }
    memset(dp,-1,sizeof dp);
    int ans=INT_MIN;
    for(int i=1;i<=n;i++){
        ans=max(ans,solve(i));
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 11412
import java.util.Scanner;

public class Main {

	public static void main(String args[])
	{
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int k=scan.nextInt();
		int ar[]=new int[n];
		for(int i=0;i<n;i++)
		{
			ar[i]=scan.nextInt();
		}
		boolean dp[]=new boolean[k+1];
		dp[0]=false;
		for(int i=1;i<=k;i++)
		{
			for(int x:ar)
			{
				if(i>=x && !dp[i-x])
				{
					dp[i]=true;
				}
			}
		}
		if(dp[k])
		{
//			System.err.println();
			System.out.println("First");
		}else {
			System.out.println("Second");
		}
		
	}
}


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

int main(){
	int x,i,j;
	cin>>x;
	
	for(i=0;i<=10000;i++)
		for(j=-10000;j<=-1;j++)
			if(i*i*i*i*i-j*j*j*j*j==x)
			{
				cout<<i<<' '<<j;
				return 0;
			}
			
	for(i=0;i<=10000;i++)
		for(j=10000;j>=0;j--)
			if(i*i*i*i*i-j*j*j*j*j==x)
			{
				cout<<i<<' '<<j;
				return 0;
			}
			
	for(i=-10000;i<=-1;i++)
		for(j=-1;j>=-10000;j--)
			if(i*i*i*i*i-j*j*j*j*j==x)
			{
				cout<<i<<' '<<j;
				return 0;
			}
}

Measured memory_bytes: 3620
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<vector>
#define prDouble(x) cout << fixed << setprecision(10) << x
#define MOD 1000000007
#define fast_io ios_base::sync_with_stdio(false)
#define ii pair<int,int>
#define ll long long int 
using namespace std;
int dp[100001][2];
vector<int>tree[100001];
ll solve(int root,int par,int isCon)
{
	if(dp[root][isCon] != -1)
		return dp[root][isCon];
	ll result = 0;
	ll w,b;
	w = b = 1;
	for(int child:tree[root])
	{
		if(child != par)
			w = (w * solve(child,root,0))%MOD;
	}
	result = (result+ w)%MOD;
	if(!isCon)
	{
		for(int child:tree[root])
		{
			if(child != par)
				b = (b * solve(child,root,1))%MOD;
		}
		result = (result + b)%MOD;
	}
	return dp[root][isCon] = result;
}
int main()
{
	int n,x,y;
	cin >> n;
	for(int i = 0;i < n-1;++i)
	{
		cin >> x >> y;
		tree[x-1].push_back(y-1);
		tree[y-1].push_back(x-1);
	}
	memset(dp,-1,sizeof(dp));
	cout << (solve(0,-1,0)) << "\n";
	return 0;
}

Measured memory_bytes: 16744
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iostream>

using namespace std;

#define FOR(i, a, b)   for(int i = (a); i < (b); i++)
#define RFOR(i, a, b)  for(int i = (a); i > (b); i--)
#define rep(i, n)	   for(int i = 0; i < (n); i++)
#define all(c)		   begin(c), end(c)
#define rall(c)		   rbegin(c), rend(c)
#define foritr(itr, c) for(auto itr = begin(c); itr != end(c); itr++)
#define SZ(a)		   ((ll) a.size())

typedef long long int		   ll;
typedef long long unsigned int llu;

void solve(string A, string B) {
	int ans = 0;
	if(SZ(A) > SZ(B)) ans = 1;
	else if(SZ(A) < SZ(B)) ans = 2;
	else {
		if(A > B) ans = 1;
		else if(A < B) ans = 2;
	}
	if(ans == 0) printf("EQUAL");
	if(ans == 1) printf("GREATER");
	if(ans == 2) printf("LESS");
}

int main() {
	string A;
	string B;
	cin >> A;
	cin >> B;
	solve(A, B);
	return 0;
}


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

ll gcd(ll a, ll b){
    if(a%b == 0) return b;
    return gcd(b, a%b);
}

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];
    vector<ll> mae(n+1), usi(n+1);
    mae[0] = a[0];
    usi[n-1] = a[n-1];
    rep(i,n-1){
        mae[i+1] = gcd(mae[i], a[i+1]);
        usi[n-i-2] = gcd(usi[n-i-1], a[n-i-2]);
    }
    usi[n] = mae[n-2];
    ll ans = usi[1];
    rep(i, n-1){
        ll memo = gcd(mae[i], usi[i+2]);
        ans = max(ans, memo);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//V,P(大文字)使用不可

const ll INF=1e18;

ll f(ll n){
    ll m=1;
    rep(i,n) m*=2;
    return m;
}

signed main(){
    ll n;
    cin>>n;
    V<ll> a(n);
    cinf(n,a);
    ll ans=0;
    for(ll i=0;i<70;i++){
        ll cnt=0;
        for(ll j=0;j<n;j++){
            if(a[j]>>i&1) cnt++;
        }
        ans+=(((cnt*(n-cnt))%mod)*(f(i)%mod))%mod;
        ans=ans%mod;
    }
    cout<<ans<<endl;
}

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

using namespace std;

inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0' || '9'<ch)ch=getchar();
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x;
}

inline void chkmin(int &a,int b){if(a>b)a=b;}
inline int minn(int a,int b){if(a<b)return a;return b;}

const int N=200009;
const int Q=200009;
const int Inf=2e9+7;

struct node
{
	int l,r;
}qu[Q];

int n,q,ans;
int b[N],sum[N];
int f[N],t[N<<2];
vector<int> g[N];

inline int zero(int l,int r)
{
	return r-(l-1)-(sum[r]-sum[l-1]);
}

inline int one(int l,int r)
{
	if(l>r)return 0;
	return sum[r]-sum[l-1];
}

#define mid ((l+r)>>1)

inline void upd(int z)
{
	t[z]=minn(t[z<<1],t[z<<1|1]);
}

inline void build(int x,int l,int r)
{
	if(l==r)
	{
		t[x]=f[l]-sum[l];
		return;
	}
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	upd(x);
}

inline void modify(int x,int l,int r,int p)
{
	if(l==r)
	{
		t[x]=f[l]-sum[l];
		return;
	}
	if(p<=mid)
		modify(x<<1,l,mid,p);
	else 
		modify(x<<1|1,mid+1,r,p);
	upd(x);
}

inline int query(int x,int l,int r,int dl,int dr)
{
	if(dl==l && r==dr)
		return t[x];
	if(dr<=mid)
		return query(x<<1,l,mid,dl,dr);
	else if(mid<dl)
		return query(x<<1|1,mid+1,r,dl,dr);
	return minn(query(x<<1,l,mid,dl,mid),query(x<<1|1,mid+1,r,mid+1,dr));
}

int main()
{
	if(fopen("hamming.in","r"))
	{
		freopen("hamming.in","r",stdin);
		freopen("hamming.out","w",stdout);
	}

	n=read();
	for(int i=1;i<=n;i++)
	{
		b[i]=read()^1;
		sum[i]=sum[i-1]+b[i];
	}
	q=read();
	for(int i=1;i<=q;i++)
	{
		qu[i].l=read(),qu[i].r=read();
		g[qu[i].l-1].push_back(qu[i].r);
	}

	for(int i=1;i<=n;i++)
		f[i]=Inf;
	f[0]=0;
	build(1,0,n);
	for(int i=0;i<n;i++)//pos
	{
		for(int j=0;j<g[i].size();j++)
		{
			chkmin(f[g[i][j]],query(1,0,n,i,g[i][j]-1)+sum[g[i][j]]);
			modify(1,0,n,g[i][j]);
		}
		chkmin(f[i+1],f[i]+(b[i+1]^1));
		modify(1,0,n,i+1);
	}

	printf("%d\n",f[n]);
	return 0;
}



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

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  vector<long> A(N + 1), B(M + 1);
  for (int i = 0, a; i < N && cin >> a; i++) A.at(i + 1) = A.at(i) + a;
  for (int i = 0, b; cin >> b; i++) B.at(i + 1) = B.at(i) + b;
  int ans = 0;
  for (int a = 0; a < N + 1 && A.at(a) <= K; a++) {
    ans = max(ans, a + (int)(upper_bound(B.begin(), B.end(), K - A.at(a)) - B.begin() - 1));
  }
  cout << ans << "\n";
}

Measured memory_bytes: 6364
import java.io.IOException;
import java.util.Scanner;
public class Main {
    public static void main (String args[]) throws IOException {
    	Scanner sc = new Scanner(System.in);
    	StringBuilder sb = new StringBuilder();
    	while(true){
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		if(a==0&&b==0){
    			break;
    		}

    		for(int i=1;i<=a;i++){
    			for(int x=1;x<=b;x++){
    				 if(i==1||i==a){
    					 sb.append("#");
    				 }
    			     else{
    				    if(x==1||x==b){
    					    sb.append("#");
    				    }else{
    				        sb.append(".");
    				    }
    			     }
    			}
    			sb.append("\n");
    		}
    		sb.append("\n");
    	}
        System.out.print(sb);
    }

}

Measured memory_bytes: 27332
#include<cstdio>
#include<algorithm>
#define N_ 301000
using namespace std;
int n, m;
char X1[N_], X2[N_], Y1[N_], Y2[N_];
long long U[N_], D[N_], L[N_], R[N_], F[N_], InvF[N_], UU[N_], LL[N_], res;
long long Mod = 998244353;
long long Pow(long long a, int b){
    long long r = 1;
    while(b){
        if(b&1)r=r*a%Mod;
        a=a*a%Mod;b>>=1;
    }
    return r;
}
long long Comb(int a, int b){
    if(a<b)return 0;
    return F[a] * InvF[b]%Mod*InvF[a-b]%Mod;
}
long long Calc(int a, int b, int c){
    return (Comb(a+b+c,c) - Comb(a+b+c-1, c) + Mod) % Mod;
}
int main(){
    int i;
    scanf("%d%d",&n,&m);
    scanf("%s",X1+1);
    scanf("%s",X2+1);
    scanf("%s",Y1+1);
    scanf("%s",Y2+1);
    F[0]=1;
    int sum = 0;
    for(i=1;i<=n;i++){
        sum += X1[i]-'0';
        sum += X2[i]-'0';
    }
    for(i=1;i<=m;i++){
        sum += Y1[i]-'0';
        sum += Y2[i]-'0';
    }
    if(!sum){
        printf("1\n");
        return 0;
    }
    for(i=1;i<=300000;i++)F[i]=F[i-1]*i%Mod;
    InvF[300000] = Pow(F[300000], Mod-2);
    for(i=300000;i>=1;i--)InvF[i-1] = InvF[i] * i % Mod;
    int s1 = 0, s2 = 0, cc = 0;
    for(i=1;i<=m;i++)if(Y1[i] == '1')cc++;
    U[0] = 1;
    for(i=1;i<=n;i++){
        if(X1[i] == '1')s1++;
        if(X2[i] == '1')s2++;
        U[i] = Calc(s1,s2,cc);
    }
    s1 = s2 = cc = 0;
    for(i=1;i<=m;i++)if(Y2[i] == '1')cc++;
    D[n+1] = 1;
    for(i=n;i>=1;i--){
        if(X1[i] == '1')s1++;
        if(X2[i] == '1')s2++;
        D[i] = Calc(s1,s2,cc);
    }
    s1 = s2 = cc = 0;
    for(i=1;i<=n;i++)if(X1[i] == '1')cc++;
    L[0] = 1;
    for(i=1;i<=m;i++){
        if(Y1[i] == '1')s1++;
        if(Y2[i] == '1')s2++;
        L[i] = Calc(s1,s2,cc);
    }
    s1 = s2 = cc = 0;
    R[m+1] = 1;
    for(i=1;i<=n;i++)if(X2[i] == '1')cc++;
    for(i=m;i>=1;i--){
        if(Y1[i] == '1')s1++;
        if(Y2[i] == '1')s2++;
        R[i] = Calc(s1,s2,cc);
    }
    UU[0] = 1;
    for(i=1;i<=n;i++){
        int t = X1[i]-'0' + X2[i]-'0';
        UU[i] = UU[i-1];
        if(t==2) UU[i] += UU[i-1];
        if(t) UU[i] += U[i];
        UU[i]%=Mod;
    }
    LL[0] = 1;
    for(i=1;i<=m;i++){
        int t = Y1[i]-'0' + Y2[i]-'0';
        LL[i] = LL[i-1];
        if(t==2) LL[i] += LL[i-1];
        if(t) LL[i] += L[i];
        LL[i]%=Mod;
    }
    for(i=1;i<=n;i++){
        int c = X1[i] - '0' + X2[i] - '0';
        res = (res + UU[i-1]*D[i+1]*c) % Mod;
    }
 //   printf("%lld\n",res);
    for(i=1;i<=m;i++){
        int c = Y1[i] - '0' + Y2[i] - '0';
        res = (res + LL[i-1]*R[i+1]*c) % Mod;
    }
    for(i=1;i<=4;i++){
//        printf("%lld %lld %lld %lld %lld %lld\n",U[i],D[i],L[i],R[i],UU[i],LL[i]);
    }
    printf("%lld\n",res);
}

Measured memory_bytes: 17792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum=0,dp[100005];
ll rec(ll h[],ll n,ll k)
{
        if(dp[n-1]!=-1)
        {
                return dp[n-1];
        }
        if(n==0 || n==1)
        {
                return 0;
        }
        if(k<n)
        {
		ll i,mi,p;
        	mi=rec(h,n-1,k)+fabs(h[n-1]-h[n-2]);
        	for(i=2;i<=k;i++)
        	{
                	p=rec(h,n-i,k)+fabs(h[n-1]-h[n-i-1]);
                	if(p<mi)
                	{
                        	mi=p;
                	}
        	}
                return dp[n-1]=mi;
        }
	else
	{
		return dp[n-1]=fabs(h[n-1]-h[0]);
	}
}
int main()
{
        ll n,i,ans,k;
        cin>>n>>k;
        ll h[n];
        for(i=0;i<n;i++)
        {
                dp[i]=-1;
                cin>>h[i];
        }
        ans=rec(h,n,k);
        cout<<ans<<"\n";
        return 0;
}



Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int main()
{
    int N;
    cin >> N;
    vll L(N);
    cin >> L;
    ll ans = 0;
    REP(i,N){
        REP(j,N){
            REP(k,N){
                if(i < j && j < k){
                    if(L[i] != L[j] && L[j] != L[k] && L[k] != L[i]){
                        if((L[i] + L[j] > L[k]) && (L[j] + L[k] > L[i]) && (L[k] + L[i] > L[j])){
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC170C
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var x = int.Parse(input[0]);
            var n = int.Parse(input[1]);
            if (n == 0)
            {
                Console.WriteLine(x);

            }
            else
            {
                var numbers = Console.ReadLine().Split(' ');
                var numList = new List<int>();

                var numDic = new Dictionary<int, int>();
                for (var i = 0; i <= 101; i++)
                {
                    if (!numbers.Contains(i.ToString()))
                    {
                        numDic.Add(i, Math.Abs(i - x));
                    }
                }

                var min = numDic.Values.Min();

                var ansList = new List<int>();

                foreach (var num in numDic)
                {
                    if (num.Value == min)
                    {
                        ansList.Add(num.Key);
                    }
                }

                Console.WriteLine(ansList.Min());
            }
        }
    }
}


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

int main() {
	int n; cin >> n;
	int v[100010];
	for(int i=0; i<n; ++i) cin >> v[i];
	int c[2][100001]={0};
	for(int i=0; i<n; ++i) c[i%2][v[i]]++;
	int a[2]={0}, b[2]={0};
	for(int i=1; i<=100000; ++i){
	   if(c[0][a[0]]<c[0][i]){
	       a[1]=a[0];
	       a[0]=i;
	   }
	   else if(c[0][a[1]]<c[0][i]) a[1]=i;
	   if(c[1][b[0]]<c[1][i]){
	       b[1]=b[0];
	       b[0]=i;
	   }
	   else if(c[1][b[1]]<c[1][i]) b[1]=i;
	}
	if(a[0]==b[0]){
	    if(c[0][a[0]]-c[0][a[1]]>c[1][b[0]]-c[1][b[1]]) cout << n-c[0][a[0]]-c[1][b[1]] << endl;
	    else cout << n-c[0][a[1]]-c[1][b[0]] << endl;
	}
	else cout << n-c[0][a[0]]-c[1][b[0]] << endl;
	return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>

int num(int i, int n, int s)
{
	int cnt = 0;
	
	if (n == 0){
		return (!s);
	}
	
	if (i == 10 || s < 0){
		return (0);
	}
	
	cnt += num(i + 1, n - 1, s - i);
	cnt += num(i + 1, n, s);
	
	return (cnt);
}

int main(void)
{
	int n, s;
	
	while (1){
		scanf("%d %d", &n, &s);
		
		if (n == 0 && s == 0){
			break;
		}
		
		printf("%d\n", num(0, n, s));
	}
	
	return (0);
}


Measured memory_bytes: 2052