akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main (){
  int n,a,c[200001],ans;
  cin>>n;
  ans=n;
  c[0]=0;
  int x=0;
  for(int i=0;i<n;i++){
    cin>>a;
    while(c[x]>a) x--;
    if(c[x] == a) ans--;
    else c[++x] = a;
  }
  cout<<ans<<endl;

  return 0;
}
    

Measured memory_bytes: 1940
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x is not None: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(root)); print(preorder(root))


Measured memory_bytes: 63396
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int N = sc.nextInt();
        sc.nextLine();
        M[] magics = new M[N];
        for (int i = 0; i < N; i++) {
            M m = new M();
            m.atack = sc.nextInt();
            m.consume = sc.nextInt();
            sc.nextLine();
            magics[i] = m;
        }
        Comparator<M> comparator = Comparator.comparingInt(m -> m.consume);
        comparator = comparator.thenComparingInt(m -> -m.atack);
        Arrays.sort(magics, comparator);
        if (magics[0].atack >= H) {
            System.out.println(magics[0].consume);
            return;
        }
        int[] DP = new int[H + 1];
        DP[0] = 0;
        for (int i = 1; i <= magics[0].atack; i++) {
            DP[i] = magics[0].consume;
        }
        for (int i = magics[0].atack + 1; i < DP.length; i++) {
            int minDP = Integer.MAX_VALUE;
            for (M magic : magics) {
                int hp = Math.max(i - magic.atack, 0);
                int dp = DP[hp] + magic.consume;
                minDP = Math.min(dp, minDP);
            }
            DP[i] = minDP;
        }

        System.out.println(DP[H]);
    }

    static class M {
        int atack;
        int consume;
    }
}

Measured memory_bytes: 35324
k = int(input())
x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(x[k-1])

Measured memory_bytes: 2940
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iterator>
#include <cstring>

using namespace std;
const int INF = (1<<30);
const int NEGA=-INF; 
typedef pair<int, int> P;
typedef long long ll;
#define PB push_back
#define rep(i, a) for (int i = 0; i < a; i++)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define mp make_pair
#define INT int_64

