akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>

#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/range/numeric.hpp>

#ifdef _MSC_FULL_VER
#include"randomizer.hpp"
#include"debug_print.hpp"
#endif

#include<cstdlib>
#include<ctime>

namespace lib
{
	template<class T>using pair = std::pair<T, T>;
	template<class T>constexpr T pow(T base, std::uint64_t p)
	{
		T ret = T(1);
		for (std::uint64_t i = 0; i <= 63; ++i)
		{
			if (((1ull << i) & p) != 0)
			{
				ret *= base;
			}
			base *= base;
		}
		return ret;
	}
	template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;

	struct union_find
	{
		std::vector<int> upper;
		union_find(std::size_t size):upper(size, -1) {}

		int group(int index)
		{
			if (upper[index] == -1)
			{
				return index;
			}
			else
			{
				return upper[index] = group(upper[index]);
			}
		}

		bool merge(int x, int y)
		{
			auto gx = group(x);
			auto gy = group(y);
			if (gx != gy)
			{
				upper[gx] = gy;
				return true;
			}
			return false;
		}

		auto get()
		{
			std::map<int, std::set<int>> ret;
			for (int i = 0; i < upper.size(); ++i)
			{
				ret[group(i)].emplace(i);
			}
			return ret;
		}

		auto tops()
		{
			std::set<int> ret;
			for (int i = 0; i < upper.size(); ++i)
			{
				ret.emplace(group(i));
			}
			return ret;
		}

		bool is_same_group(int x, int y)
		{
			return group(x) == group(y);
		}
	};
}

namespace out
{
	namespace detail
	{
		template<class>struct void_out
		{
			typedef void type;
		};
		template<class T>auto write(std::ostream& ost, T const& val)
			->typename void_out<decltype(ost << val)>::type
		{
			ost << val;
		}
		template<class T, class... Ts>void write(std::ostream& ost, T const& val, Ts const&... nexts)
		{
			write(ost, val);
			ost << " ";
			write(ost, nexts...);
		}
	}
	void write_line()
	{
		std::cout << std::endl;
	}
	template<class...Ts>void write_line(Ts const&... args)
	{
		detail::write(std::cout, args...);
		write_line();
	}
	template<class Range>void write_range(Range const& rng)
	{
		for (auto const& v : rng)
		{
			write_line(v);
		}
	}
}
namespace adaptor = boost::adaptors;

void Main()
{
	int N;
	std::cin >> N;
	std::set<lib::pair<int>> set;
	for (int i : boost::irange(1, N))
	{
		for (int k : boost::irange(i + 1, N + 1))
		{
			set.emplace(i, k);
		}
	}
	int n = N / 2;
	int K = 2 * n + 1;
	for (int i : boost::irange(1, n + 1))
	{
		set.erase(std::make_pair(i, K - i));
	}
	out::write_line(set.size());
	for (auto const& p : set)
	{
		out::write_line(p.first, p.second);
	}
}

int main()
{
	std::cin.tie(nullptr);
	std::cin.sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 512
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: usize,
        mut v: [u64;n]
    }
    v.sort();
    let mut res = 0;
    for i in 0..n {
        for j in i+1..n {
            if v[i] == v[j] { continue; }
            for k in j+1..n {
                if v[j] == v[k] { continue; }
                if v[i] + v[j] > v[k] {
                    res += 1;
                }
            }
        }
    }
    println!("{}", res);
}


