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

int main() {
  int N, Q;
  cin >> N >> Q;
  string s;
  cin >> s;
  int sum[N] = {0};
  int cur_num = 0;
  for (int i = 1; i < s.size(); i++) {
    if (s[i] == 'C' && s[i-1] == 'A') {
      cur_num++;
    }
    sum[i] = cur_num;
  }
  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << (sum[r-1] - sum[l-1]) << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,k=ii()

def f(x):
    if x==0:
        return 1
    elif x==1:
        return k-1
    elif x%2==0:
        return f(x/2)**2
    else:
        return f(x/2)**2*(k-1)

print k*f(n-1)


Measured memory_bytes: 2820
N, M = map(int, input().split())
p = list(map(int, input().split()))

par = [i for i in range(N)]
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        pass
    else:
        par[x] = y

for i in range(M):
    xi, yi = map(int, input().split())
    unite(xi - 1, yi - 1)

ans = 0
for i in range(N):
    if same(i, p[i] - 1):
       ans += 1
print(ans)

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

// Macros
#define PRAGMA(x) _Pragma(#x)
//
#define F  first
#define S  second
#define PB push_back
#define MP make_pair
//
#define ALL(container)   container.begin(),container.end()
#define MAKE_UNIQUE(vec) do { PRAGMA(message "DO NOT FORGET TO SORT THE VECTOR !!!"); vec.erase(unique(ALL(vec)),vec.end()); } while(0)
// vec.resize() sucks, use vec.assign()
// comparator -> return <

// Rename Datatypes
using ll  = long long;
using ld  = long double;
using pii = std::pair <int,int>;

// Output, Common Containers
template <typename T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <typename T> ostream& operator << (ostream &os, const set<T> &v)    { for (T i : v) os << i << ' '; return os; }
template <typename T> ostream& operator << (ostream &os, const deque<T> &v)  { for (T i : v) os << i << ' '; return os; }
template <typename T, typename S> ostream& operator << (ostream &os, const pair<T,S> &v) { os << "(" << v.F << "=>" << v.S << ") "; return os; }
template <typename T, typename S> ostream& operator << (ostream &os, const map<T,S> &v)  { for (auto i : v) os << i << ' '; return os; }

// Debugging
#ifdef LOCAL
	#define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); d__f(_it, args); }
	void d__f(__attribute__((unused)) istream_iterator<string> it) {}
	template<typename Head, typename... Tail> void d__f(istream_iterator<string> it, Head H, Tail... T) { cerr << *it << " <=> [" << H << "]\n"; d__f(++it, T...); }
#else
	#define trace(args...)
#endif


// CODE STARTS HERE

signed main() {
	std::ios::sync_with_stdio(false); //Warning: Do NOT use C I/O now.
	std::cin.tie(nullptr); //Note: Comment out this line for interactive questions.
	// std::cout.setf(std::ios::fixed); std::cout.precision(20); //Note: To output decimals correctly.

	// int tt; cin >> tt;
	// for(int test_no = 1; test_no <= tt; ++test_no){}

	int n;
	cin >> n;

	int digit = n % 10;
	if(digit == 0 or digit == 1 or digit == 6 or digit == 8) cout << "pon\n";
	else if(digit == 3) cout << "bon\n";
	else cout << "hon\n";
}


Measured memory_bytes: 3596
def main():
    N = int(input())
    H = list(map(int, input().split()))

    if N == 1:
        print(0)
        quit()

    start = 0
    moves = []
    for i in range(N-1):
        if H[i] >= H[i+1]:
            continue
        moves.append(i - start)
        start = i + 1

    if H[N-2] >= H[N-1]:
        moves.append(i - start + 1)
    print(max(moves))


if __name__ == "__main__":
    main()


Measured memory_bytes: 14224
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cmath>
#include <cstdlib>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
#define ALL(x) x.begin(), x.end()
#define INF (1001000000)
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i:c)
#define EXIST(cs,v) (find(ALL(cs),(v))!=cs.end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define UNIQ(c) (c).erase(unique((c).begin(),(c).end()), (c).end());
#define P(p) cout<<(p)<<endl;

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

    int a, b;
    cin >> a >> b;

    if (a <= 5) {
        P("0");
    } else if (a >= 13) {
        P(b);
    } else {
        P(b/2);
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, k=-1;
    cin >> n;
    int a = 1, b = 500;
    while (b - a > 1) {
        int c = (a + b) / 2;
        if (c * (c - 1) / 2 > n) b = c;
        else a = c;
    }
    if (n == a * (a - 1) / 2) {
        k = a;
        cout << "Yes" << '\n' << k << '\n';
    } else {
        cout << "No" << '\n';
        return 0;
    }
    for (int i=0; i<k; i++) {
        int l = k - 1, s = i + (i == 0);
        cout << l << ' ' << s;
        l--;
        if (i != 0) s += l;
        for ( ; l >= k-i && l > 0; l--) {
            cout << ' ' << s;
            s += l - 1;
        }

        for ( ; l > 0; l--) {
            s++;
            cout << ' ' << s;
        }
        cout << '\n';
    }
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sed second
#define i64 int64_t
#define ui64 uint64_t
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define kpair pair<int, pair<int,int>
#define lwb lower_bound
#define upb upper_bound
const int mod = 1e9+7;
const int maxn = 1e5;

using namespace std;
ifstream fi("");
ofstream fo("");
ll n,k;
ll a[100000];
ll c[100001];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];

    for(int i=1;i<n;i++) {
        c[i] = c[i-1] + abs(a[i]-a[i-1]);
        int j = 2;
        while(i-j>=0&&j<=k){
            //cout<<i<<" "<<j<<endl;
            c[i]= min( c[i-j] + abs(a[i]-a[i-j]) , c[i] );
            j++;
        }
    }
    cout<<c[n-1];
}






