akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3", "unroll-loops")

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

using namespace std;

#define ll long long
#define ld long double

#define MOD (998244353LL)

ll modpow(ll a, ll b) {
	if (b == 0) return 1;
	ll tmp = modpow(a, b / 2);
	if (b % 2 == 0) return tmp * tmp % MOD;
	return tmp * tmp % MOD * a % MOD;
}

signed main() {
	int n; cin >> n;
	vector<int> d(n);
	for (int i = 0; i < n; ++i) {
		int di; cin >> di;
		if (i != 0 && di == 0) {
			cout << 0 << endl;
			exit(0);
		}
		if (i == 0 && di != 0) {
			cout << 0 << endl;
			exit(0);
		}
		d[i] = di;
	}

	vector<int> c(n - 1, 0);
	for (auto di : d) ++c[di];

	ll mx = *max_element(d.begin(), d.end());
	ll ans = 1LL;
	for (int i = 1; i < mx; ++i)
		ans = (ans * modpow(c[i], c[i + 1])) % MOD;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#  corutopiさんとkuwaaaaaaaaaaaaaaaaaさんの解答を参考にした。
#
n = int(input())
height_list = [0] + list(map(int, input().split())) + [0]

# 山と谷のみに制限する
use_list = []

# 高度が上昇中が下降中かのフラグ
# True: 上昇中
# False: 加工中
# 左→右で探索する
up_flag = True
for i in range(len(height_list)-1):
    if up_flag:
        if height_list[i] > height_list[i+1]:
            # 山を検出した。山の高さを登録
            use_list.append(height_list[i])
            up_flag = False
    else:
        if height_list[i] < height_list[i+1]:
            # 谷を検出した。谷の高さを登録
            use_list.append(height_list[i])
            up_flag = True

            
# ソートしたリスト
len_list = len(use_list)
use_list2 = sorted(zip(use_list, range(len_list)))


# 沈んだかの判定
sink_list = [False] * len_list

# 島の最大値
max_count=0
# 島の数
count=1

# リストの前回使った高さ
pre_height = -1

if len_list == 1:
    max_count = 1
else:
# 低いところから沈んでいく
    for height, location in use_list2:
    
    
        if pre_height != height:
            max_count = max(max_count, count)
    

        sink_list[location] = True
    
        # 両隅が海
        if (location > 0 and not sink_list[location - 1]) and (location < (len_list - 1) and not sink_list[location + 1]):
            count += 1
        # 両隅が陸
        if (location > 0 and sink_list[location - 1]) and (location < (len_list - 1) and sink_list[location + 1]):
            count -= 1
        #  隅が沈んだ
        elif location == 0 and sink_list[1]:
            count -= 1
        elif location == (len_list - 1) and sink_list[len_list-1]:
            count -= 1
        
        pre_height = height
    
        # print(max_count, "height = ", height, ",location = ", location, ", count =" , count)
        # print(sink_list)
    
print(max_count)


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



void solve()
{
    int x, t, n;
    cin >> n >> x >> t;
    int ans;
    int times;
    if (n%x==0)
        times = n/x;
    else
        times = n/x+1;
    ans = times*t;
    cout << ans;
}

int main()
{

    solve();
    cout << "\n";

}




Measured memory_bytes: 3576
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc166_b
{
    class Program
    {
        static void Main(string[] args)
        {
            var inputSunukeAndSweets = Console.ReadLine().Split(' ');
            var SunukeNum = int.Parse(inputSunukeAndSweets[0]);
            var sweetsTypeNum = int.Parse(inputSunukeAndSweets[1]);
            var hasSweetsMembers = new List<String>();

            for (int i = 0; i < sweetsTypeNum; i++)
            {
                Console.ReadLine();
                var hasSweetsMember = Console.ReadLine().Split(' ');

                for (int j = 0; j < hasSweetsMember.Length; j++)
                {
                    hasSweetsMembers.Add(hasSweetsMember[j]);
                }
            }

            var possessedMember = hasSweetsMembers.Distinct().ToList();

            Console.WriteLine(SunukeNum - possessedMember.Count);
            Console.Read();
        }
    }
}


Measured memory_bytes: 28628
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

namespace AOJ
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            var N = Sarray()[0];
            var ringyou = new long[N + 1, N + 1];
            for (var i = 1; i <= N; ++i)
            {
                var ukv = Sarray();
                for (var j = 2; j < ukv.Length; ++j)
                {
                    ringyou[i, ukv[j]] = 1;
                }
            }
            var d = new long[N + 1];
            for (var i = 0; i < N + 1; ++i) d[i] = -1;
            var q = new Queue<long>();
            q.Enqueue(1);
            d[1] = 0;
            while(q.Any())
            {
                var v = q.Dequeue();
                for (var i = 1; i < N + 1; ++i)
                {
                    if (0 != ringyou[v, i] && d[i] == -1)
                    {
                        q.Enqueue(i);
                        d[i] = d[v] + 1;
                    }
                }
            }
            for (var i = 1; i <= N; ++i)
            {
                WriteLine($"{i} {d[i]}");
            }
        }
    }
}


Measured memory_bytes: 20888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18

