akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools

MOD = 10**9 + 7

# 右側に自身より低い数値をいくつ残せているか

N,*A = map(int,read().split())

A_rev = A[::-1]

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def get_sum(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i

right_zero = [0] * (N+1)
for i,x in enumerate(A_rev):
    right_zero[i+1] = right_zero[i] 
    if x == 0:
        right_zero[i+1] += 1

zero_cnt = right_zero[-1]
inv = pow(zero_cnt,MOD-2,MOD)

rest_smaller = [1] * (N+1)
for x in A:
    rest_smaller[x] = 0
rest_smaller = list(itertools.accumulate(rest_smaller))

right_smaller_prob = [(MOD+1)//2] * N
for i,x in enumerate(A_rev):
    if x != 0:
        right_smaller_prob[i] = rest_smaller[x] * inv

right_smaller_filled = [0] * N
bit = BIT(max_n = N)
p = 0
for i,x in enumerate(A_rev):
    if x != 0:
        right_smaller_filled[i] = bit.get_sum(x)
        bit.add(x,1)
        p += zero_cnt-rest_smaller[x]
    else:
        right_smaller_filled[i] = p * inv

fact = [1] * (N+1)
for n in range(1,N+1):
    fact[n] = fact[n-1] * n % MOD

answer = (1+sum(y*(x*p+z) for x,p,y,z in zip(right_zero,right_smaller_prob,fact,right_smaller_filled))) * fact[zero_cnt] % MOD
print(answer)

Measured memory_bytes: 119828
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n, k; cin >> n >> k;
	string s; cin >> s;
	
	int cnt = 0;
	rep(i, n - 1) cnt += s[i] != s[i + 1];
	cout << n - 1 - max(0, cnt - 2 * k) << endl;
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(int i=0;i<N;i++)
typedef long long ll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r;
    cin>>r;
    cout<<r*r<<endl;
}

Measured memory_bytes: 256
a, b, c = map(int, input().split())

ans = 0
for i in range(10000):
    if (a + 1) * (b + 1) * (c + 1) % 2 == 0:
        print(ans)
        break
    if a == b == c:
        print(-1)
        break
    ans += 1
    a, b, c = a // 2, b // 2, c // 2
    a, b, c = b + c, a + c, b + c
        


Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	int a,b,c,d,w1,w2;
	cin>>a>>b>>c>>d;
	w1=min(a,b);
	w2=min(c,d);
	cout<<w1+w2<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MAX 2000001

int A[MAX], B[MAX], C[MAX];
 
int main(int argc, char const *argv[]){
  int n, i, j, k = 0;
 
  scanf("%d", &n);
 
  for(i = 1; i <= n; i++){
    scanf("%d", &A[i]);
    if(k < A[i]) k = A[i];
  }
 
  for(i = 0; i <= k; i++){
    C[i] = 0;
  }
 
    for(j = 1; j <= n; j++){
      C[A[j]]++;
    }
 
  for(i = 1; i <= k; i++){
    C[i] += C[i-1];
  }
 
  for(j = n; j >= 1; j--){     
      B[C[A[j]]] = A[j];
      C[A[j]]--;
    }
 
  for(i = 1; i < n; i++){
    printf("%d ", B[i]);
  }
  printf("%d\n", B[n]);
  return 0;
}

Measured memory_bytes: 17892
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

  int n, m;
  cin >> n >> m;
  int a[n], b[n];
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i];
  }

  vector< pii > c(n);
  for(int i = 0; i < n; i++){
    c[i] = make_pair(a[i], b[i]);
  }
  sort(c.begin(), c.end());

  ll sum = 0;
  int r = m;
  for(int i = 0; r > 0 && i < n; i++){
    int t = min(c[i].second, r);
    sum += (ll)c[i].first * t;
    r -= t;
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

typedef pair<int, int> P;

// @param [in] n: ノード数
// @param [in] cost: 重みの隣接表現
// @param [in] s: スタートするノード
// @param [out] d: s からの距離
void dijkstra(const int& n, const vector<vector<pair<int, int>>>& cost, const int& s, vector<int>& d) {
  priority_queue<P, vector<P>, greater<P>> que;  // P#first が小さい順に取り出せる
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    P p = que.top(); que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (int j = 0; j < cost[v].size(); j++) {  // v から移動できる全ての node について
      int t = cost[v][j].first;
      int c = cost[v][j].second;
      if (d[t] > d[v] + c) {
        d[t] = d[v] + c;
        que.push(P(d[t], t));
      }
    }
  }
}

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

  int n;
  cin >> n;
  vector<vector<pair<int, int>>> cost(n);

  rep(i, n) {
    int u, k;
    cin >> u >> k;
    vector<pair<int, int>> tmp(k);
    rep(j, k) {
      int v, c;
      cin >> v >> c;
      tmp[j] = make_pair(v, c);
    }
    cost[i] = tmp;
  }

  // 求めるのは 0 からの距離
  vector<int> d(n, INF);
  dijkstra(n, cost, 0, d);

  rep(i, n) {
    cout << i << " " << d[i] << endl;
  }

  return 0;
}



