akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int INF = 1e9 + 5;

vector <int> h;
vector <int> dp;
int n;
int k;

int solve(int idx){

    if(dp[idx] != INF){
        return dp[idx];
    }
    
    int menor = INF;

    for(int i=1;i<=k;i++){
        
        if(idx + i < n){
            menor = min(menor, solve(idx+i) + abs(h[idx] - h[idx+i]));
        }else{
            if(i==1) return 0;
            else return dp[idx] = min(menor,INF);
        }
    }


    return dp[idx] = menor;


}

int main(){

    scanf("%d",&n);
    scanf("%d",&k);
    dp.assign(n,INF);
    
    for(int i=0;i<n;i++){
        int height;
        scanf("%d",&height);
        h.push_back(height);
    }

    printf("%d\n",solve(0));

    return 0;
}

Measured memory_bytes: 7416
#include<bits/stdc++.h>
#define ll long long
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define mod 1000000007
#define f first
#define sec second
#define gcd(x,y) __gcd(x, y)
using namespace std;
int main()
{
	ll X, K, D;
  cin >> X >> K >> D;
  X = abs(X);
  ll k = X / D;
  if (K <= k) {
    cout << X - K * D << endl;
  } else {
    X = X - k * D;
    K -= k;
    if (K % 2) {
      cout << abs(X - D) << endl;
    } else {
      cout << X << endl;
    }
  }
}


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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i
# 元indexを保持して座標位置順にソート
X.sort()
Y.sort()

edges = []
for i in range(1, N):
    # 座標上で隣り合う頂点同士で辺集合を作る
    edges.append((X[i-1][1], X[i][1], X[i][0] - X[i-1][0]))
    edges.append((Y[i-1][1], Y[i][1], Y[i][0] - Y[i-1][0]))
# コスト順にソート
edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0
# Union-Findで閉路を作らない確認をして最小全域木を作る
for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
print(ans)


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

#include <bits/stdc++.h>
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;
typedef pair<LLI,LLI> PII;
#define Lowbit(x) (x & (-x))
const int inf = 0x3f3f3f;
const int maxn = (500000 + 10);


int main() {
//    freopen("/home/qihan/Documents/in","r",stdin);
//    freopen("/home/qihan/Documents/out","w",stdout);
	int sx,sy,ex,ey;
	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	int x = ex - sx,y = ey - sy;
	for(int i = 1;i <= y;i ++)  printf("U");
	for(int i = 1;i <= x;i ++)  printf("R");
	for(int i = 1;i <= y;i ++)  printf("D");
	for(int i = 1;i <= x;i ++)  printf("L");
	printf("L");
	for(int i = 1;i <= y + 1;i ++)  printf("U");
	for(int i = 1;i <= x + 1;i ++)  printf("R");
	printf("D");
	printf("R");
	for(int i = 1;i <= y + 1;i ++)  printf("D");
	for(int i = 1;i <= x + 1;i ++)  printf("L");
	printf("U\n");
	return 0;
}

Measured memory_bytes: 256
def d_teleporter():
    N, K = [int(i) for i in input().split()]
    A = [int(i) - 1 for i in input().split()]  # 0-origin

    from collections import defaultdict
    visit = [0]
    visit_dict = defaultdict(list)
    visit_dict[0] = [0]
    current = 0
    is_found_first = False
    for i in range(N):
        current = A[current]
        if len(visit_dict[current]) == 1 and not is_found_first:
            count_to_loop = visit_dict[current][0]
            loop_length = i - visit_dict[current][0] + 1
            is_found_first = True
        visit.append(current)
        visit_dict[current].append(i + 1)

    if K <= N:
        return visit[K] + 1
    net_moving_time = ((K - count_to_loop) % loop_length) + count_to_loop
    # 上の visit に必要な分だけ付け足してもいいが，実行時間は変わらなかった
    current = 0
    for _ in range(net_moving_time):
        current = A[current]
    return current + 1

print(d_teleporter())

