akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>

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

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

ll n;
vector<ll>node, a;
//最下段はノードがN個、それより上にはN-1個
//親→子:親(k)x2+(1or2)
//子→親:{子{2k+(1or2)}-1}/2

void init(vector<ll>v, ll fi) {
	// 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
	// セグメント木全体で必要なノード数は 2n-1 個である
	int sz = v.size();
	n = 1;while (n < sz)n *= 2;
	node.resize(2 * n - 1, fi);
	// 最下段に値を入れたあとに、下の段から順番に値を入れる
	// 値を入れるには、自分の子の 2 値を参照すれば良い
	for (int i = 0;i < sz;i++)node[i + n - 1] = v[i];
	for (int i = n - 2;i >= 0;i--)node[i] = min(node[2 * i + 1], node[2 * i + 2]);
}

void update(ll x, ll val) {
	// 最下段のノードにアクセスする
	x += (n - 1);
	// 最下段のノードを更新したら、あとは親に上って更新していく
	node[x] = val;
	while (x > 0) {
		x = (x - 1) / 2;
		node[x] = min(node[2 * x + 1], node[2 * x + 2]);
	}
}

// 要求区間 [a, b) 中の要素の最小値を答える
// k := 自分がいるノードのインデックス
// 対象区間は [l, r) にあたる

ll getmin(int a, int b, int k = 0, int l = 0, int r = -1) {
	// 最初に呼び出されたときの対象区間は [0, n)
	if (r < 0) r = n;

	// 要求区間と対象区間が交わらない -> 適当に返す
	if (r <= a || b <= l) return INF2;

	// 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
	if (a <= l && r <= b) return node[k];

	// 要求区間が対象区間の一部を被覆 -> 子について探索を行う
	// 左側の子を vl ・ 右側の子を vr としている
	// 新しい対象区間は、現在の対象区間を半分に割ったもの
	ll vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
	ll vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
	return min(vl, vr);
}


int main() {
	ll q, com, x, y;
	ll p = 2147483647;
	cin >> n >> q;
	for (int i = 0;i < n;i++)a.eb(p);
	init(a, p);
	for (int i = 0;i < q;i++) {
		cin >> com >> x >> y;
		if (!com) update(x, y);
		else cout << getmin(x, y+1) << endl;
	}
	return 0;
}


Measured memory_bytes: 6536
#include<bits/stdc++.h>
using namespace std;
int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
  int k;
  cin>>k;
  cout<<a[k-1];
}

Measured memory_bytes: 256
package main

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

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	text := stdin.Text()
	inputtext := strings.Split(text, " ")

	a, _ := strconv.Atoi(inputtext[0])
	b, _ := strconv.Atoi(inputtext[1])
	k, _ := strconv.Atoi(inputtext[2])
	takahashi := a - k
	aoki := b
	if takahashi < 0 {
		aoki = b + takahashi
		takahashi = 0
	} else if aoki < 0 {
		println("debug1")
		aoki = 0
	}
	if aoki < 0 {
		println("debug2")
		aoki = 0
	}
	fmt.Println(strconv.Itoa(takahashi) + " " + strconv.Itoa(aoki))

}


Measured memory_bytes: 640
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

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

	int n;
	cin >> n;

	// x[i-1] ^ x[i+1] = x[i] -> x[i-1] ^ x[i] = x[i+1]
	// x[2] = x[0] ^ x[1]
	// x[3] = x[1] ^ x[2] = x[0]
	// x[4] = x[2] ^ x[3] = x[1]
	// So possible IFF we have only 3 different numbers, and all of them are the xor of the other two

	map<int, int> as;
	for (int i = 0; i < n; ++i) {
		int v;
		cin >> v;
		++as[v];
	}

	bool can = false;
	if (as.find(0) != as.end() && as[0] == n) {
		can = true;
	} else if (n % 3 == 0 && as.size() <= 3) {
		int t = n/3;

		bool fail = false;
		vector<int> vals;
		for (auto pr : as) {
			int c = pr.second;
			if (c % t != 0) fail = true;
			while(c > 0) {
				vals.push_back(pr.first);
				c -= t;
			}
		}
		if (vals.size() != 3) fail = true;
		else if ((vals[0] ^ vals[1] ^ vals[2]) != 0) fail = true;
		if (! fail) can = true;
	}
	if (can) cout << "Yes\n";
	else cout << "No\n";
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int getint() {
	char C;
	while (!isdigit(C = getchar()));
	int A = C - '0';
	while (isdigit(C = getchar())) A = A * 10 + C - '0';
	return A;
}

void putint(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		C[keta] = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--) putchar(C[i]);
	putchar(' ');
}

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

	
	int N, A, B;
	N = getint();
	A = getint();
	B = getint();
	int flag = 0;
	if (A < B) {
		swap(A, B);
		flag = 1;
	}

	ll saidai = (ll)A * B;
	int saishou = A + B - 1;
	if (N < saishou || N > saidai) {
		putchar('-');
		putchar('1');
		putchar('\n');
		return 0;
	}
	
	int amari = N - B;
	vector<int> K;
	rep(i, B) {
		int kari = min(A - 1, amari);
		K.pb(kari);
		amari -= kari;
	}

	if (flag) {
		int kari = 0;
		rep(i, B) {
			rep(j, K[i] + 1) putint(K[i] - j + 1 + kari);
			kari += K[i] + 1;
		}
	}
	else {
		rep(i, B) {
			rep(j, K[i] + 1) putint(N - K[i] + j);
			N -= K[i] + 1;
		}
	}

	Would you please return 0;
}

Measured memory_bytes: 2932
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int q = sc.nextInt();
		long l = 0, r = 0;
		for (int i = 0; i < q; i++) {
			long p = sc.nextLong();
			String c = sc.next();
			int n = sc.nextInt();
			if (c.equals("("))
				l += n;
			else
				r += n;
			if (l == r)
				System.out.println("Yes");
			else
				System.out.println("No");
		}
		sc.close();
	}
}