Measured memory_bytes: 7188
k,n = map(int,input().split())
A = list(map(int,input().split()))
#A = list(map(int,input().split()))

C = []

for i,v in enumerate(A):
  if i <= len(A) - 2:
    C.append(A[i+1] - A[i])
  else: #最後は0番目との距離
    C.append(k - A[i] + A[0])

maxwidth = max(C)
print(k-maxwidth) #円周 - 最も物件同士の距離が開いている孤の長さ



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

vector<ll> calc_lef(const vector<ll>& A) {
	int N = A.size();
	vector<ll> ne(N);
	for (int i = 1; i < N; i++) {
		ll val = A[i], cnt = 0;
		while (A[i - 1] >= val) val <<= 2LL, cnt += 2;
		if (A[i - 1] >= A[i]) ne[i] = cnt - 2;
	}
	vector<ll> lef(N + 1);
	lef[1] = 1;
	set<int> pos;
	pos.insert(0);
	for (int i = 1; i < N; i++) {
		if (A[i - 1] >= A[i]) {
			if (ne[i] > 0) pos.insert(i);
			lef[i + 1] = lef[i] + 1;
			continue;
		}
		ll val = A[i - 1], cnt = 0, sum = 0;
		while (val < A[i]) {
			val <<= 2LL, cnt += 2;
			int pre = *pos.rbegin();
			sum += (i - pre) * 2;
			ne[pre] -= 2;
			if (ne[pre] == 0) pos.erase(pre);
		}
		lef[i + 1] = lef[i] + sum + 1;
	}
	return lef;
}

vector<ll> calc_rig(const vector<ll>& A) {
	int N = A.size();
	vector<ll> ne(N);
	for (int i = N - 2; i >= 0; i--) {
		ll val = A[i], cnt = 0;
		while (val <= A[i + 1]) val <<= 2LL, cnt += 2;
		if (A[i] <= A[i + 1]) ne[i] = cnt - 2;
	}
	vector<ll> rig(N + 1);
	set<int> pos;
	pos.insert(N - 1);
	for (int i = N - 2; i >= 0; i--) {
		if (A[i] <= A[i + 1]) {
			if (ne[i] > 0) pos.insert(i);
			rig[i] = rig[i + 1];
			continue;
		}
		ll val = A[i + 1], cnt = 0, sum = 0;
		while (val < A[i]) {
			val <<= 2LL, cnt += 2;
			int nex = *pos.begin();
			sum += (nex - i) * 2;
			ne[nex] -= 2;
			if (ne[nex] == 0) pos.erase(nex);
		}
		rig[i] = rig[i + 1] + sum;
	}
	return rig;
}

