akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)

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

    int n, m, r;
    cin >> n >> m >> r;

    vector<int> R(r);
    REP(i, r){
        cin >> R[i];
        R[i]--;
    }
  sort(R.begin(),R.end());

    int A[n][n] = {};
    REP(i, n){
        REP(j, n){
            if(i != j) A[i][j] = 1e9;
        }
    }

    REP(i, m){
        int a, b, c;
        cin >>  a >> b >> c;
        a--; b--;
        A[a][b] = c;
        A[b][a] = c;
    }

    REP(i, n){
        REP(j, n){
            REP(k, n){
                A[j][k] = min(A[j][k], A[j][i] + A[i][k]);
            }
        }
    }

    int ans = 1e9;
    do{
        int cost = 0;
        REP(i, r - 1){
            cost += A[R[i]][R[i + 1]];
        }
        ans = min(ans, cost);
    }while(next_permutation(R.begin(), R.end()));

    /*
    REP(i, n){
        REP(j, n){
            cout << A[i][j] << " ";
        }
        cout << endl; 
    }
    */

    cout << ans << endl; 

    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
int main()
{
    char s[4];
    
    scanf("%s",s);
    
    int i,j,cnt1=0,cnt2=0;
    
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            if(s[i]==s[j])
            cnt1++;
            else
            cnt2++;
        }
    }
    
    if(cnt1==8 && cnt2==8)
    printf("Yes");
    else
    printf("No");
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#include <cstring>
#include <cctype>
#include <random>

using namespace std;
typedef long long  ll;
const ll INF = 1000000007;
const ll mod = 998244353;

vector<ll> dp(2 * 100000 + 1, -1);
vector<ll> popcount(2 * 100000 + 1, 0);

int pcnt(int x) {
	return __builtin_popcount(x);
}

int f(int x) {
	if (x == 0) return 0;
	return f(x % pcnt(x)) + 1;
}

int main()
{
	ll n;
	cin >> n;
	string s;
	cin >> s;
	vector<ll> x(n);
	// 0,1変換
	for (ll i = 0; i < n; i++)
	{
		x[i] = s[i] - '0';
	}
	// xのpopcount
	ll pc = 0;
	for (ll i = 0; i < n; i++)
	{
		pc += x[i];
	}
	vector<ll> ans(n);
	for (ll b = 0; b < 2; b++)
	{
		ll npc = pc;
		if (b == 0) npc++; else npc--;
		if (npc <= 0) continue;
		// xのnpc
		ll r0 = 0;
		for (ll i = 0; i < n; i++)
		{
			r0 = (r0 * 2) % npc;
			r0 += x[i];
		}
		ll k = 1;
		for (ll i = n - 1; i >= 0; --i) {
			if (x[i] == b) {
				int r = r0;
				if (b == 0) r = (r + k) % npc;
				else r = (r - k + npc) % npc;
				ans[i] = f(r) + 1;
			}
			k = (k * 2) % npc;
		}
	}

	for (ll i = 0; i < n; i++)
	{
		cout << ans[i] << endl;
	}
	return 0;
}

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

int d[4]={0};

int main(void){
	string s; cin >> s;
	int n=s.size();
	for(int i=0;i<n;i++){
		if(s[i]=='N') d[0]=1;
		if(s[i]=='W') d[1]=1;
		if(s[i]=='S') d[2]=-1;
		if(s[i]=='E') d[3]=-1;
	}
	
	if(d[0]+d[2]==0&&d[1]+d[3]==0){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }

	return 0;
}


Measured memory_bytes: 256
import heapq
Q = int(input())

# 中央値の左側の値、右側の値を管理する
# heapqとする。rightは最小が興味あるが、leftは最大なので、-1をかけて扱う
left, right = [], []
# 両方のSUMも管理する必要がある。毎回SUMしてたら間に合わん
Lsum, Rsum = 0,0
Lcnt, Rcnt = 0,0
B = 0
for _ in range(Q):
  q = list(map(int, input().split()))
  if len(q) == 1:
    # 2
    # heapqってPeakできないの・・・？
    l = (-1) * heapq.heappop(left)
    heapq.heappush(left,(-1)*l)
    # (l-l1) + (l-l2) + ... + (l-l) + (r-l) + ... + (r1 - l)
    print(l, Rsum//2 - Lsum//2 + B)
    #print(left,right, Lsum, Rsum)
  else:
    # 1
    _,a,b = q
    B += b
    # まず双方にaを突っ込む
    heapq.heappush(left,(-1)*a)
    heapq.heappush(right,a)
    Lsum += a
    Lcnt += 1
    Rsum += a
    Rcnt += 1
    # leftの最大値と、rightの最小値の関係が崩れていたら、交換する
    l = (-1) * heapq.heappop(left)
    r = heapq.heappop(right)
    if l>=r:
      Lsum = Lsum - l + r
      Rsum = Rsum - r + l
      l,r = r,l
    heapq.heappush(left,(-1)*l)
    heapq.heappush(right,r)

Measured memory_bytes: 104120
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int dp[5005][5005];
int mod = 1000000007;
inline void add(int &a,int b){
    a += b;
    if(a >= mod) a -= mod;
}
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int m = (int) s.size();
    dp[0][0] = 1;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if(j)add(dp[i+1][j-1],dp[i][j]);
            else add(dp[i+1][j],dp[i][j]);
            add(dp[i+1][j+1],dp[i][j]);
            add(dp[i+1][j+1],dp[i][j]);
        }
    }
    ll inv = (mod + 1) /2;
    ll ans = dp[n][m];
    rep(i,m) (ans *= inv) %= mod;
    cout << ans << endl;
}