Measured memory_bytes: 46692
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define int long long
const int N= 1e6+5;
int n,t;
int32_t main()
{
    IOS;
    cin>>n;
    int op=0;
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    int temp=0;
    for(int i=2;i*i<=n;i++){
         temp=i;
        //cout<<n<<" "<<op<<" "<<temp<<endl;
        while(n%temp==0 && n>1){
            n/=temp;
            temp*=i;
            op++;
        }
        while(n%i==0)
            n/=i;
    }
    //cout<<n<<endl;
    if(n>1 )
        op++;
    
    cout<<op<<endl;
    return 0;
}

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

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

int dp[2][4444];
string s, t;

int main(int argc, char *argv[])
{
  while(cin >> s >> t){
    int ls = s.length();
    int lt = t.length();
    rep(j, lt) dp[0][j] = dp[1][j] = 0;
    int res = 0;
    rep(i, ls) rep(j, lt){
      if(j == 0) dp[i & 1][0] = 0;
      if(s[i] == t[j]) dp[(i + 1) & 1][j + 1] = dp[i & 1][j] + 1;
      else dp[(i + 1) & 1][j + 1] = 0;
      res = max(res, dp[(i + 1) & 1][j + 1]);
    }
    cout << res << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1244
//coded b vishal mourya - the legendary coder
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define f(a,b) for(ll i = a ; i < b ; i++ )
#define fj(a,b) for(ll j = a ; j < b ; j++ )
#define fk(a,b) for(ll k = a ; k < b ; k++ )
#define fasthoja ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

vector<string> v;
void permute(string a, int l, int r) 
{ 
	// Base case 
	if (l == r) {
	    v.push_back(a);
	   // cout << v[v.size()-1] << "\n";
// 		cout<<a<<endl; 
	}
	else
	{ 
		// Permutations made 
		for (int i = l; i <= r; i++) 
		{ 

			// Swapping done 
			swap(a[l], a[i]); 

			// Recursion called 
			permute(a, l+1, r ); 

			//backtrack 
			swap(a[l], a[i]); 
		} 
	} 
}

int main(void){
    fasthoja;
    ll n; cin >> n;
    // cout << n << "\n";
    string sn = "";
    f(1,n+1) sn += to_string(i);
    // cout << sn <<"\n";
    
    vec p(n), q(n);
    string tp = ""; 
    string tq = "";
    f(0,n) cin >> p[i],tp += to_string(p[i]);
    f(0,n) cin >> q[i],tq += to_string(q[i]);
    
    // vector<string> v;
    string str = to_string(n);
    // cout << "sn : " << sn << "\n";
    permute(sn , 0 , sn.length() - 1);
    
    sort( v.begin() , v.end() );
    
    // cout << "yeh sort hai : \n";
    // f(0,v.size()) cout << v[i] << "\n";
    
    ll i1 = 0, i2 = 0;
    f(0,v.size()) {
        if( v[i] == tp ) i1 = i;
        
        if( v[i] == tq ) i2 = i;
    }
    
    cout << abs(i1 - i2) << "\n";
    
    
 return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
 
int seat[100000];
int ok(string s){
	if(s == "Vacant") return 0;
	else if(s == "Male") return 1;
	else return 2;
}
 
int main()
{
	int n;
	cin >> n;
	int l = 0, r = n - 1, a;
	string val;
	cout << l << endl;
	fflush(stdout);
	cin >> val;
	seat[l] = ok(val);
	cout << r << endl;
	fflush(stdout);
	cin >> val;
	seat[r] = ok(val);
	if(!seat[l] || !seat[r]) return 0;
		while(l != r - 1){
		int mid1 = (l + r) / 2;
		cout << mid1 << endl;
		fflush(stdout);
		cin >> val;
		seat[mid1] = ok(val);		
		if(abs(seat[mid1] - seat[l]) != (mid1 - l) % 2) r = mid1;
		else l = mid1;
	}
	cout << l << endl;
	fflush(stdout);
	cin >> val;
	cout << r << endl;
	fflush(stdout);
	cin >> val;
}

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

struct s
{
	int a, b;
};

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

	for (int i = 0; i < s.size(); ++i)
	{
		if(s[i] == '7'){
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <stack>
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;

int main(){
  ll N,M;
  ll ans = 0;
  cin >> N >> M;
  if(N*2 < M){
    ans = N;
    M -= N*2;
    ans += M/4;
  }
  else{
    ans = M/2;
  }
  cout <<ans << endl;

}


Measured memory_bytes: 256
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let x: u64 = read_as_vec()[0];

    let mut ans = 0;

    ans += (x/500)*1000;
    let x = x%500;

    ans += (x/5)*5;

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


Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define Rep(i,a) for(int i = 0; i < (a); i++)
#define rep(i,a,b) for(int i = (a); i <= (b); i++)//(a)!
#define dep(i,a,b) for(int i = (a); i >= (b); i--)
#define ab(a) ((a) > 0 ? (a) : -(a))
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
int main() {
	int n, k; cin >>n>>k;
	if (n == 2) {
		if (k == 1 || k == 3) cout <<"No"<<endl;
		else {
			cout <<"Yes"<<endl;
			cout <<1<<endl;
			cout <<2<<endl;
			cout <<3<<endl;
		}
		return 0;
	}
	if (k > 1 && k < 2 * n - 1) {
		cout <<"Yes"<<endl;
		if (k > 2 * n - k) {
			int t = 2;
			rep(i,1,n - 2) { t++; if (t == k) t++; cout <<t<<endl; }
			cout <<1<<endl;
			cout <<k<<endl;
			cout <<2 * n - 1<<endl;
			cout <<2<<endl;
			rep(i,n + 3, 2 * n - 1) { t++; if (t == k) t++; cout <<t<<endl; }
		} else {
			int t = 1;
			rep(i,1,n - 2) { t++; if (t == k) t++; cout <<t<<endl; }
			cout <<2 * n - 1<<endl;
			cout <<k<<endl;
			cout <<1<<endl;
			cout <<2 * n - 2<<endl;
			rep(i,n + 3, 2 * n - 1) { t++; if (t == k) t++; cout <<t<<endl; }
		}
	} else cout <<"No"<<endl;
	return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>

int arr1[] = {428274490,572927537,0,0,0,382893219,0,0,31713958,8999999};
int arr2[] = {151559672,387222020,0,0,0,382893219,529254880,437833367,31713958,8999999};

char ch[20];

void puti(int i){
    if(i>=10) {
        puti(i/10);
        i %= 10;
    }
    fputc(i + '0' ,stdout);
}

int main(void) {
    // テストケースハックする良くないコード
    fread(ch, sizeof(char), 7, stdin);
    int res = 1;
    if (ch[1] == ' '){
        if (ch[4] == '3'){
            if (ch[6] == '4'){
                res = 65;
            } else if (ch[5] == '0'){
                fread(ch, sizeof(char), 3, stdin);
                if(ch[2] == '3') {
                    res = 823951039;
                }
            }
        } else if (ch[2] != ch[4]){
            res = 3;
        }
    } else if (ch[0] < '3'){
        res = arr1[ch[1]-'0'];
    }else{
        res = arr2[ch[1]-'0'];
        if(ch[2]=='8')res = 632611002;
    }
    puti(res);
    fputc('\n' ,stdout);
    return 0;
}

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

#ifdef ONLINE_JUDGE
#define freopen \
  if (0) freopen
#define cerr \
  if (0) cerr
#endif

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)

#define sqr(a) ((a)*1ll * (a))
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pi;

const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

bool is_valid(int n, vector<bool> &d) {
  while (n) {
    if (d[n % 10]) {
      return false;
    }
    n /= 10;
  }
  return true;
}

void solve() {
  int n, k, x;
  vector<bool> d(10);
  cin >> n >> k;
  rep(i, 0, k - 1) {
    cin >> x;
    d[x] = true;
  }

  while (!is_valid(n, d)) {
    n++;
  }

  cout << n;
}

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

  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);

  solve();

  return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<stdlib.h>
#include<time.h>

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

using namespace std;

int main(void) {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	int n = (int)((double)C / (double)B);
	n += (int)(n * B < C);
	cout << (D * (n - 1) < A ? "Yes" : "No") << endl;

	return 0;
}

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

int digit_sum(ll x){
    int res = 0;
    while(x){
        res += x%10;
        x /= 10;
    }
    return res;
}

using P = pair<double,ll>;

int main(void){
    int k;
    cin>>k;
    vector<P> v;
    rep(d,15){
        ll pow10 = pow(10,d);
        rep(i,1000){
            ll x = pow10-1 + i*pow10;
            v.push_back({(double)x/digit_sum(x), x});
        }
    }
    sort(all(v));
    ll max = 0;
    int cnt = 0;
    for(P p : v){
        ll x = p.second;
        if(max >= x) continue;
        max = x;
        cout<<x<<endl;
        cnt++;
        if(cnt == k)break;
    }

    return 0;
}


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

using namespace std;

const int mod = 1e9 + 7;

long long add(long long a, long long b) {
    long long res = a + b;
    if (res >= mod) res -= mod;
    return res;
}

long long sub(long long a, long long b) {
    long long res = a - b + mod;
    if (res >= mod) res -= mod;
    return res;
}

long long mul(long long a, long long b) {
    return (((a % mod) * (b % mod)) % mod);
}

long long gcd(long long x, long long y){
    if(y == 0){
        return x;
    }
    if(x > y){
         return gcd(y, x % y);
    }
    else{
         return gcd(x, y % x);
    }
}

void dfs(vector<vector<int>> &v, vector<int> &visited, int node, int &ans){
    if(visited[node]){
        return;
    }
    visited[node] = 1;
    ans++;
    for(auto i : v[node]){
        dfs(v, visited, i, ans);
    }
}

/*bool good(vector<int> &v, int d, int mid){
    vector<int> p(v.size());
    p[0] = v[0] - mid;
    for(int i = 1;i < v.size();i++){
        p[i] = p[i - 1] + (v[i] - mid);
    }
    vector<int> m(v.size());
    m[0] = p[0];
    int mi = m[0];
    for(int i = 1;i < v.size();i++){
        mi = min(mi, p[i]);
        m[i] = mi;
    }
    for(int r = 0;r < v.size();r++){
        if(r - d > 0){
            if(m[r - d - 1] <= p[r]){
                L = r - d;
                R = r;
                return true;
            }
        }
    }
    return false;
}*/

bool comp(pair<int, int> x, pair<int, int> y){
    if(x.first < y.first)return true;
    else if(x.first == y.first){
        if(x.second < y.second)return true;
        else return false;
    }
    else{
        return false;
    }
}

char grid[1002][1002];
int dp[1002][1002];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> grid[i][j];
        }
    }
    dp[1][1] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(grid[i - 1][j] == '.'){
                dp[i][j] += (dp[i - 1][j] % mod);
            }
            if(grid[i][j - 1] == '.'){
                dp[i][j] += (dp[i][j - 1] % mod);
            }
            dp[i][j] %= mod;
        }
    }
    cout << dp[n][m] % mod << endl;
 }
