akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

const int INF = (int)1e18;

signed main(){
	int L;
	cin >> L;
	vector<int> A(L + 2);
	for(int i = 1; i <= L; ++i) {
		cin >> A[i];
	}
	vector<vector<int>> dp(L + 1, vector<int>(5, INF));
	dp[0].assign(5, 0);
	for(int i = 1; i <= L; ++i) {
		int r = dp[i - 1][0];

		dp[i][0] = r + A[i];

		r = min(r, dp[i - 1][1]);
		
		int a = 0;
		if (A[i] == 0) {
			a = 2;
		} else if(A[i] % 2 == 1) {
			a = 1;
		}
		dp[i][1] = r + a;

		r = min(r, dp[i - 1][2]);
		int b = A[i] % 2 == 0 ? 1 : 0;
		dp[i][2] = r + b;

		r = min(r, dp[i - 1][3]);
		dp[i][3] = r + a;

		r = min(r, dp[i - 1][4]);
		dp[i][4] = r + A[i];
	}

	int res = dp[L][0];
	for(auto a: dp[L])
		res = min(res, a);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 15872
import java.util.*;

public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main(){
		new AOJ0036().doIt();
	}
	
	class AOJ0036{
		boolean map[][];
		int ax[] = {0,1,0,1};
		int ay[] = {0,0,1,1};
		int bx[] = {0,0,0,0};
		int by[] = {0,1,2,3};
		int cx[] = {0,1,2,3};
		int cy[] = {0,0,0,0};
		int dx[] = {0,0,-1,-1};
		int dy[] = {0,1,1,2};
		int ex[] = {0,1,1,2};
		int ey[] = {0,0,1,1};
		int fx[] = {0,0,1,1};
		int fy[] = {0,1,1,2};
		int gx[] = {0,1,0,-1};
		int gy[] = {0,0,1,1};
		char test(int x,int y){
			int cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+ax[i];
				int ny = y+ay[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'A';
			cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+bx[i];
				int ny = y+by[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'B';
			cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+cx[i];
				int ny = y+cy[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'C';
			cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'D';
			cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+ex[i];
				int ny = y+ey[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'E';
			cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+fx[i];
				int ny = y+fy[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'F';
			cnt = 0;
			for(int i=0;i<4;i++){
				int nx = x+gx[i];
				int ny = y+gy[i];
				if(nx<0||nx>=8||ny<0||ny>=8)continue;
				if(map[ny][nx]==false)continue;
				cnt++;
			}
			if(cnt==4)return 'G';
			return 'X';
		}
		
		void solve(){
			char result = ' ';
			for(int i=0;i<8;i++)for(int s=0;s<8;s++){
				char a = test(s, i);
				if(a!='X')result = a;
			}
			System.out.println(result);
		}
		
		void doIt(){
			while(in.hasNext()){
				map = new boolean[8][8];
				for(int i=0;i<8;i++){
					String text = in.next();
					for(int s=0;s<8;s++){
						if(text.charAt(s)=='1')map[i][s] = true;
						else map[i][s] = false;
					}
				}
//				
//				for(int i=0;i<8;i++){
//					for(int s=0;s<8;s++)System.out.print(map[i][s]? "1":"0");
//					System.out.println();
//				}
				
				solve();
				
			}
		}
	}
	
}

Measured memory_bytes: 21364
#include <stdio.h>

int main(void)
{
    int a, b, c, max, mid, min;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);

    if (a <= b && a <= c && b <= c)
    {
        max = c;
        mid = b;
        min = a;
    }
    if (a <= b && a <= c && c <= b)
    {
        max = b;
        mid = c;
        min = a;
    }
    if (b <= a && b <= c && a <= c)
    {
        max = c;
        mid = a;
        min = b;
    }
    if (b <= a && b <= c && c <= a)
    {
        max = a;
        mid = c;
        min = b;
    }
    if (c <= a && c <= b && b <= a)
    {
        max = a;
        mid = b;
        min = c;
    }
    if (c <= a && c <= b && a <= b)
    {
        max = b;
        mid = a;
        min = c;
    }
    printf("%d", (max * 10 + mid) + min);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

using namespace std;

struct UnionFind{
    vector<ll> par;
    vector<ll> rank;
    vector<ll> sizeth;
    
    void init(ll N){
        rep(i, N){
            par.push_back(i);
            rank.push_back(0);
            sizeth.push_back(1);
        }
    }
    
    ll root(ll x) {
        if(par[x]==x) return x;
        else return par[x]=root(par[x]);
    }
    
    bool isSame(ll x, ll y) {
        return root(x)==root(y);
    }
    
    bool merge(ll x, ll y) {
        x=root(x);
        y=root(y);
        if(x==y) return false;
        if(rank[x]>rank[y]) swap(x, y);
        sizeth[y] += sizeth[x];
        par[x]=y;
        if(rank[x]==rank[y]) rank[x]++;
        return true;
    }
    
    ll size(ll x){
        return sizeth[root(x)];
    }
};

int main(void){
    ll N, M;
    stack< pair<ll, ll> > bridges;
    stack<ll> answ;
    
    cin>>N>>M;
    ll A, B;
    rep(i, M){
        cin>>A>>B;
        bridges.push({A, B});
    }
    UnionFind islands;
    islands.init(N);
    
    ll ans=N*(N-1)/2;
    
    answ.push(ans);
    
    rep(i, M-1){
        pair<ll, ll> th = bridges.top();
        bridges.pop();
        ll thA=th.first;
        ll thB=th.second;
        if(islands.isSame(thA, thB)) ;
        else{
            ans -= islands.size(thA)*islands.size(thB);
            islands.merge(thA, thB);
        }
        answ.push(ans);
    }
    rep(i, M){
        ll out=answ.top();
        answ.pop();
        cout << out << endl;
    }
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a.at(i);

    int ans = 0;
    
    while(true){
        bool odd = false;
        for(int i=0; i<n; i++){
            if(a.at(i) % 2 != 0) odd = true;
        }

        if(odd) break;

        for(int i=0; i<n; i++){
            a.at(i) /= 2;
        }
        ans++;
    }

    cout << ans << endl;
}

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

int main(){
  int h, w;
  while(true){
    cin >> h >> w;
    if(h==0&&w==0)break;
    rep(i, h){
      rep(j, w){
        if((i+j+2)%2==0){
          cout << "#";
        }
        else{
          cout << ".";
        }
      }
      cout << endl;
    }
    cout << endl;
  }

  return 0;
}


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

const int M = 105;

int n, m, arr[M];

int main() {
  int p1 = 0, p2 = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i ++) {
    scanf("%d", &arr[i]);
    if (arr[i] & 1) {
      if (p1 && p2) return puts("Impossible"), 0;
      else if (!p1) p1 = i;
      else p2 = i;
    }
  }
  if (n == 1) return printf("1\n1\n1\n"), 0;
  if (m == 1) return printf("%d\n2\n%d 1\n", n, n - 1), 0;
  if (p2) {
    swap(arr[p1], arr[1]);
    swap(arr[p2], arr[m]);
  }
  else if (p1) swap(arr[p1], arr[1]);
  for (int i = 1; i <= m; i ++) printf("%d%c", arr[i], i == m ? '\n' : ' ');
  arr[1] ++; arr[m] --;
  if (arr[m] == 0) m --;
  printf("%d\n", m);
  for (int i = 1; i <= m; i ++) printf("%d%c", arr[i], i == m ? '\n' : ' ');
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int x[3],y[3];
int a[3][3];
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
cin >> a[i][j];
}
}
x[0] = 0;
for(int i=0; i<3; i++){
y[i] = a[0][i] - x[0];
}
for(int i=0; i<3; i++){
x[i] = a[i][0] - y[0];
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(x[i]+y[j]!=a[i][j]){
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}

Measured memory_bytes: 256
while line = gets
  n,s = line.split.map(&:to_i)
  break if n == 0 && s == 0
  counter = 0
  combi = (0..9).to_a.combination(n)
  combi.each {|arr|  counter += 1 if (arr.inject {|mem, sum|  sum += mem} == s) }
  p counter
end

Measured memory_bytes: 6104
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
using namespace std;

int main() {
	const long long int mod = 1000000007;
	map<long long int, long long int>mp;
	long long int  s[200][200];
	//cout << fixed << setprecision(10);
	long long int d, w, a[200] = {}, res = 0, one = 0, two = 0, e[30][30] = {}, hasi_min = 99999, ike = 0;
	char ch[200001],onech,twoch;
	cin >> d>>w;

	while (1) {
		hasi_min = 99999999;
		res = 0;
		ike = 0;
		if (d == 0&&w==0) { return 0; }
		for (int i = 1; i <= d; i++) {
			for (int j = 1; j <= w; j++) {
				cin >> e[i][j];
			}
		}
		for (int i = 1; i <= d; i++) {
			for (int j = 1; j <= w; j++) {
				for (int p = 3; p+i-1 <= d ; p++) {
					for (int q = 3; q+j-1 <= w ; q++) {

						hasi_min = 99999999;
						for (int z = i; z <= i + p - 1; z++) {
							if (e[z][j] < hasi_min) { hasi_min = e[z][j]; }
						}
						for (int z = j; z <= j + q - 1; z++) {
							if (e[i][z] < hasi_min) { hasi_min = e[i][z]; }
						}
						for (int z = i; z <= i + p - 1; z++) {
							if (e[z][j+q-1] < hasi_min) { hasi_min = e[z][j + q - 1]; }
						}
						for (int z = j; z <= j + q - 1; z++) {
							if (e[i+p-1][z] < hasi_min) { hasi_min = e[i + p - 1][z]; }
						}
						for (int x = i + 1; x <= i + p - 2; x++) {
							for (int y = j + 1; y <= j + q - 2; y++) {
								if (e[x][y] >= hasi_min) { goto next; }
								else { res += hasi_min-e[x][y] ; }
							}
						}
						if (ike < res) { ike = res; }
					next:
						res = 0;
					}
				}
			}
		}
		cout << ike << endl;
		cin >> d>>w;
	}
}



Measured memory_bytes: 3116
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int h = Integer.parseInt(sa[0]);
		int w = Integer.parseInt(sa[1]);
		char[][] grid = new char[h][w];
		for (int i = 0; i < h; i++) {
			grid[i] = br.readLine().toCharArray();
		}
		br.close();

		long[][] dp = new long[h + 1][w + 1];
		dp[1][1] = 1;
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				if (grid[i - 1][j - 1] == '.') {
					dp[i][j] += dp[i][j - 1];
					dp[i][j] += dp[i - 1][j];
					dp[i][j] %= 1000000007;
				}
			}
		}
		System.out.println(dp[h][w]);
	}
}