ll ans = 0;
int a;
int main() 
{
    int n;
    cin>>n;
    cout<<800*n-(n/15)*200<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ld  double
#define ll long long 
#define pp push
#define pb push_back
#define pf push_front
#define mp make_pair
#define inf 1e9
#define f first
#define s second
#define pll pair<ll,ll>
#define vll vector<ll>
#define vi vector<int>
#define mod 1000000007
using namespace std;
ll n;
ll a[500];
ll pref[500];
ll dp[500][500];
ll solve(ll i,ll j)
{
    if(dp[i][j]!=-1)return dp[i][j];
    else if(i==j)return dp[i][j]=0;
    else if(i+1==j)return dp[i][j]=a[i]+a[j];
    else
    {
      ll mn=100000000000000;
      for(ll k=i;k<j;k++)
      {
          ll sum;
          if(i==0)sum=pref[j];
          else sum=pref[j]-pref[i-1];
          mn=min(mn,solve(i,k)+solve(k+1,j)+sum);
      }
      return dp[i][j]=mn;
    }
}
int main()
{
    cin>>n;
    for(ll i=0;i<n;i++)cin>>a[i];
    pref[0]=a[0];
    memset(dp,-1,sizeof(dp));
    for(ll i=1;i<n;i++)
    {
        pref[i]=pref[i-1]+a[i];
    }
    cout<<solve(0,n-1);
}

Measured memory_bytes: 2176
var
s:char;
begin
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(' ');
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(' ');
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
write(s);
read(s);
writeln(s);
end.

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

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()

#define SI(n) scanf("%d",&n)
#define PI(n) printf("%d\n",n)
#define SL(n) scanf("%lld",&n)
#define PL(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define TRACE
#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
typedef long long int 	LL;
typedef long double 	LD;
typedef pair<int,int>   II;
typedef vector<int>     VI;
const int MOD = 1e9 + 7;
const int N = 100011;


int main() {
    int A, B;
    SI(A), SI(B);
    string s;
    cin>>s;
    if(s[A] == '-' && SZ(s) == A + B + 1) {
        for(int i = 0; i < SZ(s); ++i) {
            if(i == A)
                continue;
            if(s[i] < '0' || s[i] > '9')
                return 0*printf("No\n");
        }
        return 0*printf("Yes\n");
    }
    return 0*printf("No\n");
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
string s3[3]={"aab", "b.b", "baa"};
string s4[4]={"aaba", "ccba", "abcc", "abaa"};
string s5[5]={"aab.a", "b.b.a", "bc.bb", "acaa.", "abbcc"};
string s6[6]={"aabbaa", ".b.a.b", ".b.a.b", "aabbaa", "b.a.b.", "b.a.b."};
string s7[7]={"aabbaa.", "bba...a", "a.a...a", "abb...b", "...bbab", "...a.ac", "...abbc"};
int main()
{
	int n;
	cin>>n;
	if(n==2){
		cout<<-1<<endl;
		return 0;
	}
	if(n==3){
		for(int i=0; i<n; i++) cout<<s3[i]<<endl;
		return 0;
	}
	string ans[1010];
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) ans[i]+='.';
	if(n%4==0){
		for(int i=0; i<n/4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++) ans[4*i+j][4*i+k]=s4[j][k];
	}else if(n%4==1){
		for(int j=0; j<5; j++) for(int k=0; k<5; k++) ans[j][k]=s5[j][k];
		for(int i=0; i<(n-5)/4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++) ans[5+4*i+j][5+4*i+k]=s4[j][k];
	}else if(n%4==2){
		for(int j=0; j<6; j++) for(int k=0; k<6; k++) ans[j][k]=s6[j][k];
		for(int i=0; i<(n-6)/4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++) ans[6+4*i+j][6+4*i+k]=s4[j][k];
	}else{
		for(int j=0; j<7; j++) for(int k=0; k<7; k++) ans[j][k]=s7[j][k];
		for(int i=0; i<(n-7)/4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++) ans[7+4*i+j][7+4*i+k]=s4[j][k];
	}
	for(int i=0; i<n; i++) cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 2304
s = input()
flag = True
if s[0]!='A': flag=False
if s[2:-1].count('C')!=1: flag=False
if flag:
    l = list(s[2:-1])
    l.remove('C')
    s = s[1] + ''.join(l) + s[-1]
    if s!=s.lower(): flag=False
print("AC" if flag else "WA")

Measured memory_bytes: 38384
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <iomanip>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

void pour(int idx, double &water, int l, int r, vector<double> &H, vector<double> &B, vector<double> &h){
  if(r - l >= 2){
    int mx = l+1;
    for(int i = l+1; i <r; i++){
      if(H[i] > H[mx])
        mx= i;
    }
    if(idx < mx){
      pour(idx, water, l, mx, H, B, h);
      pour(idx, water, mx, r, H, B, h);
    }else{
      pour(idx, water, mx, r, H, B, h);
      pour(idx, water, l, mx, H, B, h);
    }
  }

  double w = B[r] - B[l], u = min(H[l], H[r]);
  double dh = water / w;

  //全て入る時
  if(h[l] + dh < u){
    water = 0;
    for(int i = l; i < r; ++i){
      h[i] += dh;
    }
  //溢れる時
  }else{
    water -= (u - h[l]) * w;
    for(int i = l; i < r; ++i){
      h[i] = u;
    }
  }
}

int main(){

  int D;
  cin >> D;

  REP(ii,D){
    int n, m, l;
    cin >> n;
    vector<double> B(n+2), H(n+2);
    FOR(i,1,n+1){
      cin >> B[i] >> H[i];
    }
    B[0] = 0; B[n+1] = 100;
    H[0] = H[n+1] = 50;

    cin >> m;
    vector<double> F(m), A(m);
    REP(i,m){
      cin >> F[i] >> A[i];
      A[i] /= 30.0;
      //なんばんめの壁の右横にあるか？
      F[i] = distance(B.begin(),lower_bound(ALL(B), F[i])) - 1;
    }
    cin >> l;
    REP(i,l){
      int p, t;
      cin >> p >> t;
      vector<double> h(n+1);
      REP(j,n+1){
        h[j] = 0;
      }
      REP(j,m){
        double water = A[j] * t;
        pour(F[j], water, 0, n+1, H, B, h);
      }
      p = distance(B.begin(),lower_bound(ALL(B), p)) - 1;
      cout << setprecision(10) << h[p] << endl;
    }
  }
  return 0;
}




Measured memory_bytes: 3268
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

typedef vector<vector<int>> Graph;
queue<int> que;
vector<int> par;//各ノードの親
void bfs(int s, Graph &g){
  que = queue<int>();
  par = vector<int>(g.size(), -1);
  que.push(s);
  while(!que.empty()){
    int v = que.front();
    que.pop();
    for(int nv : g[v]){
      if(par[nv] != -1){//訪問済み
        continue;
      }
      else{
        par[nv] = v;//親ノードを保存
        que.push(nv);
      }
    }
  }
}

signed main(){
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);

  int n,m;
  cin >> n >> m;
  Graph v(n);
  REP(i,m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }

  bfs(0, v);

  cout << "Yes" << endl;
  REP(i, n - 1){
    cout << par[i + 1] + 1 << endl;
  }  

  return 0;
}

Measured memory_bytes: 12872
# n = スイッチ数, m = 電球数
n, m = gets.chomp.split(' ').map {|n| n.to_i}

k_list = [] #i番目の電球に繋がるスイッチ数
s_lists = [] #i番目の電球に繋がるスイッチのリスト
p_list = [] #i番目の電球の繋がる点灯しているスイッチの個数を2で割った余り

m.times do |i|
  line = gets.split(' ').map {|n| n.to_i}
  k = line[0]
  k_list << k
  s_lists << line.drop(1)
end
p_list = gets.split(' ').map {|n| n.to_i}

# pp k_list
# pp s_lists
# pp p_list

def check_ok?(s_case, s_lists, p_list)
  m_i = 0
  s_lists.each do |s_list|
    on_total = 0
    s_list.each do |s_id|
      on_total += s_case[s_id - 1]
    end
    return false unless on_total % 2 == p_list[m_i]
    m_i += 1
  end
  true
end

ans = 0
all_list = [0, 1].repeated_permutation(n).to_a
all_list.each do |s_case|
  ans += 1 if check_ok?(s_case, s_lists, p_list)
end

puts ans


Measured memory_bytes: 1916
#include <stdio.h> 

int main () {
	int n;
	scanf("%d", &n);
	char s[n + 1];
	scanf("%s", s);
	if (n % 2 == 1) {
		printf("No\n");
	} else {
		int flag = 1;
		for (int i = 0; i < n/2 ; i++) {
			if(s[i] != s[i + n /2]) {
				flag = 0;
			}
		}
		if (flag) {
			printf ("Yes\n");
		} else {
			printf("No\n");
		}
	}
	return 0;
}

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

a.sort()
# print (a)

ans = 0
count = 0
keep = a[0]
for i in a+[0]:
    if i == keep:
        count +=1
    else:
        if count < keep:
            ans += count
            count = 1
            # print ('A', ans)
        else:
            ans += count-keep
            count = 1
            # print ('B', ans)
    keep = i

print (ans)

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

struct Edge {
  int to, weight;
  Edge(int t, int w) :to(t), weight(w) {}
};

struct Tree {
  vector<vector<Edge>> edges;

  Tree(int N) :edges(N) {}

  void addEdge(int a, int b) { addEdge(a, b, 1); }

  void addEdge(int a, int b, int w) {
    edges[a].emplace_back(b, w);
    edges[b].emplace_back(a, w);
  }
};

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

  Tree T(N);
  rep(i, N - 1) {
    int x, y, w; cin >> x >> y >> w;
    x--; y--;
    T.addEdge(x, y, w);
  }

  vector<int> bfs(N, -1);
  queue<int> q;

  bfs[0] = 0;
  q.push(0);

  while (!q.empty()) {
    int v = q.front(); q.pop();

    for (Edge e : T.edges[v]) {
      int nv = e.to;
      if (bfs[nv] != -1) continue;

      bfs[nv] = (bfs[v] + e.weight) % 2;
      q.push(nv);
    }
  }

  rep(i, N) cout << bfs[i] << endl;
}

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