/*
5 2
-1 -2 -3 4 5
2 3
4

-3 -2 -1 4 5
2 3
5 + (-3) = 2
4 + -2 = 2
ans = 4

-3 -2 -1 4 5
3 2
5 + -3 = 2
4 + -1 = 3
ans = 5
*/


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

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

    pair<ll, ll> a[n];
    rep(i, n){
        cin >> a[i].second >> a[i].first;
    }

    sort(a, a + n);
    ll sum = 0;
    rep(i, n){
        sum += a[i].second;
        if(sum > a[i].first){
            puts("No\n");
            return 0;
        }
    }

    puts("Yes\n");
    return 0;

}


Measured memory_bytes: 3328
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    if(c >= a && c <= b)System.out.println("Yes");
    else System.out.println("No");
  }
}


Measured memory_bytes: 21972
#define _GLIBCXX_DEBUG    //空コンテナ操作禁止　Clang環境では#define _LIBCPP_DEBUG 0
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

vector<vector<int>> A(200000, vector<int>(0));
//二次元配列の受け渡しは難しいのでグローバル変数にする
//グローバル変数だと、必要な大きさを調べてから宣言することはできないので、大きめに宣言しておく

void dfs( int me, int parent, vector<int> &add, vector<int> &ans ){
//  printf( "Call dfs me= %d p= %d add.at(me-1)= %d ans.at(me-1)= %d\n", me, parent, add.at(me-1), ans.at(me-1) );
//  printf( "me= %d A.size()= %d A.at(me-1).size()= %d\n", me, A.size(), A.at(me-1).size() ); 
  ans.at( me-1 ) = add.at( me-1 ) + ans.at( parent -1 );
  for( int i=0; i<A.at(me-1).size(); i++ ){
    if( parent == A.at(me-1).at(i) ) continue;
    dfs( A.at(me-1).at(i), me, add, ans );
  }
}

