akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>

using ll = long long;
using namespace std;

#define MOD ((int)pow(10, 9) + 7)

inline vector<int> primes(int n) {
  vector<bool> is_prime(n+1, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i*i <= n; i++) {
    if (is_prime[i]) {
      for (int k = i * 2; k <= n; k += i) {
        is_prime[k] = false;
      }
    }
  }

  vector<int> x;
  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      x.push_back(i);
    }
  }

  return x;
}

inline map<ll, int> prime_factorize(ll n, vector<int> const & primes) {
  map<ll, int> result;
  for (int p: primes) {
    if (n < p * (ll)p) break;
    while (n % p == 0) {
      result[p] += 1;
      n /= p;
    }
  }

  if (n != 1) result[n] += 1;
  return result;
}

inline int ans(int N) {
  vector<int> _primes = primes(sqrt(N) + 3);
  map<ll, int> factors;

  for (int i = 1; i < N + 1; i++) {
    for (auto kv: prime_factorize(i, _primes)) {
      int p, cnt;
      tie(p, cnt) = kv;
      factors[p] += cnt;
    }
  }

  ll ret = 1;
  for (auto kv: factors) {
    int cnt = kv.second;
    ret = (ret * (1 + cnt) ) % MOD;
  }

  return ret;
}

int main (void) {
  int N;
  cin >> N;
  int _ans = ans(N);
  cout << _ans << endl;
  return 0;
}


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