Measured memory_bytes: 56804
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 06/16/20 21:00:53
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int n,k; cin>>n>>k;
  vector<int> A(n); for (auto& a:A) cin>>a;
  auto suma = accumulate(A.begin(), A.end(), 0ll);
  set<ll> cands = {1, suma};
  for (int k = 2; k <= sqrt(suma); k++) {
    if (suma%k==0) {
      cands.insert(k);
      cands.insert(suma/k);
    }
  }
  auto ok = [&](int t) {
    vector<int> M(n);
    for (int i = 0; i < n; i++) {
      M[i] = A[i]%t;
    }
    sort(M.begin(), M.end());
    int l = 0, r = n-1;
    while (l < n and M[l] == 0)
      l++;
    int c = 0;
    while (l<r) {
      auto d = min(M[l], t-M[r]);
      M[l] -= d;
      M[r] += d;
      if (M[l] == 0)
        l++;
      if (M[r] == t)
        r--;
      c += d;
    }
    return c <= k;
  };
  int ans = 1;
  for (auto it = cands.rbegin(); it != cands.rend(); ++it) {
    if (ok(*it)) {
      ans = *it;
      break;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N;
int x[MAXN],y[MAXN];
int id[MAXN],cnt,fa[MAXN];
struct node {
    int u,v,c;
}E[MAXN * 10];
int getfa(int u) {
    return fa[u] == u ? u : fa[u] = getfa(fa[u]);
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {read(x[i]);read(y[i]);}
    for(int i = 1 ; i <= N ; ++i) id[i] = i;
    sort(id + 1,id + N + 1,[](int a,int b) {return x[a] < x[b];});
    for(int i = 1 ; i < N ; ++i) {
	E[++cnt] = (node){id[i],id[i + 1],x[id[i + 1]] - x[id[i]]};
    }
    for(int i = 1 ; i <= N ; ++i) id[i] = i;
    sort(id + 1,id + N + 1,[](int a,int b) {return y[a] < y[b];});
    for(int i = 1 ; i < N ; ++i) {
	E[++cnt] = (node){id[i],id[i + 1],y[id[i + 1]] - y[id[i]]};
    }
    sort(E + 1,E + cnt + 1,[](node a,node b){return a.c < b.c;});
    for(int i = 1 ; i <= N ; ++i) fa[i] = i;
    int ans = 0;
    for(int i = 1 ; i <= cnt ; ++i) {
	if(getfa(E[i].u) != getfa(E[i].v)) {
	    ans += E[i].c;
	    fa[getfa(E[i].u)] = getfa(E[i].v);
	}
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 7424
#include<stdio.h>
#include<string.h>
#define N 1000000

int main(){
  int n, q, time[N], i, sumT1=0, sumT2=0, T;
  char name[N][10];
  
  scanf("%d%d", &n, &q);
  for(i=0; i<n; i++)
    scanf("%s%d", name[i], &time[i]);

  for(i=0; i<n; i++)
    sumT1 += time[i];
  //printf("%d\n", sumT1);
    
  i=0;
  while(sumT1 != sumT2){
    T = time[i] - q;
    
    if(T > 0){
      sumT2 +=  q;
      time[n] = T;
      strcpy(name[n], name[i]);
      n++;
    }

    else{
      sumT2 += time[i];

      printf("%s %d\n", name[i], sumT2);   
    }
    //printf("%d\n", sumT2);
    
    i++;
  }
  return 0;
}



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

using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  ll a[n];
  ll ika=0;
  ll ziyu=0;
  ll min=1000000000;
  ll ans=0;
  rep(i,n){
    cin >> a[i];
    if(a[i]<0){
      ika++;
    }
    else if(a[i]==0){
      ziyu++;
    }
    if(min>labs(a[i])){
      min=labs(a[i]);
    }
    ans+=labs(a[i]);
  }
  if(ika%2==1&&ziyu%2==0){
    ans-=min*2;
  }
  cout << ans << endl;

}


Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
#include <cmath>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

const double EPS = 1e-9;

double memo[260][260];
double data[260];
int n, m, l;

double dp[260][260];

inline double dbl(double a){ return a * a; }

int main(){
  while(scanf("%d%d%d", &n, &m, &l), n + m + l){
    REP(i,n) scanf("%lf", data + i);
    for(int len = 2; len <= n; len++){
      for(int start = 0; start + len <= n; start++){
        double mx = *max_element(data + start, data + start + len);
        double mn = *min_element(data + start, data + start + len);
        double dst = (mx - mn) / ((1 << l) - 1);

        double gosa = 0.0;

        if(dst > EPS){
          REP(i,len){
            double sa = data[start + i] - mn;
            int j = (int)floor(sa / dst + 0.5);
            double tmp = 1e10;
            for(int ii = j - 1; ii <= j + 1; ii++)
              tmp = min(tmp, dbl((mn + dst * ii) - data[start + i]));
            gosa += tmp;
          }
        }

        memo[start][start + len] = gosa;
      }
    }

    const double inf = 1e10;
    REP(i,n + 1) REP(j, m + 1)
      dp[i][j] = inf;

    dp[0][0] = 0.0;
    REP(i,n) REP(j,m) if(dp[i][j] != inf){
      for(int len = 2; i + len <= n; len++)
        dp[i + len][j + 1] = min(dp[i + len][j + 1], dp[i][j] + memo[i][i + len]);
    }

    printf("%.8f\n", dp[n][m]);
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>

#define REP(n) for(int i = 0;i < n;i++)
typedef long long int ll;
using namespace std;
#define MAX_A 1000000005

int main(){


    string s,t,u;
    cin >> s >> t >> u;
    s[0] = char(s[0]-'a' + 'A');
    t[0] = char(t[0]-'a' + 'A');
    u[0] = char(u[0]-'a' + 'A');

    cout << s[0] << t[0] << u[0] << endl;



    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef long long int ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}

//------------------変数-----------------------//
ll n, m;
typedef pair<ll, ll> P;

ll rec[90001];//kachi,kazu
ll toorimemo[114514];
vector<vector<ll>> G(301);
bool vis[300] = { false };
ll maxa = 0;
//-------------------関数----------------------//


int main() {
	ll k,cnt=1; cin >> n >> k;
	cnt *= k;
	REP(i, n - 1) { cnt *= (k - 1); }
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
import collections
d=collections.defaultdict(int)
for i in a:
    d[i]+=1
mod=(10**9)+7

if n%2==0:
    x=[i for i in d.keys()]
    x=sorted(x)
    for i in range(len(x)):
        if i==0 and (x[i]!=1 or d[x[i]]!=2):
            print(0)
            exit()
        elif i>=1:
            if x[i]-x[i-1]!=2 or d[x[i]]!=2:
                print(0)
                exit()
    print((2**len(x))%mod)
else:
    x=[i for i in d.keys()]
    x=sorted(x)
    if x[0]!=0 or d[x[0]]!=1:
        print(0)
        exit()
    x=x[1:]
    for i in range(len(x)):
        if i==0 and (x[i]!=2 or d[x[i]]!=2):
            print(0)
            exit()
        elif i>=1:
            if x[i]-x[i-1]!=2 or d[x[i]]!=2:
                print(0)
                exit()
    print((2**len(x))%mod)

Measured memory_bytes: 14692
n = int(input())
v = [int(a) for a in input().split()]

v_even = []
v_odd = []

for i in range(n):
    if i % 2 == 0:
        v_even.append(v[i])
    else:
        v_odd.append(v[i])

even_list = [0]*max(v_even)
odd_list = [0]*max(v_odd)
for j in range(len(v_even)):
    even_list[v_even[j]-1] += 1
    odd_list[v_odd[j]-1] += 1

even_list_sorted = sorted(even_list)
odd_list_sorted = sorted(odd_list)

if even_list.index(even_list_sorted[-1]) != odd_list.index(odd_list_sorted[-1]):
    ans = n - even_list_sorted[-1] - odd_list_sorted[-1]
elif len(even_list) == 1:
    ans = n // 2
elif even_list_sorted[-2] >= odd_list_sorted[-2]:
    ans = n - even_list_sorted[-2] - odd_list_sorted[-1]
else:
    ans = n - even_list_sorted[-1] - odd_list_sorted[-2]
    
print(ans)

Measured memory_bytes: 14268
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func Max(a, b int) int {
  if a < b { return b }
  return a
}

const p = 100000

func Solve1(N, M int, A []int) int {
  P := make([]int, 2 * p + 1)
  for _, a := range A {
    P[a + 1]++
  }
  for i := 0; i < 2 * p; i++ {
    P[i + 1] += P[i]
    P[i] = N - P[i]
  }
  low, high := 0, 2 * p + 1
  for ; high - low > 1; {
    med := (low + high) / 2
    cnt := 0
    for _, a := range A {
      cnt += P[Max(med - a, 0)]
    }
    if cnt < M {
      high = med
    } else {
      low = med
    }
  }
  S := make([]int, N + 1)
  for i, a := range A {
    S[i + 1] = S[i] + a
  }
  cnt := 0
  ans := 0
  for _, a := range A {
    partner := P[Max(low - a, 0)]
    cnt += partner
    ans += S[partner] + a * partner
  }
  ans -= low * (cnt - M)
  return ans
}

func main() {
  NM := NextIntVec()
  N, M := NM[0], NM[1]
  A := NextIntVec()
  sort.Sort(sort.Reverse(sort.IntSlice(A)))
  Write(Solve1(N, M, A))
  Output()
}

Measured memory_bytes: 7552
import java.util.Scanner;
public class Main{
	public static void main(String[]args) {
		Scanner input=new Scanner(System.in);
		int a=input.nextInt();
		int b=input.nextInt();
		int c=input.nextInt();
		if((a==5&&b==5&&c==7)||(a==5&&b==7&&c==5)||(a==7&&b==5&&c==5)) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 26944
// Problem : B - Substring
// Contest : AtCoder - AtCoder Beginner Contest 177
// URL : https://atcoder.jp/contests/abc177/tasks/abc177_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args&&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#define int long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define mod 998244353
#define bug cout<<"HY"<<endl
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define numize(A) A.numize(unique(A.begin(), A.end()) - A.begin())
typedef pair<int,int> P;
int power(int a,int b)
{
    if(b==0)
        return 1;
    if(b%2==0)
        return (power((a*a)%mod,b/2))%mod;
    return (a*(power((a*a)%mod,b/2))%mod)%mod;
}
int modInv(int n)
{
    return power(n, MOD-2);
}
int nCr(int n, int r, int p=MOD)
{
   if (r==0)
      return 1;
    int Fact[n+1];
    Fact[0] = 1;
    for (int i=1 ; i<=n; i++)
    {
        Fact[i] = (Fact[i-1]*i)%p;
    }
    return (((Fact[n]* modInv(Fact[r])) % MOD) *(modInv(Fact[n-r]) % MOD)) % MOD;
}
double PI=3.14159265359;
void solve()
{
	string s,t;
	cin>>s;
	cin>>t;
	int i,ans=1e9,j;
	for(i=0;i<s.length();i++)
	{
		int cnt=0;
		for(j=0;j<t.length() && i+j<s.length();j++)
		{
			if(s[i+j]!=t[j])
				cnt++;
		}
		if(j==t.length())
			ans=min(ans,cnt);
	}
	cout<<ans<<endl;
}
int32_t main()
{
    boost;
    int  t=1;
    // cin>>t;
    while(t--)
    {
    	solve();
    }
}


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

using namespace std;
long long s;
vector<long long> vec;

long long f(long long);
int main(){
  cin >> s;
  while(true){
    vec.push_back(s);
    s = f(s);
    if(find(vec.begin(),vec.end(),s)!=vec.end()){
      cout << vec.size() + 1 << endl;
      break;
    }
  }
  return 0;
}

long long f(long long n){
  if(n % 2 == 0){
    return n/2;
  }
  else{
    return 3 * n + 1;
  }
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int s = a + b + c;
    if (s - a == a || s - b == b || s - c == c) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
N = int(input())
grid = [list(map(int, input().split())) for _ in range(2)]
dp_upper = [grid[0][0]]
dp_lower = [grid[0][0] + grid[1][0]]

for i in range(1, N):
    dp_upper.append(dp_upper[i - 1] + grid[0][i])
    dp_lower.append(max(dp_upper[i], dp_lower[i - 1]) + grid[1][i])
print(dp_lower[-1])

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


int main(){

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

  if (2*x ==y){cout <<"Yes";}
  else if((y-(2*x)) <= 2*x  && (y-(2*x)) >0 &&  (y-(2*x))%2 == 0){cout << "Yes";}
  else{cout <<"No";}
  return 0;
}

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

#define MOD 1000000007
#define ll long long int 
#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int dp[100001];
vector<int> v[100001+1];

void dfs(int index){

    if(dp[index]!= -1) return;
    dp[index] = 0;
    for (int i = 0; i < v[index].size(); ++i)
    {
        dfs(v[index][i]);
        dp[index] = max(dp[index],1+dp[v[index][i]]);
    }
}

int main()
{
    off;
    
    int n,m;cin>>n>>m;
    bool root[n+1];    

    for (int i = 1; i <= n; ++i)
    {
        dp[i] = -1;
        root[i] = true;
    }

    for (int i = 1; i <= m; ++i)
    {
        int x,y;cin>>x>>y;
        v[x].push_back(y);
        root[y] = false;
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if(root[i]){
            dfs(i);
            ans = max(ans, dp[i]);
        }
    }

    cout<<ans;

    return 0;
}


Measured memory_bytes: 10880
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string S(ll n){stringstream ss;string s;ss<<n;ss>>s;return s;}
ll N(string s){stringstream ss;ll n;ss<<s;ss>>n;return n;}
string Z(string s){int i;for(i=0;i<s.size()-1;i++)if(s[i]!='0')break;return s.substr(i);}
string ADD(string s,string t) {
  if(s.size()<t.size())swap(s,t);s='0'+s;
  while(s.size()>t.size())t='0'+t;int c=0;
  for(int i=s.size()-1; i>=0; i--) {
    if(c){if(s[i]=='9'){s[i]='0';c=1;}else{s[i]=(char)(s[i]+1);c=0;}}
    int sum=(int)s[i]+(int)t[i]-'0'*2;
    if(sum>=10){s[i]=(char)(sum-10+'0');c=1;}
    else s[i]=(char)(sum+'0');
  }
  return Z(s);
}
string MUL(string s,string t) {
  string z1="",ans="";
  for(int i=t.size()-1; i>=0; i--) {
    string z2="",r="";
    for(int j=s.size()-1; j>=0; j--){r=ADD(r,S((s[j]-'0')*(t[i]-'0'))+z2);z2+="0";}
    ans=ADD(ans,r+z1);z1+="0";
  }
  return Z(ans);
}
string a[]={"","Man","Oku","Cho","Kei","Gai","Jo","Jou","Ko","Kan","Sei","Sai","Gok","Ggs","Asg","Nyt","Fks","Mts"};

int main() {
  int n;
  string m;
  while(cin >> m >> n && n) {
    string s="1";
    for(int i=0; i<n; i++) s=MUL(s,m);
    string ans="";
    for(int i=s.size()-4,k=0; i>=-3; k++,i-=4) {
      int d=min(4,4+i);
      string t=s.substr(max(0,i),d);
      int x=N(t);
      if(!x) continue;
      t=S(x);
      ans=t+a[k]+ans;
    }
    cout << ans << endl;
  }
  return 0;
}


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

signed main() {
    int a,b;
    cin >> a >> b;
    for (int x=1; x!=1300; x++) {
        if (floor(x * 0.08) == a && floor(x * 0.1) == b) {
            cout << x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s; int x, y;
  cin >> s >> x >> y;
  int n = len(s);
  int i = 0;
  while(i < n && s[i] != 'T') {
    x--;
    i++;
  }
  x = abs(x); y = abs(y);
  vector<int> a, b;
  int status = 0;
  int c = 0;
  while(i < n) {
    if (s[i] == 'T') {
      if (c == 0) {
        status ^= 1;
        i++;
        continue;
      }
      if (status == 0) a.pb(c);
      else b.pb(c);
      c = 0;
      status ^= 1;
      i++;
      continue;
    }
    c++;
    i++;
    if (i == n) {
      if (c != 0) {
        if (status == 0) a.pb(c);
        else b.pb(c);
      }
    }
  }
  int ma = 0, mb = 0;
  for (int i : a) ma += i;
  for (int i : b) mb += i;
  if (ma < x || mb < y || (ma-x) % 2 == 1 || (mb-y) % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  bitset<8001> dp1, dp2;
  dp1[0] = 1;
  for (int i : a) dp1 |= (dp1 << i);
  dp2[0] = 1;
  for (int i : b) dp2 |= (dp2 << i);
  if (dp1[(ma-x)/2] == 1 && dp2[(mb-y)/2] == 1) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


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

using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<LL> vl;
typedef vector<vector<LL>> vvl;
typedef vector<vector<vector<LL>>> vvvl;


const int inf = 1e9+7;
const LL INF = 1e18+5;
const int mod = 1e9+7;
const int mxN = 1e5+5;
const int mxM = 1e5+5;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("E:\\Coding\\Programming\\input.txt", "r", stdin);
    freopen("E:\\Coding\\Programming\\output.txt", "w", stdout);
    #endif
    string s;
    cin>>s;
    int n=s.size();
    if(s[n-1]=='s'){
        cout<<s<<"es"<<endl;
    }else{
        cout<<s<<"s"<<endl;
    }
}

Measured memory_bytes: 3628
/*
 * ALDS1_7_D.cpp
 *
 *  Created on: May 3, 2018
 *      Author: 13743
 */

#include<iostream>
#include<stack>

using namespace std;

int n;
int pre[42];
int in[42];
int preInv[42];
int inInv[42];

stack<int> post;

void reconstruct(int key, int l, int r) {
	if(l > r) return;
	post.push(key);
	int c = inInv[key];
	int leftT = c - l;
	reconstruct(pre[preInv[key]+leftT+1], c+1, r);
	reconstruct(pre[preInv[key]+1], l, c-1);
}

int main() {
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> pre[i];
		preInv[pre[i]] = i;
	}
	for(int i=1; i<=n; i++) {
		cin >> in[i];
		inInv[in[i]] = i;
	}

	reconstruct(pre[1], 1, n);

	cout << post.top();
	post.pop();
	while(!post.empty()) {
		cout << " " << post.top();
		post.pop();
	}
	cout << endl;
}





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

//The Shortest Path on A Rhombic Path
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<String> l = new ArrayList<String>();
		while(sc.hasNext())l.add(sc.next());
		int n = l.size();
		int[][] a = new int[n][];
		for(int i=0;i<n;i++){
			String[] s = l.get(i).split(",");
			int k = s.length;
			a[i] = new int[k];
			for(int j=0;j<k;j++)a[i][j]=Integer.parseInt(s[j]);
		}
		int[] dp = {a[0][0]};
		for(int i=1;i<n;i++){
			int[] tmp = new int[a[i].length];
			for(int j=0;j<tmp.length;j++){
				if(i<=n/2){
					if(j==0)tmp[j]=dp[j]+a[i][j];
					else if(j==tmp.length-1)tmp[j]=dp[j-1]+a[i][j];
					else tmp[j]=Math.max(dp[j-1]+a[i][j], dp[j]+a[i][j]);
				}
				else{
					tmp[j] = Math.max(dp[j]+a[i][j], dp[j+1]+a[i][j]);
				}
			}
			dp = tmp;
		}
		System.out.println(dp[0]);
	}
}

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

using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const ll mod = 1e9 + 7;
int n;
ll cnt[64][2];
ll a[N], p2[64];
int main() {
	cin >> n;
	p2[0] = 1; for (int i = 1; i <= 60; ++i) p2[i] = (p2[i - 1] * 2) % mod;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		for (int j = 0; j < 60; ++j)
			if (a[i] & (1LL << j)) cnt[j][1]++;
			else cnt[j][0]++;
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 60; ++j)
			if (a[i] & (1LL << j)) cnt[j][1]--;
			else cnt[j][0]--;
		for (int j=0; j<60; ++j)
			if (a[i] & (1LL << j)) {
				ll tmp = p2[j] * cnt[j][0]; tmp %= mod;
				ans += tmp;
				ans %= mod;
			}
			else {
				ll tmp = p2[j] * cnt[j][1]; tmp %= mod;
				ans += tmp;
				ans %= mod;
			}
	}
	cout << ans << endl;
}


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

using ll = long long;

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

    int N;
    cin >> N;
    vector<pair<int, int>> AB;

    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        AB.emplace_back(B, A);
    }
    sort(AB.begin(), AB.end());
    
    ll acc_time = 0;
    for (auto ab: AB) {
        acc_time += ab.second;
        if (acc_time > ab.first) {
            cout << "No" << '\n';
            return 0;
        }
    }

    cout << "Yes" << '\n';

    return 0;
}


Measured memory_bytes: 2420
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#define PI acos(-1.0)
using namespace std;
int main(){
	string s;
	int n,k;
	cin >> n >> k >> s;
	s[k-1] = s[k-1] + 32;
	cout << s; 
	return 0;
}

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

using namespace std;

const long long N = 2e5+10;
long long a[N];
int main()
{
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    for (int i=0;i<n;++i){
        cin >> a[i];
    }
    long long sum=0;
    for (int i=0;i<n-1;++i){
        if (a[i]>a[i+1]) {
            sum += a[i] - a[i+1];
            a[i+1] = a[i];
        }
    }
    cout << sum ;
    return 0;
}


Measured memory_bytes: 5188
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const ll MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse
// struct Edge {
//   int to, id;
//   Edge(int a, int b): to(a), id(b) {}
// };

struct Matrix {
	ll val[50][50];
	Matrix () {
		rep(i,50) {
			rep(j,50) {
				val[i][j]=0;
			}
		}
	}
};

Matrix operator*(Matrix a,Matrix b) {
	Matrix c;
	rep(i,50) rep(j,50) rep(k,50) {
		c.val[i][j]+=(a.val[i][k]*b.val[k][j])%MOD;
		c.val[i][j]%=MOD;
	}
	return c;
}

Matrix I,A;

Matrix power(Matrix x, ll b) {
	if (b==0) return I;
	Matrix res = power(x,b/2);
	res = res * res;
	if (b%2==1) {
		res = res * x;
	}
	return res;
}


int main(int argc, char const *argv[])
{
	rep(i,50) I.val[i][i]=1;

	ll n,k;cin>>n>>k;

	rep(i,n) {
		rep(j,n) {
			cin>>A.val[i][j];
		}
	}

	Matrix A_k = power(A,k);

	ll ans = 0;

	rep(i,n) {
		rep(j,n) {
			ans+=A_k.val[i][j];
			ans%=MOD;
		}
	}
	

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 9600
#include<iostream>
using namespace std;
int main()
{
    long long a[10],i,x;
    for(i=1;i<=5;i++)
    {
        cin>>a[i];
        if(a[i]==0)
        {
            x=i;
        }
    }
    cout<<x<<endl;
    return 0;
}

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

int main(){
    long long n,a,b;
    cin >> n >> a >> b;
    if((b-a)%2 == 0) cout << (b-a)/2 << endl;
    else cout << min(n-b+1,a-1+1) + (b-a-1)/2 << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

        int n = sc.nextInt();
        int x = sc.nextInt();
        int count = 0;

        while (!(n == 0 && x == 0)) {
            for (int i = 1; i <= n - 2; i++) {
                for (int j = i + 1; j <= n - 1; j++) {
                    for (int k = j + 1; k <= n; k++) {
                        int sum = i + j + k;
                        if (sum == x) {
                            count++;
                        }
                        sum = 0;
                    }
                }
            }

            System.out.println(count);
            n = sc.nextInt();
            x = sc.nextInt();
            count = 0;
        }

        sc.close();
    }
}


Measured memory_bytes: 27128
import math
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n-1)]

result = []
for i in range(n-1):
    t = e[i][0] + e[i][1]
    for x in e[i+1:]:
        if t <= x[1]:
            t = x[0] + x[1]
            continue
        t = math.ceil((t-x[1])/x[2])*x[2] + x[1] + x[0]
    result .append(t)

result.append(0)
for x in result:
    print(x)

Measured memory_bytes: 3188
X,Y,Z,K = (int(x) for x in input().split())
A = sorted([int(x) for x in input().split()])[::-1]
B = sorted([int(x) for x in input().split()])[::-1]
C = sorted([int(x) for x in input().split()])[::-1]

AB = []
for i in range(X):
    for j in range(Y):
        if i*j > K:
            break
        AB.append(A[i]+B[j])
AB = sorted(AB)[::-1]

ans = []
for i in range(min(K,len(AB))):
    for j in range(min(K,Z)):
        if i*j > K:
            break
        ans.append(AB[i]+C[j])
ans.sort()

for i in range(K):
    print(ans[-i-1])


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

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

  int min_cost = 1001;
  rep(i, N)
  {
    int c, t;
    cin >> c >> t;
    if (t <= T)
      min_cost = min(min_cost, c);
  }

  if (min_cost == 1001)
  {
    cout << "TLE" << endl;
    return 0;
  }
  cout << min_cost << endl;
  return 0;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int countAB(string s) {
    return cast(int) s.zip(s[1..$]).count!(e => e[0] == 'A' && e[1] == 'B');
}

int calc(string[] a) {
    int ans = a.map!(countAB).sum;

    int xa = 0; // ...A : A で終わる
    int bx = 0; // B... : B で始まる
    int ba = 0; // B..A : B で始まり、A で終わる
    foreach (s; a) {
        auto front = s[0];
        auto last = s[$-1];
        if (front == 'B' && last == 'A') ba++;
        else if (front == 'B') bx++;
        else if (last == 'A') xa++;
    }

    // ba をつなぐ
    if (ba > 0) {
        ans += ba - 1;
        // 両サイドに xa, bx をつける
        if (xa > 0) {
            ans++;
            xa--;
        }
        if (bx > 0) {
            ans++;
            bx--;
        }
    }

    // xa, bx でペアを作る
    ans += min(xa, bx);
    return ans;
}

void main() {
    int n = readint;
    string[] a;
    for (int i = 0; i < n; i++) a ~= read!string;
    writeln(calc(a));
}



Measured memory_bytes: 2556
# encoding: utf-8
anten = []
5.times do
  x = gets.chomp.to_i
  anten << x
end
K = gets.chomp.to_i
# p anten
# p K
f = true
for i in 0..3 do
  for j in (i+1)..4 do
    if (anten[j] - anten[i]) > K then
      f = false
      break;
    end
  end
end
if f then
  puts 'Yay!'
else
  puts ':('
end

Measured memory_bytes: 1788
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> Heap;

inline void Max_Heapify(int node)
{
	int l = node * 2;
	int r = node * 2 + 1;

	int largest;

	if (l < Heap.size())
	{
		if (Heap[node] < Heap[l])
		{
			largest = l;
		}
		else
		{
			largest = node;
		}
	}
	else
	{
		largest = node;
	}

	if (r < Heap.size())
	{
		if (Heap[largest] < Heap[r])
		{
			largest = r;
		}
	}

	if (largest != node)
	{
		swap(Heap[largest], Heap[node]);

		Max_Heapify(largest);
	}
}

int main()
{
	int N; scanf("%d", &N); Heap.push_back(0);

	int tmp;

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &tmp);

		Heap.push_back(tmp);
	}

	for (int i = N / 2; i >= 1; i--)
	{
		Max_Heapify(i);
	}

	for (int i = 1; i <= N; i++)
	{
		printf(" %d", Heap[i]);
	}

	printf("\n");
	
	return 0;
}

Measured memory_bytes: 4424
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
  x = 0; char c = getchar(); int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if (f) x = -x;
}

