akhauriyash/Code-Regression huggingface dataset:
require 'pp'
require 'set'
N = gets.chomp.to_i

edges = Array.new(N) { Set.new }

(N-1).times do |i|
  a, b = gets.chomp.split(" ").map(&:to_i)
  a -= 1
  b -= 1
  s = edges[a]
  s << b
  edges[a] = s

  s = edges[b]
  s << a
  edges[b] = s
end

def depth(s, i, edges)
  s = s.dup
  s << i
  nodes = edges[i]
  depth_list = []
  nodes.each do |j|
    next if s.include?(j)
    depth_list << depth(s, j, edges)
  end
  if depth_list.empty?
    1
  else
    depth_list.max + 1
  end
end


min_nodes = Set.new
min_depth = N
N.times do |i|
  s = Set.new
  s << i

  d = depth(s, i, edges)
  if min_depth > d
    min_nodes = Set.new
    min_nodes << i
    min_depth = d
  elsif min_depth == d
    min_nodes << i
  end
  # pp [i, d]
end

# pp min_depth
# pp min_nodes.to_a

min_color_count = N
min_leaf_count = 10 ** 10

def child_count(s, i, edges, depth_count_max, depth)
  s = s.dup
  s << i
  nodes = edges[i]
  nodes = nodes - s
  size = nodes.size
  depth_count_max[depth] = size if depth_count_max[depth] < size
  nodes.each do |j|
    child_count(s, j, edges, depth_count_max, depth + 1)
  end
end

min_nodes.each do |i|
  depth_count_max = Array.new(min_depth, 1)
  depth_count_max[0] = 0
  s = Set.new
  s << i
  child_count(s, i, edges, depth_count_max, 0)
  # pp i
  # pp edges
  # pp depth_count_max

  leaf_count = depth_count_max.reduce(:*)
  color_count = min_depth

  if min_leaf_count > leaf_count
    min_leaf_count = leaf_count
    min_color_count = color_count
  end

  ##

  s = Set.new
  s << i
  nodes = edges[i]
  nodes.each do |j|
    depth_count_max = Array.new(min_depth, 1)
    s2 = s.dup
    s2 << j
    child_count(s2, i, edges, depth_count_max, 0)
    child_count(s2, j, edges, depth_count_max, 0)
    leaf_count = depth_count_max.reduce(:*) * 2
    d1 = depth(s2, i, edges)
    d2 = depth(s2, j, edges)
    color_count = [d1, d2].max

    if min_color_count > color_count
      min_leaf_count = leaf_count
      min_color_count = color_count
    elsif min_color_count == color_count && min_leaf_count > leaf_count
      min_leaf_count = leaf_count
      min_color_count = color_count
    end

  end


end


puts "#{min_color_count} #{min_leaf_count}"


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

ll pow_(ll e,ll x){
	if(x==0)return 1;
	ll res = pow_(e,x/2);
	res *= res;
	if(x&1)res *= e;
	return res;
}

int main(){
	ll n,m;
	cin >> n >> m;
	cout << (1900*m + (n-m)*100 ) * pow_(2,m) << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.*;

public class Main {

  // // 最大公約数
  // public static long gcd (long m,long n) {
  //   if (m < n) return gcd(n,m);
  //   if (n == 0) return m;
  //   return gcd(n,m%n);
  // }
  //
  // // 最小公倍数
  // public static long lcm (long m,long n) {
  //   return m*n/gcd(m,n);
  // }
  //
  // // 素数判定
  // public static boolean isPrime (long n) {
  //   if (n == 2) return true;
  //   if (n < 2 || n%2 == 0) return false;
  //   double d = Math.sqrt(n);
  //   for (int i = 3; i <= d; i+=2) {
  //     if (n%i == 0) {
  //       return false;
  //     }
  //   }
  //   return true;
  // }
  //
  // public static final long gcd3(long[] param) {
  //   int len = param.length;
  //   long g = gcd(param[0], param[1]);    //gcd(a, b) は以前作ったもの
  //   for (int i = 1; i < len - 1; i++) {
  //       g = gcd(g, param[i + 1]);       //gcd(a, b) は以前作ったもの
  //   }
  //   return g;
  // }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();

    int c0 = 0;
    int c1 = 0;

    for (int i = 0; i < s.length(); i++) {
      if (s.substring(i,i+1).equals("0")) {
        c0++;
      } else {
        c1++;
      }
    }

    System.out.println(2*Math.min(c0,c1));
  }

}


Measured memory_bytes: 30416
#include<stdio.h>

int main()
{
	int n, T, c, t, min = 2000;
	scanf("%d%d", &n, &T);

	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d", &c, &t);
		if (t <= T && c < min)
			min = c;
	}
	if (min == 2000)
		printf("TLE\n");
	else
		printf("%d\n", min);

	return 0;
}

