akhauriyash/Code-Regression huggingface dataset:
//Longest Increasing Subsequence
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int A[n], L[n];
    for(int i = 0; i < n; i++) cin >> A[i];

    L[0] = A[0];
    int length = 1;

    for(int i = 1; i < n; i++) {
        if(L[length - 1] < A[i]) L[length++] = A[i];
        else {
            *lower_bound(L, L + length, A[i]) = A[i];
        }
    }
    cout << length << endl;
}


Measured memory_bytes: 3840
N = int(input())
 
V = [0]*10000
 
for j in range (1, 100):
	for k in range (1, 100):
		for l in range (1, 100):
			if j**2+k**2+l**2+j*k+k*l+j*l < 10001:
				V[j**2+k**2+l**2+j*k+k*l+j*l-1]+=1

for i in range (0, N):
	print(V[i])

Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin>>N;
  vector<int> mae(N/2);
  vector<int> ato(N/2);
  for(int i=0;i<N/2;i++){
    cin>>mae.at(i);
    cin>>ato.at(i);
  }
  sort(mae.begin(),mae.end());
  sort(ato.begin(),ato.end());
  int A=mae.at(0);
  int coA=1;
  int anA=1;
  int secA=0;
  for(int i=1;i<N/2;i++){
    if(mae.at(i-1)==mae.at(i)){
      coA++;
    }
    else{
      if(anA<=coA){
        A=mae.at(i-1);
        secA=anA;
        anA=coA;
      }
      else if(secA<coA){
        secA=coA;
      }
      coA=1;
    }
    if(i==N/2-1 &&anA<=coA){
      A=mae.at(i);
      secA=anA;
      anA=coA;
    }
  }
  if(anA==N/2){
    secA=0;
  }
  int B=ato.at(0);
  int coB=1;
  int anB=1;
  int secB=0;
   for(int i=1;i<N/2;i++){
    if(ato.at(i-1)==ato.at(i)){
      coB++;
    }
    else{
      if(anB<=coB){
        B=ato.at(i-1);
        secB=anB;
        anB=coB;
      }
      else if(secB<coB){
        secB=coB;
      }
      coB=1;
    }
    if(i==N/2-1 && anB<=coB){
      B=ato.at(i);
      secB=anB;
      anB=coB;
    }
  }
  if(anB==N/2){
    secB=0;
  }
  if(A!=B){
    cout<<N-anA-anB;
  }
  else{
    cout<<N-max(anA+secB,secA+anB);
  }
}

Measured memory_bytes: 640
N = int(input())
A = [int(x) for x in input().split()]
p = []
m = []
for a in A:
    if a < 0:
        m.append(a)
    else:
        p.append(a)
was = []
if N == 2:
    print(max(A)-min(A))
    print(max(A), min(A))
    quit()
if len(m) == 0:
    p.sort()
    m.append(p[0] - p[-1])
    was.append((p[0], p[-1]))
    p = p[1:-1]
elif len(p) == 0:
    m.sort()
    p.append(m[-1] - m[0])
    was.append((m[-1], m[0]))
    m = m[1:-1]

mm = m[0]
m = m[1:]
pp = p[0]
p = p[1:]
for x in p:
    was.append((mm,x))
    mm -= x
for x in m:
    was.append((pp,x))
    pp -= x
was.append((pp, mm))
print(pp-mm)
for p,m in was:
    print(p,m)

Measured memory_bytes: 20216
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

vector<int> ps[200010];

int main(){
  int H,W,N,x,y;
  cin>>H>>W>>N;
  for(int i=0;i<N;i++){
    cin>>x>>y;x--,y--;
    ps[y].push_back(x);
  }
  x=0;
  set<int> ans;
  for(int i=0;i<W;i++){
    sort(all(ps[i]));
    while(find(all(ps[i]),x)!=ps[i].end()){
      x++;
    }
    if(x>=H)break;
    auto it=upper_bound(all(ps[i]),x);
    if(it==ps[i].end()){
      ans.insert(H);
    }else{
      ans.insert(*it);
    }
    x++;
    //cout<<x<<" "<<i<<endl;
  }
  cout<<*ans.begin()<<endl;
}

Measured memory_bytes: 10112
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

int main() {
    Int N,T;

    cin >>N>>T;
    Int ans = inf;
    vi c = vi(N);
    vi t = vi(N);
    rep(i,N){
        cin >> c[i];
        cin >> t[i];
    }

    rep(i,N){
        if(t[i]<=T){
            ans = min(ans, c[i]);
        }
    }

    if(ans == inf){
        cout << "TLE";
    }else{
        cout << ans;
    }

    return 0;
}

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

