akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <list>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
#include <valarray>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = std::vector<int>;
using Vlli = std::vector<lli>;
using Wint = std::vector<Vint>;
using Wlli = std::vector<Vlli>;
using Vbool = std::vector<bool>;
using Wbool = std::vector<Vbool>;
using pii = std::pair<int, int>;
using pll = std::pair<lli, lli>;
template <class T>
using Vec = std::vector<T>;

constexpr int MOD = 1e9 + 7;
constexpr int INFi = 2e9 + 1;
constexpr lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {std::make_pair(1, 0), std::make_pair(-1, 0), std::make_pair(0, 1), std::make_pair(0, -1)};
constexpr char BR = '\n';

#define DEBUG(x) std::cerr << #x << " = " << x << '\n';
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define vREPcopy(ele, vec) for(auto (ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())
#define rSORT(A) std::sort((A).rbegin(), (A).rend())
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())



template <class T> inline int argmin(std::vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(std::vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){if(a < b) a = b;}
template <class T> inline void chmin(T &a, T b){if(a > b) a = b;}
inline int BitI(int k){return 1 << k;}
inline lli BitL(int k){return 1LL << k;}
inline int toInt(const string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res;
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;}
  std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~




int main(void){
  lli r, g, b, n; cin >> r >> g >> b >> n;
  Vint K(n + 1, 0);
  for(lli i = 0; i * r <= n; i++){
    lli A = i * r;
    for(lli j = 0; g * j <= n - A; j++){
      K[g * j + A]++;
    }
  }
  lli res = 0;
  while(n >= 0){
    res += K[n];
    n -= b;
  }
  cout << res << BR;
  return 0;
}

Measured memory_bytes: 888
#include<iostream>

using namespace std;

int main() {
	int x, y;
	cin >> x >> y;

	for (int i = 0; i < x+1; i++) {
		if (i * 2 + (x - i) * 4 == y) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;

	return 0;
}

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

#define endl '\n'
#define ll long long
#define re register
#define pb(x) push_back(x)
#define ce(x) cout << x << '\n';

using db = long double;
using pll = pair < ll, ll >;

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 1000000007
const db pi = acos(-1);
const long long infl = LLONG_MAX;

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision

#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (ll _tt = 0; _tt < tt; _tt++) // testcase 

int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll t,i,x,j,y,z=0,k,n;

cin>>k;	
priority_queue <ll>pq;
pq.push(k);
// while(pq.size()){
// 	z++;
// 	x=pq.top();
// 	pq.pop();
// 	if(x>1){
// 		pq.push(x/2);
// 		pq.push(x/2);
// 	}
// }
x=1;
while(k){
	k=k>>1;
	x=x<<1;
}
// ce(x)
ce(x-1)
}
/*

8->4,4
4->2,2->1,1,1,1

3->1,1
1099511627775
*/


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

int main(void) {
    int N;
    cin>>N;
    vector<int> H;
    for (int i = 0; i < N; i++) {
        int h;
        cin>>h;
        H.push_back(h);
    }

    int cnt = 0;
    int ma = 0;
    for (int i = 0; i < N - 1; i++) {
        if (H.at(i) >= H.at(i + 1)) {
            cnt++;
        } else {
            cnt = 0;
        }
        if (ma < cnt) ma = cnt;
    }
    cout << ma << endl;
    return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n;
	cin >> n;
	
	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	for(int k = 0; k < n; ++k) {
		if( k > 0 ) cout << " ";
		cout << a[k];
	}
	
	cout << endl;
	
	for(int i = 1; i < n; ++i) {
		int v = a[i];
		int j = i - 1;
		
		while( j >= 0 && a[j] > v ) {
			a[j + 1] = a[j];
			j--;
		}
		
		a[j + 1] = v;
		
		for(int k = 0; k < n; ++k) {
			if( k > 0 ) cout << " ";
			cout << a[k];
		}
		
		cout << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3104
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <queue>
#include <stack>
#include <stdlib.h>
using namespace std;
#define rep(i,n) for (int i = 0; i <n; i++) 

#include <bits/stdc++.h>
using namespace std;

using namespace std;
int main(){
    int a,b,n;cin>>n>>a>>b;
    std::cout << min(b,a*n) << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;
const int mod = 1e9+7;

int main() {
    string s; cin >> s;
    int ct = 0;
    rep(i,s.size()-1) {
        if (s[i] != s[i+1]) ct++;
    }
    cout << ct << endl;
}

Measured memory_bytes: 512
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

template<typename T> bool chmin(T& a, const T& b) {
    if (a > b) return a = b, true; else return false;
}

template<typename T> bool chmax(T& a, const T& b) {
    if (a < b) return a = b, true; else return false;
}

// End of template.

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

    int64 n, base = 26, length = 1;
    char s[20] = {};
    cin >> n;
    n--;

    while (n >= base) {
        n -= base;
        base *= 26;
        length += 1;
    }
    rep(i, length) {
        base /= 26;
        s[i] = 'a' + (char) (n / base);
        n = n % base;
    }

    cout << s << '\n';

    return 0;
}



Measured memory_bytes: 3624
s_sub= input()
t = input()
ans = []
for i in range(len(s_sub) - len(t) + 1):
    for j, c in enumerate(t):
        if s_sub[i + j] != c and s_sub[i + j] != '?':
            break
    else:
        s = s_sub[:i] + t + s_sub[i + len(t):]
        sample = ''
        for c in s:
            if c == '?':
                sample += 'a'
            else:
                sample += c
        ans.append(sample)
if len(ans) == 0:
    print('UNRESTORABLE')
else:
    print(min(ans))

Measured memory_bytes: 3064
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template<class T> inline bool chmax(T& a, T b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b) {if (a>b) {a=b; return true;} return false;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    if (s[s.size()-1] == '1' || s[0] == '0') cout << -1 << '\n';
    else {
        queue<ll> que;
        REP(i, s.size()-1) {
            if (s[i] != s[s.size()-2-i]) {
                cout << -1 << '\n';
                return 0;
            }
            if (s[i] == '1') que.push(i);
        }
        que.push(s.size()-1);
        REP(i, s.size()-1) {
            if (i == que.front()) que.pop();
            cout << i+1 << ' ' << que.front()+1 << '\n';
        }
    }
    return 0;
}


Measured memory_bytes: 2384
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<iostream>
#include<map>
#include<cstring>
#define INF 0x3f3f3f3f
#define eps 1e-10
using namespace std;
set<int> a;
map<int,int>tim;
long long n,l[105],ans,maxn,other;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&l[i]);
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            for(int k=j+1;k<=n;k++){
                if(l[i]&&l[j]&&l[k]){
                    if(l[i]==l[j]||l[j]==l[k]||l[i]==l[k])
                        continue;
                    maxn=max(l[i],max(l[j],l[k]));
                    other=l[i]+l[j]+l[k]-maxn;
                    if(other>maxn)
                        ans++;
                }
            }
    printf("%lld",ans);
}

Measured memory_bytes: 3228
#include <iostream>
#define SIZE 2000000 //確保する配列の要素数
using namespace std;
const int num = 10000; //入力される最大値

void CountingSort(int *A, int *B, int k)
{
    int C[num] = {};

    for (int i = 0; i < k; i++)
    {
        C[A[i]]++;
    }

    for (int i = 1; i < num; i++)
    {
        C[i] = C[i] + C[i - 1];
    }

    for (int j = k - 1; j >= 0; j--)
    {
        B[C[A[j]] - 1] = A[j];
        C[A[j]]--;
    }
}

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

    int A[SIZE];
    int B[SIZE];
    int k; //使う配列の要素数

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

    CountingSort(A, B, k);

    int i;
    for (i = 0; i < k - 1; i++)
    {
        cout << B[i] << ' ';
    }
    cout << B[i] << endl;
}


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

