akhauriyash/Code-Regression huggingface dataset:
import Control.Applicative
import Control.Monad
import Control.Monad.ST
-- import qualified Data.ByteString as BS
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
--import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
--import Data.Array.Unboxed
--import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
import Text.Printf
import GHC.ST
-- import System.IO.Unsafe
 
-- templete
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
getDoubles = map readDouble . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
tjoin :: (Show a, Show b) => (a, b) -> String
tjoin (x, y) = show x ++ (' ' : show y)
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
splitRec :: Int -> [a] -> [[a]]
splitRec _ [] = []
splitRec n xs = let (y,ys) = splitAt n xs in y : splitRec n ys
infixl 7 `divCeil`
divCeil :: Integral a => a -> a -> a
x `divCeil` y = (x+y-1) `div` y
coverC :: Ord a => (a, a) -> a -> Bool
coverC (l,r) x = l<=x && x<=r
coverH :: Ord a => (a, a) -> a -> Bool
coverH (l,r) x = l<=x && x<r
ibsearch :: (Int -> Bool) -> (Int,Int) -> Int
ibsearch f (ok,ng) = if abs (ok-ng) <= 1 then ok else let mid = (ok + ng) `div` 2 in ibsearch f (if f mid then (mid,ng) else (ok,mid))
whenM :: Monad m => m Bool -> m () -> m ()
whenM c a = c >>= flip when a
unconsU :: [a] -> (a, [a])
unconsU (x:xs) = (x, xs)
-- templete

calc :: [Double] -> String
calc [a,b,c,d,e,f] = printf "%.3f %.3f" fx fy
  where
    det = a*e - b*d
    det1 = c*e - b*f
    det2 = a*f - c*d
    x = det1 / det
    y = det2 / det
    fx = (/1000) $ fromIntegral $ floor $ 1000*x+0.5 :: Double
    fy = (/1000) $ fromIntegral $ floor $ 1000*y+0.5 :: Double
    

main = map (map readDouble . words) . lines <$> getContents >>= mapM_ (putStrLn . calc)
    


Measured memory_bytes: 4320
#include<stdio.h>
int main(void)
{
  int A,B,C,sum,count,day;
  sum=0;
  day=0;
  count=0;
  scanf("%d",&A);
  scanf("%d",&B);
  scanf("%d",&C);
  while(sum<C)
    {
      count++;
      day++;
      sum=sum+A;
      if(count==7)
	{
	  sum=sum+B;
	  count=0;
	}
      //printf("%d\n",sum);
    }
  printf("%d\n",day);
  
  return 0;
}


Measured memory_bytes: 2092
#include <cstdio>
#include <algorithm>

#define MOD (100000007)

typedef long long lint;

using namespace std;

lint memo[1024][1024];

lint getWay(int x, int y)
{
	if (x == 0 || y == 0){
		return (1);
	}
	if (memo[x][y]){
		return (memo[x][y]);
	}
	
	return (memo[x][y] = (getWay(x, y - 1) + getWay(x - 1, y)) % MOD);
}

int main()
{
	int d[2], a[2], b[2];
	int mul;
	
	scanf("%d %d %d %d %d %d", &d[0], &d[1], &a[0], &a[1], &b[0], &b[1]);
	
	mul = 1;
	
	for (int i = 0; i < 2; i++){
		if (abs(a[i] - b[i]) == d[i] - abs(a[i] - b[i])){
			mul *= 2;
			a[i] = abs(a[i] - b[i]);
		}
		else {
			a[i] = min(abs(a[i] - b[i]), d[i] - abs(a[i] - b[i]));
		}
	}
	
	printf("%lld\n", getWay(a[0], a[1]) * mul % MOD);
	
	return (0);
}

Measured memory_bytes: 5160
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int hp = scanner.nextInt();
        int n = scanner.nextInt();
        List<Integer> damages = new ArrayList<>(n);
        List<Integer> costs = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            int d = scanner.nextInt();
            int c = scanner.nextInt();
            damages.add(d);
            costs.add(c);
        }
        int[] damage2cost = new int[hp + 1];
        for (int less_hp = 1; less_hp <= hp; less_hp++) {
            int minimam_cost = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int last_damage = damages.get(i);
                int last_cost = costs.get(i);
                int rest_hp = less_hp - last_damage;
                int cost;
                if(rest_hp < 0){
                    cost = last_cost;
                }else{
                    cost = last_cost + damage2cost[rest_hp];
                }
                if(cost < minimam_cost){
                    minimam_cost = cost;
                }
            }
            damage2cost[less_hp] = minimam_cost;
        }
        System.out.println(damage2cost[hp]);
    }
}

