akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static int[] value;
    public static char[] color;
    
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        
        int TC = in.nextInt();
        while (TC-- > 0) {
            value = new int[9];
            color = new char[9];
            
            for (int i = 0; i < 9; i++) {
                value[i] = in.nextInt();
            }
            for (int i = 0; i < 9; i++) {
                color[i] = in.next().charAt(0);
            }
            
            if (shwe("", 0, new boolean[9])) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
    
    public static boolean isValid(int a, int b, int c) {
        if (color[a] != color[b] || color[a] != color[c]) return false;
        if (value[a] == value[b] && value[a] == value[c]) return true;
        int[] arr = {value[a], value[b], value[c]};
        Arrays.sort(arr);
        if (arr[0] == arr[1] - 1 && arr[1] == arr[2] - 1) return true;
        return false;
    }
    
    public static boolean isValid(String str) {
        int a = Integer.parseInt(str.charAt(0)+"", 10);
        int b = Integer.parseInt(str.charAt(1)+"", 10);
        int c = Integer.parseInt(str.charAt(2)+"", 10);
        return isValid(a, b, c);
    }
    
    public static boolean shwe(String ans, int pos, boolean[] visited) {
        if (ans.length() == 9) {
            if (isValid(ans.substring(6))) return true;
            return false;
        }
        if (ans.length() == 6 && !isValid(ans.substring(3))) return false;
        if (ans.length() == 3 && !isValid(ans)) return false;
        if (pos >= 9) return false;
        if (visited[pos]) return shwe(ans, pos+1, visited);
        
        boolean ret = shwe(ans, pos+1, visited);
        visited[pos] = true;
        ret = ret || shwe(ans+pos+"", 0, visited);
        visited[pos] = false;
        
        return ret;
    }
}



Measured memory_bytes: 73424
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=1e9+7 ;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int x[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;cin>>k;
    cout<<x[k-1]<<endl;


    return 0;
}

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

const int N = 200010;

char str[N];

int main() {
	int n, a, b, c, d;
	scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
	scanf("%s", str + 1);
	if(c < d) {
		for(int i = a; i < d; i++) {
			if(str[i] == '#' && str[i + 1] == '#') {
				printf("No\n");
				return 0;
			}
		}
		printf("Yes\n");
		return 0;
	}
	else {
		for(int i = a; i < c; i++) {
			if(str[i] == '#' && str[i + 1] == '#') {
				printf("No\n");
				return 0;
			}
		}
		for(int i = b; i <= d; i++) {
			if(str[i - 1] == '.' && str[i] == '.' && str[i + 1] == '.') {
				printf("Yes\n");
				return 0;
			}
		}
		printf("No\n");
		return 0;
	}
	return 0;
}

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

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

//---------------------------