namespace ABC
{
    class ProgramC
    {
        // 行数可変のdfs
        static void Main(string[] args)
        {
            _h = 2;
            _w = int.Parse(Console.ReadLine());
            _graph = new int[_h][];
            _graph[0] = Console.ReadLine().Split(" ").Select(x => int.Parse(x)).ToArray();
            _graph[1] = Console.ReadLine().Split(" ").Select(x => int.Parse(x)).ToArray();

            dfs(0, 0, 0);

            Console.WriteLine(_max);
        }

        static int[][] _graph;
        static int _h;
        static int _w;

        static int _max;
        static int[] _dx = new int[] { 0, 1 };
        static int[] _dy = new int[] { 1, 0 };

        static void dfs(int h, int w, int count)
        {
            count += _graph[h][w];
            if (h == _h - 1 && w == _w - 1)
            {
                _max = Math.Max(_max, count);
                return;
            }

            for (var i = 0; i < 2; i++)
            {
                var nh = h + _dy[i];
                var nw = w + _dx[i];

                if (nh < 0 || _h <= nh) continue;
                if (nw < 0 || _w <= nw) continue;

                dfs(nh, nw, count);
            }
        }
    }
}


Measured memory_bytes: 28316
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

			int  AB = sc.nextInt();
			int  BC = sc.nextInt();
			int  CA = sc.nextInt();

			int ans = AB * BC / 2;

			System.out.println(ans);
	}
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());
    int sum = 0;
    for (int i = 0; i < K; ++i) {
        sum += p[i];
    }
    cout << sum << '\n';
    return 0;
}

