akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
import java.util.Arrays;

public class Main { //HDL-style Disjoint Set
	static int N; // int_maxsize > 10000 (constrain)
	static int Q; // int_maxsize > 110000 (worstcase = 10000initial set  + 100000 new set)
	static boolean Com; //com only have two kind;
	static int V1;
	static int V2;
	static int[] S;
	static Scanner scanner;
	public static void main(String[] args){
		scanner = new Scanner(System.in);
		N = scanner.nextInt();
		S = new int[N];
		reset();
		Q = scanner.nextInt();
		FSM();
	}
	//end of main
	private static void reset(){
		Com = false;
		V1 = 0;
		V2 = 0;
		for(int i = 0; i<N; i++){
			S[i]=i;
		}
	}
	//end of reset
	private static void FSM(){
		while(Q>0){
			fetch();
			dispatch();
			Q--;
		}
	}
	//end of FSM
	private static void fetch(){
		Com = (scanner.nextInt() > 0)?true:false;
		V1 = scanner.nextInt();
		V2 = scanner.nextInt();
	}
	//end of feteh
	private static void dispatch(){
		if(Com){
			same();
		}else {
			unite();
		}
	}
	//end of dispatch
	private static void unite(){
		if(S[V1] == S[V2]){
			return;
		}else{
			merge();
		}
	}
	//end of unite
	private static void same(){
		if(S[V1] == S[V2]){
			System.out.println(1);
		}else{
			System.out.println(0);
		}
	}
	//end of same
	private static void merge(){
		V1 = S[V1];// use variable 1 to store the set code of V1
		V2 = S[V2];// use variable 2 to store the set code of V2
		for(int i = 0; i< N;i++)
		{
			if(S[i] == V1){
				S[i] = V2;
			}else{
				continue;
			}
		}
	}
}	



Measured memory_bytes: 101444
def main():
    N, K = map(int, input().split())
    *V, = map(int, input().split())

    m = min(N, K)

    ans = 0
    for left in range(m + 1):
        _r = m - left
        for right in range(_r + 1):
            rest = K - left - right
            take = V[:left] + V[N - right:]
            take.sort()
            s = 0
            for x in take:
                if rest and x < 0:
                    rest -= 1
                    continue
                s += x
            ans = max(ans, s)
    print(ans)


if __name__ == '__main__':
    main()

# 操作回数はK回以内
# x=min(K,N)個取り出す
# K-x個戻せる


Measured memory_bytes: 3064
#include <iostream>
#define add(a, b) a = (a+b < M ? a+b : a+b-M)

using std::cin;
using std::cout;
using std::endl;
typedef long long ll;
const ll M = 1e9+7;
const ll N = 2007;

int n, k;
int f[N][N];

int ans[N];
int main(){
    f[0][0] = 1;
    for (int i = 1; i < N; ++ i)
    for (int j = 1; j <= i; ++ j){
        f[i][j] = f[i-1][j];
        if (j) add(f[i][j], f[i-1][j-1]);
    }

    cin >> n >> k;
    int B = k, R = n-k;
    for (int i = 1; i <= k; ++ i){
        ll res = f[k][i]*1LL*f[n-k][i-1];
//        cout << i << " " << f[k][i] << " " << f[n-k][i-1] << " " << f[n-k][i] << " " << f[n-k][i+1] << "\n";
//        system("pause");

        res += f[k][i]*2LL*f[n-k][i];
        res += f[k][i]*1LL*f[n-k][i+1];
        res %= M;
        ans[i] = res;
    }

    for (int i = 1; i <= k; ++ i)
        cout << ans[i] << "\n";
}


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

#define ll long long

bool foo(pair < int, int > A){
	return (A.first == A.second);
}