Measured memory_bytes: 37892
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int  vector_length, i,divide_num;
  cin >> vector_length;
  vector <long long > a(vector_length);
  vector <long long > b(vector_length);
  vector <long long > c(vector_length);
  divide_num =(1000000000+7);
  a[0] = 8;
  b[0] = 2;
  c[0] = 0;
 

  
  
  for(i=1;i<=vector_length-1;i++){
    a[i] = (a[i-1]*8) %1000000007;
    b[i] = (b[i-1]*9) %  1000000007   + a[i-1]*2 ;//a[i-1] = 8^i
    c[i] = (c[i-1]*10) % 1000000007  + (b[i-1]) ;
  }

  
  
  
  
  cout << ((c[vector_length - 1]) % divide_num)<< endl;
}


Measured memory_bytes: 26592
#include <cstdio>

long long gcd(long long a,long long b){
	long long aa,bb;
	while(1){
		if(b == 0){ return a; }
		aa = b;
		bb = a % b;
		a = aa;
		b = bb;
	}
}

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

int main(){
	long long a,b;
	while(scanf("%lld %lld",&a,&b) != EOF){
		printf("%lld %lld\n",gcd(a,b),lcm(a,b));
	}
}

Measured memory_bytes: 0
X, K, D = map(int, input().split())