int main() {
    int a, b;
    cin >> a >> b;
    if (a + b == 15)
        cout << "+" << endl;
    else if (a * b == 15)
        cout << "*" << endl;
    else
        cout << "x" << endl;
    return 0;
}

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

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

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

    int result { 0 };

    ////////////////////
    // Write your code.
    ////////////////////

    cout << int(pow(double(N),3)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <numeric>
#include <map>
#include <sstream>
#include <bitset>
using namespace std;


bool compare_by_b(pair<string, int> a, pair<string, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second > b.second;
    }
}


int main()
{
    
    int N,M;
    cin>>N>>M;
    int k[M+10];
    int s[M+10][N+10];
    int p[M+10];
    for(int i=1;i<M+1;i++){
        cin>>k[i];
        for(int j=1;j<k[i]+1;j++){
            cin>>s[i][j];
        }
    }
    for(int i=1;i<M+1;i++){
        cin>>p[i];
    }
    
    int answer=0;
    for(int i=0;i< pow(2,N);i++){
        bool flag=true;
        for(int j=1;j<M+1;j++){
            
            int sum=0;
            for(int q=1;q<k[j]+1;q++){
                sum+=(i>>(s[j][q]-1))%2;
                
            }
            if(sum%2 != p[j]){
                flag=false;
                break;
            }
            
        }
        if(flag){
            answer+=1;
        }
    }
    
    cout<<answer<<endl;
        
    }




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

#define ll long long

typedef class Point {
	public:
		ll x, y;

		Point() {	}
		Point(ll x, ll y) : x(x), y(y) {	}
} Point;

Point operator - (Point a, Point b) {
	return Point(a.x - b.x, a.y - b.y);
}
ll cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

int n;

int main() {
	scanf("%d", &n);
	vector<ll> A (n), B (n);
	for (auto& x : A) {
		scanf("%lld", &x);
	}
	for (auto& x : B) {
		scanf("%lld", &x);
	}
	int id = 0;
	for (int i = 1; i < n; i++) {
		if (A[i] > A[id]) {
			id = i;
		}
	}
	rotate(A.begin(), A.begin() + id, A.end());
	rotate(B.begin(), B.begin() + id, B.end());
	A.push_back(A[0]);
	B.push_back(B[0]);
	
	vector<ll> C (n + 1, 0);
	for (int i = 2; i <= n; i++) {
		C[i] = 2 * (C[i - 1] + B[i - 1]) - C[i - 2];
	}

	int tp = 0;
	vector<Point> stk (n + 3);
	for (int i = 0; i <= n; i++) {
		Point P (i, A[i] - C[i]);
		while (tp >= 2 && cross(stk[tp] - stk[tp - 1], P - stk[tp]) >= 0)
			tp--;
		stk[++tp] = P;
	}

	ll res = 0;
	for (int i = 2; i <= tp; i++) {
		res += (stk[i - 1].y + stk[i].y) * (stk[i].x - stk[i - 1].x);
	}
	res += stk[1].y + stk[tp].y;
	for (int i = 0; i <= n; i++) {
		res += 2 * C[i];
	}
	res -= A[0] * 2;
	double ans = 1.0 * res / (2 * n);
	printf("%.12lf\n", ans);
	return 0;
}


Measured memory_bytes: 10868
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{

    static void Main(string[] args)
    {
        var cookTimes = new int[5];
        var indexes = new int[5];
        for(int i = 0; i < cookTimes.Length; i++)
        {
            cookTimes[i] = int.Parse(Console.ReadLine());
            indexes[i] = i;
        }

        var permIndexes = GetPermutation(indexes).ToList();
        int min = int.MaxValue;
        foreach(var indexList in permIndexes)
        {

            int t = 0;
            foreach(var index in indexList)
            {
                while (t % 10 != 0) t++;

                t += cookTimes[index];
            }
            min = Math.Min(min, t);
        }

        Console.WriteLine(min);
        
    }

    public static IEnumerable<T[]> GetPermutation<T>(IEnumerable<T> items)
    {
        if (items.Count() == 1)
        {
            yield return new T[] { items.First() };
            yield break;
        }
        foreach (var item in items)
        {
            var leftside = new T[] { item };
            var unused = items.Except(leftside);
            foreach (var rightside in GetPermutation(unused))
            {
                yield return leftside.Concat(rightside).ToArray();
            }
        }
    }

}



