akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  double A, B, H, M; cin >> A >> B >> H >> M;
  double ra = H*30 + M*0.5, rb = M*6;
  double result = sqrt(abs(A*A+B*B-2*A*B*cos((ra-rb)/180*M_PI)));
  cout << setprecision(10) << result << endl;
  return 0;
}

Measured memory_bytes: 4224
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<sstream>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

typedef struct _DP{
	string s;
	int i;
}DP;

int main(){
	string inp;
	cin >> inp;
	const int MAX_S = 10;
	
	stack<DP> st;
	DP tmp = {"" , 0 };
	tmp.s += inp[0];
	st.push(tmp);
	long long ans = 0;
	while(!st.empty()){
		DP t = st.top();
		st.pop();

		int i = t.i;
		string s = t.s;
		
		//cout << "i:" << i << " s:" << s << endl;
		if( i == inp.size() - 1){
			vector<long long> v;
			string ts = "";
			rep(i,0,s.size()){
				if(s[i] == '+'){
					stringstream ss;
					ss << ts;
					long long tl;
					ss >> tl;
					v.push_back(tl);
					ts = "";
				}
				else{
					ts += s[i];
				}
			}

			if(ts != "" ){
				stringstream ss;
				ss << ts;
				long long tl;
				ss >> tl;
				v.push_back(tl);
			}

			rep(i,0,v.size())
				ans += v[i];
		
		}
		else{
			DP a = {s+inp[i+1],i+1};
			st.push(a);
			DP b = {s+'+'+inp[i+1],i+1};
			st.push(b);
		}

	}
	P(ans);	
	ret 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let q = read::<usize>();
    let mut lower_pq = BinaryHeap::new();
    let mut higher_pq = BinaryHeap::new();
    let mut b_sum = 0;
    let mut lower_sum = 0;
    let mut higher_sum = 0;

    for i in 0..q {
        let v = read_vec::<i64>();
        if i == 0 {
            let (a, b) = (v[1], v[2]);
            b_sum += b;
            lower_pq.push(a);
            lower_sum += a;
        } else if v[0] == 1 {
            let (a, b) = (v[1], v[2]);
            b_sum += b;
            let current_median = *lower_pq.peek().unwrap();
            if a > current_median || (a == current_median && higher_pq.len() < lower_pq.len()) {
                higher_sum += a;
                higher_pq.push(-a);
                if higher_pq.len() > lower_pq.len() {
                    let higher_bottom = -higher_pq.pop().unwrap();
                    higher_sum -= higher_bottom;
                    lower_pq.push(higher_bottom);
                    lower_sum += higher_bottom;
                }
            } else {
                lower_pq.push(a);
                lower_sum += a;
                if higher_pq.len() < lower_pq.len() - 1 {
                    let lower_top = lower_pq.pop().unwrap();
                    lower_sum -= lower_top;
                    higher_pq.push(-lower_top);
                    higher_sum += lower_top;
                }
            }
        } else {
            let current_median = *lower_pq.peek().unwrap();
            let current_fx = higher_sum
                - current_median * higher_pq.len() as i64
                - (lower_sum - current_median * lower_pq.len() as i64)
                + b_sum;
            // debug!(lower_pq, higher_pq);
            println!("{} {}", current_median, current_fx);
        }
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

int main(){
	int h,w;
	while(1){
		cin>>h>>w;
		if(h==0&&w==0) return 0;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(i==0||j==0||i==h-1||j==w-1) cout<<'#';
				else cout<<'.';
			}
			cout<<endl;
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 3032
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    int N; cin >> N;
    vector<int> D(N);
    rep(i,N) cin >> D[i];
    sort(all(D));

    if(D[0] == 0){
        cout << 0 << endl;
        return 0;
    }

    vi t(25,0);
    t[0] = 1;


    int p = 0;
    for(int i=0;i<N;i++){
        if(p==0){
            t[D[i]]++;
            p=1;
        }else{
            t[24-D[i]]++;
            p=0;
        }
    }

    for(int i=0;i<24;i++) if(t[i] >= 2){
        cout << 0 << endl;
        return 0;
    }

    int ans = INF;
    for(int i=0;i<24;i++){
        for(int j=i+1;j<24;j++){
            if(t[i] and t[j]){
                int d = min(j-i,24-(j-i));
                chmin(ans,d);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
ll f[200010], invf[200010];

ll pow_mod(ll a, ll b, ll m){
    ll ret = 1;
    while (b > 0) {
        if (b & 1) {
            ret = ret * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ret;
}

ll inv_mod(ll a, ll m){
    return pow_mod(a, m - 2, m);
}

void fact(){
    f[0] = 1;
    invf[0] = 1;
    repd(i, 1, 200010){
        f[i] = (f[i - 1] * i) % mod;
        invf[i] = inv_mod(f[i], mod);
    }
}


ll comb(ll n, ll k){
    ll ret = f[n] * invf[k] % mod;
    ret = ret * invf[n - k] % mod;
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    fact();
    // source code
    ll H, W, A, B;
    cin >> H >> W >> A >> B;
    ll ret = 0;
    ll h = H - A - 1, w = B;
    while(h >= 0 && w >= 0 && H - h - 1 >= 0 && W - w - 1 >= 0){
//        cout << h << ", " << w << ": " << H - h - 1 << ", " << W - w - 1 << endl;
        ll tmp = comb(h + w, w);
        tmp = tmp * comb(H - h - 1 + W - w - 1, H - h - 1) % mod;
        ret = (ret + tmp) % mod;
        h--, w++;
    }
    
    output(ret, 0);
    
    return 0;
}

Measured memory_bytes: 3328
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();
    let k: usize = itr.next().unwrap().parse().unwrap();
    let a: Vec<usize> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();
    let b: Vec<usize> = (0..m)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut s = a.iter().sum::<usize>();

    let mut j = n;
    let mut ans = 0;
    for i in 0..m + 1 {
        while j > 0 && s > k {
            s = s.saturating_sub(a[j - 1]);
            j -= 1;
        }
        if s > k {
            break;
        }
        ans = max(ans, i + j);
        if i == m {
            break;
        }
        s += b[i];
    }
    println!("{}", ans);
}


Measured memory_bytes: 9200
N=int(input())
H=list(map(int,input().split()))

now=H[0]
count=0
max_count=0
for i in range(1,len(H)):
    if now>=H[i]:
        count+=1
    else:
        if max_count<count:
            max_count=count
        count=0
    now=H[i]
if max_count<count:
    max_count=count
print(max_count)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
 
#define eb emplace_back
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int) b; i--)
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;

int main () {
  int n;
  cin >> n;
  cout << n * n << '\n';
  return 0;
}


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

int main()
{
 int a,b,c,d;
  cin>>a>>b>>c>>d;
  int cnt = 0;
  while(1)
  {
    if(cnt%2==0)
		c -= b;
    else
      a -= d;
    if(a<=0)
    {
      cout<<"No"<<endl;
      break;
    }
     if(c<=0)
     {
		cout<<"Yes"<<endl;
       break;
     }
    cnt++;
       
  }
  return 0;
}

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

int main()
{
  	string X,Y;
  	string s[6] = {"A","B","C","D","E","F"};
  	int x,y;
  	cin >> X;
  	cin >> Y;
  
  	if(X == Y)
      cout << "=";
  
  	for(int i = 0;i <6;i++){
      if(s[i] == X)
        x = i + 10;}
  
  	for(int i = 0;i <6;i++){
      if(s[i] == Y)
        y = i + 10;}
  
  	if(x<y)
      cout << "<";
  	else if(x>y)
      cout << ">";
}

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

#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

#define debug(x) cout << "> " << #x << " = " << x << endl;
#define debug_at(arr, at) cout << "> " << #arr << "[" << at << "] = " << arr[at] << endl;
#define debug_pair(p) cout << "> " << #p << " = (" << p.first << ", " << p.second << ")" << endl;

using namespace std;

int n, m;
vector<string> grid;
vector<string> M;

inline bool inside(int x, int y) {
    return (x >= 0 and x < n) and (y >= 0 and y < m);
}

inline int many(int x, int y) {
    int cont = 0;
    fori(i, -1, 2) {
        fori(j, -1, 2) {
            int a = x + i;
            int b = y + j;
            if(!inside(a, b)) continue;
            if(a == x and b == y) continue;
            if(grid[a][b] == '#') ++cont;
        }
    }
    return cont;
}

inline void solve() {
    M = grid;
    fori(i, 0, n) {
        fori(j, 0, m) {
            if(grid[i][j] == '.') {
                char c = '0' + many(i, j);
                M[i][j] = c;
            }
        }
    }
    fori(i, 0, n) {
        cout << M[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    fori(i, 0, n) {
        string s;
        cin >> s;
        grid.push_back(s);
    }
    solve();

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef double ld;
#define X first
#define Y second
#define mk make_pair
#define pb push_back
#define Rep(i, n) for(int i = 0; i < int(n); i ++)
#define Rep1(i, n) for(int i = 1; i <= int(n); i ++)
#define all(x) (x).begin(), (x).end()
const int MOD = (int) 1e9 + 7;
const ll base =  31;
void MAIN();
int main(){
    //freopen("input.txt", "r", stdin);
    ios:: sync_with_stdio(false); cin.tie(0);
    MAIN();
    return 0;
}
////////////////////////////////////////////////////////////////////////

const int N = 100032;

int n, m, k, p, ans[N];
vector <ii> G[N], Q[N];
int d[N];
ii x[N];
vector <int> in[N];
int par[N], sz[N], cur;

int Find(int u){
    if(u == par[u]) return u;
    return par[u] = Find(par[u]);
}

void Union(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return;
    if(sz[u] >= sz[v]) swap(u, v);
    Rep(i, in[u].size()){
        int a = in[u][i];
        in[v].pb(a);
        Rep(j, Q[a].size()){
            int b = Q[a][j].X;
            if(Find(b) == v){
                ans[Q[a][j].Y] = cur;
            }
        }
    }
    in[u].clear();
    sz[v] += sz[u];
    par[u] = v;
}

void MAIN(){
    cin >> n >> m >> k >> p;
    while(m --){
        int u, v, c;
        cin >> u >> v >> c;
        G[u].pb(ii(v, c));
        G[v].pb(ii(u, c));
    }
    queue <ii> q;
    memset(d, 0x3f, sizeof d);
    while(k --){
        int u;
        cin >> u;
        d[u] = 0;
        q.push(ii(d[u], u));
    }
    bitset <N> inq;
    while(!q.empty()){
        int u = q.front().Y; inq[u] = false;
        q.pop();
        Rep(i, G[u].size()){
            int v = G[u][i].X, c = G[u][i].Y;
            if(d[v] > d[u] + c){
                d[v] = d[u] + c;
                if(!inq[v]) q.push(ii(-d[v], v));
                inq[v] = true;
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        x[i] = ii(-d[i], i);
        par[i] = i;
        sz[i] = 1;
        in[i].pb(i);
    }
    Rep(i, p){
        int s, t;
        cin >> s >> t;
        if(s == t) ans[i] = d[s];
        else {
            Q[s].pb(ii(t, i));
            Q[t].pb(ii(s, i));
        }
    }
    sort(x + 1, x + n + 1);
    memset(ans, 0xff, sizeof ans);
    for(int i = 1; i <= n; i ++){
        cur = -x[i].X;
        int u = x[i].Y;
        Rep(i, G[u].size()){
            int v = G[u][i].X;
            if(d[v] < d[u]) continue;
            Union(u, v);
        }
    }
    Rep(i, p) cout << ans[i] << "\n";
}

Measured memory_bytes: 23916
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int b[100010];
int f[100010];
vector<int> G[100010];
int n, k;
set<int> st;

int dfs(int now){
    if(G[now].size() == 0){
        st.insert(now);
        return 1;
    }
    int res = INF;
    rep(i, 0, G[now].size()){
        chmin(res, dfs(G[now][i]) + 1);
    }
    if(res <= k) st.insert(now);
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    vector<int> a(n);
    rep(i, 0, n){
        cin >> a[i]; a[i]--;
        if(a[i] != -1){
            b[a[i]]++;
            G[a[i]].push_back(i);
        }
    }
    // set<int> st;
    rep(i, 0, n){
        if(a[i] == -1){
            st.insert(i);
            dfs(i);
        }
    }
    // cout << ans << endl;
    cout << st.size() << endl;
}

Measured memory_bytes: 19140
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int result010 = 0;
        int result101 = 0;
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(i%2==0) {
                if(c=='0') {
                    result101++;
                }
                else {
                    result010++;
                }
            }
            else {
                if(c=='0') {
                    result010++;
                }
                else {
                    result101++;
                }
            }
        }
        System.out.println(Math.min(result010, result101));
    }
}


Measured memory_bytes: 25044
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int[] P = new int[N];
		for(int i = 0; i < N; i++) {
			P[i] = Integer.parseInt(sc.next());
		}
		sc.close();
		
		int count = 0;
		for(int i = 0; i < N; i++) {
			if(P[i] != i + 1) {
				count++;
			}
		}
		if(count <= 2) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}

	}

}

Measured memory_bytes: 21844
#include <stdio.h>

int main(void)
{
	int W, H, x, y, r;

	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

	if ((x >= r) && (x + r <= W)) {
		if ((y >= r) && (y + r <= H)) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}
	else {
		printf("No\n");
	}

	return 0;
}


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

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

    int D = max(A, max(B, C));
    int d = min(A, min(B, C));
    
    if(A == D){
        int E = max(B, C);
        cout << A * 10 + B + C;
    }else if(B == D){
        int F = max(A, C);
        cout << B * 10 + A + C;
    }else{
        int G = max(A, B);
        cout << C * 10 + A + B;
    }
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if(N == 1) {
			System.out.println("Hello World");
		}
		else {
			int A = sc.nextInt(), B = sc.nextInt();
			System.out.println(A + B);
		}
	}
}

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

int main()
{
	int H, W;
	scanf("%d%d", &H, &W);
	using vi = std::vector<int>;
	using vvi = std::vector<vi>;
	using vvvi = std::vector<vvi>;
	vvi number(H + 1, vi(W + 1));
	for (int i{1}; i <= H; i++)
		for (int j{1}; j <= W; j++)
		{
			int A;
			scanf("%d", &A);
			number[i][j] = A;
		}
	for (int i{1}; i <= H; i++)
		for (int j{1}; j <= W; j++)
		{
			int A;
			scanf("%d", &A);
			number[i][j] -= A;
			number[i][j] = std::abs(number[i][j]);
		}
	constexpr int center{80 * 80};
	using vbs = std::vector<std::bitset<center * 2 + 1>>;
	using vvbs = std::vector<vbs>;
	vvbs dp(2, vbs(W + 1));
	dp[0][1][center] = true;
	for (int i{1}; i <= H; i++)
	{
		for (int j{1}; j <= W; j++)
		{
			dp[1][j] |= dp[0][j] << number[i][j];
			dp[1][j] |= dp[0][j] >> number[i][j];
			dp[1][j] |= dp[1][j - 1] << number[i][j];
			dp[1][j] |= dp[1][j - 1] >> number[i][j];
			dp[0][j].reset();
			// for (int k{}; k < 2 * center + 1; k++)
			// 	if (dp[1][j][k])
			// 		printf("%d ", k - center);
			// putchar(':');
		}
		// putchar('\n');
		std::swap(dp[0], dp[1]);
	}
	int ans{1 << 30};
	for (int i{}; i < 2 * center + 1; i++)
		if (dp[0][W][i])
			ans = std::min(ans, std::abs(i - center));
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 640
s = input()
t = input()
t_long = len(t)
position = [0] * t_long
rep = 0

if set(t) <= set(s):
    position[0] = s.find(t[0])
    for i in range(1, t_long):
        if s.find(t[i], position[i - 1] + 1) > -1:
            position[i] = s.find(t[i], position[i - 1] + 1)
        else:
            position[i] = s.find(t[i])
    for k in range(t_long - 1):
        if position[k + 1] <= position[k]:
            rep += 1
    print(rep * len(s) + position[t_long - 1] + 1)
else:
    print(-1)

Measured memory_bytes: 9332
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "0" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
string S;
ll nexti[202020][26];
void nextinit(){
    ll N=S.size();
    rep(j,26) nexti[N][j]=N;
    repr(i,N-1,0){
        rep(j,26){
            nexti[i][j]=nexti[i+1][j];
            nexti[i][S[i]-'a']=i;
        }
    }
}
ll dp[202020]; //ない文字列の長さ
char reco[202020]; //ない文字列へ行く時の次の文字
//--MAIN-----------------------------------
void Main() {
    cin>>S;
    ll N=S.size();
    nextinit();
    rep(i,N+1) dp[i]=INF2;
    dp[N]=1;
    reco[N]='a';
    repr(i,N-1,0){
        rep(j,26){
            if(nexti[i][j]==N){
                if(dp[i]>1){
                    dp[i]=1;
                    reco[i]='a'+j;
                }
            }
            else{
                if(mini(dp[i],dp[nexti[i][j]+1]+1)){
                    reco[i]='a'+j;
                }
            }
        }
    }
    string ans;
    ll index=0;
    while(index<=N){
        ans+=reco[index];
        index=nexti[index][reco[index]-'a']+1;
    }
    cout<< ans <<"\n";
}
//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 43028
n, m = gets.chomp.split.map(&:to_i)

h = []
m.times do |i|
  h[i] = gets.chomp.split.map {|a| a.to_i - 1 }
end

reached = Array.new(n)
reached[0] = true

def search(from, n, m, h, reached)
  ans = 0
  queue = []
  h.each do |a|
    if a[0] == from
      queue.push([from, a[1], reached.dup])
    elsif a[1] == from
      queue.push([from, a[0], reached.dup])
    end
  end
  while !queue.empty?
    from, to, reached = queue.shift
    reached[to] = true
    if reached.all?
      ans += 1
    else
      h.each do |a|
        if a[0] == to && !reached[a[1]]
          queue.push([to, a[1], reached.dup])
        elsif a[1] == to && !reached[a[0]]
          queue.push([to, a[0], reached.dup])
        end
      end
    end
  end
  p ans
end

search(0, n, m, h, reached)


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


int main() {
ll N;
  cin>>N;
  vector<ll> A(N);
  for(ll i=0;i<N;i++) {
cin>>A[i];
  }

 ll mod=1000000007;
  
  vector<vector<bool>> vec(61,vector<bool> (N,false));
  
  for(ll i=0;i<N;i++) {
bitset<61> S(A[i]);
   for(ll j=0;j<61;j++) {
if(S.test(j)) {
vec[j][i]=true;
}
   }
  }
  
  ll ans=0;
  ll k=1;
  
  for(ll i=0;i<61;i++) {
    ll count=0;
for(ll j=0;j<N;j++) {
  if(vec[i][j]) {
count++;
  }
}
    ll X=(N-count)*count;
    X%=mod;
    ans+=k*X;
    k*=2;
    k%=mod;
    ans%=mod;
    
  }
  cout<<ans<<endl;
}
    

  
  
  
  
  

  


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    int N;
    cin >> N;

    int ans=0;
    rep(i,1,N+1){
        if(i%2==0) continue;
        int cnt=0;
        rep(j,1,i+1) if(i%j==0) ++cnt;
        if(cnt==8) ++ans;
    }

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;

    vector<long long> h(n);
    for (long long i = 0; i < n; i++) {
        cin >> h[i];
    }

    vector<long long> a(m), b(m);
    for (long long i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    vector<bool> light_house(n, true);
    for (int i = 0; i < m; i++) {
        long long idx_a = a[i];
        long long idx_b = b[i];
        if (h[idx_a] > h[idx_b]) {
            light_house[idx_b] = false;
        }
        else if (h[idx_a] < h[idx_b]) {
            light_house[idx_a] = false;
        }
        else {
            light_house[idx_a] = false;
            light_house[idx_b] = false;
        }
    }

    long long ans = 0;
    for (long long i = 0; i < n; i++) {
        if (light_house[i]) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5584
#include<bits/stdc++.h>
#define ll long long int 
#define w(x) int x; cin>>x; while(x--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
using namespace std;
int main(){
#ifndef ONLINE_JUDGE 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll a,b,z=0;
	cin>>a>>b;
	ll c[a];
	for(ll i=0; i<a; i++)
		cin>>c[i];
	sort(c,c+a);
	for(ll i=a-1-b; i>=0; i--){
		z+=c[i];
	}
	cout<<z;
	

}

Measured memory_bytes: 5168
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, D;
    cin >> N >> D;
    cout << (N + D * 2) / (D * 2 + 1) << endl;

    return 0;
}


Measured memory_bytes: 256
// Problem : I - Coins
// Contest : Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_i
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize "trapv"//  WA to RE int!!
#include <bits/stdc++.h>
#define FOR(i,n) for(long long int i=0;i<n;i++)
#define FORR(i,n) for(long long int i=n;i>=0;i--)
#define pb push_back
#define vlli vector<long long int>
#define slli set<long long int>
#define mlli map<long long int,long long int>
#define lli long long int 
#define test lli tt1234; cin>>tt1234;while(tt1234--)
#define endl "\n"
#define all(zz) zz.begin(),zz.end()
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define error(x) cerr << #x <<" is " << x << endl;
// #define error(x,y) cerr << #x <<" is " << x <<",  "<<y<< endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fint fast;test
#define set(a,x) memset(a,x,sizeof(a))
#define L(x)	((x)<<1)
#define R(x)	(((x)<<1)+1)
#define MOD 1000000007
using namespace std;
lli n;
long double arr[3000],dp[3001][3001];
long double go(lli h,lli t){
	if((h+t)==n && h>t) {return 1;}
	if(h+t>=n) return 0;
	if(dp[h][t]!=(-1.0))return dp[h][t]; 
	dp[h][t]=(arr[h+t]*go(h+1,t))+((1.0-arr[h+t])*go(h,t+1));
	return dp[h][t];
}
void solve(){
	// set(dp,-1.0);
	// scanf("%lld",&n);
	FOR(i,3001)FOR(j,3001) dp[i][j]=-1.0;
	cin>>n;
	FOR(i,n) {cin>>arr[i];}
	// cout<<go(0,0);
	// long double ans=;
	cout<<setprecision(10)<<go(0,0);
	// error(ans);
	
}


int32_t main() {
    	solve();
    return 0;
}


Measured memory_bytes: 141184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, l, r) for (int i = l; i <= (int)(r); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while(true){
        c -= b;
        if(c<=0){
            cout << "Yes" << endl;
            return 0;
        }
        a-=d;
        if(a<=0){
            cout << "No" << endl;
            return 0;
        }
    }
    // printf("%d\n", N);
    return 0;
}

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

typedef long long int LL;
#define REP(n) for(LL i = 0; i < (n); i++)
#define COUT(val) cout << (val) << endl
#define CIN(val) cin >> (val)
#define SORT(vec) sort(vec.begin(), vec.end())
#define SORT_GRE(vec) sort(vec.begin(), vec.end(), greater<LL>())

int main(){
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans += i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
NMAX = 55
T = 2500
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))

dp = [[0]*5001 for i in range(NMAX)]  # i時点で総和がSになるものの個数

dp[0][T] = 1

for i in range(N):
    for s in range(5001):
        if s+X[i] > 5001 or dp[i][s] == 0:
            continue
        dp[i+1][s] += dp[i][s]
        dp[i+1][s+X[i]] += dp[i][s]

print(dp[N][T]-1)



Measured memory_bytes: 11600
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
using namespace std;
int n,a[4000040],tot,vis[4000040],k1,k2,j;
int power(int x,int y){
	int base=x;
	int sum=1;
	while(y!=0){
		if(y%2==1){
			sum*=base;
		}
		base*=base;
		y/=2;
	}
	return sum;
}
bool cmp(int x,int y){
	return x>y;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	n=power(2,n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	/*
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
	*/
	vis[1]=1;
	for(int k=1;k*2<=n;k*=2){
		k1=0;
		j=1;
		for(int i=1;i<=n;i++){
			if(vis[i]==1){
				k1++;
				while(vis[j]==1||a[j]>=a[i]){
					j++;
					/*
					if(k==16){
						printf("%d ",j);
					}
					*/
					if(j>n){
						printf("No\n");
						return 0;
					}
				}
				vis[j]=2;
				j++;
				if(j>n&&k1<k){
					printf("No\n");
					return 0;
				}
			}
			if(k1==k){
				break;
			}
		}
		/*
		printf("\nk : %d\n",k);
		for(int i=1;i<=n;i++){
			printf("%d ",vis[i]);
		}
		printf("\n");
		*/
		for(int i=1;i<=n;i++)
			if(vis[i]==2) vis[i]=1;
	}
	printf("Yes\n");
	return 0;
}

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

template<typename T>
struct BIT {
    int n;
    vector<T> dat;

    BIT(int n=0){
        initialize(n);
    }

    void initialize(int nin){
        n = nin;
        dat.assign(n, 0);
    }

    T sum(int i){
        T s = 0;
        while(i >= 0){
            s += dat[i];
            i = (i & (i+1)) - 1;
        }
        return s;
    }

    T sum_between(int i, int j){
        return sum(j) - sum(i-1);
    }

    void plus(int i, T x){
        while(i < n){
            dat[i] += x;
            i |= i+1;
        }
    }

    // a[0]+...+a[ret] >= x
    int lower_bound(T x){
        if(x < 0) return -1;
        int ret = -1;
        int k = 1;
        while(2*k <= n) k <<= 1;
        for( ;k>0; k>>=1){
            if(ret+k < n && dat[ret+k] < x){
                x -= dat[ret+k];
                ret += k;
            }
        }
        return ret + 1;
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> C(N);
    for(int i=0; i<N; i++) scanf("%d", &C[i]), C[i]--;
    vector<vector<pair<int, int>>> R2LQ(N);
    for(int i=0; i<Q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        R2LQ[r-1].emplace_back(l-1, i);
    }

    vector<int> last(N, -1);
    vector<int> ans(Q);

    BIT<int> bit(N);
    for(int r=0; r<N; r++){
        if(last[C[r]] >= 0) bit.plus(last[C[r]], -1);
        last[C[r]] = r;
        bit.plus(last[C[r]], 1);
        for(auto& [l, q] : R2LQ[r]) ans[q] = bit.sum_between(l, r);
    }
    for(int a : ans) printf("%d\n", a);
    return 0;
}


Measured memory_bytes: 33144
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long[] name = new long[5];
		long N = sc.nextInt();
		for(int i = 0; i < N; i++) {
			switch(sc.next().charAt(0)) {
			case 'M':
				name[0] += 1;
				break;
			case 'A':
				name[1] += 1;
				break;
			case 'R':
				name[2] += 1;
				break;
			case 'C':
				name[3] += 1;
				break;
			case 'H':
				name[4] += 1;
				break;
			}
		}

		long result = 0;
		for(int i = 0; i < 3; i++) {
			for(int j = i + 1; j < 4; j++) {
				for(int k = j + 1; k < 5; k++) {
					result += name[i] * name[j] * name[k];
				}
			}
		}
		System.out.println(result);
		sc.close();
	}
}


Measured memory_bytes: 45224
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL calc(LL n,LL s){
    if(!n)
        return 0;
    return calc(n/s,s)+n%s;
}
int main(){
    LL n,s;
    cin>>n>>s;
    if(n<=s){
		cout<<((n<s)?-1:n+1)<<endl;
		return 0;
	}
	int lim1=1;
    for(LL i=2;i*i<=n;++i){
        if(calc(n,i)==s)
            {cout<<i<<endl;return 0;}
        lim1=i;
    }
    for(LL i=lim1;i>0;--i){
		if((n-s)%i==0){
			LL b=(n-s)/i+1;
			if(calc(n,b)==s){cout<<b<<endl;return 0;}
		}
	}
	puts("-1");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std ;
#define ll long long int
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>


int main()
{


ll   h ,  w , k ;
cin>>h>> w>> k ;

vector<string>  arr( h) ;
ll count = 0 ;

for(ll i =0;i< h ;i++)
cin>>arr[i] ; 
for(ll i =0;i< pow( 2 , h  ) ;i++)
{

    for(ll j =0; j < pow ( 2 , w ) ; j++ )
    {
// cout<< i << " "<< j<<endl ; 
        vector<string> brr = arr ;
        ll x = i , y = j ;

        ll itr =  0 ;
        while(x!= 0 )
        {
            if(x%2==1)
            {

                for(ll n = 0 ; n <  w ;n++ )
                {

                    brr[itr][n] = '.' ;
                }


            }
                itr++ ;
                x/=2 ;

        }
        x = y ;
        itr = 0 ;

        while(x!= 0 )
        {
            if(x%2==1)
            {

                for(ll n = 0 ; n <  h ;n++ )
                {

                    brr[n][itr] = '.' ;
                }


            }
                itr++ ;
                x/=2 ;

        }
        ll  js = 0 ;
        for(auto is :brr  )
        {

            for(auto g : is )
            {
                if(g=='#')
                    js++ ;
            }
        }

        if(js==k)
            count++ ;
    }
}

cout<<count<<endl ;

}


Measured memory_bytes: 4092
#!/usr/bin/env python3
# a1を適当に決めると、他の値は任意に決まり
# 条件はfor i in range(3): c[2][i] -c[1][i] = const であること
c = []
for i in range(3):
    c.append(list(map(int,input().split())))
#print(c)
if c[2][0]-c[0][0] == c[2][1]-c[0][1]:
    #print(1)
    if c[2][0]-c[0][0] == c[2][2]-c[0][2]:
        #print(2)
        if c[1][0]-c[0][0] == c[1][1]-c[0][1]:
           # print(3)
            if c[1][0]-c[0][0] == c[1][2]-c[0][2]:
                print("Yes")
                exit()
print("No") 


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define ll long long
#define MOD 1000000007
#define pi pair<ll,ll>
#define mp make_pair
inline ll read()
{
	ll x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
ll f[110];
vector<pi> a[110];
int main()
{
	int T=read();
	f[0]=f[1]=1;
	for(int i=2;i<=100;++i)f[i]=f[i-1]+f[i-2];
	a[1].push_back(mp(1,2));a[1].push_back(mp(1,3));a[1].push_back(mp(1,4));
	for(int i=1;i<=100;++i)
		for(int j=0,l=a[i].size();j<l;++j)
		{
			ll x=a[i][j].second,y=a[i][j].first+x;
			while(y<=f[i+3]+f[i])a[i+1].push_back(mp(x,y)),y+=x;
		}
	while(T--)
	{
		ll n=read(),m=read();if(n>m)swap(n,m);
		if(n==1&&m==1){puts("1 1");continue;}
		int p,ans=0;for(int i=1;;++i)if(!(n>=f[i]&&m>=f[i+1])){p=i-1;break;}
		printf("%d ",p);if(p==1){printf("%lld\n",(n%MOD)*(m%MOD)%MOD);continue;}
		for(int j=0,l=a[p-1].size();j<l;++j)
		{
			ll x=a[p-1][j].first,y=a[p-1][j].second;
			if(y<=n)ans=(ans+(m-x)/y)%MOD;
			if(y<=m)ans=(ans+(n-x)/y)%MOD;
		}
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010]={0};

void chmin (int &a, int b){
  if(a>b){swap(a,b);} return;}

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

for(int i =0; i < 1010; i++){ dp[i][0]=i; dp[0][i]=i;}
int m = s.size();  int n = t.size();
for(int i = 1; i <= m; i++){
  for(int j = 1; j <= n; j++){
    int  res = 1e9;
   chmin(res , dp[i-1][j]+1);
   chmin(res , dp[i][j-1]+1);

int c=1; 
if( s[i-1]==t[j-1]){c=0;}
   chmin(res ,dp[i-1][j-1]+c);

   dp[i][j]=res;

   }
}

cout << dp[m][n] << endl; return 0;}


Measured memory_bytes: 7172
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector<double> vd;
typedef std::vector<std::string> vs;
typedef std::vector<pii> vpii;
typedef std::vector<vi> vvi;
typedef std::vector<vpii> vvpii;
const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { rep(i,v.size()) is >> v[i]; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(const int &s = 0, const int &d = 0, const Weight &w = 0) : src(s), dst(d), weight(w) {}
};

typedef std::vector<Edge> Edges;
typedef std::vector<Weight> Array;
typedef std::vector<Array> Matrix;

class Graph {
  std::vector<Edges> g;

public:
  Graph(const int &size = 0) : g(size) {}
  int size() const { return g.size(); }
  const Edges &operator[](const int &i) const { return g[i]; }
  void addArc(const int &src, const int &dst, const Weight &w = 1) { g[src].emplace_back(src, dst, w); }
  void addEdge(const int &node1, const int &node2, const Weight &w = 1) {
    addArc(node1, node2, w);
    addArc(node2, node1, w);
  }
};

template<int inf = std::numeric_limits<Weight>::max() / 8> std::pair<std::vector<Weight>, std::vector<int>> dijkstra(const Graph &g, const int &src) {
  using state = std::pair<Weight, int>;
  std::priority_queue<state, std::vector<state>, std::greater<state>> q;
  std::vector<Weight> dist(g.size(), inf);
  std::vector<int> via(g.size());
  dist[src] = 0;
  q.emplace(0, src);
  while (q.size()) {
    Weight d;
    int v;
    std::tie(d, v) = q.top();
    q.pop();
    if (dist[v] < d) continue;
    for (auto &e : g[v]) {
      if (cmin(dist[e.dst], dist[v] + e.weight)) {
        via[e.dst] = v;
        q.emplace(dist[e.dst], e.dst);
      }
    }
  }
  return {dist, via};
}
main {
  int c, n, m, s, d;
  while (cin >> c >> n >> m >> s >> d, c) {
    --s, --d;
    Graph g(n * (c + 1));
    while (m--) {
      int a, b, f;
      cin >> a >> b >> f;
      --a, --b;
      rep(i, c + 1) g.addEdge(a + n * i, b + n * i, f);
      rep(i, c) {
        g.addArc(n * i + a, n * (i + 1) + b, f / 2);
        g.addArc(n * i + b, n * (i + 1) + a, f / 2);
      }
    }
    vector<Weight> dist = dijkstra(g, s).first;
    int mini = INF;
    rep(i, c + 1) cmin(mini, dist[n * i + d]);
    cout << mini << endl;
  }
}

Measured memory_bytes: 3512
class Wood:
  def __init__(self,num,noods,edges):
    self.num = num
    self.noods = noods
    self.edges = edges
  def cons(self,other):
    self.noods.extend(other.noods)
    self.edges.extend(other.edges)

class Edge:
  def __init__(self,n1,n2,length):
    self.n1 = n1
    self.n2 = n2
    self.length = length

def check(woods,edge):
  if woods[edge.n1].num != woods[edge.n2].num:
    woods[edge.n1].cons(woods[edge.n2])
    woods[edge.n1].edges.append(edge)
    for i in woods[edge.n1].noods:
      woods[i] = woods[edge.n1]
while True:
  n = int(input())
  if n == 0:
    break
  m = int(input())
  e = []
  woods = []
  for i in range(m):
    n1,n2,length = map(int,input().split(","))
    edge = Edge(n1,n2,length)
    e.append(edge)
  e = sorted(e,key=lambda x:x.length)
  for i in range(n):
    wood = Wood(i,[i],[])
    woods.append(wood)
  for edge in e:
    check(woods,edge)
  s = 0
  for edge in woods[0].edges:
    s += edge.length//100-1
  print(s)

Measured memory_bytes: 8720
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

ll N, H;
vector<ll> a, b;

void init()
{
}

void solve()
{
    ll ans = 0;
    sort(ALL(a));
    sort(ALL(b));
    auto it = upper_bound(ALL(b), a[N-1]);
    if(it != b.end()){
        ll s = 0;
        for(auto i = b.end()-1; i != it-1; i--){
            s += *i;
            ans++;
            if(s >= H) break;
        }
        H -= s;
    }
    if(H > 0){
        ans += H / a[N-1] + (H % a[N-1] == 0 ? 0 : 1);
    }
    cout << ans << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> H;
    a.resize(N);
    b.resize(N);
    REP(i, N){
        cin >> a[i] >> b[i];
    }
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 1792
/* ABC144_B
    Stuartyg */

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>


int main(void){
    int n;
    int i,j; 
    scanf("%d",&n); /*入力を受け取る*/
    for (i=1;i<=9;i++){ /* for文二個で1*1～9*9まで調べる*/
        for (j=1;j<=9;j++){
            if (n==i*j){
                printf("Yes\n");
                return 0;
            }
        }
    }

    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	string ss;
	cin >> ss;
	int64 nn = ss.length();
	for(int64 ii = 0;ii < nn;ii++)
	{
		cout << "x";
	}
	cout << endl;
	return 0;
}


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


pair = [[0] * 10 for i in range(10)]


for num in range(1,N + 1):
    temp = str(num)
    temp1 = int(temp[0])
    temp2 = int(temp[-1])
    pair[temp1][temp2] += 1
    
total = 0
for i in range(1,10):
    for j in range(1,10):
        total += pair[i][j] * pair[j][i]
        
print(total)

Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>


using namespace std;

vector<long int> min_mat(10001, -1);

vector<long int> a(1001);
vector<long int> b(1001);

long int h, n;


long int min_att(long int cur_h) {
    if (cur_h <= 0) {
        return 0;
    }
    if (min_mat[cur_h] >= 0) {
        return min_mat[cur_h];
    }
    long int min_cand = -1;

    for (int i=0; i<n; i++) {
        long int tmp = min_att(cur_h - a[i]) + b[i];
        if (i == 0) {
            min_cand = tmp;
        }
        else if (tmp < min_cand) {
            min_cand = tmp;
        }
    }
    min_mat[cur_h] = min_cand;
    return min_cand;
}



int main() {


    scanf("%ld", &h);
    scanf("%ld", &n);

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

    printf("%ld", min_att(h));

    return 0;



}


Measured memory_bytes: 768
// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

typedef long long int ll;
#define endl '\n'
#define ld long double
#define all(a) a.begin(),a.end()
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define sz(v) (int)v.size() 
#define UB upper_bound
#define LB lower_bound
#define OST tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>

const int INF = 2e9 + 0;
const int mod = 1e9 + 7;
//const int mod = 998244353;

void solve() {
   int a, b; cin >> a >> b;
   if(a > b) cout << "safe\n";
   else cout << "unsafe\n";
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    #ifndef ONLINE_JUDGE
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif
    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
}    


Measured memory_bytes: 3608