akhauriyash/Code-Regression huggingface dataset:
use std::cmp;
use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;

fn main() {
    let mut sc = Scanner::new();
    let (h, w) = (sc.parse(), sc.parse());
    println!("{}", solve(h, w));
}


fn solve(h: usize, w: usize) -> usize {
    let min_s_diff1 = {
        match h % 3 {
            0 => 0,
            _ => w,
        }
    };
    let min_s_diff2 = {
        match w % 3 {
            0 => 0,
            _ => h,
        }
    };
    let min_s_diff3 = {
        let mut min_s_diff3 = h * w;
        for h1 in 1..h {
            let s1 = w * h1;
            let s2 = (h - h1) * (w / 2);
            let s3 = (h - h1) * (w / 2 + (w % 2));
            if s1 <= s2 {
                min_s_diff3 = cmp::min(min_s_diff3, s3 - s1)
            } else if s1 <= s3 {
                min_s_diff3 = cmp::min(min_s_diff3, s3 - s2)
            } else if s3 < s1 {
                min_s_diff3 = cmp::min(min_s_diff3, s1 - s2);
                break;
            }
        }
        min_s_diff3
    };
    let min_s_diff4 = {
        let mut min_s_diff4 = h * w;
        for w1 in 1..w {
            let s1 = w1 * h;
            let s2 = (w - w1) * (h / 2);
            let s3 = (w - w1) * (h / 2 + (h % 2));
            if s1 <= s2 {
                min_s_diff4 = cmp::min(min_s_diff4, s3 - s1)
            } else if s1 <= s3 {
                min_s_diff4 = cmp::min(min_s_diff4, s3 - s2)
            } else if s3 < s1 {
                min_s_diff4 = cmp::min(min_s_diff4, s1 - s2);
                break;
            }
        }
        min_s_diff4
    };
    *[min_s_diff1, min_s_diff2, min_s_diff3, min_s_diff4]
         .iter()
         .min()
         .unwrap()
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}


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

const ll INF = 1e16;

template <typename T, bool f>
class sparse_table {
	int n;
	vector<vector<T>> t;
	T merge(const T& l, const T& r) {
		return f ? max(l, r) : min(l, r);
	}
public:
	sparse_table(const vector<T>& b) {
		n = b.size();
		t.push_back(b);
		for (int i = 2, j = 1; i <= n; i <<= 1, j++) {
			t.push_back(vector<T>());
			for (int k = 0; k + i <= n; k++) {
				t[j].push_back(merge(t[j - 1][k], t[j - 1][k + i / 2]));
			}
		}
	}
	T find(int l, int r) {
		r++;
		assert(0 <= l && l < r && r <= n);
		unsigned int w = r - l;
		int i = 31 - __builtin_clz(w);
		return merge(t[i][l], t[i][r - (1 << i)]);
	}
	T operator[](int id) {
		return t[0][id];
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, K;
	cin >> N >> M >> K;
	vector<ll> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sparse_table<ll, true> st1(A);
	sparse_table<ll, false> st2(A);
	vector<ll> dp(N + 1, INF);
	dp[0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = max(0, i - M + 1); j <= i; j++) {
			dp[i + 1] = min(dp[i + 1], dp[j] + K + (i - j + 1) * (st1.find(j, i) - st2.find(j, i)));
		}
	}
	cout << dp[N] << endl;
	return 0;
}



Measured memory_bytes: 7668
/*================================================================
*   Copyright (C) 2019 Sangfor Ltd. All rights reserved.
*
*   创 建 者： badcw
*   创建日期： 2020/1/26
*
================================================================*/
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn = 1e3+50;
const int mod = 1e9+7;
ll qp(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

template <class T>
inline bool scan(T& ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0; // EOF
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}

//template <class T>
//inline void out(T x) {
//    if (x > 9) out(x / 10);
//    putchar(x % 10 + '0');
//}

int main(int argc, char* argv[]) {
    ll a, b;
    cin >> a >> b;
    cout << (a / b + (a % b ? 1 : 0)) << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{

    public static void Main( )
    {

        var input = Console.ReadLine( ).Split( ).Select( long.Parse ).ToArray( );
        var N = input[ 0 ];
        var M = input[ 1 ];
        var K = input[ 2 ];

        var A = Console.ReadLine( ).Split( ).Select( long.Parse ).ToArray( );
        var B = Console.ReadLine( ).Split( ).Select( long.Parse ).ToArray( );

        var a = new long[ N + 1 ];
        for ( int i = 1; i < N + 1; i++ )
        {
            a[ i ] = a[ i - 1 ] + A[ i - 1 ];
        }
        var b = new long[ M + 1 ];
        for ( int i = 1; i <= M; i++ )
        {
            b[ i ] = b[ i - 1 ] + B[ i - 1 ];
        }

        long ans = 0;
        for ( int i = 0; i <= N; i++ )
        {
            if ( a[ i ] > K ) continue;

            long left = -1;
            long right = b.Length;
            while ( right - left > 1 )
            {
                long mid = ( left + right ) / 2;
                long value = b[ mid ];
                if ( value <= K - a[ i ] ) left = mid;
                else right = mid;
            } 

            ans = Math.Max( ans, i + left );
        }
        Console.WriteLine( ans );


    }
}





Measured memory_bytes: 73132
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    ll H;cin>>H;
    ll ans=1;
    while(ans<=H){
        ans*=2;
    }
    cout<<ans-1<<endl;
}


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

int main(void){
 int a,b;
 cin>>a>>b;

 if(b%a==0)cout<<b+a<<endl;
 else{
  cout<<b-a<<endl;
 }
 return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scn = new Scanner(System.in);
		if(scn.next().equals(scn.next())){
			System.out.println("H");
		}else{
			System.out.println("D");
		}
		scn.close();
	}
}


