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

using namespace std;
using namespace std::chrono;

// Counts all pairwise multiples that are strictly lesser than mid
// pos contains positive numbers, neg contains negative, zeros has the count of zero in the initial array
ll calc(ll mid, vector<ll> &pos, vector<ll> &neg, ll zeros) {
	ll count = 0;
	if(mid < 0) {
		// Take each negative number, find corresponding positive number (mid / neg[i]) + 1, and count of such elements
		// negative * large_positive will give all the negative numbers smaller than mid
		for(int i=0; i<neg.size(); i++) {
			int bigger = pos.end() - upper_bound(pos.begin(), pos.end(), mid / neg[i]);
			ll x = (mid + neg[i]) / neg[i];
			count += bigger;
		}
	}
	else {
		// If mid > 0, include all zeros
		if(mid > 0) count += zeros;
		
		// Include all negative multiples
		count += neg.size()*pos.size();

		// Slightly complicated math, but works - perhaps can be simplified
		// Find how many negative numbers starting at index i+1, when multiplied by neg[i] result in values smaller than mid
		for(int i=0; mid>0 && i<neg.size(); i++) {
			ll x = (mid + abs(neg[i]) - 1) / abs(neg[i]);
			int bigger = neg.end() - upper_bound(neg.begin()+i+1, neg.end(), -x);
			count += bigger;
		}

		// Slightly complicated math, but works - perhaps can be simplified
		// Find how many positive numbers starting at index i+1, when multiplied by pos[i] result in values smaller than mid
		for(int i=0; mid>0 && i<pos.size(); i++) {
			ll x = (mid + pos[i] - 1) / pos[i];
			int bigger = lower_bound(pos.begin()+i+1, pos.end(), x) - pos.begin()-i-1;
			count += bigger;
		}
	}
	return count;
}

void run() {
	ll n, k, x;
	cin >> n >> k;
	vector<ll> pos, neg;
	int i, j, zeros=0;
	for(i=0; i<n; i++) {
		cin >> x; 
		if(x > 0) pos.emplace_back(x);
		if(x < 0) neg.emplace_back(x);
		if(x == 0) zeros++;
	}
	ll tot_zeros = 0;
	ll start = n-1;
	while(zeros > 0) {
		tot_zeros += max(0ll, start);
		zeros--;
		start--;
	}
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end());
	ll mid, h, l, ret=-2e18;
	h = 1e18+10, l = -1e18-10;

	// Binary search objective: Find the largest number that does not have less than K multiples
	while(l <= h) {
		mid = l + (h - l) / 2;
		ll count = calc(mid, pos, neg, tot_zeros);
		// Favorable condition. Set return to h. Get rid of elements in range [mid, h] - inclusive
		if(count >= k) {
			h = mid - 1;
			ret = h;
		}
		// Unfavorable condition. Get rid of elements in range [l, mid] - inclusive
		else {
			l = mid + 1;
		}
	}
	cout << ret << endl;
}

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


Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
void in753(int N, long long a, int b){
  a*=10;
  a+=b;
  if(a>N) return;
  ans.push_back(a);
  in753(N, a, 3);
  in753(N, a, 5);
  in753(N, a, 7);
}

int main(){
  int N;
  cin >> N;
  ans.assign(0,0);
  for(int i=3; i<=7; i+=2){
    in753(N, 0, i);
  }
  for(int i=0; i<ans.size(); i++){
    vector<bool> check(3, false);
    int k=ans[i];
    bool push=false;
    while(k>0){
      int l=k%10;
      k/=10;
      if(l==3) check[0]=true;
      if(l==5) check[1]=true;
      if(l==7) check[2]=true;
      if(check[0] && check[1] && check[2]){
        push= true;
        break;
      }      
    }
    if(push==false){
      ans.erase(ans.begin()+i);
      i--;
    }
  }
  cout << ans.size() << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod ((int)1e9+7)
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update> indexed_set_pair;
ll power(ll a,ll b) {
   ll res=1;
   while(b){
      if(b%2==1) res=(res*a)%mod;
      a=(a*a)%mod;
      b>>=1;
   }
   return res;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)2e5+5;
const int M = (int)1e3+5;
const int Q = 102;
const int logN = 19;

const double pie = acos(-1);

void check(ll& ans, ll p, ll x, ll k, ll d) {
  if(abs(p)<=k && (abs(p))%2 == k%2) {
    ll pos = x - p * d;
    ans = min(ans, (ll)abs(pos));
  }
}
void solve() {
  ll x,k,d;
  cin>>x>>k>>d;
  if(x<0) x = -x;
  ll p = min(k,x/d);
  ll ans = lim;
  REP(i,-1000,1000) {
    check(ans, p+i, x, k, d);
  }
  cout<<ans;
}

int main() {
    //freopen("./sort/b2.in","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        //cout<<"\n";
    }
}


Measured memory_bytes: 3616
#include <stdio.h>

