akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, S):
    dp = [[0] * (N+1) for _ in range(N+1)]

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans = max(ans, min(j-i, dp[i][j]))

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 238304
#include<iostream>
#include<algorithm>

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;
void process();
int main(){
    process();
}
void process(){
     int N;
    ULL Y;
    int x,y,z;
    
    cin >> N >> Y;
    Y /= 1000;
    for(z=0;z<=N;z++){
        y = -(Y + 9*z - 10 * N)/5;
        x = N - z - y;
        if( x >= 0 && y >= 0 &&
           x + y + z == N && 10*x + 5*y + z == Y){
            cout << x << " " << y << " " << z << " " << endl;
            return;
        }
    }
    cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
length, quests = map(int, input().rstrip().split())
string = input()
totals = [0]

count = 0
for i in range(1, len(string)):
    if string[i-1] == "A" and string[i] == "C":
        count += 1
    totals.append(count)

for i in range(quests):
    left, right = map(int, input().rstrip().split())
    print(totals[right-1] - totals[left-1])


Measured memory_bytes: 6100
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int a;
  cin>>a;
  if(a<1200){
    cout<<"ABC"<<endl;
  }
  else{
    cout<<"ARC"<<endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(void){
	double x1,y1,x2,y2,ans;
	scanf("%lf %lf %lf %lf", &x1,&y1,&x2,&y2);
	ans = sqrt( pow(x1-x2,2)+pow(y1-y2,2));
	printf("%lf\n", ans);
	return 0;
}


Measured memory_bytes: 2060
N = int(input())
S = list(input())
 
f = 0
b = 0
count = 0
for i in range(N - 1, -1, -1):
    if S[i] == '(':
        if count > 0:
            count -= 1
        else:
            b += 1
    else:
        count += 1
 
print('(' * count, end='')
print(*S, sep='', end='')
print(')' * b)

Measured memory_bytes: 3064
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>

using namespace std;
typedef long long int ll;
void sayYes() { cout << "Yes" << endl; };
void sayNo() { cout << "No" << endl; };
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }                   // 最大公約数
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };                      // 最小公倍数
ll getDigit(ll num) { return log10(num) + 1; }                         // 桁数
ll digitSum(ll n) { return (n < 10) ? n : digitSum(n / 10) + n % 10; } // 各桁の和
#define rep(i, n) for (ll i = 0; i < n; i++)
#define repn(i, n) for (ll i = 1; i <= n; i++)

void Main()
{
    int n, k, x, y;
    cin >> n >> k >> x >> y;

    int ans = 0;
    repn(i, n)
    {
        if (i <= k)
        {
            ans += x;
        }
        else
        {
            ans += y;
        }
    }

    cout << ans << endl;

    return;
}

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


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

const int mod = 1e9+7;
#define ll long long int
const double epsilon = 1e-7;

ll mi(ll x, ll y){
    if(x<y)return x;
    return y;
}
char s[100001];
int main(void){
    scanf("%s", &s);
    int len = 0;
    while(s[len] != '\0')len++;
    for(int i = 0;i < len - 1;i++){
        if(s[i] == s[i + 1]){
            printf("%d %d\n", i + 1, i + 2);
            return 0;
        }
    }
    if(len > 2){
        for(int i = 0;i < len - 2;i++){
            if(s[i] == s[i + 2]){
                printf("%d %d\n", i + 1, i + 3);
                return 0;
            }
        }
    }
    printf("-1 -1\n");
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
inline int getInt() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

int n, k;

/*
vvi a;
void dfs(vi x) {
  if (sz(x)) a.pb(x);
  if (sz(x) == n) return;
  x.pb(1);
  while (x.back() <= k) {
    dfs(x);
    ++x.back();
  }
}
//*/

void dec(vi& a) {
  if (sz(a) == n) {
    a.back()--;
    if (a.back() == 0) a.pop_back();
  } else {
    a.back()--;
    if (a.back() == 0) a.pop_back();
    else while (sz(a) < n) a.pb(k);
  }
}

int main() {
  scanf("%d%d",&k,&n);
  // dfs({});cout<<a[(sz(a)+1)/2-1]<<endl;return 0;
  vi ans;
  if (k == 1) {
    ans = vi((n+1)/2,1);
  } else if (k%2 == 0) {
    ans = vi(n,k);
    ans[0] = k/2;
  } else {
    ans = vi(n,k/2+1);
    int x = n%2?1:2;
    x += n-2;
    x /= 2;
    rep(i,x) dec(ans);
  }
  cout<<ans<<endl;
  return 0;
}






















Measured memory_bytes: 9220
import java.util.*;

public class Main{
	
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	long n=sc.nextLong(),f=1;
    for(long i=1;i<=n;i++){
      f*=i;
      f=f%1000000007;
    }
    System.out.println(f);
  }
}


