akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,ll> pii;
const int MOD=1e9+7;
int H,W;
ll ans=0;
string board[1005];
vector<vector<ll>> dp(1005,vector<ll>(1005,-1));
ll bfs(int y,int x)
{
  if(y<0 || y>=H || x<0 || x>=W || board[y][x]=='#')
    {
      return 0;
    }
  else if(y==H-1 && x==W-1) return dp[y][x]=1;
  if(dp[y][x]!=-1) return dp[y][x];
  ll ret=0;
  ret=(ret+bfs(y,x+1))%MOD;
  ret=(ret+bfs(y+1,x))%MOD;
  return dp[y][x]=ret%MOD;
}
int main()
{
  cin >> H >> W;
  for(int i=0;i<H;i++)
    {
      cin >> board[i];
    }
  cout << bfs(0,0)%MOD << endl;
  return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}
// }}}
/* vim:set foldmethod=marker: */

void solve(){
    ll a,b,x;
    cin >> a >> b >> x;

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

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}

// sortの仕方
// int a[N];
// array<int,N> ar;
// vector<int> v;
//
// sort(a, a+N); // 配列
// sort(ar.begin(), ar.end()); // array
// sort(v.begin(), v.end()); // vector 昇順
// sort(v.begin(), v.end(), greater<int>()); // 降順

// Template
// template <class T>
// T foomax(T x, T y){
//   if (x > y){
//     return x;
//   }else{
//     return y;
//   }
// }

// string を int に変換 stoi("1010")
// int を string に変換 to_string(1010)


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

int n;
double x[100], y[100];

double dist (double p)
{
	double sum = 0;
	for (int i = 0; i < n; ++i)
	{
		sum += pow(abs(x[i] -y[i]), p);
	}
	return pow (sum, 1.0/p);
}



int main(int argc, char const *argv[])
{
	cout <<fixed << setprecision(12);
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> x[i];
	}
	for (int i = 0; i < n; ++i)
	{
		cin >> y[i];
	}

	cout << dist(1) << endl;
	cout << dist(2) << endl;
	cout << dist(3) << endl;

	double m = 0;

	for (int i = 0; i < n; ++i)
	{
		m = max(m, abs(x[i]-y[i]));
	}
	cout << m <<endl;




	return 0;
}


Measured memory_bytes: 3452
def dfs(i, j, m):
    '''
    m[i][j]??¨????????£??????????????°????????????????????????
    '''
    m[i][j] = 0
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ni = i + di
        nj = j + dj
        if ni in range(12) and nj in range(12) and m[ni][nj] == 1:
            dfs(ni, nj, m)                

while True:
    try:
        m = [list(map(int, list(input()))) for _ in range(12)]

        count = 0
        for i in range(12):
            for j in range(12):
                if m[i][j] == 1:
                    count += 1
                    dfs(i, j, m)
        
        print(count)
        input()
    except:
        break

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

