akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

inline int gcd(int m,int n){
  int r;
  if(m<n) swap(m,n);
  if(n==0) return m;
  if((r=m%n)!=0){
    return gcd(n,r);
  }
  return n;
}

inline void nextus(int u1,int s1,int u2,int s2,int &u3,int &s3){
  u3=u1*s2-s1*u2;
  s3=s1*s2;
  if(u3<0||s3<0) return;
  int g=gcd(u3,s3);
  u3/=g;
  s3/=g;
}

//vector<int> v;

int num(int ue,int sita,int pro,int promax,int n,int now){
  int ret=0;
  if(pro>promax) return 0;
  if(n==0) return 0;
  if(ue==0){
    /*for(int i=0;i<v.size();i++){
      cout << "1/" << v[i] << " ";
    }
    cout << endl;*/
    return 1;
  }

  while(1){
    int u,s;
    nextus(ue,sita,1,now,u,s);
    if(pro*now>promax) break;

    if(u<0 || s<0) {
      now++;
      continue;
    }
    //v.push_back(now);
    ret+=num(u,s,pro*now,promax,n-1,now);
    //v.pop_back();

    now++;
    if(sita*n < ue*now) break;
  }
  return ret;
}

int main(){
  int ue,sita,promax,n;
  while(cin>>ue>>sita>>promax>>n,ue+sita){
    cout << num(ue,sita,1,promax,n+1,1) << endl;
  }
  return 0;
}

Measured memory_bytes: 868
#include <iostream>
#include <string>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int total=0;
  bool flug = false;
  for(int i = 0;i<26;i++){
    for(int j =0;j<15;j++){
      total = 4*i+7*j;
      if(total == N) flug = true;
    }
  }
  if(flug == true) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3568
#include <iostream>
#include <algorithm>
#include <climits>

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

    int AN[N];
    for (int i=0; i<N; ++i) std::cin >> AN[i];

    int min = INT_MAX;
    int max = INT_MIN;

    for (int i=0; i<N; ++i)
    {
        min = std::min(min, AN[i]);
        max = std::max(max, AN[i]);
    }

    std::cout << max-min << std::endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Set<Integer> set = new HashSet<>();
		int n = sc.nextInt();
		for(int i = 0; i < n; i++) {
			set.add(sc.nextInt());
		}
		System.out.println(set.size());
	}

}


Measured memory_bytes: 21716
#include <iostream>

using namespace std;

int main()
{
int a,b,c;
cin >>a>>b>>c;
if (a==b&&a!=c){
    cout <<c;
}
if (a==c&&a!=b){
    cout<<b;
}
if (b==c&&c!=a){
    cout<<a;
}
   return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;

LL n,k;
LL dp[100005][4] = {0};
LL a[100005],win[4][4];
LL gt[4];
LL to[10005];
string s;

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for(LL i = 1;i <= 3;i ++) cin >> gt[i];
	cin >> s; s = ' ' + s;
	to['r'] = 1; to['s'] = 2; to['p'] = 3;
	win[1][2] = 1; win[2][3] = 1; win[3][1] = 1;
	for(LL i = 1;i <= n;i ++) a[i] = to[s[i]];
	
	for(LL i = 1;i <= k;i ++){
		for(LL j = 1;j <= 3;j ++){
			dp[i][j] = win[j][a[i]] * gt[j];
		}
	}
	
	for(LL i = k + 1;i <= n;i ++){
		for(LL j = 1;j <= 3;j ++){
			for(LL l = 1;l <= 3;l ++){
				if(l == j) continue;
				dp[i][j] = max(dp[i][j],dp[i - k][l] + win[j][a[i]] * gt[j]);
			}
		}
	}
	LL ans = 0;
	for(LL i = n;i >= n - k + 1;i --) ans += max(max(dp[i][3],dp[i][1]),dp[i][2]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  unsigned short *A, *B;
  int C[VMAX+1];
  int n, i, j;

  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  /* your code */
  for(i=1 ; i<=n ; i++)scanf("%d",&A[i]);

  for(i=0 ; i<=VMAX ; i++)C[i] = 0;

  for(j=1 ; j<=n ; j++)C[A[j]]++;

  for(i=1 ; i<VMAX ; i++)C[i] = C[i] + C[i-1];

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

  for(i=1 ; i<=n ; i++){
    if(i!=1)printf(" ");
    printf("%d",B[i]);
  }
  
  printf("\n");
			 
  return 0;
}




Measured memory_bytes: 9640
n = int(input()) - 1
s = input()
result_list = list()
for i in range(n):
    x = s[:i+1]
    y = s[i+1:]
    comon_set_len = len(set(ii for ii in x) & set(iii for iii in y))
    result_list.append(comon_set_len)
result_list.sort(reverse = True)
print(result_list[0])

Measured memory_bytes: 3060
from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic[check]=1
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

Measured memory_bytes: 34144
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<functional>
#include<bitset>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(int)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b, x;
	cin >> a >> b >> x;
	if(x < a) {
		cout << x % MOD << endl;
		return 0;
	}
	ll ans = a % MOD;
	x -= a;
	ll c = (a - b);
	ans += (((x / c) % MOD) * (a % MOD)) % MOD;
	ans += b + ((x % c) % MOD);
	cout << ans % MOD << endl;
}
/* --------------------------------------- */



Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
 