Measured memory_bytes: 13408
using System;
public class c
{
  public static void Main()
  {
    int n=int.Parse(Console.ReadLine());
    string[] s = Console.ReadLine().Split(' ');
    int count =0;
    int min  =99999999;
    int x=0;
    for(int i=0;i<n;i++)
    {
      x=int.Parse(s[i]);
      while(true)
      {
        if(x%2!=0)break;
        x=x/2;
        count ++; 
      }
      if(count<min)min=count;
      count=0;
   
        
    }
    Console.WriteLine(min);
  }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
#include <set>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);


int main() {
  int n; cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<int> ans(n);
  rep(i,n) ans[a[i]-1] = i+1;
  rep(i,n) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 1536
N,x = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
ans += max(a[0]-x,0)
a[0] = min(a[0],x)
for i in range(N-1):
    if a[i]+a[i+1]>x:
        ans += a[i+1]+a[i]-x
        a[i+1] = x-a[i]
print(ans)

Measured memory_bytes: 14132
def bubble_sort(A):
    count = 0
    for i in range(len(A)):
        for j in range(len(A)-1):
            if A[j+1] < A[j]:
                A[j+1], A[j] = A[j], A[j+1]
                count += 1
    return count

n = int(input())
A = list(map(int, input().split()))
count = bubble_sort(A)
print(*A)
print(count)


Measured memory_bytes: 5608
#include<stdio.h>
#include<string.h>

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
	if(ch=='A')return 1;
	else if(ch=='C')return 2;
	else if(ch=='G')return 3;
	else if(ch=='T')return 4;
	else return 0;
}
long long getKey(char str[]){
	long long sum=0,p=1,i;
	for(i=0;i<strlen(str);i++){
		sum+=p*(getChar(str[i]));
		p*=5;
	}
	return sum;
}
int h1(int key){return key%M;}
int h2(int key){return 1+(key%(M-1));}

int find(char str[]){
	long long key,i,h;
	key=getKey(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0)return 0;
	}
	return 0;
}
int insert(char str[]){
	long long key,i,h;
	key=getKey(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0){
			strcpy(H[h],str);
			return 0;
		}
	}
	return 0;
}
int main(){
	int i,n,h;
	char str[L],com[9];
	for(i=0;i<M;i++)H[i][0]='\0';
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s %s",com,str);
		
		if(com[0]=='i'){
			insert(str);
		}else{
			if(find(str)){
				printf("yes\n");
			}else{
				printf("no\n");
			}
		}
	}
	return 0;
}


Measured memory_bytes: 16052
// input! macro is published in the following URLs.
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
// https://github.com/tanakh/competitive-rs.git
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        d: usize,
        n: usize,
    }
    match d {
        0 => {
            let mut count = 0;
            for i in 1.. {
                if i % 100 != 0 {
                    count += 1;
                    if count == n {
                        println!("{}", i);
                        break;
                    }
                }
            }
        }
        1 => {
            let mut count = 0;
            for i in 1.. {
                if i % 100 == 0 && i % 10000 != 0 {
                    count += 1;
                    if count == n {
                        println!("{}", i);
                        break;
                    }
                }
            }
        }
        2 => {
            let mut count = 0;
            for i in 1.. {
                if i % 10000 == 0 && i % 1000000 != 0 {
                    count += 1;
                    if count == n {
                        println!("{}", i);
                        break;
                    }
                }
            }
        }
        _ => unreachable!(),
    }
}


Measured memory_bytes: 4352
n,x,m = gets.chomp.split(" ").map(&:to_i)
hash = Hash.new(0)
cnt = 0
ans = 0
loopans = 0
loopcnt = 0
y = x
while (hash[y] == 0 || hash[y] == 1) && cnt <= n-1
  hash[y] += 1
  ans += y
  loopans += y if hash[y] == 2
  loopcnt += 1 if hash[y] == 2
  cnt += 1
  y = (y*y) % m
end
if cnt >= n
  puts ans
else
  ans += loopans * ((n-cnt) / loopcnt)
  rest = (n-cnt) % loopcnt
  rest.times do
    ans += y
    y = (y*y) % m
  end
  puts ans
end


Measured memory_bytes: 16684
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#include <vector>
#include <numeric>
#include <map>
#include <cmath>
#include <iomanip>
#include <set>
using ll =long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
using vvs = vector<vs>;

ll prime_factor_count(ll n){
    //1も必要だったら
    ll c = 1;
    int flag = 0;
    for(ll i=2; i*i <= n; i++){
        while(n%i == 0){
            if(flag == 0){
                c++;
                flag = 1;
            }
            n /= i;
        }
        flag = 0;
    }
    if(n!= 1)  c++;
    return c;

}

int main(){
    ll A, B;

    cin >> A >> B;

    ll G, tmp;

    while(1){
        tmp = A % B;
        A = B;
        B = tmp;
        if(B == 0){
            G = A;
            break;
        }
    }

    //vl soinsu = prime_factor(G);
    //map<ll, ll> ans = prime_factor_map(G);
    //ll c = prime_factor_count(G);
    ll c = prime_factor_count(G);

    cout << c << endl;

}

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