#define pb push_back
const int N = 3e5 + 233;
int dfn[N], out[N], clk, st[N], top, id[N], dep[N], fa[N], sum[N];
int n;
vector <int> G[N];
inline void dfs(int u, int fat) {
  dfn[u] = ++ clk;
  dep[u] = dep[fa[u] = fat] + 1;
  for (auto v : G[u]) if (v != fat) dfs(v, u);
  out[u] = clk;
}

inline void work(int u, int fat, int Maxid, int Secid) {
  if (u > Maxid) Secid = Maxid, Maxid = u;
  else if (u > Secid) Secid = u;
  // cout << u << " " << Maxid << " " << Secid << "tt\n";
  st[++ top] = u; id[u] = top;
  if (u != 1) {
    int t = dep[Maxid] > dep[Secid] ? Maxid : st[id[Maxid] + 1];
    // cout << u << " " << t << "\n";
    sum[dfn[t]] ++; sum[out[t] + 1] --;
  }
  for (auto v : G[u]) if (v != fat) work(v, u, Maxid, Secid);
  -- top;
}

int main(void) {
  read(n);
  rep (i, n - 1) {
    int x, y; read(x); read(y);
    G[x].pb(y); G[y].pb(x);
  }
  dfs(1, 0); work(1, 0, 0, 0);
  rep (i, n) sum[i] += sum[i - 1];
  for (int i = 2; i <= n; i ++) cout << sum[dfn[i]] << " "; cout << "\n";
}


