akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;

namespace ALDS1_4B{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            var N = sr.Next<int>();
            var S = sr.Next<int>(N);
            var Q = sr.Next<int>();
            var T = sr.Next<int>(Q);

            Console.WriteLine(T.Count(t => Array.BinarySearch(S, t) >= 0));
            //---------------------------------
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = Console.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }
    }
}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> S[M];
    for (int i = 0; i < M; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int s;
            cin >> s;
            S[i].push_back(s);
        }
    }
    vector<int> P(M);
    for (int i = 0; i < M; i++)
        cin >> P[i];

    int res = 0;
    for (int i = 0; i < (1 << N); i++) {
        vector<int> v;
        for (int j = 0; j < N; j++) {
            if ((i >> j) & 1) {
                v.push_back(j + 1);
            }
        }

        bool flag = true;
        for (int j = 0; j < M; j++) {
            int cnt = 0;
            for (int k = 0; k < S[j].size(); k++) {
                if (binary_search(v.begin(), v.end(), S[j][k])) {
                    cnt++;
                }
            }
            if (cnt % 2 != P[j]) {
                flag = false;
                break;
            }
        }
        if (flag) res++;
    }
    cout << res << endl;
    return 0;
}

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

using namespace std;

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

    if(s[0]=='R'&& s[1]=='R'&&s[2]=='R'){
        cout<<"3"<<endl;
    }
    else if(s[0]!='R'&& s[1]!='R'&&s[2]!='R'){
        cout<<"0"<<endl;
    }
    else if(s[0]=='R'&& s[1]=='R' || s[1]=='R'&&s[2]=='R'){
        cout<<"2"<<endl;
    }
    else{
        cout<<"1"<<endl;
    }



    return 0;
}


Measured memory_bytes: 3628
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
c=[0]*m
d=[0]*m
x=[9999999999]*n
ans=[0]*n
for i in range(n):
  a[i],b[i]=map(int,input().split())
for i in range(m):
  c[i],d[i]=map(int,input().split())
for i in range(n):
  for j in range(m):
    dis=abs(a[i]-c[j])+abs(b[i]-d[j])
    if dis<x[i]:
      ans[i]=j+1
      x[i]=dis
for i in range(n):
  print(ans[i])

Measured memory_bytes: 3064
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

H = I()

sum=0
for i in range(40):
    p = pow(2,i)
    if p > H:
        n = i-1
        break
    sum += p

print(sum)


Measured memory_bytes: 27176
# abc158_b.py
# https://atcoder.jp/contests/abc158/tasks/abc158_b

# B - Count Balls /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# 高橋君は青と赤の 2色のボールを持っており、これらを一列に並べようとしています。
# 初め、列にボールはありません。
# 根気のある高橋君は、次の操作を 10100回繰り返します。
#     列の末尾に、A個の青いボールを加える。その後、列の末尾に B個の赤いボールを加える。
# こうしてできる列の先頭から N個のボールのうち、青いボールの個数はいくつでしょうか。

# 制約
#     1≤N≤1018
#     A,B≥0
#     0<A+B≤1018
#     入力は全て整数である

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N A B

# 出力
# 列の先頭から N個のボールのうち、青いボールの個数を出力せよ。

# 入力例 1
# 8 3 4

# 出力例 1
# 4

# 青いボールをb、赤いボールを rで表すと、列の先頭から 8個のボールは bbbrrrrb であるので、このうち青いボールは 4個です。

# 入力例 2
# 8 0 4

# 出力例 2
# 0

# そもそも赤いボールしか並んでいません。

# 入力例 3
# 6 2 4

# 出力例 3
# 2

# bbrrrr のうち青いボールは 2個です。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    N, A, B = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    q, mod = divmod(N, A+B)

    result = q*A + min(mod, A)

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['8 3 4']
        lines_export = [4]
    if pattern == 2:
        lines_input = ['8 0 4']
        lines_export = [0]
    if pattern == 3:
        lines_input = ['6 2 4']
        lines_export = [2]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9272
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    money = 0
    ans = 0
    for i in range(num):
        now_num = data[i]
        if money == 0:
            ans += now_num - 1
            money = 1
        else:
            if now_num > money + 1:
                kari = math.ceil((now_num - money - 1) / (money + 1))
                ans += kari
                now_num = money
            money = max(now_num, money)
        # print(money, ans)

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 50516
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;