int main(){
	int N; cin >> N;
	vector < pair < int, int > > A(N);
	for (int i = 0; i < N; i ++){
		int X, Y; cin >> X >> Y;
		A[i] = {X, Y};
	}
	bool ok = 0;
	for (int i = 2; i < N; i ++){
		if (foo(A[i]) && foo(A[i - 1]) && foo(A[i - 2])){
			ok = 1;
			break;
		}
	}
	cout << (ok ? "Yes" : "No") << "\n";
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"

using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define lin "\n"
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(0)

void solve() {
    string s;
    cin >> s;
    ll div = 0;
    ll n = 0;
    for (int i = 0; i < s.size(); ++i) {
        div += s[i] - '0';
        n = n * 10 + s[i] - '0';
    }
    if (n % div == 0) {
        cout << "Yes" << lin;
    } else {
        cout << "No" << lin;
    }
}

int main() {
    fast_io;
    int t = 1;
//    cin >> t;
//    scanf("%d",&t);
    int c = 1;
    while (t--) {
//        printf("Case %lld: ",c);
//        cout<<"Case "<<c<<": ";
        solve();
        c++;
    }
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int MAXN = 100500;

int main()
{                                                     
	ios_base::sync_with_stdio(0);
    string s;
    cin >> s;
    bool ok = false;
    for (int i = 0; i < (int)s.size() - 1; i++)
    {
        ok |= s.substr(i, 2) == "AC";
    }

    cout << (ok ? "Yes\n" : "No\n");
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define debug(n1) cout << n1 << endl;
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

const string __sep = "\n";
const ll INF = 1000000000000000001;
const int MOD = 998244353;

const int nmax = 100000;

vector<ll> memm;
ll foo(ll n, int a, int b, int c, int d) {
  if (n == 0) return 0;
  if (n == 1) return d;
  cout << " cur " << n << endl;
  if (n < nmax && memm[n]>=0) {
    //cout << " ret mem " << n << endl;
    return memm[n];
  }
  ll c1 = min(c * 1ll, 4 * n / 5 * 1ll * d) + d * (n % 5);
  ll res = c1 + foo(n / 5, a, b, c, d);
  c1 = min(c * 1ll, 4 * n / 5 * 1ll * d) + d * (5 - (n % 5));
  res = min(res, c1 + foo(1 + n / 5, a, b, c, d));

  ll b1 = min(b * 1ll, 2 * n / 3 * d) + d * (n % 3);
  res = min(res, b1 + foo(n / 3, a, b, c, d));
  b1 = min(b * 1ll, 2 * n / 3 * d) + d * (3 - (n % 3));
  res = min(res, b1 + foo(1 + n / 3, a, b, c, d));

  ll a1 = min(a * 1ll, (n >> 1) * d) + d * (n & 1);
  res = min(res, a1 + foo(n / 2, a, b, c, d));
  if (n < nmax) {
    memm[nmax] = res;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T;
  T = 1;
  //cin >> T;
  while (T-- > 0) {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    cout << max(0, (h2 - h1) * 60 + m2 - m1 - k) << endl;
  }

  return 0;
}


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

t0, x0, y0 = 0, 0, 0
judge = "Yes"

for i in range(N):
	t, x, y = list(map(int, input().split()))
	if abs(x - x0) + abs(y - y0) <= t - t0 and (abs(x - x0) + abs(y - y0) - (t - t0)) % 2 == 0:
		x0 = x
		y0 = y
		t0 = t
	else:
		judge = "No"
		break

print(judge)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
	int t, a[4];
	cin>>t;
	a[0]=t;
	a[1]=t-1;
	cin>>t;
	a[2]=t;
	a[3]=t-1;
	for(int i=0;i<3;i++)
	{
		for(int j=2;j>=i;j--)
		{
			if(a[j+1]>a[j])
			{
				t=a[j+1];
				a[j+1]=a[j];
				a[j]=t;
			}
		}
	}
	cout<<a[0]+a[1]<<endl;
	
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16

ll n;
vector<ll> v;

int main(){
  cin>>n;
  rep(i,n){
    ll a;
    cin>>a;
    v.push_back(a);
  }
  ll nmin=v[0];
  ll res=-INF;
  repl(i,1,n){
    maxch(res,v[i]-nmin);
    minch(nmin,v[i]);
  }
  cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 4876
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <tuple>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

int main ()
{
    string s; cin >> s;
    int cnt = 0;
    REP(i,s.size()) if (s[i] == 'o') cnt++;

    int lt = (15 - (int)s.size()) + cnt;
    cout << (lt < 8 ? "NO" : "YES") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define fi first
#define se second
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};

signed main(){
	int n,t,ans=1e9;
	cin>>n>>t;
	while(n--){
		int a,b;
		cin>>a>>b;
		if(b<=t)ans=min(ans,a);
	}
	if(ans==1e9)cout<<"TLE"<<endl;
	else cout<<ans<<endl;
}

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

vector<vector<int>> data(10, vector<int>(10));
vector<int> switches(10);
vector<int> ks(10);
vector<int> ps(10);
int N, M;

bool ok(){
    for(int i=0;i<M;i++){
        int sum_sw = 0;
        for(int j=0;j<ks.at(i);j++){
            sum_sw += switches.at(data.at(i).at(j)-1);
        }
        if(sum_sw%2 != ps.at(i)){
            return false;
        }
    }
    return true;
}

int search(int remaining, int i){
    if(remaining==0){
        if(ok()){
            return 1;
        }
        return 0;
    }
    int count = 0;
    for(int j=0;j<2;j++){
        switches.at(i) = j;
        count += search(remaining-1, i+1);
    }
    return count;
}

int main() {
    
    cin >> N >> M;
    int k;
    
    for(int i=0;i<M;i++){
        cin >> k;
        ks.at(i) = k;
        for(int j=0;j<k;j++){
            cin >> data.at(i).at(j);
        }
    }
    for(int i=0;i<M;i++){
        cin >> ps.at(i);
    }
    cout << search(N, 0);
    return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r\
				    :右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int n,D[MAX],H[MAX];

int Sibling(int u){
  if(T[u].p==NIL) return NIL;
  if(T[T[u].p].l!=u&&T[T[u].p].l!=NIL) return T[T[u].p].l;
  if(T[T[u].p].r!=u&&T[T[u].p].r!=NIL) return T[T[u].p].r;
  else return NIL;
}
void print(int u){
  int i,deg=0;
  printf("node %d: parent = %d, sibling = %d, ", u, T[u].p, Sibling(u));

  if(T[u].l!=NIL) deg++;
  if(T[u].r!=NIL) deg++;

  printf("degree = %d, depth = %d, height = %d, ",deg,D[u],H[u]);
  if(T[u].p==NIL) printf("root\n");
  else if(T[u].l==NIL&&T[u].r==NIL) printf("leaf\n");
  else printf("internal node\n");
}


void calcDepth(int u, int p){
  if(u==NIL) return;
  D[u] = p;
  if(T[u].l!=NIL) calcDepth(T[u].l,p+1);
  if(T[u].r!=NIL) calcDepth(T[u].r,p+1);
}
int Height(int u){
  int h1=0,h2=0;
  if(T[u].l!=NIL) h1=Height(T[u].l)+1;
  if(T[u].r!=NIL) h2=Height(T[u].r)+1;

  H[u]=(h1>h2?h1:h2);
  return H[u];
}

int main(){
  int n,i;
  int id,l,r;
  int root = 0;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = NIL;

  for(i=0; i<n; i++){
    scanf("%d %d %d",&id,&l,&r);
    T[id].l=l;
    T[id].r=r;
    if(l!=NIL) T[l].p=id;
    if(r!=NIL) T[r].p=id;
  }
  for(i = 0;i<n;i++) if(T[i].p==NIL) root=i;

  calcDepth(root, 0);
  Height(root);

  for(i=0; i<n; i++) print(i);

  return 0;
}



Measured memory_bytes: 2052
from collections import defaultdict
N=int(input())
h=[]
a=list(map(int,input().split()))
cnt_dic=defaultdict(int)
for i in range(N):
  cnt_dic[a[i]]+=1
cnt_l=sorted(cnt_dic.values(),reverse=True)
ans=len(cnt_l)
tmp=0
for i in range(ans):
  if cnt_l[i]%2==0:
    tmp+=1
if tmp%2==0:
  pass
else:
  ans-=1
print(ans)

Measured memory_bytes: 18656
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#pragma GCC optimize ("O3")
	#define NDEBUG
#endif
// #define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

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

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

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

const array<int, 4> dx = {0, 1, 0, -1};
const array<int, 4> dy = {1, 0, -1, 0};


typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);
}

int main()
{
	ios_init();
	int n, m;
	while(cin >> n >> m) {
		vector<int> a(m);
		vector<int> c(m);
		REP(i, m) {
			int aa, b;
			cin >> aa >> b;
			a[i] = aa;
			int mask = 0;
			REP(i, b) {
				int x;
				cin >> x;
				x--;
				mask |= (1 << x);
			}
			c[i] = mask;
		}
		const LL INF = 1e15;
		vector<vector<LL>> dp(m + 1, vector<LL>(1<<n, INF));
		dp[0][0] = 0;
		REP(i, m) {
			dp[i + 1] = dp[i];
			REP(mask, 1<<n) {
				chmin(dp[i + 1][mask | c[i]], dp[i][mask] + a[i]);
			}
		}
		if(dp[m][(1<<n)-1] == INF)	{
			cout << -1 << endl;
		} else {
			cout << dp[m][(1<<n)-1] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 32384
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define M 26

void run(void){
  int n;
  scanf("%d",&n);
  int min[M];
  int i;
  for(i=0;i<M;i++) min[i]=50;
  while(n--){
    char s[51];
    scanf("%s",s);
    int cnt[M]={0};
    for(i=0;s[i]!='\0';i++) cnt[s[i]-'a']++;
    for(i=0;i<M;i++) min[i]=MIN(min[i],cnt[i]);
  }
  for(i=0;i<M;i++){
    while(min[i]--) putchar('a'+i);
  }
  printf("\n");
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n; i++)
#define all(v) (v).begin(), (v).end()
#define decimal fixed << setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
const int INF = 1e9;
const LL LLINF = 1e16;
const LL mod = 1e9 + 7;

/*
!) 0-indexed
!) [a, b)に対する演算
!) m0に単位元, func(a, b)に区間をマージするときに行う二項演算を書く
*/
template<typename Monoid>
struct Segtree{
    int n;
    vector<Monoid> dat;
    Monoid m0;
    Segtree(int sz, Monoid m0) : m0(m0){
        n = 1;
        while(n < sz) n *= 2;
        dat.assign(2*n-1, m0);
    }

    Monoid func(Monoid a, Monoid b){
        // ##### WRITE HERE #####
        return max(a, b);
    }

    void set(int k, Monoid a){
        k += n-1;
        dat[k] = a;
    }
    void build() {
        for(int i = n-2; i >= 0; i--){
            dat[i] = func(dat[2*i+1], dat[2*i+2]);
        }
    }
    void update(int k, Monoid a){
        k += n-1;
        dat[k] = a;
        while(k > 0) {
            k = (k-1)/2;
            dat[k] = func(dat[k*2+1], dat[k*2+2]);
        }
    }
    Monoid query(int a, int b){
        Monoid L = m0, R = m0;
        int A = a+n-1;
        int B = b+n-1;
        while(A < B) {
            if((A&1) == 0) L = func(L, dat[A++]);
            if((B&1) == 0) R = func(dat[--B], R);
            A >>= 1;
            B >>= 1;
        }
        return func(L, R);
    }
    Monoid operator[](const int &k) const { return dat[k+n-1]; }
};



int main(){
    fastcin();
    int n;
    cin >> n;
    vector<LL> A(n);
    rep(i, n) cin >> A[i];
    // LISの長さ, 総和
    Segtree<pair<LL, LL>> dp(101010, make_pair(-LLINF, -LLINF));
    dp.update(0, make_pair(0, 0));
    rep(i, n){
        auto tmp = dp.query(0, A[i]);   // A[i]を含まない(狭義単調増加)
        dp.update(A[i], make_pair(tmp.first+1, tmp.second+A[i]));
    }
    auto ans = make_pair(0LL, -LLINF);
    rep(i, 101010){
        // cout << dp[i].first << " " << dp[i].second << endl;
        ans = max(ans, dp[i]);
    }
    cout << ans.second << endl;



}



Measured memory_bytes: 7848
#include <array>
#include <vector>
#include <iostream>
using namespace std;

const int NM_MAX = 1500;
const int WH_MAX = 1000;
const int PT_MAX = NM_MAX * WH_MAX;

// 一方の端を 0 に正規化し、
// もう一方の長さの先の点を数える
array<int, PT_MAX> nw, nh;

void normalize(const vector<int>& d, array<int, PT_MAX>& n) {
    n.fill(0);
    for (int i = 0; i < d.size(); i++) {
        int s = 0;
        for (int j = i; j >= 0; j--) {
            s += d[j];
            n[s]++;
        }
    }
}

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        vector<int> dw(n), dh(m);
        for (int& x : dw) cin >> x;
        for (int& x : dh) cin >> x;
        normalize(dw, nw);
        normalize(dh, nh);
        int cnt = 0;
        for (int i = 0; i < PT_MAX; i++) cnt += nw[i] * nh[i];
        cout << cnt << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

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

int calc_dist(pair<int, int> S, pair<int, int> C){

  return abs(S.first - C.first) + abs(S.second - C.second);

}

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

  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> student(N);
  vector<pair<int, int>> check(M);

  int a, b;
  for(int i = 0; i < N; i++){
    cin >> a >> b;
    student[i] = make_pair(a, b);
  }

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

  vector<int> ans(N);

  for(int i = 0; i < N; i++){
    int tmp_d = (1 << 30);
    int tmp_ans = 0;
    for(int j = 0; j  < M; j++){
      if(chmin(tmp_d, calc_dist(student[i], check[j]))){
        tmp_ans = j+1;
      }
    }
    ans[i] = tmp_ans;
  }

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


  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int seat(int l,int r)
{
	return r-l+1;
}
int main(void)
{
	int s=0,n,lindex,rindex;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&lindex,&rindex);
		s+=seat(lindex,rindex);
	}
	printf("%d\n",s);
}

Measured memory_bytes: 128
h,w = map(int,input().split())
c = [0]*(h+2)

r = 0

for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
    r += c[i].count("#")
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

x,y = 1,1

q = 0
ans = 1
while 1:
    if x == h and y == w:
        break
    
    s = 0
    t = 0
    if c[x+1][y] == "#":
        s = 1
    if c[x][y+1] == "#":
        t = 1
            
    if s == 1 and t == 1:
        ans = 0
        break
    elif s == 0 and t == 0:
        ans = 0
        break
    elif s == 1:
        x += 1
        q += 1
    else:
        y += 1
        q += 1
if q + 1 != r:
    ans = 0

print(["Impossible","Possible"][ans])

Measured memory_bytes: 9236
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
using namespace std;
using v = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}

int main(int argc, char *argv[]){
    int n, m; cin >> n >> m;
    int a, b, c, d;
    vector<int> A(n), B(n), C(m), D(m);
    int mx = INF, my = INF;

    rep(i, n) cin >> A[i] >> B[i];
    rep(i, m) cin >> C[i] >> D[i];

    int res, pre, cnt;
    vector<pair<int, int>> man(m);
    rep(i, n){
        rep(j, m){
            man[j] = make_pair(abs(A[i] - C[j]) + abs(B[i] - D[j]), j + 1);
        }
        sort(all(man));
        cout << man[0].second << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}


vector<ll> enum_div(ll n){//yakusu
  vector<ll> ret;
  for(ll i=1 ; i*i<=n ; ++i){
      if(n%i == 0){
        ret.push_back(i);
        if(i*i!=n)ret.push_back(n/i);
      }
  }
  return ret;
}

int main(){
  ll N;
  cin >> N;
  ll ans = enum_div(N-1).size();
  ans--;
  for(auto k:enum_div(N)){
    if(k==1)continue;
    ll n = N;
    while(n%k==0 && n)n/=k;
    if(n%k==1)ans++;
  }
  cout << ans << endl;
}


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

using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    ll H, W;
    cin >> W >> H;
    vector<ll> p(W),q(H);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    for(i=0;i<W;i++){
        cin >> p[i];
        pq.push({p[i],1});
    }
    for(i=0;i<H;i++){
        cin >> q[i];
        pq.push({q[i],0});
    }
    ll ret = 0,cnt = 0;
    H++;
    W++;
    while(H!=1 || W!=1){
        ll cost = pq.top().first;
        ll x = pq.top().second;
        pq.pop();
        if(x==0){
            ret+=cost*W;
            H--;
        }else {
            ret+=cost*H;
            W--;
        }
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 8048
#include <stdio.h>
int main(){
	long long l, n;
	long long ans;
	scanf("%lld%lld", &l, &n);
	long long x[200000];
	long long y[200000];
	long long z[200000];
	for (int i = 0; i < n; i++) {
		scanf("%lld", x + i);
		y[i] = l - x[i];
	}
	if (n % 2 == 0) {
		long long h = x[n - 1];
		ans = x[n - 1];
		for (int i = 0; i < n / 2 - 1; i++) {
			h -= x[n - 1 - i];
			h -= x[n - 2 - i];
			h += x[n - 2 - 2 * i] * 2;
			h += x[n - 3 - 2 * i] * 2;
			h += y[n - 1 - i] * 2;
			if (h > ans)ans = h;
		}
		h -= x[n / 2];
		h -= x[n / 2 - 1];
		h += x[0] * 2;
		h += y[n / 2] * 2;
		if (h > ans)ans = h;
		for (int i = 0; i < n / 2 - 1; i++) {
			h -= x[n / 2 - 1 - i];
			h -= x[n / 2 - 2 - i];
			h -= y[n - 1 - 2 * i] * 2;
			h -= y[n - 2 - 2 * i] * 2;
			h += y[n / 2 - 1 - i] * 2;
			if (h > ans)ans = h;
		}
		for (int i = 0; i < n; i++) {
			h = x[i];
			x[i] = y[i];
			y[i] = h;
		}
		for (int i = 0; i < n; i++) {
			z[n - 1 - i] = x[i];
		}
		for (int i = 0; i < n; i++) {
			x[i] = z[i];
		}
		for (int i = 0; i < n; i++) {
			z[n - 1 - i] = y[i];
		}
		for (int i = 0; i < n; i++) {
			y[i] = z[i];
		}
		h = x[n - 1];
		if (h > ans)ans = h;
		for (int i = 0; i < n / 2 - 1; i++) {
			h -= x[n - 1 - i];
			h -= x[n - 2 - i];
			h += x[n - 2 - 2 * i] * 2;
			h += x[n - 3 - 2 * i] * 2;
			h += y[n - 1 - i] * 2;
			if (h > ans)ans = h;
		}
		h -= x[n / 2];
		h -= x[n / 2 - 1];
		h += x[0] * 2;
		h += y[n / 2] * 2;
		if (h > ans)ans = h;
		for (int i = 0; i < n / 2 - 1; i++) {
			h -= x[n / 2 - 1 - i];
			h -= x[n / 2 - 2 - i];
			h -= y[n - 1 - 2 * i] * 2;
			h -= y[n - 2 - 2 * i] * 2;
			h += y[n / 2 - 1 - i] * 2;
			if (h > ans)ans = h;
		}
	}
	if (n % 2) {
		long long h = x[n - 1];
		ans = x[n - 1];
		for (int i = 0; i < n / 2; i++) {
			h -= x[n - 1 - i];
			h -= x[n - 2 - i];
			h += x[n - 2 - 2 * i] * 2;
			h += x[n - 3 - 2 * i] * 2;
			h += y[n - 1 - i] * 2;
			if (h > ans)ans = h;
		}
		h -= x[n / 2];
		h -= x[n / 2 - 1];
		h -= y[n - 1] * 2;
		h += y[n / 2] * 2;
		if (h > ans)ans = h;
		for (int i = 0; i < n / 2 - 1; i++) {
			h -= x[n / 2 - 1 - i];
			h -= x[n / 2 - 2 - i];
			h -= y[n - 2 - 2 * i] * 2;
			h -= y[n - 3 - 2 * i] * 2;
			h += y[n / 2 - 1 - i] * 2;
			if (h > ans)ans = h;
		}
		for (int i = 0; i < n; i++) {
			h = x[i];
			x[i] = y[i];
			y[i] = h;
		}
		for (int i = 0; i < n; i++) {
			z[n - 1 - i] = x[i];
		}
		for (int i = 0; i < n; i++) {
			x[i] = z[i];
		}
		for (int i = 0; i < n; i++) {
			z[n - 1 - i] = y[i];
		}
		for (int i = 0; i < n; i++) {
			y[i] = z[i];
		}
		h = x[n - 1];
		if (h > ans)ans = h;
		for (int i = 0; i < n / 2; i++) {
			h -= x[n - 1 - i];
			h -= x[n - 2 - i];
			h += x[n - 2 - 2 * i] * 2;
			h += x[n - 3 - 2 * i] * 2;
			h += y[n - 1 - i] * 2;
			if (h > ans)ans = h;
		}
		h -= x[n / 2];
		h -= x[n / 2 - 1];
		h -= y[n - 1] * 2;
		h += y[n / 2] * 2;
		if (h > ans)ans = h;
		for (int i = 0; i < n / 2 - 1; i++) {
			h -= x[n / 2 - 1 - i];
			h -= x[n / 2 - 2 - i];
			h -= y[n - 2 - 2 * i] * 2;
			h -= y[n - 3 - 2 * i] * 2;
			h += y[n / 2 - 1 - i] * 2;
			if (h > ans)ans = h;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

//tourist head

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pw(x) (1ll << (x))
////////////////////////////////////////////////////////////////////////

void read_input(){
	
}

void solve(){
	
}
int v[105];
int main(){
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		int a;
		cin>>a;
		v[a] = 1;
	}
	int res = 0;
	for(int i=0;i<105;i++){
		if (v[i]>0)
			res++;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
K = int(input())
x = 7 % K #mod(K)
if K == 1 or K == 7:
  print(1)
  exit()
ans = 1
i = 0
while i < K:
  ans += 1
  x = (x * 10 + 7) % K
  
  if x == 7 % K:
    print('-1')
    exit()
  if x == 0:
    print(ans)
    exit()
  i += 1
print('-1')

Measured memory_bytes: 9132
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i];
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion


int32_t main() {
    make(int, n, m);
    vector<string> a(n);
    for(auto& s : a){
        cin >> s;
    }
    VVI dp(n, VI(m, INT_MAX));
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if (i + 1 < n){
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (a[i][j] != a[i + 1][j]));
            }
            if (j + 1 < m){
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (a[i][j] != a[i][j + 1]));
            }
        }
    }
    cout << (dp[n - 1][m - 1] + (a[0][0] == '#')) / 2;
    return 0;
}

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

typedef pair<int,int> P;
const int INF = 1 << 28;
const int MAX_V = 1e5 * 2;
vector<int> d(MAX_V, INF);
vector<P> G;

void dijkstra (int s) {
    d[s] = 0;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, s));

    while (que.size()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i = 0; i < G.size(); i++) {
            int cost = d[v] + G[i].second;
            int to_p = v + G[i].first;
            int to_m = abs(v - G[i].first);
            if (MAX_V > to_p && d[to_p] > cost) {
                d[to_p] = cost;
                que.push(P(cost, to_p));
            }
            if (MAX_V > to_m && d[to_m] > cost) {
                d[to_m] = cost;
                que.push(P(cost, to_m));
            }
        }
    }
}

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

    for (int i = 0; i < n; i++) {
        int dis, cost;
        cin >> dis >> cost;
        P p(dis, cost);

        G.push_back(p);
    }

    dijkstra(0);
    if (d[x] != INF) cout << d[x] << endl;
    else cout << -1 << endl;
    

    return 0;
}


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

#define ll long long
#define ld long double

#define pii pair<int, int>
#define pci pair<char, int>
#define pcc pair<char, char>

#define vi vector <int>
#define vll vector<long long>
#define vld vector<long double>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>

#define vvi vector<vi>
#define vvll vector<vll>
#define vvld vector<vld>
#define vvb vector<vb>
#define vvc vector<vc>
#define vvs vector<vs>

#define vpii vector<pii>
#define vpci vector<pci>
#define vpcc vector<pcc>

#define all(v) (v).begin(), (v).end()
#define allrev(v) (v).rbegin(), (v).rend()
#define allcomp(v) (v).begin(), (v).end(), comp
#define allrevcomp(v) (v).rbegin(), (v).rend(), comp

const int MOD = 1e9 + 7;
const ld pi = 3.1415926535897932384626433832;

#define line cout<<"\n";
#define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);


void solve(int test_case){

    int n;
    string str;
    map < string, int > m;

    cin >> n;

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

    cout << m.size();
    line;
}

int main(){
    fast
    int test = 1;
    //cin>>test;
    for(int i = 1; i <= test; i++){
        solve(i);
    }
    return 0;
}


Measured memory_bytes: 19292
n, k = map(int, input().split())
list = list(map(int, input().split()))

def valid(x):
    while x:
        if (x % 10) in list:
            return 0
        x //= 10
    return 1

cur = n
while True:
    if valid(cur):
        break
    cur += 1

print(cur)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = a, i##_len = (b); i < i##_len; ++i)

int main()
{
    int N, M;
    map<int, int> D;
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        int d;
        scanf("%d", &d);
        ++D[d];
    }
    scanf("%d", &M);
    int T[M];
    for(int i = 0; i < M; ++i) {
        scanf("%d", &T[i]);
        --D[T[i]];
    }
    if(N < M) {printf("NO\n"); return 0;}
    for(int i = 0; i < M; ++i) if(D[T[i]] < 0) {
        printf("NO\n"); return 0;
    }
    printf("YES\n");
    return 0;
}

