akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main(){
  string s;
  int k;
  cin >> k >> s;
  if (s.size() <= k){
    cout << s << endl;
  }
  else {
    for (int i = 0; i < k; i++) {
      cout << s[i];
    }
    cout << "..." << endl;
  }
}


Measured memory_bytes: 3628
S = list(input())
ans = []

for i in range(len(S)):
    if S[i] == 'B':
        if len(ans) == 0:
            pass
        else:
            del ans[-1]
        
    else:
        ans.append(S[i])

for x in ans:
    print(x,end='')
print()



Measured memory_bytes: 2940
#include <stdio.h>

int main(int argc, char const *argv[])
{
	long a,b,k;
	long tmp;
	scanf("%ld%ld%ld", &a, &b, &k);
	tmp = a;
	a = a - k;
	k = k - tmp;
	if (k < 0)
		k = 0;
	b -= k;
	if (a < 0)
		a = 0;
	if (b < 0)
		b = 0;
	printf("%ld %ld", a, b);
	return 0;
}


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

int main() {
    //ifstream cin("c.in");

    int n; cin >> n;

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

    for(int i = 2; i <= n; ++i) {
        cin >> p[i];
        g[p[i]].push_back(i);
    }

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

    for(int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    
    vector<vector<int>> dp(n + 1, vector<int> (2, 1e6));

    for(int i = n; i >= 1; --i) {
        for(int tip = 0; tip < 2; ++tip) {
            vector<int> best(x[i] + 1, 1e6);
            if(g.empty())
                dp[i][tip] = 0;
            best[0] = 0;

            for(auto v : g[i]) {
                vector<int> a(x[i] + 1, 1e6);
                vector<int> b(x[i] + 1, 1e6);

                for(int sum = x[i]; sum >= 0; --sum) {
                    if(dp[v][tip] < 1e6 and sum + x[v] <= x[i])
                        a[sum + x[v]] = best[sum] + dp[v][tip];
                    if(dp[v][1 - tip] < 1e6 and sum + dp[v][1 - tip] <= x[i])
                        b[sum + dp[v][1 - tip]] = best[sum] + x[v];
                }

                for(int sum = 0; sum <= x[i]; ++sum) {
                    best[sum] = min(a[sum], b[sum]);
                }
            }

            for(int sum = 0; sum <= x[i]; ++sum)
                dp[i][tip] = min(dp[i][tip], best[sum]);
        }
    }

    if(dp[1][0] < 1e6 or dp[1][1] < 1e6) {
        cout << "POSSIBLE\n";
    } else {
        cout << "IMPOSSIBLE\n";
    }
}


Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int S[] = new int[N+1];
		for(int i = 1;i < N+1;i++) {
			S[i] = sc.nextInt();
		}
		Arrays.sort(S);
		int count = 0;
		for(int i = 1;i < S.length;i++) {
			if(S[i] == S[i-1])continue;
			count++;
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(void){
    ll A,B,m;
    
    cin >> A >> B >> m;
    ll a[A],b[B], saishoa,saishob;
    ll x[m+1],y[m+1],c[m+1];
    saishoa = 100000000;
    saishob = 100000000;
    for(ll i=0;i<A;i++){cin >> a[i];saishoa = min(saishoa,a[i]);}
    for(ll i=0;i<B;i++){cin >> b[i];saishob = min(saishob,b[i]);}
    for(ll i=1;i<=m;i++)cin >> x[i] >> y[i] >> c[i];
    
    ll price[m+1];
    price[0] = saishoa + saishob;
    for(ll i=1;i<=m;i++){
        price[i] = a[x[i]-1] + b[y[i]-1] - c[i];
    }
    sort(price,price+m+1);
    cout << price[0] << endl;
    
    return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int MOD=1e9+7;
struct node{
    int v,id;
}p[N];
ll a[N];

bool cmp(node a,node b){
    return a.v<b.v;
}

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

    int n;
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >> p[i].v;
        p[i].id=i;
    }
    sort(p+1,p+1+n,cmp);
    vector<node> t;
    for(int i=1;i<=n;i++)   t.pb(p[i]);
    for(int i=1;i<=n;i++){
        if(i<=n/2){
            a[p[i].id]=p[n/2+1].v;
        }
        else{
            a[p[i].id]=p[n/2].v;
        }
    }
    for(int i=1;i<=n;i++)   cout <<a[i]<<endl;

    return 0;
}


Measured memory_bytes: 7024
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())

using namespace std;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

using ll = long long;
constexpr int mod = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u * v / gcd(u, v);
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);

    int N;
    cin >> N;
    vector<int> dp(N + 1);
    dp[0] = 0;
    FOR(i, 1, N + 1) {
        dp[i] = INF;
        int power = 1;
        while (power <= i) {
            dp[i] = min(dp[i], dp[i - power] + 1);
            power *= 6;
        }
        power = 1;
        while (power <= i) {
            dp[i] = min(dp[i], dp[i - power] + 1);
            power *= 9;
        }
    }

    cout << dp[N] << endl;

    return 0;

}

Measured memory_bytes: 768
# -*- coding:utf-8 -*-

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

    # O(N)じゃ間に合わない

    """
    i   = 1 2 3 4 5 6 7 8
    P_i = 2 3 4 5 6 7 8 1

    ↑これが最大値なのでは？
    つまり、
    ・P_i = i + 1
    ・P_N = 1
    にすると、1 ~ N-1の和が答えになる。
    """
    ans = (1+(N-1))*(N-1)//2
    print(ans)