Measured memory_bytes: 28928
# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
ans = [[i+1] for i in range(N)]
for i in range(N):
    ans[i].append(A[i])
ans.sort(key=lambda x: x[1])
for i in range(N):
    print(ans[i][0], end=" ")

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int streak = 0;
    int maxStreak = 0;
    for (int i = 0; i < 3; i++){
        if (s[i] == 'R')
            streak++;
        else{
            maxStreak = max(streak, maxStreak);
            streak = 0;
        }
            
    }
    maxStreak = max(streak, maxStreak);
    cout << maxStreak << endl;
    return 0;
}

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

typedef long long int lli;
const lli MOD = 1e9+7;

int n;
string s;

lli memo[3001][3001];
lli f(int i, int last) {
  if (last < 0 || last > n-i)
    return 0;
  if (i == n)
    return 1;
  if (memo[i][last] != -1)
    return memo[i][last];
  lli ans;
  if (s[i-1] == '<')
    ans = (f(i, last+1) + f(i+1, last))%MOD;
  else
    ans = (f(i, last-1) + f(i+1, last-1))%MOD;
  memo[i][last] = ans;
  return ans;
}

int main() {
  for (int i=0; i<3001; ++i)
    memset(memo[i], -1, 3001*sizeof(lli));
  cin >> n >> s;
  lli ans=0;
  for (int j=0; j<n; ++j)
    ans = (ans + f(1, j))%MOD;
  cout << ans << endl;
}