Measured memory_bytes: 2184
#include<stdio.h>
#include<string.h>
char a[10000],b[10000];
int x[10000],y[10000],z[10000];
int main()
{
    int i,j;
    while(~scanf("%s",a))
    {int la=strlen(a);j=0;
    for(i=0;i<la;i++){
    if(a[i]=='9')
        {printf("Yes\n");break;}
   else
            j++;
    }if(j==la)
    printf("No\n");



    }
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int N;
    cin >> N;
    int ans = 0;
    FOR(i, 1, N + 1) if (to_string(i).size() % 2) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 256
N = input()
K = int(input())


def combination(n,k):
    if n == 0:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n*(n-1)/2
    else:
        return n*(n-1)*(n-2)/6

#桁DP
# 計算量はi*k=klogN
def dp(i,k,is_small): #i桁目以降についてk個0以外の数が含まれる数の個数(is_smallはi桁目までに0~Nが確定しているかのフラグ)
    if i == L: #全ての桁が決まった時
        return 1 if k == 0 else 0
    if k == 0:
        return 1
    if is_small:
        return combination((L-i),k)*9**k
    else:
        if N[i] == '0': #先頭が0の場合は先頭0,間,一致に分割できないので別処理(is_smallがfalseなので,i桁目までは完全に一致している)
            return dp(i+1,k,False) 
        else:
            zero = dp(i+1,k,True) #先頭が0のパターン
            aida = dp(i+1,k-1,True) * (int(N[i])-1)#先頭が0以外かつnの最大桁数より小さいパターン
            icchi = dp(i+1,k-1,False) #先頭が同じパターン
            return zero + aida + icchi
        

L = len(N)
print(int(dp(0,K,False)))

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

int main(){
	int a,b,c,d;
  	cin>>a>>b>>c>>d;
  	
  	if(a+b+c+d==21 && a*b*c*d==252){
		cout<<"YES"<<endl;
    }else{
      	cout<<"NO"<<endl;
    }
}


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

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

int main() {
  string s; cin >> s;
  int N = s.size();
  int ans = 0;
  for (int set = 0; set < 1 << N; set++) {
      if (ans < __builtin_popcount(set)) {
          string t;
          int M = 0;
          REP(i, N) if (set >> i & 1) {
              t += s[i];
              M++;
          }
          if (t.find("iwi") != string::npos) {
              bool ng = false;
              REP(i, M) {
                  if (t[i] == '(' && t[M - 1 - i] != ')') ng = true;
                  if (t[i] == '[' && t[M - 1 - i] != ']') ng = true;
                  if (t[i] == '{' && t[M - 1 - i] != '}') ng = true;

                  if (t[i] == ')' && t[M - 1 - i] != '(') ng = true;
                  if (t[i] == ']' && t[M - 1 - i] != '[') ng = true;
                  if (t[i] == '}' && t[M - 1 - i] != '{') ng = true;
              }
              if (!ng)
                  ans = __builtin_popcount(set);
          }
      }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;

int yoko[10000],tate[10000],yoko_sum,tate_sum,tate_num;


void func(){

	yoko_sum = tate_sum = 0;

	for(int i = 0; i < N; i++){
		scanf("%d",&yoko[i]);
		yoko_sum += yoko[i];
	}
	sort(yoko,yoko+N);
	reverse(yoko,yoko+N);

	int tate_num = 0;

	for(int i = 0; i < N; i++){
		scanf("%d",&tate[i]);
		tate_sum += tate[i];
		if(tate[i] > 0)tate_num++;
	}

	if(yoko_sum != tate_sum){
		printf("No\n");
		return;
	}

	for(int i = 0; i < N; i++){
		if(yoko[i] != tate_num){
			printf("No\n");
			return;
		}
		for(int k = 0; k < N; k++){
			if(tate[k] > 0){
				tate[k]--;
				if(tate[k] == 0)tate_num--;
			}
		}
	}

	printf("Yes\n");
}

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}

Measured memory_bytes: 3276
#include <stdio.h>
#define ll long long
#define MOD 1000000007
int main(){
    int n, m;
    ll x[100000];
    ll y[100000];
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;i++){
        scanf("%lld", &x[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%lld", &y[i]);
    }

    // x[j]-x[i] * y[j]-y[i]
    ll tmp=0, tmp2=0;

    for(int i=1; i<=n;i++){
        tmp = (tmp + ((2*i - n - 1)*x[i-1])%MOD)%MOD;
    }
    for(int i=1; i<=m;i++){
        tmp2 = (tmp2+ ((2*i - m -1)*y[i-1])%MOD)%MOD;

    }

    printf("%lld\n", (tmp*tmp2)%MOD);

}

Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <deque>
#include <cstring>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;


int main(){
  int n, k;
  cin >> n >> k;
  int a[n];
  int x;
  REP(i,n){
    cin >> a[i];
    if(a[i] == 1) x = i;
  }
  int l = x;
  int r = n - x - 1;

  int cl, cp;

  if(l > 0){
    cl = (l-1) / (k-1) + 1;
    cp = cl * (k-1) - l;
  }else{
    cl = 0;
    cp = 0;
  }

  int cr;
  if(r-cp > 0){
    cr = (r-1-cp) / (k-1) + 1;
  }else{
    cr = 0;
  }

  cout << cr + cl << endl;

  return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	static long bignum = 1000000000+7;

	public static int[] rudder = new int[200001];

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();

		int[] a = new int[n];
		for(int i =0;i<n;i++) {
			a[i]=0;
		}

		for(int i=1;i<n;i++) {
			for(int j=i+1;j<n+1;j++) {
				if(x>=i) {
					if(x>=j) {
						a[j-i]++;
					}
					if(j>x&&y>j) {
						a[Math.min(j-i, y-j+x-i+1)]++;
					}
					if(j>=y) {
						a[x-i+1+j-y]++;
					}
				}
				if(x<i&&y>i) {
					if(j<y) {
						a[Math.min(j-i, i-x+1+y-j)]++;
					}
					if(j>=y) {
						a[Math.min(j-i, i-x+1+j-y)]++;
					}
				}
				if(i>=y)a[j-i]++;
			}
		}

		for(int i =1;i<n;i++) {
			System.out.println(a[i]);
		}


	}





}
/*
class City{
	int order;
	int prefecture;
	int year;
	int number;
	City(int order,int prefecture, int year){
		this.order = order;
		this.prefecture = prefecture;
		this.year = year;
	}
}
*/


Measured memory_bytes: 24588
N = int(input())
A = list(map(int,input().split()))
MAX = max(A) #Aの中の最大値
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  temp = A[j]
  if Adic[temp] >= 2: #同じ数が複数ある場合には削除
    if temp in Aset:
      Aset.remove(temp)
  fmax = MAX//temp
  #print(fmax,temp)
  for i in range(2,fmax+10): #fmaxまで見る
    now = temp*i
    if now in Aset:
      Aset.remove(now)
#print(Aset)
print(len(Aset))

Measured memory_bytes: 142436
def max_array(n)
  m = (n**0.5).to_i
  a = [1] * m
  (N / m - 1).downto(1) do |i|
    add  = n / i - n / (i + 1) 
    a << add unless add.zero?
  end
  a
end

MOD = 10**9 + 7
N, K = gets.chomp.split.map(&:to_i)
array = max_array(N)

dp = Array.new(K) { Array.new(array.size, 0) }

array.size.times { |i| dp[0][i] = array[i] }

1.upto(K - 1) do |i|
  a = dp[i - 1].inject(0, &:+)
  array.size.times do |j|
    dp[i][j] = (a * array[j]) % MOD
    a -= dp[i - 1][array.size - 1 - j]
  end
end

ans = 0
array.size.times do |i|
  ans += dp[K - 1][i]
end
ans %= MOD

puts ans


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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int n, a, b;
	cin >> n >> a >> b;
	if (abs(a - b) & 1) {
		cout << "Borys" << endl;
	}
	else {
		cout << "Alice" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

int dp[100010];
int dp2[100010];
int nxt[100010];
int nxt2[100010];

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    dp[1] = 1;
    int MAX = 0;
    for(int i = 1; i * i < n; i++) MAX = i;
    rep(j, 0, k){
        for(int i = 1; i * i <= n; i++){
            nxt[i] = nxt2[i] = 0;
        }
        int sum = 0;
        for(int i = 1; i * i <= n; i++){
            (sum += dp[i]) %= mod;
        }
        for(int i = 1; i * i <= n; i++){
            (nxt[i] += sum) %= mod;
        }
        int now = 0;
        for(int i = MAX; i >= 1; i--){
            (now += dp2[i]) %= mod;
            (nxt[i] += now) %= mod;
        }
        now = 0;
        for(int i = 1; i <= MAX; i++){
            (now += dp[i]) %= mod;
            int val = n / i - n / (i + 1);
            if(i == MAX && (MAX + 1) * (MAX + 1) != n){
                val = n / i - MAX;
            }
            (nxt2[i] += now * val % mod) %= mod;
        }
        // for(int i = 1; i * i <= n; i++){
        //     cout << nxt[i] << ' ';
        // }
        // cout << endl;
        // for(int i = 1; i <= MAX; i++){
        //     cout << nxt2[i] << ' ';
        // }
        // cout << endl;
        swap(dp, nxt);
        swap(dp2, nxt2);
    }
    int ans = 0;
    for(int i = 1; i * i <= n; i++) (ans += dp[i]) %= mod;
    for(int i = 1; i <= MAX; i++) (ans += dp2[i]) %= mod;
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <stdlib.h>

int* merge(int a[], int n) {
    if (n == 1) {
        return a;
    }
    int* a1 = (int*)malloc(n/2 * sizeof(int));
    int* a2 = (int*)malloc((n-n/2) * sizeof(int));
    for(int i = 0; i < n/2; i++) {
        a1[i] = a[i];
    }
    for(int i = n/2; i < n; i++) {
        a2[i-n/2] = a[i];
    }
    a1 = merge(a1,n/2);
    a2 = merge(a2,n-n/2);
    int i1 = 0;
    int i2 = 0;
    for(int i = 0; i < n; i++) {
        if(i2 == n-n/2 || (i1 != n/2 && a1[i1] < a2[i2])) {
            a[i] = a1[i1];
            i1++;
        } else {
            a[i] = a2[i2];
            i2++;
        }
    }
    return a;
}

int main(){
    int n;
    std::cin >> n;
    while(n != 0) {
        int* a = (int*)malloc(n * sizeof(int));
        for(int i = 0; i < n; i++) {
            std::cin >> a[i];
        }
        a = merge(a,n);
        int min = a[1] - a[0];
        for(int i = 1; i < n-1; i++) {
            int tmp = a[i+1] - a[i];
            if (tmp < min) {
                min = tmp;
            }
        }
        std::cout << min << std::endl;
        std::cin >> n;
    }
    return 0;
}


Measured memory_bytes: 4432
#include<bits/stdc++.h>
using namespace std;
	int main(){
	int a, b, c;
	string s;
	cin >> s;
	if(s == "a" || s == "i" || s == "u" || s == "e" || s =="o"){
		cout << "vowel" << endl;
	}
	else cout << "consonant" << endl;
return 0;
}

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

using namespace std;

#define PI 3.14159265358979323846264338327950L

int main(void){

    long long tmp,ans;

    for(int i=0;i<5;i++){
        cin>>tmp;

        if(tmp == 0){
            ans=i+1;
        }
    }


    cout<<ans<<endl;



    return 0;
}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	const int INF = 1e9;
	int N, M;
	cin >> N >> M;
	vector<int> a(M), b(M);
	vector<vector<int>> c(M, vector<int>(N, 0));
	for (int i = 0; i < M; ++i) {
		cin >> a[i] >> b[i];
		for (int j = 0; j < b[i]; ++j) {
			int cc;
			cin >> cc;
			c[i][cc - 1] = 1;
		}
	}

	int sz = 1;
	for (int i = 0; i < N; ++i) { sz *= 2; }
	vector<vector<int>> dp(M + 1, vector<int>(sz, INF));
	dp[0][0] = 0;
	for (int i = 1; i <= M; ++i) {
		for (int j = 0; j < sz; ++j) {
			int idx = 0;
			{
				vector<int> v = c[i - 1];
				for (int k = 0; k < N; ++k) {
					if ((j>>k) & 1) { v[k] = 1; }
				}
				for (int k = v.size() - 1; k >= 0; --k) {
					idx *= 2;
					idx += v[k];
				}
			}
			dp[i][j] = min(dp[i][j], dp[i - 1][j]);
			dp[i][idx] = min(dp[i][idx], dp[i - 1][j] + a[i - 1]);
		}
	}
	int ans = (dp[M - 1][sz - 1] < INF ? dp[M - 1][sz - 1] : -1);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 16384
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, M, Q = map(int, input().split())

acc = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(M):
    l, r = map(int, input().split())
    acc[l][r] += 1
for i in range(1, N + 1):
    for j in range(1, N + 1):
        acc[i][j] += acc[i][j - 1]

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q + 1):
        ans += acc[i][q]
    print(ans)


Measured memory_bytes: 77208
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 2e6 + 10;
const ll INF = 1e18;
const ll LOG = 20;
vector<ll> dp[N];
vector<ll> num[N];
ll a[N], n, Z[N], par[N];

ll calc(ll v, ll u){
	return Z[u] - Z[v];
}

ll tav[N];
int main(){
	IOS;
	cin >> n;
	tav[0] = 1;
	for (int i = 1; i < N; i++){
		tav[i] = tav[i - 1] * 2;
		tav[i] %= MOD;
	}
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		par[i] = par[i - 1] ^ a[i];
		Z[i] = Z[i - 1] + (par[i] == 0);
		num[par[i]].pb(i);	
	}
	
	for (int i = 1; i < N; i++){
		if (num[i].size()){
			dp[i].pb(1);
			ll sum = 1;
			for (int j = 1; j < num[i].size(); j++){
				dp[i].pb((dp[i][j - 1] + sum * calc(num[i][j - 1], num[i][j])) % MOD);
				sum += dp[i][j];
			}
		}
	}
	//cout << num[1].size() << ' ' << num[3].size() << '\n';
	ll ans = 0;
	if (par[n] == 0){
		ans += tav[Z[n] - 1];
		//cout << ans << '\n';
		for (int i = 1; i < N; i++){
			for (int j = 0; j < num[i].size(); j++){
				ans += dp[i][j];
				ans %= MOD;
			}
		}
	}else{
		for (int j = 0; j < num[par[n]].size(); j++){
			ans += dp[par[n]][j] * calc(num[par[n]][j], n);
			ans %= MOD;
		}
		ans ++;
		ans %= MOD;
	}
	//cout << par[n] << '\n';
	cout << ans;
	
	
	
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> bar;
  for (int n = 0; n < 2 * N; ++n) {
    int b;
    cin >> b;
    bar.push_back(b);
  }
  sort(bar.begin(), bar.end(), greater<int>());
  int res = 0;
  for (int n = 0; n < N; ++n) {
    res += bar[2 * n + 1];
  }
  cout << res << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
	int N,A,B;
	cin>>N>>A>>B;
	string S;
	cin>>S;
	int manNums=S.length();
	int aNums=0;
	int bNums=0;
	for (int i=0;i<manNums;i++){
		if (S[i]=='a'){
			aNums++;
		}
	}
	int pass=0;

	for (int i=0;i<N;i++){
		switch(S[i]){
			case 'a':
				if (pass<A+B){
					cout<<"Yes"<<endl;
					pass++;
				}else{
					cout<<"No"<<endl;
				}
				break;
			case 'b':
				bNums++;
				if (pass<A+B && bNums<=B){
					cout<<"Yes"<<endl;
					pass++;
				}else{
					cout<<"No"<<endl;
				}
				break;
			case 'c':
				cout<<"No"<<endl;
				break;
		}

	}
	return 0;
}

Measured memory_bytes: 896
#include "bits/stdc++.h"

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
char capitalize(char c) { return static_cast<char>(std::toupper(static_cast<unsigned char>(c))); }
// template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
// template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

// #define int long long
#define YES "YES"
#define NO  "NO"

using namespace std;

signed main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int num = 0;
  // num = numeric_limits<int>::max();
  // num = numeric_limits<int>::min();
  bool flag = false;
  // flag = true;

  string s; cin >> s;
  for (auto it = s.begin(); it != s.end(); ++it) if (*it == ',') *it = ' ';
  cout << s << endl;

  // cout << num << endl;
  // cout << (flag ? "H" : "D") << endl;
  
  return 0;
}


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