if __name__ == "__main__":
    solve()


Measured memory_bytes: 3064
while True:
	n, x = map(int, input().split())
	if n == 0 and x == 0:
		exit(0)
	cnt = 0
	for i in range(1, n - 1):
		#	print(i)
		for j in range(i + 1, n):
			#		print(' {0}'.format(j))
			if n >= x - i - j > j:
				#			print('  {0} {1} {2}'.format(i, j, x - i - j))
				cnt = cnt + 1

	print(cnt)



Measured memory_bytes: 5596
package main

import "fmt"

const mod int = 1e9 + 7

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

	x := (n * (n + 1)) / 2
	ans := 0
	for i := k; i <= n+1; i++ {
		min := (i - 1) * i / 2
		max := x - ((n - i) * (n - i + 1) / 2)
		ans += max - min + 1
		ans %= mod
	}

	fmt.Println(ans)
}


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

using ll = long long;

struct edge {
    int to;
    ll cost;
    edge(int t, ll c) : to(t), cost(c) {}
};

using graph = vector<vector<edge>>;

int main() {
    int n, m; cin >> n >> m;
    graph g(n);
    for(int i = 0; i < n - 1; ++i) {
        int a, b, c; cin >> a >> b >> c;
        g[a - 1].emplace_back(b - 1, c);
        g[b - 1].emplace_back(a - 1, c);
    }
    vector<ll> s(n);
    for(auto& ss : s) cin >> ss;

    vector<ll> cs;
    function<ll(int, int, ll)> dfs = [&] (int v, int p, ll st) {
        if(p != -1 && g[v].size() == 1u) return 0LL; // leaf
        vector<ll> ch;
        for(auto const& e : g[v]) {
            if(e.to == p) continue;
            ch.push_back(dfs(e.to, v, st) + st * e.cost);
        }
        const int idx = max_element(begin(ch), end(ch)) - begin(ch);
        for(int i = 0; i < (int)ch.size(); ++i) {
            if(i == idx) continue;
            cs.push_back(ch[i]);
        }
        if(p == -1) { // root
            cs.push_back(ch[idx]);
        }
        return ch[idx];
    };
    for(int i = 0; i < n; ++i) {
        dfs(i, -1, s[i]);
    }
    sort(begin(cs), end(cs), greater<>{});

    cout << accumulate(begin(cs), begin(cs) + min((int)cs.size(), m), 0LL) << endl;
}




Measured memory_bytes: 36032
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

int main(){
	int N,table[21][21],row,col,m,div;
	char dist[2];
	bool FLG;

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		for(int i=0; i < 21; i++){
			for(int k = 0; k < 21; k++){
				table[i][k] = 0;
			}
		}

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

		row = 10,col = 10;

		scanf("%d",&m);

		for(int i=0; i < m; i++){
			scanf("%s %d",dist,&div);
			switch(dist[0]){
			case 'N':
				for(int k = row;  k <= row+div; k++){
					table[k][col] = 0;
				}
				row += div;
				break;
			case 'S':
				for(int k = row;  k >= row-div; k--){
					table[k][col] = 0;
				}
				row -= div;
				break;
			case 'E':
				for(int k = col; k <= col+div; k++){
					table[row][k] = 0;
				}
				col += div;
				break;
			case 'W':
				for(int k = col; k >= col-div; k--){
					table[row][k] = 0;
				}
				col -= div;
				break;
			}
		}

		FLG = true;

		for(int i=0; i < 21; i++){
			for(int k=0; k < 21; k++){
				if(table[i][k] == 1){
					FLG = false;
					break;
				}
			}
			if(!FLG)break;
		}

		if(FLG)printf("Yes\n");
		else{
			printf("No\n");
		}

	}


    return 0;
}

Measured memory_bytes: 2516
#include<iostream>
#include<string>
using namespace std;
char a[1001];
int main()
{
    string s;
    int k=0;
    cin>>s;
    for(int i=0;i<=s.size()-1;++i)
    {
    	if(s[i]=='0'||s[i]=='1')
    	{
    		k++;
    		a[k]=s[i];
		}
		else
		{
			if(k>0)
			k--;
		}
	}
	for(int i=1;i<=k;++i)
	cout<<a[i];
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X=sc.nextInt();
        int A=sc.nextInt();
        int B=sc.nextInt();
        if((-A+B)<=0){
            System.out.println("delicious");
        }else if((-A+B)<=X){
            System.out.println("safe");
        }else{
            System.out.println("dangerous");
        }
        
    }
}


