akhauriyash/Code-Regression huggingface dataset:
//Tuvshee
 
#include<iomanip>
#include<iostream>
#define _USE_MATH_DEFINES
#include<math.h>
#include<cmath>
#include<algorithm>
#include<string>
#include<cctype>
#include<vector>
#include<queue>
using namespace std;
#define I int
#define V void
#define D double
#define F float
#define C char
#define S string
#define B bool
#define L long long
#define rep(n) for(int i=0;i<n;i++)
#define reps(m,n,c) for(int c=m;c<n;c++)
#define repd(m,n,j) for(int j=n;j>m;j--)
#define whL while
#define eL endl
#define oR ||
#define anD &&
#define rtn return
#define pause system("PAUSE")
#define Max 300
#define max(m,n) ((n<m)?m:n)
#define min(m,n) ((n>m)?m:n)

int main()
{
	int n,a[111];
	cin>>n;
	reps(0,n,i)cin>>a[i];
	reps(0,n,i){
		if(i)cout<<' ';
		cout<<a[n-1-i];
	}
	cout<<eL;
	rtn 0;
}

Measured memory_bytes: 1160
n,m = map(int,input().split())
a = list( map(int,input().split()))
bc=[[0]*2 for _ in range(m)]
for i in range(m):
    bc[i] = list(map(int,input().split()))

a.sort()
bc.sort(reverse=True,key=lambda x:x[1])

nokori=n
bc2=[]
for (bb,cc) in bc:
    if bb<=nokori:
        bc2.extend([cc]*bb)
        nokori-=bb
    else:
        bc2.extend([cc]*nokori)
        nokori=0
        break

ans=sum(a)
for i in range(0,min(n,len(bc2))):
    if bc2[i]>a[i]:
        ans+=bc2[i]-a[i]
    else:
        break
print(ans)

Measured memory_bytes: 90860
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std ;

ll a[100100];
ll mm[100100];
ll totmm[100100];
int main()
{
    ios::sync_with_stdio(false);
   ll n,t;
   cin>>n>>t;
   if(t%2!=0)t--;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   mm[n-1]=a[n-1];
   for(int i=n-2;i>=0;i--)
   {
       mm[i]=max(mm[i+1],a[i]);
   }
   ll tot=0;
   ll kk=0;
   for(int i=0;i<n;i++)
   {
       kk=max(kk,mm[i]-a[i]);
   }
   for(int i=0;i<n;i++)
   {
       if(mm[i]-a[i]==kk)tot++;
   }
   cout<<tot<<endl;
}








Measured memory_bytes: 1792
//C
#include <cassert>
//#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//ここまで標準include

using namespace std;

long aCb(long a, long b) {
	long out = 1;
	for (long i = 1; i <= b; i++) {
		out = out * (a + 1 - i) / i;
	}
	return out;
}

int main() {
	int a, p;
	cin >> a >> p;
	cout << (a * 3 + p) / 2 << endl;
}


Measured memory_bytes: 256
package main

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

func main() {
	var sai [][2]int
	var sc = bufio.NewScanner(os.Stdin)

	sc.Scan()

	for sc.Scan() {
		s := sc.Text()
		ss := strings.Split(s, " ")

		s1, _ := strconv.Atoi(ss[0])
		s2, _ := strconv.Atoi(ss[1])

		var one [2]int
		one[0] = s1
		one[1] = s2

		sai = append(sai, one)
	}

	var cnt int

	for _, i := range sai {
		if i[0] == i[1] {
			cnt++
			if cnt >= 3 {
				fmt.Println("Yes")
				return
			}
		} else {
			cnt = 0
		}
	}

	fmt.Println("No")
}


Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**9)

N=int(input())
graph=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    graph[a].append([b,c])
    graph[b].append([a,c])

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

Q,K=map(int,input().split())
K-=1
d=[-1]*N
d[K]=0
dfs(K)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(d[x]+d[y])

Measured memory_bytes: 137936
A,B,C,D = map(int, input().split())

P=998244353

dp = [[0 for j in range(3002)] for i in range(3002)]
dp[A][B] = 1

for row in range(A, C + 1):
    for col in range(B, D + 1):
        dp[row][col] += col * dp[row - 1][col] + row * dp[row][col - 1]
        dp[row][col] -= (row - 1) * (col - 1) * dp[row - 1][col - 1]
        dp[row][col] %= P

print(dp[C][D])

Measured memory_bytes: 153240
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::*;

use std::io::*;
use std::str::FromStr;

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

fn main() {
  let n: usize = read::<usize>();
  let m: usize = read::<usize>();

  if n == m {
    println!("Yes");
  } else {
    println!("No");
  }
}


Measured memory_bytes: 4352
// 2-D 長方形の中に円が含まれるかを判定するプログラムを作成してください。
// 次のように、長方形は左下の頂点を原点とし、右上の頂点の座標 (W,H)  が与えられます。
// また、円はその中心の座標 (x,y)  と半径 r  で与えられます。 

import java.util.*;