Measured memory_bytes: 21588
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    s = LS()
    t = sorted(s)
    if s[0] == s[1]:
        print("=")
    elif s[0] == t[0]:
        print("<")
    else:
        print(">")

#B
def B():
    x,y,z = LI()
    k = 0
    for i in range(1000000000):
        k += y+z
        if k+z>x:
            print(i)
            quit()

#C
def C():
    n,m = LI()
    print((100*n+1800*m)*2**m)
#D
def D():
    n,z,w = LI()
    a = LI()
    if len(a) == 1:
        print(abs(a[0]-w))
    else:
        print(max(abs(a[-1]-w),abs(a[-2]-a[-1])))
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


Measured memory_bytes: 40176
#include <stdio.h>

int main(void)
{
    unsigned int input_sec, hour,minute,sec;

    //??\???
    scanf("%d", &input_sec);

    //??????
    // 3600sec -> 60minute -> 1hour
    hour = input_sec/3600;
    minute = (input_sec%3600)/60 ;
    sec = input_sec%60;

    printf("%d:%d:%d\n", hour, minute, sec);
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
    int A,B;
    cin>>A>>B;
    int sum=1,cnt=0;
    
    while(sum<B){
        cnt++;
        sum+=A-1;
    }
    cout<<cnt<<endl;
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

string s;

int main(void) {
  // Here your code !
  cin >> s;

  sort(s.begin(), s.end());

  if (s[0] == 'a' && s[1] == 'b' && s[2] == 'c') {
    printf("Yes");
  } else {
    printf("No\n");
  }

  return 0;
}


Measured memory_bytes: 256
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-01-22 13:10:34
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#else
#define debug(_) 1728
#endif

template<int N>
class Combination {
 public:
  //constexpr 
  Combination() { Build(); }
  static constexpr int mod_ = 1000000007;
  static constexpr int n_ = N;
  struct LookupTable {
    int64 factorial_[n_];
    int64 inverse_[n_];
    int64 finverse_[n_];
  };
  LookupTable lt{};

  // return nCk
  //constexpr 
  int64 Get(int n, int k) const noexcept {
    if (n < k || n < 0 || k < 0) return 0;
    return lt.factorial_[n] * (lt.finverse_[k] * lt.finverse_[n - k] % mod_) %
           mod_;
  }

 private:
  //constexpr 
  void Build() noexcept {
    lt.factorial_[0] = 1;
    lt.factorial_[1] = 1;
    lt.finverse_[0] = 1;
    lt.finverse_[1] = 1;
    lt.inverse_[1] = 1;
    for (int i = 2; i < n_; ++i) {
      lt.factorial_[i] = lt.factorial_[i - 1] * i % mod_;
      lt.inverse_[i] = mod_ - lt.inverse_[mod_ % i] * (mod_ / i) % mod_;
      lt.finverse_[i] = lt.finverse_[i - 1] * lt.inverse_[i] % mod_;
    }
  }
};

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

  int x, y; cin >> x >> y;
 
  if ((x + y) % 3 != 0) {
    cout << 0 << endl;
    return 0;
  }
 
  int nn = (x + y) / 3;
  int r = x - nn;

  Combination<800000> kyomu;
 
  int64 ans = kyomu.Get(nn, r);
  cout << ans << endl;

  return 0;
}

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

using ll = long long;

using namespace std;