int read() {
	int x = 0, f = 0, ch;
	while(!isdigit(ch = getchar())) f |= ch == '-';
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

const int a[] = { 0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
int main() {
	int n = read();
	printf("%d", a[n]);
	return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;

const ll INF = 1e15;

inline ld calc(ll vmax, ll vmin, ll vmax_r, ll vmin_r, ll vmax_l, ll vmin_l, ld t) {
    return max({(ld)vmax, vmax_r + t, vmax_l - t}) - min({(ld)vmin, vmin_r + t, vmin_l - t});
}

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

    ll xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;
    ll ymax_u = -INF, ymin_u = INF, ymax_d = -INF, ymin_d = INF;
    ll xmax_l = -INF, xmin_l = INF, xmax_r = -INF, xmin_r = INF;
    for (int i = 0; i < n; i++) {
        ll x, y;
        char d;
        cin >> x >> y >> d;
        if (d == 'U') {
            xmax = max(xmax, x);
            xmin = min(xmin, x);
            ymax_u = max(ymax_u, y);
            ymin_u = min(ymin_u, y);
        } else if (d == 'D') {
            xmax = max(xmax, x);
            xmin = min(xmin, x);
            ymax_d = max(ymax_d, y);
            ymin_d = min(ymin_d, y);
        } else if (d == 'L') {
            ymax = max(ymax, y);
            ymin = min(ymin, y);
            xmax_l = max(xmax_l, x);
            xmin_l = min(xmin_l, x);
        } else {
            ymax = max(ymax, y);
            ymin = min(ymin, y);
            xmax_r = max(xmax_r, x);
            xmin_r = min(xmin_r, x);
        }
    }

    ld L = 0, R = 1e8;
    for (int i = 0; i <= 150; i++) {
        ld mid1 = (L * 2 + R) / 3;
        ld x1 = calc(xmax, xmin, xmax_r, xmin_r, xmax_l, xmin_l, mid1);
        ld y1 = calc(ymax, ymin, ymax_u, ymin_u, ymax_d, ymin_d, mid1);
        ld val1 = x1 * y1;

        ld mid2 = (L + R * 2) / 3;
        ld x2 = calc(xmax, xmin, xmax_r, xmin_r, xmax_l, xmin_l, mid2);
        ld y2 = calc(ymax, ymin, ymax_u, ymin_u, ymax_d, ymin_d, mid2);
        ld val2 = x2 * y2;

        if (val1 < val2) R = mid2;
        else L = mid1;    
    }

    ld x1 = calc(xmax, xmin, xmax_r, xmin_r, xmax_l, xmin_l, L);
    ld y1 = calc(ymax, ymin, ymax_u, ymin_u, ymax_d, ymin_d, L);
    ld val1 = x1 * y1;

    ld x2 = calc(xmax, xmin, xmax_r, xmin_r, xmax_l, xmin_l, R);
    ld y2 = calc(ymax, ymin, ymax_u, ymin_u, ymax_d, ymin_d, R);
    ld val2 = x2 * y2;    
    cout << fixed << setprecision(15) << min(val1, val2) << "\n";
    return 0;
}

Measured memory_bytes: 256
N = int(input())
s = []
for i in range(N):
    s.append(input().split())
M = int(input())
t = []
for i in range(M):
    t.append(input().split())

max_gain = 0
for i in range(N):
    blue = len([s[j] for j in range(N) if s[j] == s[i]])
    red = len([t[j] for j in range(M) if t[j] == s[i]])
    max_gain = max(max_gain, blue - red)

print(max_gain)


Measured memory_bytes: 3064
import sys

def make_all_cards():
    mark = ['S', 'H', 'C', 'D']
    cards = []
    
    for i in mark:
        for n in range(1, 14):
            cards.append(i + ' ' + str(n))

    return cards

if __name__ == '__main__':
    all_cards = make_all_cards()
    n = int(sys.stdin.readline().strip())

    for _ in range(n):
        card = sys.stdin.readline().strip()
        all_cards.remove(card)

    for i in all_cards:
        print(i)

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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { -1,  0, 1, 0,  1, -1,  1, -1};
static const int dy[8] = {0,  1, 0,  -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
//const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;
const int maxn = 3e5+5;

int N;
int A[maxn];



int main()
{
    memset(A,0,sizeof(A));
    cin >> N;
    _for(i,0,N){
        int a; cin >> a;
        A[a-1]++;
    }
    sort(A,A+N,greater<int>());
    int r = N-1;
    int l = N-1;
    LL sum = A[l];

    stack<LL> st;
    /*
    _for(i,0,N){
        cout << A[i] << endl;
    }
    */
    for(; r >= 0;r--){
        if(l > r){
            l--;
            sum += A[l];
        }
        while(l && (sum/(double)(r - l + 1) > (sum + A[l-1])/(double)(r - l + 2))){
            l--;
            sum += A[l];
        }

        st.push(sum/(r - l + 1));

    }
    while(!st.empty()){
        LL a = st.top();
        st.pop();
        cout << a << endl;
    }

    return 0;
}


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

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

  int64_t N3=3*N;
  vector<int64_t> vec(N3);
  for (int i = 0; i < N3; i++) {
   cin >> vec.at(i);
  }

  sort(vec.begin(), vec.end()); 
  reverse(vec.begin(), vec.end());

  int64_t count=0;
  for (int i = 0; i < 2*N; i++) {
    if (i%2==1) count+=vec.at(i);
  }

  cout << count << endl;
}

Measured memory_bytes: 2560
/*input
9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5
*/

#include <functional>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <utility> 
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>

using namespace std;

using ll = long long;
using ld = long double;

const int SINF = 1000000009;
const ll INF =  1000000000000000018;

#define sp          cout << " "
#define nl          cout << "\n"
#define all(c)      (c).begin(),(c).end()
#define prec(n)     cout << fixed << setprecision(n)
#define PI          3.14159265358979323846264338327951
#define ifalse      ios_base::sync_with_stdio(false), cin.tie(NULL)

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(auto x: v) {
    os << x << " ";
  }
  return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}

/******************************** START *********************************/
const int N = 100005;

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

  int base = 1;
  while(base <= n) {
    base = base + base;
  }

  vector < ll > tree(2 * base);
  vector < int > v1(n);
  vector < ll > v2(n);

  cin >> v1 >> v2;

  ll dp[n + 1] = {0};

  set < int > st;
  for(int i = 0; i < n; i ++) {

    ll d = v1[i] + base;
    ll mx = 0;
    while(d > 1) {
      if(d & 1) {
        mx = max(mx, tree[d - 1]);
      }
      d /= 2;
    }
    dp[v1[i]] = mx + v2[i];
    for(int j = base + v1[i]; j >= 1; j /= 2) {
      tree[j] = max(tree[j], dp[v1[i]]);
    }
  }

  ll ans = 0;
  for(int i = 0; i <= n; i ++) {
    ans = max(ans, dp[i]);
  }

  cout << ans, nl;
  return 0; 
}