Measured memory_bytes: 3660
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl
#define NL <<"\n"

using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
//#undef NUIP
#ifdef NUIP
#include "benri.h"
#else
#define out(args...)
#endif
#ifdef __cpp_init_captures
template<typename T>vector<T> table(int n, T v){ return vector<T>(n, v);}
template <class... Args> auto table(int n, Args... args){auto val = table(args...); return vector<decltype(val)>(n, move(val));}
#endif
const ll MOD=1e9+7; //998244353

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout<<fixed<<setprecision(0);
	int n;
	cin>>n;
	vector<pair<string,int>> ps(n);
	rep(i,n) cin>>ps[i].X>>ps[i].Y;
	string s;
	cin>>s;
	ll re=0;
	int f=0;
	for(auto p:ps){
		if(f) re+=p.Y;
		if(p.X==s) f=1;
	}
	cout<<re NL;
  return 0;
}


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

int main() {
    int n;
    while(cin >> n, n) {
        vector<tuple<string, int, int>> v(n);
        for(int i=0; i<n; ++i) {
            string name;
            int w, s;
            cin >> name >> w >> s;
            v[i] = make_tuple(name, w, s);
        }
        vector<int> id(n);
        for(int i=0; i<n; ++i) {
            id[i] = i;
        }
        vector<string> res(n);
        double g = 1e9;
        do {
            bool ok = true;
            int sum = 0;
            for(int i=n-1; i>=0; --i) {
                ok &= sum <= get<2>(v[id[i]]);
                sum += get<1>(v[id[i]]);
            }
            if(ok) {
                double g2 = 0;
                for(int i=0; i<n; ++i) {
                    g2 += get<1>(v[id[i]]) * (i+1);
                }
                if(g2 < g) {
                    g = g2;
                    for(int i=0; i<n; ++i) {
                        res[i] = get<0>(v[id[i]]);
                    }
                }
            }
        } while(next_permutation(id.begin(), id.end()));
        
        for(auto& x : res) {
            cout << x << endl;
        }
    }
}


Measured memory_bytes: 3124
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  string s, t; cin >> s >> t;
  cout << (s == t.substr(0, s.length()) ? "Yes\n" : "No\n");
  return 0;
}


Measured memory_bytes: 3656
import math
X = int(input())
if X == 2:
    print(2)
    exit()
elif X == 3:
    print(3)
    exit()
elif X == 4 or X == 5:
    print(5)
    exit()
elif X == 6 or X == 7:
    print(7)
    exit()
elif X == 8:
    print(11)
    exit()
a = X
while True:
    b = math.floor(a**0.5)
    for i in range(2,(b+1)):
        if a%i == 0:
            break
        if i == b:
            print(a)
            exit()
    a += 1

Measured memory_bytes: 3188
#include<iostream>
#include<string>


using namespace std;

int main()
{
     long long n;
     string s;
      cin>> n >> s;
      int len = s.length();
      int c =1;
      for( int i=0; i<len -1; i++)
        if(s[i] != s[i+1]) c++;
      cout<<c<<endl;

    return 0;
}


Measured memory_bytes: 512
import java.util.*;

public class Main {

    public static void main(String[] args) {
        exec();
    }

    static void exec() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A = new int[n];
        int[] B = new int[n];
        int[] C = new int[n-1];

        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            B[i] = sc.nextInt();
        }
        for (int i = 0; i < n-1; i++) {
            C[i] = sc.nextInt();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += B[i];
            if(i > 0 && A[i]- A[i-1] == 1) {
                ans += C[A[i-1]-1];
            }
        }

        System.out.println(ans);
   }
}

Measured memory_bytes: 22740
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
int p[110000];
int q[110000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<b;i++)scanf("%d",q+i);
	int P=mod;
	int Q=mod;
	for(int i=0;i<a;i++)P=min(P,p[i]);
	for(int i=0;i<b;i++)Q=min(Q,q[i]);
	int ret=P+Q;
	for(int i=0;i<c;i++){
		int s,t,u;
		scanf("%d%d%d",&s,&t,&u);
		s--;t--;
		ret=min(ret,p[s]+q[t]-u);
	}
	printf("%d\n",ret);
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<int> s;
    for(int i = n-1; i >= 0; i--){
        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();
        if(idx == s.size()){
            s.push_back(a[i]);
        }
        else{
            s[idx] = a[i];
        }
    }
    cout << s.size() << endl;
    return 0;
}

Measured memory_bytes: 1276
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int s = sc.nextInt();
    int w = sc.nextInt();
    
    if(s <= w){
      System.out.println("unsafe");
    }else{
      System.out.println("safe");
    }
  }  
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x;
	cout<<x+x*x+x*x*x<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int a[10000001],an;
