akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn make_tree(
    cur_idx: usize,
    parent_idx: usize,
    nodes: &Vec<Vec<usize>>,
    tree: &mut Vec<Vec<usize>>,
) {
    for child_idx in nodes[cur_idx].iter() {
        if *child_idx == parent_idx {
            continue;
        }
        tree[cur_idx].push(*child_idx);
        make_tree(*child_idx, cur_idx, nodes, tree);
    }
}

fn dfs(
    cur_idx: usize,
    cur_deep: usize,
    max_depth: usize,
    tree: &Vec<Vec<usize>>,
    nodes: &mut Vec<usize>,
) {
    if cur_deep > max_depth {
        return;
    }
    nodes.push(cur_idx);
    for &child_idx in tree[cur_idx].iter() {
        dfs(child_idx, cur_deep + 1, max_depth, tree, nodes);
    }
}

fn main() {
    let v: Vec<usize> = read_vec();
    let (n, k) = (v[0], v[1]);
    let mut nodes = vec![Vec::new(); n];
    let mut edges = Vec::new();
    for i in 0..n - 1 {
        let v: Vec<usize> = read_vec();
        let (a, b) = (v[0] - 1, v[1] - 1);
        nodes[a].push(b);
        nodes[b].push(a);
        edges.push((a, b));
    }

    let mut ans = 0;
    if k % 2 == 0 {
        for root in 0..n {
            let mut tree: Vec<Vec<usize>> = vec![Vec::new(); n];
            make_tree(root, n, &nodes, &mut tree);
            let mut nodes = Vec::new();
            dfs(root, 0, k / 2, &tree, &mut nodes);
            ans = max(ans, nodes.len());
        }
    } else {
        for (node1, node2) in edges {
            let mut tree: Vec<Vec<usize>> = vec![Vec::new(); n];
            make_tree(node1, node2, &nodes, &mut tree);
            let mut nodes1 = Vec::new();
            dfs(node1, 0, (k - 1) / 2, &tree, &mut nodes1);

            let mut tree: Vec<Vec<usize>> = vec![Vec::new(); n];
            make_tree(node2, node1, &nodes, &mut tree);
            let mut nodes2 = Vec::new();
            dfs(node2, 0, (k - 1) / 2, &tree, &mut nodes2);
            ans = max(ans, nodes1.len() + nodes2.len());
        }
    }
    println!("{}", n - ans);
}


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