class Main{
	////プログラムのエントリポイント
	public static void main(String[] args){
		//入力ストリームの生成
		Scanner sc = new Scanner(System.in);
		//数字３つ受け取り
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int r = sc.nextInt();
		
		if( x - r < 0 || y - r < 0 || x + r > W ||  y + r > H ){
			System.out.println("No");
		}else{
			System.out.println("Yes");      
		}
	}
}

Measured memory_bytes: 17324
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int n, m;
int stop[100005];
vector<int> kr[100005];
int DP[100005];
queue<int> pokolei;

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		kr[a].push_back(b);
		stop[b]++;
	}
//	for(int i = 1; i <= n; i++){
//		printf("%d ", stop[i]);
//	}
//	printf("\n");
	for(int i = 1; i <= n; i++){
		if(stop[i] == 0) pokolei.push(i);
	}
	while(!pokolei.empty()){
//		printf("%d\n", pokolei.front());
		for(int i = 0; i < kr[pokolei.front()].size(); i++){
			DP[kr[pokolei.front()][i]] = max(DP[kr[pokolei.front()][i]], DP[pokolei.front()] + 1);
			stop[kr[pokolei.front()][i]]--;
			if(stop[kr[pokolei.front()][i]] == 0) pokolei.push(kr[pokolei.front()][i]);
		}
		pokolei.pop();
//		for(int i = 1; i <= n; i++){
//			printf("%d ", stop[i]);
//		}
//		printf("\n");
//		for(int i = 1; i <= n; i++){
//			printf("%d ", DP[i]);
//		}
//		printf("\n");
	}
	int wynik = 0;
	for(int i = 1; i <= n; i++){
		wynik = max(wynik, DP[i]);
	}
	printf("%d", wynik);
	return 0;
}

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


int main() {
	
	int N;
	cin >> N;
	double sum = 0;
	vector<double> y(N);
	for(int i=0; i<N; i++){
		double x;
		string u;
		cin >> x >> u;
		if(u=="BTC") x *= 380000;
		y.at(i) = x;
		sum += x;
	}
	cout << fixed << setprecision(8) << sum << endl;
	
	
	return 0;
}

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

int main(){
  string s;
  cin >> s;
  rep(i,int(s.length())) cout << 'x' ;
  
  cout << endl;
  return 0;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
std::vector<P> G[100100];
int color[100100];

void dfs(int u, int p, int c){
    color[u] = c;

    for(auto &e : G[u]){
        int v, w;
        std::tie(v, w) = e;

        if(v == p){
            continue;
        }

        dfs(v, u, (c + w) & 1);
    }
}

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

    std::cin >> N;

    for(int i=1;i<N;++i){
        int u, v, w;
        std::cin >> u >> v >> w;

        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    dfs(1, -1, 0);

    for(int i=1;i<=N;++i){
        std::cout << color[i] << std::endl;
    }
}


Measured memory_bytes: 8448
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	int n,m,x,y,flag;
	cin >> n >> m;
	x=1,y=n,flag=0;
	if(n&1)
	for(int i=1;i<=m;i++)
		cout << i << " " << n-i << "\n";
	else
	for(int i=1;i<=m;i++)
	{
		if(y-x<=n/2&&!flag)
		{
			--y;
			flag=1;
		}
		cout << x << " " << y << "\n";
		++x,--y; 
	}
	return 0;
}

Measured memory_bytes: 3192
#include <iostream>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
int main(){
	int am,pm;
	while(cin >> am >> pm) {
		if(am==0&&pm==0) break;
		int ret = am + pm;
		char shop = 'A';
		rep2(i,1,5) {
			cin >> am >> pm;
			if(ret < am + pm) {
				ret = am + pm;
				shop = 'A' + i;
			}
		}
		cout << shop << " " << ret << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# numpy使わずに再実装 #入れるときはpythonのほうが速いので
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for L, R in LR:
    LR2d[L][R] += 1
LR2d = np.array(LR2d, np.int64)

LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum[1:, 1:] = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# queryに答えていく
ans = []
for p, q in pq:
    ans.append(LR2d_accum[q + 1, q + 1] - LR2d_accum[q + 1, p] -
               LR2d_accum[p, q + 1] + LR2d_accum[p, p])

print(*ans, sep='\n')


Measured memory_bytes: 53300
a,b,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
p=min(a)+min(b)
for i in range(m):
    x,y,c=map(int,input().split())
    p=min(p,a[x-1]+b[y-1]-c)
print(p)

Measured memory_bytes: 18736
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [1] * (n+2)
mod = 1000000007
dp[n+1] = 0
for i in range(m):
    dp[a[i]] = 0
for i in range(n-1, -1, -1):
    if dp[i] == 0:
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])

Measured memory_bytes: 7824
#include<bits/stdc++.h>
#include<atcoder/lazysegtree>
#include<atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;
// or: typedef modint998244353 mint;

#define INF 1000000010
#define EPS 1e-9
#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
//#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;

struct S{
  mint a;
  mint size;
};

struct F{
  mint a;
};

S op(S l, S r) { return S{l.a + r.a, r.size+l.size}; }

S e() { return S{0, 0}; }