string s;
long k;
char sub() {
  for (int i = 0; i < k; ++i) {
    if (s[i] != '1') {
      return s[i];
    }
  }
  return '1';
}

int main() {
  cin >> s >> k;
  cout << sub() << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main() {
    fastio
	ll n,t,i,j,x,k;
    cin>>n>>x>>t;
    
    k=n/x*t;
    
    if(n%x) k+=t;
    cout<<k;
	
	return 0;
}

Measured memory_bytes: 3636
import math


def li():
    return list(map(int, input().split()))


def square_distance(point1, point2):
    distance = 0
    for x, y in zip(point1, point2):
        distance = distance + (x - y) ** 2
    return distance


def int_distance(point1, point2):
    return round(math.sqrt(square_distance(point1, point2)))


if __name__ == "__main__":
    [n, d] = li()
    x_list = [li() for _ in range(n)]

    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if square_distance(x_list[i], x_list[j]) == int_distance(x_list[i], x_list[j]) ** 2:
                count = count + 1
    print(count)


Measured memory_bytes: 38452
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int A, B;
    long long i;

    cin >> A >> B;

    for (i = 1; i < 10000000000; i++){
      if (A * i % B == 0){
        cout << A * i << endl;
        return 0;
      }
    }
}

Measured memory_bytes: 256
// Date: 2020-02-29

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

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