//Optimizations
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
//save time
#define endl '\n'
#define db(x) cerr << "> " << #x << ": " << x << endl
typedef long long ll;
 
//for sorting
#define all(a) a.begin(),a.end()
 
//Constants
#define PI   3.141592653593
#define MOD  1000000007LL
#define EPS  0.000000001
#define INF  0X3f3f3f3f
 
//loops
#define REP(i,n) 	    for(int i=0;i<(n);++i)
#define FOR(i,a,b)      for(int i=(a);i<(b);++i)
#define DFOR(i,a,b)     for(int i=(a);i>=(b);--i)
 
//vectors
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int,int>>
#define vlll vector<pair<ll,ll>>
#define pb 	push_back
 
//pairs
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define F first
#define S second
 
//fast I/O
#ifndef _WIN32
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define gc getchar
#define pc putchar
 
//If using cin and cout
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(NULL);cout.tie(NULL)
 
//queue
#define di deque<int>
#define dll deque<ll>
#define qi queue<int>
#define PQ priority_queue
 
//general
#define E empty()
 
//Declare all variables and methods needed between this comment and the next one(OCD lol)
const int MAXN=1e5+5;
queue<int> q;
vi dp(MAXN, 0);
vi g[MAXN];
vi vis(MAXN, false);
vi in_deg(MAXN, 0);
void dfs(int n ){
    vis[n]=1;
    REP(i, g[n].size()){
        dp[g[n][i]] = max(dp[g[n][i]], dp[n]+1);
        in_deg[g[n][i]]--;
        if(in_deg[g[n][i]] == 0 )dfs(g[n][i]);
    }
}
int main(){
    int n , m ; cin >> n >> m ; 
    
    
    REP(i, m){
        int from, to;
        cin >> from >> to;
        g[from].pb(to);
        in_deg[to]++;
    }

    FOR(i,1,n+1){
        if(!vis[i]&&!in_deg[i])dfs(i);
    }
    cout<<*max_element(all(dp));

}

Measured memory_bytes: 14384
<?php
    /*
        Problem URL : https://beta.atcoder.jp/contests/arc097/tasks/arc097_a

        Score  :
        Result :
        Time   : ms
        Memory : KB
     */

    ini_set('error_reporting', E_ALL & ~E_NOTICE);

    define('DEBUG', false);

    fscanf(STDIN, "%s", $s);
    fscanf(STDIN, "%d", $K);

    $array = array();

    $len = strlen($s);
    for ($i = 0; $i < $len; $i++) {
        $target = min($len - $i, 5);
        for ($j = 1; $j <= $target; $j++) {
            $str = substr($s, $i, $j);
            // echo $str . PHP_EOL;
            $array[$str] = 1;
        }
    }
    // var_dump($array);

    $keys = array_keys($array);
    sort($keys);
    // var_dump($keys);

    echo $keys[$K - 1] . PHP_EOL;


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


int main() {
  int W, H, N;
  cin >> W >> H >> N;
  vector<vector<int>> data(N, vector<int>(2));
  vector<int> a(N);
  for(int i = 0; i < N; ++i) {
      cin >> data[i][0] >> data[i][1];
      cin >> a[i];
  }
  int r = W;
  int l = 0;
  int u = 0;
  int t = H;
  for(int i = 0; i < N; ++i) {
    if(a[i] == 1) {
      if(l < data[i][0]) {
        l = data[i][0];
      }
    }
    if(a[i] == 2) {
      if(r > data[i][0]) {
        r = data[i][0];
      }
    }
    if(a[i] == 3) {
      if(u < data[i][1]) {
        u = data[i][1];
      }
    }
    if(a[i] == 4) {
      if(t > data[i][1]) {
        t = data[i][1];
      }
    }
  }
  int S = (r - l) * (t -u);
  if(r - l < 0 || t - u < 0) {
    cout << 0 << "\n";
  } else {
    cout << S << "\n";
  }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

	public static void main(String[] args) throws IOException, NumberFormatException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Deque<Pair> deq = new ArrayDeque<Pair>();
		
		String[] str = br.readLine().split(" ");
		
		int n = Integer.parseInt(str[0]);
		int q = Integer.parseInt(str[1]);
		
		
		for(int i = 0; i < n; i++){
			str = br.readLine().split(" ");
			deq.addFirst(new Pair(str[0], Integer.parseInt(str[1])));
		}
		
		int timeCount = 0;
		
		String[] name = new String[n];
		int[] time = new int[n];
		
		for(int i = 0; !deq.isEmpty();){
			
			Pair p = deq.removeLast();
			
			if(p.getTime() > q){
				p.overTime(q);
				deq.addFirst(p);
				timeCount += q;
			} else {
				timeCount += p.getTime();
				
				name[i] = p.getName();
				time[i] = timeCount;
				i++;
			}
		}
		
		for(int i = 0; i < n; i++){
			System.out.println(name[i] + " " + time[i]);
		}
	}

}

