akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())
d = {}
for _ in range(n):
    a, b = map(int, input().split())
    if a in d:
        d[a] += b
    else:
        d[a] = b
d = dict(sorted(d.items()))
cnt = 0
for key, v in d.items():
    cnt += v
    if cnt >= k:
        print(key)
        break

Measured memory_bytes: 24820
from itertools import accumulate
N, K = map( int, input().split())
A = list( map( int, input().split()))
accA = [0] + list( accumulate(A))
V = [1]*(N*(N+1)//2)
ans = 0
check = False
for i in range(40,-1,-1):
    W = [0]*(N*(N+1)//2)
    for l in range(N):
        for r in range(l+1,N+1):
            if V[l*(2*N+1-l)//2+r-l-1] == 0:
                continue
            if (accA[r]-accA[l])%(2**(i+1)) >= 2**i:
                W[l*(2*N+1-l)//2+r-l-1] = 1
    if check == False:
        if sum(W) >= K:
            check == True
        else:
            continue
    if sum( V and W) >= K:
        ans += 2**i
        V = V and W
print(ans)

Measured memory_bytes: 117396
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+5;

int main(){
    double l;
    cin >> l;
    cout << fixed << setprecision(10) << (l/3.000) * (l/3.0) * (l/3.0) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
#define IN(n,m)  (!(m.find(n) == m.end()))
#define TO_INT(vec,s) REP(i,s.length()){vec.push_back(s[i] - ‘0’);}
#define ENUM_v(vet) for (auto e : vec)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << "(" << itr->first.first << "," << itr->first.second << ") --> "  << itr->second << endl; }

using namespace std;
typedef vector<long> VI;
typedef vector<VI> VVI;
typedef pair<long,long> pr;
typedef map<pr,long> mp;

int main(void){
	long H,W,N,a,b;
	mp center;
	VI ans(10,0);
	cin >> H >> W >> N;
	REP(i,N) {
		cin >> a >> b;
		center[pr(a-1,b-1)]++;
		if (b >= 2) center[pr(a-1,b-2)]++;
		if (b <= (W-1)) center[pr(a-1,b)]++;
		if (a >= 2){
			center[pr(a-2,b-1)]++;
			if (b >= 2) center[pr(a-2,b-2)]++;
			if (b <= (W-1)) center[pr(a-2,b)]++;
		}
		if (a <= (H-1)){
			center[pr(a,b-1)]++;
			if (b >= 2) center[pr(a,b-2)]++;
			if (b <= (W-1)) center[pr(a,b)]++;
		}
	}

	//dump_MAP(center);

	for (auto itr = center.begin();itr != center.end();++itr){
		if (itr->first.first == 0 || itr->first.second == 0 || itr->first.first == (H-1) || itr->first.second == (W-1)) continue;
		ans[itr->second]++;
	}

	long long sumval = (H-2) * (W-2);
	FOR(i,1,10) sumval -= ans[i];
	cout << sumval << endl;
	FOR(i,1,10){
		cout << ans[i] << endl;
	}

	return 0;
}



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

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;

#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
constexpr auto INF = 200000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int n;
	cin >> n;
	int k;
	k = (n-1) % 111;

	cout << n - k + 110 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define pb(a) push_back(a)
using namespace std;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    vector<int> w(N);
    REP(i, N)
    {
        cin >> w.at(i);
    }

    int s2 = 0;
    REP(i, N)
    {
        s2 += w.at(i);
    }

    int ans = 10000;
    int s1 = 0;
    REP(i, N - 1)
    {
        s1 += w.at(i);
        s2 -= w.at(i);
        if (abs(s2 - s1) < abs(ans))
        {
            ans = abs(s2 - s1);
        }
    }

    cout << ans;
}

Measured memory_bytes: 256
import sys
import math
import bisect

def query(n, x):
    return n // x + 1

def main():
    a, b, x = map(int, input().split())
    ans = query(b, x)
    if a > 0:
        ans -= query(a - 1, x)
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
x, y = map(int, input().split())

b = (y - 2*x)
a = (4*x - y)

if a % 2 == 0 and a >= 0:
  if b % 2 == 0 and b >= 0:
    print('Yes')
  else:
    print('No')
else:
  print('No')

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

using namespace std;

#define en '\n'
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pb push_back
#define mod 1000000007

vector<ll> cnt(100005,0);

int main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   int n;
   cin>>n;
   ull sum = 0;
   for(int i = 0;i<n;++i)
   {
       ll a;
       cin>>a;
       ++cnt[a];
       sum+=a;
   }
   int q;
   cin>>q;
   while(q--)
   {
       ll a,b;
       cin>>a>>b;
       ll prev = cnt[b];
       cnt[b]+=cnt[a];
       sum-=cnt[a]*a;
       cnt[a] = 0;
       sum+=(cnt[b]-prev)*b;
       cout<<sum<<en;
   }
}


Measured memory_bytes: 3824
#include <iostream>
#include <stdint.h>
#include <vector>
#include <limits.h>
#include <utility>

using namespace std;

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

  int64_t sum = 0;
  int64_t min_abs = INT64_MAX;
  int64_t minus_count = 0;
  
  for (int n=0; n<N; ++n) {
    int64_t a;
    cin >> a;
    if (a < 0) {
      ++minus_count;
      a = -a;
    }

    sum += a;

    if (a < min_abs)
      min_abs = a;
  }

  if (minus_count%2)
    sum -= 2*min_abs;
  
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 888
n = int(input())
dic = {}

for i in range(n):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

m = max(dic.values())
arr = []

for j in dic:
    if dic[j] == m:
        arr.append(j)

arr.sort()

for k in arr:
    print(k)

Measured memory_bytes: 32096
import java.io.*;
 
public class Main{
     
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String number_s = br.readLine();
        int number_i = Integer.parseInt(number_s);
        int num = number_i*number_i*number_i;
        System.out.println(num);
        }
}

Measured memory_bytes: 17000
#include <iostream>
#include <string>
typedef long long ll;
using namespace std;
ll MOD = 1e9+7;

int main() {
    string s;
    cin >> s;
    bool flag = true;
    for(int i=0; i<s.length(); i++) {
        if(i%2==0) {
            if(s[i]=='L') flag=false;
        } else {
            if(s[i]=='R') flag=false;
        }
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <random>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <complex>
#include <functional>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < int(b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> int(a);)
#define all(v) v.begin(),v.end()
#define trav(x, v) for(auto &x : v)
#define sz(v) int((v).size())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long double ld;
const ll mod = 1e9+7;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	ll a, b;
	cin >> a >> b;
	vector<ll> s(n+1);
	s[0] = -a-b;
	rep(i,1,n+1) cin >> s[i];
	vector<ll> X(n), Y(n);
	X[0] = 1, Y[0] = 1;
	ll preX = 0, preY = 0;
	int px = 0, py = 0;
	int lex = 0, ley = 0;
	rep(i,2,n+1){
		while(s[i]-s[px] >= a){
			preY += Y[px];
			++px;
		}
		while(s[i]-s[py] >= b){
			preX += X[py];
			++py;
		}
		preY %= mod, preX %= mod;
		X[i-1] = preY;
		Y[i-1] = preX;
		if(px < i){
			while(lex < i-1){
				X[lex] = 0;
				++lex;
			}
			preX = 0;
		}
		if(py < i){
			while(ley < i-1){
				Y[ley] = 0;
				++ley;
			}
			preY = 0;
		}
		if(px == i) preY += Y[i-1];
		if(py == i) preX += X[i-1];
	}
	ll ans = 0;
	trav(x, X) ans += x;
	trav(y, Y) ans += y;
	ans %= mod;
	if(ans < 0) ans += mod;
	cout << ans << endl;
}

Measured memory_bytes: 2688
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する


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

    int n;
    cin >> n;
    vector<int> v(n);
    rep(i,0,n){
        cin >> v[i];
        v[i]--;
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        if(v[i] == i){
            i++;
            if(i != n && v[i] == i){
                ans++;
            }else{
                i--;
                ans++;
            }
        }
    }
    cout << ans << endl;





    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
vector<long>gap_list;

void insertion_sort(long A[], int n, int g){
    for(int i = g; i <= n-1; ++i){
        int v = A[i];
        int j = i-g;
        while(j>=0&&A[j]>v){
            A[j+g] = A[j];
            j = j-g;
            cnt++;
        }
        A[j+g] = v;
    }
}

void shell_sort(long A[], int n, int m){
    for(int i = m-1; i >= 0; --i){
        insertion_sort(A, n, gap_list[i]);
    }
    return;
}

int main(){
    //FILE *inp = freopen("inp.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    long arr[n];
    for(int i = 0; i < n; ++i) scanf("%ld", &arr[i]);
    for(int i = 1; i*i <= n; ++i){
        gap_list.push_back(i*i);
        if(gap_list.size()>=100)break;
    }
    int gap_cnt = gap_list.size();
    cout << gap_cnt << endl;
    for(int i = gap_cnt-1; i >=0; --i){
        if(i != gap_cnt-1) printf(" ");
        printf("%ld", gap_list[i]);
    }
    printf("\n");
    shell_sort(arr, n, gap_cnt);
    printf("%d\n", cnt);
    for(int i = 0; i < n; ++i){
        printf("%ld\n",arr[i]);
    }
    //fclose(inp);
    return 0;
}

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

int main(){

    int S, h, m, s;
    cin >> S;
    h = S / (60 * 60);
    m = (S - (h * 60 * 60)) / 60;
    s = S - (h * 60 * 60) - m * 60;
    cout << h << ":" << m << ":" << s << endl;
    return 0;

}


Measured memory_bytes: 3108
using System;

class Program
{
   static void Main(string[] args)
   {
      string input = Console.ReadLine();
      int cnt = 0; 
      
      if (input[0] == 'o') cnt++;
      if (input[1] == 'o') cnt++;
      if (input[2] == 'o') cnt++;
      Console.WriteLine(700+cnt*100);
   }
}


Measured memory_bytes: 13140
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



string str;

int main() {
	while (cin >> str) {
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '@') {
                int num = str[i+1] - '0';
                char c = str[i+2];
                for (int j = 0; j < 3; ++j) str.erase(str.begin() + i);

                string ins = "";
                for (int j = 0; j < num; ++j) ins += c;
                str = str.substr(0, i) + ins + str.substr(i);
            }
        }
            
        cout << str << endl;
	}
    
    return 0;
}


Measured memory_bytes: 1208
#include <iostream>
using namespace std;
int main(void){
    
    int a;
    int b;
    
    cin>>a;
    cin>>b;
    
    if(a<b){
        cout<<"a < b"<<endl;
    }
    
    else if(a>b){
        cout<<"a > b"<<endl;
    }
    
    else{
        cout<<"a == b"<<endl;
    }
}



Measured memory_bytes: 3068
import sys
sys.setrecursionlimit(10000000)
N = int(input())
JU = [-1 for _ in range(N)]

LI = [[] for _ in range(N)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    W = w%2
    LI[u-1].append([v-1,W])
    LI[v-1].append([u-1,W])
def dfs(x):
    for i in range(len(LI[x])):
        j = LI[x][i][0]
        k = LI[x][i][1]
        if JU[j] == -1:
            if JU[x] == 0:
                if k == 0:
                    JU[j] = 0
                    dfs(j)
                else:
                    JU[j] = 1
                    dfs(j)
            else:
                if k == 0:
                    JU[j] = 1
                    dfs(j)
                else:
                    JU[j] = 0
                    dfs(j)

JU[0] = 0
dfs(0)
for i in range(N):
    print(JU[i])

Measured memory_bytes: 81884
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 10;
int n, maxx, minn, a[maxn];

int main(int argc, char const *argv[])
{
  scanf("%d", &n), maxx = 0, minn = 1e9;
  for(int i = 1; i <= n; ++i)
    scanf("%d", &a[i]), maxx = max(maxx, a[i]), minn = min(minn, a[i]);
  if( maxx - minn > 1 ) {
    printf("No\n");
  }
  else if( maxx - minn == 0 ) {
    if( 2 * maxx <= n || minn == n - 1 ) printf("Yes\n");
    else printf("No\n");
  }
  else if( maxx - minn == 1 ) {
    int col = 0, x = 0, max_col, min_col, flag = 1;
    for(int i = 1; i <= n; ++i) a[i] == maxx ? ++x : ++col;
    min_col = col + 1, max_col = col + (x >> 1);
    // printf("%d %d\n", max_col, min_col);
    if( min_col > n && max_col < 1 ) flag = flag & 0;
    if( minn + 1 > max_col || minn + 1 < min_col ) flag = flag & 0;
    if( maxx > max_col || maxx < min_col ) flag = flag & 0;
    printf(!flag ? "No\n" : "Yes\n");
  }

  return 0;
}

Measured memory_bytes: 640
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl()
a = [-x for x in a]
heapify(a)
for _ in range(m):
    now = heappop(a)
    now /= 2
    heappush(a,now)
    # print(now)
res = 0
for x in a:
    res += int(-x)
print(res)


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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

int N;
void dfs(string str, char mx) {
    if (str.size() == N) {
        cout << str << '\n';
        return;
    }
    for (char c = 'a'; c <= mx; c++) {
        dfs(str + c, (c == mx ? (mx + 1) : mx));
    }
}


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

    cin >> N;
    dfs("a", 'b');

    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<queue>
using namespace std;
const int MAXW = 100;
const int MAXH = 100;
int map[MAXW][MAXH];
int dist[MAXW][MAXH];
int w,h;

const int BIT_LEFT  = 1 << 0;
const int BIT_RIGHT = 1 << 1;
const int BIT_UP    = 1 << 2;
const int BIT_DOWN  = 1 << 3;

void initMap(){
  for(int i = 0;i < w;i++){
    for(int j = 0;j < h;j++){
      map[i][j] = 0;
      if(i == 0  )map[i][j] |= BIT_LEFT;
      if(i == w-1)map[i][j] |= BIT_RIGHT;
      if(j == 0  )map[i][j] |= BIT_UP;
      if(j == h-1)map[i][j] |= BIT_DOWN;
      dist[i][j] = -1;
    }
  }
}
struct P{
  int x,y;
  P(int x,int y):x(x),y(y){}
};
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0,-1, 1};
int bfs(){
  queue<P> q;
  q.push(P(0,0));
  dist[0][0] = 1;
  while(!q.empty()){
    P current = q.front();q.pop();
    int x = current.x;
    int y = current.y;
    
    if(x == w-1 && y == h-1){
      return dist[x][y];
    }
    for(int i = 0;i < 4;i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      
      if(nx < 0 || ny < 0 || nx >= w || ny >= h)continue;
      if(dist[nx][ny] != -1 && dist[nx][ny] <= dist[x][y] + 1)continue;
      //cout << x << ',' << y << ':' <<map[x][y] << endl;
      if(map[x][y] & (1 << i))continue;
      
      dist[nx][ny] = dist[x][y] + 1;
      q.push(P(nx,ny));
      
    }
  }
  //cout << "error" << endl;
  return 0;
}

int main(){
  while(true){
  cin >> w >> h;
  if(w == 0 && h == 0) break;
  initMap();
  for(int i = 0; i < h; i++){
    for(int j = 0;j < w - 1;j++){
      int d = 0;
      cin >> d;
      if(d == 1){
        map[j][i]   |= BIT_RIGHT;
        map[j+1][i] |= BIT_LEFT;
      }
      //cout << i << ',' << j << ';' << map[j][i] << endl;
    }
    if(i != h-1){
      for(int j = 0;j < w;j++){
        int d = 0;
        cin >> d;
        if(d == 1){
          map[j][i]   |= BIT_DOWN;
          map[j][i+1] |= BIT_UP;
        }
      }
    }
    //cout << "hoge" << endl;
  }
  //cout << "inputEnd" << endl;
  int result = bfs();
  cout << result << endl;
  }
}

Measured memory_bytes: 1236
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

struct Graph {
    struct Edge {
        bool operator>(Edge o) { return d > o.d; }
        int d, i;
    };
    Graph(int n) : e(n), v(n) {}
    void add_edge(int i, int j, int l) {
        e[i].push_back({ l, j });
    }
    void dijkstra(int i) {
        priority_queue<Edge, vector<Edge>, greater<>> q;
        fill(v.begin(), v.end(), 1 << 30);
        q.push({ v[i] = 0, i });
        while (!q.empty()) {
            auto p = q.top(); q.pop();
            if (p.d > v[p.i]) continue;
            for (auto o : e[p.i]) {
                int d = p.d + o.d;
                if (d < v[o.i]) {
                    v[o.i] = d;
                    q.push({ d, o.i });
                }
            }
        }
    }
    vector<vector<Edge>> e;
    vector<int> v;
};

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

    int n, m, R;
    cin >> n >> m >> R;

    vector<int> r(R);
    for (int i = 0; i < R; i++) {
        cin >> r[i];
        r[i]--;
    }

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        g.add_edge(a, b, c);
        g.add_edge(b, a, c);
    }

    int d[8][8] = {};
    for (int i = 0; i < R; i++) {
        g.dijkstra(r[i]);
        for (int j = 0; j < i; j++) {
            d[i][j] = d[j][i] = g.v[r[j]];
        }
    }

    int p[8];
    for (int i = 0; i < R; i++) {
        p[i] = i;
    }
    int s = 1 << 30;
    do {
        int t = 0;
        for (int i = 1; i < R; i++) {
            t += d[p[i]][p[i - 1]];
        }
        s = min(s, t);
    } while (next_permutation(p, p + R));

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 768
/*---> 20 April 2020 <--- > 02:06:32 <---*/
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf (int)1e18+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////
const int N=1e5+5;