Measured memory_bytes: 21844
n = int(input())
nodes = [0 for i in range(n)]
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes[id] = li

def rooted_tree(id, depth, parent):
    out = {}
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[id]
    if depth == 0:
        out['type'] = 'root'
    elif len(nodes[id]) == 0:
        out['type'] = 'leaf'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[id]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))



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

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++

def main2(io):
	n=int(io())
	(t,x,y)=0,0,0
	for i in range(n):
		nt,nx,ny = map(int, io().split())
		dist = abs(x-nx) + abs(y-ny)
		duration = nt - t
		if dist > duration or dist%2 != duration%2:
			return False
		(t,x,y)=(nt,nx,ny)
	
	return True
	
def main(io):
	ret = main2(io)
	return 'Yes' if ret else 'No'

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int n,p[1<<18],q[1<<18],t[1<<18],f[1<<18];
bool circle(int a,int b,int c){return q[a]<q[b]&&q[b]<q[c]||q[b]<q[c]&&q[c]<q[a]||q[c]<q[a]&&q[a]<q[b];}
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>p[i];
		q[p[i]]=i;
	}
	f[n]=n;
	for(int i=n;--i;)
	{
		if(t[i+1])
		{
			if(circle(f[i+1],i,i+1))
			{
				t[i]=t[i+1],f[i]=f[i+1];
			}
			else
			{
				t[i]=t[i+1]+1,f[i]=i+1;
			}
		}
		else
		{
			if(q[i]<q[i+1])
			{
				t[i]=0,f[i]=i;
			}
			else
			{
				t[i]=1,f[i]=i+1;
			}
		}
	}
	cout<<t[1]<<endl;
}

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

int main(){
  string divide[4] = {"dream", "dreamer", "erase", "eraser"};
  string str; cin >> str;
  
  for (int i = 0; i < 4; i++) reverse(divide[i].begin(), divide[i].end());
  reverse(str.begin(), str.end());
  
  bool flag = true;
  for (int i = 0; i < str.size(); ){
    bool flag2 = false;
    for (int j = 0; j < 4; j++){
      if (str.substr(i, divide[j].size()) == divide[j]) {
        i += divide[j].size();
        flag2 = true;
      }
    }
    if (!flag2) {
      flag = false;
      break;
    }
  }
  if (flag) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}