int main()
{
	int N;
	cin >> N;
	vector<ll> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	auto lef = calc_lef(A);
	auto rig = calc_rig(A);
	ll res = LLONG_MAX;
	for (int i = 0; i <= N; i++) {
		res = min(res, lef[i] + rig[i]);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 6500
N = int(input())
L = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    D = list(map(int, input().split()))
    for j in range(2,len(D)):
        L[D[0]][D[j]] = 1
for i in range(1,N+1):
    print(' '.join(map(str,L[i][1:])))

    


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
typedef long long ll;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

ll modpow(ll a, ll p)
{
    if (p == 0)
        return 1;
    if (!(p % 2))
    {
        ll halfP = p / 2;
        ll half = modpow(a, halfP);
        return half * half % mod;
    }
    else
    {
        return a * modpow(a, p - 1) % mod;
    }
}

ll comb(int a, int b)
{
    if (b > a - b)
        return comb(a, a - b);
    ll ansMul = 1;
    ll ansDiv = 1;
    for (int i = 0; i < b; i++)
    {
        ansMul *= a - i;
        ansDiv *= i + 1;
        ansMul %= mod;
        ansDiv %= mod;
    }
    ll ans = ansMul * modpow(ansDiv, mod - 2) % mod;
    return ans;
}

/*
int num = 200010;
vector<ll> fact(num), ifact(num);
fact[0] = 1;
fact[1] = 1;
for (int i = 2; i < num; i++) {
    fact[i] = fact[i-1] * i;
    fact[i] %= mod;
}
for (int i = 0; i < num; i++) {
    ifact[i] = modpow(ifact[i], mod-2);
    ifact[i] %= mod;
}
*/

int main() {
    int N, T; cin >> N >> T;
    vector<int> A(N), nums;
    rep(i, N) cin >> A[i];
    int minv = A[0];
    int maxp = 0;
    int ans = 0;
    int p;
    REP(i, 1, N) {
        p = A[i] - minv;
        if (p == maxp) ans++;
        else if (p > maxp) {
            maxp = p;
            ans = 1;
        }
        minv = min(minv, A[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
def tax(p, x):
	return p * (100 + x) // 100

while True:
	x, y, s = map(int, input().split())
	if (x, y, s) == (0, 0, 0):
		break
	r = 0
	for i in range(1, s):
		for j in range(1, s):
			t = tax(i, x) + tax(j, x)
			if t > s:
				break
			if (t) == s:
				r = max((tax(i, y) + tax(j, y)), r)
	print(r)

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

int main(){
  string A, B, C;
  cin >> A >> B >> C;
  char a=A.at(0)-0x20;
  char b=B.at(0)-0x20;
  char c=C.at(0)-0x20;
  cout << a << b << c << endl;
}

Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int N = 120000;

int n;

struct seg {
    ll l, r;
};

seg a[N];
ll dp[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
    cin >> n;
    ll bl = 0;
    ll br = 1e9 + 100;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].l >> a[i].r;
        ++a[i].r;
        bl = max(bl, a[i].l);
        br = min(br, a[i].r);
    }

    ll ad = 0;

    if (bl < br) {
        ll go = br - bl;
        ad += 2 * go;
        for (int i = 0; i < n; ++i) {
            a[i].r -= go;
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, a[i].r - a[i].l);
    }

    sort(a, a + n, [] (seg a, seg b) {
            return make_pair(a.l, a.r) < make_pair(b.l, b.r);
            });

    ll oth = 1e9 + 100;

    for (int i = 0; i < n; ++i) {
        oth = min(oth, a[i].r);
        dp[i] = max(0ll, oth - a[i].l);
    }
    oth = 1e9 + 100;
    for (int i = n - 1; i > 0; --i) {
        oth = min(oth, a[i].r);
        ans = max(ans, dp[i - 1] + oth - a[n - 1].l);
    }

    cout << ans + ad << "\n";

	return 0;
}




Measured memory_bytes: 2560
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

double dp[301][301][301][2];   // dp[i][j][k][0/1]：0がi個、1がj個、2がk個となるような確率/回数期待値

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);

    int cnt[4]={0};
    int i;
    for(i=0; i<n; i++) {
        int tmp;
        scanf("%d", &tmp);
        cnt[tmp]++;
    }
    
    dp[0][cnt[1]][cnt[2]][0]=1;
    dp[0][cnt[1]][cnt[2]][1]=0;
    int j,k;
    const double eps=1.0e-12;
    for(i=0; i<=n; i++) {
        for(j=0; j<=n-i; j++) {
            for(k=0; k<=n-i-j; k++) {
                if(dp[i][j][k][0]<eps) continue;
                int l=n-i-j-k;
                if(l>0) {
                    dp[i][j][k+1][0] += dp[i][j][k][0]*l/(n-i);
                }
                if(k>0) {
                    dp[i][j+1][k-1][0] += dp[i][j][k][0]*k/(n-i);
                }
                if(j>0) {
                    dp[i+1][j-1][k][0] += dp[i][j][k][0]*j/(n-i);
                }
            }
        }
    }
    for(i=0; i<=n; i++) {
        for(j=0; j<=n-i; j++) {
            for(k=0; k<=n-i-j; k++) {
                if(dp[i][j][k][0]<eps) continue;
                int l=n-i-j-k;
                if(l>0) {
                    dp[i][j][k+1][1] += (dp[i][j][k][0]*l/(n-i))/dp[i][j][k+1][0] * (dp[i][j][k][1] + (double)n/(n-i));
                }
                if(k>0) {
                    dp[i][j+1][k-1][1] += (dp[i][j][k][0]*k/(n-i))/dp[i][j+1][k-1][0] * (dp[i][j][k][1] + (double)n/(n-i));
                }
                if(j>0) {
                    dp[i+1][j-1][k][1] += (dp[i][j][k][0]*j/(n-i))/dp[i+1][j-1][k][0] * (dp[i][j][k][1] + (double)n/(n-i));
                }
            }
        }
    }
    printf("%.10lf\n", dp[n][0][0][1]);

    return 0;
}


Measured memory_bytes: 425088
// C++ program to demonstrate insertion 
// into a vector of vectors 



#include <iostream> 
#include <vector> 
using namespace std; 


main() 
{ 
    
	int n;
	cin >> n;
	vector<vector<int> > vec; 
    vector<vector<int> > dp(n, vector<int>(3,0)); 

	for (int i = 0; i < n; i++) { 
		vector<int> v1; 
		for (int j = 0; j < 3; j++) { 
		    int val ;
		    cin >> val;
		    v1.push_back(val);
		} 
		vec.push_back(v1); 
	} 

	int maximum = -99999999;
	if(n==1){
	    for(int i=0;i<3;i++){
	        maximum = std::max(vec[0][i], maximum);
	    }
	}
	else{
	    dp[0][0] = vec[0][0],dp[0][1] = vec[0][1],dp[0][2] = vec[0][2];
	    for(int i = 1; i < n; i++ ){
	        for(int j =0; j< 3; j++){
	            int larger = -100000;
	            for(int k=0;k<3;k++){
	              if(k!=j)
	               larger = std::max(dp[i-1][k], larger);
	            }
	            dp[i][j] = vec[i][j] + larger;
	        }
	    }
        for(int i=0;i<3;i++){
            maximum =  std::max(dp[n-1][i], maximum);
        }
	}
	cout << maximum;
} 


Measured memory_bytes: 14252
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

using namespace std;


template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<1000000007>;


//二項係数ライブラリ
const int MAX = 1000000;
const int MOD = 1000000007;

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

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

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
//前処理COMinit()忘れずに


void solve() {
    int n, k; cin >> n >> k;

    COMinit();

    if (k >= n-1) {
        cout << COM(2*n-1, n-1) << endl;
        return;
    }

    mint ans = 0;

    for (int i = 0; i <= k; i++) {
        ans += COM(n-1, n-i-1) * COM(n, i);
    }

    cout << ans << endl;
}


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

Measured memory_bytes: 27076
using System;
using System.Linq;
using System.Collections.Generic;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();

            var flag = true;
            foreach(var x in a){
                if(x % 2 == 0){
                    if(x % 3 == 0 || x % 5 == 0){
                        continue;
                    }else{
                        flag = false;
                        break;
                    }
                }
            }

            Console.WriteLine(flag ? "APPROVED" : "DENIED");
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n; j++)

struct day{
  int a, b, c;
  day(int _a, int _b, int _c) {
    a = _a; b = _b; c = _c;
  }
};

int main(void) {
  int n, a, b, c;
  cin >> n;
  vector <day> v(n, day(0, 0, 0));
  ffor(n) {
    cin >> a >> b >> c;
    v[i] = day(a, b, c);
  }
  vector <day> dp(n, day(0, 0, 0)); // let dp[i] be the total happiness up to that day
  dp[0] = v[0];
  for(int i = 1; i < n; i++) {
    dp[i] = day(max(dp[i - 1].b, dp[i - 1].c) + v[i].a, 
                max(dp[i - 1].a, dp[i - 1].c) + v[i].b, 
                max(dp[i - 1].a, dp[i - 1].b) + v[i].c);
  }
  a = dp.back().a, b = dp.back().b, c = dp.back().c;
  cout << max({a, b, c}) << '\n';
}

Measured memory_bytes: 5608
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;



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

	cin >> N;
	multiset<int>ms;
	for (int i = 0; i < 1 << N; i++) {
		cin >> M;
		ms.insert(-M);
	}
	vector<int>box;
	box.push_back(*ms.begin());
	ms.erase(ms.begin());
	for (int i = 0; i < N; i++) {
		vector<int>add;
		for (auto j : box) {
			auto it = ms.upper_bound(j);
			if (it == ms.end()) {
				cout << "No\n";
				return 0;
			}
			add.push_back(*it);
			ms.erase(it);
		}
		for (auto j : add)box.push_back(j);
	}
	cout << "Yes\n";
}

