akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <map>
#include <string>
#include <cstring>
typedef long long int ll;
using namespace std;

int main() {
	int N; cin >> N;
	vector<ll>H(N);
	for (int i = 0; i < N; i++) {
		cin >> H.at(i);
	}
	vector<int>High(N, 0);
	for (int i = 1; i < N; i++) {
		if (H.at(i) <= H.at(i - 1)) High.at(i) = High.at(i - 1) + 1;
	}
	int ans = High.at(0);
	for (int i = 1; i < N; i++) {
		if (ans < High.at(i)) ans = High.at(i);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    // rとcでそれぞれmapを保持、lower_bound
    ll N, Q;
    cin >> N >> Q;
    map<ll, ll> rmap;
    map<ll, ll> cmap;
    rmap[N-1] = N-1;
    cmap[N-1] = N-1;
    ll white = 0; // 内部にある白石
    rep(i, Q) {
        ll q, x;
        cin >> q >> x;
        --x;
        if (q == 1) {
            auto it = rmap.lower_bound(x);
            white += it->second - 1;
            if (cmap[it->second] == 0 || cmap[it->second] > x) cmap[it->second] = x;
        } else {
            auto it = cmap.lower_bound(x);
            white += it->second - 1;
            if (rmap[it->second] == 0 || rmap[it->second] > x) rmap[it->second] = x;
        }
    }
    ll ans = (N-2) * (N-2) - white;
    cout << ans << '\n';
    return 0;
    // ll, 0, -, 1i, for s&g, debug
}

Measured memory_bytes: 9788
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
s = gets.chomp

if s.reverse == s
  s1 = s.slice(0, s.size/2)
  s2 = s.slice(s.size/2+1, s.size)
  if s1.reverse == s1 && s2.reverse == s2
    puts 'Yes'
    exit
  end
end

puts 'No'

Measured memory_bytes: 2300
open Printf
open Scanf

let (h,w) = sscanf (read_line ()) "%d %d" (fun x y -> (x,y));;
let array = Array.make h "";;
let _ =
for i = 0 to h-1 do
  let str = sscanf (read_line ()) "%s" (fun x -> x) in
  array.(i) <- str
done;;

let left = Array.init h (fun _ -> Array.make w 0);;
let right = Array.init h (fun _ -> Array.make w 0);;
let up = Array.init h (fun _ -> Array.make w 0);;
let down = Array.init h (fun _ -> Array.make w 0);;

let _  =
  for i = 0 to h-1 do
    for j = 0 to w-1 do

      if (array.(i).[j] = '#') then
        left.(i).(j) <- 0
      else if (j = 0) then
        left.(i).(j) <- 1
      else
        left.(i).(j) <- left.(i).(j-1) + 1;

      if (array.(i).[j] = '#') then
        up.(i).(j) <- 0
      else if (i = 0) then
        up.(i).(j) <- 1
      else
        up.(i).(j) <- up.(i-1).(j) + 1;

      let rj = w-1-j in
      if (array.(i).[rj] = '#') then
        right.(i).(rj) <- 0
      else if (rj = w-1) then
        right.(i).(rj) <- 1
      else
        right.(i).(rj) <- right.(i).(rj+1) + 1;

      let di = h-1-i in
      if (array.(di).[j] = '#') then
        down.(di).(j) <- 0
      else if (di = h-1) then
        down.(di).(j) <- 1
      else
        down.(di).(j) <- down.(di+1).(j) + 1
    done
  done;;

let ans = ref 0;;
let _  =
  for i = 0 to h-1 do
    for j = 0 to w-1 do
    let tmp = left.(i).(j) + right.(i).(j) + up.(i).(j) + down.(i).(j) - 3 in
    ans := max !ans (tmp)
  done
done;;
printf ("%d\n") !ans


Measured memory_bytes: 134780
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

int h, m, s;
int sum_s, rest_s, rest_s_3;

int main()
{
	while (cin >> h >> m >> s)
	{
		if (h == -1 && m == -1 && s == -1) break;
		sum_s = 3600 * h + 60 * m + s;
		rest_s = 7200 - sum_s;
		rest_s_3 = rest_s * 3;
		printf("%02d:%02d:%02d\n", rest_s / 3600, (rest_s % 3600) / 60, (rest_s % 3600) % 60);
		printf("%02d:%02d:%02d\n", rest_s_3 / 3600, (rest_s_3 % 3600) / 60, (rest_s_3 % 3600) % 60);
	}

	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<iomanip>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<tuple>
#include<numeric>
#include<map>
#include<cmath>
#define ll long long
#define mod 1000000000+7
#define rep(i,n) for(int i=0;i<(int) (n);i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
using namespace std;
int main() {
	ll n, m,ans=0;
	cin >> n >> m;
	priority_queue<int>que;
	rep(i, n) {
		ll a;
		cin >> a;
		que.push(a);
	}

	rep(i, m) {
		ll a;
		a = que.top();
		que.pop();
		a/=2;
		que.push(a);
	}

	rep(i, n) {
		ll a;
		a = que.top();
			que.pop();
		ans += a;
	}
	cout << ans;
}

Measured memory_bytes: 892
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
#include<string.h>
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define None cout<<"None"<<endl
#define GREATER cout<<"GREATER"<<endl
#define LESS cout<<"LESS"<<endl
#define EQUAL cout<<"EQUAL"<<endl
typedef long long ll;
using namespace std;

int main() {
	int N,M; cin >> N >> M;
	int a[N],b[N],c[M],d[M];
	int e[N];
	for (int i = 1; i <= N; ++i) cin >> a[i] >> b[i];
	for (int i = 1; i <= M; ++i) cin >> c[i] >> d[i];
	
	
	for (int i = 1; i <= N; ++i) {
		int	min = abs(a[i]-c[1])+abs(b[i]-d[1]); e[i] = 1;
		
		for (int j = 1; j <= M; ++j) {
			if (min > abs(a[i]-c[j])+abs(b[i]-d[j])) {
				min = abs(a[i]-c[j])+abs(b[i]-d[j]);
				e[i] = j;
				
			}
		}
		cout << e[i] << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define fore(x, a) for(auto &x : a)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define inf 2001001001
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vii = vector<int>;
using vll = vector<ll>;
template<class T>using vv = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<class T>void show(const vector<T> &a) { for (int i = 0; i < (int)a.size(); ++i) cout << a[i] << (i != (int)a.size()-1 ? " " : "\n"); }
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
int dy[]={0, 1, -1, 0};
int dx[]={1, 0, 0, -1};

int n, k;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> n >> k;
    cout << k * (ll)pow(k-1, n-1) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<ll, ll> P;
inline ll min(ll x, ll y) { return x < y ? x : y; }
inline ll max(ll x, ll y) { return x > y ? x : y; }

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define all(c) c.begin(), c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    rep(i, N) { cout << S[i] << T[i]; }
    return 0;
}

Measured memory_bytes: 256
while True:
    N, X = map(int, input().split())
    if N == 0:
        break
    res = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            for k in range(j+1, N+1):
                if i + j + k == X:
                    res += 1
    print(res)



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

int main() {
  int N, A = 0, B = 0;
  cin >> N;
  vector <int> vec(N);

  // 入力を配列で受け取る
  for(int i =0; i < N;i++){
    cin >> vec.at(i);
  }
  //大きい順にソートする
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());

  //偶数はA、奇数はBとして数値を代入する
  for (int i = 0; i < N; i++){
    if (i % 2 == 0){
      A += vec.at(i);
    }else{
      B += vec.at(i);
    }
  }
  //AとBの差を表示する

  cout << A - B << endl;




}


Measured memory_bytes: 256
x,n=map(int,input().split())

if n==0:
    print(x)

if n>0:
    p=list(map(int,input().split()))
    i=1
    if (x in p) == False:
        print(x)
    else:
        while(True):
            if ((x-i) in p) == False:
                print(x-i)
                break
            elif ((x+i) in p) == False:
                print(x+i)
                break
            else:
                i+=1

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

int H, W;
char Field[102][102];
const int dir[4][2] = {
	{1, 0},
	{-1, 0},
	{0, 1},
	{0, -1}
};

void dfs(int x, int y)
{
	char f = Field[y][x];
	Field[y][x] = '.';

	for(int i=0; i<4; i++){
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if(ny < H && ny >= 0 && nx < W && nx >= 0 && Field[ny][nx] == f)
			dfs(nx, ny);
	}

	return;
}

int main()
{
	while(true)
	{
		cin >> H >> W;
		if(H == 0 && W == 0) break;

		for(int i=0; i<H; i++){
			for(int j=0; j<W; j++)
				cin >> Field[i][j];
		}

		int ans = 0;
		for(int i=0; i<H; i++)
			for(int j=0; j<W; j++)
				if(Field[i][j] == '@' || Field[i][j] == '#' || Field[i][j] == '*'){
					dfs(j, i);
					ans++;
				}

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

}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

int n, ans, cnt;
string s;
int x[26], y[26];
int main() {
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        ++y[s[i] - 'a'];
    }

    for (int i = 0; i < n - 1; ++i) {
        int d = s[i] - 'a';
        if (x[d] == 0 && y[d] > 1) {
            ++cnt;
        }
        if (x[d] > 0 && y[d] == 1) {
            --cnt;
        }
        ++x[d];
        --y[d];
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
#define MAX 2000000

int H, A[MAX + 1];

void maxHeapify(int i) {
  int l, r, largest;
  l = 2 * i;
  r = 2 * i + 1;

  if ( l <= H && A[l] > A[i] ) largest = l;
  else largest = i;
  if ( r <= H && A[r] > A[largest] ) largest = r;

  if ( largest != i ) {
    swap(A[i], A[largest]);
    maxHeapify(largest);
  }
}

int main() {
  cin >> H;

  for ( int i = 1; i <= H; i++ ) cin >> A[i];

  for ( int i = H / 2; i >= 1; i-- ) maxHeapify(i);

  for ( int i = 1; i <= H; i++ ) {
    cout << " " << A[i];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 4956
from itertools import groupby
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
D = groupby(sorted(D))
t = 998244353

ans = 1
pre = 0
cur = 0
for i, d in D:
    if i != cur:
        print(0)
        exit()
    else:
        cur += 1
    l = len(list(d))
    if i == 0 and l > 1:
        print(0)
        exit()
    if i <= 1:
        pre = l
        continue
    ans = ans * (pre**l)
    pre = l

print(ans % t)

Measured memory_bytes: 55092
def add word
	@dic[hashF word] << word
end

def hashF word
    temp = word.dup
	temp.gsub!("A", "1")
	temp.gsub!("C", "2")
	temp.gsub!("G", "3")
    temp.gsub!("T", "4")
	return temp.to_i(5) % @dic.length
end

def find word
    @dic[hashF word].each{|v| return true if v == word}
    return false
end

n = gets.to_i
@dic = Array.new(n * 2){[]}
n.times{
	command, word = gets.chomp.split
	case command
	when "insert"
		add word
	else
		puts (find word) ? "yes" : "no"
	end
}

Measured memory_bytes: 368520
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define endl '\n'
const int mod=1e9+7,u=3e3+5;

ld dp[u][u];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);

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

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

    ld ans=0;
    for(int i=n/2+1;i<=n;i++){
        ans+=dp[n][i];
    }
    cout<<fixed<<setprecision(10)<<ans;

    return 0;
}

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

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template<typename A, typename B> inline char SMAX(A &a, const B &b) {return a < b ? a = b , 1 : 0;}
template<typename A, typename B> inline char SMIN(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I>
inline void read(I &x) {
	int f = 0, c;
	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
	x = c & 15;
	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
	f ? x = -x : 0;
}

int n, k;

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	read(n), read(k);
	if (k <= (n + 1 >> 1)) puts("YES");
	else puts("NO");
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class B
{
	public static void Main()
	{
		long N = GetLong();
		long X = GetLong();
		Console.WriteLine(N + f(X, N - X));
	}

	private static long f(long x, long y)
	{
		if(y == 0)
			return 0;

		if(x < y)
		{
			long tmp = x;
			x = y;
			y = tmp;
		}

		if(x % y == 0)
			return y * (2 * (x / y) - 1);
		else
			return y * 2 * (x / y) + f(y, x % y);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int a,b[100]={},c,d,e,f=0;
    cin>>a;
    for(int i=0;i<a;i++){
        cin>>b[i];
    }
    for(int i=0;i<a;i++){
        c=i;
        d=i-1;
        for(int j=i;j>0;j--){
            if(c==0){
                break;
            }else if(b[c]<b[d]){
                    e=b[c];
                    b[c]=b[d];
                    b[d]=e;
                    f++;
                    c--;
                    d--;
            }
        }
    }
    for(int i=0;i<a-1;i++){
        cout <<b[i]<<" ";
    }
    cout <<b[a-1]<<"\n"<<f<<endl;
    return 0;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
何ループかをみる。
ループじゃないやつを10^5個別に探してく
それだと順番考慮もれてるか
2回つなげて、何文字目にあるかを調べるべきか

そうでもない。1文字ずつlowerで
*/
int main(){
  string S,T; cin>>S>>T;
  vector<vector<ll>> A(30);
  ll Ssz=S.size(), Tsz=T.size(), Ssz2=Ssz*2;
  ll loop=0;
  S+=S;
  for(ll i=0; i<Ssz2; i++){
    ll n=S[i]-'a';
    A[n].push_back(i+1);
  }
// now=2
// 2,3,5,6 
  //初期位置
  ll now=0, next=0;
  ll n=T[0]-'a';
  if(A[n].size()==0){
    cout<<-1<<endl;
    return 0;
  }  
  now=A[n][0];
  ll ans=now;
  for(ll i=1; i<Tsz; i++){
    n=T[i]-'a';
    auto IT=upper_bound(A[n].begin(), A[n].end(), now);
    if(IT==A[n].end()){
      cout<<-1<<endl;
      return 0;
    }
    ll next=*IT;
    ans+=next-now;
    if(next>Ssz) next-=Ssz;
    now=next;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 2804
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int A[n];
  for(int i=0;i<n;i++) cin>>A[i];
  int ans=0;
  bool flag=1;
  while(flag){
    flag=0;
    for(int j=n-1;j>0;j--){
      if(A[j]<A[j-1]){
	swap(A[j],A[j-1]);
	flag=1;
	ans++;
      }
    }
  }
  for(int i=0;i<n;i++) cout<<A[i]<<" \n"[i==n-1];
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3056
#include <iostream>

using namespace std;

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

    int a_min = 1;
    for (int i = 0; i < N; i++) {
        int douN = a_min * 2;
        int addN = a_min + K;
        if (douN <= addN) {
            a_min = douN;
        }
        else {
            a_min = addN;
        }
    }
    cout << a_min << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()


class LCA {
public:
	LCA(int n, const vector<int> edge[], int root = 0): edge(edge), size(n), depth(n), heavy(n), prev(n) {
		depth[root] = 0;
		dfs_sz(root);
		n_heavy = 0;
		dfs_hld(root, n_heavy++, -1);
	}
	int query(int u, int v) const {
		while (heavy[u] != heavy[v]) {
			if (prev[u] == -1 || prev[v] != -1 && depth[prev[u]] < depth[prev[v]]) {
				v = prev[v];
			}
			else {
				u = prev[u];
			}
		}
		return depth[u] < depth[v] ? u : v;
	}
private:
	void dfs_sz(int u) {
		size[u] = 1;
		for (int v : edge[u]) {
			depth[v] = depth[u] + 1;
			dfs_sz(v);
			size[u] += size[v];
		}
	}
	void dfs_hld(int u, int h, int p) {
		prev[u] = p;
		heavy[u] = h;
		int ma = 0;
		for (int v : edge[u]) {
			ma = max(ma, size[v]);
		}
		for (int v : edge[u]) {
			if (ma == size[v]) {
				dfs_hld(v, h, p);
				ma = -1;
			}
			else {
				dfs_hld(v, n_heavy++, u);
			}
		}
	}
	const vector<int>* edge;
	vector<int> depth;
	vector<int> size;
	int n_heavy;
	vector<int> heavy, prev;
};


vector<int> edge[100000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k, v;
		cin >> k;
		for (int j = 0; j < k; j++) {
			cin >> v;
			edge[i].push_back(v);
		}
	}
	LCA lca(n, edge, 0);
	int q, u, v;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> u >> v;
		cout << lca.query(u, v) << endl;
	}
	return 0;
}



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

using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

ll get(ll x, vector<ll> &D) {
    ll M = D.size();
    if ((x + 100000000000LL) % 2 == 1) {
        return ((1LL << M) - 1 - x) / 2;
    } else {
        return (1LL << (M - 1)) | ((1LL << (M - 1)) - (x + 1)) / 2;
    }
}

void solve() {
    ll N;
    cin >> N;
    vector<pii> P;
    set<ll> S;
    for (int i = 0; i < N; i++) {
        ll x, y;
        cin >> x >> y;
        P.push_back({x + y, x - y});
        S.insert((x + y + 1000000000000LL) % 2);
        S.insert((x - y + 1000000000000LL) % 2);
    }

    if (S.size() == 2) {
        cout << "-1" << endl;
        return;
    }

    ll M = 39;
    vector<ll> D(M);
    for (int i = 0; i < M; i++) {
        D[i] = 1LL << i;
    }

    vector<ll> D_ = D;

    if (*S.begin() % 2 == 0) {
        D_.push_back(1);
        M++;
    }

    cout << D_.size() << endl;
    for (int i = 0; i < D_.size(); i++) {
        cout << D_[i];
        if (i + 1 != D_.size()) {
            cout << " ";
        }
    }
    cout << endl;
    
    for (int i = 0; i < N; i++) {
        ll k1 = get(P[i].first, D_);
        ll k2 = get(P[i].second, D_);
        for (ll i = 0; i < M; i++) {
            ll k = ((k1 >> i & 1) << 1) | (k2 >> i & 1);
            if (k == 0) {
                cout << "R";
            } else if (k == 1) {
                cout << "U";
            } else if (k == 2) {
                cout << "D";
            } else {
                cout << "L";
            }
        }
        cout << endl;
    }
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
using namespace std;

int main(){
    int n,a,b[300010]={},maxi=0;;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        b[a]--;
    }
    sort(b,b+n+1);
    for(int i=0;i<=n;i++){
        b[i]*=-1;
    }
    int p=0,x=n,y,z=n;
    a=n;
    for(int i=1;i<=n;i++){
        do{
            y=x/i;
            a=x;
            if(z!=y){
                x-=(z-y)*p;
                z=y;
            }
            while(b[p]>y){
                x-=b[p]-y;
                p++;
            }
        }while(a!=x);
        printf("%d\n",y);
    }
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;

#define ALL(a) (a).begin(),(a).end()
#define ZP(a, len) setfill('0') << setw(len) << right << a
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

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

int N;

signed main() {
    cin >> N;
    ll ans = 1;
    for (int i = 0; i < N; ++i) {
        ll t;
        cin >> t;
        ans = lcm(ans, t);
    }

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

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 21:01:23 2020

@author: arute
"""


from sys import stdin

import time
import numpy as np


############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
M = int(temp[1])

if M >= N:
    print("unsafe")
else:
    print("safe")

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

int main() {
  int A, B, C;
   cin >> A >> B>> C;
  int temp;
  temp = A;
  A = C;
  C = B;
  B = temp;
  cout << A << ' ' << B << ' ' << C;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef long long LL;
const int MAXN = 2e5+17;
const int MOD = 1e9+7;
int dp[MAXN],nxt[MAXN][26+3],ocr[26+3];
int main(int argc ,char const *argv[])
{
  #ifdef noob
  freopen("Input.txt","r",stdin);freopen("Output.txt","w",stdout);
  #endif  
  string str;
  cin>>str;
  int n = str.size();
  for (int i = 0; i < 26; ++i)
  {
    ocr[i] = n;
  }
  for (int i = n-1; i >=0; i--)
  {
    ocr[str[i]-'a'] = i;
    for (int j = 0; j < 26; ++j)
    {
      nxt[i][j] = ocr[j];
    }
    dp[i] = MOD;
  }


  dp[n] = 1;
  for (int i = n-1; i > -1; --i)
    for (int j = 0; j < 26; ++j)
      dp[i] = min(dp[i],dp[nxt[i][j]+1]+1);

  for (int i = 0; dp[0]; --dp[0])
  {
    for (int j = 0; j < 26; ++j)
    {
      if(dp[i]==dp[nxt[i][j]+1]+1)
      {
        printf("%c",j+'a');
        i = nxt[i][j]+1;
        break;
      }
    }
  }

  cout<<endl;

  return 0; 
}


Measured memory_bytes: 24068
#include<stdio.h>

int main(void)
{
	int x;
	int y;
	
	while(1){
		scanf("%d %d", &x, &y);
		if(x == 0 && y == 0){
			break;
		}
		else if(x < y){
			printf("%d %d\n", x, y);
		}
		else{
			printf("%d %d\n", y, x);
		}
	}
	return (0);
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i=0;i<(int)(n);++i)
template <typename T> ll gcd(T a, T b) {return b?gcd(b, a%b):a;}
template <typename T> ll lcm(T a, T b) {return a * b / gcd(a, b);};
template <typename T> inline void chmin(T &a, const T& b){if(a>b)a=b;}
template <typename T> inline void chmax(T &a, const T& b){if(a<b)a=b;}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int r, g, b, n;
  cin >> r >> g >> b >> n;
  ll ans = 0;
  for (int i = 0; r * i <= n; ++i) {
    for (int j = 0; r * i + g * j <= n; ++j) {
      if (!((n - r * i - g * j) % b)) ++ans;
    }
  }
  cout <<  ans  << '\n';
}


Measured memory_bytes: 256
n, m = gets.chomp.split(" ").map(&:to_i)
a_ary = []
n.times do
  a_ary.push(gets.chomp.split(" ").map(&:to_i))
end
sorted_a_ary = a_ary.sort {|a,b| a[0] <=> b[0]}
drink_sum = 0
money_sum = 0
last_shop = 0
sorted_a_ary.each_with_index do |sorted_a, index|
  drink_sum += sorted_a[1]
  if drink_sum >= m
    last_shop = index
    break
  end
end
drink_sum = 0
if last_shop > 0
  sorted_a_ary[0..last_shop - 1].each_with_index do |sorted_a, index|
    drink_sum += sorted_a[1]
    money_sum += sorted_a[0] * sorted_a[1]
  end
end
money_sum += (m - drink_sum) * (sorted_a_ary[last_shop][0])
puts money_sum

Measured memory_bytes: 12968
#include <bits/stdc++.h>
using namespace std;
long long n,m,k,a,b,c,ans=0,cnt=1;
string s,t;
int main(){
	cin >> a >> n;
	cnt=n;
	for(int i=0;i<a;i++){
		n*=100;
	}
	if(cnt==100){
		n+=pow(100,a);
	}
	cout << n << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<cctype>
#define ld long double
#define ll long long int
#define ull unsigned long long int
using namespace std;
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;}
const long long INF=1LL<<60;


int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	string s,t;
	cin>>s>>t;
	int i;
	for(i=0;i<s.length();i++){
		if(i!=s.length()-1)cout<<s[i]<<t[i];
		else if(s.length()!=t.length())cout<<s[i];
		else cout<<s[i]<<t[i];
	}
	cout<<endl;
	
		
	return 0;
}

Measured memory_bytes: 256
#n=int(input())
k,x=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

l=[i for i in range(max(x-k+1,-1000000),min(x+k-1,1000000)+1)]

print(*l,sep=" ")


Measured memory_bytes: 3060
#include <stdio.h>

int main() {
    int n = 0;
    scanf("%d", &n);
    int a[n];
    int i = 0;
    for (i=0;i<n;i++) {
        scanf("%d", &a[i]);
    }
    int s = 0;
    n = sizeof(a) / sizeof(a[0]);
    for (i=0;i<n;i++) {
        s ^= a[i];
    }
    n -= 1;
    for (i=0;i<n;i++) {
        printf("%d ", s ^ a[i]);
    }
    printf("%d", s ^ a[n]);
}

Measured memory_bytes: 3300
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VMAX 10000
 
int main(){
    unsigned short *A,*B;
     
    int C[VMAX+1];
    int n,i,j;
    scanf("%d",&n);
     
    A=malloc(sizeof(short)*n+1);
    B=malloc(sizeof(short)*n+1);
     
    for(i=0;i<=VMAX;i++)C[i]=0;
     
    for(i=0;i<n;i++){
        scanf("%hu",&A[i+1]);
        C[A[i+1]]++;
    }
     
    for(i=1;i<=VMAX;i++)C[i]=C[i]+C[i-1];
     
    for(j=1;j<=n;j++){
        B[C[A[j]]]=A[j];
        C[A[j]]--;
    }
     
    for(i=1;i<=n;i++){
        if(i>1)printf(" ");
        printf("%d",B[i]);
    }
    printf("\n");
     
    return 0;
}

Measured memory_bytes: 9576
N = int(input())
mod = int(1E9+7)

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            dp[2][i][j][k] = 1
dp[2][2][1][0] = 0
dp[2][1][2][0] = 0
dp[2][2][0][1] = 0

for i in range(3, N):
    for x in range(4):
        for y in range(4):
            dp[i][0][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][1][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][2][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
            dp[i][3][x][y] = dp[i-1][x][y][0] + dp[i-1][x][y][1] + dp[i-1][x][y][2] + dp[i-1][x][y][3]
    
    dp[i][2][3][1] -= dp[i-1][3][1][0]
    dp[i][2][1][3] -= dp[i-1][1][3][0]
    dp[i][2][0][1] -= dp[i-1][0][1][0]
    dp[i][2][1][0] -= dp[i-1][1][0][0]
    dp[i][2][1][1] -= dp[i-1][1][1][0]
    
    dp[i][1][2][0] = 0
    dp[i][2][0][1] = 0
    dp[i][2][1][0] = 0
    
    


ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans = (ans + dp[N-1][i][j][k]) % mod
print(ans)

Measured memory_bytes: 3420
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1e9+7;

int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    if(n < b){
        ll ans = a*n/b;
        cout << ans << endl;
    }
    else{
        ll k = n/b;
        ll m = k*b-1;
        ll ans1 = a*m/b-a*(m/b);
        ll ans2 = a*n/b-a*(n/b);
        if(ans1 > ans2) cout << ans1;
        else cout << ans2 << endl;
    }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;



int main() {
//    cout << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    int a[n + 1], b[n + 1], c[n + 1];
    for (int i = 1; i < n + 1; i++) cin >> a[i];
    for (int i = 1; i < n + 1; i++) cin >> b[i];
    for (int i = 1; i < n; i++) cin >> c[i];

    ll ans = 0;

    for (int i = 1; i < n; i++) {
        ans += b[a[i]];
        if (a[i + 1] == a[i] + 1) ans += c[a[i]];
    }

    ans += b[a[n]];

    cout << ans;



}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _LIBCPP_DEBUG 0
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;
int INF = 1 << 20;

int N;

void dfs(string S, char mx){
    if(S.length()==N){
        cout<<S<<endl;
    }else{
        for (char i = 'a'; i <= mx; ++i) {
            dfs(S+i, (i==mx)?(mx+1):mx);
        }
    }

}

int main(void){

    cin>>N;
    dfs("", 'a');

    return 0;
}


Measured memory_bytes: 1536
while (line = gets)
    str = line.chomp
    status = 0
    uns = ""
    num = 0
    str.each_char do |ch|
        case status
        when 0 then
            if ch == "@"
                status = 1
            else
                uns += ch
            end
        when 1 then
            num = ch.to_i
            status = 2
        when 2 then
            num.times {uns += ch}
            status = 0
        end
    end

    puts uns
end



Measured memory_bytes: 6844
import numpy as np
K,N=map(int, input().split())
A=list(map(int, input().split()))
A = np.array(A)
distance_list = A[1:N] - A[0:N-1]
distance_list = np.append(distance_list, K-A[N-1]+A[0])
print(K-max(distance_list))

Measured memory_bytes: 43556
#include "bits/stdc++.h"
using namespace std;

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	int sum=0;
	cin>>a[0];
	sum+=abs(a[0]);
	for(int i=1;i<n;i++){
		cin>>a[i];
		sum+=abs(a[i-1]-a[i]);
	}
	sum+=abs(a[n-1]);
	cout<<sum-abs(a[0])-abs(a[0]-a[1])+abs(a[1])<<endl;
	for(int i=1;i<n-1;i++){
		cout<<sum-abs(a[i-1]-a[i])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1])<<endl;
	}
	cout<<sum-abs(a[n-2]-a[n-1])-abs(a[n-1])+abs(a[n-2])<<endl;
	
}

Measured memory_bytes: 1664
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		

		
		String[] tmpArray = br.readLine().split(" ");
		
		int[] input = new int[n];
		int[] index = new int[100001];
		Arrays.fill(index, -1);
		
		for(int i = 0; i < n; i++){
			input[i] = Integer.parseInt(tmpArray[i]);
		}
		
		Arrays.sort(input);
		if(n == 1){
			System.out.println(1);
			return;
		}		
		if(n == 2){
			if(input[1] - input[0] <= 2){
				System.out.println(2);
			}
			else {
				System.out.println(1);
			}
			return;
		}
		
		if(input[n - 1] - input[0] <= 2){
			System.out.println(n);
			return;
		}
		
		for(int i = 0; i < input.length ; i++){
			if(index[input[i]] == -1){
				index[input[i]] = i;
			}
		}
		
		for(int i = 1; i < index.length; i++){
			if(index[i] == -1 && index[i - 1] >= 0){
				index[i] = index[i - 1];
			}
		}
		
		int max = 0;
		for(int i = 0; i < index.length - 3 ; i++){
//			if(Math.max(index[i + 2], index[i + 1]) - index[i] + 1 > max){
//				max = Math.max(index[i + 2], index[i + 1]) - index[i] + 1;
//			}
			
			int top = -1;
			int bottom = -1;
			
			if(index[i + 3] != -1){
				top = index[i + 3];
			}
//			else if(index[i + 1] != -1){
//			else {
//				top = index[i + 1];
//			}
//			
			if(index[i] != -1){
				bottom = index[i];
			}
			//else if(index[i + 1] != -1){
//			else {
//				bottom = index[i + 1];
//			}
//			
//			if(i <= 10)System.out.println("top "+top+" bottom "+bottom);
			if(bottom != -1 && top != -1 && max < top - bottom){
				max = top - bottom;
			}
		}
		
		System.out.println(max);
	}

}


Measured memory_bytes: 37076
#include<cstdio>
#include<algorithm>
#define N_ 201000
using namespace std;
int n;
struct point {
	int A, B;
	bool operator<(const point &p)const {
		return A - B < p.A - p.B;
	}
}w[N_];
long long M = 1e18, S;
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i].A, &w[i].B);
		S += w[i].A;
		if (w[i].B < w[i].A) {
			M = min(w[i].B*1ll, M);
		}
	}
	if (M > 1e15)printf("0\n");
	else {
		printf("%lld\n", S - M);
	}
}

Measured memory_bytes: 384
from fractions import gcd
from functools import reduce


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


def solve(string):
    n, m, *a = map(int, string.split())
    c = 2**len(bin(a[0]).split("1")[-1])
    l = reduce(lcm, (_a if not _a % c and _a // c % 2 else 2 * m + 2 for _a in a))
    return str((m - l // 2) // l + 1) if l <= 2 * m else "0"


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 17172
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> cnt(n+1);
  for(int x=1; x<=100; x++) {
    for(int y=1; y<=100; y++) {
      for(int z=1; z<=100; z++) {
        ll tmp = x*x+y*y+z*z+x*y+y*z+z*x;
        if(tmp <= n) cnt[tmp]++;
      }
    }
  }
  rep(i, n+1) if(i) cout << cnt[i] << endk;
  return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
 
int search(int A[], int n, int key){
    int i = 0;
    A[n] =key;
    while( A[i] != key ) i++;
    return i != n;
}
 
int main(void){
    int i,n,A[10000+1],q,key,sum = 0;
     
    scanf("%d",&n);
    for( i = 0; i < n; i++)scanf("%d",&A[i]);
     
    scanf("%d",&q);
    for( i = 0; i < q; i++){
        scanf("%d",&key);
        if(search(A,n,key))sum++;
    }
    printf("%d\n",sum);
     
    return 0;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <utility>
#include <complex>
#include <stack>
#include <climits>
#include <set>
#include <numeric>

using namespace std;

double sq(double x){return x*x;}

int main(){
	int t;
	cin>>t;
	while(t--){
		int a[10];
		bool t[10];
		for (int i = 0; i < 10; i++)
		{
			cin>>a[i];
		}
		memset(t,0,10);
		int b;
		for (int i = 0; i < 2; i++)
		{
			b = 0;
			for (int j = 0; j < 10; j++)
			{
				if(t[j])continue;
				if(b < a[j]){
					b = a[j];
					t[j] = true;
				}
			}
		}
		int s = accumulate(t,t+10,0);
		if(s == 10)
			puts("YES");
		else 
			puts("NO");
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

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

  int n;
  cin >> n;
  vector<vector<int> > a(n, vector<int>(n-1));
  for (auto &x: a) {
    for (auto &y: x) {
      cin >> y;
      y--; // zero index
    }
  }

  vector<int> next(n);
  vector<int> waiting(n, -1);
  queue<int> que;
  for (int i = 0; i < n; i++) que.push(i);
  queue<int> pending;
  int ans = 0;
  while (true) {
    ans++;
    while (!que.empty()) {
      auto now = que.front();
      que.pop();
      if (next[now] == n-1) continue;
      waiting[now] = a[now][next[now]];
      if (waiting[a[now][next[now]]] == now) {
        waiting[a[now][next[now]]] = -1;
        next[a[now][next[now]]]++;
        if (next[a[now][next[now]]] < n-1) pending.push(a[now][next[now]]);
        waiting[now] = -1;
        next[now]++;
        if (next[now] < n-1) pending.push(now);
      }
    }
    while (!pending.empty()) {
      auto now = pending.front();
      pending.pop();
      que.push(now);
    }
    if (que.empty()) break;
  }

  bool good = true;
  for (int i = 0; i < n; i++) {
    if (next[i] != n-1) {
      good = false;
      break;
    }
  }

  if (good) {
    cout << ans << endl;
  }
  else {
    cout << -1 << endl;
  }

  return 0;
}


Measured memory_bytes: 4224
#include<vector>
#include<iostream>
#include<list>
#include<algorithm>
#include<chrono>
#include<map>
#include<set>
#include<string>
#include<unordered_map>

using namespace std;


int main()
{
    long long n;
    cin >> n;
    string str = "";
    while(n){
        if(n%26){
            str.push_back(n%26+'a'-1);
        }
        else{
            str.push_back('z');
            n -= 26;
        }
        n /= 26;
    }
    reverse(str.begin(), str.end());
    cout << str;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define fori(i,n) for(int i =0;i<n;i++)
#define pb push_back
#define ll long long
#define int long long
#define F first
#define S second
#define mp make_pair
#define rev(a) reverse(a.begin(),a.end())
#define srt(a) sort(a.begin(),a.end())
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout.precision(15);
 
 
int mod = 1e9+7;
 
int pow(int a, int b) {
    int ans = 1;
    a %= mod;
    while(b) {
        if(b%2) {
            ans *= a;
            ans %= mod;
        }
        b /= 2;
        a *= a;
        a %= mod;
    }
    return ans;
}

int inv(int a) {
    return pow(a,mod-2);
}

int mul (int a,int b) {
    return ((a%mod)*(b%mod))% mod;
}

struct cmp {
    bool operator() (pair<int,int> a, pair<int,int> b) const {
        int x = a.F;
        int y = b.F;
        return x>=y;
    }
};


int32_t main() {
    FAST;
    int t;
    // cin>>t;
    t = 1;
    while(t--) {
        int n,k;
        cin>>n>>k;
        vector<int>v(n);
        fori(i,n) cin>>v[i];
        srt(v);
        int ans = 0;
        fori(i,k) ans += v[i];
        cout<<ans;

    }
    
    return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vs = vector<string>;
using vd = vector<double>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
 
const int mod=1e9+7;
 
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
 
mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}
 
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
map<ll, ll> primeFact(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n]++;
  return res;
}
 
void printv(vi& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
void printv(vll& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
int vtotal(vi& v){
  int total=0;
  rep(i,v.size()) total+=v[i];
  return total;
}
 
int main()
{
  //init(); // mint初期化
  cin.tie( 0 );
  ios::sync_with_stdio( false );
  
  string s;cin>>s;
  replace_all(s,',',' ');
  cout(s);
  
  return 0;
}

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

bool enough(int T){
	ll t=0;
	rep(i,N){
		ll r=h[i]-(ll)B*T;
		if(r>0)t+=(r-1)/(A-B)+1;
	}
	return t<=T;
}

int main(void){
	cin>>N>>A>>B;
	h.resize(N);
	rep(i,N)cin>>h[i];

	int ng=0,ok=1e9;
	while(ng+1<ok){
		int m=(ng+ok)/2;
		if(enough(m))ok=m;
		else ng=m;
	}
	cout<<ok<<endl;
	return 0;
}


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

#define REP(i,s,n) for(int i=s; i<n; ++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

typedef long long ll;
typedef pair<int, int> ii;

int main(){

	int n;
	cin >> n;
	map<ll, int> mp;
	rep(i, n){
		ll a;
		cin >> a;
		mp[a]++;
	}

	ll ans = 0;
	for(auto it : mp){
		if(it.first < it.second) ans += (it.second - it.first);
		else if(it.first > it.second) ans += it.second;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;++i)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
using namespace std;

int main(){
  char s[20];
  scanf("%s",s);
  for(int i=0;i<strlen(s);i++){
    if (s[i]==',') printf(" ");
    else printf("%c",s[i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>                                                                          
using namespace std;
int main()
{
  int N,D,X;
  cin >> N >> D >> X;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin >> A.at(i);
  }
  int count=0;
  int j=0;
  for(int i=0; i<N; i++){
    while(1){
      if((A.at(i)*j+1)<=D)
        count++;
      else
        break;
      j++;
    }
    j=0;
  }
  cout << count+X << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double PI = 3.14159265358979;
const double E = 2.718281828459045;
const double root2 = sqrt(2);
typedef pair<int, int> P;
typedef unsigned int ui;
int main() {
	int x; bool g = true;
	while (cin >> x) {
		if (x == 0)break;
		if (!g)cout << endl;
		g = false;
		int coin[4];
		for (int i = 0; i < 4; i++)cin >> coin[i];
		int re = 10 * coin[0] + 50 * coin[1] + 100 * coin[2] + 500 * coin[3] - x;
		int recoin[4] = {};
		recoin[3] = re / 500; re %= 500;
		recoin[2] = re / 100; re %= 100;
		recoin[1] = re / 50; re %= 50;
		recoin[0] = re / 10;
		int out[4];
		for (int i = 0; i < 4; i++)out[i] = coin[i] - recoin[i];
		if (out[0] > 0)cout << 10 << " " << out[0] << endl;
		if (out[1] > 0)cout << 50 << " " << out[1] << endl;
		if (out[2] > 0)cout << 100 << " " << out[2] << endl;
		if (out[3] > 0)cout << 500 << " " << out[3] << endl;
	}
	return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>//for queue and priority_queue
#include <fstream>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#define endl "\n"
typedef long long ll;
using namespace std;
void Lancer() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
bool isPrime(ll n){
	if (n == 2 || n == 3 || n == 5)
		return true;
	else if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n == 1)
		return false;
	else {
		for (int i = 5; i <= sqrt(n); i += 2){
			if (n%i == 0)
				return false;
		}
		return true;
	}
}

int frq[123];
int main(){
	Lancer();
	ll d, n;
	cin >> d >> n;
	if (n < 100){
		if (d == 0)
			cout << n;
		else if (d == 1)
			cout << n * 100;
		else
			cout << n * 10000;
	}
	else {
		if (d == 0)
			cout << n+1;
		else if (d == 1)
			cout << (n+1) * 100;
		else
			cout << (n+1) * 10000;

	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3656