S mapping(F l, S r) { if(l.a==0) return r;
  return S{r.size*l.a, r.size};
}

F composition(F l, F r) {
  if(l.a==0) return r;
  return l;
}

F id() { return F{0}; }


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n,q;
  cin>>n>>q;
  int l,r,d;
  vector<S> a(n);
  mint now=1;
  repn(i,n-1){
    a[i]=S{now,now};
    now*=10;
  }
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
  rep(i,q){
    cin>>l>>r>>d;
    l--;
    seg.apply(l,r,F{d});
    cout<<seg.all_prod().a.val()<<endl;
   
  }

  return 0;
}


Measured memory_bytes: 10128
# import sys
# sys.setrecursionlimit
getarr = lambda _f: list(map(_f, input().split()))
inf = 10**8 + 1

N, M = getarr(int)

keys = []
key_max = 2**N - 1
for _ in range(M):
    a, b = getarr(int)
    c = getarr(int)
    k = key_max
    for ci in c:
        k -= (1 << (ci - 1))
    keys.append([a, k])
dp = [[inf] * (M + 1) for _ in range(2**N + 1)]
for i in range(M + 1):
    dp[0][i] = 0

for j in range(M):
    for i in range(2**N + 1):
        _cost = keys[j][0]
        _key = keys[j][1]
        dp[i][j + 1] = min(_cost + dp[i & _key][j], dp[i][j])

ans = dp[key_max][M]

print(ans if ans != inf else -1)

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

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    ll S = 0;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        S += a[i];
    }
    vector<ll> x(n);
    for(int i=1; i<n; i+=2) {
        S -= 2 * a[i];
    }
    x[0] = S;
    cout << x[0] << " ";
    for(int i=1; i<n; i++) {
        x[i] = 2 * a[i-1] - x[i-1];
        cout << x[i] << " ";
    }
}

Measured memory_bytes: 4756
import sys,bisect,math
from functools import reduce
sys.setrecursionlimit(15000)

A,B = map(int,sys.stdin.readline().split())

def exgcd0(x,y):
  # if x < y:
  #   x,y = y,x
  a0,b0,r0=1,0,x
  a1,b1,r1=0,1,y
  while r1 > 0:
    q1=r0//r1
    r2=r0%r1
    a2=a0-q1*a1
    b2=b0-q1*b1
    a0,b0,r0=a1,b1,r1
    a1,b1,r1=a2,b2,r2
  return a0,b0,r0#a,b,c

def exgcd(a,b):
  if b==0:
    return 1,0,a
  else:
    q=a//b
    r=a%b
    s1,t1,c = exgcd(b,r)
    s = t1
    t = s1-t1*q
    return s,t,c

ret = exgcd0(A,B)
print(ret[0],ret[1])


Measured memory_bytes: 6364
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner in = new Scanner(file);
		
		Scanner in = new Scanner(System.in);
		
		String A = in.next();
		String B = in.next();
		String C = in.next();
		System.out.println((A.charAt(A.length()-1) == B.charAt(0) && B.charAt(B.length()-1) == C.charAt(0)) ? "YES" : "NO");
	}
}


Measured memory_bytes: 21844
#include <complex>
#include <cmath>

using Real = long double;

const Real EPS = 1e-10;

// 宇宙船演算子
inline Real compare(Real a, Real b) {
    if (std::abs(a - b) < EPS) return 0;
    return a - b > 0 ? 1 : -1;
}

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


using Point = std::complex<Real>;
using Segment = std::pair<Point, Point>;

inline Real length(Segment s) {
    return std::abs(s.second - s.first);
}

// inner product
inline Real dot(Point x, Point y) {
    return std::real(std::conj(x) * (y));
}

// outer product
inline Real cross(Point x, Point y) {
    return std::imag(std::conj(x) * (y));
}

// lに対するxの正射影
Point proj(Segment s, Point p) {
    Real ratio = dot(s.second - s.first, p - s.first) / sq(length(s));
    return s.first + (s.second - s.first) * ratio;
}

// lを軸としてxに対称な点
Point refl(Segment s, Point p) {
    Point t = proj(s, p);
    return t + (t - p);
}

// lに対するpの位置
// counter clockwise -> 1, clockwise   -> -1
// online front      -> 2, online back -> -2
// on segment        -> 0
int side(Segment s, Point p) {
    Real c = cross(s.second - s.first, p - s.first);
    if (compare(c, 0) != 0) return compare(c, 0);

    Real d = dot(s.second - s.first, p - s.first);
    if (compare(d, 0) < 0) return -2;

    return (compare(length(Segment(s.first, p)), length(s)) > 0 ? 2 : 0);
}

inline bool isorthogonal(Segment s1, Segment s2) {
    return compare(dot(s1.second - s1.first, s2.second - s2.first), 0) == 0;
}

inline bool isparallel(Segment s1, Segment s2) {
    return compare(cross(s1.second - s1.first, s2.second - s2.first), 0) == 0;
}


#include <iostream>
#include <array>

using namespace std;