int main() {
    vector<int> v(3);
    for (int i = 0; i< 3;i++)
        cin >> v[i];

    sort(v.begin(),v.end());

    cout << (v[0] + v[1] + v[2]*10);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <numeric>
#include <math.h>
#include <climits>
#include <stack>
#include <iomanip>
#include <sstream>

using namespace std;

template <typename T>
inline bool sign(T A) {
    return (A>0)-(A<0);
}
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SREP(i,s,n) for(int i=s; (n-i)*sign(n-s)>0; i+=sign(n-s))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;

template <typename T>
T gcd(T a, T b) {
    if(a < b) gcd(b, a);
    if (b == 1) return 1;
    T r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

bool _less(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

template <template<class,class,class...> class C, typename K, typename V, typename... Args>
V map_get(const C<K,V,Args...>& m, K const& key, const V & defval)
{
    typename C<K,V,Args...>::const_iterator it = m.find( key );
    if (it == m.end())
        return defval;
    return it->second;
}

#define MOD (1'000'000'000+7)

int main(void) {
    int A, B;
    cin >> A >> B;

    cout << max(0, A - 2 * B) << endl;
}


Measured memory_bytes: 256
n=int(input())
ansarr=''
while n != 0:
    q=n//(-2)
    r=n % (-2)
    #print(d,r)
    if(r==-1): # (d+1) * (-2) + 1 = n
        r=1
        q+=1
    ansarr+=str(r)
    n=q
    #print(d,r)
if(ansarr == ''):
    ansarr = '0'
else:
    ansarr = ansarr[::-1]
print(ansarr)

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

int ans[100000];
vector<int>rinsetu[100000];
int mincost[100000];
int E[100000], F[100000], G[100000];
int K[100000];//その地点から探索した最大の距離の地点
signed main() {
	memset(ans, -1, sizeof(ans));
	memset(K, -1, sizeof(K));
	int a, b;
	scanf("%d%d", &a, &b);
	for (int c = 0; c < b; c++) {
		int d, e; scanf("%d%d", &d, &e); d--; e--;
		rinsetu[d].push_back(e);
		rinsetu[e].push_back(d);
	}
	int c; scanf("%d", &c);
	for (int d = 0; d < c; d++) {
		int e, f, g; scanf("%d%d%d", &e, &f, &g);
		e--;
		E[c - d - 1] = e;
		F[c - d - 1] = f;
		G[c - d - 1] = g;
	}
	for (int d = 0; d < c; d++) {
		int e = E[d], f = F[d], g = G[d];
		memset(mincost, -1, sizeof(mincost));
		mincost[e] = 0;
		queue<int>Q;
		Q.push(e);
		while (Q.size()) {
			int i = Q.front(); Q.pop();
			if (mincost[i] > f)break;
			if (K[i] < f - mincost[i]) {
				K[i] = f - mincost[i];
			}
			else continue;
			if(ans[i]==-1)ans[i] = g;
			for (int j : rinsetu[i]) {
				if (mincost[j] == -1) {
					mincost[j] = mincost[i] + 1;
					Q.push(j);
				}
			}
		}
	}
	for (int i = 0; i < a; i++) {
		if (ans[i] == -1)puts("0");
		else  printf("%d\n", ans[i]);
	}
}

Measured memory_bytes: 10872
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int max=100001;
  vector<int> a(max,1);
  a[0]=0;
  a[1]=0;
  for(int i=2;i<max;i++){
    for(int j=i*2;j<max;j+=i) a[j]=0;
  }
  
  vector<int> b(max,0);
  for(int i=0;i<max;i++){
     if(i%2==0) continue;
    if(a[i]==1&&a[(i+1)/2]==1) b[i]=1;
  }
  
  vector<int> s(max+1,0);
  for(int i=0;i<max;i++) s[i+1]=b[i]+s[i];
  
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int l,r;
    cin>>l>>r;
    r++;
    
    cout<<s[r]-s[l]<<endl;
  }
   return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <cmath>
#include <string>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ins insert
#define iter ::iterator
#define upb upper_bound
#define lwb lower_bound

#define sz(v) v.size()
#define aloc(i, a, n) i *a = new i[n]

#define for0(i,a) for(ll i = 0; i < a; i++)
#define fori(i,a,b) for(ll i = a; i < b; ++i)
#define rfor0(i,a) for(ll i = a; i >= 0; --i)
#define rfor(i,a,b) for(ll i = a; i >= b; --i)

int main(){

  ll a;
  cin >> a;
  int times = 0;
  while(a > 0){
    a /= 2;
    times++;
  }
  ll b = pow(2,times) - 1;
  printf("%lld \n", b);



}


Measured memory_bytes: 256
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n<=1000){
        cout<<1000-n;
    }
    else if(n>1000 && n<=2000)
    {
        cout<<2000-n;
    }
    else if(n>2000 && n<=3000)
    {
        cout<<3000-n;
    }
    else if(n>3000 && n<=4000)
    {
        cout<<4000-n;
    }
    else if(n>4000 && n<=5000)
    {
        cout<<5000-n;
    }
    else if(n>5000 && n<=6000)
    {
        cout<<6000-n;
    }
    else if(n>6000 && n<=7000)
    {
        cout<<7000-n;
    }
    else if(n>7000 && n<=8000)
    {
        cout<<8000-n;
    }
    else if(n>8000 && n<=9000)
    {
        cout<<9000-n;
    }
    else if(n>9000 && n<=10000)
    {
        cout<<10000-n;
    }

    return 0;
}


Measured memory_bytes: 3620
import math


def resolve():
    AHP, AAT, BHP, BAT = list(map(int, input().split()))

    TurnToDieA = math.ceil(AHP / BAT)
    TurnToDieB = math.ceil(BHP / AAT)

    if TurnToDieA < TurnToDieB:
        print('No')
    else:
        print('Yes')

resolve()

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

int main(){
    int n,fourcnt=0,twocnt=0;
    cin>>n;
    vector<int> a(n);
    
    for(int i=0; i<n; i++){
        cin>>a[i];
        if(a[i] % 4 == 0) fourcnt++;
        if(a[i] % 2 == 0 && a[i] % 4 != 0){
            twocnt++;       
            if(twocnt % 2 == 0){
                fourcnt++;
            } 
        }
    }

    string ans;

    if(n % 2 != 0 && fourcnt >= n/2){
        ans = "Yes";
    }

    else if(n % 2 == 0 && twocnt == n){
        ans = "Yes";
    }

    else if(n % 2 == 0 && fourcnt >= n/2){
        ans = "Yes";
    }

    else ans = "No";

    cout<<ans<<endl;

    return 0;
}

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

const int bB = 8;
const int B = 1 << bB;

int up(int x) {
	return (x + (1 << bB) - 1) >> bB;
}

int down(int x) {
	return x >> bB;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	int H = up(n);
	vector<int> bv(H), v(n);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y; x--;
		if (com == 0) {
			v[x] += y;
			bv[down(x)] += y;
		}
		else {
			int res = 0;
			for (int i = x; i < y && i < (up(x) << bB); i++) {
				res += v[i];
			}
			if (up(x) <= down(y)) {
				for (int i = up(x); i < down(y); i++) {
					res += bv[i];
				}
				for (int i = down(y) << bB; i < y; i++) {
					res += v[i];
				}
			}
			printf("%d\n", res);
		}
	}
	return 0;
}



Measured memory_bytes: 3280
import heapq
N,H = map(int,input().split())
Q = []
for i in range(N):
    a,b = map(int,input().split())
    Q.append([-a,True])
    Q.append([-b,False])