int main() {
   int N;
   cin >> N;
   int S = 0;
   int n = N;
   while ( N > 0 ) {
     S = S + N - N / 10 * 10;
     N = N / 10;
   }

   if( n % S == 0 ) cout << "Yes" << endl;
   else cout << "No" << endl;

}

Measured memory_bytes: 3560
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <list>
#include <deque>
#include <sstream>
using namespace std;
typedef pair<int, int> P;

#define FOR(i, a, n) for (ll i = (ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef vector<int> VI;
int GCD(int a, int b){
    if(b==0) return a;
    return GCD(b, a%b);
}

int main() {
    int n; cin >> n;
    int ans=0, cnt=0, out_cnt=0; 
    while(n){
        string s; cin >> s;
        if(s=="HIT"){
            cnt++;
            if(cnt==4){
                ans++;
                cnt--;
            }
        }else if(s=="HOMERUN"){
            ans += cnt+1;
            cnt=0;
        }else{
            out_cnt++;
            if(out_cnt==3){
                cnt=0;
                n--;
                out_cnt=0;
                cout << ans << endl;
                ans=0;
            }
        }
    }
	return 0;
}


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

int main(void)
{
    int a;
    cin >> a;

    int b;char c;
    char d[4][13];
    map<char, int>e;
    map<int, char>f;
    e['S']=0;e['H']=1;e['C']=2;e['D']=3;
    f[0]='S';f[1]='H';f[2]='C';f[3]='D';
    for (int i=0; a > i ; i++)
    {
        cin >> c >> b;
        d[e[c]][b-1]='o';
    }

    for (int i = 0; i < 4; i++)
    {
        for (int t = 0; t < 13; t++)
        {
            if (d[i][t] != 'o')
            {
                cout << f[i] << " " << t+1 << "\n";
            }
        }
    }
}




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