Measured memory_bytes: 281472
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <functional>
#include <cmath>
#include <cstring>
#include <numeric>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <complex>
#include <list>
#include <cassert>
#include <deque>

#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()

using namespace std;
using ll = long long;

/*
struct UnionFind {
    // union tree
    // used for tracking a set of elements partitioned into a number of disjoint subsets
    // rankなしでの実装

    vector<int> par;
    // par[i] means i's parent
    // (ex) par[3] = 2 means 2 is a parent of 3

    UnionFind(int N) : par(N) {
      //used for initialization
      for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
      // データxが属する木の根を再帰で得る
      // root(x) = {xの木の根}
      if (par[x] == x) return x;
      return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
      // xとyのtreeのmerge
      int rx = root(x); //xの根をrx
      int ry = root(y); //yの根をry
      if (rx == ry) return; //同じ時はそのままに
      par[rx] = ry; //xの根rxをyの根ryにつける
    }

    bool same(int x, int y) {
      // 2つのデータx, yが属する木が同じならtrueを返す
      int rx = root(x);
      int ry = root(y);
      return rx == ry;
    }
};

template<typename T>
struct SegTree {
  //segment tree

  //木は配列で表現
  vector<T> seg;
  //木の1/2の大きさ
  int size;
  //単位元
  const T unit;
  //比較関数の型
  using F = function<T(T,T)>;
  //mergeする関数
  const F f;

  //単位元がaで大きさnのsegtreeの初期化を行う
  //大きさnとはすなわち葉の数がnであることをいう
  SegTree(int n, const T a, const F f) : unit(a), f(f) {
    size = 1;
    while(size < n) size <<= 1;
    seg.assign(2*size, unit);
    size--;
  }

  //k番目にtを代入する
  void set(int k, const T& t) {
    seg[k + size] = t;
  }

  //関数fによって木を構築する
  void build(){
    for (int i = size - 1; i >=0; i--){
      seg[i] = f(seg[i*2+1],seg[i*2+2]);
    }
  }

  //i番目の要素を返す
  T operator[](const int i){
    return seg[i + size];
  }

  //k番目の値をaに更新する
  void update(int k, T a){
    k = k + size;
    //必要ならばここを変えても良い
    seg[k] = a;
    //自分の親の情報を再帰的に更新していく
    while(k>0){
      k = ((k-1) >> 1);
      seg[k] = f(seg[k*2+1],seg[k*2+2]);
    }
  }

  //[a,b)についてfをした結果を返す
  //例えば、fがminだったらどうなるかを考えるとわかりやすい
  //unitについては足し算なら0,掛け算なら1,minならinf,どんな値が来てもその値を返すもの
  T query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) {
      return unit;
    } else if (a <= l && r <= b) {
      return seg[k];
    } else {
      T lch = query(a, b, k * 2 + 1, l, (l + r) / 2);
      T rch = query(a, b, k * 2 + 2, (l + r) / 2, r);
      return f(lch, rch);
    }
  }
  T query(int a, int b) { return query(a, b, 0, 0, size+1); }
};
*/