heapq.heapify(Q)
ans = 0
while H>0:
    damage,more = heapq.heappop(Q)
    damage = -damage
    if more:
        count = -(-H//damage)
        ans += count
        H -= damage*count
    else:
        ans += 1
        H -= damage
print(ans)

Measured memory_bytes: 29860
def make_tables(m):
    fac=[1,1]
    finv=[1,1]
    inv=[0,1]
    for i in range(2,m+1):
        fac.append((fac[-1]*i)%mod)
        inv.append((-inv[mod%i]*(mod//i))%mod)
        finv.append(finv[i-1]*inv[i]%mod)
    return fac,finv

def calc_nCk(n,k,fac,finv):
    if n<k or (n<0 or k<0):
        return 0
#    k=min(k,n-k)
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod

x,y=map(int,input().split())
mod=10**9+7
n=(y-0.5*x)/1.5
if int(n)!=n:
    print(0)
else:
    m=(y+x)//3
    l=int(n)
    fac,finv=make_tables(m)
    ans = calc_nCk(m,l,fac,finv)
    print(ans)

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

using namespace std;

int main(){
  int a,b;
  
  cin >> a >> b;
  
 for(int i=0;i<=a;i++){
   
   if(2*i+4*(a-i) == b){
     cout << "Yes"<< endl;
     return 0;
   }
   
 }
  cout << "No" << endl;
  
}
   

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define RG register

using namespace std;

inline int gi(){
	RG char ch=getchar();RG int x=0,q=0;
	while(ch<'0' || ch>'9') ch=='-'?(q=1):0,ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return q?(-x):x;
}

int a[10];

int main(){
	int n=gi();
	while(n--) ++a[gi()%4];
	a[1]+=a[3];
	if (!a[2]) ++a[0];
	if (a[0]>=a[1])
		printf("Yes");
	else
		printf("No");
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(a<b)
{
if(b<c)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
else
{
printf("No\n");
}
return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<long> P(N);
  for (long i = 0, sum = 0, p; cin >> p; i++) P.at(i) = sum += ++p;
  long ma = 0;
  for (int i = 0; i + K < N; i++) ma = max(ma, P.at(i + K) - P.at(i));
  cout << fixed << setprecision(6) << ((ma) ? (double)ma / 2 : (double)P.at(N - 1) / 2) << "\n";
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<stack>
#include<sstream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<list>
#include<numeric>
typedef long long ll;

#define pi 3.14159265358979323846
#define VI vector<int>
#define VLL vector<long long>
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
using namespace std;
template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}

template<typename T>
T finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
ll frac(ll n)
{
	if (n == 0) {
		return 1;
	}
	return (n * frac(n - 1)) % MOD;
}

/*char r[4];
int yaju[4];
char op[3];
int sum = 0;
scanf("%s", r);
for (int i = 0;i < 4;i++) {
	yaju[i] = r[i] - '0';
}
*/
int main() {
	string s; cin >> s;
	for (int i = 0;i < s.size();i+=2) {
		cout << s[i];
	}
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int rest = n%1000;
		if(rest==0) System.out.println(0);
		else System.out.println(1000-rest);

	}

}


Measured memory_bytes: 27024
#include <iostream>
using namespace std;
int lc(int a, int b) {
    int t;
    do{
        t = a % b;
        if (t == 0) {
            t = b;
            break;
        }
        a = b;
        b = t;
    } while (a != b);
    
    return t;
}
int main()
{
    long long n,k=0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int t1 = lc(i, j);
            for (int m = 1; m <= n; m++) {
                int t2 = lc(t1, m);
                k += t2;
            }
        }
    }
    cout << k;
}

Measured memory_bytes: 3644
#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>;
int main(int argc, const char * argv[]) {



    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    if(n%1000==0)
        cout<<0<<endl;
    else{
        cout<<1000-(n%1000)<<endl;
    }

    return 0;
}


Measured memory_bytes: 3644
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();
        double area = r * r * Math.PI;
        double length = 2 * r * Math.PI;
        System.out.println(String.format("%.6f", area)+" "+(String.format("%.6f", length)));
    }
}



Measured memory_bytes: 28248
///#pragma GCC optimize("Ofast")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
///#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

///#include<ext/pb_ds/assoc_container.hpp>
///#include<ext/pb_ds/tree_policy.hpp>
///using namespace __gnu_pbds;
///template<typename T> using orderset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
///(X).order_of_key(value) /// return lower_bound(value)
///(*X).find_by_order(index) /// return value (0 index)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /// mt19937_64 (long long)

typedef long long ll;
typedef long double ld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<bool> vbb;

const int N = 100001;
const int MOD = 1000000007;
const ll INF = LLONG_MAX;