int main() {
    int Q;
    cin >> Q;

    for (int q = 0; q < Q; ++q) {
        array<Segment, 2> s;
        for (int i = 0; i < 2; ++i) {
            array<Point, 2> p;
            for (int j = 0; j < 2; ++j) {
                Real x, y;
                cin >> x >> y;
                p[j] = Point(x, y);
            }
            s[i] = Segment(p[0], p[1]);
        }

        int ans;
        if (isparallel(s[0], s[1])) {
            ans = 2;
        } else if (isorthogonal(s[0], s[1])) {
            ans = 1;
        } else {
            ans = 0;
        }
        cout << ans << endl;
    }
    return 0;
}



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

int main(){
  bool cards[4][14];
  int n, rank;
  string suit;
  
  for ( int s = 0; s < 4; s++)
    for ( int r = 1; r <= 13; r++)
      cards[s][r] = 0;

  cin >> n;
  for ( int i = 0; i < n; i++ ){
    cin >> suit >> rank;
    if ( suit == "S" ) cards[0][rank] = 1;
    if ( suit == "H" ) cards[1][rank] = 1;
    if ( suit == "C" ) cards[2][rank] = 1;
    if ( suit == "D" ) cards[3][rank] = 1;
  }

  for ( int s = 0; s < 4; s++ ){
    for ( int r = 1; r <= 13; r++ ){
      if ( cards[s][r] ) continue;
      if ( s == 0 ) suit = "S";
      if ( s == 1 ) suit = "H";
      if ( s == 2 ) suit = "C";
      if ( s == 3 ) suit = "D";
      cout << suit << " " << r << endl;
    }
  }
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef vector<ld> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)


ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "yes" << endl;}
void no(){ cout << "no" << endl;}

//-----------------------------------------
template<class T>
class BT{
  private:
    struct Node{
      T key;
      Node *par, *lef, *rig;
    };
    Node *NIL, *root;
  public:
    BT(){
      NIL = NULL;
    }
    void insert(T k){
      Node *y = NIL;
      Node *x = root;
      Node *z;

      z = (Node*)malloc(sizeof(Node));
      z->key = k;
      z->lef = NIL;
      z->rig = NIL;

      while(x != NIL){
        y = x;
        if(k < x->key) x = x->lef;
        else x = x->rig;
      }
      z->par = y;
      if(y == NIL) root = z;
      else if(z->key < y->key) y->lef = z;
      else y->rig = z;
    }

    bool finding(T k, Node *t){
      if(t == NIL) return false;
      if(t->key == k) return true;
      if(k < t->key) return finding(k,t->lef);
      else return finding(k,t->rig);
    }
    bool find(T k){
      return finding(k,root);
    }

    void pmid(Node *t){
      if(t == NIL) return;
      pmid(t->lef);
      cout << " " << t->key;
      pmid(t->rig);
    }

    void ppre(Node *t){
      if(t == NIL) return;
      cout << " " << t->key;
      ppre(t->lef);
      ppre(t->rig);
    }

    void pr(){
      pmid(root);
      cout <<endl;
      ppre(root);
      cout <<endl;
    }
};
//-----------------------------------------

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

  int n;
  cin >> n;
  BT<int> tree;
  REP(i,n){
    string s;
    cin >> s;
    if(s == "insert"){
      int a;
      cin >> a;
      tree.insert(a);
    }
    else if(s == "find"){
      int a;
      cin >> a;
      if(tree.find(a)) yes();
      else no();
    }
    else{
      tree.pr();
    }
  }



  return 0;
}






Measured memory_bytes: 21932
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(20)
#define highest(x) (63 - __builtin_clzl(x))

int main(){
    int N;
    cin >> N;
    int a[N];
    cins(a, a + N);
    double all = 0;
    for(int i = 0; i < N; i++){
        all += a[i];
    }
    int ans = 0;
    for(int i = 1; i < N; i++){
        if(abs(all / N - a[ans]) - 1e-6 > abs(all / N - a[i])){
            ans = i;
        }
    }
    cout << ans << endl;
}



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


double func(double x,double q)
{
	double a, b;

	a = pow(x, 3)-q;
	b = pow(x, 2)*3;

	return (x - a / b);
}

int main()
{
	double q,x,r;
	
	while (1)
	{
		scanf("%lf",&q);
		if (q == -1)
		{
			break;
		}

		r = 0.00001*q;
		x = q / 2;

		while (1)
		{
			x = func(x,q);
			if (fabs(q- (pow(x, 3))) < r)
			{
				break;
			}
		}
		printf("%.6f\n", x);
	}


	return 0;
}