class Pair {
	String name;
	int time;
	
	Pair(String name, int time){
		this.name = name;
		this.time = time;
	}
	
	void overTime(int over){
		time -= over;
	}
	int getTime(){
		return time;
	}
	String getName(){
		return name;
	}
}

Measured memory_bytes: 76216
#include <cstdio>
#include <iostream>
#include <unordered_map>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)

const int MAX_N = 5000;

class UnionFind{
public:
    UnionFind(int n){
        REP(i, n){
            par[i] = i;
            rank[i] = 0;
        }
    }
    int find(int x){
        if(x == par[x])return x;
        return par[x] = find(par[x]);
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y){return;}
        
        if(rank[x] > rank[y]){
            par[y] = x;
        }else{
            par[x] = y;
            if(rank[x] == rank[y]){rank[y]++;}
        }
    }
private:
    int rank[MAX_N], par[MAX_N];
};

int N, M;
int X[5000];
std::unordered_map<std::string, int> map;
UnionFind uf(5000);

int main(){
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        std::string name;
        std::cin >> name >> X[i];

        map[name] = i;
    }

    scanf("%d", &M);
    
    for(int i=0;i<M;i++){
        std::string from, to;
        std::cin >> from >> to;

        uf.unite(map[from], map[to]);
    }

    int sum = 0;
    for(int i=0;i<N;i++){
        int mn = 1001001001;
        for(int j=0;j<N;j++){
            if(uf.same(i, j)){
                mn = std::min(mn, X[j]);
            }
        }

        sum += mn;
    }

    printf("%d\n", sum);
}

Measured memory_bytes: 1788
# 桁DP 最適化もうむり

MOD = 10 ** 9 + 7
s = gets.chomp.split("")
question = s.map { |c| c == "?" }
length = s.length
# dp[上から i 桁まで][13 で割ったあまり]の出現回数
# 桁の自由度(smaller)は本問では不要
dp = (length + 1).times.map { Array.new(13, 0) }
# 初期化
# dp[0 桁目まで][13 で割ったあまりが 0]の出現回数は 1
dp[0][0] = 1
# （右から見た）桁数 % 6
mod_memo = [4, 1, 10, 9, 12, 3]
all_nums = (0..9).to_a

# 桁数分ループする（i は遷移元の桁）
length.times do |i|
  # 13 で割ったあまりの増加分を求める
  addition = mod_memo[(length - i) % 6]
  # 桁の数字が "?" の場合は 10 回ループ、それ以外の場合はその数字のみ
  nums = question[i] ? all_nums : [s[i].to_i]
  original_counts = dp[i]
  # ★★★とにかく繰り返し dp を見るのが遅いようなので tmp を用意しました★★★
  tmp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  # 13 で割ったあまりごとに確認する
  13.times do |mod|
    original_count = original_counts[mod] % MOD
    nums.each do |d|
      # 次の桁に遷移する
      tmp[(mod + addition * d) % 13] += original_count
    end
  end
  dp[i + 1] = tmp
end

puts dp[length][5] %= MOD


Measured memory_bytes: 34684
# https://atcoder.jp/contests/arc092/submissions/13926597
# 最大流で解くという発想

# https://tjkendev.github.io/procon-library/python/max_flow/dinic.html


# Dinic's algorithm
from collections import deque


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None] * self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10 ** 9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def main():
    N = int(input())

    reds = [tuple(map(int, input().split())) for _ in range(N)]
    blues = [tuple(map(int, input().split())) for _ in range(N)]

    dnc = Dinic(N * 2 + 2)
    for i, (rx, ry) in enumerate(reds, start=1):
        dnc.add_edge(fr=0, to=i, cap=1)
        for j, (bx, by) in enumerate(blues, start=N + 1):
            if rx < bx and ry < by:
                dnc.add_edge(fr=i, to=j, cap=1)

    for j in range(N + 1, N * 2 + 1):
        dnc.add_edge(fr=j, to=N * 2 + 1, cap=1)

    ans = dnc.flow(0, N * 2 + 1)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4080
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<double> H(N);
  for(int i=0;i<N;i++){
    cin >> H[i];
  }
  double cnt=1;
  vector<double> X(N);
  for(int i=0;i<N;i++){
    cnt*H[i];
  }
  double cntt=0;
  for(int i=0;i<N;i++){
    X[i]=cnt/H[i];
    cntt+=X[i];
  }
  printf("%.14f\n",cnt/cntt);
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

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

    s+="abcdefghijklmnopqrstuvwxyz";
    
    vector<int> bounds;
    bounds.pb(s.size());
    vector<bool> hist(26,0);
    for(int i=s.size()-1;i>=0;i--){
        hist[s[i]-'a'] = true;
        if(hist==vector<bool>(26,true)){
            bounds.pb(i);
            hist = vector<bool>(26,0);
        }
    }
    reverse(all(bounds));
    
    vector<int> pos[26];
    rep(i,s.size()){
        pos[s[i]-'a'].pb(i);
    }
    
    
    int p = -1;
    string ans = "";
    while(1){
        if((int)s.size()-26<=p)break;
        for(char ch = 'a';ch<='z';ch++){
            if(upper_bound(all(bounds),p)==bounds.end())goto end;
            int b = *upper_bound(all(bounds),p);
            int t = *upper_bound(all(pos[ch-'a']),p);
            if(b<=t){
                ans+=ch;
                p = t;
                break;
            }
        }
    }
