akhauriyash/Code-Regression huggingface dataset:
K = int(input())

def calc_sunuke(num):
    st = str(num)
    s_num = 0
    for c in st:
        s_num += int(c)
    return num / s_num

def search_sunuke(num):
    num_sunuke = calc_sunuke(num)
    if num >= 100:
        digits = len(str(num))
        if digits < 12:
            for i in range(count + 10**(digits-2), 10**digits, 10**(digits-2)):
                if num_sunuke > calc_sunuke(i):
                    return False
            return True
        else:
            for i in range(count + 10**(digits-3), 10**digits, 10**(digits-3)):
                if num_sunuke > calc_sunuke(i):
                    return False
            return True
    else:
        for i in range(count+1, 100):
            if num_sunuke > calc_sunuke(i):
                return False
        return True



count = 1
sunuke_num = 0
while sunuke_num != K:
    if search_sunuke(count):
        print(count)
        sunuke_num += 1
    if count < 99:
        count += 1
    else:
        count_str = str(count)
        digits = len(count_str)
        r_count = count
        if digits < 12:
            for c in count_str:
                if c != '9':
                    count += 10**(digits - 2)
                    break
            if r_count == count:
                count += 10**(digits - 1)
        else:
            for c in count_str:
                if c != '9':
                    count += 10**(digits - 3)
                    break
            if r_count == count:
                count += 10**(digits - 2)
        

        

Measured memory_bytes: 3188
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<stdio.h>
#include<cstdio>

int v[2000001];
char s[2000001],t[500002];
void Zalgorithm(int N){
  int i=1,j=0,k=0;
  while(i<N){
    while(i+j<N&&s[i+j]==s[j])++j;
    v[i]=j;
    if(!j){
      ++i;
      continue;
    }
    k=1;
    while(v[k]+k<j){
      v[i+k]=v[k];
      ++k;
    }
    i+=k;
    j-=k;
  }
}
int i,j,K,quef[1000001],ques[1000001],size;
int main(){
  int N,ng=500001,mid;
  std::fgets(t,1000000,stdin);
  std::fgets(s,1000000,stdin);
  while(ng-K>1){
    mid=(ng+K)>>1;
    (s[mid]?K:ng)=mid;
  }
  while(t[i]!='\n'){
    s[K+i]=t[i];++i;
  }
  N=i;
  i+=K;
  while(i<2000001){
    s[i++]=t[j++];
    j*=j<N;
  }
  N=(K+N-1)/N*N;
  Zalgorithm(N+K*2);
  for(i=0;i<N;++i){
    if(v[i+K]<K)ques[size++]=i+K-(i+K>=N)*N;
  }
  for(i=0;i<N;++i){
    if(i==size){
      puts("-1");
      return 0;
    }
    if(v[ques[i]+=K]>=K){
      ques[size]=ques[i]-N*(ques[i]>=N);
      quef[size++]=quef[i]+1;
    }
  }
  printf("%d\n",quef[N-1]);
}

Measured memory_bytes: 16128
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

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

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