Measured memory_bytes: 98048
#include <iostream>
using namespace std;
int main()
{
	while(true){
		int w;
		cin >> w;
		if(w==-1)
			break;

		int x=0,y=0;
		
		if(w>=0 && w<10)
			y = 1150;
		else if(w>=10 && w<20){
			x = w-10;
			y = 1150 + 125*x;
		}
		else if(w>=20 && w<30){
			x = w-20;
			y = 1150 + 125*10 + 140*x;
		}
		else if(w>=30){
			x = w-30;
			y = 1150 + 125*10 + 140*10 + 160*x;
		}

		cout << (4280 - y) << endl;
	}
	return 0;
}

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

using namespace std;

int main(){
  int N;
  cin >> N;
  if(N==1){
    return 0;
  }
  vector<vector<int>> info(N-1,vector<int>(3));
  for(int i=0;i<N-1;++i){
    cin >> info[i][0] >> info[i][1] >> info[i][2];
  }
  
  for(int i=0;i<N-1;++i){
    int total_time = 0;
    for(int j=i;j<N-1;++j){ 
      if(info[j][1] >= total_time){
        total_time = info[j][1]+info[j][0];
      }else{
        int tmp1 = (total_time-info[j][1] + info[j][2] -1)/info[j][2];
        total_time = info[j][1] + tmp1*info[j][2] + info[j][0];
      }
    }
    cout << total_time << endl;
  }
  cout << 0 << endl; // start from last station
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,i,k;
      long int num=0;
      cin>>n>>k;
      int ar[n];
      for(i=0;i<n;i++){
      cin>>ar[i];
    }
      sort(ar,ar+n);
      for(i=0;i<n-k;i++){
        num+=ar[i];
    }
      cout<<num;
  return 0;
}

Measured memory_bytes: 1024
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024*1024), bufio.MaxScanTokenSize)
}

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	L := nextInt()
	R := nextInt()
	MIN := 214748347
	for i := L; i < R; i++ {
		for j := i + 1; j <= R; j++ {
			MIN = min(MIN, (i*j)%2019)
			if MIN == 0 {
				fmt.Println(MIN)
				return
			}
		}
	}
	fmt.Println(MIN)
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}


Measured memory_bytes: 1804
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
  ll a;
  cin>>a;
  vector<ll>vec(a);
  for(ll i=0;i<a;i++){
    cin>>vec.at(i);
  }
  if(a==1){
    cout<<"Yes"<<endl;
    return 0;
  }
  for(ll i=0;i<a-1;i++){
    if(vec.at(i)-vec.at(i+1)>1){
      cout<<"No"<<endl;
      return 0;
    }
    if(vec.at(i)>vec.at(i+1)){
      vec.at(i+1)+=1;
    }
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 4000
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {

    class ClassMain {

        public static void Main(String[] args) {
            string line;

            while ((line = Console.ReadLine()) != null) {
                int n = int.Parse(line);
                if (n == 0) { break; }
                int[] ageHist = new int[7];
                for (int i = 0; i < n; i++) {
                    int k = int.Parse(Console.ReadLine());
                    int k2 = k / 10;
                    if (k2 >= 6) { ageHist[6]++; }
                    else { ageHist[k2]++; }
                }
                for (int i = 0; i < 7; i++) {
                    Console.WriteLine(ageHist[i]);
                }
            }
        }
    }

}

Measured memory_bytes: 5816
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
const ll INF = 1e9 + 7;
typedef pair<int,int> P;// pair型は２つの値の組を表せる

int main(){
    int N; cin >> N;
    int ans=0;
    if (N%2!=0) ans=N/2+1;
    else ans=N/2;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _i in range(m)]
 
visit = [-1 for _ in range(n)]
visit[0] = 0
tree = [[] for _ in range(n)]
for a, b in ab:
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
 
from collections import deque
q = deque([0])
while q:
    p = q.popleft()
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = p
            q.append(i)
if all(i >= 0 for i in visit):
    print("Yes")
    for i in visit[1:]:
        print(i+1)
else:
    print("No")


Measured memory_bytes: 70784
n, m = map(int , input().split())

k = []
num_list = []
for x in range(n):
    a = list(map(int, input().split()))
    k.append(a[1:])
    num_list += a[1:]

num_list = list(set(num_list))

result = 0

for x in num_list:
    for a in k:
        f = False
        for b in a :
            if b == x:
                f = True
        if f != True:
            break
    if f :
        result += 1

print(result)

Measured memory_bytes: 3064
def main():
    A, B, C, D = map(int, input().split())

    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

    def lcm(a, b):
        return a * b // gcd(a, b)

    def count(x, c, d) -> int:
        return x - x // c - x // d + x // lcm(c, d)

    res = count(B, C, D) - count(A - 1, C, D)
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
def operation_of_foa(input_seq, times)
	operated_seq = Array.new
	count_seq = Hash.new
	input_seq.each do |n|
		if count_seq.has_key?(n)
			count_seq[n] += 1
		else
			count_seq[n] = 1
		end
	end
	input_seq.each do |n|
		operated_seq << count_seq[n]
	end
	if operated_seq == input_seq
		return [operated_seq, times-1]
	else
		operation_of_foa(operated_seq, times+1)
	end
end

def print_seq(seq_times)
	puts seq_times.last
	seq_times.first.each.with_index { |x,i| print (i.zero? ? x : " #{x}") }
	puts ""
end
while gets
	n = $_.to_i
	break if n == 0
	input_seq = gets.chomp.split.map(&:to_i)
	print_seq(operation_of_foa(input_seq, 1))
end

Measured memory_bytes: 6136
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new java.util.Scanner(System.in);
		int N = in.nextInt();
		int count2 = 0;
		int count4 = 0;
		for(int i=0; i<N; i++){
			int tmp = in.nextInt();
			if(tmp%2==0 && tmp%4!=0){
				count2++;
			}else if(tmp%4==0){
				count4++;
			}
		}
		if((N-count2-count4) > 1+count4){
			System.out.println("No");

		}else if((N-count2-count4) == count4+1 && count2!=0){
			System.out.println("No");
		}else{
			System.out.println("Yes");

		}
		
	}
}