Measured memory_bytes: 728
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define all(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
const int MAX = (int)2e5 + 5;

int W, H, N;
char field[100][100] = {};
//          x    y

int main() {
	cin >> W >> H >> N;
	rep(i, N) {
		int x, y, a;
		cin >> x >> y >> a;
		if (a == 1) {
			rep(i, x) rep(j, H) {
				field[i][j] = 1;
			}
		}
		if (a == 2) {
			REP(i, x, W) rep(j, H) {
				field[i][j] = 1;
			}
		}
		if (a == 3) {
			rep(i, W) rep(j, y) {
				field[i][j] = 1;
			}
		}
		if (a == 4) {
			rep(i, W) REP(j, y, H) {
				field[i][j] = 1;
			}
		}
	}
	int res = 0;
	rep(i, W) rep(j, H) {
		if (field[i][j] == 0) res++;
	}
	if (test) {
		for(int j = H-1; j > -1; j--) {
			rep(i, W) {
				cout << (int)field[i][j];
			}
			cout << endl;
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
// atcoder 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int A, B, K;
    cin >> A >> B >> K;
    for(int i=0; i<K; i++){
        if(i%2 == 0){
            if(A%2 == 1) A = A-1;
            B += A/2;
            A = A/2;
        }
        else{
            if(B%2 == 1) B = B-1;
            A += B/2;
            B = B/2;
        }
    }
    cout << A << " " << B << endl;
    return 0;
}


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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

void getString(string &nt, stack<int> &q) {
  int c = 0;
  while (!q.empty()) {
    int u = q.top();
    q.pop();
    if (c % 2 == 0) {
      nt[u] = 'D';
    } else {
      nt[u] = 'P';
    }
    c++;
  }
}

int main() {
  string t;
  cin >> t;
  int n = t.size();
  string nt = t;
  char prev = 'x';
  stack<int> q;
  for (int i = 0; i < n; i++) {
    char cur = t[i];
    if (cur == '?') {
      if (prev == 'P') {
        nt[i] = 'D';
      } else if (i + 1 < n && t[i + 1] == 'D') {
        nt[i] = 'P';
      } else {
        q.push(i);
        if (i == n - 1) {
          getString(nt, q);
        }
      }
    } else {
      getString(nt, q);
    }
    prev = nt[i];
  }
  cout << nt << endl;
  return 0;
}


Measured memory_bytes: 4452
#include<bits/stdc++.h>
#include<iostream>
#define ll          long long
#define mp	    make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;


void solve(){
    int n, q, m = 0;
    string s;
    cin>>n>>q>>s;
    int cnt[(int)s.length()+1];
    cnt[0] = 0;
    rep(i,1,s.size()){
        if(s[i] == 'C' && s[i-1] == 'A')
            m++;
        cnt[i] = m;
    }
    
    while(q--){
        int l, r;
        cin>>l>>r;
        l--;r--;
        cout<<cnt[r]-cnt[l] << endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
     t =1;
//     cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 1488
N, Y = map(int, input().split())

for m10 in range(N + 1):
    for m5 in range(N + 1 - m10):
        m1 = N - m10 - m5
        if m10 * 10000 + m5 * 5000 + m1 * 1000 == Y:
            print(m10, m5, m1)
            exit(0)

print('-1 -1 -1')

Measured memory_bytes: 3060
import java.util.Scanner;

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

        int n = stdIn.nextInt();
        int[] a = new int[n];

        for(int i=0; i<n; i++){
            a[i] = stdIn.nextInt();
        }

        int q = stdIn.nextInt();
        int[] m = new int[q];

        for(int i=0; i<q; i++){
            m[i] = stdIn.nextInt();
        }

        for(int i=0; i<q; i++){
            boolean[] bit = new boolean[n];
            boolean clearflag = false;
            do{
                int sum = 0;
                for(int j=0; j<bit.length; j++){
                    if(bit[j]){
                        sum += a[j];
                    }
                }
                if(sum == m[i]){
                    System.out.println("yes");
                    clearflag = true;
                    break;
                }
                changeBit(bit);
            }while(!finish(bit));

            if(!clearflag){
                System.out.println("no");
            }
        }
    }

    static void changeBit(boolean[] bit){
        boolean carryBit = true;
        for(int i=0; i<bit.length; i++){
            if(carryBit){
                if(bit[i]){
                    bit[i] = false;
                }else{
                    bit[i] = true;
                    carryBit = false;
                }
            }
        }
    }

    static boolean finish(boolean[] bit){
        for(int i=0; i<bit.length; i++){
            if(!bit[i]){
                return false;
            }
        }
        return true;
    }
}


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

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	
  	string s, t;
  	cin >> s >> t;
  	int m = s.length(), n = t.length(), same, ans = 0;
  	
  	for(int i = 0; i <= m-n; i++)
    {
      	same = 0;
      	for(int j = 0; j < n; j++)
          	if(s[i+j] == t[j])
              	same++;
      	ans = max(ans, same);
    }
  
  	cout << n-ans;
	return 0;
}


Measured memory_bytes: 3648
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    #[allow(unused_mut)]
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    n: usize,
    aa: [usize; n]
  }
  let mut dp = vec![vec![vec![0.0; n+1]; n+1]; n+1];
  let mut pop = vec![0usize; 4];
  for &a in aa.iter() {
    pop[a] += 1;
  }
  dp[pop[3]][pop[2]][pop[1]] = 1.0;
  let mut ans = 0.0;
  for three in (0 .. pop[3] + 1).rev() {
    for two in (0 .. pop[3] - three + pop[2] + 1).rev() {
      for one in (0 .. pop[3] - three + pop[2] - two + pop[1] + 1).rev() {
        let dish = (one + two + three) as f64;
        if one + two + three > 0 {
          ans += dp[three][two][one] * n as f64 / dish;
        }
        if three > 0 && two + 1 <= n {
          dp[three-1][two+1][one] += dp[three][two][one] * (three as f64) / dish;
        }
        if two > 0 && one + 1 <= n {
          dp[three][two-1][one+1] += dp[three][two][one] * (two as f64) / dish;
        }
        if one > 0 {
          dp[three][two][one-1] += dp[three][two][one] * (one as f64) / dish;
        }
      }
    }
  }
  println!("{:.15}", ans);
}


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