end:;
    cout<<ans<<endl;
}


Measured memory_bytes: 1412
fun main(args: Array<String>) {
    val (H, W) = readInputLine().split(" ").map { it.toInt() }
    val cArr = Array(10) { readInputLine().split(" ").map { it.toInt() }.toIntArray() }
    
    var costOld = IntArray(10) { Int.MAX_VALUE }
    for (i in 0..9) {
        costOld[i] = cArr[i][1]
    }
    val cost = costOld.copyOf()

    while (true) {
        var changed = false
        for (i in 0..9) {
            if (i == 1) {
                continue
            }
            for (j in 0..9) {
                if (cost[i] > costOld[j] + cArr[i][j]) {
                    cost[i] = costOld[j] + cArr[i][j]
                    changed = true
                }
            }
        }
        
        if (!changed) {
            break
        }
        
        costOld = cost.copyOf()
    }

    val cnt = IntArray(10)

    for (i in 1..H) {
        readInputLine().split(" ").forEach {
            val tmp = it.toInt()
            if (tmp != -1) {
                cnt[tmp]++
            }
        }
    }
    
    println(cnt.foldIndexed(0) { index, acc, cnt -> acc + cost[index] * cnt})
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 41552
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<map>
#include<random>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include <queue>
#include<boost/multiprecision/cpp_int.hpp>


using namespace std;
using namespace boost::multiprecision;

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldb = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIF(v, n) printf("%."#n"f\n", v)
#define PRIY PRI("Yes")
#define PRIN PRI("No")
template<typename A, typename B>
void mins(A & a, const B & b) { a = min(a, (A)b); };
template<typename A, typename B>
void maxs(A & a, const B & b) { a = max(a, (A)b); };


int main() {
	string s;
	cin >> s;
	if (s.back() == 's') {
		s += "es";
	}
	else s += 's';
	PRI(s);
	return 0;
}

Measured memory_bytes: 3624
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

n = inp[0]
pt = na2(n,0)
n.times do |i|
  m = inp[0]
  m.times do
    dp = inp
    dp[0] = dp[0]-1
    pt[i].push([dp[0],dp[1]])
  end
end
max = 0
(1..(2**n-1)).each do |ds|
  c = 0
  t = Array.new(n)
  f = false
  n.times do |pi|
    next if ds[pi] == 0
    c+=1
    pt[pi].each do |voice|
      if(voice[1] != ds[voice[0]])
        f = true
        break
      end
    end
  end
  next if f
  [max = [c,max].max]
end
p max

Measured memory_bytes: 1916
def main():
    n, k, *a = map(int, open(0).read().split())
    a = [0] + a
    check = [0] * (n + 1)
    check[1] = 1

    i = 0
    nw = 1
    path = [1]
    while 1:
        nx = a[nw]
        i += 1
        if i == k:
            print(nx)
            break
        if check[nx]:
            j = path.index(nx)
            d = j + (k - i) % (i - j)
            print(path[d])
            break
        path.append(nx)
        check[nx] = 1
        nw = nx


if __name__ == '__main__':
    main()


Measured memory_bytes: 31804
//Author: AnandRaj uux
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll; 

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test() int t;cin>>t;while(t--)
#define forn(i,f,n) for(int i=f;i<f+n;i++)
#define rforn(i,l,n) for(int i=l;i>l-n;i--)
#define all(v) v.begin(),v.end()
#define prin(V) for(auto v:V) cout<<v<<" ";cout<<endl
#define take(V,f,n) for(int i=f;i<f+n;i++) cin>>V[i]
#define what(x) cerr<<#x<<" = "<<x<<endl
#define KStest() int t,t1;cin>>t;t1=t;while(t--)
#define KScout cout<<"Case #"<<t1-t<<": "

const int MOD = 1e9+7,MAX = 1e5+5;
/////////////////FastExp///////////////////
ll powN(ll a,ll p)
{
	if(p==0) return 1;
	ll z=powN(a,p/2);
	z=(z*z)%MOD;
	if(p%2) z=(z*a)%MOD;
	return z;
}
/////////////////FastExp///////////////////
//////////////////Sieve////////////////////
vector<bool> is_prime(MAX+1, true);
void Sieve()
{
	is_prime[0] = is_prime[1] = false;
	int i,j;
	for (i = 2; i*i <= MAX; i++) 
	{
    	if (is_prime[i]) 
    	{
        	for (j = i * i; j <= MAX; j += i)
            	is_prime[j] = false;
    	}
	}
}
//////////////////Sieve////////////////////

int main()
{
	int n,m;
	cin>>n>>m;
	cout<<n*(n-1)/2 + m*(m-1)/2<<endl;
}		

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int inputnum, i;
    int kat_num[20], kaka_num[20];
    int ans=0, anstmp;

    scanf("%d", &inputnum);
    for(i=0; i<inputnum; i++){
        scanf("%d", &kat_num[i]);
    }
    for(i=0; i<inputnum; i++){
        scanf("%d", &kaka_num[i]);
        anstmp = kat_num[i] - kaka_num[i];
        if(anstmp > 0){
            ans = ans + anstmp;
        }
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
import java.util.*;
import javax.lang.model.util.ElementScanner6;
import java.lang.Math;

public class Main {

    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);

        // 入力
        String s = sc.next();
        //double a = sc.nextDouble();
        //double b = sc.nextDouble();

        // 
        String out = s.substring(0, 3);

        // 出力
        System.out.println(out);
    }    
}


Measured memory_bytes: 35728
#include <stdio.h>
int main(){
  int A,B,C;
  scanf("%d%d%d", &A, &B, &C);
 
  int no=0;
  
  if(A==B&&B!=C){
    no=1;
  }  
  if(A==C&&C!=B){
    no=1;
  }  
  if(C==B&&B!=A){
    no=1;
  }
  if(no==1){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
  
  return 0;
}   

Measured memory_bytes: 128
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var s = Console.ReadLine().Trim();
        getAns(n, s);
    }
    static void getAns(int n, string s)
    {
        var w1 = 0;
        var w2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] >= 'A' && s[i] <= 'M') w1++;
            else if (s[i] >= 'N' && s[i] <= 'Z') w1--;
            else if (s[i] >= 'a' && s[i] <= 'm') w2++;
            else w2--;
        }
        var ans = "";
        if (w1 > 0) ans += new string('A', w1);
        else if (w1 < 0) ans += new string('N', -w1);
        if (w2 > 0) ans += new string('a', w2);
        else if (w2 < 0) ans += new string('n', -w2);
        Console.WriteLine(ans.Length);
        Console.WriteLine(ans);
    }
}



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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int MAXH = 400;

