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

#define MAX 10000
#define NIL -1

struct Node{
  int p;
  int left;
  int right;
};

Node tree[MAX];

//int num;
void preParse(int);
void inParse(int);
void postParse(int);

int main(){
  int num;
  int i, v ,left, right, root;
  cin >> num;
  for(i = 0; i < num; i++){
    tree[i].p = NIL;
  }
  for(i = 0; i < num; i++){
    cin >> v >> left >> right;
    tree[v].left = left;
    tree[v].right = right;
    if(left != NIL){
      tree[left].p = v;
    }
    if(right != NIL){
      tree[right].p = v;
    }
  }

  for(i = 0; i < num; i++){
    if(tree[i].p == NIL){
      root = i;
    }
  }
  cout << "Preorder" << endl;
  preParse(root);
  cout << endl;
  cout << "Inorder" << endl;
  inParse(root);
  cout << endl;
  cout << "Postorder" << endl;
  postParse(root);
  cout << endl;
  return 0;
}


void preParse(int u){
  if(u == NIL){
    return;
  }
  cout << " "<< u;
  preParse(tree[u].left);
  preParse(tree[u].right);
}

void inParse(int u){
  if(u == NIL ){
    return;
  }
  inParse(tree[u].left);
  cout << " " << u;
  inParse(tree[u].right);
}