Measured memory_bytes: 10368
#include<iostream>
using namespace std;
int main(){
	
	int d;
	cin >> d;

	if (d == 25){ cout << "Christmas" << endl; }
	else if (d == 24){ cout << "Christmas Eve" << endl; }
	else if (d == 23){ cout << "Christmas Eve Eve" << endl; }
	else{ cout << "Christmas Eve Eve Eve" << endl; }

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 5;
const int M = 4e6 + 5;
const int Q = 4e6 + 5;
int cnt[M] = {};
int arr[N] = {};
int ans[Q] = {};
int tot = 0;
struct query {
    int b, l, r, id;
} ask[Q];
inline bool cmp(const query &a, const query &b) {
    return a.b == b.b ? ((a.b & 1) ? a.r > b.r : a.r < b.r) : a.b < b.b;
}
inline void add(const int &x) {
    tot += (++cnt[arr[x]] == 1);
}
inline void del(const int &x) {
    tot -= (--cnt[arr[x]] == 0);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    int B = ceil(sqrt(n));
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    int l, r;
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        ask[i] = {l / B, l, r, i};
    }
    sort(ask + 1, ask + 1 + m, cmp);
    l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        while (ask[i].l < l) add(--l);
        while (r < ask[i].r) add(++r);
        while (l < ask[i].l) del(l++);
        while (ask[i].r < r) del(r--);
        ans[ask[i].id] = tot;
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << '\n';
    return 0;
}