int main(void){
    char s[100];
    char t[100];
    int a,b;
    char u[100];
    
    scanf("%s %s", s, t);
    scanf("%d %d", &a, &b);
    scanf("%s", u);
    
    if(strncmp(s, u, 10) == 0){
        printf("%d %d", a-1, b);
    }else{
        printf("%d %d", a, b-1);
    }
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base:: sync_with_stdio(false);
    cin.ignore(NULL);
    int n,l,i;
    string s[100];
    cin>>n>>l;
    for(i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n);
    for(i=0;i<n;i++){
        cout<<s[i];
    }
    return 0;
}


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

#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}
template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }
template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

int main(void)
{
    int a, p;
    cin >> a >> p;
    
    int ans = ((a * 3)+p)/2;
    cout << ans << endl;

    return 0;
} /*atcoder*/


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1LL << 60;
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 dp[100010];
signed main(){
    int n;
    cin >> n;
    vector<int> a(100010);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < 100010; i++){
        dp[i] = INF;
    }
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        chmin(dp[i],dp[i - 1] + abs(a[i] - a[i - 1]));
        if( i > 1) chmin(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]));
    }
    cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>

int selectionSort(int A[], int N) {
    int minj, sw = 0;
    int temp;
    int i, j;
    for ( i = 0; i < N - 1; i++ ) {
        minj = i;
        for ( j = i; j < N; j++ ) {
            if (A[j] < A[minj])
                minj = j;
        }
        temp = A[i];
        A[i] = A[minj];
        A[minj] = temp;
        if ( i != minj )
            sw++;
    }

    return sw;
}