Measured memory_bytes: 25668
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve();
        }

        void Solve()
        {
            var tmp = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            int n = tmp[0];
            int y = tmp[1];

            bool solved = false;
            for (int man = 0; man <= n; man++)
            {
                for (int gosenn = 0; gosenn <= n - man; gosenn++)
                {
                    int sen = n - man - gosenn;
                    if (10000 * man + 5000 * gosenn + 1000 * sen == y)
                    {
                        Console.WriteLine(man + " " + gosenn + " " + sen);
                        solved = true;
                    }

                }
                if (solved)
                    break;
            }

            if (!solved)
                Console.WriteLine("-1 -1 -1");


        }

    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;



int main() {
  char b;cin >> b;
  char ans;
  if(b == 'A') ans = 'T';
  if(b == 'T') ans = 'A';
  if(b == 'C') ans = 'G';
  if(b == 'G') ans = 'C';
  cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3452
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;

typedef long long ll;
const int MAXN = 100010;

int n;
ll A[MAXN];

void solve() {
    vector<ll> IS = {-A[0]};
    for (int i=1;i<n;i++) {
        auto pos = upper_bound(IS.begin(), IS.end(), -A[i]);
        if (pos == IS.end()) {
            IS.push_back(-A[i]);
        } else {
            *pos = -A[i];
        }
    }
    cout << IS.size() << endl;
}

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

    cin >> n;
    for (int i=0;i<n;i++) {
        cin >> A[i];
    }
    solve();
}


Measured memory_bytes: 2168
#include <stdio.h>
int main(void) {
    int i,n,minr,nowr,maxd,nowd;
    scanf("%d",&n); //*n >= 2*
    scanf("%d %d",&minr,&nowr);
    maxd=nowd=nowr-minr;
    for(i=3;i<=n;i++){
        if(nowr<minr) minr=nowr;
        scanf("%d",&nowr);
        nowd=nowr-minr;
        if(nowd>maxd) maxd=nowd;
    }
    printf("%d\n",maxd);
    return 0;
}

Measured memory_bytes: 596
#include <stdio.h>