Measured memory_bytes: 17416
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const int MAXN=1000002;
int a,b,c,d;

int main()
{
    read(a); read(b); read(c); read(d);
    bool flag=false;
    while(a>0&&c>0)
    {
    	if(flag) a-=d;
    	else c-=b;
    	flag=!flag;
    }
    printf("%s",a<=0?"No":"Yes");
    return 0;
}

Measured memory_bytes: 3684
from collections import deque


def BFS(s):
    color=["white" for _ in range(n+1)]
    D=[0 for _ in range(n+1)]

    D[s]=0
    color[s]="gray"
    queue=deque([s])

    while len(queue)>0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                D[i]=D[u]+1
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())
M=[[] for _ in range(n+1)]
for i in range(1,n):
    M[i].append(i+1)
    M[i+1].append(i)
M[x].append(y)
M[y].append(x)

A=[0]*(n)
for i in range(1,n+1):
    for j in BFS(i)[i:]:
        A[j] +=1

for i in A[1:]:
    print(i)

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

int main()
{
  int n,m;
  cin >> n;
  for(int i=1;i<=n;i++)
    {
      m=i;
      if(m%3==0)
        {
          cout << " " << i;
          continue;
        }
      while(1)
        {
          if(m==0) break;
          if(m%10==3)
            {
              cout << " " << i;
              break;
            }
          m/=10;
          if(m) continue;
        }
    }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3120
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4,avx2,abm,fma")
#include <bits/stdc++.h>
using namespace std;
#define _USE_MATH_DEFINES

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;

const char nl = '\n';
const ll INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const ld EPS = 1e-13;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e5 + 1;
ll fact[N], invf[N];
ll ncr(int n, int r) {
	if(r<0 || r>n) return 0;
	return fact[n] * invf[r] % MOD * invf[n-r] % MOD;
}

ll power(ll n, int e) {
	ll res = 1;
	for(;e;e/=2) {
		if(e&1) res = res*n % MOD;
		n = n*n % MOD;
	}
	return res;
}

ll inverse(ll n) {
	return power(n, MOD-2);
}

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

	fact[0] = invf[0] = 1;
	for(int i=1; i<N; i++) {
		fact[i] = i*fact[i-1] % MOD;
		invf[i] = inverse(fact[i]);
	}

	int n, k;
	cin >> n >> k;
	ll ans = 0;
	for(int i=n; i>=max(1,n-k); i--) {
		ans += ncr(n,i) * ncr(n-1, i-1) % MOD;
	}
	cout << ans % MOD << nl;

	return 0;
}