int estimate_Tanri(int operatingfund,double rate_of_interest,int period,int fee);
int estimate_Fukuri(int operatingfund,double rate_of_interest,int period,int fee);

int main(void) {
	int m;
	scanf("%d",&m);
	int i;
	for(i=0;i<m;i++){
		int operatingfund;
		scanf("%d",&operatingfund);
		int period;
		scanf("%d",&period);

		int n;						//?????¨??????????¨??????°
		scanf("%d",&n);
		int result = 0;
		int j;
		for(j=0;j<n;j++){
			int TorF;
			double rate_of_interest;
			int fee;
			scanf("%d %lf %d",&TorF,&rate_of_interest,&fee);

			int tmp;
			if(TorF == 0){
				tmp = estimate_Tanri(operatingfund,rate_of_interest,period,fee);
			}
			else{
				tmp = estimate_Fukuri(operatingfund,rate_of_interest,period,fee);
			}

			if(result<=tmp){
				result = tmp;
			}
		}
		printf("%d\n",result);
	}
	return 0;
}

int estimate_Tanri(int operatingfund,double rate_of_interest,int period,int fee){
	int i;
	int total_interest = 0;
	for(i=0;i<period;i++){
		total_interest += (int)(operatingfund * rate_of_interest);
		operatingfund -= fee;
	}
	return total_interest + operatingfund;
}

int estimate_Fukuri(int operatingfund,double rate_of_interest,int period,int fee){
	int i;
	for(i=0;i<period;i++){
		operatingfund = operatingfund + (int)(operatingfund * rate_of_interest) - fee;
	}
	return operatingfund;
}

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

int main(void){
  int h, n;
  scanf("%d%d", &h, &n);
  int a[n];
  int S=0;
  int i;
  for(i=0; i<n; i++){
    scanf("%d", &a[i]);
    S+=a[i];
  }
  
  if(S<h){
    printf("No\n");
  }else{
    printf("Yes\n");
  }
  
  return 0;
}

Measured memory_bytes: 1976
def bomb(x,y):
    s=M[y]
    if s[x]=="0":return
    M[y]=s[:x]+"0"+s[x+1:]
    for e in [-3,-2,-1,1,2,3]:
        bomb(x+e,y)
        bomb(x,y+e)
    return

A=range(14)
B=range(3,11)
M=["00000000000000" for i in A]
z="000"
n=input()
for i in range(n):
    s=raw_input()
    for j in B:
        M[j]=z+raw_input()+z
    x=input()+2
    y=input()+2
    bomb(x,y)
    print "Data %d:" %(i+1)
    for j in B:
        print M[j][3:-3]

Measured memory_bytes: 4280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll a,b,c,d,e,f,i,j,s=0;
	cin>>a>>b>>c;
	if((a%2)==0||(b%2)==0||(c%2)==0) cout<<0;
	else 
	{
		cout<<min(a*b,min(b*c,c*a));
	}
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
	n, k = map(int, input().split())
	s = str(input())

	ans = []
	for i in range(len(s)):
		if i+1 == k:
			if s[i] == 'A':
				ans.append('a')
			if s[i] == 'B':
				ans.append('b')
			if s[i] == 'C':
				ans.append('c')
		else:
			ans.append(s[i])
	print(''.join(ans))

if __name__ == '__main__':
	import sys
	sys.exit(main())


Measured memory_bytes: 3060
fun main(args: Array<String>) {

    val (R, G, B, N) = readLine()!!.split(" ").map { Integer.parseInt(it) }
    val RMax = N / R + 1
    val GMax = N / G + 1
    val BMax = N / B + 1
    var result = 0

    for (r in 0 until RMax) {
        if ((r * R) > N) {
            break
        }
        for (g in 0 until GMax) {
            if ((r * R + g * G) > N) {
                break
            }
            val rest = N - (r * R + g * G)
            if (rest % B == 0) {
                if (((rest / B) <= BMax) && ((rest / B) >= 0)) {
                    result++
                }
            }

        }
    }
    print(result)

}

Measured memory_bytes: 38084
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System;
using System.Numerics;
using static System.Math;
using static System.Console;

class E { static void Main() => new J(); }
class J
{
	int F() => int.Parse(ReadLine());
	long FL() => int.Parse(ReadLine());
	int[] G() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
	long[] GL() => ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray();
	int MOD = 1000000007;
	public J()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var I = GL();
		Console.WriteLine(Abs(I[0] - I[1]) <= 1 ? "Brown" : "Alice");
	}
}