/* --- ここからコード --- */

int main(){
  ll N;
  int K;
  cin >> N >> K ;
  int ans = 0;
  while(N >= 1){
    N = N / K;
    ans+=1;
  }
  cout << ans  << endl;



  return 0;
}

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

using namespace std;

int main() {
  int N, Y;
  scanf("%d %d", &N, &Y);
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; i + j <= N; ++j) {
      int k = N - (i + j);
      int total = i * 10000 + j * 5000 + k * 1000;
      if (total == Y) {
	printf("%d %d %d\n", i, j, k);
	return 0;
      }
    }
  }
  puts("-1 -1 -1");
  return 0;
}


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

int main(){
  int  a;
  scanf("%d",&a);
  int x=a/100;
  int y=a%100;

  if(x>=1 && x<=12){
    if(y>=1 && y<=12) cout<<"AMBIGUOUS\n";
    else  cout<<"MMYY\n";
  }
  else{
    if(y>=1 && y<=12) cout<<"YYMM\n";
    else cout<<"NA\n";
  }
  return 0;
}

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

using namespace std;

#define ipair pair<int,int>
#define rep(I,N) for(int I=0; I<N; I++)
#define rrep(I,N) for(int I=N; I>=0; I--)
#define repj(i,j,n) for(int i=j;i<n;i++)

