akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

"""
マージソート
・再帰で全部分割してから統合
"""

import sys
def input(): return sys.stdin.readline().strip()

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

def merge(l, m, r):
    # 比較回数
    global ans    

    # aNからl～mとm～rの範囲を取り出す
    L = aN[l:m]
    R = aN[m:r]
    # 番兵(最後の要素の処理をしやすくする)
    L.append(float('inf'))
    R.append(float('inf'))

    i = j = 0
    # 前から順番にLとRを比べて、
    # 小さい方からaNに更新かけて添字を進める
    for k in range(l, r):
        if L[i] <= R[j]:
            aN[k] = L[i]
            i += 1
        else:
            aN[k] = R[j]
            j += 1
        ans += 1

def merge_sort(l, r):
    # l==rの時は何もしない
    if l+1 < r:
        # l==r(要素が1つ)になるまで再帰処理で分割する
        m = (l+r) // 2
        merge_sort(l, m)
        merge_sort(m, r)
        # 統合していく
        merge(l, m, r)

merge_sort(0, N)
print(*aN)
print(ans)



Measured memory_bytes: 61656
#include <iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<string> v;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		v.push_back(s);
	}

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	cout << v.size() << '\n';



}

Measured memory_bytes: 9092
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(llint a, llint b) {
	return a > b;
}

int main() {
	int n;
	string s;
	cin >> n;
	cin >> s;
	vint a(n + 1, 0);
	vint b(n + 1, 0);
	rep(i, n) {
		if (s[i] == '.') {
			a[i + 1] = a[i] + 1;
			b[i + 1] = b[i];
		}
		else {
			a[i + 1] = a[i];
			b[i + 1] = b[i] + 1;
		}
	}
	int ans = 2 * n;
	rep(i, n) {
		ans = min(b[i] + a[n] - a[i + 1], ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2180
def make_divisors(n):
    a = 1
    b = n
    for i in range(int(n**0.5)+1, 0, -1):
        if n % i == 0:
            a = i
            b = n//i
            break

    # divisors.sort()
    return (a+b-2)

N = int(input())

print(make_divisors(N))

Measured memory_bytes: 3060
#include<iostream>
#include<string>

using namespace std;

int main() {
	string S;
	long long K, min;
	char p = '1';

	cin >> S >> K;

	if (S.length() < K) min = S.length();
	else min = K;

	for (int i = 0; i < min; i++) {
		if (S[i] != '1') {
			p = S[i];
			break;
		}
	}
	

	cout << p << endl;
}

Measured memory_bytes: 256
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=1e18;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int h,w,dp[1005][1005]={};
  string s[1005]={};
  cin >> h >> w;
  for(int i=0; i<h; i++) {
    cin >> s[i];
  }
  for(int i=0; i<w; i++) {
    if(s[0][i]=='#') {
      break;
    }
    dp[0][i]=1;
  }
  for(int i=0; i<h; i++) {
    if(s[i][0]=='#') {
      break;
    }
    dp[i][0]=1;
  }
  for(int i=1; i<h; i++) {
    for(int j=1; j<w; j++) {
      if(s[i][j]=='#') {
        continue;
      }
      dp[i][j]+=(s[i-1][j]!='#'?dp[i-1][j]:0);
      dp[i][j]%=MOD;
      dp[i][j]+=(s[i][j-1]!='#'?dp[i][j-1]:0);
      dp[i][j]%=MOD;
    }
  }
  cout << dp[h-1][w-1] << endl;
}

Measured memory_bytes: 5248
//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int x,y;
	cin>>x>>y;
	if(x != 1 && y !=1){
		cout<<1;
		return 0;
	}
	if(x != 2 && y !=2){
		cout<<2;
		return 0;
	}
	if(x != 3 && y !=3){
		cout<<3;
		return 0;
	}
	
	return 0;
}


Measured memory_bytes: 3564
#include <stdio.h>

int main(void){


	int n, b, f, r, v, i;
	int su[4][3][10];
	
	//??????????????????
	for(b = 0; 4 > b; b++){
		for(f = 0; 3 > f; f++){
			for(r = 0; 10 > r; r++){
				su[b][f][r] = 0;
			}
		}
	}
	scanf("%d", &n);
	
	for(i = 0; n > i; i++){
		scanf(" %d %d %d %d", &b, &f, &r, &v);
		su[b-1][f-1][r-1] = su[b-1][f-1][r-1] + v;
	}
	
	for(b = 0; 4 > b; b++){
		for(f = 0; 3 > f; f++){
			for(r = 0; 10 > r; r++){
				printf(" %d", su[b][f][r]);
			}
			printf("\n");
		}
		if(b!=3){
			printf("####################\n");
		}
	}
	
	



	return 0;
	
}

Measured memory_bytes: 612
#include<iostream>
#include<cmath>
#include<map>
#include<deque>
#include<vector>
#include<string>
#include<algorithm>
#include<bitset>
typedef long long ll;

#define all(x) (x).begin(),(x).end()
#define puts(x) cout<< x << endl;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define fore(i,a) for(auto i:a)
#define MOD 1000000007;
using namespace std;
int k;
int gcd(int a,int b){
 if(a<b){
  int temp=a;a=b;b=temp;
 }
 int r=a%b;
 while(r!=0){
  a=b;b=r;r=a%b;
 }
 return b;
}

int main(){
    cin>>k;
    ll ans=0;
    rep(a,1,k+1){
        rep(b,1,k+1){
            rep(c,1,k+1){
                ans+=gcd(a,gcd(b,c));
            }
        }
    }
    puts(ans);
    
}



Measured memory_bytes: 3632
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

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

int main()
{
    int n;
    cin>>n;
    while(n>1000)
    {
        n=n%1000;
    }
    if(n!=0)
    cout<<1000-n<<"\n";
    else
    cout<<0<<"\n";
    

    return 0;
}


Measured memory_bytes: 3612
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
        int H = sc.nextInt();
        int W = sc.nextInt();
        if ( H == 0 || W == 0 ) break;
        for ( int i = 0; i < H; i++ ){
        	 if(i % 2 == 0){
            for ( int j = 0; j < W; j++ ){
               
                    if(j % 2 == 0){
                    	System.out.print("#");
                    }
                    else{
                    	System.out.print(".");
                    }
                }
        	 }
            else{
            	for ( int j = 0; j < W; j++ ){
            		if(j % 2 == 0){
            			System.out.print(".");
            		}
            		else{
            			System.out.print("#");
            		}
            }
            }
            System.out.println("");
        }
        System.out.println();
    }
}
}