Measured memory_bytes: 8320
#include <iostream>
#define int long long
using namespace std;

const int mod = 1000000007;
int n;
char c[200];
int dp[201][201];

void input() {
	cin >> n;	
	int sz = 0;
	for (int i = 0; i < n; i++) {
		char p; cin >> p;
		if (p == '-') continue;
		c[sz++] = p;
	}
	n = sz;
}

signed main() {
	input();
	
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (c[i] == 'U') {
				dp[i + 1][j + 1] += dp[i][j]; dp[i + 1][j + 1] %= mod;
				dp[i + 1][j] += dp[i][j] * j; dp[i + 1][j] %= mod;
			}
			else {
				dp[i + 1][j] += dp[i][j] * j; dp[i + 1][j] %= mod;
				if (j > 0) {
					dp[i + 1][j - 1] += dp[i][j] * j * j; dp[i + 1][j - 1] %= mod;
				}
			}
		}
	}
	cout << dp[n][0] << endl;
	return 0;
}

Measured memory_bytes: 3340
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
v(x)=x>>1<<1

function main()
    a,b,c,d,e,f,g = readline() |> split |> parseMap
    q = v(a)+b+v(d)+v(e)
    if a%2==1&&d%2==1&&e%2==1
        q += 3
    elseif  (a%2==1&&d%2==0&&e%2==1&&d>0) || (a%2==1&&d%2==1&&e%2==0&&e>0) || (a%2==0&&d%2==1&&e%2==1&&a>0)
        q += 1
    end 
    println(q)
end
main()

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

int main(){
  int i,j,k,n,m,x,y;
  cin >> n >> m >> x >> y;
  int a[n+1],b[m+1];
  for(i=0;i<n;i++)cin >> a[i];
  for(i=0;i<m;i++)cin >> b[i];
  a[n]=x;
  b[m]=y;
  sort(a,a+n+1);
  sort(b,b+m+1);
  if(a[n]<b[0])cout << "No War" << endl;
  else cout << "War" << endl;
  return 0;
}


Measured memory_bytes: 256
S,N,A,K,i,T,U;
main()
{
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
		scanf("%d%d",&A,&K);
		while(T=A/K+1,U=(A-(T-1)*K)%T)A=(T-1)*K-T+U;
		S^=T-1;
	}
	puts(S?"Takahashi":"Aoki");
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <unordered_map>
#include <set>
#include <string>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <queue>

#define N 100009

using namespace std;

char s1[N];
vector<int> comps;

int main(){
    int i,j,t1,t2,t3,t4,n,rem,lim,cur;
    bool yay;
    scanf("%s",s1+1);
    n=strlen(s1+1);
    if(s1[n]=='1' || s1[1]=='0' || s1[n-1]=='0'){
        printf("-1\n");
        return 0;
    }
    n--;
    for(i=1;i<=n/2;i++){
        if(s1[i]!=s1[n-i+1]){
            printf("-1\n");
            return 0;
        }
    }
    yay=true;
    for(i=1;i<=n;i++){
        if(s1[i]!='1'){
            yay=false;
        }
    }
    if(yay){
        for(i=1;i<=n;i++){
            printf("%d %d\n",i,i+1);
        }
        return 0;
    }   
    rem=n;
    lim=n/2;
    if(n%2){
        lim++;
    }
    comps.push_back(0);
    for(i=1;i<=lim;i++){
        if(s1[i]=='1'){
            comps.push_back(i);
        }
    }
    reverse(comps.begin(),comps.end());
    cur=2;
    printf("1 2\n");
    for(i=0;i<(int)comps.size()-1;i++){
        for(j=0;j<comps[i]-comps[i+1]-1;j++){
            printf("%d %d\n",cur,cur+1+j);
        }
        if(i==(int)comps.size()-2){
            break;
        }
        printf("%d %d\n",cur,cur+comps[i]-comps[i+1]);
        cur+=(comps[i]-comps[i+1]);
    }
    // n+1-(1+comps[0]) are left
    t1=1+comps[0];
    for(i=0;i<n+1-(1+comps[0]);i++){
        printf("1 %d\n",++t1);
    }
    return 0;
}