Measured memory_bytes: 3328
#pragma GCC optimize("Ofast",3,"inline")
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;

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; }
void SWAP(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
void SWAP(int& a, int& b) { a ^= b; b ^= a; a ^= b; }


class D {
	vvi g;
	int n;
	vi col;
	vi from;
	deque<int> sf;
public:
	D()
	{
		cin >> n;
		g.resize(n);
		from.resize(n, -1);
		col.resize(n, -1);

		REP(i, n - 1)
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			g[a].PB(b);
			g[b].PB(a);
		}
	}

	void dfs_path(int v, int frm)
	{

		from[v] = frm;

		if (v == n - 1)
			return;

		for (int nxt : g[v])
			if (nxt != frm)
				dfs_path(nxt, v);
	}


	void dfs(int v, bool p, int frm)
	{
		col[v] = p;

		for (int nxt : g[v])
			if (nxt != frm && col[nxt] != (!p) )
				dfs(nxt, p, v);
	}

	void solve()
	{
		dfs_path(0, -1);

		int v = n - 1;
		while (v != 0)
		{
			sf.push_front(v);
			v = from[v];

		}
		sf.push_front(0);

		bool p = false;
		while (!sf.empty())
		{
			if (!p)
			{
				col[sf.front()] = p;
				sf.pop_front();
			}

			else
			{
				col[sf.back()] = p;
				sf.pop_back();
			}

			p = !p;
		}


		dfs(0, 0, -1);
		dfs(n - 1, 1, -1);

		int cnt0, cnt1;
		cnt0 = cnt1 = 0;

		REP(i, n)
		{
			if (col[i] == 0)
				++cnt0;
			else
				++cnt1;
		}

		if (cnt0 > cnt1)
			cout << "Fennec" << endl;
		else
			cout << "Snuke" << endl;
	}
};