if int(abs(X) / D) < K:
    if abs(X) < abs(X) % D:
        if K % 2 == 0:
            print(abs(X))
        else:
            print(min(abs(X - D), abs(X + D)))
    else:
        if int(K - int(abs(X) / D)) % 2 == 0:
            print(abs(X) % D)
        else:
            print(min(abs(abs(X) % D - D), abs(abs(X) % D + D)))
else:
    print(abs(X) - D * K)

Measured memory_bytes: 9212
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
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; }
int INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
 if(!b)return 1; if(b&1)return modpow(a,b-1,m)*a%m;
 int memo = modpow(a,b>>1,m);
 return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  int a,b;
  cin>>a>>b;
  vector<int> c(a),d(a-1),e(a);
  rep(i,a)
    cin>>c[i];
  sort(all(c));
  rep(i,a-1){
  d[i]=c[i+1]-c[i];
  }
  e[0]=0;
  rep(i,a-1){
  e[i+1]=d[i]+e[i];
  }
  int g=INF;
    rep(i,a-b+1){
     
  int h=min(g,e[i+b-1]-e[i]);
    //out();
  g=h;
  }
  out(g);
}


Measured memory_bytes: 2560
#include <iostream>
#include <string>
 
using namespace std;
 
int main() {
string a;
string b;
cin >> a >> b;
bool ans = true;
for (int i = 0; i < 3;i++) {
if (a[i] != b[2 - i]) {
ans = false;
}
}
if (ans) {
cout << "YES";
}
else {
cout << "NO";
}
}

Measured memory_bytes: 256
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18

# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const pair <ll,ll> &a,const pair <ll,ll> &b){
    return a.second<b.second;
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};


struct c_h {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}
ll n,m;
bool ok(ll a,ll b){
    return a>=0&&b>=0&&a<n&&b<m;
}
ll dx[8]={1,0,-1,0,1,-1,1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};

int main(){
    IOS;
    make2(ll,n,m);
    vector <string> vec(n);
    vector <vector <ll> >ans(n,vector <ll>(m) );
    fr(i,n) cin>>vec[i];
    fr(i,n){
        bool flag=1;
        fr(j,m) if(vec[i][j]=='#') flag=0;
        if(!flag){
            fr(j,m) ans[i][j]=1;
        }
    }

    fr(i,m){
        bool flag=1;
        fr(j,n) if(vec[j][i]=='#') flag=0;
        if(flag) {
            fr(j,n) ans[j][i]=0;
        }
    }

    fr(i,n){
        bool flag=0;
        fr(j,m){
            if(ans[i][j]) {cout<<vec[i][j];flag=1;}
        }
        if(flag) cout<<endl;
    }

    return 0;
}


Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int inf = 1LL << 60;