int main(){
    int n, m; cin >> n >> m;
    cout << ((n == m)?"Yes":"No") << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long b = sc.nextLong();
    long k = sc.nextLong();

    if(a>=k){
      a = a-k;
    }else if(a<k && b>=(k-a)){
      b = b-(k-a);
      a = 0;
    }else{
      a = 0;
      b = 0;
    }
    System.out.println(a+" "+b);
  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (ll i=0; i<(n); ++i)
typedef long long ll;
bool debug=false;
string yes = "Yes";
string no = "No";

int main(){
  string s; cin >> s;
  cout << ((s=="ARC")?"ABC":"ARC") << endl;
  return 0;
}




Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main()
{
    int n, m, ab[51] = {0}, a, b;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        ab[a] += 1;
        ab[b] += 1;
    }
    for(int i = 1; i <= n; i++){
        cout << ab[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int W, H, N;
  cin >> W >> H >> N;
  int xmin = 0;
  int xmax = W;
  int ymin = 0;
  int ymax = H;
  int x[N], y[N], a[N];
  for (int i=0; i<N; i++){
    cin >> x[i] >> y[i] >> a[i];
    switch (a[i]){
      case 1:
        xmin = max(xmin, x[i]);
        break;
      case 2:
        xmax = min(xmax, x[i]);
        break;
      case 3:
        ymin = max(ymin, y[i]);
        break;
      case 4:
        ymax = min(ymax, y[i]);
        break;
    }
  }
  if ((xmax >= xmin) && (ymax >= ymin))
    cout << (xmax - xmin) * (ymax - ymin) << endl;
  else
    cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(int n){
    cout << "Yes" << endl;
}

void no (int n){
    cout << "No" << endl;
}

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

Measured memory_bytes: 3588
"""
C - Traveling Plan
あらかじめ、beginからnまで、endからnまでを計算しておく
"""

point_n = int(input())

# points 場所nの座標
points = [0]
for point in input().split():
    points.append(int(point))
points.append(0)

# 添字にnで場所nまでの距離
prep_forward = []
pre_point = 0
pre_distance = 0
for point in points:
    pre_distance += abs(pre_point - point)
    prep_forward.append(pre_distance)
    pre_point = point

# 添字にnで場所nまでの距離
prep_backward = []
pre_point = 0
pre_distance = 0
for point in reversed(points):
    pre_distance += abs(pre_point - point)
    prep_backward.append(pre_distance)
    pre_point = point
prep_backward

"""
print(points)
print(prep_forward)
print(prep_backward)
"""

# 場所nを抜かして計算してみる
for n in range(1, point_n+1):
    travel_distance = prep_forward[n-1] + abs(points[n-1] - points[n+1]) + prep_backward[point_n - n]
    #print(prep_forward[n-1])
    #print(abs(points[n-1] - points[n+1]))
    #print(prep_backward[point_n - n])
    print(travel_distance)

Measured memory_bytes: 16424
int1 = lambda x: int(x) - 1
N, A, B, C, D = map(int1, input().split())
S = input()

if "##" not in S[A:B+1] and "##" not in S[C:D+1]:
    if C > D and "..." not in S[B-1:D+2]:
        print("No")
    else:
        print("Yes")
else:
    print("No")

Measured memory_bytes: 3572
import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

def main(): 
    n = int(input())
    s = []
    dic = {}
    ans = 0
    for i in range(n):
        b = ""
        a = sorted(input())
        for j in range(len(a)):
            b += str(a[j])
        s.append(b)
        if b in dic:
            dic[str(b)] = dic[str(b)] + 1
        else:
            dic[str(b)] = 1

    for key in dic:
        if dic[key] > 1:
            ans += ncr(dic[key], 2)
    
    print(int(ans))
    # print(dic)

if __name__ == "__main__":
    main()

Measured memory_bytes: 19028
a , b , c , d , e , f = 0 , 0 , 0 , 0 , 0 , 0  
num = gets.to_i
for i in 1..num
	height = gets.to_i
	if height < 165.0
		a = a + 1
	elsif 165.0 <= height && height < 170.0
		b = b + 1
	elsif 170.0 <= height && height < 175.0
		c = c + 1
	elsif 175.0 <= height && height < 180.0
		d = d + 1
	elsif 180.0 <= height && height < 185.0
		e = e + 1
	elsif 185.0 <= height
		f = f + 1
	end
end
puts "1:" + "*" * a
puts "2:" + "*" * b
puts "3:" + "*" * c
puts "4:" + "*" * d
puts "5:" + "*" * e
puts "6:" + "*" * f

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

int main(){
  int x;
  rep(i, 10000){
    cin >> x;
    if(x == 0) {
      break;
    }
    else{
      cout << "Case " << i+1 << ": " << x << endl;
    }
  }
}





Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[20];
    scanf("%s",s);
    int n=strlen(s);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='x')
            sum++;
    }
    if(sum>7)
        printf("NO\n");
    else
        printf("YES\n");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
using namespace std;
using P = pair<int, int>;
using ll = long long;

int main()
{
    int h,w,k;
    cin >> h >> w >> k;
    vector<vector<char>> c(h, vector<char>(w));
    rep(i,h)rep(j,w) cin >> c[i][j];


    int ans = 0;
    for(int i=0; i < (1<<h); i++){
        for(int j=0; j < (1<<w); j++){
            int tmp = 0;
            for(int y=0; y<h; y++){
                for(int x=0; x<w; x++){
                    if(c[y][x] == '#' && !(i & (1<<y) || j & (1<<x))){
                        tmp++;
                    } 
                }
            }
            if(tmp == k) ans++;
        }
    }


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

Measured memory_bytes: 3632
#include <iostream>


int main() {
    int A;
    long long int B, N;
    std::cin >> A >> B >> N;

    if (B - 1 <= N) {
        std::cout << int(A * ((B - 1.0) / B)) << std::endl;
    } else {
        std::cout << int(A * (double(N) / B)) << std::endl;
    }
}


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

int main(){
    int n, y, i, j;
    cin >> n >> y;
    for(i=0; i<=min(y/10000,n); i++){
        for(j=0; j<=min(y/5000, n-i); j++){
            if(i*10000+j*5000+(n-i-j)*1000 == y){
                cout << i << ' ' << j << ' ' << n-i-j;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1";
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
using namespace std;
int N;
int i = 2;
int num;
int main()
{

  scanf("%d", &N);
  long long ans = (long long)N * (N + 1) - 1;

  while (i * i <= N)
  {
    num = N / i;
    ans += (long long)(num - i + 1) * i * (i + num) - i * i;
    i += 1;
  }
  printf("%lld", ans);
}


Measured memory_bytes: 1736
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		
		int[][] S = new int[H][W];
		for (int i = 0; i < H; i++) {
			String s = sc.next();
			for (int j = 0; j < W; j++) {
				S[i][j] = s.charAt(j);
			}
		}
		System.out.println(solve(S, H, W));
	}
	static int solve(int[][] S, int H, int W) {

		boolean[][][][] a = new boolean[H][W][H][W];
		int max = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				for (int ii = 0; ii < H; ii++) {
					for (int jj = 0; jj < W; jj++) {
						a[i][j][ii][jj] = true;
						if (S[i][j] == '#' || S[ii][jj] == '#')
							continue;
						if (a[ii][jj][i][j]) {
							a[ii][jj][i][j] = true;
							continue;
						}
						if (dfs(S, H, W, i, j, ii, jj) == Integer.MAX_VALUE)
							continue;
						max = Math.max(max, dfs(S, H, W, i, j, ii, jj));
					}
				}
			}
		}
		return max;
	}
	static int dfs(int[][] S, int H, int W, int sx, int sy, int gx, int gy) {

		int[] dx = {0, 1, 0, -1};
		int[] dy = {1, 0, -1, 0};
		int[][] d = new int[H][W];
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				d[i][j] = Integer.MAX_VALUE;
			}
		}
		Queue<Masu> q = new ArrayDeque<>();
		q.add(new Masu(sx, sy));
		d[sx][sy] = 0;
		while (q.size() > 0) {

			Masu mas = q.poll();
			if (mas.x == gx && mas.y == gy) 
				break;
			for (int i = 0; i < 4; i++) {
				int nx = mas.x + dx[i];
				int ny = mas.y + dy[i];

				if (nx >= 0 && nx < H && ny >= 0 && ny < W 
					&& S[nx][ny] != '#' && d[nx][ny] == Integer.MAX_VALUE) {
					q.add(new Masu(nx, ny));
					d[nx][ny] = d[mas.x][mas.y] + 1;
				}
			}
		}
		if (d[gx][gy] == Integer.MAX_VALUE) return 0;
		else return d[gx][gy];
	}
	static class Masu {

		int x;
		int y;
		public Masu(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

Measured memory_bytes: 321116
import Data.List

conv :: [Int] -> [(Int,Int)]
conv [] = []
conv lst@(l:ls) = 
  let n = length $ takeWhile (==l) lst
  in
    (l,n):(conv $ drop n lst)

--ans :: [Int] -> [Int]
ans :: [Int] -> [(Int,Int)]
ans list =
  let sort0 = sort list
      conv0 = conv sort0
      sort1 = sortBy (\(v1,n1) (v2,n2) -> compare n2 n1) conv0
      ans   = takeWhile (\(f,s) -> s >= snd (sort1!!0)) sort1
  in
    ans

main = do
  c <- getContents
  let i = map read $ lines c :: [Int]
      o = ans i
  mapM_ (putStrLn . show . fst) o

Measured memory_bytes: 4064
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



int main(){
    ll n,x;
    cin>>n>>x;
    vector<ll> a(n);
    for(auto &I:a){cin>>I;}
    ll ans=E;
    for(int i=0;i<n;i++){
        ll cnt=x*i;
        map<ll,ll> M;
        for(int t=0;t<i;t++){M[a[t]]++;}
        ll l=0;
        for(int t=i;t<n;t++){
            M[a[t]]++;
            cnt+=M.begin()->first;
            M[a[l]]--;
            if(M[a[l]]==0){M.erase(a[l]);}
            l++;
        }
        for(int t=0;t<i;t++){
            M[a[t]]++;
            cnt+=M.begin()->first;
            M[a[l]]--;
            if(M[a[l]]==0){M.erase(a[l]);}
            l++;
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
    
    
    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		int k=s.nextInt();
		int q=s.nextInt();
		int[] a=new int[q];
		for (int i = 0; i < a.length; i++) {
			a[i]=s.nextInt();
		}
		
		int[] b=new int[n];
		
		for (int i = 0; i < a.length; i++) {
			b[a[i]-1]++;
		}
		for (int i = 0; i < b.length; i++) {
			b[i]-=q;
			//System.out.print(b[i]+" ");
			b[i]+=k;
			//System.out.println(b[i]);
		}
		for (int i = 0; i < b.length; i++) {
			if(b[i]>0) {
				System.out.println("Yes");
			}
			else {
				System.out.println("No");
			}
		}
		
	}

}


Measured memory_bytes: 57264
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define pi acos(-1)
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

lli n;
ld p[N];
ld cache[3003][3003];

ld dp(lli idx, lli heads) {

    if(idx == n + 1) {
        return (heads * 2 >= n);
    }

    ld &ans = cache[idx][heads];
    if(ans != -1)
        return ans;

    ans = (p[idx] * dp(idx + 1, heads + 1)) + ((1 - p[idx]) * dp(idx + 1, heads));

    return ans ;

}

void solve()
{


    cin>>n;
    for(int i = 1; i <= n; i ++) {
        cin>>p[i];
    }

    for(int i = 0; i <= n + 1; i ++) {
        for(int j = 0; j <= n + 1; j ++) {
            cache[i][j] = -1;
        }
    }

    cout<<fixed<<setprecision(10);

    ld ans = dp(1, 0);
    cout<<ans;

    cout<<'\n';
    return ;
}

/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 141824
#include<stdio.h>
int main(void)
{
	int a,b;

	scanf("%d %d",&a,&b);

	if(a<b){
		printf("a < b\n");
	}
	else if(a==b){
		printf("a == b\n");
	}
	else{
		printf("a > b\n");
	}
	return 0;

}


Measured memory_bytes: 2140
#include<bits/stdc++.h>
using namespace std;
const long long  maxn=2e5+5;
const long long  inf=0x3f3f3f3f;
long long a[maxn],b[maxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	if(n%2==1)
	{
		long long x=a[n/2+1];
		long long y=b[n/2+1];
		cout<<y-x+1<<endl;
	}
	else
	{
		long long x=a[n/2]+a[n/2+1];
		long long y=b[n/2]+b[n/2+1];
		cout<<y-x+1<<endl;
	}
	return 0;
}




Measured memory_bytes: 6740
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll  powFac(ll a,ll b,ll m)
{
  ll temp1=1, ans=1;
  if(a<0)temp1=0;
  else {
  for(ll i=1;i<=a;i++)temp1=temp1*i%m;
}
   while(b>0)
   {
    if(b&1)ans=ans*temp1%m;
    temp1=temp1*temp1%m;
    b>>=1;
   }
 return ans;
} 





int main()
{
   
    ll i,j,n,k,flag=0,temp1=0,temp2=0,temp3=0,m=1000000007;
   cin>>n>>k;

   for(i=1;i<=k;i++)
   {
     temp1=powFac(n-k+1,1,m);
     temp1=temp1*(powFac(i,m-2,m))%m;
     temp1=temp1*powFac(n-k-i+1,m-2,m)%m;

     temp2=powFac(k-1,1,m);
     temp2=temp2*powFac(i-1,m-2,m)%m;
     temp2=temp2*powFac(k-i,m-2,m)%m;

     temp3=temp2*temp1%m;

     cout<<temp3<<"\n";

   }
   

 return 0;
  }

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
int num[1000001];

bool sosu(int n){
	if (num[n] == -1)
		return false;
	if (num[n] == 1)
		return true;

	int sqr = sqrt(n);
	for (int i = 2; i <= sqr ;i++){
		if (n % i == 0){
			num[n] = -1;
			return false;
		}
	}
	num[n] = 1;
	return true;
}

int main()
{
	int a, d, n;
	num[1] = -1;
	while (cin >> a >> d >> n, a || d || n){
		int counter = 0;
		for (int i = a;; i = i + d){
			if (sosu(i))
				counter++;
			if (counter == n){
				cout << i<<endl;
				break;
			}
		}

	}
	return 0;
}

Measured memory_bytes: 4892
n = int(input())
r = []
for i in range(0, n):
	r.append(int(input()))

rmax = r[1] - r[0]  # 初期値は0番目と1番目の差分
imin = 0 # 最低値のindex

for i in range(1, len(r)):
	if r[i]-r[imin] > rmax:
		rmax = r[i]-r[imin]
	if r[i] < r[imin]:
		imin = i

print(rmax)


Measured memory_bytes: 13588
import java.util.*

fun main() {
    abc166b()
}

fun abc166b() {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val set = mutableSetOf<Int>()
    for (i in 1..b) {
        val d = sc.nextInt()
        for (j in 1..d) {
            val e = sc.nextInt()
            set.add(e)
        }
    }
    println(a - set.size)
}

Measured memory_bytes: 46536
#include <iostream>
#include <vector>
#include <string>

using namespace std;


int main() {
	int n;
	bool p[1000000];

	p[0] = 0;
	p[1] = 0;

	for(int i = 2; i <= 999999; i++) {
		p[i] = true;
	}

	for(int i = 2; i * i <= 999999; i++) {
		for(int j = 2; j * i <= 999999; j++) {
			p[j * i] = false;
		}
	}

	while(cin >> n) {
		int count = 0;
		for(int i = 2; i <= n; i++) {
			if(p[i] == true) {
				count++;
			}
		}

		cout << count << endl;
	}
}

Measured memory_bytes: 2136
import java.util.Scanner;

public class Main {

	static long bignum = 1000000000+7;

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		long a = sc.nextLong();
		long b = sc.nextLong();
		long n = sc.nextLong();

		double biggestbs = 0;
		if(n>=b) {
			n=b-1;
		}
		
		
		double temp = n/(double)b;
		


		System.out.println((long)(a*temp));
	}

	static long divn(int target, int times) {//10_9+7のあまり累乗版
		int sqtimes = (int)Math.sqrt(times);
		long ans = 1;
		for(int i =0;i<sqtimes;i++) {
			ans = (ans * target)%(1000000000+7);
		}
		long holder = ans;
		ans = 1;
		for(int i =0;i<sqtimes;i++) {
			ans = (ans*holder)%(1000000000+7);
		}
		for(int i=0;i<times - sqtimes*sqtimes;i++) {
			ans = (ans * target)%(1000000000+7);
		}
		return ans;
	}

	static long div(long a) {//10_9+7のあまり
		if(a<0)a+=1000000000+7;
		return a%(1000000000+7);
	}

}
/*
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: 35784
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
struct rpr{
  in x,y;
  rpr(in a=0, in b=0){
    x=a;
    y=b;
  }
  rpr sp()const{
    return rpr(y,x);
  }
  bool operator<(const rpr cp)const{
    if(x!=cp.x)
      return x<cp.x;
    return y<cp.y;
  }
};
const in ulm=in(1e10)+9;
const in crt=2500;
in sm=0;
map<rpr,in> mp;
void pr(in n){
  VI pm,pw;
  for(in i=2;i<=crt && i<=n;++i){
    if(n%i)
      continue;
    pm.PB(i);
    pw.PB(0);
    while(n%i==0){
      n/=i;
      ++pw.back();
    }
    pw.back()%=3;
  }
  if(n!=1 && n<crt*crt){
    pm.PB(n);
    pw.PB(1);
    n=1;
  }
  if(n>=crt*crt){
    in mn=crt-1;
    in mx=1e6;
    in md;
    while(mx-mn>1){
      md=(mx+mn)/2;
      if(md*md<=n)
	mn=md;
      else
	mx=md;
    }
    if(mn*mn!=n){
      ++sm;
      return;
    }
    pm.PB(mn);
    pw.PB(2);
    n=1;
  }
  in tx=1;
  in ty=1;
  forv(i,pm){
    forn(j,pw[i])
      tx*=pm[i];
    forn(j,(3-pw[i])%3){
      ty*=pm[i];
      if(ty>ulm){
	++sm;
	return;
      }
    }
  }
  ++mp[rpr(tx,ty)];
  mp[rpr(ty,tx)];
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  in s;
  forn(i,n){
    cin>>s;
    pr(s);
  }
  in t=0;
  fors(i,mp){
    if(i->first.x==1)
      ++sm;
    else
      t+=max(i->second,mp[i->first.sp()]);
  }
  sm+=t/2;
  cout<<sm<<endl;
  return 0;
}

Measured memory_bytes: 10496
#include <stdio.h>

typedef long long ll;

int main(void)
{
	ll x, price = 100, ans = 0;

	scanf("%lld", &x);

	while (price < x)
	{
		++ans;
		price = price + price / 100;
	}

	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 1732
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<sstream>
#include<map>
#include<queue>
#include<complex>
using namespace std;
#define int long long
vector<int> dat;
int sz;
void init(int n) {
	sz = 1;
	while (sz < n)sz *= 2;
	dat.clear();
	dat.resize(2 * sz, 0);
}
void update(int k, int a) {
	k += sz - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
}
int query(int a, int b, int k, int l, int r) {
	if (r <= a || b <= l)return 0;
	if (a <= l && r <= b)return dat[k];
	int m = (l + r) / 2;
	int vl = query(a, b, 2 * k + 1, l, m);
	int vr = query(a, b, 2 * k + 2, m, r);
	return max(vl, vr);
}
int query(int a, int b) {
	return query(a, b, 0, 0, sz);
}
int N;
signed main() {
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		a--;
		A[a] = i;
	}
	
	init(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		int mx = query(0, A[i]);
		//cerr << i << " " << A[i] << " " << mx << endl;
		update(A[i], mx + i + 1);
		res = max(res, mx + i + 1);
	}
	cout << (((N + 1)*N) / 2) - res << endl;
}


Measured memory_bytes: 5740
# ABC099C - Strange Bank
# DP ver.
def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  # initialize with using only ¥1
    cand = [6 ** i for i in range(1, 7) if 6 ** i <= n]
    cand += [9 ** i for i in range(1, 6) if 9 ** i <= n]
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

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

using i64 = int_fast64_t;
using f64 = double;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 n;
    cin >> n;
    map<i64, i64> m;
    for (i64 i = 0; i < n; i++) {
        i64 a;
        cin >> a;
        m[a]++;
    }

    string ans = "No";

    switch (m.size()) {
    case 1:
        if (m[0] == n) ans = "Yes";
        break;

    case 2:
        i64 key;
        for (auto& e : m) if (e.first != 0) key = e.first;
        if (m[0] == n / 3 && m[key] == 2 * n / 3) ans = "Yes";
        break;
        
    case 3:
        i64 flag0 = 0, flag1 = 0;
        for (auto& e : m) {
            flag0 ^= e.first;
            flag1 |= e.second != n / 3;
        }
        if (!flag0 && !flag1) ans = "Yes";
        break;
    }

    cout << ans << endl;
}

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


Measured memory_bytes: 5120
# coding: utf-8
# Your code here!
import math
import sys
N = int(input())
A = list(map(int, input().split()))
#A.sort()
a_dic = {}
for n in range(N):
    if A[n] in a_dic:
        a_dic[A[n]] += 1
    else:
        a_dic[A[n]] = 1
#print(a_dic)
A = list(set(A))
A.sort()
#print(A)
maxA = max(A)
dp = [1 for i in range(maxA+1)]
ans = 0
for a in A:
    if dp[a] == 1 and a_dic[a] == 1:
        ans += 1
    j = a + a
    while j <= maxA:
        dp[j] = 0
        j += a
        #print(j)
#print(dp)
print(ans)

Measured memory_bytes: 44672
#include<stdio.h>
#include <string.h>
int main()
{
    char s[1002];
    int i,h,len,j,n;
        scanf(" %[^\n]", s);
        n=0;
        len=strlen(s);
        for(j=0;j<len;j++){
            if(s[j] =='+'){
                n=n+1;
            }
            else if(s[j] == '-'){
                n=n-1;
            }}
        printf("%d\n",n);
    return 0;
}

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

int main(){
    int N,M,X,Y;
    cin >> N >> M >> X >> Y;
    vector<int> kuni_x(N);
    vector<int> kuni_y(M);
    for (int i = 0; i < N; i++){
        cin >> kuni_x.at(i);
    }
    for (int i = 0; i < M; i++){
        cin >> kuni_y.at(i);
    }
    int max_x = kuni_x.at(0);
    for (int i = 1; i < N; i++){
        max_x = max(max_x, kuni_x.at(i));
    }
    int min_y = kuni_y.at(0);
    for (int i = 1; i < M; i++){
        min_y = min(min_y, kuni_y.at(i));
    }
    if (min_y <= max_x){
        cout << "War" << endl;
    }
    else{
        int count = 0;
        for (int i = max_x; i < min_y; i++){
            if (X <= i && i < Y){
                count++;
            }
        }
        if (count >= 1){
            cout << "No War" << endl;
        }
        else{
            cout << "War" << endl;
        }
    }
}


Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
int grid[15][15] = {};
int main() {
	int n;
	cin >> n;
	REP(i, n) {
		int a;
		cin >> a;
		REP(q, a) {
			int b, c;
			cin >> b >> c;
			b--;
			grid[i][b] = c+1;
		}
	}
	int ans = 0;
	for (int i = 1; i < (1 << n); ++i) {
		int gogo = 0;
		REP(q, n) {
			if (((1 << q) & i) == 0) continue;
			gogo++;
			REP(j, n) {
				if (grid[q][j] != 0) {
					if (grid[q][j] == 1) {
						if (((1 << j) & i) != 0) {
							gogo = -10000;
						}
					}
					else {
						if (((1 << j) & i) == 0) {
							gogo = -10000;
						}
					}
				}
			}
		}
		ans = max(ans, gogo);
	}
	cout << ans << endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> p_s;
  vector<int> p;
  rep(i, n){
    ll x;
    cin >> x;
    p_s.emplace_back(x);
    p.emplace_back(x);
  }
  sort(ALL(p_s));
  ll l = p_s[n / 2 - 1];
  ll r = p_s[n / 2];
  // cout << "l " << l << endl;
  // cout << "r " << r << endl;
  rep(i, n){
    if(p[i] <= l) cout << r << endl;
    else cout << l << endl;
  }
}


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

int main(){

  char s[100006];

  scanf("%s", s);

  int i;
  int n;
  int ans = 0;
  n = strlen(s);
  for(i = 0;i < n - 1;i++){
    if(s[i] == 'W' && s[i + 1] == 'B' || s[i] == 'B' && s[i + 1] == 'W') ans++;
  }

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

  return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
struct k{
	int x,y,c;
};
queue<k> q;
int p[1002][1002],m[1002][1002];
int main(void) {
	k z,z1;
	char d;
	int v=1,h,w,n,i,j,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	cin >> h >> w>>n;
	for (i = 0; i != w + 2; i++) {
		for (j = 0; j != h + 2; j++){
			p[j][i] = 99;
			m[j][i]=0;
		}
	}for (i = 1; i != w + 1; i++) {
		for (j = 1; j != h + 1; j++){
			m[j][i]=99;
		}
	}
	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++){
			cin >> d;
			switch(d){
				case 'S':
					z.x=j;
					z.y=i;
					z.c=0;
					p[i][j]=-1;
					break;
				case '.':
					p[i][j]=-1;
					break;
				case 'X':
					p[i][j]=99;
					break;
				case '1':
					p[i][j]=1;
					break;
				case '2':
					p[i][j]=2;
					break;
				case '3':
					p[i][j]=3;
					break;
				case '4':
					p[i][j]=4;
					break;
				case '5':
					p[i][j]=5;
					break;
				case '6':
					p[i][j]=6;
					break;
				case '7':
					p[i][j]=7;
					break;
				case '8':
					p[i][j]=8;
					break;
				case '9':
					p[i][j]=9;
					break;
			}
		}
	}
	q.push(z);
	while(!q.empty()){
			z=q.front();
			q.pop();
			if(m[z.y][z.x]==v)
				continue;
			if(p[z.y][z.x]==v){
				if(p[z.y][z.x]==n)
					break;
				while(!q.empty())
					q.pop();
				q.push(z);
				v++;
				//printf("%d %d %d\n",z.x,z.y,z.c);
			}
		//	cout<<p[z.y][z.x]<<" "<<z.y<<" "<<z.x<<endl;
			m[z.y][z.x]=v;
			for(i=0;i!=4;i++){
				if(p[z.y+dy[i]][z.x+dx[i]]!=99/*&&z.x+dx[i]!=v&&z.y+dy[i]!=v*/){
					z1.x=z.x+dx[i];
					z1.y=z.y+dy[i];
					z1.c=z.c+1;
					q.push(z1);
				}
			}
	}
	cout <<z.c<< endl;
}