Measured memory_bytes: 32824
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int main(int argc, char const *argv[]) {
  int n, k, x, y, i, sum=0;
  scanf("%d %d %d %d", &n, &k, &x, &y);
  // printf("%d %d %d %d\n", n, k, x, y);
  for(i=1; i<n+1; i++){
    if(i<=k) sum += x;
    else sum += y;
  }
  printf("%d\n", sum);
  return 0;
}


Measured memory_bytes: 128
n, m = map(int, input().split())
ss = [tuple(map(int, input().split())) for _ in range(n)]
ps = [tuple(map(int, input().split())) for _ in range(m)]


def d(s, p):
    return abs(s[0] - p[0]) + abs(s[1] - p[1])


for s in ss:
    mini = 0
    mind = d(s, ps[0])
    for i in range(1, len(ps)):
        p = ps[i]
        if d(s, p) < mind:
            mini = i
            mind = d(s, p)

    print(mini + 1)

Measured memory_bytes: 39408
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }


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

	int n, a, b, c;
	cin >> n >> a >> b >> c;
	vector<string> s(n);
	rep(i, n) cin >> s[i]; s.pb("D");
	vector<char> ans;
	rep(i, n) {
		if (s[i] == "AB") {
			if (a + b == 0) {
				cout << "No\n";
				return 0;
			}
			if (b && s[i + 1] != "BC" || !a) {
				a++; b--; ans.pb('A');
			}
			else {
				a--; b++; ans.pb('B');
			}
		}
		if (s[i] == "BC") {
			if (b + c == 0) {
				cout << "No\n";
				return 0;
			}
			if (c && s[i + 1] != "AC" || !b) {
				b++; c--; ans.pb('B');
			}
			else {
				b--; c++; ans.pb('C');
			}
		}
		if (s[i] == "AC") {
			if (c + a == 0) {
				cout << "No\n";
				return 0;
			}
			if (a && s[i + 1] != "AB" || !c) {
				c++; a--; ans.pb('C');
			}
			else {
				c--; a++; ans.pb('A');
			}
		}
	}
	cout << "Yes\n";
	for (char c : ans) cout << c << '\n';
}

Measured memory_bytes: 9552
#pragma GCC optimize ("O2")
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"

#define DEBUG 0
#define dd if (DEBUG)

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

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, A) for (auto & a : A)
#define all(a) (a).begin (), (a).end ()
#define rall(a) (a).rbegin (), (a).rend ()
#define sz(a) (int) (a).size ()
#define szl(a) (int) (a).length ()
#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit);

typedef long long ll;
typedef pair <int, int> pii;
#define f first
#define s second
#define mp(a, b) make_pair((a), (b))
typedef vector <int> vi;
typedef vector <vi> mi;
typedef vector <ll> vll;
typedef vector <vll> mll;
#define pb(a) push_back ((a))

const ll MOD = 1e+9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int INFi = 0x3f3f3f3f;
const ll MAXN = 1e+6+7;

// 01:59:32

void mod_sum (ll & a, ll b)
{
    a += b;
    while (a >= MOD) a -= MOD;
    while (a < 0) a += MOD;
}

int main ()
{
    FASTIO;
    ll i, j, n, k;
    cin >> n >> k;
    vll A (n);
    mll dp (n, vll (k + 1));
    trav (a, A)
        cin >> a;
    for (i = 0; i <= A[0]; ++i)
        dp[0][i] = 1;
    for (i = 1; i < n; ++i)
    {
        vll sums (k + 1);
        for (j = 0; j <= k; ++j)
        {
            mod_sum (sums[j], dp[i - 1][j]);
            if (j + A[i] + 1 <= k)
                mod_sum (sums[j + A[i] + 1], MOD-dp[i - 1][j]);
        }
        mod_sum (dp[i][0], sums[0]);
        for (j = 1; j < sz(dp[i]); ++j)
        {
            mod_sum (sums[j], sums[j - 1]);
            mod_sum (dp[i][j], sums[j]);
        }
    }
    dd for (i = 0; i < sz (dp); ++i)
    {
        for (j = 0; j < min (30, sz (dp[i])); ++j)
            printf ("% 3lld", dp[i][j]);
        printf ("\n");
    }
    cout << dp[n - 1][k]%MOD << '\n';

    return 0;
}



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

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

  long long int ans=0,tmpb=0,tmp=0,cnt=0;
  
  rep(i,0,n){
    tmp=0;
    cin>>tmp;
    if(tmpb>=tmp){cnt++;}
    else{cnt=0;}
    if(ans<cnt){ans=cnt;}
    tmpb=tmp;
  }

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int a[10], b[10];
	for(int i=0;i<10;i++) cin >> a[i] ;
	for(int i=0;i<10;i++) cin >> b[i] ;
	sort(a, a+10); sort(b, b+10) ;
	int suma=a[9]+a[8]+a[7];
	int sumb=b[9]+b[8]+b[7];
	cout << suma << ' ' << sumb << endl;
}