int main(void) {
	int i = 0;
	int number;
	int stack[10];
	
	while (scanf("%d", &number) != EOF) {
		if(number != 0)
			stack[i++] = number;
		else
			printf("%d\n", stack[i-- - 1]);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(v) v.begin(), v.end()
#include <cmath>
int main() {
    static const double pi = acos(-1);
    int A, B, H, M;
    cin >> A >> B >> H >> M;

    double x = (H*60 + M)   /720.0;
    double y = (H*30 + M/2.0) /360;
    //ここの部分で 30H + M/2とすると桁落ちする？
    //printf("%.20f\n",x);
    //printf("%.20f\n",y);

    double th = 2 * pi * y;
    double tm = 2 * pi * M / 60;
    double theta  = th - tm;
    double ans;
    ans = sqrt(A * A + B * B - 2 * A * B * cos(theta));

    printf("%.10f\n",ans);
      
    return 0;
}

Measured memory_bytes: 4216
#!/usr/bin/env python3


def read_h(conv=int):
    return map(conv, input().split())


def read_v(n, conv=int):
    return [conv(input()) for _ in range(n)]


def main():
    n = int(input())

    for i in range(n // 7 + 1):
        if (n - 7 * i) % 4 == 0:
            print('Yes')
            return

    print('No')


if __name__ == '__main__':
    main()


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

typedef struct pair { int d, p; } Pair;

int comp(const void* a, const void* b)
{
    Pair x=*((Pair*)a), y=*((Pair*)b);
    return x.p<y.p;
}

Pair a[10010];
int main(void)
{
    int n, m;
    while (scanf("%d%d", &n, &m), (n|m)) {
        int i, res;
        for(i=0;i<n;++i) {
            int d, p;
            scanf("%d%d", &d, &p);
            a[i].d=d, a[i].p=p;
        }
        qsort(a, n, sizeof(Pair), comp);

#define min(x, y) x<y?x:y
        res=0;
        for(i=0;i<n;++i) {
            int x=min(m, a[i].d);
            a[i].d-=x;
            m-=x;
            res+=a[i].p*a[i].d;
        }
        printf("%d\n", res);
    }
    return 0;
}

Measured memory_bytes: 800
#include <bits/stdc++.h>
using namespace std;
const int N = 200009;
int n, m, a[N], x, y, num[N], tag[N], b[N], ans;
bool check(int x)
{
	return x >= 1 && x <= n;
}
void add(int x)
{
	if (check(x) && tag[x]++ == 0)
		ans--;
}
void del(int x)
{
	if (check(x) && --tag[x] == 0)
		ans++;
}
#define inc(x) add(num[x]--)
#define dec(x) del(++num[x])
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		num[i] = i;
	ans = n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		inc(a[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		dec(a[x]);
		inc(y);
		a[x] = y;
		cout << ans << '\n';
	}
}

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

int main(){

  int N;
  cin >> N;
  
  vector<int> a(N);
  
  int Alice = 0,Bob = 0;
    
  for(int i = 0; i < N; ++i){
  
    cin >> a.at(i);
  
  }
  
  sort(a.begin(), a.end());
  
  for(int i = 0; i < N; ++i){
  
    if(i % 2 == 0){
    
      Alice += a.at(N-1-i);
    
    }else{
    
      Bob += a.at(N-1-i);
    
    }
  
  }
  
  cout << Alice - Bob << endl;
  
  return 0;

}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int2(a, b);

    cout << b * 2.0 - (double)a << endl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

int main(void){
    int N;
    cin >> N;
    int A[N];
    int ans=0;
    rep(i,N) cin >> A[i];
    rep(i,N) if(i%2==0 && A[i]%2==1) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --------------------------------------------------------
#define FOR(i,l,r) for (int i = (l); i < (r); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0)
#define SUMLL(c) accumulate(ALL(c), 0LL)
#define SZ(c) ((int)(c).size())
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<int,int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const int INF = 1 << 30;
// const ll INF = 1LL << 62;
// --------------------------------------------------------


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);

    int N; cin >> N;
    VI A(N); REP(i,N) cin >> A[i];
    VI B(N); REP(i,N) cin >> B[i];
    VI C(N); REP(i,N) cin >> C[i];

    SORT(A);
    SORT(B);
    SORT(C);

    ll ans = 0;
    for (auto b : B) {
        ll n_A = lower_bound(ALL(A), b) - A.begin();
        ll n_C = C.end() - upper_bound(ALL(C), b);
        ans += n_A * n_C;
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 4516
#include<stdio.h>

int main(){
  char s[12];
  int a,b,i,ans=1;
  scanf("%d%d%s",&a,&b,s);
  for(i=0;i<a+b+1;i++){
    if(i==a){
      if(s[i]!='-'){
        ans=0;
        break;
      }
    }
    else{
      if(s[i]=='-'){
        ans=0;
        break;
      }
    }
  }
  puts(ans?"Yes":"No");
}

Measured memory_bytes: 128
//Vector, mapa, set.
//para cada una se debe incluir una libreria que es de mismo nombre.
/*vector: arreglo dinamico 
 * vector<tipo-de-dato> nombre;
*/
/*mapa: un par key, valor estilo f(x)=y siendo x absolutamente cualquier tipo de dato (puedo tener x como un string).
 * map<tipoDeKey,tipoDeValor> nombre;
*/
/*set: exactamente igual que un vector pero SOLAMENTE puede almacenar valores unicos. 
 * set<tipo-de-dato> nombre;
*/
//existe una librería muy potente que se llama algorithm. Esta te permite manipular con mayor facilidad los tipos de datos dinamicos
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	vector<string> entrada;
	int n;
	string auxiliar;
	cin>>n;
	//entrada.resize(n); define el tamaño físico del arreglo en n.
	for(int i = 0; i<n; i++){
		cin>>auxiliar;
		entrada.push_back(auxiliar); //Insertar al final, previamente aumentando el tamaño físico en 1.
	}
	//Borro los elementos repetidos de un arreglo.
	sort(entrada.begin(),entrada.end()); //Ordeno el arreglo.
	entrada.erase(unique(entrada.begin(),entrada.end()),entrada.end()); //Borro los únicos.
	cout<<entrada.size()<<endl;
	return 0;
}


Measured memory_bytes: 11572
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int MOD=1e9+7;
const int INF32=1<<30;
const ll INF64=1LL<<60;

void solve(){
  int n; cin >>n;
  int c[10][10]; memset(c,0,sizeof(c));
  for(int i=1; i<=n; i++){
    string s=to_string(i); char a=s[0];
    int x=a-'0',y=i%10;
    c[x][y]++;
  }
  int ans=0;
  for(int i=1; i<10; i++) for(int j=1; j<10; j++) ans+=c[i][j]*c[j][i];
  cout <<ans;
}

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

Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  string s;
  int n;
  cin>>s>>n;
  deque<char> d;
  rep(i,0,s.size()) d.push_back(s[i]);
  int p=1;
  rep(i,0,n){
    int q;
    cin>>q;
    if(q==1) p=3-p;
    else{
      int r;
      char c;
      cin>>r>>c;
      if(p==r) d.push_front(c);
      else d.push_back(c);
    }
  }
  if(p==1){
    while(d.size()){
      cout<<d.front();
      d.pop_front();
    }
  }
  else{
    while(d.size()){
      cout<<d.back();
      d.pop_back();
    }
  }
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define F first
#define S second
#define PB push_back

vector<ll> ps;
bitset<1000005> bs;

void sieve(ll upper) {
    ll sz = upper + 1;
    bs.set();
    bs[0] = bs[1] = 0;
    for (ll i = 2; i <= sz; i++)
        if (bs[i]) {
            ps.PB(i);
            for (ll j = i * i; j <= sz; j += i)
                bs[j] = 0;
        }
}

vii factorize(ll n) {
    vii ans;
    ll e, tmp = n;
    for (int p: ps) {
        if (p * p > tmp) {
            if (tmp == 1) {
                return ans;
            } else {
                ans.PB({tmp, 1});
                return ans;
            }
        }
        e = 0;
        while (tmp % p == 0) {
            e++;
            tmp /= p;
        }
        if (e)
            ans.PB({p, e});
    }
    ans.PB({tmp, 1});
    return ans;
}

int main() {
    sieve(1000000);

    ll N; cin >> N;
    vii fac = factorize(N);
    ll ans = 0;
    for (auto f: fac) {
        for (int i = 1; f.S > 0; i++) {
            f.S -= i;
            if (f.S >= 0)
                ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 4244
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
const ll mod=1000000007;
ll gcd(ll a,ll b){if(a<b)swap(a,b);while((a%b)!=0){a=b;b=a%b;}return b;}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main(){
  int na,nb,nc; cin>>na>>nb>>nc;

  bool f=0;
  if(na==7&&nb==5&&nc==5)
  f=1;
  else if(nb==7&&na==5&&nc==5)
  f=1;
  else if(nc==7&&na==5&&nb==5)
  f=1;
  if(f)
  puts("YES");
  else
  puts("NO");

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
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;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

const long long MOD = 1000000007LL;
const long long max_cache=1000000LL;
long long cache_fact[max_cache],cache_inv_fact[max_cache];
long long combination_cached(long long n,long long r,long long m){
  if(r<0||r>n)return 0;
  if(r==0||r==n)return 1;
  static bool cached=false;
  if(cached==false){
    cached=true;
    cache_inv_fact[1]=1;
    for (long long i = 2; i < max_cache; i++) {
      cache_inv_fact[i]=(m-m/i)*cache_inv_fact[m%i]%m;
    }
    for (long long i = 2; i < max_cache; i++){
      cache_inv_fact[i]=cache_inv_fact[i]*cache_inv_fact[i-1]%m;
    }
    cache_fact[0]=1;
    for (long long i = 1; i < max_cache; i++) {
      cache_fact[i]=cache_fact[i-1]*i%m;
    }
  }
  r=min(r,n-r);
  return cache_fact[n]*cache_inv_fact[r]%m*cache_inv_fact[n-r]%m;
}

void solve(long long n, long long k){
  if(k>=n){
    k=n-1;
  }
  ll ans=1;
  REP(k){
    ll ii=i+1;
    ans+=combination_cached(n,ii,MOD)*combination_cached(ii+(n-ii-1),n-ii-1,MOD)%MOD;
    ans%=MOD;
  }
  cout<<ans<<endl;
}

int main(){
  cout<<setprecision(1000);
  cin.tie(0);
  ios::sync_with_stdio(false);
    long long n;
    scanf("%lld",&n);
    long long k;
    scanf("%lld",&k);
    solve(n, k);
    return 0;
}


Measured memory_bytes: 15872
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>

#define ll long long
#define ld long double
#define ull unsigned ll
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  Inf = 2 * 1000 * 1000 * 1000;
ll LINF = (ll)4e18;
using namespace std;
#define M_PI       3.14159265358979323846   // pi


int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;

	int mn = 2e9;

	int cur = 0;

	for (int i = 0; i < (int)s.size(); i++) {
		if (i % 2 == 0 && s[i] == '0') cur++;
		if (i % 2 && s[i] == '1') cur++;
	}

	mn = min(mn, cur);
	cur = 0;

	for (int i = 0; i < (int)s.size(); i++) {
		if (i % 2 && s[i] == '0') cur++;
		if (i % 2 == 0 && s[i] == '1') cur++;
	}
	mn = min(mn, cur);
	cout << mn;
 	return 0;
}

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

int x[10][10];

int ssn(int a, int b, int c, int d){
    return x[x[x[x[0][a]][b]][c]][d];
}

int check(int a, int b, int c, int d, int e){
    return x[x[x[x[x[0][a]][b]][c]][d]][e];
}

int main(){
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++) cin>>x[i][j];
    }
    int cnt=0;
    for(int a=0;a<10;a++)
    for(int b=0;b<10;b++)
    for(int c=0;c<10;c++)
    for(int d=0;d<10;d++){
        int e=ssn(a,b,c,d);
        //Type1
        int bad = 0;
        for(int aa=0;aa<10;aa++){
            if(aa==a) continue;
            bad|=!check(aa,b,c,d,e);
        }
        if(bad){
            cnt++;
            continue;
        }
        for(int bb=0;bb<10;bb++){
            if(bb==b) continue;
            bad|=!check(a,bb,c,d,e);
        }
        if(bad){
            cnt++;
            continue;
        }
        for(int cc=0;cc<10;cc++){
            if(cc==c) continue;
            bad|=!check(a,b,cc,d,e);
        }
        if(bad){
            cnt++;
            continue;
        }
        for(int dd=0;dd<10;dd++){
            if(dd==d) continue;
            bad|=!check(a,b,c,dd,e);
        }
        if(bad){
            cnt++;
            continue;
        }
        for(int ee=0;ee<10;ee++){
            if(ee==e) continue;
            bad|=!check(a,b,c,d,ee);
        }
        if(bad){
            cnt++;
            continue;
        }
        //Type2
        if(a!=b&&!check(b,a,c,d,e)){
            cnt++;
            continue;
        }
        if(b!=c&&!check(a,c,b,d,e)){
            cnt++;
            continue;
        }
        if(c!=d&&!check(a,b,d,c,e)){
            cnt++;
            continue;
        }
        if(d!=e&&!check(a,b,c,e,d)){
            cnt++;
            continue;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 3092
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        if(N < 10 || N > 100)
            System.out.println("No");
        if(Integer.toString(N).contains("9") == true)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 21844
# -*- coding: utf-8 -*-

def infinite_product(n, k):
    inpr = 1
    if k == 0:
        k = 1
    
    for i in range(n, k+1):
        inpr *= i
    
    return inpr


s = input().split()
N = int(s[0])
K = int(s[1])

print(N-K+1)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
#define sign(a) ((a>0)-(a<0))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define LL long long
#define INF (LL)(1LL<<60)
#define all(a) a.begin(), a.end()
#define gr greater<LL>()

using namespace std;

template <class T>
class SegTree{
public:
    vector<T> arr;
    function<T(T,T)> f;
    T ini;
    uint n;
    SegTree(int N, function<T(T,T)> func, T ini_){
        f=func;
        ini=ini_;
        n=1;
        while(n<N)n<<=1u;
        arr.assign(2*n-1, ini);
    }

    void update(uint i, T val){
        i+=n-1;
        arr[i]=val;
        while(i>0){
            i=(i-1)/2;
            arr[i]=f(arr[2*i+1],arr[2*i+2]);
        }
    }

    T find(uint s, uint t){
        return __find(s,t,0,0,n);
    }
private:
    T __find(uint s, uint t, uint k, uint l, uint r){
        if(t<=l || s>=r)return ini;
        if(s<=l && t>=r)return arr[k];
        T vl=__find(s,t,2*k+1,l,(l+r)/2);
        T vr=__find(s,t,2*k+2, (l+r)/2, r);
        return f(vl,vr);
    }
};

int main(){
    LL N;
    cin >> N;
    vector<LL> A(N);
    rep(i,N)cin >> A[i];

    vector<LL> B(A);
    sort(all(B));
    rep(i,N)A[i]=(lower_bound(all(B),A[i]) - B.begin());

    SegTree<LL> st(200000, [](LL a, LL b){return a+b;}, 0);

    LL ans = 0;
    rep(j, N){
        auto a = A[j];
        ans += (j-st.find(0,a+1));
        st.update(a,st.arr[st.n-1+a]+1);
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 9980
N, M = map(int, input().split())
accepted = [0] * N
penalties = [0] * N
for _ in range(M):
    p, ac = input().split()
    p, ac = int(p) - 1, ac == "AC"
    accepted[p] |= ac
    penalties[p] += not accepted[p]
print(sum(accepted), sum(p for ac, p in zip(accepted, penalties) if ac))


Measured memory_bytes: 46168
h, w, a, b = map(int, input().split())

ans = []
for i in range(h):
    tmp = []
    if i < b:
        x = 0
    else:
        x = 1
    for j in range(w):
        if j < a:
            y = 0
            tmp.append(str(x^y))
        else:
            y = 1
            tmp.append(str(x^y))
    ans.append(tmp)

for l in ans:
    print("".join(l))

Measured memory_bytes: 83804
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>
#include<random>
using namespace std;

int main()
{
	string s;
	int y, m, d;
	vector<string> ans;
	while (cin >> s)
	{
		if (s == "#") break;
		cin >> y >> m >> d;
		if (y > 31 || (y == 31 && m > 4))
		{
			s = "?";
			y = y - 31 + 1;
		}
		s += " ";
		s += to_string(y);
		s += " ";
		s += to_string(m);
		s += " ";
		s += to_string(d);
		ans.push_back(s);
	}
	for (const auto& a : ans)
	{
		cout << a << endl;
	}
	
	return 0;

}


Measured memory_bytes: 3192
n,x,y = map(int,input().split())
ko = [0 for i in range(10**4)]
for i in range(1,n):
  for j in range(i+1,n+1):
    c1 = j-i
    if i<=x and y<=j:
      c2 = (x-i)+1+(j-y)
    elif i<=x and j<y:
      c2 = (x-i)+1+(y-j)
    elif x<i and y<=j:
      c2 = (i-x)+1+(j-y)
    else:
      c2 = (i-x)+1+(y-j)
    ko[min(c1,c2)] += 1
  #  print(i,j,j-i,c1,c2,ko[:10])
for i in range(1,n):
  print(ko[i])

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

using namespace std;

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

typedef long long ll;
typedef long double ld;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    string s;
    cin >> s;
    bool ok = true;
    int n = s.size();
    if (n % 2) {
        cout << "No" << endl;
        return 0;
    }
    rep (i, s.size()) {
        if ((i % 2 == 0) && s[i] != 'h') ok = false;
        if ((i % 2) && s[i] != 'i') ok = false;
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int x;
   cin >> x;
   auto V = [&](int a,int b){
      return a*a*a*a*a - b*b*b*b*b == x;
   };
   f(i,-2000,2001){
      f(j,-2000,2001){
         if(V(i,j)){
            return cout << i << ' ' << j,0;
         }
      }
   }
   return 0;
}

Measured memory_bytes: 3656
#include <stdio.h>
int main(){
    double a,b,c,d,e,f,g,h;
    while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f,&g,&h)!=EOF){
     if(f<=d && b<=h){
         if(e<=c && a<=g){
             printf("YES\n");
             continue;
         }}
     printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 612
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<set>
#include<math.h>
#include<iomanip>
#include<unordered_map>
#include<algorithm>

using namespace std;


int main(void)
{
    int n;
    cin>>n;
    string s;
    unordered_map<string,long int> mp;
    long int an=0;
    
    for(int i=0;i<n;i++){
        cin>>s;
        sort(s.begin(),s.end());
        
        unordered_map<string,long int>::const_iterator itr=mp.find(s);
        
        if(itr!=mp.end()){
            an+=mp[s];
            mp[s]++;
        }
        else{
            mp[s]=1;
        }
    }
    
    
    
   
    
    cout<<an<<endl;
    
}


Measured memory_bytes: 10660
#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 998244353
#define MAX 4040
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int jc[MAX],jv[MAX],inv[MAX],n,k,tot[MAX];
int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int main()
{
    scanf("%d%d",&k,&n);
    jc[0]=jv[0]=inv[0]=inv[1]=1;
    for(int i=2;i<=n+k;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=1;i<=n+k;++i)jc[i]=1ll*jc[i-1]*i%MOD;
    for(int i=1;i<=n+k;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
    for(int i=1;i<=k;++i)tot[i+1]+=1,tot[i+k+1]-=1;
    for(int i=1;i<=k+k;++i)tot[i]+=tot[i-1];
    for(int i=2;i<=k+k;++i)
    {
        int cnt=(tot[i]+1)/2,ans=0;
        for(int j=0,d=1;j<=cnt&&j+j<=n;++j,d=MOD-d)
            add(ans,1ll*d*C(cnt,j)%MOD*C(n-2*j+k-1,k-1)%MOD);
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
// *st.find_by_order(index), 0-based
// order_of_key(e)

int mx=1e5+777;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll N,X,M; cin>>N>>X>>M;
	ll cur=X;
	map<ll,ll> A;
	map<ll,ll> idx;
	A[0]=cur;
	idx[cur]=0;
	ll period=-1, start=-1;
	for (ll i=1; i<mx; i++) {
		ll nxt=(cur*cur)%M;
		if(idx.count(nxt)) {
			period=i-idx[nxt];
			start=idx[nxt];
			break;
		}
		idx[nxt]=i;
		A[i]=nxt;
		cur=nxt;
	}

	ll sum=0;
	for (int i=0; i<period; i++)
		sum+=A[start+i];

	ll q=(N-start)/period, r=N-q*period;
	ll ret=q*sum;
	for (int i=0; i<r; i++)
		ret+=A[i];
	cout<<ret<<"\n";
	return 0;
}

Measured memory_bytes: 9836
#include "bits/stdc++.h"
#define ll long long
using namespace std;
int main(){
string s;
ll ans = 0,tmp=0;
cin>>s;
for(ll i=0;i<s.size();i++){
  if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T'){
    tmp++;
  }
  else
  tmp=0;
  if(ans<tmp){
    ans = tmp;
  }
}

printf("%ld\n",ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define rep(i, n)for(int i=0; i<n; i++)

int main(){
  string S, T;
  cin >> S >> T;

  int count = 0;
  
  rep(i, S.length())
    if(S[i] != T[i])
      count++;
  
    cout << count << endl;

  return 0;
}


Measured memory_bytes: 3916
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <limits>

using namespace std;

const auto LIM = numeric_limits<long long>::max();

long long solve(long long N, long long A, long long B, long long C, long long D)
{
	map<long long, long long> best;
	queue<long long> q;

	q.push(N);
	q.push(0);
	while (!q.empty()) {
		long long x = q.front(); q.pop();
		long long c = q.front(); q.pop();

		if (x < LIM / D && c < LIM - x / D) {
			auto x2 = 0;
			auto c2 = c + x * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}

		if (c < 0) {
			cout << "debug: x=" << x << ", c=" << c << endl;
		}
		int r2 = x % 2;
		int r3 = x % 3;
		int r5 = x % 5;

		int r2m = (2 - r2) % 2;
		int r3m = (3 - r3) % 3;
		int r5m = (5 - r5) % 5;

		//r2
		{
			auto x2 = (x - r2) / 2;
			auto c2 = c + A + r2 * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}
		{
			auto x2 = (x + r2m) / 2;
			auto c2 = c + A + r2m * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}
		//r3
		{
			auto x2 = (x - r3) / 3;
			auto c2 = c + B + r3 * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}
		{
			auto x2 = (x + r3m) / 3;
			auto c2 = c + B + r3m * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}
		//r5
		{
			auto x2 = (x - r5) / 5;
			auto c2 = c + C + r5 * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}
		{
			auto x2 = (x + r5m) / 5;
			auto c2 = c + C + r5m * D;
			if (best.count(x2) == 0 || best[x2] > c2) {
				best[x2] = c2;
				q.push(x2);
				q.push(c2);
			}
		}
	}
	return best[0];
}

int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		long long N, A, B, C, D;
		cin >> N >> A >> B >> C >> D;
		cout << solve(N, A, B, C, D) << endl;
	}
}


Measured memory_bytes: 4380
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n, m;
int ans;
vector<int> p, fa;

vector<int> getPerm(const vector<int> &a){
  vector<int> res;
  for(int i = 0; i < n; i++){
    res.push_back(i);
  }
  for(int i = 0; i < m; i++){
    swap(res[a[i]], res[a[i] + 1]);
  }
  return res;
}

int getMinStep(const vector<int> &a){
  vector<int> pre;
  int res = 0;

  for(int i = 0; i < m; i++){
    bool flg = true;

    for(int j = 0; j < pre.size(); j++){
      if(pre[j] == a[i] || pre[j] == a[i] + 1 ||
         pre[j] + 1 == a[i] || pre[j] + 1 == a[i] + 1){
        flg = false;
        break;
      }
    }

    if(!flg){
      pre.clear();
      res++;
    }
    pre.push_back(a[i]);
  }
  if(pre.size() != 0){
    res++;
  }
  return res;
}

void dfs(int idx, vector<int> va, bool *used){
  if(idx == m){
    if(getPerm(va) == p){
      ans = min(ans, getMinStep(va));
    }
    return;
  }

  va.push_back(-1);

  for(int i = 0; i < m; i++){
    if(used[i]) continue;

    used[i] = true;
    va[idx] = fa[i];
    dfs(idx + 1, va, used);
    used[i] = false;
  }
}

void solve(){
  p = getPerm(fa);

  ans = m;
  bool used[100];
  memset(used, 0, sizeof(used));
  vector<int> va;
  dfs(0, va, used);

  cout << ans << endl;
}

int main(){
  while(cin >> n >> m){
    fa.clear();
    for(int i = 0; i < m; i++){
      int x;
      cin >> x;
      fa.push_back(x - 1);
    }

    solve();
  }
}

Measured memory_bytes: 1224
object Main extends App {
  import java.util.Scanner

  val scan = new Scanner(System.in)
  val h, w = scan.nextInt
  var s = Vector(): Vector[String]
  for (i <- 0 to h - 1) {
    s :+= scan.next.trim()
  }
  var dw = Array.ofDim[Int](h, w)
  var dh = Array.ofDim[Int](w, h)
  for ( i <- 0 to (h - 1) ) {
    var count = 0
    for ( j <- 0 to (w - 1) ) {
      if (s(i)(j) == '#') {
        dw(i)(j) = 0
      }
      else if (j == 0 || s(i)(j - 1) == '#') {
        def loop1(i: Int, k: Int, w: Int, count: Int): Int = {
          if (k > w - 1 || s(i)(k) != '.') {
            return count
          }
          else {
            return loop1(i, (k + 1), w, (count + 1))
          }
        }
        count = loop1(i, j, w, 0)
        dw(i)(j) = count
      }
      else {
        dw(i)(j) = count
      }
    }
  }
  for ( j <- 0 to (w - 1) ) {
    var count = 0
    for ( i <- 0 to (h - 1) ) {
      if (s(i)(j) == '#') {
        dh(j)(i) = 0
      }
      else if (i == 0 || s(i - 1)(j) == '#') {
        def loop2(k: Int, j: Int, h: Int, count: Int): Int = {
          if (k > h - 1 || s(k)(j) != '.') {
            return count
          }
          else {
            return loop2((k + 1), j, h, (count + 1))
          }
        }
        count = loop2(i, j, h, 0)
        dh(j)(i) = count
      }
      else {
        dh(j)(i) = count
      }
    }
  }
  var max = 0
  for (i <- 0 to (h - 1)) {
    for (j <- 0 to (w - 1)) {
      var sum = dw(i)(j) + dh(j)(i)
      if (max < sum) {
        max = sum
      }
    }
  }
  println(max - 1)
}


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

int F[55];
long long dp[2][(1 << 20)];
vector< pair<int, int> > X[55];

int dfs(int i, int par, int target, int curr)
{
    if(i == target)
        return 1;
    
    int ans = 0;
    
    for(auto x : X[i])
        if(x.first != par)
        {
            int y = dfs(x.first, i, target, curr);
            ans |= y;

            if(y == 1)
                F[x.second] |= curr;
        }
    
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);

    int N;
    cin >> N;

    for(int i=1; i<=N-1; i++)
    {
        int a, b;
        cin >> a >> b;

        X[a].push_back({b, i});
        X[b].push_back({a, i});
    }

    int M;
    cin >> M;

    for(int i=0; i<M; i++)
    {
        int u, v;
        cin >> u >> v;

        dfs(u, 0, v, (1 << i));
    }

    int prev = 0, curr = 1, goal = (1 << M) - 1;
    dp[0][0] = 1;

    for(int i=1; i<=N-1; i++, swap(prev, curr))
    {
        for(int j=0; j<=goal; j++)
            dp[curr][j] = dp[prev][j];
        
        for(int j=0; j<=goal; j++)
            dp[curr][(j | F[i])] += dp[prev][j];
    }
    
    cout << dp[prev][goal] << "\n";
    return 0;
}


Measured memory_bytes: 16640
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }

fun main(args: Array<String>) {
    var (N, x) = readInts()
    val a = readInts()

    var ans = 0
    for (want in a.sorted()) {
        if (x - want < 0 || (a.max() == want && x / want < 2 && x - want > 0)) {
            break
        } else {
            x -= want
            ans++
        }
    }

    println(ans)
}

Measured memory_bytes: 37940
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,k;
	cin>>n>>k;
	int i=0,res=0;
	while(i<n-1){
		i+=k-1;
		res++;
	}
	cout<<res<<'\n';
}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

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

    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    sort(ALL(A));
    vector<ll> cum1(N);
    cum1[0] = A[0]; cum1[1] = A[1];
    for (int i = 2; i < N; i++) cum1[i] = cum1[i-2] + A[i];
    vector<ll> cum2(N);
    cum2.back() = A.back();
    for (int i = N - 2; i >= 0; i--) cum2[i] = cum2[i+1] + A[i];
    REP(q, Q) {
        int x;
        cin >> x;
        int lb = 0, ub = 1e9;
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            int i = lower_bound(ALL(A), x - m) - A.begin();
            int j = upper_bound(ALL(A), x + m) - A.begin();
            int cnt = j - i;
            if (cnt <= N - j) lb = m;
            else ub = m;
        }
        int i = lower_bound(ALL(A), x - lb) - A.begin();
        int j = upper_bound(ALL(A), x + lb) - A.begin();
        i -= (N - j) - (j - i);
        ll ans = (i > 0 ? cum1[i-1] : 0) + (j < N ? cum2[j] : 0);
        cout << ans << '\n';
    }
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define BeatMeScanf ios_base::sync_with_stdio(false);cin.tie(NULL);
#define tc(x) int x; cin >> x; while(x--)
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define mii map<int,int>
#define MOD 10000007

int main()
{
    BeatMeScanf;

    string str;
    cin >> str;

    if(str[2] == str[3] && str[4] == str[5])
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n'; 
    return 0;
}


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

int main(){
	int N , A , B , P1 , P2;
  	cin >> N >> A >> B;
  	P1 = N * A;
  	P2 = B;
  	if (P1 >= P2)
      cout << P2 << endl;
  	else
      cout << P1 << endl;
}

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

int n, base[4][13], rate[10];
string mark = "SCHD";

int getNumber(char c) {
	if (c == 'A') return 0;
	if (c == 'T') return 9;
	if (c == 'J') return 10;
	if (c == 'Q') return 11;
	if (c == 'K') return 12;
	return c - '0' - 1;
}

bool isStraight(string card) {
	int tmp[5];
	for (int i=0; i<5; ++i) tmp[i] = getNumber(card[2 * i]);
	sort(tmp, tmp + 5);
	for (int i=0; i<4; ++i) if (tmp[i]+1 != tmp[i+1]) return false;
	return true;
}

bool isFlush(string card) {
	char tmp = card[1];
	for (int i=1;i<5; ++i) if (tmp != card[2*i+1]) return false;
	return true;
}

bool isRoyal(string card) {
	set< char > num_set;
	for (int i=0; i<5; ++i) num_set.insert(card[2*i]);
	set< char > yes = {'A','T','J','Q','K'};
	return num_set == yes;
}

int getID(string card) {
	int cnt[13];
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<5; ++i) ++cnt[getNumber(card[2 * i])];
	
	int pair_num = 0, max_card = 0;
	for (int i=0; i<13; ++i) {
		if (cnt[i] == 2) ++pair_num;
		max_card = max(max_card, cnt[i]);
	}
	
	if (max_card == 2 && pair_num == 1) return 0; // one pair
	if (max_card == 2 && pair_num == 2) return 1; // two pair
	
	if (max_card == 3) {
		if (pair_num == 0) return 2; // three card
		return 5; // full house
	}
	
	bool royal = isRoyal(card), straight = isStraight(card), flush = isFlush(card);
	
	if (royal && flush) return 8;
	if (straight && flush) return 7;	
	if (straight || royal) return 3;
	if (flush) return 4;
	
	if (max_card == 4) return 6;
	
	return 9;
}

void solve() {
	for (int i=0; i<n; ++i) {
		string card;
		int sum = 0;
		for (int j=0; j<5; ++j) {
			string cj;
			cin >> cj;
			card += cj;
			sum += base[mark.find(cj[1])][getNumber(cj[0])];
		}
		cout << sum * rate[getID(card)] << endl;
	}
}

int main() {
	rate[9] = 0;
	int i = 0;
	while (cin >> n) {
		if (i > 0) cout << endl;
		for (int i=0; i<4; ++i) for (int j=0; j<13; ++j) cin >> base[i][j];
		for (int i=0; i<9; ++i) cin >> rate[i];
		solve();
		++i;
	}
}


Measured memory_bytes: 3164
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
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;}
constexpr int INF = 1e18;



signed main(){
	int N;
	cin >> N;
	vector<int>a(N);
	cin >> a;
	int ans = 0;
	FOR(i, 1, N) {
		int t = max(0ll, a[i - 1] - a[i]);
		ans += t;
		CHMAX(a[i], a[i - 1]);
	}
	out(ans);
}

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

int main() {
  long K, num;
  int N;
  cin >> K >> N;
  vector<long>A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  num = A.at(0) + K - A.at(N-1);
  for (int i = 0; i < N-1; i++) {
    if (A.at(i+1) - A.at(i) > num) {
      num = A.at(i+1) - A.at(i);
    }
  }
  cout << K - num;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vs = vector<string>;
using vl = vector<ll>;
using vvl = vector<vl>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (i64 i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define RS(x) rsort(x.begin(),x,end()))
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define fst first
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define sw swap
#define UP(x) transform(x.begin(), x.end(), x.begin(), ::toupper);
#define LOW(x) transform(x.begin(), x.end(), x.begin(), ::tolower);
#define na(a, n) rep(i, n) cin >> a[i];
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
vb d(10);
int ans(int x)
{
    while (x)
    {
        if (d[x % 10])
            return 0;
        x /= 10;
    }
    return 1;
}
//ここからメイン
int main()
{   int n,k,q,ans;
    cin >> n>>k>>q;
    vector<ll> a(n);
    rep(i,n){
     a[i]+=k;
     a[i]-=q;
    }
    rep(i,q){
        cin >> ans;
        a[ans-1]+=1;
    }
    rep(i,n){
        if(a[i]>=1){
            cout << "Yes"<<"\n";
        }else{
            cout << "No"<<"\n";
        }
    }
return 0;
}

Measured memory_bytes: 1408