Measured memory_bytes: 47144
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
double x1,x2,y1,y2;
cin >>x1 >>y1 >>x2 >>y2;
double d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
printf("%lf\n",d);
return 0;
}

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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  ll n, x;
  cin >> n >> x;

  vector<ll> va(n);
  for (int i = 0; i < n; ++i) {
    cin >> va[i];
  }

  ll ans = 0;
  if (va.front() > x) {
    ans += va.front() - x;
    va[0] = x;
  }

  for (int i = 1; i < va.size(); ++i) {
    ll sum = va[i] + va[i - 1];
    if (sum > x) {
      va[i] -= sum - x;
      ans += sum - x;
    }
  }

  cout << ans << '\n';
}

Measured memory_bytes: 4040
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    String s = sc.next();
    if (s.equals("ABC")) {
      pw.println("ARC");
    } else {
      pw.println("ABC");
    }
  }
}


Measured memory_bytes: 35656
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <string>
#include <cctype>
#include <cstdio>
#include <math.h>
using f32 = float;
using f64 = double;
using f80 = __float80;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vs = vector<string>;
using vl = vector<LL>;
using vvl = vector<vl>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
#define REP(i, n) for (LL i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (LL i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define fst first
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define sw swap
#define UP(x) transform(x.begin(), x.end(), x.begin(), ::toupper);
#define LOW(x) transform(x.begin(), x.end(), x.begin(), ::tolower);
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
int main(){
	LL s;
	cin>>s;
	const LL v=1000000000;
	LL x=(v-s%v)%v;
	LL y=(s+x)/v;
	
	cout<<"0 0 1000000000 1 "<<x<<" "<<y<<endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main implements Comparable<Main> {
	int no;
	String name;

	Main(int no, String name) {
		this.no = no;
		this.name = name;
	}

	public int compareTo(Main main) {
		int ret = this.name.compareTo(main.name);

		if (ret != 0) {
			return ret;
		}
		return Integer.compare(this.no, main.no) * -1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		List<Main> main = new ArrayList<>();
		int[] point = new int[N]; 
		

		for(int i = 0; i < N; i++) {
			String str = sc.next();
			int n = sc.nextInt();
			main.add(new Main(n, str));
			point[i] = n;
		}

		Collections.sort(main);

		for(Main m : main) {
			for(int i = 0; i < N; i++) {
				if(point[i] == m.no) {
					System.out.println(i + 1);
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 21716
#include <iostream>

using namespace std;

bool prime(int n)
{
	if(n < 2){
		return false;
	} else if(n == 2){
		return true;
	}
	
	if(n % 2 == 0){
		return false;
	}
	
	for(int i = 3; i*i <= n; i+= 2){
		if(n % i == 0){
			return false;
		}
	}
	
	return true;
}

int main(int argc, char **argv)
{
	int n, c;
	
	while(cin >> n){
		c = 0;
		for(int i = 2; i < n; i++){
			if(prime(i)&&prime(n-i+1)){
				c++;
			}
		}
		cout << c << endl;
	}
	
	return 0;
}

Measured memory_bytes: 868
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(), (x).end())
#define Reverse(x) reverse((x).begin(), (x).end())
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15) //15桁まで表示
#define str string
typedef std::pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ui,ui> puu;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<str> vs;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int floor(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template<class T>inline bool chmax(T& a,T b){if(a < b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a > b){a=b;return true;}return false;};

int main() {
    int n,ans=0,cnt=1;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];
    Sort(a);
    REP(i,1,n){
        //cout<<cnt<<endl;
        if(a[i]==a[i-1]) cnt++;
        else{
            if (a[i-1]<=cnt) ans+=cnt-a[i-1];
            else ans+=cnt;
            cnt=1;
        }
    }
    if (a[n-1]<=cnt) ans+=cnt-a[n-1];
    else ans+=cnt;
    cout << ans << endl;
}

Measured memory_bytes: 640
import scala.io.StdIn

object Main{
  def main(args: Array[String]){
    val num = StdIn.readLine()
    var cards = Array.ofDim[Boolean](4, 14)

    for(i <- 1 to num.toInt){
      val sai = StdIn.readLine().split(" ")
      sai(0) match{
        case "S" => cards(0)(sai(1).toInt) = true
        case "H" => cards(1)(sai(1).toInt) = true
        case "C" => cards(2)(sai(1).toInt) = true
        case "D" => cards(3)(sai(1).toInt) = true
        case _ => None
      }
    }

    for(i <- 0 to 3){
      for(j <- 1 to 13){
        if(cards(i)(j) == false){
          i match{
            case 0 => println("S " + j)
            case 1 => println("H " + j)
            case 2 => println("C " + j)
            case 3 => println("D " + j)
            case _ => None
          }
        }
      }
    }
  }
}

Measured memory_bytes: 43800
#include<bits/stdc++.h>
#include<boost/algorithm/string/replace.hpp>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::algorithm;
using namespace boost::multiprecision;
 
#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define ALL(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;
 
const int INF = 1e9;
const int MOD = 1e9+7;

//C++17
template<typename Type>
Type GCD(Type a,Type b){ return b ? GCD(b,a%b) : a ;}
template<typename Type>
Type LCM(Type a,Type b){ return a*b / GCD(a,b) ;}

template<typename Type>//文字列の置換/Boost:replace_all()
Type replace_str(Type str, string target, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(target, pos), pos != string::npos) {
        str.replace(pos, target.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main() {
    int n;cin >> n;
    vector<int> x(n);
    vector<int> y(n);
    rep(i,n)cin >> x[i] >> y[i];

    if(n==1){
        cout << 1 << endl;
        return 0;
    }
    int ans = n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            int dx = x[j] - x[i];
            int dy = y[j] - y[i];

            int sub = 0;
            for(int i2=0;i2<n;i2++){
                for(int j2=0;j2<n;j2++){
                    if(i2==j2)continue;
                    if(dx == x[j2] - x[i2] && dy == y[j2] - y[i2])sub++;
                }
            }
            ans = min(ans,n-sub);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define db(x){if(cond)cerr<<__LINE__<<" "<<#x<<" " <<x<<endl;}
#define rep(i,b)for(auto i=(0);i<(b);++i)
#define fo(i,a,b)for(auto i=(a);i<=(b);++i)
#define ford(i,a,b)for(auto i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define vv vector
#define pb push_back
template<typename X>void MA(X&a,X b){a=max(a,b);}template<typename X>void MI(X&a,X b){a=min(a,b);}
template<typename X>void clr(X&x,int a){memset(x,a,sizeof(a));};typedef long long ll;typedef long double ld;
typedef array<int,2>i2;typedef vv<int>vi;int cond=0,multi=0,gcj=0;

struct solver_t;solver_t *solver;
struct solver_t{


  void solve(){
    ll N;cin>>N;
    ll sum;cin>>sum;
    sum/=1000;

    fo(b10,0,N){
      fo(b5,0,N-b10){
        if(9*b10+4*b5+N==sum){
          cout<<b10<<" "<<b5<<" "<<N-b10-b5<<"\n";
          return;
        }
      }
    }
    cout<<"-1 -1 -1\n";
  }
  void gen(){}
  void brute(){}
};

int main(int argc,char** argv){
  fo(i,1,argc-1)for(int j=0;argv[i][j];j++)if(argv[i][j]=='.')freopen(argv[i],"r",stdin);
  fo(i,1,argc-1)if(argv[i]==string("q"))cond=1<<30;
  fo(i,1,argc-1)if(argv[i]==string("gen")){(solver=new solver_t())->gen();exit(0);}
  fo(i,1,argc-1)if(argv[i]==string("brute")){(solver=new solver_t())->brute();exit(0);}
  ios::sync_with_stdio(false),cin.tie(0);
  cout.setf(ios::fixed),cout.precision(10);int t;if(multi||gcj)cin>>t;else t=1;
  fo(i,1,t){if(cond)cerr<<__LINE__<<" "<<i<<endl;if(gcj)cout<<"Case #"<<i<<": ";
    solver = new solver_t();
    solver->solve();
  }return 0;
}
template class std::vector<int>;
template class std::vector<ll>;


Measured memory_bytes: 256
def dfs(edges, a, b, v, visited)
  return if visited.include?(v)

  visited.push(v)
  edges[v].each_with_index do |exist, u|
    if exist && !(v == a && u == b) && !(v == b && u == a)
      dfs(edges, a, b, u, visited)
    end
  end
end
n, m = gets.split.map(&:to_i)
a = []
b = []
edges = n.times.map { Array.new(n, false) }
for i in 0...m do
  aa, bb = gets.split.map(&:to_i)
  a[i] = aa - 1
  b[i] = bb - 1
  edges[a[i]][b[i]] = true
  edges[b[i]][a[i]] = true
end
count = 0
for i in 0...m do
  visited = []
  dfs(edges, a[i], b[i], a[i], visited)
  count += 1 if visited.size < n
end
puts count


Measured memory_bytes: 1916
N = int(input())
a = list(map(int, input().split()))

if N == 2:
    print(*a[::-1])
else:
    product = a[0]
    for i in range(N):
        if i == 0:
            product = a[i]
        else:
            product = product ^ a[i]
    ans = []
    for i in range(N):
        product = product ^ a[i]
        ans.append(product)
        product = product ^ a[i]
    print(*ans)


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

int main(){
    while(1){
        int mH,mW;
        cin>>mH>>mW;
        if((mH==0)&&(mW==0))break;
        int guuki=1;
        for(int i=0;i<mH;i++){
            int guuki2=1;
            for(int j=0;j<mW;j++){
                if(((guuki%2)&&(guuki2%2))||(!(guuki%2)&&!(guuki2%2))){
                    cout<<"#";
                }else{
                    cout<<".";
                }
                guuki2++;
            }
            guuki++;
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const int MOD = 1000000007;

template<class T = ll> struct Edge {
    int to;
    T cost;
    Edge() {}
    Edge(int to, T cost) : to(to), cost(cost) {}
    bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

template<class T = ll> vector<T> Dijkstra(vector<vector<Edge<T>>> edges, int st) {

    int V = (int)edges.size();
    vector<T> dist(V, INF);
    dist[st] = 0;

    priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> p_que;
    p_que.emplace(st, dist[st]);

    while (!p_que.empty()) {

        Edge<T> now(p_que.top().to, p_que.top().cost);
        p_que.pop();

        if (dist[now.to] < now.cost) continue;
        for (const Edge<T> &e : edges[now.to]) {
            T tmp_cost = now.cost + e.cost;
            if (dist[e.to] > tmp_cost) {
                dist[e.to] = tmp_cost;
                p_que.emplace(e.to, dist[e.to]);
            }
        }
    }

    return dist;
}

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

    vector<vector<Edge<int> > > Edges(3 * N + 1);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        Edges[u].emplace_back(v + N, 1);
        Edges[u + N].emplace_back(v + 2 * N, 1);
        Edges[u + 2 * N].emplace_back(v, 1);
    }
    cin >> S >> T;

    auto ans = Dijkstra<int>(Edges, S);
    if (ans[T] == INF) {
        cout << -1 << endl;
    } else {
        cout << ans[T] / 3 << endl;
    }
}

Measured memory_bytes: 34176
#include <iostream>
#include <algorithm>
#include <set>
#include <functional>
#include <list>
#include <bitset>
#include <numeric>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <map>

#define INF 1e9
#define MOD 1000000007
#define ll long long
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
typedef unsigned long long ull;
typedef pair<int, int> pr;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,h,w;
    cin>>n>>h>>w;
    cout<<(n-h+1)*(n-w+1)<<endl;
    // vector<int>a={1,2,3,4,5,6};
    // rotate(a.rbegin(), a.rbegin()+1, a.rend());
    // for(auto &itr:a){
    //     cout<<itr<<" ";
    // }
    // rotate(a.rbegin(), a.rbegin()+1, a.rend());
    // cout<<endl;
    // for(auto &itr:a){
    //     cout<<itr<<" ";
    // }
    // cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

bool flag[3010];

signed main() {
	int A, B, C, D, E, F;
	cin >> A >> B >> C >> D >> E >> F;

	flag[0] = true;
	rep(i, 3001) {
		if (i >= C) flag[i] |= flag[i - C];
		if (i >= D) flag[i] |= flag[i - D];
	}

	double maxNoudo = 0.000000001;
	int ret1 = 100 * A;
	int ret2 = 0;
	REP(a, 0, 30) {
		REP(b, 0, 30) {
			int mizu = 100 * A * a + 100 * B * b;
			int maxE = min((A * a + B * b) * E, F - mizu);
			int satou = 0;
			rep(i, maxE + 1) {
				if (flag[i]) satou = i;
			}
			double noudo = 100.0 * satou / (mizu + satou);
			if (noudo > maxNoudo) {
				maxNoudo = noudo;
				ret1 = mizu + satou;
				ret2 = satou;
			}
		}
	}

	cout << ret1 << " " << ret2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <algorithm>
#include <time.h>
#include <assert.h>

using namespace::std;

int ri()
{
        int x;
        scanf("%d", &x);

        return x;
}

void wi(int x)
{
        printf("%d\n", x);
}

int64_t ab(int64_t x, int64_t y)
{
        int64_t z = x - y;
        if (z < 0)
                z = -z;

        return z;
}

int main()
{
        int N = ri();
        int64_t Z = ri();
        int64_t W = ri();

        vector<int64_t> A(N + 1);
        A[0] = W;

        for (int i = 0; i < N; i++)
                A[i + 1] = ri();

        vector<int64_t> mx(N);
        vector<int64_t> mn(N);

        mx[N - 1] = mn[N - 1] = ab(A[N - 1], A[N]);

        for (int i = N - 2; i >= 0; i--)
        {
                // mx
                int64_t u = ab(A[i], A[N]);
                for (int j = i + 1; j < N; j++)
                        u = max(u, mn[j]);
                mx[i] = u;

                // mn
                int64_t v = ab(A[i], A[N]);
                for (int j = i + 1; j < N; j++)
                        v = min(v, mx[j]);
                mn[i] = v;
        }

        int64_t ans = mx[0];
        printf("%lld\n", ans);

        return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int w = Integer.parseInt(scanner.nextLine());
        int n = Integer.parseInt(scanner.nextLine());
        int a[] = new int[n];
        int b[] = new int[n];
        int z[] = new int[w];
        for (int i = 0; i < n; i++) {
            String s = scanner.nextLine();
            String t[] = s.split(",");
            a[i] = Integer.parseInt(t[0]);
            b[i] = Integer.parseInt(t[1]);
        }
        for (int i = 0; i < w; i++) {
            int p = i + 1;
            for (int j = 0; j < n; j++) {
                if (p == a[j]) {
                    p = b[j];
                } else if (p == b[j]) {
                    p = a[j];
                }
            }
            z[p-1] = i + 1;
        }
        for (int i = 0; i < w; i++) {
            System.out.println(z[i]);
        }
    }
}


Measured memory_bytes: 26180
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    vector<vector<int>> bingo(3,vector<int>(3));
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cin >> bingo.at(i).at(j);
        }
    }

    int N=0;
    cin >> N;

    vector<int> me(N);

    for(int i=0; i<N; i++){
        cin >> me.at(i);
    }

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<N; k++){
                if(bingo.at(i).at(j) == me.at(k)){
                    bingo.at(i).at(j) = 0;
                }
            }
        }
    }

    int count=0;

    for(int i=0; i<3; i++){
        if(bingo.at(i).at(0) == bingo.at(i).at(1) && bingo.at(i).at(1) == bingo.at(i).at(2)) count++;
    }
    for(int i=0; i<3; i++){
        if(bingo.at(0).at(i) == bingo.at(1).at(i) && bingo.at(1).at(i) == bingo.at(2).at(i)) count++;
    }
    if(bingo.at(0).at(0) == bingo.at(1).at(1) && bingo.at(1).at(1) == bingo.at(2).at(2)) count++;
    if(bingo.at(0).at(2) == bingo.at(1).at(1) && bingo.at(1).at(1) == bingo.at(2).at(0)) count++;

    if(count != 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<complex>
#include<string.h>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#define MS(ptr,val) memset(ptr,val,sizeof(ptr));
#define INPUT(n,m) int n,m;scanf("%d%d",&n,&m);

using namespace std;
typedef long long ll;

int main()
{
	INPUT(n, m);
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int h;
		scanf("%d", &h);
		if (h >= m)cnt++;
	}
	printf("%d", cnt);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using ll = long long;
const ll mod = 1e9+7; int INF=INT_MAX; ll LLINF = 1LL << 60;
const vector<int> d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vector<int> d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vector<int> d4x = {1, 0, -1, 0}; vector<int> d4y = {0, 1, 0, -1};

//

int main(){
    int n; cin>>n;
    vector<int> w(n);
    rep(i,0,n) cin>>w[i];
    vector<int> ruiseki(n,0);
    ruiseki[0]=w[0];
    rep(i,1,n) ruiseki[i]=ruiseki[i-1]+w[i];
    int ans=INF;
    rep(i,0,n-1){
        int temp=abs(ruiseki[n-1]-2*ruiseki[i]);
        ans=min(ans,temp);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
N,M,*P = $<.read.split.map &:to_i
C = [m=1]*(N+1)
A = C.map {[]}
(0...M).map {|i| a=P[i+=i]; b=P[i+1]; a<b ? [a,b] : [b,a]}.sort.each{|a,b| A[a] << b}
1.upto(N) {|i|
  a = A[j=i]
  a.each {k = A[_1][-1]||_1; j<k && j=k}
  next  if j == i
  a.each {b=A[_1]; b << j  if b[-1]!=j}
  m < C[j]+=C[i] and m = C[j]
}
p m

Measured memory_bytes: 62484
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    long long a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    int right = 0;
    long long sum = 0;
    long long res = 0;
    for (int left = 0; left < n; left++)
    {
        while (right < n && (sum ^ a[right]) == (sum + a[right]))
        {
            sum += a[right];
            right++;
        }
        res += right - left;
        if(left == right) right++;
        else sum -= a[left];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;
int main() {
fastio;
string str;
cin>>str;
ll sum=0;
for(ll i=0;i<str.length();i++){
    sum+=(str[i]-48);
    //cout<<"Sum is -> "<<sum;
}
if((sum%9==0)){
    cout<<"Yes";
}
else{
    cout<<"No";
}
return 0;
}

Measured memory_bytes: 3692
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string.h>
#include <array>
#include <bitset>

using namespace std;

typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	ll sum=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			for(int k=1; k<=n; k++){
				sum+=__gcd(__gcd(i, j), k);
			}
		}
	}
	cout << sum << '\n';
	return 0;
}

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

using namespace std;
const int maxn = 1e5+10;
int main()
{
	int n;
	int a[maxn];
	cin >> n;
	for(int i = 0;i < n;i ++)
		cin >> a[i];
	int cnt = 0,maxx = 0;
	for(int i = n-2;i >= 0;i --){
		if(a[i] >= a[i+1]){
			cnt ++;	
		}else {
			maxx = max(cnt,maxx);
			cnt = 0;
		}
	}
	maxx = max(maxx,cnt);
	cout << maxx << endl;
	return 0;
}

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

#define mod 1000000007

using namespace std;
 
int main(void){
	
	int A[3], K;
	
	cin >> A[0] >> A[1] >> A[2] >> K;
	
	sort(A, A+3);
	
	for(int i=0; i<K; i++)
		A[2] *= 2;
	
	cout << A[0] + A[1] + A[2];
	
	return 0;
}

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

ll solve() {
    ll H, W, K;
    cin >> H >> W >> K;
    string s, e;
    vector<vector<ll>> S(H, vector<ll>(W));
    for ( int i = 0; i < H; i++ ) {
        cin >> s;
        for ( int j = 0; j < W; j++ ) {
            S[i][j] = (s[j] == '#' ? 1 : 0);
        }
    }
    ll fr = -1;
    for ( int h = 0; h < H; h++ ) {
        for ( int w = 0; w < W; w++ ) {
            if ( S[h][w] == 1 ) {
                fr = h;
                break;
            }
        }
        if ( fr >= 0 ) break;
    }

    vector<vector<ll>> ans(H, vector<ll>(W));
    ll x = 0;
    for ( int h = fr; h < H; h++ ) {
        bool ex = false;
        for ( int w = 0; w < W; w++ ) {
            if ( S[h][w] == 1 ) ex = true;
        }
        if ( !ex ) {
            for ( int w = 0; w < W; w++ ) {
                ans[h][w] = ans[h-1][w];
            }
            continue;
        }
        x++;
        bool f = true;
        for ( int w = 0; w < W; w++ ) {
            if ( S[h][w] == 1 ) {
                if ( !f ) {
                    x++;
                } else {
                    f = false;
                }
            }
            ans[h][w] = x;
            if ( h == fr ) {
                for ( int h2 = fr-1; h2 >= 0; h2-- ) {
                    ans[h2][w] = ans[h][w];
                }
            }
        }
    }
    
    for ( int h = 0; h < H; h++ ) {
        for ( int w = 0; w < W; w++ ) {
            cout << (w != 0 ? " " : "") << ans[h][w];
        }
        cout << "\n";
    }
    
    return 0;
}

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

Measured memory_bytes: 2176
class Array
  def cumsum
    inject([]) { |a, v| a << (a.last || 0) + v }
  end
end
n = gets.to_i
as = gets.split.map(&:to_i).cumsum
ans = Float::INFINITY
for i in 0...n-1
  x = as[i]
  y = as[n-1] - as[i]
  ans = [ans, (x-y).abs].min
end
p ans

Measured memory_bytes: 20796
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int N;
int a[100];

int bubbleSort() {
  int count = 0;
  for(int j = N-1; j >= 1; j--) {
    if(a[j] < a[j-1]) {
      swap(a[j], a[j-1]);
      count++;
    }
  }
  return count;
}

int main() {
  cin >> N;
  rep(i, N) {
    cin >> a[i];
  }
  int ans = 0;
  rep(i, N-1) {
    ans += bubbleSort();
  }
  rep(i, N) {
    cout << a[i];
    if(i != N-1) cout << " ";
    else cout << endl;
  }
  // cout << a[0] << " " << a[1] << endl;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3088
N,A=map(int, input().split())
x=list(map(int, input().split()))
dp = [[[0]*(51*51) for _ in range(N+1)] for _ in range(N+1)]
# dp[j][k][s]
for j in range(N+1):
    for k in range(j+1):
        for s in range(51*51):
            if j==0 and k==0 and s==0:
                dp[j][k][s] = 1
            elif j >=1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >=1 and k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s] = 0

ans = 0
for i in range(1, N+1):
    ans+= dp[N][i][i*A]
print(ans)

Measured memory_bytes: 94556
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

N = int(input())
a = list(map(int, input().split()))

INF = 10**18
dp = [[INF] * N for _ in range(N)]

# def calc(i, j, t):
#     if dp[i][j] != INF:
#         return dp[i][j]
#     if t == 0:
#         if i == j:
#             dp[i][j] = a[i]
#         else:
#             dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
#     else:
#         if i == j:
#             dp[i][j] = -a[i]
#         else:
#             dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
#     return dp[i][j]

# print(calc(0, N-1, 0))

for l in range(N):
    t = (N-l) % 2
    for i in range(N-l):
        j = i + l
        if t == 1:
            if l == 0:
                dp[i][j] = a[i]
            else:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j])
        else:
            if l == 0:
                dp[i][j] = -a[i]
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j])
print(dp[0][N-1])

Measured memory_bytes: 112988
#include <iostream>
 
using namespace std;
 
int main(){
 
    int x,i=0;
    int ans=1;
 
    cin >> x ;
  
    for(i;i<3;++i){
        ans=ans*x;
    }
     
 
    cout << ans << endl;
 
 
 
    return 0;
 
}

Measured memory_bytes: 1160
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,N) for(int i = 0;i < (int)(N);i++)
int main(){
  int n;
  cin>>n;
  string s,t;
  cin>>s>>t;
  rep(i,n) cout<<s[i]<<t[i];
}
  


Measured memory_bytes: 256
n = int(input())
cards = {}
taro, hanako = 0, 0
for i in range(n):
    cards["taro"], cards["hanako"] = input().split()
    if cards["taro"] > cards["hanako"]:
        taro += 3
    elif cards["taro"] < cards["hanako"]:
        hanako += 3
    else:
        taro += 1
        hanako += 1

print(taro, hanako)


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
int n,a[300001];
bool add1(list<pair<int,int>> &v,int base)
{
	if(base==1)return 0;
	auto it=--v.end();
	for(;;)
	{
		if(it->first>1)v.insert(it,{it->first-1,it->second}),it->first=1;
		if(++it->second<base)break;
		if(it==v.begin())return 0;
		it-- ->second=0;
	}
	return 1;
}
bool check(int base)
{
	list<pair<int,int>> v;
	v.push_back({a[1],0});
	for(int i=2;i<=n;i++)
		if(a[i-1]<a[i])v.push_back({a[i]-a[i-1],0});
		else
		{
			int x=a[i-1]-a[i];
			while(x)
				if(v.back().first<=x)x-=v.back().first,v.pop_back();
				else v.back().first-=x,x=0;
			if(!add1(v,base))return 0;
		}
	return 1;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int l=1,r=n,ans=n;
	while(l<=r)
	{
		int m=(l+r)/2;
		if(check(m))ans=m,r=m-1;
		else l=m+1;
	}
	cout<<ans<<'\n';
}


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

int N;

char ask(int n, int k) {
  cout << "? " << n + 1;
  for (int i = 0; i < N-1; i++) cout << " " << ((k + i) % (2*N)) + 1;
  cout << endl;
  string T; cin >> T;
  if (T == "Red") return 'R';
  if (T == "Blue") return 'B';
  exit(1);
}

int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  cin >> N;
  char bl = ask(0, 1);
  char br = bl == 'R' ? 'B' : 'R';
  int l = 0;
  int r = N;
  while (l + 1 < r) {
    int mid = (l + r) / 2;
    char b = ask(mid, mid+1);
    if (b == bl) l = mid;
    else         r = mid;
  }
  char res[2*N+1];
  res[2*N] = 0;
  for (int i = 0; i < 2*N; i++) {
    if (i == l)          res[i] = bl;
    else if (i == l + N) res[i] = br;
    else if (i < l)      res[i] = ask(i, l+1);
    else if (i < l + N)  res[i] = ask(i, l+1 + N);
    else                 res[i] = ask(i, l+1);
  }
  cout << "! " << string(res) << endl;
  return 0;
}