Measured memory_bytes: 13984
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		String T = sc.next();

		boolean flg = false;

		for (int i = 0; i < S.length(); i++) {
			if (S.equals(T)) {
				flg = true;
				break;
			}
			S = change(S);
		}

		System.out.println(flg ? "Yes" : "No");

	}

	private static String change(String str) {

		str = String.valueOf(str.charAt(str.length() - 1)) + str.substring(0, str.length() - 1);
		return str;
	}
}

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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }
//Write From this Line

int main()
{
	ll n, m, v, p;
	cin >> n >> m >> v >> p;

	vector<ll> a(n);
	rep(i, n)cin>>a[i];
	SORT(a); rSORT(a);

	ll ok = 0, ng = n;	
	while(ng - ok > 1){
		ll mid = ok + ng; mid /= 2;
		if(mid < p){
			ok = mid;
			continue;
		}

		//上のp-1個には投票していい。
		ll use = (p-1) * (m);

		//a[mid]以下にも投票していい。
		use += (n - mid) * m;

		// a[p-1] ~ a[mid-1]に入れても良い分だけ入れる
		for(int i = p - 1; i <= mid - 1; i++){
			// 0票以上入れること。マイナスは無理
			use += min(m,max(0ll, (a[mid] + m) - a[i]));
		}
		bool muri = false;
		if(a[mid] + m < a[p-1]){
			// 無理
			muri = true;
		}
		if(use >= m * v);//ok
		else muri = true;
		if(muri){
			ng = mid;
		} else {
			ok = mid;
		}
	}
	cout << ok + 1 << endl;
}


Measured memory_bytes: 1152
N,M = map(int,input().split())
S = input()
S = S[::-1]
s = 0
used = [0]
while s < N:
    for i in range(M,-1,-1):
        if s+i > N:
            i = N-s
        if S[s+i]=='0':
            s += i
            used.append(s)
            break
    if i==0:
        break
if s==N:
    ans = []
    for i in range(len(used)-1):
        ans.append(used[i+1]-used[i])
    ans = ans[::-1]
    ans = ' '.join([str(c) for c in ans])
    print(ans)
else:
    print(-1)

Measured memory_bytes: 49888
S = input()
N = len(S)+1

i = 0
total = 0

def suma(n):
    if n <= 1:
        return 0
    return (n-1)*n//2