int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};

string s[MAXH];
int h, w;

bool visited[MAXH][MAXH];

ll solve(int i, int j){
    ll white = 0, black = 0;
    // bfs
    queue<tuple<int, int, bool> > Q;
    visited[i][j] = true;
    Q.push(make_tuple(i, j, true));
    // cout << i << " " << j << endl;
    while(!Q.empty()){
        auto v = Q.front();
        Q.pop();
        int ci = get<0>(v);
        int cj = get<1>(v);
        bool isblack = get<2>(v);
        if(isblack) black++;
        else white++;
        for(int k=0;k<4;k++){
            if(ci + di[k] < 0 || ci + di[k] >= h || cj + dj[k] < 0 || cj + dj[k] >= w) continue;
            if(visited[ci + di[k]][cj + dj[k]]) continue;
            if(isblack && s[ci + di[k]][cj + dj[k]] == '.'){
                visited[ci + di[k]][cj + dj[k]] = true;
                Q.push(make_tuple(ci + di[k], cj + dj[k], false));
            }else if(!isblack && s[ci + di[k]][cj + dj[k]] == '#'){
                visited[ci + di[k]][cj + dj[k]] = true;
                Q.push(make_tuple(ci + di[k], cj + dj[k], true));
            }
        }
    }
    return white * black;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> h >> w;
    for(int i=0;i<h;i++) cin >> s[i];
    ll ans = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j] == '#' && !visited[i][j]){
                ans += solve(i, j);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define INF ((1e9)+10000)
#define N 5005
using namespace std;
int n,k,a[N],memo[N][N],minsum[N],ans;
bool used[N][N],used2[N];

int dfs(int x,int sum){
  if(sum>=k)return sum;
  if(x==n)return INF;
  if(used[x][sum])return memo[x][sum];
  used[x][sum]=1;
  int res=INF;
  res=min(res,dfs(x+1,sum+a[x]));
  minsum[x]=min(minsum[x],res);
  res=min(res,dfs(x+1,sum));
  return memo[x][sum]=res;
}

int main(){
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i];
    minsum[i]=INF;
  }
  dfs(0,0);
  for(int i=0;i<n;i++)
    if(minsum[i]-a[i]>=k)ans++;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 122752
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){

  char s[1001];
  char word[8]; word[7]='\0';
  int n;
  int j;

  cin >> n;
  getchar();

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

    gets(s);
    j=0;

    while(s[j+7]!='\n'){


        for(int k=0; k<7; k++){
          if(s[j+k]==' '){ break; }
          word[k]=s[j+k];
        }

        //cout << "test:" <<word << endl;


        if(strcmp(word,"Hoshino")==0){
          s[j+6]='a';
        }
      
      j++;
    }
    cout << s << endl;
  }


  return 0;

}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define PI acos(-1)

int main() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    cout << 15 - a - b - c - d - e << endl;
    return 0;
}