Measured memory_bytes: 13268
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
    if(x==1||x==3||x==5||x==7||x==8||x==10||x==12){
      if(y==1||y==3||y==5||y==7||y==8||y==10||y==12){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }
    }else if(x==4||x==6||x==9||x==11){
      if(y==4||y==6||y==9||y==11){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }
    }else{
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 20564
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <numeric>
#include <climits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <utility>
#include <cctype>
#include <iterator>
////////////////////////////////////////////////
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define REPe(e, mp) for (auto& e : mp)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
using ll = long long int;
using vecint = vector<int>;
using vecll = vector<ll>;
using vec2int = vector<vector<int>>;
using P = pair<int, int>;
////////////////////////////////////////////////
#include <iostream>
using namespace std;
////////////////////////////////////////////////
int main() {
  ////////////////////////////////////////////////
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ////////////////////////////////////////////////
  long double a;
  long double b;
  cin >> a >> b;
  ll c = floor(a * b);
  cout << c << endl;
}
//////////////////////////////////////////////


Measured memory_bytes: 3812
N,M=map(int,input().split())
H=list(map(int,input().split()))
ans=[0]*N    #N個のメモ欄を用意
for i in range(M):
    A,B=map(int,input().split())
    if H[A-1]<H[B-1]:    #A,Bで繋がれた展望台のうち、低いほうに印を着けていく。
        ans[A-1]+=1
    elif H[B-1]<H[A-1]:
        ans[B-1]+=1    #ここのB間違えとるやないかい
    else:    #AとBの標高が同じならどちらにも印をつける。
        ans[A-1]+=1
        ans[B-1]+=1
print(ans.count(0))    #印をつけられていない展望台をカウント。




Measured memory_bytes: 84740
#include<bits/stdc++.h>
const long double pi=acos(-1);
const int N=2e5+10;
using namespace std;
int arr[50];
bool check(int n)
{
	while(n)
	{
		if(arr[n%10])
		{
			return false;
		}
		n/=10;
	}
	return true;
}
int main()
{
  	string s,s1="";
  	cin>>s;
  	for(int i=0;i<s.size();i++)
  	{
  		if(s[i]=='1')
		s1+='1';
		if(s[i]=='0')
		s1+='0';
		if(s[i]=='B'&&s1.size()!=0)
		s1.erase(s1.end()-1);	
	}
	cout<<s1<<"\n";
	return 0;
}

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

int N, M;
vector<int> adj[110000];
ll dp1[110000];
ll dp2[110000];

void dfs(int nd, int prv = -1) {
	ll res = 1;
	for (int child : adj[nd]) {
		if (child == prv) continue;
		dfs(child, nd);
		res *= dp1[child];
		res %= M;
	}
	dp1[nd] = (res + 1) % M;
}

void dfs2(int nd, int prv = -1) {
	if (prv == -1) dp2[nd] = 1;
	vector<ll> lprod = vector<ll>(adj[nd].size(), 1);
	vector<ll> rprod = vector<ll>(adj[nd].size(), 1);
	for (int i = 0; i < adj[nd].size(); i++) {
		int child = adj[nd][i];
		if (i - 1 >= 0) lprod[i] = lprod[i - 1];
		if (child == prv) continue;
		lprod[i] *= dp1[child]; lprod[i] %= M;
	}
	for (int i = (int)adj[nd].size() - 1; i >= 0; i--) {
		int child = adj[nd][i];
		if (i + 1 < adj[nd].size()) rprod[i] = rprod[i + 1];
		if (child == prv) continue;
		rprod[i] *= dp1[child]; rprod[i] %= M;
	}
	for (int i = 0; i < adj[nd].size(); i++) {
		int child = adj[nd][i];
		if (prv == child) continue;
		ll rest_prod = 1;
		if (i - 1 >= 0) rest_prod = rest_prod * lprod[i - 1] % M;
		if (i + 1 < adj[nd].size()) rest_prod = rest_prod * rprod[i + 1] % M;
		dp2[child] = (rest_prod * dp2[nd] + 1) % M;
		dfs2(child, nd);
	}
}

ll ans[110000];
void dfs3(int nd, int prv = -1) {
	ans[nd] = dp2[nd];
	for (int child : adj[nd]) {
		if (child == prv) continue;
		ans[nd] *= dp1[child];
		ans[nd] %= M;
		dfs3(child, nd);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N - 1; i++) {
		int a, b; cin >> a >> b;
		a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(0);
	dfs2(0);
	dfs3(0);

	for (int i = 0; i < N; i++) cout << ans[i] << '\n';
	return 0;
}

Measured memory_bytes: 20608
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    print(sum(list(map(lambda x: x - 1, nl()))))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9308
//Code is like humor. When you have to explain it, it’s bad.
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#define MOD 1000000007
#define MOD1 998244353
#define endl "\n"
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mkp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pairs;
typedef map<int,int> maps;
typedef vector <int> VI;
typedef std::multimap<int, pair<int,int>>::iterator MMIPIterator;
typedef std::map<int, int>::iterator MIIIterator;
double pi = 2 * acos(0.0);

int32_t main()  {
    fastio;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    #endif
    
    int n;
    cin>>n;
    int i=0;
    int a = 100;
    while(a<n) {
    	a += (a/100);
    	i++;
    }
    cout << i << endl;
    return 0;
    //fflush(stdout);
}



Measured memory_bytes: 3652
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    string S; cin >> S;
    int N = sz(S);
    int data[N]; F0R(i, N) data[i] = S[i] - '0';

    int cost[N][2];
    F0R(i, N) {
        cost[i][0] = data[i];
        cost[i][1] = 9-data[i];
    }

    int dp[N+1];
    int best = 100000000;
    dp[0] = 0;

    F0R(i, N) {
        best = min(best, dp[i] + 2);
        best += cost[i][1];
        dp[i+1] = min(dp[i] + cost[i][0], best);
    }

    cout << dp[N] << endl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	ll a, b, n;
	cin >> a >> b >> n;

	//ll x = min(n, b-1);
	//cout << a*x/b - a * (x/b) << endl;
	cout << a*min(n, b-1) / b << endl;
	return 0;
}

Measured memory_bytes: 3612
n = input()
int_n = int(n)
len_n = len(n)
ans = sum([int(i) for i in n])

for i in range(len_n):
    target = int(n[:i+1][-1]) -1
    if target < 0:
        continue
    tmp_n = n[:i] + str(target) + '9'* (len_n - i - 1)
    tmp_n_ans = sum([int(i) for i in tmp_n])
    ans = max(tmp_n_ans, ans)
print(ans)

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

int main() {
    string S, T;
    cin >> S >> T;
    string ret = "Yes";
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) != T.at(i)) {       
            ret = "No";
            break;
        }
    }
    cout << ret << endl;
}

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