int main(){
  priority_queue<ll> q;
  ll n, m;
  cin >> n >> m;
  cin.ignore();
  ll tmp;
  for (ll i = 0; i < n; i++){
    cin >> tmp;
    q.push(tmp);
  }

  for (ll i = 0; i < m; i++){
    tmp = q.top();
    q.pop();
    tmp >>= 1;
    q.push(tmp);
  }

  ll sum = 0;
  while(!q.empty()){
    sum += q.top();
    q.pop();
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1400
fn solve() {
    let s: Vec<char> = read::<String>().chars().collect();
    let mut total = 0;
    for i in 0..s.len() {
        total += s[i] as u8 - b'0';
        total %= 9;
    }
    if total % 9 == 0 {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    let stack_size = 104_857_600;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


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

using namespace std;

int main(){

	int a, b, c, c5 = 0, c7 = 0;
	cin >> a >> b >> c;
	if(a == 5){
		c5++;
	}	
	else if(a == 7){
		c7++;
	}
	if(b == 5){
		c5++;
	}	
	else if(b == 7){
		c7++;
	}
	if(c == 5){
		c5++;
	}	
	else if(c == 7){
		c7++;
	}
	if(c7 == 1 and c5 == 2){
		cout << "YES";
	}
	else{
		cout << "NO";
	}

	return 0;
}

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

int main(){
    bool b[110] = {};
    b[0] = true;
    for(int i = 0; i < 101; i++){
        if(b[i])    b[i+4] = b[i+7] = true;
    }

    int n;
    cin >> n;

    if(b[n])    cout << "Yes" << endl;
    else        cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl
#define NN cout << "No" << endl
#define pint pair<int,int>
#define vi(v) rep(i,v.size())cin >> v[i]
#define vc(v) rep(i,v.size())cout << v[i] << endl
#define ni(n) cin >> n
#define nc(n) cout << n << endl
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int solve(){
  int n;
  cin >> n;
  string s,t;
  cin >> s >> t;
  rep(i,n + 1){
    if(s.substr(i) == t.substr(0,n - i)){
      cout << n + i << endl;
      return 0;
    }
  }
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    REP(i, h) cin >> s[i];
    int ans[50][50] = {};

    REP(i, h)REP(j, w){
        if(s[i][j] == '.'){
            FOR(ii, -1, 1)FOR(jj, -1, 1){
                if(ii == 0 && jj == 0) continue;
                if(i + ii >= 0 && j + jj >= 0 && i + ii < h && j + jj < w){
                    if(s[i + ii][j + jj] == '#') ans[i][j]++;
                }
            }
        }
    }

    REP(i, h){
        REP(j, w){
            if(s[i][j] == '.') cout << ans[i][j];
            else cout << '#';
        }
        cout << "\n";
    }


    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
   public static void main(String[] args) {  
      Scanner sc = new Scanner(System.in);
      
      String s = sc.nextLine();
      int zero = 0;
      int one = 0;
      for(int i = 0; i < s.length(); i++) {
         if(s.charAt(i) == '0')
            zero++;
         else
            one++;
      }
      System.out.println(2*Math.min(zero, one));
   }
}

Measured memory_bytes: 28476
#include <stdio.h>
int main(void){
	int i;
	int n, x;
	scanf("%d", &n);
	for (i = 1; i <= n; i++){
		if (i % 3 == 0){
		printf(" %d", i);
		}
		else {
		x = i;
		while (x > 0){
			if (x % 10 == 3){
			printf(" %d", i);
			break;
			}
			x /= 10;
			}
		}
	}
	printf("\n");
	
	return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

// ref : https://atcoder.jp/contests/abc167/submissions/13086967

int main(){
    int n;
    cin >> n;
    vector<P> pos, neg;

    rep(i, n){
        string s;
        cin >> s;
        int tmp = 0, mn = 0;
        for(char c : s){
            if (c == '(') tmp++;
            else tmp--;
            mn = min(mn, tmp);
        }
        if (tmp >= 0) pos.push_back({mn, tmp});
        else neg.push_back({mn, tmp});
    }
    sort(pos.rbegin(), pos.rend());

    int tot = 0;

    for (auto p : pos){
        if (tot + p.first < 0) {
            cout << "No" << endl;
            return 0;
        }
        tot += p.second;
    }

    sort(neg.begin(), neg.end(), [](auto a, auto b){ return a.second - a.first > b.second - b.first; } ); // sum - mnが大きい順にソートする

    for(auto& p : neg){
        if(tot + p.first < 0){
            cout << "No" << endl;
            return 0;
        }
        tot += p.second;
    }
 
    if(tot != 0){
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 18860
n,k,*t=map(int,open(0).read().split())
e=[set()for _ in[0]*n]
for a,b in zip(t[::2],t[1::2]):
  e[a-1]|={b-1}
  e[b-1]|={a-1}
c,q=k,[0]
while q:
  v,i=q.pop(),1
  for w in e[v]:
    c=c*(k-i-(v>0))%(10**9+7)
    e[w]-={v}
    q+=w,
    i+=1
print(c)

Measured memory_bytes: 49216
from collections import deque as D
line, stack = D(input().split()), D()
while line:
    hoge = line.popleft()
    if hoge.isdigit():
        stack.append(hoge)
    else:
        a, b = int(stack.pop()), int(stack.pop())
        if hoge == "*":
            stack.append(a*b)
        elif hoge == "+":
            stack.append(a+b)
        elif hoge == "-":
            stack.append(b-a)
        else:
            stack.append(b//a)
print(stack.popleft())

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

using namespace std;

int main(){

  int w, h, n;
  int x, y, a;
  cin >> w >> h >> n;

  int xmin=0, xmax=w, ymin=0, ymax=h;
  for (int i = 0; i < n; i++){
    cin >> x >> y >> a;
    if (a == 1){
      xmin = max(xmin, x);
    }
    else if (a == 2){
      xmax = min(xmax, x);
    }
    else if (a == 3){
      ymin = max(ymin, y);
    }
    else {
      ymax = min(ymax, y);
    }
  }

  if (ymax < ymin){
    ymax = ymin;
  }

  if (xmax < xmin){
    xmax = xmin;
  }

  cout << (xmax - xmin) * (ymax - ymin) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define lli long long int
#define vi vector<int>
#define vlli vector<lli>
#define vvi vector<vi >
#define str string
#define vs vector<str>
#define vb vector<bool>
#define slli set<lli>
#define mii map<int, int>
#define mlli map<int, lli>
#define msi map<str, int>
#define mp make_pair
#define pii pair<int, int>
#define pll pair<lli, lli>
#define vpii vector<pii >
#define vpll vector<pll >
#define pb push_back
#define loop(i, s, l, j) for(int i = s; i < l; i += j)
#define rloop(i, s, l, j) for(int i = s; i >= l; i -= j)
#define rep(i, n) loop(i,0,n,1)
#define rrep(i, n) rloop(i,n-1,0,1) 
#define fastio() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ft first
#define sd second   
#define mit mii::iterator
#define vit vi::iterator
#define all(a) a.begin(),a.end()
#define min3(a, b, c) min(a, min(b, c))
#define mod 1000000007
#define inf 10000000000000000
#define limit 200005
/**********************************************************************************************************************************************/
int dx4[4] = {0, -1, 0, 1};
int dy4[4] = {1, 0, -1, 0};
int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Power(int base,int exp){int ans=1;  while(exp > 0){if(exp&1)ans=(1LL*ans*base)%mod; exp=exp>>1; base=(1LL*base*base)%mod;}  return ans;}
/**********************************************************************************************************************************************/ 

struct TrieNode
{
	vector<TrieNode* >ptr;
	vi fre;
	TrieNode()
	{
		ptr.resize(26);
		rep(i,26)
			ptr[i] = NULL;
		fre.resize(26, 0);
	}
};
void Insert(TrieNode* root, str s)
{
	int n = s.length();

	rloop(i,n-1,1,1)
	{
		int c = s[i]-'a';
		if(root->ptr[c])
			root = root->ptr[c];
		else
		{
			root->ptr[c] = new TrieNode;
			root = root->ptr[c];
		}
	}
	root->fre[s[0]-'a']++;
}
void input()
{  
    int n;
    cin >> n;
    
	vs s(n);
    TrieNode *root = new TrieNode;
    rep(i,n)
    {
    	cin >> s[i];
    	s[i] += 'a';
    	Insert(root, s[i]);
    }
    
    lli ans = 0;
    rep(i,n)
    {
    	TrieNode *tmp = root;
    	vi fres(26, 0);
    	int m = s[i].length();
    	rep(j, m)
    		fres[s[i][j]-'a']++;

    	rloop(j, m-1, 1, 1)
    	{
    		tmp = tmp->ptr[s[i][j]-'a'];
    		fres[s[i][j]-'a']--;
    		rep(k, 26)
    			if(tmp->fre[k] && fres[k])
    			{
   					if(j == 1)
   						ans += max(0, tmp->fre[k]-1);
   					else
    					ans += tmp->fre[k];
    			}
    	}
    }
    cout << ans <<'\n';
}

int main()
{
	
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
 
    fastio();
    int q = 1;
    //cin >> q;
    while(q--)
        input();
}

Measured memory_bytes: 395312
#include<stdio.h>

int main()
{
  int X,Y,stock=0;
  scanf("%d%d",&X,&Y);
  
  if(X>=Y){
    stock+=X;
    X--;
  }else{
    stock+=Y;
    Y--;
  }
  
  //printf("%d %d\n",X,Y);
  
  if(X>=Y){
    stock+=X;
    X--;
  }else{
    stock+=Y;
    Y--;
  }
  
  printf("%d\n",stock);
  return 0;
}

Measured memory_bytes: 128
from sys import exit

n, m = map(int, input().split())
s = input()[::-1]

res = []
pos = 0
while True:
    if pos + m >= n:
        res.append(n - pos)
        break

    step = m
    while s[pos + step] == '1':
        step -= 1
        if step == 0:
            print(-1)
            exit()
    
    pos += step
    res.append(step)
    
print(*res[::-1], sep=' ')

Measured memory_bytes: 75152
// G++ MACRO.CPP -STD=C++14
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;

#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl

#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])

#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl

#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}

#define ALL(obj) (obj).begin(),(obj).end()

#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

template <class T = ll>
T IN(){T x;cin>>x;return (x);}

template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
    seco.resize(head);
    VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
  VECCIN(head);
  VT2(move(tail)...);
}

template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
  seco[head]=IN();
  VT3(head,move(tail)...);
}

#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision; // cpp_int

#define P pair<ll,ll>
#define V vector<ll>
#define M map<int,int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int,V,greater<int>>

#define str string

#define pb(a) push_back(a)
#define mp make_pair


int main(){
  CIN(n,m);
  
  int cons = 100 * (n-m);
  int ran = 1900 * m;

  COUT((cons + ran) * pow(2,m));
 
  return 0;
}


Measured memory_bytes: 256
import itertools


X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse=True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])


Measured memory_bytes: 273608
n,q=map(int,input().split())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

c=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    c[p-1]+=x

from collections import deque
visited=[False]*n
q=deque()
q.append(0)
while q:
    cur=q.popleft()
    visited[cur]=True
    for nx in G[cur]:
        if visited[nx]:continue
        c[nx]+=c[cur]
        q.append(nx)
print(*c)



Measured memory_bytes: 56168
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <regex>
using namespace std;

int main() {
    string s;
    cin >> s;

    bool r = regex_match(s, regex("(dream|dreamer|erase|eraser)+"));
    cout << (r ? "YES" : "NO") << endl;

    return 0;
}


Measured memory_bytes: 39808
#include <math.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <array>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
using namespace std ;
#define int long long
#define ii pair<int,int>
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
//const int N = 3e5+7 ;
//const int INF = 1e18 ;
//const int MOD = 1e9 + 7 ;


void solve(){
	int x , n ;
	cin >> x >> n ;
	set<int> st ;
	for(int i = 0 , x ; i < n ; i++){
		cin >> x ;
		st.insert(x) ;
	}
	for(int i = 0 ; i <= 1000 ; i++){
		int cur = x+i ;
		int cur2 = x-i ;
		int ans = -1 ;
		if(st.count(cur) == 0) ans = cur ;
		if(st.count(cur2) == 0) ans = cur2 ;
		if(~ans){
			cout << ans ;
			return ;
		}
	}

}

int32_t main(){
	FAST_IO ;
	int t = 1 ;
//	cin >> t ;
	while(t--){
		solve() ;
	}
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    cout<<s[0]<<len(s)-2<<s.back()<<endl;
}

Measured memory_bytes: 256
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
// #include<C:\Users\J\Desktop\AC\athead.h>
#define showa(v) for(int iii = 0; iii < v.size(); iii++){ cout << v[iii] << " ";} cout << endl;
#define show(iiii) cout << iiii << endl; 
#define shows(iiiii) cout << iiiii << " ";
#include <iostream>
#include <string>
#include<vector>
#include<stdio.h>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include<tuple>
#include <utility>
#include <map>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << n*n*n;
}

Measured memory_bytes: 256
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());
      
      int answer = 0;
      answer = Math.min(a,n);
      n -= Math.min(a,n);
      
      n -= Math.min(b,n);
      
      answer -= n;
      
      out.println(answer);
      
      
      
      
      
      
      
      
      out.close();
   }
   
      
}

Measured memory_bytes: 32704
import sys
input = sys.stdin.readline

N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
dp0 = [0] * T # finish eating by time j
dp1 = [0] * T # order by time j
for A, B in AB:
    for j in range(T):
        dp1[j] = max(dp1[j], dp0[j] + B)
    for j in range(A, T)[::-1]:
        dp0[j] = max(dp0[j], dp0[j-A] + B)
print(dp1[-1])

Measured memory_bytes: 44780
#include <iostream>
#include <algorithm>
#include <string>

#define mod (long)(1e9 + 7)

using namespace std;

int main() {
    string s;
    cin >> s;
    long dp[4] = {1, 0, 0, 0};
    for (auto c:s) {
        if (c == '?') {
            for (int i = 3; i >= 0; i--) {
                if (i <= 2)
                    dp[i + 1] = (dp[i] + dp[i + 1]) % mod;
                dp[i] = (dp[i] * 3) % mod;
            }
        } else {
            int j = c - 'A';
            dp[j+1] = (dp[j] + dp[j+1]) % mod;
        }
    }
    cout << dp[3] << '\n';
    return 0;
}

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

typedef long long ll;
const int MAX = 1e+5 * 3;
int N;
int a[MAX+1];

int main() {
  // 入力
  cin >> N;
  for (int i=0; i<3*N; i++) cin >> a[i];
  sort(a, a+3*N);
  reverse(a, a+3*N);
  ll ans = 0;
  for (int i=1; i<2*N; i+=2) {
    ans += a[i];
  }
  // 解答
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1408
#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>;

ll n,m,x;
ll mi =100000000;
vector<ll> c(12);
vector<vector<ll>> a(12, vector<ll>(12));

void f(ll i,vector<ll> b,ll ans){
  if(i==n){
    rep(i,m){
      if(b[i]<x){
        return;
      }
    }
    mi=min(mi,ans);
    return;
  }
  i++;
  f(i,b,ans);
  ans+=c[i-1];
  rep(j,m){
    b[j]+=a[i-1][j];
  }
  f(i,b,ans);
}

int main() {
  cin >>n>>m>>x;
  vector<ll> b(12,0);
  rep(i,n){
    cin >> c[i];
    rep(j,m){
      cin >> a[i][j];
    }
  }
  f(0,b,0);
  if(mi==100000000){
    cout<<-1 <<endl;
  }else{
    cout<<mi <<endl;
  }
  
}


Measured memory_bytes: 3632
package main

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

var (
	N   string
	L   int
	M   int = 1001001
	dp  [1001001][2]int
	INF int = 1234567890123456789
)

func readVariables() {
	N = "0" + nextStr()
	L = len(N)
	for i := 0; i < M; i++ {
		for j := 0; j < 2; j++ {
			dp[i][j] = INF
		}
	}
	dp[0][0] = 0
}

func getDigitAt(i int) int {
	return int(N[i-1] - '0')
}

func main() {
	readVariables()
	for i := 0; i < L; i++ {
		digit := getDigitAt(i + 1)
		//0->0
		dp[i+1][0] = MinInt(dp[i][0]+digit, dp[i+1][0])
		//0->1
		dp[i+1][1] = MinInt(dp[i][0]+digit+1, dp[i+1][1])
		//1->0
		dp[i+1][0] = MinInt(dp[i][1]+10-digit, dp[i+1][0])
		//1->1
		dp[i+1][1] = MinInt(dp[i][1]+9-digit, dp[i+1][1])
	}
	fmt.Println(dp[L][0])
}

/* 以下、テンプレート*/

var scanner *bufio.Scanner

func init() {
	Max := 1001001
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 0, Max), Max)
	scanner.Split(bufio.ScanWords)
}

//nextInt converts next token from stdin and returns integer value.
//nextInt panics when conversion into an integer fails.
func nextInt() int {
	if !scanner.Scan() {
		panic("No more token.")
	}
	num, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic("nextInt(): cannot convert to int: " + scanner.Text())
	}
	return num
}

