akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
n, x, y = map(int, input().split())

x -= 1
y -= 1

d = y - x - 1
g = [i for i in range(n)]
for i in range(y, n):
    g[i] -= d

l = [0 for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if j <= x or y <= i:
            k = j - i
        elif i <= x and y <= j:
            k = g[j] - g[i]
        else:
            # 通常
            k = j - i
            # i -> x, j -> y経由
            _k = abs(x - i) + abs(y - j) + 1
            k = min(k, _k)
        l[k] += 1

for k in l[1:]:
    print(k)


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

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;

typedef pair<ll, ll> P;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main()
{
    int n;
    cin >> n;

    ll f[n][10], p[n][11];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> f[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 11; j++) {
            cin >> p[i][j];
        }
    }
    
    ll ans = -1*inf;

    for (int mask = 1; mask < (1<<10); mask++) {
        ll cnt, tmp = 0;
        for (int i = 0; i < n; i++) {
            cnt = 0; 
            for (int j = 0; j < 10; j++) {
                if (((mask>>j) & 1) && f[i][j]) cnt++;
            }
            tmp += p[i][cnt];
        }
        chmax(ans, tmp);
    }

    cout << ans << endl;

    return 0;
}



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

using namespace std;

int main()
{
    char str[64];
    char lf[] = "qwertasdfgzxcvb";
    
    while (scanf("%s", str) && str[0] != '#'){
        int ct = 0;
        
        for (int i = 1; str[i]; i++){
            bool j1 = false, j2 = false;
            for (int j = 0; lf[j]; j++){
                if (str[i] == lf[j]) j1 = true;
                if (str[i - 1] == lf[j]) j2 = true;
            }
            
            ct += (j1 ^ j2);
        }
        
        printf("%d\n", ct);
    }
    
    return (0);
}

Measured memory_bytes: 1136
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:256000000")
#include<utility>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

//4Head
#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(NULL));

// belik's shit
ll const mod = 1e9 + 7;
namespace {
	ll mult(ll a, ll b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) {
			val += mod;
		}
		if (val >= mod) {
			val -= mod;
		}
		return val;
	}
	ll poww(ll a, ll b)
	{
		ll val = 1;
		a %= mod;
		while (b > 0){
			if (b % 2) val = mult(a, val);
			a = mult(a, a);
			b >>= 1;
		}
		return val % mod;
	}
	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

ll const maxn = 5e5 + 5;
vector<ll>g[maxn];
bool used[maxn]; 
ll fact[maxn];
ll k;

ll f(ll n, ll k) {
	if (n < k) return 0LL;
	return mult(fact[n], inv(fact[n - k]));
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n; cin >> n; cin >> k;
	fact[0] = 1;
	for (ll i = 1; i < maxn; i++) {
		fact[i] = mult(fact[i - 1], i);
	}
	for (ll i = 0; i < n - 1; i++) {
		ll a, b; cin >> a >> b;
		a--; b--;
		g[a].push_back(b); g[b].push_back(a);
	}
	ll ans = 1;
	ll root = 0;
	queue<ll>q;
	ll cnt = 1;
	q.push(root); used[root] = 1; q.pop();
	for (ll v : g[root]) {
		q.push(v);
		used[v] = 1;
		cnt++;
	}
	ans = mult(ans, f(k, cnt));
	while (!q.empty()) {
		ll u = q.front();
		used[u] = true;
		q.pop();
		cnt = 0;
		for (ll v : g[u]) {
			if (used[v]) continue;
			q.push(v);
			cnt++;
		}
		ans = mult(ans, f(k - 2, cnt));
	}
	cout << ans << endl;
	return 0;
}
/*

*/

Measured memory_bytes: 21108
import sys
readline = sys.stdin.buffer.readline

import math


a, b, h, m = map(int, readline().split())

theta_a = 360 * h / 12 + m / 2
theta_b = 360 * m / 60

if ((theta_a <= 180) & (theta_b <= 180)) or \
    ((theta_a >= 180) & (theta_b >= 180)):
    theta_a = min(theta_a, 360 - theta_a)
    theta_b = min(theta_b, 360 - theta_b)
    theta = abs(theta_b - theta_a) * math.pi / 180
else:
    theta_a = min(theta_a, 360 - theta_a)
    theta_b = min(theta_b, 360 - theta_b)
    theta = abs(theta_b + theta_a) * math.pi / 180

c = a ** 2 + b ** 2 - 2 * a * b * math.cos(theta)

print(c ** 0.5)

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