Measured memory_bytes: 23252
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



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

  ll a, b, x;
  cin >> a >> b >> x;

  double l = 0;
  double r = 90;
  while(l+1e-8<r){
    double c = (l+r)/2;
    double m;
    if (b*tan((90.0-c)/180.0*PI) < a){
      m = 0.5*a*b*b*tan((90.0-c)/180.0*PI);
    } else {
      double bb = a*tan(c/180.0*PI);
      m = 0.5*a*a*bb + a*a*(b-bb);
    }
    if (m > x){
      l = c;
    } else {
      r = c;
    }
  }

  cout << fixed << setprecision(10) << l << "\n";
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll x;
	cin >> x;
	ll tmp = 100;
	int ans = 0;
	while (tmp < x) {
		tmp += tmp * 0.01;
		ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int p[7] = {2, 3, 5, 7, 11, 13, 17};
int q[7] = {9, 6, 4, 3, 3, 3, 3};
int r[7];
int n, z, pc = 7;
int a[320];
int b[320];
int w[320];
void dfs(int x) {
	if (x == pc) {
		memset(w, 0, sizeof w);
		for (int i = 0; i < n; i++) {
			bool flag = false;
			int u = a[i];
			int v = b[i];
			for (int j = 0; j < pc; j++) {
				for (int k = 0; k < r[j]; k++) {
					if (u % p[j] == 0) {
						u /= p[j];
					} else {
						break;
					}
				}
				if (u % p[j] == 0) {
					flag = true;
					break;
				}
			}
			if (flag) {
				continue;
			}
			w[u] += v;
		}
		int t = w[1];
		for (int i = 2; i <= 300; i++) {
			if (w[i] > 0) {
				t += w[i];
			}
		}
		z = max(z, t);
	} else {
		for (r[x] = 0; r[x] < q[x]; r[x]++) {
			dfs(x + 1);
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i], &b[i]);
	}
	dfs(0);
	printf("%d\n", z);
	return 0;
}
/////

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;

ll rui(ll a,ll b){
    if(b==1) return a%mod;
    else if(b==0) return 1;
    else if(b%2==0) return (rui(a,b/2)*rui(a,b/2))%mod;
    else return (rui(a,b-1)*a)%mod;
}

ll inv[MAX],fac[MAX],finv[MAX];

void make(){
    
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    
    for(int i=2;i<MAX;i++){
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        fac[i]=fac[i-1]*(ll)i%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
    
}

ll comb(ll a,ll b){
    if(a<b) return 0;
    return fac[a]*(finv[b]*finv[a-b]%mod)%mod;
}

int main(){

    int N,K;cin>>N>>K;
    make();
    ll dp[N+1][K+1];
    for(int i=0;i<N+1;i++){
        for(int j=0;j<K+1;j++){
            dp[i][j]=0;
        }
    }
    for(int j=0;j<K+1;j++){
        dp[0][j]=1;
    }
    
    dp[1][1]=1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=K;j++){
            if(i==1&&j==1) continue;
            if(i-j<0) dp[i][j]=dp[i][j-1];
            else dp[i][j]=(dp[i][j-1]+dp[i-j][j])%mod;
        }
    }
    if(N<K) cout<<0<<endl;
    else cout<<dp[N-K][K]<<endl;
}




Measured memory_bytes: 13252
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <complex>

#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;


ll powMod(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll t = powMod(x, n/2, mod);
  t = t * t % mod;
  if (n & 1) return t * x % mod;
  return t;
}

ll gcd(ll a, ll b) {
  if (a == 0 || b == 0) return a + b;
  if (b > a) return gcd(b, a);
  return gcd(b, a % b);
}

 

int main(void) {

  int n, k, d[200], a[200][200];
  int s[200] = {};
  
  cin >> n >> k;
  rep(i, k) {
    cin >> d[i];
    rep(j, d[i]) {
      cin >> a[i][j];
      s[a[i][j]]++;
    }
  }

  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == 0) ans++;
  }

  cout << ans << endl;
}

  

  


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
const int mod = 1e9 + 7;


int main() {
    int n; cin >> n;
    V<ll> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    V<ll> w(n + 1);
    for(int i = 0; i < n; i++){
        w[i + 1] = (w[i] + v[i]);
    }

    ll ans = 0;
    for(int i = 0; i < n - 1; i++){
        ans += (w[n] - w[i + 1]) % mod * v[i] % mod;
        ans %= mod;
    }
    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 6360
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
    ll n, k;
    cin >> n >> k;
    map<ll, ll> mp;
    for (ll i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;
        mp[a] += b;
    }
    ll cnt = 0;
    for (pair<ll, ll> p : mp) {
        cnt += p.second;
        if (k <= cnt) {
            cout << p.first << endl;
            break;
        }
    }
}


Measured memory_bytes: 4224
const main = input => {
const [a, b, c, d] = input.trim().split(" ").map(e => Number.parseInt(e))
const h = (360 / 12 / 60) * (Math.PI / 180);
const m = (360 / 60) * (Math.PI / 180);
const x1 = b*Math.cos(m*d) // m-x
const x2 = a*Math.cos(h*(c*60+d)) // h-x
const y1 = b*Math.sin(m*d) // m-y
const y2 = a*Math.sin(h*(c*60+d)) // h-y
return Math.sqrt((x1-x2)**2+(y1-y2)**2)
}
console.log(main(require('fs').readFileSync('/dev/stdin', 'utf8')))

Measured memory_bytes: 29792
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb; 
typedef long long ll;  
typedef double db;                         
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, N = 3e3 + 48, mod = 1e9 + 7, maxn = 102;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;



int n;
double p[N], dp[N][N];