Measured memory_bytes: 1176
import Foundation

func main() {
 let inputString = readLine()!
 let split: [Int] = inputString.components(separatedBy: " ").map{Int(String($0))!}
 
 let minA = split[0]
 let maxA = split[1]
 let minB = split[2]
 let maxB = split[3]
 
 let minAminB = minA * minB
 let minAmaxB = minA * maxB
 let maxAminB = maxA * minB
 let maxAmaxB = maxA * maxB
  
 var kekka =  minAminB < minAmaxB
 var res:Int = kekka ? minAmaxB:minAminB
 kekka = res < maxAminB
 res = kekka ? maxAminB:res
 kekka = res < maxAmaxB
 res = kekka ? maxAmaxB:res
 print(res)
}

main()

Measured memory_bytes: 14200
#include <iostream>
#include <stdlib.h>
#include <utility>
#include <math.h>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define   FOR(i,n) for(int i=0;i<n;i++)

using namespace std;
int int_sort(const void*a,const void *b) {
	return *(  int *) b - *(int *) a;
	//qsort(b, a, sizeof(long long int), int_sort);
}

int main() {
	int a,count=1;
	vector<int>A(1000000,0);
	cin>>a;
	while(1){
		if(A[a]!=0){
			cout<<count;
			return 0;
		}
		A[a]=count;
		count++;
		if(a%2==0)
			a=a/2;
		else
			a=a*3+1;

		
	}

	return 0;


}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
     
int main() {
    int n;
    cin >> n;
    if (n % 10 == 2 || n % 10 == 4 || n % 10 == 5 || n % 10 == 7 || n % 10 == 9)
        cout << "hon" << endl;
    else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8)
        cout << "pon" << endl;
    else
        cout << "bon" << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<(int)N;i++)
int main()
{
  int N,a,b,first=1;
  cin>>N;
  vector<int> A(N,0),Edge(N-1,0),Color(N,0);
  rep(i,N-1)
  {
    cin>>a>>Edge.at(i);
    Edge.at(i)--,A.at(Edge.at(i))=a-1;
  }
  rep(i,N-1)
  {
    a=A.at(i+1),b=Color.at(a)+1;
    b+=b==A.at(a);
    Color.at(a)=A.at(i+1)=b;
    first=max(b,first);
  }
  cout<<first<<endl;
  for(int x:Edge)cout<<A.at(x)<<endl;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define pii pair<int, pair<int, int>>
#define ss second
#define ff first
#define all(x) ((x).begin(), (x).end())

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;
const ll oo = 1e14;

int main(){
    ios_base::sync_with_stdio(false);
    ll n, ans = oo;
    cin >> n;

    for (ll i=1; i*i<=n; i++){
        if (n%i == 0){
            ans = min(n/i + i, ans);
        }
    }

    cout << (ans == oo? n - 1: ans - 2) << endl;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]

fn main() {
    // let s = std::io::stdin();
    // let mut sc = Scanner { stdin: s.lock() };
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let D:usize = sc.read();
    let C:Vec<i64> = sc.vec(26);
    let S: Vec<Vec<i64>> = (0..D).map(|_| sc.vec(26)).collect();
    let mut past: Vec<i64> = (0..26).map(|_| -1).collect();
    let mut ANS:Vec<usize> = Vec::new();
    let mut point:i64 = 0;
    for i in 0..D{
        let mut m:i64 = -1000000000;
        let mut ind:usize = 0;
        for j in 0..26{
            let mut temp_point:i64 = point+S[i][j];
            for k in 0..26{
                temp_point -= C[j]*((i as i64)-past[k]);
            }
            if m < temp_point{
                ind = j;
                m = temp_point;
            }
        }
        ANS.push(ind);
        point = m;
        past[ind] = i as i64;
    }

    for i in 0..D{
        println!("{}", ANS[i]+1);
    }
    // for i in 0..D{
    //     ans += S[i][T[i]-1];
    //     past[T[i]-1] = i as i64;
    //     for j in 0..26{
    //         ans -= C[j]*((i as i64)-past[j]);
    //     }
    //     println!("{}", ans);
    // }
}

struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);


impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
        .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
}





Measured memory_bytes: 2284
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
typedef long long unsigned int ll;
typedef pair<int, int> P;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvdi(xs) sort(xs.begin(), xs.end(), std::greater<int>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)

#define rep(i,n) for(auto i=0; i<(n); i++)
#define isValidPoint(x, y, mx, my) x >= 0 && x  < mx && y >= 0 && y < my

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

const int MOD = 1000000007;

long exp_mod(long long a, long long b, long m) {
	long long res = 1;
	while (b > 0) {
		if (b&1)
			res = (res * a)%m;
		a = (a * a)%m;
		b >>= 1;
	}
	return (long)res;
}

long fact_mod(long n, long m) {
	long long res = 1;
	for (long i=n; i>0; --i)
		res = (res * i)%m;
	return (long)res;
}