#define PB(a,i) (a).push_back(i)
#define ALL(a) (a).begin(),(a).end()

#define OK(i) cout<<"OK "<<i<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl

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

  int x[100000];

  rep (i, N) {
    cin >> x[i];
  }

  int ans = INT_MAX;
  rep (i, N) {
    int res = abs(x[i]);
    if (i+K <= N) { res += abs(x[i+K-1] - x[i]); }
    else if(i-K+1 >= 0) { res += abs(x[i-K+1] - x[i]); }
    else continue;

    // printf("%d\n", res);

    ans = min(res, ans);
  }

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

  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int N, i = 0, d = 0;
char s[100];

int main() {
        scanf("%d", &N);
        scanf("%s", s);
        do {
                if (s[i] == 'R')
                        d++;
                else if (s[i] == 'B')
                        d--;
        } while (s[++i]);
        if (d > 0)
                printf("Yes\n");
        else
                printf("No\n");
        return 0;
} 

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010, mod = 1e9 + 7;

int n, a[N];

int qp(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a[x]++;
    }

    bool flag = true;
    if(a[0] != n % 2) flag = false;
    for(int i = 1 + n % 2; i < n; i += 2)
        if(a[i] != 2)
        {
            flag = false;
            break;
        }


    if(!flag) puts("0");
    else cout << qp(2, n / 2) << endl;
    return 0;
}


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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define MX              200005
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1
#define ull unsigned long long
#define ll long long