Measured memory_bytes: 1792
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

L = 41

A, B = reads()
def solve(n):
  ans = 0
  for i in range(L+1):
    q, r = divmod(n, 2 ** (i + 1))
    ans |= ((q * (2 ** i) + max(0, r - 2 ** i)) & 1) << i
  return ans
print(solve(A) ^ solve(B+1))


Measured memory_bytes: 3828
//
// Created by Takaaki Hirano on 2018/09/01.
//
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
int x[2], y[2];

void solve() {
    int vec_x = x[1] - x[0];
    int vec_y = y[1] - y[0];
    int vecx3 = -vec_y;
    int vecy3 = vec_x;
    int x4 = x[0] + vecx3;
    int y4 = y[0] + vecy3;
    int x3 = x4 + vec_x;
    int y3 = y4 + vec_y;
    printf("%d %d %d %d", x3, y3, x4, y4);
}

int main() {
    cin >> x[0] >> y[0] >> x[1] >> y[1];
    solve();
    return 0;
}


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

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

	int free = 0;
	vector<int> color(8, 0);
	for(int i=0; i<N; i++)
	{
		int a;
		cin >> a;

		if(a >= 3200)
		{
			free++;
			continue;
		}

		color[a/400]++;
	}

	int ret_min = 0;
	for(int i=0; i<color.size(); i++)
		if(color[i] != 0)
			ret_min++;

	int ret_max = ret_min + free;
	if(ret_min == 0)
		ret_min = 1;

	cout << ret_min << " " << ret_max << endl;

	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 1e9+7;
const int maxn = 2e5+5;
int main() {
	ll n;
	cin>>n;
	ll ans = 0;
	for(ll i=1;i<=n;i++){
		ll t = n/i;
		int b1 = i,b2 = i*t;
		ll sum = (b1+b2)*t/2;
		ans+=sum;
	}
	cout<<ans<<endl;
//	cout<<cnt<<endl;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int n;
      string s;
      cin >> n >> s;
      
      int ans = 0;
      
      for (int i = 0; i < s.size(); i++) {
        int count = 0;
        for (char a = 'a'; a <= 'z'; a++) {
          bool left = false, right = false;
          
          for (int j = 0; j < i; j++) if (s[j] == a) left = true;
          for (int j = i; j < n; j++) if (s[j] == a) right = true;
          if (left && right) count++;
        }
        if (ans < count) ans = count;
      }
      
      cout << ans << endl;
    }

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

#define hell                         1000000007
#define lcm(a,b)                     (a*b)/__gcd(a,b)
#define ll                           long long
#define vll                          vector<ll>
#define vi                           vector<int>
#define pll                          vector< pair<ll,ll> >
#define pb                           push_back
#define mp                           make_pair
#define all(v)                       v.begin(),v.end()
#define lbnd                         lower_bound
#define ubnd                         upper_bound
#define bs                           binary_search
#define F                            first
#define S                            second
#define rep(i,a,b)                   for(i=a;i<b;i++)
#define parr(a,n)                    for(ll it=0;it<n;it++) cout<<a[it]<<" ";cout<<endl;
#define pcont(a)                     for(auto it:a) cout<<it<<" ";cout<<endl;
#define ret(x)                       return cout<<x,0;
#define endl                           '\n'

/*constants*/
#define MAXN                         100005
#define PI                           3.14159265358979323846

/*debug*/
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>void __f(const char* name, Arg1&& arg1){ std::cout << name << " : " << arg1 << '\n';}
    template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ','); std::cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define trace(...)
#endif

using namespace std;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	ll i,j,n,m,k,cnt=0,ans=0,t=1;
	cin>>n>>m;
	ll h,w;
	cin>>h>>w;
	cout<<(n*m)+(h*w)-m*h-n*w;	
	return 0;
}

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

using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
ll a[100003];
int righ[100003];
int pre[1000003][41];
int query(int x,int y){

int ans=0,i;

for(i=40;i>=0;i--)
{
    if(pre[x][i]>=y)
        continue;
    else{
//cout<<i<<endl;
        ans=ans+(1<<i);
        x=pre[x][i];


    }



}
ans++;



return ans;


}
int main(){

int n;
cin>>n;
int i,j;
ll l;
int q;

for(i=1;i<=n;i++)
    cin>>a[i];
cin>>l;
righ[n]=n;
for(i=n-1;i>0;i--){

    ll o=l+a[i];
righ[i]=(int)(upper_bound(a+1,a+n+1,o)-a);
righ[i]--;
//cout<<righ[i]<<endl;

    }
    for(i=0;i<=40;i++)
    {

        pre[n][i]=n;

    }

    for(i=n-1;i>=1;i--){


        pre[i][0]=righ[i];

        for(j=1;j<=40;j++){


            pre[i][j]=pre[pre[i][j-1]][j-1];

            }
        }

/*for(i=0;i<=40;i++)
    cout<<pre[1][i]<<endl;*/
    cin>>q;
    while(q--){


       int x,y;
       cin>>x>>y;


      int ans  =query(min(x,y),max(x,y));

cout<<ans<<endl;



    }





    return 0;

    }


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

