akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
*/

ll n,a[200020],sum=0,m[200010]={};

int main(void){
	cin>>n;
	rep(i,n){
		cin>>a[i];
		m[a[i]]++;
	}
	reg(i,1,n)sum+=m[i]*(m[i]-1)/2;
	rep(i,n){
		cout<<sum - m[a[i]]*(m[a[i]]-1)/2 + (m[a[i]]-1)*(m[a[i]]-2)/2<<endl;
	}
	return 0;
}

Measured memory_bytes: 4736
import math
count=2
i=3
prime=[2,3]
for i in range(5,1000000,2):
    if count==10000:break
    check=1
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            check=0
            break
    if check==1:
        prime.append(i)
        count+=1
while 1:
    n=int(input())
    if n==0:break
    print(sum(prime[:n]))


Measured memory_bytes: 6136
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
  ll n,cnt=0;
  cin>>n;
  ll arr[n];
  for(ll i=0;i<n;i++)
  {
    cin>>arr[i];
    if(i!=0 && arr[i-1]>arr[i])
    {
      cnt += arr[i-1]-arr[i];
      arr[i]=arr[i-1];
    }
  }
  cout<<cnt;
  return 0;
}

Measured memory_bytes: 5148
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////





int main() {

	ll N;
	cin >> N;
	string S;
	cin >> S;

	vector<bool> s(N + 1);
	repn(i, N) { 
		if (S[i - 1] == 'o') { s[i] = 1; }
		else { s[i] = 0; }
	}

	vector<ll> ans(N + 1, -1);
	
	rep(j, 4) {
		
		vector<bool> v(N + 1);
		v[1] = j % 2;
		v[2] = j / 2;


		for (ll i = 3; i <= N; i++) {
			v[i] = v[i - 2] ^ v[i - 1] ^ s[i - 1];
		}

		//repn(i, N)cout << v[i];
		//cout << endl;

		if (v[N - 1] ^ v[N] ^ v[1] == s[N] && v[N] ^ v[1] ^ v[2] == s[1]) {
			repn(i, N) { ans[i] = v[i];}
			break;
		}

		
	}

	//repn(i, N) cout << ans[i];

	if (ans[1] == -1) { cout << -1; }
	else {
		repn(i, N) {
			if (ans[i] == 0) { cout << "W"; }
			else { cout << "S"; }
		}
	}



	system("PAUSE");
}


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

int main() {
    int k;
    cin >> k;
    int a[] = { 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};
    cout << a[k - 1] << endl;
    return 0;
}


Measured memory_bytes: 256
use std::io;

fn gets() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn main() {
    let line = gets();
    let a = line.trim().parse::<u32>().unwrap();
    println!("{}", a * (1 + a * (1 + a)));
}


Measured memory_bytes: 2100
N = int(input())

lst = []

for i in range(N):
   lst.append(input())

C0 = str(lst.count('AC'))
C1 = str(lst.count('WA'))
C2 = str(lst.count('TLE'))
C3 = str(lst.count('RE'))

result = 'AC x ' + C0 +'\nWA x ' + C1 + '\nTLE x ' + C2 + '\nRE x ' + C3

print(result)

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

int main()
{
	int n,ans=0;
	cin >> n;
	int b[n] = {0};
	for (int i = 0; i < n-1; ++i) cin >> b[i];
	
	ans += b[0];
	for (int i = 1; i < n-1; ++i)
	{
		ans += min(b[i-1], b[i]);
	}
	ans += b[n-2];
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
from bisect import bisect

n,h=map(int,input().split())
b=[]
a_max=0
for i in range(n):
  x,y=map(int,input().split())
  b.append(y)
  a_max=max(a_max,x)

b=sorted(b)
lim_inx=bisect(b,a_max)

cnt=0
total=0
inx=n-1
while total<h:
  if inx>=lim_inx:
    total+=b[inx]
    cnt+=1
    inx-=1
  else:
    if (h-total)%a_max==0:
      cnt+=(h-total)//a_max
    else:
      cnt+=(h-total)//a_max+1
    print(cnt)
    exit()
print(cnt)

Measured memory_bytes: 8276
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, gcd;
    cin >> n;
    int a[n], p[2000010];
    bool pairwise = true;
    for (int i = 0; i < 2000010; i++) p[i] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i == 0) gcd = a[i];
        gcd = __gcd(a[i], gcd);
        p[a[i]]++;
    }
    for (int i = 2; i < 2000010; i++)
    {
        int sum = 0;
        for (int j = i; j < 2000010; j += i)
        {
            sum += p[j];
            if (sum > 1)
            {
                pairwise = false;
                break;
            }
        }
        if (pairwise == false) break;
    }
    if (pairwise == true) cout << "pairwise coprime";
    else if (gcd == 1) cout << "setwise coprime";
    else cout << "not coprime";
}

Measured memory_bytes: 15268
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  int n;
  cin>>n;
  std::vector<int> h(n);
  for(int i=0;i<n;i++){
    cin>>h[i];
  }
  for(int i=n-1;i>=1;i--){
    if(h[i-1]>h[i]){
      h[i-1]--;
    }
  }
  for(int i=1;i<n;i++){
    if(h[i-1]>h[i]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;

  return 0;
}


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

typedef long long ll;
typedef pair<int,int> P;

const int INF=1e9;
const int MOD=1e9+7;

int main(){
    string s,t;
    cin >> s >> t;
    int ans=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]) ans++;
    }
    cout << ans << endl;
}

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

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

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