int n; 
int a[201010];
vector<vector<int>> to;
vector<int> LIS(201010,inf);

int ans[201010];

void dfs(int pos, int par){
  
  for(auto next : to[pos] ){ 
    
    if( next == par ){ continue;} 
    
    //nextを更新したい
    
    int itr = lower_bound(LIS.begin(),LIS.end(),a[next])-LIS.begin();
    
    ans[next] = itr;
    
    ans[next] = max(ans[next],ans[pos]);
    //でかい方をとっていい
    
    int res = LIS[itr];
    
    LIS[itr] = a[next];
    
    dfs(next,pos);
    
    LIS[itr] = res; 
    //元に戻す
    
  }
  
  
  return ;
} 
    

signed main(void){ 
  
  cin >> n;
  
  for(int i = 0; i < n; i++){ cin >> a[i];}
  
  to.resize(n);
  
  for(int i = 0; i < n-1; i++){ 
    
    int u,v; cin >> u >> v; u--; v--;
    to[u].push_back(v); 
    to[v].push_back(u);
  
  }
  
  LIS[0] = a[0];
  ans[0] = 0; //0-indexedで測っているため、出力の際はインクリメントすること
  dfs(0,-1);
  
  for(int i = 0; i < n; i++){ 
    cout << ans[i]+1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 33124
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
    
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(a.begin(), a.end());
  cout << a[a.size()-1] - a[0] << endl;
  return 0;
}


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


int main(){
  int N, M;
  cin >> N >> M;
  vector<string> A(N);
  vector<string> B(M);
  for(auto& a : A){
    cin >> a;
  }
  for(auto& b : B){
    cin >> b;
  }
  for(int row=0; row<=N-M; row++){
    for(int col=0; col<=N-M; col++){
      bool flg = true;
      for(int ii=0; ii<M; ii++){
        if(A[row+ii].substr(col, M) == B[ii]) continue;
        flg = false;
        break;
      }
      if(flg){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int n, s; 
	while (cin >> n >> s) {
		if (!n && !s)return 0;
		int a[20001]; for (int i = 0; i < n; i++)cin >> a[i];
		long long sum = 0;
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (a[i] + a[j] > s)sum++;
			}
		}
		cout << sum << endl;
	}
	char c; cin >> c;
}

Measured memory_bytes: 2992
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return

    # sizeの大きいほうがx
    if par[x] > par[y]:
        x, y = y, x

    par[x] += par[y]
    par[y] = x


# xが属する集合の個数
def size(x):
    return -par[find(x)]


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


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

res = 0
for i in range(m):
    par = [-1] * n
    flag = False

    for j in range(m):
        if i == j:
            continue
        a, b = e[j]
        union(a-1, b-1)
    
    for j in range(n):
        for k in range(j+1, n):
            if not same(j, k):
                flag = True
    
    if flag:
        res += 1

print(res)

Measured memory_bytes: 74732
# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())
mod=998244353

fact, inv_fact=[1], [1]
fact_tmp=1
for i in range(1, N+1):
    fact_tmp*=i
    fact_tmp%=mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

def ncr(n,r):
	if n<0 or r<0 or n<r:	return 0
	else:   return (fact[n]*inv_fact[r]*inv_fact[n-r])%mod

ans=0
for k in range(K+1):
    ans+=ncr(N-1,k)*M*pow(M-1,N-1-k,mod)
    ans%=mod
print ans

Measured memory_bytes: 99056
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll n;
  R n;
  pr(n*800-n/15*200);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
bool fi[5100][5100];
using namespace std;
int main(){

    int n;
    while(cin>>n,n){
        for(int i = 0;i < 5000;i++)
            for(int j = 0;j < 5000;j++)fi[i][j] = false;
        int x[3100],y[3100];
        for(int i = 0;i < n;i++)cin>>x[i]>>y[i],fi[x[i]][y[i]] = true;

        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                int dx = x[j] - x[i];
                int dy = y[j] - y[i];
                int X = x[i] - dy, Y = y[i] + dx;
                if(!(0 <= X && X <= 5000 && 0 <= Y && Y <= 5000))continue;
                if(!fi[X][Y])continue;
                X = x[j] - dy, Y = y[j] + dx;
                if(!(0 <= X && X <= 5000 && 0 <= Y && Y <= 5000))continue;
                if(!fi[X][Y])continue;
                ans = max(ans,dx*dx + dy*dy);
                //cout<<i<<" "<<j<<" "<<ans<<endl;
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

Measured memory_bytes: 26080
import java.util.*;

class Pair{
    int H,W;
    Pair(int H,int W){
        this.H = H;
        this.W = W;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Pair> list = new ArrayList<Pair>();
        while(true){
            int H=sc.nextInt(),W=sc.nextInt();
            if(H==0&&W==0){
                break;
            }
            Pair p = new Pair(H,W);
            list.add(p);
        }
        for(int i=0;i<list.size();i++){
            Pair p = list.get(i);
            for(int j = 0;j < p.H ; j++){
                for(int k = 0;k < p.W;k++){
                    if(j==0||j==p.H-1||k==0||k==p.W-1){
                        System.out.print("#");
                    }else{
                        System.out.print(".");
                    }
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}



Measured memory_bytes: 35852
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<cassert>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<limits>
#include<ctime>
#include<stack>
#include<bits/stdc++.h>
#include<string>
#include<stdlib.h>
#include<stdio.h>
typedef long long ll;

using namespace std;

int main() {
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int sum=0;
	if(n%2==0){
		for(int i=0;i<n;i++){
			if(i%2==0){
				sum-=a[i];
			}
			else{
				sum+=a[i];
			}
		}
	}
	else{
		for(int i=0;i<n;i++){
			if(i%2==0){
				sum+=a[i];
			}
			else{
				sum-=a[i];
			}
		}
	}
	cout<<sum;
}



Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

LL dp[31][100000];
map<int,LL> ma;

LL dfs(int a,int b,LL sum){
    for(int k=0;k<31;k++){
        if(b<=dp[k][a]){
            if(k==0) return sum+1;
            return dfs(dp[k-1][a],b,sum+(1<<(k-1)));
        }
    }
}

int main(){
    int N;
    cin >> N;
    vector<LL> X;
    for(int i=0;i<N;i++){
        LL x;
        cin >> x;
        X.eb(-x);
        ma[i]=x;
    }
    sort(ALL(X));
    LL L,Q;
    cin >> L >> Q;
    for(int i=0;i<N;i++){
        dp[0][i]=X.end()-lower_bound(ALL(X),-(ma[i]+L))-1;
    }
    for(int k=1;k<31;k++){
        for(int i=0;i<N;i++){
            dp[k][i]=dp[k-1][dp[k-1][i]];
        }
    }
    while(Q--){
        int a,b;
        cin >> a >> b;
        a--,b--;
        if(a>b) swap(a,b);
        cout << dfs(a,b,0) << endl;
    }
    return 0;
}

Measured memory_bytes: 32116
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cstdlib>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
#include<string>
#include<bitset>
#define lmid l,mid,rt<<1
#define rmid mid+1,r,rt<<1|1
#define ll long long
using namespace std;
char s[20];
int main() {
     int a, b;
     scanf("%d%d", &a, &b);
     scanf("%s", s + 1);
     bool flag = true;
     if (s[a + 1] != '-') flag = false;
     for (int i = 1; i <= a + b + 1; i++) {
          if (i == a + 1) continue;
          if (s[i] < '0' || s[i] > '9') {
               flag = false;
               break;
          }
     }
     if (flag) printf("Yes\n");
     else printf("No\n");
     return 0;
}


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

using namespace std;

int main () {

    int i, j, k, l, n, p[101], m[101][101];

    cin >> n;

    for (i = 1; i <= n; i++) {
        cin >> p[i - 1] >> p[i];
    }

    for (i = 1; i<= n; i++) {
        m[i][i] = 0;
    }

    for (l = 2; l <= n; l++) {
        for (i = 1; i <= n - l+ 1; i++) {
            j = i + l - 1;
            m[i][j] = (1 << 21);

            for (k = i; k <=j - 1; k++) {
                m[i][j] = min (m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
            }
        }
    }

    cout << m[1][n] << endl;

    return 0;

}

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

int main(){
  int a,b,c;
  bool flag=false;
  cin >> a >> b >> c;
  r(i,a){
    r(j,b){
      if(i*b+j*a-i*j*2==c)flag=true;
    }
  }
  if(flag)cout << "Yes"<<endl;
  else cout << "No"<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        while(true){
            int d=s.nextInt();
            int w=s.nextInt();
            if(d==0&&w==0) break;
            int depth[][]=new int[d][w];
            for(int i=0;i<d;i++){
                for(int j=0;j<w;j++){
                    depth[i][j]=s.nextInt();
                }
            }
            int max=0;
            
            for(int starti=1;starti<d-1;starti++){
                for(int startj=1;startj<w-1;startj++){
                    for(int endi=starti;endi<d-1;endi++){
                        for(int endj=startj;endj<w-1;endj++){
                            int ddd=dd(starti,startj,endi,endj,depth);
                            if(ddd>max) max=ddd;
                        }
                    }
                }
            }
            System.out.println(max);
        }
    }
    public static int dd(int starti,int startj,int endi,int endj,int[][] depth){
        int max=0;
        int min=depth[starti-1][startj-1];
        for(int i=starti;i<=endi;i++){
            for(int j=startj;j<=endj;j++){
                if(max<depth[i][j]) max=depth[i][j];
            }
        }
        for(int j=startj-1;j<=endj+1;j++){
            if(min>depth[starti-1][j]) min=depth[starti-1][j];
            if(min>depth[endi+1][j]) min=depth[endi+1][j];
        }
        for(int i=starti;i<=endi;i++){
            if(min>depth[i][startj-1]) min=depth[i][startj-1];
            if(min>depth[i][endj+1]) min=depth[i][endj+1];
        }
        //System.out.println(max+" "+min);
        if(max>=min) return 0;
        else{
            int sum=0;
            for(int i=starti;i<=endi;i++){
                for(int j=startj;j<=endj;j++){
                    sum+=(min-depth[i][j]);
                }
            }
            return sum;
        }
    }
}


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

int main() {
  int a,b;
  char op;
  cin >> a >> op >> b;
  if(op == '+')
    cout << a + b << endl;
  else
    cout << a - b << endl;
}
	

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long 

// fact(n)
int fact(int n){
	if(n == 1)	return 1;
	else return (n * fact(n - 1));
}

// combination(n,r)
int combination(int n, int r){
	if(r == 0 || r == n)	return 1;
	else if(r == 1)	return n;
	return (combination(n - 1, r - 1) + combination(n - 1, r));
}

int gcd(int a,int b){
	if(!(a % b)) return b;
	return gcd(b,a % b);
}

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

// qsort(array, size, sizeof(int),comp);
int comp(const int *a,const int *b){
	return (*a - *b);
}

// append(array,*size,addNum)
void append(int *array,int *size,int num){
	realloc(array, sizeof(int) * (*size + 1));
	array[(*size)] = num;
	++(*size);
}

// pop(array,*size) & nongetpop(array,*size)
int pop(int *array,int *size){
	int temp = array[(*size - 1)];
	nongetpop(array,&(*size));
	return temp;
}

void nongetpop(int *array,int *size){
	realloc(array,sizeof(int) * (*size - 1));
	--(*size);
}

int main(int argc, char const *argv[]){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a % 2 == 0 || b % 2 == 0)	puts("No");
	else puts("Yes");
	return 0;
}


Measured memory_bytes: 128
k = int(input())
n=0
a=1
b=0
if a==1 and n<9:
    while n<9 and b<k:
        n+=1
        print(n)
        b+=1
    a+=1
if a==2:
    while n<90 and b<k:
        n+=10
        print(n)
        b+=1
    a+=1
while b<k:
    n+=10**(a-1)
    print(n)
    b+=1
    if (n>((a-1)*10**a-10**(a-1)) and a<12) or (n>((a-2)*10**a-10**(a-1)) and a>=12):
        a+=1

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;


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

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

int main(){
	string in;
	int cnt[26];
	for(int i=0; i<26; i++){
		cnt[i] = 0;
	}
	for(;;){
		if(cin >> in){
			for(int i=0; i<in.length(); i++){
				if(in.at(i)>='a' && in.at(i)<='z'){
					cnt[in.at(i)-'a']++;
				}else if(in.at(i)>='A' && in.at(i)<='Z'){
					cnt[in.at(i)-'A']++;
				}
			}
		}else{
			break;
		}
	}
	for(int i=0; i<26; i++){
		cout << (char)('a'+i) << " : " << cnt[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
 
using namespace std;
 
typedef long long int ll;
typedef vector<long long int> VL;
typedef vector<VL> VVL;
 
int main() {
    int n;
    cin >> n;
    
    int t_s = 0, h_s = 0;
    for(int i=0; i<n; i++) {
        string t, h;
        cin >> t >> h;
        
        int res = t.compare(h);
        if(res > 0) {
            t_s += 3;
        } else if(res == 0) {
            t_s += 1;
            h_s += 1;
        } else {
            h_s += 3;
        }
    }
    
    cout << t_s << " " << h_s << endl;
    
    return 0;
}



Measured memory_bytes: 3180
#include <iostream>

using namespace std;

int main() {
  string O, E;
  cin >> O >> E;

  for (size_t i = 0; i != O.size()+E.size(); ++i) {
    cout << (i%2? E[i/2] : O[i/2]);
  }
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    map<ll,ll> mp; 
    rep(i,n){
        ll tmp;
        cin>>tmp;
        mp[tmp]++;
    }
    mp[0]++;mp[1000000005]++;
    ll cnt=0;
    for(int i=40;i>=1;i--){
        ll val = 1LL<<i;
        auto it = mp.begin();
        it++;
        while(it!=mp.end()&&(*it).first!=1000000005){
            auto it2 = mp.find(val-(*it).first);
            if(!(it==it2&&(*it).second<2)&&it2!=mp.end()&&(*it2).first!=0&&(*it2).first!=1000000005){
                DEBUG{
                    printf("mp.first: %lld\n",(*it2).first);
                    printf("mp.second: %lld\n",(*it2).second);
                }
                if((*it2).second==1){
                    it2 = mp.erase(it2);
                }else{
                    (*it2).second--;
                }
                if((*it).second==1){
                    it = mp.erase(it);
                }else{
                    (*it).second--;
                }
                cnt++;
            }else{
                it++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 12800
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

vector<int> vec[211111];

int slv(int now, int pos);
int n,m;
int a,b;
int f[211111] = {};

int main(){

  scanf(" %d %d",&n,&m);
  for(int i=0;i<m;i++){
    scanf(" %d %d",&a,&b);
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  
  if(slv(0,1)){
    printf("POSSIBLE\n");
  } else {
    printf("IMPOSSIBLE\n");
  }

  return 0;
} 


int slv(int now, int pos){
  if(f[pos])return 0;
  if(now == 2){
    if(pos == n)return 1;
    return 0;
  }
  
  f[pos] = 1;
  
  int ans = 0;
  for(int i=0;i<vec[pos].size();i++){
    ans += slv(now+1,vec[pos][i]);
  }

  return ans;
} 


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

typedef long double ll;

ll n;
ll ds[305][305][305];
bool vis[305][305][305];
const ll mod = 1e9 + 7;

ll dp(int x, int y, int z){
	if(x + y + z == 0) return 0; 
	if(vis[x][y][z]) return ds[x][y][z];
	vis[x][y][z] = true;
	ll &ans = ds[x][y][z];
	int d = n - x - y - z;
	if(x) ans += (x * dp(x - 1, y, z));
	if(y) ans += (y * dp(x + 1, y - 1, z));
	if(z) ans += (z * dp(x, y + 1, z - 1));
	ans += n;
	ans /= (n - d);
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << setprecision(15) << fixed;
	cin >> n;
	int x, y, z;
	x = y = z = 0;
	for(int i = 0; i < n; i++){
		int t;
		cin >> t;
		if(t == 1) x++;
		else if(t == 2) y++;
		else z++;
	}
	cout << dp(x, y, z) << "\n";
	return 0;
}

Measured memory_bytes: 467328
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

  int v1 = B / A;
  if(v1 >= C){
    cout << C << endl;
  }
  else{
    cout << v1;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
int n,i,A[2000];
int solve(int,int);
int main(){
  int m[2000],q;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++)
    scanf("%d",&m[i]);
  for(i=0;i<q;i++){
    if(solve(0,m[i])==1)
      printf("yes\n");
    else printf("no\n");
  }
  return 0;
}
int solve(int i,int m){
  int res;
  if(m==0)
    return 1;//真                                                               
  if(i>=n)
    return 0;//負                                                               
  res=solve(i+1,m)||solve(i+1,m-A[i]);
  return res;
}




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

typedef long long ll;

int main(){
  ll a,b;
  cin >> a >> b;
  
  int ret = 1;
  for(ll i = 2;i*i <= min(a,b);i++){
    if(a%i == 0 && b%i == 0)ret++;
    while(a%i == 0)a /= i;
    while(b%i == 0)b /= i;
  }
  if(a > 1 && b > 1){
  	if(b % a == 0 || a % b == 0)ret++;
  }
  
  cout << ret << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#include <unordered_map>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

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

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;

template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
void SWAP(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
void SWAP(int& a, int& b) { a ^= b; b ^= a; a ^= b; }


class C {
	unordered_map<int, int> um;
	vector<pii> v;
	int k, n;
	int now{ 0 };
public:
	C()
	{
		cin >> n >> k;
	}
	void solve()
	{
		int a;
		unordered_map<int, int>::iterator it;

		REP(i, n)
		{
			cin >> a;
			it = um.find(a);

			if (it != um.end())
				++it->second;
			else
			{
				um.insert(MP(a, 1));
				++now;
			}
		}

		if (now <= k)
		{
			cout << 0 << endl;
			return;
		}

		for(it = um.begin(); it != um.end(); it++)
		{
			v.emplace_back(*it);
		}

		sort(ALL(v), [](pii& left, pii& right) { return left.second < right.second; });

		int ans{ 0 };
		for (int i{ 0 }; i < now - k; i++)
			ans += v[i].second;

		cout << ans << endl;
	}
};


int main()
{
	C solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 11592
#n進数への変換関数の定義
#Python 3.7とかではデフォであるが，Python 3.4.3(AtCoder仕様)ではまだない
########10進法からn進法への変換関数部分##############
def format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
############################

########10進法からn進法への変換関数(m桁埋める)部分##############
def format0(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    if len(out) < m:
        out = "0" * (m - len(out)) + out
    return out
############################
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(d)]
ans=1000

for i in range(pow(2,d)):
  pt=0
  ans_=0
  t = format0(i,2,d)
  for j in range(d):
    if t[j]=="1":
      pt += (j+1)*100*pc[j][0]+pc[j][1]
      ans_ += pc[j][0]
  if pt >= g:
    ans = min(ans,ans_)
    continue
  for j in range(d):
    j=d-1-j
    if t[j]=="1":
      continue
    if pt + ((j+1)*100*(pc[j][0]-1))>=g:
      q=(j+1)*100
      k = (g-pt+q-1)//q
      pt += (j+1)*100*k
      ans_ += k
      break
    else:
      pt += (j+1)*100*(pc[j][0]-1)
      ans_ += pc[j][0]-1
  if pt>=g:
    ans = min(ans,ans_)
print(ans)

Measured memory_bytes: 3188
import math
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1
ah = 1
while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(math.ceil(th/x),math.ceil(ah/y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(th+ah)

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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    cout << (b-a)*(b-a-1)/2 - a << endl;
    return 0;
}


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

ll h,n,minv=inf;
ll f[2000005];

int main()
{
	f[0]=0;	
	for(int i=1;i<=2000000;i++)  f[i]=inf;
	cin>>h>>n;
	long long int a[n+1],b[n+1];
	for (int i=1;i<=n;i++)  cin>>a[i]>>b[i];
	for (int j=1;j<=n;j++)
	{
		for (int i=a[j];i<=20000;i++)  f[i]=min(f[i-a[j]]+b[j],f[i]);
	}
	for(int i=h;i<=20000;i++)
	{
		if (f[i]<minv)  minv=f[i];
	}
	cout<<minv<<endl;
	return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
long long sum,dif;
int a[10005],b[10005];
int main(){
	//freopen("readin.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i = 0;i < n;i++)scanf("%d",a + i),sum-=a[i];
	for(int i = 0;i < n;i++)scanf("%d",b + i),sum+=b[i];
	for(int i = 0;i < n;i++)if(b[i] > a[i])dif+=(1 + b[i] - a[i])/2;
	puts(dif > sum ? "No" : "Yes");
}

Measured memory_bytes: 384
import java.util.Scanner;

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

        String b = sc.next();

        if (b.equals("A")) {
            System.out.println("T");
        } else if (b.equals("T")) {
            System.out.println("A");
        } else if (b.equals("G")) {
            System.out.println("C");
        } else {
            System.out.println("G");
        }
    }
}



Measured memory_bytes: 23764
def ff(x,y,z):
    return(x**2+y**2+z**2+x*y+y*z+z*x)

n=int(input())
an=[0]*n
for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            wk=ff(i,j,k)
            if wk<=n:
                an[wk-1]+=1
for i in an:
    print(i)

Measured memory_bytes: 9068
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <deque>
#include <string.h>
#include <math.h>

using namespace std;

#define PI 3.141592653589793
#define epsilon 0.000000001
#define INF 1000000000000000000
#define MOD 1000000007

int main(){
    //freopen("grass.in", "r", stdin); freopen("grass.out", "w", stdout);
    int N, M, K; cin >> N >> M >> K;
    for(int i = 0; i <= N; i++){
        if(N-2*i == 0){
            if(K-i*M == 0){
                cout << "Yes\n";
                return 0;
            }
            continue;
        }
        int j = (K-i*M)/(N-2*i);
        if(j*(N-2*i) == (K-i*M) && j > -1 && j < M+1){
            //cout << i << " " << j << endl;
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <numeric>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
#define fcout cout<<fixed<<setprecision(10)
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
//template<typename T>void pp(T x){cout<<x<<endl;}

using namespace std;
template<typename T> void test(vector<T> v){for(int i=0;i<v.size();i++){if(i)cout<<" ";cout<<v[i];}cout<<endl;}

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    Sort(v);
    cout<<v.back()-v[0]<<endl;
    
    return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin >>a>>b;

  int a2019 ,b2019,aa,bb;
  a2019 =a%2019;
  b2019 =b%2019;
 // aa = (a-a2019)/2019;
 // bb = (b-b2019)/2019;
  int ans =2019;
  if(a2019>=b2019) cout <<0<<endl;
  else if(b-a>=2019) cout << 0<<endl;
  else{
   for(int i =a2019;i<b2019;i++){
   for(int j =i+1;j<=b2019;j++){
     if(i*j%2019<ans) ans =i*j%2019;
   }
   }
    cout <<ans <<endl;
  }
    
  
}

Measured memory_bytes: 256
import bisect
A=int(input())
ai=[]
for i in range(A):
    ai.append(int(input()))
min_num=[ai[0],float("inf")]
len_mn=2
for i in ai[1:]:
    b=bisect.bisect_left(min_num,i)
    if b==0:
        min_num[0]=i
    elif b+1==len_mn:
        min_num.insert(-1,i)
        len_mn+=1
    else:
        min_num[b]=i
print(len(min_num)-1)


Measured memory_bytes: 11144
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int a,b,h;
	int S;
	cin >> a >> b >> h;
	S = ( a + b ) * h/2;
	cout << S << endl;
}


Measured memory_bytes: 256