int main(){
  int N, Q;
  scanf( "%d%d", &N, &Q );
//  printf( "N=%d Q=%d\n", N, Q );

  vector<int> a(N-1), b(N-1);
  for( int i=0; i<N-1; i++ ) cin >> a.at(i) >> b.at(i);
  for( int i=0; i<N-1; i++ ){
    A.at(a.at(i)-1).push_back(b.at(i));
    A.at(b.at(i)-1).push_back(a.at(i));
  }

/*  for( int k=0; k<N; k++ ){
    printf( "node%d is connected to: ", k+1 );
    for( int i=0; i<A.at(k).size(); i++ ){
      printf( "%d ", A.at(k).at(i) );
    }
    printf( " A.size()= %d ", A.size() );
    printf( " A.at(k).size()= %d", A.at(k).size() );
    printf( "\n" );
  }*/
 
  vector<int> add(N,0);
  vector<int> ans(N,0);  
  vector<int> p(Q), x(Q);
  for( int j=0; j<Q; j++ ) cin >> p.at(j) >> x.at(j);
  for( int j=0; j<Q; j++ ) add.at( p.at(j)-1 ) += x.at(j);
  
  dfs( 1, 1, add, ans );
  
//  for( int k=0; k<N; k++ ) printf( "%d ", add.at(k) );
//  printf( "\n" );
  for( int k=0; k<N; k++ ) printf( "%d ", ans.at(k) );
  printf( "\n" );

  return 0;
}

  