int main() {
    int a, b, c, x, y;
    scanf("%d%d%d%d%d", &a, &b, &c, &x, &y);
    int ans = inf;
    rep(i, 0, x) {
        int tp = i * a;
        if(i < x) {
            tp += 2*c*(x-i);
            int ry = y-(x-i);
            if(ry > 0) tp += min(ry * b, 2 * ry * c);
        } else tp += min(y * b, 2 * y * c);
        ans = min(ans, tp);
    }
    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define INF 10000000001
#define DIM 200001
#define mod 1000000007
#define PI 3.1415926535897932384626433
#define se second
#define fi first
#define pb push_back
#define T true
#define F false
#define endl "\n"
typedef char ch;
typedef bool boll;
typedef string st;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef set < string > sst;
typedef set < long long > sl;
typedef queue < long long > que;
typedef vector < long long > vec;
typedef map < long long, long long > mll;
typedef pair < long long, long long > pll;
typedef vector < pair < long long, long long > > vpl;
typedef pair < long long, unsigned long long > pul;
ll a,b,n,z,x,c,s,t;
int main()
{
    fast;
    cin>>x>>z;
    if(x%z==0)
    cout<<(x/z)<<endl;
    else cout<<(x/z)+1<<endl;
}


Measured memory_bytes: 256
<?php
$price = trim(fgets(STDIN));
$count = substr($price, 0, strlen($price)-2);
$value = substr($price, -2);

$five = $count - floor($value / 5);
if($five < 0){
  echo 0;
} elseif($five == 0 && $value % 5 == 0){
  echo 1;
} elseif($five > 0){
  echo 1;
} else {
  echo 0;
}
?>

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

#define rep(i , a , b) for(register int i=(a);i<=(b);i++)
#define rop(i , a , b) for(register ll i=(a);i<(b);i++)
#define per(i , a , b) for(register ll i=(a);i>=(b);i--)
#define por(i , a , b) for(register ll i=(a);i>(b);i--)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double , double > pi;
template<class T>
inline void read (T &x) {
    x = 0;
    int sign = 1;
    char c = getchar ();
    while (c < '0' || c > '9') {
        if ( c == '-' ) sign = - 1;
        c = getchar ();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar ();
    }
    x = x * sign;
}
const int maxn = 1e5+10;
const int inf = int (1e9);
const ll INF = ll(1e18);
const double PI = acos (-1);
const int mod = 1e9+7;
const double eps = 1e-8;

struct node {
    int a,b;
}e[maxn];

bool cmp(node A,node B) {
    return A.a<B.a;
}
int n,m;
int main(){
    read (n);read (m);
    rep (i,1,n) {
        read (e[i].a);read (e[i].b);
    }
    sort (e+1,e+1+n,cmp);
    ll ans = 0;
    for(int i=1;m>=0&&i<=n;i++) {
        if(m>=e[i].b) {
            m-=e[i].b;
            ans+=1ll*e[i].a*e[i].b;
        }
        else {
            ans+=1ll*m*e[i].a;
            m=0;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
n = int(input())
lista=list(map(int,input().split()))

count=0
zougen=""
for i in range(n-1):
    if zougen=="":
        if lista[i]<lista[i+1]:
            zougen="up"
        if lista[i]>lista[i+1]:
            zougen="down"
    elif  zougen=="up":
        if lista[i]>lista[i+1]:
            count+=1
            zougen=""
    elif zougen=="down":
        if lista[i]<lista[i+1]:
            count+=1
            zougen=""
print(count+1)

Measured memory_bytes: 15020
mod=10**9+7

import bisect,sys

input=sys.stdin.readline

N,A,B=map(int,input().split())
S=[int(input()) for i in range(N)]

datax=[i for i in range(N+1)]
datay=[i for i in range(N+1)]

for i in range(2,N+1):
    if S[i-1]-S[i-2]>=A:
        datax[i]=datax[i-1]
    if S[i-1]-S[i-2]>=B:
        datay[i]=datay[i-1]

#print(datax)
#print(datay)

dpx=[0]*(N+1)
imosx=[0]*(N+1)
dpy=[0]*(N+1)
imosy=[0]*(N+1)
dpx[0]=1
dpy[0]=1
imosx[0]=1
imosy[0]=1

for i in range(1,N):
    id=bisect.bisect_right(S,S[i]-B)
    R=min(id+1,i)
    L=datax[i]
    if R>=L:
        dpx[i]=(imosy[R-1]-imosy[L-2]*(L>=2))%mod
        imosx[i]=(imosx[i-1]+dpx[i])%mod
    else:
        imosx[i]=imosx[i-1]

    id=bisect.bisect_right(S,S[i]-A)
    R=min(id+1,i)
    L=datay[i]
    if R>=L:
        dpy[i]=(imosx[R-1]-imosx[L-2]*(L>=2))%mod
        imosy[i]=(imosy[i-1]+dpy[i])%mod
    else:
        imosy[i]=imosy[i-1]

i=N

R=i
L=datax[i]
if R>=L:
    dpx[i]=(imosy[R-1]-imosy[L-2]*(L>=2))%mod
    imosx[i]=(imosx[i-1]+dpx[i])%mod
else:
    imosx[i]=imosx[i-1]

R=i
L=datay[i]
if R>=L:
    dpy[i]=(imosx[R-1]-imosx[L-2]*(L>=2))%mod
    imosy[i]=(imosy[i-1]+dpy[i])%mod
else:
    imosy[i]=imosy[i-1]

#print(dpx)
#print(dpy)
print((dpx[-1]+dpy[-1])%mod)


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

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

    int n;
    double t, a, d = 1e9;
    cin >> n >> t >> a;

    int idx = 0;
    for(int i = 0; i < n; i++){
        double c;
        cin >> c;
        double h = t - c * 0.006;
        if(abs(h - a) < d){
            idx = i;
            d = abs(h - a);
        }
    }

    cout << idx + 1 << endl;

    return 0;
}

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

int64_t myadd(int64_t a, int64_t b) {
  int64_t a_ = a % 1000000007;
  int64_t b_ = b % 1000000007;
  return ( a_ + b_ ) % 1000000007;
}

pair<int64_t, int64_t> get_base(int64_t N, vector<int64_t> &A) {
  int64_t smaller = 0;
  int64_t larger = 0;
  for(int64_t i = 0; i < N; i++) {
    for(int64_t j = i+1; j < N; j++) {
//      cout << "(" << i << "," << j << ")" << endl;
      if ( A.at(i) < A.at(j) ) {
        smaller += 1;
      }
      else if ( A.at(i) > A.at(j) ) {
        larger += 1;
      }
    }
  }
//  cout << smaller << "," << larger << endl;
  return make_pair(smaller, larger);
}

int main() {
  //input
  int64_t N, K;
  cin >> N >> K;
  vector<int64_t> A(N);
  rep(i,N) {
    cin >> A.at(i);
  }
  //calc
  int64_t S, L;
  tie(S, L) = get_base(N, A);
//  cout << S << "," << L << endl;
  int64_t answer = 0;
  int64_t cL = 0;
  int64_t cS = 0;
  if ( K % 2 == 0 ) {
    cL = K / 2;
    cS = K / 2;
    cL = myadd(0, cL * (K+1));
    cS = myadd(0, cS * (K-1));
  }
  else {
    cL = (K+1)/2;
    cS = (K-1)/2;
    cL = myadd(0, cL * K);
    cS = myadd(0, cS * K);
  }
  answer = myadd(myadd(0, L*cL), myadd(0, S*cS));
  //output
  cout << answer << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n, k, a[100000], dp[100000];
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; ++i)
        scanf("%d", a+i);
    dp[n-1] = 0;
    for(int i=n-2; i>=0; --i)
    {
        dp[i] = 1e9;
        for(int j=1; j <= k && j+i < n ; ++j)
        {
            dp[i] = min( dp[i], dp[i+j]+abs(a[i]-a[i+j]));
        }
    }
    cout << dp[0];
    return 0;
}

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

//各マスのRLの境目に密集する。
//RRLRLのような文字列を、(2,1),(1,1)のように表す。例えば、
//RRRLLRLLRRRLLLLLは(3,2),(1,2),(3,5)となる
//各ペア(i,j)について、i,jの偶奇で場合分け。
//共に偶数の場合、例えばRRLLLLなどなので、111111 022110 023100 033000 のようにして半々になる
//共に奇数の場合、偶数の場合と同じ
//iが奇数、jが偶数の時、RRRLLなど。11111 01220 00320 00230 というように振動。
//10^100は偶数だから、00320のように、( (i+j+1)/2 , (i+j-1)/2 )のようになる。
//偶奇が逆の場合、RRLなど。111 021 012というように振動。
//( (i+j-1)/2 , (i+j+1)/2 )のようになる


void solve(){
    string s;
    cin >> s;
    vector<pair<int,int>> v;
    //sを削っていく。２つのモードx,yを用意し、
    //モードxの時はs[0]=Lになるまでa++
    //モードyの時はs[0]=Rになるまでb++
    //モードは順番に実行される
    int a=0;
    int b=0;
    while(s.size()!=0){
        while(s[0]=='R'){
                a++;
                s = s.substr(1, s.size());
            }
        while(s[0]=='L'){
                b++;
                s = s.substr(1, s.size());
            }
        
        v.emplace_back(make_pair(a,b));
        a=0;
        b=0;
    }
    //cout << v[0].first << " " << v[0].second << " " << v[1].first << " " << v[1].second << endl;

    //各ペア(p,q)について、
    //pとqの偶奇が一致している時、0 0 ... 0 (p+q)/2 [i個] (p+q)/2 0 0 ... 0 [j個] となる

    for(int i = 0; i < v.size(); i++){
        int p = v[i].first;
        int q = v[i].second;

        if((p-q)%2==0){
        for(int j=0; j<p-1; j++){
            cout << "0 ";
        }
        cout << (p+q)/2 << " " << (p+q)/2 << " ";
        for(int j=0; j<q-1; j++){
            cout << "0 ";
        }
        }
        else if(p%2==1){
        for(int j=0; j<p-1; j++){
            cout << "0 ";
        }
        cout << (p+q+1)/2 << " " << (p+q-1)/2 << " ";
        for(int j=0; j<q-1; j++){
            cout << "0 ";
        }
        }
        else{
        for(int j=0; j<p-1; j++){
            cout << "0 ";
        }
        cout << (p+q-1)/2 << " " << (p+q+1)/2 << " ";
        for(int j=0; j<q-1; j++){
            cout << "0 ";
        }
        }
    }

    cout << endl;
}

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


Measured memory_bytes: 1008
#include<iostream>
using namespace std;
int n1[1000],m1[1000];
int main(){
  int n,m,cnt,ccc,ooo;
  while(1){
    cin >> n >> m;
    if(n==0 && m==0)break;
    cnt=0,ccc=0,ooo=0;
    for(int i=0;i<n;i++){
      cin >> n1[i];
    }
    for(int i=0;i<m;i++){
      cin >> m1[i];
    }
    while(1){
      ccc++;
      cnt+=m1[ooo];
      cnt+=n1[cnt];
      if(cnt>=n-1){break;}
      ooo++;
    }
    cout << ccc << endl;
  }
  return 0;
}

Measured memory_bytes: 1168
/*
      author  : nishi5451
      created : 14.08.2020 21:24:46
*/

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

const int INF = 2020202020;

int main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    int l = x, r = y;
    rep(i,n){
        int a;
        cin >> a;
        l = max(l,a);
    }
    rep(i,m){
        int a;
        cin >> a;
        r = min(r,a);
    }
    if(r-l >= 1) cout << "No War" << endl;
    else cout << "War" << endl;

    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int a, b;
	char op;
	cin >> a >> op >> b;
	if (op == '+') cout << a + b << endl;
	else cout << a - b << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>
#include<time.h>
typedef long long int ll;
//#include<bits/stdc++.h>


using namespace std;



int main()
{

    int n;
    cin >> n;
    vector<int>a(n);
    ll ans = 0;
    ll t = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i)if (a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i] = a[i - 1];
        }
    }

    cout << ans << endl;


    return 0;

}


Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, count = 0;
    cin >> n;
    vector<ll> a(n+1);
    map<ll , ll> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        m[i - a[i]]++;
    }
    for(int i = 1; i <= n; i++) {
        count += m[a[i] + i];
    }
    cout << count << "\n";
    return 0; 
}