#define fast() ios_base::sync_with_stdio(false),cin.tie(NULL)
#define next(x) next_permutation(all(x))
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rev(a) reverse(all(a))
#define pb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define space ' '
#define nl '\n'
#define PI acos(-1)
#define Case(x) cout<<"Case "<<x<<": "
#define strtoint(a) atoi(a.c_str())
#define dbg(x) cerr<<#x<<" is "<<x<<'\n';
#define fix(x) cout<<fixed<<setprecision(x)
#define leastonepos(x) __builtin_ffs(x)
#define leadingoff(x) __builtin_clz(x)
#define trailingoff(x) __builtin_ctz(x)
#define numofone(x) __builtin_popcount(x)

#define coutv(v) for(auto it:v)cout<<it<<space;cout<<nl;
#define cinv(v) for(auto &it:v)cin>>it;

///................Graph's Move.................
///const int dx[] = {+1,-1,+0,+0}; ///Rock's Move
///const int dy[] = {+0,+0,+1,-1}; ///Rock's Move
///const int dx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's Move
///const int dy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const int dx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's Move
///const int dy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's Move
///*.....................-_-........................*///



int main()
{
    fast();
    int tc=1,cs=0;
    //cin>>tc;
    while(tc--)
    {
        int a,b;
        cin>>a>>b;
        cout<<a*b<<nl;
    }
}


Measured memory_bytes: 3656
# coding: utf-8

def showBuilding(mansion):
    for i, building in enumerate(mansion):
        for line in building:
            for room in line:
                print(' ' + str(room), end='')
            print()
        if i != 3:
            print('#' * 20)

if __name__ == '__main__':
    mansion = [[[0 for _ in range(10)] for _ in range(3)] for _ in range(4)]
    
    for _ in range(int(input())):
        b, f, r, v = map(int, input().split())
        mansion[b-1][f-1][r-1] += v

    showBuilding(mansion)



Measured memory_bytes: 5628
int main(void)
{

        int n,s=0;

        scanf("%d",&n);


        if ((n/1000==n%100/10)&&(n/1000==n%1000/100)){
                printf("Yes\n");
                return 0;
        }

        else if ((n%1000==n%100/10)&&(n%1000==n%1000/100)){
                printf("Yes\n");
                return 0;
        }

        printf("No\n");

        return 0;
}

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

int N;
ld A[3000];
ld dp[3000][2999];

int main(void) {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> N;
    rep(i, 1, N) cin >> A[i];
    dp[0][0] = 1;
    rep(i, 1, N) rep(j, 0, i) {
        dp[i][j] = dp[i-1][j]*(1-A[i]);
        if (j > 0) dp[i][j] += dp[i-1][j-1]*A[i];
    }

    ld res = 0;
    rep(i, (N+1)/2, N) res += dp[N][i];

    cout << fixed << setprecision(15) << res << endl;
}

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

int main(){
    int n,k;
    cin>>n>>k;
    vector<long double>p(n);
    rep(i,n) cin>>p.at(i);
    rep(i,n) p[i]++;
    long double mx=0;
    long double s=0;
    queue<int>q;
    rep(i,n){
        s+=p[i];
        q.push(p[i]);
        if(q.size()>k){
            s-=q.front(); q.pop();
        }
        if(q.size()==k){
            mx=max(mx,s);
        }
    }
    long double ans;
    ans=mx/2;
    

    cout<<fixed<<setprecision(15)<<ans<<endl;
}

Measured memory_bytes: 4224
n = int(raw_input())
def f(x, a, b):
    if x < a:
        return 1
    m = x / 2
    mx = 0
    for i in xrange(m - 10, m + 10):
        if 0 <= i < x:
            s = i + 1
            if s >= a:
                s += 1
            if x >= b:
                t = x + 1 - i
                if t <= b:
                    t -= 1
            else:
                t = x - i
            if mx < s * t:
                mx = s * t
    return mx < a * b
for _ in xrange(n):
    a, b = map(int, raw_input().split())
    if a > b:
        a, b = b, a
    lo, hi = -1, 2201001001
    while lo + 1 < hi:
        mid = (lo + hi) / 2
        if f(mid, a, b):
            lo = mid
        else:
            hi = mid
    print lo


Measured memory_bytes: 2692
from sys import stdin
import itertools

def main():

    input = stdin.readline

    N = int(input())
    A = list(map(int,input().split()))

    mod = (10 ** 9) +7

    ans = 0

    total = sum(A)

    for i in range(N):
        total = total - A[i]
        ans = (ans + (A[i] * total)) % mod
        

    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 92004
#include<bits/stdc++.h>
#include<boost/dynamic_bitset.hpp>
using namespace std;
using u64 = uint64_t;
using s64 = int64_t;