while True:
    j = S.find('><', i)
    if j == 0:
        total += 1
        i = j+1
    elif j > 0:
        t = S[i:j+1]
        tl = len(t)
        tc_s = t.count('<')
        tc_b = t.count('>')
        if t == tc_s or tl == tc_b:
            total += suma(tl+1)
        elif tc_s >= tc_b:
            total += suma(tc_s+1) + suma(tc_b)
        elif tc_s < tc_b:
            total += suma(tc_s) + suma(tc_b+1)
        i = j+1
    else:
        t = S[i:]
        tl = len(t)
        tc_s = t.count('<')
        tc_b = t.count('>')
        if t == tc_s or tl == tc_b:
            total += suma(tl+1)
        elif tc_s > tc_b:
            total += suma(tc_s+1) + suma(tc_b-1)
        elif tc_s < tc_b:
            total += suma(tc_s-1) + suma(tc_b+1)
        else:
            total += suma(tc_s+1) + suma(tc_b)
        break
print(total)


Measured memory_bytes: 44508
#include<iostream>

using namespace std;

int main(){
  int base, s, m, h;
  cin >> base;
  s=base%60;
  base-=s;
  base/=60;
  m=base%60;
  base-=m;
  h=base/60;
  cout << h << ":" << m << ":" << s << endl;
  return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
int id[300];
int need[4];
int sl[4];
int sl1[4];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	int xx , yy;
	cin >> xx >> yy;

	string s;
	string t;
	cin >> s >> t;

	id['L'] = 0;
	id['R'] = 3;
	id['U'] = 1;
	id['D'] = 2;

	need[1] = xx;
	need[2] = n - xx + 1;
	need[0] = yy;
	need[3] = m - yy + 1;
	for(int i=0;i<k;i++) {
		int u = id[s[i]];
		sl[u] ++;
		//cerr << sl[u] << " " << sl1[3-u] <<" " << need[u] << endl;
		if (sl[u] - sl1[3-u] >= need[u]) {
			cout << "NO";
			return 0;
		}

		int v = id[t[i]];
		sl1[v] ++;
		if (sl1[v] - sl[3 - v] > need[v] - 1) {
			sl1[v] = need[v] - 1 + sl[3 - v];
		}
	}
	cout << "YES";
	return 0;
}


Measured memory_bytes: 920
#include<bits/stdc++.h>
using namespace std;
typedef int Int;
#define int long long
#define INF 0x3f3f3f3f
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{

}
Int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    cout<<2*n/gcd(2,n)<<endl;
    return 0;
}

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

int main() {
    int a, b;
    int cnt = 0;
    cin >> a >> b;
    for (int i=a; i<=b; i++) {
        int x1, x2, x4, x5;
        x5 = i % 10;
        x4 = (i - x5) / 10 % 10;
        x1 = i / 10000;
        x2 = (i - x1*10000) / 1000;
        if (x1 == x5 && x2 == x4) {
            cnt++;
        }
    }
    cout << cnt << endl;
}

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

int main()
{
	int n = 0;
	cin >> n;
	int *array;
	array = new int[n];
	for (int i = 0; i < n; i++) cin >> array[i];
	for (int j = n - 1; j > 0; j--) cout << array[j] << " ";
	cout << array[0] << endl;
	return 0;
}

Measured memory_bytes: 1188
#include <algorithm>
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <cmath>
#include <iomanip>
#include <set>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<unsigned> als(n);
	vector<array<unsigned, 2>> bcls(m);
	for (auto& a : als)cin >> a;
	sort(als.begin(), als.end());
	for (auto& bc : bcls)cin >> bc[0] >> bc[1];
	sort(bcls.begin(), bcls.end(), [](array<unsigned, 2> l, array<unsigned, 2> r) {
		return l[1] > r[1];
		});

	unsigned pt = 0;
	for (int i = 0; pt < m && i < n; ++i) {
		if (als[i] > bcls[pt][1])break;
		als[i] = bcls[pt][1];
		--bcls[pt][0];
		if (bcls[pt][0] == 0)++pt;
	}
	unsigned long long asum = 0;
	for (auto a : als)asum += a;

	cout << asum << endl;

	return 0;
}

Measured memory_bytes: 1408
import re

N = int(input())
S = input()

R = re.findall("R", S)
G = re.findall("G", S)
B = re.findall("B", S)

c = 0
for i in range(N-2):
  for d in range((N-1-i)//2):
    if S[i] != S[i+d+1] and S[i+d+1] != S[i+2*d+2] and S[i+2*d+2] != S[i]:
      c += 1

print(len(R)*len(G)*len(B)-c)

Measured memory_bytes: 9924
import java.util.*;
public class Main
{
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int h=sc.nextInt();
    int n=sc.nextInt();
    long sum=0;
    for(int i=0;i<n;i++)
      sum+=sc.nextInt();
    if(sum>=h)
      System.out.println("Yes");
    else
      System.out.println("No");
  }
}


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

int main() {
  double w,h,x,y;
  cin >> w >> h >> x >> y;
  double ans = w*h / 2;
  int flag = 0;
  if (x*2 == w && y*2 == h) flag = 1;
  else flag = 0;
  cout << ans << " " << flag << endl;
  return 0;
}


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