int main()
{
	D solution;
	solution.solve();

	return 0;
}



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

#define BUF_SIZE 20

// size: specify sizeof(str)
int get_str(char *str, int size) {
    if(!fgets(str, size, stdin)) return -1;
    return 0;
}

int get_int(void) {
  int num;
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return 0;
  sscanf(line, "%d", &num);
#else
#error
#endif
  return num;
}

#define ARR_MAX 100000

static int stack[ARR_MAX];
static int pos = 0;

void push(int val) {
    stack[pos++] = val;
}

int get_size(void) { return pos; }

// arr: monotonous decrease sequence
int upper_bound(int *arr, int size, int key) {
    int low = size;
    int high = -1;
    while(high + 1 < low) {
        int mid = (low + high)/2;
        if(arr[mid] < key) {
            low = mid;
        } else { 
            high = mid;
        }
#ifdef DEBUG
        printf("judge; %d, %d<%d\n", mid, arr[mid],key);
#endif
    }
    return low;
}

int main(void) {
    int num = get_int();
    static int arr[ARR_MAX];
    int i;
    for(i = 0; i < num; i++) {
        arr[i] = get_int();
    }

    push(arr[0]);
    for(i = 1; i < num; i++) {
        int key = arr[i];
        int idx = upper_bound(stack, get_size(), key);
#ifdef DEBUG
        printf("key: %d -> idx: %d\n", key, idx);
#endif
        // push or update
        if(idx == get_size()) {
            push(key);
        } else {
            stack[idx] = key;
        }
    }
    printf("%d\n", get_size());
    return 0;
}