int main() {
  int N;
  long K;
  cin >> N >> K;
  vector<ll> A(N), F(N);
  rep(i, N)  cin >> A.at(i);
  rep(i, N)  cin >> F.at(i);
  sort(A.begin(), A.end());
  sort(F.begin(), F.end());
  reverse(F.begin(), F.end());
  ll ng = -1 , ok = A.at(N - 1) * F.at(0);
  while ( abs(ok-ng) > 1 ) {
    ll mid = (ng + ok) / 2;
    ll count = 0;
    rep(i, N) {
      ll x = A.at(i) * F.at(i) - mid;
      if (x > 0) count += (x + F.at(i) - 1) / F.at(i);
    }
    if (count <= K)  ok = mid;
    else  ng = mid;
  }
  cout << ok << endl;
}

Measured memory_bytes: 3328
import copy
n=int(input())
a=list(input().split())
def BubbleSort(l,n):
    a=copy.deepcopy(l)
    for i in range(n):
        for j in reversed(range(i+1,n)):
            if int(a[j][1])<int(a[j-1][1]):
                a[j],a[j-1]=a[j-1],a[j]
    return a

def SelectionSort(l,n):
    a=copy.deepcopy(l)
    for i in range(n):
        minj=i
        for j in range(i,n):
            if int(a[j][1])<int(a[minj][1]):
                minj=j
        a[i],a[minj]=a[minj],a[i]
    return a

def SP(l):
    for i in range(len(l)):
        if i !=len(l)-1:
            print(l[i],end=' ')
        else:
            print(l[i]) 

BS=BubbleSort(a,n)
SS=SelectionSort(a,n)
SP(BS)
print('Stable')
SP(SS)
if BS==SS:
    print('Stable')
else:
    print('Not stable')


Measured memory_bytes: 6344
#include <bits/stdc++.h> 
using namespace std; 
 
void div(int a) 
{ 
 
	int division[a + 1]; 
	memset(division, 0, sizeof division); 
 
	for (int i = 1; i <= a; i++) 
	{ 
		for (int j = 1; j * i <= a; j++)
		{
			division[i * j]++;
		}
	} 
	long long sum = 0;
	for (int i = 1; i <= a; i++) 
	{
		sum = sum + 1LL * i * division[i];
	}
	cout << sum << "\n";
} 
 
int main() 
{ 
	int x;
	cin >> x;
	div(x);
	return 0; 
}

Measured memory_bytes: 42692
# -*- coding: utf-8 -*-
ALPHABET = ("a", "b", "c", "d", "e", "f", "g", "h", "i", "j")


def f(num, n, s):
    if n == num:
        for _s in sorted(s):
            print(_s)
        return
    else:
        tmp = []
        for i, _s in enumerate(s):
            pre_last_index = ALPHABET.index(sorted(tuple(_s))[-1])
            for al in ALPHABET[:pre_last_index + 2]:
                tmp.append(_s + al)
        f(num + 1, n, tmp)



def main():
    n = int(input())
    f(1, n, ["a"])


if __name__ == '__main__':
    main()


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

using ll = long long;

bool can_do_with_x_attacks(vector<ll> v, const ll x, const ll a, const ll b){
    const ll delta = a-b;
    for(auto& y : v) y -= b * x;
    ll extra_cost = 0;

    for(const auto y : v)
        extra_cost += (ll)ceil((double)max(y, 0ll) / (double)delta);

    return extra_cost <= x; }

ll cbin(const ll st, ll dr, vector<ll> v, const ll a, const ll b){
    for(ll step = 1ll << (ll)log2(dr-st+1); step; step/=2)
        if(dr-step >= st && can_do_with_x_attacks(v, dr-step, a, b))
            dr -= step;
    return dr; }

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> v(n);
    for(auto& x : v) cin >> x;

    cout << cbin(0, 1e9 + 10, v, a, b) << endl;
    return 0; }


Measured memory_bytes: 2560
N,M=map(int, input().split())
A=[int(input()) for _ in range(M)]

A=set(A)
D=[0]*(N+1)
D[0]=1

direction=[1,2]

for i in range(1,N+1):
 if i in A: continue
 # print([abs(H[i]-H[i-a])+D[i-a] for a in [1,2]])
 cnt=0
 for d in direction:
    prv=i-d
    if 0<=prv and not(prv in A): 
        cnt=cnt+D[prv]
        #print(i, prv,D[prv])

 D[i]=cnt
print(D[-1] % 1000000007)

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N;
vector<ll> a;
vector<ll> psum;

ll _sum(ll t) {
  ll ng = -1, ok = N;
  while(ng+1 < ok) {
    ll m = (ok+ng)/2;
    if (a[m] >= t){
      ok = m;
    } else {
      ng = m;
    }
  }
  ll pos = ok;
  if (pos == 0) {
    return t*N;
  }
  // printf("%d + %dx%d\n",psum[pos-1],t,(N-pos));
  return psum[pos-1] + t*(N-pos);
}