int main()
{
	memset(a,0,sizeof(a));
	int n,sum=0;
	cin>>n;
	for (int i=1; i<=n; ++i)
	{
	
		cin>>a[i];
	     sum+=abs(a[i]-a[i-1]);
     }
     //cout<<sum<<endl;
     int ans;
    for (int i=1; i<=n-1;++i)
    {
    	ans=sum;
    	ans=ans-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]);
    	cout<<ans+abs(a[n])<<endl;
	}
	ans=sum;
    cout<<ans-abs(a[n]-a[n-1])+abs(a[n-1])<<endl;
 } 

Measured memory_bytes: 40320
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
l=[lmp() for i in range(n)]
l.append([10**6,10**6])
val=[]
heapq.heapify(val)
ans=0
c=0
l=sorted(l,key=lambda x: x[0],reverse=True)
for i in range(1,m+1):
    while l[-1][0]==i:
        q=l.pop()
        heapq.heappush(val,(-1)*q[1])
        c+=1
    if c>0:
        ans-=heapq.heappop(val)
        c-=1
print(ans)

Measured memory_bytes: 31796
N,M = list(map(int,input().split()))

AC = [0]*N
WA = [0]*N
miss = 0

for i in range(M):
    p,S = list(map(str,input().split()))
    p = int(p)-1
    
    if S == 'AC' and AC[p] == 0:
        AC[p] = 1
        miss += WA[p]
        
    WA[p] += 1
        
print(sum(AC),miss)

Measured memory_bytes: 4596
// A - Shrinking

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

bool done(string t, char c) {
	bool res = true;
	for (int i=0; i<t.size(); i++) {
		if (t[i] != c) {
			res = false;
			break;
		}
	}

	return res;
}

int main() {
	string s;
	cin >> s;

	int ans = INF;
	for (char c='a'; c<='z'; c++) {
		int cnt = 0;
		string t = s;
		for (int i=t.size()-1; i>=0; i--) {
			//cout << t << endl; // **** debug ****
			if (done(t, c)) break;
			cnt++;
			string u = "";

			for (int j=0; j<i; j++) {
				if (t[j] == c || t[j+1] == c) u.push_back(c);
				else u.push_back(t[j]);
			}
			t = u;
		}
		ans = min(ans, cnt);
	}

	cout << ans << endl;

	return 0;
}

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

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

struct mobile {
  int lm,rm,lc,rc,ll,rl;
  mobile(int lc,int rc,int ll,int rl)
  : lc(lc), rc(rc), ll(ll), rl(rl) {
    lm = rm = -1;
  }
};

int gcd(int a,int b) {
  return b != 0 ? gcd(b, a%b) : a;
}

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

int dfs(int pos,vector<mobile> &vm) {
  mobile now = vm[pos];
  now.lm = (now.lc == -1) ? 1 : dfs(now.lc,vm);
  now.rm = (now.rc == -1) ? 1 : dfs(now.rc,vm);
  int g = lcm(now.ll*now.lm, now.rl*now.rm);
  now.rm = g / now.rl;
  now.lm = g / now.ll;
  return now.rm+now.lm;
}

int main() {
  int n,i,p,q,r,b,root;
  while(cin>>n, n) {
    vector<mobile> vm;
    vector<bool> isroot(n+1,true);
    root = -1;
    rep(i,n) {
      cin>>p>>q>>r>>b;
      r--,b--;
      if(r >= 0) isroot[r] = false;
      if(b >= 0) isroot[b] = false;
      vm.push_back(mobile(r,b,p,q));
    }

    rep(i,n) if(isroot[i] == true) root = i;
    cout<<dfs(root,vm)<<endl;
  }
}

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

int N;
int a[100010];

int main()
{
	ios::sync_with_stdio(false);
	
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+N);
	int cnt=unique(a+1,a+1+N)-(a+1);
	if(cnt%2==0) cnt--;
	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 640
mod = 10**9 + 7
fac = []
pw = []

fac.append(1 % mod)
pw.append(1 % mod)
for i in range(1, 1001):
    fac.append(fac[i-1]*i % mod)

for i in range(1, 1001):
    pw.append(pow(fac[i], mod-2, mod))

k, n = [int(s) for s in input().split()]
if k > n:
    print(0)
else:
    print(fac[n]*pw[k]*pw[n-k] % mod)



Measured memory_bytes: 5624
import itertools

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

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)

ans = 0
div = fact(n)
for lst in itertools.permutations(range(n), n):
    start = xy[lst[0]]
    for pos in lst:
        dx = start[0] - xy[pos][0]
        dy = start[1] - xy[pos][1]
        d = (dx ** 2 + dy ** 2) ** 0.5
        ans += d / div