Measured memory_bytes: 128
use std::io::*;
use std::str::FromStr;

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

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let a = read::<i64>();
  let b = read::<i64>();
  let c = read::<i64>();
  let d = read::<i64>();

  if a < c {
    println!("{}", max(0, min(b - c, d - c)));
  }

  if c < a {
    println!("{}", max(0, min(d - a, b - a)));
  }

  if c == a {
    println!("{}", min(d - c, b - c));
  }
}



Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f;
int main()
{
    int n,minn=inf;
    int a[105];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=1;i<=100;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            sum+=(i-a[j])*(i-a[j]);
        }
        minn=min(sum,minn);
    }
    cout<<minn;
	return 0;
}


Measured memory_bytes: 256
"use strict";
function Main(input) {
    let lines = input.split("\n");
    let N = lines.shift() - 0;
    let abc = new Array(N+1);
    for (let n = 0; n < N; n++) {
        abc[n] = lines.shift().split(/\s/).map((v) => v - 0);
    }
    let dp = new Array(N + 1).fill(0).map((v) => [0, 0, 0]);
    for (let n = 0; n < N; n++)
        for (let j = 0; j < 3; j++)
            for (let k = 0; k < 3; k++)
                if (k != j) dp[n + 1][k] = Math.max(dp[n + 1][k], dp[n][j] + abc[n][k]);
    console.log(Math.max(...dp[N]));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 57532
A, B, M = map(int, input().split(' '))
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
min = 10000000
for i in range(M):
    x, y, c = map(int, input().split(' '))
    price = a[x - 1] + b[y - 1] - c
    if price < min:
        min = price
minA = minB = 1000000
for e in a:
    if e < minA:
        minA = e
for e in b:
    if e < minB:
        minB = e

if minA + minB < min:
    print(minA + minB)
else:
    print(min)

Measured memory_bytes: 18200
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  string s,ans = "";
  cin >> s;
  rep(i,0,s.size()){
    if(s[i]=='0') ans += '0';
    if(s[i]=='1') ans += '1';
    if(s[i]=='B') {
      if(ans.size()==0) continue;
      else ans.pop_back();
    }
  }
  cout << ans << endl;
}


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


int main()
{
	int N, X, num, count =0;
	vector<int> m;

	cin >> N >> X;
	for (int i = 0;i<N; ++i) {
		cin >> num;
		m.push_back(num);
	}

	sort(m.begin(), m.end());
	for (int i = 0;i<m.size(); ++i) {
		X -= m[i];
		++count;
	}
	for (int i = 0;X >= m[0]; ++i) {
		X -= m[0];
		++count;
	}
	
	cout << count << endl;


	return 0;
}

Measured memory_bytes: 256
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <math.h>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define MAXN 100005
# define eps 1e-5
# define MAXM 500001
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
typedef long long LL;
typedef unsigned long long ULL;
int _MAX(int a, int b){return a>b?a:b;}
int _MIN(int a, int b){return a>b?b:a;}

LL a[1005][3];
double dis[1005][1005];

double dist(LL x1, LL y1, LL x2, LL y2)
{
    LL x = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
    return sqrt(x);
}
int main ()
{
    int sx, sy, tx, ty, n;
    scanf("%d%d%d%d%d",&sx,&sy,&tx,&ty,&n);
    FOR(i,1,n) scanf("%lld%lld%lld",&a[i][0],&a[i][1],&a[i][2]);
    a[0][0]=sx, a[0][1]=sy, a[n+1][0]=tx, a[n+1][1]=ty;
    FOR(i,0,n+1) FOR(j,i+1,n+1){
        double dd = dist(a[j][0],a[j][1],a[i][0],a[i][1])-a[i][2]-a[j][2];
        if (dd<0) dd=0;
        dis[i][j]=dis[j][i]=dd;
    }
  //  FOR(i,0,n+1){ FOR(j,0,n+1) printf("%.2lf\n",dis[i][j]); putchar('\n');}
    FOR(k,0,n+1) {
        FOR(i,0,n+1) {
            if (dis[i][k]>dis[0][n+1]) continue;
            FOR(j,0,n+1) {
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
            }
        }
    }
    printf("%.10lf\n",dis[0][n+1]);
    return 0;
}


Measured memory_bytes: 8192
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,d;
    cin>>n>>d;
    float a[n][d];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<d;j++)
        {
            cin>>a[i][j];
        }
        cout<<"\n";
    }
    int c=0;
    float sum=0;
    int x;
    for(int k=0;k<n;k++)
    {
        for(int i=k+1;i<n;i++)
        {
            sum=0;
            for(int j=0;j<d;j++)
            {
                sum=sum+abs(a[i][j]-a[k][j])*abs(a[i][j]-a[k][j]);
            }
            sum=sqrt(sum);
            x=(int)sum;
            if(x==sum)
            {
                c++;
            }
        }
    }
    cout<<c<<"\n";
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = 0
 
for i in range(n):
  if a[i] >= b[i]:
    c += b[i]
  else:
    c += a[i]
    c += min(a[i+1],b[i]-a[i])
    if a[i+1] >= b[i]-a[i]:
      a[i+1] = a[i+1] - (b[i] - a[i])
    else:
      a[i+1] = 0
     