#define ll long long
#define endl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int r;
    cin >> r;
    cout << 2.0 * 3.1415926 * (double)r << endl;
    return 0;
}

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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int h,w,a,b;
void solve(){
    cin>>h>>w>>a>>b;
    rep(i,0,h){
        rep(j,0,w){
            if(i<b and j<a) cout<<0;
            else if(i>=b and j>=a) cout<<0;
            else cout<<1;
        }
        cout<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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

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

//INSERT ABOVE HERE
signed main(){
  Int h,w,k;
  cin>>h>>w>>k;
  vector<string> s(h);
  for(Int i=0;i<h;i++) cin>>s[i];
  auto show=[&](){
    cout<<endl;
    for(Int i=0;i<h;i++) cout<<s[i]<<endl;
    cout<<endl;
  };
  
  auto bk=s;
  auto drop=[&](){
    Int flg=0;
    for(Int i=0;i<h-1;i++)
      for(Int j=0;j<w;j++)
	if(s[i][j]!='#'&&s[i+1][j]=='#')
	  swap(s[i][j],s[i+1][j]),flg=1;
    return flg;
  };
  auto calc=[&](){
    Int cnt=0;
    for(Int i=0;i<h;i++){
      for(Int j=0;j<w;j++){
	if(s[i][j]=='#') continue;
	Int x=j;
	while(x<w&&s[i][j]==s[i][x]) x++;
	if(x-j>=k){
	  cnt+=(x-j)*(s[i][j]-'0');
	  for(Int y=j;y<x;y++) s[i][y]='#';
	}
      }
    }
    return cnt;
  };
  Int ans=0;
  for(Int i=0;i<h;i++){
    for(Int j=0;j<w;j++){
      s=bk;
      s[i][j]='#';
      while(drop());
      Int tmp=0,po=1;
      while(Int cnt=calc()){
	tmp+=cnt*po;
	po*=2;
	while(drop());
	//show();
      }
      chmax(ans,tmp);
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

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

  int N; cin >> N;
  vector<vector<ll>> G(N);
  vector<pair<ll, ll>> vp;

  for (ll i = 0; i < N - 1; i++) {
    ll a, b; cin >> a >> b; a--; b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    vp.emplace_back(a, b);
  }

  ll K = 0;
  map<pair<ll, ll>, ll> m;
  vector<ll> colors(N, 0);

  vector<ll> used(N, 0);
  queue<ll> q;
  q.emplace(0);
  used[0] = 1;

  while (!q.empty()) {
    ll c = q.front(); q.pop();
    K = max(K, (ll) G[c].size());
    int color = 1;
    for (ll n: G[c]) {
      if (used[n]) continue;
      if (color == colors[c]) color++;
      used[n] = 1;
      colors[n] = color;
      m[make_pair(c, n)] = color;
      m[make_pair(n, c)] = color;
      q.emplace(n);
      color++;
    }
  }
  
  cout << K << '\n';
  for (ll i = 0; i < N - 1; i++) {
    cout << m[vp[i]] << '\n';
  }
  return 0;
}

Measured memory_bytes: 22128
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;

int dp[3][100010];

int main(){
    int n;
    cin >> n;
    int a[n], b[n], c[n];
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }

    for(int i = 0; i < n; i++){
        dp[0][i+1] = max(dp[1][i]+a[i], dp[2][i]+a[i]);
        dp[1][i+1] = max(dp[0][i]+b[i], dp[2][i]+b[i]);
        dp[2][i+1] = max(dp[0][i]+c[i], dp[1][i]+c[i]);
    }

    for(int i = 0; i < 3; i++){
        for(int j = 0; j <= n; j++){
            cerr << dp[i][j] << "\t";
        }
        cerr << endl;
    }

    cout << max(dp[0][n], max(dp[1][n], dp[2][n]));

    return 0;
}


Measured memory_bytes: 2560
N, K = map(int, input().split())
LL = []
RR = []
mod = 998244353
for i in range(K):
    L, R = map(int, input().split())

    LL.append(L)
    RR.append(R + 1)


keep = 0
dp = [0] * 2 * N
dp[N] = 1
for i in range(1, N):
    for j in range(K):

        keep = (keep + dp[N + i - LL[j]] - dp[N + i - RR[j]]) % mod 

    dp[N + i] = (dp[N + i] + keep) % mod
print(dp[2 * N - 1] % mod)


Measured memory_bytes: 18448
x,n = map(int,input().split())
p = list(map(int,input().split()))
i = x
j = x
ansa = 0
ansb = 0
while True:
  if i not in p:
    ansa = i - x
    break
  else:
    i += 1

while True:
  if j not in p:
    ansb = x - j
    break
  else:
    j -= 1

print(i if ansa<ansb else j)

Measured memory_bytes: 9096
import java.util.*;

public class Main{
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = Integer.parseInt(sc.next());
        int[] l = new int[n];
        int count = 0;
        for(int i = 0;i<n;i++){
            l[i] = Integer.parseInt(sc.next());
        }
        Arrays.sort(l);
        for(int i = 0;i<n-2;i++){
            int temp1 = l[i];
            int temp2 = 0;
            int temp3 = 0;
            for(int j = i+1;j<n-1;j++){
                temp2 = l[j];
                for(int k = j + 1;k<n;k++){
                    temp3 = l[k];
                    if(temp1 < temp2 && temp2 < temp3 && temp1 + temp2 > temp3){
                        count++;
                    }
                }
            }            
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 36116
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
typedef long long ll;
#define PI 3.14159265
ll exponent(ll x,ll n,ll m)
{  if(n==0)
    return 1;
    if(n%2!=0)
    {
        return (x*exponent(((x%m)*(x%m))%m,(n-1)/2,m))%m;
    }
    else
    return exponent(((x%m)*(x%m))%m,n/2,m);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(NULL);
    ll n,m;
    cin>>n>>m;
    ll a[n];
    for(int j=0;j<n;j++)
        cin>>a[j];
    set<ll>s;
    ll lcm=1;
    for(int i=0;i<n;i++)
    {
        ll x=a[i]/2,cnt=0;
        while(x%2==0)
        {
            ++cnt;
            x=x/2;
        }
        s.insert(cnt);
        x=a[i]/2;
        lcm=(lcm*x)/__gcd(lcm,x);
    }
    //cout<<lcm<<endl;
    if(lcm>m||s.size()>1)
        cout<<"0";
    else
    {
        ll ans;
        ans=m/lcm;
        if(ans%2==0)
        cout<<ans/2;
        else
            cout<<ans/2+1;
    }
    return 0;
}


Measured memory_bytes: 1024
var lines = [];

var readline = require('readline')
var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});


rl.on('line', (x) => {
    lines.push(x)
});

rl.on('close', () => {
    var N = Number(lines[0]); lines.shift();
    var s = [];

    for (var i = 0; i < N; i++) {
        var m = lines[i].split(" ");
        s.push([m[0], Number(m[1]), i]);
    }


    s.sort((a, b) => {
        if (a[0] < b[0]) { return (-1); }
        else if (a[0] > b[0]) { return (1); }
        else { return (b[1] - a[1]); }
    });

    for (var i = 0; i < N; i++) { console.log(s[i][2] + 1) }

});

Measured memory_bytes: 11852
def gcd(a,b):
    if a>b:
        x=a
        y=b
    else:
        x=b
        y=a

    if y==0:
        return x
    else:
        return gcd(y,x%y)

p,q=[int(i) for i in input().split(" ")]
print(gcd(p,q))

Measured memory_bytes: 7548
class Combinatorics
  def initialize(n, mod)
    @mod = mod
    @fact, @inv, @finv = Array.new(3){[1, 1]}
    2.upto(n) do |i|
      @fact[i] = (@fact[i-1] * i) % @mod
      @inv[i]  = (@inv[@mod % i] * (@mod - @mod / i) ) % @mod
      @finv[i] = (@finv[i-1] * @inv[i] ) % @mod
    end
  end
  def combination(n, r)
    return 0 if (n < r) || (n < 0) || (r < 0)
    (@fact[n] * @finv[n-r] % @mod) * @finv[r] % @mod
  end
  def permutation(n, r)
    return @fact[n] * @finv[n-r] % @mod
  end
end

M=10**9+7
N,K=gets.split.map(&:to_i)
A=gets.split.map(&:to_i).sort
C=Combinatorics.new(N+K+1, M)

ans=0
A.reverse.each.with_index do |a,i|
  ans+=a*C.combination(N-1-i, K-1)%M
  ans%=M
end
A.each.with_index do |a,i|
  ans+=M-a*C.combination(N-1-i, K-1)%M
  ans%=M
end
p ans

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

#define N 300010 

using namespace std;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {
	int x = 0, f = 1;
	char c = nc();
	while (c < 48) {
		if (c == '-')
			f = -1;
		c = nc();
	}
	while (c > 47) {
		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
	}
	return x * f;
}

int head[N], to[N << 1], nxt[N << 1], tot;

inline void add(int x, int y) {
	to[ ++ tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
}

int mx[N], sz[N], d[N], c[N], son[N];

void calc(int p, int fa, int v) {
	son[p] = 1;
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] != fa && to[i] < v) {
			calc(to[i], p, v);
			son[p] += son[to[i]];
		}
	}
}

void dfs(int p, int fa) {
	mx[p] = max(mx[fa], p);
	sz[p] = 1;
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] != fa) {
			dfs(to[i], p);
			sz[p] += sz[to[i]], d[p] += d[to[i]];
		}
	}
	if (mx[p] == p) {
		calc(p, fa, mx[fa]);
		d[p] = -sz[p];
	}
	if (mx[fa] == fa) {
		d[p] += sz[p];
	}
}

