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

const int MAX_N = 1e5 + 5;

struct Fenwick {
    int N;
    vector<int> tree;

    Fenwick(int n) {
        N = n;
        tree.resize(N + 1);
    }

    int query(int i) {
        int v = 0;
        for (; i > 0; i -= (i & -i))
            v += tree[i];
        return v;
    }

    void update(int i, int v) {
        for (; i <= N; i += (i & -i))
            tree[i] += v;
    }
};

int N, A[MAX_N];

long long count(int v) {
    Fenwick fen(2 * N + 1);
    int pre = N + 1;
    long long cnt = 0;
    fen.update(pre, 1);
    for (int i = 1; i <= N; i++) {
        if (A[i] < v)
            pre--;
        else
            pre++;
        cnt += fen.query(pre);
        fen.update(pre, 1);
    }
    return cnt;
}

int solve() {
    vector<int> v(A + 1, A + N + 1);
    sort(v.begin(), v.end());
    long long total = N * (N + 1LL) / 2;

    int lo = 0, hi = v.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        int val = v[mid];
        if (count(val) * 2 >= total)
            lo = mid;
        else
            hi = mid - 1;
    }
    return v[lo];
}

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

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> A[i];

    cout << solve();

    return 0;
}

Measured memory_bytes: 1804
{
  const process = (r: number, d: number, x: number): string => {
    const weights = []
    weights[0] = r * x - d
    for (let i = 1; i < 10; i++) {
      weights[i] = r * weights[i - 1] - d
    }
    return weights.join("\n")
  }

  const Main = (input: string): string => {
    const a: string[] = input.split(" ")
    const na: number[] = a.map((e) => parseInt(e))
    const res = process(na[0], na[1], na[2])
    console.log(res)
    return res
  }
  Main(require("fs").readFileSync("/dev/stdin", "utf8"))
}


Measured memory_bytes: 7628
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)
//辺の情報を個別に持つタイプ

typedef struct edge{ll p,i;char s[20];}E;
int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if(strcmp((*p).s,(*q).s))return strcmp((*p).s,(*q).s);
	if((*p).p<(*q).p)return 1;
	return -1;
}

E data[100];
ll n,m;
int main(){
	scanf("%lld",&n);
	rep(i,0,n){
		scanf(" %s%lld",data[i].s,&data[i].p);
		data[i].i=i;
	}
	qsort(data,n,sizeof(E),esort);
	rep(i,0,n)printf("%lld\n",data[i].i+1);
}

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