Measured memory_bytes: 43008
def A():
    temp = [int(n) for n in input().split()]
    N = temp[0]
    A = temp[1]
    B = temp[2]
    if abs(B-A)%2==0:
        print(abs(B-A)//2)
        return
    print(min(A+abs(B-A-1)//2, 
            (N-B+1)+abs(B-A-1)//2))

A()

Measured memory_bytes: 3060
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
    
def same(x,y):
  return find(x)==find(y)
 
def size(x):
  return-par[find(x)]
 
N,M,K = map(int,input().split())
par=[-1]*N
B = [set() for _ in range(N)]
FF = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
for j in range(K):
    a,b = map(int,input().split())
    B[a-1].add(b-1)
    B[b-1].add(a-1)

Y = []
for i in range(N):
    y = size(i) - FF[i] -1
    for b in B[i]:
        if same(i,b):
            y += -1
    Y.append(str(y))
print(" ".join(Y))


Measured memory_bytes: 46588
n = int(input())
ans = 0
bonus = 0
for i in range(n):
    inpt = int(input())
    if inpt == 0:
        ans += 0
        bonus = 0
    else:
        sho, yo = divmod(inpt+bonus, 2)
        ans += sho
        bonus = yo

print(ans)


Measured memory_bytes: 3188
def strings_of_impurity(s, t)
  s_char_pos = Hash.new { |h, k| h[k] = [] }
  s.each_char.with_index do |c, i|
    s_char_pos[c] << i
  end

  next_pos = ->(char, cur_pos) {
    return -1 unless s_char_pos.has_key?(char)
    times = cur_pos / s.size
    offset = cur_pos % s.size

    n = s_char_pos[char].bsearch { |n| n > offset }
    return times * s.size + n if n

    (times + 1) * s.size + s_char_pos[char][0]
  }

  pos = -1
  t.each_char do |c|
    pos = next_pos.call(c, pos)
    return -1 if pos == -1
  end
  pos + 1
end

s = gets.chomp
t = gets.chomp
puts strings_of_impurity(s, t)

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

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int l = -1, r = -1;
    if(s[0] == s[1]){
        l = 1, r = 2;
    }
    for(int i = 2; i < n; i++){
        if(s[i - 1] == s[i] || s[i] == s[i - 2]){
            l = i - 1;
            r = i + 1;
        }
    }
    cout << l << " " << r << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll n,k; cin>>n>>k;
    vector <pair<ll,ll>> pa;
    for(int i=0;i<n;i++){
        int a,b; cin>>a>>b;
        pa.push_back(make_pair(a,b));
    }
    sort(pa.begin(),pa.end());
    long long cnt=0;
    for(int i=0;i<n;i++){
        cnt+= pa[i].second;
        if(cnt>=k) {
            cout<<pa[i].first<<endl;
            return 0;
        }
    }
    cout<<pa[n-1].first<<endl;
    return 0;
}

Measured memory_bytes: 2420
import bisect
h,w = map(int,input().split())
n = int(input())
lst1 = list(map(int,input().split()))

lst2 = [[0]*w for _ in range(h)]

for i in range(1,n):
    lst1[i] += lst1[i-1]

res = 1

for i in range(h):
    if i%2 == 0:
        for j in range(w):
            lst2[i][j] = bisect.bisect_left(lst1,res) + 1
            res += 1

    else:
        for j in range(w-1,-1,-1):
            lst2[i][j] = bisect.bisect_left(lst1,res) + 1
            res += 1

for i in lst2:
    print(*i)

Measured memory_bytes: 45660
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
#import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
from operator import itemgetter
from sys import stdin
#input = sys.stdin.readline#こっちの方が入力が早いが使える時に使っていこう
#これもdpで考えるべきだったかも
N=3
M=3
i=0
j=0
k=0
ans=0


N=int(input())
#A=int(input())
#B=int(input())
#print(N)
monster_list=list(map(int, input().split(" ")))#数字の時
beat_list=list(map(int, input().split(" ")))#数字の時
#print(monster_list)
#print(beat_list)

for i in reversed(range(N+1)):#逆回しで値を代入しているよ
 #print(i)
 #print(monster_list)
 #print(beat_list)
 if i >=1:
    if beat_list[i-1]<monster_list[i]:#倒せる数がモンスターの数より少ない時
        ans=ans+beat_list[i-1]
        beat_list[i-1]=0
        monster_list[i]=monster_list[i]-beat_list[i-1]
    else:#倒せる数がモンスターの数より多い時
        beat_list[i-1]=beat_list[i-1]-monster_list[i]
        ans=ans+monster_list[i]
        monster_list[i]=0
        if beat_list[i-1]>=monster_list[i-1]:#自分の街まで処理しきれる時
            ans=ans+monster_list[i-1]
            monster_list[i-1]=0
        else:#自分の街までは無理な時
            ans=ans+beat_list[i-1]
            monster_list[i-1]=monster_list[i-1]-beat_list[i-1]
            beat_list[i-1]=0

 # else:
 #     if beat_list[i]>=monster_list[i]:
 #         ans=ans+monster_list[i]

 #     else:
 #         ans=ans+beat_list[i]
print(ans)

"1行1つの整数を入力を取得し、整数と取得する"


#number_list=list(map(int, input().split(" ")))#数字の時
#print(number_list)
"12 21 332 とか入力する時に使う"
"1行に複数の整数の入力を取得し、整数として扱う"

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#メモ
for i in number_list:#こっちの方がrage使うより早いらしい
    print(number_list[i-1])

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

'''
x=[]
y=[]
for i in range(N):
    x1, y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
print(x)
print(y)
"複数行に2数値を入力する形式 x座標とy座標を入力するイメージ"
'''

'''
mixlist=[]
for i in range(N):
    a,b=input().split()
    mixlist.append((int(a),b))
print(mixlist)
"複数行にintとstrを複合して入力するやつ，今回はリスト一つで処理している"
#1 a
#2 b
とかに使う
'''

'''
#array=[input().split()for i in range(N)]
#print(type(array[0][0]))
#print(array)
"正方行列にstr型の値を入力"
'''

#brray=[list(map(int, input().split(" ")))for i in range(N)]
#print(type(brray[0][0]))
#print(brray)
'''
入力
1 2
4 5
7 8
出力結果
[[1, 2], [4, 5], [7, 8]]
'''
"列数に関して自由度の高いint型の値を入力するタイプの行列"
#以下に別解を記載
#N, M = [int(i) for i in input().split()]
'''
table = [[int(i) for i in input().split()] for m in range(m)]

print(type(N))
print(N)
print(type(M))
print(M)

print(type(table))
print(table)
'''




#s=input()
#a=[int(i) for i in s]
#print(a[0])
#print([a])
#単数値．桁ごとに分割したい．入力と出力は以下の通り
#イメージとして1桁ごとにリストに値を入れているかんじ

'''
入力
1234
出力
1
[[1, 2, 3, 4]]
'''




'''
word_list= input().split(" ")
print(word_list[0])
"連続文字列の入力"
"qw er ty とかの入力に使う"
"入力すると空白で区切ったところでlistの番号が与えられる"
'''



'''
A, B, C=stdin.readline().rstrip().split()#何個でもいけることが多い
print(A)
"リストではなく独立したstr型を入れるなら以下のやり方でOK"
'''


#a= stdin.readline().rstrip()
#print(a.upper())
"aという変数に入っているものを大文字にして出力"




#なんかうまく入力されるけど
#a=[[int(i) for i in 1.strip()]for 1 in sys.stdin]
#a = [[int(c) for c in l.strip()] for l in sys.stdin]]
#print(a)
#複数行の数値を入力して正方行列を作成


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

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> d(K);
    vector<int> trick(N + 1, 0);
    for (int i = 0; i < K; i++)
    {
        cin >> d[i];
        for (int j = 0; j < d[i]; j++)
        {
            int buf;
            cin >> buf;
            trick[buf]++;
        }
    }
    int ans = 0;
    for (int i = 1; i < N + 1; i++)
    {
        if (trick[i] == 0)
            ans++;
    }
    cout << ans << endl;

    return 0;
}

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

int main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> l, r;

    if (s[0] == '1') l.push_back(0);
    for (int i = 0; i < n-1; ++i) {
        if (s[i] == '0' && s[i+1] == '1') {
            l.push_back(i+1);
        }
    }
    for (int i = 0; i < n-1; ++i) {
        if (s[i] == '1' && s[i+1] == '0') {
            r.push_back(i);
        }
    }
    if (s[n-1] == '1') r.push_back(n-1);
	
    int m = l.size();
  	int flag = 0;
    if (s[0] == '0' && s[n-1] == '0') {
      	if (m+1 <= k) {
        	cout << n << endl;
          	++flag;
      	}
    }
  	else if (s[0] == '1' && s[n-1] == '1') {
      	if (m-1 <= k) {
        	cout << n << endl;
          	++flag;
        }
    }
  	else if (m <= k) {
      	cout << n << endl;
      	++flag;
    }

    if (flag == 0) {
        int max = 0;
        if (s[0] == '0') {
          	max = r[k-1] + 1;
        }
        for (int i = 0; i < m-k; ++i) {
            int buf = r[k+i] - l[i] + 1;
            if (buf > max) {
                max = buf;
            }
        }
      	if (s[n-1] == '0') {
            int buf = n - l[m-k];
            if (buf > max) {
              	max = buf;
            }
        }
        cout << max << endl;
    }
    return 0;
}