int main()
{
    int N, A[100], sw;

    scanf("%d", &N);

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

    sw = selectionSort(A, N);

    for (int i = 0; i < N; i++ ) {
        if (i > 0)
            printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
    printf("%d\n", sw);

    return 0;
}



Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<int> a(n);
    vector<int> num(100000,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
        num[a[i]]++;
    }
    sort(a.begin(),a.end());
    long long kazu=0;
    long long ans=num[0]+num[1];
    for(long long i=1;i<=a[n-1];i++){
        kazu=num[i-1]+num[i]+num[i+1];
        ans=max(ans,kazu);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    int A[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K; cin >> K;
    cout << A[K-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int x,y,z,tmp;
    int gcd;
    scanf("%d %d", &x,&y);
    if(x<y){
      tmp=x;
      x=y;
      y=tmp;
    }
    while((z = x % y) != 0)
    {
        x = y;
        y = z;
        z=x%y;
    }
    printf("%d\n",y);
    return 0;
}



Measured memory_bytes: 2104
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define NP next_permutation
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;

const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;

template<class T> bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T> void decimal(T a){cout<<fixed<<setprecision(a);}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}

void YesNo(bool a){if(a) out("Yes"); else out("No");}
void yesno(bool a){if(a) out("yes"); else out("no");}
void YESNO(bool a){if(a) out("YES"); else out("NO");}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){ll c=1; while(b>0){if(b&1){c=a*c %mod;}a=a*a %mod;b>>=1;}return c;}
vi calc(ll x){vi res; while(x>0){res.pb(x%10);x/=10;}reverse(all(res)); return res;}

void solve(){
  int a,b;
  cin>>a>>b;
  if(a>0&&b>0){
    if(a<=b) out(b-a);
    else out(a-b+2);
  }
  else if(a<0&&b<0){
    if(a<=b) out(b-a);
    else out(a-b+2);
  }
  else if(a>0&&b<0){
    if(a<-b) out(1-a-b);
    else out(a+b+1);
  }
  else if(a<0&&b>0){
    if(-a<=b) out(1+a+b);
    else out(-a-b+1);
  }
  else if(a==0&&b==0){
    out(0);
  }
  else if(a==0){
    if(b<0) out(1-b);
    else out(b);
  }
  else{
    if(a>0) out(a+1);
    else out(-a);
  }
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<string>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<map>

#include<sstream>
#include<ctype.h>

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
 
typedef long long ll;
using namespace std;
 
const int INF = 0x7f7f7f7f;
const double PI = acos(-1.0);
const int maxn = 1005;
const int MOD = (int)1e9+7;
#define LOCAL 0
#define MOD 1000000007

int a[15],l[15],r[15];
bool res;

bool dfs(int apos,int lpos,int rpos){
	
	if(apos == 11)	return true;
	if(a[apos] > l[lpos-1]){
		l[lpos] = a[apos];
		if(dfs(apos+1,lpos+1,rpos)) return true;
	} 
	if(a[apos] > r[rpos-1]){
		r[rpos] = a[apos];
		if(dfs(apos+1,lpos,rpos+1)) return true;
	} 
	return false;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(a,0,sizeof(a));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		for(int i = 1 ; i <= 10 ; i ++) 	scanf("%d",&a[i]);		
		if(dfs(1,1,1)){
			cout << "YES" << endl;	
		}else{
			cout << "NO" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1200
n = gets.chomp.to_i
str_ary =  gets.chomp.to_s.chars
i = gets.chomp.to_i
str = str_ary[i-1]
str_ary.each_with_index do |v, k|
  str_ary[k] = "*" unless v == str
end

puts str_ary.join


Measured memory_bytes: 1788
package main

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

var (
	n     int
	G     [100000][]int
	color [100000]*int
)

func dfs(r int, c int) {
	S := Stack{}
	S.Push(r)
	color[r] = &c
	for !S.IsEmpty() {
		u := S.Pop()
		for i := 0; i < len(G[u]); i++ {
			v := G[u][i]
			if color[v] == nil {
				color[v] = &c
				S.Push(v)
			}
		}
	}
}

func assignColor() {
	id := 1
	for i := 0; i < n; i++ {
		color[i] = nil
	}
	for u := 0; u < n; u++ {
		if color[u] == nil {
			id++
			dfs(u, id)
		}
	}
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ = strconv.Atoi(sc.Text())
	sc.Scan()
	r, _ := strconv.Atoi(sc.Text())

	for i := 0; i < r; i++ {
		sc.Scan()
		s, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		t, _ := strconv.Atoi(sc.Text())
		G[s] = append(G[s], t)
		G[t] = append(G[t], s)
	}
	assignColor()
	sc.Scan()
	qNum, _ := strconv.Atoi(sc.Text())
	for i := 0; i < qNum; i++ {
		sc.Scan()
		s, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		t, _ := strconv.Atoi(sc.Text())
		if color[s] == color[t] {
			fmt.Println("yes")
		} else {
			fmt.Println("no")
		}
	}
}

// Stack is Stack
type Stack struct {
	stack []int
}

// Push new value
func (stack *Stack) Push(val int) {
	stack.stack = append(stack.stack, val)
}

// Pop new value
func (stack *Stack) Pop() int {
	val := stack.stack[len(stack.stack)-1]
	stack.stack = stack.stack[0 : len(stack.stack)-1]
	return val
}

// IsEmpty return true when stack is empty
func (stack *Stack) IsEmpty() bool {
	return len(stack.stack) == 0
}



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

int main(){
  int n;
  cin>>n;
  vector<int> h(n);
  for(int i=0;i<n;i++){
    cin>>h[i];
  }
  int t=0;
  int ans=0;
  for(int i=0;i<n;i++){
    t=max(t,h[i]);
    if(t==h[i]){
      ans++;
      
    }
  }
  cout<<ans<<endl;
  
  
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) x*=i;
    return x;
}

ll gcd(ll a,ll b)
{
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

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



int main(){
    ll h,w;
    cin>>h>>w;
    char s[55][55];
    rrep(i,h) rrep(j,w) cin>>s[i][j];
    
    
    
    rrep(i,h) rrep(j,w){
        if(s[i][j]=='#'){
            if(s[i-1][j]!='#' && s[i+1][j]!='#' && s[i][j-1]!='#' && s[i][j+1]!='#'){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 256
#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;

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 main() {
    int n, W;
    cin >> n >> W;
    vector<vector<ll>> dp(n+1, vector<ll>(W+1));
    rep(i, n) {
        int w, v;
        cin >> w >> v;
        rep(j, W+1) {
            int jw = j-w;
            
            if (jw >= 0) {
               chmax(dp[i+1][j], dp[i][jw]+v);
            }
            
            chmax(dp[i+1][j], dp[i][j]);

            // printf("dp[%d] = %lld\n", j, dp[i+1][j]);
        }
    }
    cout << dp[n][W] << endl;

    return 0;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define SORT(v) sort(all(v))
#define REV(v) sort((v).begin(), (v).end(), greater<int>())
#define INF 1000000007
#define fcout cout << fixed << setprecision(15)
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){std::fill( (T*)array, (T*)(array+N), val );};
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 N, W;
ll dp[110][100010];
ll w[110], v[110];

ll dfs(ll i, ll j) {
  if(dp[i][j]) return dp[i][j];
  ll res;
  if(i == N) res = 0;
  else if(j < w[i]) res = dfs(i + 1, j);
  else res = max(v[i] + dfs(i + 1, j - w[i]), dfs(i + 1, j));
  dp[i][j] = res;
  return res;
}

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

  cin >> N >> W;
  
  rep(i, N) cin >> w[i] >> v[i];
  cout << dfs(0, W) << endl;
  return 0;
}


Measured memory_bytes: 78080
#include<stdio.h>
#include<math.h>

int main(){

double a,b,c,d,e,f;
double x,y;

while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF){

x=(c*e-b*f)/(a*e-b*d);
y=(c*d-a*f)/(b*d-a*e);

if(x==0) x=fabs(x);
if(y==0) y=fabs(y);

printf("%.3lf %.3lf\n",x,y);
	}

return 0;
	}

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

struct dsu {
  const int n;
  vector<int> p, sz;
  dsu(int _n) : n(_n), p(n, -1), sz(n, 1) {}
  int root(int v) { return p[v] == -1 ? v : v = root(p[v]); }
  void unite(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
  }
  int size(int v) { return sz[root(v)]; }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int h, w;
  while (cin >> w >> h, w) {
    vector<vector<int>> a(h, vector<int>(w));
    for (auto&& v : a) {
      for (auto&& e : v) {
        cin >> e;
      }
    }
    dsu d(h * w);
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (a[i][j]) {
          for (int di = -1; di <= 1; ++di) {
            for (int dj = -1; dj <= 1; ++dj) {
              if (di or dj) {
                int ni = i + di, nj = j + dj;
                if (0 <= ni and ni < h and 0 <= nj and nj < w and a[ni][nj]) {
                  d.unite(i * w + j, ni * w + nj);
                }
              }
            }
          }
        }
      }
    }
    set<int> se;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (a[i][j]) {
          se.insert(d.root(i * w + j));
        }
      }
    }
    cout << se.size() << '\n';
  }
}



Measured memory_bytes: 3156
class Heap
  def initialize(xs = [], &block)
    @que = xs
    @size = xs.size
    @cmp = block || lambda{ |a,b| a < b }
  end

  def push(x)
    i = @size
    while i > 0 do
      j = (i - 1) / 2
      break unless @cmp.call(x, @que[j])
      @que[i] = @que[j]
      i = j
    end
    @que[i] = x
    @size += 1
  end

  def replace
    m = @que[0]
    x = yield m
    i = 0
    while (ii = i * 2 + 1) < @size do
      j1 = ii
      j2 = ii + 1
      j1 = j2 if j2 < @size && @cmp.call(@que[j2], @que[j1])
      break unless @cmp.call(@que[j1], x)
      @que[i] = @que[j1]
      i = j1
    end
    @que[i] = x
    m
  end
end

def get_target(l, h, n, fs)
  r = 0
  fs.each do |f| r += h / f end

  # t0 = (l*h/r).ceil, t = (l*h/(r+n)).ceil
  lh = l * h
  t0 = (lh + r - 1) / r
  t = (lh + r + n - 1) / (r + n)

  raise if (t0 >= t + 2)

  t
end

n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)
fs = gets.split.map(&:to_i)
 
l = as.inject(:+) - k

if (l <= 0)
  p 0
  exit
end

# O(n * log(n))
afs = as.sort.zip(fs.sort.reverse).sort_by do |item| item[0]*item[1] end

# O(n * log(n))
sum = afs.map do |a, f|
  a
end
for i in (0...n-1)
  sum[i+1] += sum[i]
end
left = -1
right = n - 1
while right - left > 1 do
  mid = (left + right) / 2
  s = 0
  af = afs[mid][0] * afs[mid][1]
  #afs.each do |a,f| s += [af / f, a].min end
  for i in (0...n-1-mid)
    s += af / afs[n-1-i][1]
  end
  s += sum[mid]
  if(s > l)
    right = mid
  else
    left = mid
  end
end
m = right
# p ["m:",m]
if (m > 0)
  afs = afs.drop(m)
  n -= m
end
 
l = -k
max_f = 0
 
# O(n)
fs = afs.map do |a, f|
  l += a
  max_f = f if f > max_f
  f
end
 
# O(n)
t = get_target(l, l * max_f * max_f, n, fs)
# p ["t:", t]
max_af = 0
 
# O(n)
xs = fs.map do |f|
  l -= (a = t / f)
  af = a * f
  max_af = af if af > max_af
  [af + f, f]
end
if (l == 0)
  p max_af
else
  # O(n * log(n))
  xs = xs.sort_by do |item| item.first end
  q = Heap.new(xs) do |a,b| a.first < b.first end
 
  # assert: l <= 2*n
  # O(n * log(n))
  af, = q.replace do |a| [a[0] + a[1], a[1]] end while (l -= 1) >= 0
  p af
end



Measured memory_bytes: 63956
#include<iostream>
#include<queue>
#include<memory>
#include<map>
#include<set>
#include<unordered_map>
#include<array>
#include<vector>
#include<algorithm>
#include<list>
#include<limits>
#include<stdio.h>
#include<math.h>
#include<string>

using namespace std;
using ll = long long;
using vec = vector<int>;
using mat = vector<vec>;
using lst = list<ll>;

const ll MOD = 1000000007;



int main()
{
	int N, K;
	cin >> N >> K;

	vec H(N);

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

	sort(H.rbegin(), H.rend());

	ll ans = 0;
	for (int i = K; i < N; ++i)
	{
		ans += H[i];
	}

	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;

int N;
long long W,weight[110],value[110];

long long dp[110][100100] = {0};

int main(){
  cin >> N >> W;
  for(int i=0;i<N;i++){
    cin >> weight[i] >> value[i];
  }
  for(int i=0;i<N;i++){
    for(int sum_w = 0;sum_w <= W;sum_w++){
      
      if(sum_w - weight[i] >= 0){
        chmax(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i]);
      }
      
      chmax(dp[i + 1][sum_w],dp[i][sum_w]);
    }
  }
  cout << dp[N][W] << endl;
}


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

int main(){
    int n;
    cin>>n;
    int arr[n];
    int temp[n];
    for (int i=0;i<n;++i){
        cin>>arr[i];
        temp[i]=arr[i];
    }
    vector<int>v;
    sort(temp,temp+n);
    for (int i=0;i<n;++i){
        if (arr[i]!=temp[i]){
            v.push_back(i);
        }
    }
    if (v.size()>2 || v.size()==1){
        cout<<"NO";
        return 0;
    }
    cout<<"YES";
    
}

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

int main() {
  int A, B, C, D ,L ,R;
  cin >> A >>B >>C >>D ;
  L = A + B;
  R = C + D;
  if(L == R)
    cout <<"Balanced"<<endl;
  if(L > R)
    cout <<"Left"<<endl;
  if(R > L)
    cout <<"Right"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  int n, k, l[51];
  cin >> n >> k;
  REP(i, n) cin >> l[i];
  sort(l, l + n, greater<int>());
  int sum = 0;
  REP(i, k) sum += l[i];
  cout << sum << endl;
  return 0;
}


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

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

  string s;
  cin >> s;
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    string c;
    cin >> c;
    int a, b;
    cin >> a >> b;
    if (c == "print") {
      cout << s.substr(a,b-a+1) << endl;
    }
    if (c == "reverse") {
      reverse(s.begin() + a, s.end() - s.size() + b + 1);
    }
    if (c == "replace") {
      string s1;
      cin >> s1;
      s.replace(a, b-a+1, s1);
    }
  }
} 