Measured memory_bytes: 724
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    int m = max({a, b, c});
    if((3*m)%2 == (a+b+c)%2) cout << ((3*m)-(a+b+c))/2 << endl;
    else cout << ((3*(m+1)) - (a+b+c))/2 << endl;

    return 0;
}

Measured memory_bytes: 3616
import math

def isPrime( x ):
	if 2 == x or 3 == x:
		return True
	if 0 == x&1:
		return False
	i = 3
	limit = math.sqrt( x )
	while  i <= limit:
		if 0 == x%i:
			return False
		i += 2
	return True
 
 
n = int( raw_input( ) )
nums = []
i = 0
while i < n:
    nums.append( int( raw_input( ) ) )
    i += 1
cnt = i = 0
for val in nums:
    if isPrime( val ):
        cnt += 1
 
print( cnt )

Measured memory_bytes: 6676
#include<bits/stdc++.h>
using namespace std;
#define MN 1<<24
priority_queue<pair<int,int>> Q;
int d[MN],n,s,L,x[MN],y[MN],t[MN],ti[MN],mn,mid,i;
int main(){
	cin>>n>>s>>L;
	Q.push(make_pair(0,-1));
	x[0]=1;t[0]=0;y[0]=0;t[s+1]=L;
	for(i=1;i<=s;i++){cin>>x[i]>>t[i]>>y[i];}
	for(i=0;i<=s;i++){
		d[x[i]]+=y[i];
		Q.push(make_pair(d[x[i]],-x[i]));
		while(1){
			pair<int,int>p=Q.top();
			if(p.first==d[-p.second]){
				ti[-p.second]+=t[i+1]-t[i];break;
			}
			Q.pop();
		}
	}
	for(i=1;i<=n;i++){
		if(mn<ti[i]){
			mn=ti[i];
			mid=i;
		}
	}
	cout<<mid<<endl;
}