Measured memory_bytes: 3552
#include<bits/stdc++.h>
using namespace std;
int p[100010],sum[100010]; 
int main(){
	p[1] = 1;
	p[2] = 0;
	for (int i=2;i<=100000;i++){
		for(int j=i*2;j<=100000;j=i+j){
			p[j]=1;
		}
	}
	sum[2]=1;
	for (int i=1;i<=100000;i++){
		if (p[i]==0&&p[(i+1)/2]==0){
			sum[i] = sum[i-1]+1;
		}
		else
		    sum[i]=sum[i-1];
	}
	int T;
	cin>>T;
	while (T--){
		int n,m;
		cin>>n>>m;
		cout<<sum[m]-sum[n-1]<<endl;
	} 
	return 0;
} 

Measured memory_bytes: 1408
// finish date: 2018/01/19
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define bigmod 1000000007
#define INF 500000000


int main() {
    int N, T, A;
    cin >> N;
    ll X = 1, Y = 1;
    ll n;
    rep(i, N) {
        cin >> T >> A;
        n = max((X+T-1)/T,(Y+A-1)/A);
        X = n*T;
        Y = n*A;
    }
    cout << X + Y << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn=1e6+10;
#define p 1000000007
int main(){
	fast;
	int d,t,s; cin>>d>>t>>s;
	if(d<=s*t)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}
//prime func
//subset production
//factorization
//modpow
//modinv ( a^(p-2)=a^(-1) (mod p) )
//sieve
//ncr
//euler totien func (co prime divisiors upto n)
//matrix exponentation
//dsu
//Trees
//Graphs(dfs,bfs,shortes path etc.)
//DP-Recursion

Measured memory_bytes: 3608
/// Template made by Eugen Ajechiloae
#include <bits/stdc++.h>
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
#ifdef _WIN32
#include <windows.h>
#define print(x) PRINT(x, #x)
template<typename T> inline const void PRINT(T VARIABLE, string NAME)
{
#ifndef ONLINE_JUDGE /// ONLINE_JUDGE IS DEFINED ON CODEFORCES
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, 10);
    cerr << NAME << " = " << VARIABLE;
    SetConsoleTextAttribute(hConsole, 7);
    cerr << '\n';
#endif
}
#else
#define print(x) 0
#endif
struct pair_hash
{
    template<typename T1, typename T2>
    size_t operator () (const pair<T1, T2> &p) const
    {
        auto h1 = hash<T1> {}(p.first);
        auto h2 = hash<T2> {}(p.second);
        return h1 ^ h2;
    }
};
typedef long long ll;
typedef unsigned long long ull;
const ll INFLL = 2 * (ll)1e18 + 100;
const int INFINT = 2 * (int)1e9 + 100;
//ifstream fin(".in");
//ofstream fout(".out");
void die()
{
    cout << "-1\n";
    exit(0);
}
const int NMAX = 100 + 55;
const int MOD = 1e9 + 7; /// careful here (7 or 9, 66.. etc)
const double PI = atan(1) * 4;
const double EPS = 1e-12;

ll n, m;

ll solve(ll x, ll y)
{
    ll ret = INFLL;
    for(int i = 1; i < x; i++)
    {
        vector<ll> temp;
        temp.pb(i * y);
        temp.pb(((x - i) / 2) * y);
        temp.pb(((x - i + 1) / 2) * y);
        sort(all(temp));
        ret = min(ret, temp[2] - temp[0]);
        temp.clear();
        temp.pb(i * y);
        temp.pb((y / 2) * (x - i));
        temp.pb((y / 2 + y % 2) * (x - i));
        sort(all(temp));
        ret = min(ret, temp[2] - temp[0]);
    }
    return ret;
}