double EPS = 1e-9;

int main(){
  int A, B; cin >> A >> B;
  rep(i, 10000) {
    double c = 0.08 * i + EPS, d = 0.1 * i + EPS;
    if ((int)c == A && (int)d == B) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
int b[510][4];
struct wolf{
	int a[4];
	wolf(){}
};
inline bool operator==(const wolf &a,const wolf &b){
	for(int i=0;i<4;i++)if(a.a[i]!=b.a[i])return false;
	return true;
}
inline bool operator<(const wolf &a,const wolf &b){
	for(int i=0;i<4;i++){
		if(a.a[i]!=b.a[i])return a.a[i]<b.a[i];
	}
	return false;
}
wolf p[510];
int q[8];
int g[4][4]={
{0,4,6,1},
{1,6,7,2},
{2,7,5,3},
{4,0,3,5},
};
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		for(int j=0;j<4;j++)scanf("%d",&b[i][j]);
		
		for(int j=0;j<4;j++)p[i].a[j]=b[i][j];
		for(int j=1;j<4;j++){
			wolf tmp;
			for(int k=0;k<4;k++)tmp.a[k]=b[i][(j+k)%4];
			p[i]=min(p[i],tmp);
		}
	}
	std::sort(p,p+a);
//	for(int i=0;i<a;i++)printf("%d %d %d %d\n",p[i].a[0],p[i].a[1],p[i].a[2],p[i].a[3]);
	long long ret=0;
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					q[l]=p[i].a[(l+k/4)%4];
					
				}
				q[4]=p[j].a[(k+1)%4];
				q[5]=p[j].a[(k+2)%4];
				q[6]=p[j].a[(k)%4];
				q[7]=p[j].a[(k+3)%4];
				
				map<wolf,int> M;
				M[p[i]]=1;
				if(M.count(p[j]))M[p[j]]++;
				else M[p[j]]=1;
				long long ks=1;
				for(int l=0;l<4;l++){
					wolf tmp;
					wolf res;
					res.a[0]=q[g[l][0]];
					res.a[1]=q[g[l][1]];
					res.a[2]=q[g[l][2]];
					res.a[3]=q[g[l][3]];
					for(int m=1;m<4;m++){
						for(int n=0;n<4;n++)tmp.a[n]=q[g[l][(m+n)%4]];
						res=min(res,tmp);
					}
					int sz=0;
					for(int m=0;m<a;m++)if(res==p[m])sz++;
					if(sz==0){ks=0;break;}
			//		printf("%d %d %d %d\n",res.a[0],res.a[1],res.a[2],res.a[3]);
					if(M.count(res)){
						sz-=M[res];
						if(sz==0){ks=0;break;}
						M[res]++;
					}else{
						M[res]=1;
					}
					if(res.a[0]==res.a[1]&&res.a[0]==res.a[2]&&res.a[0]==res.a[3])sz*=4;
					else if(res.a[0]==res.a[2]&&res.a[1]==res.a[3])sz*=2;
					ks*=sz;
				}
				ret+=ks;
			}
		}
		
	}
	ret/=3;
	printf("%lld\n",ret);
}

Measured memory_bytes: 256