Measured memory_bytes: 18816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n,a,b;
string s;
int main(void){
    cin>>n>>a>>b>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='a'){
            if(a+b>0){
                cout<<"Yes"<<endl;
                a--;
            }else{
                cout<<"No"<<endl;
            }
        }else if(s[i]=='b'){
            if(a+b>0&&b>0){
                cout<<"Yes"<<endl;
                b--;
            }else{
                cout<<"No"<<endl;
            }
        }else{
            cout<<"No"<<endl;
        }
    }
    
    
}


Measured memory_bytes: 3764
from bisect import bisect

def solve():
    N = int(input())
    A = sorted(map(int,input().split()))
    if N == 2:
        res = [(max(A),min(A))]
        s = max(A)-min(A)
        return s, res

    if A[0] >= 0:
        res = []
        x = A[0]
        for a in A[1:-1]:
            res.append((x,a))
            x -= a
        res.append((A[-1],x))
        x = A[-1]-x
        return (x,res)
    if A[-1] <= 0:
        res = []
        x = A[-1]
        for a in A[:-1]:
            res.append((x,a))
            x -= a
        return (x,res)

    res = []
    p = bisect(A,0)-1
    x = A[p]
    for a in A[p+1:N-1]:
        res.append((x,a))
        x -= a
    res.append((A[-1],x))
    x = A[-1]-x
    for a in A[:p]:
        res.append((x,a))
        x -= a
    return (x,res)