ll solve(ll k) {
  ll ok = 0, ng = 300010;
  while(ok+1 < ng) {
    ll m = (ok+ng)/2;
    if (_sum(m) >= m*k) {
      ok = m;
      // printf("ok=%d\n", m);
    } else {
      ng = m;
      // printf("ng=%d sum=%d m*k=%d\n", m, _sum(m), m*k);
    }
  }
  return ok;
}

signed main() {
  ll orig_N;
  {
    //orig_N=24;
    //N = 5;
    //a.push_back(1);
    //a.push_back(3);
    //a.push_back(5);
    //a.push_back(7);
    //a.push_back(8);
  }
  {
    map<ll,ll> mp;
    cin>>orig_N;
    rep(i,orig_N) {
      ll x;
      cin >> x;
      mp[x]++;
    }
    N = mp.size();
    for (auto e: mp) {
      a.push_back(e.second);
    }
  }

  sort(begin(a),end(a));
  psum.resize(a.size());
  psum[0] = a[0];
  for (ll i=1; i<N; i++) {
    psum[i] = psum[i-1] + a[i];
  }

  //cout << "N=" << N << " ";
  //cout << "a=";
  //rep(i,N){
  //  cout<<a[i]<<" ";
  //}
  //cout<<endl;

  //printf("sum(%d)=%d\n", 2, _sum(2));
  for (ll k=1; k<=orig_N; k++) {
    cout << solve(k) << endl;
  }
}


Measured memory_bytes: 22512
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Collections;
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String C = scan.next();
    String alphabet[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
    for (int i = 0;i < 25;i++) {
      if (C.equals(alphabet[i])) {
        System.out.println(alphabet[i + 1]);
        return;
      }
    }
  }
}

Measured memory_bytes: 21588
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 100001
int n;
int prime[MAX];
int cnt[MAX]={};
void eratos() {
	for (int i=0;i<MAX;i++) {
	//全部primeと設定する
	prime[i] = 1;
	}
	prime[0] = prime[1] = 0;

	for (int i=2;i<MAX;i++) {
	for (int j=i+i;j<MAX;j+=i) {
	if (prime[j]) prime[j] = 0;
	}
	}
}

void like() {
	for (int i=3;i<MAX;i++) {
	if (i%2 == 1) {	
	if (prime[i] && prime[(i+1)/2]) {
	++cnt[i];
	}
	}
	cnt[i] += cnt[i-1];
	}
	
}



int main() {
	int q;
	int l,r;
	cin >> q;
	eratos();
	like();
	for (int i=0;i<q;i++) {
	scanf("%d %d", &l, &r);
	printf("%d\n", cnt[r]-cnt[l-1]);
	}

/*	for (int i=0;i<=11;i++) {
	cout << "p "<<prime[i] << endl;
	cout << "c "<<cnt[i] << endl;
	}
*/
	return 0;
}