void add(int &a,int b){
    a+=b;
    if(a>=mod)
        a-=mod;
}
int nCr(long long m, long long n){

    //6 * 5 * 4 *../ 1*2*3*...
    int ans = 1;
    for (long long i = 1; i <= n; i++){
        ans = ans * (m - i + 1) / i;
 
    }
    return ans;
}

int32_t main()
{
    int n;cin>>n;
    string s;
    //char ch[]={'a','b','c','d','e'};
    
    int f=0;
    while(n>0){
        int d=n/26;
        int r=n%26;
        if(r==0)s+='z',n=d-1;
        else
            s+='a'+r-1,n/=26;
    }
    reverse(s.begin(),s.end());
    std::cout << s << std::endl;
    return 0;
}


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

int main(){
    int N,M;
    cin >> N >> M;
    int A[N];
    vector<pair<ll, ll>>  v;
    int B,C;
    
    for(ll i = 0; i < N; i++)
        cin >> A[i];
    sort(A, A+N);
    
    for(ll i = 0; i < M; i++){
        cin >> B >> C;
        v.push_back({C,B});
    }
    sort(v.begin(), v.end(), greater<pair<ll, ll> >());
    
    ll pos = 0;
    for(ll i = 0; i < M; i++){
        if(A[pos] >= v[i].first)
            break;
        for(; pos < N; pos++){
            if(v[i].second <= 0)
                break;
            if(A[pos] > v[i].first)
                break;
            A[pos] = v[i].first;
            v[i].second--;
        }
    }    
    ll ans = 0;
    for(ll i = 0; i < N; i++){
        ans += A[i];
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 2804
H,W = map(int,input().split())
S = [input() for i in range(H)]
dy = [0,1,0,-1]
dx = [1,0,-1,0]
for y in range(H):
    for x in range(W):
        if S[y][x] == '.':
            continue
        cnt = 0
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == '#':
                cnt += 1
        if cnt == 0:
            print('No')
            exit()
print('Yes')

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

const int INF = 1000000;
const int MAX_V = 101;
const int MAX_E = 20000;

int cost[MAX_V][MAX_V];
int tttt[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;

int n,m;

void dijkstra(int s,bool r){
    fill(d,d+m,INF);
    memset(used,false,sizeof(used));
    d[s]=0;
    while(1){
        int v=-1;
        for(int u=0;u<m;u++){
            if(used[u]) continue;
            if(v==-1||d[u]<d[v]){
                v=u;
            }
        }
        if(v==-1) break;
        used[v]=true;
        for(int u=0;u<m;u++){
            int c;
            if(r) c=cost[u][v];
            else c=tttt[u][v];
            d[u]=min(d[u],d[v]+c);
        }
    }
}
int main(){
    while(cin >> n >> m,n+m){
        for(int i=0;i<m+1; i++){
            for(int j=0; j<m; j++){
                cost[i][j]=INF;
                tttt[i][j]=INF;
            }
        }
        for (int i = 0; i < m+1; ++i) {
            cost[i][i]=0;
            tttt[i][i]=0;
        }
        for (int i = 0; i < n; ++i) {
            int to,from,c,t;
            cin >> to>>from>>c>>t;
            to--; from--;
            cost[to][from]=c;
            cost[from][to]=c;
            tttt[to][from]=t;
            tttt[from][to]=t;
        }
        int k; cin>>k;
        for (int i = 0; i < k; ++i) {
            int p,q,r;
            cin>>p>>q>>r;
            p--; q--;
            dijkstra(p,!r);
            cout<<d[q]<<endl;
        }
    }
}

Measured memory_bytes: 1240