Measured memory_bytes: 27356
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(cin>>s){
    list<char> st;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='B'){
            if(!st.empty()){
                st.pop_back();
            }
        }
        else st.push_back(s[i]);
    }
    if(st.empty())cout<<endl;
    else{
        auto it = st.begin();
        while(!st.empty()){
            cout<<*it;
            it++;
            st.pop_front();
        }
        cout<<endl;
    }
    }
}


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

int main(){
  int n,tmp=0;
  cin >> n;
  int a[n] = {0};
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    while(a[i]%2 != 1){
      tmp += 1;
      a[i] = a[i]/2;
    }
  }
  cout << tmp << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
   
    int a, b, tmp;
   
    while(1){
       scanf("%d%d",&a,&b);
       if(a == 0 && b == 0)  break;
       if (a > b){
          tmp = a;
          a = b;
          b = tmp;
        }
         printf("%d %d\n",a,b);
    }
     return 0;
}

Measured memory_bytes: 600
#include<stdio.h>
static const int N = 501;
static const int INFTY = (1<<21);

int main(){
  
  int M[N][N];
  int a,b,c,d; 
  int i,j;

  scanf("%d",&a);

  for(i=0;i<a;i++){
    for(j=0;j<a;j++)M[i][j]=0;
  }
  
  for(i=0;i<a;i++){
    scanf("%d%d",&b,&c);
    b--;
    for(j=0;j<c;j++){
      scanf("%d",&d);
      d--;
      M[b][d]=1;
    }
  }
  
  for(i=0;i<a;i++){
    for(j=0;j<a;j++){
      if(j) printf(" ");
      printf("%d",M[i][j]);
    }
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 10000000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

void solve(long long Q, long long H, long long S, long long D, long long N){
	ll two = INF, one = INF;
	two = min(two, Q*8);
	two = min(two, Q*6+H);
	two = min(two, Q*4+H*2);
	two = min(two, Q*4+S);
	two = min(two, Q*2+H*3);
	two = min(two, Q*2+H*1+S);
	two = min(two, H*4);
	two = min(two, H*2+S);
	two = min(two, S*2);
	two = min(two, D);
	one = min(one, Q*4);
	one = min(one, Q*2+H);
	one = min(one, H*2);
	one = min(one, S);
	cout << N/2*two+N%2*one << endl;
}

int main(){	
	long long S;
	long long Q;
	long long H;
	long long D;
	long long N;
	scanf("%lld",&Q);
	scanf("%lld",&H);
	scanf("%lld",&S);
	scanf("%lld",&D);
	scanf("%lld",&N);
	solve(Q, H, S, D, N);
	return 0;
}



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

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)2e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

int main()
{                         
	string s;
	stack< int > st;
	cin >> s;
	for(int i = 0; i < s.size(); i++){
		if(!st.empty() && st.top() == 'S' && s[i] == 'T')
			st.pop();
		else
			st.push(s[i]);
	}
	cout << st.size();
	return 0;
}


Measured memory_bytes: 1284
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(int i=(int)(st),i##end=(int)(ed);i<=i##end;++i)
#define DREP(i,st,ed) for(int i=(int)(st),i##end=(int)(ed);i>=i##end;--i)
template<typename T>bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
template<typename T>T read(){
	T x=0,f=1;
	char c=getchar();
	while((c<'0')||(c>'9')){if(c=='-')f=-1;c=getchar();}
	while((c>='0')&&(c<='9'))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
#define read() read<int>()
template<typename T>void write(T x,char c){
	static char t[25];
	static int tlen;
	t[tlen=1]=c;
	if(x<0)putchar('-'),x=-x;
	do t[++tlen]=(x%10)^48;
	while(x/=10);
	while(tlen)putchar(t[tlen--]);
}
#define pb push_back
typedef long long ll;
typedef double lf;
char s[20];
int main(){
	int cnt=0,n,tmp=0,ans=0;
	scanf("%s",s+1);
	n=strlen(s+1);
	REP(i,1,n)
		ans+=s[i]-'0';
	REP(i,1,n){
		if(s[i]=='0')cnt++;
		else cnt=0,tmp+=s[i]-'0';
		chkmax(ans,9*(n-i)+9*cnt+tmp-1);
	}
	write(ans,'\n');
	return 0;
}

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

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

    bool odd = false;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] % 2 == 1) odd = true;
    }

    int c = 0;
    if (!odd) {
        while (1) {
            c++;
            for (int i = 0; i < n; i++) {
                a[i] /= 2;
                if (a[i] % 2 == 1) {
                    odd = true;
                    break;
                }
            }
            if (odd) break;
        }
    }

    cout << c << endl;

    return 0;
}