int main()
{
    FASTIO;
    cin >> n >> m;
    cout << min(solve(n, m), solve(m, n));

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

int main(){
	int n,m;
	int i,j,k;
	int a,b,c;
	cin>>n;
	n%=10;
	switch(n){
		case 2:case 4:case 5:case 7:case 9:
		cout<<"hon"<<endl;
		break;
		case 0:case 1:case 6:case 8:
		cout<<"pon"<<endl;
		break;
		case 3:default:
		cout<<"bon"<<endl;
	}
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n, x = 0;
    string s;
    char c;
    cin>>n>>s;
    x = s.size();
    c = s[0];
    for(ll i=1; i<s.size(); i++)
    {
        if(c == s[i])
        {
            x--;
        }
        else c = s[i];
    }
    cout<<x<<endl;
    return 0;
}


Measured memory_bytes: 3704
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    n: usize,
    mut m: usize,
    mut ab: [(usize, usize); n]
    }
    ab.sort();
    let mut ans: usize = 0;
    for i in 0..n {
        if m > ab[i].1 {
            m -= ab[i].1;
            ans += ab[i].1 * ab[i].0;
        } else {
            ans += ab[i].0 * m;
            break;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 5776
import java.util.*

fun main(args: Array<String>) = abc157e()

fun abc157e() {
    val n = readLine()!!.toInt()
    val s = readLine()!!
    val q = readLine()!!.toInt()
    val queries = (1..q).map {
        readLine()!!.split(' ').map { it }
            .let { Query(if (it[0].toInt() == 1) QueryType.UPDATE else QueryType.GET, it[1].toInt(), it[2]) }
    }

    val arr = IntArray(n)
    s.forEachIndexed { index, c -> arr[index] = charToBit(c) }

    val st = SegmentTree(arr, Int::or)
    val answer = StringBuilder()

    for ((type, x, y) in queries) {
        when (type) {
            QueryType.UPDATE -> st[x - 1] = y[0]
            else -> answer.appendln(st[x - 1..y.toInt() - 1])
        }
    }

    print(answer)
}

private fun charToBit(char: Char) = Math.pow(2.0, (char - 'a').toDouble()).toInt()

private data class Query(val type: QueryType, val x: Int, val y: String)
private enum class QueryType { UPDATE, GET }

private class SegmentTree(init: IntArray, val monad: (Int, Int) -> Int) {
    val indices: Int
    val nodes: IntArray

    init {
        var indices = 1
        while (indices < init.size) indices = indices shl 1
        val nodes = IntArray(2 * indices - 1)
        for (i in init.indices) nodes[i + indices - 1] = init[i]
        for (i in indices - 2 downTo 0) nodes[i] = monad(nodes[2 * i + 1], nodes[2 * i + 2])
        this.indices = indices
        this.nodes = nodes
    }

    operator fun set(x: Int, value: Char) {
        var index = x + indices - 1
        nodes[index] = charToBit(value)
        while (index > 0) {
            index = (index - 1) / 2
            nodes[index] = monad(nodes[2 * index + 1], nodes[2 * index + 2])
        }
    }

    operator fun get(range: IntRange): Int =
        BitSet.valueOf(longArrayOf(get(range.first, range.last + 1).toLong())).cardinality()

    fun get(a: Int, b: Int, k: Int = 0, l: Int = 0, r: Int = indices): Int {
        if (r <= a || b <= l) return 0
        if (a <= l && r <= b) return nodes[k]
        return monad(
            get(a, b, 2 * k + 1, l, (l + r) / 2),
            get(a, b, 2 * k + 2, (l + r) / 2, r)
        )
    }
}


Measured memory_bytes: 63020
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int A,B;
int cnt[3];

int main(void){
    scanf("%d",&n);
    scanf("%d%d",&A,&B);
    for(int i=0;i<n;i++){
        int a;
        scanf("%d",&a);
        if(a<=A){
            cnt[0]++;
        }else if(a<=B){
            cnt[1]++;
        }else{
            cnt[2]++;
        }
    }
    printf("%d\n",min(cnt[0],min(cnt[1],cnt[2])));
    return 0;
}

Measured memory_bytes: 256
def main():
    a, b, c = map(int, input().split())
    if a == 5 and b == 5 and c == 7:
        ans = 'YES'
    elif a == 5 and b == 7 and c == 5:
        ans = 'YES'
    elif a == 7 and b == 5 and c == 5:
        ans = 'YES'
    else:
        ans = 'NO'
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9192
use proconio::input;

fn main() {
    input! {
        n: String,
    };
    let v: Vec<char> = n.chars().collect();
    if v[0].to_string() == "7" || v[1].to_string() == "7" || v[2].to_string() == "7" {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2152
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll ;
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 const ll inf=1e9+7;

int main()
{
    fast;
    
ll n;
cin>>n;
ll a[n];
for(auto &e:a)cin>>e;
ll cost=0,min_cost=inf;
for(ll i=-100;i<=100;i++)
{
	cost=0;
	for(auto x: a)
	{
		cost+=abs(x-i)*abs(x-i);
	}
	min_cost=min(min_cost,cost);
	
	
}
    
    cout<<min_cost;
    
 
   
}

		
	
	
	
	


Measured memory_bytes: 3692
// Aizu Vol0 0076: Treasure Hunt II
// 2017.7.31

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char *gets(char *);
char buf[100];

#define MAX 1000

double r[MAX + 2], d[MAX + 2];

int main()
{
	int i;

	r[1] = 1, d[1] = 0;
	for (i = 2; i <= MAX; i++) {
		d[i] = d[i-1] + atan(1 / r[i-1]);
		r[i] = sqrt(r[i-1]*r[i-1] + 1);
	}

	while (1) {
		gets(buf);
		if ((i = atoi(buf)) < 0) break;
		printf("%lf\n%lf\n", r[i]*cos(d[i]), r[i]*sin(d[i]));
	}
	return 0;
}

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }

  map<ll, ll> m;
  rep(i, 0, N) { m[A[i]]++; }
  if (sz(m) <= K) {
    put(0);
    return 0;
  }

  vector<ll_ll> v;
  for (auto p : m) {
    v.pb({p.second, p.first});
  }
  sort(all(v));
  ll ans = 0;
  rep(i, 0, sz(v) - K) ans += v[i].first;
  put(ans);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

template <class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

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

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


Measured memory_bytes: 20208
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	vs := make([]int, n)
	cs := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&vs[i])
	}

	for i := 0; i < n; i++ {
		fmt.Scan(&cs[i])
	}

	ret := 0
	for i := 0; i < n; i++ {
		if vs[i] > cs[i] {
			ret += vs[i] - cs[i]
		}
	}

	fmt.Println(ret)

}