main () {
	cin >> n;
	forn (i, 1, n)
		cin >> p[i];

	dp[0][0] = 1;
	forn (i, 1, n)
		forn (j, 0, n) {
			if (j)
				dp[i][j] += dp[i - 1][j - 1] * p[i]; 
			dp[i][j] += dp[i - 1][j] * (1 - p[i]);
		}

	db ans = 0;
	forn (i, n / 2 + 1, n)
		ans += dp[n][i];


	cout << fixed << setprecision(12);		
	cout << ans << endl;		
}                       

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


int main() {
	ll a; cin >> a;
	string b; cin >> b;
	int n = b.size();
	string b1 = "";
	for (int i = 0; i < n; i++) {
		if (b[i] != '.') {
			b1 += b[i];
		}
	}
	int b2 = stoi(b1);
	cout << (a*b2)/100 << endl;
	return 0;
}

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

int main(void) {
  ll N;
  cin >> N;
  vector<ll> A(N);
  REP(i, 0, N) cin >> A[i];

  vector<ll> sum(N + 1, 0);
  REP(i, 0, N) sum[i + 1] = sum[i] + A[i];

  ll ans = 1LL << 60;
  REP(i, 2, N - 1) {
    ll l1 = 1, h1 = i;
    while(h1 - l1 > 1) {
      ll m1 = (l1 + h1) / 2;
      if((sum[m1] - sum[0]) - (sum[i] - sum[m1]) < 0) l1 = m1;
      else h1 = m1;
    }

    ll l2 = i + 1, h2 = N;
    while(h2 - l2 > 1) {
      ll m2 = (l2 + h2) / 2;
      if((sum[m2] - sum[i]) - (sum[N] - sum[m2]) < 0) l2 = m2;
      else h2 = m2;
    }

    REP(j, -1, 2) REP(k, -1, 2) {
      ll p = l1 + j, q = l2 + k;
      if(p < 1 || p >= i || q < i + 1 || q >= N) continue;

      ll s1 = sum[p] - sum[0];
      ll s2 = sum[i] - sum[p];
      ll s3 = sum[q] - sum[i];
      ll s4 = sum[N] - sum[q];
      ll x = max({ s1, s2, s3, s4 });
      ll y = min({ s1, s2, s3, s4 });
      ans = min(ans, x - y);
    }
  }
  cout << ans << endl;
}

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

using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, n) for (int i = 1; i < (int)(n+1); i++)
#define rep4(i, s, n) for (int i = (s); i < (int)(n+1); i++)
#define repr(i,n) for (int i = (n-1); i>=0;i--)
#define repr2(i,s,n) for (int i = (n-1); i>=(int)(s);i--)
#define repr3(i,n) for(int i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
const ll INF = 1001001000100010;
const ld PI = 3.14159265358979323846;


int main() {
int N,K;

cin>>N>>K;
ll B[20];
rep(i,N){
    cin>>B[i];

}
ll memo=0,cost=0,min_cost=INF,count=0;
rep(i,1<<N){
    memo=0;
    cost=0;
    count=0;
    rep(j,N){
        if((i>>j)&1){
            memo=max(memo+1,B[j]);
            cost+=max(memo,B[j])-B[j];
            count++;
        }
        else{
            if(B[j]>memo){
            memo=B[j];
            count++;
            }
        }
    }
    if(count==K){
    min_cost=min(min_cost,cost);
    }

}
cout<<min_cost<<endl;
return 0;
}



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

int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int,int>> data(n);
  rep(i,m) {
    int now;
    string r;
    cin >> now >> r;
    int res = 1;
    if(r == "WA") res = 0;
    if(data[now - 1].first == 1) continue;
    else if(res == 1) data[now - 1].first = 1;
    else if(res == 0) data[now - 1].second++;
  }
  
  int ACnum = 0;
  int WAnum = 0;
  for(auto c : data) {
    int x, y;
    tie(x, y) = c;
    if(x == 0) y = 0;
    ACnum += x;
    WAnum += y;
  }
  cout << ACnum << " " << WAnum << endl;
}

Measured memory_bytes: 1024
# WA math.ceilは浮動小数点演算の影響を受けるので、正しく切り上げできないときがある
# >>> math.ceil((12345678901234*456+0.1)/12345678901234)
# 456
# >>> math.ceil((12345678901234*456+1)/12345678901234)
# 457

import math

n = int(input())
vote_ratio = [ list(map(int, input().split())) for _ in range(n)]
# print(vote_ratio)

# ans = vote_ratio[0] は同じオブジェクトを参照してしまうので避ける
ans = [vote_ratio[0][0], vote_ratio[0][1]]