Measured memory_bytes: 3220
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String S = sc.nextLine();
    String T = sc.nextLine();
    int n = S.length() + T.length();
    
    for(int i = 0; i < n; i++){
      if(i%2 == 0){
        System.out.print(S.charAt(i/2));
      }else{
        System.out.print(T.charAt(i/2));
      }
    }
    System.out.println("");
  }
}

Measured memory_bytes: 21844
package main

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

func main() {
	d, t, s := readFloat64(), readFloat64(), readFloat64()

	if d/s <= t {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	log.SetFlags(log.Lshortfile)
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readInt() int {
	return int(readInt64())
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


Measured memory_bytes: 1776
#include <iostream>
#include <utility>
#include <queue>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN(v) int v;cin>>v;
#define OUT(v) cout<<v<<endl
const int INF = 1000000000;

const int BLACK = 0, WHITE = INF;

int main() {
  IN(H); IN(W);

  vvi A(H, vi(W, WHITE));
  queue<pii> black;
  REP(i, H) {
    REP(j, W) {
      char a; cin >> a;
      if (a == '#') {
        A[i][j] = BLACK;
        black.push(make_pair(i, j));
      }
    }
  }
  int ans = 0;
  while (!black.empty()) {
    pii p = black.front(); black.pop();
    int dr[4]={0, 1, 0, -1}; // row
    int dc[4]={1, 0, -1, 0}; // column
    REP(i, 4) {
      int r = p.first + dr[i], c = p.second + dc[i];
      if (!(0 <= r && r < H && 0 <= c && c < W))
        continue;
      if (A[r][c] == WHITE) {
        ans = A[r][c] = A[p.first][p.second] + 1;
        black.push(make_pair(r, c));
      }
    }
  }
  OUT(ans);

  return 0;
}


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

const int L = 15;

int n, mx = 0;
char str[L];
map<string, int> m;

int main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", str);
		mx = max(mx, ++m[string(str)]);
	}
	for (map<string, int> :: iterator it = m.begin(); it != m.end(); it++) {
		if (it -> second == mx) cout << it -> first << endl;
	}
	return 0;
}

Measured memory_bytes: 23808
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
//using ll=long long;
const double EPS = 1e-10;
inline bool equals(double a, double b) { return fabs(a - b) < EPS; }
const double PI = 3.141592653589793238;
class Point {
public:
	double x, y;
	Point(double x, double y) :x(x), y(y) {}
	Point() {}
	Point operator +(const Point &p) const{ return Point(x + p.x, y + p.y); };
	Point operator -(const Point &p) const{ return Point(x - p.x, y - p.y); }
	Point operator *(double k) { return Point(x*k, y*k); }
	Point operator /(double k) { return Point(x / k, y / k); }
};

using Vector = Point;
inline double norm(Vector a) {
	return a.x*a.x + a.y*a.y;
}
double absv(Vector a) {
	return sqrt(norm(a));
}
inline double dot(Vector a, Vector b) {
	return a.x*b.x + a.y*b.y;
}
inline double cross(Vector a, Vector b) {
	return a.x*b.y - a.y*b.x;
}
struct Segment {
	Point p1, p2;
};

using Line = Segment;
class Circle {
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0) :c(c), r(r) {}
};
using Polygon = vector<Point>; 
Point project(Segment s, Point p) {
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / norm(base);
	return s.p1 + base*r;
}
Point reflect(Segment s, Point p) {
	return p + (project(s, p) - p)*2.0;
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0, Point p1, Point p2) {
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if (cross(a, b) > EPS) return COUNTER_CLOCKWISE;
	if (cross(a, b) < -EPS) return CLOCKWISE;
	if (dot(a, b) < -EPS) return ONLINE_BACK;
	if (norm(a) < norm(b)) return ONLINE_FRONT;
	return ON_SEGMENT;
}
bool intersection(Point p1, Point p2, Point p3, Point p4) {
	return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 and ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0);
}