long comb_mod(long n, long r) {
	long long res = 1;
	for (long i=0; i<r; ++i)
		res = (res * (n - i) )%MOD;
	return ( res * exp_mod(fact_mod(r, MOD), MOD-2, MOD) ) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

struct Pony
{
    int x,y;

    Pony(int x_, int y_)
    {
        x = x_;
        y = y_;
    }

    bool operator<(const Pony &another) const
    {
        return x < another.x;
    };
};

long modinv(long a, long m) {
    long b = m, u = 1, v = 0;
    while (b) {
        long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

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

  int x, a;
  cin >> x>>a;


  if (x < a) cout << 0 << endl;
  else cout << 10 << endl;
}



Measured memory_bytes: 888
N,M = map(int,input().split())
A = list(map(int, input().split()))
total = sum(A)
cutoff = total/(4*M)

over=[]
for i in A:
    if i>=cutoff:
        over.append(i)

if len(over)>=M:
    print('Yes')
else:
    print('No')

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

int main() {
	int n;
	std::cin >> n;
	int p;
	int diff = 0;
	for (int i = 1; i <= n; i++) {
	    std::cin >> p;
	    if (p!=i) diff++;
	}
	
	if(diff==0 or diff==2) {
	    std::cout << "YES" << std::endl;
	}else{
	    std::cout << "NO" << std::endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
object Main extends App {
  var n = scala.io.StdIn.readInt()
  var a = scala.io.StdIn.readLine()
  val aArray =  a.split(" ").map(_.toInt).toVector
  val amin = aArray.min

  def judgeMinArray(array: Vector[Int], min: Int):Int = {
    val divideResult = array.map(a=> a % min)
    val divideResultMax = divideResult.max
    if(divideResultMax == 0) {
      min
    } else {
      val divideResultMinWithOutZero = divideResult.filter(_ != 0).min
      if(divideResultMinWithOutZero == 1) {
        1
      } else {
        judgeMinArray(aArray, divideResultMax)
      }
    }
  }
  println(judgeMinArray(aArray, amin))
}


Measured memory_bytes: 42460
/* Reason this implementation is slow:
we did not maintain a binary heap structure when we insert value
only rely on maxHeapify and buildMaxheap to
build up it again and again

*/

#include<cstdio>
#include<cstring>
#define MAX 2000001
#define NIL 0

int pq[MAX];
int sizeOfHeap = 0;

int getLeft(int node) {
	if (node * 2 > sizeOfHeap)
		return NIL;
	else
		return node * 2;
}

int getRight(int node) {
	if (node * 2 + 1 > sizeOfHeap)
		return NIL;
	else
		return node * 2 + 1;
} 

void swapValue(int a, int b){
	int tmp = pq[a];
	pq[a] = pq[b];
	pq[b] = tmp;
}

void maxHeapify(int currNode) {
	int left = getLeft(currNode);
	int right = getRight(currNode);
	int largest;
	// pick out the largest one among currNode and its child nodes
	if (left <= sizeOfHeap && pq[left] > pq[currNode])
		largest = left;
	else
		largest = currNode;
	if (right <= sizeOfHeap && pq[right] > pq[largest])
		largest = right;

	if (largest != currNode){
		swapValue(currNode, largest);
		maxHeapify(largest);
	}
}


// for testing
void printHeap() {
	for (int i = 1; i <= sizeOfHeap ; i++ ) {
		printf(" %d", pq[i]);
	}
	printf("\n");
}

int extract() {
	int max = pq[1];
	pq[1] = pq[sizeOfHeap];
	sizeOfHeap--;
	maxHeapify(1);

	return max;
}

void insert(int value) {
	sizeOfHeap++;

	int positionOfInsertedValue = sizeOfHeap;
	int parentOfInsertedNode = positionOfInsertedValue / 2;

	pq[positionOfInsertedValue] = value;

	while (positionOfInsertedValue > 1
		&& pq[positionOfInsertedValue] > pq[parentOfInsertedNode])
	{
		swapValue(positionOfInsertedValue, parentOfInsertedNode);
		positionOfInsertedValue = parentOfInsertedNode;
		parentOfInsertedNode = positionOfInsertedValue / 2;
	}

}


int main(){
	pq[NIL] = -1; // p[0] = -1 , for comparision
	char com[10];
	int v;

	while ( 1 ) {
		scanf("%s", com);
		if (com[2] == 'd')
			break;
		if (com[0] == 'i') {
			scanf("%d", &v);
			insert(v);
		}
		if (com[0] == 'e' && sizeOfHeap > 0) {
			printf("%d\n", extract());
		}
	}

	return 0;
}

Measured memory_bytes: 6576
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

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

    while (!e.equals(0)) {
      List<Integer> candidates = new ArrayList<>();
      Integer max_z = new Double(Math.cbrt(e)).intValue();
      for(int z = max_z; z >= 0; z--) {
        Integer zzz = z*z*z;
        Integer y = new Double(Math.sqrt(e - zzz)).intValue();
        Integer x = e - zzz - y*y;
        candidates.add(x+y+z);
      }
      System.out.println(candidates.stream().sorted().findFirst().get());
      e = Integer.parseInt(sc.next());
    }
  }
}



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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
#define re return
#define mp make_pair
#define makeunique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define endl '\n'

typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<string> vs;

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }

const double pi = acos(-1.);
const ll inf = 1e10 + 7;
const ll inf2 = 1e18 + 7;
const int N = 3e5 + 17;

int n, m;
ll a[N];
int t[3000];
map<ll, int> cnt, cnto;
map<ll, ll> sqrs;
map<ll, pair<ll, ll>> fact;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for (int i = 2; i < 2200; i++)
		if (!t[i])
			for (int j = 2 * i; j < 2200; j += i)
				t[j] = 1;
	vi p;
	for (int i = 2; i < 2200; i++)
		if (!t[i]) p.pb(i);
	for (ll i = 2; i * i < inf; i++) sqrs[sqr(i)] = i;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i], cnto[a[i]]++;
	for (auto tmp: cnto) {
		auto x = tmp.fi;
		ll fi = 1, se = 1;
		for (auto d: p)
			if (x % d == 0) {
				int cur = 0;
				while (x % d == 0) {
				 	cur++;
				 	x /= d;
				}
				cur %= 3;
				if (cur == 1) fi *= d;
				if (cur == 2) se *= d;
			}
		if (sqrs.count(x)) se *= sqrs[x];
		else fi *= x;
		ll l = fi * sqr(se);
		if (l == 1) cnt[1] = 1;
		else {
			fact[l] = {fi, se};
			cnt[l] += tmp.se;
		}	
	}
	int ans = 0;
	for (auto q: cnt) {
		auto cur = q.fi;
		if (cur == 1) { ans += q.se; continue; }
		auto f = fact[cur];		
		if (f.fi < inf2 / (f.se * f.fi)) {
		    ll r = sqr(f.fi) * f.se;
			if (cnt.count(r)) {
				if (cur > r) ans += max(cnt[cur], cnt[r]);
			} else ans += cnt[cur];
		} else ans += cnt[cur];
	}
	cout << ans;
}