Measured memory_bytes: 1536
import java.util.Scanner;

public class Main {

	public class Dice {

		int[] diceInit = new int[6];
		int[] dice = new int[6];

		/**
		 * サイコロを用意する
		 * @param nums
		 */
		public Dice(int[] nums) {
			dice = nums;
			diceInit = nums;
		}

		/**
		 * サイコロの状態を確認
		 */
		public int[] checkSurface() {
			return dice;
		}


		/**
		 * 入力された方向に移動
		 * @param order
		 */
		public void move(String order) {

			for(Character s : order.toCharArray()) {
				int buf;
		        switch(s){
		            case 'N':{
		                buf = dice[0];
		                dice[0] = dice[1];
		                dice[1] = dice[5];
		                dice[5] = dice[4];
		                dice[4] = buf;
		                break;
		            }
		            case 'E':{
		                buf = dice[0];
		                dice[0] = dice[3];
		                dice[3] = dice[5];
		                dice[5] = dice[2];
		                dice[2] = buf;
		                break;
		            }
		            case 'W':{
		                buf = dice[0];
		                dice[0] = dice[2];
		                dice[2] = dice[5];
		                dice[5] = dice[3];
		                dice[3] = buf;
		                break;
		            }
		            case 'S':{
		                buf = dice[0];
		                dice[0] = dice[4];
		                dice[4] = dice[5];
		                dice[5] = dice[1];
		                dice[1] = buf;
		                break;
		            }
		            case 'R': {
		            	buf = dice[1];
		            	dice[1] = dice[2];
		            	dice[2] = dice[4];
		            	dice[4] = dice[3];
		            	dice[3] = buf;
		            }
		        }
			}
		}

		/**
		 * 指定された状態になるまで回転を行う
		 * @param upper
		 * @param flont
		 * @return dice サイコロの状態
		 */
		public int[] checkRight(int upper, int front) {

			// サイコロを初期状態にリセット
			dice = diceInit;

			// 上面が指定の面になるまで回転
			for(int i=0; i<3; i++) {
				if(dice[0] == upper) break;
				move("W");
			}
			if(dice[0] != upper) {
				for(int i=0; i<3; i++) {
					if(dice[0] == upper) break;
					move("N");
				}
			}

			// 正面が指定の面になるまで回転
			for(int i=0; i<3; i++) {
				if(dice[1] == front) break;
				move("R");
			}

			return dice;
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int[] nums = new int[6];
		for(int i=0; i<6; i++) {
			nums[i] = sc.nextInt();
		}

		Dice dice = new Main().new Dice(nums);

		int n = sc.nextInt();
		for(int i=0; i<n; i++) {
			int upper = sc.nextInt();
			int front = sc.nextInt();
			int[] surface = dice.checkRight(upper, front);
			System.out.println(surface[2]);
		}
		sc.close();

	}

}


Measured memory_bytes: 26176
#include <stdio.h>
#include <string.h>
int main(void)
{
	char s[101];
	char t[101];
	char temp[101];
	int flag = 0;
	scanf("%s", s);
	scanf("%s", t);
	int slen = strlen(s);

	for (int i = 0; i < slen; i++)
	{
		char c = s[slen - 1];
		for (int j = slen - 1; j > 0; j--)
		{
			s[j] = s[j - 1];
		}
		s[0] = c;
		if (strcmp(s, t) == 0)
		{
			puts("Yes");
			flag = 1;
			break;
		}	
	}
	if (flag == 0)	puts("No");
	return 0;

}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

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

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

int dist[100005];
vector<P_ii> g[100005];

bool dfs(int s,int p){
    for(auto to:g[s]){
        if(to.first == p) continue;
        if(dist[to.first]==-1) {
            dist[to.first] = dist[s] + to.second;
            if(dfs(to.first,s)) return true;
        } else {
            if(dist[to.first] != dist[s] + to.second) return true;
        }
    }

    return false;
}

int main() {
    int N,M;
    cin >> N >> M;


    REP(i,M){
        int L,R,D;
        cin >> L >> R >> D;
        L--;R--;
        g[L].push_back({R,D});
        g[R].push_back({L,-D});
    }

    memset(dist,-1,sizeof(dist));

    int flg = dfs(0,-1);
    REP(i,N-1){
        if(flg) break;
        if(dist[i+1]!=-1) continue;

        flg = dfs(i+1,-1);
    }

    Yes(!flg)

    return 0;
}


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

int n;
vector<int> a;
vector<vector<int>> e;
vector<int> dp;
vector<int> ans;

void dfs(int pre, int crt, int size)
{
  auto ud = lower_bound(dp.begin(), dp.begin() + size + 1, a[crt]);
  int tmp = *ud;
  *ud = a[crt];
  if (tmp == INT_MAX)
    size++;
  ans[crt] = size;
  for (int i : e[crt])
    if (i != pre)
      dfs(crt, i, size);
  *ud = tmp;
}

int main()
{
  cin >> n;
  a.resize(n);
  rep(i, n)
    cin >> a[i];
  e.resize(n);
  rep(i, n - 1)
  {
    int u, v;
    cin >> u >> v;
    e[u-1].push_back(v - 1);
    e[v-1].push_back(u - 1);
  }
  ans.resize(n);
  dp.resize(n);
  fill(dp.begin(), dp.end(), INT_MAX);
  dfs(-1, 0, 0);
  rep(i, n)
    printf("%d\n", ans[i]);
  return 0;
}

Measured memory_bytes: 30956
using System;

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var tpl = new Tuple<string, int, int>[n];
        for (int i = 0; i < n; i++)
        {
            var sp = Console.ReadLine().Split();
            tpl[i] = Tuple.Create(sp[0], 100 - int.Parse(sp[1]), i + 1);
        }