bool intersection(Segment s1, Segment s2) {
	return intersection(s1.p1, s1.p2, s2.p1, s2.p2);
}

int main() {
	int q, x[4], y[4];
	Point p[4];
	cin >> q;
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> x[j] >> y[j];
			p[j] = Point(x[j], y[j]);
		}
		cout << intersection(p[0], p[1], p[2], p[3]) << endl;
	}
}

Measured memory_bytes: 3100
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

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

    if((a + b) % 2 == 0)
        cout << ((a + b) / 2) << endl;
    else
        cout << "IMPOSSIBLE" << endl;

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for i in range(num_v):
        update = False
        for edge in edges:
            e_from, e_to, e_cost = edge
            if e_from != -float('inf') and visited[e_to] and dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
                update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
f = defaultdict(dict)
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
    f[b-1][a-1] = 1
visited = [False]*n
def dfs(x):
    visited[x] = True
    for t in f[x].keys():
        if not visited[t]:
            dfs(t)
dfs(n-1)
d,f = Bellman_Ford(edge,n,0)
if not f:
    print(-1)
else:
    print(max(0,d[-1]))


Measured memory_bytes: 53596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    int n;cin>>n;
    string s;cin>>s;
    int res=0,now=0;
    rep(i,n){
        if(s[i]=='I')now++;
        else now--;
        res=max(res,now);
    }
    cout<<res<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a[13];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	a[1] = a[3] = a[5] = a[7] = a[8] = a[10] = a[12] = 1;
	a[4] = a[6] = a[9] = a[11] = 2;
	a[2] = 3;
	int x, y;
	cin >> x >> y;
	if (a[x] == a[y])cout << "Yes\n";
	else cout << "No\n";
}

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