s,res = solve()
print(s)
print('\n'.join(f'{a} {b}' for a,b in res))

Measured memory_bytes: 32916
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
using namespace std;
typedef long long ll;
// cd test ; rm -R ./*; cd .. 
ll n;
int ans = 0;
void dfs(string s) {
  if (s.size() > 10) return;

  bool calc = true;
  bool ok7 = false, ok5 = false, ok3 = false;
  rep (i, s.size()) {
    if (s[i] == '3') ok3 = true;
    if (s[i] == '5') ok5 = true;
    if (s[i] == '7') ok7 = true;
  }
  if (!ok3 || !ok5 || !ok7) calc = false;

  if (calc) {
    if (stoll(s) <= n) ans++;
  }

  dfs(s + '3');
  dfs(s + '5');
  dfs(s + '7'); 

}

int main(void) {
  cin >> n;

  dfs("");

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

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

int main(){
    int b,i,c=0;
    string a;
    cin>>b>>a;
    for(i=0;i<b;i++){

           if(a[i] != a[i+b/2]){
            c++;
        }else if(i>=b/2-1){
        break;
        }
       }

    if(c==0 && b!=0  && b%2==0 ){
        cout<<"Yes";
    }else{cout<<"No";}
    




}



Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(void)
{
	double r,f,x,y;
	f=M_PI;
	scanf("%lf",&r);
	x=r*r*f;
	y=2.0*f*r;
	printf("%lf %lf\n",x,y);
	return 0;
}



Measured memory_bytes: 2760
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,a;
  cin>>n;
  map<ll,ll> mp;
  for(ll i=0;i<n;i++){
    cin>>a;
    mp[a]++;
    if(n%2==1){
      if(a%2==1||mp[a]>2||a>=n||mp[0]>1){
        cout<<0<<endl;
        return 0;
      }
    }else{
      if(a%2==0||mp[a]>2||a>=n){
        cout<<0<<endl;
        return 0;
      }
    }
  }
  ll c=1;
  for(ll i=0;i<n/2;i++){
    c*=2;
    c%=1000000007;
  }
  cout<<c<<endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>

using namespace std;

struct Node
{
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k){
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL){
        y = x;
        if(z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = x;

    if(y==NIL) root = z;
    else if(z->key < y->key) y->left = z;
    else y->right = z;

}

Node *find(int k){
    Node *x = root;

    while(x != NIL && k != x->key){
        if(k < x->key) x = x->left;
        else x = x->right;
    }

    return x;

}

void preOrder(Node *u){
    if(u == NIL) return;
    cout << " " << u->key;
    preOrder(u->left);
    preOrder(u->right);
}

void inOrder(Node *u){
    if(u == NIL) return;
    inOrder(u->left);
    cout << " " << u->key;
    inOrder(u->right);
}

int main(){
    int n,i,x;
    string com;

    cin >> n;
    
    for(int i=0;i<n;++i){
        cin >> com;
        if(com == "find"){
            cin >> x;
            Node *t = find(x);
            if(t != NIL) cout << "yes" << endl;
            else cout << "no" << endl;
        }
        else if(com == "insert"){
            cin >> x;
            insert(x);
        } else if( com == "print"){
            inOrder(root);
            cout << endl;
            preOrder(root);
            cout << endl;
        }
    }
}


Measured memory_bytes: 21912