Measured memory_bytes: 10952
unittest
{
	assert( [ "2 3 4", "100", "600", "400", "900", "1000", "150", "2000", "899", "799" ].solve == "350\n1400\n301\n399" );
	assert( [ "1 1 3", "1", "10000000000", "2", "9999999999", "5000000000" ].solve == "10000000000\n10000000000\n14999999998" );
}



import std.algorithm;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto a = 0L;
	auto b = 0L;
	auto q = 0L;
	input.front.formattedRead!"%s %s %s"( a, b, q );
	auto ss = new long[ a ];
	foreach( ref s; ss )
	{
		input.popFront;
		s = input.front.to!( long );
	}
	auto ts = new long[ b ];
	foreach( ref t; ts )
	{
		input.popFront;
		t = input.front.to!( long );
	}
	auto xs = new long[ q ];
	foreach( ref x; xs )
	{
		input.popFront;
		x = input.front.to!( long );
	}
	
	auto anss = new long[ q ];
	auto ss_s = ( -10L ^^ 16 ~ ss ~ 10L ^^ 16 ).assumeSorted;
	auto ts_s = ( -10L ^^ 16 ~ ts ~ 10L ^^ 16 ).assumeSorted;
	foreach( ref ans, x; lockstep( anss, xs ) )
	{
		auto si = ss_s.lowerBound( x ).length.signed;
		auto sl = x - ss_s[ si - 1 ];
		auto sr = ss_s[ si ] - x;
		auto ti = ts_s.lowerBound( x ).length.signed;
		auto tl = x - ts_s[ ti - 1 ];
		auto tr = ts_s[ ti ] - x;
		ans = min( max( sl, tl ), max( sr, tr ), sl * 2 + tr, sl + tr * 2, tl * 2 + sr, tl + sr * 2 );
	}
	return anss.to!( string[] ).join( "\n" );
}


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

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