const char newl = '\n';

const ll mod = 1000000007;
//const ll mod = 998244353;

const int MAX_N = 100010;
ll fact[MAX_N],fact_inv[MAX_N],inv[MAX_N];

ll pow_mod(ll a,ll b) {
    ll ret;
    if (b < 0) ret = pow_mod(a,mod+b-1);
    else if (b == 0) ret = 1;
    else if (b == 1) ret = a;
    else {
        ll c = pow_mod(a,b/2);
        if (b%2) ret = (c*c)%mod*a%mod;
        else ret = c*c%mod;
    }
    return ret;
}

void init(int x) {
    fact[0] = 1;fact[1] = 1;
    for (int i = 2;i <= x;++i) fact[i] = fact[i-1]*i%mod;
    fact_inv[x] = pow_mod(fact[x],-1);
    for (int i = x;i > 0;--i) fact_inv[i-1] = fact_inv[i]*i%mod;
    for (int i = 1;i <= x;++i) inv[i] = fact_inv[i]*fact[i-1]%mod;
}

ll combi(ll a, ll b) {
    return fact[a]*fact_inv[b]%mod*fact_inv[a-b]%mod;
}

int main() {
    init(2000);
    int s;
    cin >> s;
    ll ans = 0;
    for (int i = 1;i < s/3+1;++i) {
        (ans += combi(s-i*3+i-1,i-1)) %= mod;
    }
    cout << ans << newl;
}

Measured memory_bytes: 3692
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
#define arrprint(v,n) rep(i,0,n-1)cout << v[i] << " ";cout << endl;
#define matprint(v,n,m) rep(i,0,n-1){rep(j,0,m-1){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
typedef long long ll;
typedef pair<int,int> P;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

ll p5(ll x){
    return x*x*x*x*x;
}

int main(){
    ll x;
    cin >> x;
    ll a = 0;
    ll b = 0;
    while(-1*p5(b) < x)b--;
    while(p5(a) - p5(b) != x){
        a++;
        while(p5(a) - p5(b) > x)b++;
    }

    cout << a << " "  << b << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 3596
if __name__=='__main__' :
    c1=input().split()
    c2=input().split()

    cx1 = int(c1[0])
    cy1 = int(c1[1])
    cr1 = int(c1[2])

    cx2 = int(c2[0])
    cy2 = int(c2[1])
    cr2 = int(c2[2])

    d = ((cx1-cx2)**2+(cy1-cy2)**2)**(1/2)
    if d > cr1+cr2 :
        print(4)
    elif d == cr1+cr2 :
        print(3)
    elif (d < cr1+cr2) and (abs(cr1-cr2) < d) :
        print(2)
    elif  abs(cr1-cr2) == d :
        print(1)
    elif d < abs(cr1-cr2) :
        print(0)




Measured memory_bytes: 5624
import sys

K = int(input())

count = 1
ans = -1
remainder = 0
check = [False] * (K + 1)

while True:
    remainder = (remainder * 10 + 7) % K
    if remainder == 0:
        ans = count
        break

    if check[remainder]:
        break

    check[remainder] = True
    count += 1

print(ans)


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

int main() {
  char c;
  cin >> c;
  cout << char(c+1) << endl;

  return 0;
}


Measured memory_bytes: 256
from math import log2, ceil

N, K = tuple([int(x) for x in input().split(' ')])

M = min(N, K)
ans = sum([0.5 ** ceil(log2(K) - log2(n)) for n in range(1,M+1)])
ans += max(N-K, 0)
ans /= float(N)

print(ans)

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

/////////////////////////////////////////////////////////////
ll mypow_core(ll x, int n, ll result) {
  if (n == 0) {
    return result;
  }

  if (n % 2 == 0) {
    return mypow_core(x * x, n / 2, result);
  } else {
    return mypow_core(x, n - 1, x * result);
  }
}

ll mypow(ll x, int n) { return mypow_core(x, n, 1); }
/////////////////////////////////////////////////////////////

const int MAX_N = (int)(2e5 + 5);

int n;
ll a[MAX_N];
ll b[MAX_N];

ll decide(int k) {
  // printf("k: %d\n", k);

  // for (int i = 0; i < n; ++i) {
  //   printf("%lld ", b[i]);
  // }
  // printf("\n");

  ll t = mypow(2LL, k);

  vector<ll> ma;
  vector<ll> mb;

  for (int i = 0; i < n; ++i) {
    ma.push_back(a[i] % (2LL * t));
    mb.push_back(b[i] % (2LL * t));
  }

  sort(mb.begin(), mb.end());

  // for (auto &e : mb) {
  //   printf("%lld ", e);
  // }
  // printf("\n");

  ll cnt = 0LL;

  for (auto &e : ma) {
    ll fst = upper_bound(mb.begin(), mb.end(), 2LL * t - e - 1LL) - lower_bound(mb.begin(), mb.end(), t - e);
    ll snd = upper_bound(mb.begin(), mb.end(), 4LL * t - e - 1LL) - lower_bound(mb.begin(), mb.end(), 3LL * t - e);
    cnt += fst + snd;
  }

  return cnt % 2LL;
}

int main(void) {
  // Here your code !
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%lld", &(a[i]));
  }

  for (int i = 0; i < n; ++i) {
    scanf("%lld", &(b[i]));
  }

  vector<ll> target_bits;

  for (int i = 0; i < 30; ++i) {
    target_bits.push_back(decide(i));
  }

  ll base = 1LL;
  ll ans = 0LL;

  for (int i = 0; i < target_bits.size(); ++i) {
    ans += target_bits[i] * base;
    base *= 2LL;
  }

  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 10352
a,b,k = gets.split.map(&:to_i)

if k >= (a+b) then
     print(0," ",0,"\n")
elsif k < (a+b) then
    if k >= a then
        print(0," ",b-(k-a),"\n")
    else 
        print(a-k," ",b,"\n")
    end
else
    if k >=a then
        print(0," ",b-(k-a),"\n")
    else
        print(a-k," ",b,"\n")
    end
end


Measured memory_bytes: 1788
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 210000;

int n,m;
int v[maxn];
int p[maxn],a[maxn];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]),a[p[i]]++;
	for(int i=1;i<=n;i++) 
		for(int j=max(i-a[i],0);j<i;j++) v[j]++;
	
	int ans=0;
	for(int i=0;i<n;i++) if(!v[i]) ans++;
	
	while(m--)
	{
		int x,y; scanf("%d%d",&x,&y);
		int c=p[x];
		if(c-a[c]>=0&&v[c-a[c]]==1) ans++;
		if(c-a[c]>=0) v[c-a[c]]--; a[c]--;
		c=y; p[x]=c;
		if(c-a[c]-1>=0&&!v[c-a[c]-1]) ans--;
		a[c]++; if(c-a[c]>=0) v[c-a[c]]++;
		printf("%d\n",ans);
	}
	
	return 0;
}


