akhauriyash/Code-Regression huggingface dataset:
//2014_q5.cpp (2014/11/09-)

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

#define T_MAX 5000
#define INF 100000000

struct TAXI{
    int cost;
    int road;
    int dji;
    bool kaku;
    vector<int> vec1,vec2;
    TAXI(){
        kaku=false;
        dji=INF;
    };
} taxi[T_MAX];

int main(){
    int n,k,wa,wb,p,co,ro;
    
    scanf("%d%d",&n,&k);
    
    for(int i=0;i<n;i++)
        scanf("%d%d",&taxi[i].cost,&taxi[i].road);
    
    for(int i=0;i<k;i++){
        scanf("%d%d",&wa,&wb);
        taxi[wa-1].vec1.push_back(wb-1);
        taxi[wb-1].vec1.push_back(wa-1);
    }
    
    //graph
    for(int i=0;i<n;i++){
        queue<int> haba;
        
        for(int j=0;j<taxi[i].vec1.size();j++){
            haba.push(taxi[i].vec1[j]);
            taxi[taxi[i].vec1[j]].kaku=true;
        }
        
        for(int j=1;j<taxi[i].road;j++){
            haba.push(-1);
            while(haba.front()!=-1){
                p=haba.front(); haba.pop();
                
                for(int l=0;l<taxi[p].vec1.size();l++)
                    if(taxi[taxi[p].vec1[l]].kaku==false){
                        haba.push(taxi[p].vec1[l]);
                        taxi[taxi[p].vec1[l]].kaku=true;
                    }
            }
            haba.pop();
        }
        for(int j=0;j<n;j++)
            if(taxi[j].kaku==true){
                taxi[i].vec2.push_back(j);
                taxi[j].kaku=false;
            }
    }

    
    //dikject
    priority_queue< pair<int,int> > pq;
    pair<int,int> a;
    pq.push(make_pair(0,0));
    
    while(1){
        a = pq.top();
        pq.pop();
        co = -1*a.first;
        ro = a.second;
        
        if(ro==n-1) break;
        
        if(taxi[ro].kaku==false){
            
            taxi[ro].kaku=true;
            taxi[ro].dji=co;
        
            for(int i=0;i<taxi[ro].vec2.size();i++)
                if(taxi[taxi[ro].vec2[i]].kaku==false){
                    pq.push(make_pair(-1*(co+taxi[ro].cost),taxi[ro].vec2[i]));
                }
        }
        
    }
    
    printf("%d\n",co);
    return 0;
}

Measured memory_bytes: 69624
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	c := Scanner()
	if c == "a" || c == "i" || c == "u" || c == "e" || c == "o" {
		fmt.Println("vowel")
	} else {
		fmt.Println("consonant")
	}
}


Measured memory_bytes: 1776
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;

vector<bool> eratosthenes(int n) {
	vector<bool> prime(n + 1);
	for (int i = 2; i <= n; i++) {
		prime[i] = true; // 初期化
	}
	prime[0] = prime[1] = false;
	for (int i = 2; i*i <= n;i++) {
		if (prime[i]) {
			for (int j = i * 2; j <= n; j += i) {
				prime[j] = false;
			}
		}
	}
	return prime;
}
int n, m,p[10], ans = 0,a[29], b[29];
const int nmax = 8;
bool graph[nmax][nmax];
/**
 * pos個は決定済み
 * mask 残に置く数の集合を表すビット配列
 */
void dfs(int pos, int mask) {
//	cout << "pos=" << pos << ",mask=" << mask << endl;
	if (pos == n) { // posが最後までいった
//		cout << p[0] << p[1] << p[2] << endl;
		return;
	}
	REP(i, n) {
		if (mask  & (1 << i)) { // 残の中にiが残っている場合
//			cout << "mask=" << mask << ",1<<" << i << "="  << (1 << i) << "=true" << endl;
			p[pos] = i; // 配列のPOS位置を0～nまでループ
			if (p[0] != 0)continue;
			if (pos > 0 && graph[p[pos - 1]][p[pos]] == false) {
				//				cout << "pos=" << pos << "," << p[0] << p[1] << p[2] << ",graph[" << p[pos - 1] << "][" << p[pos] << "]=false" << endl;
				continue;
			}
			dfs(pos + 1, (mask ^ (1 << i))); // 配列のPOS位置を進める,排他的論理和でフラグを下ろす
		}
		else {
//			cout << "mask=" << mask << ",1<<" << i << "=" << (1 << i) << "=false" << endl;
		}
	}
}
/*int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	scanf("%d %d", &n ,&m);

	REP(i, m) {
		scanf("%d %d",&a[i], &b[i]);
		p[i] = i;
		graph[a[i] - 1][b[i] - 1] = graph[b[i] - 1][a[i] - 1] = true;
	}

	dfs(0, (1 << n) - 1);
	cout << ans << endl;
	return 0;
}*/
/**
 * v 現在の頂点
 */
