akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
"""
http://abc061.contest.atcoder.jp/tasks/abc061_a

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    A, B, C = map(int, input().split())
    if A <= C <= B:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main(sys.argv[1:])
    


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAX = 100000;

int main()
{
	int n;
	int a[MAX] = {0};
	int count[MAX] = {0};

	scanf("%d", &n);

	int max = 0;

	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		count[a[i]]++;

		if (max < a[i])
		{
			max = a[i];
		}
	}

	int sum = 0;

	for(int i = 0; i <= max; i++)
	{
		if (count[i] > 1)
		{
			sum += count[i] - 1;
		}
	}

	if (sum % 2 ==0)
	{
		printf("%d\n", n - sum);
	}else
	{
		printf("%d\n", n - sum - 1);
	}

	return 0;
}
	

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n % 1000 == 0 ? 0 : 1000 - n % 1000);
    }

}


Measured memory_bytes: 35788
//============================================================================
// Name        : ATcoder.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {


	string str = "abcdefghijklmnopqrstuvwsyz";

	string str2;
	int flg=0;
	int t=0;
	cin>>str2;

	for(int i=0; i<26; i++){
		flg=0;
		for(int j=0; j<str2.size(); j++){
			if(str2[j]==str[i]){
				flg+=1;
			}
		}
		if(flg>1){
			t+=1;
		}
	}

	if(t>0){
		cout<<"no"<<endl;

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

	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

int main(void){


int n;


int x;


int num;


int min=1000001;


int max=-1000001;


long total=0;


scanf("%d",&n);


for(x=0;x<n;x++){


scanf("%d",&num);


if(min>num)min=num;


if(max<num)max=num;


total+=num;


}


printf("%d %d %ld\n",min,max,total);


return (0);


}

Measured memory_bytes: 600
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <assert.h>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
using namespace std;

// #define __DEBUG__

#ifdef __DEBUG__
bool debug_disabled = false;
#else
bool debug_disabled = true;
#endif

#define dbg if (debug_disabled) {} else cerr

void solve() {
    long long A, B, N;
    cin >> A >> B >> N;
    if (N <= B - 1) {
        cout << (A * N) / B << endl;
    } else {
        cout << (A * (B - 1)) / B << endl;
    }
}

int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.setf(ios::showpoint);
    cout.precision(12);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
typedef pair<int, int> pii;

int main(){
	while(true){
		int N;
		cin >> N;
		if(N == 0){ break; }
		vector<pii> guys(N);
		for(int i = 0; i < N; ++i){
			int M, L, mask = 0;
			cin >> M >> L;
			for(int j = 0; j < M; ++j){
				int S, E;
				cin >> S >> E;
				S -= 6; E -= 6;
				mask |= ((1 << E) - 1) ^ ((1 << S) - 1);
			}
			guys[i] = pii(mask, L);
		}
		vector<int> dp(1 << (22 - 6));
		int answer = 0;
		for(int i = 0; i < dp.size(); ++i){
			answer = max(answer, dp[i]);
			for(int j = 0; j < N; ++j){
				int mask = guys[j].first;
				if(i & mask){ continue; }
				dp[i | mask] = max(dp[i | mask], dp[i] + guys[j].second);
			}
		}
		cout << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n , k;
string s , t;
int main(){
    cin >> n >> k;
    cin >> s;
    int i = 0 , j = 1 , ans = 1 , cost = 0;
    cost += (s[0] == '0');
    while(j < n){
        if(s[j] == '0' && s[j] != s[j - 1])
            cost++;
        while(cost > k){
            if(s[i] == '0'){
               cost--;
               while(s[i] == '0')i++;
               break;
            }
            i++;
        }
        ans = max(ans , j - i + 1);
        j++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int arr[N];
int main(){
	int sum=0;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)
			sum+=arr[i]*arr[j]; 
	}
	cout<<sum<<endl;
	return 0;
} 

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
int main(void){
  char a[11], b[11], c[11];
  int am, bm, cm;
  
  scanf("%s", a);
  scanf("%s", b);
  scanf("%s", c);
  
  am = strlen(a);
  bm = strlen(b);
  cm = strlen(c);
  
  if(a[am - 1] == b[0] && b[bm - 1] == c[0]) {
    printf("YES");
  }
  else {
    printf("NO");
  }
  return 0;
}

Measured memory_bytes: 128
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("-ffloat-store")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef vector <int> vi;
typedef pair< int ,int > pii;
#define endl "\n"
#define f(i,a,b) for(int i=a;i<b;i++)
#define debug(val) printf("check%d\n",val)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define mod 1000000007
#define inf  1e18
#define ps(x,y)   fixed<<setprecision(y)<<x
#define clr(val) memset(val,0,sizeof(val))
#define what_is(x) cerr << #x << " is " << x << endl;
#define inp(a,n) for(int i=0;i<n;i++) cin>>a[i];
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main() 
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
    #endif
    FIO;
    // int t;
    // cin>>t;
    // while(t--)
    //{
        // ll n;   
        // cin>>n;
         ll sum=0;
        // while(n)
        // {
        //     sum+=n%10;
        //     n=n/10;
        // }
        // if(sum%9==0)
        // cout<<"Yes";
        // else
        // {
        //     cout<<"No";
        // }
        string s;
        cin>>s;
        for(auto c:s)
        {
            sum+=int(c) - '0';
        }
        if(sum%9==0)
        cout<<"Yes";
        else 
        cout<<"No";
    // }
return 0;   
}

Measured memory_bytes: 3772
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<double>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int main(){
    int a;
    while(cin>>a){
        vi range; range.push_back(a);
        ll sum=0; sum+=a;
        rep(i,10){if(i){int gotiusa; cin>>gotiusa; range.push_back(gotiusa);sum+=gotiusa;}char gomi; cin>>gomi;}
        double v; cin>>v; v/=10; char gomi; cin>>gomi;
        double u; cin>>u; u/=10;
        double tiya=u,rize=v;
        bool touch=false;
        for(int i=0;;i++){
            if(v+u-(double)sum>=0)touch=true;
            if(touch)break;
            v+=rize;u+=tiya;
        }
        rep(i,range.size()){
            v-=range[i];
            if(v<=0){cout<<i+1<<endl; break;}
        }
    }
}

Measured memory_bytes: 3124
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>
#include <stack>
 
using namespace std;
 
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)



int main() {
    ll a,b;
    cin >> a >> b;
    ll ans=-1;
    for(ll i=1;i<100000;i++){
        if(floor(i*0.08)==a && floor(i*0.1)==b) {
            ans=i;
            break;
        }
    }
    cout << ans << endl;
}



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

using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;

#define all(a) a.begin(), a.end()
#define mp make_pair
#define pb push_back

void solve() {
    int l, r, d;
    cin >> l >> r >> d;
    int res = 0;
    for (int i = l; i <= r; i++) {
        if (l <= i && i <= r && i % d == 0) res++;
    }
    cout << res;
}

int main() {
    solve();
}

Measured memory_bytes: 3648
/*
 * author :Sadik Hassan
 *
*/
#include "bits/stdc++.h"
using namespace std;
using   ll =          long long;
#define nl            "\n"
#define pb            push_back
#define fi            first
#define se            second
#define PI            (acos(-1.0))
#define repp(i,a,n)   for(int i=a;i<n;i++)
#define rep(i,n)      for(int i=0;i<n;i++)
#define SZ(s)         s.size()
#define SRT(x,y)      sort(x,x+y)
#define REV(a,b)      reverse(a,a+b)
#define VSRT(x)       sort(x.begin(),x.end())
#define VREV(x)       reverse(x.begin(),x.end())
#define w(t)          int t;cin>>t;while(t--)
#define TSFL(s)       transform(s.begin(),s.end(),s.begin(),::toupper);
#define TSFH(s)       transform(s.begin(),s.end(),s.begin(),::tolower);
#define _SAD()        ios::sync_with_stdio(0),cin.tie(0), cout.tie(0),cout<<fixed<<setprecision(15);
typedef vector<int> vi;
typedef vector<ll> vii;
typedef set<int> si;
typedef set<ll> sii;
/*---------------------------------------------------------------------*/

const int N = 2e5+10;
const int INF = (int)1e9+5;

int main()
{
    _SAD()
    int h1,m1,h2,m2,k;
    cin>>h1>>m1>>h2>>m2>>k;
    int cnt=0;
    while(1)
    {
        if(h1==h2&&m2==m1)break;
        m1++;
        cnt++;
        if(m1==60)
        {
            m1=0;
            h1++;
        }
    }
    cout<<max(0,cnt-k)<<nl;
    return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  lint n; cin >> n;
  V<lint> a(5); for (auto&& e : a) cin >> e;
  lint mx = 0;
  for (int i = 0; i < 5; ++i) {
    mx = max(mx, (n + a[i] - 1) / a[i] - 1);
  }
  lint res = mx + 5;
  cout << res << '\n';
}

Measured memory_bytes: 256
using System;
using System.Linq;

class E
{
	static void Main()
	{
		var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
		int n = h[0], k = h[1];
		Console.WriteLine(Totients(k).Select((x, i) => i == 0 ? 0 : x * MPow(k / i, n)).Sum() % M);
	}

	static int[] Totients(int n)
	{
		var b = new bool[n + 1];
		for (int p = 2; p * p <= n; ++p) if (!b[p]) for (int x = p * p; x <= n; x += p) b[x] = true;
		var r = new int[n + 1];
		for (int x = 1; x <= n; ++x) r[x] = x;
		for (int p = 2; p <= n; ++p) if (!b[p]) for (int x = p; x <= n; x += p) r[x] = r[x] / p * (p - 1);
		return r;
	}

	const int M = 1000000007;
	static long MPow(long b, int i)
	{
		for (var r = 1L; ; b = b * b % M)
		{
			if (i % 2 > 0) r = r * b % M;
			if ((i /= 2) < 1) return r;
		}
	}
}


Measured memory_bytes: 28640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  ll n;
  cin >> n;
  vector<ll> a(n),b(n);
  rep(i,n){
    cin >> a.at(i);
  }
  b=a;
  sort(b.begin(),b.end());
  ll p,q;
  p=b.at(n/2-1),q=b.at(n/2);
  rep(i,n){
    if(p>=a.at(i)){
      cout << q << endl;
    }else{
      cout << p << endl;
    }
  }
}

Measured memory_bytes: 6284
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
 
int main() {
	int n;
	cin >> n;
	int a[1081];
	rep1(i,n) cin >> a[i];
	a[n+1]=0;
 
	long long int money=1000;
	long long int kabu=0;
 
	rep1(i,n){
		if(a[i+1]>a[i]){
			kabu = kabu + money / a[i];
			money = money - (money/a[i])*a[i];
		}
		if(a[i+1] < a[i]){
			money = money + kabu*a[i];
			kabu=0;
		}
	}
 
	cout << money << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const int MOD = 1e9 + 7;
using namespace std;
typedef long long ll;

map<ll, int> mp;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a, b, k;
	cin >> a >> b >> k;
	for (int i = 0; i < k; i++) {
		if (i % 2 == 0) {
			if (a % 2 == 1) a--;
			b += a / 2;
			a /= 2;
		}
		else {
			if (b % 2 == 1) b--;
			a += b / 2;
			b /= 2;
		}
	}
	cout << a << " " << b << endl;
	return 0;
}

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

int main()
{
	std::string str[3];
	int cnt=0,cnt1=0;
	int n, m;
	std::string str1[1000];
	int num[1000];
	double sum = 0;
	double re;


	for (int i = 0; i < 2; i++) {
		std::cin >> str[i];
	}

	n = stoi(str[0]);
	m = stoi(str[1]);
	
	for (int i = 0; i < n; i++) {
		std::cin >> str1[i];
		num[i] = stoi(str1[i]);
		sum += num[i];
	}
	
	re = (double)sum / (4 * m);
	

	for (int i = 0; i < n; i++) {
		if (re <= num[i]) {
			cnt1++;
		}
	}

	
	if (cnt1>=m) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;

}



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

int main() {
    int n;
    cin >> n;
    int64_t a[n];
    rep(i,n) cin >> a[i];
    sort(a, a+n);
    int64_t suma[n+1];
    suma[0] = 0;
    rep(i,n) suma[i+1] = suma[i] + a[i];
    int ans = 1;
    rep(i,n-1) {
        if (2*suma[n-i-1] >= a[n-i-1]) ans++;
        else break;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int N, A, B, C, D; cin >> N >> A >> B >> C >> D;
	A--; B--; C--; D--;

	char S[200004]; cin >> S;

	if (D < C) {//入れ替えが必要な場合
		bool flag = false;
		for (int i = B; i <= D; i++) {
			if (S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.') {
				flag = true;
				break;
			}
		}
		if (flag == false) {
			cout << "No" << endl;
			return 0;
		}
	}

	{
		bool* dp = new bool[N];
		for (int i = 0; i < N; i++) {
			dp[i] = false;
		}
		dp[B] = true;
		dp[B + 1] = (S[B + 1] == '.');

		for (int i = B + 2; i <= D; i++) {
			if (S[i] == '.') {
				dp[i] = dp[i - 2] | dp[i - 1];
			}
		}
		if (dp[D] == false) {
			cout << "No" << endl;
			return 0;
		}
	}

	{
		bool* dp = new bool[N];
		for (int i = 0; i < N; i++) {
			dp[i] = false;
		}
		dp[A] = true;
		dp[A + 1] = (S[A + 1] == '.');

		for (int i = A + 2; i <= C; i++) {
			if (S[i] == '.') {
				dp[i] = dp[i - 2] | dp[i - 1];
			}
		}
		if (dp[C] == false) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 768
# 高橋君と青木君がモンスターを闘わせます。
# 高橋君体力  A  攻撃力  B  です。
# 青木君体力  C  攻撃力  D  です。
# 高橋君→青木君→高橋君→青木君→... の順に攻撃を行います。
# このことをどちらかのモンスターの体力が  0  以下になるまで続けたとき、
# 先に自分のモンスターの体力が  0  以下になった方の負け、そうでない方の勝ちです。
# 高橋君が勝つなら Yes、負けるなら No を出力してくださ

a, b, c, d = list(map(int, input(). split()))#10 9 10 10

while True:
    c -= b
    if c  <= 0:
        print("Yes")
        break
    a -= d
    if a <= 0:
        print("No")
        break




Measured memory_bytes: 9164
import sys
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
p=[]
m=[]
for i,j in zip(a,b):
    k=i-j
    if k < 0:
        m.append(k)
    else:
        p.append(k)
if sum(p)+sum(m) < 0:
    print(-1)
    sys.exit()
p.sort(reverse=True)
ans=0
P=0
M=abs(sum(m))

for i in range(n):
    if P >= M:
        print(ans+len(m))
        sys.exit()
    P+=p[i]
    ans+=1



Measured memory_bytes: 19060
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b;
    cin >>a >>b;
    if(a<b){
        cout << "a < b" << endl;
    }
    else if(a>b){
        cout << "a > b" << endl;
    }
    else{
        cout << "a == b" << endl;
    }
}


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

int main(){
	int num[3];
	int odd=0;
	for(int i=0;i<3;i++){
		cin>>num[i];
		if(num[i]%2) odd++;
	}
	int ans=0;
	if(odd==2){
		ans=1;
		for(int i=0;i<3;i++){
			if(num[i]%2) num[i]++;
		}
	}else if(odd==1){
		ans=1;
		for(int i=0;i<3;i++){
			if(num[i]%2==0) num[i]++;
		}
	}

	int M=max(num[0], max(num[1], num[2]));
	for(int i=0;i<3;i++){
		ans+=(M-num[i])/2;
	}

	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007

int main(){
   string a,b;
   cin >> a >> b;
   int la=a.length();
   int lb=b.length();
   if(la>lb){
       cout << "GREATER" << endl;
       return 0;
   }
   else if(la<lb){
       cout << "LESS" << endl;
       return 0;
   }
   else {
       for(int i=0;i<la;i++){
           if(a[i]>b[i]){
                cout << "GREATER" << endl;
                return 0;
           }
           else if(a[i]<b[i]){
                cout << "LESS" << endl;
                return 0;
           }
       }
       cout << "EQUAL" << endl;
       return 0;
   }
}

Measured memory_bytes: 256
n = gets.to_i
edge = Array.new(n+1) {[]}

(n-1).times do
    a, b = gets.split.map(&:to_i)
    edge[a] << b
    edge[b] << a
end

c = gets.split.map(&:to_i).sort_by{|e| -e}
m = c.inject(:+) - c[0]

que = [1]
ans = Array.new(n+1)
while now = que.shift
    next if ans[now]
    ans[now] = c.shift
    que += edge[now]
end

puts m, ans[1..-1] * " "

Measured memory_bytes: 74376
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,a,b,l,r,f,u[1111];
vector<int>v[1111];
void dfs(int x,int d){
    u[x]=d;
    if(d)l++;
    else r++;
    r(i,v[x].size()){
        int nx=v[x][i];
        if(u[nx]!=-1){
            if(u[nx]==u[x])f++;
        }
        else{
            dfs(nx,d^1);
        }
    }
}
int main(){
    while(cin>>n>>m,n){
        l=r=f=0;
        r(i,n)v[i].clear();
        r(i,m){
            cin>>a>>b;
            a--;b--;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        memset(u,-1,sizeof(u));
        dfs(0,0);
        if(f)cout<<0<<endl;
        else{
            vector<int>ans;
            if(l%2==0)ans.push_back(l/2);
            if(r%2==0&&l!=r)ans.push_back(r/2);
            sort(ans.begin(),ans.end());
            cout<<ans.size()<<endl;
            r(i,ans.size()){
                cout<<ans[i]<<endl;
            }
        }
    }
}



Measured memory_bytes: 3276
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <cstring>

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))

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

using namespace std;

const int INF = 1e9;

int main(){
    int n;

    while(cin >> n && n){

        vector< vector<int> > stage(n, vector<int>(n+1, 0));

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n+1; j++){
                cin >> stage[i][j];
            }
        }

        vector<int> dp(1 << n, INF);

        dp[0] = 0; //Nothing's selected yet.

        for(int bit = 0; bit < (1 << n); bit++){
            for(int i = 0; i < n; i++){
                if((bit & (1 << i)) == 1) continue; //クリア済み
                int cost = stage[i][0]; //クリアしていないステージ

                for(int j = 0; j < n; j++){
                    if((bit & (1 << j)) == 0) continue; //開放されていない
                    cost = min(stage[i][j+1], cost);
                }
                int now = (bit | (1 << i)); //i番目のステージを選択
                dp[now] = min(dp[now], dp[bit] + cost);
            }
        }
        cout << dp[(1 << n) - 1] << endl;
    }
    return 0;
}


Measured memory_bytes: 3336
//daddy's back in town, back to rolling the damn hash yoooo babeeeeees//
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define int ll
const ll mod = 998244353;
int n, k;
string s;
set<string> ss;

int32_t main(){
	ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin>>s>>k;
	for(int i=0; i<s.size(); i++){
		int cnt=0;
		string cur="";
		while(i+cnt<s.size() && cnt<=k){
			cur+=s[i+cnt];
			ss.insert(cur);
			cnt++;
		}
	}
	auto it=ss.begin();
	int cnt=1;
	while(cnt<k) it++, cnt++;
	cout<<(*it);
}

Measured memory_bytes: 2176
#include <iostream>

using namespace std;

int main(void) {
	int area, i, X_LOW, X_HIGH, Y_LOW, Y_HIGH;
	int W, H, N;
	int x, y, a;
	// get input --------------------------------
	cin >> W >> H >> N;
	X_LOW = 0;
	X_HIGH = W;
	Y_LOW = 0;
	Y_HIGH = H;
	for (i = 0; i < N; i++) {
		cin >> x >> y >> a;
		if (a == 1) {
			if (X_LOW < x) {
				X_LOW = x;
			}
		}
		else if (a == 2) {
			if (X_HIGH > x) {
				X_HIGH = x;
			}
		}
		else if (a == 3) {
			if (Y_LOW < y) {
				Y_LOW = y;
			}
		}
		else {
			if (Y_HIGH > y) {
				Y_HIGH = y;
			}
		}
	}
	// calc area ----------------------------------
	if (X_HIGH > X_LOW && Y_HIGH > Y_LOW) {
		area = (X_HIGH - X_LOW) * (Y_HIGH - Y_LOW);
	}
	else {
		area = 0;
	}
	// disp answer --------------------------------
	cout << area << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define PI 3.141592653589
#define MOD 1000000007

using namespace std;

int n;
vector< vector< pair<int, int> > > v;
//pair first=人，second=証言「0,1」

bool judge(int bit){
    //i人目の証言を検証
    REP(i,n){
        if(!(bit & (1<<i))) continue;

        for(pair<int, int> xy : v[i]){
            int x = xy.first; //xが
            int y = xy.second; //親切or不親切

            if(y == 1 && !(bit & (1<<x))){
                //y==1「親切という証言」かつ!(bit & 1<<x)「xは実際には不親切」
                return false;
            }

            if(y == 0 && (bit & (1<<x))){
                return false;
            }
        }
    }
    return true;
}

void solve_C(){
    cin >> n;
    v.resize(n);
    REP(i,n){
        int a;
        cin >> a;
        v[i].resize(a);

        REP(j,a){
            cin >> v[i][j].first >> v[i][j].second;
            v[i][j].first--; //0indexedにする
        }
    }
    

    int ans = 0;
    for(int bit = 0; bit < (1<<n); bit++){
        //このbitについて，生合成が取れているか
        if(judge(bit)){
            //正直者（1の数）を数える
            int ctr = 0;
            REP(i,n){
                if(bit & (1<<i)){
                    ctr++;
                }
            }
            ans = max(ans, ctr);
        }
    }

    cout << ans << endl;
}

int main(void){
    solve_C();
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// spec test

using pll = pair<long long, long long>;
bool cmp(pll a, pll b) {
    return a.second < b.second;
}

int N;
vector<pll> v;

int main() {
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), cmp);

    bool ok = true;
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += v[i].first;
        if (sum > v[i].second) ok = false;
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3328
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]//=2
x=a[0]
for j in range(30):
    if x%2==0:
        x//=2
    else:
        p=j
        break
for i in range(1,n):
    x=a[i]
    for j in range(30):
        if x%2==0:
            x//=2
        else:
            if p!=j:
                print(0)
                exit()
            break
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // gcd(ans, a[i])
    if ans>m:
        print(0)
        exit()
if (m//ans)%2==0:
    print(m//ans//2)
else:
    print(m//ans//2+1)

Measured memory_bytes: 63856
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+7;
struct Node{
    int key;
    Node* parent;
    Node* left;
    Node* right;
};
Node* T;
void insert_num(int z){
    Node* s = (Node*)malloc(sizeof(Node));
    s->key = z;
    s->parent = NULL;
    s->left = NULL;
    s->right = NULL;

    Node* y = NULL; // parent of x
    Node* x = T;
    while(x != NULL){
        y = x; // set the parent
        if(z < x->key){
            x = x->left; // move to the left child
        }else{
            x = x->right; // move to the right child
        }
    }
    s->parent = y;
    if(y == NULL){
        T = s;
    } // T is empty
    else if(z < y->key){
        y->left = s;
    }// z is the left child of y
    else{
        y->right = s;
    }// z is the right child of y
}
void in(Node* T){
    if(T==NULL) return;
    in(T->left);
    printf(" %d", T->key);
    in(T->right);
}
void pre(Node* T){
    if(T==NULL) return;
    printf(" %d", T->key);
    pre(T->left);
    pre(T->right);
}
void print_nums(){
    in(T);
    printf("\n");
    pre(T);
    printf("\n");
}

bool find_num(int num){
    Node* p = T;
    while(p != NULL){
        if(p->key > num){
            p = p->left;
        }else if(p->key < num){
            p = p->right;
        }else{
            return true;
        }
    }
    return false;
}

int main(){
    T = NULL;
    int n;
    scanf("%d", &n);
    char s[10];
    for(int i = 0; i < n; i++){
        scanf("%s", s);
        if(s[0] == 'i'){
            int num;
            scanf("%d", &num);
            insert_num(num);
        } else if(s[0] == 'f'){
            int num;
            scanf("%d", &num);
            bool x = find_num(num);
            if(x == true){
                printf("yes\n");
            }else{
                printf("no\n");
            }
        } else{
            print_nums();
        }

    }
    return 0;
}



Measured memory_bytes: 21896
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=1e5+5;
const int mod=1e9+7;

int n,k,a[N],dp[105][N];
ll rec(int i,int k){
    if(k==0) return 1;
    if(i>n or k<0) return 0;
    int &cache=dp[i][k];
    if(cache!=-1) return cache;
    int mini=min(a[i],k);
    return cache=(rec(i+1,k)-rec(i+1,k-mini-1)+mod+rec(i,k-1))%mod;
}
signed main(){
    FastIO;
    cin>>n>>k;
    rep(i,1,n) cin>>a[i];
    memset(dp,-1,sizeof dp);
    cout<<rec(1,k);
    return 0;
}


Measured memory_bytes: 52452
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    int N;
    string S;
    cin >> N >> S;
    string A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for(auto e:S){
        int n = e-'A';
        cout << A[(n+N)%26];
    }
    cout << endl;
}

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

using namespace std;

typedef long long ll;

ll N, K;
int main(){
int A;
int B;
cin>>A>>B;
if(B%A == 0){
    cout<<A+B<<endl;
}
else {
    cout<<B-A<<endl;
}
  

    return 0;

}



Measured memory_bytes: 256
CACHE = None
A,B,C,D = None,None,None,None

def f(N):
    if N == 1:
        return D

    if N in CACHE:
        return CACHE[N]

    x = None
    if N%2 == 0:
        x = f(N//2) + A
    else:
        N2 = N//2
        x = min(f(N2+1), f(N2)) + A + D

    N3 = N%3
    if N3 == 0:
        x = min(x, f(N//3)+B)
    elif N3 == 1:
        x = min(x, f(N//3)+B+D)
    else:
        x = min(x, f(N//3+1)+B+D)
        
    if N >= 4:
        N5 = N%5
        if N5 == 0:
            x = min(x, f(N//5)+C)
        elif N5 <= 2:
            x = min(x, f(N//5)+C+D*N5)
        else:
            x = min(x, f(N//5+1)+C+D*(5-N5))

    if D <= x/N:
        x = min(x, D*N)
        
    CACHE[N] = x
    return x


T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int, input().split())
    CACHE = {}
    print(f(N))


Measured memory_bytes: 11108
import Control.Applicative
import Control.Monad
import Data.Array
import Data.Array.ST
import Data.List
import qualified Data.Map as M
import qualified Data.Set as S
import Text.Printf

readInts :: IO [Int]
readInts = map read . words <$> getLine

main :: IO ()
main = do
  [m,f,r] <- readInts
  when ((m,f,r) /= (-1,-1,-1)) $ do
    putChar $ solve m f r
    putChar '\n'
    main

solve :: Int -> Int -> Int -> Char
solve (-1) _ _  = 'F'
solve _ (-1) _  = 'F'
solve m f r
  | m + f <  30 = 'F'
  | m + f >= 80 = 'A'
  | m + f >= 65 = 'B'
  | m + f >= 50 = 'C'
  | r >= 50     = 'C'
  | otherwise   = 'D'



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

int main() {
	vector<int>v;
	vector<int>::iterator pv=v.begin();
	int n;
	while (cin>>n) {
		if (n == 0) {
			int x = v.size();
			cout << v[x - 1] << endl;
			v.pop_back();
			continue;
		}
		v.push_back(n);	
	}
	return 0;
}

Measured memory_bytes: 3112
/*
Though leaves are many , the root is one.
Through all the lying days of my youth
I swayed my leaves and flowers in the sun.
Now I may wither into the truth.
	  	  	- William Butler Yeats
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#pragma comment("-Wl,--stack=1024000000")
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=998244353;
typedef long long ll;
#ifndef LOCAL
#define cerr if(0)cout
#define eprintf(...) 0
#else
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#endif
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){int ret=1;do{if(y&1)ret=(ll)ret*x%md;x=(ll)x*x%md;}while(y>>=1);return ret;}
int n;
pair<int,int>p[200005];
int nxt[200005];
struct SGT{
	#define SIZE 262144
	int f[SIZE<<1];
	SGT(){memset(f,0xf7,sizeof f);}
	void set(int x,int v){
		x+=SIZE;f[x]=v;
		while(x>1){
			x>>=1;
			f[x]=max(f[x<<1],f[x<<1|1]);
		}
	}
	int ask(const int &ql,const int &qr,int l=0,int r=SIZE-1,int k=1){
		if(r<ql||qr<l)return -inf;
		if(ql<=l&&r<=qr){
			return f[k];
		}
		return max(ask(ql,qr,l,(l+r)/2,k<<1),ask(ql,qr,(l+r)/2+1,r,k<<1|1));
	}
}T;
int dp[200005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second;
	sort(p+1,p+n+1);
	nxt[n]=n+1;T.set(n,n+1);
	for(int i=n-1;i>=1;i--){
		int L=i,R=n+1;
		while(R-L>1){
			int mid=(L+R)/2;
			if(p[mid].first<p[i].first+p[i].second)L=mid;
			else R=mid;
		}
		nxt[i]=max(i+1,T.ask(i,L));
		T.set(i,nxt[i]);
		cerr<<i<<" "<<L<<" "<<nxt[i]<<endl;
	}
	dp[n+1]=1;dp[n]=2;
	for(int i=n-1;i>=1;i--)dp[i]=(dp[i+1]+dp[nxt[i]])%mod;
	cout<<dp[1]<<endl;
	return 0;
}

Measured memory_bytes: 5376
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp15
{
    class Class392
    {
        static void Main()
        {
            var NK = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = NK[0], K = NK[1];
            var RSP = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int R = RSP[0], S = RSP[1], P = RSP[2];
            string T = Console.ReadLine();

            int ans = 0;
            List<char> hand = new List<char>();
            for (int i = 0; i < T.Length; i++)
            {
                char t = T[i];
                if (hand.Count >= K)
                {
                    if(hand[hand.Count-K]==Win(t))
                    {
                        hand.Add('?');
                        continue;
                    }
                }
                hand.Add(Win(t));
                if (Win(t) == 'r') ans += RSP[0];
                if (Win(t) == 's') ans += RSP[1];
                if (Win(t) == 'p') ans += RSP[2];
            }

            Console.WriteLine(ans);
        }

        static char Win(char t)
        {
            if (t == 'r') return 'p';
            if (t == 's') return 'r';
            if (t == 'p') return 's';
            return 'E';
        }
    }
}


Measured memory_bytes: 29124
n = gets.chomp.to_i

arr = gets.chomp.split(' ').map(&:to_i)

# 平均を出して、入力のうち最小値から最大値までの整数のうち、一番距離の短い整数にする
# -> 四捨五入した数

avg = arr.inject(&:+)/n.to_f

target = 0

# 0.5の場合 → arrの中にあるものを優先
if avg - avg.to_i == 0.5
  if arr.include? avg.to_i
    target = avg.to_i
  else
    target = avg.to_i - 1
  end
else
  target = avg.round
end

cost = 0

arr.each do |item|
  cost += (item - target) ** 2
end

puts cost

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


int main(){
    int n, m;
    cin >> n >> m;
    vector<P> p(m);
    rep(i,m){
        cin >> p[i].first >> p[i].second;
    }
    rep(x,1000){
        int nx = x / 10;
        vector<int> digit(1, x % 10);
        while(nx){
            digit.push_back(nx % 10);
            nx /= 10;
        }
        if(digit.size() != n)
            continue;
        bool flag = true;
        reverse(digit.begin(), digit.end());
        rep(i, m)
        {
            if(digit[p[i].first-1] != p[i].second)
                flag = false;
        }
        if(flag){
            cout << x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
//
//  main.swift
//  AtCoder
//
//  Copyright © 2020 dazy. All rights reserved.
//

import Foundation

func rl() -> String {
    readLine()!
}

func rls() -> [String] {
    readLine()!.components(separatedBy: " ")
}

let s = rl()
print(s == "ABC" ? "ARC" : "ABC")


Measured memory_bytes: 13088
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
#define rep(i, m, n) for (int i = m; i < n; ++i)
const int64 INF = 1e18;

struct BellmanFord {
    struct Edge {
        int from, to;
        long long cost;
    };
private :
    int n;
    const long long INF;
    vector<Edge> edges;
public :
    vector<long long> dist;
    vector<bool> nega;
    BellmanFord(int _n, int _m, long long _INF) :
    edges(_m), dist(_n, _INF), nega(_n), n(_n), INF(_INF) {}
    void input(int i, int a, int b, long long c) {
        edges[i] = {a, b, c};
    }
    void exe(int s) {
        dist[s] = 0;
        for(int loop = 0; loop < n - 1; ++loop) {
            for(auto &e : edges) {
                if(dist[e.from] == INF) continue;
                if(dist[e.to] > dist[e.from] + e.cost) {
                    dist[e.to] = dist[e.from] + e.cost;
                }
            }
        }
    }
    void negative() {
        for(int loop = 0; loop < n; ++loop) {
            for(auto &e : edges) {
                if(dist[e.from] == INF) continue;
                if(dist[e.to] > dist[e.from] + e.cost) {
                    dist[e.to] = dist[e.from] + e.cost;
                    nega[e.to] = true;
                }
                if(nega[e.from]) nega[e.to] = true;
            }
        }
    }
};

int main() {
    int N, M, P;
    cin >> N >> M >> P;
    BellmanFord bf(N, M, INF);
    rep(i, 0, M){
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        bf.input(i, a, b, P - c);
    }
    bf.exe(0);
    bf.negative();
    if(bf.nega[N - 1]) cout << -1 << endl;
    else {
        int64 ans = -bf.dist[N - 1];
        if(ans > 0) cout << ans << endl;
        else cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define X first
#define Y second

using namespace std;

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

int num[40];
void dfs(int x, int n, int k){
	if (n == 0){
		rep(i, x) cout << (i ? " " : "") << num[i];
		cout << endl;
	}

	for (int i = min(n, k); i > 0; --i){
		num[x] = i;
		dfs(x + 1, n - i, i);
	}
}

int main(){
	int n;
	while (cin >> n, n){
		dfs(0, n, n);
	}

	return 0;
}

Measured memory_bytes: 1164
# https://atcoder.jp/contests/abc088/tasks/abc088_c

import itertools
import collections
import bisect

def main():
    A = [list(map(int, input().split())) for _ in range(3)]

    for a1 in range(101):
        b1 = A[0][0] - a1
        b2 = A[0][1] - a1
        b3 = A[0][2] - a1
        for a2 in range(101):
            if all([a2 + b1 == A[1][0], a2 + b2 == A[1][1], a2 + b3 == A[1][2]]):
                for a3 in range(101):
                    if all([a3 + b1 == A[2][0], a3 + b2 == A[2][1], a3 + b3 == A[2][2]]):
                        print("Yes")
                        exit()

    print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
##import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
c=list(input())
d=Counter(c)
w=d["w"]
r=d["R"]
res_w=res_r=0
for i in range(r):
    if c[i]=="W":
        res_w+=1
for i in range(r,n):
    if c[i] == "R":
        res_r+=1
print(min(res_r,res_w))

Measured memory_bytes: 82496
#include<stdio.h>
#include<algorithm>
#include<utility>
using namespace std;
int a,b,c;
int main(){
  scanf("%d%d%d",&a,&b,&c);
  if(a>b){
    swap(a,b);
  }
  if(a<c && c<b){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  
}

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

int a, b, c, d;

int main() {
  scanf("%d%d%d%d", &a, &b, &c, &d);
  if (abs(c-a) <= d || (abs(a-b) <= d && abs(c-b) <= d)) printf("Yes\n");
  else printf("No\n");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    int h[n+1]={0};
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    int dp[n+1]={0};
    for(int i=2;i<=n;i++){
        if(i==2){
            dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
        }
        else{
            dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
        }
    }
    cout<<dp[n];
    return 0;
}


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

using namespace std;

#define fcout(d) cout << fixed << setprecision(d)
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rep1(i,n) for(int (i) = 1; (i) <= (n); ++(i))
#define repU(i,bottom,ceiling) for(auto (i) = (bottom); (i) <= (ceiling); ++(i))
#define repD(i,ceiling,bottom) for(auto (i) = (ceiling); (i) >= (bottom); --(i))
#define repS(s,n) for(int (s) = 0; s < 1 << (n); ++(s))
#define repV(i,v) for(auto (i) = begin(v); (i) < end(v); ++(i))
#define all(v)  begin(v),end(v)
#define clr(v) fill(all(v),0)
#define l_bnd lower_bound
#define u_bnd upper_bound
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
#define divceil(n,d) ((n)/(d) + ((n)%(d) > 0))
#define parity(a,b) (((a) & 1LL)^((b) & 1LL)^1LL)

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

const pair<int,int> DIR[] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const int INF = -1 + (1 << 30);
const int MOD = (int)1e9 + 7;

ull next_subset(ull subset){
	ull tem = subset + (subset & -subset);
	ull btm = (~tem & subset) / (subset & -subset) >> 1;
	return btm | tem;
}


int N,K,t = 0,c[200001];

void solve(){
	
	sort(all(c));
	int l = u_bnd(all(c),0) - c;
	int res = 0;
	
	while(t > K){
		--t;
		res += c[l];
		++l;
	}
	
	cout<<res<<endl;
	
	return;
}

void input(){
	
	cin>>N>>K;
	clr(c);
	int a;
	
	rep(i,N){
		cin>>a;
		if(!c[a]) ++t;
		++c[a];
	}
	
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	input();
	solve();
	
	return 0;
}





Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int f(int b[][1001],int xb,int xe,int y,int m,int c){
  int i,j;
  for(i=xb;i<xe;i++){
    for(;i<xe&&b[i][y]==1;i++);
    for(j=i;j<xe&&b[j][y]==0;j++);
    if(c>m&&j-i>m)
      m=c;
    if(j-i>m)
      m=f(b,i,j,y+1,m,c+1);
    i=j;
  }
  return m;
}
int main(){
  int i,j;
  int n,m;
  int b[1001][1001];
  string s;
  for(;;){
    cin>>n;
    if(n==0)
      break;
    memset(b,1,sizeof(b));
    for(i=0;i<n;i++){
      cin>>s;
      for(j=0;j<n;j++){
	if(s[j]=='.')
	  b[j][i]=0;
      }
    }
    m=0;
    for(i=0;i<n;i++)
      m=f(b,0,n,i,m,1);
    cout<<m<<endl;
  }
  return 0;
}

Measured memory_bytes: 4844
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 105000;
const int mod = (int) 1e9 + 7;

int n, k;
int a[MAXN];
long long f[MAXN];
long long ans;

long long binpow(long long x, long long p) {
  long long res = 1;
  while (p) {
    if (p & 1) {
      res = (res * x) % mod;
      p--;
    } else {
      x = (x * x) % mod;
      p /= 2;
    }
  }
  return res % mod;
}

long long inv(long long x) {
  return binpow(x, mod - 2) % mod;
}

long long cnk(long long n, long long k) {
  long long res = f[n];
  res = res * inv(f[k]) % mod;
  res = res * inv(f[n - k]) % mod;
  return res;
}

int main() { 

  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }

  sort(a, a + n);

  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1] * i % mod;
  }

  for (int i = 0; i < n; i++) {
    if (i >= k - 1) {
      long long add = 1ll * a[i] * cnk(i, k - 1) % mod;
      ans = (ans + add) % mod;
    }
    if (n - i - 1 >= k - 1) {
      long long rem = 1ll * a[i] * cnk(n - i - 1, k - 1) % mod;
      ans = (ans - rem) % mod;
      if (ans < 0) {
        ans += mod;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a == 5 && b == 5 && c == 7){
    cout << "YES" << endl;
  }else if(a == 5 && b == 7 && c == 5){
     cout << "YES" << endl;
  }else if(a == 7 && b == 5 && c == 5){
     cout << "YES" << endl;
  }else{
  cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;
class Main{
  public static void main(String[]args){
    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
    int a=s.nextInt();
    if(n<=a){
    	System.out.println("unsafe");
    }else{
    	System.out.println("safe");
    }
  }
}

Measured memory_bytes: 35600
"""
https://atcoder.jp/contests/abc139/tasks/abc139_a
"""


def calc(S: str, T: str) -> int:
    hit = [s == t for s, t in zip(S, T)]
    return sum(hit)


def main() -> None:
    S = input()
    T = input()
    result = calc(S, T)
    print(result)


main()


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

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int inf = 1e9 + 7;
const int mod = 1e9 + 7;

inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

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

inline int pw(int x, int n) {
  int res = 1;
  while (n > 0) {
    if (n % 2) {
      res = mul(res, x);
      n--; 
    } else {
      x = mul(x, x);
      n /= 2;
    }
  }
  return res;
}

const int N = 1e5 + 7;

int dp[N][2];
vector <int> g[N];

void dfs(int v, int pr) {
  dp[v][0] = 1;
  dp[v][1] = 1;
  for (int to : g[v]) {
    if (to == pr) continue;
    dfs(to, v);
    for (int me = 0; me < 2; me++) {
      int val = 0;
      for (int was = 0; was < 2; was++) {
        if ((me & was) != 1) {
          add(val, dp[to][was]);
        }
      }
      dp[v][me] = mul(dp[v][me], val);
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(0, -1);
  int ans = dp[0][0];
  add(ans, dp[0][1]);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 13440