void dfs2(int p, int fa) {
	if (fa) {
		if (mx[p] == p) {
			c[p] += son[p];
		}
		else if (mx[fa] == fa) {
			c[p] -= son[p], c[p] += d[p];
		}
		c[p] += c[fa];
	}
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] != fa) {
			dfs2(to[i], p);
		}
	}
}

int main() {
	int n = rd();
	for (int i = 1; i < n; i ++ ) {
		int x = rd(), y = rd();
		add(x, y), add(y, x);
	}
	dfs(1,0), dfs2(1,0);
	for (int i = 2; i <= n; i ++ )
		printf("%d ", c[i]);
	return 0;
}

Measured memory_bytes: 20864
import itertools

N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

a = None
b = None

c = 0
for x in itertools.permutations(range(1,N+1)):
  c += 1
  x = list(x)
  
  if x == P:
    a = c
  if x == Q:
    b = c
    
print(abs(a-b))

Measured memory_bytes: 3064
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())

ans = INF
for a in range(1, N):
    b = N - a
    ans = min(ans, sum(list(map(int, str(a)))) + sum(list(map(int, str(b)))))
print(ans)


Measured memory_bytes: 13600
#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
    int a[5],k,i,a1[5];
    for(int i=0; i<5; i++)
    {
        scanf("%d",&a[i]);
        a1[i]=a[i]%10;
    }
    int zj=1;
    for(int i=0; i<5; i++)
    {
        if(a1[i]!=0)
        {
            zj=0;
        }
    }
    if(zj==1)
        k=10;
    else
        for(i=0,k=9; i<5; i++)
        {
            if(a1[i]<k&&a1[i]!=0)
                k=a1[i];
        }
    for(int i=0; i<5; i++)
    {
        if(a[i]%10==0)
            k+=a[i];
        else
            k+=((a[i]/10)+1)*10;
    }
    printf("%d",k-10);
}



Measured memory_bytes: 256
N = int(input())
X_list = [int(item) for item in input().split()]
res = 1000000
next_res = 10000000

for j in range(100):
    res = min(res, next_res)
    next_res = 0
    for i in range(N):
        next_res += (X_list[i] - j)**2

print(res)


Measured memory_bytes: 2940
N = input()
A, B = map(int, input().split())
P = list(map(int, input().split()))

q1 = len([p for p in P if p <= A])
q2 = len([p for p in P if A < p and p <= B])
q3 = len([p for p in P if p > B])

print(min(q1, q2, q3))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

const ll INF = 1e18;