Measured memory_bytes: 896
n=int(input())
aa=list(map(int,input().split(" ")))
#aaa=input().split()
#aa=map(int,aaa)
#これが原因ではない

j=True
i=0
while j:
    for a in aa:
        if a%2!=0:
            j=False

    if j:
        for k in range(n):
            aa[k]=aa[k]/2

        i+=1
print(i)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<limits>

using namespace std;
int main() {
  int n;
  cin >> n;
  auto v = vector<int>(n);
  for(int i = 0; i < n; i++) {
    cin >> v.at(i);
  }
  
  int minval =  numeric_limits<int>::max();
  int minidx =  numeric_limits<int>::max();
  bool end = false;
  while(!end) {
	end = true;
    for(auto i = 0; i < n; i++) {
        auto e = v.at(i);
      if (e > 0 && e < minval) {
        minval = e;
          minidx = i;
        end = false;
      }
    }
      if(end) break;
    for(auto i = 0; i < n; i++) {
        if(minidx == i) continue;
      v.at(i) %= minval;
    }
  }
  cout << minval;
}

Measured memory_bytes: 640
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, A, B = MAP()

print("Alice" if abs(A-B)%2 == 0 else "Borys")


Measured memory_bytes: 5400
#include <stdio.h>

int main(){
	float a,b,c,d,e,f,x,y;

	while(scanf("%f %f %f %f %f %f",&a,&b,&c,&d,&e,&f) != EOF){

		y=(a*f-c*d)/(a*e-b*d);
		x=(c-b*y)/a;

		if(-0.0005<x && x<=0) x=0;
		if(-0.0005<y && y<=0) y=0;

		printf("%.3f %.3f\n",x,y);

	}
	return(0);
}