Measured memory_bytes: 1408
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=int(input())
    YesNo(N%500<=A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
n = int(input())
a = list(map(int,input().split()))
k = 0

for i in range(n):
    if a[i]%2 == 0:
        if a[i]%3 != 0 and a[i]%5 != 0:
            k += 1
        else:
            continue
    else:
        continue

if k == 0:
    print("APPROVED")
else:
  print("DENIED")

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

int infty = (1 << 21);
int cost[100][100];
int mincost[100];
bool used[100];
int V;

int prim() {
	for (int i = 0; i < V; ++i) {
		mincost[i] = infty;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;

	while (1) {
		int v = -1;
		for (int u = 0; u < V; u++) {
			if (!used[u] && (v == -1 || mincost[u] < mincost[v])) {
				v = u;
			}
		}
		if (v == -1)break;
		used[v] = true;
		res += mincost[v];

		for (int u = 0; u < V; u++) {
			mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	return res;
}


int main() {
	cin >> V;
	rep(i, 0, V)rep(j, 0, V) {
		int e; cin >> e;
		cost[i][j] = (e == -1) ? infty : e;
	}

	cout << prim() << endl;
}


Measured memory_bytes: 3120
import math


def primes(x):
    x+=1
    if x < 2:
        return []

    prime = [i for i in range(x)]
    prime[1] = 0

    for p in prime:
        if p > math.sqrt(x):
            break
        if p == 0:
            continue
        for non_prime in range(2 * p, x, p):
            prime[non_prime] = 0

    return [p for p in prime if p != 0]


def over(l, x):
    ans = 0
    for i in range(len(l)):
        if l[i] >= x:
            ans += 1
    return ans


def combinations_count(n, r):
    return math.factorial(n)//(math.factorial(n-r) * math.factorial(r))


n = int(input())


p = primes(n)
r = [1 for i in range(len(p))]

for i in range(n):
    j = 0
    k = i+1
    while k!=1:
        while k%p[j]==0:
            r[j]+=1
            k//=p[j]
        j+=1

ans = 0

ans += over(r,75)

for i in range(len(r)):
    if r[i]>=25:
        ans += over(r,3)-1
    if r[i]>=15:
        ans += over(r,5)-1

o5 = over(r,5)
o3 = over(r,3)
if o5>=2 and o3>=3:
        ans += combinations_count(o5,2) * combinations_count(o3-2,1)

print(ans)




Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
     
int main() {
  int A, B;
  cin >> A >> B;
  
  bool answer = false;
  
  for(int i = 0; i < 10000 ; i++){
    if(i * 8 / 100 == A && i / 10 == B){
      cout << i << endl;
      answer = true;
      break;
    }
  }
  
  if(answer == false){
    cout << -1 << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

char keypad[10][8] = {{' ',' ',' ',' ',' ',' ',' ',' '},
                      {'\'', ',', '.', '!', '?'},
                      {'a','b','c','A','B','C'},
                      {'d','e','f','D','E','F'},
                      {'g','h','i','G','H','I'},
                      {'j','k','l','J','K','L'},
                      {'m','n','o','M','N','O'},
                      {'p','q','r','s','P','Q', 'R', 'S'},
                      {'t','u','v','T','U','V'},
                      {'w','x','y','z','W','X', 'Y', 'Z'}};

int main()
{
  string s;

  while (cin >> s)
  {
    int p=0;
    while (p<s.size())
    {
      char key = s[p];
      p++;
      int r=0;
      while (key == s[p])
      {
        r++;
        p++;
      }
      if (key == '0')
      {
        for (int i=0;i<r;i++) cout << ' ';
      }
      else
      {
        cout << keypad[key-'0'][r]; // ???????????????
      }
    }
    cout << endl;
  }
  return 0;
}

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

#ifdef _LOCAL_DEBUG
#include "templates/debug.h"
#else
#define debug(...) 
#endif

ll encode(int x, int y) {
    return (ll)x * 1'000'000'000LL + y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, b;
    cin >> n >> m >> b;
    vector<int> r(n), c(m);
    unordered_set<ll> bombs;
    for (int i = 0; i < b; i++) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        bombs.insert(encode(x, y));
        r[x]++;
        c[y]++;
    }
    int maxr = *max_element(r.begin(), r.end());
    int maxc = *max_element(c.begin(), c.end());
    vector<int> cr, cc;
    for (int i = 0; i < n; i++)
        if (r[i] == maxr)
            cr.push_back(i);
    for (int i = 0; i < m; i++)
        if (c[i] == maxc)
            cc.push_back(i);
    bool f = 1;
    for (int x : cr) {
        for (int y : cc) {
            if (!bombs.count(encode(x, y))) {
                f = 0;
                break;
            }
        }
        if (!f) break;
    }
    cout << maxr + maxc - f << '\n';
    return 0;
}

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

// ll m;
// ll g(ll a){
//     return m%a;
// }

// ll f(vector<ll> A){
//     ll ans;
//     for(ll x : A){
//         ans+=g(x);
//     }
// }

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

Measured memory_bytes: 256
let () =
  let rec get_data l = function
      0 -> l
    | i -> get_data (read_int()::l) (i-1)
  in
  let all i l = List.for_all (fun x -> x=i) l and
      ex i l = List.exists (fun x -> x=i) l
  in
  let rec read () =
    let n = read_int () in
    if n = 0 then ()
    else
      begin
        let l = n::((get_data [] 4) |> List.rev) in
        let a = Array.of_list l in
        if (all 1 l) || (all 2 l) || (all 3 l) then
          for i = 0 to 4 do
            print_endline "3"
          done
        else if (ex 1 l) && (ex 2 l) &&  (ex 3 l) then
          for i = 0 to 4 do
            print_endline "3"
          done
        else if (ex 1 l) && (ex 2 l) then
          Array.iter (fun x -> print_endline (if x = 1 then "1" else "2")) a
        else if (ex 1 l) && (ex 3 l) then
          Array.iter (fun x -> print_endline (if x = 3 then "1" else "2")) a
        else if (ex 2 l) && (ex 3 l) then
          Array.iter (fun x -> print_endline (if x = 2 then "1" else "2")) a
        ;read ()
      end
  in read ()
;;

Measured memory_bytes: 2132
#include <stdio.h>

int main(void)
{
	int H = 0, W = 0, i, j;

	while(1)
	{
		scanf("%d %d", &H, &W);

		if (H == 0 && W == 0) break;

		for (i = 0; i < H; i++)
		{
			int flg = 0;
			if (i % 2 == 0)
			{
				for (j = 0; j < W; j++)
				{
					if (flg == 0)
					{
						printf("#");
						flg = 1;
					}
					else
					{
						printf(".");
						flg = 0;
					}
				}
			}
			else
			{
				for (j = 0; j < W; j++)
				{
					if (flg == 0)
					{
						printf(".");
						flg = 1;
					}
					else
					{
						printf("#");
						flg = 0;
					}
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

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

typedef long long ll;

int memo(string N, string x) {

    int r = 0;

    int a = 0, b = 0, c = 0;

    if(atoi(x.c_str()) > atoi(N.c_str())) return 0;

    for(int i = 0; i < x.length(); i++) {
        if(x[i] == '3') {
            a++;
        } else if(x[i] == '5') {
            b++;
        } else if(x[i] == '7') {
            c++;
        }
    }

    if(a > 0 && b > 0 && c > 0) {
        r++;
    }

    if(N.length() == x.length()) return r;

    r += memo(N, x + '3');
    r += memo(N, x + '5');
    r += memo(N, x + '7');

    return r;
}

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

    string N;
    cin >> N;

    int ans = 0;
    ans += memo(N, "3");
    ans += memo(N, "5");
    ans += memo(N, "7");

    cout << ans << endl;
}

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

using namespace std;
const double PI = 3.14159265358979323846;

const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    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 pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};


struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} c(2000005);




int main()
{
    ll N;


    cin >> N;

    if(N==1){
        cout << 0 << endl;
        return 0;
    }


    mint ans=0;


    for(ll i=2;i<=N;i++){

        ans = ans+ c(N,i)*mint(8).pow(N-i)*(mint(2).pow(i)-2);

    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 34212
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	int n;cin >> n;
	
	vector<int> v;
	
	REP(i,n)
	{
		int tmp;cin >> tmp;
		
		v.PB(tmp);
	}
	v.PB(1000000009);
	
	sort(ALL(v));
	
	int ans = 0;
	int now = -1;
	int cou = 0;
	REP(i,n+1)
	{
		if(now != v[i])
		{
			if(now > cou)ans += cou;
			now = v[i];
			cou = 1;
		}
		else
		{
			cou++;
		}
//		cout << now << ' ' << cou << endl;
		if(cou > now)ans++;
	}
	
	cout << ans << endl;
			
		
	
	return 0;
}

Measured memory_bytes: 1020
class Integer
    def digit_sums
        x, sum = self, 0
        
        while x > 0 do
            x, r = x.divmod(10)
            sum += r
        end
        
        sum
    end
end

N = gets.to_i
puts N % N.digit_sums == 0 ? "Yes" : "No"

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

int main() {
	
	int n;
	cin >> n;
	double ans = 0.0;
	
	rep(i, n){
		double u;
		string s;
		cin >> u >> s;
		if(s == "JPY") ans += u;
		else ans += u * 380000.0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
require 'matrix'

def exp(n, k, mod = nil)
	x = 1	
	r = n
	while k > 0
		x *= r if k & 1 == 1
		r *= r		
		if mod
			x %= mod
			r %= mod
		end
		k >>= 1
	end
	x
end

class Matrix
	def %(mod)
		map{|x| x % mod}
	end
end

loop {
	n, m, a, b, c, t = gets.split.map &:to_i 
	break if n == 0
	states = Vector[*gets.split.map(&:to_i)]
	mat = Matrix.build(n, n){|i, j|
		j == i-1 ? a :
		j == i   ? b :
		j == i+1 ? c : 0
	}
	puts (exp(mat, t, m) * states).to_a.map{|x| x % m}.join(" ")
}

Measured memory_bytes: 9876
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    string s;
    cin >> s;
    if (s == "SUN") cout << 7 << endl;
    else if (s == "MON") cout << 6 << endl;
    else if (s == "TUE") cout << 5 << endl;
    else if (s == "WED") cout << 4 << endl;
    else if (s == "THU") cout << 3 << endl;
    else if (s == "FRI") cout << 2 << endl;
    else if (s == "SAT") cout << 1 << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
from bisect import bisect
n,m=map(int,input().split())
l=[tuple(map(int,input().split())) for _ in range(m)]
a=defaultdict(list)
for x,y in sorted(l):
    a[x]+=[y]

for x,y in l:
    z=bisect(a[x],y)
    print('%06d%06d'%(x,z))

Measured memory_bytes: 39992
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int Maxn=200000;
typedef long long ll;
int n,k;
int h[Maxn+5];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
	}
	sort(h+1,h+1+n);
	ll ans=0;
	for(int i=1;i<=n-k;i++){
		ans+=h[i];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdlib>
#include <cmath>

using namespace std;

int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(s.at(i)==',')  s.at(i)=' ';
  }
  cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/

/+---test
4 3
---+/

void main(string[] args) {
  long a, b;
  readf(" %d %d ", &a, &b);

  foreach (i; 0..max(a, b)) min(a, b).to!string.write;
  writeln;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX_N = 16;
const int INF   = 1 << 25;

int N, T[MAX_N][MAX_N + 1];
int dp[1 << (MAX_N + 1)];

void solve()
{
  memset(dp, INF, sizeof(dp));
  dp[0] = 0;
  for (int S = 1; S < (1 << N); S++) {
    dp[S] = INF;
    for (int i = 0; i < N; i++) {
      if ((S >> i) & 1) {
        int pS = S & ~(1 << i);
        dp[S] = min(dp[S], dp[pS] + T[i][0]);
        for (int j = 0; j < N; j++) {
          if (((pS >> j) & 1) && (i != j)) {
            dp[S] = min(dp[S], dp[pS] + T[i][j + 1]);
          }
        }
      }
    }
  }

  cout << dp[(1 << N) - 1] << endl;
}

int main()
{
  while (cin >> N && N) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j <= N; j++)
        cin >> T[i][j];

    solve();
  }
}

Measured memory_bytes: 1380
use std::io::{stdin, Read};

fn main() {
    let v = get_param();
    println!("{}", solve(v[0], v[1], v[2], v[3]));
}

fn get_param() -> Vec<i32> {
    let mut s = String::new();
    stdin().read_to_string(&mut s).ok();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}

fn solve(a: i32, b: i32, c: i32, x: i32) -> usize {
    pairs(a, b, c)
        .iter()
        .filter(|p| exact(p.0, p.1, p.2, x))
        .count()
}

fn pairs(a: i32, b: i32, c: i32) -> Vec<(i32, i32, i32)> {
    (0..a + 1)
        .flat_map(move |a| (0..b + 1).flat_map(move |b| (0..c + 1).map(move |c| (a, b, c))))
        .collect()
}

fn exact(a: i32, b: i32, c: i32, x: i32) -> bool {
    500 * a + 100 * b + 50 * c == x
}


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


int main(){
int N,count,Answer1,memory;
count=0;
Answer1=0;
scanf("%d",&N );
int a[N];
for (int i = 0; i < N; i++) {
  scanf("%d",&a[i] );
}




for (int i = 0; i < N; i++) {

count=0;
  for (int j = 0; j <100; j++) {

    if(a[i]%2==0){
      count++;
      a[i]=a[i]/2;
    }
  else  if(a[i]%2!=0||a[i]==1)break;
  }

Answer1+=count;

}

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




return 0;


}

Measured memory_bytes: 256
const main = (input) => {
  const lines = input.trim().split("\n")
  const [N, K] = lines[0].split(" ").map(str => parseInt(str))
  let H = lines[1].split(" ").map(str => parseInt(str))
  H.sort((a, b) => a - b).reverse()
  H = H.slice(K)
  const sum = (arr) => arr.reduce((a , b) => a + b, 0)
  console.log(sum(H))
}

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


Measured memory_bytes: 37444
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 100000000000000

int main(){
	int n;cin>>n;
	vector<int> c(n-1),s(n-1),f(n-1);
	for(int i=0;i<n-1;i++){
		cin>>c[i]>>s[i]>>f[i];
	}

	vector<int> ans(n,0);
	for(int i=0;i<n;i++){
		ans[i]=s[i]+c[i];//とりあえず次の駅へ行くまでの時間を入れる
	}

	for(int i=0;i<n-2;i++){//i駅について
		for(int j=i+1;j<n-1;j++){
			ans[i]=s[j]+max(0,(ans[i]-s[j]+f[j]-1)/f[j])*f[j];//s[次の駅]が到着時間より遅ければ、ans=s[次の駅]  //　そうでなければ、できるだけ早い電車に乗る
			ans[i]+=c[j];//次の駅へ行く所要時間
		}
	}

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

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

#define rep(i,n) for(int i = 0;i<n;i++)
#define vv(Type,Name, n,m,d)vector<vector<Type>> Name(n, vector<Type>(m, d))
#define P pair<long double,int>
using namespace std;
using ll = long long;
using T = tuple<long double, int, int>;

int main(void) {



	int n; cin >> n;
	int k; cin >> k;
	
	vector<int> a(n);
	int m = 0;
	rep(i, n) {
		cin >>a[i];
		m = max(m, a[i]);
	}
	
	
	
	
	int l = 0;
	int r = m;

	while (r-l > 1){

		int c = (r + l) / 2;

		int tmp = 0;
		rep(i, n) {
			tmp += a[i] / c;
			if (a[i] % c == 0) tmp--;
			
			if (tmp > k) break;

		}

		if (tmp > k) l = c;
		else r = c;
	}

	int tmp = 0;
	rep(i, n) {
		tmp += a[i] / r;
		if (a[i] % r == 0) tmp--;
	}

	/*if (tmp <= k) cout << r << endl;
	else cout << l << endl;*/

	cout << r << endl;
	



	return 0;
}


Measured memory_bytes: 3972
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

string s;

int main(){
	//IO("input.txt", "output.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	sort(s.begin(), s.end());
	if(s[0] == s[1] && s[2] == s[3] && s[0] != s[2]) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int sum1=0,sum2=0;
    for(int i=0;i<s.size();i++)
        if(s[i]=='A')   sum1++;
    else    sum2++;
    if(sum1&&sum2)  cout<<"Yes";
    else    cout<<"No";
}


Measured memory_bytes: 256
X, Y, Z, K = map(int, input().split())

A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

ANS = []

# x * y * z <= K のはず
for x in range(X):
  for y in range(Y):
    if (x*y >= K): break
    for z in range(Z):
      if (x*y*z >= K): break
      ANS.append(A[x]+B[y]+C[z])

for ans in sorted(ANS, reverse=True)[:K]:
  print(ans)

Measured memory_bytes: 130820
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <fstream>
#include <map>
#include <cassert>
#include <sstream>
#include <numeric>
#include <regex>
#include <cctype>
#include <utility>
#include <stdio.h>
#include <set>
#include <queue>
#include <deque>

typedef long long ll;

#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define MOD 1000000007
#define pb push_back
#define llnums vector<ll>
#define FOR(i,n) for(int i{0}; i < n; ++i)

using namespace std;

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  vi num(11, 0);
  for (int i=0; i < 3; i++) {
      int x;
      cin >> x;
      num[x]++;
  }
  if (num[5] == 2 && num[7] == 1) {
      cout << "YES\n";
  }
  else {
      cout << "NO\n";
  }
  return 0;
}









Measured memory_bytes: 3600
#include <iostream>
#include <iomanip>
#include <climits>
#include <string>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = pair<ii, int>;
#define vt vector
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1e9 + 7;
const int INF = INT_MAX;
// const int N = ;

int cnt, ans;
string s;

void solve() {
    cin >> s;
    for(char c : s) {
        if(c == 'R') cnt++;
        else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    if(cnt) ans = max(ans, cnt);
    cout << ans << "\n";
}

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

Measured memory_bytes: 3624
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
#define LL long long
char s[1010][1010];
int main(){
	int n,m,a,b;
	scanf("%d%d%d%d",&n,&m,&a,&b);
	for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)s[i][j]='.';
	if(m&1)for(int i=1 ;b && i<n; i+=2){
		s[i][m]='^';s[i+1][m]='v';
		b--;
	}
    if((b&1)&&(n&1)&&m>2&&n>1){ 
        s[n-1][m-2]='^';s[n][m-2]='v';
		b--;
    } 
	for(int i=1;i<n;i++){
        for (int j=1;j<=m-(m&1) && b;j++){
            if(s[i][j]=='.'&&s[i+1][j]=='.'){
                s[i][j]='^';s[i+1][j]='v';
				b--;	
			}
        }
	}
    for(int i=1;i<=n;i++){
        for(int j=1;j<m&&a;j++){
            if(s[i][j]=='.'&&s[i][j+1]=='.'){
            	s[i][j]='<';s[i][j+1]='>';
				a--;
			}
    	}
	}
	if(a||b)
        puts("NO");
    else
    {
        puts("YES");
        for(int i=1;i<=n;i++)printf("%s\n",s[i]+1);
    }
}

Measured memory_bytes: 2176
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

print(*ans)


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

// A_i < B_j < C_kをみたす(i, j, k)の組を数える
// B_j(つまりj)を固定すれば，
// A_i < B_jを満たすiの個数とB_j < C_kを満たすkの個数の積
// これを全てのjに対して和を取る

using ll = long long;

int main() {
    ll N; cin >> N;
    vector<ll> A(N, 0), B(N, 0), C(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    for (int i = 0; i < N; i++) {
        cin >> B.at(i);
    }
    for (int i = 0; i < N; i++) {
        cin >> C.at(i);
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    ll ans = 0;
    for (int j = 0; j < N; j++) {
        ll ai = lower_bound(A.begin(), A.end(), B.at(j)) - A.begin();
        ll ck = C.end() - upper_bound(C.begin(), C.end(), B.at(j));
        ans += ai*ck;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cerr << #x " = " << (x) << endl;
#define P(x) cerr << #x << endl;    
#define int long long
typedef pair<int, int> pii;
const int mod = 1000000007;


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(9);
    
    
    int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt = 1;
	for(int i = 1; i < n; ++ i)
	{
		if(s[i] != s[i - 1]) 
		{
			
			++ cnt;
		}
	}
	cout << cnt << '\n';
    
    return 0;
}






Measured memory_bytes: 512
n = gets.chomp.to_i
a = [[0, 0, 0], [0, 0, 0]]
n.times do
  a << gets.chomp.split.map(&:to_i)
end

dp = Array.new(n + 2).map{Array.new(3, 0)}

for i in 1..n
  for j in 0..2
    for k in 0..2
      dp[i+1][k] = [dp[i+1][k], dp[i][j] + a[i+1][k]].max if j != k
    end
  end
end

puts dp.last.max


Measured memory_bytes: 16892