int main(){
  ll d, g;
  cin >> d >> g;
  vector<ll> p(d), c(d);
  rep(i, d){
    ll a, b;
    cin >> a >> b;
    p.at(i) = a; c.at(i) = b;
  }
  
  ll ans = INF;
  rep(bit, 1 << d){
    ll add = 0;
    ll sum = 0;
    rep(i, d){
      if((bit & (1 << i)) != 0){
        add += p.at(i);
        sum += 100*p.at(i)*(i+1)+c.at(i);
      }
    }
    if(sum >= g){
      ans = min(ans, add);
      continue;
    }

    rrep(i, d){
      if((bit & (1 << i)) != 0) continue;
      if(sum + 100*p.at(i)*(i+1) >= g){
        add += (g-sum+((100*(i+1)-1)))/(100*(i+1));
        ans = min(ans, add);
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
N=int(raw_input())
tree=[]
for i in range(N):
    tree.append([])
for i in range(N-1):
    inp=map(int,raw_input().split())
    tree[inp[0]-1].append(inp[1]-1)
    tree[inp[1]-1].append(inp[0]-1)
nodes=[1]+[0]*(N-1)
route=[0]
node=0
while 1:
    flag=True
    for i in tree[node]:
        if nodes[i]==0:
            nodes[i]=1
            route.append(i)
            node=i
            flag=False
            break
    if flag:
        route.pop()
        node=route[-1]
    if node==N-1:
        break
l=len(route)
nodes=[0]*N
for i in range((len(route)+1)/2,len(route)):
    nodes[route[i]]=1
total=0
node=0
route.append(0)
while len(route)>l:
    flag=True
    for i in tree[node]:
        if nodes[i]==0:
            total+=1
            nodes[i]=1
            route.append(i)
            node=i
            flag=False
            break
    if flag:
        route.pop()
        node=route[-1]
if total*2>N:
    print "Fennec"
else:
    print "Snuke"


Measured memory_bytes: 25832
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const double INF = 1 << 29;

struct edge {
    int to;
    int cost;
    int limit;

    edge() {}
    edge(int a, int b, int c): to(a), cost(b), limit(c) {}
};

struct state {
    int pos;
    double cost;
    int speed;
    int prev;

    state() {}
    state(int a, double b, int c, int d): pos(a), cost(b), speed(c), prev(d) {}

    bool operator < (const state& o) const {
        return cost > o.cost;
    }
};

int N, M, S, G;

vector<edge> graph[30];

double memo[30][31][30];


bool solve() {
    cin >> N >> M;
    if (N+M == 0) { return false; }

    for (int j = 0; j < N; ++j) { graph[j].clear(); }
    for (int j = 0; j < N; ++j) {
        for (int k = 0; k <= 30; ++k) {
            fill(memo[j][k], memo[j][k]+30, INF);
        }
    }


    cin >> S >> G;
    --S; --G;
    for (int j = 0; j < M; ++j) {
        int x, y, d, c;
        cin >> x >> y >> d >> c;
        --x; --y;

        graph[x].emplace_back(y, d, c);
        graph[y].emplace_back(x, d, c);
    }

    priority_queue<state> pq;
    pq.emplace(S, 0, 0, S);
    memo[S][0][S] = 0;
    while (!pq.empty()) {
        state st = pq.top(); pq.pop();
        if (st.cost > memo[st.pos][st.speed][st.prev]) { continue; }

        for (edge& e: graph[st.pos]) {
            if (st.prev == e.to) { continue; }
            for (int dv = -1; dv <= 1; ++dv) {
                int next_speed = st.speed + dv;
                if (next_speed <= 0 || e.limit < next_speed) { continue; }

                double next_cost = st.cost + (double)e.cost / next_speed;
                if (next_cost < memo[e.to][next_speed][st.pos]) {
                    memo[e.to][next_speed][st.pos] = next_cost;
                    pq.emplace(e.to, next_cost, next_speed, st.pos);
                }
            }

        }
    }
    double ans = INF;
    for (int j = 0; j < N; ++j) {
        ans = min(ans, memo[G][1][j]);
    }
    if (fabs(ans-INF) < 1e-7) { printf("unreachable\n"); }
    else { printf("%.12f\n", ans); }
    return true;
}

int main() { for (; solve(); ); return 0; }

Measured memory_bytes: 3676
#include <bits/stdc++.h>
#include <boost/format.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/optional.hpp>

#ifdef DEBUG
#include "libs/debug.cpp"
#define DEBUG 1
#else
#define DEBUG 0
#endif

#define rep(i, n) repr((i), 0, (n))
#define repr(i, a, t) reps((i), (a), (t), 1)
#define reps(i, a, t, s) for (long long (i) = (a); (i) < (long long)(t); (i) += (s))
#define rrep(i, n) rrepr((i), (n) - 1, 0)
#define rrepr(i, a, t) rreps((i), (a), (t), 1)
#define rreps(i, a, t, s) for (long long (i) = (a); (i) >= (long long)(t); (i) -= (s))
#define each(v, c) for (auto &&(v) : (c))
#define all(c) (c).begin(), (c).end()

using namespace std;
namespace mp = boost::multiprecision;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ml = mp::cpp_int;
template<typename T>
using optional = boost::optional<T>;
const auto none = boost::none;
const long long MOD = 1e9 + 7;
const long long INF = 1e14;

vector<ll> dijkstra(
    const vector<vector<tuple<long long, long long>>> &graph,
    long long from_i) {
  const long long INF = 1e18;

  vector<long long> dist(graph.size(), INF);
  dist[from_i] = 0;

  priority_queue<tuple<long long, long long>, vector<tuple<long long, long long>>, greater<>> que;
  que.push(make_tuple(0, from_i));
  while (!que.empty()) {
    long long d, v;
    tie(d, v) = que.top();
    que.pop();
    if (d > dist[v]) continue;

    for (const auto &edge : graph[v]) {
      long long w, u;
      tie(u, w) = edge;
      if (d + w < dist[u]) {
        dist[u] = d + w;
        que.push(make_tuple(d + w, u));
      }
    }
  }

  return dist;
}

int main() {
  cout << fixed << setprecision(10);
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ifstream ifs;
  if (DEBUG) {
    ifs.open("src/_in.txt");
    cin.rdbuf(ifs.rdbuf());
  }

  ll N, M, L;
  cin >> N >> M >> L;
  vector<tuple<ll, ll, ll>> ABC(M);
  rep (i, M) {
    cin >> get<0>(ABC[i]) >> get<1>(ABC[i]) >> get<2>(ABC[i]);
  }
  ll Q;
  cin >> Q;
  vector<tuple<ll, ll>> ST(Q);
  rep (i, Q) {
    cin >> get<0>(ST[i]) >> get<1>(ST[i]);
  }

  vector<vector<ll>> dist(N, vector<ll>(N, INF));
  rep (i, N) {
    dist[i][i] = 0;
  }
  each (abc, ABC) {
    ll a, b, c;
    tie(a, b, c) = abc;
    dist[a - 1][b - 1] = c;
    dist[b - 1][a - 1] = c;
  }

  rep (k, N) {
    rep (i, N) {
      rep (j, N) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        if (dist[i][j] > L) dist[i][j] = INF;
      }
    }
  }

  vector<vector<tuple<ll, ll>>> graph(N, vector<tuple<ll, ll>>());
  rep (i, N) {
    rep (j, N) {
      if (dist[i][j] < INF) {
        graph[i].emplace_back(j, 1ll);
        graph[j].emplace_back(i, 1ll);
      }
    }
  }

  vector<vector<ll>> ans;
  rep (i, N) {
    ans.push_back(dijkstra(graph, i));
  }

  each (st, ST) {
    ll s, t;
    tie(s, t) = st;
    if (ans[s - 1][t - 1] < INF) {
      cout << ans[s - 1][t - 1] - 1 << "\n";
    } else {
      cout << -1 << "\n";
    }
  }
}

Measured memory_bytes: 8576
n_people,bus_capacity,can_wait = map(int,input().split())
arriving_time_ls = [0] * n_people
for i in range(n_people):
    arriving_time_ls[i] = int(input())
arriving_time_ls.sort()

waiting_last = 0
bus_count = 0
for i in range(1,n_people):
    if (arriving_time_ls[i] - arriving_time_ls[waiting_last] > can_wait) or (i - waiting_last + 1 > bus_capacity):
        bus_count += 1
        waiting_last = i
bus_count += 1
print(bus_count)

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

int main(void){

    int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
    int x = tx - sx;
    int y = ty - sy;
    for(int i = 0; i < x; i++) cout << "R";
    for(int i = 0; i < y; i++) cout << "U";
    for(int i = 0; i < x; i++) cout << "L";
    for(int i = 0; i < y; i++) cout << "D";
    
    cout << "D";
    for(int i = 0; i <= x; i++) cout << "R";
    for(int i = 0; i <= y; i++) cout << "U";
    cout << "L";
    cout << "U";
    for(int i = 0; i <= x; i++) cout << "L";
    for(int i = 0; i <= y; i++) cout << "D";
    cout << "R" << endl;

    return 0;
}


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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)

int main() {
	string s;
	cin >> s;
	if (s == "AAA" || s == "BBB") {
		cout << "No\n";
	}
	else {
		cout << "Yes\n";
	}
	return(0);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
int main(){
    int n;
    cin >> n;
    long a[n];
    rep(i,n){
        cin >> a[i];
        a[i]-=(i+1);
    }
    sort(a,a+n);
    long b;
    if(n%2==1){
        b = a[(n-1)/2];
    }
    else{
        b = a[n/2];
    }
    long ans = 0;
    rep(i,n){
        ans+=abs(a[i]-b);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
#define MOD 1999993

int table[2000000];

int stokey(char* s){
	int ret=0,tmp,i=0;

	while(s[i]!='\0'){
		switch(s[i]){
			case 'A':
				tmp=1;
				break;

			case 'C':
				tmp=2;
				break;

			case 'G':
				tmp=3;
				break;

			case 'T':
				tmp=4;
				break;
		}
		ret=ret*5 + tmp;
		i++;
	}

	return ret;
}

int h1(int key){
	return key%MOD;
}
int h2(int key){
	return 1+key%(MOD-1);
}
int h(int key, int col, int com){
	int pos= ( h1(key)+col*h2(key) )%MOD;

	if(com==1){
		// insert
		if(table[pos]==0)return pos;
		else return h(key, col+1,1);
	}else{
		// find
		if(table[pos]==key)return 1;
		else if(table[pos]==0)return 0;
		else return h(key,col+1,0);
	}
}
void insert(char* s){
	int key=stokey(s);

	table[ h(key,0,1) ]=key;

	return;
}
void find(char* s){
	int key=stokey(s);
	if(h(key,0,0)==1)printf("yes\n");
	else printf("no\n");

	return;
}

int main(){
	char com[10],string[20];
	int i,n;	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s%s",com,string);
		if(com[0]=='i'){
			insert(string);
		}else{
			find(string);
		}
	}

	return 0;
}



Measured memory_bytes: 10396
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999999
#define F first
#define S second
#define pb push_back
#define read(x)  freopen("input.txt","r",stdin);
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pi 2*acos(0.0)
#define ee exp(1)
#define mx 100000+100
using namespace std;
ll m[mx],s[mx];
vector<ll>v;
int main(){//read(x);
//fast;
ll a,b,c,d,e,f,g,h,i,j,k,l=0,n,t;
c=0;
cin>>n>>k;
for(i=1;i<=n;i++){
    cin>>m[i];
    s[i]=m[i]+s[i-1];
}l=1;h=n;a=0;
b=s[n];
for(i=1;i<n;i++){
    a=m[i]+m[i+1];
    if(a>=k){
        c++;
        v.pb(i);
    }
}

if(c==0)cout<<"Impossible\n";
else if(v.size()==n-1){
    cout<<"Possible\n";
    for(i=0;i<v.size();i++){
        cout<<v[i]<<endl;
    }
}
else{
    cout<<"Possible\n";
    for(i=1;i<v[v.size()-1];i++)cout<<i<<endl;
    for(i=n-1;i>v[v.size()-1];i--)cout<<i<<endl;
    cout<<v[v.size()-1]<<endl;
}
//v.clear();
//main();
}














Measured memory_bytes: 5840
n = int(input())
a = list(map(int, input().split()))

mod = 10 ** 9 + 7


def cumsum(num, lst):

    cumsumlst = [0] * num

    for hoge in range(1, n):
        cumsumlst[hoge] = (cumsumlst[hoge-1] + lst[hoge]) % mod
    
    return cumsumlst

lst = cumsum(n, a)

ans = 0

for i in range(n-1):
    ans += (a[i] * (lst[n-1] - lst[i])) % mod
    ans %= mod

print(ans)

Measured memory_bytes: 31592
fn main() {
    let n = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.trim_end().split_whitespace();
        let n: usize = iter.next().unwrap().parse().unwrap();
        n
    };

    let mut b: Vec<usize> = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.trim_end().split_whitespace();
        let b: Vec<usize> = (0..n)
            .map(|_| {
                let a: usize = iter.next().unwrap().parse().unwrap();
                a
            })
            .collect();
        b
    };
    
    let mut ans: Vec<usize> = Vec::new();
    while b.len() > 0 {
        let mut nB: Vec<usize> = Vec::new();
        let mut done: bool = false;
        for (i, val) in b.iter().rev().enumerate() {
            if b.len() - i == *val && !done {
                ans.push(*val);
                done = true;
            } else {
                nB.push(*val);
            }
        }
        if nB.len() == b.len() {
            println!("{}", -1);
            return;
        } else {
            nB.reverse();
            b = nB;
        }
    }
    ans.reverse();
    for v in ans {
        println!("{}", v);
    }
}


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

int main()
{
    string src,dist;
    string word[] = {"apple","peach"};
    getline(cin,src);
    dist = src;
    for(int i = 0; i < 2; ++i){
        string::size_type pos = src.find(word[i]);
        while(pos != string::npos){
            dist.replace(pos,5,word[1-i]);
            pos = src.find(word[i],pos + 1);
        }
    }
    cout << dist << endl;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
char a[200001];
int main()
{
	int b=0,i,l;
	long long ans=0;//,now=1;
	scanf("%s",a);
	l=strlen(a);
	for(i=0;i<l;i++)
	{
		if(a[i]=='W')
			ans+=b;
		else
			b++;
	}
	/*while(now!=0)
	{
		now=0;
		for(i=l-2;i>=0;i--)
		{
			if(a[i]=='B'&&a[i+1]=='W')
			{
				now++;
				swap(a[i],a[i+1]);
			}
		}
		ans+=now;
	}*/
	printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner (System.in);
		StringBuilder sb = new StringBuilder();
		int max = 0;
		final int n = scan.nextInt();
		int[] sequence = new int[n];
		int[] output = new int[n];
		
		for (int i = 0; i < n; i++) {
			sequence[i] = scan.nextInt();
			max = Math.max(max, sequence[i]);
		}
		scan.close();
		
		CountingSort (sequence, output, max);
		
		
		sb.append(output[0]);
		
		for (int i = 1; i < n; i++) {
			sb.append(" " + output[i]);
		}
		
		System.out.println(sb);
		
	}
	
	static void CountingSort (int[] input, int[] output, int k) {
		int n = input.length;
		int[] count = new int[k + 1];
		
		Arrays.fill(count, 0);
		
		for (int i = 0; i < n; i++) {
			count[input[i]]++;
		}
		
		for (int i = 1; i <= k; i++) {
			count[i] += count[i - 1];
		}
		
		for (int i = n - 1; i >= 0; i--) {
			output[--count[input[i]]] = input[i];
		}
	}

}



Measured memory_bytes: 567084
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define fir first
#define sec second
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
typedef pair<int,int> pii;
#define N 200005
int a[N];
signed main()
{
#ifdef __LOCAL__
	freopen("in.txt","r",stdin);
#endif
	int n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==cnt+1) cnt++;
	}
	if(cnt!=0) cout<<n-cnt<<endl;
	else cout<<"-1\n";
#ifdef __LOCAL__
	printf("Time Used : %d\n",clock());
#endif
	return 0;
}