Measured memory_bytes: 648
N,W = map(int,input().split())
INF = 10**9+7
NV = (10**3)*N
dp = [[INF for j in range(NV+1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(NV+1):
        if j < v:
            dp[i][j] = min(dp[i-1][j], w)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v]+w)
ans = 0
for j in range(NV+1):
    if dp[N][j] <= W:
        ans = j
print(ans)


Measured memory_bytes: 171508
# C
N = int(input())
a_list = list(map(int, input().split()))
cnt_dict = dict()

for a in a_list:
    if a not in cnt_dict.keys():
        cnt_dict[a] = 0
    cnt_dict[a] += 1
    if a+1 not in cnt_dict.keys():
        cnt_dict[a+1] = 0
    cnt_dict[a+1] += 1
    if a-1 not in cnt_dict.keys():
        cnt_dict[a-1] = 0
    cnt_dict[a-1] += 1

print(max(list(cnt_dict.values())))

Measured memory_bytes: 18732
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int a[100100];
long long frac[100100];
const int mo = 1e9 + 7;
int main(){
	//	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for (int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	frac[0] = 1;
	for (int i = 1;i <= n; i++)
		frac[i] = (frac[i - 1] * i) % mo;
	int last = 0;
	long long ans = 1;
	long long cnt = n;
	for (int i = 1; i <= n; i++){
		if (a[i] < 2 * (i - last) - 1){
			ans = (ans * (i - last)) % mo;
			last++;
			cnt --;
		}
	}
	if (last != n) ans = (ans * frac[n - last]) % mo;
	//	cout << last << endl;
	cout << ans << endl;
	return 0;
}


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

int main() {
 int n,m;
 cin>>n>>m;
 vector< pair<ll,ll> >p,q; 
 vector<ll>v;
 for(int i=0;i<n;i++)
 {
      ll x,y;
      cin>>x>>y;
      p.push_back( make_pair(x,y) ); 
 }
 for(int i=0;i<m;i++)
 {
   int x,y;
   cin>>x>>y;
   q.push_back( make_pair(x,y) ); 

 }
 for(int i=0;i<n;i++)
 { ll ans=LONG_LONG_MAX,index=0;
      for(int j=0;j<m;j++)
      {
         ll temp=abs(p[i].first-q[j].first)+abs(p[i].second-q[j].second);
         if(temp<ans)
         {
           ans=temp;
           index=j+1;
         }
      }
      v.push_back(index);
 }
 for(int i=0;i<v.size();i++)
 {
   cout<<v[i]<<endl;
 }
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    T = list(map(int, input().split()))
    M = int(input())
    drink = []
    for _ in range(M):
        p, x = map(int, input().split())
        drink.append((p, x))

    sum_time = sum(T)
    for i in range(M):
        p, x = drink[i]
        p -= 1
        print(sum_time - (T[p] - x))



if __name__ == "__main__":
    main()


Measured memory_bytes: 62336
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=25;
inline int read(){
	char c=getchar();int t=0,f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
int n,ans,cho[maxn],alfa[maxn],vis[maxn];
void dfs(int now){
	if(now==n+1){
		int tmp=0;
		for(int i=1;i<=n;i++){
			tmp=tmp+i%cho[i];
		}
		if(ans<tmp){
			ans=tmp;
			for(int i=1;i<=n;i++)alfa[i]=cho[i];
		}
		return ;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			cho[now]=i;
			dfs(now+1);
			vis[i]=0;
		}
	}
}
signed main(){
	n=read();
	//dfs(1);
	//printf("%d\n",ans);
	//for(int i=1;i<=n;i++)
//	printf("%d ",alfa[i]);
	printf("%lld\n",(n*(n-1))/2); 
	return 0;
}


Measured memory_bytes: 256