akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;

int main()
{
  int N;
  cin >> N;
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 1000; i < 2000; ++i)
  {
    string check = to_string(i).substr(1);
    int index = 0;
    for (int j = 0; j < N; ++j)
    {
      if (s[j] == check[index])
      {
        if (index == 2)
        {
          ans += 1;
          break;
        }
        index += 1;
      }
    }
  }
  cout << ans << endl;
}


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

static const int INF=1e9;
static const int MOD=1000000007;
typedef long long ll;
typedef pair<int,int> P;

int H,W;
char s[50][50];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int solve(int sx,int sy){
    int d[50][50]={};
    int used[50][50]={};
    queue<P> que;
    que.push({sx,sy});
    used[sx][sy]=1;
    while(!que.empty()){
        P q=que.front(); que.pop();
        for(int i=0;i<4;i++){
            int nx=q.first+dx[i];
            int ny=q.second+dy[i];
            if(used[nx][ny]==1) continue;
            if(nx>=H||ny>=W||nx<0||ny<0||s[nx][ny]=='#') continue;
            used[nx][ny]=1;
            d[nx][ny]=d[q.first][q.second]+1;
            que.push({nx,ny});
        }
    }
    int ans=0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            ans=max(ans,d[i][j]);
        }
    }
    return ans;
}


int main(){
    cin >> H >> W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> s[i][j];
        }
    }
    int ans=0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(s[i][j]=='#') continue;
            ans=max(ans,solve(i,j));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import kotlin.math.*
import java.util.*

fun main(args: Array<String>) {
  val (a, b, n) = readLine()!!.split(' ').map(String::toLong)
  val x = min(b - 1, n)
  val y = floor(a * x / b.toDouble()).toLong() - a * floor(x / b.toDouble()).toLong()
  println(y)
}


Measured memory_bytes: 36236
#include <stdio.h>

int X[1000000],num;

int binarySearch(int bn){
  int L = 0,R = num,M;

  while(L< R){
    M = (L + R) /2;
    if(bn == X[M]) {
      return 1;
    }
    if(bn > X[M]) {
      L = M +1;
    }
    else if(bn < X[M]) {
      R = M;
    }
  }
    return 0;
  }

    int main(){
      int i,num2,bn,S=0;

      scanf("%d",&num);
      for(i=0;i<num;i++){
	scanf("%d",&X[i]);
      }

      scanf("%d",&num2);
      for(i=0;i<num2;i++){
	scanf("%d",&bn);
	if(binarySearch(bn)){
	  S++;
	}
      }
	printf("%d\n",S);

	return 0;
      }
		      
      



Measured memory_bytes: 2108
#include<iostream>
using namespace std;
int main(){
   int n,max=0,maxnum,sum=0;
   cin >> n;
   int l[n];
   for(int i=1;i<=n;i++){
       cin >> l[i];
       if(l[i]>max) max=l[i],maxnum=i;
   }
   for(int i=1;i<=n;i++){
       if(i!=maxnum) sum+=l[i];
   }
   if(sum>max) cout << "Yes" <<endl;
   else cout << "No" << endl;

}

Measured memory_bytes: 256
def main():
    N = input()
    N = int(N)

    S = input()

    x = 0
    lst =[0]

    for i in S:
        if i == "I":
            x +=1
        else:
            x -=1
        lst.append(x)

    print(max(lst))

if __name__ == "__main__":
        main()


Measured memory_bytes: 3060
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	rep(i, 4) {
		cout << s[i];
	}
	cout << " ";
	REP(i, 4, s.size()) cout << s[i];
	cout << endl;
	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

main(){
	int a,b,d,r;
	double f;
	scanf("%d%d",&a,&b);
	
	d=a/b;
	r=a%b;
	f=(double)a/b;
	
	printf("%d %d %f\n",d,r,f);
	
	return 0;
}

Measured memory_bytes: 636
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 1
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	m := getNextInt(scanner)

	a := make([]string, n)
	b := make([]string, m)
	for i := 0; i < n; i++ {
		a[i] = getNextString(scanner)
	}
	for i := 0; i < m; i++ {
		b[i] = getNextString(scanner)
	}
	for i := 0; i+m <= n; i++ {
		for j := 0; j+m <= n; j++ {
			if equal(i, j, a, b) {
				fmt.Fprintln(writer, "Yes")
				return
			}
		}
	}

	fmt.Fprintln(writer, "No")
}

func equal(i, j int, a, b []string) bool {
	m := len(b)
	for k := 0; k < m; k++ {
		for l := 0; l < m; l++ {
			if a[i+k][j+l] != b[k][l] {
				return false
			}
		}
	}
	return true
}