Measured memory_bytes: 1024
import numpy as np

N = int(input())
A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)
ans = 0

for i in range(N):
    if A[i] < B[i]:
        ans += A[i]
        B[i] -= A[i]
        
        if A[i+1] <= B[i]:
            ans += A[i+1]
            A[i+1] = 0
        
        else:
            ans += B[i]
            A[i+1] -= B[i]            
            
    else:
        ans += B[i]
        
print(int(ans))

Measured memory_bytes: 25656
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

inline map<ll,int> sieve(ll n){
  map<ll,int> PrimeNumber;
  for(ll i = 2; i*i <= n; i++){
    while(n % i == 0){
      PrimeNumber[i]++;
      n /= i;
    }
  }
  if(n != 1) PrimeNumber[n] = 1;
  return PrimeNumber;
}

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  ll n,p; cin >> n >> p;
  auto res = sieve(p);
  ll ans = 1;
  for(auto x : res) ans *= pow(x.first,x.second/n);
  cout << ans;
  cout << "\n";
  return 0;
}


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

const int N = 2e5+5 , INF = 20000;

int n  , m ;
long long sol ;
vector<string> v;
map<string , int> mp;

int main() {

    cin>>n;
    for(int i = 0;i<n;i++)
    {
        string s;
        cin>>s;
        sort(s.begin() , s.end());
        v.push_back(s);
    }
    for(int i = n-1;i>=0;i--)
    {
        sol+=mp[ v[i] ];
        mp[ v[i] ]++;
    }
    cout<<sol;
    return 0;
}