void postParse(int u){
  if( u ==NIL ){
    return;
  }
  postParse(tree[u].left);
  postParse(tree[u].right);
  cout << " " << u;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
#define X first;
#define Y second;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const ll INF = 2e18;
const int inf = 1e9+10;
const int maxN = 2e5 + 10;
const int maxD = 15;
const int maxH = 100; 
const int MOD = 1e9+7;


int a[maxN];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		if(i%2==1 && a[i]%2 == 1)
		{
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3644
N,M = map(int,input().split())
count= 0
a = [int(i) for i in input().split()]
a_new = sorted(a,reverse=True)
for i in range(M):
    if a_new[i] >= (sum(a)*(1/(4*M))):
        count += 1
        
print('Yes' if count==M else 'No')

Measured memory_bytes: 38384
s = str(input())[::-1]

tmp_amari = [0]*2019

#amari = 0
num = 0
order = 1
for i in s:
    num += int(i)*order
    num %= 2019
    #print(num)
    tmp_amari[num] += 1
    order *= 10
    order %= 2019
    #print(order)

tmp_print = [i for i in tmp_amari if i > 0]
#print(tmp_print)

ans = 0
ans += tmp_amari[0]

for i in tmp_print:
    ans += (i*(i-1))//2

print(ans)


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

using namespace std;

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


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 200005
#define INF 1000000005LL

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int N;
ll K;

int main()
{
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	int A,B,C;
	A = abs(a-b);
	B = abs(b-c);
	C = abs(c-a);
	int ans = min({A+B,B+C,C+A});
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main(){
  int n;cin>>n;
  vector<pair<int,int>> a(n);
  int x; int l;
  for (int i=0; i<n; i++){cin>>x; cin>>l; a[i]=make_pair(x+l,x-l);}
  sort(a.begin(),a.end());
  int tend=a[0].first;
  int ans=1;
  for(int i=1;i<n;i++){
if(a[i].second>=tend){tend=a[i].first; ans++;}    
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
def solve(x,m,n,str)
	str.split("").each do |c|
		if c=="D"
			x-=1
		elsif c=="I"
			x+=1
			if x>m then m=x end
		end
	end
	p m
end


if __FILE__==$0
	read_i=lambda{|s|s.strip.to_i}
	read_s=lambda{|s|s.strip}
	n=read_i[gets]
	str=read_s[gets]
	solve(0,0,n,str)
end

Measured memory_bytes: 1788
import sys

divs = [2, 3, 5]

t = int(input())

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {}

    def dfs(x):
        if x in dp:
            return dp[x]

        # print(x, file=sys.stderr)

        if x == 0:
            dp[x] = 0
            return dp[x]

        ret = x * d
        for i in range(-4, 5):
            if x - i < 0:
                continue

            nx = x - i
            for cost, div in zip(costs, divs):
                if nx % div != 0 or nx // div >= x:
                    continue

                ret = min(ret, dfs(nx // div) + cost + abs(i) * d)

        dp[x] = ret
        return ret

    print(dfs(n))


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

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

template <typename T> T gcd(T x, T y) { return( y ? gcd(y, x % y) : x); }
template <typename T> T lcm(T x, T y) { return( x / gcd(x, y) * y); }
template <typename T> void printVec(vector<T> &vec) {
  cout << "";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

int main() {
  int k;
  string s;
  cin >> k >> s;
  if (s.size() <= k) {
    cout << s << endl;
  } else {
    string x = s.substr(0, k);
    cout << x << "..." << endl;
  }
	return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int ans[N];

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

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

    int ans = 2e9+10;
    if (b>=a)   ans = min(ans, b-a);
    if (-b>=a)  ans = min(ans, -b-a+1);
    if (b>=-a)  ans = min(ans, b+a+1);
    if (-b>=-a) ans = min(ans, -b+a+2);

    cout<<ans<<endl;
}


Measured memory_bytes: 3612
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 4010


int main(){
  int a,b,c,d,e,f;
  bool dp[SIZE] = {};
  
  scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);

  dp[0] = true;

  a *= 100;
  b *= 100;
  
  for(int i=0;i<=3000-c;i++)
    dp[i+c] |= dp[i];

  for(int i=0;i<=3000-d;i++)
    dp[i+d] |= dp[i];
  
  int ans1 = a, ans2 = 0;
  
  for(int i=0;i<=f/a;i++){
    for(int j=0;j<=(f - i*a)/b;j++){
      if(i + j == 0) continue;
      
      int remein = f - a*i - b*j;

      if(remein < 0) continue;
      
      for(int k=remein;k>=0;k--){
        if(!dp[k] || (a*i+b*j)/100 * e < k) continue;

        
        if(ans2 * (a*i+b*j+k) < k * ans1){
          ans1 = a*i+b*j+k;
          ans2 = k;
          break;
        }
        
      }
    }
  }

  printf("%d %d\n",ans1, ans2);
  
  return 0;
}



Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

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

void Main()
{
	string S;
  	cin >> S;
  	int cnt = 0;
  	rep(i,3) if(S[i] == 'A') cnt++;
  	if (cnt>0 && cnt<3) cout << "Yes" << endl;
  	else  cout << "No" << endl;
	return;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  getline(cin, s);
  string result = "";
  for ( int i = 0; i < s.size(); i++) {
    if (isalpha(s[i])) {
      if (islower(s[i])) {
        result += toupper(s[i]);
      } else if (isupper(s[i])) {
        result += tolower(s[i]);
      } 
    } else {
      result += s[i];
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 3176
#include <stdio.h>

int main(void)
{
	int n;
	int a, b, c;
	
	scanf("%d", &n);
	while (n-- > 0){
		scanf("%d %d %d", &a, &b, &c);
		if (a > b && a > c){
			(a * a == (b * b) + (c * c)) ? puts("YES") : puts("NO");
		}
		else if (b > a && b > c){
			(b * b == (a * a) + (c * c)) ? puts("YES") : puts("NO");
		}
		else if (c > a && c > b){
			(c * c == (a * a) + (b * b)) ? puts("YES") : puts("NO");
		}
		else {
			puts("NO");
		}
	}
	
	return (0);
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF ((ll)(1e18))

using namespace std;

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

const int MAX_N = 105;
const int MAX_V = (int)1e5 + 5;

ll dp[MAX_N][MAX_V]; 

int main()
{
	rep (i, MAX_N) rep (j, MAX_V) dp[i][j] = INF;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N, W; cin >> N >> W;
	vector<int> w(N, 0), v(N, 0);
	rep (i, N){
		cin >> w[i] >> v[i];
	} // end rep
	
	dp[0][0] = 0LL;
	rep (i, N){
		rep (j, MAX_V){
			if (dp[i][j] != INF){
				if (j + v[i] < MAX_V){ 	
					dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j] + (ll)w[i]);
				} // end if
				dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
			} // end if
		} // end rep
	} // end rep

	int res = 0;
	rep (j, MAX_V){
		if (dp[N][j] <= (ll)W){
			res = j;
		} // end if
	} // end for

	cout << res << endl;		

	return 0;
}

Measured memory_bytes: 82304
package main

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

var sc = bufio.NewScanner(os.Stdin)

func readInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func readFloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func readString() string {
	sc.Scan()
	return sc.Text()
}

var count map[int]int

const A int = 2 * 10000

func main() {
	sc.Split(bufio.ScanWords)
	n, k := readInt(), readInt()

	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = i + 1
	}
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i] + a[i]
	}

	ans := 0
	for i := k; i <= n; i++ {
		max := s[n] - s[n-i]
		min := s[i-1] - s[0]
		ans += max - min + 1
	}
	fmt.Println((ans + 1) % 1000000007)
}


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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m = M) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int exp(int n, int k) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int ax = exp(n, k / 2);
  ax = mod(ax * ax);
  if (k % 2) ax = mod(ax * n);
  return ax;
}

int gcd(int a, int b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}
//#define MULTIPLE_TEST_CASE
void solution() {
  int n, k;
  cin >> n >> k;
  multiset<int> s;
  int v[n];
  for (int i = 0; i < n; i++) cin >> v[i];
  for (int i = 0; i < k; i++) s.insert(v[i]);
  for (int i = k; i < n; i++) {
    if (v[i - k] < v[i]) {
      cout << "Yes" << endl;

    } else
      cout << "No" << endl;
    s.erase(s.find(v[i - k]));
    s.insert(v[i]);
  }
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}


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

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

typedef long long ll;

const int MAX = 1e5 + 10; 

int N, x, a[MAX];
 
int main(){
    cin >> N >> x;
    rep(i, N) cin >> a[i];

    ll ans = 0;
    rep(i, N-1){
        if(a[i] + a[i + 1] > x){
            int num = a[i + 1];
            a[i + 1] = x - a[i];
            ans += num - a[i + 1];
            if(a[i + 1] < 0) a[i + 1] = 0;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <stdlib.h>

using namespace std;
// vector push_back push front top empty pop make_pair long long insert begin end  
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair <int,int> > vpi;
typedef vector<long long> vll;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define B begin()
#define RB rbegin()
#define E end()
#define RE rend()
#define Z size()
#define REP(i,a,b) for (int i = a; i < b; i++)
#define L length()
#define show(a) cerr << " *** " << a << endl;
#define show1(a) cerr << " /// " << a << endl;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    string str;
    cin >> str;
    if (str == "Sunny")
        cout << "Cloudy";
    if (str == "Cloudy")
        cout << "Rainy";
    if (str == "Rainy")
        cout << "Sunny";
}


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

int main(){
  int h,w,h1,w1;
  scanf("%d",&h);
  scanf("%d",&w);
  scanf("%d",&h1);
  scanf("%d",&w1);
  printf("%d\n",(h-h1)*(w-w1));
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

void print() {
    cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << ' ';
    }
    cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}

// template<typename T>
// void print(T &arr){
//     ll sz = sizeof(arr)/sizeof(arr[0]);
//     for(int i = 0;i < sz-1;i++){cout << arr[i] << ' ';}
//     cout << arr[sz-1] << endl;
// }

int main(){
    vector<int> price(5);
    rep(i,5)cin >> price[i];
    int res = INT_MAX;
    sort(price.begin(), price.end());
    do{
        int temp = 0;
        rep(i,4){
            temp += price[i];
            temp = ceil(temp / 10.0) * 10;
            // print(price[i], temp);
        }
        temp += price[4];
        // print(price);
        // print(temp);
        res = min(res, temp);
    }while(next_permutation(price.begin(), price.end()));
    cout << res << endl;
    return 0;
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 x,y,a,b,c;
    cin >> x >> y >> a >> b >> c;
    vector<pii> apples;
    REP(i,a){
        int32 p;
        cin >> p;
        apples.pb(pii(p,0));
    }
    REP(i,b){
        int32 q;
        cin >> q;
        apples.pb(pii(q,1));
    }
    REP(i,c){
        int32 r;
        cin >> r;
        apples.pb(pii(r,2));
    }
    sort(ALL(apples),greater<pii>());
    int64 sum = 0;
    int32 cnt = x + y;
    REP(i,a+b+c){
        if(apples[i].second == 0){
            if(x == 0)continue;
            x--;
        }else if(apples[i].second == 1){
            if(y == 0)continue;
            y--;
        }
        cnt--;
        sum += apples[i].first;
        if(cnt == 0)break;
    }
    ANS(sum);
    return 0;
}

Measured memory_bytes: 10604
/* ****revpro**** */
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl     '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii      map<ll,ll>
using namespace std;

#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update> 
void solve()
{
  ll tmp;
  cin>>tmp;
  rep(n,1,tmp+1){
  ll ans=0;
  rep(i,1,n+1){
    if(i*i>n) break;
    rep(j,1,n+1){
      if(i*i+j*j+i*j>n) break;
      rep(k,1,n+1){
        if(i*i+j*j+k*k+i*j+i*k+k*j>n) break;
        if(i*i+j*j+k*k+i*j+i*k+k*j==n) ans++;
      }
    }
  }
  cout<<ans<<endl;
}
}
signed main()
{
  
    /***********************************/
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 generator (seed);
    /***********************************/
 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS=1;
//  cin>>TESTS;
  while(TESTS--)
  {
    solve();
    
  }
  TIME
  return 0;
}

Measured memory_bytes: 3780
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let s: Vec<String> = (0..n).map(|_| input()).collect();

    let mut v = vec![0; 5];
    for i in s {
        let c = i.chars().nth(0).unwrap();
        match c {
            'M' => v[0] += 1,
            'A' => v[1] += 1,
            'R' => v[2] += 1,
            'C' => v[3] += 1,
            'H' => v[4] += 1,
            _ => (),
        }
    }
    println!("{}", dfs(0, 0, 1, &v));
}

fn dfs(cur: usize, cnt: usize, n: i64, v: &Vec<i64>) -> i64 {
    if cur == 5 {
        if cnt == 3 {
            n
        } else {
            0
        }
    } else {
        let mut ans = 0;
        ans += dfs(cur + 1, cnt, n, v);
        ans += dfs(cur + 1, cnt + 1, n * v[cur], v);
        ans
    }
}


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

struct edge{
	long long to, cost;
};

int N, Q, K;
long long d[100000];
vector<edge> v[100000];
bool used[100000];

void dfs(int now, long long dist){
	d[now] = dist;
	used[now] = true;
	for(int i=0; i<v[now].size(); i++){
		edge e = v[now][i];
		if(!used[e.to]){
			dfs(e.to, dist + e.cost);
		}
	}
}

int main(){
	cin >> N;
	for(int i=0; i<N-1; i++){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		edge p1 = {b, c};
		edge p2 = {a, c};
		v[a].push_back(p1);
		v[b].push_back(p2);
	}
	cin >> Q >> K;
	fill(used, used+N, false);
	dfs(K-1, 0);
	for(int i=0; i<Q; i++){
		int x, y;
		cin >> x >> y;
		x--; y--;
		cout << d[x] + d[y] << endl;
	}
	return 0;
}

Measured memory_bytes: 14336
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <queue>
using namespace std;
#define sd(n) scanf("%d", &n)
#define sdd(n, m) scanf("%d%d", &n, &m)
#define sddd(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n, m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n, m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld", &n)
#define sldd(n, m) scanf("%lld%lld", &n, &m)
#define slddd(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
#define sf(n) scanf("%lf", &n)
#define sc(n) scanf("%c", &n)
#define sff(n, m) scanf("%lf%lf", &n, &m)
#define sfff(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
#define ss(str) scanf("%s", str)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define mem(a, n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mod(x) ((x) % MOD)
#define gcd(a, b) __gcd(a, b)
#define lowbit(x) (x & -x)
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
inline int read()
{
    int ret = 0, sgn = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            sgn = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    return ret * sgn;
}
inline void Out(int a) //ê?3?ía1ò
{
    if (a > 9)
        Out(a / 10);
    putchar(a % 10 + '0');
}

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

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
///快速幂m^k%mod
ll qpow(ll x, ll n, ll mod)
{
    if (n == 0)
        return 1;
    ll res = qpow((x * x) % mod, n / 2, mod) % mod;
    if (n & 1)
        res = (res * x) % mod;
    return res % mod;
}
// 快速幂求逆元
int Fermat(int a, int p) //费马求a关于b的逆元
{
    return qpow(a, p - 2, p);
}

///扩展欧几里得
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return g;
}

const int N = 25;

int main()
{
    int n;
    sd(n);
    cout << (n + 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
fn get_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().to_string()
}

fn main() {
    let os = get_line();
    let es = get_line();

    let ol = os.len();
    let el = es.len();

    let xs: Vec<char> = os.chars().collect();
    let ys: Vec<char> = es.chars().collect();
    for i in 0..el {
        print!("{}{}", xs[i], ys[i]);
    }

    if ol > el {
        print!("{}", xs[el]);
    }
    println!("");

}


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

using namespace std;

template<typename T> void cmax(T &x, const T &y)
{
	if(y > x) x = y;
}

template<typename T> void read(T &x)
{
	x = 0;
	char c = getchar();
	bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

int g(int x, int k)
{
	if(x%k == 0) return x/k;
	else if(x < k) return 0;
	else return g(x-(x/k+1)*((x%k-1)/(x/k+1)+1), k);
}

int main()
{
	int n, a, k, xo = 0;
	read(n);
	for(int i=1; i<=n; i++)
	{
		read(a), read(k);
		xo ^= g(a, k);
	}
	puts((xo==0) ? "Aoki" : "Takahashi");
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
            int[] x = new int[3000];
            int[] y = new int[3000];
            
            for(int i = 0; i < 3000; i++){
                x[i] = scan.nextInt();
                y[i] = scan.nextInt();
                
                if(x[i] == 0 && y[i] == 0)
                break;
                
                if(x[i] < y[i])
                System.out.println(x[i] + " " + y[i]);
                else
                System.out.println(y[i] + " " + x[i]);
            
        }
    }
}


Measured memory_bytes: 36092
#include <iostream>

using namespace std;

int main() {
  int n, t;
  cin >> n >> t;
  int ans = 0;
  int last = 0;
  while (n--) {
    int t2;
    cin >> t2;
    ans += min(t, t2 - last);
    last = t2;
  }
  cout << ans + t << endl;
}


Measured memory_bytes: 3528
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <random>
#include <cstdlib>
#define INT_MAX 2147483647
#define INT_MIN -2147483646
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int main() {
	int a, b;
	while (scanf("%d %d", &a, &b) != EOF) {
		printf("%d\n", a + b);
	}
	return 0;
}

Measured memory_bytes: 3092
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: i64,
        l: i64
    }
    let mut x: Vec<i64> = (1..n+1).map(|i| i+l-1).collect::<_>();
    x.sort_by_key(|v| v.abs());
    println!("{}", x.iter().skip(1).sum::<i64>());
}


Measured memory_bytes: 4476
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
signed main(){
    string s;
    cin>>s;
    int ma=0,mz=s.size()-1;
    while(1){
        if(s[ma]=='A'){
            break;
        }
        ma++;
    }
    while(1){
        if(s[mz]=='Z'){
            break;
        }
        mz--;
    }
    cout<<mz-ma+1<<endl;
    return 0;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=((ll)n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=((ll)a);i<((ll)n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    queue<ll> q;
    range(i,1,10)q.push(i);
    rep(i,n-1){
        ll p=q.front();
        q.pop();
        if(p%10!=0)q.push(p*10+p%10-1);
        q.push(p*10+p%10);
        if(p%10!=9)q.push(p*10+p%10+1);
    }
    puta(q.front());
    return 0;
}

Measured memory_bytes: 4716
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
 
using namespace std;
 
signed main()
{
    fast;
    int a,b,c;

    cin>>a>>b>>c;

    if ( a + b + c >= 22 )
    {
        cout<<"bust"<<endl;
    }
    else
    {
        cout<<"win"<<endl;
    }
    return 0;
}

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

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;

int main() { _
  int n; cin >> n;
  vector<ld> prob(n, 0);
  for (int i = 0; i < n; i++) {
    ld temp; cin >> temp;
    prob[i] = 1 - temp;
  }
  if (n == 1) cout << 1-prob[0] << endl;
  else {
    vector<vector<ld> > dp(n, vector<ld>(n/2+1, 0));
    dp[0][0] = 1-prob[0]; dp[0][1] = prob[0];
    for (int i = 1; i < n; i++) {
      dp[i][0] = dp[i-1][0]*(1-prob[i]);
      for (int j = 1; j <= min(i+1, n/2); j++) {
        dp[i][j] = dp[i-1][j]*(1-prob[i]) + dp[i-1][j-1]*prob[i];
      }
    }
    ld ans = 0;
    for (int i = 0; i <= n/2; i++) {
      ans += dp[n-1][i];
    }
    cout << setprecision(10) << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 70784
N=int(input())
P=[]
for i in range(0,N):
    P.append(list(map(int,input().split())))
from itertools import permutations
from math import sqrt
total=0
n=0
for i in permutations([j for j in range(0,N)]):
    for j in range(0, N-1):
        total+=sqrt((P[i[j]][0]-P[i[j+1]][0])**2+(P[i[j]][1]-P[i[j+1]][1])**2)
    n+=1
print(total/n)

Measured memory_bytes: 3064
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a,b = LI()
    t = [1]
    for i in range(2,1000):
        t.append(t[-1]+i)
    s = b-a
    c = 0
    for i in range(1000):
        if t[i+1] - t[i] == s:
            c = i
            break

    return t[c] - a


print(main())



Measured memory_bytes: 7752
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i < e; ++i)
#define sort_(a) stable_sort(a.begin(), a.end())
#define rsort(a) stable_sort(a.rbegin(), a.rend())
#define sum(a) accumulate(a.begin(), a.end(), 0LL)
#define join(a, d) accumulate(a.begin() + 1, a.end(), a[0], [](string s, string t) {return s + d + t;})
#define all(a) a.begin(), a.end()
// #define __lcm(a, b) std::__detail::__lcm(a, b)
typedef long long ll;
const long mod = 1e9 + 7;

int main(void) {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
#endif

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

  int N;
  cin >> N;
  vector<ll> A(N);
  rep(i, 0, N) cin >> A[i];
  vector<ll> nums(N);
  partial_sum(all(A), nums.begin());
  ll ans = __LONG_LONG_MAX__;
  rep(i, 0, N - 1) {
    ans = min(ans, abs(nums[i] - (nums[N-1] - nums[i])));
  }
  cout << ans << endl;
  return 0;
}


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

typedef long long int ll;
typedef pair <int, int> pii;
const int mod = 1e9+7;

int main(){
    int n;
    scanf("%d",&n);
    bool ok = false;
    while(n){
        if(n%10==7){
            ok = true;
            break;
        }
        n/=10;
    }
    if(ok) printf("Yes\n");
    else printf("No\n");
	return 0;
}


Measured memory_bytes: 3764
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<sstream>
using namespace std;

#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())

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

int main(){
	int p[8];
	while( cin >> p[0] ){
		rep(i,1,8)
			cin >> p[i];
		
		

		queue<int> q;
		q.push(4);
		q.push(1);
		q.push(4);
		q.push(1);
		q.push(2);
		q.push(1);
		q.push(2);
		q.push(1);

		queue<int> q2=q;

		int ans = 0x7FFFFFFF;
		vector<int> idx;
		rep(i,0,8){

			int sum = 0;
			rep(j,0,8){
				int num = q.front();
				q.pop();
				//cout << "test:" << p[j] - num << " num:" << num << endl;
				sum += max( p[j] - num , 0 );
				q.push(num);
			}

			//cout << "sum:" << sum << endl;
			if( ans > sum ){
				ans = sum;
				vector<int> tmp2;
				idx = tmp2;
				idx.push_back(i);
			}
			else if( ans == sum ){
				idx.push_back(i);	
			}

			//cout << "ans:" << ans << " idx:" << idx[0] << endl;

			q.push(q.front());
			q.pop();

		}

		
		stringstream ss;
		long out = 99999999;
		string outS;
		rep(i,0,idx.size()){
			q = q2;
			rep(j,0,idx[i]){
				q.push(q.front());
				q.pop();
			}	
			
			rep(i,0,8){
				ss << q.front();
				q.pop();
			}
			
			string s = ss.str();

			ss.str("");
			long che;
			sscanf(s.c_str(),"%ld",&che);
			//cout << "che:" << che << endl;
			if( out > che ){
				outS = s;	
				out = che;
			}
			
		}
			
		rep(i,0,8){
			cout << outS[i];
			if( i != 7 )
				cout << " ";
			else
				cout << endl;
		}
	}



	ret 0;
}


Measured memory_bytes: 3256
#!/usr/bin/env python3
#APC1 B

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
one,two = 0,0
for i in range(n):
    x = a[i] - b[i]
    if x == 0:
        continue
    if x > 0:
        one += x
        continue
    if x < 0:
        if x % 2:
            x -= 1
            one += 1
        two += (-x)//2
if one <= two:
    print('Yes')
else:
    print('No')


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

int main(){
  int N,L;
  cin>>N>>L;
  string S[N];
  for(int i=0;i<N;i++) cin>>S[i];
  sort(S,S+N);
  for(int i=0;i<N;i++) cout<<S[i];
  cout<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int a,b,c;
  int min,mid,max;

  scanf("%d%d%d",&a,&b,&c);
  if(a<=b&&a<=c){
    min = a;
    if(b<=c){
      mid = b;
      max = c;
    }else {
      mid = c;
      max = b;
    }
  }else if(b<=a&& b<=c){
    min = b;
    if(a<=c){
      mid = a;
      max = c;
    }else {
      mid = c;
      max = a;
    }
  }else if(c<=a&&c<=b){
    min = c;
    if(b<=a){
      mid = b;
      max = a;
    }else {
      mid = a;
      max = b;
    }
  }
  printf("%d %d %d\n",min,mid,max);

  return 0;
}


Measured memory_bytes: 1848
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;
template <typename T> bool chmin(T &x, const T &y) {if (x > y) {x = y; return true;} return false;}
template <typename T> bool chmax(T &x, const T &y) {if (x < y) {x = y; return true;} return false;}

int main() {
    int N, M;
    ll L;
    cin >> N >> M >> L;
    vector<vector<ll>> dist(N, vector<ll>(N, INF));
    rep(i, N) dist[i][i] = 0;
    rep(i, M) {
        int A, B;
        ll C;
        cin >> A >> B >> C;
        --A; --B;
        chmin(dist[A][B], C);
        chmin(dist[B][A], C);
    }
    
    rep(k, N) rep(i, N) rep(j, N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
    vector<vector<int>> G(N);
    rep(i, N) rep(j, N) {
        if (dist[i][j] <= L) G[i].push_back(j);
    }
    vector<vector<int>> DIST(N, vector<int>(N, -1));
    rep(i, N) {
        DIST[i][i] = 0;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : G[u]) {
                if (DIST[i][v] == -1) {
                    DIST[i][v] = DIST[i][u] + 1;
                    q.push(v);
                }
            }
        }
    }
    
    int Q;
    cin >> Q;
    rep(i, Q) {
        int s, t;
        cin >> s >> t;
        --s; --t;
        if (DIST[s][t] == -1) cout << -1 << "\n";
        else cout << DIST[s][t] - 1 << "\n";
    }
    return 0;
}


Measured memory_bytes: 5272
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
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; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }

// gcc拡張マクロ
#define gcd __gcd
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    string s; cin >> s;
    ll l = 0, r = s.size()-1;
    ll ans = 0;
    while (l < r) {
        if (s[l] == s[r]) {
            l++; r--;
        } else if (s[l] == 'x') {
            l++;
            ans++;
        } else if (s[r] == 'x') {
            r--;
            ans++;
        } else {
            ans = -1;
            break;
        }
    }
    cout << ans << endl;
    
}

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

using namespace std;

#define inf 1<<30
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> P;


int main(){
	llong N, K;
	map<int, llong> m;
	cin >> N >> K;
	int a, b;
	for(int i = 0; i < N; i++){
		cin >> a >> b;
		m[a] += b;
	}

	llong ans = 0;
	for(auto it = m.begin(); it != m.end(); it++){
		ans += it->second;
		if(ans >= K){
			cout << it->first << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 4224
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        try{
        	   //?????±?????\???
        	   String az=input.readLine();
      	       int a=Integer.parseInt(az);
               //[0][0][0]0????????????????§??????????????????????
	           int Array[][][]=new int[5][4][11];
	           int b=0;
	           int f=0;
	           int r=0;
	           int v=0;
	           for(int i=0; i<a; i++){
	        	   String ab = input.readLine();
		           String []strAry = ab.split(" ");
	           //??´??°??\???
	           b=Integer.parseInt(strAry[0]);
	           //????±???\???
	           f=Integer.parseInt(strAry[1]);
	           //??¨?±??????\???
	           r=Integer.parseInt(strAry[2]);
	           //?????°??\???
	              v=Integer.parseInt(strAry[3]);
	             //Array???????????°????????????????¢????
	              if(Array[b][f][r]>0){
	            	  Array[b][f][r]+=v;
	              }else{
	            	  //??????Array???b??´f???r??¨?±??????\?????????????????????????´?
	                    Array[b][f][r]=v;
	              }

	           }
                 int count=1;
	           for(int u=1; u<5; u++){
	        	   for(int o=1; o<4; o++ ){
	        		   for(int q=1; q<11; q++){
	        			   //Array????????°????????\??£?????????????????????????????????????´??????????????????¨??????????????\??£?????????
	        			  System.out.print(" "+Array[u][o][q]);
	        			}
	        		   System.out.println("");
	        		 }
	        	       if(count<4){
                       System.out.print("####################");

	        		   System.out.println("");
	        	       }
	        		   count++;
	        	 }



       		      }catch(IOException e) {   System.out.println("Exception : " + e);
		    }



	}//240 Array?????£?????????????????????????????????

}

Measured memory_bytes: 24728
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; string s1, s2;
    cin >> n >> s1 >> s2;
    int dp[55][3][3];
    memset(dp, 0, sizeof(dp));
    int mod = 1000000007;
    for (int i = 0; i < n; ++ i) {
        for (int c1 = 0; c1 < 3; ++ c1) {
            for (int c2 = 0; c2 < 3; ++ c2) {
                if ((c1 == c2) ^ (s1[i] == s2[i])) continue;
                if (!i) dp[i][c1][c2] = 1;
                else
                for (int c3 = 0; c3 < 3; ++ c3) {
                    for (int c4 = 0; c4 < 3; ++ c4) {
                        if ((c1 == c3) ^ (s1[i] == s1[i - 1])) continue;
                        if ((c2 == c4) ^ (s2[i] == s2[i - 1])) continue;
                        (dp[i][c1][c2] += dp[i - 1][c3][c4]) %= mod;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int c1 = 0; c1 < 3; ++ c1) {
        for (int c2 = 0; c2 < 3; ++ c2) {
            (ans += dp[n - 1][c1][c2]) %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  deque<char> str;
  string s; cin >> s;
  for(char v : s) str.push_back(v);
  int q; cin >> q;
  bool flag = true;
  for(int i=0; i<q; i++) {
    int t; cin >> t;
    if(t == 1) flag = !flag;//反転
    else {
      int f; cin >> f;
      char c; cin >> c;
      if(flag) {
        if(f == 1) str.push_front(c);
        else str.push_back(c);
      } else {
        if(f == 1) str.push_back(c);
        else str.push_front(c);
      }
    }
  }
  if(flag) {
    for(auto it=str.begin(); it!=str.end(); it++) {
      cout << *it;
    }
  }
  else {
    for(auto it=str.rbegin(); it!=str.rend(); it++) {
      cout << *it;
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 896
# -*- coding: utf-8 -*-
"""
http://abc062.contest.atcoder.jp/tasks/arc074_b

"""
import sys
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline


def solve(A, N):
    red_pq = []
    blue_pq = []

    for a in A[:N]:
        heappush(red_pq, a)
    red_total = sum(A[:N])

    blue_total = 0
    for a in A[2*N:]:
        heappush(blue_pq, -a)
        blue_total += a

    blue_lut = [0] * (3*N)
    blue_lut[2*N] = blue_total
    for k in range(2*N - 1, N - 1, -1):
        t1 = A[k]
        heappush(blue_pq, -t1)
        t2 = heappop(blue_pq)
        blue_total += (t1 + t2)
        blue_lut[k] = blue_total

    best_ans = red_total - blue_total

    for k in range(N, 2*N):
        t1 = A[k]
        heappush(red_pq, t1)
        t2 = heappop(red_pq)
        red_total += (t1 - t2)

        ans = red_total - blue_lut[k+1]
        best_ans = max(best_ans, ans)

    return best_ans


def main(args):
    N = int(input())
    A = [int(x) for x in input().split()]
    result = solve(A, N)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 39516
#include<iostream>
#include<algorithm>
using namespace std;
int n,s;
struct no
	{
	int x;
	bool v;
}a[20000098];
bool cmp(no a,no b)
{
	return a.x>b.x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>s;
	for(int i=1;i<=n;i++)
		{
		cin>>a[i].x>>a[i+n].x;
		a[i+n].v=true;
	}
	int ans=0;
	sort(a+1,a+1+n*2,cmp);
	for(int i=1;i<=n*2;i++)
		{
		if(a[i].v)
			{
			ans++;
		s-=a[i].x;
		}
		else
			{
			ans+=s/a[i].x;//输出ans所以改变ans的值
			if(s%a[i].x)
				ans++;
			s=-1;
		}
		if(s<=0)
			{printf("%d",ans);return 0;}
		
	}
}

Measured memory_bytes: 1792