for i in range(1,n):
	bairitsu = max(ans[0] // vote_ratio[i][0], ans[1] // vote_ratio[i][1])
	if vote_ratio[i][0] * bairitsu < ans[0] \
	or vote_ratio[i][1] * bairitsu < ans[1]:
		bairitsu += 1
	ans = [vote_ratio[i][0] * bairitsu, vote_ratio[i][1] * bairitsu]

print(sum(ans))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(12), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
using Int = long long;
int main() {
    int N, M; cin >> N >> M;
    vector<string> S(N); for (auto &s : S) cin >> s;
    int cnt = 0, edge = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cnt += (S[i][j] == 'o');
            edge += (i + 1 < N && S[i][j] != '#' && S[i + 1][j] != '#');
            edge += (j + 1 < M && S[i][j] != '#' && S[i][j + 1] != '#');
        }
    }
    mcf_graph<int, Int> graph(N * M + 4);
    int start = N * M, goal = N * M + 1, ss = N * M + 2, tt = N * M + 3;
    graph.add_edge(ss, start, cnt, 0);
    graph.add_edge(goal, tt, cnt, 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (S[i][j] == '#') {
                continue;
            }
            if (S[i][j] == 'o') {
                graph.add_edge(start, i*M+j, 1, 0);
            }
            if (S[i][j] == 'o' || S[i][j] == '.') {
                graph.add_edge(i*M+j, goal, 1, 0);
            }
            if (i + 1 < N && S[i + 1][j] != '#') {
                //graph.add_edge(i*M+j, (i+1)*M+j, cnt, -1);
                graph.add_edge(ss, (i+1)*M+j, cnt, 0);
                graph.add_edge((i+1)*M+j, i*M+j, cnt, 1);
                graph.add_edge(i*M+j, tt, cnt, 0);
            }
            if (j + 1 < M && S[i][j + 1] != '#') {
                //graph.add_edge(i*M+j, i*M+(j+1), cnt, -1);
                graph.add_edge(ss, i*M+(j+1), cnt, 0);
                graph.add_edge(i*M+(j+1), i*M+j, cnt, 1);
                graph.add_edge(i*M+j, tt, cnt, 0);
            }
        }
    }
    auto [cap, cost] = graph.flow(ss, tt, cnt + cnt * edge);
    cout << -(cost - cnt * edge) << endl;
    return 0;
}

Measured memory_bytes: 4764
n, y = map(int, input().split(" "))
for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i+5000*j+1000*(n-i-j) == y:
            print(str(i)+" "+str(j)+" "+str(n-i-j))
            quit()
print("-1 -1 -1")

Measured memory_bytes: 3068
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
b=[a[0]]
for i in range(1,n):
    b.append(b[i-1]+a[i])
#print(b)
ans=float("inf")
for i in range(n-1):
    ans=min(abs((b[-1]-b[i])-b[i]),ans)
print(ans)


Measured memory_bytes: 82000
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  string s;
  cin >> s;
  int n = s.length();

  for (int i = 0; i < n / 2; ++i) {
    if (s[i] != s[n - 1 - i]) {
      cout << "No\n";
      return 0;
    }
  }

  for (int i = 0; i < n / 2; ++i) {
    if (s[i] != s[n / 2 - 1 - i]) {
      cout << "No\n";
      return 0;
    }
  }

  for (int i = n / 2 + 1; i < n; ++i) {
    if (s[i] != s[n - 1 - i]) {
      cout << "No\n";
      return 0;
    }
  }

  cout << "Yes\n";
}


Measured memory_bytes: 3136
N,M = map(int,input().split())
*X, = map(int,input().split())

cnt = [0]*(10**5+10)
cntMod = [0]*M
cntPairsMod = [0]*M
for x in X:
    cnt[x] +=1
    cntMod[x%M] +=1