int dfs(int v, int n, bool visited[]) {
	bool all_visited = true; // 全頂点を訪問済
	REP(i, n) {
		if(!visited[i])all_visited = false;
	}
	if (all_visited)return 1; //答を1増やす
	int ret = 0;
	REP(i, n) { //頂点i:頂点vに隣接、且つ、未訪問
		if (!graph[v][i])continue;
		if(visited[i])continue;

		visited[i] = true;
		ret += dfs(i, n, visited);
		visited[i] = false;
	}
	return ret;
}
int main() {
	scanf("%d %d", &n, &m);

	REP(i,m) {
		scanf("%d %d", &a[i], &b[i]);
		graph[a[i] - 1][b[i] - 1] = graph[b[i] - 1][a[i] - 1] = true;
	}
	
	bool visited[nmax];
	REP(i, n)visited[i] = false;
	
	visited[0] = true;
	ans = dfs(0, n, visited);
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 3005;
const int mod = 1000000007;
int n,m,a[N],f[N][N],ans;
int main(){
	n=gi();m=gi();
	for (int i=1;i<=n;++i) a[i]=gi();
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			f[i][j]=(a[i]<a[j]);
	for (int t=1;t<=m;++t){
		int x=gi(),y=gi();
		for (int i=1;i<=n;++i)
			if (i!=x&&i!=y){
				f[i][x]=f[i][y]=500000004ll*(f[i][x]+f[i][y])%mod;
				f[x][i]=f[y][i]=500000004ll*(f[x][i]+f[y][i])%mod;
			}
		f[x][y]=f[y][x]=500000004ll*(f[x][y]+f[y][x])%mod;
	}
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
			ans=(ans+f[j][i])%mod;
	for (int i=1;i<=m;++i) ans=(ans<<1)%mod;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); };
template<typename T> void OUT(T && a) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

int main() {
	IN(int, n);
	vector<vector<int>> g(n);
	inc(i, n - 1) {
		IN(int, a, b);
		a--; b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	
	function<int(int, int)> dfs = [&](int v, int p) {
		int x = 0;
		RF(e, g[v]) {
			if(e == p) { continue; }
			x ^= dfs(e, v) + 1;
		}
		return x;
	};
	
	OUT(dfs(0, -1) == 0 ? "Bob" : "Alice");
}


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

int main() {
  ll N,K;
    ll S =0;
    cin >> N >> K;
  vector<ll> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H.at(i);
  }
  sort(H.begin(), H.end());
  N -= K;
  int i = 0; // カウンタ変数
while (i < N) {
 S += H[i] ;
  i++; 
}
  cout << S << endl;
}

Measured memory_bytes: 1792
a,b,c,d,e,f= map(int, input().split())
youeki=0
yousitu=0
noudo=0
n_a=int(f/(100*a))


for i in range(1+n_a):
 for j in range(1+int((f-100*i*a)/(100*b))):
  for k in range(1+int((f-100*i*a-100*j*b)/c)):
   for l in range(1+int((f-100*i*a-100*j*b-k*c)/d)):
    S=100.0*a*i+100.0*b*j+c*k+d*l
    T=c*k+d*l
    if S!=0:
     L=100.0*T/S
     if S<=f and L<=100*e/(100+e) and L>=noudo:
      noudo=L
      youeki=S
      yousitu=T
print(int(youeki),int(yousitu))

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

int main() {
    string s, t, u;
    cin >> s >> t;
    int ns = s.size(), nt = t.size();
    u = s;
    rep(i, ns) if (u[i] == '?') u[i] = 'a';

    vector<string> matches;
    rep(i, ns - nt + 1) {
        string a = s.substr(i, nt);
        bool ok = true;
        rep(j, nt) if (a[j] != '?' && a[j] != t[j]) ok = false;

        if (ok) matches.push_back(u.substr(0, i) + t + u.substr(i + nt));
    }

    if (matches.size() == 0)
        cout << "UNRESTORABLE" << endl;
    else {
        sort(matches.begin(), matches.end());
        cout << matches[0] << endl;
    }
    return 0;
}


Measured memory_bytes: 3644
h, w = map(int, input().split())

board = ['.'*(w+2)]

for i in range(h):
    line = input()
    board.append('.' + line + '.')
board.append('.'*(w+2))

new_board = []

for y in range(1,h+1):
    temp_text = ''

    for x in range(1, w+1):
        if board[y][x] == '#':
            temp_text = temp_text + '#'

        else:
            check_text = board[y-1][x-1:x+2] + board[y][x-1:x+2] + board[y+1][x-1:x+2]
            bomb_count = check_text.count('#')
            temp_text = temp_text + str(bomb_count)

    new_board.append(temp_text)

for text in new_board:
    print(text)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

ll lcm(ll a, ll b) {
	ll c;
	c = a * b / gcd(a, b);
	return c;
}

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;


map<string, int> memo;

using P=pair<int, int>;




/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}
ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}
//E869120 
void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}


int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int ans = max({a*10+b+c,a+b*10+c,a+b+c*10});
	cout << ans;
	return 0;
}













Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <utility>
using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i > b; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)

const int kMaxN = 100000;
const int kMaxK = 1000;

int N, K;
int x[kMaxN], y[kMaxN];
char c[kMaxN];
int ans = 0;