int main() {
  string drop;
  int loop_count = 0;
  int g = 0, w =0, p=0, y=0;
  int drop_count=0;
  cin >> loop_count;

  for(int i=0;i < loop_count;i++){
    cin >> drop;
    if(drop=="G" && g==0){
      g++;
    }else if(drop=="W" && w==0){
      w++;
    }else if(drop=="P" && p==0){
      p++;
    }else if(drop=="Y" && y==0){
      y++;
    }
  }
  drop_count = g + w + p + y;
 
  if(drop_count ==4 ){      
      cout << "Four";
    }else if(drop_count==3){
      cout << "Three";
    }else if(drop_count==2){
      cout << "Two";
    }else if(drop_count==1){
      cout << "One";
    }else{
      cout << "Zero";
    }
      
  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//long long int countt[200003];
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define int long long
#define f first
#define s second
signed main()
{
    FAST;
    
     int i=0,j=0,k=0,n=0,m=0,count=0,temp=0,z;
    int temp1=0,temp2=0,temp3=0,x=0,l=0,y=0,sum=0;
    int left=0,up=0,anss=0,start=0,end=0,r=0,q=0,total=0;
    int maxx=0,minn=0,curr=0,ans=0,places=0,zeroes=0,low=0,high=0;
    int prev=0,mid=0,zz=0,d=0,val=0;
    
    cin>>k>>n;
    int a[n];
    
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    
    ans = a[n-1]-a[0];
    ans = min(ans , k-a[1]+a[0]);
   // cout<<ans<<endl;
    
    for(i=1;i<n-1;i++)
    {
        ans = min(ans , k - a[i] + a[i-1]);
        ans = min(ans , a[i] - 0 + k - a[i+1]);
    }
    cout<<ans<<endl;
        
    
    
    
    
    
}


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

how_many=[]
num=[]

counter=0
for i in range(1,n):
    counter+=1
    if s[i-1]!=s[i]:
        how_many.append(counter)
        num.append(int(s[i-1]))
        counter=0
how_many.append(counter+1)
num.append(int(s[-1]))


ans=0
accumulate=[0]
for i in range(len(how_many)):
    accumulate.append(accumulate[-1]+how_many[i])

for g in range(len(num)):
    l=g
    if num[l]==0:
        r=min(g+2*k,len(num))
    else:
        r=min(g+2*k+1,len(num))
    ans=max(ans,accumulate[r]-accumulate[l])
print(ans)

Measured memory_bytes: 51548
def main():
    X = int(input())

    for i in range(-1000, 1000):
        for j in range(-1000, 1000):
            if i**5 - j**5 == X:
                print(i, j)
                exit()

    print('No')


def test():
    for i in range(-10, 11):
        for j in range(-10, 11):
            print(i**5-j**5)


if __name__ == "__main__":
    main()
    # test()


Measured memory_bytes: 9192
#include <cstdio>
int nx, ny;
char map[55][55];
int dir[4][2]={{1,0}, {0,1}, {-1,0}, {0,-1}};
bool check(int y, int x){
    for (int i=0; i<4; i++){
        int yy=y+dir[i][1], xx=x+dir[i][0];
        if (yy<0 || xx<0 || xx>=nx || yy>=ny) continue;
        if (map[yy][xx]=='#') return true;
    }return false;
}

int main(void){
    char tmp;

    scanf("%d%d", &nx, &ny);
    for (int y=0; y<ny; y++) scanf("%s", map[y]);

    bool flg=true;
    for (int y=0; y<ny; y++){
        for (int x=0; x<nx; x++)
            if (map[y][x]=='#' && check(y, x)==false) {
                flg=false;
                break;
            }
        if (flg==false) break;
    }

    if (flg) printf("Yes\n");
    else printf("No\n");

    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main()
{
    int S, W;

    scanf("%d %d", &S, &W);

    if((S >= 1 && S <= 100) && (W >= 1 && W <= 100))
    {

        if(W >= S)
        {
            printf("unsafe");
        }

        else if(S > W)
        {
            printf("safe");
        }
    }
    return 0;
}


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

#define MAXN 100010
#define NEUT 1000000000

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k; cin >> n >> k;
	int h[MAXN];
	int dp[MAXN];
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		h[i] = x;
	}
	
	dp[n] = 0;
	/*
	for(int i = n - 2; i >= n - k; i--){
		int m = abs(h[i]- h[n]);
		for(int j = i+1; j < n; j++){
			m = min(m, abs(h[j] - h[i]) + dp[j]);
		}
		dp[i] = m;
	}
	*/
	for(int i = n-k; i < n; i++){
		dp[i] = abs(h[i] - h[n]);
	}
	
	for(int i = n-k-1; i > 0; i--){
		int m = NEUT;
		for(int j = i + 1; j <= i + k; j++){
			m = min(m, abs(h[j] - h[i]) + dp[j]);
		}
		dp[i] = m;
	}
	/*
	for(int i = 1; i <= n; i++){
		cout << dp[i] << " ";
	}
	cout << "\n";
	*/
	cout << dp[1] << "\n";
}

	