Measured memory_bytes: 3600
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    N = int(input())
    p = []
    a = N

    while a > 0:
        m = (a-1) % 26
        p.append(m)
        a = (a-1)//26

    # print(list(reversed(p)))
    # " abcdefghijklmnopqrstuvwxyz"
    print("".join([chr(ord('a')+n) for n in reversed(p)]))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61824
#include<iostream>
#include<string.h>
using namespace std;

char c[200099];
int main()
{
	int i=0;
	while(scanf("%c",&c[i])!=EOF)
	{
		if(i>0)
		{
			if(c[i-1]=='S'&&c[i]=='T')
			i=i-2;
		}
		i++;
	}
	cout<<i-1<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(){
 int w,n,am[30],i,a,b,buf;

 scanf("%d",&w);
 scanf("%d",&n);
 for(i=0;i<w;i++)
  am[i]=i+1;
 for(i=0;i<n;i++){
  scanf("%d,%d",&a,&b);
  buf=am[a-1];
  am[a-1]=am[b-1];
  am[b-1]=buf;
 }
 for(i=0;i<w;i++){
  printf("%d\n",am[i]);
 }
 return 0;
}

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

//Thanksgiving
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if((n|m)==0)break;
			int[] a = new int[n];
			int s = 0;
			for(int i=0;i<n;i++){
				a[i] = sc.nextInt();
				s+=a[i];
			}
			Arrays.sort(a);
			int k = 0;
			for(int i=n-1;i>=0;i--){
				k++;
				if(k%m==0)s-=a[i];
			}
			System.out.println(s);
		}
	}
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

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