Measured memory_bytes: 3840
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
#define llMAX 9223372036854775807
#define llMIN -9223372036854775808
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  ll ans=0;
  cin >> n;
  vi a(n),b(n);
  REP(i,n-1){
    cin>>k;
    b[k-1]++;
  }

  REP(i,n){
    cout<<b[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 6372
INF = 10_000_000
N = gets.to_i
H = gets.split.map(&:to_i)
ans = 0

loop do
  break if H.all?(&:zero?)

  head = Array.new(N)
  ranges = {}
  
  H.each_index do |i|
    if head[i - 1] && H[i] > 0
      head[i] = head[i - 1]
    elsif head[i - 1].nil? && H[i] > 0
      head[i] = i
    end
  end
  
  head.each_with_index do |head, tail|
    ranges[head] = tail if head
  end
  
  ranges.each do |head, tail|
    w = H[head .. tail].min
    (head .. tail).each{|i| H[i] -= w}
    ans += w
  end
end
puts ans

Measured memory_bytes: 1916
/*

	TRY_TO_BE8T_ME

*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define FIO ios::sync_with_stdio(0);
ll gcd(ll a,ll b){while(a&&b)a>b?a%=b:b%=a;return a+b;}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
int main() 
{
	FIO;
	ll i,j,k,c=0,n,m,d=0,maxim=0;
	cin>>n;
	for(i=1;i<=1000;i++)
	{
		for(j=2;j<=1000;j++)
		{
			c=pow(i,j);
			if(c>n)
				break;
			else
			{
				if(c>=maxim)
					maxim=c;
			}
		}
	}
	cout<<maxim;
	return 0;
}

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

#define REP(A, H) for(int A = 0; A < H; A++)
#define ALL(c) c.begin(), c.end()
#define MOD 1000000007

typedef long long ll;

bool check(std::vector<char> four) {
  REP(i, 4) {
    std::vector<char> l(four);
    if (i != 0) {
      char t = l[i - 1];
      l[i - 1] = l[i];
      l[i] = t;
    }
    REP(j, 2) {
      bool res = l[j] == 0 && l[j + 1] == 2 && l[j + 2] == 1;
      if (res) return false;
    }
  }
  return true;
}

ll memo[101][4][4][4];

void init_memo() {
  REP(i, 101) REP(j, 4) REP(k, 4) REP(l, 4) memo[i][j][k][l] = -1;
}

ll dfs(int depth, int n, std::vector<char> three) {
  if (memo[depth][three[0]][three[1]][three[2]] != -1) {
    return memo[depth][three[0]][three[1]][three[2]];
  }
  if (depth == n) {
    return 1;
  }
  ll ret = 0;
  REP(c, 4) {
    std::vector<char> four(4); 
    four[0] = three[0];
    four[1] = three[1];
    four[2] = three[2];
    four[3] = (char)c;
    std::vector<char> nthree(3);
    nthree[0] = three[1];
    nthree[1] = three[2];
    nthree[2] = (char)c;
    if (check(four)) {
      ret = (ret + dfs(depth + 1, n, nthree)) % MOD;
    }
  }
  memo[depth][three[0]][three[1]][three[2]] = ret;
  return ret;
}

int main(void) {
  int n; std::cin >> n;
  init_memo();
  std::vector<char> start(3);
  REP(i, 3) start[i] = 3;
  std::cout << dfs(0, n, start) << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define F first
#define S second
#define pb emplace_back
#define mt make_tuple
#define gcd __gcd
#define PI 3.141592653589
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
// Iterator
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define what(x) cerr << #x << " : " << x << "\n"
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define M 998244353
#define N 100005  //check the limits, man
int main()
{
    int n,m,c,x,a,i;
    in3(n,m,c);
    vi v(m);
    read(v,i,m);
    int ans=0;
    while(n--)
    {
        x=c;
        rep(i,m)
            in(a),a*=v[i],x+=a;
        if(x>0)
            ans++;
    }
    out(ans);
}





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

    int ichi = N%10;
    if (
        ichi == 2 ||
        ichi == 4 ||
        ichi == 5 ||
        ichi == 7 ||
        ichi == 9) {
            cout << "hon" << endl;
    } else if (
        ichi == 0 ||
        ichi == 1 ||
        ichi == 6 ||
        ichi == 8) {
            cout << "pon" << endl;
    } else {
        cout << "bon" << endl;
    }


    return 0;
}

Measured memory_bytes: 3636
let cmbs = (arrA, arrB) => {
  let r = []
  arrA.map((a) => {
    arrB.map((b) => {
      r.push([a, b])
    })
  })
  return r
}
let solve = (input) => {
  const n = Number(input)
  const p = n % 2 === 0 ? n : n - 1
  const clusters = Array.from({ length: Math.ceil(p / 2) }).map((_, i) => {
    const l = i + 1

    const m = n % 2 !== 0 ? n - l : n - l + 1
    return [l, m]
  })
  if (n % 2 !== 0) {
    clusters.push([n])
  }
  let r = []
  for (let i = 0; i < clusters.length; i++) {
    for (let j = i + 1; j < clusters.length; j++) {
      // r.concat(
      r = [...r, ...cmbs(clusters[i], clusters[j])]
    }
  }
  let len = r.length
  let rr = r
    .map((r) => {
      return `${r[0]} ${r[1]}`
    })
    .join("\n")
  const rrr = [len, rr].join("\n")

  return rrr
}
const input = require("fs").readFileSync("/dev/stdin", "utf8")
console.log(solve(input.trim()))


Measured memory_bytes: 10824
import sys
from collections import deque
import copy
import math

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [S] = [(input_raw[0])]
    input_raw = read_func().strip().split()
    [K] = [int(input_raw[0])]
##    if len(S) >= K:
##        min_s = "zzzzzzz"
##        for i in range(len(S) - K):
##            if S[i : i + K]< min_s:
##                min_s = S[i : i + K]
##        print min_s
##        return
##    else:
    sub_list = set([])
    for i in range(len(S)):
        for j in range(i + 1, i + 6):
            sub_list.add(S[i:j])

    sub_list = list(sub_list)
    sub_list.sort()
    print sub_list[K - 1]


if __name__ == '__main__':
    main()


Measured memory_bytes: 32796
#!/usr/bin/env python
import os
import operator
import sys
from io import BytesIO, IOBase

def inar():
    return [int(k) for k in input().split()]
def main():
    n,we=map(int,input().split())
    arr=[]
    for i in range(n):
        w,v=inar()
        arr.append([w,v])
    arr.sort()
    dp=[]
# ?print(arr)
    for i in range(n+1):
        lis=[0]*(we+1)
        dp.append(lis)
    # for i in range(n+1):
    #     print(*dp[i])
    for i in range(1,n+1):
        for j in range(1,we+1):
            if arr[i-1][0]>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]])
    # for i in range(n+1):
    #     print(*dp[i])
    print(dp[n][we])








BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

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

typedef long long ll;
typedef pair<int,int> pii;

const int N = 2e5;

int n,d,a;
pii li[N+5];

int get_idx(int x){
	int l = 0;
	int r = n;
	if(x >= li[r].first) return r;
	int ret = l;
	while(l<=r){
		int mid = (l+r)/2;
		if(li[mid].first <= x){
			ret = mid;
			l = mid+1;
		} else {
			r = mid-1;
		}
	}
	return ret;
}

ll ps[N+5];

int main(){
	scanf("%d%d%d",&n,&d,&a);
	for(int i=1;i<=n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		li[i] = make_pair(u,v);
	}
	sort(li+1,li+n+1);
	ll ans = 0ll;
	ll acc = 0ll;
	for(int i=1;i<=n;i++){
		acc += ps[i];
		li[i].second -= acc;
		if(li[i].second <= 0) continue;
		ll mult = ( li[i].second + a - 1 ) / a;
		ans += mult;
		int ujung = li[i].first + 2*d;
		int idx = get_idx(ujung);
		acc += mult*(ll)(a);
		ps[idx+1] -= mult*(ll)(a);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3328
while True:
    [n,m,a]=input().split()
    if [n,m,a]==["0","0","0"]: break
    [n,m]=[int(n),int(m)]
    yokobo={}
    for k in range(m):
        [h,p,q]=input().split()
        yokobo[h,p]=q
        yokobo[h,q]=p
    high=1000
    while high>0:
        if (str(high),a) in yokobo:
            a=yokobo[str(high),a]
        high-=1
    print(a)

Measured memory_bytes: 8040
#define first f
#define second s
#define ll long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#include <bits/stdc++.h>
#define pii pair<string,int>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1e5+5;
const int MOD=998244353;
const double PI=acos(-1);
const double e=2.718281828459;


int main()
{
    int n,r;
    scanf("%d%d",&n,&r);
    if(n>=10){
        printf("%d\n",r);
    }
    else{
        printf("%d\n",r+(10-n)*100);
    }
    return 0;
}


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

const int Maxn = 105;

int n;
int a[Maxn];
int nd[Maxn];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a + n);
    if (a[n - 1] != a[n - 2] || (n > 2 && a[n - 1] == 1))
        printf("Impossible\n");
    else {
        for (int i = 1; i < a[n - 1]; i++)
            nd[max(i, a[n - 1] - i)]++;
        int lim = (a[n - 1] + 1) / 2;
        int spec = 0;
        for (int i = 0; i < n - 2; i++)
            if (a[i] < lim) {
                printf("Impossible\n"); return 0;
            } else nd[a[i]]--;
        for (int i = 0; i < a[n - 1]; i++)
            if (nd[i] > 0) {
                printf("Impossible\n"); return 0;
            }
        if (nd[(a[n - 1] + 1) / 2] != 0) {
            printf("Impossible\n"); return 0;
        }
        printf("Possible\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll k;
	cin>>k;
	queue<ll>q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);
	q.push(7);
	q.push(8);
	q.push(9);
	ll count=0;
	ll num;
	while(count<k)
	{
		num=q.front();
		q.pop();
		if(num%10!=0)
			q.push(num*10+num%10-1);
		q.push(num*10+num%10);
		if(num%10!=9)
			q.push(num*10+num%10+1);
		count++;
	}
	cout<<num;
}


Measured memory_bytes: 1792
package main

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

type part struct {
	category rune
	size     int
}

type parts []part
type byCategory struct{ parts }
type bySize struct{ parts }

func (p parts) Len() int                { return len(p) }
func (p parts) Swap(i, j int)           { p[i], p[j] = p[j], p[i] }
func (b byCategory) Less(i, j int) bool { return b.parts[i].category < b.parts[j].category }
func (b bySize) Less(i, j int) bool     { return b.parts[i].size < b.parts[j].size }

func main() {
	io := newIo()
	n := io.nextInt()

	seq := []part{}
	for i := range make([]struct{}, 3) {
		for range make([]struct{}, n) {
			seq = append(seq, part{rune('A' + i), io.nextInt()})
		}
	}
	sort.Sort(sort.Reverse(byCategory{seq}))
	sort.Stable(bySize{seq})

	var ans, i, j int
	for _, v := range seq {
		switch v.category {
		case 'A':
			i++
		case 'B':
			ans += i * (n - j)
		case 'C':
			j++
		}
	}
	fmt.Println(ans)
}

type io struct {
	reader    *bufio.Reader
	tokens    []string
	nextToken int
}

func newIo() *io {
	return &io{
		reader: bufio.NewReader(os.Stdin),
	}
}

func (io *io) nextLine() string {
	var buffer []byte
	for {
		line, isPrefix, _ := io.reader.ReadLine()
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *io) nextString() string {
	for io.nextToken >= len(io.tokens) {
		line := io.nextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *io) nextInt() int {
	i, _ := strconv.Atoi(io.nextString())
	return i
}


Measured memory_bytes: 27136
#include<bits/stdc++.h>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;

const int maxn=3007,mo=1e9+7;

int n,m,Ans;
int f[maxn][maxn][2];

void Init(){
	scanf("%d%d",&n,&m);
}

void Plus(int &a,int b){
	(a+=b)%=mo;
}
void Solve(){
	f[0][0][1]=1;
	fo(i,1,n) f[0][i][0]=1;
	fo(i,0,m-1){
		fo(j,0,n)
			fo(k,0,1){
				if (j>0){
					Plus(f[i+1][j-1][k|(j-1==0)],f[i][j][k]);
					Plus(f[i+1][j][k|(j-1==0)],f[i][j][k]);
				}
				if (j<n){
					Plus(f[i+1][j+1][k],f[i][j][k]);
					Plus(f[i+1][j][k],f[i][j][k]);
				}
			}
	}
}

void Print(){
	fo(i,0,n) Plus(Ans,f[m][i][1]);
	printf("%d\n",Ans);
}

int main(){
	Init();
	Solve();
	Print();
	return 0;
}

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

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

int main(){
	int n;
	bool ani[100000];
	string s;
	cin >> n >> s;
	for(int i = 0;i < 4;i++){
		ani[0] = dx[i];
		ani[1] = dy[i];
		for(int j = 1;j < n - 1;j++){
			if(ani[j] && s[j] == 'o') ani[j + 1] = ani[j - 1];
			else if(ani[j] && s[j] == 'x') ani[j + 1] = !ani[j - 1];
			else if(!ani[j] && s[j] == 'o') ani[j + 1] = !ani[j - 1];
			else ani[j + 1] = ani[j - 1];
		}
		bool f = true;
		if(s[n - 1] == 'o'){
			if((ani[n - 1] && ani[n - 2] != ani[0]) || (!ani[n - 1] && ani[n - 2] == ani[0])) f = false;
		}else{
			if((ani[n - 1] && ani[n - 2] == ani[0]) || (!ani[n - 1] && ani[n - 2] != ani[0])) f = false;
		}
		if(s[0] == 'o'){
			if((ani[0] && ani[n - 1] != ani[1]) || (!ani[0] && ani[n - 1] == ani[1])) f = false;
		}else{
			if((ani[0] && ani[n - 1] == ani[1]) || (!ani[0] && ani[n - 1] != ani[1])) f = false;
		}
		if(f){
			for(int i = 0;i < n;i++){
				if(ani[i]) cout << "S";
				else cout << "W";
			}
			cout << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var N = F;
		var map = new int[N, 2];
		for (var i = 0; i < 2; i++)
		{
			var I = G;
			for (var x = 0; x < N; x++) map[x, i] = I[x];
		}
		var max = new int[N, 2];
		for (var x = N-1; x >= 0; x--)
			for (var y = 1; y >= 0; y--)
			{
				if (x < N - 1) max[x, y] = Max(max[x, y], max[x + 1, y]);
				if (y < 1) max[x, y] = Max(max[x, y], max[x, y + 1]);
				max[x, y] += map[x, y];
			}
		Console.WriteLine(max[0, 0]);
	}
}


Measured memory_bytes: 13396
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] pri = new int[25000];
		pri[0] = 2;
		pri[1] = 3;
		pri[2] = 5;
		pri[3] = 7;
		pri[4] = 11;
		pri[5] = 13;
		pri[6] = 17;
		pri[7] = 19;
		pri[8] = 23;
		pri[9] = 29;
		int fl = 0;
		int a=0;
		int b=0;
		int c=0;
		while(pri[a]<=250000){
			fl++;
			for(int i=0;i<8;i++){
				a=0;
				b=0;
				c=0;				
				if(i==0){
					c=1;
				}else if(i>0){
					c=pri[2+i];
				}
				while(pri[a]!=0){
					if((30*fl + c)%pri[a]==0){
						b=1;
						break;
					}
					a++;
				}
				if(b==0){
					pri[a]=(30*fl + c);
				}
			}					
		}
		
		boolean exit = true;
		while(exit==true){
			int n = sc.nextInt();
			if(n==0)exit=false;
			if(exit==true){
				int sum=-1;
				int i=0;
				while(true){
					if(pri[i]>n)sum++;
					if(pri[i]>2*n)break;
					i++;
				}
				System.out.println(sum);
			}
		}
	}
	
}

Measured memory_bytes: 21096
#include <iostream>
#include <string>
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<ll(b);i++)
#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)
#define endl "\n"
#define ALL(x) x.begin(),x.end()
#define ALLR(x) x.rbegin(),x.rend()
using namespace std;

int k;
string s;
int main() {
	cin >> k >> s;
	int sl = s.length();
	if(sl > k){
		rep(i, 0, k) cout << s[i];
		cout << "..." << endl;
	}
	else {
		cout << s << endl;
	}
    return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
template<typename T>
void print(T x) {
    cout << x << endl;
}
int main(void) {
    ll n, h, w; cin >> n >> h >> w;
    ll ans = 0;
    rep(i, n) {
        ll a, b; cin >> a >> b;
        if(a >= h && b >= w) ans++;
    }
    print(ans);
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define ull unsigned long long
#define ld long double

#define mod 1000000007
#define EULER 2.7182818284
#define INF 1000000000

#define pb push_back
#define ins insert
#define IT iterator
#define PQ priority_queue

#define fi first
#define se second
#define maxe max_element
#define mine min_element
#define er erase
#define lb lower_bound
#define ub upper_bound

#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define ex 1e18

#define mem(v,i) memset(v,i,sizeof(v)) // v is array. To set all elements to 0 or -1 only. mem(arr,0);


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORd(i,a,b) for(int i=(a);i>=(b);i--)
#define FORl(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORN(i,n) for(int i=(0);i<(n);i++)
#define FORR(i,n) for(int i=(n);i>=0;i--)
#define bs bitset
#define bpc(a) __builtin_popcount(a)

ll max(ll a,ll b)
{
    if(a>b)return a;return b;
}
ll min(ll a,ll b)
{
    if(a<b)return a;return b;
}

ll mypow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}
//..............................!!!!!!Get ready to fight!!!!!!............................



int main()
{
    fast
    ll n,i;
    cin>>n;
    ll a[n];
    unsigned ll exe=1000000000000000000;
   
    for(i=0;i<n;i++)
    {
        cin>>a[i];
       
       
    }
    sort(a,a+n);
    unsigned ll prod=1;
    bool f=true;
    bool p=false;
    for(i=0;i<n;i++)
    {
        
        if(a[i]>(exe/prod))
        {
            f=false;
            break;
           
        }
        else
        {
            prod=prod*a[i];
        }
        if(prod==0)
        {
            p=true;
            break;
        }
        
    }
    if(p)
    cout<<"0";
    else if(f)
    cout<<prod;
    else
    cout<<"-1";
        
    
    return 0;
}

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

int main(){

    string e,o;

    cin >> o >> e;

    rep(i,max(o.size(),e.size())){
        if(i<o.size()){
            cout << o[i];
        }
        if(i<e.size()){
            cout << e[i];
        }
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 256
import bisect

A, B, Q = map(int, input().split())
S = [ int(input()) for _ in range(A) ] 
T = [ int(input()) for _ in range(B) ] 

for _ in range(Q):
  x = int(input())
  s_ = bisect.bisect_right(S, x)
  t_ = bisect.bisect_right(T, x)
  s_min = x-S[max(s_-1, 0)]
  s_max = S[min(s_, A-1)]-x
  t_min = x-T[max(t_-1, 0)]
  t_max = T[min(t_, B-1)]-x
  #print(s_min, s_max, t_min, t_max)
  if s_min < 0:
    s_min =  3 * 10 ** 10 + 7
  if s_max < 0:
    s_max = 3 * 10 ** 10 + 7
  if t_min < 0:
    t_min = 3 * 10 ** 10 + 7
  if t_max < 0:
    t_max = 3 * 10 ** 10 + 7
  print(min([
    max(s_min, t_min), 
    max(s_max, t_max), 
    s_min + t_max + min(s_min, t_max),
    s_max + t_min + min(s_max, t_min)
  ]))
  

Measured memory_bytes: 12088
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", ans);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

using Graph = vector<vector<pair<ll, ll>>>;
using Pi = pair<ll, ll>;

Graph g(100005);
const ll MOD = 100000000000000000;

//準備...Graph g;
//入力...g[Node].push_back(make_pair(nextNode, weight));

vector<ll> djkstra(Graph &g, ll s) {
	vector<ll> dist(g.size(), MOD);
	dist[s] = 0;
	priority_queue<Pi, vector<Pi>, greater<Pi>> que;
	que.emplace(dist[s], s);
	while ( !que.empty() ) {
		ll cost; ll u; tie(cost, u) = que.top(); que.pop();
		if (dist[u] < cost) continue;
		for (auto &x : g[u]) {
			ll v; ll nc; tie(v, nc) = x;
			if (chmin(dist[v], dist[u] + nc)) que.emplace(dist[v], v);
		}
	}

	return dist;
}

int main(void) {
	int n;
	cin >> n;
	rep (i, n - 1) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		g[a].eb(b, c);
		g[b].eb(a, c);
	}

	int q, k;
	cin >> q >> k;
	k--;
	vector<ll> dist = djkstra(g, k);

	vector<ll> ans;
	rep (i, q) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		ans.pb(dist[x] + dist[y]);
	}

	rep (i, q) cout << ans[i] << '\n';
	return 0;	
}

Measured memory_bytes: 11120
#include<iostream>
#include<vector>
#include<deque>
#include<queue> 
#include<functional>
#include<climits>

//#define INF 2147483647
#define INF INT_MAX

using namespace std;

int n;
priority_queue<pair<int, int>,  deque<pair<int,int>>, greater<pair<int,int>>> q;
vector<vector<int>> c;
vector<int> d;


int input(){
  cin >> n;
  int u = 0, k = 0, v = 0;
  c.resize(n);
  for( int i = 0; i < n; i++ ){
    cin >> u >> k;
    c[u].resize(n, -1);
    for( int j = 0; j < k; j++ ){
      cin >> v;
      cin >> c[u][v];
    }
  }
  d.resize(n, INF);
  return 0;
}

int checkContinue(){
  for( int i = 0; i < n; i++ ){
    if( d[i] == INF ){ return 1; }
  }
  return 0;
}

int run(){
  q.emplace(pair<int,int>(0,0));
  while( checkContinue() ){
    pair<int, int> p = q.top();
    q.pop();
    if( d[p.second] < p.first ){ continue; }
    d[p.second] = p.first;
    for( int i = 0; i < n; i++ ){
      if( c[p.second][i] < 0 ){ continue; }
      q.push(pair<int,int>(p.first+c[p.second][i], i));
      // cout << p.first+c[p.second][i] << "," << i << endl;
    }
  }
  for( int i = 0; i < n; i++ ){
    cout << i << " " << d[i] << endl;
  }
  return 0;
}

int main(){
  input();
  run();
  return 0;
}




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

int dp[55][55][55][55];
int W,H;
char C[55][55];
int dx[]={1,0};
int dy[]={0,1};

typedef pair<int,int> P;
vector<P> pos[56];

bool isout( P p, int x1,int y1,int x2,int y2){
  return p.first < x1 || x2  < p.first || p.second < y1 || y2 < p.second;
}

int solve(int x1,int y1,int x2,int y2){
  int &ret = dp[x1][y1][x2][y2];
  if( ret != -1 ) return ret;
  if( x1 == x2 && y1 == y2 ) return ret=0;
  ret = -(1<<29);


  if( islower( C[x1][y1] ) ){
    int aid = C[x1][y1] - 'a';
    for( P p : pos[aid] ){
      if( isout( p, x1,y1,x2,y2 ) ) continue;
      if( p.first == x2 && p.second == y2 ) continue;
      for(int i=0;i<2;i++){
        int nx = x1+dx[i], ny = y1+dy[i];
        if( isout( P(nx,ny), x1,y1,p.first,p.second ) ) continue;
        if( C[nx][ny] == '#' ) continue;
        // cout << x1 << ", "<< y1 << " -> " << nx << ", "<< ny << " : " << p.first << ", " << p.second << " -> " << x2 << ", "<< y2 << endl;
        ret = max( ret, solve( nx,ny,p.first,p.second)+1+solve(p.first,p.second,x2,y2) );
      }      
    }
  }

  for(int i=0;i<2;i++){
    int nx = x1+dx[i], ny = y1+dy[i];
    if( isout( P(nx, ny), x1,y1,x2,y2 ) ) continue;
    if( C[nx][ny] == '#' ) continue;
    ret = max( ret, solve( nx,ny, x2,y2 ) );      
  }    

  //cout << x1 << ", "<< y1 << " - "<<x2 << ", "<< y2 << " :" << ret << endl;
   
  return ret;
}

bool used[55][55];
bool dfs(int x,int y){
  if( used[x][y] ) return false;
  used[x][y] = true;
  if( x == W+1 && y == H+1 ) return true;
  if( x>W+1 || y>H+1 ) return false;
  if( C[x][y] == '#' ) return false;
  if( dfs(x+1,y) ) return true;
  if( dfs(x,y+1) ) return true;  
  return false;
}

void view(){
  for(int i=0;i<=H+1;i++){
    for(int j=0;j<=W+1;j++) cout << C[j][i];
    cout << endl;
  }
}


int main(){
  while( cin >> H >> W && (H|W) ){

    for(int i=0;i<56;i++) pos[i].clear();

    for(int i=0;i<=H+1;i++)
      for(int j=0;j<=W+1;j++)
        C[j][i] = '#';
    C[0][0] = '.';
    C[0][1] = '.';
    C[1][0] = '.';
    C[W+1][H+1] = '.';
    C[W+1][H] = '.';
    C[W][H+1] = '.';

    for(int i=1;i<=H;i++){
      for(int j=1;j<=W;j++){
        cin >> C[j][i];
        if( isupper(C[j][i]) )
          pos[C[j][i]-'A'].push_back( P(j,i) );        
      }
    }
    // view();
    memset( used,0,sizeof(used) );
    if( !dfs( 0,0 ) ) cout << -1 << endl;
    else {     
      memset( dp,-1,sizeof(dp));
      int res = solve(0,0,W+1,H+1);
      cout << res << endl;
    }
  }
}

Measured memory_bytes: 38768
n,k=map(int,input().split())
s=input()

stand = [0]
rev = [0]
if s[0] == '0':	
	rev.append(0)
cnt = 1
for i in range(1,n):
	if s[i] == s[i-1]:
		cnt += 1
	else:
		if s[i-1] == '0':
			stand.append(cnt)	
		else:
			rev.append(cnt)
		cnt = 1
if s[n-1] == '0':
	stand.append(cnt)
	rev.append(0)
else:
	rev.append(cnt)

for i in range(1,len(rev)):
	rev[i] += rev[i-1]
	
for i in range(1,len(stand)):
	stand[i] += stand[i-1]

ans = 0

k = min(k,len(stand)-1)
for i in range(len(rev) - k - 1):
	sms = rev[i+k+1] - rev[i] + stand[i+k] - stand[i]
	ans = max(ans,sms)

print(ans)

Measured memory_bytes: 45168
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int a,b,n;
vector<int> licz(vector<int> te_same, vector<int> rozne){
  int x = rozne.back();
  rozne.pop_back();
  vector<int> res;
  if(SZ(rozne)){
    int y = rozne.back();
    rozne.pop_back();
    vector<int> xx = licz(rozne, {y});
    for(int el:xx)res.PB(el);
    res.PB(x);
    xx = licz({y},rozne);
    for(int el:xx)res.PB(el);
  }else{
    res.PB(x);
  }
  
  for(int el:te_same){
    vector<int> res2 = {el};
    for(int el2 : res){
      res2.PB(el2);
      res2.PB(el);
    }
    swap(res,res2);
  }
  return res;
  
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> a >> b;
  vector<int> te_same;
  vector<int> rozne;
  R(i,n){
    if(((a >> i) & 1) == ((b >> i) & 1)){
      te_same.PB(i);
    }else{
      rozne.PB(i);
    }
  }
  if(SZ(rozne) % 2 == 0){
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  vector<int> pom = licz(te_same,rozne);
  debug(pom);
  assert(SZ(pom) + 1 == (1 << n));
  R(i,SZ(pom)){
    cout << a << " ";
    a ^= 1 << pom[i];
  }
  assert(a == b);
  cout << b << "\n";
}


Measured memory_bytes: 2216
#include <stdio.h>
#define rep(i, a) for(int i = 0; i < a; ++i)

typedef long long ll;

int main(void) {
  ll i, j, k, n, m, l;
  scanf("%lld%lld%lld", &n, &m, &l);
  ll a[n][m], b[m][l], c[n][l];
  rep(i, n) rep(j, m) scanf("%lld", &a[i][j]);
  rep(i, m) rep(j, l) scanf("%lld", &b[i][j]);
  rep(i, n) rep(j, l) c[i][j] = 0;
  rep(i, n) rep(j, l) rep(k, m) c[i][j] += a[i][k] * b[k][j];
  rep(i, n) rep(j, l) {
    if(j != l - 1) printf("%lld ", c[i][j]);
    else printf("%lld\n", c[i][j]);
  }
  return 0;
}


Measured memory_bytes: 2912
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;

int gcd(int a, int b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

int lcm(int a, int b) { //最小公倍数
  return a * b / gcd(a, b);
}


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


  cout<<min(b,a*n)<<endl;
  return 0;
}


Measured memory_bytes: 3596
#include  <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1000000007
//P pa(114,514);   ,vector<P>vec(N,0);
//vector<vector<int>> vec(縦, vector<int>(横));
#define REP(i,N) for(int i=0;i<N;i++)
int gcd(int a, int b) {
    if(a>b){
        swap(a,b);
        }
    while(b%a!=0){
        b%=a;
        swap(a,b);
    }
    return a;
}
//cout << setprecision(123);
//a=atoi(S.c_str());
//S=to_string(a);
int main(){
  int N,ans=0,a,b,c;
  cin>>N;
  vector<int>V(N);
  REP(i,N){
    cin>>V[i];
  }
  
  sort(V.begin(),V.end());
  
  for(int i=0;i<N-2;i++){
    for(int j=i+1;j<N-1;j++){
      for(int k=j+1;k<N;k++){
        a=V[i];
        b=V[j];
        c=V[k];
        if(c<a+b){
          ans++;
        }
        else{
          break;
        }
      }
    }
  }
  
  cout<<ans<<endl;
  
}

Measured memory_bytes: 256