Measured memory_bytes: 1024
N = int(input())
A = list(map(int, input().split()))

A_sort = sorted(A, reverse=True)
Alice = [a for i, a in enumerate(A_sort) if i%2==0]
Bob = [a for i, a in enumerate(A_sort) if i%2==1]

ans = sum(Alice) - sum(Bob)

print(ans)

Measured memory_bytes: 9124
package main

import (
	"fmt"
)

func main() {

	var n int
	fmt.Scan(&n)
	if n == 1 {
		fmt.Println("Hello World")
	} else {
		var a, b int
		fmt.Scan(&a)
		fmt.Scan(&b)
		fmt.Println(a + b)
	}

}


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

using namespace std;


int main() {

    int l,r,d;
    cin>> l >> r >> d;
    int ans = 0;
    for (int i = l; i <= r; ++i)
    {
        if (i % d == 0)
            ans++;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

ll fac[510000], finv[510000], inv[510000];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < 510000; ++i) {
		fac[i] = fac[i - 1] * i%INF;//i!のmod INF
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}


int main() {
	int n;
	cin >> n;
	vector<pair<ll,ll>>x;
	REP(i, n) {
		ll X, L; cin >> X >> L;
		x.push_back({ X, L });
	}
	sort(x.begin(), x.end());
	ll ans = 0;
	ll now = x[0].first + x[0].second;
	for (int i = 1; i < n; ++i) {
		if (now > x[i].first - x[i].second) {
			now = min(x[i].first + x[i].second, now);
			ans++;
		}
		else {
			now = x[i].first + x[i].second;
		}
	}
	cout << n - ans << endl;
	return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define RES(a,i,j) a.resize(i);rep(ii,i)a[ii].resize(j); 
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout<<a<<" "<<b<<" "<<c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 
#define gre(n) greater<n>()

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
const int INF = 1000000000;
const double dINF = 1000000000;
const ll INF64 = 922337203685477580ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;
//メモ
//二次元配列のresizeのしかた
//vv.resize(n);
//for(size_t i=0; i<n; i++){
// vv[i].resize(n);
//}

//メモ
//負の辺を持つ最短経路問題では到達不可経路でも初期化値より小さくなりうるので注意しよう！
int main(){
    ll x;
    std::cin >> x;
    rrep(i,-150,150){
        rrep(j,-150,150){
            if(i*i*i*i*i-j*j*j*j*j==x){
                ppri(i,j);
                exit(0);
            }
        }
    }
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

vector<int> a,b,c;
int n,ma,mb;
int dp[50][500][500];

int f(int i, int ac, int bc){
	if(i == n){
		// cout<<"here"<<endl;
		int g = __gcd(ac,bc);
		if(g == 0){
			return 1e8;

		}
		if(ac/g == ma && bc/g == mb){
			return 0;
		}
		else{
			return 1e8;
		}
	}	
	if(dp[i][ac][bc] != -1){
		return dp[i][ac][bc];
	}

	dp[i][ac][bc] = min(c[i] + f(i+1,ac+a[i],bc+b[i]), f(i+1,ac,bc));
	return dp[i][ac][bc];
}


void solve(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>ma>>mb;
	a.resize(n);
	b.resize(n);
	c.resize(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	int ans = f(0,0,0);
	if(ans < 1e8){
		cout<<ans<<endl;
	}
	else{
		cout<<-1<<endl;
	}
}

int main(){
	// fastread;
	int t = 1;
	// cin>>t;
	for(int i=1;i<=t;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}


Measured memory_bytes: 49024
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		String[] bubbleAry =  br.readLine().split(" ");
		String[] selectAry = (String[])bubbleAry.clone();

		bubbleSort(n,bubbleAry);
		selectSort(n, selectAry);

		if(isStable(n,bubbleAry,selectAry)){
			System.out.println("Stable");
		}else{
			System.out.println("Not stable");
		}

	}

	public static void bubbleSort(int n, String[] cardAry){
		boolean flag = true;
		int y = 1;
		while(flag){
			flag = false;
			for(int i = n - 1 ; y <= i ; i-- ){
				if( (int)cardAry[i].charAt(1) < (int)cardAry[i - 1].charAt(1)){
					String tmp = cardAry[i];
					cardAry[i] = cardAry[i - 1];
					cardAry[i - 1] = tmp;
					flag = true;
				}
			}
			y++;
		}

		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < n; i++){
			sb.append(cardAry[i]);
			sb.append(" ");
		}
		sb.deleteCharAt(sb.length() - 1);
		System.out.println(sb.toString());
		System.out.println("Stable");
	}

	public static void selectSort(int n,String[] cardAry){
		int count = 0;
		for(int i = 0 ; i < n ; i++){
			int minIndex = i;
			for(int y = i + 1 ; y < n ; y++){
				if((int)cardAry[minIndex].charAt(1) > (int)cardAry[y].charAt(1)){
					minIndex = y;
				}
			}
			if(minIndex != i){
				String tmp = cardAry[minIndex];
				cardAry[minIndex] = cardAry[i];
				cardAry[i] = tmp;
				count++;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < n; i++){
			sb.append(cardAry[i]);
			sb.append(" ");
		}
		sb.deleteCharAt(sb.length() - 1);
		System.out.println(sb.toString());
	}

	public static boolean isStable(int n,String[] bubbleAry,String[] selectAry){

		for(int i = 0; i < n ; i++){
			if(!bubbleAry[i].equals(selectAry[i])) return false;
		}
		return true;
	}

}

Measured memory_bytes: 24360
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LLMAX (1ll << 60) - 1
#define INTMAX (1 << 30) - 1
#define MOD 1000000007 
#define NMAX 1000*100+1

#define numberOfSetBits(S) __builtin_popcount(S) // __builtin_popcountl(S) __builtin_popcountll(S)
#define MSET(x,y) memset(x,y,sizeof(x))
#define gcd(a,b) __gcd(a,b)
#define all(x)  x.begin(),x.end()
#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define print(x)    for(auto it=x.begin();it!=x.end();it++) cout<<*it<<' '; cout<<endl;
#define printii(x)  for(auto it=x.begin();it!=x.end();it++) cout<<*it.F<<' '<<*it.S<<'\t';  cout<<endl;
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}

#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define mc(a,b,c) mp(mp(a,b),c)
vi r,g,b;
ll ans = 0,n,x,t,m;
string s;


void solve(){
    for(int i=0;i<r.size();i++){
        for(int j=0;j<g.size();j++){
            ll x = r[i]+g[j];
            if(x%2==0){
                if(lower_bound(all(b),x/2)!=b.end()){

                    if(*lower_bound(all(b),x/2)==x/2){
                        ans--;
                    }
                }
            }
            if((2*g[j]-r[i]<n)&&(2*g[j]-r[i]>=0)){
                x = 2*g[j]-r[i];
                if(lower_bound(all(b),x)!=b.end()){

                    if(*lower_bound(all(b),x)==x){
                        ans--;
                    }
                }
            }
            if((2*r[i]-g[j]<n)&&(2*r[i]-g[j]>=0)){
                x = 2*r[i]-g[j];
                if(lower_bound(all(b),x)!=b.end()){

                    if(*lower_bound(all(b),x)==x){
                        ans--;
                    }
                }
            }
        }
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='R'){
            r.pb(i);
        }
        else if(s[i]=='G'){
            g.pb(i);
        }
        else{
            b.pb(i);
        }
    }
    ans = r.size() * g.size() * b.size();
    solve();
    cout<<ans;
    return 0;
}







Measured memory_bytes: 3728
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
    int N, K;  cin >> N >> K;
    V D(K);  VECCIN(D);

    while(true){
      map<int,bool> mp;  int tmp = N;  bool flag = true;
      for(int i = 0 ; i <= 9 ; i++)  mp[i] = false;
      while(tmp){  mp[tmp%10] = true;  tmp /= 10;  }
      for(int num : D){
        if(mp[num] == true){  N += 1;  flag = false;  }
      }
      if(flag){
      	cout << N << endl;
      	return 0;
      }
    }
	return 0;
}