struct P{
  int x;
  int y;
  int h;
};

int main(void){
  int N; cin >> N;
  vector<P> p(N);
  for(auto& _p: p){
    cin >> _p.x >> _p.y >> _p.h;
  }

  for(int y = 0; y <= 100; y++){
    for(int x = 0; x <= 100; x++){
      int H;
      bool res = true;
      for(int i = 0; i < N; i++){
        if(p[i].h > 0){
          H = p[i].h + abs(p[i].x - x) + abs(p[i].y - y);
          break;
        }
      }

      for(int i = 0; i < N; i++){
        if(p[i].h != max(0, H - abs(p[i].x - x) - abs(p[i].y - y))){
          res = false;
        }
      }
      if(res){
        cout << x << " " << y << " " << H << endl;
        return 0;
      }
    }
  }
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
#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##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int N;
vv<int> graph;

void dfs(vector<int>& depth, int v, int p) {
    if (p != -1) depth[v] = depth[p] + 1;
    for (int u : graph[v]) {
        if (u != p) {
            dfs(depth, u, v);
        }
    }
}

int main() {
    cin >> N;
    graph.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    if (N == 1) {
        write("First");
        return 0;
    }
    else if (N == 2) {
        write("Second");
        return 0;
    }

    vector<int> depth(N);
    dfs(depth, 0, -1);
    int s = 0;
    rep(i, N) {
        if (depth[i] > depth[s]) s = i;
    }
    depth[s] = 0;
    dfs(depth, s, -1);
    int rad = 0;
    rep(i, N) {
        rad = max(rad, depth[i] + 1);
    }

    vector<int> dp(rad + 1);
    dp[1] = 1;
    dp[2] = 0;
    rep(i, 3, rad + 1) {
        rep(j, 3) {
            if (j != dp[i - 2] && j != dp[i - 1]) {
                dp[i] = j;
                break;
            }
        }
    }

    write(dp[rad] ? "First" : "Second");
}

Measured memory_bytes: 22144
T=!p
F=!T
class Object
alias:%:==
def!=x
!self|x
end
end
until/#/=~gets
puts (0..2047).all?{|x|
eval$_.tr"-=>*+abcdefghijk","!%=&|"+("%011b"%x).tr("01","TF")
}?'YES':'NO'
end

Measured memory_bytes: 13292
import numpy as np

N, K = map(int, input().split())
A_lis = list(map(int, input().split()))
F_lis = list(map(int, input().split()))
A_lis = np.sort(A_lis)[::-1]
F_lis = np.sort(F_lis)

if A_lis.sum() <= K:
    print(0)
    exit()
if K == 0:
    print((A_lis * F_lis).max())

high = (A_lis * F_lis).max()
low = 0

while high > low + 1:
    mid = (high + low) // 2
    if (A_lis - np.minimum(A_lis, (mid // F_lis))).sum() <= K: #可能
        high = mid
    else:
        low = mid
print(high)


Measured memory_bytes: 43628
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>
#include <fstream>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	string s; cin >> s;
	for (char x : s)
	{
		if (x == '?')cout << 'D';
		else cout << x;
	}
}

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

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define PI 3.14159265358979323846

int Power(int a,int b)
{
    if(b == 0)
        return a;
    if(b &1)
        return a*Power(a,b-1);

    int t = Power(a,b/2);
    return t*t;
}

int GCD(int a,int b)
{
    if(b == 0)
        return a;
    return GCD(b,a%b);
}

void dfs(vector <int> graph[],bool visited[],int node,int n)
{
    visited[node] = true;

    for(int i=0;i<graph[node].size();i++)
    {
        int child = graph[node][i];
        if(!visited[child])
            dfs(graph,visited,child,n);
    }
    return;
}

void solve()
{
    int n,m;cin>>n>>m;
    vector <int> graph[n];

    while(m--)
    {
        int u,v;cin>>u>>v;
        u--;v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    bool visited[n];
    memset(visited,false,sizeof(visited));

    int connect = 0;

    for(int i=0;i<n;i++)
    {
        if(!visited[i])
        {
            connect++;
            dfs(graph,visited,i,n);
        }
    }
    connect--;
    cout<<connect;

    return;
}

int main()
{
   fast;

   int t;t = 1;
   while(t--)
    solve();

   return 0;

}




Measured memory_bytes: 10128
#include <stdio.h>
#define MAXSIZE 200000

int main(void){
    int maxBenefit=-2000000000,min,size,i,a[MAXSIZE];
    scanf("%d",&size);
    for(i=0;i<size;i++){
        scanf("%d",&a[i]);
    }
    
    min=a[0];
    for(i=1;i<=size-1;i++){
        maxBenefit=maxBenefit>(a[i]-min)?maxBenefit:(a[i]-min);
        min=min<a[i]?min:a[i];
    }
    
    printf("%d\n",maxBenefit);

    return 0;
}




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

string b(int n)
{
    if (n == 0)
        return "P";
    return "B" + b(n - 1) + "P" + b(n - 1) + "B";
}
ll bnum(int n)
{
    if (n == 0)
        return 1ll;
    return 3ll + 2 * bnum(n - 1);
}
ll pnum(int n)
{
    if (n == 0)
        return 1ll;
    return 1ll + 2 * pnum(n - 1);
}
ll solve(ll n, ll x)
{
    ll ret = 0;
    if (n == 0)
        return 1ll;
    if (x == 1)
        return 0ll;
    x -= 1;
    if (x <= bnum(n - 1))
    {
        return ret + solve(n - 1, x);
    }
    x -= bnum(n - 1);
    ret += pnum(n - 1);
    if (x == 1)
        return 1ll + ret;
    ret += 1;
    x -= 1;

    if (x <= bnum(n - 1))
    {
        return ret + solve(n - 1, x);
    }
    x -= bnum(n - 1);
    ret += pnum(n - 1);
    return ret;
}
int main()
{
    ll n, x;

    cin >> n >> x;

    cout << solve(n, x) << endl;

    return 0;
}

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

int calcLCM(int, int);

int main()
{
	const int matches[9]{2, 5, 5, 4, 5, 6, 3, 7, 6};
	int n, m;
	scanf("%d%d", &n, &m);
	std::vector<int> a(m);
	for (auto& e: a)
	{
		scanf("%d", &e);
		e--;
	}
	std::vector<std::pair<int, int>> dp(n + 1, {0, -1});
	dp[0].second = 0;
	for (int i{}; i < n; i++)
	{
		if (dp[i].second < 0) continue;
		for (int j{}; j < m; j++)
		{
			if (i + matches[a[j]] > n) continue;
			std::pair<int, int> next(dp[i].first + 1, a[j]);
			dp[i + matches[a[j]]] = std::max(dp[i + matches[a[j]]], next);
		}
	}
	int now{n};
	while (dp[now].first)
	{
		putchar('1' + dp[now].second);
		now -= matches[dp[now].second];
	}
	putchar('\n');

	return 0;
}

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

int main(){
  int res = 1e9;
  
  int N; cin >> N;
  
  int cnt = 0;
  
  for(int i = 0; i < N; i++){ 
    int a; cin >> a;
    if( a <= res ){ cnt++; res = a;}
    
  }
  
  cout << cnt << endl; return 0;
}

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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  ll n, w;
  cin >> n >> w;

  vector<pair<ll, ll>> v_wv(n);
  for (auto &p : v_wv) {
    cin >> p.first >> p.second;
  }

  ll offset = v_wv.front().first;
  array<vector<ll>, 4> vw;
  for (auto &p : v_wv) {
    vw[p.first - offset].push_back(p.second);
  }

  for (auto &v : vw) {
    sort(v.begin(), v.end(), greater<ll>());
  }

  ll ans = 0;
  for (ll i = 0; i <= vw[0].size(); i++) {
    for (ll j = 0; j <= vw[1].size(); j++) {
      for (ll k = 0; k <= vw[2].size(); k++) {
        for (ll l = 0; l <= vw[3].size(); l++) {
          ll sum_v = 0;
          sum_v += accumulate(vw[0].begin(), vw[0].begin() + i, 0ll);
          sum_v += accumulate(vw[1].begin(), vw[1].begin() + j, 0ll);
          sum_v += accumulate(vw[2].begin(), vw[2].begin() + k, 0ll);
          sum_v += accumulate(vw[3].begin(), vw[3].begin() + l, 0ll);
          ll sum_w = offset * i + (offset + 1) * j + (offset + 2) * k +
                     (offset + 3) * l;
          if (sum_w <= w) {
            // cout << i << ' ';
            // cout << j << ' ';
            // cout << k << ' ';
            // cout << l << ' ';
            // cout << "add: " << sum_v << ' ' << sum_w << '\n';
            ans = max(ans, sum_v);
          }
        }
      }
    }
  }

  cout << ans << '\n';
}

Measured memory_bytes: 3628
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scan(&s)

	if s[0] != 'A' {
		fmt.Println("WA")
		return
	}

	if strings.Count(s[2:len(s)-1], "C") != 1 {
		fmt.Println("WA")
		return
	}

	s = strings.Replace(s, "A", "a", 1)
	s = strings.Replace(s, "C", "c", 1)

	if s != strings.ToLower(s) {
		fmt.Println("WA")
		return
	}

	fmt.Println("AC")
}


Measured memory_bytes: 640
A = list(map(int,input().split()))
H = A[1]
N = A[0]

a = [0]
b = [0]

for i in range(0,N):
    A = list(map(int,input().split()))
    a.append(A[0])
    b.append(A[1])

a.sort(reverse = True)
b.sort(reverse = True)

countb = 0

while(True):
    if(H<=0):
        print(countb)
        exit()
    if (b[countb] > a[0]):
        H -= b[countb]
        countb += 1
        continue
    else:
        break

print(countb + int(H/a[0]) + (0!=H%a[0]))



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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int j;
	j=0;
	string S,T;
	cin>>S>>T;
	for(int n=0;n<3;n++)
	{
		if(S.substr(n,1)==T.substr(n,1))
		j++;
		else
		j+=0;
	} 
	cout<<j;
    return 0;
}

Measured memory_bytes: 256
l = [input() for i in range(5)]

a = 10
y = 0
for i in range(5):
  s = int(l[i]) % 10
  if a > s & s != 0:
    a = s
    y = i
    
sum = 0
for i in range(5):
  if y == i:
    sum += int(l[y])
  else:
    sum += int(l[i])
    if int(l[i])%10 != 0:
      sum += (10 - (int(l[i])%10))
print(sum)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long lint;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    int y, m, d;
    y = (s[0] - '0') * 1000 + (s[1] - '0') * 100 + (s[2] - '0') * 10 + (s[3] - '0');
    m = (s[5] - '0') * 10 + (s[6] - '0');
    d = (s[8] - '0') * 10 + (s[9] - '0');
    // cout << y << " " << m << " " << d << endl;
    if(y <= 2018){
        cout << "Heisei" << endl;
    }
    else {
        if(y == 2019 && m <= 4){
            cout << "Heisei" << endl;
        }
        else {
            cout << "TBD" << endl;
        }
    }
    return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> H(N);
  int64_t sum = 0LL;
  for (int i = 0; i < N; i++) cin >> H.at(i);
  if (M >= N) {
    cout << 0 << endl;
  } else {
    sort(H.begin(), H.end());
    for (int i = 0; i < N - M; i++) {
      sum += H.at(i);
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 4032
using System;

class aizu_judge
{
    static void Main()
    {
        while(true)
        {
            string[] cal = Console.ReadLine().Split();
            int a = Convert.ToInt32(cal[0]);
            int b = Convert.ToInt32(cal[2]);
            bool endFlg = false;
            switch(cal[1])
            {
                case "+":
                    Console.WriteLine(a + b);
                    break;
                case "-":
                    Console.WriteLine(a - b);
                    break;
                case "*":
                    Console.WriteLine(a * b);
                    break;
                case "/":
                    Console.WriteLine(a / b);
                    break;
                default:
                    endFlg = true;
                    break;
            }
            if (endFlg)
                break;
        }
    }
}

Measured memory_bytes: 9232
#include <bits/stdc++.h>
const int N=200005;
int c[N],d[N],a[N],b[N],mx,n,sum;
bool cmp(int x,int y){
	return x>y;
}
int solve(int x){
	for (int i=1;i<=n;i++) c[i]=a[i]%(x<<1),d[i]=b[i]%(x<<1);
	std::sort(c+1,c+n+1,cmp);
	std::sort(d+1,d+n+1);
	int pl1=1,pr1=0,pl2=1,pr2=1,ans=0;
	for (int i=1;i<=n;i++){
		long long t=c[i];
		while (d[pl1]+t<x && pl1<=n) pl1++;
		while (d[pr1+1]+t<2ll*x && pr1<n) pr1++;
		if (pr1>=pl1 && (pr1-pl1+1)&1) ans^=1;
		while (d[pl2]+t<3ll*x && pl2<=n) pl2++;
		while (d[pr2+1]+t<4ll*x && pr2<n) pr2++;
		if (pr2>=pl2 && (pr2-pl2+1)&1) ans^=1;
	}
	return ans*x;
}
int main(){
	scanf("%d",&n);
	int mx=0;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),mx=std::max(mx,a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]),mx=std::max(mx,b[i]);
	for (int i=0;(1<<i)<=(mx<<1);i++)
		sum+=solve(1<<i);
	printf("%d\n",sum);
} 

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

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n)
    {
        ll in;
        cin >> in;
        a[i] = in - 1;
    }
    ll next = 0;
    vector<ll> show(n, -1);
    show[0] = 0;
    ll gap = 0;
    bool kShort = false;
    rep(i, k)
    {
        next = a[next];
        if (show[next] != -1 && kShort == false)
        {
            kShort = true;
            gap = i + 1 - show[next];
            i = show[next] + gap * ((k - show[next]) / gap) - 1;
        }
        else
        {
            show[next] = i + 1;
        }
        if (i >= k - 1)
        {
            cout << next + 1 << endl;
            return 0;
        }
    }

    return 0;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,n,a,b,c;
    t = 1;
    while(t--) {
     cin >> a >> b >> c;
     n = a * 100 + b * 10 + c;
     if(n % 4 == 0)
      cout << "YES" << endl;
     else
      cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
fun main(arr: Array<String>) {
    val inpt = readLine()!!.split(" ").map { it.toInt() }
    a = inpt[0]
    b = inpt[1]
    x = inpt[2]
    println(getAns(0.0, 90.0))
}

var a = 0
var b = 0
var x = 0

fun getAns(min:Double, max:Double):Double {
    if(x == a*a*b) {
        return 0.0
    }
    if(max-min <= 0.000000001) {
        return min
    }
    val mid = (max+min)/2
    var isSafe = false
    var triangleEdge = Math.tan(Math.toRadians(mid)) * a
    val remain = x - ((a * triangleEdge / 2) * a)
    val tmp = Math.round(remain * 100000)/100000.0
    if(remain < 0) {
        val squareEdge = Math.sqrt(x*2.0/a/Math.tan(Math.toRadians(90-mid)))
        isSafe = squareEdge <= b
    } else if (remain >= 0) {
        val t = remain / (a*a)
        isSafe = t+triangleEdge <= b
    } else {
        isSafe = triangleEdge <= b
    }
    if(isSafe) {
        return getAns(mid, max)
    } else {
        return getAns(min, mid)
    }
}

Measured memory_bytes: 36576
def gcd(n, m):
    if min(n, m) == 0:
        return max(n,m)
    else:
        return gcd(min(n,m), max(n,m) % min(n,m))

def lcm(n, m):
    return n * m // gcd(n, m)


n = int(input())
t = []
for i in range(0, n):
    t.append(int(input()))
t_sorted = sorted(t)

time = 0
for i in range(0, n):
    if i == 0:
        time = t_sorted[0]
    else:
        time = lcm(time, t_sorted[i])

print(int(time))

Measured memory_bytes: 3064
n = int(input())
S = [int(i) for i in input().split()] + [0]
q = int(input())
T = [int(i) for i in input().split()]


def search(A,n,key):
  i = 0
  S[n] = key
  #S.append(key)
  while S[i] != key:
    i += 1
  return i != n

cnt = 0
for i in range(q):
  if search(S,n,T[i]):
    cnt += 1
    #print("cnt",cnt)
print(cnt)


Measured memory_bytes: 6552
#include<stdio.h>
int main(void)
{
    int a[100000];
    int n, i, j, b = 0, c = 0;

    scanf("%d", &n);

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

    }

    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
           b = a[i] - a[j];
           if(b < 0)
             b = -1 * b;
           if(b >= c)
             c = b;
        }
    }
    printf("%d\n", c);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#define ll long long