func nextStr() string {
	if !scanner.Scan() {
		panic("No more token.")
	}
	return scanner.Text()
}

// MinInt は、2つの整数を受け取り、最小値を返します。
func MinInt(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}

//MaxInt は、2つの整数を受け取り、最大値を返します。
func MaxInt(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

//AbsInt は、整数の絶対値を返します。
func AbsInt(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

//ModPow は整数の累乗関数で、剰余もサポートします。
//base^exponentの値をmoduleで割った余りを返します。
//moduloが1以下の場合には、剰余演算をしません。
//baseが負の値である場合には、返す値が負になることがあります。
func ModPow(base, exponent, modulo int) (result int) {
	result = 1
	for exponent > 0 {
		if exponent%2 == 1 {
			result *= base
			if modulo > 1 {
				result %= modulo
			}
		}
		base *= base
		if modulo > 1 {
			base %= modulo
		}
		exponent /= 2
	}
	return
}

//Gcd は、引数の整数全ての最大公約数を返します。
func Gcd(vals ...int) (result int) {
	if len(vals) == 0 {
		return
	}
	result = vals[0]
	for i := 1; i < len(vals); i++ {
		result = gcd(result, vals[i])
	}
	return
}

func gcd(x, y int) int {
	x, y = AbsInt(x), AbsInt(y)
	for y > 0 {
		x, y = y, x%y
	}
	return x
}

//Lcm は、与えられた整数の最小公倍数を返します。
func Lcm(vals ...int) (result int) {
	if len(vals) == 0 {
		return
	}
	result = vals[0]
	for i := 1; i < len(vals); i++ {
		result = lcm(result, vals[i])
	}
	return
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}


Measured memory_bytes: 19328
#!/usr/bin/env python3

import sys

input = sys.stdin.buffer.readline

def gcd(a,b):
    return a if b == 0 else gcd(b,a%b)

def lcm(a,b):
    return a*b // gcd(a,b)

def prime_factorize(n):
    pf={}
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            pf[i] = pf.get(i, 0) + 1
            n //= i
    if n > 1: pf[n] = 1
    return pf

A,B = map(int,input().split())

pf = prime_factorize(gcd(A,B))
print(len(pf) + 1)

Measured memory_bytes: 9364
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<=n;i--)
using namespace std;
int main(){
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int ans=0;
	while(1){
		if(k==0)
			break;
		k--;
		a--;
		if(a>=0)
			ans++;
		else{
			b--;
			if(b<0){
				c--;
				if(c>=0)
					ans--;
				else 
					break;
				}
			}
		}
	
	
	cout<<ans<<endl;
		
}
	

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

int main(){
    long long N;
    cin >> N;
    long long A[N+1];
    long long i,j,k,l;
    for(i=1; i<=N; i++){
        cin >> A[i];
    }
    long long M=1000;
    long long mai;
    for(i=1; i<=N-1; i++){
        for(j=i+1; j<=N; j++){
            if(A[j-1]>=A[j]){
                break;
            }
        }
        if(j==i+1){
            continue;
        }else if(j==N+1){
            mai = M/A[i];
            M = M-A[i]*mai;
            M = M + A[N]*mai;
            break;
        }else{
            mai = M/A[i];
            M = M - A[i]*mai;
            M = M + A[j-1]*mai;
            i = j-1;
        }

    }
    cout << M << endl;
    system("pause");
    return 0;
}

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

using namespace std;
using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const ll inf = 1e9+7;
const ll mod = 1e9+7;

int main(){
    ll n,a,b;
    cin>>n>>a>>b;

    cout<<a*(n/(a+b))+min(n%(a+b),a)<<endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
#include <iomanip> //cout << fixed << setprecision(12) << ans << endl;
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define loop(i, l, r) for(int i = l; i < r; i++)
#define rloop(i, l, r) for(int i = l; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vec_i;

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int INF = 1e9;
const int MOD = 1e9+7;

int main()
{
	int a,b;
	cin >> a >> b;
	if(a >= 13) cout << b << endl;
	else if(a >= 6) cout << b/2 << endl;
	else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector <int> v[1000];
int d[1000],msum;

void saiki(int ima,int pre,int sum){
  for(int i=0;i<v[ima].size();i++) {
    int nx=v[ima][i];
    if(nx==pre) continue;
    if(v[nx].size()==1&&msum<sum)msum=sum;
    if(v[nx].size()!=1)saiki(nx,ima,sum+d[max(nx,ima)]);
  }
}

int main() {
  int n;
  while(cin>>n,n){
    memset(d,0,sizeof(d));
    for(int i=0;i<n;i++) v[i].clear();

    for(int i=1,a;i<n;i++){
    cin>>a;
    a--;
    v[a].push_back(i);
    v[i].push_back(a);
  }
    for(int i=1;i<n;i++)cin>>d[i];
    msum=0;
    for(int i=0;i<n;i++)if(v[i].size()==1)saiki(v[i][0],i,0);
    
  int ans=0;
  for(int i=0;i<n;i++)ans+=3*d[i];
  for(int i=0;i<n;i++)if(v[i].size()==1) ans-=2*d[max(i,v[i][0])];
  cout << ans-msum<<endl;
  }	 
  return 0;
}

Measured memory_bytes: 1328
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define N 5e6
const lli mod = 1e9+7;
lli x, y;
vector<lli> inv(N);
vector<lli> fact(N);
vector<lli> fact_inv(N);

void setinv(){
    inv[1] = 1;
    for(int i = 2; i < N; i++){
        inv[i] = mod-((mod/i)*inv[mod%i]%mod);
    }
}
void setfact(){
    fact[0] = fact[1] = 1;
    for(int i = 2; i < N; i++){
        fact[i] = i*fact[i-1]%mod;
    }
}
void setfact_inv(){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i = 2; i < N; i++){
        fact_inv[i] = inv[i]*fact_inv[i-1]%mod;
    }
}
lli comb(lli n, lli k){
    lli ret = (fact[n]*fact_inv[k]%mod)*fact_inv[n-k]%mod;
    return ret;
}

int main(void){
    setinv();
    setfact();
    setfact_inv();
    cin >> x >> y;
    lli a = 2*y-x;
    lli b = 2*x-y;
    if(a < 0 || b < 0 || a%3 != 0 || b%3 != 0){
        cout << 0 << endl;
        return 0;
    }
    a/=3;
    b/=3;
    cout << comb(a+b, a) << endl;
    return 0;
}


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

#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif

signed main(){

  int h,w,n; cin >> h >> w >> n;
  set<pair<int,int>> st,table;
  for(int i = 0; i < n; i++){
    int a,b; cin >> a >> b;
    a--,b--;
    st.insert({a,b});
    for(int dy : {-1,0,1}){
      for(int dx : {-1,0,1}){
        int ny = a + dy;
        int nx = b + dx;
        if(ny-1 < 0 || h <= ny+1 || nx-1 < 0 || w <= nx+1) continue;
        table.insert({ny,nx});
      }
    }
  }

  vector<int> ans(10,0);
  ans[0] = (h-2) * (w-2);
  for(auto p : table){
    int cnt = 0;
    for(int dy : {-1,0,1}){
      for(int dx : {-1,0,1}){
        int ny = p.first + dy;
        int nx = p.second + dx;
        // auto res = lower_bound(st.begin(),st.end(),make_pair(ny,nx));
        // if(res != st.end() && *res.first == ny && *res.second == nx) cnt++;
        cnt += st.count(make_pair(ny,nx));
      }
    }
    //cout << p << " " << cnt << endl;
    ans[cnt]++;
    ans[0]--;
  }

  for(int p : ans){
    cout << p << endl;
  }

  return 0;
}


Measured memory_bytes: 62720
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){


}

Node treeMaximum(Node x){


}

Node treeSearch(Node u, int k){
  while(u!=NULL && k!=u->key){
    if(k<u->key) u=u->left;
    else u=u->right;
  }
  return u;

}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL) root=z;
  else if(z->key<y->key) y->left=z;
  else y->right=z;
}
			   