int main(){

	ll N,K;
	scanf("%lld %lld",&N,&K);

	if(N == 0){

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

	ll tmp = N%K;
	if(tmp == 0){

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

	printf("%lld\n",min(tmp,abs(tmp-K)));

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
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; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };


int main(){cout<<fixed<<setprecision(10);
           int a,b;
		   cin>>a>>b;
           if(a+b<10)cout<<a+b<<endl;
           else cout<<"error"<<endl;
}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define N 100500
using namespace std;
int vis[N]= {0};
int team[10*N],c1,c2;
int dis[N]= {0};

int spfa(int x)
{
    for(int i=0; i<=x; i++)dis[i]=INT_MAX;
    c1=c2=0;

    for(int i=1; i<=9; i++)team[c2++]=i,dis[i]=i,vis[i]=1;

    while(c1<c2)
    {
        int now=team[c1];

        for(int i=0; i<=9; i++)
        {
            if(dis[(now*10+i)%x]>dis[now]+i)
            {

                dis[(now*10+i)%x]=dis[now]+i;

                if(!vis[(now*10+i)%x])
                {
                    team[c2++]=(now*10+i)%x;
                    vis[(now*10+i)%x]=1;
                }
            }
        }

        vis[now]=0;
        c1++;
    }
    return dis[0];
}

int main()
{
    int k;
    scanf("%d",&k);
    printf("%d\n",spfa(k));
    return 0;
}

Measured memory_bytes: 4992
import java.util.*;
public class Main {

	static int N,M;
	static int[] a, b;
	static boolean[] visited;
	
	public static int dfs(int x, boolean[] visited) {
		boolean ok = true;
		for(int i = 1; i <= N; i++)
			if(!visited[i])
				ok = false;
		if(ok)
			return 1;
		int ans = 0;
		visited[x] = true;
		for(int i = 0; i < M; i++) {
			if(a[i] == x) {
				if(visited[b[i]])
					continue;
				visited[b[i]] = true;
				ans += dfs(b[i], visited);
				visited[b[i]] = false;
			}
			if(b[i] == x) {
				if(visited[a[i]])
					continue;
				visited[a[i]] = true;
				ans += dfs(a[i], visited);
				visited[a[i]] = false;
			}
		}
		return ans;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		a = new int[M];
		b = new int[M];
		visited = new boolean[N+1];
		for(int i = 0; i < M; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}
		System.out.println(dfs(1,visited));
	}

}

Measured memory_bytes: 22100
S = input()
ans = 0
for i in range(1 << (len(S)-1)):
    eq = S
    k = 0
    for j in range(len(S)-1):
        if i & (1 << j):
            eq = eq[:j+1+k] + "," + eq[j+1+k:]
            k +=1
        else:
            pass
    eq = eq.split(",")
    eq = list(map(int,eq))
    ans += sum(eq)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int N;
  cin >> N;
  rep(i,N){
    string S;
    cin >> S;
    if(S=="Y"){
      cout << "Four" << endl;
      break;
    }
    if(i==N-1){
      cout << "Three" << endl;
    }
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int A,B;
  int ans = 0;
  scanf("%d %d",&A,&B);

  if(A < B){
    ans += B;
    B --;
  }else{
    ans += A;
    A --;
  }

  if(A < B){
    ans += B;
    B --;
  }else{
    ans += A;
    A --;
  }

  printf("%d",ans);

  return 0;
}


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

int main(void){

  int N, H; cin >> N >> H;
  vector<int> a(N), b(N);
  for(int i = 0; i < N; i++){
    cin >> a[i] >> b[i];
  }
  int amax = *max_element(a.begin(), a.end());
  sort(b.begin(), b.end(), greater<int>());
  int ans = 0;
  int idx = 0;
  while(b[idx] > amax){
    H -=b[idx];
    idx++;
    ans++;
    if(H <= 0) break;
    if(idx >= N) break;
  }

  if(H > 0){
    ans += H / amax;
    if(H % amax != 0) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
  int k, x, y;
  cin >> k >> x >> y;

  int flippedX = 0, flippedY = 0;
  if (x < 0)
  {
    x = -x;
    flippedX = 1;
  }
  if (y < 0)
  {
    y = -y;
    flippedY = 1;
  }

  if (x % 2 != y % 2 && k % 2 == 0)
  {
    cout << -1 << endl;
    return 0;
  }

  long long ans = (x + y + k - 1) / k;
  if (ans == 1 && x + y != k)
    ans++;
  if (ans * k % 2 != (x + y) % 2)
    ans++;

  cout << ans << '\n';
  long long curX = 0, curY = 0, neg = (ans * k - x - y) / 2;
  for (int i = 0; i < ans; i++)
  {
    if (neg >= k)
    {
      if (x - curX < y - curY) curX -= k;
      else curY -= k;
      neg -= k;
    }
    else if (neg)
    {
      if (x - curX < y - curY)
      {
        curX -= neg;
        curY += k - neg;
      }
      else
      {
        curY -= neg;
        curX += k - neg;
      }
      neg = 0;
    }
    else
    {
      long long dx = min(x - curX, k * 1LL);
      curX += dx;
      curY += k - dx;
    }
    cout << (flippedX ? -curX : curX) << ' ' << (flippedY ? -curY : curY) << '\n';
  }
  assert(curX == x && curY == y);
}


Measured memory_bytes: 2304
N,T=map(int,input().split())

ablist=[]
bsum=0
for _ in range(N):
  a,b=map(int,input().split())
  ablist.append((a,b))
  bsum+=b
ablist.sort()
  
dp=[[0]*T for _ in range(N+1)]
for i in range(1,N+1):
  a,b=ablist[i-1]
  for j in range(T):
    dp[i][j]=dp[i-1][j]
    if j-a>=0:
      dp[i][j]=max(dp[i][j],dp[i-1][j-a]+b)      
#print(dp[N])

if dp[N][T-1]==bsum:
  print(bsum)
else:
  answer=0
  for i in range(1,N+1):
    answer=max(answer,dp[i-1][T-1]+ablist[i-1][1])
  print(answer)

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

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


    int p;
    int ans = 0;


    for (int i = N-1; i >= 0; i--)
    {
        cin >> p;

        if(p != N-i){
            ans++;
        }
    }

    if(ans > 2){
        cout << "NO";
    } else {
        cout << "YES";
    }
    
}

Measured memory_bytes: 764
n = gets.chomp.to_i
if n % 2 !=0
  puts 0
elsif n == 0
  puts 0
else
  n1 = n/2
  count_5 = 0
  divisor = 5
  while  n1 >= divisor  do
    count_5 += n1/divisor
    divisor = 5*divisor
  end
  count_2 = 0
  divisor2 = 2
  while n1 >= divisor2 do
    count_2 += n1/divisor
    divisor2 = 2*divisor
  end
   count_2 += n/2
  if count_5 < count_2
  puts count_5
  else
  puts count_2
  end
end

Measured memory_bytes: 1788
<?php
$a = explode(" ", trim(fgets(STDIN)));
$max = max($a);
$sum = array_sum($a);

$tmp = $max * 3 - $sum;

if ($tmp % 2 === 0) {
	echo $tmp / 2 . PHP_EOL;
} else {
	echo ($tmp + 3) / 2 . PHP_EOL;
}


Measured memory_bytes: 4604
import sys
N=input()
A=list(map(int,input().split()))
ans=1
for i in range(len(A)):
  if A[i]==0:
    print(0)
    sys.exit()
for i in range(len(A)):
  ans=ans*A[i]
  if ans>10**18:
    print(-1)
    sys.exit()

print(ans)

Measured memory_bytes: 21632
import java.util.*;

class Main {
  public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  String s = sc.next();
  int c1Count = 0;
  int c2Count = 0;
  int c1 = 0;
  int c2 = 1;
  for (int i=0;i<s.length();i++){
    int x1 = Character.getNumericValue(s.charAt(i));
    if (x1 == c1){
      c2Count ++;
    }else
    {
      c1Count ++;
    }
    c1 = (c1 +1) % 2;
    c2 = (c2 +1) % 2;
  }
  System.out.println(Math.min(c1Count,c2Count));
  }
}

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

	int main() {
	#ifdef LOCAL_DEFINE
		// freopen("data.in", "rt", stdin);
		// freopen("data.out", "w", stdout);
		auto _start = chrono::high_resolution_clock::now();
	#endif

		ios::sync_with_stdio(false);
		cin.tie(0);
		cout << fixed << setprecision(15);
		string s, t;
		cin >> s >> t;
		int n = s.length(), m = t.length();
		vector<vector<int>> dp(n + 1, vector<int>(m + 1));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i] == t[j]) {
					dp[i + 1][j + 1] = dp[i][j] + 1;
				} else {
					dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
				}
			}
		}
		string ans;
		int i = n, j = m;
		while(dp[i][j]) {
			if(dp[i][j] == dp[i - 1][j]) i--;
			else if(dp[i][j] == dp[i][j - 1]) j--;
			else ans += s[i - 1], i--, j--;
		}
		reverse(ans.begin(), ans.end());
		cout << ans << '\n';

	#ifdef LOCAL_DEFINE
		auto _end = chrono::high_resolution_clock::now();
		cerr << "elapsed time: " << chrono::duration<double, milli>(_end - _start).count() << " ms\n";
	#endif
		return 0;
	}

