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

const int MAXN = 3e5+5;

int a[MAXN], n, s, ans, dp[MAXN];

bool chk(int x) {
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; i += 2) {
		if (i == 0) {
			dp[0] = a[0];
			continue;
		}
		if (dp[i-2] < x) {
			dp[i] = dp[i-2] - a[i-1] + a[i];
		} else {
			dp[i] = max(dp[i-2] - a[i-1] + a[i], a[i]);
		}
	}
	return (dp[n-1] >= x);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		s += a[i];
	}
	if (n%2 == 0) {
		int x = 0;
		for (int i = 0; i < n; i += 2)
			x += a[i];
		cout << max(x, s-x) << ' ' << min(x, s-x) << endl;
		return 0;
	}
	for (int i = 0; i < n; i += 2)
		ans += a[i];
	int lo = 0, hi = s;
	while (lo != hi) {
		int mid = (lo+hi+1)/2;
		if (chk(mid))
			lo = mid;
		else
			hi = mid-1;
	}
	cout << s-ans+lo << ' ' << ans-lo << endl;
}

Measured memory_bytes: 2560
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let s = get!(String).chars().collect::<Vec<_>>();
    let n = s.len();
    let mut count = 0usize;
    for i in 0..n/2 {
        if s[i] != s[n-i-1] {
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 8572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define PI (acos(-1))

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;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<double> p(n+1);
	rep(i,n){
		cin>>p[i+1];
	}
	vector<vector<double>> dp(n+1,vector<double>(n+1,0));
	dp[0][0]=1.0;
	FOR(i,1,n+1){
		rep(j,i+1){
			if(j!=0) dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
			else{
				dp[i][0]=dp[i-1][0]*(1-p[i]);
			}
		}
	}
	double ans=0;
	rep(j,n+1){
		if(j>n-j){
			ans+=dp[n][j];
		}
	}
	cout<<setprecision(10)<<ans<<endl;
}

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

#define MOD 1000000007

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;

    long long all = 1, ex_0 = 1, ex_9 = 1, ex_09 = 1;
    for (int i = 0; i < n; i++) {
        all = (all * 10) % MOD;
        ex_0 = (ex_0 * 9) % MOD;
        ex_9 = (ex_9 * 9) % MOD;
        ex_09 = (ex_09 * 8) % MOD;
    }
    long long ans = (all - ex_0 - ex_9 + ex_09) % MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>

int main(void){
  int n,i,s,max,p[10];
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++)
    scanf("%d",&p[i]);
  
  max=p[0];s=0;
  for(i=1;i<n;i++)
    if(max<p[i]) max=p[i];
  for(i=0;i<n;i++)
     s=s+p[i];
  s=s-(max/2);
  
  printf("%d",s);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll n,cnt=1;
string s;
int main(void){
    cin>>s;
    n=s.size();
    if(n==2&&s=="10"){
        cout<<"1 2"<<endl;
        return 0;
    }
    if(s[n-1]=='1'||s[0]=='0'){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0;i<(n-1)/2;i++){
        if(s[i]!=s[n-i-2]){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=0;i<n-1;i++){
        cout<<cnt<<" "<<i+2<<endl;
        if(s[i]=='1'){
            cnt=i+2;
        }
    }
}


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

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int n;
    scanf("%d", &n);

    int v[n], c[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &c[i]);
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (v[i] > c[i])
            ans += v[i] - c[i];
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k; cin >> n >> k;
	int pre[n + 1] = {};
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		pre[i + 1] = pre[i] + x;
	}
	int mx = 0;
	for (int i = k; i <= n; i++)
		mx = max(mx, pre[i] - pre[i - k]);
	printf("%.6f\n", (mx + k) / 2.0);
}

Measured memory_bytes: 1024
L = []
N, M = map(int, input().split())
for i in range(N):
    A, B = map(int, input().split())
    L.append((A, B))
ans = 0
cnt = 0
for k, v in sorted(L):
    ans += k * v
    cnt += v
    if cnt >= M:
        break
ans -= (cnt - M) * k
print(ans)