Measured memory_bytes: 512
#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
	int n,l,r;
	int sum = 0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> l >> r;
		sum += r-l+1;
	}
	cout << sum << endl;
	return 0;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> R(2*M);
  for(int i = 0; i < 2*M; i++) cin >> R.at(i);
  
  vector<int> ans(N);
  for(int i = 0; i < N; i++){
    int count = 0;
    for(c : R){
     if(c == i + 1) count++;
    }
    ans.at(i) = count;
  }
  for(int i = 0; i < N; i++){
    cout << ans.at(i) << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(int i=0;i<n;i++)
int gcd(int a, int b){
    int r=1;
    while(r!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void revStr(char* str){
    int size = strlen(str);
    int i,j;
    char tmp = {0};
    for(i = 0, j = size - 1; i < size / 2; i++, j--){
        tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }return;
}
typedef struct{
    int a,b,c;
}data;

//昇順
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
//構造体降順
int comp( const void *c1, const void *c2 )
{
  data test1 = *(data *)c1;
  data test2 = *(data *)c2;
  int tmp1 = test1.b;   /* b を基準とする */
  int tmp2 = test2.b;
  return tmp2 - tmp1;
}

#define MAXSIZE 200000
int list[MAXSIZE];
int tail;

void Init(void){
    tail=0;
}
int Top(void){
    return 0;
}

int Next(int pos){
    if(pos<tail-1){
        return pos+1;
    }else{
        return -1;
    }
}
int Count(void){
    return tail;
}

int Item(int pos){
    if((pos>=0)&&(pos<tail)){
        return list[pos];
    }else{
        return 0;
    }
}
void Add(int value){
    if(tail<MAXSIZE){
        list[tail]=value;
        tail++;
    }
}
void Delete(int pos){
    if((pos>=0)&&(pos<tail)){
        int i;
        for(i=pos;i<tail-1;i++){
            list[i]=list[i+1];
        }
        tail--;
    }
}
int kai(int n){
    if(n==0){
        return 1;
    }
    int sum=1;
    for(int i=1;i<=n;i++){
        sum*=i;
    }
    return sum;
}

int main(){
    char s[27];
    scanf("%s",s);
    rep(i,strlen(s)){
        rep(j,strlen(s)){
            if(j==i){
                ;
            }else if(s[j]==s[i]){
                printf("no");
                return 0;
            }else{
                ;
            }
        }
    }
    printf("yes");
    return 0;
}



Measured memory_bytes: 1736
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		TreeMap<Integer, Integer> a = new TreeMap<Integer, Integer>();
		for(int i = 0; i < n; i++){
		    int key = sc.nextInt();
		    if(a.containsKey(key)){
		        a.put(key, a.get(key) + 1);
		    }else{
		        a.put(key, 1);
		    }
		}
	    for(int i = 0; i < m; i++){
		    int b = sc.nextInt();
		    int c = sc.nextInt();
		    if(a.containsKey(c)){
		        a.put(c, a.get(c) + b);
		    }else{
		        a.put(c, b);
		    }
		}
		
		// 計算
		long result = 0;
		int rest = n;
		while(n > 0){
		    Map.Entry<Integer, Integer> entry = a.pollLastEntry();
		    long key = entry.getKey();
		    long val = entry.getValue();
		    if(rest > val){
		        result += key * val;
		        rest -= val;
		    }else{
		        result += key * rest;
		        break;
		    }
		}
		
		// 出力
		System.out.println(result);
	}
}

Measured memory_bytes: 110648
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

int dp[105][100005];			// dp[i][j] - min wt you can have with first i items and atmost j value

int32_t main(){
	int n, w;
	cin >> n >> w;
	int wt[n], val[n];
	for(int i = 0; i < n; i++)
		cin >> wt[i] >> val[i];
		
	const int INF = 1e9 + 15;
	
	for(int i = 0; i <= 100; i++)
		for(int j = 0; j <= 100000; j++)
			dp[i][j] = INF;
	
	for(int i = 0; i <= n; i++)
		dp[i][0] = 0;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= 100000; j++){
			dp[i][j] = dp[i-1][j];
			if(j - val[i-1] >= 0){
				dp[i][j] = min(dp[i][j],dp[i-1][j-val[i-1]] + wt[i-1]);
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= 100000; j++)
			if(dp[i][j] <= w)
				ans = max(ans,j);
	
	
	cout << ans << endl;
	
	return 0;
}



Measured memory_bytes: 80256
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <cmath>
#include <tuple>
#include <queue>
#include <set>

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


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

    int N, i;
    cin >> N >> i;

    cout << N - i + 1 << endl;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long k,a,b,c=0;
    cin >> k >> a >> b;
    for(int i=0;i*2<=k;i++){
        long x = k-2*i;
        if(x+1>=a) c = max(c,x+1+i*(b-a));
    }
    cout << c << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <map>

using namespace std;

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

    constexpr int kMods[] = {-1, 0, 1};
    map<int, int> count;

    for (auto i = 0; i < n; i += 1) {
        int num;
        cin >> num;

        for (const auto &mod : kMods) {
            count[num + mod] += 1;
        }
    }

    auto res = 0;
    for (const auto &p : count) {
        res = max(res, p.second);
    }

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


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
//size_t f = string::npos
//make pair, tuple

int main(){
      int n,m;cin >> n >> m;
      char arr[n + 5][m + 5];
      for(int i = 0;i < m + 2;i++)cout << '#';
      cout << "\n";
      for(int i = 0;i < n;i++){
            cout << '#';
            for(int i = 0;i < m;i++){
                  char t;cin >> t;
                  cout << t;
            }
            cout << "#\n";
      }
      for(int i = 0;i < m + 2;i++)cout << '#';
}

Measured memory_bytes: 256
// #pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma vector temporal
// #pragma simd
// #pragma GCC diagnostic ignored "-W"

#include<cassert>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<sstream>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<vector>
#include<utility>
#include<functional>
#include<complex>
#include<climits>

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vint vector<int>
#define SS stringstream
#define PQ priority_queue
#define MS(x,v) memset((x),(v),sizeof(x))
#define RZUNI(x) sort(x.begin(),x.end()), x.resize(unique(x.begin(),x.end())-x.begin())
#define FLH fflush(stdout)
#define CPPinput ios_base::sync_with_stdio(0); cin.tie(0)
#define FIN(fname) freopen(fname,"r",stdin)
#define FOUT(fname) freopen(fname,"w",stdout)

#define tm Ovuvuevuevue
#define y1 Enyetuenwuevue
#define left Ugbemugbem
#define ws Osas
#define dec tetteterette
#define exp expexpexpexp
#define expl explexplexpl

#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl

#ifdef WEAK
#include"/home/edison/Coding/cpp/template/debug.cpp"
#define DEB(...) printf(__VA_ARGS__),fflush(stdout)
#define WHR() printf("%s: Line %d",__PRETTY_FUNCTION__,__LINE__),fflush(stdout)
#define LOG(...) printf("%s: Line %d ",__PRETTY_FUNCTION__,__LINE__),printf(__VA_ARGS__),fflush(stdout)
#define DEBUG 1
#define exit(x) cout<<"exit code "<<x<<endl, exit(0)
#else
#define PDE(...) ;
#define DEB(...) ;
#define WHR() ;
#define LOG(...) ;
#define DEBUG 0
#endif

#define lowbit(x) ((x)&(-(x)))

#if __cplusplus >= 201103L
#include<unordered_map>
#include<unordered_set>
#include<tuple>
#endif

void JIZZ(string output=""){cout<<output; exit(0);}

const ld PI=3.14159265358979323846264338327950288;
const ld eps=1e-13;
const ll mod=1e9+7;

long long a[55];
int main(){
    CPPinput;
    int n; cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    long long ans=0;
    while(1){
        bool meow=0;
        for(int i=1;i<=n;++i){
            if(a[i]>=n){
                meow=1;
                ans+=a[i]/n;
                for(int j=1;j<=n;++j){
                    if(i==j)continue;
                    a[j]+=a[i]/n;
                }
                a[i]%=n;
            }
        }
        if(!meow)break;
    }
    cout<<ans<<endl;
}


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

long long solve(long long N){
  long long l = 2;
  long long m = 1;
  long long t;
  for (int i = 2; i <= N; i++) {
    t = m;
    m = l + m;
    l = t;
  }
  return m;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
  long long N;
  scanf("%lld",&N);
  cout << solve(N) << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int n,i;
  double a,sum=0.0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%lf",&a);
    a=1/a;
    sum+=a;
  }
  sum=1/sum;
  printf("%lf\n",sum);
  return(0);

}


Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