void solve(long long H, long long W, long long N){
    cout << min((N + H - 1) / H, (N + W - 1) / W) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    long long N;
    scanf("%lld",&N);
    solve(H, W, N);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,i,j,k,l,m,n,a[10005],b[100005];
    char s[100005];
    map<int,int>mp;
    pair<int,int>p[200005];
    cin>>i>>j>>k;
    if(i+j==2*k)
    cout<<"Yes";
    else
    cout<<"No";
    return 0;
}

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

using namespace std;

#define il inline
#define re register int
#define Rep(i, s, e) for (re i = s; i <= e; ++i)
#define Dep(i, s, e) for (re i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)

typedef long long ll;

const int N = 200010;

il ll read() {
	ll x = 0; bool f = true; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = false; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return f ? x : -x;
}

ll h;
int main() {
	h = read();
	Dep(i, 40, 0) {
		ll tp = 1ll << i;
		if (tp <= h) {
			return printf("%lld", (tp << 1) - 1) & 0;
		}
	}
}

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

int main() {
    // 制約見て！！！デカかったらlong longにすること！
    string s;
    cin >> s;
    bool flag = false;
    string t[] = {
        "AKIHABARA", "AKIHABAR", "AKIHABRA", "AKIHABR", "AKIHBARA", "AKIHBAR",
        "AKIHBRA",   "AKIHBR",   "KIHABARA", "KIHABAR", "KIHABRA",  "KIHABR",
        "KIHBR",     "KIHHBARA", "KIHBRA",   "KIHBAR"
    };

    rep(i,2*2*2*2){
        if(t[i]==s){
            flag = true;
            break;
        }
    }

    if(flag){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 3596
#include <iostream>

using namespace std;

long long gcd(long long a, long long b){
	if(b==0){
		return a;
	}
	return gcd(b,a%b);
}

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

long long a[100010];
int main(){
	long long i,n,x;
	cin >> n >> x;
	for(i=0;i<n;i++){
		cin >> a[i];
		if(x>a[i]){
			a[i] = x-a[i];
		}else{
			a[i] = a[i]-x;
		}
	}
	long long y = a[0];
	for(i=0;i<n;i++){
		y = gcd(y,a[i]);
		//cout << x << endl;
	}
	cout << y << endl;
}
	

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

int n,arr[100001];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",arr+i);

    int ans=0;
    for(int i=1,j;i<=n;i=j) {
        if(arr[i]!=i) {
            j=i+1;
            continue;
        }
        for(j=i;j<=n && arr[j]==j;j++);
        ans += (j-i+1)/2;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ldb = long double;
using pa = pair < ll, ll >;
using vec = vector < ll >;
#define pb push_back
#define F  first
#define S  second
#define int ll
#define f(i,x,n) for(ll i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
#define edl "\n"
#define ceils(s,n) (s+n-1)/n
#define str string
#define add insert
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
const int MOD = 1e9 + 7, N = 1e5 + 10;
const ll LINF = LLONG_MAX;
ll a,b,c,d,n;
str s1,s2,s;
ll ans=0;
int32_t main() {
    fast();
   char ch1[26];
   int cc=0;
   for(char ch='A';ch<='Z';ch++){
   	ch1[cc]=ch;
   	cc++;
   }
   cin >> n >> s;
   f(i,0,s.size()){
   	int a=s[i];
   	int n1=n;
   	// cout<<s[i]<<" "<<a<<" "<<a+n<<"\n";
   	if(a+n>90){
   		n1-=(90-a);
   		a=65+n1-1;

   	}
   	else{
   		a+=n;
   	}
  
  	 char ch=a;	
  	 cout<<ch;
  
   }


    cerr << "\nTime taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
    return 0;
}
 

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

int main() {
	int n;
	cin >> n;
	int is[n];
	int avg1 = 0;
	int avg2 = 0;
	for (int i = 0; i < n; i++) {
		cin >> is[i];
		avg1 += is[i];
		avg2 += is[i];
	}
	int temp = !(!(avg1 % n));
	avg1 /= n;
	avg1 += temp;
	avg2 /= n;
	int cost1 = 0;
	int cost2 = 0;
	for (int i: is) {
		cost1 += (i-avg1) * (i-avg1);
		cost2 += (i-avg2) * (i-avg2);
	}
	cout << min(cost1, cost2) << endl;
	return 0;
}

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

int main() {
	int n,m,x;
	cin>>n>>m>>x;
	int a[m];

	int head=0;
	int tail=0;
	for(int i=0;i<m;i++){
		cin>>a[i];
		if(a[i]<x)head++;
		if(a[i]>x)tail++;
	}
	if(head<tail){
		cout<<head<<endl;
	}else{
		cout<<tail<<endl;
	}
	return 0;
}


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

int main() {
    int a, b, c, x, count=0;
    cin >> a >> b >> c >> x;

    for(int i=0; i<=a; i++) {
        for(int j=0; j<=b; j++) {
                if((x-500*i-100*j) >= 0 && (x-500*i-100*j) <= 50*c) count++;
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 256
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
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 n, k;
vector<vector<int>> g;

void solve() {
	cin >> n;
    g.assign(n, vector<int>());
    rep(i, n - 1) {
        int a, b; cin >> a >> b; --a; --b;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin >> k;
    priority_queue<P, vector<P>, greater<P>> pque;
    vector<int> d(n, -INF);
    rep(i, k) {
        int v, k; cin >> v >> k;
        --v;
        pque.push(P{k, v});
        d[v] = k;
    }
    while(!pque.empty()) {
        P p = pque.top(); pque.pop();
        int k = p.fr, v = p.sc;
        if(d[v] != k) {
            cout << "No" << endl;
            return;
        }
        for(auto nv: g[v]) {
            if(d[nv] == k - 1 || d[nv] == k + 1) continue;
            if(d[nv] == -INF) {
                d[nv] = k + 1; //k - 1となるべきならもうすでにそーなってるはず
                pque.push(P{k + 1, nv});
            } else {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
    rep(i, n) {
        cout << d[i] << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

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

int t[1000000];

int main()
{
	int N;
	while(scanf("%d",&N), N)
	{
		int i,c,x;
		for(i=c=0; i<N; i++)
		{
			scanf("%d",&t[i]);
			if(c==0)	x=t[i];
			if(x==t[i])	c++; else c--;
		}

		for(i=c=0; i<N; i++)
		{
			if(t[i]==x) c++;
		}

		if(c*2>N)
			printf("%d\n",x);
		else
			printf("NO COLOR\n");

	}
}

Measured memory_bytes: 4676
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1; i * j < n; j++) ans++;
	}
	cout << ans << '\n';

}



Measured memory_bytes: 3696
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl
#define NL <<"\n"

using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
//#undef NUIP
#ifdef NUIP
#include "../benri.h"
#else
#define out
#endif
#ifdef __cpp_init_captures
template<typename T>vector<T> table(int n, T v){ return vector<T>(n, v);}
template <class... Args> auto table(int n, Args... args){auto val = table(args...); return vector<decltype(val)>(n, move(val));}
#endif
const ll MOD=1e9+7; //998244353

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout<<fixed<<setprecision(0);
	int n;
	ll t;
	cin>>n>>t;
	vector<int> a(n);
	rep(i,n) cin>>a[i];
	vector<int> ad(n);
	{
		vector<int> nxt(212345);
		rrep(i,n) nxt[a[i]]=i+n;
		rrep(i,n){
			ad[i]=nxt[a[i]]-i+1;
			nxt[a[i]]=i;
		}
	}
	out(ad,1);
	vector<int> vst(n,-1);
	vector<int> re;
	for(ll i=0,j=0;i<n && j<t;){
		if(vst[i]>=0){
			ll d=(j-vst[i]);
			ll x=(t-2-j)/d;
			out(i,j,d,x,1);
			j+=x*d;
		}else{
			vst[i]=j;
		}
		if(i+ad[i]>=n){
			if(j+1==t && i+ad[i]>n){
				re.pb(a[i]);
				++i;
			}else{
				i+=ad[i];
				j+=i/n;
				i%=n;
			}
		}else{
			i+=ad[i];
		}
		out(i,j,1);
	}
	out(re,1);
	for(int x:re) cout<<x<<" ";cout<<endl;
  return 0;
}


Measured memory_bytes: 5696
#include <iostream>

int main(){
   std::string S;
   std::cin >> S;

   std::string year = S.substr(0,4);
   if(year!="2019") {
      std::cout << "TBD" << std::endl; 
      return 0;
   }

   std::string month = S.substr(5,2);
   if(month!="04" && month!="03" && month!="02" && month!="01"){
      std::cout << "TBD" << std::endl;
      return 0;
   }

   std::cout << "Heisei" << std::endl;
   return 0;
}


Measured memory_bytes: 256
n, k = gets.chomp.split.map(&:to_i)

MOD = 10**9 + 7

memo = []
memo[0] = 0
1.upto(n) do |i|
  memo[i] = memo[i-1] + i
end

ans = 0
k.upto(n+1) do |i|
  if i == n+1
    ans += 1
  else
    ans += memo[n] - memo[n-i] - memo[i-1] + 1
  end
  ans %= MOD
end
p ans


Measured memory_bytes: 16172