Measured memory_bytes: 256
from math import ceil, sqrt

def prime_factorize_tuple(n):
    ret = []
    tmp = n
    for i in range(2, ceil(sqrt(n))):
        if tmp % i == 0:
            count = 0
            while tmp % i == 0:
                count += 1
                tmp //= i
            ret.append((i, count))

    if tmp != 1:
        ret.append((tmp, 1))

    if not ret:
        ret.append([n, 1])  # n = 1

    return ret

n = int(input())
ans = 0
for i in range(1, n + 1, 2):
    tmp = 1
    for prime, count in prime_factorize_tuple(i):
        tmp *= (count + 1)
    if tmp == 8:
        ans += 1
print(ans)


Measured memory_bytes: 62312
#include <stdio.h>
#define mod 1000000007
typedef long long ll;

int main(void) {
  ll i, j, k, n, m;
  scanf("%lld%lld", &n, &m);
  ll dp[n + 1][m + 1], s[n], t[m];
  for(i = 0; i < n; ++i) scanf("%lld", &s[i]);
  for(i = 0; i < m; ++i) scanf("%lld", &t[i]);
  for(i = 0; i <= n; ++i) dp[i][0] = 1;
  for(i = 0; i <= m; ++i) dp[0][i] = 1;
  for(i = 0; i < n; ++i) for(j = 0; j < m; ++j) {
    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j];
    if(s[i] != t[j]) dp[i + 1][j + 1] += mod - dp[i][j];
    dp[i + 1][j + 1] %= mod;
  }
  printf("%lld", dp[n][m]);
  return 0;
}

Measured memory_bytes: 31488
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() { 
    long long int n, a[5], ans = 4;
    cin >> n >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
    sort(a, a+5);
    if(a[0] >= n) {
        cout << 5 << '\n';
    } else {
        if(n%a[0]) {
            ans++;
        }
        cout << (ans + n/a[0]) << '\n';
    }
}


Measured memory_bytes: 256