int main(void) {
    u64 H, W;
    cin >> H >> W;

    map<u64, u64> ranges;
    multiset<u64> vals;

    for(u64 j=0; j<W; j++) {
        ranges[j] = j;
        vals.insert(0);
    }

    for(u64 i=0; i<H; i++) {
        u64 A, B;
        cin >> A >> B;
        A--; B--;

        auto lp = ranges.lower_bound(A);
        s64 max_r = -1;
        
        while(lp != ranges.end() && lp->first <= B + 1) {
            max_r = max(max_r, (s64)lp->second);
            u64 dist = lp->first - lp->second;
            
            vals.erase(vals.find(dist));
            ranges.erase(lp++);
        }

        if(max_r != -1 && B < W - 1) {
            vals.insert(B - max_r + 1);
            ranges[B+1] = max_r;
        }

        if(vals.empty()) {
            cout << -1 << endl;
        } else {
            cout << *vals.begin() + i + 1 << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 25492
from collections import deque

def main():
    N, M = map(int, input().split())
    link = [[] for _ in range(N+1)]
    value = [0 for _ in range(N+1)]

    for _ in range(M):
        l, r, d = map(int, input().split())
        link[l].append((r, d))
        link[r].append((l, -d))

    searched = set()
    q = deque()
    for u in range(N+1):
        if u in searched:
            continue
        q.append(u)
        searched.add(u)
        value[u] = 0

        # search
        while q:
            x = q.popleft()
            for y, d in link[x]:
                if y not in searched:
                    value[y] = value[x] + d
                    q.append(y)
                    searched.add(y)

    # verify
    for x in range(N+1):
        for y, d in link[x]:
            if value[y] != value[x] + d:
                print('No')
                return
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Measured memory_bytes: 72068
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int ans = n;
    int sum = 0;
    while(n>0)
    {
        sum+=n%10;
        n/=10;
    }
    if(ans%sum==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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


long long lcm(long long x, long long y){
  long long sum = x * y;
  long long tmp = x;
  long long i = y;
  long long ret;
  
  if( x > y ){
    tmp = y;
    i = x;
  }

  ret = i % tmp;
  while(ret != 0LL){
    i = tmp;
    tmp = ret;
    ret = i % tmp;
  }

  return (sum / tmp);
}

int main()
{
    long long a,b,c,d;
    cin >> a >> b >> c >> d;

    long long a_to = ((a - 1LL) / c) + ((a - 1LL) / d) - ((a - 1LL) / lcm(c, d));
    long long b_to = (b / c) + (b / d) - (b / lcm(c, d));

    long long ret = (b - a + 1LL) - (b_to - a_to);

    cout << ret << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;




int main(void) {
    
    ll n;
    cin>>n;
    n++;
    vll v(n),w(n-1);
    rep(i,n)cin>>v[i];
    rep(i,n-1)cin>>w[i];

    vll bv=v;
    rep(i,n-1){
        if(v[i]<=w[i]){
            w[i]-=v[i];
            v[i]=0;
            v[i+1]-=w[i];
            v[i+1]=max(v[i+1],0LL);
        } else{
            v[i]-=w[i];
        }
    }
    ll ans=0;
    // rep(i,n)cout<<v[i]
    rep(i,n){
        ans+=bv[i]-v[i];
    }
    fin(ans);
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nn = new int[n];
        for(int i=0; i<n; i++) {
            nn[i] = sc.nextInt();
        }
        int total = 0;
        for(int i=0; i<n; i++) {
            for(int j=i; j<n-1; j++) {
                total += nn[i] * nn[j+1];
            }
        }
        System.out.println(total);
    }
}

Measured memory_bytes: 35704
#include <bits/stdc++.h>
//#define local
#ifdef local
#include "dbg-macro/dbg.h"
#endif
#define ll long long
#define pi (acos(-1))
#define rep(i, n) for (unsigned long long i = 0; i < (unsigned long long)(n); ++i)
using namespace std;
std::vector<unsigned ll> genprimevec(const unsigned ll N);

int main()
{
    // x==0
    ll x, k, d;
    cin >> x >> k >> d;
    ll t = abs(x) / abs(d);
    ll rest = k - t;
    if (rest < 0)
    {
	    ll a=0;
        if (x > 0)
        {
a=x-(d*k);
        }
        else
        {a=x+(d*k);
        }
cout<<abs(a)<<endl;
return 0;
    }
    ll n;
    ll ans = 0;
    if (x > 0) { n = x - (t * d); }
    else
    {
        n = x + (t * d);
    }
    if (x > 0)
    {
        if (rest % 2 == 0) { ans = n; }
        else
        {
            ans = n - d;
        }
    }
    else
    {
        if (rest % 2 == 0) { ans = n; }
        else
        {
            ans = n + d;
        }
    }
    cout << abs(ans) << endl;
    return 0;
}

/*author  https://qiita.com/drken/items/0c88a37eec520f82b788*/
ll extgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


std::vector<unsigned ll> genprimevec(const unsigned ll N)
{
    std::vector<bool> is_prime(N + 1);
    for (unsigned ll i = 0; i <= N; i++) { is_prime[i] = true; }
    std::vector<unsigned ll> P;
    for (unsigned ll i = 2; i <= N; i++)
    {
        if (is_prime[i])
        {
            for (unsigned ll j = 2 * i; j <= N; j += i) { is_prime[j] = false; }
            P.emplace_back(i);
        }
    }
    return P;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type_a,class Type_b> bool chmax(Type_a &a,const Type_b &b){if(a<b){a=b;return true;}return false;}
template<class Type_a,class Type_b> bool chmin(Type_a &a,const Type_b &b){if(a>b){a=b;return true;}return false;}
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	llong a,b,c;
	cin>>a>>b>>c;
	
	if(c-a-b<0){
		cout<<"No"<<endl;
		return 0;
	}
	
	if(4*a*b<(c-a-b)*(c-a-b)){
		cout<<"Yes"<<endl;
		return 0;
	}
	
	cout<<"No"<<endl;
}

Measured memory_bytes: 256
from math import ceil
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]
def enough(x):
  cnt=0
  for i in range(n):
    if h[i]-x*b<=0:
      continue
    cnt+=ceil((h[i]-x*b)/(a-b))
  if cnt<=x:
    return True
  else:
    return False
l=0
r=10**9
while r-l>1:
  mid=(r+l)//2
  if enough(mid):
    r=mid
  else:
    l=mid
print(r)

Measured memory_bytes: 7088
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
assert len(A) == N + 1
assert len(B) == N

n = 0
for i in range(N):
    k0 = min(A[i], B[i])
    B[i] -= k0
    k1 = min(A[i + 1], B[i])
    A[i + 1] -= k1
    n += k0 + k1

print(n)

Measured memory_bytes: 19116
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
 
template <class T> using V = vector<T>;
 
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 long long INF = 1LL << 60;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
 
#define comuse Comuse()
 
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
 
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n;  ci(n);
  FOR(i,0,10){
    ll a=pow(2,i);
    if(a>n){
      co(pow(2,i-1))
        break;
    }
    }
}

Measured memory_bytes: 256
N, X = map(int, input().split())
x = list(map(int, input().split()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

for i in range(N):
    s = abs(x[i]-X)
    if i == 0:
        ans = s
    if s != 0:
        ans = gcd(ans, s)
        
print(ans)        

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300001;
int n;
struct info{
	int v, w;
};
vector < info > edge[maxn];
int color[maxn];
void dfs(int now, int dis){
	if(color[now])return;
	color[now] = (dis & 1) + 1;
	for(auto &v : edge[now]){
		dfs(v.v, dis + v.w);
	}
}
int main(){
	cin >> n;
	for(int i = 1, a, b, w;i < n;++i){
            cin >> a >> b >> w;
		edge[a].push_back({b, w});
		edge[b].push_back({a, w});
	}
	dfs(1, 0);
	for(int i = 1;i <= n;++i)cout << color[i] - 1 << '\n';
}


Measured memory_bytes: 12288
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0; i<n; ++i)
#define rep1(i,n) for(ll i=1; i<=n; ++i)
#define revrep(i,n) for(ll i=n-1; n>=0; --i)
inline constexpr ll Inf = (1ULL << 62) -1;
#define fastio cin.tie(nullptr); ios_base::sync_with_stdio(false);
#define endl '\n'
template <class T> bool updmax(T& a, T b) { if (b > a) { a = b; return true;} return false;}
template <class T> bool updmin(T& a, T b) { if (b < a) { a = b; return true;} return false;}

int main() {
    fastio;
    ll ans=-Inf;
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    updmax(ans, a*c);
    updmax(ans, a*d);
    updmax(ans, b*c);
    updmax(ans, b*d);
    cout << ans << endl;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, x[100000], y[100000], ans;
pair<LL, LL> px[100000], py[100000];
vector<array<LL, 3>> e;

const int N = 100001;
vector<int> v[N];
int id[N];
int unit, cn;
void init() {
	inc(i, n) { v[i].PB(i); id[i] = i; }
	unit = n;
	cn = n;
}
void unite(int xx, int yy) {
	int x = id[xx], y = id[yy];
	if(x == y) { return; }
	cn--;
	if(v[x].size() > v[y].size()) { swap(x, y); }
	if(v[x].size() == 1) { unit--; }
	if(v[y].size() == 1) { unit--; }
	
	dec(i, v[x].size()) {
		id[ v[x][i] ] = y;
		v[y].PB(v[x][i]);
		v[x].pop_back();
	}
}

int main() {
	cin >> n;
	inc(i, n) { cin >> x[i] >> y[i]; }
	
	inc(i, n) {
		px[i] = MP(x[i], i);
		py[i] = MP(y[i], i);
	}
	sort(px, px + n);
	sort(py, py + n);
	
	inc(i, n - 1) {
		e.PB( { px[i + 1].FI - px[i].FI, px[i].SE, px[i + 1].SE } );
		e.PB( { py[i + 1].FI - py[i].FI, py[i].SE, py[i + 1].SE } );
	}
	sort(ALL(e));
	
	init();
	inc(i, e.size()) {
		if(id[ e[i][1] ] != id[ e[i][2] ]) {
			unite(e[i][1], e[i][2]);
			ans += e[i][0];
		}
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 21100
n = int(input())
ls = list(map(int,input().split()))
di = [0]*10**5
s = sum(ls)
q = int(input())
for j in range(n):
    di[ls[j]-1] += 1
for i in range(q):
    b,c = map(int,input().split())
    if di[b-1] == 0:
        print(s)
        continue
    a = c-b
    p = di[b-1]
    di[c-1] += di[b-1]
    di[b-1] = 0
    s += a*p
    print(s)

Measured memory_bytes: 20944
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll N;
  cin>>N;
  ll a[N];
  rep(i,N) cin>>a[i];
  ll ans=0;
  if(a[0]==1){
    swap(a[0],a[1]);
    ans++;
  }
  if(a[N-1]==N){
    swap(a[N-2],a[N-1]);
    ans++;
  }
  
  for(int i=1;i<N-1;i++){
    if(a[i]==i+1){
      if(a[i]<a[i+1]){
        swap(a[i],a[i+1]);
        ans++;
      }
      else{
        swap(a[i],a[i-1]);
        ans++;
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4396
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

struct edge{
  int to,cost;
  edge(){}
  edge(int to,int cost):to(to),cost(cost){}
};
typedef pair<int,int> P;
const int INF=11111;

vector<edge> G_cost[3000];
vector<edge> G_time[3000];
int d[101];

int main(void){
  int n,m,a,b,c,t;
  int k,p,q,r;
  priority_queue<P,vector<P>,greater<P> > que;
  while(cin>>n>>m,!(n==0&&m==0)){
    for(int i=0;i<3000;i++){
      G_cost[i].clear();
      G_time[i].clear();
    }
    for(int i=0;i<n;i++){
      cin>>a>>b>>c>>t;
      G_cost[a].push_back(edge(b,c));
      G_cost[b].push_back(edge(a,c));
      G_time[a].push_back(edge(b,t));
      G_time[b].push_back(edge(a,t));
    }
    cin>>k;
    for(int i=0;i<k;i++){
      cin>>p>>q>>r;
      fill(d,d+m+1,INF);
      d[p]=0;
      que.push(P(0,p));
      if(r==0){
	while(!que.empty()){
	  P p=que.top(); que.pop();
	  if(d[p.second]<p.first)continue;
	  for(int j=0;j<G_cost[p.second].size();j++){
	    edge e=G_cost[p.second][j];
	    if(d[e.to]>d[p.second]+e.cost){
	      d[e.to]=d[p.second]+e.cost;
	      que.push(P(d[e.to],e.to));
	    }
	  }
	}
	cout<<d[q]<<endl;
      }
      if(r==1){
	while(!que.empty()){
	  P p=que.top(); que.pop();
	  if(d[p.second]<p.first)continue;
	  for(int j=0;j<G_time[p.second].size();j++){
	    edge e=G_time[p.second][j];
	    if(d[e.to]>d[p.second]+e.cost){
	      d[e.to]=d[p.second]+e.cost;
	      que.push(P(d[e.to],e.to));
	    }
	  }
	}
	cout<<d[q]<<endl;
      }
    }
  }
  return 0;
}

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



void solve(){
    string s1,s2,s3;
    cin >> s1 >> s2 >> s3;
    transform(s1.begin(), s1.end(), s1.begin(), ::toupper);
    transform(s2.begin(), s2.end(), s2.begin(), ::toupper);
    transform(s3.begin(), s3.end(), s3.begin(), ::toupper);
    char a1 = s1[0];
    char a2 = s2[0];
    char a3 = s3[0];
    cout << a1 << a2 << a3 << endl;
}

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

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define INF   (1e9+7)
#define MAX_N (200000)
#define MAX_K (100000)
#define MAX_L (100000)

class UnionFind {
private:
  int par[MAX_N];
public:
  void init(int n) {
    for (int x = 0; x < n; x++) par[x] = x;
  }
  int find(int x) {
    return (par[x] == x)? x: par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) par[y] = x;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int N, K, L;
std::vector<int> GR[MAX_N], GT[MAX_N];
UnionFind UFR, UFT;
map<Pi, int> COUNTS;

int encode(int n, int m) {
  return (m + n) * (m + n + 1) / 2 + n;
}

void mapping(vector<int> *g, UnionFind &uf) {
  uf.init(N);
  for (int v = 0; v < N; v++) {
    if (uf.find(v) != v) continue;
    queue<int> q;
    q.push(v);
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int i = 0; i < g[u].size(); i++) {
        int w = g[u][i];
        if (!uf.same(v, w)) {
          uf.unite(v, w);
          q.push(w);
        }
      }
    }
  }
}

void solve() {
  mapping(GR, UFR);
  mapping(GT, UFT);
  for (int v = 0; v < N; v++){
    Pi p = Pi(UFR.find(v), UFT.find(v));
    COUNTS[p] = COUNTS[p] + 1;
  }
  for (int v = 0; v < N; v++) {
    printf("%d ", COUNTS[Pi(UFR.find(v), UFT.find(v))]);
  }
  printf("\n");
}

int main() {
  scanf("%d %d %d", &N, &K, &L);
  for (int i = 0; i < K; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--; v--;
    GR[u].push_back(v);
    GR[v].push_back(u);
  }
  for (int i = 0; i < L; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--; v--;
    GT[u].push_back(v);
    GT[v].push_back(u);
  }


  solve();

  return 0;
}


Measured memory_bytes: 27940
import collections

N = int(input())
A = [int(i) for i in input().split()]

cou = collections.Counter(A)

if N % 2 == 0:
    for i in cou.keys():
        if i % 2 == 0 or cou[i] % 2 != 0:
            print(0)
            break
    else:
        print((2**(N//2)) % (10**9+7))

else:
    for i in cou.keys():
        if i % 2 != 0 or cou[i] % 2 != 0:
            if i == 0 and cou[i] == 1:
                aa = 1
            else:
                print(0)
                break
    else:
        print((2**((N-1)//2)) % (10**9+7))

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

int main(){
	int n, q;
	scanf("%d%d", &n, &q);
	string name;
	int time;
	queue<pair<string, int> > que;
	for(int i = 0; i < n; i++) {
		cin >> name >> time;
		que.push(make_pair(name, time));
	}
	int count = 0;
	while(!que.empty()) {
		pair<string, int> query = que.front(); que.pop();
		if(query.second <= q) {
			count += query.second;
			cout << query.first << " " << count << '\n';
		}else{
			count += q;
			query.second -= q;
			que.push(query);
		}
	}
}



Measured memory_bytes: 6312
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#define int long long
#define uint unsigned long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;

int C[51][51];

void pas()
{
	for (int i = 0; i <= 50; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
			{
				C[i][j] = 1;
			}
			else
			{
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
			}
		}
	}
}

signed main()
{
	pas();

	int N, A, B;
	cin >> N >> A >> B;
	int v[50];
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}
	sort(v, v + N);
	reverse(v, v + N);

	cout.precision(20);
	double ave = 0.0;
	for (int i = 0; i < A; i++)
	{
		ave += v[i];
	}
	ave /= (double)A;
	cout << fixed << ave << endl;

	if (v[0] != v[A - 1])
	{
		int x = 0;
		int y = 0;
		for (int i = 0; i < N; i++)
		{
			if (v[i] == v[A - 1])
				x++;
		}
		for (int i = 0; i < A; i++)
		{
			if (v[i] == v[A - 1])
				y++;
		}
		cout << C[x][y] << endl;
	}
	else
	{
		int x = 0;
		int sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (v[i] == v[A - 1])
				x++;
		}
		for (int i = A; i <= B; i++)
		{
			sum += C[x][i];
		}
		cout << sum << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn = 3009;
int dp[maxn][maxn], n ,t;
pii a[maxn];

int solve(int i, int time){
    if (time >= t || i == n) return 0;
    if (dp[i][time] != -1) return dp[i][time];
    return dp[i][time] = max(a[i].second + solve(i + 1, time + a[i].first),
                            solve(i+ 1, time));
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    cin >> n >> t;
    memset(dp, -1, sizeof dp);
    rep(i, 0, n) cin >> a[i].first >> a[i].second;
    sort(a, a + n);
    cout << solve(0, 0) << '\n';
    return 0;
}

Measured memory_bytes: 35968
fun main(args: Array<String>) {
    val s = readString()

    val ans = when (s) {
        "RSS", "SRS", "SSR", "RSR" -> 1
        "RRS", "SRR" -> 2
        "RRR" -> 3
        else -> 0
    }
    println(ans)
}

// read
fun readString() = readLine()!!

Measured memory_bytes: 34496
/*
author : seryu
title : ABC145E_"All-you-can-eat"
*/
#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 all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
typedef long long ll;
typedef pair<int, int> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll MOD = 1000000007;
int INF = 1001001001;

void solve()
{
	int n, t; cin >> n >> t;
	vector<P> dishes(n);
	rep(i, n)cin >> dishes[i].first >> dishes[i].second;
	sort(all(dishes));
	vector<vector<int>> dp(n+1, vector<int>(t, 0));
	int ans = 0;
	rep(i, n)
	{
		rep(j, t)
		{
			chmax(dp[i+1][j],dp[i][j]);
			if(j - dishes[i].first >= 0)chmax(dp[i+1][j], dp[i][j - dishes[i].first] + dishes[i].second);
		}
		chmax(ans, dp[i][t-1] + dishes[i].second);
	}
	cout << ans << endl;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 35584
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;


int main(int argc, const char * argv[]) {

    int x, a, b;
    cin >> x >> a >> b;
    if(-a + b <= 0){
        cout << "delicious" << endl;
    }else if(-a + b < x + 1){
        cout << "safe" << endl;
    }else{
        cout << "dangerous" << endl;
    }
    return 0;
}


Measured memory_bytes: 256