signed main(){
	int M,D;
	cin>>M>>D;
	int ans=0;
		for(int d=2;d<10;d++){
			for(int e=2;e<10;e++){
				if(d*10+e>D)continue;
				if(d*e<=M)ans++;
			}
		}
	
	cout<<ans<<endl;
	return 0;
}

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

int main()
{
	int N;
	int64_t L;
	scanf("%d%lld", &N, &L);
	std::vector<int64_t> a(N);
	for (auto& e: a) scanf("%lld", &e);
	int center{-1};
	for (int i{}; i + 1 < N; i++)
		if (a[i] + a[i + 1] >= L)
		{
			center = i;
			break;
		}
	if (center == -1)
	{
		puts("Impossible");
		return 0;
	}
	puts("Possible");
	for (int i{}; i < center; i++)
		printf("%d\n", i + 1);
	for (int i{N - 2}; i >= center; i--)
		printf("%d\n", i + 1);

	return 0;
}

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

int main(){
  int n,m;
  cin >> n >> m;
  vector <bool> fori(n,false);
  vector <bool> forn(n,false);
  for(int i = 0; i < m; i++){
      int a,b;
      cin >> a >> b;
      if (a == 1){
          fori.at(b-1) = true;
      }
      if(b == n){
          forn.at(a-1) = true;
      }
  }
  string frag = "IMPOSSIBLE";
  for(int i = 0; i < n; i++){
      if(fori.at(i) == true && forn.at(i) == true){
          frag ="POSSIBLE";
      }
  }
  cout << frag << endl;
}

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

using namespace std;

int main(){
    int N,M;
    int tmp;
    long sum = 0;

    cin >> N >> M;

    priority_queue<long long> price;

    for(int i = 0; i < N; i++){
        cin >> tmp;
        price.push(tmp); //優先順位Q
    }

    for(int i = 0; i < M; i++){
        price.push(price.top()/2);
        price.pop();
    }

    while(!price.empty()){
        sum += price.top();
        price.pop();
    }

   cout << sum << endl;


    return 0;
}

Measured memory_bytes: 1400