for i,c in enumerate(cnt):
    cntPairsMod[i%M] += (c//2)*2

ans = cntMod[0]//2
if M%2==0:ans += cntMod[M//2]//2
for i in range(1,M//2 +M%2):
    j = M-i
    pairs = min(cntMod[i],cntMod[j])
    ans += pairs
    cntMod[i] -= pairs
    cntMod[j] -= pairs
    ans += min(cntMod[i],cntPairsMod[i])//2
    ans += min(cntMod[j],cntPairsMod[j])//2
print(ans)

Measured memory_bytes: 14008
#include<algorithm>
#include<clocale>
#include<cmath>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<iostream>
#include<istream>
#include<map>
#include<math.h>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
using namespace std;
int n,a[100010],x[100010],k;
int main(){
	cin>>n>>k;
	for (int i=0;i<n;i++) cin>>a[i];
	for (int i=0;i<n;i++) x[i]=1e9;
	x[0]=0;
	for (int i=1;i<n;i++)
		for (int j=1;j<=k&&i-j>=0;j++)
			x[i]=min(abs(a[i]-a[i-j])+x[i-j],x[i]);
	cout<<x[n-1]<<endl;
	return 0;
}

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

int main(){

    int n, m, t; cin >> n >> m >> t;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    vector<int> imos(t + 1, 0);
    for(int i = 0; i < n; i++){
        imos[a[i] - m]--;
        if(a[i] + m <= t) imos[a[i] + m]++;
    }

    for(int i = 2; i <= t; i++){
        imos[i] += imos[i - 1];
    }

    int ans = 0;

    for(int i = 0; i < t; i++){
        //cout << imos[i] << " ";
        if(imos[i] == 0) ans++;
    }
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3128
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int[] coins = new int[m];
		for (int i = 0; i < m; i++) {
			coins[i] = in.nextInt();
		}
		int[] c = new int[200001];
		Arrays.fill(c, Integer.MAX_VALUE);
		for (int i = 0; i < m; i++) {
			c[coins[i]] = 1;
		}

		for (int i = 2; i < c.length; i++) {
			for (int j = 0; j < m; j++) {
				if (i-coins[j] <= 0) continue;
				int a = c[i-1]+1;
				int b = c[i-coins[j]]+1;
				c[i] = Math.min(c[i], Math.min(a, b));
			}
		}

		System.out.println(c[n]);


	}

}



Measured memory_bytes: 28000
import java.util.Scanner;

public class Main{

  static boolean isInOut_Circle(int[] pos) {
    int[] sq_pos = {pos[0], pos[1]};
    int[] ci_pos = {pos[2], pos[3]};
    int rad = pos[4];

    if (((ci_pos[0] - rad) < 0) || ((ci_pos[0] + rad) > sq_pos[0])) {
      return false;
    } else if (((ci_pos[1] - rad) < 0) || ((ci_pos[1] + rad) > sq_pos[1])) {
      return false;
    } else {
      return true;
    }
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    int inNum[] = new int[5];
    for (int i = 0;i < inNum.length ;i++ ) {
      inNum[i] = stdIn.nextInt();
    }

    if (isInOut_Circle(inNum)) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


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

int main(){
  string s;
  cin >> s;
  if(s=="AAA"||s=="BBB"){
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
}

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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repm(i, a, b) for (int i = (a); i > (b); i--)

using namespace std;
using ll = long long;

ll saiki (string s) {
  if (s.size()==1) return stoi(s);
  ll ret = saiki(s.substr(1)) * 2;
  int top = s[0] - '0';
  rep (i,0,s.size()) {
    int times;
    if (i == s.size()-1) {
      times = 1;
    } else {
      times = pow(2,s.size()-2-i);
    }
    ret += top * pow(10,i) * times;
  }
  return ret;
}

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

  cout << saiki(s) << endl;
  
  return 0;
}

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

double deg_to_rad(double degree){
    double pi = acos(-1);
    double rad = pi*degree/180;
    return rad;
}

int main() {
 
    double A,B;
    double H,M;
    cin >> A >> B >> H >> M;
    double S = H*30.0+M*30/60;
    double L = M*6;
    double degree = abs(S-L);
    double rad = deg_to_rad(degree);
    double ans = A*A+B*B-2*A*B*cos(rad);
 
    cout << fixed << setprecision(15);
    cout << sqrt(ans) << endl;
}

Measured memory_bytes: 4140
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Set<Integer> set = new HashSet<>();
		int n = sc.nextInt();
		int k = sc.nextInt();
		for(int i = 0; i < k; i++) {
			int a = sc.nextInt();
			for(int j = 0; j <a;j++) {
				set.add(sc.nextInt());
			}
		}
		System.out.println(n-set.size());
	}
}

Measured memory_bytes: 45940
#include<bits/stdc++.h>
#define maxn 500000
using namespace std;
long long mod=1e9+7;
long long step(long long x,long long y) {
    if(y==0ll) return 1ll;
    if(y&1ll) return (x*step(x,y-1ll))%mod;
    else return step((x*x)%mod,y>>1ll);
}
long long inverse(long long x) {
    return step(x,mod-2);
}
int n;
vector<int> a[maxn];
long long fact[maxn];
long long invfact[maxn];
long long precalc() {
    fact[0]=invfact[0]=1;
    for(int i=1;i<=n;i++) {
        fact[i]=(i*fact[i-1])%mod;
        invfact[i]=inverse(fact[i]);
    }
}
/*long long binomial(long long x,long long y) {
    if(y<=0 || y>=x) return 1ll;
    return (fact[x]*((inverse[y]*inverse[x-y])%mod))%mod;
}*/
long long ch[maxn];
long long ph[maxn];
int cs[maxn];
int par[maxn];
long long ans[maxn];
void dfs1(int u,int p=-1) {
    cs[u]=1;
    ch[u]=1;
    for(auto v:a[u]) {
        if(v!=p) {
            par[v]=u;
            dfs1(v,u);
            cs[u]+=cs[v];
        }
    }
    ch[u]=fact[cs[u]-1];
    for(auto v:a[u]) {
        if(v!=p) {
            ch[u]=(ch[u]*ch[v])%mod;
            ch[u]=(ch[u]*invfact[cs[v]])%mod;
        }
    }
    //cout<<u<<" "<<cs[u]<<" "<<ch[u]<<endl;
}
void dfs2(int u,int p=-1) {
    long long cr=(ph[u]*invfact[n-cs[u]])%mod;
    //cout<<cr<<endl;
    for(auto v:a[u]) {
        if(v!=p) {
            cr=(cr*ch[v])%mod;
            cr=(cr*invfact[cs[v]])%mod;
        }
    }
    for(auto v:a[u]) {
        if(v!=p) {
            cr=(cr*inverse(ch[v]))%mod;
            cr=(cr*fact[cs[v]])%mod;
            cr=(cr*fact[n-cs[v]-1])%mod;
            ph[v]=cr;
            cr=(cr*invfact[n-cs[v]-1])%mod;
            cr=(cr*ch[v])%mod;
            cr=(cr*invfact[cs[v]])%mod;
        }
    }
    for(auto v:a[u]) {
        if(v!=p) {
            par[v]=u;
            dfs2(v,u);
        }
    }
    //cout<<u<<" "<<ph[u]<<" "<<ch[u]<<endl;
}
void dfsa(int u,int p=-1) {
    ans[u]=(ch[u]*ph[u])%mod;
    ans[u]=(ans[u]*invfact[cs[u]-1])%mod;
    ans[u]=(ans[u]*fact[n-1])%mod;
    ans[u]=(ans[u]*invfact[n-cs[u]])%mod;
    for(auto v:a[u]) {
        if(v!=p) {
            par[v]=u;
            dfsa(v,u);
        }
    }
}
int main() {
    int u,v;
    scanf("%d",&n);
    precalc();
    for(int i=0;i<n-1;i++) {
        scanf("%d %d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    par[1]=-1;
    dfs1(1);
    ph[1]=1;
    dfs2(1);
    dfsa(1);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}


Measured memory_bytes: 43892
N=int(input())
h=list(map(int,input().split()))
dp=[0]*N
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i] = min(dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i]))
print(dp[N-1])

Measured memory_bytes: 13980
import sys
from collections import deque
def bfs(s,g,n):
    bfs_map = [-1]*n
    bfs_map[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    q.append(y)
    return bfs_map

def update(s,g,bfs_map):
    f = float("inf")
    p = [[None]*2 for i in range(bfs_map[g])]
    y = g
    for i in range(bfs_map[g])[::-1]:
        p[i][1] = y
        for x in v[y]:
            if c[x][y] > 0 and bfs_map[x] == i:
                if c[x][y] < f:
                    f = c[x][y]
                y = x
                p[i][0] = x
                break
        else:
            return 0
    for x,y in p:
        c[x][y] -= f
        c[y][x] += f
    return f

def dinic(s,g,n):
    f = 0
    while 1:
        bfs_map = bfs(s,g,n)
        if bfs_map[g] < 0:
            return f
        cap = update(s,g,bfs_map)
        while cap > 0:
            f += cap
            cap = update(s,g,bfs_map)

n = int(sys.stdin.readline())
d = [int(x) for x in sys.stdin.readline().split()]
c = [[0]*(n+1) for i in range(n+1)]
v = [[] for i in range(n+1)]
for i in range(1,n):
    if d[i-1] > 0:
        v[i].append(n)
        v[n].append(i)
        c[i][n] = float("inf")

for i in range(n-1):
    a,b,p = [int(x) for x in sys.stdin.readline().split()]
    v[a].append(b)
    v[b].append(a)
    c[a][b] = p
    c[b][a] = p

print(dinic(0,n,n+1))



Measured memory_bytes: 14116
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  while(1){
    int m;
    cin >> m;
    if(m==0){
      return 0;
    }
    int a[10],b[10],g,n,i,j,k,l;
    for(i=0;i<m;i++){
      cin >> a[i] >> b[i];
    }
    cin >> g;
    for(i=0;i<g;i++){
      cin >> n;
      ll dp[10][1010];
      for(j=0;j<=m;j++){
        for(k=0;k<=n;k++){
          dp[j][k]=0;
        }
      }
      dp[0][0]=1;
      for(j=1;j<=m;j++){
        for(k=0;k<=n;k++){
          for(l=0;l<=b[j-1];l++){
            int v=a[j-1]*l;
            if(k-v>=0){
              dp[j][k]+=dp[j-1][k-v];
            }
          }
        }
      }
      printf("%lld\n",dp[m][n]);
    }
  }
  return 0;
}


Measured memory_bytes: 3084
ACGT=["A","C","G","T"]
s=list(input())
s.append("0")
s.append(" ")
i=0
ans=[0]
length=0
while s[i] != " ":
  if s[i] in ACGT:
    length += 1
    i += 1
  else:
    ans.append(int(length))
    length = 0
    i += 1

print(max(ans))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
    long n;
    cin >> n;
    long a[n + 1];
    for (long i = 1; i <= n; i++) cin >> a[i];
    if (n % 2 == 0)
    {
        for (long i = n; i >= 2; i = i - 2) cout << a[i] << ' ';
        for (long i = 1; i < n; i = i + 2) cout << a[i] << ' ';
    }
    else
    {
        for (long i = n; i >= 1; i = i - 2) cout << a[i] << ' ';
        for (long i = 2; i < n; i = i + 2) cout << a[i] << ' ';
    }
}