int32_t main(){__
	int n,x;
	cin>>n;
	vi ans(n+1);
	for(int i=0;i<n-1;i++){
		cin>>x;
		ans[x]++;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<"\n";
return 0;
}

Measured memory_bytes: 4776
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front

using ll = long long;
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using namespace std;
int digits(int n)
{
    int count = 0;
    while (n > 0)
    {
        n /= 10;
        count++;
    }
    return count;
}
const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll M = 1000000007;
int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    COMinit();
    vector<vector<ll>> used(9, vector<ll>(9));
    FOR(i,1, n+1)
    {
        if (i % 10 != 0)
        {
            cnt++;
            int len = digits(i);
            stringstream ss;
            ss << i;
            string t = ss.str();
            int f = t[0] - '0';
            int e = t[len - 1] - '0';
            used[f - 1][e - 1]++;
        }
    }
    ll ans = 0;
    rep(i, 9)
    {
        FOR(j, 0, 9)
        {
            
            ans += used[i][j] * used[j][i];
           
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 12160
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>

//#include<bits/stdc++.h>


using namespace std;
int main() {

	string a, b;
	int n, m;
	cin >> a >> b;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	reverse(b.begin(), b.end());
//	cout << a << "#" << b;
	if (a < b)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

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

int main(){
    string s;
    ll k;
    cin >> s >> k;
    ll one = -1;
    rep(i, 0, s.size()){
        if(s[i] == '1') one = i;
        else break;
    }
    if(k-1 <= one) cout << 1 << endl;
    else cout << s[one+1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
   int n,i,a[200000];
   long all,c[200000];

   scanf("%d",&n);
   for (i=0;i<n;i++) {
      scanf("%d",&a[i]);
      c[i+1]=0;
   }
   for (i=0;i<n;i++) c[a[i]]++;
   all=0;
   for (i=1;i<=n;i++) all+=c[i]*(c[i]-1)/2;
   for (i=0;i<n;i++) printf("%ld\n",all-c[a[i]]+1);
   return 0;
}


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

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

int main(){
    ll n;   cin >> n;
    ll ans=1, mod=1e+9;
    for(ll i=1; i<=n; i++)
        ans = ans*i%(mod+7);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string S;
    cin >> S;
    int value = atoi(S.c_str());
    int a = value/100;
    int b = value%100;
    
    if(a == 0 || a > 12){
        if(b == 0 || b > 12){
            printf("NA\n");
        }else{
            printf("YYMM\n");
        }
    }else{
        if(b == 0 || b > 12){
            printf("MMYY\n");
        }else{
            printf("AMBIGUOUS\n");
        }
    }
    return 0;
}

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

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

    int len = s.size();

    vector<int> alpha(26, 0);
    for (int i = 0; i < len; i++)
    {
        alpha[s[i] - 97]++;
    }

    int spec = 0;
    for (int i = 0; i < 26; i++)
    {
        if (alpha[i] > 0)
            spec++;
    }
    if (spec == 1)
    {
        cout << 0 << endl;
        return 0;
    }

    int operation = len;
    for (int a = 0; a < 26; a++)
    {
        string baseStr = s;
        for (int l = len - 1; l > 1; l--)
        {
            string newStr;
            newStr.resize(l);
            for (int i = 0; i < l; i++)
            {
                if (baseStr[i] - 97 == a)
                {
                    newStr[i] = baseStr[i];
                }
                else if (baseStr[i + 1] - 97 == a)
                {
                    newStr[i] = baseStr[i + 1];
                }
                else
                {
                    if (i % 2 == 0)
                    {
                        newStr[i] = baseStr[i + 1];
                    }
                    else
                    {
                        newStr[i] = baseStr[i];
                    }
                }
            }
            baseStr = newStr;
            for (int i = 0; i < 26; i++)
            {
                alpha[i] = 0;
            }

            for (int i = 0; i < len; i++)
            {
                alpha[baseStr[i] - 97]++;
            }

            int spec = 0;
            for (int i = 0; i < 26; i++)
            {
                if (alpha[i] > 0)
                    spec++;
            }
            if (spec == 1)
            {
                break;
            }
        }
        
        int op = s.size() - baseStr.size();
        if(op < operation) operation = op;
    }

    cout << operation << endl;

    return 0;
}


Measured memory_bytes: 3596
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>	
#include <cmath>
#include <string>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define Cout(s) cout<<s<<endl
using namespace std;
typedef long long ll;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }



ll a = 1, b = 0, c, d, n, k = 0, ans = 0;
string s, t;

int main()
{
	cin >> a >> b >> c >> d;
	ll C = b / c - (a - 1) / c;
	ll D = b / d - (a - 1) / d;
	ll CD = b / lcm(c, d) - (a - 1) / lcm(c, d);
	cout << b - a + 1 - C - D + CD << endl;

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
typedef long long lld;
const int MAXN = 2e5+5;
int A[MAXN];
int F[MAXN];
lld K;
int N;

bool f(lld x) {
    lld sum = 0LL;
    for (int i = 0; i < N; ++i) {
        lld prod = 1LL * A[i] * F[i];
        if (prod > x) {
            lld B = x / F[i];
            sum += (A[i] - B);
            if (sum > K) {
                return false;
            }
        }
    }
    return (sum <= K);
}

int main() {
    scanf(" %d%lld", &N, &K);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d", &F[i]);
    }
    std::sort(A, A+N);
    std::sort(F, F+N, std::greater<int>());
    lld lo = 0;
    lld hi = 0;
    for (int i = 0; i < N; ++i) {
        hi = std::max(1LL * A[i] * F[i], hi);
    }
    while (lo < hi) {
        lld x = (lo + hi) / 2;
        if (f(x)) {
            hi = x;
        } else {
            lo = x + 1;
        }
    }
    printf("%lld\n", lo);
    return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>

int main() {
    int a[26];
    for (int i = 0; i < 26; i++)
        a[i] = 0;
    
    char str[100001];
    scanf("%s", str);

    for (int i = 0; str[i]; i++)
        if (a[str[i] - 'a'] == 0)
            a[str[i] - 'a']++;

    int i;
    for (i = 0; i < 26; i++)
        if (a[i] == 0)
            break;
        
    if (i != 26)
        printf("%c", i + 'a');
    else
        printf("None");

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using ll = long long int;
long long int mod = 1e9 + 7;
ll primesum[100010];

void fillprimesum()
{
    int n = 1e5;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2*i; j <= n; j += i)
        {
            primesum[j] += i-primesum[i];
        }
    }
}

long long int binpow(long long int a, long long int b)
{
    ll ans = 1;
    b %= mod;
    for (; b > 0; b >>= 1)
    {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
    }

    return ans;
}

int main()
{
    long long int ans = 0;
    long long int n, k;
    std::cin >> n >> k;

    ll dp[100010] = { 0 };
    for (ll i = k; i >= 1; --i)
    {
        dp[i] = binpow(k/i, n) % mod;
        for (ll j = i + i; j <= k; j += i)
        {
            dp[i] -= dp[j];
            dp[i] += mod;
            dp[i] %= mod;
        }
        ans += (i * dp[i]) % mod;
        ans %= mod;
    }

//    for (ll i = 1; i <= k; ++i)
//    {
//        ll left = i - primesum[i];
//        ans += ((left * binpow(k/i, n)) % mod);
//        ans %= mod;
//    }

    std::cout << ans;
}


Measured memory_bytes: 4408
#include <cstdint>
#include <vector>

using namespace std;

size_t binary_search(uint32_t array[], size_t size, uint32_t v)
{
  uint32_t lindex = 0;
  uint32_t rindex = size;

  while (lindex < rindex) {
    uint32_t half = (lindex + rindex) / 2;
    uint32_t pivot = array[half];
    if (v == pivot)
      return true;
    else if (v < pivot)
      rindex = half;
    else
      lindex = half + 1;
  }
  return false;
}

#if !defined(TEST)
#include <iostream>

static vector<uint32_t> s, t;

int32_t main(void)
{
  uint32_t n, m;
  cin >> n;
  for (uint32_t i = 0; i < n; i++) {
    uint32_t val;
    cin >> val;
    s.push_back(val);
  }

  uint32_t cnt = 0;

  cin >> m;
  for (uint32_t i = 0; i < m; i++) {
    uint32_t val;
    cin >> val;
    if (binary_search(&s[0], s.size(), val)) {
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}
#endif

Measured memory_bytes: 3420
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> mp[200001];
vector<long long> dp[3][200001];
int cntd[200001];
void dfs(int k,int d)
{
	++cntd[d];
	int pos=0;
	for (size_t i=0;i<mp[k].size();++i)
	{
		int u=mp[k][i];
		dfs(u,d+1);
		if (int(dp[0][u].size())>int(dp[0][k].size()))
		{
			dp[0][k].swap(dp[0][u]);
			dp[1][k].swap(dp[1][u]);
			dp[2][k].swap(dp[2][u]);
		}
		pos=max(pos,int(dp[0][u].size()));
		for (int p1=int(dp[0][k].size())-1,p2=int(dp[0][u].size())-1;p2>=0;--p1,--p2)
		{
			long long tot=((dp[0][k][p1]+dp[1][k][p1]+dp[2][k][p1])%1000000007)*(dp[0][u][p2]+dp[1][u][p2]+dp[2][u][p2]);
			dp[1][k][p1]=(dp[1][k][p1]*dp[0][u][p2]+dp[0][k][p1]*dp[1][u][p2])%1000000007;
			(dp[0][k][p1]*=dp[0][u][p2])%=1000000007;
			dp[2][k][p1]=(tot-dp[0][k][p1]-dp[1][k][p1])%1000000007;
			if (dp[2][k][p1]<0)
				dp[2][k][p1]+=1000000007;
		}
		dp[2][u]=dp[1][u]=dp[0][u]=vector<long long>();
	}
	for (size_t i=dp[0][k].size()-pos;i<dp[0][k].size();++i)
	{
		(dp[0][k][i]+=dp[2][k][i])%=1000000007;
		dp[2][k][i]=0;
	}
	dp[0][k].push_back(1);
	dp[1][k].push_back(1);
	dp[2][k].push_back(0);
}
int pw2[200001];
int main()
{
	int n;
	scanf("%d",&n);
	pw2[0]=1;
	for (int i=1;i<=n;++i)
	{
		int p;
		scanf("%d",&p);
		mp[p].push_back(i);
		pw2[i]=(pw2[i-1]*2)%1000000007;
	}
	dfs(0,0);
	long long ans=0;
	for (int i=int(dp[1][0].size())-1,j=0;i>=0;--i,++j)
		(ans+=dp[1][0][i]*pw2[n-cntd[j]+1])%=1000000007;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 69080
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using namespace std;
//LLONG_MAX = 90^18
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No"); }
void Yes() { cout << "Yes"; }
void No() { cout << "No"; }


int L;
int A;

//---------- にぶたん ----------
bool isOK(int index)
{
	double a1 = A / 1000.0;
	double b1 = index / 1000.0;
	double c1 = L - a1 - b1;

	double a2 = A / 1000.0;
	double b2 = (index + 0.0001) / 1000.0;
	double c2 = L - a2 - b2;

	double s1 = a1 * b1 * c1;
	double s2 = a2 * b2 * c2;

	if (s1 > s2)
	{
		return true;
	}

	return false;
}

int binary_search(int n)
{
	int left = -1;
	int right = n;
	while (right - left > 1)
	{
		int mid = left + (right - left) / 2;
		if (isOK(mid))
			right = mid;
		else
			left = mid;
	}
	return right;
}


signed main()
{
	cin >> L;

	double ma = 0;
	for (int i = 0; i < L * 1000; i++)
	{
		A = i;
		int B = binary_search(L * 1000);
		double a = A / 1000.0;
		double b = B / 1000.0;
		double c = L - a - b;
		double S = a * b * c;
		ma = max(ma, S);
	}
	cout << fixed << setprecision(10);
	cout << ma << endl;
}




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

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

int main() {
    LL n, x, d;
    cin >> n >> x >> d;

    if ( d==0 ) {
        if ( x==0 ) {
            cout << 1 << '\n';
        } else {
            cout << n+1 << '\n';
        }
        return 0;
    }

    if ( d<0 ) {
        d=-d; x=-x;
    }

    map<LL,vector<P>> mp;
    for ( int k=0; k<=n; k++ ) {
        LL s=k*x;
        LL l=(LL)k*(k-1)/2;  // 0+1+..+k-1
        LL r=l+(n-k)*k;      // (n-k)+..+n-1
        mp[(s%d+d)%d].emplace_back(s/d+l,s/d+r+1);
    }

    LL ans=0;
    for ( auto &p:mp ) {
        auto v=p.second;
        sort(v.begin(),v.end());
        LL now=-1e18;
        for ( int i=0; i<v.size(); i++ ) {
            LL l=v[i].first, r=v[i].second;
            if ( l>=now ) {
                ans+=r-l;
                now=r;
            } else if ( r>=now ) {
                ans+=r-now;
                now=r;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}













Measured memory_bytes: 22144
N, C = map(int, input().split())
MAX = 10**5
s_list = [[] for _ in range(MAX+1)]
t_list = [[] for _ in range(MAX+1)]
for _ in range(N):
  s, t, c = map(int, input().split())
  s_list[s].append(c)
  t_list[t].append(c)
cnt = 0
ans = 0
before = 0
for i in range(MAX+1):
  if before != 0:
    cnt -= before
    before = 0
  for s in s_list[i]:
    cnt += 1
  for t in t_list[i]:
    if not t in s_list[i]:
      before +=1
    cnt -= 1
  cnt += before
  ans = max(ans, cnt)
print(ans)

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

#define SENTINEL (1<<30)

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

int Merge_Sort(int *A, int left, int right) {
  int cnt = 0;
  int mid;
  if(left+1 < right) {
    mid = (left + right)/2;
    cnt += Merge_Sort(A, left, mid);
    cnt += Merge_Sort(A, mid, right);
    cnt += Merge(A, left, mid, right);
  }
  return cnt;
}

int main() {
  int i;
  int n, A[500000], cnt;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) {
    scanf("%d", A+i);
  }
  cnt = Merge_Sort(A,0,n);
  for(i = 0; i < n; ++i) {
    printf(i ? " %d" : "%d", A[i]);
  }
  printf("\n%d\n", cnt);
  return 0;
}

Measured memory_bytes: 2988
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    long k = sc.nextLong();
    long ans = 0;
    for(long b=1;b<=n;b++){
      long p = 0;
      long r = n;
      while(r>=b){
        p++;
        r-=b;
      }
      ans+=p*Math.max(b-k,0)+Math.max(0,r-k+1);
    }
    if(k==0)ans-=n;
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;


int main(void){
    int n;
    cin >> n;
    vector< pair<int,int> > a(n-1),b(n-1);
    vector<int> color(n,0);
    vector<int> dotcolor(n,0);
    map<pair<int,int>,int> I;
    int maxcolor=0;
    int l,r;
    for(int i=0; i<n-1; i++){
        cin >> l >> r;
        a[i]=make_pair(l-1,r-1);
        b[i]=make_pair(l-1,r-1);
    }
    sort(a.begin(), a.end());
    int colorcount=0;
    int prevdot=0;
    for(int i=0; i<n-1; i++){
        l=a[i].first;r=a[i].second;
        if(prevdot!=l)colorcount=1;
        prevdot=l;
        if(dotcolor[l]==colorcount){
            colorcount++;
            dotcolor[r]=colorcount;
            color[i]=colorcount;
        }else {
            dotcolor[r]=colorcount;
            color[i]=colorcount;
        }
        maxcolor=max(maxcolor,color[i]);
        I[make_pair(l,r)]=color[i];
        colorcount++;
    }


    cout << maxcolor << endl;
    for(int i=0; i<n-1; i++){
        cout << I[b[i]] << endl;
    }
    return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   string str;
   cin>>str;
   str[5]=' ';
   str[13]=' ';
   cout<<str;
   
    return 0;
}








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

int main(){
    int N;
    int vmin,vmax;
    cin >> N;
    vector<int> l(N);
    //入力
    for(int i = 0; i < N; i++){
        cin >> l.at(i);
    }
    vmin = l.at(0);
    vmax = l.at(0);
    for(int i = 0; i < N; i++){
        if(vmin > l.at(i)){
            vmin = l.at(i);
        }
        else if(vmax < l.at(i)){
            vmax = l.at(i);
        }
    }
    cout << vmax - vmin << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
S = [input() for i in range(n)]

min_cnt = [50]*26

for i in range(n):
  word = [0]*26
  for j in range(len(S[i])):
    word[ord(S[i][j])-ord("a")] += 1
  for j in range(26):
    min_cnt[j] = min(min_cnt[j],word[j])
str = ""
for i in range(26):
  for j in range(min_cnt[i]):
    str += chr(i+ord("a"))
print(str)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n,k,y;
    long long ans=0;
    cin >> n;
    vector<int> a(n-1),b(n-1),m(n+1),c(n),p(n),o(n+1);
    vector<vector<int>> d(n+1,vector<int>(0));
    queue<int> q;

    for (int i=0;i<n-1;i++){
        cin >> a.at(i) >> b.at(i);
        d.at(a.at(i)).push_back(i);
        d.at(b.at(i)).push_back(i);
        p.at(i+1)=0;
    }
    for (int i=0;i<n;i++){
        cin >> c.at(i);
        if (d.at(i+1).size()==1) q.push(i+1);
        p.at(i)=d.at(i+1).size();
    }
    sort(c.begin(),c.end());
    for (int i=0;i<n-1;i++){
        int u=q.front();

        q.pop();
        m.at(u)=c.at(i);
        for (int i=0;i<d.at(u).size();i++){
            if (o.at(a.at(d.at(u).at(i)))==0 && o.at(b.at(d.at(u).at(i)))==0) y=i;
        }
        o.at(u)=1;
        if (a.at(d.at(u).at(y))==u) k=b.at(d.at(u).at(y));
        if (b.at(d.at(u).at(y))==u) k=a.at(d.at(u).at(y));
        p.at(k-1)--;
        if (p.at(k-1)==1) q.push(k);
        ans=ans+c.at(i);
    }
    m.at(k)=c.at(n-1);
    cout << ans << endl;
    cout << m.at(1);
    for (int i=2;i<n+1;i++){
        cout << " " << m.at(i);
    }
    cout << endl;
}


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

typedef long long int LL;
typedef pair<LL, LL> PLL;


int main(int argc, char *argv[]) {
  LL N, C;
  cin >> N >> C;
  N+=2;
  vector<PLL> sushi(N);
  sushi[0].first = sushi[0].second = 0;
  sushi[1].first = C;
  sushi[1].second = 0;
  for (int i = 2; i < N; ++i) {
    cin >> sushi[i].first >> sushi[i].second;
  }
  sort(sushi.begin(), sushi.end());

  // Sum of all calories going counter-clockwise.
  vector<LL> acum_ccw(N);
  LL acum = 0;

  // Best result up to i if going ccw once.
  vector<LL> best_ccw(N);
  LL best = 0;

  // Best result up to i if going ccw and back.
  vector<LL> best_ccw_back(N);
  LL best_back = 0;

  for (int i = N - 1; i >= 0; i--) {
    acum += sushi[i].second;
    acum_ccw[i] = acum;
    LL cost = C - sushi[i].first;

    LL benefit = acum_ccw[i] - cost;
    LL benefit_back = acum_ccw[i] - 2 * cost;
    if (i == N - 1) {
      best = benefit;
      best_back = benefit_back;
      best_ccw[i] = best_ccw_back[i] = i;
      continue;
    }
    best_ccw[i] = best_ccw[i + 1];
    best_ccw_back[i] = best_ccw_back[i + 1];

    if (benefit > best) {
      best = benefit;
      best_ccw[i] = i;
    }

    if (benefit_back > best_back) {
      best_back = benefit_back;
      best_ccw_back[i] = i;
    }
  }

  best = 0;
  LL benefit_cw = 0;
  for (int i = 0; i < N-1; ++i) {
    LL walk_cw = sushi[i].first;
    benefit_cw += sushi[i].second;
    LL benefit_one_dir = benefit_cw - walk_cw;
    best = max(best, benefit_one_dir);

    
    LL pos_ccw = best_ccw[i + 1];
    LL walk_ccw = C - sushi[pos_ccw].first;
    LL benefit_ccw = acum_ccw[pos_ccw];
    LL benefit_two_dir = benefit_one_dir + benefit_ccw - walk_ccw - walk_cw;
    best = max(best, benefit_two_dir);

    LL pos_ccw_back = best_ccw_back[i + 1];
    LL walk_ccw_back = C - sushi[pos_ccw_back].first;
    LL benefit_ccw_back = acum_ccw[pos_ccw_back];
    LL benefit_two_dir_back = benefit_one_dir + benefit_ccw_back - 2*walk_ccw_back;
    best = max(best, benefit_two_dir_back);
  }

  cout << best << endl;
  return EXIT_SUCCESS;
}

Measured memory_bytes: 4224
from sys import stdin
import random

#a , b = 81,79
#x = a**5 - b**5
'''
while x < 1 or x > 10**9:
    a = random.randint(-100, 100)
    b = random.randint(-100, 100)
    x = a**5 - b**5
'''
#print(a,b,x)
x = int(stdin.readline().rstrip())

fivelist = []

i = 0
while True:
    n = i**5
    # print(i,n)
    if n > 2*(10**15):
        break
    fivelist.append(n)
    i += 1


a = 0
b = 0
ans = False
for i in range(len(fivelist)):
    for j in range(len(fivelist)):
        if x == (fivelist[i] - fivelist[j]):
            a, b = i, j
            ans = True
            break
        if x == (-fivelist[i] - fivelist[j]):
            a, b = -i, j
            ans = True
            break
        if x == (fivelist[i] + fivelist[j]):
            a, b = i, -j
            ans = True
            break
        if x == (-fivelist[i] + fivelist[j]):
            a, b = -i, -j
            ans = True
            break
    if ans:
        break

print("{} {}".format(a, b))


Measured memory_bytes: 76928
s = input()
 
def dfs( i,  f ):
    if i == len( s ) - 1:
        return sum( list( map( int, f.split( "+" ))))
    return dfs( i + 1, f + s[ i  + 1 ] ) + dfs( i + 1, f +  "+" + s[  i   + 1 ])
print( dfs( 0, s[ 0 ]) ) 


Measured memory_bytes: 3060