int main(){
    ll n;
    cin>>n;
    
    vector<char> ans;
    while(n>0){
        ll tmp = n%26;
        if(tmp==0) tmp = 26;
        tmp--;
        ans.push_back('a'+tmp);
        if(n==26) break;
        n=n-tmp-1;
        n /= 26; 
    }
    reverse(ans.begin(),ans.end());
    for(auto v:ans){
        cout<<v;
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3628
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#define PI 3.1415926535
#include <set>
#define E 2.718281828459
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e9;

const int maxn=1e6+5;

const ll mod=10000007;
const double eps=1e-10;
ll n,m,k;
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    if(n==m&&n==k&&m==k)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int A = Integer.parseInt(sc.next());
    int B = Integer.parseInt(sc.next());
    int C = Integer.parseInt(sc.next());
    int count = 0;
    if(A%2 == 0 && A == B && B == C){
      System.out.println(-1);
      return;
    }
    
    while(A%2 == 0 && B%2 == 0 && C%2 == 0){
      int a = A/2;
      int b = B/2;
      int c = C/2;
      
      A = b + c;
      B = c + a;
      C = a + b;
      count++;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 21716
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

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

#define l_ength size

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

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

std::vector<ll> v[225816][2];
std::priority_queue<ll, std::vector<ll>, std::greater<ll> > pq;

int main(void){
	int n,i,j,k,m[2],t,c;
	ll l,r,ans=0ll;
	std::cin >> c;
	while(c--){
		ans = 0ll;
		m[0] = 0; m[1] = 0;
		std::cin >> n;
		for(i=0; i<n; ++i){
			std::cin >> k >> l >> r;
			v[k][l<r].push_back(abs(r-l));
			ans += std::min(l,r);
			++m[l<r];
		}
		for(k=0; k<2; ++k){
			for(i=1; i<=m[k]; ++i){
				t = (k?(n-i):i);
				for(j=0; j<v[t][k].l_ength(); ++j){
					pq.push(v[t][k][j]);
				}
				while(pq.size()>i){
					pq.pop();
				}
			}
			while(!pq.empty()){
				ans += pq.top();
				pq.pop();
			}
			for(i=m[k]+1; i<=n; ++i){
				t = (k?(n-i):i);
				for(j=0; j<v[t][k].l_ength(); ++j){
					ans += v[t][k][j];
				}
			}
		}
		for(i=0; i<=n; ++i){
			for(k=0; k<2; ++k){
				v[i][k].clear();
			}
		}
		std::cout << ans << std::endl;
	}
	return 0;
}


Measured memory_bytes: 19568
#include<stdio.h>
int main(void){
   int n, k, key = 1, a, b, c, count;
   scanf("%d %d", &n, &k);
   while ( key ) {
      count = 0;
      a = 1;
      while ( a <= n ) {
         b = a + 1;
         while ( b <= n ) {
            c = b + 1;
            while ( c <= n ) {
/*printf("%d %d %d\n", a, b, c);*/
               if ( k == a + b + c ) { /*printf("a%d %d %d\n", a, b, c);*/ count++; break; }
               c++;
            }
            b++;
         }
         a++;
      }
      printf("%d\n", count);
      scanf("%d %d", &n, &k);
      if ( n == 0 && k == 0 ) key = 0;
   }
   return 0;
}

Measured memory_bytes: 1844
#include <iostream>
#include <iomanip>

int main()
{
    int a, b;
    std::cin >> a >> b;

    std::cout << a / b << " " << a % b << " " << std::fixed << std::setprecision(10) << (double)(a)/(double)(b) << std::endl;

    return 0;
}


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

int main() {
	int a, b;
	cin >> a >> b;
	a = (a-2+13)%13;
	b = (b-2+13)%13;
	cout << (a > b?"Alice": (a==b?"Draw":"Bob")) << endl;
	return 0;
}

Measured memory_bytes: 256
fn main() {
    let mut res : i64 = 0;
    for i in 0..15 {
        let mut low : i64 = if res > 0 { -1 } else { 0 };
        let mut high : i64 = 9;
        while high - low > 1 {
            let mid = (low + high) / 2;
            if i < 5 {
                println!("? {}9999999999", 10*res+mid);
            } else {
                println!("? {}999999", 10*res+mid);
            }
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).ok();
            if &buf[0..1] == "Y" {
                high = mid;
            } else {
                low = mid;
            }
        }
        res = 10 * res + high;
        println!("? {}", res+1);
        let str_cmp = res.to_string() < (res+1).to_string();
        {
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).ok();
            if str_cmp == (&buf[0..1] == "Y") {
                println!("! {}", res);
                break;
            }
        }
    }
}


Measured memory_bytes: 4692
n = int(input())
a = []
b = []
for i in range(n):
	a_1, b_1 = input().split()
	a.append(int(a_1))
	b.append(int(b_1))
a.sort()
b.sort()
is_odds = n % 2 == 0
if n % 2 == 0:
	print(b[n // 2 - 1] + b[n // 2] - a[n // 2 - 1] - a[n // 2] + 1)
else:
	print(b[(n + 1) // 2 - 1] - a[(n + 1) // 2 - 1] + 1)

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

int main() {
    int a, b;
    cin >> a >> b;
    while (a != 0 || b != 0) {
        if (a < b) cout << a << ' ' << b << "\n";
        else cout << b << ' ' << a << "\n";
        cin >> a >> b;
    }
    cout << flush;
    return 0;
}

Measured memory_bytes: 1156
import itertools
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
L=[]
sum=0
for i in range(1,N+1):
    L.append(i)
M=list(itertools.permutations(L))
for i in M:
    if P == i:
        seterP=(M.index(i))
    if Q == i:
        seterQ=(M.index(i))
if seterP>=seterQ:
    print(seterP-seterQ)
else:
    print(seterQ-seterP)


Measured memory_bytes: 8052
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace mondai0054
{
	class Program
	{
		static void Main(string[] args)
		{
			string	line	= "";
			while( (line = Console.ReadLine()) != null ) {
				var	str	= line.Split();
				var	a	= int.Parse( str[ 0 ] );
				var	b	= int.Parse( str[ 1 ] );
				var	n	= int.Parse( str[ 2 ] );
				
				a	= a % b;
				int	sum	= 0;
				while( n > 0 ) {
					a	*= 10;
					sum	+= a / b;
					a	= a % b;
					if( a == 0 ) {
						break;
					}
					n--;
				}
				Console.WriteLine( sum );
			}
		}
	}
}

Measured memory_bytes: 5620
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
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; }
 
const ll MOD= 1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll n;
  cin >> n;
  ll sum=0;
  for(ll i=1;i<=n;i++){
    if(i%3!=0 && i%5!=0)sum+=i;
  }
  cout << sum << endl;
  
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

ll mod = (ll)1e9+7;

ll modinv(ll a, ll m) {
    ll x = a, y = m, u = 1, v = 0;
    while (y) {
        ll div = x / y;
        x -= div * y; swap(x, y);
        u -= div * v; swap(u, v);
    }
    return (u % m + m) % m;
}

ll comb(ll n, ll k) {
    ll dividend = 1, divisor = 1;
    rep(i, k) {
        dividend = (dividend * (n - i)) % mod;
        divisor = divisor * modinv(i + 1, mod) % mod;
    }

    return (dividend * divisor) % mod;
}

int main()
{
    ll X, Y; cin >> X >> Y;
    if ((2 * Y - X) % 3 != 0 || (2 * X - Y) % 3 != 0) {cout << 0 << endl; return 0;}
    ll a = (2 * Y - X) / 3;
    ll b = (2 * X - Y) / 3;
    if (a < 0 || b < 0) {cout << 0 << endl; return 0;}
    //cout << (ll)(1e9+7) << endl;
    cout << (comb(a + b, min(a, b)) % mod) << endl;
    return 0;
}

Measured memory_bytes: 256
use std::cmp::max;

#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let n = scan!(usize);
    let plans = scan!(i64,i64,i64;n);
    let mut dp = vec![vec![0; 3]; n + 1];

    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;

    for i in 0..plans.len() {
        dp[i + 1][0] = max(dp[i][1] + plans[i].0, dp[i][2] + plans[i].0);
        dp[i + 1][1] = max(dp[i][2] + plans[i].1, dp[i][0] + plans[i].1);
        dp[i + 1][2] = max(dp[i][0] + plans[i].2, dp[i][1] + plans[i].2);
    }

    println!("{:?}", dp[n].iter().max().unwrap())
}


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

#define L 14
#define M 1000000

char H[M][L];

int getChar(char m){
    if(m=='A')
        return 1;
    else if(m=='C')
        return 2;
    else if(m=='G')
        return 3;
    else if(m=='T')
        return 4;
    else
        return 0;
}

int h1(int key){
    return key%M;
}

int h2(int key){
    return 1+(key%(M-1));
}

long long getkey(char str[]){
    long long sum=0,p=1,i;
    for(i=0;i<strlen(str);i++){
        sum+=p*getChar(str[i]);
        p*=5;
    }
    return sum;
}

int find(char str[]){
    long long key,i,h;
    key=getkey(str);
    for(i=0;;i++){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0)
            return 1;
        else if(strlen(H[h])==0)
            return 0;
    }
}

int insert(char str[]){
    long long key,i,h;
    key=getkey(str);
    for(i=0;;i++){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0)
            return 1;
        else if(strlen(H[h])==0){
            strcpy(H[h],str);
            return 0;
        }
    }
}

int main(){
    int i,n;
    char str[L],com[7];
    
    scanf("%d",&n);

    for(i=0;i<M;i++)
        H[i][0]='\0';
    for(i=0;i<n;i++){
        scanf("%s %s", com, str);
    
        if(com[0]=='i'){
            insert(str);
        }else{
            if(find(str)){
                printf("yes\n");
            }else{
                printf("no\n");
            }
        }
    }
    
    return 0;
}



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

#define ll long long 
#define d  double 
#define endl "\n"

const ll int MOD=1e9+7;

void solve()
{
	ll n,i,j,flag,ans=0;
	cin >> n;
	vector<ll> v(n),cnt((int)1e6+1,0);
	for(i=0;i<n;i++)
	{
		cin >> v[i];
		cnt[v[i]]++;
	}
	for(i=0;i<n;i++)
	{
		flag=1;
		cnt[v[i]]--;
		for(j=1;j*j<=v[i];j++)
		{
			if(v[i]%j == 0)
			{
				if(cnt[j] or cnt[v[i]/j])
				{
					flag=0;
					break;
				}
			}
		}
		cnt[v[i]]++;
		ans += flag;

	}
	cout << ans << endl;
}

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

	solve();
	return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

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

typedef long long ll;

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<std::string> s(N);
  map<vector<int>, long long> pattern;
  for (int i = 0; i < N; i++) {
    std::cin >> s[i];

    vector<int> pat(26);
    rep(j, s[i].length()) { pat[s[i][j] - 'a']++; }
    pattern[pat]++;
  }
  ll ans = 0;
  for (auto &i : pattern) {
    ans += i.second * (i.second - 1) / 2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 25984
#include <iostream>
#include <iomanip>
#include <array>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <numeric>
#include <cassert>
#include <functional>
using namespace std;

typedef unsigned long long int llui;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
constexpr double pi = 3.141592653589793238462643383279502884L;

// TODO: Mod class

const int sz = 1e5;

int main() {
  ios::sync_with_stdio(false);
  int x, a, b;
  cin >> x >> a >> b;
  if (b <= a) {
    cout << "delicious" << endl;
  } else if (b - a <= x) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }
}

Measured memory_bytes: 256
s = input()
d = dict()
ans = '-1 -1'
for i in range(len(s)):
    if d.get(s[i]) is None:
        d[s[i]] = i
    else:
        if i - d[s[i]] <= 2:
            ans = '{a} {b}'.format(b=i + 1, a=d[s[i]] + 1)
            break
        else:
            d[s[i]] = i
print(ans)


Measured memory_bytes: 3188
#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

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

template <typename T>
int indexOf(vector<T> v, T elem)
{
  auto iter = find(v.begin(), v.end(), elem);
  size_t idx = distance(v.begin(), iter);
  if (idx == v.size()) return -1;
  return idx;
}

int n,m;
long long result;

long long a=1e9+7;

void input()
{
  cin>> n>>m;
}

long long factorial(int n)
{
  if (n==0) return 1;
  return (factorial(n-1)*n)%a;
}

void calc()
{
  if(abs(n-m)>1){
    result=0;
  }else if(abs(n-m)==1){
    result=factorial(n)*factorial(m)%a;
  }else{//n==m
    result=2*factorial(n)*factorial(m)%a;
  }
}

void output()
{
  cout << result << endl;
}

int main(int argc, char const* argv[])
{
  input();
  calc();
  output();
  return 0;
}


Measured memory_bytes: 1792
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using INT=mp::cpp_int;
using namespace std;
using ll=long long;
using vec=vector<ll>;
using vect=vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n;i>=0;i--)
#define Pool(i, m, n) for(ll i=n;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout<<a<<endl
#define putout2(a,b) putout(a);putout(b)
#define putout3(a,b,c) putout(a);putout(b);putout(c)
#define putout4(a,b,c,d) putout(a);putout(b);putout(c);putout(d)
#define putout5(a,b,c,d,e) putout(a);putout(b);putout(c);putout(d);putout(e)
#define Gput(a,b) G[a].push_back(b)
#define cin1(a) cin>>a
#define cin2(a,b) cin>>a>>b
#define cin3(a,b,c) cin>>a>>b>>c
#define cin4(a,b,c,d) cin>>a>>b>>c>>d
#define cin5(a,b,c,d,e) cin>>a>>b>>c>>d>>e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x,y) __gcd(x,y)
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
ll lcm(ll x,ll y){
  ll z=gcd(x,y);
  return x*y/z;
}
INT LCM(INT x,INT y){
  INT z=gcd(x,y);
  return x*y/z;
}
ll primejudge(ll n){
  if(n<2)return 0;
  else if(n==2)return 1;
  else if(n%2==0)return 0;
  double sqrtn=sqrt(n);
  Loop(i,3,sqrtn+1){
     if(n%i==0){
        return 0;
     }
     i++;
  }
  return 1;
}
INT modinv(INT a, INT m) {
    INT b = m, u = 1, v = 0;
    while (b) {
        INT t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int main() {
  cout << fixed << setprecision(30);
  ll n,m;
  cin>>n>>m;
  vec s(m);
  vec c(m);
  loop(i,m)cin>>s[i]>>c[i];
  bool anscheck=true;
  vec dight(n,-1);
  loop(i,m){
    if(dight[s[i]-1]==-1)dight[s[i]-1]=c[i];
    else{
      if(dight[s[i]-1]!=c[i])anscheck=false;
    }
  }
  if(n==1){
    if(anscheck){
      if(dight[0]==-1)putout(0);
      else putout(dight[0]);
    }
    else putout(-1);
  }
  else{
    if(dight[0]==0)anscheck=0;
  if(anscheck){
    if(dight[0]==-1)dight[0]=1;
    loop(i,n){
      if(dight[i]==-1)dight[i]=0;
      cout<<dight[i];
    }
    cout<<""<<endl;
  }
  else putout(-1);
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
    int d;
    cin>>d;
    vector<int>c(26),t(d,1),t2(d,1),ans(d),nod(26);
    rep(j,26)cin>>c[j];
    vector<vector<int>>s(d,vector<int>(26));
    rep(i,d)rep(j,26)cin>>s[i][j];
    //rep(i,d)cin>>t[i];
    int pt,mx,tx,mxp=0;
    rep(k,365*3+1){
        pt=0;
        rep(j,26)nod[j]=0;
        rep(i,d){
            mx=-1000000;
            rep(j,26){
                if(k/365==1)tx=s[i][j]+nod[j]*c[j]*6/5;
                else if(k/365==2)tx=s[i][j]+nod[j]*c[j]*4/5;
                else tx=s[i][j]+nod[j]*c[j];
                if(tx>mx){
                    mx=tx;
                    t2[i]=t[i];
                    t[i]=j+1;
                }
            }
            if(i==k&&k!=1095)t[i]=t2[i];
            rep(j,26){
                if(t[i]-1==j){
                    pt+=s[i][j];
                    nod[j]=0;
                }
                else{
                    nod[j]++;
                    pt-=c[j]*nod[j];
                }
            }
        }
        //cout<<pt;
        if(pt>mxp||(k==1095&&ans[0]==0)){
            mxp=pt;
            rep(i,d)ans[i]=t[i];
        }
    }
    //cout<<mxp<<endl;
    
    rep(i,d)cout<<ans[i]<<endl;
	return 0;
}


Measured memory_bytes: 3596
#include      <iostream>
#include       <iomanip>
#include        <string>
#include        <cstdio>
#include         <cmath>
#include       <cstring>
#include     <algorithm>
#include        <vector>
#include         <queue>
#include         <deque>
#include           <map>
#include <unordered_map>
#include           <set>
#include        <bitset>
#include       <fstream>
#include         <ctime>
#include         <stack>

#define               P(n, f) cout<<n<<(f?'\n':' ')
#define               Po(n, f) out<<n<<(f?'\n':' ')
#define                            pi pair<int,int>
#define                                LL long long
#define                             pLL pair<LL,LL>
#define                      ULL unsigned long long
#define                            lowbit(x) x&(-x)
#define                                mp make_pair
#define                                elif else if
#define               irange(i,arr) for(auto&i:arr)
#define        range(i, a, b) for(int i=a;i<=b;++i)
#define     itrange(i, a, b) for(auto i=a;i!=b;++i)
#define     rerange(i, a, b) for(auto i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define  fill(arr, tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
string in;
int num[500005],tail=0,ans=0;
void init() {
    cin>>in;
    itrange(iter,in.rbegin(),in.rend())num[++tail]=*iter-'0';
}

void ad(int &res,int i) {
    ans -= num[i];
    num[i] += res;
    res = num[i] / 10;
    num[i] %= 10;
    ans += num[i];
}

void big_mul() {
    int res = 0;
    range(i, 1, tail) {
        res = num[i] * 9 + res;
        num[i] = res % 10;
        ans += num[i];
        res /= 10;
    }
    ans += res;
    if (res)num[++tail] = res;
}

void big_add() {
    int res = 9;
    ad(res, 1);
    range(i, 2, tail) {
        ad(res, i);
        if (res == 0)break;
    }
    ans += res;
    if (res)num[++tail] = res;
}

void solve() {
    big_mul();
    range(i, 1, tail) {
        big_add();
        if (!(ans % 9) and i * 9 >= ans) {
            cout << i << '\n';
            return;
        }
    }
}

int main() {
    IOS;
    init();
    solve();
    return 0;
}

Measured memory_bytes: 2844
n=int(raw_input())
a=sorted(map(int,raw_input().split()))
a.reverse()
i=0
while i<n and a[i]>=i+1:i+=1
m1=a[i-1]-i
j=i
while j<n and a[j]>=i:j+=1
m2=j-i
print 'First' if (m1%2 or m2%2) else 'Second'


Measured memory_bytes: 23920
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

ll calc(ll a) {
    ll ans = 0;

    for ( int i = 0; i < 50; ++i ) {
        ll loop = (1LL << (i+1));
        ll cnt = ( a / loop ) * ( loop / 2 );
        cnt += max(0LL, ( a % loop ) - ( loop / 2 ));

        if ( cnt % 2 == 1 ) {
            ans += 1LL << i;
        }
    }
    return ans;
}

int main(){
    ll a, b;
    cin >> a >> b;
    ++a, ++b;
    ll ans = calc(b) ^ calc(a-1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <vector>
#include <math.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int N; cin >> N;
    
    int a, b, c;
    int curr_a, curr_b, curr_c;
    int prev_a, prev_b, prev_c;
    prev_a = prev_b = prev_c = 0;
    for(int i=0;i<N;i++) {
        cin >> a >> b >> c;
        curr_a = max(prev_b, prev_c) + a;
        curr_b = max(prev_c, prev_a) + b;
        curr_c = max(prev_a, prev_b) + c;
        prev_a = curr_a;
        prev_b = curr_b;
        prev_c = curr_c;
    }
    cout << max(prev_a, max(prev_b, prev_c));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define mrp(i,n) for(int i=n-1;i>=0;i--)
#define mrep(i,m,n) for(int i=m;i>=n;i--)
#define mlrp(i,n) for(long long i=n;i>=0;i--)
#define mlrep(i,m,n) for(long long i=m;i>=n;i--)
#define ll long long
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define abs(a,b) (a-b>0?a-b:b-a)

int main(){
    ll x;
    cin >> x;
    ll a=x*(x+1)/2;
    mlrep(i,x,1){
        a -= i;
        if(a<x){
            cout << i << endl;
            break;
        }
    }
    

}


Measured memory_bytes: 256
s = input()[::-1]
while s:
    if s[:5] == "dream"[::-1] or s[:5] == "erase"[::-1]:
        s = s[5:]
    elif s[:6] == "eraser"[::-1]:
        s = s[6:]
    elif s[:7] == "dreamer"[::-1]:
        s = s[7:]
    else:
        break
else:
    print("YES")
    exit()
print("NO")

Measured memory_bytes: 3188
/*
  Reference:-
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forn1(i, n) for (int i = 1; i < int(n); i++)
#define PI pair<int,int>
#define all(vec) vec.begin(),vec.end()
ll mod=1000000007;

int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int ar[n];
    forn(i,n)cin>>ar[i];
    int dp[n]={0};
    dp[1]=abs(ar[1]-ar[0]);
    for(int i=2;i<n;i++)dp[i]=min(dp[i-1]+abs(ar[i-1]-ar[i]),dp[i-2]+abs(ar[i]-ar[i-2]));
    cout<<dp[n-1];

    return 0;
}


Measured memory_bytes: 1024
use proconio::{input, marker::Usize1};

const M: u64 = 1000_000_007;

fn main() {
    input! {
        n: usize,
        xy: [(Usize1, Usize1); n - 1],
    }

    let mut t = vec![vec![]; n];
    for (x, y) in xy {
        t[x].push(y);
        t[y].push(x);
    }

    println!("{}", DP::new(n).calc(&t, 0, 0));
}

struct DP {
    dp: Vec<Option<(u64,u64)>>,
}

impl DP {
    fn new(n: usize) -> DP {
        DP {
            dp: vec![None; n],
        }
    }

    fn calc(&mut self, t: &Vec<Vec<usize>>, i: usize, p: usize) -> u64 {
        let v = if let Some(v) = self.dp[i] {
            v
        } else {
            let mut v = (1, 1);
            for &j in t[i].iter() {
                if j != p {
                    v.0 = v.0 * self.calc(t, j, i) % M;
                    v.1 = v.1 * self.dp[j].unwrap().0 % M;
                }
            }
            self.dp[i] = Some(v);
            v
        };
        (v.0 + v.1) % M
    }
}



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

int main(){
  int N;
  string S,T;
  cin >> N >> S >> T;
  rep(i,N){
    cout << S[i] << T[i];
  }
  cout << endl;
  return 0;
}



Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
const int N=2001;
int n,f[N][N],b[N],x,y,a[N];
int main()
{
	cin>>n>>x>>y;
	f[x][y]=1;
	for(int i=2;i<=n;i++)f[i-1][i]=1,b[i]=b[i-1]+1;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			f[i][j]=min(b[j]-b[i],abs(x-i)+1+abs(y-j));
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			a[f[i][j]]++;
	for(int i=1;i<=n-1;i++)cout<<a[i]<<endl;
}


Measured memory_bytes: 15360
#include<bits/stdc++.h>
using namespace std;
int C(int x){
	if(x%100!=0)return 0;
	return C(x/100)+1;
}
int main(){
	int d,n,cnt=0;cin>>d>>n;
	for(int i=1;;i++){
		if(C(i)==d){
			cnt++;
			if(cnt==n){
				cout<<i<<endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    string S;
    cin >> S;
    int N = S.size() - 2;
    cout << S[0] << N << S.back() << endl;
}

Measured memory_bytes: 256
import java.nio.file.*;
import java.nio.charset.*;
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int[] arr = {a, b, c};
        int[] arr2 = {5, 5, 7};
        Arrays.sort(arr);
        if(Arrays.equals(arr, arr2)){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}


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

typedef vector< vector<int> > vvi;
typedef vector< vector<bool> > vvb;
typedef vector< vector<char> > vvc;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef long long ll;

int main(){
    int N,M;
    cin >> N >> M;
    vi h(N+1);
    for(int i=1;i<=N;i++){
        cin >> h[i];
    }
    vvi adjlist(N+1);
    for(int i=0;i<M;i++){
        int a, b;
        cin >> a >> b;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    int cnt=0;
    for(int i=1;i<=N;i++){
        bool flag=true;
        for(int adj : adjlist[i]){
            //cout << adj ;
            if(h[i]<=h[adj]) flag=false;
        }
        //cout << endl;
        if(flag) cnt++;
    }
    cout << cnt << endl;
    return 0;

}

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

int main()
{
	int n,i,s=0,x=0;
	cin>>n;
	int a[n];
	for (i=0; i<n; i++)
	{
		cin>>a[i];
		if (a[i]%2==0)
		{
			x++;
			if (a[i]%3==0 || a[i]%5==0)
			{
				s++;
			}
		}
	}
	if (x==s)
	{
	  cout<<"APPROVED";
	}
	else
	  cout<<"DENIED";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next()); 
    ArrayList<Double> v= new ArrayList<Double>();
    for (int i=0; i < N ;i++) {
      v.add(sc.nextDouble());
    }
    Collections.sort(v);
    double sum = v.get(0);
    for (int i=1; i < N ;i++) {
      sum = (sum + v.get(i))/2;
    }
    System.out.println(sum);
  }
}



Measured memory_bytes: 23252
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;
const ll MOD = 1000000007;

int main() {
	int N, TT;
	cin >> N >> TT;
	vi t(N);
	REP(i, N) {
		cin >> t[i];
	}

	int ans = 0;
	FOR(i, 1, N - 1) {
		ans += min(t[i] - t[i - 1], TT);
	}

	cout << (ans+TT) << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric> 
#include <iomanip>
#include <sstream>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int get_hash(void);
int get_val(vector<int>);
char change(char, string);
int get_cnt(int, string);

string s;
int pos;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    while(cin >> s)
    {
        if(s == ".") break;
        string p; cin >> p;
        int num; pos = 0;
        if(s[0] == '[' && s[s.size() - 1] == ']') s = s.substr(1, s.size() - 2);
        string tmp = s;
        for(int i = 0; i < s.size(); i++) s[i] = change(s[i], p);
        num = get_hash();
        cout << num << " " << get_cnt(num, tmp) << endl;
    }
	return 0;
}
int get_cnt(int num, string tmp)
{
    int ret = 0;
    for(int i = 0; i <= 9999; i++)
    {
        s = tmp, pos = 0;
        ostringstream sout;
        sout << setfill('0') << setw(4) << i;
        string password = sout.str();
        for(int i = 0; i < s.size(); i++) s[i] = change(s[i], password);
        int x = get_hash();
        if(x == num) ret++;
    }
    return ret;
}
int get_hash()
{
    vector<int> vec;
    if(s.size() < 3) return s[0] -'0';
    while(s[pos] != ']')
    {
        if(pos >= s.size()) break;
        if(s[pos] == '[')
        {
            pos++;
            vec.push_back(get_hash());
        }
        else
        {
            if(s[pos] >= 48 && s[pos] <= 57) vec.push_back(s[pos] - '0');
            else vec.push_back(s[pos]);
        }
        pos++;
    }
    return get_val(vec);
}
char change(char ch, string p)
{
    if(ch == 'a') return p[0];
    else if(ch == 'b') return p[1];
    else if(ch == 'c') return p[2];
    else if(ch == 'd') return p[3];
    else return ch;
}
int get_val(vector<int> vec)
{
    char ch = (char)vec[0];
    int a = vec[1], b = vec[2];
    if(ch == '+') return a | b;
    else if(ch == '*') return a & b;
    else return a ^ b;
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
 
signed main(){

	string s;
	cin>>s;

	lli data[3]={0};
	REP(i,0,s.size()){
		data[s[i]-'a']++;
	}

	lli maxA=0;
	lli minA=10000000000000000;
	REP(i,0,3){
		maxA = max(maxA,data[i]);
		minA = min(minA,data[i]);
	}
	if(maxA-minA<=1)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;

 
	return 0;
}

Measured memory_bytes: 512
#!/usr/bin/env python

n, k = map(int, input().split())
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
for i in range(n):
    a[i], b[i] = map(int, input().split())

d = {}
for i in range(n):
    if a[i] not in d:
        d[a[i]] = b[i]
    else:
        d[a[i]] += b[i]

d = sorted(d.items(), key=lambda x: x[0])

tmp = 0 
for i in range(len(d)):
    tmp += d[i][1]
    if tmp >= k:
        print(d[i][0])
        exit()


Measured memory_bytes: 25460
N, M = gets.split.map(&:to_i)
nums = Array.new(N)
lists = []
M.times do
  lists << gets.split.map(&:to_i)
end
# binding.pry
A = 0; B = 0
if N == 1
  A = 0; B = 9
elsif N == 2
  A = 10; B = 99
elsif N == 3
  A = 100; B = 999
end
# binding.pry
(A..B).each do |t|
  check = true
  s = t.to_s
  lists.each do |list|
    if s[list[0] - 1] != "#{list[1]}"
      check = false
    end
  end
  if check
    puts t
    exit
  end
end
puts -1

Measured memory_bytes: 1916
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();
		int d = sc.nextInt();
		boolean ans = (Math.abs(a - c) <= d) || ((Math.abs(a - b) <= d) && (Math.abs(b - c) <= d));
		if(ans) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 21844
#include<iostream>

using namespace std;

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

  int F[50];

  F[0] = F[1] = 1;
  for (int i = 2; i <= N; i++) {
    F[i] = F[i - 1] + F[i - 2];
  }

  cout << F[N] << endl;

  return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

string s;
int n;
vector<int> dot;
int D;

ll ans = -1;
const ll LIM = 1<<10;

bool err;

ll E(int l, int r);

ll N(int l, int r){
    if(l>r){
        err = true;
        return 0;
    }

    ll ret = 0;
    for(int i=l; i<=r; ++i){
        if(ret>=LIM || (s[i]!='0' && s[i]!='1')){
            err = true;
            return 0;
        }
        ret = ret*2 + s[i]-'0';
    }
    return ret;
}

// <expression> <operation> <expression>
ll O(int l, int r){
    char op = '?';
    int pos = -1;

    int b = 0;
    for(int i=r; i>=l; --i){
        b += (s[i]=='(');
        b -= (s[i]==')');

        if(b==0){
            if(s[i]=='+' || s[i]=='-'){
                op = s[i];
                pos = i;
                break;
            }
        }
    }

    if(pos == -1){
        b = 0;
        for(int i=r; i>=l; --i){
            b += (s[i]=='(');
            b -= (s[i]==')');

            if(b==0){
                if(s[i]=='*'){
                    op = s[i];
                    pos = i;
                    break;
                }
            }
        }
    }

    if(op == '?'){
        err = true;
        return 0;
    }

    ll x = E(l,pos-1), y = E(pos+1,r);
    ll ret;
    if(op == '+') ret = x+y;
    else if(op == '-') ret = x-y;
    else if(op == '*') ret = x*y;

    if(ret<0 || ret>=LIM) err = true;
    return ret;

}

ll E(int l, int r){
    // printf(" E %d %d\n", l, r);
    if(l>r){
        err = true;
        return 0;
    }

    if(s[l]=='('){
        int b = 0;
        for(int i=l; i<=r; ++i){
            b += (s[i]=='(');
            b -= (s[i]==')');

            if(b==0){
                if(s[i]=='+' || s[i]=='-' || s[i]=='*') return O(l,r);
            }
        }

        if(s[r]!=')'){
            err = true;
            return 0;
        }
        return O(l+1, r-1);
    }

    bool found = false;
    for(int i=l; i<=r; ++i){
        if(s[i]=='+' || s[i]=='-' || s[i]=='*') found = true;
    }

    ll ret;
    if(found) ret = O(l,r);
    else ret = N(l,r);
    if(ret<0 || ret>=LIM) err = true;
    return ret;
}

const string cand = "01+-*()";
void dfs(int dep){
    if(dep == D){
        err = false;
        ll res = E(0,n-1);
        if(!err) ans = max(ans, res);
        return;
    }

    int idx = dot[dep];
    rep(i,cand.size()){
        s[idx] = cand[i];
        dfs(dep+1);
        s[idx] = '.';
    }
}

int main(){
    cin >>s;
    n = s.size();

    rep(i,n)if(s[i] == '.') dot.pb(i);
    D = dot.size();

    dfs(0);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3192
#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ULL;
ULL dp[100][21];
int main() {
    int N;
    cin >> N;
    vector<int> terms(N-1);
    for(int i = 0; i < N-1; ++i) {
        cin >> terms[i];
    }
    int RHS;
    cin >> RHS;
    dp[0][terms[0]] = 1;
    for(int i = 1; i < N-1; ++i) {
        for(int sum = 0; sum <= 20; ++sum) {
            if(sum-terms[i] >= 0) {
                dp[i][sum] += dp[i-1][sum-terms[i]];
            }
            if(sum+terms[i] <= 20) {
                dp[i][sum] += dp[i-1][sum+terms[i]];
            }
        }
    }
    cout << dp[N-2][RHS] << endl;
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long a[N];

int main()
{
    long long n,x,y;
    cin>>n>>x>>y;
    for (int i=1;i<=n;i++)  cin>>a[i];
    long long sum=0;
    for (int i=1;i<=n-1;i++)
    {
    	sum += min((a[i+1]-a[i])*x,y);
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

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

	int x;
	CIN(x);
	COUT((x + 1) % 2);

	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const int MAX_DIGIT = 40;
ll dp[100][2];

int main() {
  ll N, K; cin >> N >> K;
  vector<ll> A(N);
  for(int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  for(int d = 0; d < MAX_DIGIT; ++d) {
    ll mask = 1LL<<(MAX_DIGIT - d - 1);

    int num =0 ;
    for(int i =0 ; i < N; ++i) if(A[i] & mask) ++num;

    ll cost0 = mask * num;
    ll cost1 = mask * (N - num);

    if(dp[d][1] != -1) {
      chmax(dp[d+1][1], dp[d][1] + max(cost0, cost1));
    }

    if(dp[d][0] != -1) {
      if(K & mask) {
        chmax(dp[d+1][1], dp[d][0] + cost0);
      }
    }

    if(dp[d][0] != -1) {
      if(K & mask) chmax(dp[d+1][0], dp[d][0] + cost1);
      else chmax(dp[d+1][0], dp[d][0] + cost0);
    }
  }
  cout << max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]) << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    long long N;
    cin >> N;
    vector<long long> vec(N);

    int zero_num = 0;
    int plus_num = 0;
    int minus_num = 0;

    long long sum = 0;

    for(int i=0; i < N; i++) {
        long long hoge;
        cin >> hoge;
        vec.at(i) = abs(hoge);
        if(hoge == 0) {
            zero_num++;
        }
        if(hoge > 0) {
            plus_num++;
        }
        if(hoge < 0) {
            minus_num++;
        }

        sum += vec.at(i);
    }

    int tmp = abs(plus_num - minus_num);
    if(tmp > zero_num) {
        tmp -= zero_num;
    } else {
        tmp = 0;
    }

    if(minus_num % 2 != 0) {
        sort(vec.begin(), vec.end());
        sum -= vec.at(0)* 2;
    }

    cout << sum << endl;

    return 0;
}



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

#Male/Femaileはおおむね交互に並んでいるはず
#Vacantがあるとそこで並びがずれる
#ずれの検出有無で二分探索する

#0を基準とする
print(0, flush=True)
s0=input()
if s0=='Vacant':
    exit()

l=0   #ずれてない(ずれてるかもしれないが気にしない)
r=N-1 #ずれてる(絶対ずれてる)
while r-l>1:
    m=(l+r)//2
    print(m, flush=True)
    s=input()
    if s=='Vacant':
        exit()
    if m&1:
        if s!=s0:
            l=m
        else:
            r=m
    else:
        if s==s0:
            l=m
        else:
            r=m
print(r, flush=True)
sr=input()


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

using namespace std;

int main(){
	int n,i,a,b,c,t;

	cin >> n;
	for (i=0; i<n; i++){
		cin >> a >> b >>c;
		if (a>b) {t=a; a=b; b=t;}
		if (b>c) {t=b; b=c; c=t;}
		if(a*a+b*b==c*c) cout<<"YES"<<endl;
		else			cout<<"NO"<<endl;
}
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
const int nax=1e5+5;
vector<int> edge [nax];
int mod=1e9+7;
int mul(int a,int b)
{
    return (long long) a*b%mod;
}
pair<int,int> dfs(int a,int parent)
{
    int white=1;
    int black=0;
    for(auto x: edge[a])
    {
        if(x!=parent)
        {
            pair<int,int> p=dfs(x,a);
           int  old_white=white;
            white=mul(white,p.second);
            black=(mul(old_white,p.first)+mul(black,p.first+p.second))%mod;
        }
    }
    return make_pair(white,(white+black)%mod);
}
int  main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    pair<int,int> ans=dfs(1,-1);
    cout<<(ans.first+ans.second)%mod<<endl;
}

Measured memory_bytes: 14472
using namespace std;
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define INFINITE 1e9 + 5
#define MOD 1000000007
#define MAXN 100001 
#define pll pair<ll,ll>
#define pii pair<int,int>
#define debugArray(arr) cout << #arr<<" : "<<endl;for(int i : arr){cout << i <<", ";} cout <<endl;
#define debugVariable(x) cout <<#x<<"="<<x<<"\n";
#define check(x) cout<<"CHECK="<<#x<<"\n";
int X[4]={1,0,-1,0};
int Y[4]={0,1,0,-1};
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
    int test;
    test=1;
    while(test--)
    {
        int num;
        cin>>num;
        if(num%1000!=0)
        {
            int x=num/1000;
            x=1000*x+1000;
            cout<<x-num;
        }   
        else
        {
            cout<<0;
        }
        
    }
}

Measured memory_bytes: 3628
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
	int N;
	std::cin >> N;
	std::vector<int> v;
	for (int i = 0; i < 2*N; ++i) {
		int in;
		std::cin >> in;
		v.push_back(in);
	}
	std::sort(v.begin(), v.end());
	int ret = 0;
	for (int i = 0; i < 2*N; i += 2)
		ret += v[i];
	std::cout << ret << std::endl;
	return 0;
}

Measured memory_bytes: 764