using namespace std;


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

void solve(){
  ll N,M;
  string S,T;
  cin >>N>>M;
  cin >>S;
  cin >>T;
  ll g=gcd(N,M);
  ll n=N/g;
  ll m=M/g;

  for(ll k=0;k<g ;k++){
    if(S[k*n]!=T[k*m]){
      cout <<-1<<endl;
      return ;
    }
  }


  cout <<m*n*g<<endl;
}

int main(){
  solve();

  return 0;
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <iostream>

using namespace std;

#define sz(a) (int)a.size()

const int N = 6e3;

int n, dp[N][N], ans;
string s;

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	cin >> s;
//	s = '#' + s;
	n = sz(s) - 1;
	for(int i = 1; i <= n + 1; ++i) {
		for(int j = i + 1; j <= n + 1; ++j) {
			if(s[i - 1] == s[j - 1] && (j - i) > dp[i - 1][j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				ans = max(dp[i][j], ans);
			}
	 	}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 119040
#include <iostream>
#include <string.h>
#include <math.h>
#include <complex>
using namespace std;

typedef complex<double> P;

int main(){

  int n,m,bx,by,x,y,sampm;
  P samp[9],vec[9],vec2[9],test;

  while(1){
  
      cin>>n;if(n==0)return 0;
      cin>>m;sampm=m;
      for(int i=0;i<m;i++){
        cin>>x>>y;
        if(i!=0){samp[i-1]=P(x-bx,y-by);}
        bx=x;by=y;
      }
      for(int h=1;h<=n;h++){
        cin>>m;
        for(int i=0;i<m;i++){
	  cin>>x>>y;
          if(i!=0){vec[i-1]=P(x-bx,y-by);}
          bx=x;by=y;
        }
        int same=0;
        for(int i=0;i<4;i++){
          int p=0;
          for(int j=0;j<m-1;j++)if(vec[j]!=samp[j])p=1;
          if(p==0){same=1;break;}
          for(int j=0;j<m-1;j++){vec[j]=vec[j]*P(0,1);}
	}
        if(same==0){
          for(int i=0;i<m-1;i++){vec2[i]=vec[m-2-i];}
          for(int i=0;i<4;i++){
          int p=0;
          for(int j=0;j<m-1;j++)if(vec2[j]!=samp[j])p=1;
          if(p==0){same=1;break;}
          for(int j=0;j<m-1;j++){vec2[j]=vec2[j]*P(0,1);}
  	  }
	}
        if(same==1&&m==sampm)cout<<h<<endl;
      }
      cout<<"+++++"<<endl;
    }
}

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

using namespace std;


#ifdef zxc

#include <sys/resource.h>
#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = int64_t;
using ld = long double;
const ld EPS = 1e-9;
//const ll MOD = 924844033;
const ld PI = 3.141592653589793;
const int maxn = 300001;
const ll MOD = 998244353;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

signed main() {
#ifdef zxc
    struct rlimit rl;
    const rlim_t kStackSize = 512L * 1024L * 1024L;
    assert(!getrlimit(RLIMIT_STACK, &rl));
    rl.rlim_cur = kStackSize;
    assert(!setrlimit(RLIMIT_STACK, &rl));
    freopen("../kolya_input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    //    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    //            freopen("", "r", stdin);
    //        freopen("hack.out", "w", stdout);
#endif


    function<void(int)> solve = [](int t) {
        int h1, m1;
        int h2, m2;
        cin >> h1 >> m1;
        cin >> h2 >> m2;
        int k;
        cin >> k;
        int t1 = 60 * h1 + m1;
        int t2 = 60 * h2 + m2;
        cout << t2 - t1 - k << "\n";
    };


    fast_io();
    cout.precision(9);
    cout << fixed;
    auto start = chrono::steady_clock::now();
//    int t;
//    cin >> t;
    for (int i = 1; i <= 1; ++i)solve(i);
    auto end = chrono::steady_clock::now();

    debug("time", chrono::duration_cast<chrono::milliseconds>(end - start).count() / 1000.0);

}


Measured memory_bytes: 3640
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            byte sx = 0, sy = 0;
            byte w = (byte) sc.nextInt();
            byte h = (byte) sc.nextInt();
            if (w == 0 && h == 0) break;
            byte[][] board = new byte[w][h];//x座標,y座標の順番
            for (byte i = 0; i < h; i++) {
                for (byte j = 0; j < w; j++) {
                    board[j][i] = (byte) sc.nextInt();
                    if (board[j][i] == 2) {
                        sx = j;
                        sy = i;
                        board[j][i] = 0;
                    }
                }
            }
            System.out.println(solve(w, h, board, sx, sy));
        }
    }

    private static byte solve(byte w, byte h, byte[][] board, byte sx, byte sy) {
        Queue<byte[][]> que_board = new ArrayDeque<>();
        Queue<byte[]> que_info = new ArrayDeque<>();
        byte[] info = {0, sx, sy};
        que_board.add(board);
        que_info.add(info);
        byte[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!que_board.isEmpty()) {
            byte[][] b_board = que_board.remove();
            byte[] b_info = que_info.remove();
            if (b_info[0] >= 10) break;
            for (byte[] dir : move) {
                byte[][] a_board = new byte[w][h];
                for (byte i = 0; i < w; i++) {
                    for (byte j = 0; j < h; j++) {
                        a_board[i][j] = (byte) (b_board[i][j] + 0);
                    }
                }
                byte[] a_info = b_info.clone();
                byte x = (byte) (a_info[1] + dir[0]);
                byte y = (byte) (a_info[2] + dir[1]);
                if (0 <= x && x < w
                        && 0 <= y && y < h) {
                    if (a_board[x][y] != 1) {
                        while (true) {
                            if (0 <= x && x < w
                                    && 0 <= y && y < h) {
                                if (a_board[x][y] == 0) {
                                    a_info[1] += dir[0];
                                    a_info[2] += dir[1];
                                    x += dir[0];
                                    y += dir[1];
                                } else if (a_board[x][y] == 1) {
                                    a_board[x][y] = 0;
                                    a_info[0] += 1;
                                    que_board.add(a_board);
                                    que_info.add(a_info);
                                    break;
                                } else if (a_board[x][y] == 3) {
                                    return (byte) (a_info[0] + 1);
                                }
                            } else break;
                        }
                    }
                }
            }
        }
        return -1;
    }
}



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


int main() {
  int a, b, c;
  cin >> a >> b >> c;
  set<int> S;
  S.insert(a);
  S.insert(b);
  S.insert(c);
    
  cout << S.size() << endl;  
  return 0;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii  = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define MOD 1000000007
#define EPS 10e-8
int gcd(int a,int b){return b?gcd(b,a%b):a;}    //最大公約数
int lcm(int a, int b) {return a * b / gcd(a, b);}   //最小公倍数

int main(){
    string s;
    cin >> s;
    bool flag = true;
    for (int i = 0; i < s.length(); i++)
    {
        if((i%2==0&&s[i]=='L')||(i%2==1&&s[i]=='R')){
            flag = false;
        }
    }
    if(flag)
    cout<< "Yes" << endl;
    else
    {
        cout<< "No" << endl;
    }
    
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define ll long long
int main () {
    ll X;
    cin >> X;
    ll ans = 0;
    for (auto i = 1; i <= X; i++) {
        ll mul = 1;
        while (i * mul <= X) {
            ans += i * mul;
            mul++;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll f[100005],a[100005],A,B;
int n,pre[100005],sum[100005];
int main(){
	scanf("%d%lld%lld",&n,&A,&B);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	a[++n]=5e18;
	pre[1]=1;
	for(int i=2;i<n;i++){
		pre[i]=pre[i-1];
		while(a[i+1]-a[pre[i]]>=B&&pre[i]<i) pre[i]++;
	}
	for(int i=2;i<=n;i++) sum[i]=sum[i-1]+(a[i]-a[i-1]<A);
	for(int i=1;i<n;i++){
		if(sum[i]-sum[pre[i]]) pre[i]=n+1;
	}
	ll sum=1;f[0]=1;
	for(int i=1,L=1;i<=n;i++){
		if(i>2&&a[i-1]-a[i-2]<B) sum=0,L=i-2;
		while(a[i]-a[L]>=A&&L<i-1) sum=(sum+f[pre[L]])%mod,L++;
		f[i]=sum;
		if(i>1&&a[i]-a[i-1]>=A) f[i]=(f[i]+f[i-1])%mod;
	}
	printf("%lld",f[n]);
	return 0;
}

Measured memory_bytes: 2560
INF = float("inf")

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,input_func:[input_func() for _ in range(n)]

import importlib
import_module = lambda module_name:importlib.import_module(module_name)

init_array_1dim = lambda value,n:[value]*n # 1次元配列を生成
init_array_2dim = lambda value,n,m:[init_array_1dim(value,n) for _ in range(m)] # 2次元配列を生成

gcd_base = lambda value1,value2:import_module('fractions').gcd(value1,value2) # 最大公約数（2値)
gcd = lambda lst:import_module('functools').reduce(gcd_base,lst) # 最大公約数（リスト）
lcm_base = lambda value1,value2:(value1*value2)//gcd_base(value1,value2) # 最小公倍数(2値)
lcm = lambda lst:import_module('functools').reduce(lcm_base,lst,1) # 最小公倍数(リスト)

permutations = lambda lst,n:import_module('itertools').permutations(lst,n) # 順列
combinations = lambda lst,n:import_module('itertools').combinations(lst,n) # 組み合わせ
product = lambda lst1,lst2:import_module('itertools').product(lst1,lst2) # 二つのリストの直積

round = lambda value:round(value) # 四捨五入
ceil = lambda value:import_module('math').ceil(value) # 切り上げ
floor = lambda value:import_module('math').floor(value) # 切り捨て

# キュー
init_q = lambda lst: import_module('collections').deque(lst)
q_pop = lambda q: q.popleft() # 先頭から取り出し
q_push = lambda q,value:q.appendleft(value) # 先頭に追加（値）
q_pushlist = lambda q,lst:q.extendleft(lst) # 先頭に追加（リスト）
q_append = lambda q,value:q.append(value) # 末尾に追加（値）
q_appendlist = lambda q,lst:q.extend(lst) # 末尾に追加（リスト）

# プライオリティキュー
init_heap = lambda a:import_module('heapq').heapify(a)
heap_push = lambda a,v:import_module('heapq').heappush(a,v)
heap_pop = lambda a:import_module('heapq').heappop(a) # 最小値を取り出す

def solution():
    # ここに実装
    N,K = input_ints()
    h = input_ints_list()

    dp = init_array_1dim(0,N)
    for i in range(N):
        if i == 0:
            continue
        temp = []
        for j in range(K):
            if i-j-1 < 0:continue
            temp.append(dp[i-j-1]+abs(h[i]-h[i-j-1]))
        dp[i] = min(temp)
    print(dp[N-1])
    
if __name__ == '__main__':
    solution()

Measured memory_bytes: 54304
N = int(input())
A,B = map(int, input().split())
Ps  = list(map(int, input().split()))

cnt_a = 0
cnt_b = 0
for p in Ps:
    if p <= A:
        cnt_a += 1
    elif p > B:
        cnt_b += 1
print(min(cnt_a,cnt_b,N-cnt_a-cnt_b))


Measured memory_bytes: 3060
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    x = II()
    print('Yes' if x >= 30 else 'No')

if __name__ == '__main__':
    main()

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

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define PB push_back
#define pb push_back

#define MP make_pair
#define mp make_pair
#define PII pair<int,int>
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>

#define ALL(a) (a).begin(),(a).end()
#define all(a) (a).begin(),(a).end()
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define VS vector<string>
#define VI vector<int>
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define in scanf
#define out printf
#define SORT(v, n) sort(v, v+n)
#define VSORT(v) sort(v.begin(), v.end())

using namespace std;

int main() {
    vector<char> chars(0);
    char tmp[100];
    string str;

    in("%s", tmp);
    str = tmp;

    REP(i, (int)str.size()){
        char c = str[i];
        if(c == 'B'){
            if(chars.size() > 0){
                chars.pop_back();
            }
        }else{
            chars.push_back(c);
        }
    }

    for(auto it = chars.begin(); it != chars.end(); it++){
        cout << *it;
    }
    cout << endl;

}


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

int main() {
	int M, D, ans = 0;
	cin >> M >> D;
	for (int i = 1; i <= M; ++i) {
		for (int j = 10; j <= D; ++j) {
			int d1 = j % 10, d10 = j / 10 % 10;
			if (2 <= d1 && 2 <= d10 && d1 * d10 == i) ++ans;
		}
	}
	cout << ans;
}

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

const ll M = 1000000007;

int main(void){
   ll n,a,b,i;
   cin >> n >> a>>b;
   ll ans=0;
   //ll a[n];
   //for(i=0;i<n;i++){
       
   //}
  
    std::cout << min(n*a,b) << std::endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }
    

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int H = cin.nextInt();
        int W = cin.nextInt();
        int N = cin.nextInt();
        int[] A = cin.ArrayInt(N);
        int[,] ans = new int[H, W];
        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < A[i]; j++)
            {
                int y = cnt / W;
                int x = cnt % W;
                if(y % 2 == 1)
                {
                    x = (W - 1) - x;
                }
                ans[y, x] = i + 1;
                cnt++;
            }
        }

        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                Console.Write($"{ans[i,j]} ");
            }
            Console.WriteLine();
        }
    }


}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 13140
n = int(input())
h = [int(i) for i in input().split()]
inf = 10**7
dp = [inf]*100005
dp[0] = 0
for i in range(1,n):
    dp[i] = min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]))
print(dp[n-1])

Measured memory_bytes: 20556
n=int(input())
s=input()
r=s.count('R')
g=s.count('G')
b=s.count('B')
ans=r*g*b
for i in range(1,(n+1)//2):
  for j in range(n-2*i):
    if len(set([s[j],s[j+i],s[j+2*i]]))==3:
      ans-=1
print(ans)

Measured memory_bytes: 9028