Measured memory_bytes: 5168
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    int a_max=1;
    vector<int> A(N);
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        a_max = max(a,a_max);
        A.at(i) = a;
    }
    sort(A.begin(), A.end());
    vector<int> B(a_max+1, 1);
    int ans=0;
    bool first = true;
    for(int i=0; i<N; i++){
        int p = A.at(i);
        if(B.at(p) == 1){
            ans++;
            if(i>=1){
                if(A.at(i) == A.at(i-1)){
                    if(first) ans -= 2;
                    else ans--;
                    first = false;
                }
                else{
                    first = true;
                }
            }

        }
        p += p;
        while(p < a_max+1){
            B.at(p) = 0;
            p += A.at(i);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 7976
//odds in oddness
#include <bits/stdc++.h>
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define pi pair<int,int> 
#define mod 1000000007
#include<stdio.h>
using namespace std;
int main()
{
	double n;
	cin>>n;
	int k=n;
	if(k%2==0)
	{
		double x=.5;
		printf("%.7f",x);
	}
	else
	{
		double x=(k/2+1)/n;
		printf("%.7f",x);
	}
}


Measured memory_bytes: 256
h, w = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))

c = [[0] * w for i in range(h)]
cnt = 0
flag = 0
for i in range(n):

    for j in range(a[i]):
        if cnt < w:
            c[flag][cnt] = i + 1
            cnt += 1
        else:
            flag += 1
            c[flag][0] = i + 1
            cnt = 1