print(ans)
    

Measured memory_bytes: 9368
from sys import stdin
 
def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    # print(l)
    ans = 0
    for i in range(len(l)-2):
        first = l[i]
        for j in range(i + 2, len(l)):
            second = l[j]
            s = i + 1
            e = j 
            # print("start",s, e)
            while(True):
                mid = int((s + e) / 2)
                # print("S",s, e, mid)
                
                if s == e:
                    break
                else:
                    if second >= first + l[mid]:
                        if s == mid:
                            s = e
                        else:
                            s = mid
                    else:
                        e = mid
            # print(s)
            ans += j - s
            # print("ans", ans)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 41820
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <string>

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

using namespace std;
void C_143()
{
  int N;
  string S;
  cin >> N >> S;

  int slime_num = 1;
  for (int i = 1; i < (int)S.size(); ++i)
  {
    if (S[i] != S[i - 1]) ++slime_num;
  }
  cout << slime_num << endl;
}

int main()
{
  //C_140();
  //C_141();
  //C_142();
  C_143();
  return 0;
}


Measured memory_bytes: 512
function main(input){
    lines = input.split(" ");
    var N = Number(lines[0]);
    var P = Number(lines[1]);
    var i=1;
    var ans=1;
    if(N==1){
        ans=P;
    }else if(P==1||N>P){
        ans=1;
    }else{
        while(true){
            var k = Math.pow(i,N);
            if(k>P){break;}
            if(P%k==0){ans=i;}
            i++;
        }
    }

    console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin','utf8'));


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

int main() {
  int n, k;
  cin >> n >> k;
  
  int sum = 1;
  for (int i = 0; i < n; i++) {
    if (sum * 2 <= sum + k) {
      sum *= 2;
    }
    else if (sum * 2 >= sum + k) {
      sum += k;
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
/*Keyence Programming Contest 2020*/
/*A*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;

#define LL long long
#define DB double
#define MOD 59393
#define Pr pair<DB,int>
#define X first
#define Y second
#define MAXN 100000
#define INF 1200000001
#define mem(x,p) memset(x,p,sizeof(x))

LL read(){
  LL x=0,F=1;char c=getchar();
  while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
  return x*F;
}

int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return 1LL*a*b%MOD;}

int n,ans;
struct node{
    int l,r;
}p[MAXN+5];
bool cmp(node s1,node s2){
    return s1.r<s2.r;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++){
        int a=read(),b=read();
        p[i]=(node){a-b,a+b};
    }
    sort(p+1,p+n+1,cmp);
    int r=p[1].r;ans++;
    for(int i=2;i<=n;i++)
    if(p[i].l>=r)r=p[i].r,ans++;
    printf("%d",ans);
}


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

int main() {
    int N;
    cin >> N;
    if (N <= 999) cout << "ABC" << endl;
    else cout << "ABD" << endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    S = input()
    if S[0] != 'A':
        print('WA')
        exit()
    if S[2:-1].count('C') != 1:
        print('WA')
        exit()
    s = list(S)
    s[0] = 'a'
    ci = 2 + S[2:-1].index('C')
    s[ci] = 'c'
    if ''.join(s) != S.lower():
        print('WA')
        exit()
    print('AC')


main()


Measured memory_bytes: 3064
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	ll x, y;
	cin>>x>>y;
	ll res = 0;
	while(x<=y){
		res++;
		x<<=1;
	}
	cout<<res<<endl;
	return 0;
}


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

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

int Q;
int ansA[200200];
pii AB[200200];
int TYPE[200200];
int A2[200200];
int grad[200200];

struct BIT {
    int dat[200200];

    BIT() {
        rep(i, 200200)dat[i] = 0;
    }

    void add(int a, int x) {
        while (a < 200200) {
            dat[a] += x;
            a += a & -a;
        }
    }

    int sum(int a) {
        int res = 0;
        while (a > 0) {
            res += dat[a];
            a -= a & -a;
        }
        return res;
    }
};


signed main() {
    cin >> Q;
    vector<int> AS;
    rep(i, Q) {
        cin >> TYPE[i];
        int type = TYPE[i];
        if (type == 1) {
            int a, b;
            cin >> a >> b;
            AB[i] = pii(a, b);
            AS.push_back(a);
        }
    }
    sort(AS.begin(), AS.end());
    AS.erase(unique(AS.begin(), AS.end()), AS.end());
    rep(i, Q) {
        if (TYPE[i] == 1) {
            A2[i] = l_b(AS.begin(), AS.end(), AB[i].first) - AS.begin();
        }
    }
    BIT bit, bit2;
    int sum = 0, bsum = 0;
    int n = 0;
    rep(i, Q) {
        if (TYPE[i] == 1) {
            bit.add(A2[i] + 1, 1);
            bit2.add(A2[i] + 1, AS[A2[i]]);
            n++;
            sum += AB[i].first;
            bsum += AB[i].second;
        } else {
            int cannot = 0, can = 200100;
            while (can - cannot > 1) {
                int m = (cannot + can) / 2;
                if (bit.sum(m) < (n + 1) / 2) {
                    cannot = m;
                } else can = m;
            }
            ansA[i] = AS[can - 1];
            int ans = 0;
            ans += sum + bsum - n * AS[can - 1];
            ans -= 2 * (bit2.sum(can - 1) - AS[can - 1] * bit.sum(can - 1));
            cout << ansA[i] << " " << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 14708
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, m, s, a[MAXN];
int x, y, cur[MAXN], res[MAXN], ans[MAXN];
bool cnp(int s, int t) {
	if ((a[s] == x) == (a[t] == x)) return s < t;
	else return (a[s] == x) < (a[t] == x);
}
void work(int len) {
	bool valid = true, found = false;
	for (int i = 1; i <= len; i++)
		a[cur[i]]--;
	int Min = a[1], Max = a[1];
	for (int i = 2; i <= n; i++) {
		chkmin(Min, a[i]);
		chkmax(Max, a[i]);
	}
	if (Min * 2 >= Max) {
		found = true;
		for (int i = 1; i <= len; i++)
			res[i] = cur[i];
		sort(res + 1, res + len + 1);
	} else if (Min * 2 + 1 == Max) {
		x = Min, y = Max;
		int k1 = 0, k2 = 0, k = 0;
		static int res1[MAXN], res2[MAXN];
		for (int i = 1; i <= len; i++)
			if (a[cur[i]] == Min || a[cur[i]] == Max) res1[++k1] = cur[i];
			else res2[++k2] = cur[i];
		sort(res1 + 1, res1 + k1 + 1, cnp);
		sort(res2 + 1, res2 + k2 + 1);
		int x1 = 1, x2 = 1;
		for (int i = 1; i <= len; i++)
			if (x1 <= k1 && x2 <= k2) {
				if (res1[x1] < res2[x2]) res[i] = res1[x1++];
				else res[i] = res2[x2++];
			} else {
				if (x1 <= k1) res[i] = res1[x1++];
				else res[i] = res2[x2++];
			}
		found = true;
		for (int i = len + 1; i <= n; i++)
			if (a[cur[i]] == Min) found = false;
		found |= (x1 == 0) || (a[res1[1]] == Max);
	}
	for (int i = 1; i <= len; i++)
		a[cur[i]]++;
	if (!valid || !found) res[1] = 0;
}
bool cmp(int *a, int *b) {
	int pos = 1;
	while (a[pos] == b[pos]) pos++;
	return a[pos] < b[pos];
}
bool check() {
	int Min = a[1], Max = a[1];
	for (int i = 2; i <= n; i++) {
		chkmin(Min, a[i]);
		chkmax(Max, a[i]);
	}
	return Min * 2 >= Max;
}
int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		s += a[i];
	}
	if (!check()) {
		puts("-1");
		return 0;
	}
	for (int i = 1; i <= n; i++)
		cur[i] = i;
	work(n);
	for (int i = 1; i <= n; i++) {
		m++, a[res[i]]--;
		cur[i] = res[i];
		ans[m] = res[i];
	}
	while (m != s) {
		static int inc[MAXN];
		memset(inc, 0, sizeof(inc));
		int len = 0; inc[1] = n + 1;
		for (int i = 1; i <= n; i++) {
			work(i);
			if (res[1] != 0 && cmp(res, inc)) {
				len = i;
				for (int j = 1; j <= i; j++)
					inc[j] = res[j];
			}
		}
		for (int i = 1; i + len <= n; i++)
			cur[i] = cur[i + len];
		for (int i = 1; i <= len; i++) {
			ans[++m] = inc[i];
			cur[n - len + i] = inc[i], a[inc[i]]--;
		}
	}
	for (int i = 1; i <= m; i++)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}


Measured memory_bytes: 3792
from queue import PriorityQueue
import sys

sys.setrecursionlimit(10**9)

IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N=100005
fa=[int(0) for i in range(2*(N+1))]
xNum=[int(0) for i in range(2*(N+1))]
yNum=[int(0) for i in range(2*(N+1))]

def find(x):
    if(x==fa[x]):return x
    else:
        fa[x]=find(fa[x])
        return fa[x]

n=input()
n=int(n)

for i in range(2*N+1):
    fa[i]=i

for i in range(n):
    x,y=IA()
    y+=N
    fx=int(find(x))
    fy=int(find(y))
 
    if(fx!=fy):
        fa[fy]=fx
for i in range(N):
    xNum[find(i)]+=1
for i in range(N):
    yNum[find(i+N)]+=1
ans=0
for i in range(N):
    ans+=xNum[i]*yNum[i]
print(ans-n)




Measured memory_bytes: 15152
n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

a=[0]
b=[0]
for i in range(n):
  a.append(a[i]+A[i])
for i in range(m):
  b.append(b[i]+B[i])
ans=0
j=m
for i in range(n+1):
  if a[i]>k:
    break
  while a[i]+b[j]>k:
    j-=1
  ans=max(ans,i+j)
print(ans)

Measured memory_bytes: 47300
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
#define rep(i,n) for(int i = 0;i<(n);i++);
using namespace std;
using ll = long long;
const ll INF = 100100100100100;

int main() {
	vector<ll> num = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	ll x;
	cin >> x;
	cout << num[x - 1] << endl;
}

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

int main() {
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
	ll ans = 0;
	if(K<A){
		ans += K;
		cout << ans << endl;
		return 0;
	}
	ans += A;
	K -= A;
	if(K<B){
		cout << ans << endl;
		return 0;
	}
	K -= B;
	ans -= K;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
n = int(input())
a = list(map(int,input().split()))
a.sort()

def solve(m):
    size = sum(a[:m])
    for j in range(m,n):
        if size*2 >= a[j]:
            size += a[j]
        else:
            return False
    return True

def binary_search(l,r):
    while abs(r-l) >1:
        mid = (l+r)//2
        if solve(mid):#判定のとこは別で
            r = mid
        else:
            l = mid
    return l
print(n-binary_search(0,n))

Measured memory_bytes: 63856
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second

void Max(int &x, int y) {
    if (x < y) x = y;
}

void Min(int &x, int y) {
    if (x > y) x = y;
}


int main(void) {

    int n, m;
    cin >> n >> m;
    int x = 0, y = 0;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            string s;
            cin >> s;
            if (s == "snuke") {
               x = j;
               y = i + 1;
            }
        }
    }
    printf("%c%d\n", x + 'A', y);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int n,d,k,i,x,sum=0;;
    cin>>n>>d>>k;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        sum=sum+(d-1)/x+1;
    }
    cout<<k+sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e5 + 5;


int32_t main()
{
   IOS;
   string s;
   cin >> s;

   if(s[s.length()-1]=='s')
   {
   		cout << s << "es" << endl;
   }

   else
   {
   		cout << s << "s" << endl;
   }
   


   return 0;
}
 

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;

ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}
ll mod(ll a, ll b) {return (a % b + b) % b;}
using namespace std;

int main() 
{
	string ss= "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
	fast;
	ll n; string s; cin>>n; vector<string>v;
	for(ll i = 0; i < n; i++)
	{
		cin>>s; v.pb(s);
		if(s.length() < ss.length()) ss = s;
		else if(s.length() == ss.length())
		{
			int c = s.compare(ss);
			if(c < 0) ss = s;
		}
	} ll flag = 0;
	for(ll i = 0; i < ss.size(); i++)
	{
		char c = ss[i]; flag = 1;
		for(ll j = 0; j < n; j++)
		{
			size_t ttt = v[j].find(c);
			if( ttt == string::npos) flag = 0;
			else
			{
				v[j].erase(ttt,1);
			}
		}
		if(flag == 0)
			ss[i] = '.';	
	} 
	sort(ss.begin(),ss.end());
	for(ll i = 0; i < ss.size(); i++)
	{
		if(ss[i] == '.') continue;
		else cout << ss[i];
	}
  	return 0; 
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int a, b, k, n;
	bool flag;
	cin >> k;
	cin >> a >> b;
	n = a;
	flag = false;
	while (n <= b) {
		if (n%k == 0) {
			flag = true;
			break;
		}
		n++;
	}

	if (flag) cout << "OK\n";
	else cout << "NG\n";

	return 0;
}

Measured memory_bytes: 3132
/****************************************************************************************************
                                        SUBMITTED BY-

                                                AISH_07

****************************************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
#define sl set<ll>
#define vs vector<string>
#define pb push_back
#define vl vector<ll>
#define vi vector<int>
#define PI  3.14159265
#define mod 998244353

int main()
{

int n,k;
cin>>n>>k;
ll a[n];
for(int i=0;i<n;i++)
    cin>>a[i];

sort(a,a+n);

ll mini=LONG_MAX;

for(int i=n-1;i-k+1>=0;i--)
    mini=min(a[i]-a[i-k+1],mini);


cout<<mini<<"\n";
return 0;
}


Measured memory_bytes: 4304