print(c)

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

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

    std::vector<std::vector<pair<int, int>>> mention(N);
    for(int i = 0;i < N;i++){
        int A;
        cin >> A;
        for(int j = 0;j < A;j++){
            int x, y;
            cin >> x >> y;
            mention[i].push_back(pair<int, int>(x-1, y));
        }
    }

    // cout << N << endl;
    int ans = 0;
    for(int i = 0;i < pow(2, N);i++){
        // cout << i << endl;
        int t = i;
        std::vector<int> tt(N);
        int honN = 0;

        for(int j = 0;j < N;j++){
            tt[j] = t % 2;
            honN += t % 2;
            t /= 2;
        }
        // cout << honN << endl;

        bool ok = true;

        for(int j = 0;j < N;j++){
            if(tt[j] == 0) continue;
            for(auto&& men : mention[j]){
                if(tt[men.first] == men.second){

                }else{
                    ok = false;
                    break;
                }
            }
            if(!ok) break;
        }
        if(ok){
            ans = max(ans, honN);
            // cout << i << endl;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# 3 本の柱が等間隔に並んでいます。柱の高さは左から順に a メートル, b メートル, c メートル です。
# 柱の先端が同一直線上に並んでいる時、つまり b − a = c − b を満たしているとき、 この柱の並び方を美しいと呼びます。
# 柱の並び方が美しいかどうかを判定してください。

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

if b - a == c - b:
    print('YES')

else:
    print('NO')

Measured memory_bytes: 9160
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int n, m; cin >> n >> m;
  vector<pair<ll, ll>> v(n), t(m);
  rep(i, n) cin >> v[i].first >> v[i].second;
  rep(i, m) cin >> t[i].first >> t[i].second;
  rep(i, n){
    ll x = v[i].first, y = v[i].second;
    ll d = 1e10; int ans = 0;
    rep(j, m){
      ll k = abs(x-t[j].first)+abs(y-t[j].second);
      if(d > k){
        d = k;
        ans = j+1;
      }
    }
    cout << ans << endl;
  }
  system("pause");
}


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

typedef long long ll;
typedef unsigned long long ull;
#define endl "\n";
#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define POSITIVE_INFINITY 9223372036854775807
#define NEGATIVE_INFINITY -9223372036854775807
const ll MOD = 1000000007;

int main()
{
  FASTER;
  int n;
  cin >> n;
  ll gg = 0;
  for (int i = 0; i < n; i++){
    ll x;
    cin >> x;
    if (x != 0)
      gg = __gcd(gg, x);
  }
  cout << gg << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
public static void main(String[] a){
Scanner s=new Scanner(System.in);
int i,sum=0,d;
while(s.hasNext()){
d=s.nextInt();
for(i=1;d*i<600;i++){
sum+=(int)Math.pow(d*i, 2)*d;
}
System.out.println(sum);
sum=0;
}
}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define forn(i, a, b) for (int i=a; i<(signed)(b); ++i)
#define pb push_back
 
 
// debug templates 
#define debug(x)       cerr<< #x <<" : "<< x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[0].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";
 
// a number xor'd with itself is 0 
void solve(){
	int n; cin >> n;
	int a[n];
	forn(i,0,n) cin >> a[i];
	int xor_prod = 0;
	forn(i,0,n){
		xor_prod ^= a[i];
	}
	forn(i,0,n){
		cout << (xor_prod^a[i]) <<  " ";
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	solve();
	return 0;
}
 


Measured memory_bytes: 4344
#include <stdio.h>
#include <string.h>

int main(int argc, const char* argv[])
{
	char inputN[10];
	scanf("%s", &inputN);

	long len = strlen(inputN);
	int hasSeven = 0;

	for (int i = 0; i < len; i++)
	{
		if (inputN[i] == '7')
		{
			hasSeven = 1;
			break;
		}
	}

	if (hasSeven == 1)
	{
		printf("Yes \n");
	}
	else
	{
		printf("No \n");
	}

	return 0;
}


Measured memory_bytes: 1664
/* 
 * Project: AtCoder Beginners Contest 169 A - Multiplication 1
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/05/31
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <cmath>
using namespace std;

int a, b;

void solve() {
    printf("%d\n", a*b);

}

int main() {

    scanf("%d", &a);
    scanf("%d", &b);

    solve();

}

Measured memory_bytes: 3196
import java.util.Scanner;
public class Main {
	public static void main(String[] args){

//	入力の読み込み
		Scanner sc = new Scanner(System.in);
		int natsuyasumi = sc.nextInt();
		int shukudai = sc.nextInt();

//	宿題の数分、宿題やる日を夏休みから引く
		for(int i=0 ; i<shukudai ; i++) {
			int bangou = sc.nextInt();
			natsuyasumi -= bangou;
		}

//	遊べる日数が0日以上かどうか判断
		if(natsuyasumi>=0) {
			System.out.print(natsuyasumi);
		}
		else {
			System.out.print(-1);
		}
	}
}


Measured memory_bytes: 39040
#include <iostream>

int main()
{
	int a, b;
	char op;

	while (std::cin >> a >> op >> b) {
		if (op == '?') {
			break;
		}
		switch (op) {
		case'+':
			std::cout << a + b << std::endl;
			break;
		case'-':
			std::cout << a - b << std::endl;
			break;
		case'*':
			std::cout << a*b << std::endl;
			break;
		case'/':
			std::cout << a/b << std::endl;
			break;
		}
	}
    return 0;
}

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



int A(int num){
	return num*num*num;
}

int B(int num){
	return (num*(num+1)*(num+2))/6;
}


int main(){
	for(int n,ans=0;cin>>n,n;ans=0){
		for(int i=0;i<54;i++){
			for(int j=0;j<96;j++){
				if(A(i)+B(j)<=n)ans=max(ans,A(i)+B(j));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 1160
N,C = map(int,input().split())
src = [list(map(int,input().split())) for i in range(N)]
MAX = 10**5
bucket = [[] for i in range(MAX+2)]
bucket2 = [set() for i in range(MAX+2)]
for s,t,c in src:
    bucket[s].append((t,c))
    bucket2[s].add(c)

imos = [0]*(MAX+2)

for s in range(MAX):
    for t,c in bucket[s]:
        imos[s-1] += 1
        if c in bucket2[t]:
            imos[t-1] -= 1
        else:
            imos[t] -= 1

ans = tmp = 0
for im in imos:
    tmp += im
    ans = max(ans, tmp)
print(ans)

Measured memory_bytes: 64796
#include<bits/stdc++.h>
#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define per(i,n,j) for(int i=(n);i>=(j);i--)
using ll=long long;
using namespace std;
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; }
const ll INF=1LL<<60;

int x;

int main(){
    cin>>x;
    ll num=0;
    int i=1;
    while(num>=0){
        num+=i;
        if(x<=num){
            cout<<i<<"\n";
            return 0;
        }
        i++;
    }
    return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 9999999999;
const int INFI=2147483647;
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
  T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }


int main() {
  int a,b,c; cin >>a >>b >>c;
  cout <<((a<b && b<c) ? "Yes" : "No") <<endl;
}



Measured memory_bytes: 3088
#include <iostream>
#include <string>
using namespace std;
string S, T; char mS[26], mT[26]; int ok = 1;
int main() {
  cin >> S >> T;
  for(int i = 0; i < S.size(); ++i) {
    int s = S.at(i)-'a';
    if(mS[s] == 0) {
      mS[s] = T.at(i);
      continue;
    }
    if(mS[s] != T.at(i)) {
      ok = 0;
      break;
    }
  }
  for(int i = 0; ok && i < S.size(); ++i) {
    int t = T.at(i)-'a';
    if(mT[t] == 0) {
      mT[t] = S.at(i);
      continue;
    }
    if(mT[t] != S.at(i)) {
      ok = 0;
      break;
    }
  }
  cout << (ok?"Yes":"No") << endl;
}

Measured memory_bytes: 776
#include <iostream>
#include <vector>
#include <list>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <tuple>

//....................................................................................................................//

using std::cin;
using std::cout;
using std::vector;
using std::list;
using std::unordered_set;
using std::set;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
using std::swap;
using std::stack;
using std::deque;
using std::queue;
using std::ios_base;
using std::ifstream;
using std::ofstream;
using std::string;
using std::tuple;
using std::make_tuple;
using std::get;
using std::upper_bound;
using std::lower_bound;
using std::max_element;
using std::min_element;

//....................................................................................................................//

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long ul;

[[maybe_unused]] const string endl = "\n";
[[maybe_unused]] const string sep = " ";
[[maybe_unused]] const string yes = "OK\n";
[[maybe_unused]] const string no = "NG\n";
[[maybe_unused]] const double pi = acos(-1);

//....................................................................................................................//



int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout.precision(10);
    ll k, a , b;
    cin >> k >> a >> b;
    for (int i = a; i <= b; ++i) {
        if (i % k == 0)  {
            cout << yes;
            return 0;
        }
    }
    cout << no;

    return 0;
}

Measured memory_bytes: 3048
x = int(input())
prlist = []
n = 2
sosuu = 0
answer = 0
while n**2 < x:
    for i in prlist:
        if n % i == 0:
            sosuu = 1
            break
    if sosuu == 0:
        prlist.append(n)
    sosuu = 0
    n += 1
sosuu = 1
while answer == 0:
    for j in prlist:
        if x % j == 0:
            sosuu = 2
            break
    if sosuu == 1:
        answer = x
    sosuu = 1
    x += 1
print(answer)

Measured memory_bytes: 63188
#include <stdio.h>
int main(void) {
	int i = 1;
	int n;

	scanf("%d", &n);

	for (i; i <= n; i++) {
		if (i % 3 == 0) {
			printf(" %d", i);
		}
		else {
			int x = i;

			while (x){
				if (x % 10 == 3) {
					printf(" %d", i);
					break;
				}
				x /= 10;
			}
		}
	}
	printf("\n");
	return 0;
}

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long double sum = 0;
    long double e = 1;
    for (int i = 0; i < n; ++i) {
        int now;
        cin >> now;
        sum += e / now;
    }
    cout << setprecision(20) << fixed;
    cout << e / sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int t; cin >> t; cin.ignore(); while(t--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
ll xpow(ll n, ll m){if(m==0){return 1;}else{ll x = xpow(n, m/2);if(m&1){return x*x*n;}else{return x*x;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}

int main(){
    fast();
 
/* you get what you work for not what you wish for */
    
    string s;
    cin >> s;
    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 if(s=="SAT"){
        cout << 1 << endl;
    }
    else{
        cout << 7 << endl;
    }
}

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

int main() {
    int n,c;
    long long ans=1000000000000;
    cin >> n >> c;
    vector<vector<int>> a(c+1,vector<int>(c+1));
    for(int i=1;i<c+1;i++){
        for (int j=1;j<c+1;j++){
            cin >> a.at(i).at(j);
        }
    }
    int p;
    vector<int> a1(0),a2(0),a0(0);
    for (int i=1;i<n+1;i++){
        for (int j=1;j<n+1;j++){
            cin >> p;
            if ((i+j)%3==0) a0.push_back(p);
            if ((i+j)%3==1) a1.push_back(p);
            if ((i+j)%3==2) a2.push_back(p);
        }
    }
    vector<long long> b0(c+1),b1(c+1),b2(c+1);
    for (int j=1;j<c+1;j++){
        b0.at(j)=0;
    for (int i=0;i<a0.size();i++){
        b0.at(j)+=a.at(a0.at(i)).at(j);
    }
    }
    for (int j=1;j<c+1;j++){
        b1.at(j)=0;
    for (int i=0;i<a1.size();i++){
        b1.at(j)+=a.at(a1.at(i)).at(j);
    }
    }
    for (int j=1;j<c+1;j++){
        b2.at(j)=0;
    for (int i=0;i<a2.size();i++){
        b2.at(j)+=a.at(a2.at(i)).at(j);
    }
    }
    long long u=0;
    for (int i=1;i<c+1;i++){
        int ti=0;
        u+=b0.at(i);
        ti=u;
        for (int j=1;j<c+1;j++){
            if (i==j) continue;
            int tj=b1.at(j);
            u+=b1.at(j);
            for (int k=1;k<c+1;k++){
                if (i==k || j==k) continue;
                long long tk=u;
                tk+=b2.at(k);
                ans=min(tk,ans);
            }
            u=u-tj;
        }
        u=u-ti;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1528
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
//#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 10000000000000000;
const ll mod = 1000000007;
ll test[12345678];
signed main() {
	ll n, m, k, l, cnt = 0, z = 0; cin >> n >> m;
	for (int h = 0; h < m; h++) {
		cin >> k >> l;
		if (test[l] != 0 && k == 1) { cout << "POSSIBLE" << endl; return 0; }
		if (test[k] != 0 && l == n) { cout << "POSSIBLE" << endl; return 0; }
		if (k == 1) { test[l]++; }
		if (l == n) { test[k]++; }
	}
	cout << "IMPOSSIBLE" << endl;
	cin >> n; return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.rbegin(), t.rend());
	if(s < t) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

int main()
{
	string str;
	cin >> str;
	string moji = "ACGT";
	int cnt = 0;
	int ans = 0;
	for( char c : str ) {
		if( moji.find( c ) == -1 )
		{
			ans = max( cnt, ans );
			cnt = 0;
		}
		else
			cnt++;
	}
	ans = max( cnt, ans );
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}



signed main(){

    int N, H, W; cin >> N >> H >> W;
    if(N >= H && N >= W) cout << (N - H + 1) * (N - W + 1);
    else cout << 0;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;
//typedef pair<int,int> P;
int const INF=1001001001;
ll const LINF=1001001001001001001;
ll const MOD=1000000007;

ll N;
string S;

int main(){
    cin>>S;
    N=S.size();

    ll w=0;
    ll ans=0;
    rep(i,N){
        if(S[i]=='W'){
            ans+=i-w;
            w++;
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 3704
program abc
    integer,dimension(5) :: dishes, mod10
    integer :: estimated_time, tmp = 0

    do i=1,5
        read *, dishes(i)
    end do

    do i=1,5
        mod10(i) = 10- MOD(dishes(i), 10)
    end do

    estimated_time = SUM(dishes)

    tmp = SUM(mod10, MASK=mod10<10)
    if (tmp>0) then
        estimated_time = estimated_time + tmp
    end if

    tmp = MAXVAL(mod10, MASK=mod10<10)
    if (tmp>0) then
        estimated_time = estimated_time - tmp
    end if

    print '(I0)', estimated_time
end program abc

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

int main(){
    int n;
    for(int l = 0;;l++){
        cin >> n;
        if(n == 0) break;
        if(l != 0) cout << endl;
        vector<string> s(n);
        vector<pair<int, int> > d;
        for(int i = 0; i < n; i++){
            int a, b, c;
            cin >> s[i] >> a >> b >> c;
            d.push_back(make_pair(3 * a + c, -i));
        }
        sort(d.begin(), d.end());
        reverse(d.begin(), d.end());
        for(int i = 0; i < n; i++){
            cout << s[-d[i].second] << "," << d[i].first << endl;
        }
    }
}

Measured memory_bytes: 3180
import static java.lang.System.out;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();

        int divideAns = a / b;
        int modAns = a % b;
        double fewAns = (double) a / b;

        out.printf("%d %d %f%n", divideAns, modAns, fewAns);
    }   
} 

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

int x[50][26];

int main(){
  string s[50];
  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    for (int j = 0; j < s[i].size(); j++){
      x[i][s[i][j]-'a']++;
    }
  }
  for (int i = 0; i < 26; i++) {
    int mi = x[0][i];
    for (int j = 0; j < n; j++) {
      mi = min(mi, x[j][i]);
    }
    for (int k = 0; k < mi; k++) {
      printf("%c", i+'a');
    }
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 256
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 52;

ll K,k;
ll a[maxn];

int main()
{
	scanf("%lld",&K); k=K%50ll;
	for(int i=50;i>50-k;i--) a[i]=50;
	for(int i=50-k;i>=1;i--) a[i]=50-k-1;
	k=K/50ll;
	for(int i=1;i<=50;i++) a[i]+=k;
	printf("50\n");
	for(int i=1;i<=50;i++) printf("%lld ",a[i]);
	
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:https://atcoder.jp/contests/abc144/tasks/abc144_b>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll N; cin >> N;
    for(int i = 1; i <= 9;i++){
        for(int j = 1; j <= 9;j++){
            if(i*j == N) return "Yes";
        }
    }
    return "No";
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<string>() << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <locale>
#include <algorithm>

using namespace std;

int main()
{
    string str;
    getline(cin, str);

    for (auto& c : str)
    {
        if (isalpha(c))
            if (isupper(c))
                c = tolower(c);
            else if (islower(c))
                c = toupper(c);
    }

    cout << str << endl;

    return 0;
}

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

int main (){
    int a[5], k;
    cin >>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>k;
    string ans = "Yay!";
    for (int i=0; i<5; i++){
        for(int j=i; j<5; j++){
            if (a[j] - a[i] > k){
                ans = ":(";
            }
        }
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
""" AtCoder """

N = int(input())
a = [int(input()) for _ in range(N)]
a.insert(0, 0)

p = 1
ans = 0

for _ in range(N):
    ans += 1
    if a[p] == 2:
        print(ans)
        exit()
    p = a[p]

print(-1)


Measured memory_bytes: 7084
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0

for a in range(N-2):
    for b in range(a+1, N-1):
        ans += bisect.bisect_left(L, L[a]+L[b]) - (b+1)
print(ans)

Measured memory_bytes: 3188
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int md=1000000007;
struct node
{
	int a[2][2];
}f,g;
int n,m,i,j,x,y,num,w;
long long K;
char s[1005][1005];
int pw(int a,long long b)
{
	int rtn=1;
	while(b)
	{
		if(b&1)
			rtn=1ll*rtn*a%md;
		a=1ll*a*a%md;
		b>>=1;
	}
	return rtn;
}
void mult(node &a,node &b)
{
	node c;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			c.a[i][j]=0;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%md;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			a.a[i][j]=c.a[i][j];
}
int main()
{
	scanf("%d%d%lld",&n,&m,&K);
	if(K<=1)
	{
		printf("1");
		return 0;
	}
	for(i=1;i<=n;++i)
	{
		scanf("%s",s[i]+1);
		for(j=1;j<=m;++j)
			if(s[i][j]=='#')
				++num;
	}
	x=y=0;
	for(i=1;i<=n;++i)
		if(s[i][1]=='#'&&s[i][m]=='#')
			++x;
	for(i=1;i<=m;++i)
		if(s[1][i]=='#'&&s[n][i]=='#')
			++y;
	if(x&&y)
	{
		printf("1");
		return 0;
	}
	if(!x&&!y)
	{
		printf("%d",pw(num,K-1));
		return 0;
	}
	if(x)
	{
		for(i=1;i<=n;++i)
			for(j=1;j<m;++j)
				if(s[i][j]=='#'&&s[i][j+1]=='#')
					++w;
	}
	else
	{
		for(i=1;i<=m;++i)
			for(j=1;j<n;++j)
				if(s[j][i]=='#'&&s[j+1][i]=='#')
					++w;
		x=y;
	}
	g.a[0][0]=num,g.a[0][1]=w,g.a[1][0]=0,g.a[1][1]=x;
	f.a[0][0]=num,f.a[0][1]=w;
	K-=2;
	while(K)
	{
		if(K&1)
			mult(f,g);
		mult(g,g);
		K>>=1;
	}
	printf("%d",(f.a[0][0]-f.a[0][1]+md)%md);
	return 0;
}

Measured memory_bytes: 1152
def divi(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return res
N, K = map(int, input().split())
A = list(map(int, input().split()))

SA = sum(A)
D = divi(SA)
D.sort(reverse = True)
ans = 0
for d in D:
    P = []
    for a in A:
        P.append(-(-a//d)*d - a)
    P.sort()
    ups = sum(P)
    if ups <= K:
        ans = d
        break
    ss = ups
    for i in range(1, N+1):
        ss -= P.pop()
        if max(ss, i*d -ups + ss) <= K:
            ans = d
            break
    else:
        continue
    break
print(ans)

Measured memory_bytes: 42348
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};



int main(){
    int n;cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    LL now = 2;
    LL ans = a[0] - 1;
    for (int i = 1; i < n; i++) {
        if(a[i] == now) now++;
        else{
            ans += (a[i] - 1)/ now;
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define fRead(x)  freopen(x,"r",stdin)
#define fWrite(x) freopen (x,"w",stdout)

#define LL long long
#define ULL unsigned long long
#define ff first
#define ss second
#define pb push_back
#define INF 2e16
#define PI acos(-1.0)
#define mk make_pair

#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(a,min(b,min(c,d)))
#define max4(a,b,c,d) max(a,max(b,max(c,d)))
#define SQR(a) ((a)*(a))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,b) for(int i=0;i<b;i++)
#define MEM(a,x) memset(a,x,sizeof(a))
#define ABS(x) ((x)<0?-(x):(x))

#define scanI(a) scanf("%d",&a)
#define scanI2(a,b) scanI(a) , scanI(b)
#define scanI3(a,b,c) scanI(a), scanI(b), scanI(c)
#define scanI4(a,b,c,d) scanI(a), scanI(b), scanI(c), scanI(d)

#define scanL(a) scanf("%I64d",&a)
#define scanL2(a,b) scanL(a) , scanL(b)
#define scanL3(a,b,c) scanL(a), scanL(b), scanL(c)
#define scanL4(a,b,c,d) scanL(a), scanL(b), scanL(c), scanL(d)

#define SORT(v) sort(v.begin(),v.end())
#define REV(v) reverse(v.begin(),v.end())

#define FastRead ios_base::sync_with_stdio(0);cin.tie(nullptr);

const int N = 18;
int n , dp[1 << N][51],A[N],B[N];

int call(int pos,int mask,int pre)
{
    if(pos == n){
        return 0;
    }
    if(dp[mask][pre] != -1)return dp[mask][pre];
    int ret = 1e9;
    vector<pair<int,int>>v1,v2;

    int got = pos;
    for(int i = 0;i < n;i++){
        if(!(mask & (1 << i))){
            if(got % 2 == 0){
                v1.push_back(mk(A[i],i));
                v2.push_back(mk(B[i],i));
            }else{
                v2.push_back(mk(A[i],i));
                v1.push_back(mk(B[i],i));
            }
        }else got++;
    }
//    cout << mask << " " << pre << " " << endl;
//    cout << "eleA: ";
//    for(int i = 0;i < v1.size();i++)cout << v1[i].first << " " << v1[i].second << "\t";
//    cout << endl;
//    cout << "eleB: ";
//    for(int i = 0;i < v2.size();i++)cout << v2[i].first << " " << v2[i].second << "\t";
//    cout << endl;
    for(int i = 0;i < v1.size();i += 2){
        int newmask = mask | (1 << v1[i].second);
        if(v1[i].first >= pre){
//            cout << "up dhuksi\n";
//            cout << "A: " << mask << " " << v1[i].first << "\n";
            ret = min(ret, i + call(pos + 1,newmask,v1[i].first));
        }
    }
    for(int i = 1;i < v2.size();i += 2){
        int newmask = mask | (1 << v2[i].second);
        if(v2[i].first >= pre){
//            cout << "down dhuksi\n";
//            cout << "B: " << mask << " " << v2[i].first << "\n";
            ret = min(ret, i + call(pos + 1,newmask,v2[i].first));
        }
    }
//    cout << mask << " " << pre << " " << ret << "\n";
    return dp[mask][pre] = ret;
}
int main()
{
    cin >> n;
    for(int i = 0;i < n;i++)cin >> A[i];
    for(int i = 0;i < n;i++)cin >> B[i];
    MEM(dp,-1);
    int ans = call(0,0,0);
    if(ans >= 1e9)ans = -1;
    cout <<  ans << "\n";
}



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

const int MAX = 3000;
double probs[MAX];

double dp[MAX][MAX];

int main(void){
    int n;
    cin>>n;
    probs[0]=0.0;
    for(int i=1;i<=n;i++){
        double k;
        cin>>k;
        probs[i]=k;
    }

    double res = 0.0;
    memset(dp, 0.0, sizeof dp);

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(j>i){
                dp[i][j]=0.0;
                continue;
            }
            if(i<=0) continue;;
            if(i==1&&j==0) dp[i][j]=(double) 1.0-probs[i];
            else if(i==1 && j==1) dp[i][j]=(double) probs[i];
            else if(j==0){
                dp[i][j]=dp[i-1][j]*(double)(1.0-probs[i]);
            }
            else{
                dp[i][j]=(double)(1.0-probs[i])*dp[i-1][j] + (double) (probs[i])*dp[i-1][j-1];
            }
        }
    }

    res=0.0;
    for(int i=n/2+1;i<=n;i++){
        res+=dp[n][i];
    }

    cout<<fixed<<setprecision(10)<<res<<endl;
    /*
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    return 0;
}


Measured memory_bytes: 70656
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque
def solve():
    n = II()
    H = LI()

    d = deque()

    def split_0(lst):
        res = []
        tmp = []
        for l in lst:
            if l == 0:
                if len(tmp) > 0:
                    res.append(tmp)
                    tmp = []
            else:
                tmp.append(l)
        if len(tmp) > 0:
            res.append(tmp)
        return res

    r = split_0(H)
    d.extend(r)
    # print(d)

    cnt = 0
    while len(d) > 0:
        lst = d.popleft()
        mn = min(lst)
        res = split_0(list(map(lambda x: x - mn, lst)))
        cnt += mn
        d.extend(res)
    print(cnt)




if __name__ == '__main__':
    solve()


Measured memory_bytes: 3444
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int n, h, w, x[40000], y[40000];
int p[40000], flag[40000], c;
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
bool use[40000];
vi tate[100000], yoko[100000];

void merge(int a, int b){
	a = root(a); b = root(b);
	if(a == b) return;
	c--;
	p[a] = b;
	flag[b] |= flag[a];
}
int main(){
	cin >> n >> w >> h;
	rep(i, n){
		cin >> x[i] >> y[i];
		if(x[i] == 1) flag[i] |= 1 << 0;
		if(x[i] == w) flag[i] |= 1 << 1;
		if(y[i] == 1) flag[i] |= 1 << 2;
		if(y[i] == h) flag[i] |= 1 << 3;
		p[i] = i;
		
		tate[x[i] - 1].pb(i);
		yoko[y[i] - 1].pb(i);
	}
	c = n;
	rep(i, 100000){
		if(tate[i].size() > 1) rep(j, tate[i].size() - 1) merge(tate[i][j], tate[i][j + 1]);
		if(yoko[i].size() > 1) rep(j, yoko[i].size() - 1) merge(yoko[i][j], yoko[i][j + 1]);
	}
	int ans = inf, cnt[4] = {};
	rep(i, n){
		int r = root(i);
		if(use[r]) continue;
		use[r] = 1;
		rep(j, 4) if(flag[r] & 1 << j) cnt[j]++;
	}
	rep(i, 4) ans = min(ans, n - 1 + c - cnt[i]);
	if(c == 1) ans = n - 1;
	cout << ans << endl;
	
	return 0;
}

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

int c[10000], s[100];

int main(){
  int n, ans = 0;;

  cin >> n;

  for(int i=0; i<n; ++i){
    cin >> s[i];

    ++c[s[i]];
  }

  int work = s[0];
  for(int i=1; i<n; ++i){
    if(work == s[i]){
      for(int ix=0; ix<10000; ++ix){
	if(c[ix] == 0){
	  s[i] = ix;
	  ++c[ix];
	  ++ans;
	  break;
	}
      }
    }
    work = s[i];
  }

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


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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<unsigned long long> a(n);
	for (auto &&e : a) {
		cin >> e;
	}
	
	unsigned long long count = 0;
	
	for (int i = 0; i < n; ++i) {
		while (a[i] % 2 == 0) {
			++count;
			a[i] /= 2;
		}
	}
	
	cout << count << endl;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
char a[101];
long long maxn=0,n,high=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]=='I')
        {
            high++;
            if(high>maxn)
            {
                maxn=high;
            }
        }
        if(a[i]=='D')
        {
            high--;
        }

    }
    cout<<maxn;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scanner = new Scanner(System.in);
		
		String inputN = scanner.nextLine();
		String inputH = scanner.nextLine();

		scanner.close();
		
		int n = Integer.parseInt(inputN);
		String[] hsStr = inputH.split(" ", 0);
		
		Integer[] hs = new Integer[hsStr.length];
		for(int i = 0; i < hsStr.length ; i++) {
			hs[i] = Integer.parseInt(hsStr[i]);
		}

		int viewable = 0;
		int curHighest = 0;
		for(int hn = 0; hn < hs.length; hn++) {
			if(curHighest <= hs[hn]) {
				curHighest = hs[hn];
				viewable++;
			}
		}
		System.out.println(viewable);
	}
}

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

using namespace std;
typedef long long llong;

void solve_test()
{
	llong n, a, b;
	cin >> n >> a >> b;
	llong full = n / (a + b);
	cout << full * a + min(n % (a + b), a) << "\n";
}

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

	int tests = 1;
	//cin >> tests;
	while (tests--)
		solve_test();

	return 0;
}


Measured memory_bytes: 3628
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	list := make([]int, n)
	for i := 0; i < n; i++ {
		list[i] = nextInt()
	}
	sort.Ints(list)

	begin := list[n/2-1]
	end := list[n/2]

	fmt.Println(end - begin)
}

// ---- readfunc
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 3224