int main(){
    
    int i, j, n, u, k, v, N[110][110];
    
    scanf("%d", &n);
    
    for(i = 1; i <= n; i++){
        scanf("%d", &u);
        scanf("%d", &k);
        for(j = 1; j <= k; j++){
            scanf("%d", &v);
            N[u][v] = 1;
        }
    }
    
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            if(N[i][j] != 1) N[i][j] = 0;
            if(j > 1) printf(" ");
            printf("%d", N[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 644
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 5005 , P = 1e9 + 7;
int Pow(int x,int t) {int r=1;for(;t;t>>=1,x=ll(x)*x%P)if(t&1)r=ll(r)*x%P;return r;}
int fac[N] , ifac[N];

int comb(int a,int b) {
  if(a < b || a < 0 || b < 0)
    return 0;
  return ll(fac[a]) * ifac[b] % P * ifac[a - b] % P;
}

int main(){
  rep(i,0,N) fac[i] = i ? ll(fac[i-1]) * i % P : 1;
  rep(i,0,N) ifac[i] = Pow(fac[i] , P - 2);
  int n , A , B , C;
  cin >> n >> A >> B >> C;
  if(B & 1) {
    cout << 0 << endl;
    return 0;
  }
  int ans = 0;
  for(int cnt13=0;cnt13<=A&&cnt13<=C;cnt13++) {
    for(int cnt333=0;cnt13+cnt333*3<=C;cnt333++) {
      int remainC = C - cnt13 - cnt333 * 3;
      int way = B == 0 ? remainC == 0 : comb(remainC + B / 2  - 1 , remainC);
      way = ll(way) * fac[B / 2 + cnt13 + cnt333 + A - cnt13] % P
        * ifac[B / 2] % P * ifac[cnt13] % P * ifac[cnt333] % P * ifac[A - cnt13] % P;
      ans += way;
      if(ans >= P)
        ans -= P;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import math
A, B, H, M = (int(i) for i in input().split())  

hx = math.cos(math.radians(30 * H + (M / 2))) * A
hy = math.sin(math.radians(30 * H + (M / 2))) * A
mx = math.cos(math.radians(6 * M)) * B
my = math.sin(math.radians(6 * M)) * B

print(math.sqrt(abs(hx-mx) ** 2 + abs(hy-my) ** 2))



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

#define int long long int
#define rep(a,b,c) for(int a=b;a<c;a++)
#define repm(a,b,c) for(int a=(b-1);a>=c;a--)
#define pb push_back
#define str string
#define sf(a) scanfs("%d",&a)
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()

using namespace std;

const int INF = 1e18 + 9;
const int Mod = 1e9 + 7;
inline int replac(str s){double ans=0;rep(i,0,s.length()){ans+=(s[i]-'0')*pow(10,s.length()-i-1);}return (int)ans;}
inline string numstr(int m){str s="";while(m>0){char c;int a=m/10;if(a>0)a=m%(a*10);else a=m;c=(char)('0'+a);s+=c;m/=10;}str st="";for(int i=s.size()-1;i>=0;i--){st+=s[i];}return st;}
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
int cost[1002001];
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,d[1001];
    while(1){
    cin >> n >> m;
    if(n==0&&m==0)break;
    int ans=0;
    rep(i,0,n){
        cin >> d[i];
        if(ans<d[i]&&d[i]<=m)ans=d[i];
    }
    d[n]=0;
    int cou=0;
    rep(i,0,n+1){
        rep(j,0,n+1){
            cost[cou]=d[i]+d[j];
            if(cost[cou]>ans&&cost[cou]<=m)ans=cost[cou];
            cou++;
        }
    }
    sort(cost,cost+cou);
    int left=0;
    int right=cou;
    rep(i,0,cou){
        while((cost[i]+cost[right-1])>m)right--;
        int a=cost[i]+cost[right-1];
        if(right<i)break;
        //cout << right << " " << a << endl;
        if(a<=m)ans=max(a,ans);
    }
    cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 10856
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class C
{
	public static void Main()
	{
		int N = GetInt();
		int[] A = new int[N];
		for(int i = 0; i < N; i++)
			A[i] = GetInt();

		int min = A[0];
		int max = A[0];
		int iMin = 0;
		int iMax = 1;
		for(int i = 1; i < N; i++)
		{
			if(A[i] < min)
			{
				min = A[i];
				iMin = i;
			}
			if(A[i] > max)
			{
				max = A[i];
				iMax = i;
			}
		}

		StringBuilder sb = new StringBuilder();
		int num = min;
		for(int i = 0; i < N; i++)
		{
			if((i == iMin) || (i == iMax) || (A[i] < 0))
				continue;

			sb.AppendFormat($"{num} {A[i]}\n");
			num = num - A[i];
		}

		sb.AppendFormat($"{max} {num}\n");
		num = max - num;

		for(int i = 0; i < N; i++)
		{
			if((i == iMin) || (i == iMax) || (A[i] >= 0))
				continue;

			sb.AppendFormat($"{num} {A[i]}\n");
			num = num - A[i];
		}

		Console.WriteLine(num);
		Console.Write(sb);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}


Measured memory_bytes: 33708
s = input()
q = [0,0,0]
for i in s:
    if i == 'a':
        q[0] += 1
    elif i == 'b':
        q[1] += 1
    else:
        q[2] += 1

if max(q) - min(q) > 1:
    print('NO')
else:
    print('YES')

Measured memory_bytes: 39536
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define max 100005
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;

int main(){
    char s[3];
    cin>>s;
    rep(i,3){
        if(s[i]=='7'){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 3504
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;



int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
	
	
	int n,k;
	string s;
	cin>>n>>k>>s;
	
	s[k-1]=s[k-1]+('a'-'A');
	cout<<s<<endl;
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
//////////////////////////////////////////////////////
return 0;}











Measured memory_bytes: 256
// Crt. 2019-10-24  14:34:54
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int Mod = 1e9 + 7;

int n, m, f[102][100005], sum[100005];
int R[100005], val[100005];

int main() {
    cin >> m >> n;

    int cnt = 0;
    for (int l = 1, r; l <= m; l = r + 1)
        r = m / (m / l), R[++cnt] = r, val[cnt] = f[1][cnt] = r - l + 1;

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= cnt; ++j)
            sum[j] = (sum[j - 1] + f[i - 1][j]) % Mod;
        int pos = cnt;
        for (int j = 1; j <= cnt; ++j) {
            while (R[pos] > m / R[j]) --pos;
            f[i][j] = 1ll * val[j] * sum[pos] % Mod;
        }
    }

    int ans = 0;
    for (int i = 1; i <= cnt; ++i)
        ans = (ans + f[n][i]) % Mod;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 40192
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

using namespace std;

const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

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

	int n;
	cin >> n;
	pll ans = pll(1, 1);
	pll ta;
	ll d;
	rep(i, n) {
		cin >> ta.first >> ta.second;

		d = max(ans.first / ta.first + (ans.first % ta.first == 0 ? 0 : 1), ans.second / ta.second + (ans.second%ta.second == 0 ? 0 : 1));
		ans = pll(ta.first*d, ta.second*d);
	}

	cout << ans.first + ans.second << "\n";

	return 0;
}



Measured memory_bytes: 256
<?php
list($n) = ints();
$a = ints();
$cnt = 0;
for ($i = 0; $i < $n; ++$i) if ($i % 2 === 0 && $a[$i] % 2) ++$cnt;
echo $cnt;
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 16112
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        var arr = sc.ArrayInt(3);
        WriteLine(arr.OrderByDescending(i => i).Skip(1).Sum());
    }
}


class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


Measured memory_bytes: 13396
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>

using namespace std;

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

int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

static const double EPS = 1e-8;

int dp[1000000][5];

int main(){
	int n;
	while(~scanf("%d",&n)){
		if(n==0) break;

		memset(dp,0,sizeof(dp));

		dp[0][0] = 1;
		for(int i=1;i*i<=n;i++){
			for(int k=1;k<=4;k++){
				for(int j=i*i;j<=n;j++){
					dp[j][k] += dp[j-i*i][k-1];
				}
			}
		}

		printf("%d\n",dp[n][4] + dp[n][3] + dp[n][2] + dp[n][1]);
	}
}

Measured memory_bytes: 20724
use std::vec::Vec;
use std::cmp::*;
use std::collections::BinaryHeap;

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

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

fn main() {
  let n: usize = read();
  let mut g: Vec<Vec<(usize, u64)>> = vec![vec![]; n];
  for _ in 0..n-1 {
    let v: Vec<usize> = read_vec();
    g[v[0] - 1].push((v[1] - 1, v[2] as u64));
    g[v[1] - 1].push((v[0] - 1, v[2] as u64));
  }

  let (q, k) = {
    let v: Vec<usize> = read_vec();
    (v[0], v[1] - 1)
  };

  let mut tasks = Vec::new();
  for _ in 0..q {
    let v: Vec<usize> = read_vec();
    tasks.push((v[0] - 1, v[1] - 1));
  }

  //dijkstra法による単一始点からの最短経路長を探索
  let dist = dijkstra(n, &g, k);

  for (x, y) in tasks {
    println!("{}", dist[x] + dist[y]);
  }
}


fn dijkstra(n: usize, adj_list: &Vec<Vec<(usize, u64)>>, start: usize) -> Vec<u64> {
  let mut dist = vec![std::u64::MAX; n];
  let mut p_queue: BinaryHeap<(i64, usize)> = BinaryHeap::new();

  //init
  dist[start] = 0;
  p_queue.push((0, start));

  while !p_queue.is_empty() {
    // 起点となるノード
    let (cost, now)
      = match p_queue.pop() {
        None => break,
        Some(e) => (-e.0 as u64, e.1),
      };

    // 繋がっているノードを探索
    for &edge in &adj_list[now] {
      let next = edge.0;
      let weight = edge.1;

      if dist[next] > weight + cost {
        p_queue.push((-((weight + cost) as i64), next));
        dist[next] = weight + cost;
      }
    }

  }

  dist
}


Measured memory_bytes: 22780
def main():
    n = int(input())
    s = input()
    #rn = s.count("R")
    #wn = s.count("W")
    #red = 0
    #white = 0
    l = 0
    r = n-1
    ans = 0
    while(True):
        if(l >= n or r < 0):
            break
        if(s[l] == "R"):
            l += 1
            continue
        else:
            while(s[r] == "W"):
                if(r < 0):
                    print(0)
                    return
                r -= 1
            if(l >= r):
                break
            l += 1
            r -= 1
            ans += 1
            if(l >= r):
                break
    print(ans)



if __name__ == "__main__":
    main()


Measured memory_bytes: 67688
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
def main():
    n, m = map(int,input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        uf.unite(a, b)
    uf_lis = uf.parents
    ans = 0
    for p in uf_lis:
        if p < 0:
            ans = max(ans, -p)
    print(ans)


if __name__=='__main__':
    main()

Measured memory_bytes: 14644
using System;

class B {
    public static void Main() {
        var line = Console.ReadLine().Split();
        var k = int.Parse(line[0]);
        var s = int.Parse(line[1]);
        var a = new int[4, s + 2];
        for (int i = 0; i <= s; ++i) a[0, i + 1] = 1;
        for (int i = 1; i <= 3; ++i)
            for (int j = 0; j <= s; ++j) {
                var a1 = a[i, j] + a[i - 1, j + 1];
                var a2 = k <= j ? a[i - 1, j - k] : 0;
                a[i, j + 1] = a1 - a2;
            }
        Console.WriteLine(a[3, s + 1] - a[3, s]);
    }
}


Measured memory_bytes: 11152
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include <climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
struct P {
	ll pos, cost;
	bool operator<(const P &b) const { return cost < b.cost; }
	bool operator>(const P &b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) const { return cost < b.cost; }
	bool operator>(const E &b) const { return cost > b.cost; }
};
struct H {
	ll x, y;
	bool operator<(const H &b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) const { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) const { return (*this) != b; }
};
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int H, W, h, w;
int a[1000][1000];
signed main() {
	cin >> H >> W >> h >> w;
	if ((H == h && W == w) || (h == 1 && w == 1)) {
		cout << "No\n";
		return 0;
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			a[i][j] = 1000;
		}
	}
	int res = 0;
	int t = -(h*w - 1) * 1000 - 1;
	a[h - 1][w - 1] = t;
	for (int i = h - 1; i < H; i += h) {
		for (int j = w - 1; j < W; j += w) {
			a[i][j] = t;
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			res += a[i][j];
		}
	}
	if (res <= 0) {
		cout << "No\n";
		return 0;
	}
	cout << "Yes\n";
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cout << (j == 0 ? "" : " ") << a[i][j];
		}
		cout << endl;
	}
}

Measured memory_bytes: 5632
#include <bits/stdc++.h>
bool ACGT(char a){
  if(a == 'A' || a == 'C' || a == 'G' || a == 'T'){
    return true;
  }
  else{
    return false;
  }
}
using namespace std;
int main(){
  int ans=0,count=0;
  string S;
  cin >> S;
  int N=S.size();
  for(int i=0;i<N;i++){
    if(ACGT(S[i])){
      count++;
    }
    else{
      ans = max(ans,count);
      count = 0;
    }
    if(i == N-1){
      ans = max(ans,count);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define M (((long long)1e9)+7)
int main() {
    // your code goes here
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("res.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   	int n;
   	cin>>n;
   	long long ans=0;
   	for(int i=1;i<=n-1;i++)
   	{
   		ans+=n/i-(n%i==0);
   	}
   	cout<<ans;
   	return 0;
}

Measured memory_bytes: 3656
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
int a,b,c;
int main() {
	cin>>a>>b>>c;

	int R=a;
	if(R<b)R=b;
	if(R<c)R=c;

	cout<<a+b+c-R<<endl;
 	return 0;
}


Measured memory_bytes: 764
#include <stdio.h>

int main(){
    int a;
    scanf("%d", &a);
    printf("%d:%d:%d\n", a / 3600, (a - 3600*(a/3600))/60, a - 60*((a - 3600*(a/3600))/60) - 3600*(a/3600));
    return 0;
}


Measured memory_bytes: 2052
#include <stdio.h>
#define MOD 2019
#define NUM


int main(void)
{
    
    long long int a,b,i,j,L,R;
    scanf("%lld%lld",&L,&R);
    if(R-L>2019){
        a=0;
        printf("%lld\n",a);
        return 0;
    }
    b=2020;
    for(i=L;i<=(R-1);i++){
        
        for(j=(i+1);j<=R;j++){
            a=(i*j)%MOD;
            if(a<b)
                b=a;
        }
    }
   
    printf("%lld\n",b);
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back

typedef vector<int> vint;
typedef long long ll;

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

  vint x(5);
  for (auto &ref : x) {
    cin >> ref;
  }
  rep(i, 5) {
    if (x[i] == 0) {
      cout << i + 1 << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1000000007;
vl a1(5);
vl sousuu,pat;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
ll solve(ll a,ll x){
  if(x==0) return 0;
  if(a < 2) return a1[x];
  if(x <= sousuu[a-2]) return solve(a-1,x-1);
  else if(x == sousuu[a-2]+1) return pat[a-2] + 1;
  else if(x == 2*sousuu[a-2]+1||x == 2*sousuu[a-2]+2) return 2*pat[a-2] + 1;
  else return solve(a-1,x-sousuu[a-2]-2) + pat[a-2] + 1;
}
int main(){
  ll n,x;
  cin >> n >> x;
  sousuu.assign(n,0),pat.assign(n,0);
  sousuu[0] = 5;
  pat[0] = 3;
  a1[0] = 0;
  a1[1] = 1;
  a1[2] = 2;
  a1[3] = 3;
  a1[4] = 3;
  REP(i,n-1) {
    sousuu[i+1] = 2 * sousuu[i] + 3;
    pat[i+1] = 2 * pat[i] + 1;
  }
  cout << solve(n,x-1) << endl;

}


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

int main()
{
	int i,j,n,x,f=1;
	string ans = "No";
	vector <int> seki;
	cin >> n;
	for( i=f; i<10; i++ ){
		for( j=1; j<10; j++ ){
			seki.push_back( i*j );
		}
		f++;
	}
	for( x : seki){
		if( x==n ){
			ans = "Yes";
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> z(n);
    for (int i = 0; i < n; i++) {
        cin >> z[i];
    }
    ll zr = 0;
    ll jasd = 100;
    for (int i = 0; i < min(k,jasd); i++) {
        vector<ll> t(n+1);
        for (int j = 0; j < n; j++) {
            t[max(zr, j - z[j])]++;
            t[min(n, j + z[j]+1)]--;
        }
        for (int j = 1; j < n; j++) {
            t[j] += t[j - 1];
        }
        for (int j = 0; j < n; j++) {
            z[j] = t[j];
        }
    }
    for (int j = 0; j < n; j++) {
        cout << z[j] << " ";
    }
    cout << endl;
}

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

using namespace std;

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

  int n, k;
  cin >> n >> k;
  int res = k;
  for (int i = 1; i < n; ++i)
    res *= (k-1);
  cout << res << endl;

  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
	int ans = INT_MAX;
	for(int i=0;i<(int)s.length()-(int)t.length()+1;++i){
		int cnt = 0;
		for(int j=i;j<i+(int)t.length();++j){
			if(s[j]!=t[j-i])
				++cnt; 
		}
		ans = min(ans,cnt);
	}
	cout<<ans<<'\n';
	return 0;
}

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

int main()
{
  int a,b,c,cnt=0;
  cin >> a >> b	>> c;
  for(int i=a;i<=b;i++)
    {
      if(c%i==0) cnt++;
    }   
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n; cin >> n;
    int n_odd = 0;
    rep(i,n) {
        int x; cin >> x;
        if (x&1) n_odd++;
    }
    if (n_odd&1) cout << "NO" << endl;
    else cout << "YES" << endl; 
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long double ld;
const int maxn=1e5+10;

inline char gc(){
	return getchar();
	static const int maxs=1<<16;static char buf[maxs],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
    ll x=0;char c=gc();bool neg=0;
    while(c<'0'||c>'9'){if(c=='-') neg=1;c=gc();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=gc();
    return neg?(~x+1):x;
}

int N,a[maxn],mi[maxn],oi[maxn],ma[maxn],oa[maxn];
int stk[maxn][2],sh;

inline void calc(){
	mi[1]=ma[1]=a[1];
    for(int i=2;i<=N;i++){
    	if(a[i]-ma[i-1]<mi[i-1]-a[i]) mi[i]=a[i]-ma[i-1],oi[i]=0;
    	else mi[i]=mi[i-1]-a[i],oi[i]=1;
    	if(a[i]-mi[i-1]>ma[i-1]-a[i]) ma[i]=a[i]-mi[i-1],oa[i]=1;
    	else ma[i]=ma[i-1]-a[i],oa[i]=0;
    }
}

int main(){
    //freopen("","r",stdin);
    N=rd();for(int i=1;i<=N;i++) a[i]=rd();
    sort(a+1,a+N+1);
    int n=1;
    for(int i=1;i<=N&&a[i]<=0;i++) n=i;
    if(n==N) n--;
	int ans=0;
	for(int i=1;i<=n;i++) ans-=a[i];
	for(int i=n+1;i<=N;i++) ans+=a[i];
	printf("%d\n",ans);
	int now=a[N];
	for(int i=1;i<n;i++){
		printf("%d %d\n",now,a[i]);
		now-=a[i];
	}
	int now2=a[n];
	for(int i=n+1;i<N;i++){
		printf("%d %d\n",now2,a[i]);
		now2-=a[i];
	}
	printf("%d %d\n",now,now2);
    return 0;
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#define maxn 100100

int main()
{
    int n,t;
    int las,ans;
    while(~scanf("%d%d",&n,&t))
    {
        int x;
        las=ans=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&x);
            ans+=min(x-las,t);
            las=x;
        }
        ans+=t;
        printf("%d\n",ans);
    }

    return 0;
}


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

const int inf = 1e9;

signed main(void){
 int N; cin >> N;
  vector<int> X(N);
  for(int i = 0; i < N; i++){ cin >> X[i];}
  
  int ans = inf;
  
  for(int pos = -1000; pos <= 1000; pos++){
    
    int res = 0;
    
    for(int i = 0; i < N; i++){ 
      
      res += (X[i]-pos)*(X[i]-pos);
    }
    
    ans = min(ans,res);
    
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void)
{
	int x, h;

	scanf("%d", &x);
	scanf("%d", &h);
	while (x != 0 || h != 0){
		double height = sqrt(x * x / 4.0 + h * h);
		printf("%f\n", x * (x + 2 * height));
		scanf("%d", &x);
		scanf("%d", &h);
	}

	return 0;
}

Measured memory_bytes: 632
#include <stdio.h>

int main(void) {
    int W, H, x, y, r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if ((0 <=x-r) && (W >= x+r) && (H >= y + r) && (0 <= y - r)){
        printf("Yes");
    }
    else {
        printf("No");
    }
    printf("\n");
  
    return 0;
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(int argc, char const *argv[])
{
	int n, k; cin >> n >> k;
	if (k % 2) {
		ll cnt = 0;
		reps(i, 1, n + 1) {
			if (i % k == 0) cnt++;
		}
		printf("%lld\n", cnt * cnt * cnt);
	} else {
		ll cnt1 = 0, cnt2 = 0;
		reps(i, 1, n + 1) {
			if (i % k == 0) cnt1++;
			if (i % k == k / 2) cnt2++;
		}
		printf("%lld\n", cnt1 * cnt1 * cnt1 + cnt2 * cnt2 * cnt2);
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("fma")
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
ll n; 
ll a[100005];
vll adj[100005];
void dfs(ll u, ll p){
	ll sum = 0, mx = 0;
	for (ll i = 0; i < adj[u].size(); i++){
		ll v = adj[u][i]; if (v == p) continue;
		dfs(v, u); mx = max(mx, a[v]); sum += a[v];
	}
	ll ops = min(sum - mx, sum / 2);
	if (adj[u].size() == 1) return;
	if (a[u] > sum){
		cout << "NO\n"; exit(0);
	}
	if ((sum - a[u] > ops) && (adj[u].size() > 1)){
		cout << "NO\n"; exit(0);
	}
	a[u] = 2 * a[u] - sum;
	if (a[u] < 0){
		cout << "NO\n"; exit(0);
	}
}
int main(){
	fastio;
	cin >> n;
	for (ll i = 0; i < n; i++) cin >> a[i];
	if (n == 2){
		if (a[0] == a[1]) cout << "YES\n";
		else cout << "NO\n"; 
		return 0;
	}
	for (ll i = 0; i < n - 1; i++){
		ll u, v; cin >> u >> v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	for (ll i = 0; i < n; i++){
		if (adj[i].size() > 1){
			dfs(i, i); 
			if (a[i] != 0) cout << "NO\n";
			else cout << "YES\n";
			return 0;
		}
	}
}

Measured memory_bytes: 16464
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <map>

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

  if ((A+B) % 2) return puts("IMPOSSIBLE"), 0;
  printf("%d\n", (A+B)/2);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  string ans = "";
  if(a+b == c+d) ans = "Balanced";
  else if(a+b > c+d) ans = "Left";
  else ans = "Right";
  cout << ans << endl;
}

Measured memory_bytes: 3632
N = int(input())
X = [0]
for n in range(1,N+1):
    x = X[-1]+1

    r6 = 6
    while n-r6>=0:
        x = min(x, X[n-r6]+1)
        r6*=6

    r9 = 9
    while n-r9>=0:
        x = min(x, X[n-r9]+1)
        r9*=9

    X.append(x)

print(X[N])

Measured memory_bytes: 3860
N = int(input())
L = []
for i in range(N-1):
    L.append(list(map(int,input().split())))
for j in range(N):
    if j == N-1:
        print(0)
    else:
        t = L[j][0]+L[j][1]
        for k in range(j+1,N-1):
            if t >= L[k][1] and t%L[k][2] == 0:
                t += L[k][0]
            else:
                if t < L[k][1]:
                    t = L[k][0]+L[k][1]
                else:
                    t = t+L[k][2]-(t%L[k][2])+L[k][0]
        print(t)

Measured memory_bytes: 3188
#include <iostream>            
#include <vector>              
#include <string>              
#include <cstring>
#include <cmath>               
#include <algorithm>           
using namespace std;           

typedef long long ll;          

#define REP(var,n) for(int var=0;var<(n);var++)
#define REPP(var,n) for(int var=1;var<(n);var++)
#define ALL(c) (c).begin(),(c).end()

int main(){                    
  int N,a,b;

  cin >> N;

  if(N==1){                    
    cout << "Hello World" << endl;  
  }
  else{
    cin >> a >> b;
    cout <<  a+b << endl;
  }
  return 0;
}


Measured memory_bytes: 256
def intMap(): return map(int,input().split())
def intList(): return list(map(int, input().split())) #横並びの場合
def intListVertical(): [int(input()) for _ in range(N)] #縦並びの場合

#s = input()
n = int(input())
#s,t = input().split()
#n,m = intMap()
a = intList()
#w = intListVertical()

ans = 1
limit = 1000 * 1000 * 1000 * 1000 * 1000 * 1000

for i in range(n):
    if a[i] == 0:
        print(0)
        exit()

for i in range(n):
    ans *= a[i]
    if ans > limit:
        print(-1)
        exit()
print(ans)


Measured memory_bytes: 21996
N,Y = map(int,input().split())
f = False
for i in range(N+1):
    for j in range(N+1):
        k = N - i - j
        if k < 0:
            continue
        if 10000 * i + 5000 * j + 1000 * k == Y:
            print(i, j, k)
            f = True
            break
    if f :
        break
if (not f): 
    print(-1, -1, -1)


Measured memory_bytes: 3060
n = int(input())

tan = list(map(int, input().split()))

f = 0

a=True

for i in range(n-1):
    if tan[i] < tan[i+1] :
        f -= 1
    else :
        f += (tan[i]-tan[i+1])

    if f < 0 :
        f=0
    elif f >= 2 :
        print("No")
        exit()
    else :
        pass

if a :
    print("Yes")

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

typedef long long ll;

int main() {

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

    ll n = 0;
    cin >> n;
    vector<ll> v(n , 0);
    ll mn = 1e9 + 5;
    ll mx = -1e9 + 5;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        mn = min(mn, v[i]);
        mx = max(mx, v[i]);
    }

    ll ans = 1e9 + 5;
    for(int i = mn; i <= mx; i++) {
        ll temp = 0;
        for(int j = 0; j < n; j++) {
            temp += pow(abs(v[j] - i), 2);
        }
        ans = min(ans, temp);
    }   

    cout << ans << endl;



    return 0;
}

Measured memory_bytes: 256
import sys

n = int(input())
s = len(str(n))

_max = ""
for i in range(1, s+1):
    _max += "9"
if str(n).count("9") == s:
    print(s*9)
else:
    for j in range(1, 10):
        for k in range(0, s):
            if int(_max) - j*10**k <= n:
                tmp = str(int(_max) - j*10**k)
                amari = tmp.replace("9", "")
                if len(amari) != 0:
                    print(tmp.count("9")*9+int(amari))
                else:
                    print(tmp.count("9")*9)
                sys.exit()

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
 
using namespace std;
 
typedef pair<long long int, long long int> P;
long long int INF = 1e18;
 
int main(){
	
	int A, B;
	cin >> A >> B;
	
	if(B == 100){
		B = 101;
	}
	
	cout << B;
	
	for(int i = 0; i < A; i++){
		cout << "00";
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 256
from math import ceil

n,k = map(int,input().split())
A = list(map(int,input().split()))

l = 0
r = 10**9
ans = 0
while l+1 < r:  
  m = (l+r)//2  
  c = 0
  for a in A:
    c += ceil(a/m)-1
  if c <= k:
    ans = min(ans,m)
    r = m
  else:
    l = m
  
print(r)

Measured memory_bytes: 93976
#include <bits/stdc++.h>
using namespace std;
int main(){
    long n;
    long cnt = 0;
    cin >> n;
    vector<long> a(n+1);
    vector<long> b(n);
    for(int i=0;i<n+1;i++)cin >> a[i];
    for(int i=0;i<n;i++)cin >> b[i];
    for(int i=0;i<n;i++){
        if(a[i] < b[i]){
            cnt += a[i];
            b[i] -= a[i];
            if(a[i+1] < b[i]){
                cnt += a[i+1];
                 a[i+1] = 0;
            }else{
                cnt += b[i];
                a[i+1] -= b[i];
            }
        }else{
            cnt += b[i];
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 4796