int main(){
    ll x; cin >> x;
    rep2(b, -1000, 1001){
        rep2(a, b, 1001){
            ll p = a, q = b;
            if(p*p*p*p*p - q*q*q*q*q == x){
                cout << p << " " << q << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3596
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[] map = new int[n];
        Arrays.fill(map, -1);

        map[n-1] = 0;
        for (int i = n-2; i >= 0; i--) {
            map[i] = Math.abs(arr[i+1]-arr[i]) + map[i+1];
            if (i+2 < n) {
                map[i] = Math.min(map[i], Math.abs(arr[i+2]-arr[i]) + map[i+2]);
            }
        }
        System.out.println(map[0]);
    }
}


Measured memory_bytes: 59512
package main

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

type IntList []int
type MemoInt struct {
	M map[int]int
	F func(int, func(int) int) int
}

func (a IntList) ChMax(i int, value int) bool {
	curV := a[i]
	if curV < value {
		a[i] = value
		return true
	}
	return false
}
func lib_MaxInt(values ...int) (max int, err error) {
	if len(values) == 0 {
		return 0, errors.New("empty slice is given")
	}
	max = values[0]
	for _, value := range values {
		if max < value {
			max = value
		}
	}
	return
}
func lib_MustMaxInt(values ...int) (max int) {
	max, err := lib_MaxInt(values...)
	if err != nil {
		panic(err)
	}
	return max
}
func lib_NewIntList(length int, initialValue int) IntList {
	ret := make([]int, length, length)
	for i := 0; i < length; i++ {
		ret[i] = initialValue
	}
	return ret
}
func lib_NewMemoInt(f func(int, func(int) int) int) *MemoInt {
	return &MemoInt{M: map[int]int{}, F: f}
}
func (m *MemoInt) Call(v int) int {
	if cachedResult, ok := m.M[v]; ok {
		return cachedResult
	}
	res := m.F(v, m.Call)
	m.M[v] = res
	return res
}
func main() {
	scanner := bufio.NewScanner(os.Stdin)
	const initialBufSize = 4096
	const maxBufSize = 1000000
	scanner.Buffer(make([]byte, initialBufSize), maxBufSize)
	scanner.Split(bufio.ScanWords)
	var N int
	scanner.Scan()
	N, _ = strconv.Atoi(scanner.Text())
	var M int
	scanner.Scan()
	M, _ = strconv.Atoi(scanner.Text())
	x := make([]int, M)
	y := make([]int, M)
	for i := 0; i < M; i++ {
		scanner.Scan()
		x[i], _ = strconv.Atoi(scanner.Text())
		scanner.Scan()
		y[i], _ = strconv.Atoi(scanner.Text())
	}
	fmt.Println(solve(N, M, x, y))
}
func solve(N int, M int, x []int, y []int) int {
	neighbors := make([][]int, N+5, N+5)
	dp := lib_NewIntList(N+5, 0)
	for i := 0; i < M; i++ {
		curX, curY := x[i], y[i]
		neighbors[curX] = append(neighbors[curX], curY)
	}
	memo := lib_NewMemoInt(func(n int, self func(int) int) int {
		for _, neighbor := range neighbors[n] {
			dp.ChMax(n, self(neighbor)+1)
		}
		return dp[n]
	})
	ret := 0
	for i := 1; i <= N; i++ {
		ret = lib_MustMaxInt(ret, memo.Call(i))
	}
	return ret
}


Measured memory_bytes: 34304
//B - Counting Roads
//Assunto:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100050
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n, m, x, y;
    cin >> n >> m;
    vector<int> adj[n+1];
    loop(i, 0, m) {
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    loop(i, 1, n+1) {
        cout << adj[i].size() << "\n";
    }
}

Measured memory_bytes: 256
n,wei = [int(x) for x in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)
dp = [[-1]*(wei+1) for x in range(n+1)]
for i in range(wei+1):
    dp[0][i] = 0

for i in range(n):
    for j in range(wei+1):
        if j<w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[n][wei])


Measured memory_bytes: 120172
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
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 (b<a) { a=b; return 1; } return 0; }
#define print(x) cout << (x) << endl;
#define sz(x) int(x.size())
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};


struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(ll n) : par(n, -1) { }
    void init(ll n) { par.assign(n, -1); }

    ll root(ll x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

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

    bool merge(ll x, ll y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

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

int main(void){
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int n,m;
    cin >> n >> m;
    vector<ll> a(m);
    vector<ll> b(m);
    rep(i,m){
      cin >> a[i] >> b[i];
      --a[i], --b[i];
    }
    vector<ll> ans(m);
  	ans[m-1] = (ll)n * (n - 1) / 2;

    UnionFind Uni(n);

    for(ll i = m-1; i >= 1; i--){
      ans[i-1] = ans[i];
      if(!(Uni.issame(a[i],b[i]))){
        ans[i-1] -= (long long)Uni.size(a[i]) * Uni.size(b[i]);
        Uni.merge(a[i],b[i]);
      }
    }
    rep(i,m){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 4480
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,K = map(int,readline().split())
A = np.array(readline().split(),np.int64)
F = np.array(readline().split(),np.int64)

A.sort(); F.sort(); F=F[::-1]

Asum = A.sum()

left = -1 # 不可能目標
right = 10**12 # 可能目標
while left+1 < right:
    mid = (left+right)//2
    if Asum - np.minimum(A,mid//F).sum() <= K:
        right = mid
    else:
        left = mid

answer = right
print(answer)


Measured memory_bytes: 26164
#include <string.h>
#include <stdio.h>
int main(void){
    char taro[100];
    char hanako[100];
    int i,n;
    int p_taro=0,p_hana=0;
    
    scanf("%d",&n);
    
    for(i=0; i<n; i++){
        scanf("%s",taro);
        scanf("%s",hanako);
        
        if(strcmp(taro,hanako) == 0){
            p_taro++;
            p_hana++;
        }
        
        else if(strcmp(taro,hanako) > 0){
            p_taro += 3;
        }
        
        else p_hana += 3;
    }
    
    printf("%d %d\n",p_taro,p_hana);
    return 0;
}

Measured memory_bytes: 604
object Main extends App {

  def gcd(i: Long, reminder: Long): Long =
    if (reminder == 0) i else gcd(reminder, i % reminder)

  def lcm(n: Long, m: Long): Long = (n*m) / gcd(m, n)

  for (str <- io.Source.stdin.getLines) {
    val Array(n, m) = str.split(" ").map(_.toLong)
    println(s"${gcd(n, m)} ${lcm(n, m)}")
  }
}

Measured memory_bytes: 43952
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}
std::vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend
#define all(x) (x).begin(),(x).end()
#define size_t ll
const int mod = 1000000007;
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
int n,ans=0,m=INT_MAX;
std::vector<int> p;
int main(){
  cin >> n;
  p.resize(n);
  for (size_t i = 0; i < n; i++) {
    cin >> p[i];
    if(m > p[i]){
      ans++;
      m = p[i];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = 10 ** 9 + 7

sum_x = 0
sum_y = 0

for i in range(n):
    sum_x += (2 * i + 1 - n) * x[i] % mod
for j in range(m):
    sum_y += (2 * j + 1 - m) * y[j] % mod

print((sum_x * sum_y) % mod)


Measured memory_bytes: 18624
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+11;
const int M=4e6+11;
const int mod=1e9+7;
int n,k,f[N][N],fac[M],ifac[M];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int qpow(int a,int b){
    int re=1;
    while(b){
        if(b&1) re=(re*a)%mod;
        b>>=1;a=a*a%mod;
    }return re;
}
int C(int a,int b){
    if(a<b) return 0;
    return fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
signed main(){
    n=read(),k=read();
    if(k==1) return puts("1"),0;
    fac[0]=1;ifac[0]=1;f[0][0]=1;
    for(int i=1;i<=n*k;i++) fac[i]=fac[i-1]*i%mod;
    ifac[n*k]=qpow(fac[n*k],mod-2);
    for(int i=n*k-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++){
            if(i>=j) f[i][j]+=f[i-1][j];
            f[i][j]=(f[i][j]+f[i][j-1]*C((n-j+1)*(k-1)+n-i-1,k-2)%mod)%mod;
        }
    printf("%lld\n",f[n][n]*fac[n]%mod);
    return 0;
}

Measured memory_bytes: 94208
N, A, B = map(int,input().split())
S = input()

a_counter = 0
b_counter = 0

for i in range(N):
  s = S[0]
  if s == "a" and a_counter + b_counter <A+B:
    a_counter += 1
    print("Yes")
  elif s == "b" and b_counter < B and a_counter + b_counter <A+B:
    b_counter += 1
    print("Yes")
  else:
    print("No")
  
  S = S[1:]

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

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;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

int main() {
  ll n, m;
  cin >> n;
  vector <ll> v(n);
  rep(i, n) cin >> v.at(i);
  cin >> m;
  rep(i, m) {
    ll a;
    cin >> a;
    a--;
    if (a < n-1) {
      if (v.at(a)+1 == v.at(a+1)) {
        continue;
      } else {
        v.at(a)++;
      }
    } else {
      if (v.at(a) == 2019) {
        continue;
      } else {
        v.at(a)++;
      }
    }
  }
  rep(i, n) {
    cout << v.at(i) << endl;
  }
}


Measured memory_bytes: 3112
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String str[];
		int dp1[];
		int dp2[];

		str = sc.next().split(",");
		dp1 = new int[str.length];
		dp1[0] = Integer.valueOf(str[0]);
		while (sc.hasNext()) {
			str = sc.next().split(",");
			dp2 = new int[str.length];
			if (dp1.length < dp2.length) {
				for (int i = 0; i < str.length; i++) {
					if (i == 0) {
						dp2[i] = dp1[0] + Integer.valueOf(str[0]);
					} else if (i == str.length - 1) {
						dp2[i] = dp1[dp1.length - 1] + Integer.valueOf(str[str.length - 1]);
					} else {
						dp2[i] = Math.max(dp1[i - 1], dp1[i]) + Integer.valueOf(str[i]);
					}
				}
			} else {
				for (int i = 0; i < str.length; i++) {
					dp2[i] = Math.max(dp1[i + 1], dp1[i]) + Integer.valueOf(str[i]);
				}
			}
			dp1 = dp2;
		}
		System.out.println(dp1[0]);
	}
}

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

#define DEBUG

#ifdef DEBUG
#define dump(x) cout << "[*] " #x ": " << x << endl
#define debug(x) x
#else
#define dump(x)
#define debug(x)
#endif

//#define int long long
typedef long long ll;
//constexpr int INF = 1e9;
//constexpr int MOD = 1000000007;

decltype(1) main() {
    //cin.tie(nullptr);
    //ios_base::sync_with_stdio(false);
    int h, n;
    int a;
    cin >> h >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        sum += a;
    }
    cout << (sum >= h ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 384
package main

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

var (
	in = bufio.NewScanner(os.Stdin)
)

func init() {
	in.Buffer([]byte{}, math.MaxInt64)
	in.Split(bufio.ScanWords)
}
func main() {
	a := readInt64Slice(3)
	fmt.Printf("%d %d %d ",a[2], a[0], a[1])
}

func readInt64Slice(n int) []int64 {
	line := readStringSlice(n)
	slice := make([]int64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseInt(tmp, 10, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)
	}
	return slice
}
func readFloat64Slice(n int) []float64 {
	line := readStringSlice(n)
	slice := make([]float64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseFloat(tmp, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)

	}
	return slice
}
func readString() string {
	in.Scan()
	return in.Text()

}
func readStringSlice(n int) []string {
	s := make([]string, n)
	for i := 0; i < n; i++ {
		s[i] = readString()
	}
	return s
}
func dump(value ...interface{}) {
	for _, v := range value {
		fmt.Printf("%#v\n", v)
	}
}

Measured memory_bytes: 640
/*
 ╔═══╦═══╦═══╗
 ║╔═╗║╔══╩╗╔╗║
 ║║░║║╚══╗║║║║
 ║║░║║╔══╝║║║║
 ║╚═╝║╚══╦╝╚╝║
 ╚══╗╠═══╩═══╝
 ░░░╚╝░░░░░░░░
 */

#include <bits/stdc++.h>
#define ll					long long
#define MOD					1000000007
#define MAX					1e9
#define MIN                 -1e9
#define PI					acos(-1.0)
#define vi					vector<int>
#define vii					vector<vi>
#define vll					vector<ll>
#define mid(s,e)			(s+(e-s)/2)
#define clz(n)				__builtin_clzll(n))

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template<typename T>
void printVec(const T &v, char sep=' ') {for (auto &i: v) cout << i << sep;}
template<typename T>
void printVecPair(const T &v, char sep=' ') {for (auto &i: v) cout << i.first <<" " << i.second<< sep;}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0);
	int n,w;
	cin>>n>>w;
	vector<ll> dp(w+1,0);
	while(n--) {
			int a,b;
			cin>>a>>b;
			auto dp2 = dp;
			for(int i=0;i<=w;i++) {
					if(i+a <= w) {
							dp[i+a] = max(dp[i+a], dp2[i] + b);
					}
			}
	}
	cout<<dp[w];
	
	return 0;
}





Measured memory_bytes: 1804
N, K = map(int, input().split())
*V, = map(int, input().split())
ans = 0

for l in range(K + 1):
	for r in range(K - l + 1):
		inHand = []
		if l + r > N:  # Nを超えてしまうありえない場合を処理
			break
		# inHandに左からl個、右からr個の要素を追加
		inHand = V[: l]
		inHand.extend(V[N - r:])
		tmp = sum(inHand)  # 現時点でのinHandの和をtmpとして負の要素をtmpから引いていく
		# inHand中の負の要素を消せるだけ消す
		inHand.sort()
		for i in range(min(K - l - r, l + r)):
			if inHand[i] >= 0:
				break
			tmp -= inHand[i]
		ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (i * j == N) {
                    System.out.println("Yes");
                    return;
                }
            }
        }

        System.out.println("No");
    }
}

Measured memory_bytes: 21844
input_number = int(input())
input_Hina = input().split()
a = 0
if input_Hina.count("G") > 0:
    a += 1
if input_Hina.count("W") > 0:
    a += 1
if input_Hina.count("Y") > 0:
    a += 1
if input_Hina.count("P") > 0:
    a += 1

if a == 4:
    print("Four")
elif a == 3:
    print("Three")


Measured memory_bytes: 3060
n = int(input())
a = sorted(map(int,input().split()))
b = sorted(map(int,input().split()))
c = sorted(map(int,input().split()))

lis = [0] * n
j = 0
for i in range(n):
    while j < n and a[j] < b[i]:
        j += 1
    lis[i] = j

li = [0] * n
m = 0
j = 0
for i in range(n):
    while j < n and b[j] < c[i]:
        m += lis[j]
        j += 1
    li[i] = m
print(sum(li))


Measured memory_bytes: 24564
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int a,s,d;
	cin>>a>>s>>d;
	int cnt=0;
	FORD(i,1000,1){
		if(a%i==0&&s%i==0){
			cnt++;
		}
		if(cnt==d){
			cout<<i<<endl;
			return 0;
		}
	}
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

struct tim{
	int h, m, s;
};

int main(void){

	tim s[3],t[3];
	int st,tt,zt;

	for(int i = 0; i < 3; i++){
		cin >> s[i].h >> s[i].m >> s[i].s >> t[i].h >> t[i].m >> t[i].s;
	}

	for (int i = 0; i < 3; i++){
		st = s[i].s + s[i].m * 60 + s[i].h * 60 * 60;
		tt = t[i].s + t[i].m * 60 + t[i].h * 60 * 60;
		zt = tt - st;
		cout << zt / 3600 << " " << (zt % 3600) / 60 << " " << ((zt % 3600) % 60) << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <algorithm>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void A_Beginner(void) {

	int N, R;
	cin >> N >> R;
	cout << ((N >= 10) ? R : R + 100 * (10 - N));
	return;
}

void B_Digits(void) {

	int N, K;
	cin >> N >> K;

	for (int loop = 0; loop < 40; loop++) {
		if (N < (int)pow(K, loop)) {
			cout << loop << flush;
			return;
		}
	}
	return;
}

int main(void) {

	//A_Beginner();
	B_Digits();
	return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())

info = ["." + "x" * (w - 1)] + [input() for i in range(h)]
INF = 10 ** 5
h += 1
dp = [[INF] * w for i in range(h)]
dp[0][0] =  0

for i in range(h):
    for j in range(w):
        for ii, jj in [(i, j + 1), (i + 1, j)] :
            if not(0 <= ii < h and 0 <= jj < w):
                continue
            if info[ii][jj] == "x":
                continue
            if info[i][j] != info[ii][jj] and info[ii][jj] == "#":
                dp[ii][jj] = min(dp[i][j] + 1, dp[ii][jj])
            else:
                dp[ii][jj] = min(dp[i][j], dp[ii][jj])
print(dp[-1][-1])

Measured memory_bytes: 41584
#include<bits/stdc++.h>
using namespace std;
int main()
{ios_base::sync_with_stdio(false);

long long int n,ans=0;
string s,temp;
cin>>n;
long long int r[n],g[n],b[n];
cin>>s;r[0]=g[0]=b[0]=0;
if(s[0]=='R')
r[0]=1;
else if(s[0]=='G')
    g[0]=1;
else
    b[0]=1;
for(long long int i=1;i<n;i++)
{
r[i]=r[i-1];g[i]=g[i-1];b[i]=b[i-1];
    if(s[i]=='R')
r[i]+=1;
else if(s[i]=='G')
    g[i]+=1;
else
    b[i]+=1;
}
long long int R=r[n-1],G=g[n-1],B=b[n-1];
//cout<<R<<G<<B<<endl;
for(long long int i=0;i<n;i++)
    for(long long int j=i+1;j<n;j++)
{
    if(s[j]!=s[i])
    {
        if((s[i]=='R'&&s[j]=='G')||(s[i]=='G'&&s[j]=='R'))
            ans+=(B-b[j]);
        else if((s[i]=='B'&&s[j]=='G')||(s[i]=='G'&&s[j]=='B'))
            ans+=(R-r[j]);
        else
            ans+=(G-g[j]);
            if(2*j-i<n)
             if(s[2*j-i]!=s[i]&&s[2*j-i]!=s[j])
                ans--;
    }

}
cout<<ans<<endl;
}


Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {

    static long ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int[] a = new int[n];
        for (int i = 0; i < k; i++) {
            int d = Integer.parseInt(sc.next());
            for (int j = 0; j < d; j++) {
                a[Integer.parseInt(sc.next()) - 1]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 41432
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);

	String N = sc.next();
	String T = sc.next();
	int cnt = 0;

	if(N.charAt(0)==T.charAt(0)) {
		cnt++;
	}
	if(N.charAt(1)==T.charAt(1)) {
		cnt++;
	}
	if(N.charAt(2)==T.charAt(2)) {
		cnt++;
	}
	System.out.println(cnt);

	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <deque>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

stack<int> cars;

int main() {
	int input = -1;

	cin >> input;
	while (input != -1) {
		if (input > 0) {
			cars.push(input);
		} else {
			cout << cars.top() << endl;
			cars.pop();
		}

		input = -1;
		cin >> input;
	}

	return 0;
}

/*@@@@@@@@@@@@@@@@@@@@@@@@@*/
/*@                       @*/
/*@ debug output erased ? @*/
/*@                       @*/
/*@@@@@@@@@@@@@@@@@@@@@@@@@*/

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

int main(){
  int a, b;
  std::cin >> a >> b;
  if (a > b) {
    for(int i = 0; i < a; i++){
      cout << b;
    }
  }
  else{
    for(int i = 0; i < b; i++){
      cout << a; 
    }
  }
  return 0;
}

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

typedef long long int ll;
typedef long int li;

const ll mod = 1000000007;
const ll inf = 1000000000000000000;

typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vli> vvli;
typedef vector<vll> vvll;
typedef vector<vs> vvs;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;

#pragma GCC optimize ("-O3")
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define pb push_back
#define mp make_pair
#define fs first
#define sec second
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define tol(s) transform(s.begin(), s.end(), s.begin(), ::tolower);
#define tou(s) transform(s.begin(), s.end(), s.begin(), ::toupper);
#define all(v) v.begin(), v.end()
#define FOR(i, j, k, in) for(li i=j; i<k; i+=in)
#define RFOR(i, j, k, de) for(li i=j; i>=k; i-=de)
#define rep(i,j,k) FOR(i, j, k, 1)
#define rrep(i,j,k) RFOR(i, j, k, 1)
#define repc(v) for(auto it=v.begin(); it!=v.end(); it++)
#define T ll t; cin>>t; while(t--)

int main(){
  FAST

   int k;
  cin>>k;
  int a[]= {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout<<a[k-1];
  return 0;
}








Measured memory_bytes: 256
#include<stdio.h>

#define MAX_LENGTH 32

int main(void)
{
        char line[MAX_LENGTH];
        int a,b;

        fgets(line, sizeof(line), stdin);
        sscanf(line, "%d %d", &a, &b);

        if( a < b ) {
                printf("a < b\n");
        } else if ( a == b) {
                printf("a == b\n");
        } else {
                printf("a > b\n");
        }

        return 0;
}

Measured memory_bytes: 588
#include <stdio.h>

int main(){
  
    long long a, b, c;
    
    scanf("%lld %lld.%lld", &a, &b, &c);
    
    long long d = b * 100 + c;
    long long x = (a * d) / 100;
  
    printf("%lld", x);
    
    return 0;
}

Measured memory_bytes: 1732
import java.util.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(System.in);
		int p = Integer.parseInt(sc.next());
		int q = Integer.parseInt(sc.next());
		int r = Integer.parseInt(sc.next());
		sc.close();
		int pq = p + q;
		int qr = q + r;
		int rp = r + p;
		System.out.println(Math.min(Math.min(pq, qr),rp));
	}
}

Measured memory_bytes: 21844
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int n;

int main()
{
	while(scanf("%d",&n),n)
	{
		int p,d1,d2,mxd=-1,mxp;
		rep(i,n)
		{
			scanf("%d%d%d",&p,&d1,&d2);
			if(d1+d2>mxd)mxd=d1+d2,mxp=p;
		}
		printf("%d %d\n",mxp,mxd);
	}
	return 0;
}

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

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    rep(i,n) ans += ll(i+1)*ll(n-i);
    rep(i,n-1)
    {
        ll s, t;
        cin >> s >> t;
        s--; t--;
        if(s > t) swap(s, t);
        ans -= ll(s+1)*ll(n-t);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
#define ll long long
#define dat(a,b) (dat){a,b}
#define data(a,b,c,d) (data){a,b,c,d}
using namespace std;
const int N=5e5+50,inf=1e9;
inline int gi() {
  char ch=getchar(); int q=0,x=0;
  while(ch<'0'||ch>'9') q=(ch=='-'?1:q),ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int a[N],o[N],tot,top;
struct data{ int l,r,k,b; }w[N];
struct dat{
  ll k,b;
  void operator += (const dat &c){
    k+=c.k,b+=c.b; return;
  }
}f[N];
int main(){
  int n=gi(),s;
  for (int i=1; i<=n; ++i) a[i]=gi();
  for (int i=1; i<=n; ++i){
    s=a[i]-i,o[++top]=s;
    w[++tot]=data(-inf,s,-1,s);
    w[++tot]=data(s,inf,1,-s);
  }
  o[++top]=inf,o[++top]=-inf;
  sort(o+1,o+top+1);
  top=unique(o+1,o+top+1)-o-1;
  for (int i=1; i<=tot; ++i){
    w[i].l=lower_bound(o+1,o+top+1,w[i].l)-o;
    w[i].r=lower_bound(o+1,o+top+1,w[i].r)-o;
  }
  for (int i=1; i<=tot; ++i)
    f[w[i].l]+=dat(w[i].k,w[i].b),f[w[i].r+1]+=dat(-w[i].k,-w[i].b);
  for (int i=1; i<=top; ++i)
    f[i]+=f[i-1];
  ll ans=1e18;
  for (int i=1; i<=top; ++i)
    ans=min(ans,f[i].k*o[i]+f[i].b);
  cout<<ans;
  return 0;
}

Measured memory_bytes: 16640
#include <cstdio>
#include <cmath>

int main(){
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if(std::abs(a-c)<=d || (std::abs(a-b)<=d && std::abs(b-c)<=d)) printf("Yes\n");
    else printf("No\n");
    return 0;
}

Measured memory_bytes: 128
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<int, II> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 3010;
const int MAXM = 600010;
const int MAXK = 110;
const int MAXQ = 200010;

int dp[MAXN][MAXN], n, t;
II a[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> t;
    FOR(i,1,n) cin >> a[i].FI >> a[i].SE;
    sort(a+1, a+n+1);

    dp[0][0] = 0;
    FOR(i,1,t-1) dp[0][i] = -1000000000;

    FOR(i,1,n)
        FOR(j,0,t-1) {
            dp[i][j] = dp[i-1][j];
            if (j - a[i].FI >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-a[i].FI] + a[i].SE);
        }

    int res = 0;
    FOR(i,0,n) {
        int Max = 0;
        FOR(j,0,t-1) Max = max(Max, dp[i][j]);
        int Max2 = 0;
        FOR(j,i+1,n) Max2 = max(Max2, a[j].SE);
        res = max(res, Max + Max2);
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 35584
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   ff   first
#define   ss   second
#define   pii  pair<int,int>
using namespace std;

inline void solve(){
    string  s; cin >> s;
    int len=sz(s),res=1000000;
    for (int i=0;i<len-2;i++){
        int ans=0,h=0,c=1;
        for (int j=i,k=100;j<i+3;j++,k/=10){
            ans += (s[j]-'0')*k;
        } 
        res = min(res,abs(ans-753));
    }
    cout << res << endl;
    
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define ll long long int
#define ss second
#define ff first
#define pb push_back
#define all(v) v.begin(),v.end()
#define unik(v)  v.erase(unique(v.begin(),v.end()),v.end())
using namespace std;
typedef pair<int, int> pii;
const ll mod = 998244353;
const int sz = 200000 + 3, inf = 1e9 + 10;
vector<int>adj[2000 + 10];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, x, y;
	cin >> n >> x >> y;

	std::vector<int> count(n, 0);

	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int d_ij = j - i;
			int d_ixyj = abs(i - x) + 1 + abs(j - y);
			int d_iyxj = abs(i - y) + 1 + abs(j - x);
			int d_min = min({d_ij, d_ixyj, d_iyxj});
			count.at(d_min) += 1;
		}
	}
	for (int i = 1; i < n; i++)cout << count[i] << "\n";

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<int> s(n);
    REP(i, n) cin >> s[i];
    int q;
    cin >> q;
    int t;
    int ans = 0;
    while (q--) {
        cin >> t;
        auto p = lower_bound(ALL(s), t);
        if (p != s.end() && *p == t) ans++;
    }
    cout << ans << endl;

}




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

typedef long long LL;
const int N = 524288 + 5, mo = 924844033, g = 5;
int n, sz[N], rev[N];
vector<int> E[N];
LL c[N], a[N], b[N], f[N];

void dfs(int x, int f){
	sz[x] = 1;
	for (int i = 0; i < E[x].size(); ++i){
		int y = E[x][i];
		if (y == f) continue;
		dfs(y, x);
		sz[x] += sz[y];
		--c[sz[y]];
		--c[n - sz[y]];
	}
}

LL pwr(LL a, LL b){
	LL res = 1;
	for (; b; b >>= 1, (a *= a) %= mo)
		if (b & 1) (res *= a) %= mo;
	return res;
}

LL inv(LL x){return pwr(x, mo - 2);}

void NTT(LL *a, int len, int d = 1) {
	for (int i = 0; i < len; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	int id = 0;
	for (int m = 2; m <= len; m <<= 1) {
		id++;
		LL wm = pwr(g, (d * (mo - 1) / m) + mo - 1);
		for (int i = 0; i < len; i += m) {
			LL w = 1;
			for (int j = i; j < i + m / 2; j++) {
				LL u = a[j], v = w * a[j + m / 2] % mo;
				a[j] = (u + v) % mo;
				a[j + m / 2] = (u - v) % mo;
				w = w * wm % mo;
			}
		}
	}
	if (d == -1) {LL iv = inv(len); for (int i = 0; i < len; i++) a[i] = a[i] * iv % mo;}
}

int main(){
	scanf("%d", &n);
	REP(i, 2, n){
		int x, y;
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1, 0); c[n] = n; f[0] = 1;
	REP(i, 1, n) f[i] = f[i - 1] * i % mo;
	REP(i, 0, n) a[i] = c[i] * f[i];
	REP(i, 0, n) b[i] = inv(f[i]);
	for (int i = 0; i <= n / 2; ++i) swap(a[i], a[n - i]);
	int len;
	for (len = 1; len < 2 * (n + 1); len <<= 1);
	for (int i = 1; i < len; ++i)
		if (i & 1) rev[i] = (rev[i >> 1] >> 1) ^ (len >> 1);
		else rev[i] = (rev[i >> 1] >> 1);
	NTT(a, len); NTT(b, len);
	for (int i = 0; i < len; ++i) a[i] = a[i] * b[i] % mo;
	NTT(a, len, -1);
	PER(i, n - 1, 0){
		LL ans = a[i];
		ans = ans * inv(f[n - i]) % mo;
		printf("%lld\n", (ans + mo) % mo);
	}
	return 0;
}

Measured memory_bytes: 48128
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>
#include <set>
#include <list>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

int main()
{
	int A, B;
	cin >> A >> B;
	cout << A * B << endl;
	return 0;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define until(x) while(!(x))
#define unless(x) if(!(x))
#define all(x) (x).begin(),(x).end()

map<int,char> ma;
int32_t main(){
	int n,m;
	string s,t;
	cin>>n>>m;
	cin>>s>>t;
	int len = (n*m)/__gcd(n,m);
	for(int i=0;i<n;i++){
		ma[i*(len/n)+1]=s[i];
	}
	for(int i=0;i<m;i++){
		if(ma.count(i*(len/m)+1)){
			if(ma[i*(len/m)+1]!=t[i]){
				cout<<-1;
				return 0;
			}
		}
	}
	cout<<len;
}


Measured memory_bytes: 6144
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}


int main(){
  ll N;
  cin>>N;
  vector<ll> d(N);
  rep(i,N){
    cin>>d[i];
  }
  sort(d.begin(),d.end());
  ll me=(N-1)/2;
  ll an=me+1;

  if(d[me]==d[an]) cout<<"0"<<endl;
  else{
    ll ans=d[an]-d[me];
    cout<<ans<<endl;
  }
}



Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
int segment[1000005];
int init(int n);
void update(int i,int num,int n);
int find(int a,int b,int left,int right,int node);
int main(){
  int n;
  int q;
  cin>>n>>q;
  n=init(n);
  fill(segment,segment+n*2,INT_MAX);
  for(int i=0;i<q;i++){
    int com;
    cin>>com;
    if(com==0){
      int k,a;
      cin>>k>>a;
      update(k,a,n);
    }else if(com==1){
      int a,b;
      cin>>a>>b;
      cout<<find(a,b,0,n-1,0)<<endl;
    }
  }
  return(0);
}

int init(int n){
  int a=1;
  while(a<n){
    a*=2;
  }
  return(a);
}

void update(int i,int num,int n){
  i+=n-1;
  segment[i]=num;
  while(i>0){
    i=(i-1)/2;
    segment[i]=min(segment[i*2+1],segment[i*2+2]);
  }
  return;
}

int find(int a,int b,int left,int right,int node){
  if(a<=left&&right<=b){
    return segment[node];
  }
  if(right<a||b<left){
    return INT_MAX;
  }
  int vleft=find(a,b,left,(left+right)/2,node*2+1);
  int vright=find(a,b,(left+right)/2+1,right,node*2+2);
  return min(vleft,vright);
}

Measured memory_bytes: 4104
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main(void)
{
    std::string s;
    std::cin >> s;

    long long ans = 0;

    for (int i = 0; i < (1 << (s.length() - 1)); i++) {
        long long temp_ans = 0;
        long long num = s[0] - '0';
        for (int j = 0; j < s.length() - 1; j++) {
            if ((1 << j) & i) {
                temp_ans += num;
                num = s[j + 1] - '0';
            } else {
                num *= 10;
                num += s[j + 1] - '0';
            }
        }

        ans += temp_ans + num;
    }

    std::cout << ans << std::endl;
}


Measured memory_bytes: 760
#include <stdio.h>
#include <string.h>
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
char s1[100001],s2[100001];
int main()
{
    int n,m;
    scanf("%d%d%s%s",&n,&m,s1,s2);
    long long len=(long long)n*m/gcd(n,m),step1=len/n,step2=len/m,pos1=0,pos2=0,j=0;
    for (int i=0;i<n;++i,pos1+=step1)
    {
        while (pos2<pos1)
        {
            ++j;
            pos2+=step2;
        }
        if (pos1==pos2&&s1[i]!=s2[j])
        {
            printf("-1\n");
            return 0;
        }
    }
    printf("%lld\n",len);
    return 0;
}


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

int main() {
  int A, B;
  cin >> A >> B;
  for (int ans = 1; ans < 10000; ++ans) {
    if (ans * 8 / 100 == A && ans * 10 / 100 == B) {
      cout << ans << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}


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

int main(){

    int h[10004], n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> h[i];

    int min = h[0], cont=0;
    for(int i=0; i<n; i++){
        if(h[i] >= min) cont++;
        min = max(h[i], min);
    }
    cout << cont << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int> vec(n, 0);
	for(int i = 0; i < n; ++i)cin>>vec[i];
	vector<int> table(n, 0);
	table[0] = vec[0];
	for(int i = 1; i < n; ++i){
		if(vec[i] > vec[i - 1]){
			table[i] = table[i - 1] + abs(vec[i] - vec[i - 1]);
		}
		else if(vec[i] == vec[i - 1]){
			table[i] = table[i - 1];
		}
		else {
			table[i] = table[i - 1];
		}
	}
	cout<<table[n - 1]<<endl;
	return 0;
}


Measured memory_bytes: 256