        Array.Sort(tpl);

        for (int i = 0; i < n; i++)
        {
            Console.WriteLine(tpl[i].Item3);
        }
    }
}


Measured memory_bytes: 13408
// include
// ----------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>

// repetition
// ----------------------------------------------------------------------------
#define FOR(i, a, b) for (i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// memory clear
// ----------------------------------------------------------------------------
#define CLRNUM(a) memset((a), 0, sizeof(a))
#define CLRBOOL(a, flag) memset((a), flag, sizeof(a))
#define CLRCHAR(a) memset((a), '\0', sizeof(a))

// debug
// ----------------------------------------------------------------------------
#define DEBUGINT(x) printf("%d\n", x);
#define DEBUGFLOAT(x) printf("%f\n", x);
#define DEBUGCHAR(x) printf("%c\n", x);
#define DEBUGSTR(x) printf("%s\n", x);
#define DEBUGFORINT(i, a, b, x) FOR(i, a, b){ printf("%d ", x[i]); }
#define DEBUGFORFLOAT(i, a, b,x ) FOR(i, a, b){ printf("%f ", x[i]); }
#define DEBUGFORCHAR(i, a, b, x) FOR(i, a, b){ printf("%c ", x[i]); }
#define DEBUGREPINT(i, n, x) REP(i, n){ printf("%d ", x[i]); }
#define DEBUGREPFLOAT(i, n, x) REP(i, n){ printf("%f ", x[i]); }
#define DEBUGREPCHAR(i, n, x) REP(i, n){ printf("%c ", x[i]); }

// other
// ----------------------------------------------------------------------------
#define PUTNL printf("\n")

// constant
// ----------------------------------------------------------------------------
#define INF 1000000000