int grid[2*kMaxK+1][2*kMaxK+1];

int main() {
  cin >> N >> K;
  REP(i, N) { cin >> x[i] >> y[i] >> c[i]; }

  REP(i, N) {
    if (c[i] == 'W') { x[i] += K; }
    x[i] %= 2*K;
    y[i] %= 2*K;
  }

  REP(i, N) {
    if (x[i] >= K && y[i] >= K) {
      x[i] -= K;
      y[i] -= K;
    }
    if (x[i] < K && y[i] < K) {
      grid[0][0] += 1;
      grid[x[i]+1][0] -= 1;
      grid[x[i]+1+K][0] += 1;
      grid[0][y[i]+1] -= 1;
      grid[x[i]+1][y[i]+1] += 2;
      grid[x[i]+1+K][y[i]+1] -= 2;
      grid[0][y[i]+1+K] += 1;
      grid[x[i]+1][y[i]+1+K] -= 2;
      grid[x[i]+1+K][y[i]+1+K] += 2;
    }
    if (x[i] < K && y[i] >= K) {
      x[i] += K;
      y[i] -= K;
    }
    if (x[i] >= K && y[i] < K) {
      grid[x[i]-K+1][0] += 1;
      grid[x[i]+1][0] -= 1;
      grid[0][y[i]+1] += 1;
      grid[x[i]-K+1][y[i]+1] -= 2;
      grid[x[i]+1][y[i]+1] += 2;
      grid[0][y[i]+K+1] -= 1;
      grid[x[i]-K+1][y[i]+K+1] += 2;
      grid[x[i]+1][y[i]+K+1] -= 2;
    }
  }
  REP(j, 2*K+1) { FOR(i, 1, 2*K+1) { grid[i][j] += grid[i-1][j]; } }
  REP(i, 2*K+1) { FOR(j, 1, 2*K+1) { grid[i][j] += grid[i][j-1]; } }
  REP(i, 2*K) { REP(j, 2*K) { ans = max(ans, grid[i][j]); } }

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


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

using namespace std;

using ll = long long;
using vi = vector<int>;
using db = double;
#define pb push_back
#define fir first
#define sec second

// 有趣又有难度的构造题

const int mxn = 100006;

int n;
int ra, rb;
vi ea[mxn], eb[mxn];
vi s[mxn];

void input(vi *e, int &r) {
	for (int i = 1; i <= n; ++i) {
		int p;
		scanf("%d", &p);
		if (p == -1)
			r = i;
		else
			e[p].pb(i);
	}
}

int w[mxn];
vi e[mxn];

void add(int x, int y) {
	e[x].pb(y);
	e[y].pb(x);
}

bool odd(int x) {
	return ea[x].size() % 2 == 0;
}

void dfs(vi *e, int x) {
	for (auto i : e[x]) {
		dfs(e, i);
		if (!s[i].empty()) {
			s[x].pb(s[i].back());
			s[i] = {};
		}
	}
	if (odd(x))
		s[x].pb(x);
	while (s[x].size() >= 2) {
		add(s[x].back(), *next(s[x].rbegin()));
		s[x].pop_back();
		s[x].pop_back();
	}
}

void draw(int x, int c) {
	if (w[x]) return;
	w[x] = c;
	for (auto i : e[x])
		draw(i, c * -1);
}

int main() {
	#define ass(x) ({if(!(x)){puts("IMPOSSIBLE"); return 0;}})
	cin >> n;
	
	input(ea, ra);
	input(eb, rb);
	
	for (int i = 1; i <= n; ++i)
		ass(ea[i].size() % 2 == eb[i].size() % 2);
	
	dfs(ea, ra);
	for (int i = 1; i <= n; ++i)
		s[i] = {};
	dfs(eb, rb);
	
	for (int i = 1; i <= n; ++i) if (!w[i] && odd(i))
		draw(i, +1);
	
	puts("POSSIBLE");
	for (int i = 1; i <= n; ++i)
		printf("%d ", w[i]);
	puts("");
	
	return 0;
}


Measured memory_bytes: 21760
#include<iostream>
using namespace std;
int main(){
  double v;
  while(cin>>v){
    double t,y;
    t=v/9.8;
    y=4.9*t*t;
    y=(y+5.0)/5.0;
    if(y-(int)y!=0) y+=1;
    cout<<(int)y<<endl;
  }
}

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

int main() {
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    int X, Y; cin >> X >> Y;
    string board[60];
    rep(i, 0, X) {
        cin >> board[i];
    }
    rep(i, 0, X) {
        rep(j, 0, Y) {
            if (board[i][j] == '.') {
                int cnt = 0;
                rep(k, 0, 8) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x >= 0 && x < X && y >= 0 && y < Y && board[x][y] == '#') {
                        cnt++;
                    }
                }
                board[i][j] = '0' + cnt;
            }
        }
    }
    rep(i, 0, X) {
        cout << board[i] << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef long long int ll;

double func(double a,double b,double t,double v){
	if(a<=t&&t<=b)return v;
	if(t<a)return v+(a-t);
	return v+(t-b);
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<double> t(n+1,0),v(n);
	for(int i=0;i<n;i++){
		cin >> t[i+1];
		t[i+1]+=t[i];
	}
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	vector<double> s(t[n]*2+1);
	int j=0;
	for(double tt=0;tt<=t[n];tt+=0.5){
		double vv=1e9;
		for(int i=0;i<n;i++){
			vv=min(vv,func(t[i],t[i+1],tt,v[i]));
		}
		vv=min(vv,tt);
		vv=min(vv,t[n]-tt);
		s[j]=vv;
		j++;
	}
	double ans=0;
	for(int i=1;i<=2*t[n];i++){
		ans+=0.25*(s[i-1]+s[i]);
	}
	printf("%.8f\n",ans);
}
 

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int N;
  std::vector<int> v;
  std::cin >> N;
  for(int i = 0 ; i < N ; i++){
    int temp;
    std::cin >> temp;
    v.push_back(temp);
  }
  std::sort(v.begin(), v.end());

  double resa = 0;
  double ave = v[0];
  for(int i = 0 ; i < (int)v.size() - 1 ; i++){
    ave = (ave + v[i+1]) / 2.0;
  }

  std::cout << ave << std::endl;
  return 0;
}