for i in range(h):
    if i % 2 == 0:
        print(*c[i])
    else:
        print(*c[i][::-1])

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

class A
{
	static void Main()
	{
		var s = Console.ReadLine();

		foreach (var i in new[] { 0, 4, 6, 8 }.Where(i => i < s.Length && s[i] != 'A' || i == s.Length))
			s = s.Insert(i, "A");
		Console.WriteLine(s == "AKIHABARA" ? "YES" : "NO");
	}
}


Measured memory_bytes: 13268
////*24-AUG-19*///
//Why do we fall?//
// So we can learn to pick ourself up!//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define endl "\n"
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr(a,b,c) for(int a=b; a<c; a++)
#define frr(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
#define pii pair<int,int>
#define R(a) ll a; cin >> a;
#define RA(a, n) ll a[(n) + 1] = {}; fr(i, 1, (n)+1) {cin >> a[i];}
#define RM(a, n, m) int a[n + 1][m + 1] = {}; fr(i, 1, n) {fr(j, 1, m) cin >> a[i][j];}
#define reset(X) memset(X, 0, sizeof(X))
const int inf = 1e18;
const int mod=1e9+7;
unsigned int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
bool isPrime(int n)
{   if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
    }

    //z function -  z[i] is the length of the longest common prefix between s and the suffix of s starting at i
vector<int>z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
signed main()
{
    fastio;
    int n;
    cin>>n;
    int dis[n][n];
    fr(i,0,n)
    {
        fr(j,0,n)
        {
            dis[i][j]=inf;
        }
    }
    vector<int>adj[n];
    fr(i,0,n)
    {
        fr(j,0,n)
        {
            char c;
            cin>>c;
            if(i==j)
            {
                dis[i][j]=0;
            }
            if(c=='1')
            {
                dis[i][j]=1;
                 adj[i].pb(j);
            }

        }
    }
    vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
    if (side[st] == -1) {
        q.push(st);
        side[st] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int u : adj[v]) {
                if (side[u] == -1) {
                    side[u] = side[v] ^ 1;
                    q.push(u);
                } else {
                    is_bipartite &= side[u] != side[v];
                }
            }
        }
    }
}
    for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
}
int mx=0;
fr(i,0,n)
{
    fr(j,0,n)
    {
        mx=max(mx,dis[i][j]);
    }
}
if(is_bipartite)
{
    cout<<mx+1<<endl;
}
else
    cout<<-1<<endl;

}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios_base::fixed);
    cout.precision(12);

    var(int, N);
    vector<int> a(N);
    read(a);

    int ans = 0;
    rep(i, 0, N) {
        rep(j, i + 1, N) {
            rep(k, j + 1, N) {
                if (a[i] == a[j] || a[j] == a[k] || a[i] == a[k]) continue;
                vector<int> xs{a[i], a[j], a[k]};
                sort(all(xs));

                if (xs[0] + xs[1] > xs[2]) ++ans;
            }
        }
    }

    print(ans);

    return 0;
}


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

signed main(){
  long long x;
  cin >> x;
  long long sum = 100;
  long long i = 1;
  long day = 0;
  while(true){
    sum += (sum / 100);
    day++;
    if(x <= sum)
      break; 
  }

  cout << day << endl;
}

Measured memory_bytes: 3596
import scala.io.StdIn

object Main {

  def main(args: Array[String]): Unit = {
    val Array(l, r) = StdIn.readLine.split(' ').map(_.toLong)
    val m = 2019l
    val r2 = r min (l + m)
    val ijs = for {
      i <- l until r2
      j <- (i + 1) to r2
    } yield (i * j) % m
    println(ijs.min)
  }

}


Measured memory_bytes: 131312
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in a:c[i-1]+=1
ind=c.index(2)
x=[]
for i in range(n+1):
    if a[i]==ind+1:x.append(i)
m=n+x[0]-x[1]
f=[1]
for i in range(1,n+2):f.append(f[-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
for k in range(1,n+2):
    if k==1:print(n);continue
    if k-1>m:print(comb(n+1,k));continue
    ans=comb(n+1,k)-comb(m,k-1)
    print(ans%mod)

Measured memory_bytes: 13812
n = gets.chomp.to_i
v = gets.chomp.split(" ").map(&:to_i)

if v.all?{|i| i==v[0]}
    puts n/2
    exit
end

even = Hash.new(0)
odd = Hash.new(0)

v.each_with_index do |e, i|
    if i % 2 != 0
        odd[e.to_s] += 1
    else
        even[e.to_s] += 1
    end
end

evenMax = even.max{|x, y| x[1] <=> y[1]}
oddMax = odd.max{|x, y| x[1] <=> y[1]}

if evenMax[0] != oddMax[0]
    puts n - evenMax[1] - oddMax[1]
else
    even.delete(evenMax[0])
    odd.delete(oddMax[0])
    evenSecondMax = even.max{|x, y| x[1] <=> y[1]}
    oddSecondMax = odd.max{|x, y| x[1] <=> y[1]}
    puts [n - evenSecondMax[1] - oddMax[1], n - evenMax[1] - oddSecondMax[1]].min
end

Measured memory_bytes: 23180