int main() {
    while(true) {
        int N, M; cin >> N >> M;
        if(N == 0) break;
        vector<pair<int, int>> PD(N);        
        rep(i, N) cin >> PD[i].second >> PD[i].first;
        sort(begin(PD), end(PD));
        reverse(begin(PD), end(PD));
        long long ans = 0;
        rep(i, N) {
            int p = PD[i].first, d = PD[i].second;
            int m = min(M, d);
            d -= m;
            M -= m;
            ans += d * p;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 3036
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/
int SUM(int m){
    int sum = 0;
    int i = 1;
    while(m > sum){
        sum += i;
        i++;
    }
    return sum;
}
int main(){
    int n; cin >> n;
    int i = 1;
    int sum = 0;
    int m = SUM(n);
    //cout << SUM(n) << endl;

    while(true){
        if(m - n == i){
            i++;
            continue;
        }
        cout << i << endl;
        sum += i;
        i++;
        if(sum == n)break;
    }
}

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

using namespace std;
int arr[10050]= {0};
int main()
{
    int n;
    cin>>n;
    for(int i = 1 ; i <= 105; i++)
    {
        for(int j = 1 ; j <= 105; j++)
        {
            for(int k = 1 ; k <= 105; k++)
            {
                int h = (i*i)+(j*j)+(k*k)+(i*j)+(i*k)+(j*k);
              //  cout<<h<<endl;
                if(h<10050)
                    arr[h]+=1;
            }
        }
    }

    for(int i = 1 ; i <= n; i++)
    {
        cout<<arr[i]<<endl;
    }

    return 0;
}


Measured memory_bytes: 3560
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
int main()
{
    string str;
    int n, digit_sum;
    n = 0;
    char c;
    while(std::cin >> str){
        n = str.length();
        if(str[0] == '0'){
            break;
        }
        digit_sum = 0;
        for (int i=0; i<n; ++i){
            c = str[i];
            digit_sum += (int)(c - '0');
        }
        std::cout << digit_sum << endl;
    }
    return 0;
}



Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

int main() {
    long long N;
    long long K;

    cin >> N >> K;

    long long V = N / K;

    N -= V*K;
    long long theMin = N;

    // N < K
    // |N-K| = K-N
    // K-N - K = N
    for (int i = 0; i < 2; ++i) {
        N -= K;

        if (N < 0) {
            N = -N;
        }

        theMin = min(theMin, N);
    }


    cout << theMin << endl;


    return 0;
}

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


int main(){
  int a,b,det,ans;
  cin>>a>>b;
  det=b-a;
  int h=0;
  for(int i=1;i<det;i++){
    h+=i;
  }
  ans=h-a;
  cout<<ans<<endl;
}


Measured memory_bytes: 256
import math
import cmath

def arg(center, point):
	return cmath.phase(complex(point[0] - center[0], point[1] - center[1]))

n = int(input())
dots = [list(map(int, input().split())) for _ in range(n)]

if n == 2:
	print(0.5)
	print(0.5)
else:
	ans = []
	for d in dots:
		arg_list = []
		for e in dots:
			if d == e:
				continue
			else:
				arg_list.append(arg(d, e))
		arg_list.sort()
		convex = False
		if arg_list[-1] - arg_list[0] <= math.pi:
			convex = True
			theta = arg_list[-1] - arg_list[0]
			ans.append(0.5 - theta / (2 * math.pi))
		else:
			for i in range(len(arg_list) - 1):
				if arg_list[i + 1] - arg_list[i] >= math.pi:
					convex = True
					theta = arg_list[i + 1] - arg_list[i]
					ans.append(theta / (2 * math.pi) - 0.5)
			if convex == False:
				ans.append(0)

	for a in ans:
		print(a)


Measured memory_bytes: 40816
A = "abcdefghijklmnopqrstuvwxyz"

def solve(X, n):
    q, r = divmod(X, 26)
    if q == 0:
        return A[r]
    return solve(q - 1, n) + A[r]

N = int(input()) - 1
print(solve(N, 26))


Measured memory_bytes: 9100
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <list>
#include <math.h>
#include <map>
using namespace std;

int dx[4] = {0,-1,1,0};
int dy[4] = {-1,0,0,1};
int main(void){
	int W, a, b;
	cin >> W >> a >> b;
	if(abs(a-b) < W){
		cout << 0 << endl;
	}else{
		cout << min(abs(a-W-b), abs(a+W-b)) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main {
	public void kami() {
		Scanner sc = new Scanner(System.in);
		long gou = 0;
		int min = 1000000;
		int max = -1000000;
		int n = sc.nextInt();
		if(n == 0){
			min = 0;
			max = 0;
		}else {
			for(int i = 1; i <= n; i++){
				int ai = sc.nextInt();
				gou = ai + gou;
				
				if(n == 1){
					min = ai;
					max = ai;
				}
				
				if(ai < min){
					min = ai;
				}else if(ai > max){
					max = ai;
				}
			}
		}
		
		System.out.println(min + " " + max + " " + gou);
	}

    public static void main(String[] args) {
		new Main().kami();
	}

}

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

int main() {
int a = 0;
cin >> a;
if(a % 2 == 0){
  cout << a / 2 * a / 2 << endl; 
}else{
  cout << (a + 1) / 2 * (a - 1) / 2 << endl;
}
}


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

#define ll long long

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;

	cin >> N;

	vector<ll> A(N);

	ll sum = 0;
	map<ll, ll>occur;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
		occur[A[i]]++;
	}

	ll Q, B, C;

	cin >> Q;

	while (Q--) {
		cin >> B >> C;

		sum += (C - B) * occur[B];

		cout << sum << endl;

		occur[C] += occur[B];
		occur[B] = 0;
	}




	return 0;
}

Measured memory_bytes: 10040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int maxn = 1e5+5;

int main ()
{
    int n;
    scanf("%d",&n);
    int cnt = 0, ans = 0;
    rep(i,1,n+1) {
        int t;
        scanf("%d",&t);
        if (t == i) {
            cnt++;
        } else {
            if (cnt == 0) continue;
            if (cnt & 1)
                ans += (cnt + 1) / 2;
            else
                ans += cnt / 2;
            cnt = 0;
        }
    }
    if (cnt & 1)
        ans += (cnt + 1) / 2;
    else
        ans += cnt / 2;
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
X = int(input())

gojo = []
i = 0
ans = 0
while ans <= 1000000000000000000:
    ans = i**5
    gojo.append(ans)
    i += 1

risou = 0
for j, B in enumerate(gojo):
    risou = B + X
    mirisou = X - B
    for k in range(j,len(gojo)):
        if gojo[k] == risou:
            print(k, j)
            exit()
        elif gojo[k] == mirisou:
            print(k, -j)
            exit()
        if gojo[k] > risou and gojo[k] > mirisou:
            break

Measured memory_bytes: 64988
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    b_ += [(b,c)]
for i in range(n):
    b_ += [(1, a[i])]

from operator import itemgetter
b_.sort(key=itemgetter(1), reverse=True)

count = n
res = 0
for j, k in b_:
    if count > j:
        res += k * j
        count -= j
    elif count <= j:
        res += k * count
        break
print(res)

Measured memory_bytes: 32072
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const int INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[4] = {1,0,-1,0};
constexpr ll ny[4] = {0,1,0,-1};
class Dijkstra{
    private:
        struct edge{
            int to,cost;
        };
        vector<vector<edge>> G;
        vector<int> d;
        int siz;
    public:
        Dijkstra(int n){
            G.resize(n);
            siz = n;
        }
        void add_edge(int from,int to,int cost){
            G[from].push_back(edge{to,cost});
        }
        vector<int> dijkstra(int s){
            priority_queue<P,vector<P>,greater<P>> q;
            d.assign(siz,INF);
            d[s] = 0;
            q.push(P(0,s));
            while(!q.empty()){
                P p = q.top();q.pop();
                int v = p.second;
                if (d[v] < p.first) continue;
                for(edge &e:G[v]){
                    if (chmin(d[e.to],d[v]+e.cost)){
                        q.push(P(d[e.to],e.to));
                    }
                }
            }
            return d;
        }
    };
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    Dijkstra g(k);
    rep(i,k){
        g.add_edge(i,(i+1)%k,1);
        g.add_edge(i,10*i%k,0);
    }
    vector<int> d;
    d = g.dijkstra(1);
    PRINT(d[0]+1);
}


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

int main() {
  string s;
  cin >> s;
  int n = s.size();
  
  if (n==1) cout << s << endl;
  else {
    bool ok = true;
    rep(i,n-1) if (s[i+1] != '9') ok = false;
    if (ok) cout << s[0] - '0' + 9 * (n-1) << endl;
    else cout << s[0] - '1' + 9 * (n-1) << endl;
  }
}

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

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

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

int main() {

	int n;
	cin >> n;
	int minus = 0, mi = INF;
	ll ans = 0;

	rep(i, n) {
		int a;

		cin >> a;

		if (a < 0) {
			minus++;
			a *= (-1);
		}

		mi = min(mi, a);
		ans += a;
	}

	if (minus % 2 == 1)ans -= 2 * (ll)mi;

	cout << ans << endl;
}

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

int main(){
  int k,x;
  cin >> k >> x;
  if(k*500 >= x)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<math.h>
#include<iterator>

using namespace std;

int main(){
  string s;
  cin >> s;
  bool isC=false;
  bool isF=false;
  for (auto&& it : s) {
    if(it == 'C')isC=true;
    if(isC){
      if(it == 'F')isF=true;
    }
  }
  if(isF)cout <<"Yes"<<endl;
  else cout <<"No"<<endl;
}


Measured memory_bytes: 256
import std;

alias sread = () => readln.chomp();
alias aryread(T = long) = () => readln.split.to!(T[]);

void main()
{
    long h, w;
    scan(h, w);
    auto s = new string[](h);
    foreach (i; 0 .. h)
    {
        s[i] = sread();

    }
    // writeln(s);
    auto ans = new long[][](h, w);
    // writeln(ans);
    long[] moves = [-1, 0, 1];

    foreach (i; 0 .. h)
    {
        foreach (j; 0 .. w)
        {
            //8方向見て#のとき+1する
            foreach (y; moves)
            {
                foreach (x; moves)

                {
                    if ((i + y < 0) || (i + y > h - 1) || (j + x < 0) || (j + x > w - 1))
                    {
                        continue;
                    }
                    if (s[i + y][j + x] == '#')
                    {
                        ans[i][j] += 1;
                    }
                }

            }
        }
    }
    // writeln(ans);
    foreach (i; 0 .. h)
    {
        foreach (j; 0 .. w)
        {
            if (s[i][j] == '.')
            {
                write(ans[i][j]);
            }
            else
            {
                write('#');
            }

        }
        writeln();
    }
}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}


Measured memory_bytes: 3648
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;

int main() {
    string s;
    cin >> s;
    int countc = 0;
    int counts = 0;
    if (s.at(0) == 'A') {
        for (int i = 2; i <= s.size() - 2; i++) {
            if (s.at(i) == 'C') countc++;
            else if (s.at(i) <= 'z' && s.at(i) >= 'a') {
                counts++;
            }
        }
        if (countc == 1 && counts == s.size() - 4) {
            if (s.at(1) <= 'z' && s.at(1) >= 'a' && s.at(s.size() - 1) <= 'z' && s.at(s.size() - 1) >= 'a') {
                cout << "AC" << endl;
                return 0;
            }
        }
    }
    cout << "WA" << endl;
}

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

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

  int res = 0, mi = n;

  for(int i=0; i<n; ++i){
    int p;
    cin >> p;
    mi = min(mi, p);
    if(mi == p) res++;
  }
  cout << res;
}


Measured memory_bytes: 256