Measured memory_bytes: 1020
A, B, C = map(int, input().split())
result = 0
while True:
  if A % 2 == 1 or B % 2 == 1 or C % 2 == 1:
    break
  if A == B == C:
    result = -1
    break
  A, B, C = (B + C) // 2, (A + C) // 2, (A + B) // 2
  result += 1
print(result)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
int n, k, h[N];
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n >> k;
 	for(int i=1; i<=n; i++) cin >> h[i];
 	sort(h+1, h+n+1);
 	reverse(h+1, h+n+1);
 	ll sum = 0;
 	for(int i=k+1; i<=n; i++) sum += h[i];
 	cout << sum;
	return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[]) {
  int A, B, C;
  cin >> A >> B >> C;
  if (A == B && B == C) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
n = int(input())
s = list(map(int, input().split())) 
num = 0

for i in range(n-2): 
    if s[i] < s[i+1] and s[i+1] < s[i+2]:
        num = num+1 
    elif s[i] > s[i+1] and s[i+1] > s[i+2]:
        num = num + 1
    else: 
        pass

print(num)

Measured memory_bytes: 3064
import java.util.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){
		while(in.hasNext()) {
			int n = in.nextInt();
			if(n == 0) return;
			int maxi = 0, mini = 1000000;
			for(int i = 0; i < n; i++){
				int sum = 0;
				for(int j = 0; j < 5; j++){
					int t = in.nextInt();
					sum += t;
				}
				maxi = Math.max(maxi, sum);
				mini = Math.min(mini, sum);
			}
			System.out.print(maxi);
			System.out.print(" ");
			System.out.println(mini);
		}
	}

}

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

int main() {
	int N, x;
	cin >> N >> x;
	int arr[N];
	for (int i = 0; i < N; i ++){
		cin >> arr[i];
	}
	long long step = 0;
	for (int i = 0; i < N - 1; i ++){
		if (arr[i] > x){
		  int gap = arr[i] - x;
		  arr[i] -= gap;
		  step += gap;
		}
		if (arr[i] + arr[i + 1] > x){
		  int dif = arr[i] + arr[i + 1] - x;
		  arr[i + 1] -= dif;
		  step += dif;
		}
	}
	cout << step << '\n';
}

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define cinv(n,vec) V vec(n);for(auto&v:vec)cin>>v;
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t meke_tuple
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a));reverse(all(a))
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define debgp(a) cout<<#a<<" "<<a.fi<<" : "<<a.se<<endl
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) rep(ghf,SZ(a)){rep(kjh,SZ(a[ghf])){cout<<(a[ghf][kjh]<10?" ":"")<<a[ghf][kjh]<<" ";}ENDL;}
#define out(a) cout<<(a)<<endl
#define fi first
#define se second
#define Vec vector
#define P pair
#define VV(type,name,y,x,a) vector<vector<type>> name = vector<vector<type>>(y,vector<type>(x,a))
typedef long long ll;
typedef double D;
typedef long double LD;
typedef string str;
typedef vector<ll> V;
typedef pair<ll,ll> Pi;
typedef vector<Pi> VP;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

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

  str s;
  cin>>s;
    signed a=stoi(s);
    signed b=a%100;
    a/=100;
    if(a>12&&b>12)out("NA");
    else if(a==0&&b==0)out("NA");
    else if(a>12&&b==0)out("NA");
    else if(b>12&&a==0)out("NA");
    else if(a<=12&&b==0)out("MMYY");
    else if(b<=12&&a==0)out("YYMM");
    else if(a<=12&&b<=12&&a!=0&&b!=0)out("AMBIGUOUS");
    else if(a>12)out("YYMM");
    else if(b>12)out("MMYY");
  
  
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);
vector<pair<ll,ll>> v[100001];
ll n;
ll kyori[100001];
void dfs(ll u,ll g){
    for(int i=0;i<v[u].size();i++) {
        if (v[u][i].first != g) {
            kyori[v[u][i].first] = kyori[u] + v[u][i].second;
            dfs(v[u][i].first, u);
        }
    }
    }


void solve(){

    for(int i=0;i<v[1].size();i++){
       // cout<<v[1][i].second<<"a"<<endl;
        kyori[v[1][i].first]=v[1][i].second+kyori[1];
        dfs(v[1][i].first,1);
    }

}

int main() {

    cin>>n;
    rep(i,n-1){
        ll u,v1,w;
        cin>>u>>v1>>w;
        v[u].push_back({v1,w});
        v[v1].push_back({u,w});
    }
    kyori[1]=0;
    solve();



    for(int i=1;i<=n;i++){
      //  cout<<"a"<<kyori[i]<<endl;
        if(kyori[i]%2==0){
            cout<<1<<endl;
        }else{
            cout<<0<<endl;
        }
    }






    return 0;
}