Measured memory_bytes: 12020
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

vector<string> rotate(int n, const vector<string>& s)
{
    if(n == 0)
        return s;

    vector<string> t(3, string(3, ' '));
    for(int i=0; i<3; ++i){
        for(int j=0; j<3; ++j){
            t[j][2-i] = s[i][j];
        }
    }
    return rotate(n-1, t);
}

class Dice
{
public:
    vector<vector<string> > pip; // 東南西北上下の目
    Dice(){
        pip.assign(6, vector<string>(3, string(3, ' ')));
    }
    void roll(int d){ // 東南西北右左に回転
        int dir[][4] = {{4,2,5,0},{4,3,5,1},{4,0,5,2},{4,1,5,3},{0,3,2,1},{0,1,2,3}};
        vector<string> tmp = pip[dir[d][0]];
        for(int i=0; i<3; ++i)
            pip[dir[d][i]] = pip[dir[d][i+1]];
        pip[dir[d][3]] = tmp;

        if(d == 0){
            pip[1] = rotate(3, pip[1]);
            pip[2] = rotate(2, pip[2]);
            pip[3] = rotate(1, pip[3]);
            pip[5] = rotate(2, pip[5]);
        }else if(d == 1){
            pip[0] = rotate(1, pip[0]);
            pip[2] = rotate(3, pip[2]);
        }else if(d == 2){
            pip[0] = rotate(2, pip[0]);
            pip[1] = rotate(1, pip[1]);
            pip[3] = rotate(3, pip[3]);
            pip[5] = rotate(2, pip[5]);
        }else{
            pip[0] = rotate(3, pip[0]);
            pip[2] = rotate(1, pip[2]);
        }
    }
    bool operator==(const Dice& d) const{
        return pip == d.pip;
    }
};