ll N, K;
vector<vector<int> > edge(100005);

ll anstree[100005];

void solve(int v, int u){
  ll num = 0;
  if(u==-1){
    for(ll i=0;i<edge[v].size();++i){
      if(edge[v][i]==u) continue;
      anstree[edge[v][i]] = K-1-num;
      num++;
      solve(edge[v][i], v);
    }
  }
  else{
    for(ll i=0;i<edge[v].size();++i){
      if(edge[v][i]==u) continue;
      anstree[edge[v][i]] = K-2-num;
      num++;
      solve(edge[v][i], v);
    }
  }
}

int main() {
  cin>>N>>K;
  int a, b;
  for(int i=0;i<N-1;++i){
    cin>>a>>b;
    a--;
    b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  anstree[0] = K;
  solve(0, -1); 
  ll ans = 1;
  for(int i=0;i<N;++i){
    ans *= anstree[i];
    ans %= mod;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 13912
def comb(n, r, mod):
    r = min(r, n-r)
    mol = 1
    deno = 1
    for i in range(1, r+1):
        mol = mol * (n-r+i) % mod
        deno = deno * i % mod
    ret = mol * pow(deno, mod-2, mod) % mod
    return ret

n,a,b = map(int,input().split())

P = 10**9+7

nCa = comb(n, a, P)
nCb = comb(n, b, P)

ans = (pow(2,n,P) -1 - nCa - nCb + 2*P)%P
print(ans)


Measured memory_bytes: 38512
#include <cstdint>
#include <iostream>

void shift(uint64_t &v)
{
    v = v << 1;
}

int main(void)
{
    uint64_t a, b, c;
    uint32_t k;

    std::cin >> a >> b >> c;
    std::cin >> k;

    for (uint32_t i=0; i < k; ++i) {
        if (a >= b && a >= c) shift(a);
        else if (b > a && b >= c) shift(b);
        else shift(c);
    }

    std::cout << a+b+c << std::endl;

    return 0;
}

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

#define pb push_back
#define int ll

using ll=long long;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vpii=vector<pii>;
using vvpii=vector<vpii>;

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

    int n;
    cin >> n;
    vi hs(n);
    for (int i=0; i<n; ++i)
        cin >> hs[i];
    int prev = 0;
    bool poss = true;
    for (int i=0; i<n; ++i) {
        if (hs[i] < prev) {
            poss = false;
            break;
        }
        if (hs[i]-1 >= prev)
            --hs[i];
        prev = hs[i];
    }
    if (poss)
        cout << "Yes\n";
    else
        cout << "No\n";
}


Measured memory_bytes: 1024
#n,m=0,0
n, m = map(int, input().split( ))
a = []
b = []
c = []
for _ in range(m):
    A,B = map(int, input().split( ))
    C = list(map(int, input().split( )))
    C2 = 0
    for i in C:
        C2 += 2**(i-1)
    a.append(A)
    c.append(C2)

#print(a)
#print(c)
#dp = [[10**9 for j in range(2**n)] for i in range(m)]
dp = [10**9 for j in range(2**n)]
dp[0] = 0
#for i in range(m):
#    dp[i][0] = 0
#print(dp)
##ちょうど開く箱がどれか、で状態を追う。
##指定した箱以外は開いていない。

#直前以外使わないのだが
#c[i]まで使ったdpとc[i-1]までしか使っていないdpが混在していいのか
#↑試しに消してみた
for i in range(m):
    for j in range(2**n):
        #dp[i][j] = min(dp[i][j],dp[i-1][j])
        dp[j|c[i]] = min(dp[j|c[i]],dp[j] + a[i])

        #dp[i][j|c[i]] = min(dp[i-1][j|c[i]],dp[i-1][j] + a[i])
        #print(dp[i][j|c[i]],end = " ")
    #print(dp[i],dp[i][c[i]])
#print(dp)
#print(dp[m-1][2**n-1])
if dp[2**n-1]<10**9-1:
    print(dp[2**n-1])
else:
    print(-1)


Measured memory_bytes: 46184
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const ll inf = 1e18;
const int mod = 1e9+7;
const int N = 1e5+5;
//int a[N];

int main()

{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int m, d, ans = 0;

    cin >> m >> d;

    for (int i = 4; i <= m; i++) {

        for (int j = 2; j <= d; j++) {

            for (int k = 2; k < 10; k++) {

                if (j*k == i && j*10+k <= d) {

                	ans++;
                	//cout << j << " " << k << endl;
                }
            }
        }
    }

    cout << ans;

    return 0;
}


//long long vs int
//pow function (+0.5)
//read carefully: overflow, constraints, etc...


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

#ifndef DEBUG
#define endl '\n'
#define debug(...)
#else
#define debug(...) __VA_ARGS__
#endif
#define debugf(...) debug(printf(__VA_ARGS__);)

const int N = 1e5 + 5;

int f[N];


int (((((main)))))() <%
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int d; cin >> d;
        for (int i = 0; i < d; i++) {
            int x; cin >> x;
            f[x]++;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!f[i])
            ans++;
    }

    cout << ans << endl;

    return 0;
%>

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N-1);
    REP(i,N){
        cin >> A[i];
        --A[i];
    }
    REP(i,N) cin >> B[i];
    REP(i,N-1) cin >> C[i];
    int ans = 0;
    REP(i,N){
        ans += B[A[i]];
        if(i >= 1 && A[i-1] + 1 == A[i]) ans += C[A[i]-1];
        //cout << ans << endl;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct wj{
	int t;
	int f;
	char s;
}a[200005];
int main(){
	int n,m=0,k;
	char st[600005];
	int l=300000,r;
	scanf("%s",st+l);
	for(r=l;st[r]!='\0';r++);
//	cout<<r<<endl;
	cin>>k;
	for(int i=0;i<k;i++){
		cin>>n;
		if(n==1){
			m++;
			a[i].t=1;
		}
		else{
			a[i].t=2;
			cin>>a[i].f>>a[i].s;
		}
	}
	n=0;
	int l1=l,r1=r;
	for(int i=0;i<k;i++){
		if(a[i].t==1){
			n++;
		}
		else{
			if((m-n+a[i].f)%2==1){
				st[--l1]=a[i].s;
			}
			else st[r1++]=a[i].s;
		}
	}
	int i=r;
	for(;l1<l;l1++) printf("%c",st[l1]);
	if(m%2){
		for(r--;r>=l;r--) printf("%c",st[r]);
	}
	else {
		for(l;r>l;l++) printf("%c",st[l]);
	}
	for(;i<r1;i++) printf("%c",st[i]);
	cout<<endl;
	return 0;
}