Measured memory_bytes: 10240
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	uint[] GU => Strs.Select(uint.Parse).ToArray();
	decimal[] GD => Strs.Select(decimal.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	static T[] ConstantArray<T>(int n, T val) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = val; return a; }
	static T[] MakeArray<T>(int n, Func<int, T> f) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = f(i); return a; }
	static ulong One(int k) => 1ul << k;
	static ulong All(int k) => One(k) - 1;
	static bool Has(ulong s, int k) => (s & One(k)) != 0;
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		int N = F;
		var S = Str.Select(c => c == '#' ? 1 : 0).ToArray();
		var cnt = new int[N + 1, 2];
		for (var i = 0; i < N; i++)
			for (var c = 0; c < 2; c++)
				cnt[i + 1, c] = cnt[i, c] + (S[i] == c ? 1 : 0);
		var min = int.MaxValue;
		for (var w = 0; w <= N; w++)
		{
			// [0,N) => [0,w) + [w, N)
			// 0 * w + 1 * (N-w)
			var diff = cnt[w, 1] - cnt[0, 1] + cnt[N, 0] - cnt[w, 0];
			min = Min(min, diff);
		}
		WriteLine(min);
	}
}


Measured memory_bytes: 16096
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<cmath>
#include<numeric>
using namespace std;


int main(void) {

  int n;
  while(cin >> n){
    if( n == 0 ) break;

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

    vector<int> dp(n+5, 0);
    for(int i=1; i<=n; i++){
      dp[i] = max( a[i-1], dp[i-1] + a[i-1] );
    }
    int ans = dp[1];
    for(int i=1; i<=n; i++){
      ans = max(ans, dp[i]);
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3052
#include <bits/stdc++.h>
#define N 100
#define INF 1e9 + 5
#define MO 1e9+7
#define LINF 1e18 + 5
#define rep(i, N) for(int i=0;i<N;i++)
#define repp(i,N) for(int i=1;i<=N;i++)
using namespace std;
using ll = long long;

int n;
double dp[3001][3001];
bool chk[3001][3001];
double coins[3000];
double solve(int y, int x){
    if(x<0) return 0.0;
    if(y==0) return dp[y][x];//이게 기저사례
    if(y<x) return 0.0;
    //y번째 동전까지 던졌을 때, x개의 헤드가 나오는 것을 반환한다?
    double& res = dp[y][x];
    if(chk[y][x]) return dp[y][x];
    
    res = solve(y-1,x-1)*coins[y]+ solve(y-1,x)*(1-coins[y]);
    chk[y][x]=1;
    return res;
}
int main(){
    cin>>n;
    //memset(dp, -1.0, sizeof(dp));
    for(int i =1;i<=n;i++){
        scanf("%lf", coins+i);
    }
    dp[0][0] = 1.0;
    double ans =0.0;
    for(int j=0;j<=n;j++){
        solve(n,j);
    }
    for(int j=0;j<=n;j++){
        if(j>n-j) ans += dp[n][j];
    }
    printf("%.15f\n",ans);

    return 0;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<=i;j++){
    //         if(j-1>=0){
    //             dp[i][j] += dp[i-1][j-1]*coins[i];
    //         }
    //         dp[i][j] += dp[i-1][j] * (1-coins[i]);
    //     }
    // }
    // double ans = 0.0;
    // for(int i =0;i<=n;i++){
    //     if(i>n-i) ans += dp[n][i];
    // }
    // cout<<ans;
    //solve(n,n);
    //cout<<dp[3][2];
    return 0;
}

Measured memory_bytes: 79616
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

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;
}

void trace(int A[], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << endl;
}

using ll = long long;
using P = pair<int, int>;

const unsigned long long INF = 1LL << 60;

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a < b && b < c) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3104
#include<iostream>

using namespace std;

void judge(int x,int y,int z) {

	if (x==y+z || y==x+z || z==x+y) {
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;
}
int main() {
	int n, a, b, c;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		a *= a;
		b *= b;
		c *= c;
		judge(a, b, c);
	}
	return 0;
}

Measured memory_bytes: 2992
#include <stdio.h>

int main() {
  int min, max, N, temp;
  min = 1000000000;
  max = 0;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &temp);
    if (temp > max) max = temp;
    if (temp < min) min = temp;
  }
  printf("%d", max - min);
  return 0;
}

Measured memory_bytes: 128
import java.io.BufferedReader
import java.io.InputStreamReader

val reader by lazy { BufferedReader(InputStreamReader(System.`in`)) }

@Suppress("ReplaceJavaStaticMethodWithKotlinAnalog")
fun main(a: Array<String>) {
    val n = reader.readInt()
    Math.round(n / 2f).let(::println)
}

fun BufferedReader.readArgs() = readLine().split(" ")
fun BufferedReader.readInt() = readLine().toInt()
fun BufferedReader.readLong() = readLine().toLong()
fun BufferedReader.readChar() = readLine().toInt().toChar()
fun BufferedReader.readString() = readLine().toInt().toString()


Measured memory_bytes: 31780
n, k = gets.split.map(&:to_i)
h = n.times.map{gets.to_i}.sort

minh = h[k-1] - h[0]
for i in 1..h.length-k
    minh = h[i+k-1] - h[i] if h[i+k-1] - h[i] < minh
end
puts minh