func main() {
	sc.Split(bufio.ScanWords)
	A, op, B := getInt(), getString(), getInt()

	ans := A + B
	if op == "-" {
		ans = A - B
	}
	out(ans)
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define VEC(TYPE, A, NAME, INIT) vector<TYPE> NAME(A, INIT)
#define VEC2(TYPE, A, B, NAME, INIT) vector<vector<TYPE>> NAME(A, vector<TYPE>(B, (INIT)))

int main()
{
    int n = 0;
    cin >> n;
    VEC(ll, n, x, 0);
    VEC(ll, n, y, 0);
    int mod = -1;
    bool is = true;
    REP(i, n)
    {
        cin >> x[i] >> y[i];
        int m = ( abs( x[i] ) + abs( y[i] ) ) % 2;
        if( i == 0 ) mod = m;
        else if( mod != m ) is = false;
    }
    if( !is ) cout << -1 << endl;
    else
    {
        int k_ = 32;
        int k = k_;
        if( mod == 0 ) ++k;
        cout << k << endl;
        VEC(ll, k, d, 1);
        REP(i,k_) d[i] = ( 1ll << (k_ - i - 1) );
        REP(i, k) cout << d[i] << " ";
        cout << endl;

        REP( i, n )
        {
            ll xx = x[i] + y[i];
            ll yy = x[i] - y[i];
            ll xc = 0;
            ll yc = 0;

            REP(j, k)
            {
                if( xc <= xx && yc <= yy ) 
                {cout << "R"; xc += d[j]; yc += d[j];}
                else if( xc <= xx && yc > yy )
                { cout << "U"; xc += d[j]; yc -= d[j];}
                else if( xc > xx && yc <= yy ) 
                {cout << "D";xc -= d[j]; yc += d[j];}
                else if( xc > xx && yc > yy ) 
                {cout << "L";xc -= d[j]; yc -= d[j];}
            }
            cout << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <bitset>

using namespace std;


int main(){
    while(1){
    int a;
    vector<int> seg  {0b0111111,0b0000110,0b1011011,0b1001111,0b1100110,0b1101101,0b1111101,0b0100111,0b1111111,0b1101111};
    cin >> a;
    if(a == -1){
        
        return 0;
    }else{
        int b,c,d;
        c = 0b0000000;
        
    for(int i=0;i<a;i++){
        
        cin >>b;
        d = seg[b]^c;
        cout << bitset<7>(d) <<endl;
        c = seg[b];
    }
    }
    }
}


Measured memory_bytes: 2980
#include <iostream>
using namespace std;
using ll = long long;
int main() {
    ll n, m;
    
    cin >> n >> m;
    ll kadai[m];
    ll prop = 0;
    for (ll i = 0; i < m; i++)
    {
        cin >> kadai[i];
        prop += kadai[i];
    }
    if(prop > n){
        cout << -1 << endl;
    }else{
        cout << n - prop << endl;
    }
}

Measured memory_bytes: 3656
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
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; }

// constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
// constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    VP ps(n);
    REP(i,0,n) {
        cin >> ps[i].first >> ps[i].second;
    }
    int ans = 0;

    sort(all(ps), [](auto &l, auto &r) {
        if (l.first == r.first) return l.second < r.second;
        return l.first < r.first;
    });
    chmax(ans, abs(ps[n-1].first - ps[0].first) + abs(ps[n-1].second - ps[0].second));

    sort(all(ps), [](auto &l, auto &r) {
        if (l.second == r.second) return l.first < r.first;
        return l.second < r.second;
    });
    chmax(ans, abs(ps[n-1].first - ps[0].first) + abs(ps[n-1].second - ps[0].second));

    sort(all(ps), [](auto &l, auto &r) {
        return l.first + l.second < r.first + r.second;
    });
    chmax(ans, abs(ps[n-1].first - ps[0].first) + abs(ps[n-1].second - ps[0].second));

    sort(all(ps), [](auto &l, auto &r) {
        return l.first - l.second < r.first - r.second;
    });
    chmax(ans, abs(ps[n-1].first - ps[0].first) + abs(ps[n-1].second - ps[0].second));

    cout << ans << endl;
}

signed main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 4836
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=300+10;
const int mod=1e9+7;

int n,m;
vector<pair<int,int>> v[N];
int dp[N][N][N];

bool check(int x,int y,int z) {
	for (auto i:v[x]) {
		int l=i.first,c=i.second;
		if ((x>=l)+(y>=l)+(z>=l)!=c) return 0;
	}
	return 1;
}

int main() {
	n=read(),m=read();
	for (int i=1;i<=m;++i) {
		int l=read(),r=read(),c=read();
		v[r].emplace_back(make_pair(l,c));
	}
	dp[1][0][0]=3;
	for (int i=1;i<n;++i)
		for (int j=0;j<i;++j)
			for (int k=0;!k||k<j;++k) {
				if (!check(i,j,k)) { dp[i][j][k]=0; continue; }
				dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
				dp[i+1][i][j]=(dp[i+1][i][j]+dp[i][j][k])%mod;
				dp[i+1][i][k]=(dp[i+1][i][k]+dp[i][j][k])%mod;
			}
	int ans=0;
	for (int i=0;i<n;++i)
		for (int j=0;!j||j<i;++j)
			if (check(n,i,j)) ans=(ans+dp[n][i][j])%mod;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 59352
# DPを用いて解く。
# 少し複雑なので、自分の解説と照らし合わせて読むこと。
MOD = 10**9+7
N = int(input())

# AGCT→0123として扱う

# dpテーブルの作成shape=(101, 3,3,3) #長さが0~100まで扱いたいため
import numpy as np
dp = np.zeros((N+1, 4, 4, 4), dtype=int)

dp[0, 3, 3, 3] = 1  # 解説放送流テクニカルな楽な初期化
# 末尾がc3,c2,c1で終わる長さlの文字列の通りの数を計算していく
# print(dp)
for l in range(N):
    for c3 in range(4):
        for c2 in range(4):
            for c1 in range(4):
                # すでに条件を満たしていないのでスキップ(なくても多分平気)
                if dp[l, c3, c2, c1] == 0:
                    continue
                # 最後につける一文字を考える
                for a in range(4):
                    # あかん条件
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue
                    dp[l + 1, c2, c1, a] += dp[l, c3, c2, c1] % MOD
                    dp[l + 1, c2, c1, a] %= MOD
                    # print('ok?')

print(dp[N, :, :, :].sum() % MOD)


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

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

int main(){
  int N;
  cin >> N;
  int ac =0;
  int wa = 0;
  int tle = 0;
  int re = 0;
  rep(i,N){
    string s;
    cin >> s;
    if(s == "AC") ac++;
    else if(s == "WA") wa++;
    else if(s == "TLE") tle++;
    else re++;
  }
  cout << "AC x " << ac << endl;
  cout << "WA x " << wa << endl;
  cout << "TLE x " << tle << endl;
  cout << "RE x " << re << endl;
}


Measured memory_bytes: 3628
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
#include<time.h>
#include<map>
#include<set>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e16
using namespace std;
typedef pair<ll, ll> P;
vector<ll>a[100000];

int main(void) {
	ll n, m;
	cin >> n >> m;
	vector<ll>p(m), y(m);
	for (ll i = 0;i < m;i++) {
		cin >> p[i] >> y[i];
		a[p[i]].push_back(y[i]);
	}
	for (ll i = 1;i <= n;i++) {
		sort(a[i].begin(), a[i].end());
	}
	for (ll i = 0;i < m;i++) {
		printf("%012ld\n", (ll)1000000*p[i]+(lower_bound(a[p[i]].begin(), a[p[i]].end(), y[i]) - a[p[i]].begin()) + 1);
	}
	return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
int N, K;
bool f(vector<ll> &A, ll mid) {
  ll cnt = 0;
  REP(i, A.size()) {
    ll tmp = A[i];
    cnt += (tmp - 1) / mid;
    if (cnt > K) return false;
  }
  if (cnt > K) return false;
  return true;
}
int main() {
  cin >> N >> K;
  vector<ll> A(N);
  REP(i, N) cin >> A[i];
  sort(A.begin(), A.end());
  ll l = 0, r = A[A.size() - 1];
  while (r - l > 1) {
    ll mid = l + (r - l) / 2;
    if (f(A, mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  cout << r << endl;
}

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

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

    long long sum = 0;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            long long a = n / i;
            if (a - 1 > i) sum += a - 1;
            if (i - 1 > a) sum += i - 1;
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define ll long long
using namespace std;
const int MOD = 1000000007;
const long long INF = 1LL << 60;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<string> s(n);
  map<char, ll> mp;
  ll cnt;
  for (ll i = 0; i < n; i++) {
    cin >> s[i];
  }
  int cntab = 0;
  int a = 0;
  int b = 0;
  int ba = 0;
  for (int i = 0; i < n; ++i) {
    if (s[i].front() == 'B') b++;
    if (s[i].back() == 'A') a++;
    if (s[i].front() == 'B' && s[i].back() == 'A') ba++;
    for (int j = 0; j < (int)s[i].size() - 1; ++j) {
      if (s[i][j] == 'A' && s[i][j + 1] == 'B') cntab++;
    }
  }
  cntab += min(a, b);
  if (a > 0 && a == b && a == ba) cntab--;
  cout << cntab << endl;
}

Measured memory_bytes: 3684
//38
#include<iostream>
#include<vector>

using namespace std;

int main(){
  for(int n,r;cin>>n>>r;){
    vector<int> da[2];
    for(int i=0;i<n;i++){
      da[0].push_back(n-1-i);
    }
    while(r--){
      int c;
      cin>>c;
      vector<int> dc;
      da[1].insert(da[1].begin(),da[0].end()-n/2,da[0].end());
      da[0].erase(da[0].end()-n/2,da[0].end());
      while(dc.size()!=n){
	for(int i=0;i<2;i++){
	  int dp=(da[i].size()<c)?da[i].size():c;
	  dc.insert(dc.begin(),da[i].end()-dp,da[i].end());
	  da[i].erase(da[i].end()-dp,da[i].end());
	}
      }
      da[0]=dc;
    }
    cout<<da[0][0]<<endl;
  }
  return 0;
}
      

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

int main(){
  int INF = 1000000000;
  int h, w;
  cin >> h >> w;
  int sy, sx, gy, gx;
  cin >> sy >> sx >> gy >> gx;
  sy--; sx--; gy--; gx--;
  vector<string> g(h);
  rep(i,h) cin >> g[i];
  vvi dist(h, vi(w, INF));
  dist[sy][sx] = 0;
  deque<pair<int,int>> q;
  q.push_front({sy, sx});
  vi v = {1, 0, -1, 0, 1};
  while(!q.empty()){
    int y = q.front().first;
    int x = q.front().second;
    int d = dist[y][x];
    q.pop_front();
    rep(i,4){
      int ny = y + v[i];
      int nx = x + v[i+1];
      if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
      if(g[ny][nx] == '#') continue;
      if(d < dist[ny][nx]){
        dist[ny][nx] = d;
        q.push_front({ny, nx});
      }
    }
    for(int i=-2; i<=2; i++){
      for(int j=-2; j<=2; j++){
        int ny = y + i;
        int nx = x + j;
        if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
        if(g[ny][nx] == '#') continue;
        if(d + 1 < dist[ny][nx]){
          dist[ny][nx] = d + 1;
          q.push_back({ny, nx});
        }
      }
    }
  }
  if(dist[gy][gx] == INF) dist[gy][gx] = -1;
  cout << dist[gy][gx] << endl;
}


Measured memory_bytes: 9444
#include<stdio.h>

unsigned long long int x[20];


unsigned long long int factrial(int n){

  if(x[n]!=0) return x[n];
  else if(n==1){
    x[n]=1;
    return x[n];
  }

  x[n]=n*factrial(n-1);

  return x[n];
}


int main(void){

  int n;

  while(scanf("%d", &n)!=EOF){
  
    printf("%lld\n", factrial(n));
  }


  return(0);
}



Measured memory_bytes: 2056
class UnionFind():
    # 作りたい要素数nで初期化
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズ
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, K, L = map(int, input().split())
U1 = UnionFind(N)
U2 = UnionFind(N)
for _ in range(K):
    a, b = map(int, input().split())
    U1.Unite(a, b)
for _ in range(L):
    a, b = map(int, input().split())
    U2.Unite(a, b)

Roots = [0]
dic = {}
for n in range(1, N+1):
    r1 = U1.Find_Root(n)
    r2 = U2.Find_Root(n)
    r = r1*2*N + r2
    Roots.append(r)
    if not r in dic.keys():
        dic[r] = 1
    else:
        dic[r] += 1
    
ans = []
for n in range(1, N+1):
    ans.append(dic[Roots[n]])

print(" ".join([str(a) for a in ans]))

Measured memory_bytes: 44572
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
typedef vector<int> vi;
const int MAX=1e5+5;

int main(){
	int N;
	cin>>N;
	lli a[MAX];
	rep(i,N){
		cin>>a[i];
	}
	lli ans;
	sort(a,a+N);
	lli b[MAX];
	if(N%2==0){
		rep(i,N){
			if(i<(N/2))b[2*i+1]=a[i];
			else b[2*i-N]=a[i];
		}
		lli sum=0;
		rep(i,N-1)sum+=abs(b[i]-b[i+1]);
		ans=sum;
	}
	else{
		lli sum1=0;
		rep(i,N){
			if(i<N/2)b[2*i+1]=a[i];
			else if(i==N/2)b[0]=a[i];
			else if(i==N/2+1)b[N-1]=a[i];
			else b[2*i-N-1]=a[i];
		}
//      	rep(i,N)cout<<b[i]<<" ";
//        cout<<endl;
		rep(i,N-1)sum1+=abs(b[i]-b[i+1]);
		lli sum2=0;
		rep(i,N){
			if(i<=N/2-2)b[2*i+2]=a[i];
			else if(i==N/2-1)b[0]=a[i];
			else if(i==N/2)b[N-1]=a[i];
			else b[2*i-N]=a[i];
		}
//      	rep(i,N)cout<<b[i]<<" ";
//        cout<<endl;
		rep(i,N-1)sum2+=abs(b[i]-b[i+1]);
//      	cout<<sum1<<" "<<sum2<<endl;
		ans=max(sum1,sum2);
	}
	cout<<ans<<endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  long long ans = 0;
  int b = 0;
  int j = 0;
  for (int i = 0; i < N; i++) {
    while (j < N && (b & A[j]) == 0) {
      b ^= A[j];
      j++;
    }
    b ^= A[i];
    ans += (j - i);
  }
  cout << ans << endl;
}


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

typedef long long  LL;
struct edge{int s,t,d,n;}e[200010];
int n,h[100010],siz[100010];
LL ans;

void dfs(int x,int f)
{
	int t=0;
	siz[x]=1;
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if (y!=f)
			{
				dfs(y,x),siz[x]+=siz[y],t=max(t,siz[y]);
				ans+=2LL*min(siz[y],n-siz[y])*e[i].d;
				if (2*siz[y]==n)  ans-=e[i].d;
			}
	t=max(t,n-siz[x]);
	if (2*t<n)
		{
			t=1<<30;
			for (int i=h[x]; i; i=e[i].n)  if (e[i].t!=f)  t=min(t,e[i].d);
			ans-=t;
		}
}

void work()
{
	scanf("%d",&n);
	for (int i=1,u,v,w,tot=0; i<n; i++)
		{
			scanf("%d %d %d",&u,&v,&w);
			e[++tot]=(edge){u,v,w,h[u]},h[u]=tot;
			e[++tot]=(edge){v,u,w,h[v]},h[v]=tot;
		}
	dfs(1,0);
	printf("%lld",ans);
}

int main()
{
	work();
	return 0;
}


Measured memory_bytes: 9472
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.typecons;
import std.numeric, std.math;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
bool minimize(T)(ref T x, T y) { if (x > y) { x = y; return true; } else { return false; } }
bool maximize(T)(ref T x, T y) { if (x < y) { x = y; return true; } else { return false; } }

long mod = 10^^9 + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto H = RD;
	auto W = RD;
	auto h = RD;
	auto w = RD;

	writeln(H*W - (h*W+w*H-h*w));
	stdout.flush();
}

Measured memory_bytes: 256
function Main(input) {
  var args = input.split('\n');
  var n = parseInt(args.shift());
  var s = args.shift();
  var k = parseInt(args.shift());

  var kstr = s.charAt(k - 1);
  var ret = s.replace(new RegExp('[^' + kstr + ']', 'g'), '*');

  console.log(ret);

}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    cin >> N;

    bool check = false;

    for (int i = 0; i <= 25; i++)
    {
        for (int j = 0; j <=14; j++)
        {
            if(N == 4*i + 7*j) check = true;
        }
        
    }

    if(check == false) cout << "No" << endl;
    // if(check == true) cout << "Yes" << endl;
    else cout << "Yes" << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define EMPTY	(1000000001)

int main(void)
{
	int n;
	long now;
	long prev = EMPTY;
	
	scanf("%d", &n);
	while (n--){
		scanf(" %lld", &now);
		
		if (prev != now){
			
			if (prev == EMPTY){
				printf("%lld", now);
			}
			else {
				printf(" %lld", now);
			}
			
			prev = now;
		}
	}
	
	puts("");
	
	return (0);
}


Measured memory_bytes: 2100
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
typedef pair<int, int> P;


void solve() {
	int N; cin >> N;
	if (N == 0)exit(0);
	vector<int>p(N);
	REP(i, N) {
		cin >> p[i];
	}
	//dp[i][j]=i番目までで、おつりがj円の時の、{500円玉の枚数のmax,消費金額のmin}
	vector<vector<P>>dp(N + 1, vector<P>(50500, { -1,1e8 }));
	dp[0][0] = { 0,0 };
	REP(i, N) {
		REP(j, 50005) {
			if (dp[i][j].first <0)continue;
			int otsuri = (1000 - p[i] % 1000) % 1000;
			int cnt = dp[i][j].first;
			int cost = dp[i][j].second;
			//買わない
			if (cnt>dp[i + 1][j].first) {
				dp[i + 1][j] = { cnt,cost };
			}
			else if (cnt == dp[i + 1][j].first&&cost<dp[i + 1][j].second) {
				dp[i + 1][j] = { cnt,cost };
			}

			//おつりが500円以上の時(1000円で買えば500円がもらえる)
			if (otsuri >= 500) {
				//500円のmaxを増やせるとき
				if (cnt + 1>dp[i + 1][j + otsuri - 500].first) {
					dp[i + 1][j + otsuri - 500] = { cnt + 1,cost + p[i] };
				}
				//消費金額のminを小さくできるとき
				else if (cnt + 1 == dp[i + 1][j + otsuri - 500].first&&cost + p[i]<dp[i + 1][j + otsuri - 500].second) {
					dp[i + 1][j + otsuri - 500] = { cnt + 1,cost + p[i] };
				}
			}
			else {
				//手持ちのおつりと合わせて500円がもらえる
				if (j + otsuri >= 500) {
					int d = 500 - otsuri;//500円との差額
										 //買うけど500円はもらわない
					if (cnt>dp[i + 1][j + otsuri].first) {
						dp[i + 1][j + otsuri] = { cnt,cost + p[i] };
					}
					else if (cnt == dp[i + 1][j + otsuri].first&&cost + p[i]<dp[i + 1][j + otsuri].second) {
						dp[i + 1][j + otsuri] = { cnt,cost + p[i] };
					}

					//500円のmaxを増やせるとき
					if (cnt + 1>dp[i + 1][j - d].first) {
						dp[i + 1][j - d] = { cnt + 1,cost + p[i] };
					}
					//消費金額のminを小さくできるとき
					else if (cnt + 1 == dp[i + 1][j - d].first && cost + p[i]<dp[i + 1][j - d].second) {
						dp[i + 1][j - d] = { cnt + 1,cost + p[i] };
					}
				}
				else {
					if (cnt>dp[i + 1][j + otsuri].first) {
						dp[i + 1][j + otsuri] = { cnt,cost + p[i] };
					}
					else if (cnt == dp[i + 1][j + otsuri].first&&cost + p[i]<dp[i + 1][j + otsuri].second) {
						dp[i + 1][j + otsuri] = { cnt,cost + p[i] };
					}
				}
			}
		}
	}
	int cnt_max = 0;
	REP(j, 50001) {
		cnt_max = max(cnt_max, dp[N][j].first);
	}
	int mn_cost = 1e9;
	REP(j, 50001) {
		if (dp[N][j].first == cnt_max) {
			mn_cost = min(mn_cost, dp[N][j].second);
		}
	}
	cout << cnt_max << " " << mn_cost << endl;
}
int main() {
	while (true)solve();
}


Measured memory_bytes: 43152
#include <bits/stdc++.h>
using namespace std;
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define pb push_back
#define MAX 1000000000
#define MOD 1000000007
int main(){
  int a[4];
  for(int i = 0; 4 > i; i++){
    cin >> a[i];
  }
  int b[4]={1,9,7,4};
  for(int i = 0; 4 > i; i++){
    rep(j,4){
      if(b[i] == a[j]){
        b[i] = -1;
        a[j] = -1;
        break;
      }
    }
  }
  string res = "YES";
  rep(i,4){
    if(b[i] != -1)res = "NO";
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
typedef pair<int, int> P;
vector<P> field;
int dx[] = {-2, -2, -2, -1,  0,  1,  2, 2, 2, 1, 0, -1};
int dy[] = { 1,  0, -1, -2, -2, -2, -1, 0, 1, 2, 2,  2};
bool flag = false;
int num;

void DFS(int y, int x, int n)
{
	if(n == num)
	{
		flag = true;
		return;
	}
	for(int i = 0; i < 12; ++i)
	{
		int X = x + dx[i];
		int Y = y + dy[i];
		for(int sx = -1; sx <= 1; ++sx)
		{
			int SX = field[n].first + sx;
			for(int sy = -1; sy <= 1; ++sy)
			{
				int SY = field[n].second + sy;
				if(2 <= X && X < 12 && 2 <= Y && Y < 12 && X == SX && Y == SY)
				{
					DFS(Y, X, n + 1);
				}
			}
		}
	}
}

void solve()
{
	int x, y;
	while(cin >> x >> y, x || y)
	{
		flag = false;
		field.clear();
		cin >> num;
		field.resize(num);
		for(int i = 0; i < num; ++i)
		{
			cin >> field[i].first >> field[i].second;
			field[i].first += 2;
			field[i].second += 2;
		}
		DFS(y + 2, x + 2, 0);
		if(flag)
		{
			cout << "OK" << endl;	
		}
		else
		{
			cout << "NA" << endl;
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 0
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	int n;
	string a, b, c;
	cin >> n >> a >> b >> c;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		set<char> ss {a[i], b[i], c[i]};
		ans += ss.size() - 1;
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 256
<?php
// A - Eating Symbols Easy
$result = 0;

$stdin = trim(fgets(STDIN));
for ($i=0; $i < 4; $i++) {
  $symbol = substr($stdin, $i, 1);
  if ($symbol == '+') $result = $result + 1;
  else if ($symbol == '-') $result = $result - 1;
}

echo ("$result\n");
?>


Measured memory_bytes: 3576
/*
 * CardGame.cpp
 *
 *  Created on: 2014/08/03
 *      Author: WanWan1985
 */
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
using namespace std;

// for util
#define FOR(i, a, b) 	for(int i = (a); i < (b); i++)
#define REP(i, n)		FOR(i, 0, n)
#define PB				push_back
#define MP				make_pair
#define CL				clear
#define EXIT			(0)

typedef unsigned int u_int;
typedef long long ll;

void compareCards(const vector<string> a_vecTarosCards, const vector<string> a_vecHanakosCards);

int main(void) {
	int iTurnNum = 0;
	cin >> iTurnNum;
	vector<string> vecTarosCards;
	vector<string> vecHanakosCards;
	REP(i, iTurnNum) {
		string strTarosCard, strHanakosCard;
		cin >> strTarosCard >> strHanakosCard;
		vecTarosCards.PB(strTarosCard);
		vecHanakosCards.PB(strHanakosCard);
	}

	compareCards(vecTarosCards, vecHanakosCards);

	return EXIT;
}

void compareCards(const vector<string> a_vecTarosCards, const vector<string> a_vecHanakosCards) {

	int iTurnNum = a_vecTarosCards.size();
	int iTarosPoints = 0;
	int iHanakosPoints = 0;
	REP(i, iTurnNum) {
		string Taro = a_vecTarosCards.at(i);
		string Hanako = a_vecHanakosCards.at(i);

		bool bTaroWin	= lexicographical_compare(Hanako.begin(), Hanako.end(), Taro.begin(), Taro.end());
		bool bHanakoWin = lexicographical_compare(Taro.begin(), Taro.end(), Hanako.begin(), Hanako.end());

		if (bTaroWin && !bHanakoWin) {
			iTarosPoints += 3;
		} else if (!bTaroWin && bHanakoWin) {
			iHanakosPoints += 3;
		} else if (bTaroWin == bHanakoWin) {
			iTarosPoints += 1;
			iHanakosPoints += 1;
		}
	}
	cout << iTarosPoints << " " << iHanakosPoints << endl;
}

Measured memory_bytes: 1336
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	// 奇数番目の値の個数のカウント用
	vector<int> odds(100001, 0);
	// 偶数番目の値の個数のカウント用
	vector<int> evens(100001, 0);
	// 入力されたvの値が何個あるのかを数えるための対応
	// iが奇数の場合は、奇数番目の配列へ、iが偶数のの場合は偶数番目の配列へ
	for (int i = 0; i < n; i++)
	{
		int v;
		cin >> v;
		if (i % 2 == 0)
		{
			odds[v]++;
		}
		else {
			evens[v]++;
		}
	}
	
	
	// 偶数番目の配列の最大値と2番目に大きい値を求める
	int odds_1 = 0;
	int odds_2 = 0;
	// 偶数番目の配列の最大値と2番目に大きい値を求める
	int evens_1 = 0;
	int evens_2 = 0;
	
	for (int i = 1; i <= 100000; i++)
	{
		// 奇数番目の配列の計算
		if (odds[i] >= odds[odds_1])
		{
			odds_2 = odds_1;
			odds_1 = i;
		}
		else if (odds[i] >= odds[odds_2])
		{
			odds_2 = i;
		}
		
		// 偶数番目の配列の計算
		if (evens[i] >= evens[evens_1])
		{
			evens_2 = evens_1;
			evens_1 = i;
		}
		else if (evens[i] >= evens[evens_2])
		{
			evens_2 = i;
		}
	}
	
	// 出力
	int answer = 0;
	if (odds_1 != evens_1)
	{
		answer = n - odds[odds_1] - evens[evens_1];
	}
	else {
		if (odds[odds_1] - odds[odds_2] <= evens[evens_1] - evens[evens_2])
		{
			answer = n - odds[odds_2] - evens[evens_1];
		}
		else {
			answer = n - odds[odds_1] - evens[evens_2];
		}
	}
	cout << answer << endl;
	
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

const int bound = 100100;

vector<int> graph[bound];
vector<ll> cost;
// 親が i である木（親は適当に決める）の中でノードが持つコストの最小値
vector<ll> mini(bound);
bool besucht[bound];

void dfs( int gesehen, int elternteil ){
	besucht[gesehen] = true;
	mini[elternteil] = min( cost[gesehen], mini[elternteil]	);
	for( auto nachbar : graph[gesehen] ){
		if( !besucht[nachbar] ) dfs(nachbar, elternteil);
	}
}

int main(){
	fill_n( mini.begin(), bound, INF );
	int n, m; cin >> n >> m;
	for( int i = 0; i < n; ++i ){
		ll temp; cin >> temp;
		cost.push_back(temp);
	}
	for( int i = 0; i < m; ++i ){
		int x, y; cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	// dfs で木の本数を求める
	int cnt = 0;
	for( int i = 0; i < n; ++i ){
		if( !besucht[i] ){
			++cnt;
			dfs(i, i);
		}
	}
	// もとから木
	if( cnt == 1 ){
		cout << 0 << endl;
		return 0;
	}
	// ノードの数が木の構成に不十分な場合
	if( !( n >= (cnt-1)*2 ) ){
		cout << "Impossible" << endl;
		return 0;
	}
	ll ans = 0;
	// すべての木に対して予め最小値を足しておく
	for( int i = 0; i < n; ++i ){
		if( mini[i] != INF ) ans += mini[i];
	}
	sort( cost.begin(), cost.end() );
	// コスト a のノードは全体で見ると b 個存在する
	map<ll, ll> mp;
	for( int i = 0; i < n; ++i ) mp[cost[i]] += 1;
	// 予め足しておいた最小値のノードは除去しておく
	for( int i = 0; i < n; ++i ){
		if( mini[i] != INF ) mp[mini[i]] -= 1;
	}
	// 最初に引く辺は最小値ノード同士を結んでおけば良くて，あとは小さい方から足す
	int fois = 1;
	for( int i = 0; i < n; ++i ){
		if( fois >= cnt-1 ){
			break;
		}
		if( mp[cost[i]] > 0 ){
			ans += cost[i];
			mp[cost[i]] -= 1;
			++fois;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> c(h);
  int ans = 0;
  rep(i, h) { cin >> c[i]; }
  vector<vector<bool> > bl(h, vector<bool>(w, false));
  rep(i, h) rep(j, w) {
    if (c[i][j] == '#') {
      bl[i][j] = true;
    }
  }

  for (int bit1 = 0; bit1 < (1 << h); ++bit1) {
    for (int bit2 = 0; bit2 < (1 << w); ++bit2) {
      vector<vector<bool> > check(h, vector<bool>(w, false));
      check = bl;
      rep(i, h) {
        if (bit1 & (1 << i)) {
          rep(j, w) {
            if (c[i][j] == '#') check[i][j] = false;
          }
        }
      }
      rep(i, w) {
        if (bit2 & (1 << i)) {
          rep(j, h) {
            if (c[j][i] == '#') check[j][i] = false;
          }
        }
      }
      int cnt1 = 0;
      rep(i, h) rep(j, w) {
        if (check[i][j]) cnt1++;
      }
      if (cnt1 == k) ans++;
    }
  }

  cout << ans << endl;

  return 0;
} 

Measured memory_bytes: 3628
while(<>){
	chomp;
	($n, $k) = split(/ /, $_) if($. == 1);
	@s = split(//, $_) if($. == 2);
}
$pre = "";
$cnt = 0;
for $i (0 .. $#s){
	$cnt++ if($pre ne $s[$i]) and ($i != 0);
	$pre = $s[$i];
}
$d = ($cnt + ($k * -2)) < 0 ? 0 : ($cnt + ($k * -2));
printf $n - $d - 1 . "\n";


Measured memory_bytes: 13952
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template<class T> inline bool chmax(T& a, T b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b) {if (a>b) {a=b; return true;} return false;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k; cin >> n >> k;
    vll v(n); REP(i, n) cin >> v[i];
    ll ans = 0;
    REP(i, min(n, k+1)) {
        REP(j, min(k-i+1, n-i+1)) {
            priority_queue<ll, vll, greater<ll> > que;
            REP(_i, i) que.push(v[_i]);
            REP(_j, j) que.push(v[n-_j-1]);
            ll tmp = 0;
            ll t = min(k - (ll)que.size(), (ll)que.size());
            REP(_, t) {
                ll q = que.top(); que.pop();
                if (q > 0) {
                    que.push(q); break;
                }
            }
            while (!que.empty()) {
                tmp += que.top(); que.pop();
            }
            chmax(ans, tmp);
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

int main(void){
    int n, k;
    int l[100];
    long long dp[100][100];
    vector<int> vec;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> l[i];
    }
    sort(l,l+n);
    int i=n-1, cnt=0;
    long long sum=0;
    while(cnt < k){
        sum += l[i];
        cnt++;
        i--;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        String s = scanner.next();
        if (s.length() % 2 == 1) {
            s += " ";
        }
        for (int i = s.length() - 2; i >= 0; i -= 2) {
            if (s.substring(0, i / 2).equals(s.substring(i / 2, i))) {
                System.out.println(i);
                return;
            }
        }
    }
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
#define pb push_back
#define ff first
#define ss second
#define all(s) (s).begin(), (s).end()

int main()
{
    long double PI = acos(-1);
    long double r;
    cin >> r;
    cout << setprecision(5) << 2 * PI * r << endl;
    return 0;
}

Measured memory_bytes: 3796
import java.util.*;

class Main{

    void solve(){
        Scanner sc = new Scanner(System.in);

        //int max = 30;
        int max = (int)Math.pow(2, 15) + 10;
        int[][] dp = new int[5][max];
        dp[0][0] = 1;
        for(int j=1; j*j<max; j++){
            for(int i=1; i<5; i++){
                for(int sum=j*j; sum<max; sum++){
                    dp[i][sum] += dp[i-1][sum-j*j];
                }
            }
        }

        int n = sc.nextInt();
        while(n!=0){
            int cnt = 0;
            for(int i=0; i<5; i++) cnt += dp[i][n];
            System.out.println(cnt);
            n = sc.nextInt();
        }
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 23664
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define range_for(i, b, e) for(int i=(b), i##_len=(e); i<=i##_len; ++i)
# define ALL(x) (x).begin(), (x).end()
# define RALL(x) (x).rbegin(), (x).rend()
# define pb push_back
# define len(x) ((int)(x).size())
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
# define debug(x) std::cerr<<#x<<": "<<(x)<<endl;
# define LINT_MAX (LONG_LONG_MAX)
# define cauto const auto
using namespace std;
using lint = long long;
template <class Type> inline constexpr bool InRange(const Type& x, const Type& i, const Type& a) { return (i <= x) && (x <= a); }
template<class Integer>bool chmax(Integer &a, const Integer &b) { if (a<b) { a=b; return 1; } return 0; }
template<class Integer>bool chmin(Integer &a, const Integer &b) { if (b<a) { a=b; return 1; } return 0; }
template<class Integer>bool IsOdd(Integer &n) { return n & 1; }
template<class Integer>bool IsEven(Integer &n) { return !(n & 1); }
int ctoi(const char c) { return ('0' <= c && c <= '9') ? (c - '0') : -1; }
string YesNo(bool b) { return b ? "Yes" : "No"; }
string YESNO(bool b) { return b ? "YES" : "NO"; }
string yesno(bool b) { return b ? "yes" : "no"; }
static const lint MOD9 = (lint)1e9+7;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

// 整数の桁数を返す ( log(N) )
template <class Integer> Integer GetDigit(Integer n) {
    Integer d = 0;
    while (n) {
        n /= 10;
        d++;
    }
    return d;
}

// 素数かどうかを返す ( O(sqrt(N)) )
template <class Integer>
constexpr bool IsPrime(const Integer n) noexcept {
    if (n < 4) return n == 2 || n == 3;
    if (n % 2 == 0 || n % 3 == 0 || (n % 6 != 1 && n % 6 != 5)) return false;
    for (Integer i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}


int main()
{
  int N; cin >> N;
  vector<int> H(N); rep (i, N) { cin >> H[i]; }
  
  int m = H[0];
  int ans = 1;
  for (int i = 1; i < N; ++i)
  {
    if (chmax(m, H[i]) or m == H[i])
    {
      ans++;
    }
  }

  cout << ans << "\n";
  
  return 0;
}


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

#include <fstream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  /*
  ifstream in("input.txt");
  cin.rdbuf(in.rdbuf());
  //*/
  string S;
  cin >> S;
  int i = 0;
  bool bad = true;
  while (bad && i < S.size()) {
    bad = false;
    if (S[i] == 'd') {
      if (i < S.size() && S.substr(i, 5) == "dream") {
        //cout << "dream" <<endl;
        i += 5;
        bad = true;
        if(i < S.size() && S.substr(i, 2) == "er"){
          if(!(S.substr(i, 3) == "era")){
            i+=2;
          }
        }
      }
    } else if (S[i] == 'e') {
      if (i < S.size() && S.substr(i, 5) == "erase") {
        //cout << "erase" <<endl;
        i += 5;
        bad = true;
        if (i < S.size() && S.substr(i, 1) == "r") {
          i += 1;
          //cout << "r" <<endl;
        }
      }
    }
  }
  if(i == S.size()){
    cout << "YES" <<endl;
  } else{
    cout << "NO" <<endl;
  }
}


Measured memory_bytes: 3784
#include<stdio.h>

int main(void){

int ai,n,i,b,s;

double w;

b=-1000000;

s=1000000;

scanf("%d",&n);

for(i=0;i<n;i++){

scanf("%d",&ai);

if(ai<s){

s=ai;

}

if(b<ai){

b=ai;

}

w=w+ai;

}

printf("%d %d %0.lf\n",s,b,w);

return 0;

}

Measured memory_bytes: 636
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;

int dfs(const vector<vector<int>> &p, vector<int> &r, int n){
  if(r[n]!=-1) return r[n];
  int a=-1;
  for(auto m:p[n]){
    a=max(a,dfs(p,r,m));
  }
  return r[n]=a+1;
}

int main(){
  int N,M;
  cin >> N >> M;
  vector<vector<int>> p(N);
  for(int i=0;i<M;i++){
    int x,y; cin >> x >> y;
    --x; --y;
    p[x].push_back(y);
  }

  int res=-1;
  vector<int> r(N,-1);
  for(int i=0;i<N;i++){
    res=max(res,dfs(p,r,i));
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 8832
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <bitset>
#include <cmath>
#include <iomanip>

using namespace std;

using int64 = long long;

/////////////////////
// Code starts here//
/////////////////////


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, W;
    cin >> N >> W;

    vector<pair<int, int>> items(N + 1);
    for (int i = 1; i <= N; i++)
        cin >> items[i].first >> items[i].second;

    vector<vector<int64>> dp(N + 1, vector<int64>(W + 1));

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= items[i].first) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - items[i].first] + items[i].second);
            }
        }
    }

    cout << dp[N][W] << "\n";

    return 0;
}


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

int64_t saisyo(int64_t c, int64_t d)
{
	int64_t dai = max(c, d);
	int64_t syo = min(c, d);

	while (dai % syo != 0) {
		int64_t temp = dai % syo;
		dai = syo;
		syo = temp;
	}

	return c * d / syo;
}

int64_t kansuu(int64_t num, int64_t c, int64_t d)
{
	int64_t cd = saisyo(c, d);
	int64_t wareru = num / c + num / d - num / cd;
	return num - wareru;
}

int main()
{
	int64_t a, b, c, d;
	cin >> a >> b >> c >> d;
	
	int64_t ans = kansuu(b, c, d) - kansuu(a - 1, c, d);

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;} return false;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;} return false;}

int main(){
    ll a, b;
    cin >> a >> b;
    cout << a*b << endl;
    return 0;
}

Measured memory_bytes: 3596
#include<stdio.h>

int main(void){
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    int cost=0, ave=0;
    for(int i=0;i<n;i++){
        ave += a[i];
    }
    if((2*(ave%n))>n) ave=ave/n+1;
    else ave = ave/n;
    for(int i=0;i<n;i++){
        cost += (a[i]-ave)*(a[i]-ave);
    }
    printf("%d\n",cost);
    
    return 0;
}




Measured memory_bytes: 128
while True:
    a=[int(num)for num in input().split(' ')]
    n=a[0]
    if n==0:break
    hanafuda=[i+1 for i in range(n)]
    for i in range(a[1]):
        b=[int(num)for num in input().split(' ')]
        for j in range(b[1]):hanafuda.append(hanafuda.pop(n-(b[0]+b[1])+1))
    print(hanafuda.pop())

Measured memory_bytes: 7620
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	ll N, A, B;
	cin >> N >> A >> B;
	vector<ll> h(N);
	for (int i = 0; i < N; i++)cin >> h[i];
	sort(h.begin(), h.end());
	ll r = h[N - 1] / B;
	ll ans = INF_LL;
	for(int i = 0; i < 500; i++) {
		ll damage = B * r;
		ll l_d = r;
		for (int j = 0; j < N; j++) {
			if (h[j] <= damage)continue;
			l_d -= ceil((double)(h[j] - damage) / (double)(A - B));
		}

		if (l_d < 0) r += ceil((double)(h[N - 1] / B) / pow(2, i));
		else if (l_d > 0) {
			ans = min(r, ans);
			r -= ceil((double)(h[N - 1] / B) / pow(2, i));
		}
		else {
			ans = min(r, ans);
			break;
		}
	}

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

Measured memory_bytes: 1024
#include <cmath>
#include <cstdio>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stack>
#include <fstream>
#include <queue>
#include <iomanip>
#include <iterator>
#include <map>
#include <unordered_map>
#include <set>
#define fast ios_base::sync_with_stdio(false)
#define mxn (ll)1e5
#define mod (ll)(1e9+7)
#define mod1 (ll)(998244353)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vvi vector<vi >
#define pi pair<ll,ll>
#define vvpi vector<vector<pi > >
#define vpi vector<pi >
#define vppi vector<pair<ll,pi > >
#define vs vector<string>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define fs first
#define se second
#define crz(v,n) v.clear(),v.resize(n+1,0)
#define print(v) for(ll it=0;it<v.size();it++) cout<<v[it]<<" ";cout<<endl
#define printp(v) for(ll it=0;it<v.size();it++) cout<<v[it].first<<" "<<v[it].second<<endl
using namespace std;
int main(){
	int k;cin>>k;int c=7%k;
	for(int i=0;i<k+5;i++){
		if(!c) return cout<<i+1<<endl,0;
		c=(c*10+7)%k;
	}cout<<"-1\n";
}


Measured memory_bytes: 3588