Measured memory_bytes: 640
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int n;
  scanf("%d", &n);
  int c[n-1], s[n-1], f[n-1];
  for (int i=0; i<n-1; i++)
    scanf("%d%d%d", c+i, s+i, f+i);
  for (int i=0; i<n; i++) {
    int ans = 0;
    for (int j=i; j<n-1; j++) {
      if (ans <= s[j]) {
        ans = s[j]+c[j];
      } else {
        ans = ((ans - s[j]-1)/f[j] + 1)*f[j] + s[j] + c[j];
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}


Measured memory_bytes: 128
n,k=[int(i) for i in input().split()]
array=[]
for i in range(n):
    a,b=[int(_) for _ in input().split()]
    array.append(tuple([a,b]))
array.sort(key=lambda x:x[0])
count=0
for a,b in array:
    count+=b
    if count>=k:
        print(a)
        break

Measured memory_bytes: 18188
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int n;
    cin>>n;
    int a[n],b[n];
    rep(i,n)    cin>>a[i];
    rep(i,n)    cin>>b[i];
    int suma[n+1],sumb[n+1];
    suma[0]=0;sumb[0]=0;
    rep(i,n){
        suma[i+1]=suma[i]+a[i];
        sumb[i+1]=sumb[i]+b[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,suma[i]+sumb[n]-sumb[i-1]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main() {
  int a, b;
  std::cin >> a >> b;
  if (a <= 0 && b >= 0) {
    std::cout << "Zero" << std::endl;
  } else if (a > 0 || (b-a)%2 == 1) {
    std::cout << "Positive" << std::endl;
  } else {
    std::cout << "Negative" << std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
n,m = gets.chomp.split(" ").map(&:to_i)
a = Array.new(n){Array.new}
n.times do |i|
  a[i] = gets.chomp.split(" ").map(&:to_i)
end
cnt = Array.new(m+1,0)
n.times do |i|
  a[i][1..-1].each do |x|
    cnt[x] += 1
  end
end
ans = 0
cnt.each do |x|
  ans += 1 if x == n
end
puts ans


Measured memory_bytes: 14348
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static const ll INF=1000000000000000;
using P=pair<ll,ll>;
ll N;
int main(){
  cin>>N;
  vector<P>A(N);
  for(ll i=0;i<N;i++){
  ll x,y;cin>>x>>y;P p(x,y);
    A[i]=p;
  }ll M1=-INF;ll M2=-INF;ll m1=INF;ll m2=INF;
  for(ll i=0;i<N;i++){
  ll x=A[i].first;ll y=A[i].second;
    if(M1<x+y)M1=x+y;
    if(x+y<m1)m1=x+y;
   if(M2<x-y)M2=x-y;
    if(x-y<m2)m2=x-y;
   }ll ans=max(M1-m1,M2-m2);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 6420
#include "bits/stdc++.h"
#include <random>
#include <algorithm>
#include <unordered_set>
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
#define ld long double
#define Sort(a) sort(a.begin(),a.end())
#define cSort(a,cmp) sort(a.begin(),a.end(),cmp)
#define reSort(a) sort(a.rbegin(), a.rend())
static const ll llMAX = numeric_limits<long long>::max();
static const int intMAX = numeric_limits<int>::max();
static const ll  llMIN = numeric_limits<long long>::min();
static const int intMIN = numeric_limits<int>::min();
static const ll d_5 = 100000;
static const ll d9_7 = 1000000007;
static const ll d_9 = 1000000000;
static const double PI=3.14159265358979323846;
template<class T>
T gcd(T a,T b){
  if(a==0){
    return b;

  }else if(b==0){
    return a;
  }
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}
ll digitpower(ll a,ll b){//aのb乗を計算
  if(b==1){
    return a;
  }else if(b==0){
    return 1;
  }
  int mode=1;
  if(mode==0){
    if(b%2==1){
      ll tmp = digitpower(a,(b-1)/2);
      tmp%=d9_7;
      tmp*=tmp;
      tmp%=d9_7;
      tmp*=a;
      return (tmp)%d9_7;
    }else{
      ll tmp = digitpower(a,(b)/2);
      tmp%=d9_7;
      tmp*=tmp;
      tmp%=d9_7;
      return (tmp)%d9_7;
    }
  }else{
    if(b%2==1){
      ll tmp = digitpower(a,(b-1)/2);
      tmp*=tmp;
      tmp*=a;
      return (tmp);
    }else{
      ll tmp = digitpower(a,(b)/2);
      tmp*=tmp;
      return (tmp);
    }
  }
  return 0;
  
}
template<class T>
void Printvector(std::vector<T> &a){
  int size = a.size();
  rep(i,size){
    cout<<a[i]<<" ";
  }
  cout<<endl;
}
template<class T>
void Printvector(std::vector<std::vector<T>> &a){
  int size = a.size();
  rep(i,size){
    int size2=a[i].size();
    rep(j,size2){
      cout<<a[i][j]<<" ";
    }
    cout<<endl;
  }
  cout<<endl;
}
//自身を除く約数の列挙
unordered_set<ll> primes(ll n){
  unordered_set<ll> ret;
  for(ll i=2;i*i<=n;i++){
    if(n%i==0){
      ret.insert(i);
      ret.insert(n/i);
    }
  }
  return ret;
}
int main(void){
  ll n;
  cin>>n;
  if(n==2){
    cout<<1<<endl;
    return 0;
  }
  unordered_set<ll> p=primes(n);
  p.insert(n);
  ll ans=0;
  for(auto i:p){
    ll n2=n;
    while(n2%i==0){
      n2/=i;
    } 
    if(n2%i==1){
      ans++;
    }
  }

  ll n3=n;
  unordered_set<ll>p3=primes(n3-1);
  p3.insert(n3);
  ans+=p3.size();
  cout<<ans<<endl;
  return 0;
}

//<<std::setprecision(30)

//重複削除
 /* std::sort(vec.begin(), vec.end());
 
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());*/

  //ペアの全探索
  /*do{
		int s=0;
		for(int i=0;i<n/2;i++)s+=v[i]^v[i+n/2];
		r=max(s,r);
		reverse(v.begin()+n/2,v.end());
	}while(next_permutation(v.begin(),v.end()));*/


Measured memory_bytes: 512
#include<bits/stdc++.h> 
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
ll gcd(ll a,ll b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
bool isprime(ll n)
{
    for(ll i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
ll visited[100005]={0};
ll dp[100005]={0};
ll max1=0;
ll dfs(ll current,vector<ll>graph[])
{
	visited[current]=1;
	for(ll i=0;i<graph[current].size();i++)
	{
		ll node=graph[current][i];
		if(!visited[node])
		{
			dp[current]=max(dp[current],1+dfs(node,graph));
		}
		else
		 dp[current]=max(dp[current],1+dp[node]);
	}
	return dp[current];
}
int main()
{
	ll n,m,i;
	cin>>n>>m;
	vector<ll>graph[n+1];
	for(i=0;i<m;i++)
	{
		ll u,v;
		cin>>u>>v;
		graph[u].pb(v);
	}
	for(i=1;i<=n;i++)
	{
		if(visited[i]==0)
		max1=max(max1,dfs(i,graph));
	}
	cout<<max1;
	return 0;
}

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

int n, m, result = 0;

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

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

 
int main() 
{
	
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  long long n;
  cin>>n;
  vector<long long> v(n),ans(n);
  for(long long i=0;i<n;++i)
      cin>>v[i];
  
  for(int i=n-1;i>=0;--i)
  {
    if(i>n/2)
    {
      ans[i] = v[i];
    }
    else if(i==0)
    {
      continue;
    } else 
    {
      long long index=i+i+1;
      long long cnt =0;
      while(index<n){
        cnt += ans[index];
        index += i+1;
      }
      if(cnt%2==v[i])
      {
        ans[i] = 0;
      }
      else
      {
        ans[i] = 1;
      }
    }
  }
  long long cnt = accumulate(ans.begin()+1,ans.end(),0);
  if(cnt%2==v[0])
  {
    ans[0] = 0;
  }
  else 
  {
    ans[0] = 1;
    ++cnt;
  }
  
  cout << cnt << endl;
  for(int i=0;i<n;++i){
    if(ans[i]==1)
      cout << i+1 << " ";
  }
  return 0;
}
 

Measured memory_bytes: 3968
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main() {
	vector<int> card(5);
	char c;
	while (cin >> card[0] >> c >> card[1] >> c >> card[2] >> c >> card[3] >> c >> card[4]){
		SORT(card);
		int pair = 0;
		for (int i = 0; i < 4;i++){
			for (int j = i + 1; j < 5; j++){
				if (card[i] == card[j])
					pair++;
			}
		}
		bool st = true;
		REP(i, 4){
			if (card[i] + 1 != card[i + 1])
				st = false;
		}
		if (card[0] == 1 && card[1] == 10 && pair == 0)
			st = true;
		if (pair == 6)
			cout << "four card" << endl;
		else if (pair==4)
			cout << "full house" << endl;
		else if (st )
			cout << "straight" << endl;
		else if (pair==3 )
			cout << "three card" << endl;
		else if (pair==2 )
			cout << "two pair" << endl;
		else if (pair==1 )
			cout << "one pair" << endl;
		else
			cout << "null" << endl;
	}
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n

typedef long long ll;

typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<string> vs;

typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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

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

ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll n,a,ans=0;
	deque<ll> d;
	cin >> n;
	rep(i,n){
		cin >> a;
		d.pb(a);
	}
	while(!d.empty()){
		ll tmp=d.front();
		d.pop_front();
		if(tmp<d.front()){
			while(tmp<=d.front() && !d.empty()){
				tmp=d.front();
				d.pop_front();
			}
			ans++;
		}
		else if(tmp>d.front()){
			while(tmp>=d.front() && !d.empty()){
				tmp=d.front();
				d.pop_front();
			}
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
<?php
  $s = trim(fgets(STDIN));
  $ans = "";
  for($i=0; $i<strlen($s); $i++){
      if($s[$i] == "B"){
          $ans = substr($ans,0,strlen($ans)-1);
      }else{
          $ans .= $s[$i];
      }
  }
  
  echo $ans."\n";

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

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

struct frac
{
	int a, b;

	frac() { }
	frac(int _a, int _b): a(_a), b(_b) { }

	friend bool operator<(const frac &a, const frac &b)
	{
		return (LL)a.a * b.b < (LL)b.a * a.b;
	}

};

int sz[3], D;

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d%d%d%d", sz, sz + 1, sz + 2, &D);
	int cur[3] = {0};
	int ans = (LL)min(sz[0], D + 1) * min(sz[1], D + 1) % Mod * min(sz[2], D + 1) % Mod;
	priority_queue<pair<frac, int>, vector<pair<frac, int> >, greater<pair<frac, int> > > q;
	q.push(mp(frac(1, sz[0]), 0));
	q.push(mp(frac(1, sz[1]), 1));
	q.push(mp(frac(1, sz[2]), 2));
	while (!q.empty())
	{
		int x; 
		frac val;
		{
			auto tmp = q.top(); q.pop();
			val = tmp.x;
			x = tmp.y;
		}
		int w[3];
		REP(i, 0, 3)
		{
			int tmp = 1;
			REP(j, 0, 3) if (j != i)
			{
				int l = max(0, cur[j] - D), r = min(cur[j] + D, sz[j] - 1);
				tmp = (LL)tmp * (r - l + 1) % Mod;
			}
			w[i] = tmp;
		}
		REP(i, 0, 3)
		{
			int l = cur[i], r = sz[i] - 1;
			while (l < r)
			{
				int mid = (l + r + 1) >> 1;
				if (val < frac(mid, sz[i])) r = mid - 1;
				else l = mid;
			}
			if (cur[i] + D < sz[i])
			{
				int lim = sz[i] - D - 1;
				(ans += LL(min(l, lim) - cur[i]) * w[i] % Mod) %= Mod;
			}
			cur[i] = l;
		}
		if (cur[x] + 1 < sz[x]) 
		{
			if (cur[x] == D + 1)
			{
				q.push(mp(frac(max(sz[x] - D - 1, cur[x] + 1), sz[x]), x));
			}
			else 
			{
				q.push(mp(frac(cur[x] + 1, sz[x]), x));
			}
		}
	}
	(ans += Mod) %= Mod;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#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 a,b,c;
  cin >> a >> b >> c;
  int mi = min({a,b,c}),ma = max({a,b,c});
  int v[] = {a,b,c};
  int ans = 1e9;
  for(int x = mi;x<=ma;++x){
    int res = 0;
    rep(i,3){
      if(v[i]>x){
        res += v[i]-x;
      }else{
        res += (x-v[i]+1)/2;
        if((x-v[i])%2) ++res;
      }
    }
    ans = min(ans,res);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    string s;
    cin >> s;

    cout << s.substr(0, 3) << endl;

    return 0;
}

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

const int NMAX = 105;
int n, d[NMAX][2];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> d[i][0] >> d[i][1];
    }
    bool ok = 0;
    for(int i = 1; i <= n - 2 && !ok; i++) {
        if(d[i][0] == d[i][1] && d[i + 1][0] == d[i + 1][1] && d[i + 2][0] == d[i + 2][1]) {
            ok = 1;
        }
    }
    if(ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

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

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		int sum = 0;
		int tmp = i;
		while(tmp) {
			sum += tmp%10;
			tmp /= 10;
		}
		if(sum >= a && sum <= b) ans += i;
	}
	cout << ans << endl;
	return 0;
}

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


/*
 *X=10
 *A= ,B= A^5-B^5=
 *X=N
 *A=N,B=N-1 A^5-B-5>=10**9
 */
int main()
{
	ll X;
	cin>>X;
	ll A,B;
	A=-1;
	B=-1;
	for(ll a=-120;a<=120;a++)
	{
		for(ll b=-120;b<=120;b++)
		{
			if(pow(a,5)-pow(b,5)==X)
			{
				A=a;
				B=b;
			}
		}
	}
	cout<<A<<" "<<B<<endl;
	return 0;
}


Measured memory_bytes: 4064
a = input()
b = input()

for i in range(len(a) - len(b) + 1):
    f = True
    for j in range(len(b)):
        if a[i+j] == b[j]:
            pass
        else:
            if b[j] == '_':
                pass
            else:
                f = False
                break
    if f:
        print('Yes')
        exit()
print('No')


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

int main() {
 int n;
 cin >> n;
 
 vector<int> a(n);
 rep(i,n) {
  cin >> a.at(i);
 }
        
 int count = 0;
 for(int i = 0; i < n - 2; i++) {
  if( (a.at(i) < a.at(i + 1) && a.at(i + 1) < a.at(i + 2)) || (a.at(i) > a.at(i + 1) && a.at(i + 1) > a.at(i + 2))  ) {
   count++;}
 }
        
        cout << count;
}

Measured memory_bytes: 3596
#include <iostream>
#include <cstdint>
#include <vector>

int main() {
  std::int_fast64_t n, m;
  std::cin >> n >> m;
  std::vector<std::int_fast64_t> road_counts(n, 0);
  for (std::int_fast64_t i = 0; i < m; ++i) {
    std::int_fast64_t a, b;
    std::cin >> a >> b;
    ++road_counts[a - 1];
    ++road_counts[b - 1];
  }
  for (const std::int_fast64_t& road_count : road_counts) {
    std::cout << road_count << std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

const int sz = 1000010;
int arr[sz] = {};
int cnt[sz] = {};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin, n;

    REP(i, 0, n) {
        int a;
        cin, a;
        arr[a]++;
    }

    vector<int> x;
    REP(i, 0, sz) {
        if (arr[i] > 0) {
            x.push_back(i);
        }
    }

    int ans = 0;
    n = x.size();

    REP(i, 0, n) {
        for (int j = 2 * x[i]; j < sz; j += x[i]) {
            cnt[j]++;
        }
    }

    REP(i, 0, n) {
        if (arr[x[i]] != 1) continue;
        ans += (cnt[x[i]] == 0);
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 11880
#include<bits/stdc++.h>
using namespace std;
int main(){
  double t,d,ta,tb,da,db;
  cin>>t>>d>>ta>>tb>>da>>db;
  double ans=1e9;
  for(int i=0;i<=1000;i++)
    for(int j=0;j<=1000;j++){
      double va=da*i;
      double vb=db*j;
      if(va+vb>d||i+j==0)continue;
      ans=min(ans,abs(t-(ta*va+tb*vb)/(va+vb)));
    }
  printf("%.10lf\n",ans);
  return 0;
}



Measured memory_bytes: 3284
package main
  
import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    bs := make([][]int, n)
    for i := 0; i < n; i++ {
        var x, y int
        fmt.Scan(&x, &y)
        bs[i] = []int{x, y}
    }
    tm := make(map[string]int)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            tm[diff(bs[i], bs[j])]++
            tm[diff(bs[j], bs[i])]++
        }
    }
    var max int
    for _, v := range tm {
        if v > max {
            max = v
        }
    }
    fmt.Println(n - max)
}

func diff(a, b []int) string {
    dx, dy := a[0]-b[0], a[1]-b[1]
    return fmt.Sprintf("%d,%d", dx, dy)
}


Measured memory_bytes: 896
#include <iostream>
#include <algorithm>

using namespace std;

long long data1[100000] = {};
long long data2[100000] = {};
long long data3[100000] = {};

int main()
{
	long long n, cnt = 0;
	cin >> n;
	for (long long i = 0; i < n; i++)
	{
		cin >> data1[i];
	}
	for (long long i = 0; i < n; i++)
	{
		cin >> data2[i];
	}
	for (long long i = 0; i < n; i++)
	{
		cin >> data3[i];
	}
	//
	sort(data1, data1 + n);
	sort(data2, data2 + n);
	sort(data3, data3 + n);
	//
	for (long long i = 0; i < n; i++)
	{
		long long min = 0, max = n - 1;
		long long x = -1;
		long long min2 = 0, max2 = n - 1;
		long long x2 = -1;
		long long ans, ans2;
		while (min <= max)
		{
			x = ((max + min) / 2);
			if (data2[i] > data1[x])
			{
				min = x + 1;
			}
			else
			{
				max = x - 1;
			}
		}
		ans = min;
		while (min2 <= max2)
		{
			x2 = ((max2 - min2) / 2) + min2;
			if (data2[i] >= data3[x2])
			{
				min2 = x2 + 1;
			}
			else
			{
				max2 = x2 - 1;
			}
		}
		ans2 = min2;
		cnt += ans * (n - ans2);
	}
	cout << cnt;
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define print(x) cout << (x) << endl;
#define printa(x, n) for(ll i = 0; i < n; i++) {cout << (x[i]) << " ";} cout << endl;
using namespace std;
using ll = long long;

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

    rep (i, s.size()) {
        if (i == s.size() - 1) {
            s[i] = char(((s[i] - 'a') + k) % 26 + 97);
            break;
        }
        if (s[i] == 'a') continue;
        if ((26 - (int)(s[i] - 'a')) - k <= 0) {
            k -= 26 - (int)(s[i] - 'a');
            s[i] = 'a';
        }
    }
    
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const ll MOD = 1000000007LL;
//const long double PI = (acos(-1));
//const long double EPS = 0.0000000001;

const int MAX_N = 100050;
ll n, k;
vector<int> adj[MAX_N];

ll dfs(int here, int from) {
	if(from == -1) {
		ll ret = 1LL;
		int c = adj[here].size();
		rep(i,0,c) {
			ret *= (k-1-i);
			ret %= MOD;
		}
		rep(i,0,sz(adj[here])) {
			int there = adj[here][i];
			ret *= dfs(there, here);
			ret %= MOD;
		}
		return ret;
	}

	ll ret = 1LL;
	int c = adj[here].size()-1;
	rep(i,0,c) {
		ret *= (k-2-i);
		ret %= MOD;
	}
	rep(i,0,sz(adj[here])) {
		int there = adj[here][i];
		if(there == from) continue;
		ret *= dfs(there, here);
		ret %= MOD;
	}
	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> n >> k;
	rep(i,0,n-1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	ll ret = k * dfs(0,-1);
	ret %= MOD;
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 10368
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Math.max;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void solve() throws Exception {
		int n = scanInt();
		int pi[] = new int[n];
		for (int i = 0; i < n; i++) {
			pi[scanInt() - 1] = i;
		}
		int ans = 0;
		for (int i = 0, j; i < n; i = j) {
			for (j = i + 1; j < n && pi[j] > pi[j - 1]; j++) { }
			ans = max(ans, j - i);
		}
		out.print(n - ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

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

int main(void) {
    int N;
    string s;
    int maxnochange = 0;
    int nochange;
    cin >> N >> s;

    vector<int> esum(N);
    vector<int> wsum(N);
    int e = 0,w = 0;
    for(int i=0;i<N;i++) {
        if(s[i] == 'E') {
            e++;
        }
        esum[i] = e;
    }
    for(int i=N-1;i>=0;i--) {
        if(s[i] == 'W') {
            w++;
        }
        wsum[i] = w;
    }

    // 累積和を取って
//(gdb) p esum 
//$1 = std::vector of length 12, capacity 12 = {0, 1, 1, 2, 2, 3, 4, 5, 5, 5, 5, 6}
//(gdb) p wsum 
//$2 = std::vector of length 12, capacity 12 = {1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 6, 6}
    for(int i=0;i<N;i++) {
        nochange = 0;
        // 左側で右を向いている人を加算
        if(i) {
            nochange += esum[i-1];
        }

        // 右側で左を向いている人を加算
        if(i != (N-1)) {
            nochange += wsum[i+1];
        }
//printf("i:%d m:%d\n", i, maxnochange);
        if(maxnochange < nochange) {
            maxnochange = nochange;
        }
    }

    cout << N - maxnochange - 1 << endl;

    return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using Int = long long;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
using namespace std;
struct Data {
    Int x, y, h;
    Int valid(Int cx, Int cy, Int ch) {
        return max(ch - abs(cx - x) - abs(cy - y), 0LL) == h;
    }
};

int main() {
    int n;
    cin >> n;
    auto v = vector<Data>();
    auto maxH = 0LL;
    rep(i, n) {
        Int x, y, h;
        cin >> x >> y >> h;
        v.push_back(Data{x, y, h});
        maxH = max(maxH, h);
    }
    rep(cx, 101) {
        rep(cy, 101) {
            rep(ch, 202) {
                auto flag = true;
                for (auto d : v) {
                    if (!d.valid(cx, cy, maxH + ch)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    printf("%d %d %lld\n", cx, cy, maxH + ch);
                    return 0;
                }
            }
        }
    }
}


Measured memory_bytes: 256
#[allow(dead_code)]
const MOD: usize = 1_000000000 + 7;

fn main() {
    let mut cin = Scanner::new();
    let a = cin.next_isize();
    let b = cin.next_isize();
    let c = cin.next_isize();
    let ans = if a == b {
        c
    } else if a == c {
        b
    } else {
        a
    };
    println!("{}", ans);
}


struct Scanner {
    reader: std::io::Stdin,
    tokens: std::collections::VecDeque<String>,
}

impl Scanner {
    fn new() -> Self {
        Scanner {
            reader: std::io::stdin(),
            tokens: std::collections::VecDeque::new(),
        }
    }

    fn next(&mut self) -> String {
        if self.tokens.is_empty() {
            let mut s = String::new();
            loop {
                self.reader.read_line(&mut s).ok();
                let s = s.trim();
                if s.len() != 0 {
                    for it in s.split_whitespace() {
                        self.tokens.push_back(it.into())
                    }
                    break;
                }
            }
        }
        self.tokens.pop_front().unwrap()
    }

    fn next_generics<T>(&mut self) -> T where
        T: std::str::FromStr + std::marker::Copy,
        <T as std::str::FromStr>::Err: std::fmt::Debug
    {
        self.next().parse().unwrap()
    }
    
    #[allow(dead_code)] fn next_i32(&mut self) -> i32 { self.next_generics::<i32>() }
    #[allow(dead_code)] fn next_i64(&mut self) -> i64 { self.next_generics::<i64>() }
    #[allow(dead_code)] fn next_u64(&mut self) -> u64 { self.next_generics::<u64>() }
    #[allow(dead_code)] fn next_usize(&mut self) -> usize { self.next_generics::<usize>() }
    #[allow(dead_code)] fn next_isize(&mut self) -> isize { self.next_generics::<isize>() }
}



Measured memory_bytes: 4352
/* 
Hey there stalker....
 
█▀▀▄░░░░░░░░░░░▄▀▀█
░█░░░▀▄░▄▄▄▄▄░▄▀░░░█
░░▀▄░░░▀░░░░░▀░░░▄▀
░░░░▌░▄▄░░░▄▄░▐▀▀
░░░▐░░█▄░░░▄█░░▌▄▄▀▀▀▀█ 
░░░▌▄▄▀▀░▄░▀▀▄▄▐░░░░░░█
▄▀▀▐▀▀░▄▄▄▄▄░▀▀▌▄▄▄░░░█
█░░░▀▄░█░░░█░▄▀░░░░█▀▀▀
░▀▄░░▀░░▀▀▀░░▀░░░▄█▀
░░░█░░░░░░░░░░░▄▀▄░▀▄
░░░█░░░░░░░░░▄▀█░░█░░█
░░░█░░░░░░░░░░░█▄█░░▄▀
░░░█░░░░░░░░░░░████▀
░░░▀▄▄▀▀▄▄▀▀▄▄▄█▀
 
Like what you see?
*/
#include <bits/stdc++.h>
using namespace std;
 
#define fastIO ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
#define ld long double
#define lli long long int
#define p_b push_back
#define m_p make_pair
#define fs first
#define sc second
#define all(x) x.begin(),x.end()
#define fr(i,a,n) for(lli i=a; i<n; i++)
#define fre(i,a,n) for(lli i=a; i<=n; i++)
const lli mod = 1e9 + 7;
/*****************************************************/
void lcs( string X, string Y, int m, int n ) 
{ 
   int L[m+1][n+1]; 
   for (int i=0; i<=m; i++) 
   { 
     for (int j=0; j<=n; j++) 
     { 
       if (i == 0 || j == 0) 
         L[i][j] = 0; 
       else if (X[i-1] == Y[j-1]) 
         L[i][j] = L[i-1][j-1] + 1; 
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]); 
     } 
   }
   int index = L[m][n]; 
    char lcs[index+1]; 
   lcs[index] = '\0'; 
   int i = m, j = n; 
   while (i > 0 && j > 0) 
   { 
      if (X[i-1] == Y[j-1]) 
      { 
          lcs[index-1] = X[i-1]; 
          i--; j--; index--;   
      } 
        else if (L[i-1][j] > L[i][j-1]) 
         i--; 
      else
         j--; 
   }  
   cout <<lcs; 
} 
int main()
{
    fastIO
    string s1,s2,s="";
    cin>>s1;
    cin>>s2;
    lcs(s1,s2,s1.length(),s2.length());
    //cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;
    return 0; 
} 

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

cnt = 0

jug = 2
for i in range(n - 1):
    if jug == 2:
        if a[i] < a[i+1]:
            jug = 0
        elif a[i] > a[i+1]:
            jug = 1 
    elif jug == 0:
        if a[i] > a[i+1]:
            jug = 2
            cnt += 1
    elif jug == 1:
        if a[i] < a[i+1]:
            jug = 2
            cnt +=1
print(cnt+1)

Measured memory_bytes: 62704
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef long long ll;
ll MOD = 1000000007;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

	ll n, k, kind_sum = 0, erased_sum=0, erased_kind=0;
	cin >> n >> k;
	vector<ll>a(n), cnt(200010, 0);
	rep(i, n)cin >> a[i];
	for (ll i = 0; i < n; i++) {
		cnt[a[i]]++;
	}
	sort(all(cnt));
	kind_sum += cnt.size() - count(all(cnt), 0);
	rep(i, cnt.size()) {
		if (kind_sum - erased_kind <= k)return cout << erased_sum << endl, 0;
		else erased_sum += cnt[i],erased_kind += cnt[i] <= 0 ? 0 : 1;
	}
}


Measured memory_bytes: 3456
a,b,m = map(int,input().split())
alist = list(int(x) for x in input().split())
blist = list(int(x) for x in input().split())
x = []
y = []
c = []
for i in range(m):
  inp1,inp2,inp3 = map(int,input().split())
  x.append(inp1)
  y.append(inp2)
  c.append(inp3)
mini = min(alist) ++ min(blist)
for i in range(m):
  if alist[x[i]-1] + blist[y[i]-1] - c[i] < mini:
    mini = alist[x[i]-1] + blist[y[i]-1] - c[i]
print(mini)

Measured memory_bytes: 24804
a = []
a = input().split()
K = int(a[0])
N = int(a[1])
#print('K=', K, 'N=', N)
A = []
A = input().split()
A = [int(i) for i in A]
#print('A=', A)

l = []

for i in range(len(A)-1):
  l.append(A[i+1] - A[i])
l.append(K - A[len(A)-1] + A[0])

#print('l=', l)

M = max(l)

#print('M=', M)

print(K - M)


Measured memory_bytes: 26444
using System;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int k = int.Parse(Console.ReadLine());
            string[] line = Console.ReadLine().Split(' ');
            int a = int.Parse(line[0]);
            int b = int.Parse(line[1]);

            for(int i=a; i<=b; i++){
                if(i%k==0){
                    Console.WriteLine("OK");
                    return;
                }
            }
            Console.WriteLine("NG");
        }
    }
}


Measured memory_bytes: 17856
def chebyshev_0(a, b):
    return a - b
def chebyshev_1(a, b):
    return a + b

N = int(input())
X = [0] * N
Y = [0] * N

for i in range(N):
    X[i], Y[i] = map(int, input().split())

max_0 = - (10 ** 9) - 1
min_0 = 2 * (10 ** 9)
for x, y in zip(X, Y):
    if chebyshev_0(x, y) > max_0:
        max_0 = chebyshev_0(x, y)
    if chebyshev_0(x, y) < min_0:
        min_0 = chebyshev_0(x, y)
l0 = abs(max_0 - min_0)

max_1 = - (10 ** 9) - 1
min_1 = 2 * (10 ** 9)
for x, y in zip(X, Y):
    if chebyshev_1(x, y) > max_1:
        max_1 = chebyshev_1(x, y)
    if chebyshev_1(x, y) < min_1:
        min_1 = chebyshev_1(x, y)
l1 = abs(max_1 - min_1)

print(max([l0, l1]))


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

int main(){
  string S;
  cin >> S;
  int one, zero;
  one = 0; 
  zero = 0;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == '0'){
      zero++;
    }
    if(S[i] == '1'){
      one++;
    }
  }
  cout << min(zero,one) * 2 << endl;
}

Measured memory_bytes: 512
def traverse
	
		a = []
		len = 1
		now = 0
		$list[now] = 1
		loop{
		$n.times do |i|
			if $m[now][i] == 1 && $list[i] == 0
				a << [i, len + 1]
				$data[i].len = len
				$list[i] = 1
			end
		end
	 return nil	if a.empty?
		nex = a.shift
		now = nex[0]
		len = nex[1]
	}
end

D = Struct.new(:len)
$n = gets.to_i
$time = 0
$m = Array.new($n){Array.new($n){0}}
$data = Array.new($n){D.new(-1)}
$list = Array.new($n){0}
$n.times do
	s = gets.split.map(&:to_i)
	i = s[0] - 1
	s[1].times do |l|
		j = s[l + 2] - 1
		$m[i][j] = 1 
	end
end
$data[0].len = 0
traverse



$n.times do |i|
	puts "#{ i + 1 } #{$data[i].len}"
end

Measured memory_bytes: 8708
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = pair<ii, int>;
#define vt vector
#define pq priority_queue
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define __lcm(a, b) a * b / __gcd(a, b)
// #define multicase
const int MOD = 1e6;
const int INF = 2e9;
// const int N = ;

int k, a, b;

void solve() {
    int T = 1;
  #ifdef multicase
    cin >> T;
  #endif
    while(T--) {
        cin >> k >> a >> b;
        for(int i = a; i <= b; i++) {
            if(i % k == 0) {
                cout << "OK\n";
                return;
            }
        }
        cout << "NG\n";
    }
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    solve();
    
}

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

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

// Graph
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  ll sum = 0;
  ll mul = 1;
  int digitsNum = 1;
  vector<ll> sum26(15);
  for (int i = 1; i < 15; i++)
  {
    mul *= 26;
    sum += mul;
    sum26[i] = sum;
    if (N <= sum)
    {
      digitsNum = i;
      break;
    }
  }
  ll k = N - sum26[digitsNum - 1];
  k--;
  cerr << k << endl;
  string ans;
  while (k > 0)
  {
    ans += (char)('a' + (k % 26));
    k /= 26;
  }
  while ((int)ans.size() < digitsNum)
  {
    ans += 'a';
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>
#include <stdlib.h>
int main(){
    int n,a=0;
    scanf("%d",&n);
    int p[n];
    for(int i=0;i<n;i++)scanf("%d",&p[i]);
    for(int i=1;i<n-1;i++){
        if((p[i-1]<p[i]&&p[i]<p[i+1])||(p[i+1]<p[i]&&p[i]<p[i-1]))a++;
    }
    printf("%d",a);
    return 0;
}

Measured memory_bytes: 128
<?php
$input = trim(fgets(STDIN));

list($N, $X) = explode(' ', $input);

$input = trim(fgets(STDIN));
$xs = explode(' ', $input);

$distances = [];
$begin = $X;
foreach($xs as $x) {
    $distance = abs($x - $begin);
    $distances[] = $distance;
    $begin = $x;
}

$distanceA = array_pop($distances);
foreach($distances as $distanceB) {
    $distanceA = gcd($distanceA, $distanceB);
}

echo $distanceA;

function gcd($a, $b) {
    if ($b === 0) return $a;

    return gcd($b, $a % $b);
}


Measured memory_bytes: 18932
n,q = map(int,input().split())

ki = [[] for _ in range(n)] 
for _ in range(n - 1):
    a, b = map(int, input().split())
    ki[a - 1].append(b-1)
    ki[b - 1].append(a-1)

counter = [0 for _ in range(n)] 

for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

qux = [0]

while qux:
    x = qux.pop()
    for ko in ki[x]:
        counter[ko] += counter[x]
        qux.append(ko)
        ki[ko].remove(x)

print(" ".join(map(str,counter)))

Measured memory_bytes: 65312
/*
    In the name of Allah

    MohammadErfan Gooneh

*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

#define endl                        '\n'
#define all(a, n)                   for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
#define IOS                         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7;
int main() {
    IOS ;
    int a ;
    string s ;
    cin >> a >> s; 
    if(a < 3200)cout << "red" ; 
    else cout << s ;























return 0 ;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll MOD=10000000;
const ll INF=1000000001;
const ll LINF=4000000000000000010;
const double EPS=1e-9;
int d,g;
int p[11],c[11];
int main(){
    int ans=INF;
    cin>>d>>g;
    for(int i=0;i<d;i++){
        cin>>p[i]>>c[i];
    }
    for(int i=0;i<(1<<d);i++){
        int co=0,s=0;
        for(int j=0;j<d;j++){
            if(i&(1<<j)){
                s+=100*(j+1)*p[j];
                s+=c[j];
                co+=p[j];
            }
        }
        for(int j=d-1;j>=0;j--){
            if(i&(1<<j))continue;
            if(s>=g)break;
            for(int k=0;k<p[j]-1;k++){
                if(s>=g)break;
                s+=100*(j+1);
                co++;
            }
        }
        if(s>=g){
            ans=min(co,ans);
        }
    }
    cout<<ans<<endl;
}


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

using namespace std;

const int CMax = 102;

int n, m, ats;
string S[CMax];

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

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (S[i][j] == '.') {
                ats = 0;
                if (i - 1 >= 0 && S[i-1][j] == '#') ats++;
                if (j - 1 >= 0 && S[i][j-1] == '#') ats++;
                if (i + 1 < n && S[i+1][j] == '#') ats++;
                if (j + 1 < m && S[i][j+1] == '#') ats++;
                if (i - 1 >= 0 && j - 1 >= 0 && S[i-1][j-1] == '#') ats++;
                if (i - 1 >= 0 && j + 1 < m && S[i-1][j+1] == '#') ats++;
                if (i + 1 < n && j + 1 < m && S[i+1][j+1] == '#') ats++;
                if (i + 1 < n && j - 1 >= 0 && S[i+1][j-1] == '#') ats++;

                S[i][j] = (char)(ats + '0');
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << S[i] << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
  int K;
  cin >> K;
  long long ans = 0;;
  for (int i = 1; i<=K; i++){
    for (int j = 1; j<=K; j++){
      for(int k = 1; k<=K; k++){
         ans += __gcd(__gcd(i,j),k);
      }
    }
  }

  cout << ans << endl;

}

Measured memory_bytes: 3644