Measured memory_bytes: 3200
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
V = lr()
answer = 0
limit = min(N, K)
for i in range(limit+1): # iは左から取り出す個数
    for j in range(limit-i+1): # jは右から取り出す個数
        stone = V[:i] + V[N-j:]
        stone.sort()
        result = sum(stone)
        if result > answer:
            answer = result
        for k in range(min(len(stone), K-(i+j))): # kは戻す個数
            if stone[k] > 0:
                break
            result -= stone[k] 
            if result > answer:
                answer = result

print(answer)
# 07

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define SIZE 5005
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
 
bool dp[SIZE];
int A[SIZE];
P pos[SIZE];
 
int main()
{
	int n,K;
	scanf("%d %d",&n,&K);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	//iを含む中で、K以上K+A[i]未満のものがあればok
	//i以外でぎりぎりK未満のものがあればよさそう
	sort(A,A+n);
	ll sum=0;
	for(int i=0;i<n;i++) sum+=A[i];
	memset(dp,false,sizeof(dp));
	dp[0]=true;
	int ret=0;
	for(int i=n-1;i>=0;i--)
	{
		bool up=false;
		for(int j=0;j<K;j++)
		{
			if(dp[j]&&j+sum>=K) up=true;
		}
		if(!up) ret++;
		sum-=A[i];
		for(int j=K-1;j>=A[i];j--) dp[j]|=dp[j-A[i]];
	}
	printf("%d\n",ret);
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; ++i) cin >> A[i];
    int res = 0;
    while (true) {
        bool exist_odd = false;
        for (int i = 0; i < N; ++i) if (A[i] % 2 != 0) exist_odd = true;
        if (exist_odd) break;
        for (int j = 0; j < N; ++j) A[j] /= 2;
        ++res;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define N 200100
#define pii pair<int,int>
#define rep(i,k,n) for(int i=k;i<n;i++)
#define vi vector<int>
#define inf 1e9
vector<string> v;
void permute(string a,int l,int r){
	if(l==r){
		v.push_back(a);
		return;
	}
	for(int i=l;i<=r;i++){
		swap(a[l],a[i]);
		permute(a,l+1,r);
		swap(a[l],a[i]);
	}
}
void solve(){
	int n;
	cin>>n;
	string a="";
	for(int i=1;i<=n;i++){
		a+='0'+i;
	}
	permute(a,0,n-1);
	// for(auto i:v){
	// 	cout<<i<<endl;
	// }
	sort(v.begin(),v.end());
	string s1="";
	for(int i=1;i<=n;i++){
		int temp;
		cin>>temp;
		s1+='0'+temp;
	}
	string s2="";
	for(int i=1;i<=n;i++){
		int temp;
		cin>>temp;
		s2+='0'+temp;
	}
	int pos1,pos2;
	for(int i=0;i<v.size();i++){
		if(v[i]==s1){
			pos1=i;
			break;
		}
	}
	for(int i=0;i<v.size();i++){
		if(v[i]==s2){
			pos2=i;
			break;
		}
	}
	cout<<abs(pos1-pos2)<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Measured memory_bytes: 2424
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

typedef long long ll;
typedef pair< int, int > pii;

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

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

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

  ll m;
  cin >> m;

  for(ll n = 1; n <= 3500; n++){
    for(ll h = 1; h <= 3500; h++){
      if(4 * h * n - m * n - m * h <= 0) continue;
      if((m * h * n) % (4 * h * n - m * n - m * h) != 0)
        continue;
      ll w = (m * h * n) / (4 * h * n - m * n - m * h);
      if(w < 0 || w > 3500) continue;
      cout << to_string(n) + " " + to_string(h) + " "
        + to_string(w) << endl;
        return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< ll, ll >   cp2;
typedef pair< string, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789


///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////

int N, M;
int k[11];
int s[11][11];
int p[11];
int ans = 0;
int idx[11];
bool flag;
int a = 0;

int main(){
    
    cin>>N>>M;
    fill( idx, idx+11, 0);
    
    REP( i, M ){
        cin>>k[i];
        REP(j, k[i]){
            cin>>s[i][j];
            idx[s[i][j]] = 1;
        }
    }
    
    REP( i, 11 ) if( idx[i] == 1 ) idx[i] = a++;
    
    REP( i, M ) cin>>p[i];
    
    REP( x, 1<<N ){
        flag = true;
        REP( i, M ){
            int cnt = 0;
            REP( j, k[i] ) cnt += (1 && ( x & 1<<idx[s[i][j]] ) );
            if( cnt % 2 != p[i] ){
                flag = false;
                break;
            }
        }
        if( flag ){
            ans++;
            //cout<<"***"<<x<<endl;
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}



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

#define SENTINEL 1000000000

void mergeSort(int [], int, int);
void merge(int [], int, int, int);
int count=0;

void mergeSort(int A[],int left,int right){
  int i,mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}



void merge(int A[],int left,int mid,int right){
  int n1,n2,i,j,k;
  int *L,*R;
  n1=mid-left;
  n2=right-mid;
  L=(int *)malloc(sizeof(int)*(n1+1));
  R=(int *)malloc(sizeof(int)*(n2+1));
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(j=0;j<=n2-1;j++){
    R[j]=A[mid+j];
  }
  L[n1]=SENTINEL;
  R[n2]=SENTINEL;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      count++;
    }
        else{
      A[k]=R[j];
      j++;
      count++;
    }
  }
  free(L);
  free(R);
}


main(){
  int A[500000];
  int n,i;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  mergeSort(A,0,n);
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i<n-1)printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
}


Measured memory_bytes: 5456
#include<bits/stdc++.h>
#define REP(n)    for(int i = 0; i < (n); ++i)
#define RREP(n)   for(int i = (n); i >= 0; --i)
#define FOR(m, n) for(int i = (m); i < (n); ++i)
#define SZ(x)       ( (int)(x).size() )
#define BIT(n)      ( 1LL << (n) )
#define EXIST(x)    ( (x).find()		!= (x).end() )
#define DEBUG(n)    cerr << #n << " : " << n << '\n';
#define PB  push_back
#define UB  upper_bound			//k <
#define LB  lower_bound			//k	<= 
#define F   first
#define S   second
#define INF 1.0e9


using namespace std;

typedef long long			ll;
typedef pair<int, int>		pii;
typedef pair<long			long, long long>   pll;
typedef vector<int>			vi;
typedef vector<double>		vd;
typedef vector<long long>   vll
;

template<class T> void chmax(T &	a, const T & b){ if( a < b ) a = b; }
template<class T> void chmin(T &	a, const T & b){ if( a > b ) a = b; }

int r_up(const int a, const int b){ return (a + b - 1) / b; }

const int dx[] = { 0,  0, 1, -1 };
const int dy[] = { 1, -1, 0,  0 };

struct UFT{
  vi	p;
  UFT(){}
  UFT(int N)       { p.resize( N, -1 ); }
  int	par(int a)   { if( p[a] >= 0 ){ p[a]  = par( p[a] ); return p[a]; } return a;  }
  int size(int a)  { return -p[par(a)]; }
  bool	same(int a, int b) { return par(a)	 == par(b); }
  void unite(int	a, int b){
	a													  = par(a);  b = par(b);
	if( a == b ) return;
	if( size(a) < size(b) ) swap(a,b);
	p[a]												 -= size(b);
	p[b]												  = a;
  }
};

vll cnt(51,0);

ll rec(int n,ll x){
  DEBUG(n);
  DEBUG(x);
  DEBUG(cnt[n]);
  
  if(x==0)return 0;
  ll ans=0;
  if(cnt[n]/2>x)
  	return rec(n-1,x-1);
  if(cnt[n]/2==x)
	return cnt[n]/4;
  if(cnt[n]/2+1==x)
  	return cnt[n]/4+1;
  if(cnt[n]==x)
	return cnt[n]/2+1;
  return cnt[n]/4+1+rec(n-1,x-(cnt[n]/2+1));
}

int main(){
  int n;
  ll x;
  cin>>n>>x;

  cnt[0]=1;
  FOR(1,51)cnt[i]=cnt[i-1]*2+3;

  cout<<rec(n,x)<<endl;
  
  return 0;
}


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

#define int long long
int pw(int n,int k,int MOD){
  assert(k>=0);
  int res=1;
  while(k){
    if(k&1)(res*=n)%=MOD;
    (n*=n)%=MOD;
    k>>=1;
  }
  return res;
}
int f(string s,int a){
  if(a==0)return -1;
  int res=0,t=1;
  reverse(s.begin(),s.end());
  for(int i=0;i<s.size();i++){
    (res+=t*(s[i]=='1'))%=a;
    (t*=2)%=a;
  }
  return res;
}
int p(int a){
  int res=0;
  while(a){
    if(a&1)res++;
    a>>=1;
  }
  return res;
}
int F(int a){
  int res=0;
  while(a){
    res++;
    a%=p(a);
  }
  return res;
}

signed main(){
  int n;cin>>n;
  string s;cin>>s;
  int sum=0;
  for(char p:s)sum+=p=='1';
  int A=f(s,sum+1);
  int B=f(s,sum-1);
  for(int i=0;i<n;i++){
    if(sum==1&&s[i]=='1'){
      cout<<0<<endl;
      continue;
    }
    if(s[i]=='0'){
      int res=A;
      res+=pw(2,n-i-1,sum+1);res%=sum+1;
      cout<<F(res)+1<<endl;
    }
    else{
      int res=B;
      res-=pw(2,n-i-1,sum-1);
      res+=sum-1;res%=sum-1;
      cout<<F(res)+1<<endl;
    }
  }
}


Measured memory_bytes: 3916
n = [int(x) for x in input()]
s=len(n)-1

for i in range(2 **s):
    op = ["-"] * s
    for j in range(s):
        if ((i >> j) & 1):
            op[s - 1 - j] = "+"

    sum=n[0]
    ans=str(n[0])
    
    for i in range(s):
        if op[i] == '+':
            sum+=n[i+1]
            ans += '+'
        else:
            sum-=n[i+1]
            ans += '-'
        ans += str(n[i+1])

    if sum == 7:
        ans+='=7'
        print(ans)
        break



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5, inf = 1e8;
int n, p[maxn + 10], val[maxn + 10];
int f[maxn + 10][2], suf[maxn + 10];
vector<int> a, b, ans;

struct bit {
	int c[maxn + 10], w[maxn + 10];
	vector<pair<int, int> > mod[maxn + 10];
	
	void sss() {
		memcpy(w, c, sizeof c);
	}
	
	void xxx() {
		memcpy(c, w, sizeof w);
	}

	void init(int v) {
		for (int i = 1; i <= n + 1; ++i) c[i] = v;
	}

	void modify(int p, int v, int id) {
		p = n + 1 - p;
		for (; p <= n + 1; p += p & -p) {
			mod[id].push_back(make_pair(p, c[p]));
			c[p] = max(c[p], v);
		}
	}

	int query(int p) {
		p = n + 1 - p;
		int ans = -inf;
		for (; p; p -= p & -p) ans = max(ans, c[p]);
		return ans;
	}
	
	void undo(int id) {
		for (auto i: mod[id])
			c[i.first] = i.second;
	}

}c[2];

bool push(vector<int> &a, int v) {
	if (a.empty() || v > a.back()) {
		a.push_back(v); return 1;
	}
	return 0;
}

bool chk(int id) {
	int v = (int)b.size() + suf[id + 1] - (int)a.size();
	return v >= 0 && c[v & 1].query(a.empty() ? 0 : a.back()) >= v;
}

vector<int> solve1() {
	c[0].xxx(); c[1].xxx();
	a.clear(); b.clear();
	vector<int> ans;
	for (int i = 1; i <= n; ++i) {
		c[0].undo(i); c[1].undo(i);
		bool is = push(a, p[i]);
		if (chk(i)) ans.push_back(0);
		else {
			ans.push_back(1);
			if (is) a.pop_back();
			push(b, p[i]);
			if (!chk(i)) {
				ans.clear(); ans.push_back(inf);
				return ans;
			}
		}
	}
	return ans;
}

vector<int> solve2() {
	c[0].xxx(); c[1].xxx();
	a.clear(); b.clear();
	vector<int> ans;
	for (int i = 1; i <= n; ++i) {
		c[0].undo(i); c[1].undo(i);
		bool is = push(b, p[i]);
		if (chk(i)) ans.push_back(0);
		else {
			ans.push_back(1);
			if (is) b.pop_back();
			push(a, p[i]);
			if (!chk(i)) {
				ans.clear(); ans.push_back(inf);
				return ans;
			}
		}
	}
	return ans;
}


int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
	for (int i = 1; i <= n; ++i)
		if (push(a, p[i])) val[i] = 2;
		else val[i] = 1;
	c[0].init(0); c[1].init(-inf);
	for (int i = 1; i <= n; ++i) f[i][0] = f[i][1] = -inf;
	for (int i = n; i >= 1; --i) {
		f[i][val[i] & 1] = c[0].query(p[i]) + val[i];
		f[i][(val[i] ^ 1) & 1] = c[1].query(p[i]) + val[i];
		c[0].modify(p[i], f[i][0], i);
		c[1].modify(p[i], f[i][1], i);
	}
	for (int i = n; i >= 1; --i) suf[i] = suf[i + 1] + val[i] - 1;
	c[0].sss(); c[1].sss();
	ans = min(solve1(), solve2());
	if (ans[0] == inf) {
		printf("-1"); return 0;
	}
	for (auto i: ans) printf("%d", i);
}


Measured memory_bytes: 68084
// ネタバレ防止






























#include <iostream>    
#include <vector>
#include <queue>
#include <functional>
#include <utility>
using namespace std;

template<class T>
vector<T> dijkstra(vector<vector<int>> E, vector<vector<T>> W, int s, T inf)
{
    int n = (int)E.size();

    vector<T> D(n, inf);
    typedef pair<T,int> P;
    priority_queue<P,vector<P>,greater<P>> Q;

    D[s] = T();
    Q.push(make_pair(D[s], s));

    while (!Q.empty())
    {
        int d = Q.top().first;
        int p = Q.top().second;
        Q.pop();
        if (d > D[p])
            continue;
        for (int i=0; i<(int)E[p].size(); i++)
        {
            int t = E[p][i];
            if (d+W[p][i] < D[t])
                D[t] = d+W[p][i],
                Q.push(make_pair(D[t], t));
        }
    }
    return D;
}

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

    vector<vector<int>> E(K+1);
    vector<vector<int>> W(K+1);
    for (int k=0; k<=K; k++)
        for (int i=0; i<10; i++)
        {
            int t = k+K*i;
            E[k].push_back(t/10);
            W[k].push_back(t%10);
        }
    int ans = K;
    for (int i=1; i<10; i++)
        ans = min(ans, dijkstra(E, W, K*i/10, K)[0] + K*i%10);
    cout<<ans<<endl;
}


Measured memory_bytes: 40120
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  
  if(S=="SUN") cout << 7 << endl;
  else if(S=="MON") cout << 6 << endl;
  else if(S=="TUE") cout << 5 << endl;
  else if(S=="WED") cout << 4 << endl;
  else if(S=="THU") cout << 3 << endl;
  else if(S=="FRI") cout << 2 << endl;
  else cout << 1 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100
#define INFTY (1<<21)
#define LEN 1000


int Q[LEN];
int head, tail;
int n, G[N][N], d[N];

void enqueue(int x){
  Q[tail] = x;
  tail = ( tail + 1 ) % LEN;
}

void dequeue(){
  int x = Q[head];
  head = ( head + 1 ) % LEN;
}

void bfs(int s){
  int i, u, v;

  enqueue(s);

  for( i = 0 ; i < n ; i++ ) d[i] = INFTY;
  d[s] = 0;

  while( head != tail ){
    u = Q[head];
    dequeue();
    for( v = 0 ; v < n ; v++ ){
      if( G[u][v] == 0 ) continue;
      if( d[v] != INFTY ) continue;
      d[v] = d[u] + 1;
      enqueue(v);
    }
  }

  for( i = 0 ; i < n ; i++ ){
    printf("%d %d\n",i+1,((d[i]==INFTY) ? (-1) : d[i]));
  }
}

int main(){
  int i, j, u, k ,v;

  scanf("%d",&n);

  for( i = 0 ; i < n ; i++ ){
    for( j = 0 ; j < n ; j++ ){
      G[i][j] = 0;
    }
  }

  for( i = 0 ; i < n ; i++ ){
    scanf("%d%d",&u,&k);
    u--;
    for( j = 0 ; j < k ; j++ ){
      scanf("%d",&v);
      v--;
      G[u][v] = 1;
    }
  }
  
  bfs(0);
  return 0;

}



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

ll mod = 1e9+7;
ll dp[401][401];
ll p[401][401];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    ll n,m;
    cin>>n>>m;
    ll a[n],b[n];
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    for(ll i=1;i<=400;i++){
        p[i][0]=1;
        for(ll j=1;j<=400;j++){
            p[i][j] = p[i][j-1]*i%mod;
        }
    }
    for(int i=1;i<=400;i++){
        for(int j=0;j<=400;j++){
            p[i][j] += p[i-1][j];
            p[i][j] %= mod;
        }
    }
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=j;k++){
                ll sum = p[b[i]][k] + mod - p[a[i]-1][k];
                sum %= mod;
                dp[i+1][j] += sum * dp[i][j-k];
                dp[i+1][j] %= mod;
                // cerr << sum << " " << dp[i][j-k] << " " << sum*dp[i][j-k] << endl;
            }
        }
    }
    cout << dp[n][m] << endl; 
    

}

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