int main(void)
{
    int student;
    int num;
    int i;

    while (scanf("%d", &num) != EOF){
        student = 1;

        for (i = 1; i < num; ++i){
            if (student < 39){
                student++;
            }
            else if (student == 39){
                student = 1;
            }
        }
        
        printf("3C%02d\n", student);
    }
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
int N, X;

int A[199999];
int main() {
  cin >> N >> X;
  if(X == 1 || X == 2 * N - 1){
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
    
    if (N == 2) {
      cout << 1 << endl;
      cout << 2 << endl;
      cout << 3 << endl;
    } else {
      if (X == 2){
        A[N - 2] = 3;
        A[N - 1] = 2;
        A[N    ] = 1;
        A[N + 1] = 4;
      } else {
        A[N - 2] = X - 1;
        A[N - 1] = X;
        A[N    ] = X + 1;
        A[N + 1] = X - 2;
      }
      
      int j = 0;
      for(int i = 1; i <= 2 * N - 1; ++i){
        if(A[N - 2] == i) continue;
        if(A[N - 1] == i) continue;
        if(A[N    ] == i) continue;
        if(A[N + 1] == i) continue;
        A[j] = i; 
        while(A[j] != 0) ++j;
      }
      
      for(int i = 0; i < 2 * N - 1; ++i){
        cout << A[i] << endl;
      }
    }
  }
}

Measured memory_bytes: 2304
#include <iostream>
#include <vector>

using namespace std;
using llong = long long;
llong A[200000];
llong prefix_sum[200001]={0};
int main(){
  int N;
  cin >> N;
  for(int i=0;i<N;++i){
    cin >> A[i];
    prefix_sum[i+1] += prefix_sum[i]+A[i];
  }
  
  llong min_dif = 10000000000;
  for(int i=1;i<N;++i){
    auto dif = abs(prefix_sum[N]-2*prefix_sum[i]);
    if(dif<min_dif){
      min_dif = dif;
    }
  }
  
  cout << min_dif << endl;
  return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

using llint = long long int;

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr long long int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;



class Graph{
public:
    ////////////グラフサイズを渡して作成する
    ////////////infの値は必要に応じて調整すること
    Graph(long long int n):g_size(n),edges(n,vector<long long int>(n,inf)){
        REP(i,n){
            edges[i][i] = 0;
        }


    }
    

    ///////////初期状態では有向
    ///////////無向にするときは
    /*  edges[b][a] = cost;  */
    //を追加
    void add_edge(long long int a,long long int b,long long int cost=1){
        edges[a][b] = cost;
        edges[b][a] = cost;  
    }

    llint solve(){
        llint result = 0;
        result += search(0,1<<0);
        return result;
    }
    llint search(llint n,llint bit){
        if(bit==(1<<g_size)-1){
            return 1;
        }
        llint result = 0;
        REP(i,g_size){
            if(edges[n][i]!=1||((1<<i)&bit)){
                continue;
            }else if(((bit | (1 << i)))==(1<<g_size)-1){
                    return 1;
            }else{
                result += search(i, (bit | (1 << i)));
            }
        }
        return result;
    }
  
private:
    long long int g_size;
    vector<vector<long long int>> edges;
  
};


int main(){

    llint n, m;
    cin >> n >> m;
    Graph graph(n);
    llint tmpa, tmpb;
    REP(i,m){
        cin >> tmpa >> tmpb;
        graph.add_edge(tmpa-1, tmpb-1);
    }
    cout << graph.solve() << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

void insertionSort(int *A, int n) {
	for(int i=1; i<n; i++) {
		int v=A[i];
		int j=i-1;
		while(j>=0 && A[j]>v) {
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=v;
		cout<<A[0];
		for(int k=1; k<n; k++) cout<<' '<<A[k];
		cout<<'\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, A[1000];
	cin>>n;
	for(int i=0; i<n; i++) cin>>A[i];
	cout<<A[0];
	for(int i=1; i<n; i++) cout<<' '<<A[i];
	cout<<'\n';
	insertionSort(A, n);
	return 0;
}



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

/* -------------------------------- Template -------------------------------- */

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf() { assert(false); }
template<> constexpr int inf<int>() { return 1e9; }
template<> constexpr ll inf<ll>() { return 1e18; }
template<> constexpr ld inf<ld>() { return 1e30; }

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

int main() {
  int N, a;
  cin >> N;
  ll res = 0, n = 1;
  REP(i,N) {
    cin >> a;
    if (a == n) {
      ++n;
    }
    else if (a > n) {
      res += (a - 1) / n;
    }
    chmax(n, 2LL);
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b>>c;
if(a>b)swap(a,b);
if(b>c)swap(b,c);
if(a>b)swap(a,b);
cout<<a<<" "<<b<<" "<<c<<endl;
}


Measured memory_bytes: 3104
M = 10**9 + 7
def pow(x, n):
    if n == 0:
        return 1
    res = pow(x * x % M, n//2)
    if n % 2 == 1:
        res = res * x % M
    return res

n, a, b = map(int, input().split())
base = (pow(2, n) - 1) % M
inv_t = [0]+[1]
ns = [0, n % M]
max_ab = max(a, b)
min_ab = min(a, b)
for i in range(2,max_ab+1):
    inv_t += [inv_t[M % i] * (M - int(M / i)) % M]
    n -= 1
    ns += [(ns[-1] * n) % M]
aa = ns[a]
bb = ns[b]
for i in range(2,min_ab+1):
    aa = (aa * inv_t[i]) % M
for i in range(2,max_ab+1):
    bb = (bb * inv_t[i]) % M
print(((base - aa)%M - bb)%M)

Measured memory_bytes: 60780
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author naruse
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        LuckyPIN solver = new LuckyPIN();
        solver.solve(1, in, out);
        out.close();
    }

    static class LuckyPIN {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            String s = in.next();
            int cnt[][] = new int[10][n];
            for (int i = 0; i < n; i++) {
                cnt[s.charAt(i) - '0'][i] = 1;
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < 10; j++) {
                    cnt[j][i] = cnt[j][i] + cnt[j][i - 1];
                }
            }
            long ans = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    for (int k = 0; k < 10; k++) {
                        for (int l = 1; l < n - 1; l++) {
                            if (s.charAt(l) - '0' != j) continue;
//                        ans += cnt[i][l - 1] * (cnt[k][n - 1] - cnt[k][l]);
                            if (cnt[i][l - 1] * (cnt[k][n - 1] - cnt[k][l]) > 0) {
                                ans++;
                                break;
                            }
                        }
                    }
                }
            }
            out.println(ans);
        }

    }
}



Measured memory_bytes: 24732
#include<stdio.h>

int dai(int a,int b,int h){
  return (a+b)*h/2;
}

int main(){
  int a,b,h;
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&h);
  printf("%d",dai(a,b,h));
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

int main(){
    vector<int> c(5);
    REP(i,5) cin>>c[i];
    int k;cin>>k;
    REP(i,5){
        REP(j,5){
            if (abs(c[i]-c[j])>k){
                cout<<":("<<endl;
                return 0;
            }
        }
    }
    cout<<"Yay!"<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

int main(void) {
	char  str[4];
	s_cin(str);
	if(str[0]==str[2])
		 s_cout("Yes");
	else s_cout("No");
	return 0;
}


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

typedef vector<int> vi;
typedef pair<int, int> pi;

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); ++i)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

signed main() {
    int A, B;
    cin >> A >> B;

    if (1 <= A && A <= 9 && 1 <= B && B <= 9) {
        cout << A * B << endl;
    } else {
        cout << -1 << 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);
		int w = sc.nextInt();
		int h = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		
		double s = (double)w * h / 2;
		System.out.print(s);
		
		if (x*2==w&&y*2==h) {
			System.out.println(" 1");
		} else {
			System.out.println(" 0");
		}
		
		sc.close();
	}
}

Measured memory_bytes: 23124