Measured memory_bytes: 512
/*
 * Author : Andrew J
*/
#include <bits/stdc++.h>
using namespace std;
#define rall(x) x.rbegin() , x.rend()
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
using ll = long long;
using ii = pair <ll , ll>;
void in(ll &x);
const ll N = 2e5 + 10;
#define singleCase
// #define multipleCase
ll pos[N],n;

void work() {
   in(n);
   for (ll i = 1, x ; i <= n ; i++) {
      in(x);
      pos[x] = i;
   }
   ll sol = 0;
   set <ll> s;
   s.insert(0); s.insert(n + 1);
   for (ll i = 1 ; i <= n ; i++) {
      auto it = s.upper_bound(pos[i]);
      ll high = *it;
      --it;
      ll low = *it;
      ll k = min(pos[i] - low , high - pos[i]);
      sol += i * (k * (k + 1) + k * (high - low - 1 - 2 * k));
      s.insert(pos[i]);
   }
   printf("%lld\n" , sol);
   return;
}

int main() {
   #ifdef multipleCase
      ll nQ; in(nQ);
      while (nQ--)
         work();
   #endif
   #ifdef singleCase
      work();
   #endif
   return 0;
}

void in(ll &x) {
	bool neg = false;
	register ll c;
	x = 0;
	c = getchar();
	if(c == '-') {
		neg = true;
		c = getchar();
	}
	for (; c > 47 && c < 58; c = getchar())
	  x = (x << 1) + (x << 3) + c - 48;
	if (neg) x *= -1;
}


Measured memory_bytes: 14544
/* 

*/
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <bitset>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define LSOne(S) (S & (-S))
#define EPS 1e-9
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pd;
typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

const int MOD = 1e9+7;
const char WALL = '#';

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); // BEFORE SUBMIT DON'T FORGET TO UNCOMMENT THIS
    int h, w;
    cin >> h >> w;
    vector<vector<char>> board(h+5, vector<char>(w+5));

    for(int i = 1; i <= h; ++i)
    {
        for(int j = 1; j <= w; ++j)
        {
            cin >> board[i][j];
        }
    }

    vector<ll> dp(w+5);
    dp[1] = 1;
    for(int i = 1; i <= h; ++i)
    {
        vector<ll> prev = dp;
        for(int j = 1; j <= w; ++j)
        {
            if(board[i][j] == WALL) dp[j] = 0;
            else dp[j] = (dp[j-1] + prev[j]) % MOD;
        }
    }
    cout << dp[w] << "\n";
    return 0; 
}


Measured memory_bytes: 1280
N = int(input())
AB = [0] * N
B = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

sortAB = sorted(AB, key = lambda x: (x[1], x[0]))

isYes=True
s=0
for a in sortAB:
    s += a[0]
    if s > a[1]:
        isYes=False
        break

if isYes:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 69472
#include<iostream>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	string s;
	cin >> s;

	int max = 0;
	int tmp = 0;
	for(int i=0; i<s.length(); i++){
		if(s.at(i)=='A' || s.at(i)=='T' || s.at(i)=='G' || s.at(i)=='C'){
			tmp++;
			if(tmp>max){
				max = tmp;
			}
		}else{
			tmp=0;
		}
	}


	cout << max << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max = 1e3 + 7;
int ls1[Max], ls2[Max];
int n;


int main()
{
	string s, t;
	cin >> s >> t;
	for (int i = 0; i <= s.size() - 1; i++)
	{
		ls1[i] = s[i] - 'a' + 1;
	}
	for (int i = 0; i <= t.size() - 1; i++)
	{
		ls2[i] = t[i] - 'a' + 1;
	}
	sort(ls1, ls1 + s.size());
	sort(ls2, ls2 + t.size(),greater<int>());
	int f =0;
	for (int i = 0; i <= max(s.size(), t.size()) - 1; i++)
	{
		if (ls1[i] == ls2[i])continue;
		if (ls1[i] < ls2[i])
		{
			f = 1;
			break;
		}
		else
		{
			f = 0;
			break;
		}
	}
	if (f)cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 3056
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int k = sc.nextInt();
    ArrayList<Integer>ans  = new ArrayList<>();
    
    for(int i=1; i<=Math.max(a,b); i++) {
    	if(a%i==0 && b%i==0) {
    		ans.add(i);
    	}
    }
    Collections.sort(ans,Collections.reverseOrder());
	System.out.println(ans.get(k-1));
      }
}


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

#include <iostream>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  int ans = min(int(a / 0.08), int(b / 0.1));
  while (true) {
    if (int(ans * 0.08) == a && int(ans * 0.1) == b) {
      break;
    }
    if (int(ans * 0.08) > a || int(ans * 0.1) > b) {
      ans = -1;
      break;
    }
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256