int main(){
    string s,t;
    int ans;
    cin >> s >> t;
    ans = t.size();
    /**/
    int m = 0;
    for(int i = 0;i < s.size() - t.size() + 1;i++){
        int cnt = 0;
        for(int j = 0;j < t.size();j++){
            if(t[j] == s[i + j]){
                cnt++;
            }
        }
        m = max(m, cnt);
    }

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

Measured memory_bytes: 3176
from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0]*N

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)



Measured memory_bytes: 124452
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int a,b,c; cin>>a>>b>>c;
	cout<<max({a,b,c})-min({a,b,c});
	
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>

#include <vector>
#include <map>
#include <algorithm>
#include <fstream>
#include<cstdio>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include <cstdlib>
#include <typeinfo>

#define REP(i, n) for(int i=0;i<n;i++)
#define REP2(i, s, n) for(int i=s;i<n;i++)
#define REP_1(i, n) for(int i=1;i<n+1;i++)
#define bitSearch(bit, n) for(int bit = 0; bit < (1 << N); bit++)
using namespace std;

void printAns(long long a) { cout << a << endl; }

void yesno(bool a) { if (a)cout << "Yes" << endl; else cout << "No" << endl; }

void YESNO(bool a) { if (a)cout << "YES" << endl; else cout << "NO" << endl; }