Measured memory_bytes: 3820
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector1d(type,name,...) vector<type>name(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll updivide(ll a,ll b){if(b==1) return a;else if(a%b==0) return a/b;else return (a/b)+1;}

int num(string s,string t){
    int counter=0;
    for(int i=0;i<s.length();i++){
        counter+=(s[i]!=t[i]);
    }
    return counter;
}

int main(){
    string s,t;
    cin>>s>>t;
    int ans=t.length();
    for(int i=0;i<s.length()-t.length()+1;i++){
        ans=min(ans,num(s.substr(i,t.length()),t));
    }
    out(ans);
}

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

int main(){
  int x, y, s;
  int max, ss;
  while(cin >> x >> y >> s && !(x==0 && y==0 && s==0)){
    max=0;
    for(int i=1;i<s;i++){
      for(int j=1;j<s;j++){
	if(i*(100+x)/100+j*(100+x)/100==s){
	  ss=i*(100+y)/100+j*(100+y)/100;
	  if(max<ss) max=ss;
	}
      }
    }

    cout << max << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3108
using System;

    class Program
    {
        static void Main()
        {
            while (true)
            {
                int[] num = TypeConverter.arrayStrToInt(Console.ReadLine().Split(' '));

                if (num[0] == 0 && num[1] == 0)
                    break;

                int res = 0;
                for (int x1 = 1; x1 <= num[0]; x1++)
                {
                    for (int x2 = x1 + 1; x2 <= num[0]; x2++)
                    {
                        for (int x3 = x2 + 1; x3 <= num[0]; x3++)
                        {
                            if (x1 + x2 + x3 == num[1])
                                res++;
                        }
                    }
                }

                Console.WriteLine(res.ToString());
            }
        }
    }

class TypeConverter
    {
        static public int[] arrayStrToInt(string[] str)
        {
            return Array.ConvertAll<string, int>(str,
                delegate(string value)
                {
                    return int.Parse(value);
                }
            );
        }

        static public string[] arrayIntToStr(int[] x)
        {
            return Array.ConvertAll<int, string>(x,
                delegate(int value)
                {
                    return value.ToString();
                }
            );
        }
    }

Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<ll, ll>;

bool operator>(const P &a , const P &b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second > b.second;
}

int main(){
    int n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    sort(RALL(a));
    ll ans = 0;
    //<small, large>
    priority_queue<P> q;
    q.push(P(a[0], a[0]));
    for(int i = 1; i < n; i++){
        P p = q.top();
        q.pop();
        ll s = p.first;//小さい
        ll t = p.second;//大きい
        //cout << s << " " << t << endl;
        ans += s;
        q.push(P(a[i], s));
        //cout << a[i] << " " << s << endl;
        q.push(P(a[i], t));
        //cout << a[i] << " " << t << endl;
        //cout << " " << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 9024
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline void read(long long &x)
{
    int i=1;
    x=0;
    char a=getchar();
    while(a<'0'||a>'9')
    {
        if(a=='-') i=-1;
        a=getchar();
    }
    while(a>='0'&&a<='9')
    {
        x=x*10+a-48;
        a=getchar();
    }
    x*=i;
}
inline void write(long long x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+48);
}
long long t[100100],a[100100],b[100100];
int main()
{
	long long qw,f=0,times;
    read(qw);
	for(int i=1;i<=qw;i++)
	{
    	read(t[i]);
    	read(a[i]);
    	read(b[i]);
    	times=t[i]-t[i-1];
    	int sum=a[i]-a[i-1]+b[i]-b[i-1];
    	if(sum>t[i])
    	f=1;
    	else if((times-sum)%2!=0)
    	f=1;
    	if(f==1) break;
    }
    if(f==0) printf("Yes");
    else printf("No");
    return 0; 
}

Measured memory_bytes: 2560
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    long long int x, y;
    cin >> x >> y;
    
    int ans;
    if(abs(x)==abs(y)) {
        if(x*y>=0) ans=0;
        else ans=1;
    } else if(abs(x)<abs(y)) {
        if(x*y>0) {
            ans = y>0 ? abs(y)-abs(x) : abs(y)-abs(x)+2;
        } else if(x*y<0) {
            ans = abs(y)-abs(x)+1;
        } else {
            ans = y>0 ? abs(y)-abs(x) : abs(y)-abs(x)+1;
        }
    } else {
        if(x*y>0) {
            ans = x>0 ? abs(x)-abs(y)+2 : abs(x)-abs(y);
        } else if(x*y<0) {
            ans = abs(x)-abs(y)+1;
        } else {
            ans = x>0 ? abs(x)-abs(y)+1 : abs(x)-abs(y);
        }
    }
    cout << ans << endl;

    return 0;
    
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func to_i(b byte) int {
	return int(b - "0"[0])
}

func calc(s string, op1, op2, op3 int) int {
	return to_i(s[0]) + op1*to_i(s[1]) + op2*to_i(s[2]) + op3*to_i(s[3])
}

func to_s(op int) string {
	if op == 1 {
		return "+"
	}
	return "-"
}

func to_ans(s string, op1, op2, op3 int) string {
	return s[0:1] + to_s(op1) + s[1:2] + to_s(op2) + s[2:3] + to_s(op3) + s[3:4] + "=7"
}

func main() {
	var s string
	fmt.Scanln(&s)
	sign := []int{1, -1}
	for _, op1 := range sign {
		for _, op2 := range sign {
			for _, op3 := range sign {
				if calc(s, op1, op2, op3) == 7 {
					fmt.Println(to_ans(s, op1, op2, op3))
					return
				}
			}
		}
	}
	fmt.Println()
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    ll a = 1e18;
    cin >> N;
    for(int i = 1; i <= 5; i++) {
        ll b;
        cin >> b;
        chmin(a, b);
    }
    cout << 4 + (N + a - 1) / a << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<memory.h>
int max(int a, int b)
{
   if(a > b)return a;
   return b; 
}
int min(int a, int b)
{
    if(a < b)return a;
    return b;
}
int abs(int a)
{
    if(a<0)return -a;
    return a;
}
int h[100000];
int dp[100000];
int main()
{
    int N;
    //freopen("input.txt", "r", stdin);
    while(scanf("%d", &N) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<N; i++)
        {
            scanf("%d", &h[i]);
            int pre1 = max(0, i-1);
            int pre2 = max(0, i-2);
            dp[i] = min(dp[pre1] + abs(h[i]-h[pre1]), dp[pre2]+abs(h[i]-h[pre2]));
        }
        printf("%d\n", dp[N-1]);
    }
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h> 
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("bhar.txt", "w", stdout);
    #endif
    long long q(1);//cin>>q;
    while(q--){
       long long n,m,k,tot(0),p(0);
       string s,l;
       bool ok(1),okk(0);
       cin>>s;
       if(s[s.size()-1]=='s')
       	cout<<s+"es";
       else 
       	cout<<s+"s";
    }
}

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

#define POS y*w+x

int main(){
while(1){
	int w, h;
	string str;
	getline( cin, str );
	sscanf( str.c_str(), "%d %d", &h, &w );
	if( (h==0)&&(w==0) ) break;

	char *data = new char[w*h];
	// data input
	for( int y=0; y<h; y++ ){
		getline( cin, str );
		for( int x=0; x<w; x++ ){
			data[POS] = str.c_str()[x];
		}
	}

	// search
	int p = 0, cnt=0;
	while( data[p] != '.' ){
		switch(data[p]){
		case '>':
			p++;
			break;
		case '<':
			p--;
			break;
		case 'v':
			p+=w;
			break;
		case '^':
			p-=w;
			break;
		}
		cnt++;
		if( cnt > w*h ) break;
	}

	// output
	if( cnt > w*h ){
		cout << "LOOP" << endl;
	}else{
		cout << p%w << " " << p/w << endl;
	}

	delete[] data;
	data = 0;
}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
int main(){
	fast;
	char a;
	cin>>a;
	if(a=='a'||a=='e'||a=='i'||a=='o'||a=='u')
		cout<<"vowel";
	else
		cout<<"consonant";
	return 0;
	
}



Measured memory_bytes: 3576
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

s = readline().decode().rstrip()

p1 = 0
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] == "1":
            p1 += 1
    else:
        if s[i] == "0":
             p1 += 1

p2 = 0
for i in range(len(s)):
    if i % 2 == 0:
        if s[i] == "0":
            p2 += 1
    else:
        if s[i] == "1":
             p2 += 1

print(min(p1,p2))

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

using namespace std;
/**
********************************************************************
******************* Author:Bisnu sarkar ****************************
********************************************************************
**/

#define ull            unsigned long long
#define ll             long long
#define vi             vector<int>
#define pb             push_back
#define mp             make_pair
#define pii            pair<int,int>
#define vit            vector<int> :: iterator
#define sit            set<int> :: iterator
#define vrit           vector<int> :: reverse iterator
#define ff             first
#define ss             second

#define what_is(x)     cerr << #x << " is " << x << endl;

///*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it)
{
    cout << endl ;
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

int dx[8]= {1,0,-1,0,-1,-1,1,1};
int dy[8]= {0,1,0,-1,-1,1,-1,1};
int ini()
{
    int x;
    scanf("%d",&x);
    return x;
}
long long inl()
{
    long long x;
    scanf("%lld",&x);
    return x;
}

const int N = (int) 1e6 + 5;
const int M = (int) 1e9 + 7;
const double pi=2* acos(0.0);

int main()
{
  int n,k;
   cin>>n>>k;
   double res=0.0;
   double l=n;
   for(int i=1;i<=n;i++){
    int x=i,c=0;
    double p=1.0/l;
    while(x<k){
      x=x*2;
      p=p*0.5;
      c++;
    }
   // error(c);
    res+=p;
   }
   printf("%.12f\n", res);

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(i*j==n){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
}


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

int N;

void dfs(string s, char mx){
    if(s.length() == N){
        // c_str()を付けないと、char型をstring型として読み取ろうとするため文字化けが発生する
        printf("%s\n", s.c_str());
        // printf("%s\n", s);
    }else{
        for(char c='a'; c<=mx; c++){
            dfs(s+c, (c == mx ? (char)(mx+1) : mx));
        }
    }
}

int main()
{
    cin >> N;
    dfs("", 'a');
    return 0;
}

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

using ll = long long;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

int main() {
    int N;
    cin >> N;
    vector<int> p(N);
    for(int i = 0; i < N; ++i) {
        cin >> p[i];
    }

    vector<int> a(N), b(N);
    for(int i = 0; i < N; ++i) {
        a[i] = 20001 * i;
        b[i] = 20001 * (N - i);
    }
    for(int i = 0; i < N; ++i) {
        a[p[i] - 1] += i + 1;
    }
    //for(int i = 0; i < N; ++i) {
    //    cout << a[p[i] - 1] + b[p[i] - 1] << endl;
    //}
    for(int i = 0; i < N; ++i) {
        cout << a[i] << " \n"[i == N - 1];
    }
    for(int i = 0; i < N; ++i) {
        cout << b[i] << " \n"[i == N - 1];
    }
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
int A,B,n,x,y;
char c[200010],s[200010];
bool chk(int X,int x,char A,char D){
	int L=1,R=X;
	for(int i=n;i>=1;i--){		
		L-=s[i]==A;R+=s[i]==D;
		if(L<1)L=1;if(R>X)R=X;
		R-=c[i]==A;L+=c[i]==D;
		if(L>R)return 1;
		if(R>X)R=X;if(L<1)L=1;
	} 
	return(L>x||R<x);
}
int main(){
	std::cin>>A>>B>>n>>x>>y;
	scanf("%s%s",c+1,s+1);
	puts((chk(A,x,'D','U')|chk(B,y,'R','L'))?"NO":"YES");
	return 0;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int n, i, cntOne, cntTwo, cycle;
int fr[200001], a[200001];
long long int k;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    i = 1;
    while (i) {
        fr[i]++;
        if (fr[i] == 1)
            cntOne++;
        if (fr[i] == 2)
            cntTwo++;
        if (fr[i] == 3)
            break;
        i = a[i];
    }
    cntOne -= cntTwo;
    i = 1;
    if (k > cntOne) {
        cycle = (k - cntOne) % cntTwo;
        while (cntOne--)
            i = a[i];
    }
    else
        cycle = k;

    while (cycle--) {
        i = a[i];
    }

    cout << i << "\n";

    return 0;
}


Measured memory_bytes: 5196
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
const ll mod=1000000007;
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

int main() {
  string s;cin >>s;
  ll k;cin >>k;
  vector<pair<ll,ll>> v;
  string prev = s.substr(0,1);
  ll start = 0LL;
  ll cnt = 1LL;
  for(ll i=1;i<s.size();++i){
    auto tmp =s.substr(i,1);
    if(prev==tmp){
      ++cnt;
    } else {
      if(cnt>1LL)v.push_back(make_pair(start,cnt));
      start = i;
      prev = tmp;
      cnt = 1LL;
    }
  }
  if(cnt>1LL)v.push_back(make_pair(start,cnt));
  if(s.size()==1){
    cout << k/2 << endl;
    return 0;
  } else if(v.size()==1&&v[0].first+v[0].second==s.size()){
    cout << (v[0].second*k)/2 << endl;
    return 0;
  }
  ll out =0LL;
  for(auto& ele: v) out += ele.second/2LL;
  out *= k;
  ll edge_cnt =0LL;
  ll edge_cnt_end =0LL;
  ll edge_cnt_start =0LL;
  if(s.substr(0,1)==s.substr(s.size()-1,1)){
    if(s[0] == s[1]){
      edge_cnt += v[0].second;
      edge_cnt_start = v[0].second;
    } else {
      edge_cnt += 1LL;
    }
    if(s[s.size()-2] == s[s.size()-1]){
      edge_cnt += v[v.size()-1].second;
      edge_cnt_end = v[v.size()-1].second;
    } else {
      edge_cnt += 1LL;
    }
  }
  if(edge_cnt>0LL) {
    ll addedge = edge_cnt/2LL;
    out += addedge*(k-1LL);
    ll removeedge1 = edge_cnt_start/2LL;
    ll removeedge2 = edge_cnt_end/2LL;
    out -= removeedge1*(k-1LL);
    out -= removeedge2*(k-1LL);
  }
  cout << out << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<utility>
#include<string>
#include<algorithm>
using namespace std;
pair<string,int>p[101];

int main()
{
    int n,m,i,j,k;
    string s;
    cin>>n;
    bool flag=true;
    for(i=0;i<101;i++)p[i].second=0;
    k=0;
    for(i=0;i<n;i++){
        cin>>s;
        flag=true;
        for(j=0;j<101;j++){
            if(s==p[j].first){
                p[j].second++;
                flag=false;
                break;
            }
        }
        if(flag==true) {
            p[k].first=s;
            p[k].second=1;
            k++;
        }
    }
//    for(i=0;i<k;i++){
//        cout<<p[i].second<<endl;
//    }
    cin>>m;
    for(i=0;i<m;i++){
        cin>>s;
        for(j=0;j<101;j++){
            if(s==p[j].first){
                p[j].second--;
                break;
            }
        }
    }
    int maxi=0;
    for(i=0;i<101;i++){
        maxi=max(maxi,p[i].second);
    }
    cout<<maxi<<endl;
}


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

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/

  string s;

  cin>>s;

  int cnt=0;
  int cnt1=0;

  
  for(int i=0;i<s.length()-1;i++){
    if(s[i]!=s[i+1]){
      cnt++;
    }
  }

  
  for(int i=s.length();i>=1;i--){
    if(s[i]!=s[i-1]){
      cnt1++;
    }
  }

  cout<<min(cnt,cnt1)<<endl;
  
  return 0;

}


Measured memory_bytes: 512
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
L = [0]*N
for i in range(N):
  for j in range(i, N):
     L[min(abs(j-i), abs(j-X)+1+abs(Y-i), abs(i-X)+1+abs(j-Y))] += 1
for k in range(1, N):
  print(L[k])

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

void merge(int *A, int left, int mid, int right);
void mergeSort(int *A, int left, int right);

int count = 0;

int main(){
  int i,n,left,right;
  int *S;
  
  scanf("%d",&n);
  //printf("a\n");
  
  S = (int *)malloc(sizeof(int) * n);

  for(i = 0 ; i < n ; i++)
    scanf("%d",&S[i]);

  left = 0;
  right = n;

  //printf("a\n");
  
  mergeSort(S, left, right);

  //printf("a\n");
  for(i = 0 ; i < n ; i++){
    printf("%d",S[i]);
    if(i < n-1) printf(" ");
  }

  printf("\n%d\n",count);

  
  
  return 0;
}

void merge(int *A, int left, int mid, int right){
  int n1,n2,i,j,k;
  int *L,*R;

  n1 = mid - left;
  n2 = right - mid;

  L = (int *)malloc(sizeof(int) * (n1+1));
  R = (int *)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] = 1000000000;
  
  R[n2] = 1000000000;

  i = 0;
  j = 0;
  
  for(k = left ; k < right ; k++){
    if(L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
      count++;
      
    }
    else{
      A[k] = R[j];
      j = j + 1;
      count++;
    }
  } 
}

void mergeSort(int *A, int left, int right){
  int mid;

  if(left + 1 < right){
    mid = (left + right) / 2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
  
}

Measured memory_bytes: 63348
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll minm;
ll dp[100001];
int fn(ll a[],ll n,ll k)
{
    if(n==0)
    {
        dp[n] = min(minm,dp[n]);
        return dp[n];
    }
    if(dp[n] != INT_MAX)
    {
        return dp[n];
    }
    if(k>=2 && n>=2)
    {
        ll p = 0;
        for(ll i = n-1; i>=max(n-k,p); i--)
        {
            ll x = abs(a[n]-a[i]);
            dp[n] = min(x+fn(a,i,k),dp[n]);
        }
    }
    else
    {
        ll x = abs(a[n]-a[n-1]);
        dp[n] = x+fn(a,n-1,k);
    }
    // return dp[n];
    return dp[n];
}
int main()
{
    ll i,n,k;
    cin>>n>>k;
    ll a[n];
    for(i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(i=0; i<n; i++)
    {
        dp[i]=INT_MAX;
    }
    // memset(dp,-1,sizeof(dp));
    dp[0] = INT_MAX;
    fn(a,n-1,k);
    // cout<<"\n\n\n\n";
    // for(i=0; i<n; i++)
    // {
    //     cout<<dp[i]<<" ";
    // }
    cout<<dp[n-1]<<"\n";
    return 0;
}

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

using namespace std;

typedef long long ll;

int main(int argc, char *argv[])
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    ll N, W, wi, vi, wj;
    cin >> N >> W;

    ll ans = 0;
    unordered_map<ll, ll> current, tmp;
    for (int i = 0; i < N; i++)
    {
        cin >> wi >> vi;
        if (wi > W) continue;

        tmp.clear();
        tmp = current;

        ans = max(ans, vi);
        tmp[wi] = max(tmp[wi], vi);

        for (auto it = current.begin(); it != current.end(); ++it)
        {
            wj = wi + it->first;
            if (wj <= W)
            {
                tmp[wj] = max(tmp[wj], it->second + vi);
                ans = max(ans, tmp.at(wj));
            }
        }

        current = tmp;
    }

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


Measured memory_bytes: 9800
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long
#define mod 1000000007

int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  vector<int> alph(26, 0);
  for(int i=0; i<S.size(); i++) {
    alph[int(S[i]-'a')]++;
  }
  ll ans = 1;
  for(int i=0; i<26; i++) {
    ans *= (alph[i]+1);
    ans %= mod;
  }
  ans--;
  ans %= mod;
  cout << ans << endl;
  return 0;
}


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

#define llong long long
#define inf 999999999
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<PP, int> PPP;
typedef struct data{
	int now;
	int cost;
}data;
int nh[4] = {1, 0, -1, 0};
int nw[4] = {0, 1, 0, -1};





int main(){
	int l, a, b, c, d;
	cin >> l >> a >> b >> c >>d;
	cout << l - max(a%c==0?a/c:a/c+1, b%d==0?b/d:b/d+1) << endl;
	return 0;
}


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int p=n%100;
    int q=p%10;
    if(q==3){
      System.out.println("bon");
    }else if((q==0)||(q==1)||(q==6)||(q==8)){
      System.out.println("pon");
    }else{
    System.out.println("hon");
    }
  }
}


Measured memory_bytes: 35760
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using E = System.Linq.Enumerable;
using System.Runtime.InteropServices.ComTypes;
using System.Threading.Channels;
using System.IO.Pipes;

class Program
{
    static char[] abc = "abcdefghijklmnopqrstuvwxyz".ToCharArray();
    static long mod = 1000000007;
    static void Main(string[] args)
    {

        var N = long.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        //var D = inp[0];
        //var T = inp[1];
        //var S = inp[2];
        //var S = Console.ReadLine();
        //var T = Console.ReadLine();
        var sum = new Modular(A.Sum());
        var ans = new Modular(0);
        for (int i = 0; i < N; i++)
        {
            ans += (A[i] * (sum - A[i]));
            sum -= A[i];
        }

        Console.WriteLine(ans.value);
    }
}

class Modular
{
    private const int M = 1000000007;
    public long value;
    public Modular(long value) { this.value = value; }
    public static implicit operator Modular(long a)
    {
        var m = a % M;
        return new Modular((m < 0) ? m + M : m);
    }
    public static Modular operator +(Modular a, Modular b)
    {
        return (a.value + b.value) % M;
    }
    public static Modular operator -(Modular a, Modular b)
    {
        return a.value - b.value;
    }
    public static Modular operator *(Modular a, Modular b)
    {
        return a.value * b.value;
    }
    public static Modular Pow(Modular a, int n)
    {
        switch (n)
        {
            case 0:
                return 1;
            case 1:
                return a;
            default:
                var p = Pow(a, n / 2);
                return p * p * Pow(a, n % 2);
        }
    }
    public static Modular operator /(Modular a, Modular b)
    {
        return a * Pow(b, M - 2);
    }
    private static readonly List<int> facs = new List<int> { 1 };
    private static Modular Fac(int n)
    {
        for (int i = facs.Count; i <= n; ++i)
        {
            facs.Add((int)(Math.BigMul(facs.Last(), i) % M));
        }
        return facs[n];
    }
    public static Modular Ncr(int n, int r)
    {
        return (n < r) ? 0
             : (n == r) ? 1
                        : Fac(n) / (Fac(r) * Fac(n - r));
    }
    public static explicit operator int(Modular a)
    {
        return (int)a.value;
    }

    public static Modular Lcm(Modular a, Modular b)
    {
        var tmp = Gcdl(a.value, b.value);
        return ((a * b) / new Modular(tmp));
    }
    static Modular Gcd(Modular m, Modular n)
    {
        if (n.value > m.value) return Gcd(n, m);
        if (n.value == 0) return m;
        var r = new Modular(m.value % n.value);
        return Gcd(n, r);
    }

    static long Gcdl(long m, long n)
    {
        if (n > m) return Gcdl(n, m);
        if (n == 0) return m;
        return Gcdl(n, m % n);
    }
}




Measured memory_bytes: 64264
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args){
		FastScanner stdIn = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int k = stdIn.nextInt();
		
		List<Integer> list = new ArrayList<>();
		
		int i = 1;
		while(i<=Math.max(a,b)) {
			if(a%i==0 && b%i==0) {
				list.add(i);
			}
			i++;
		}
		Collections.sort(list);
		Collections.reverse(list);		
		int cnt = 0;
		for(int x: list) {
			cnt++;
			if(cnt==k) {
				out.println(x);
			}
		}
		out.flush();
		
		}
	}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 21460