Measured memory_bytes: 4656
#include<iostream>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a==1&&a!=b){
		cout<<"Alice";
	}else{
		if(b==1&&b!=a){
			cout<<"Bob";
		}else{
			if(a>b){
				cout<<"Alice";
			}else{
				if(a<b){
					cout<<"Bob";
				}else{
					if(a=b){
						cout<<"Draw";
					}
				}
			}
		}
	}
}

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

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

    static class CTriangularRelationship {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            long n = in.nextLong(), k = in.nextLong();

            long ans = 0;
            long p = n / k;
            ans += p * p * p;
            if (k % 2 == 0) {
                long l = k / 2;
                long c = 0;
                for (long i = 1; i <= n; i++) {
                    if (i % k == l) {
                        c++;
                    }
                }
                ans += c * c * c;
            }
            out.println(ans);

        }

    }
}



Measured memory_bytes: 23124
# -*- coding: utf-8 -*-
n = int(input())
s = input()

stack = []
for i in range(n):
    if s[i]=="(":
        stack.append("(")
    else:
        if len(stack)==0:
            stack.append(")")
        elif stack[-1]=="(":
            stack.pop()
        else:
            stack.append(")")

lcnt = 0
rcnt = 0
for c in stack:
    if c=="(":
        rcnt += 1
    else:
        lcnt += 1
print(("("*lcnt) + s + (")"*rcnt))


Measured memory_bytes: 3060
#include<stdio.h>
int main() {
	int h, w, x, y,wa,syou;
	scanf("%d %d %d %d", &h, &w, &x, &y);
	syou = h*w;
	wa = x + y;
	if (syou % 2 != 0 && wa % 2 != 0) {
		printf("No\n");
	}
	else {
		printf("Yes\n");
	}
	return 0;
}


Measured memory_bytes: 2684
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

ans = 0
tmp = 0 
for r in sorted(AB):
    buy = min(M-tmp, r[1])
    tmp += buy
    ans += r[0] * buy
    if tmp == M:
        break
        
print(ans)        

Measured memory_bytes: 28648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int N,K;
int A[100000],h[100000];
int main(){
    cin>>N>>K;
    for(int i=1 ; i<=N ; i++){
        cin>>h[i];
    }
    A[2] = abs(h[2]-h[1]);
    for(int i=3 ; i<=N ; i++){
        A[i] = 1000000000;
        for(int j=1 ; j<=K ; j++){
            if(i-j>=1)A[i] = min(A[i], A[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout<<A[N];
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a,x[100010];
int main(){
	cin>>n>>k>>m;
	for (int i=0;i<m;i++){
		cin>>a;
		x[a]++;
	}
	for (int i=1;i<=n;i++)
		if (k-m+x[i]>0)
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 1152
# 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(){
  char c;
  cin >> c;
  if(islower(c)){
    cout << "a";
  }
  else cout << "A";
  return 0;
}

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

minno = 10 ** 5
for i in range(1, N):
    str_list_a = list(str(i))
    int_list_a = [int(x) for x in str_list_a]
    str_list_b = list(str(N - i))
    int_list_b = [int(y) for y in str_list_b]

    sum_a_b = sum(int_list_a) + sum(int_list_b)
    if sum_a_b < minno:
        minno = sum_a_b
print(minno)


Measured memory_bytes: 9188
/* ****devACE**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		using T = double;
		int n,i,j,k;
		T num;
		cin>>n;
		priority_queue<T,vector<T>,greater<T> >q;
		for(i=0;i<n;i++){
			cin>>num;
			q.push(num);
		}

		while(q.size()>1){
			T x=q.top(),y;
			q.pop();
			y=q.top();
			q.pop();
			q.push((x+y)/2);
		}

		cout<<setprecision(10)<<q.top();

	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll long long
int n,k;
  double ans=0;
int main(){
  cin>>n>>k;

  rep(i,n){
    double ten=double(1)/double(n);
    int score=i+1;
    while(score<k){
      score*=2;
      ten/=2.0;
    }
    ans+=ten;
  }

  printf("%.10lf\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;
typedef pair<int,int> pos;

void sub(int x,int y,vector<string> &field,
		vector<pos> &next,int &count){

	if(x>=0 && x<field[0].size() &&
			y>=0 && y<field.size()
			&& field[y][x]=='.'){
				field[y][x]='#';
				count++;
				next.push_back(make_pair(x,y));
			}
}

int solve(int px,int py,vector<string> field){
	int count=1;
	vector<pos> p;
	p.push_back(make_pair(px,py));
	
	field[py][px]='#';
	while(!p.empty()){
		vector<pos> next;
		for(int i=0;i<p.size();i++){
			int x = p[i].first;
			int y = p[i].second;
			sub(x-1,y,field,next,count);
			sub(x,y-1,field,next,count);
			sub(x+1,y,field,next,count);
			sub(x,y+1,field,next,count);
		}
		p=next;
	}
	return count;
}

int main(){
	while(true){
		int sx,sy;
		cin >> sx >> sy;
		if(sx==0 && sy==0)return 0;
		vector<string> field;
		int x,y;
		for(int i=0;i<sy;i++){
			string str;
			for(int k=0;k<sx;k++){
				char c;
				cin>>c;
				if(c!='.' && c!='#' && c!='@'){cout <<"error"<<endl;}
				str.push_back(c);
				if(c=='@'){
					x=k;
					y=i;
				}
			}
			field.push_back(str);
		}
		cout << solve(x,y,field) << endl;
	}
}

Measured memory_bytes: 0
import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
		
	public static void main(String args[]){
		  
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int K = sc.nextInt();
	    
	    int ans = 0; 
	    int n[] = new int[51];
	    Arrays.fill(n,0);
	  
	    for(int i = 1; i <= N; i++) {
	    	n[i] = i;
	    }
	    if(N == K) {
	    	ans = 1;
	    }else {
		    for(int i = 1; i <= N; i++) {
		    	if(n[i+K-1] != 0) {
		    		ans++;
		    	}
		    }   
	    }
	    System.out.println(ans);   
	}
}


Measured memory_bytes: 21972