int solve(Dice d0)
{
    set<vector<vector<string> > > s;
    queue<vector<vector<string> > > q;
    s.insert(d0.pip);
    q.push(d0.pip);

    int ret = 0;
    for(;;){
        int n = q.size();
        while(--n >= 0){
            Dice d;
            d.pip= q.front();
            q.pop();

            int tmp = 0;
            for(int i=0; i<3; ++i){
                if(d.pip[1][2][i] == '*')
                    tmp |= 1;
                if(d.pip[3][0][i] == '*')
                    tmp |= 2;
            }
            if(tmp == 3)
                return ret;

            for(int i=0; i<4; ++i){
                Dice d2 = d;
                d2.roll(i);
                if(s.find(d2.pip) == s.end()){
                    s.insert(d2.pip);
                    q.push(d2.pip);
                }
            }
        }
        ++ ret;
    }
}

int main()
{
    int to[] = {1, 0, 3, 2, 4, 5};

    for(;;){
        Dice d;
        for(int i=0; i<6; ++i){
            for(int j=0; j<3; ++j){
                cin >> d.pip[to[i]][j];
                if(d.pip[to[i]][j] == "#")
                    return 0;
            }
        }
        d.pip[0] = rotate(3, d.pip[0]);
        d.pip[2] = rotate(1, d.pip[2]);
        d.pip[3] = rotate(2, d.pip[3]);

        cout << solve(d) << endl;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e10;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 21;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<ll> fac(1000010,1);
    rep(i,1000000){
        fac[i+1] = fac[i]*(i+1)%MOD;
    }
    ll n,m,s,t;
    cin >> n >> m;
    priority_queue<ll,vector<ll>,greater<ll>> a,b;
    vector<ll> cnt(n*m+1,0);
    rep(i,n){
        cin >> s;
        cnt[s]++;
        a.push(s);
    }
    rep(i,m){
        cin >> t;
        cnt[t]++;
        b.push(t);
    }
    rep(i,n*m){
        if (cnt[i+1] >= 3){
            PRINT(0);
            return 0;
        }
    }
    ll x = n,y = m,k = min(a.top(),b.top()),ans = fac[k-1];
    while(true){
        //cout << x << " " << y << " " << k << " " << ans << '\n';
        if (x == 0 || y == 0){
            if (k <= n*m) ans = 0;
            break;
        }
        if (k == a.top() && k == b.top()){
            x--;
            y--;
            a.pop();
            b.pop();
        }
        else if (k == a.top()){
            (ans *= y)%=MOD;
            x--;
            a.pop();
        }
        else if (k == b.top()){
            (ans *= x)%=MOD;
            y--;
            b.pop();
        }
        else{
            if (x*y < n*m-k+1){
                ans = 0;
                break;
            }
            else{
                (ans *= (x*y-(n*m-k)))%=MOD;
            }
        }
        k++;
    }
    PRINT(ans);
}


Measured memory_bytes: 15872
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.regex.Pattern;
import java.util.stream.Stream;

public class Main {
  public static void main(String[] args) {

    new Main().run();
  }

  public void run() {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String line = br.readLine();
      final Pattern delim = Pattern.compile(" ");
      int[] arrayS = delim
        .splitAsStream(line)
        .mapToInt(Integer::parseInt)
        .toArray();

      OptionalInt max =
        Arrays.stream(arrayS).max();

      dispIntArray( countingSort(arrayS, max.getAsInt()) );
    }
    catch ( IOException e ) {
      System.out.println("IOException!");
    }

  }

  public int[] countingSort(int[] a, int k) {

    int   aLength = a.length;
    int[] result  = new int[aLength];
    int[] counter = new int[k+1];

    for (int var : a) {
      counter[var]++;
    }

    for (int i=1, max=k+1; i < max; i++) {
      counter[i] += counter[i-1];
    }

    for (int i=aLength-1, val=0; i>=0; i--) {
      val = a[i];
      result[counter[val]-1] = val;
      counter[val]--;
    }

    return result;
  }

  public void dispIntArray(int[] target) {
    StringBuilder s = new StringBuilder();

    for (int i : target) { s.append(i).append(" "); }
    s.setLength(s.length()-1);

    System.out.println(s);
  }
}


Measured memory_bytes: 180636
#include<stdio.h>

main()
{
int N,c[4],ans=0,i,j,n,m;

while(scanf("%d",&N)!=EOF){
ans=0;
for(i=0;i<=9;i++){
	c[0]=i;
	for(j=0;j<=9;j++){
		c[1]=j;
		for(n=0;n<=9;n++){
			c[2]=n;
			for(m=0;m<=9;m++){
				c[3]=m;
				if(c[0]+c[1]+c[2]+c[3]==N){
					ans++;
				}
			}
		}
	}
}
printf("%d\n",ans);

}
return 0;

}