Measured memory_bytes: 36864
#include <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  debug_out(t...);
}

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if(b==0)return 1;

  if ((a == 0)||(mod!=-1&&(a+mod)%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<long long, long long>;

ll gcd(ll a,ll b){
  if(a%b==0)return b;
  return gcd(b,a%b);
}

using namespace std;

vector<ll> list_mod_inverse(ll n, ll m)
{
    vector<ll> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = inv[m % i] * (m - m / i) % m;
    return inv;
}

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

  ll n,k;
  std::cin>>n>>k;

  std::vector<ll> a(n);
  rep(i,0,n){
    std::cin>>a[i];
  }

  std::sort(all(a));

  if(k==1){
    std::cout<<0<<"\n";
    return 0;
  }

  std::vector<ll> inv=list_mod_inverse(n+2,MOD);

  std::vector<ll> comb(n,1),sum(n,0),sum_inv(n,0);

  sum[0]=(a[0]+MOD)%MOD;sum_inv[n-1]=(a[n-1]+MOD)%MOD;
  rep(i,1,n)sum[i]=(sum[i-1]+a[i]+MOD)%MOD;
  for(ll i=n-2;i>=0;i--)sum_inv[i]=(sum_inv[i+1]+a[i]+MOD)%MOD;


  rep(i,k-1,n)comb[i]=((comb[i-1]*i%MOD)*inv[i-k+2])%MOD;


  ll ans=0;

  rep(i,k,n+1){
    ll temp=(sum_inv[i-1]-sum[n-i]+MOD)%MOD;
    temp=(temp*comb[i-2])%MOD;
    ans=(ans+temp)%MOD;
  }

  std::cout<<ans<<"\n";

  return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int dp[MAXN][MAXN];
int size[MAXN], f[MAXN];
vector <int> a[MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
void work(int pos, int fa) {
	dp[pos][1] = 1, size[pos] = 1;
	for (auto x : a[pos])
		if (x != fa) {
			work(x, pos);
			static int tmp[MAXN];
			memset(tmp, 0, sizeof(tmp));
			for (int i = 0; i <= size[pos]; i++)
			for (int j = 0; j <= size[x]; j++)
				update(tmp[i + j], 1ll * dp[pos][i] * dp[x][j] % P);
			memcpy(dp[pos], tmp, sizeof(tmp));
			size[pos] += size[x];
		}
	for (int i = 1; i <= size[pos]; i++)
		update(dp[pos][0], P - 1ll * dp[pos][i] * f[i] % P);
}
int main() {
	int n; read(n), f[0] = 1;
	for (int i = 2; i <= n; i += 2)
		f[i] = (i - 1ll) * f[i - 2] % P;
	for (int i = 1; i <= n - 1; i++) {
		int x, y; read(x), read(y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	work(1, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		update(ans, 1ll * dp[1][i] * f[i] % P);
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main()
{
    int N, M;
    vector<tuple<int,int,int>> a;
    cin >> N >> M;
    for(int i = 0; i < M; ++i) {
        int p, y;
        cin >> p >> y;
        a.push_back(make_tuple(y, p, i));
    }
    sort(a.begin(), a.end());
    int count[N+1] = {0};
    pair<int,int> res[M];
    for(int i = 0; i < M; ++i) {
        int p, y, index;
        tie(y, p, index) = a[i];
        count[p]++;
        res[index] = make_pair(p, count[p]);
    }
    for(int i = 0; i < M; ++i) {
        printf("%06d%06d\n", res[i].first, res[i].second);
    }
    return 0;
}

Measured memory_bytes: 3956
import collections
n = int(input())
d =list(int(i) for i in input().split())
m = int(input())
t =list(int(i) for i in input().split())
a = collections.deque(sorted(d))
b = collections.deque(sorted(t))


for i in range(n):
  if a[0] == b[0]:
    b.popleft()
  a.popleft()
  if len(b) == 0:
    print('YES')
    exit()
  elif len(a) == 0:
    break
print('NO')

Measured memory_bytes: 35408
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c) 
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;

int main(){
    ll n,m;
    cin >> n >> m;
    if(n==1 && m==1) cout << 1;
    else if(n==1 || m==1) cout << max(m,n)-2;
    else if(m==2 || n==2) cout << 0;
    else cout << (n-2)*(m-2);
}

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

int main()
{
    int n;
    cin >> n;
    ll a[n + 5];

    rep(i,n){
        cin >> a[i];
    }

    sort(a, a + n);

    rep(i,n-1){
        if(a[i]==a[i+1]){
            cout << "NO" << endl;

            return 0;
        }
    }

    cout << "YES" << endl;


    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define mp make_pair
#define S second
#define F first
ll mod=1e9+7;
#define input_from_file  freopen("input.txt", "r", stdin);

int main()
{
  // input_from_file;
  ll n,m,k,x;cin>>n>>k;
  vector<ll> vec(n+1,0);for(int i=1;i<=n;i++)  cin>>vec[i];
  vector<vector<ll>> dp(n+1,vector<ll>(k+1,0)),prefix(n+1,vector<ll>(k+1,0));
  for(int i=0;i<=n;i++)   {
    dp[i][0]=1;
}
  for(ll i=1;i<=n;i++){
    for(ll j=1;j<=k;j++){
      dp[i-1][j]+=dp[i-1][j-1];
      // if(i==1) dp[i][j]= j>vec[i-1]? 0: 1 ;
      if(j>vec[i])
        dp[i][j]=(dp[i-1][j]+mod-dp[i-1][j-vec[i]-1])%mod;
      else  
        dp[i][j]=dp[i-1][j]%mod; 
    }
  }
  cout<<dp[n][k]%mod;
  return 0;
}


Measured memory_bytes: 159088
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define mp make_pair
using namespace std;
#define int ll
string s,t;
int cnts[33],cntt[33];
int nxt[100005][30];
int ft[27];
int lt[27];
signed main(){
	ios_base::sync_with_stdio(false);
	cin>>s>>t;
	s=" "+s,t=" "+t;
	for(int i=1;i<s.size();++i)cnts[s[i]-'a']++;
	for(int i=1;i<t.size();++i)cntt[t[i]-'a']++;
	for(int i=0;i<26;++i)if(cntt[i]>0 and cnts[i]==0){
		cout<<-1<<endl;
		return 0;
	}
	memset(nxt,-1,sizeof(nxt));
	memset(ft,-1,sizeof(ft));
	for(int i=s.size()-1;~i;--i){
		lt[s[i]-'a']=i;
		for(int j=0;j<26;++j)nxt[i][j]=ft[j];
		if(i)ft[s[i]-'a']=i;
	}
	ll lst=0;
	ll ans=0;
	for(int i=1;i<t.size();++i){
		if(nxt[lst][t[i]-'a']==-1){
			ans+=(s.size()-1-lst+ft[t[i]-'a']);
			lst=ft[t[i]-'a'];
//			cerr<<i<<' '<<lst<<' '<<ans<<endl;
			continue;
		}
		ans+=(nxt[lst][t[i]-'a']-lst);
		lst=nxt[lst][t[i]-'a'];
//		cerr<<i<<' '<<lst<<' '<<ans<<endl;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 23864
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

ans = 10**10
for i in range(N):
    if i == 0:
        tmpa = A[N-1] - A[i]
    else:
        tmpa = K - (A[i]-A[i-1])

    if i == N-1:
        tmpb = A[i] - A[0]
    else:
        tmpb = K - (A[i+1]-A[i])

    if ans > min(tmpa, tmpb):
        ans = min(tmpa, tmpb)

print(ans)


Measured memory_bytes: 26444
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <bitset>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(void){
    ll n;
    cin >> n;
    ll a[n];
    ll INF = 1e+9+7;
    for(ll i = 0; i < n; i++)
        cin >> a[i];
    ll ans = 0;
    ll b = 1;
    for(ll d = 0; d < 60; d++){
        ll n1 = 0, n0 = 0;
        for(ll i = 0; i < n; i++){
            if(a[i]&((ll)1<<d)) n1++;
            else n0++;
        }
        ll c = ((ll)b << d)%INF;
        ll n = n0*n1%INF;
        ans = (ans+c*n)%INF;
        //cout << d << " " << n0 << " " << n1 << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_right().to_owned()
}

fn main() {
    let v: Vec<u64> = read_line().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (a, b) = (v[0], v[1]);
    let mut coins = vec![a, b, a - 1, b - 1];
    coins.sort_by(|a, b| b.partial_cmp(a).unwrap());
    println!("{}", coins[0] + coins[1]);
}


Measured memory_bytes: 4352
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.io.PrintWriter;

@SuppressWarnings("unchecked")
public class Main {
    public static void main(String[] args) throws IOException {
        final String S;

        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            S = reader.readLine();
        }

        PrintWriter out = new PrintWriter(System.out);

        char a = S.charAt(0);
        char b = a;

        int ans = 0;

        for (int i = 0; i < S.length(); i++) {
            if (b != S.charAt(i)) ans++;
            b = S.charAt(i);
        }

        out.println(ans);

        out.flush();
    }
}


Measured memory_bytes: 24916
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
 
using namespace std;
 
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
 
typedef vector<int> vi;
typedef pair<int,int> pii;
 
int main(void) {
  int i,j;
  int a,b;
  string s;
  cin>>a>>b;
  if(a%3==0||b%3==0||(a+b)%3==0)cout<<"Possible"<<endl;
  else cout<<"Impossible"<<endl;
}


Measured memory_bytes: 256
class Main {

	public static void main(String[] a) {
		// ??????????????°
		int tate=1;		//????????°
		int yoko;		//?¨??????°
		int kotae;

		//?¨????
		for(tate=1; tate<=9; tate++){
			yoko=1;
			for(yoko=1; yoko<=9; yoko++){
				kotae = tate * yoko;
				System.out.println(tate + "x" + yoko + "=" + kotae);
			}

		}

	}

}

Measured memory_bytes: 24152
using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        long[] nk = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long n = nk[0];
        long k = nk[1];
        int[][] ab = new int[n][];
        for(int i = 0; i < n; i ++) ab[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Array.Sort(ab, (x,y) => x[0]-y[0]);
        long count = 0;
        long ans = 0;
        for(int i = 0; i < n; i ++) {
            count += ab[i][1];
            if(count >= k) {
                ans = ab[i][0];
                break;
            }
        }
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 23868
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

int main(){
	for(int n;scanf("%d",&n),n;){
		ll len=0;
		rep(i,n){ int a; scanf("%d",&a); len+=a; }

		static int joint[64999];
		rep(i,n-1) scanf("%d",joint+i);

		sort(joint,joint+n-1);

		ll ans=0;
		rep(i,n){
			ans=max(ans,(n-i)*len);
			if(i<n-1) len+=joint[n-i-2];
		}
		printf("%lld\n",ans);
	}

	return 0;
}

Measured memory_bytes: 1296
N = int(input())
cnt = [[0] * 10 for i in range(10)]
for n in range(1, N + 1):
    cnt[int(str(n)[0])][int(str(n)[-1])] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += cnt[i][j] * cnt[j][i]

print(ans)

Measured memory_bytes: 40428
li = [2,3,4,5,6,7,8,9,10,11,12,13,1]
a,b = map(int,input().split())
if li.index(a) == li.index(b):
    print("Draw")
elif li.index(a) > li.index(b):
    print("Alice")
else:
    print("Bob")

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

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

    int m=n%10;
    if(m==2||m==4||m==5||m==7||m==9) ans="hon";
    else if(m==0||m==1||m==6||m==8) ans="pon";
    else ans="bon";

    cout<<ans<<endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n;
  cin >> n;
  int a[n];
  int ans[n];
  rep(i,n){
    cin>>a[i];
    ans[a[i]-1]=i+1;
  }
  rep(i,n){
    cout << ans[i] << endl;
  }
  
}


Measured memory_bytes: 1536
import Data.Ord
import Data.List

main = interact $ unlines . map (show . amida) . read' . lines
 where
  read' ("0 0 0":_) = []
  read' (x:xs) = (a,hpqs) : read' xs'
   where
    [n,m,a] = map read (words x)
    (hpqs', xs') = splitAt m xs
    hpqs = map ((\[h,p,q]->(h,(p,q))) . map read . words) hpqs'

amida (a,hpqs) = election a ((reverse . sortBy (comparing fst)) hpqs)
 where
  election a' [] = a'
  election a' ((h,(p,q)):hpqs)
   | p == a' = election q (dropWhile ((==h) . fst) hpqs)
   | q == a' = election p (dropWhile ((==h) . fst) hpqs)
   | otherwise = election a' hpqs

Measured memory_bytes: 5792
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

/*
0-index
functionの中を書いて使う
segtree<ll> seg(n, [](ll a, ll b){return a + b;}, 0);
*/
template<typename T>
struct segtree{
	int n;
	vector<T> dat;
	T ZERO;
	function<T(T,T)> func;//要素と要素をマージする関数

	segtree(int n_, function<T(T,T)> func_, T zero):func(func_), ZERO(zero){
	  n = 1;
	  while(n < n_)n*=2;
	  dat.resize(2*n);
	  for(int i = 0;i < 2*n;i++)dat[i] = ZERO;
	}

	void update(int k, T a){
	  k += n - 1;dat[k] = a;
	  while(k > 0){
		k = (k-1)/2;
		dat[k] = func(dat[k*2+1],dat[k*2+2]);
	  }
	}

	void set(int k, T a) {
		k += n - 1;dat[k] = a;
	}

	void build(){
		for(int i = n - 2;i >= 0;i--){
			dat[i] = func(dat[2 * i + 1], dat[2 * i + 2]);
		}
	}

	T get(int k){return dat[k+n-1];}

	T que(int a,int b){
		T L = ZERO,R = ZERO;
		int A = a + n - 1;
		int B = b + n - 1;
		while(A < B){
			if((A & 1) == 0)L = func(L,dat[A++]);
            if((B & 1) == 0)R = func(dat[--B],R);
            A = A >> 1;
            B = B >> 1;
		}
		return func(L,R);
	}
};

//ａをbで割る
long long mod_div(long long a,long long b){
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}

#define MAX_K 333333
vector<long long> fact(MAX_K);
long long combination(long long n, long long r){
    if(n < r || n < 0 || r < 0)
        return 0;
	if(fact[0] != 1){
		fact[0] = 1;
		for(long long i = 1;i < MAX_K;i++)fact[i] = (fact[i-1] * i) % MOD;
	}
    long long ret = fact[n];
	long long tmp = (fact[r] * fact[n-r]) % MOD;
    return mod_div(ret,tmp);
}

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

	ll n, k;cin >> n >> k;
	segtree<ll> seg_a(n + 2, [](ll a, ll b){return (a + b) % MOD;}, 0);
	segtree<ll> seg_b(n + 2, [](ll a, ll b){return (a + b) % MOD;}, 0);
	ll ans = 0;
	ll seica = mod_div(1, 2);
	ll base = 1;

	REP(i, n) {
		ll a; cin >> a;
		if(i >= k)base = base * mod_div(k - 1, k) % MOD;
		ans = (ans + seg_a.que(0, a) * base % MOD) % MOD;
		ans = (ans + seg_b.que(a + 1, n + 1) * 1 - seg_a.que(a + 1, n + 1) * base % MOD + MOD) % MOD;
		seg_a.update(a, seica * mod_div(1, base) % MOD);
		seg_b.update(a, 1);
		//REP(j, n+1)cout << seg_a.que(j, j+1) << " ";cout << endl;
	}

	cout << ans << endl;

	return 0;
}


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

int arr[200005];


signed main() {
  int n;
  cin >> n;
  for(int i = 0; i < n;i++) {
    cin >> arr[i];
  }
 int res = INT_MAX;
  for(int i = 1; i < n;i++) arr[i] += arr[i-1];
  for(int i = 0; i < n; i++) {
    int ilk = arr[i];
    int iki = arr[n-1] - arr[i];
    res = min(res, abs(iki-ilk));
  }
  cout << res << endl;


}


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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

const ll MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1.0);
const db ERR = 1e-8;
const int MAXN = 1e7;

struct node{
    ll a,b;
}d[MAX_SIZE];


int main(int argc, char const *argv[]){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    ll ans=0;
    ll t=INF;
    ll m=0;
    //vector<ll> eq; 
    bool flag=1;
    for(int i=0;i<n;i++){
        cin>>d[i].a>>d[i].b;
        // cout<<d[i].a<<" "<<d[i].b<<endl;;
        m+=d[i].a;
        if(d[i].a!=d[i].b){
            flag=0;
        }
    
        if(d[i].a>d[i].b){
            t=min(t,d[i].b);
            // cout<<t<<endl;
        }
    }   
    
    if(flag){
        cout<<0<<endl;
        return 0;
    }
    // cout<<m<<endl;
    ans=m;
    if(t!=INF){
        ans-=t;
    }

    cout<<ans<<endl;


    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define ll long long
#define rep(i,a) for(ll i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>

int n,m;
int tmp[111111];
int a[111111],b[111111],c[111111];
int t[111111];


struct unionFind{
	int n;
	vector<int>par;
	vector<int>rank;
	vector<int>size;//size[i]=親がiの要素のサイズ
	unionFind(int x){
		n=x;
		par.resize(x);
		rank.resize(x);
		size.resize(x);
		rep(i,n){
			par[i]=i;
			rank[i]=0;
			size[i]=1;
		}
	}
	
	int find(int x){
		if(par[x]==x)return x;
		else return par[x]=find(par[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	
	void unite(int x,int y){//x,yを併合
		x=find(x);
		y=find(y);
		if(x==y)return;
 
		if(rank[x]<rank[y]){
			size[y]+=size[x];
			par[x]=par[y];//yにxをつける
		}	
		else{
			size[x]+=size[y];
			par[y]=x;
			if(rank[x]==rank[y])rank[x]++;//xにyをつける
		}
	}
 
	int getSize(int i){return size[find(i)];}
};
 

int main(){
  cin>>n>>m;
  unionFind u(111111);

  rep(i,m){
    int ta,tb,tc;
    cin>>ta>>tb>>tc;
    ta--;tb--;tc--;

    a[i]=ta,b[i]=tb,c[i]=tb;
    u.unite(ta,tb);
  }

  rep(i,n)t[u.find(i)]++;
  int ans=0;
  rep(i,n)if(t[i]>0)ans++;
  cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define INF 1e9
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long l, r;
    cin>>l>>r;

    /*
    for(int i = 1; i <= 2019; i++){
        for(int j = 1; j <= 2019; j++){
            l*
        }
    }
    */

    long long ans = 2019;
    if(r/2019 > l/2019){
        ans= 0;
    }else{
        for(long long i=l;i<r;i++){
            for(long long j=l+1;j<=r;j++){
                ans = min(ans,(i*j)%2019);
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);
		int n=Integer.parseInt(scan.next());
		double[][] xy=new double[n][2];		
		for (int i=0;i<n;++i) {
			xy[i][0]=Double.parseDouble(scan.next());
			xy[i][1]=Double.parseDouble(scan.next());
		}
	
		double sum=0;
		for (int i=0;i<n;++i) {
			for(int k=0;k<n;++k) {
				if(k==i) continue;
				sum+=Math.sqrt(Math.pow(xy[i][0]-xy[k][0],2)+Math.pow(xy[i][1]-xy[k][1],2));
			}
		}
		
		System.out.print(sum/n);
		
		
}		
}
//end

Measured memory_bytes: 23636
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
 
using namespace std;

#define mod 1000000007
#define maxnum 1000000000

int main()
{
    int n;
    cin >> n;
    int p[20010];
    for(int i = 1; i <= n; i++){
        int tmp;
        cin >> tmp;
        p[tmp] = i;
    }
    for(int i = 1; i <= n; i++){
        cout << i * n + n + p[i];
        if(i != n) cout << " ";
    }
    cout << endl;
    for(int i = 1; i <= n; i++){
        cout << (n - i + 1) * n;
        if(i != n) cout << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 640
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define int unsigned long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

#define i1e18 1000000000000000000

void MAIN() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto &i : a) cin >> i;
  sort(all(a));
  if (a[0] == 0) {
    cout << 0 << '\n';
    return;
  }
  int ans = 1;
  for (auto &t : a) {
    if (ans <= i1e18 / t) {
      ans *= t;
      if (ans > i1e18) {
        cout << -1 << '\n';
        return;
      }
    } else {
      cout << -1 << '\n';
      return;
    }
  }
  cout << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3992
n=int(input())
s=input()
l=set()
r=set()

for i in range(0,n-2):
    a=set()
    if s[i] in r:
        continue
    else:
        r.add(s[i])
    for j in range(i+1,n-1):
        b=set()
        if s[j] in a:
            continue
        else:
            a.add(s[j])
        for k in range(j+1,n):
            if s[k] in b:
                continue
            else:
                b.add(s[k])
            m=s[i]+s[j]+s[k]
            l.add(m)
print(len(l))


Measured memory_bytes: 3188
h,w,n = map(int, input().split())
grid = {}
count = {i:0 for i in range(10)}
for _ in range(n):
    a,b = map(int, input().split())
    for dx in range(-1,2):
        for dy in range(-1,2):
            x,y = b+dx,a+dy
            if not (2 <= y <= h-1) or not (2 <= x <= w-1):
                continue
            if (y,x) not in grid:
                grid[(y,x)] = 0
            grid[(y,x)] += 1

from collections import Counter
c = Counter(grid.values())

print((h-2)*(w-2) - sum(c.values()))
for i in range(1,10):
    print(c.get(i,0))


Measured memory_bytes: 166724
#include <iostream>

using namespace std;

int main(){
  int n, d;
  cin >> n >> d;
  int ans = n / (2 * d + 1);
  if( n % (2 * d + 1) > 0  ) cout << n / (2 * d + 1) + 1;
  else cout << n / (2 * d + 1);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int tate[30], w, n, a, b;
    char comma;
    for(int i=0;i<30;i++) tate[i]=i+1;
    
    cin >> w;
    cin >> n;
    
    for(int i=0;i<n;i++){
        cin >> a >> comma >> b;
        swap(tate[a-1],tate[b-1]);
    }
    
    for(int i=0;i<w;i++){
        cout << tate[i] << endl;
    }
    return 0;
}

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

int main(){
    int N;
    cin>>N;
    int x[N];
    for(int i=0;i<N;++i)cin>>x[i];
    for(int i=0;i<N-1;++i)cout<<x[N-1-i]<<" ";
    cout<<x[0];
    cout<<endl;
}


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

vector<int> hs;
int n, k;
int main() {
 	cin >> n >> k;
  	hs.resize(n, 0);
  	for (int i = 0; i < n; i++) cin >> hs[i];
  	sort(hs.begin(), hs.end());
  	int ans = hs[k - 1] - hs[0];
  	for (int i = k - 1; i < n; i++) ans = min(ans, hs[i] - hs[i - k + 1]);
  	cout << ans << endl;
}

Measured memory_bytes: 640
<?php

list($n, $m) = explode(' ', trim(fgets(STDIN)));

$l = 1;
$r = $n;
for($i=0; $i<$m; $i++){
  $t = explode(' ', trim(fgets(STDIN)));
  if ($l < $t[0]) $l = $t[0];
  if ($r > $t[1]) $r = $t[1];
}

echo $r-$l+1 >= 0? $r-$l+1 : 0;


?>

Measured memory_bytes: 4604
#abc140b

n=int(raw_input())
a=map(int,raw_input().split())
b=map(int,raw_input().split())
c=map(int,raw_input().split())
res=sum(b)
for i in xrange(n-1):
 if a[i+1]==a[i]+1:
  res+=c[a[i]-1]
print res


Measured memory_bytes: 2568
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int func(long long a, long long b){
    int cnta=0, cntb=0;
    while(a>0){
        a/=10;cnta++;
    }
    while(b>0){
        b/=10;cntb++;
    }
    return max(cnta, cntb);
}
int main(void){
    long long n;cin>>n;
    int min=11;
    long long rn = (long long)sqrt(n);
    for(long long i=1;i<=rn;i++){
        if(n%i==0){
        int f=func(i, n/i);
        if(min>f)min=f;
        }
    }
    cout<<min<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
//DP用
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;
}
const long long INF = 1LL << 60;

int count(int i,int c) {
    if(i % c == 0) {
        return i/c;
    }else {
        return i/c+1;
    }
}

int main() {
    int a,b;
    cin >> a >> b;
    if(a >= 1 && a <= 9 && b >= 1 && b <= 9) {
        cout << a*b;
        return 0;
    }
    cout << -1;
    return 0;
}



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

int main()
{
    int N;
    long long a, b;

    cin >> N;

    cin >> a >> b;

    for(int i = 0; i < N - 1; i++) {
        int T, A;
        cin >> T >> A;

        a = ((a - 1) / T + 1) * T;
        b = ((b - 1) / A + 1) * A;

        if(b <= A * (a / T)) b = A * (a / T);
        if(a <= T * (b / A)) a = T * (b / A);
    }

    cout << a + b << endl;

    return (0);
}


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

namespace ForAtcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            long a = long.Parse(Console.ReadLine());
            Console.WriteLine(a + Math.Pow(a, 2) + Math.Pow(a, 3));
        }
    }
}

Measured memory_bytes: 27844
#include <math.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define PI 3.14159265358979323846264338327950L
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int H_1, M_1, H_2, M_2, K;
  cin >> H_1 >> M_1 >> H_2 >> M_2 >> K;

  int ans = H_2 * 60 + M_2 - (H_1 * 60 + M_1) - K;

  cout << ans << endl;
}


Measured memory_bytes: 3624
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int A=sc.nextInt();
		int B=sc.nextInt();
		int rs1=N*A;
		if(rs1<B){
			System.out.println(rs1);
		}
		else if(rs1>B){
			System.out.println(B);
		}
		else if(rs1==B){
			System.out.println(B);
		}
	}

}

Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000],arr1[1000000];
map <long long, long long > cnt;
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    
    long long n,a,b,k,i,j,x,y;
    cin>>n>>a>>b;
    for (i=0;i<n;i++)
    {
    	cin>>arr[i];
	}
	y=0;
	for (i=1;i<n;i++)
	{
		x=(arr[i]-arr[i-1])*a;
		y=y+min(x,b);
	}
	cout<<y<<endl;
}

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

using ll = long long;
using namespace std;
constexpr ll inf = 1e9;
constexpr ll mod = 1e9+7;

struct Edge {
    int to;
    int cap;
    int rev;
};
vector<Edge> edges[11001];
bool used[11001] = {false};

int dfs(int v, int t, int f) {
    if (v == t) return f;
    used[v] = true;
    for (auto&& edge : edges[v]) {
        if (used[edge.to] || edge.cap <= 0) continue;
        int d = dfs(edge.to, t, min(f, edge.cap));
        if (d > 0) {
            edge.cap -= d;
            edges[edge.to][edge.rev].cap += d;
            return d;
        }
    }
    return 0;
}

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

    int X, Y, E;
    cin>>X>>Y>>E;
    for (int e = 0; e < E; e++) {
        int x, y;
        cin>>x>>y;
        x++; y += X+1;
        edges[x].push_back(Edge{y, 1, (int)edges[y].size()});
        edges[y].push_back(Edge{x, 0, (int)edges[x].size()-1});
    }

    for (int x = 1; x <= X; x++) {
        edges[0].push_back(Edge{x, 1, (int)edges[x].size()});
        edges[x].push_back(Edge{0, 0, (int)edges[0].size()-1});
    }
    for (int y = X+1; y < X+Y+1; y++) {
        edges[y].push_back(Edge{X+Y+1, 1, (int)edges[X+Y+1].size()});
        edges[X+Y+1].push_back(Edge{y, 0, (int)edges[y].size()-1});
    }

    int flow = 0;
    while (1) {
        fill(begin(used), end(used), false);
        int f = dfs(0, X+Y+1, inf);
        if (f == 0) break;
        flow += f;
    }
    cout<<flow<<endl;

    return 0;
}



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

const int maxn = 200 * 1000 + 20;
long long n, m, q;
bool vis[maxn];
long long num[maxn], ans[maxn];
vector <long long> adj[maxn];

void input() {
    cin >> n >> q;
    for (int i = 0, a, b; i < n - 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0, a, b; i < q; i++) {
        cin >> a >> b;
        num[a] += b;
    }
}

void dfs (int v, long long x) {
    vis[v] = 1;
    x += num[v];
    ans[v] = x;
    for (int u : adj[v]) 
        if (!vis[u]) 
            dfs(u, x);
}
void output() {
    for (int i = 1; i <= n; i++) 
        cout << ans[i] << ' ';
}
int main() {
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    input();
    dfs(1, 0);
    output();
    return 0;
}

Measured memory_bytes: 22656