typedef long long ll;
typedef unsigned long ul;
typedef long double ld;

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//ll INF = 10000000;
//ll mod = 1000000007;//10^9+7

//using Graph = vector<vector<pair<int, int>>>;
//Graph G(100100);


//番号ズレ注意！！
int main() {
    int A, B;
    cin >> A >> B;
    int ans = A + B;
    chmax(ans, A - B);
    chmax(ans, A * B);
    printAns(ans);
}


Measured memory_bytes: 256
A=list(map(int,input().split()))
x1=A[0]
y1=A[1]
B=list(map(int,input().split()))
x2=B[0]
y2=B[1]
C=list(map(int,input().split()))
x3=C[0]
y3=C[1]
a=((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))**0.5
b=((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1))**0.5
c=((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3))**0.5
S=abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/2
print(2*S/(a+b+c+4*S/(max(a,b,c))))


Measured memory_bytes: 3316
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	decimal[] GD => Strs.Select(decimal.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	static T[] ConstantArray<T>(int n, T val) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = val; return a; }
	static T[] MakeArray<T>(int n, Func<int, T> f) { var a = new T[n]; for (var i = 0; i < n; i++) a[i] = f(i); return a; }
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int N, min = int.MaxValue;
	int[] A, l, x;
	void Solve()
	{
		var I = G;
		N = I[0];
		A = I.Skip(1).ToArray();
		l = MakeArray(N, _ => F);
		x = new int[N];
		DFS(0);
		WriteLine(min);
	}
	void DFS(int n)
	{
		if (n == N)
		{
			var s = 0;
			var c = new int[3];
			var L = new int[3];
			for (var i = 0; i < N; i++) if (x[i] < 3) { c[x[i]]++; L[x[i]] += l[i]; }
			if (c.Contains(0)) return;
			for (var i = 0; i < 3; i++) s += Abs(L[i] - A[i]) + 10 * (c[i] - 1);
			min = Min(min, s);
		}
		else for (x[n] = 0; x[n] < 4; x[n]++) DFS(n + 1);
	}
}


Measured memory_bytes: 17484