Measured memory_bytes: 596
/**
 *    author:  tourist
 *    created: 14.01.2020 00:07:50       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  if (s == t) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> a;
  vector<int> b;
  int j = n - 1;
  for (int i = n - 1; i >= 0; i--) {
    if (i == 0 || t[i] != t[i - 1]) {
      b.push_back(i);
      while (j >= 0 && (j > i || s[j] != t[i])) {
        --j;
      }
      if (j < 0) {
        cout << -1 << '\n';
        return 0;
      }
      a.push_back(j);
    }
  }
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  int sz = (int) a.size();
  int low = 0, high = sz - 1;
  while (low < high) {
    int mid = (low + high) >> 1;
    bool ok = true;
    for (int i = 1; i < sz - mid; i++) {
      int val = a[i + mid] - mid;
      if (val < b[i]) {
        ok = false;
        break;
      }
    }
    if (!ok) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  cout << low + 1 << '\n';
  return 0;
}


Measured memory_bytes: 13456
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

n, m = divmod(X, 100)

if 5*n >= m:
	print(1)
else:
	print(0)


Measured memory_bytes: 5388
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//increase stack size
#pragma comment(linker, "/STACK:16777216")

ll mxm() {return LLONG_MIN;}
template<typename... Args>
ll mxm(ll a, Args... args) { return max(a,mxm(args...)); }

ll mnm() {return LLONG_MAX;}
template<typename... Args>
ll mnm(ll a, Args... args) { return min(a,mnm(args...)); }

template<class T> ostream& operator<<(ostream& os,vector<T> V){
	os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}
template<class L,class R> ostream& operator<<(ostream& os,pair<L,R> P){
	return os<<"("<<P.first<<","<<P.second<<")";
}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__,__VA_ARGS__)
template<typename Arg1>
void __f(const char* name,Arg1&& arg1){
	cout<<name<<" : "<<arg1<<endl;
}
template <typename Arg1,typename... Args>
void __f(const char* names,Arg1&& arg1,Args&&... args){
	const char* comma=strchr(names+1,',');cout.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
}
#else
#define trace(...) 1
#endif

#define ld long double
#define pll pair<ll,ll>
#define ii pair<int,int>
#define vll vector<ll>
#define vii vector<ii>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvii vector<vii>
#define I insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x)	x.begin(),x.end()

const int mod=1e9+7;
// 128 bit: __int128
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}

struct compare{
	bool operator() (const int &a,const int &b) const{
		return a>b;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;
	m1 = h1 * 60 + m1, m2 = h2 * 60 + m2;
	cout << m2 - k - m1 << endl;			
}

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

int main()
{
	long int n,m;
	while(cin>>n){
		vector<int> number(1000000,0);
		int ans=0;

		for(int i=2;i<=n;i++){
			if(number[i]==0){
				ans++;
				//cout<<i<<endl;
				for(m=i;m<=n;m+=i){
					number[m]=1;
				}
			}
		}
		cout<<ans<<endl;
	}
}

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

int partition(int a[],int p,int r) {
  int x=a[r]; 
  int i=p-1;
  for(int j=p;j<r;j++)
    if(a[j]<=x) i++,swap(a[i],a[j]);
 
  swap(a[i+1],a[r]); 
  return i+1;
}

int main(){
  int n,a[100001];
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];

  int idx=partition(a,0,n-1);
  for(int i=0;i<idx;i++)cout <<a[i]<<" ";
  cout <<"["<<a[idx]<<"] ";
  for(int i=idx+1;i<n-1;i++) cout <<a[i]<<" ";
  cout << a[n-1]<<endl;
	
  return 0;
}

Measured memory_bytes: 1552
import math
N, X = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
x.append(X)
x.sort()

xdst = [x[i+1] - x[i] for i in range(N)]
#print(xdst)

ans = 10**10
if len(xdst) == 1:
    print(xdst[0])
    exit()

for i in range(N-1):
    ans = min(math.gcd(xdst[i], xdst[i+1]),ans)
print(ans)

Measured memory_bytes: 20260
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    set<int> hon = {2, 4, 5, 7, 9};
    set<int> bon = {3};
    n %= 10;
    if (hon.count(n) == 1)
        cout << "hon"
             << "\n";
    else if (bon.count(n) == 1)
        cout << "bon"
             << "\n";
    else
        cout << "pon"
             << "\n";
    return 0;
}

Measured memory_bytes: 3652
# frozen_string_literal: true

X = gets.chomp.to_i

def next_prime?(num)
  return num if num == 2
  return num unless (2..((num / 3) + 1)).any? { |i| (num % i).zero? }

  num += 1
  next_prime?(num)
end

puts next_prime?(X)


Measured memory_bytes: 3836
N, M = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for ai in a:
    if ai not in d:
        d[ai] = 1
    else:
        d[ai] += 1
for i in range(M):
    b, c = map(int, input().split())
    if c not in d:
        d[c] = b
    else:
        d[c] += b
d_sort = sorted(list(d.items()), reverse=True)
i = 0
cnt = 0
sum_ = 0
while cnt < N:
    #print(cnt)
    if N >= cnt + d_sort[i][1]:
        sum_ += d_sort[i][0] * d_sort[i][1]
        cnt += d_sort[i][1]
    else:
        for j in range(N - cnt):
            sum_ += d_sort[i][0]
            cnt += 1
    i += 1
print(sum_)

Measured memory_bytes: 42272