Measured memory_bytes: 29384
import math
Max = 1000001
prime = Max*[1]
def sieve():
	prime[0] = 0
	prime[1] = 0
	for i in range(2,Max):
		if prime[i]==1:				
			j = 2*i
			while j < Max:
				prime[j] = 0
				j += i

def Howmany(x):
	res = 1
	while x>=res:
		x -= res
		res += 1
	return res-1

N = int(input())
sieve()
ans = 0
R = int(math.sqrt(N))
for i in range(2, R):
	if prime[i]==1 and N%i==0:
		cnt = 0
		while N%i==0:
			N //= i
			cnt+=1
		ans += Howmany(cnt)

if N!=1:
	ans += 1
print(ans)



Measured memory_bytes: 16600
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
using ll = long long;
int N, cnt = 0, ans = 0, tmp = 0;

int main(){
    int A, B;
    cin >> A >> B;
    int C = A + B;
    if(A % 3 == 0 || B % 3 == 0 || C % 3 == 0) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    
    return 0;
    
}

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

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

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

const int mod = 1000000007;
class mint {
public:
    ll x;
    mint(ll x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

struct Edge {
    int to;
};
using Graph = vector<vector<Edge>>;

const ll INF=1e8;
#define MAX 1000000005

vector<bool> seen;
vector<ll> S, S0;
vector< vector<ll> > memo;

int dfs1(const Graph& G, int v)
{
    int res = 1;
    seen[v] = true;
    for (auto e : G[v]) {
        if (seen[e.to]) continue;
        res += dfs1(G, e.to);
    }
    return res;
}

ll dfs2(ll s, ll t)
{
    if (s < t) return 0;
    if (t == 0) return 1;
    if (memo[s][t]) return memo[s][t];

    mint res = mint(dfs2(s-1,t));
    res += mint(dfs2(s-1,t-1)) * mint(S[s-1]);
    memo[s][t] = res.x;

    return res.x;
}

int main(int, char**)
{
    int n;
    cin >> n;

    seen.assign(n, false);
    Graph G(n);
    vector<int> p(n);
    rep(i,n) {
        cin >> p[i];
        if (p[i] == -1) continue;
        p[i]--;
        G[i].push_back({p[i]});
        G[p[i]].push_back({i});
    }

    rep(i,n) {
        if (p[i] != -1) continue;
        S.push_back(dfs1(G, i));
    }
    rep(i,n) {
        if (p[i] == -1 || seen[i]) continue;
        S0.push_back(dfs1(G, i));
    }
    int k = S.size();
    int k0 = S0.size();
    memo.assign(k+1, vector<ll>(k+1));

    mint cyc = 0, fact = 1;
    rep(i,k) {
        if (!i) {
            cyc += (mint(dfs2(k,i+1)) - k) * mint(n-1).pow(k-1);
            continue;
        }
        cyc += mint(dfs2(k,i+1)) * fact * mint(n-1).pow(k-i-1);
        fact *= i+1;
    }
    cyc += mint(k0) * mint(n-1).pow(k);
    mint ans = mint(n) * mint(n-1).pow(k);
    ans -= cyc;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 199248
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		l = scanner.nextInt();
		turara = new int[n + 2];
		for (int i = 1; i <= n; i++)
			turara[i] = scanner.nextInt();
		dp = new int[n + 1];
		Arrays.fill(dp, -1);

		int ret = 0;
		for (int i = 1; i <= n; i++) {
			if (dp[i] == -1)
				ret = Math.max(ret, slove(i));
		}
		System.out.println(ret);
	}

	private int slove(int idx) {
		Deque<Integer> deque = new ArrayDeque<Integer>();
		deque.push(idx);
		int ret = 0;
		while (!deque.isEmpty()) {
			int x = deque.peek();
			if (turara[x] < turara[x + 1] && dp[x + 1] == -1) {
				deque.push(x + 1);
				continue;
			}
			if (turara[x] < turara[x - 1])
				ret = Math.max(ret, dp[x - 1]);

			ret = dp[x] = ret + (l - turara[x]);
			deque.poll();
		}
		return ret;
	}

	int[] dp, turara;
	int n, l;

}

Measured memory_bytes: 64252
// O(n'2 + e)
// テ」ツδ療」ツδェテ」ツδ?ヲツウツ?

#include <iostream>
#include <algorithm>
#define MAX 100
#define INF 999999

using namespace std;

int cost[MAX + 1][MAX + 1];
int mincost[MAX + 1];
bool used[MAX + 1];

int prim(int V){ // テ」ツδ偲」ツδシテ」ツδ嘉ヲツ閉ー

  for(int i = 0 ; i < V ; i++){ // テ・ツ按敕ヲツ慊淌・ツ個?
    mincost[i] = INF;
    used[i] = false;
  }

  mincost[0] = 0; 
  int res = 0 ; 

  while(true){
    int v = -1;
    for(int u = 0 ; u < V ; u++){
      if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
      // テ、ツスツソテ」ツ?」テ」ツ?ヲテ」ツ?ェテ」ツ??」ツつ?」ツ?、テ」ツ?ァテヲツ慊?」ツつづ・ツーツ湘」ツ?陛」ツ??ostテ」ツ?ョテヲツキツサテ・ツュツ療」ツつ津ヲツ篠「テ」ツ??
    }
    if(v == -1) break;
    used[v] = true; // テ」ツ?凖」ツ?ァテ」ツ?ォテ、ツスツソテ」ツ?」テ」ツ?淌」ツ?禿」ツ?ィテ」ツ?ォテ」ツ?凖」ツつ?
    res += mincost[v];

    for(int u = 0 ; u < V ; u++){
      mincost[u] = min(mincost[u], cost[v][u]);
      // mincostテ」ツ?ョテァツ「ツコテ・ツョツ?
    }
  }
  return res;
}

int main(void){

  int n, m;
  while(cin >> n >> m, n + m){

    fill(cost[0], cost[MAX], INF);

    for(int i = 0 ; i < m ; i++){
      int a, b, c;
      cin >> a >> b >> c;
      cost[a][b] = cost[b][a] = c;
    }
    cout << prim(n) << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
 
#define TRACE(x) cerr << #x << " = " << x << endl
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
#define SZ(x) (int)(x).size()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
template<class Num>
Num mabs(Num A){
  if(A < 0) return -A;
  return A;
}

const int N = 1 << 18;

struct Tour{
  int n, off;
  vector<int> tree;
  
  Tour(int _n){
    n = _n;
    int i;
    for(i = 1; i <= n; i *= 2);
    off = i;
    tree.resize(2 * off + 1);
  }
  
  void build(int node, int a, int b){
    if(a == b){
      tree[node] = 0;
      return;
    }
    int mid = (a + b) / 2;
    build(node * 2, a, mid);    
    build(node * 2 + 1, mid + 1, b);    
    tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
  }
  
  void update(int node, int a, int b, int pos, int val){
    if(a == b){
      tree[node] = max(tree[node], val);
      return;
    }
    int mid = (a + b) / 2;
    if(pos <= mid)
      update(node * 2, a, mid, pos, val);
    else
      update(node * 2 + 1, mid + 1, b, pos, val);
      
    tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
  }
  
  pii walk(int node, int a, int b, int least){
    if(a == b) return mp(a, tree[node]);
    int mid = (a + b) / 2;
    if(tree[node * 2] >= least)
      return walk(node * 2, a, mid, least);
    else return walk(node * 2 + 1, mid + 1, b, least);
  }
  
  int query(int least){
    if(tree[1] < least) return n;
    return walk(1, 0, off - 1, least).fi;
  }
  
  void build(){
    build(1, 0, off - 1);
  }
  
  void update(int p, int val){
    update(1, 0, off - 1, p, val);
  }
  
};

int n, q;

int main(){
  scanf("%d %d", &n, &q);
  Tour rows(n), cols(n);
  rows.build(); cols.build();
  
  ll ans = (ll)(n - 2) * (ll)(n - 2);
  
  while(q--){
    int f, x; scanf("%d %d", &f, &x);
    if(f == 1){
      //x-ta kolona, spustam dolje
      int dokle = rows.query(x);
      ans -= (ll)(dokle - 2);
      cols.update(x, dokle);
    }
    
    else{
      int dokle = cols.query(x);
      ans -= (ll)(dokle - 2);
      rows.update(x, dokle);
    }
  }
  
  printf("%lld\n", ans);
  
  return 0;
}


Measured memory_bytes: 7508
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const ll MOD=1e9+7;
const ll INF=1e9;
const double PI=acos(-1);
const int MAX=100010;


ll sum_e(vector<ll> x) {
    int n=x.size();
    ll sx=0;
    rep(i,n/2) {
        sx=(sx+((x[n-1-i]-x[i])*(n-1-2*i))%MOD)%MOD;
    }
    return sx; 
}

int main() {
    ios_base::sync_with_stdio(false); 

    int n,m;
    cin >> n >> m;
    vector<ll> x(n),y(m);
    rep(i,n) cin >> x[i];
    rep(i,m) cin >> y[i];
    ll sx=sum_e(x);
    ll sy=sum_e(y);
    
    cout << (sx*sy)%MOD << endl;

    return 0;
}


Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define endl              "\n"
#define pb              push_back
#define fir               first
#define sec               second
#define all(v)            ((v).begin()), ((v).end())
#define sz(v)            ((int)((v).size()))
#define ll              long long
#define ld              long double
#define lp(i, n)        for(int i = 0 ; (int)i<n ; i++)
#define loop(i, x, n)       for(int i=x ; (int)i<=n ; i++)
#define isPowerOfTwo(s) (!(s & (s-1)))
typedef vector<int> vi;
typedef deque<int> de;
void origi() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
}
void tiranga() {
    int n;
    cin >> n;
    multiset<int>mm;
    int x;
    cin >> x;
    mm.insert(x);
    lp(i, n - 1) {
        cin >> x;
        auto itr = mm.lower_bound(x);
        if (itr == mm.begin()) mm.insert(x);
        else mm.erase(--itr) , mm.insert(x);
    }
    cout << mm.size();
}
int main() {
#ifndef ONLINE_JUDGE.
    //freopen("input.txt", "r", stdin);
#else
#endif
    
    origi();
    tiranga();
    //cout << sumOfDig(123654);
   // genLarge(10, 10);
   // genSmall(10);

}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  string s;
  cin>>s;
  int u = stoi(s.substr(0,2));
  int l = stoi(s.substr(2));
  bool ismmyy = (1 <= u && u <= 12);
  bool isyymm = (1 <= l && l <= 12);
  if (ismmyy) {
    if (isyymm) {
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "MMYY" << endl;
    }
  } else {
    if (isyymm) {
      cout << "YYMM" << endl;
    } else {
      cout << "NA" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>

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

using namespace std;

const double INF=1e77;
const double PI=acos(-1);

struct point{
	int r,i;
	bool operator==(const point &p)const{ return r==p.r && i==p.i; }
};

struct edge{ int v; double cost; };

int main(){
	for(int n,m;scanf("%d%d",&n,&m),n||m;){
		const double COST=2*sin(PI/n); // 正 n 角形の一辺の長さ

		point s,t;
		scanf("%d%d%d%d",&s.r,&s.i,&t.r,&t.i); s.i--; t.i--;
		point bad[100][2];
		rep(i,m) rep(j,2) scanf("%d%d",&bad[i][j].r,&bad[i][j].i), bad[i][j].i--;

		vector<int> R; // 候補となる頂点の r の値
		R.push_back(1);
		R.push_back(s.r);
		R.push_back(t.r);
		rep(i,m) rep(j,2) {
			R.push_back(bad[i][j].r);
			R.push_back(bad[i][j].r+1);
			R.push_back(max(bad[i][j].r-1,1));
		}
		sort(R.begin(),R.end());
		R.erase(unique(R.begin(),R.end()),R.end());

		int N=n*R.size();
		static vector<edge> G[60300];
		rep(u,N) G[u].clear();
		rep(i,R.size()){
			int r=R[i];
			rep(j,n){
				// 左
				bool ok=true;
				rep(k,m){
					if(bad[k][0]==(point){r,j} && bad[k][1]==(point){r,(j-1+n)%n}
					|| bad[k][1]==(point){r,j} && bad[k][0]==(point){r,(j-1+n)%n}) ok=false;
				}
				if(ok){
					int u=n*i+j,v=n*i+(j-1+n)%n;
					G[u].push_back((edge){v,r*COST});
					G[v].push_back((edge){u,r*COST});
				}

				// 上
				if(i+1<R.size()){
					ok=true;
					int r2=R[i+1];
					rep(k,m){
						if(bad[k][0]==(point){r,j} && bad[k][1]==(point){r2,j}
						|| bad[k][1]==(point){r,j} && bad[k][0]==(point){r2,j}) ok=false;
					}
					if(ok){
						int u=n*i+j,v=n*(i+1)+j;
						G[u].push_back((edge){v,r2-r});
						G[v].push_back((edge){u,r2-r});
					}
				}
			}
		}

		// Dijkstra
		int s_id=n*(find(R.begin(),R.end(),s.r)-R.begin())+s.i;
		int t_id=n*(find(R.begin(),R.end(),t.r)-R.begin())+t.i;
		static double d[60300];
		rep(u,N){
			d[u]=(u==s_id?0:INF);
		}
		priority_queue< pair<double,int> > Q; Q.push(make_pair(0,s_id));
		while(!Q.empty()){
			double d_now=-Q.top().first;
			int u=Q.top().second; Q.pop();

			if(d_now>d[u]) continue;

			rep(i,G[u].size()){
				edge e=G[u][i];
				if(d[e.v]>d[u]+e.cost){
					d[e.v]=d[u]+e.cost;
					Q.push(make_pair(-d[e.v],e.v));
				}
			}
		}

		printf("%.9f\n",d[t_id]);
	}

	return 0;
}

Measured memory_bytes: 5068
import sys
rl = sys.stdin.readline


def solve():
    N, A, B = map(int, rl().split())
    h = [int(rl()) for _ in range(N)]
    ad_d = A - B
    
    def calc(t):
        cnt = 0
        for i in range(N):
            d = h[i] - B * t
            if 0 < d:
                cnt += d // ad_d if d % ad_d == 0 else d // ad_d + 1
        return cnt <= t
    
    ok, ng = 10 ** 9, 0
    while 1 < ok - ng:
        mid = (ok + ng) // 2
        if calc(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 43996
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
#include <map> // pair
#include <cstdlib>  // abs() for integer
#include <cmath>    // abs() for float, and fabs()
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;

using namespace std;
using ll = long long;
typedef pair <ll, ll > pll;

int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll n, m, K;
	ll memo[1003][1003] = { {} };
	ll memox[1003] = {};
	ll memoy[1003] = {};
	ll x[1000006] = {};
	ll y[200005] = {};
	ll z[200005] = {};
	string s;
	string s1, s2;
	//IntStack yStack;
	//charStack Stack;
	ans = 99999999999;
	cin >> a;
	cin >> b;
	for (int i = 1; i <= a; i++)
	{
		ans = min(ans,max(max(i*(b / 2), i*(b - b / 2)), (a - i)*b)-min(min( i*(b / 2) , i*(b - b / 2) ), (a - i)*b));
	}
	for (int i = 1; i <= b; i++)
	{
		ans =min(ans, max(max( i*(a / 2), i*(a - a / 2)), (b - i)*a)-min(min( i*(a / 2) , i*(a - a / 2) ), (b - i)*a));
	}
	ans = min(ans, max(max(a*(b - 2 * b / 3), a*((2 * b) / 3 - b / 3)), a*(b / 3)) -min(min(a*(b - 2 * b / 3) , a*((2 * b) / 3 - b / 3) ), a*(b / 3)));
	ans = min(ans, max(max(b*(a - 2 * a / 3), b*((2 * a) / 3 - a / 3)), b*(a / 3))-min(min(b*(a - 2 * a / 3) , b*((2 * a) / 3 - a / 3)) , b*(a / 3)));
	cout << ans << endl;


	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}

//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  vector<string> data(H);
  vector<vector<int>> mine(H,vector<int>(W));
  for(int i=0;i<H;i++){
    cin >> data.at(i);
  }
  for(int i=0;i<H;i++){
    string datai=data.at(i);
    for(int j=0;j<W;j++){
      if(datai.at(j)=='#'){
        if(j!=0)
          mine.at(i).at(j-1)++;
        if(j!=W-1)
          mine.at(i).at(j+1)++;
        if(i!=0)
          mine.at(i-1).at(j)++;
        if(i!=H-1)
          mine.at(i+1).at(j)++;
        if(i!=0&&j!=0)
          mine.at(i-1).at(j-1)++;
        if(i!=0&&j!=W-1)
          mine.at(i-1).at(j+1)++;
        if(i!=H-1&&j!=0)
          mine.at(i+1).at(j-1)++;
        if(i!=H-1&&j!=W-1)
          mine.at(i+1).at(j+1)++;
      }
    }
  }
  for(int i=0;i<H;i++){
    string datai=data.at(i);
    for(int j=0;j<W;j++){
      if(datai.at(j)=='#')
        cout << datai.at(j);
      if(datai.at(j)!='#')
        cout << mine.at(i).at(j);
    }
    cout<<endl;
  }
}

Measured memory_bytes: 256
package main

import(
    "fmt"
)



func main() {
    var a,b,c int
    fmt.Scan(&a,&b,&c)
    if (a*100+b*10+c) % 4 == 0{
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}





func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}


Measured memory_bytes: 512
n = input()
arr = map(int, raw_input().split())
arr.sort()

res = 0
cur = 0
for i in xrange(len(arr) - 1):
	cur += arr[i]
	res += 1
	if not (arr[i+1] <=  2 * cur):
		res = 0

print res + 1
	


Measured memory_bytes: 11320
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>
#include<stack>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define sz(a) (int)a.size()
using namespace std;

int main() {
	string s;
	cin >> s;
	if (s == "ABC") cout << "ARC" << endl;
	else cout << "ABC" << endl;
}

Measured memory_bytes: 3548
def submit():
    n = int(input())
    s = input()

    cnt = 0
    op = 0
    for c in s:
        if c == "(":
            cnt += 1
        else:
            if cnt == 0:
                op += 1
            else:
                cnt -= 1

    print("(" * op + s + ")" * cnt)


submit()

Measured memory_bytes: 2940
#include <stdio.h>

int main(void){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);

    int l=a+b;
    int r=c+d;

    if(l<r){
        printf("Right\n");
    }
    else if(l>r){
        printf("Left\n");
    }
    else{
        printf("Balanced\n");
    }

    return 0;
}

Measured memory_bytes: 1648
#import <Foundation/Foundation.h>
#import <stdio.h>

int main(int argc, char **argv) {
  NSInteger N;
  
  scanf("%ld", &N);
  
  NSInteger num3 = N / 3;
  NSInteger num5 = N / 5;
  NSInteger num15 = N / 15;
  
  NSInteger sum = (N + 1) * N / 2;
  sum -= 3 * (num3 + 1) * num3 / 2;
  sum -= 5 * (num5 + 1) * num5 / 2;
  sum += 15 * (num15 + 1) * num15 / 2;

  printf("%ld", sum);
  return 0;
}

Measured memory_bytes: 12696
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define maxn 100010
using namespace std;
char s[maxn];
int n;
int a[maxn];
int cnt;
int po[maxn];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    if(s[1]=='0')
    {
        puts("-1");
        return 0;
    }
    if(s[n]=='1')
    {
        puts("-1");
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        if(s[i]!=s[n-i])
        {
            puts("-1");
            return 0;
        }
        if(s[i]=='1')  a[++cnt]=i;
    }
    po[1]=1;
    int now=1;
    for(int i=2;i<=a[1];i++)
    {
        cout<<1<<" "<<++now<<endl;
    }
    for(int i=2;i<=cnt;i++)
    {
        int cha=a[i]-a[i-1];
        po[i]=++now;
        cout<<po[i]<<" "<<po[i-1]<<endl;
        for(int j=1;j<=cha-1;j++)
        {
            cout<<po[i]<<" "<<++now<<endl;
        }
    }
    cout<<po[cnt]<<" "<<n<<endl;
    return 0;
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
int main(){
  int k;cin >> k;
  string s;
  cin >> s;
  int n = s.length();
  if(n<=k)cout << s;
  else{
    for(int i = 0;i<k;i++)
    cout << s[i];
    cout <<"...";
  }
  return 0;
}

Measured memory_bytes: 3628