int main(void){
    long long n, k, x[100010], ans = 500001000, minus=-1;
    cin >> n >> k;
    for(int i=0;i<=n;++i) x[i] = 300001000;
    for(int i=0;i<n;++i){
        cin >> x[i];
        if(x[i] < 0) minus = i;
    }
    int sum = 0, r[100010], l[100010], p=1;
    for(int i=0;i<=n;++i){
        r[i] = 300001000;
        l[i] = 300001000;
    }
    r[0] = 0;l[0] = 0;
    for(int i=minus+1;i<n;++i){
        r[p] = x[i];
        ++p;
    }
    p = 1;sum = 0;
    for(int i=minus;i>=0;--i){
        l[p] = abs(x[i]);
        ++p;
    }
    for(int i=0;i<=k;++i){
        long long mi = min(r[i]+l[k-i]*2, r[i]*2+l[k-i]);
        if(mi < ans)ans = mi;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    rep(i, n) {
        int a;
        cin >> a;
        ans += a >= k;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
bool func(int A,int B,int C,int K){
  if(K==0){
    if(A<B && B<C){
      return true;
    }
    return false;
  }
  return (func(2*A,B,C,K-1) || func(A,2*B,C,K-1) || func(A,B,2*C,K-1));
}
    
int main(){ 
  int A,B,C,K;
  cin >> A >> B >> C >> K;
  if(func(A,B,C,K)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
} 

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

int top, S[1000];

void push(int x){
    S[++top] = x;
}

int pop(){
    top--;
    return S[top+1];
}

int main(){
    int a, b;
    top = 0;
    string d;

    while (cin >> d){
        if(d == "+"){
            a = pop();
            b = pop();
            push(a+b);
        }else if(d == "-"){
            b = pop();
            a = pop();
            push(a - b);
        }else if (d == "*"){
            a = pop();
            b = pop();
            push(a * b);
        }else{
            push(stoi(d));
        }
    }

    cout << pop() << endl;

    return 0;

}


Measured memory_bytes: 3172
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define all(v) v.begin(), v.end()
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int A,B;
    cin>>A>>B;
    if(A<=8&&B<=8) cout<<"Yay!"<<endl;
    else cout<<":("<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b;
    cin>>a>>b;
    ll flag=0;
    int i=1;
    for( i=1;i<10000;i++)
    {
        if(int(i*0.08)==a&&int(i*0.10)==b)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
        cout<<i<<"\n";
    else cout<<-1<<"\n";

    return 0;
}


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

int main() {

    long long int N;
    long long int tmp;
    long long int A[200000];
    long long int sum = 0;
    cin >> N;
    for (int i=0; i < N; i++) {
        cin >> tmp;
        A[i] = tmp - (i+1);
        sum += A[i];
    }

    sort(A, A+N);

    long long int b = sum / N;
    long long int b1;
    b = A[N/2];
    b1 = A[N/2+1];
    long long int cost_b = 0;
    long long int cost_b1 = 0;
    for (int i=0; i< N; i++) {
        cost_b += abs(A[i]-b);
        cost_b1 += abs(A[i]-b1);
    }

    cout << min(cost_b, cost_b1) << endl;

    return 0;
}


Measured memory_bytes: 1792
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
//#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


//std::ios::sync_with_stdio(false);
int n,m,q;
int res=0;
int a[55],b[55],c[55],d[55];
int gen(int pos,vi v,int x){
	int j,i;
	if(pos==n){
		int ans=0;
		rep(i,q){
			if(v[b[i]]-v[a[i]]==c[i]){
				ans+=d[i];
			}
		}
		res=max(res,ans);
		return 0;
	}
	vi v1;
	f(j,x,m+1){
		v1=v;
		v1.pb(j);
		gen(pos+1,v1,j);
	}
	return 0;
}
int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int i;
	cin>>n>>m>>q;
	rep(i,q){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		a[i]--;
		b[i]--;
	}
	vi vec;
	gen(0,vec,1);
	cout<<res<<endl;
	return 0;
} 


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	i64 n; scanf("%lld", &n);

	std::vector<std::pair<i64, int>> vec;
	for(i64 i = 2; i * i <= n; i++) {
		if(n % i) continue;

		vec.push_back({i, 0});
		while(!(n % i)) {
			vec.back().second++;
			n /= i;
		}
	}
	if(n != 1) vec.push_back({n, 1});

	int ans = 0;
	for(auto e: vec) {
		int tmp = e.second;
		for(int i = 1; i <= tmp; i++) {
			ans++;
			tmp -= i;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3756
import math

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

cities = [a, b, c, d, e]
min_val = 1e18
for i, x in enumerate(cities):
    if x < min_val:
        min_val = x
        idx = i

ans = 0 if idx == 0 else idx

ans += math.ceil(n / min_val)
ans = ans + 4 - idx
print(ans)


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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

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

const int MAXN = 1e5 + 5;

int n, sz[MAXN];
vector <point> E[MAXN];
ll dist[MAXN], sol;
vector <int> centroid;

void dfs(int x, int p) {
  sz[x] = 1;
  int mx = 0;
  for (auto e : E[x]) {
    if(e.first == p) continue;

    dfs(e.first, x);
    sz[x] += sz[e.first];
    mx = max(mx, sz[e.first]);
  }

  if(max(mx, n - sz[x]) <= n / 2)
    centroid.push_back(x);
}

void dfs_dist(int x, int p = -1){
  sz[x] = 1;
  for(auto e : E[x]){
    if(e.first == p) continue;
    dist[e.first] = dist[x] + e.second;
    dfs_dist(e.first, x);
    sol += 2LL * e.second * min( sz[e.first], n - sz[e.first] );
    sz[x] += sz[e.first];
  }
}

ll solve(int x){
  sol = 0;
  dfs_dist(x);

  ll mn = 1e18;
  for(auto e : E[x])
    mn = min(mn, (ll)e.second);

  if(sz(centroid) == 1)
    return sol - mn;

  for(auto e : E[x])
    if(e.first == centroid[0] || e.first == centroid[1])
      return sol - e.second;
}

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

  cin >> n;
  REP(i, n - 1){
    int a, b, c;
    cin >> a >> b >> c;
    a --; b --;
    E[a].pb(point(b, c));
    E[b].pb(point(a, c));
  }

  dfs(0, 0);
  ll sol = 1e18;
  for(auto it : centroid)
    sol = min(sol, solve(it));
  cout << sol;
}


Measured memory_bytes: 12288
#include <stdio.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
int h,w,a,res=0;
int c[10][10];

int main(int argc, char const *argv[]){
	scanf("%d%d",&h,&w);
	rep(i,10)rep(j,10)scanf("%d",&c[i][j]);
	rep(k,10)rep(i,10)rep(j,10)
		if(c[i][j]>c[i][k]+c[k][j]) c[i][j]=c[i][k]+c[k][j];
	rep(i,h)rep(j,w){
		scanf("%d",&a);
		if(a>=0)res+=c[a][1];
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 7368791

static int m;
static int n;

static int h[N];

int main(void) {
  int i, j;
  
  for (;;) {
    scanf("%d%d", &m, &n);
    if (m == 0 && n == 0) break ;
    memset(h, 0, sizeof(h));
    
    for (i = m; i < N; ++i) {
      if (h[i] != 0) continue ;
      if (n == 0) break ;
      for (j = i; j < N; j += i)
        h[j] = 1;
      --n;
    }
    printf("%d\n", i);
  }

  return EXIT_SUCCESS;
}

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

int main(){
    ll a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    ll ans = 0;
    if (a + b > 2 * c){
        ans += min(x, y) * 2 * c;
        ll xx = x;
        x -= min(x,y);
        y -= min(xx,y);
        if (x > 0){
            if (a > 2 * c){
                ans += x * 2 * c;
            }
            else {
                ans += x * a;
            }
        }
        else {
            if (b > 2 * c){
                ans += y * 2 * c;
            }
            else {
                ans += y * b;
            }
        }
    }
    else {
        ans += x * a + y * b;
    }
    cout << ans << endl; 
}


Measured memory_bytes: 256
#include <cstring>
#include <cassert>
#include <utility>
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <tuple>
#include <climits>
#include <limits>
#include <deque>
#include <list>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <complex>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
 
#define init ios::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL);
#define setpr(x) cout << setprecision((x))
#define PI atan(1)*4
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define mk(a , b) { min((a) , (b)) , max((a) , (b)) }
#define flush cout.flush()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endc "\n"
#define MOD 1000000007
#define meme(x) memset((x), 0, sizeof((x)))
#define memo(x) memset((x),-1, sizeof((x)))
 
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

// #define int ll

ll egcd(ll a, ll b, ll &x, ll &y){
    if (a == 0LL){  
        x = 0LL;  
        y = 1LL;  
        return b;  
    }
    ll xx, yy;
    ll val = egcd(b % a, a, xx, yy);  
    x = yy - (b / a) * xx;  
    y = xx;  
    return val;
}

ll gcd(ll a, ll b){
    while(true){
        if(a>b)
            swap(a,b);
        if (a == 0) 
            return b; 
        ll p = b % a  , q = a;
        a = p;
        b = q;
    }
}
 
ll powerMod(ll x,ll y){
    ll res = 1;
    x %= MOD;
    while(y > 0){
        if(y & 1)res = (res*x)%MOD;
        y = y >> 1;
        x = (x * x)%MOD;
    }
    return res%MOD;
}

//  ==========      //\\       //||     ||====//||
//      ||         //  \\        ||     ||   // ||
//      ||        //====\\       ||     ||  //  ||
//      ||       //      \\      ||     || //   ||
//  ==========  //        \\  ========  ||//====|| 
//  code

vector< vector<int> > a, dp;

int rec(int idx, int owomen, int n){
    if(owomen == pow(2, n) - 1)
        return 1;

    if(dp[idx][owomen] > -1){
        return dp[idx][owomen];
    }

    int ans = 0;      
    for(int j = 0; j < n; j++){
        if(((1 << j) & owomen))
            continue;
        if(a[idx][j]){
            ans += rec(idx + 1, owomen | (1 << j), n);
            ans %= MOD;
        }
    }
    return dp[idx][owomen] = ans;
}

void solve(){
    int n,i,j,k,l,p;
    cin >> n;
    a.resize(n, vector<int>(n));
    k = pow(2, n) - 1;
    dp.resize(n, vector<int>(k, -1));

    for(auto &i : a){
        for(auto &j : i)
            cin >> j;
    }

    cout << rec(0, 0, n) << endc;
}

int32_t main(){
    init;
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 183956
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d,e,f,goukei;
	cin>>a>>b>>c>>d>>e>>f;
	goukei=a+b*5+c*10+d*50+e*100+f*500;
	if(goukei>=1000){
	cout<<"1"<<endl;
	}else{
	cout<<"0"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1156
//C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Others
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
const int dx[8] = { -1,0,1,-1,1,-1,0,1 };
const int dy[8] = { 1,1,1,0,0,-1,-1,-1 };


//LOVE NyantakoGG	https://www.youtube.com/channel/UC6XdFs8T6Ei54O0FYl3PVVA


using namespace std;


int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<char>>data(H, vector<char>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> data[i][j];
		}
	}
	vector<vector<char>>ans(H, vector<char>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (data[i][j] == '#') {
				ans[i][j] = '#';
			}
			else{
				int n = 0;
				for (int k = 0; k < 8; k++) {
					int ni = i + dx[k];
					int nj = j + dy[k];
					if (ni < 0 || H <= ni) {
						continue;
					}
					if (nj < 0 || W <= nj) {
						continue;
					}
					if (data[ni][nj] == '#') {
						n++;
					}
				}
				ans[i][j] = char(n + '0');
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cout << ans[i][j];
		}
		cout << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i = 0;i < (n); ++i)
#define all(v) v.begin(),v.end()
#define sort_1(v) sort(v.begin(),v.end())
#define sort_2(v) sort(v.begin(),v.end(),greater<ll>())
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    int h,w;
    cin >> h >> w;
    char a[h][w];
    vector<int> b;
    vector<int> c;
    vector<pair<int, int>> p;
    rep(i,h)rep(j,w){
        cin >> a[i][j];
    }
    rep(i,h){
        bool flag = true;
        rep(j,w){
            if(a[i][j] == '#'){
                flag = false;
                break;
            }
        }
        if(flag){
            rep(k,w){
                pair<int, int> ps = {i, k};
                p.pb(ps);
            }
        }
    }
    rep(i,w){
        bool flag = true;
        rep(j,h){
            if(a[j][i] == '#'){
                flag = false;
                break;
            }
        }
        if(flag){
            rep(k,h){
                pair<int, int> ps = {k, i};
                p.pb(ps);
            }
        }
    }
    rep(i,h){
        int count = 0;
        rep(j,w){
            bool flag = true;
            rep(k,p.size()){
                if(p[k].first == i && p[k].second == j){
                    flag = false;
                    count++;
                    break;
                }
            }
            if(flag){
                cout << a[i][j];
            }
        }
        if(count != w) cout << endl;
    }
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const int MOD = 1000000007;

int main() {
  string s;
  cin >> s;
  int ans = sz(s);
  rep(i, sz(s) - 1) {
    if (s[i] != s[i + 1]) ans = min(ans, max(i + 1, sz(s) - i - 1));
  }
  cout << ans << endl;
}


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

#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define eb emplace_back

typedef long long ll;
typedef pair<int,int> ii;
typedef vector< pair<int,int> > vii;
const int INF = 0x3f3f3f3f;

vector<string> v;
int n;

int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s;
        sort(s.begin(), s.end());
        v.pb(s);
    }

    sort(v.begin(), v.end());
    v.pb("$");

    ll l = 0;
    ll r = 0;
    ll ans = 0;

    while(l < n) {
        while(v[l] == v[r]) r++;
        ll ok = r-l;
        ans += (ok*(ok-1))/2;
        l = r;
    }

    cout << ans << endl;

    return 0;
}



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

#define HASH 3000011

typedef struct List {
	struct List *next;
	char *s;
} list;

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

int hash_string(char* s)
{
	int i, x = 0;
	for (i = 0; s[i] != 0; i++) x = ((x << 5) + s[i] - 'a') % HASH;
	return x;
}

int lex_smaller(char* s1, char* s2)
{
	int i;
	for (i = 0; s1[i] != 0 && s2[i] != 0; i++) {
		if (s1[i] < s2[i]) return 1;
		else if (s1[i] > s2[i]) return -1;
	}
	if (s1[i] == s2[i]) return 0;
	else if (s1[i] == 0) return 1;
	else return -1;
}

int main()
{
	int i, j, l[200001], N;
	char *S[200001], T[1000001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%s", T);
		for (l[i] = 0; T[l[i]] != 0; l[i]++);
		S[i] = (char*)malloc(sizeof(char) * (l[i] + 1));
		for (j = 0; j <= l[i]; j++) S[i][j] = T[j];
	}
	
	int h[200001];
	list *p, *hash[HASH], d[200001];
	for (i = 1; i <= N; i++) {
		h[i] = hash_string(&(S[i][1]));
		d[i].s = S[i];
		d[i].next = hash[h[i]];
		hash[h[i]] = &(d[i]);
	}
	
	int k, m, dp[26];
	long long ans = 0, tmp, pow[32];
	const long long inv = div_mod(1, 32, HASH);
	for (k = 1, pow[0] = 32; k < 32; k++) pow[k] = pow[k-1] * pow[k-1] % HASH;
	for (i = 1; i <= N; i++) {
		if (l[i] <= 1) continue;
		for (j = l[i] - 2, k = 0, tmp = 1; j > 0; j >>= 1, k++) if ((j & 1) == 1) tmp = tmp * pow[k] % HASH;
		h[i] = (h[i] - tmp * (S[i][1] - 'a') % HASH + HASH) % HASH;
		for (j = 0; j < 26; j++) dp[j] = 0;
		dp[S[i][0] - 'a'] = 1;
		for (j = 1, m = 1; j < l[i]; j++) {
			dp[S[i][j] - 'a'] = 1;
			for (p = hash[h[i]]; p != NULL; p = p->next) {
				if (dp[p->s[0] - 'a'] == 1 && lex_smaller(&(p->s[1]), &(S[i][j+1])) == 0) ans++;
			}
			tmp = tmp * inv % HASH;
			h[i] = (h[i] - tmp * (S[i][j+1] - 'a') % HASH + HASH) % HASH;
		}
	}
	
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

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

int main()
{
    int N,M;
    cin >> N >> M;
    int load[N] = {0};

    for(int i=0; i<M; i++)
    {
        int a,b;
        cin >> a >> b;
        load[a-1] += 1;
        load[b-1] += 1;
    }

    for(int i=0; i<N; i++) cout << load[i] << endl;
    return 0;
}

Measured memory_bytes: 3544
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
  long double d, t, s;
  cin >> d >> t >> s;
  if((d/s) <= t ) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main() {
  int N;
  int count = 0;
  string S;
  cin >> N;
  cin >> S;

  for (int i = 0; i < N - 2; i++) {
   if (S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C') {
     count++;
   }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    var ans = n / 2
    if (n % 2 == 0) {
        ans--
    }
    println(ans)
}

fun readStrings() = readLine()!!.split(" ")
fun readIntegers() = readStrings().map(String::toInt)


Measured memory_bytes: 33720
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    string a,b;
    cin>>a>>b;
    if(a.length()>b.length()){cout<<"GREATER";}
    else if(a.length()<b.length()){cout<<"LESS";}
    else{
    if(a>b){cout<<"GREATER";}
    else if(a<b){cout<<"LESS";}
    else{cout<<"EQUAL";}
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
P=tuple(map(int,input().split()))
Q=tuple(map(int,input().split()))
data=[]
for ii in itertools.permutations(range(1,n+1),n):
    data.append(ii)
data.sort()
for i,di in enumerate(data):
    if di==P:
        p=i
    if  di ==Q:
        q=i
print(abs(q-p))

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

int main(){
  string S;
  cin>>S;
  for(int i=0;i<S.size()-1;i++){
    if(S.at(i)==S.at(i+1)){
      cout<<"Bad"<<endl;
      return 0;
    }
  }
  cout<<"Good"<<endl;
}

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

#include <cmath>
using namespace std;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

int main() {
    int R;
    cin >> R;
    cout << 2 * R * M_PI << endl;
    return 0;
}

Measured memory_bytes: 3780
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<complex>
#include<random>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-8
#define REP(i, m) for(long long i = 0; i < m; ++i)
#define FOR(i, n, m) for(long long i = n; i < m; ++i)
#define ALL(v) v.begin(), v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<ll> vl;
typedef vector<vector<ll> > vll;

int main() {
	ios::sync_with_stdio(false);
	ll q,h,s,d;
	cin>>q>>h>>s>>d;
	ll n;
	cin>>n;
	ll lc2=min(q*8,min(min(h*4,s*2),d));
	ll lc1=min(q*4,min(h*2,s));
	ll res=0;
	res+=(n/2)*lc2;
	res+=(n%2)*lc1;
	cout<<res<<endl;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    string Sa, Sb, Sc;
    cin >> Sa >> Sb >> Sc;

    REV(Sa); REV(Sb); REV(Sc);
    char x = Sa.back();
    Sa.pop_back();
    while(true) {
        if(x == 'a') {
            if(SZ(Sa) > 0) {
                x = Sa.back();
                Sa.pop_back();
            }
            else {
                PR("A");
                break;
            }
        }
        if(x == 'b') {
            if(SZ(Sb) > 0) {
                x = Sb.back();
                Sb.pop_back();
            }
            else {
                PR("B");
                break;
            }
        }
        if(x == 'c') {
            if(SZ(Sc) > 0) {
                x = Sc.back();
                Sc.pop_back();
            }
            else {
                PR("C");
                break;
            }
        }
    }

    return 0;
}

/*



*/

Measured memory_bytes: 3632
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

struct Edge {
	int from;
	int to;
	int cost;
};
//kaette konai kuru
pair<long long int, long long int>dfs(const int now, const int from,const vector<vector<Edge>>&neededges) {
	vector<pair<long long int,long long int>>ps;
	for (const auto e : neededges[now]) {
		if (e.to == from)continue;
		else {
			pair<long long int, long long int>p(dfs(e.to, e.from, neededges));
			p.first += 1 * e.cost; p.second += 2*e.cost;
			ps.emplace_back(p);
		}
	}
	
	long long int maxsa =0;
	for (auto p : ps) {
		maxsa = max(maxsa, p.second - p.first);
	}
	long long int konai = 0, kuru = 0;
	for (auto p : ps) {
		konai += p.second;
		kuru += p.second;
	}
	konai -= maxsa;
	return make_pair(konai, kuru);
}
int main() {
	while (1) {
		int N; cin >> N;
		if (!N)break;
		vector<int>ps, ds;
		for (int i = 0; i < N - 1; ++i) {
			int p; cin >> p; p--;
			ps.push_back(p);
		}
		for (int i = 0; i < N - 1; ++i) {
			int d; cin >> d;
			ds.push_back(d);
		}
		long long int ans = accumulate(ds.begin(), ds.end(),0l);
		vector<vector<Edge>>edges(N);
		for (int i = 0; i < N - 1; ++i) {
			edges[i+1].push_back(Edge{ i+1,ps[i],ds[i] });
			edges[ps[i]].push_back(Edge{ ps[i],i+1,ds[i] });
		}
		vector<vector<Edge>>neededges(edges);
		for (int i = 0; i < N; ++i) {
			if (edges[i].size() == 1) {
				neededges[i].clear();
				neededges[edges[i][0].to].erase(find_if(neededges[edges[i][0].to].begin(), neededges[edges[i][0].to].end(), [=](const Edge&e) {return e.to == i; }));
			}
		}

		long long int mincost = 1e17;
		
			for (int i = 0; i < N; ++i) {
				if (!neededges[i].empty()) {
					pair<long long int, long long int>p(dfs(i, -1, neededges));
					mincost = min(mincost, p.first);
				}
			}
			if (mincost > 1e16)mincost = 0;
		
		cout << mincost + ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3344
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  if(s[2]==s[3] && s[4]==s[5]){
    cout<<"Yes";
  }
  else{
   cout<<"No";
  }
  return(0);
}

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

int main()
{
	int n, min, max;
	long sum;
	int a[10000];              //?????????????????????
    
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	min = a[0];
	max = a[0];
	sum = a[0];
	for (int j = 1; j < n; j++) {
		if (min > a[j]) {
			min = a[j];
		}else if (max < a[j]) {
				max = a[j];
		}
		sum = sum + a[j];
	}
	cout << min << " " << max << " " << sum << endl;
	
    return 0;
}

Measured memory_bytes: 1200
n,a,b=gets.split.map &:to_i
r=[]
n.times do
  r<< gets.split.map(&:to_i)
end
r.sort!{|a,b|a[2]<=>b[2]}
h={}
n.times do |i|
  x,y,z=r[i]
  hh=h.dup
  h.each do |e,v|
    hh[[e[0]+x,e[1]+y]]=v+z if !h[[e[0]+x,e[1]+y]] || h[[e[0]+x,e[1]+y]]>v+z
  end
  hh[[x,y]]=z if !h[[x,y]] || h[[x,y]]>z
  h=hh.dup
end
c=10**9
h.each do |e,v|
  c=v if e[0]*b==e[1]*a && c>v
end
p c==10**9 ? -1:c

Measured memory_bytes: 21436
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main()
{
    int a,b,c;
    int f=0;
    vector<int> v;

    cin>>a>>b>>c;
    while(a <= b)
    {
        if(a%c == 0)
        {
            f++;
        }
        a++;
    }
    cout<<f<<endl;
}

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  ll A, B, K;
  cin >> A >> B >> K;

  while(K > 0){

    if(A % 2 == 1) A--;
    B += A/2;
    A /= 2;
    K--;
    if(K==0) break;

    if(B % 2 == 1) B--;
    A += B/2;
    B /= 2;

    K--;

  }

  cout << A << " " << B << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i< (int)(n); i++)
#define rep2(i,x,n) for(int i = (int)x; i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define repitr(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<pair<string, int>> vp(n);
	rep(i, n) cin >> vp.at(i).first >> vp.at(i).second;
	string x;
	cin >> x;
	int ans = 0;
	bool flag = false;
	rep(i, n){
		if(flag == true) ans += vp.at(i).second;
		if(vp.at(i).first == x){
			flag = true;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  1_6
//
//  Created by Keita on 2020/06/19.
//  Copyright © 2020 Keita. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
using namespace std;

void doProblemA(){
    int x1, x2, x3, x4, x5;
    cin >> x1 >> x2 >> x3 >> x4 >> x5;
    cout << 15 - x1 - x2 - x3 - x4 - x5 << endl;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    doProblemA();
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;
#define x first
#define y second
#define mp make_pair

const int MAXN = (int)1e5;
int n, m;
string s;
int dp[MAXN + 5], otkud[MAXN + 5];
set <pll> g;
const int inf = (int)1e9;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> s;
g.insert(mp(0, 0));
for(int i = 1 ; i <= n ; ++i){
	if(s[i] == '1'){
		dp[i] = inf;
		otkud[i] = 0;
	}
	else{
		/*
		for(set <pll>::iterator j = g.begin() ; j != g.end() ; ++j){
			pll u = *j;
			cout << u.x << ' ' << u.y << endl;
		}
		*/
		pll o = *g.begin();
		dp[i] = o.x + 1;
		otkud[i] = o.y;
	}
	g.insert(mp(dp[i], i));
	if((int)g.size() > m){
		g.erase(g.find(mp(dp[i - m], i - m)));
	}
}
if(!dp[n] || dp[n] >= inf){
	cout << -1 << endl;
	return 0;
}
vector <int> sol;
int sad = n;
while(sad){
	sol.push_back(sad - otkud[sad]);
	sad = otkud[sad];
}
for(int i = (int)sol.size() - 1 ; i >= 0 ; --i){
	cout << sol[i] << ' ';
}
cout << endl;

return 0;
}



Measured memory_bytes: 7168
import sys

def main():

    # sys.stdin = open('input_a.txt')

    n = int(input())
    h = list(map(int, input().split()))

    dp = [0] * n
    dp[1] = abs(h[1] - h[0])

    for i in range(2, n):
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))

    print(dp[-1])
if __name__ == '__main__':
    main()


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

#define M 1046257
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch) {
  if ( ch == 'A' ) return 1;
  else if ( ch == 'C' ) return 2;
  else if ( ch == 'G' ) return 3;
  else if ( ch == 'T' ) return 4;
  return 0;
}

long long getKey(char str[]) {
  long long sum =0, p = 1, i;
  for(i=0;i<strlen(str);i++) {
    sum += p*(getChar(str[i]));
    p*= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1 + (key % (M-1)); }

int find(char str[]) {
  long long key, i, h;
  key = getKey(str); 
  for(i=0; ;i++) {
    h = (h1(key) + i*h2(key)) %M;
    if( strcmp(H[h],str) == 0) return 1;
    else if ( strlen(H[h]) == 0 ) return 0;
  }
  return 0;
}

int insert(char str[]) {
  long long key, i, h;
  key = getKey(str); // 文字列を数値に変換
  for(i=0; ; i++) {
    h = (h1(key) + i * h2(key)) %M;
    if(strcmp(H[h],str) == 0) return 1;
    else if(strlen(H[h]) == 0) {
      strcpy(H[h],str);
      return 0;
    }
  }
  return 0;
}

int main(void) {
  int i, n;
  char str[L], com[9];
  for(i=0;i<M;i++) H[i][0] = '\0';
  scanf("%d",&n);
  for(i=0;i<n;i++) {
    scanf("%s %s",com,str);
    if(com[0] == 'i') {
      insert(str);
    } else {
      if(find(str)){
        printf("yes\n");
      } else {
        printf("no\n");
      }
    }
  }
  return 0;
}


Measured memory_bytes: 16036
// abc153 E
// AOJで無制限ナップザックを倒したあとだったので行けるかと思ったら手こずった（応用する能力が皆無だからね 向いてないね
// WAが取れない ジャッジバグってんじゃねぇのか
// ググったコードの漸化式をパクってみた（解説にこういう細かいケースについての説明はどうせ期待できないので見てない）

package main
import "fmt"
func main(){
	var H, N int
	fmt.Scan(&H, &N)
	As, Bs := make([]int, N), make([]int, N)
	minA, minB := 100000, 100000
	for i:=0; i<N; i++{
		fmt.Scan(&As[i], &Bs[i])
		if minA > As[i]{
			minA = As[i]
		}
		if minB > Bs[i]{
			minB = Bs[i]
		}
	}
	if H<=minA{
		// どれでも倒せる
		fmt.Println(minB)
		return
	}
	INF := int(1e18)
	DP := make([][]int, N+101) // DP[i][j] := i番目までの魔法を好きなだけ使って数値をj以上にするときの最小の魔力消費値
	for i:=0; i<len(DP); i++{
		DP[i] = make([]int, H+10101)
		for j:=0; j<H+10101; j++{
			DP[i][j] = INF
		}
	}
	for i:=0; i<len(DP); i++{
		DP[i][0] = 0	// 0以下にするのは当然0回でいいので消費魔力も0
	}
	DP[0][0] = 0
	for i:=1; i<=N; i++{
		for j:=0; j<=H; j++{
			// if j>=As[i-1]{ 
			// 	DP[i][j] = min(DP[i-1][j], DP[i][j-As[i-1]]+Bs[i-1])
			// }else{
			// 	DP[i][j] = Bs[i-1]	// 一発で倒せるので
			// }
			// ↓ （解説は見ても意味ないので）ググったらこれが出てきた
			DP[i][j] = min(DP[i-1][j], DP[i][max(0, j-As[i-1])]+Bs[i-1])
			// なんでこれが通って今まで自分が書いたやつが通らないのかは完全に謎
		}
	}
	fmt.Println(DP[N][H])
}

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

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

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

using namespace std;

int main(){
	priority_queue<pair<int,int> > q;
	int k,t;
	scanf("%d%d",&k,&t);
	for(int i=0;i<t;i++){
		int n;
		scanf("%d",&n);
		q.push(make_pair(n,i));
	}
	while(q.size()>1){
		pair<int,int> t1 = q.top();q.pop();
		pair<int,int> t2 = q.top();q.pop();
		if(t1.first>1){
			q.push(make_pair(t1.first-1,t1.second));
		}
		if(t2.first>1){
			q.push(make_pair(t2.first-1,t2.second));
		}
	}
	if(q.size()==1){
		printf("%d\n",q.top().first-1);
	}else{
		printf("0\n");
	}
	return 0;
}



Measured memory_bytes: 256
/* ****revpro**** */
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl     '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii      map<ll,ll>
using namespace std;

#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update> 
ll dp[55][2505],vis[55][2505];
void solve()
{
  ll n,m,s;
  cin>>n>>m>>s;
  vector <pair<ll,pii>>a[n+1];
  ll c[n+1],d[n+1];
  rep(i,0,m)
  {
    ll x,y,z,w;
    cin>>x>>y>>z>>w;
    a[x].pb({y,{z,w}});
    a[y].pb({x,{z,w}});
  }
  rep(i,1,n+1) cin>>c[i]>>d[i];
  rep(i,0,n+1) rep(j,0,2505) dp[i][j]=1e18;
  dp[1][min(2500LL,s)]=0;
  priority_queue <pair<ll,pii>> q;
  q.push({0,{1,-min(2500LL,s)}});
  ll i,j;
  while(!q.empty())
  {
    pii v=q.top().S;
    q.pop();
    i=v.F;
    j=-v.S;
    if(vis[i][j]) continue;
    vis[i][j]=1;
    for(auto k:a[i])
    {
      if((k.S.F<=j)&&(dp[k.F][j-k.S.F]>dp[i][j]+k.S.S))
      {
       dp[k.F][j-k.S.F]=dp[i][j]+k.S.S;
        q.push({-dp[k.F][j-k.S.F],{k.F,-j+k.S.F}});
      }
    }
    if(dp[i][min(j+c[i],2500LL)]>dp[i][j]+d[i])
    {
      dp[i][min(j+c[i],2500LL)]=min(dp[i][min(j+c[i],2500LL)],dp[i][j]+d[i]);
      q.push({-dp[i][min(j+c[i],2500LL)],{i,-min(j+c[i],2500LL)}});
    }
  }
  rep(i,2,n+1) cout<<*min_element(dp[i],dp[i]+2505)<<endl;
}
signed main()
{
  
    /***********************************/
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 generator (seed);
    /***********************************/
 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS=1;
//  cin>>TESTS;
  while(TESTS--)
  {
    solve();
    
  }
  TIME
  return 0;
}

Measured memory_bytes: 8256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
 
int main(void)
{
    vector<int> a(3);
    int d;
    cin >> a[0] >> a[1] >> a[2] >> d;
    sort(a.begin(),a.end());
    for(int i = 0;i < d;i++)
        a[2] *= 2;

    cout << a[0]+a[1]+a[2] << endl;
        
}

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

int main() {
 int N,X,Y;
  cin >>N>>X>>Y;
  vector<int>count(N+1);
  for(int i=1;i<=N-1;i++){
  	for(int j=i+1;j<=N;j++){
    int p=min(abs(X-i)+abs(Y-j)+1,j-i);
    count[p]++;
    }
  
  }
  for(int i=1;i<N;i++){
  cout <<count[i]<<endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
PII arr[MAXN];
bool cmp(PII x,PII y){
	if(x.ff!=y.ff)
		return (x<y);
	return (x.ss>y.ss);	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
		scanf("%d%d",&arr[i].ff,&arr[i].ss);
	sort(arr,arr+m,cmp);
	int ans=0,mn=INF;
	for(int i=0;i<m;i++){
		umin(mn,arr[i].ss);
		if(arr[i].ff>=mn){
			ans++;
			mn=arr[i].ss;
		}
		else
			umin(mn,arr[i].ss);
	}	
	printf("%d\n",ans+1);
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        boolean rainflg = false;
        int answer = 0;
        for (int i = 0; i < 3; i++) {
            if (s.charAt(i) == 'R') {
                answer++;
                rainflg = true;
            } else {
                if (rainflg) {
                    break;
                }
            }
        }
        System.out.println(answer);
        sc.close();
    }
}

Measured memory_bytes: 35652