void inorder(Node u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
      } 
    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } /*else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
      }*/
  }

  return 0;
}



Measured memory_bytes: 20444
#include<iostream>
using namespace std;
#define UUI long long int
UUI x,y,n,m;
char tile[120][120],a;
int main(){
    while(1){
            cin >> n >> m;
            if(n==0&&m==0)break;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a;
            tile[i][j]=a;
        }
    }
    x=0;
    y=0;
    while(1){
            if(tile[y][x]==0){
                    cout << "LOOP" << endl;
                    break;
            }
    if(tile[y][x]=='>'){
        tile[y][x]=0;
        x=x+1;
    }else if(tile[y][x]=='<'){
        tile[y][x]=0;
        x=x-1;
    }else if(tile[y][x]=='^'){
        tile[y][x]=0;
        y=y-1;
    }else if(tile[y][x]=='v'){
        tile[y][x]=0;
        y=y+1;
    }else if(tile[y][x]=='.'){
            cout << x <<" "<< y << endl;
        break;
    }
    }
    }
return 0;
}

Measured memory_bytes: 1172
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define ct(string) cout << string << endl

int main() {
    int n, ans=0, ma=0;
    cin >> n;
    rep(i,n) {
        int c;
        cin >> c;
        if (c >= ma) ans++;
        ma = max(ma, c);
    }
    ct(ans);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;

int main(int argc, char *argv[]) {
  /*
  cin>>x;
  cout<<x<<endl;
  */
  int i,j,n=0,m=0;
  string s,t="01";
  cin>>s;
  for(i=0;i<s.length();i++){
    if(t[i%2]==s[i])
      n++;
    else
      m++;
  }
  cout<<min(n,m)<<endl;
}


Measured memory_bytes: 512
##############################
# priority que
##############################

X,Y,Z,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

def Nmb(tp):
  return A[tp[0]-1]+B[tp[1]-1]+C[tp[2]-1]

from heapq import heapify, heappop, heappush, heappushpop
hp = []
heapify(hp)
tp = (1, 1 , 1)
heappush(hp, (-Nmb(tp),)+tp)
hist = {tp}

for k in range(K):
  #最上位をpop
  rec = heappop(hp)
  print(rec[0]*-1)
# 次の順位を登録する
# Aを次の配列
  tp = (rec[1]+1, rec[2], rec[3])
  if tp[0]<=X and not tp in hist:
    heappush(hp, (-Nmb(tp),)+tp)
    hist.add(tp)
# Bを次の配列
  tp = (rec[1], rec[2]+1, rec[3])
  if tp[1]<=Y and not tp in hist:
    heappush(hp, (-Nmb(tp),)+tp)
    hist.add(tp)
# Cを次の配列
  tp = (rec[1], rec[2], rec[3]+1)
  if tp[2]<=Z and not tp in hist:
    heappush(hp, (-Nmb(tp),)+tp)
    hist.add(tp)

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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s;
	cin >> s;

	int n = s.size();

	cout << s[0] << n-2 << s.back() << endl;
	return 0;	
}

Measured memory_bytes: 256