Measured memory_bytes: 54104
#include <iostream>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i,k,n) for(int i = k; i < (int)(n); i++)
using namespace std;
int main(){

        int N,M,X; cin>>N>>M>>X;
        int a[100+1]; rep(i,M) cin>>a[i];
        int ans0=0,ansn=0;
        rep(i,M) if(a[i]<X) ans0++; else ansn++;
        cout << min(ans0,ansn) << endl;
        return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, m, x = input_to_int_map()
    ca = [input_to_int_tuple() for i in range(n)]

    import itertools
    ret = 10 ** 10
    for temp in itertools.product([0, 1], repeat=n):
        money = 0
        understands = [0] * m
        for i, val in enumerate(temp):
            if val == 1:
                t_ca = ca[i]
                money += t_ca[0]
                a = t_ca[1:]
                for j, under in enumerate(a):
                    understands[j] += under
        if len(list(filter(lambda t : t >= x, understands))) == m:
            ret = min(ret, money)

    if ret == 10 ** 10:
        ret = -1

    return ret


if __name__ == "__main__":
    print(main())


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

int n, m, x, ans1, ans2, temp;

int main() {
  cin >> n >> m >> x;
  vector<int> a(m);
  rep (i, m) {
    cin >> a.at(i);
  }
  ans1 = 0;
  for (int i = x; i > 0; i--) {
    if (find(a.begin(), a.end(), i) != a.end()) ans1++;
  }
  ans2 = 0;
  for (int i = x; i < n; i++) {
    if (find(a.begin(), a.end(), i) != a.end()) ans2++;
  }
  cout << min(ans1, ans2) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if(abs(n-m)>=2)
	{
		printf("%d\n",0);
		return 0;
	}
	long long res = 1,mod = 1e9+7;
	for(int i=1;i<=n;i++)
	res = res * i % mod;
	for(int i=1;i<=m;i++)
	res = res * i % mod;
	if(n==m) res = res * 2 %mod;
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  zero
//
//  Created by 叶金炜 on 2019/4/2.
//  Copyright © 2019 okstal. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#define pi acos(-1)
using namespace std;
int main() {
    int x,y;
    while (cin>>x>>y&&(x!=0||y!=0)) {
        for(int i=1;i<=x;i++)
            for(int j=1;j<=y;j++)
            {
                if(i==1||j==1||i==x||j==y)printf("#");
                else printf(".");
                if(j==y)printf("\n");
            }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2984
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second
#define mkp make_pair

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
static const int INF=1<<24;


int main(){
	int n,m;
	while(cin>>m>>n,n||m){
		int a[n][m];
		rep(i,n){
			rep(j,m){
				cin>>a[i][j];
				//cout<<a[i][j]<<" ";
			}
			//cout<<endl;
			
		}
		//cout<<endl;
		int ans=0;
		rep(i,n){
			rep(j,m){
				if(a[i][j]==1){
					a[i][j]=0;
					ans++;
					queue<pii> q;
					q.push(mkp(i,j));
					while(!q.empty()){
						int qs= q.size();
						rep(k,qs){
							pii tp=q.front();
							q.pop();
							int v[8][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
							rep(l,8){
								int x=tp.F+v[l][0],y=tp.S+v[l][1];
								if(x>=0&&y>=0&&x<n&&y<m){
									if(a[x][y]==1){
										q.push(mkp(x,y));
										a[x][y]=0;
									}
								}
							}
						}
					}/*
					
					rep(k,n){
						rep(l,m){
							cout<<a[k][l]<<" ";
						}
						cout<<endl;
					}
					cout<<endl;
					*/
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
				

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

using namespace std;

const int MXN = 200 + 9;

int n, a[MXN];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i] >> a[i + n];
	sort(a, a + n * 2);
	int ans = 0;
	for (int i = 0; i < n * 2; i += 2) {
		ans += a[i];
	}
	cout << ans << endl; 
	return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
t = []
l = [0]*(n+1)
for i in range(n+1):
    t.append([])
for i in range(m):
    a,b = map(int,input().split())
    t[a].append(b)
    t[b].append(a)
x = [1]
p = 0
while(p < n):
    for i in range(len(t[x[p]])):
        c = t[x[p]][i]
        if(l[c] == 0):
            x.append(c)
            l[c] = x[p]
    p += 1
print("Yes")
for i in range(2,n+1):
    print(l[i])

Measured memory_bytes: 100220
#include <iostream>

using namespace std;

int main () {
    string S, S1, S2;
    cin >> S;

    int left, right;
    S1 = S.substr(0,2);
    S2 = S.substr(2,2);

    left  = stoi(S1);
    right = stoi(S2);

    string ans;

    bool left_MM  = 0;
    bool right_MM = 0;

    if ( left >= 1 && left <= 12) left_MM = 1;
    if ( right >= 1 && right <= 12) right_MM = 1;

    if( left_MM == 0 && right_MM == 0 ){
        ans = "NA";
    }else if( left_MM == 0 && right_MM == 1 ){
        ans = "YYMM";
    }else if( left_MM == 01&& right_MM == 0 ){
        ans = "MMYY";
    }else if( left_MM == 1 && right_MM == 1 ){
        ans = "AMBIGUOUS";
    }

    cout << ans << endl;
    
}

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

int main() {
    int n,temp;
    cin>>n;
    string s;
    pair<pair<string,int>,int> p[n];
    rep(i,n) {
        cin>>s>>temp;
        p[i]=make_pair(make_pair(s,-temp),i);
    }
    sort(p,p+n);
    rep(i,n) cout<<p[i].second+1<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#define NUM 200010

int main(void){
    int N;
    char S[NUM];
    int o_count = 0;
    int x_count = 0;
    int o[NUM];
    int x[NUM];
    
    scanf("%d", &N);
    scanf("%s", S);

    for(int i = 0; i < N; i++){
        if(S[i] == '#'){
            x_count++;
        }
        x[i] = x_count;
    }

    for(int i = N - 1; 0 <= i; i--){
        if(S[i] == '.'){
            o_count++;
        }
        o[i] = o_count;
    }

    int ans = N;
    for(int i = 0; i <= N; i++){
        int ans_;
        if(i == 0){
            ans_ = o[i];
        }
        if(i == N){
            ans_ = x[i];
        }
        ans_ = x[i - 1] + o[i];
        if(ans_ < ans){
            ans = ans_;
        }
    }

    printf("%d\n", ans);
}


Measured memory_bytes: 2168
#include <stdio.h>
int main(void){
  int n, a[10] = {0}, max = 0, sum = 0;
  scanf("%d", &n);getchar();
  for(int i = 0; i < n; i++){
    scanf("%d", &a[i]);getchar();
    sum += a[i];
    if(a[i] > max){
      max = a[i];
    }
  }
  if(max < sum - max){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
using namespace std;

const int maxn = 100005;
int del[maxn], c[maxn], n, x, y, rt, ans;
vector<int> e[maxn];

int dfs(int u, int fa) {
	int son = 0, sum = 0, sz = e[u].size();
	rep (i, 0, sz - 1)
		if (e[u][i] != fa && !del[e[u][i]]) {
			sum += dfs(e[u][i], u);
			son++;
		}
	// printf("%d %d\n", u, fa);
	if (sum < son - 1) ans += son - 1 - sum;
	return son >= 1;
}

int main() {
	scanf("%d", &n);
	rep (i, 2, n) {
		scanf("%d%d", &x, &y);
		c[++x]++; c[++y]++;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	rep (i, 1, n)
		if (c[i] == 2) {
			int a = 0, b = 0, sz = e[i].size();
			rep (j, 0, sz - 1)
				if (!del[e[i][j]]) {
					if (!a) a = e[i][j];
					else b = e[i][j];
				}
			e[a].push_back(b);
			e[b].push_back(a);
			del[i] = 1;
		}
		else if (c[i] > 2) rt = i;
	if (!rt) puts("1");
	else { dfs(rt, 0); cout << ans << endl; }
	return 0;
}


Measured memory_bytes: 8064
use List::Util qw(max);
use List::Util qw(sum);
my $input = <STDIN>;
chomp $input;
my ($A, $B, $C) = split / /, $input;
my $max = max($A,$B,$C);
my $sum = sum($A,$B,$C);
my $res = 9*$max+$sum;
print "$res\n";

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int ans[100];

int main()
{
	int n,m;cin >> n>>m;
	
	REP(i,m)
	{
		int a,b;cin >> a >> b;
		ans[a]++;
		ans[b]++;
	}
	
	REP(i,n)
	{
		cout <<ans[i+1] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define MAXN 2005
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {putchar('-');x = -x;}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,M,bl[MAXN],fa[MAXN],dep[MAXN],up,eq;
int64 X,T,faE[MAXN];
bool vis[MAXN];
struct Edge {
    int to,next;int64 val;
}E[MAXN * 2];
int head[MAXN],sumE;
struct node {
    int u,v;int64 val;
    friend bool operator < (const node &a,const node &b) {
	return a.val < b.val;
    }
}Ed[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
int fpow(int x,int c) {
    int res = 1,t = x;
    while(c) {
	if(c & 1) res = mul(res,t);
	t = mul(t,t);
	c >>= 1;
    }
    return res;
}
void update(int &x,int y) {
    x = inc(x,y);
}
void add(int u,int v,int64 c) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    E[sumE].val = c;
    head[u] = sumE;
}
void dfs(int u) {
    dep[u] = dep[fa[u]] + 1; 
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa[u]) {
	    fa[v] = u;
	    faE[v] = E[i].val;
	    dfs(v);
	}
    }
}
int getfa(int u) {
    return bl[u] == u ? u : bl[u] = getfa(bl[u]);
}
int64 Query(int u,int v) {
    if(dep[u] < dep[v]) 
        swap(u,v);
    int64 res = 0;
    while(dep[u] > dep[v]) {
	    res = max(res,faE[u]);
	    u = fa[u];
    }
    if(u == v) 
        return res;
    while(u != v) {
	    res = max(res,faE[u]);
	    res = max(res,faE[v]);
	    u = fa[u];v = fa[v];
    }
    return res;
}

void Solve() {
    read(N);read(M);read(X);
    for(int i = 1; i <= M ; ++i) {
	read(Ed[i].u);read(Ed[i].v);read(Ed[i].val);
    }
    for(int i = 1 ; i <= N ; ++i) bl[i] = i;
    sort(Ed + 1,Ed + M + 1);
    for(int i = 1 ; i <= M ; ++i) {
	if(getfa(Ed[i].u) != getfa(Ed[i].v)) {
	    vis[i] = 1;
	    T += Ed[i].val;
	    add(Ed[i].u,Ed[i].v,Ed[i].val);
	    add(Ed[i].v,Ed[i].u,Ed[i].val);
	    bl[getfa(Ed[i].u)] = getfa(Ed[i].v);
	}
    }
    dfs(1);
    for(int i = 1 ; i <= M ; ++i) {
	if(!vis[i]) {
	    int64 d = Ed[i].val - Query(Ed[i].v,Ed[i].u);
	    if(d == X - T) ++eq;
	    else if(d > X - T) ++up;
	}
    }
    if(X < T) {puts("0");return;}
    else if(X == T) {
	int ans = 0;
	update(ans,mul(inc(fpow(2,N - 1),MOD - 2),fpow(2,M - N + 1)));
	update(ans,mul(mul(2,inc(fpow(2,eq),MOD - 1)),fpow(2,up)));
	out(ans);enter;
    }
    else {
	int ans = 0;
	update(ans,mul(mul(2,inc(fpow(2,eq),MOD - 1)),fpow(2,up)));
	out(ans);enter;
    }
}
int main() {
    Solve();
}

Measured memory_bytes: 3784
/*input
19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

int a[maxn];

int main()
{
	//IOS;
	int n;
	cin>>n;
	REP(i,n) cin>>a[i];

	ll ans=0;
	int r=n;
	int cnt=0;

	for(int i=n-1;i>=0;i--){
		while(r>i+1&&(a[i]^cnt)!=a[i]+cnt){
			r--;
			cnt^=a[r];
		}
		cnt^=a[i];
		ans+=r-i;
	}
	cout<<ans<<'\n';
	return 0;
}


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

int main(){
 int n;
 cin >> n;
  
 vector<int> a(n);
 rep(i,n) cin >> a[i];
 sort(a.begin(), a.end());
 a.erase(unique(a.begin(), a.end()), a.end());
 if(a.size() == n) cout << "YES" << endl;
 else cout << "NO" << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int, int> p;
 
int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, h;
    cin >> a >> b >> h;

    cout << (a + b) * h / 2 << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readInt()
    val h = readIntList().toMutableList()

    var l = 0
    var r = 0
    var ans = 0

    while (true) {
        l = h.indexOfFirst { it != 0 }
        if (l == -1) {
            break
        }
        r = l + 1
        while (r < n && h[r] != 0) {
            r++
        }
        r--
        for (i in l..r) {
            h[i]--
        }
        ans++
    }
    println(ans)
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 38168
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>

using namespace std;

/********** TEMPLATE STARTS HERE ***********/

#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define PI 3.1415926535897932384626433832795
#define gcd __gcd 
#define digits(n) (int)(log10(n) + 1)

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pll> vll;
typedef vector <pii> vii;

const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;

template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

/********** TEMPLATE ENDS HERE ***********/

int Map[70][70];


main()
{
	IOS
	
	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			
			if(c == '#')
			{
				Map[i][j] = 1;
			}
		}

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(Map[i][j] == 1 && Map[i - 1][j] == 0 && Map[i][j - 1] == 0 && Map[i + 1][j] == 0 && Map[i][j + 1] == 0)
			{
				cout << "No";
				return 0;
			}
	cout << "Yes";
}

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

int main(){
	ll n;
	cin >> n;
	map<string, int> mp;
	for(ll i = 0;i <= n; i++){
		string str;
		getline(cin , str);
// 		cout << str << endl;
		mp[str]++;
	}
	int max_val = 0;
	for(auto it = mp.begin(); it != mp.end(); ++it){
		int val = it->second;
		// cout << it->first << endl;
		max_val = max(max_val, val);
	}
	for(auto it = mp.begin(); it != mp.end(); it++){
		int val = it->second;
		if(val == max_val){
			string str = it->first;
			cout << str << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1e9
#define EPS 10e-8

ll A[3],T;

int main(){
  char S[4][107];
  rep(i,3){
    cin >> S[i];
  }
  T=0;
  A[0]=0;
  A[1]=-1;
  A[2]=-1;
  while(1){
    if(S[T][A[T]]=='a'){
      T=0;
      A[T]++;
    }
    else if(S[T][A[T]]=='b'){
      T=1;
      A[T]++;
    }
    else{
      T=2;
      A[T]++;
    }
    if(A[T]==strlen(S[T])){
      break;
    }
  }
  cout<< (T==0 ? "A" : (T==1 ? "B" : "C")) << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define db(x) cerr << #x << ": " << x << '\n';
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define rz(v, n) v.resize((n) + 1);
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 int power (int a, int b = mod - 2)
{
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	read(x);
	FOR (i, -1000, 1000)
	{
	    FOR (j, -1000, 1000)
	        if (x == power(i, 5) - power(j, 5)) {cout << i << " " << j << endl; return 0;}
	}
}


















Measured memory_bytes: 3696
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
using namespace std;

int main(){
    int N,M,L[100010],R[100010],max=0,min=100010;
    cin>>N>>M;
    for(int i=0;i<M;++i){
        cin>>L[i]>>R[i];
        if(L[i]>max)max=L[i];
        if(R[i]<min)min=R[i];
    }
    if(max<=min)cout<<min-max+1<<endl;
    else cout<<0<<endl;

    return 0;

}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;


int main() {
    int n,x,sum;
    cin>>n>>x;

    vector<int>a(n);
    rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }

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

    x-=sum;

    cout<<x/a[0]+n<<endl;
}

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

int main() {
    string s;
    cin >> s;
    int x=0;
    for(int i = 0; i < s.size()-1; i++) {
        if(s[i]!=s[i+1]) x++;
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 3728
cond=list(map(int,input().split()))
X=int(cond[1]/1000 - cond[0])
T=True
x=0
while T and x<=int(cond[1]/10000):
    for y in range(int(cond[1]/5000)+1):
        if ((X-9*x)%4!=0):
           continue
        else:
           XX=x
           Y=(cond[1]/1000 - cond[0] - 9*x)/4
           Z=cond[0]-XX-Y
           if Z<0:
               XX=Y=Z=None
               continue
           elif Y<0:
               XX=Y=Z=None
               continue
           else:
               T=False
               break
    x+=1
if len(str(Z))==0 or Z==None:
    print('-1 -1 -1')
else:
    print(int(XX), int(Y), int(Z))

Measured memory_bytes: 40924
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    int n,m;cin>>n>>m;
    deque<P> ps;
    rep(i, n){
        int a,b;cin>>a>>b;
        ps.push_back(P(a, b));
    }
    priority_queue<ll> ms;
    sort(all(ps));
    ll ans = 0;
    for(int i = m-1;i>=0;i--){
        ll si = ps.size();
        rep(j, si){
            P p = ps.front();
            if(p.first<=m-i){
                ps.pop_front();
                ms.push(p.second);
                debug("i%d  %d added\n", i, p.second);
            }else{
                break;
            }
        }
        
        if(!ms.empty()){
            ll ss = ms.top();
            debug("i%d ms%d\n", i, ss);
            ans += ms.top();
            ms.pop();
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2300
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    string s, c, front = "", back = "";
    cin >> s;
    int q, t, f, is_reverse = -1;
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> t;
        if(t == 1) is_reverse *= -1;
        else{
            cin >> f >> c;
            switch(f * is_reverse){
                case -1:
                case 2:
                    front += c;
                    break;
                case 1:
                case -2:
                    back += c;
                    break;
                default:
                    break;
            }
        }
    }
    if(is_reverse == -1){
        reverse(front.begin(), front.end());
        cout << front << s << back;
    }
    else{
        reverse(s.begin(), s.end());
        reverse(back.begin(), back.end());
        cout << back << s << front;
    }
    return 0;
}

Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int r = sc.nextInt();

		sc.close();

		int p = 3;

		int x = p * r * r;

		int a = x / p;

		System.out.println(a);


	}


}


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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll A[200005];
bool U[200005];

int main()
{
    int N;
    cin >> N;
    REP(i, N)
    {
        cin >> A[i];
    }
    sort(A, A + N);
    ll ans = 0;
    ll max = 1LL << 35;
    for (int i = N - 1; i >= 0; --i)
    {
        if (U[i])
            continue;
        while (A[i] * 2 < max)
            max >>= 1;

        ll ok = i, ng = -1;
        while (abs(ok - ng) > 1)
        {
            ll mid = (ok + ng) / 2;
            if (A[i] + A[mid] >= max)
            {
                if (A[i] + A[mid] == max && U[mid])
                    ng = mid;
                else
                    ok = mid;
            }
            else
                ng = mid;
        }
        //cout << max << " " << A[i] << " " << A[ok] << " " << ok << endl;
        if (ok < i && A[i] + A[ok] == max)
        {
            U[ok] = true;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1920
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	void solve(Supplier<String> sc) {
		int D = Integer.parseInt(sc.get());
		int[] C = new int[26];
		Arrays.setAll(C, $ -> Integer.parseInt(sc.get()));
		var S = new int[D][26];
		for (int i = 0; i < D; i++) {
			int[] row = S[i];
			Arrays.setAll(row, $ -> Integer.parseInt(sc.get()));
		}

		var currentSatisfaction = 0;
		var last = new int[26];
		int[] result = new int[D];
		for (int day = 0; day < D; day++) {
			int max = Integer.MIN_VALUE;
			int maxIdx = -1;
			for (int open = 0; open < 26; open++) {
				int attempt = currentSatisfaction + S[day][open];

				for (int k = 0; k < 26; k++) {
					if (k == open) continue;
					attempt -= calcSatisfactionDecrease(C[k], day, last[k]);
				}

				if (max < attempt){
					max = attempt;
					maxIdx = open;
				}
			}

			last[maxIdx] = day + 1;
			currentSatisfaction = result[day] = maxIdx;
		}

		for (int value : result) {
			System.out.println(value + 1);
		}
	}

	int calcSatisfactionDecrease(int rate, int day, int last){
		return rate * (day + 1 - last);
	}

	void judge(Supplier<String> sc){
		int D = Integer.parseInt(sc.get());
		int[] C = new int[26];
		Arrays.setAll(C, $ -> Integer.parseInt(sc.get()));
		var S = new int[D][26];
		for (int i = 0; i < D; i++) {
			int[] row = S[i];
			Arrays.setAll(row, $ -> Integer.parseInt(sc.get()));
		}
		int[] T = new int[D];
		Arrays.setAll(T, $ -> Integer.parseInt(sc.get()) - 1);

		var currentSatisfaction = 0;
		var last = new int[26];
		for (int i = 0; i < D; i++) {
			last[T[i]] = i + 1;
			currentSatisfaction += S[i][T[i]];
			for (int j = 0; j < 26; j++) {
				currentSatisfaction -= C[j] * (i + 1 - last[j]);
			}
			System.err.println(currentSatisfaction);
		}
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		new Solver().solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

Measured memory_bytes: 35712
#include<iostream>
#include<boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;
using namespace std;

int main()
{
   cpp_int n;
   cin >> n;
  
  std::vector<cpp_int> r;
  {
    cpp_int t = 1;
    for (int i=0; i<20; ++i){
      t = t * 26;
      r.push_back(t);
      //cout << t << endl;
    }
  }
  cpp_int p = n-1;
  for (int i=0; i<20; ++i){
    if (p < r[i]){
      for (int j=i-1; j>=0; --j){
        cpp_int x = p / r[j];
        cout << static_cast<char>('a' + x);
        
        p -= r[j] * x ;
      }
      cout << static_cast<char>('a' + p);
      break;
    }
    else {
      p -= r[i];
    }
  }
  
  cout<<endl;
  return 0;
}


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

int main(){
        string in;
        cin >> in;
        int Q;
        cin >> Q;
        list<char> ans;
        for(char y:in) ans.push_back(y);

        bool isForward = 1;
        rep(i,Q){
                int x;
                cin >> x;
                if(x == 1) {
                        isForward = !isForward;
                }
                else {
                        int f; char c;
                        cin >> f >> c;
                        if((isForward == 1 && f == 1) || (isForward == 0 && f == 2)) {
                                ans.push_front(c);
                        }
                        else ans.push_back(c);
                }
        }
        if(isForward == 0) reverse(ans.begin(),ans.end());
        string S;
        for(char x : ans) S += x;
        cout << S << endl;
}


Measured memory_bytes: 10500
import sys
input=sys.stdin.readline

N=int(input())
s_list=[]

for i in range(N):
    s_list.append(input().strip())

s_list.sort()
s_old=s_list[0]
cnt=1
maxc=0
max_list=[]
for s in s_list[1:]:
    if s==s_old:
        cnt+=1
    else:
        if cnt>maxc:
            max_list=[s_old]
            maxc=cnt
        elif cnt==maxc:
            max_list.append(s_old)
        else:
            pass

        cnt=1

    s_old=s

if cnt>maxc:
    max_list=[s_list[-1]]
elif cnt==maxc:
    max_list.append(s_list[-1])

for s in max_list:
    print(s)

Measured memory_bytes: 74064
///cREATED bY BERNARB.01
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef priority_queue<int,vector<int>,greater<int>> pqil;
typedef priority_queue<int> pqig;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef priority_queue<pii> pqiig;
typedef vector<pii> vii;
typedef vector<piii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef map<int, int> mii;
#define mid ((l+r)/2)
#define PB push_back
#define PP pop_back
#define PF push_front
#define DF pop_front
#define F first
#define S second
#define MP make_pair
#define C continue
#define B break
#define R return
#define sz(v) (int)(v).size()
#define len(s) (int)(s).length()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(arr, x) memset((arr), (x), sizeof (arr))
#define loop(n) for(int i=0; i<(n); i++)
#define lop(a, n) for(int i=(a); i<(n); i++)
#define jloop(n) for(ll j=0; j<(n); j++)
#define kloop(n) for(ll k=0; k<(n); k++)
#define gloop(n) for(ll g=0; g<(n); g++)
#define rloop(n) for(ll i=(n)-1; i>=0; i--)
#define sgm(y) (((y)*((y)+1))/2)
const ll INF = 2e17+423;
const ll mod = 1e9+7; //998244353;
const ld pi = acos(-1.0);
const ld cmpf = 1e-9;
//__int128_t
//      -ASCII-
//a -> z | A -> Z | 0 -> 9
//97 122 | 65  90 | 48  57
#define endl '\n'
ll po(ll,ll);

























int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int A[3];
    A[0]=1;
    A[1]=2;
    A[2]=3;
    int a, b;
    cin >> a >> b;
    loop(3) if(A[i]!=a&&A[i]!=b){
        cout << A[i] ;
        B;
    }
    R 0;
}
/*

*/




























































ll po(ll x, ll n){
  if(n==0) R 1;
  ll y = po(x, n/2);
  y = ((y)*(y));
  if(n%2) y = (y*(x));
  R y;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> p(m);
    vector<vector<int>> G(n, vector<int>(n, INF)), g(n, vector<int>(n, INF));
    rep(i, n) g[i][i] = 0;
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        p[i] = make_pair(a, b);
        g[a][b] = 1; g[b][a] = 1;
    }
    int v = n, ans = 0;
    rep(i, m){
        G = g;
        int a = p[i].first; int b = p[i].second;
        G[a][b] = INF; G[b][a] = INF;
        for (int k = 0; k < v; k++) {
            for (int i = 0; i < v; i++) {
                for (int j = 0; j < v; j++) {
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
        rep(i, n){
            if(G[a][i] == INF || G[b][i] == INF){
                ans++;
                //cout << a+1 << "," << b+1 << endl;
                break;
            }
        }
    }
    cout << ans << endl;
}




Measured memory_bytes: 256
n=int(input())
a=[]
for i in range(n):
    x,l=map(int,input().split())
    a.append([x-l,x+l])
a.sort(key=lambda x:x[1])
r=-10**10
ans=0
for i in range(n):
    if a[i][0]>=r:
        ans+=1
        r=a[i][1]
print(ans)

Measured memory_bytes: 21336
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    
    int N,K;
    cin >> N >> K;
    
    vector<int> h(N);
    int n = N;
    int i = 0;
    while(n--){
        cin >> h[i];
        
        i++;
    }
    
    sort(h.begin(),h.end());
    
    int ans = 1000000000;
    
    for(i=0;i<=N-K;i++){
        ans = min(h[i+K-1]-h[i],ans);
    }
        

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


Measured memory_bytes: 640
import heapq

N = int(input())
V = [int(a) for a in input().split()]
h = []
for v in V:
    heapq.heappush(h, v)

for i in range(N-1):
    heapq.heappush(h, (heapq.heappop(h) + heapq.heappop(h)) / 2)

print(heapq.heappop(h))

Measured memory_bytes: 38256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  vector<int> xs;
  for (int i = 0; i < N; ++i) {
    int xi;
    cin >> xi;
    if (xi == 0) {
      --K;
    } else {
      xs.push_back(xi);
    }
  }
  if (K == 0) {
    cout << 0 << endl;
    return 0;
  }

  int ans = INT_MAX;
  for (int i = 0; i < N - K + 1; ++i) {
    int min_val = xs[i];
    int max_val = xs[i + K - 1];
    if (min_val < 0 && max_val < 0) {
      ans = min(ans, abs(min_val));
    } else if (min_val > 0 && max_val > 0) {
      ans = min(ans, max_val);
    } else {
      if (abs(min_val) < max_val) {
        ans = min(ans, 2 * abs(min_val) + max_val);
      } else {
        ans = min(ans, abs(min_val) + 2 * max_val);
      }
    }
  }

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

Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main (int argc, char * const argv[]) {
    // insert code here...
    int h;
	int yama[10];
	for(int i=0;i<10;i++){
		cin >> h;
		yama[i]=h;
	}
	sort(yama, yama+10);
	
	cout << yama[9] <<endl;
	cout << yama[8] <<endl;
	cout << yama[7] <<endl;
	return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  if(b % a == 0) {
      cout << a+b << endl;
  } else {
      cout << b-a << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <cmath>
 
using namespace std;
using ll = long long;
 
int main(void){
    ll n,p;
    cin>>n>>p;
    if( n == 1 ){
		cout << p << endl;
		return 0;
	}
    ll ans = 1;
    for(ll i =sqrt(p);i>1;--i){
        if(p%i == 0){
            int count = 0;
            while(p%i == 0){
               p /= i;
               count++;
            }
            if(count >= n) ans *= i;
            else for(int j=0;j<count;++j)p *= i;
        }
        
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var V = Console.ReadLine().Split(" ");
        var C = Console.ReadLine().Split(" ");

        var count = 0;
        for(int i = 0; i < N; i++)
        {
            var diff = int.Parse(V[i]) -  int.Parse(C[i]);
            if (diff > 0) count += diff;
        }

        Console.WriteLine(count);
    }
}


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

const int INF = 1e9;

pair<int, int> get_max(const vector<vector<int>>& a, const vector<char>& used) {
    vector<int> took(a[0].size());
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            if (used[a[i][j]]) {
                ++took[a[i][j]];
                break;
            }
        }
    }
    int mx_id = -1, mx = -1;
    for (int i = 0; i < took.size(); ++i) {
        if (mx < took[i]) {
            mx = took[i];
            mx_id = i;
        }
    }
    return {mx_id, mx};
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
            --a[i][j];
        }
    }

    int ans = INF;
    vector<char> used(m, true);
    for (int i = 0; i < m; ++i) {
        auto res = get_max(a, used);
        used[res.first] = false;
        ans = min(ans, res.second);
    }

    printf("%d\n", ans);
}


Measured memory_bytes: 640
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readC(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=rdsp;foreach(ref v;t)pick(r,v[i]);}}

void main()
{
  int h, w; readV(h, w);
  string[] a; readC(h, a);

  auto sh = new bool[](h), sw = new bool[](w);
  foreach (i; 0..h)
    if (a[i].all!(ai => ai == '.'))
      sh[i] = true;
  foreach (j; 0..w)
    if (a.map!(ai => ai[j]).all!(aj => aj == '.'))
      sw[j] = true;

  foreach (i; 0..h) {
    if (sh[i]) continue;
    foreach (j; 0..w) {
      if (sw[j]) continue;
      write(a[i][j]);
    }
    writeln;
  }
}


Measured memory_bytes: 256