akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
using namespace std;

long long frac_mod(long long M, long long MOD){
    if(M==1)return 1;
    return (M*frac_mod(M-1, MOD))%MOD;
}

long long gcd(long long a, long long b) {
  long long _max = a > b ? a : b;
  long long _min = a > b ? b : a;
  if (!(_max%_min)) return _min;
  else return gcd(_min, _max%_min);
}
 
long long lcm(long long a, long long b) {
  return a/gcd(a,b)*b;
}

const long long MOD = 1000000007;

void solve(long long N, long long M){
    auto frac = (frac_mod(N, MOD)*frac_mod(M, MOD))%MOD;
    if(abs(N-M)>1)cout << 0 << endl;
    else if(abs(N-M)==1) cout << frac << endl;
    else cout << (2*frac)%MOD << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    solve(N, M);
    return 0;
}


Measured memory_bytes: 3328
#include <cstdio>
#include <algorithm>
using namespace std;
#define M 10000 + 5

int n, sz, E[M][2];

void Construct(int k)
{
	for (int i = 1; i * 2 < k; i ++)
	{
		int j = k - i + 1, nxt = i + 1, _nxt = k - nxt + 1;
		sz ++, E[sz][0] = i, E[sz][1] = nxt;
		sz ++, E[sz][0] = j, E[sz][1] = nxt;
		sz ++, E[sz][0] = i, E[sz][1] = _nxt;
		sz ++, E[sz][0] = j, E[sz][1] = _nxt;
	}
}

int main()
{
	scanf("%d", &n);
	Construct(n - (n & 1));
	if (n & 1)
	{
		sz ++, E[sz][0] = 1, E[sz][1] = n;
		sz ++, E[sz][0] = n - 1, E[sz][1] = n;
		if (n > 3)
		{
			sz ++, E[sz][0] = n - 1 >> 1, E[sz][1] = n;
			sz ++, E[sz][0] = n + 1 >> 1, E[sz][1] = n;
		}
	}
	else if (n > 4)
	{
		sz ++, E[sz][0] = 1, E[sz][1] = n >> 1;
		sz ++, E[sz][0] = 1, E[sz][1] = (n >> 1) + 1;
		sz ++, E[sz][0] = n, E[sz][1] = n >> 1;
		sz ++, E[sz][0] = n, E[sz][1] = (n >> 1) + 1;
	}
	printf("%d\n", sz);
	for (int i = 1; i <= sz; i ++)
		printf("%d %d\n", E[i][0], E[i][1]);
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

#define INF 100000000000000000LL

using namespace std;

int main()
{
	int N, M, R, r[8], A, B;
	long long int C, d[200][200], dist, ans=INF;

	scanf("%d %d %d", &N, &M, &R);

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(i==j){
				d[i][j]=0;
			}else{
				d[i][j]=INF;
			}
		}
	}

	for(int i=0; i<R; i++){
		scanf("%d", &r[i]);
		r[i]--;
	}

	for(int i=0; i<M; i++){
		scanf("%d %d %lld", &A, &B, &C);
		d[A-1][B-1]=C;
		d[B-1][A-1]=C;
	}

	for(int k=0; k<N; k++){
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				if(d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
					d[j][i]=d[i][j];
				}
			}
		}
	}

	int nperm=1;
	vector<int> rv;

	for(int i=1; i<=R; i++){
		rv.push_back(r[i-1]);
		nperm=nperm*i;
	}

	for(int i=0; i<nperm; i++){
		dist=0;
		for(int j=0; j<R-1; j++){
			dist=dist+d[rv[j]][rv[j+1]];
		}
		if(ans>dist){
			ans=dist;
		}
		next_permutation(rv.begin(), rv.end());
	}

	printf("%lld\n", ans);

	return 0;

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#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--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define F first
#define S second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int Inf = 1e9;
const double EPS = 1e-9;



int main()
{
  int h, w ;
  cin >> h >> w ;
  vector<bool> gyou(h,false) ;
  vector<bool> retsu(w,false) ;
  vector<string> lit(h) ;
  
  REP(i,h){
    cin >> lit.at(i) ;
  }
  
  REP(i,h){
    REP(j,w){
      if(lit.at(i).at(j)!='.'){
        gyou.at(i) = true ;
        retsu.at(j) = true ;
      }
    }
  }
  
  REP(i,h){
    if(gyou.at(i)){
      REP(j,w){
        if(retsu.at(j)){
          cout << lit.at(i).at(j) ;
        }
      }
      cout << endl ;
    }
  }

  
  return 0 ;
}




Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    int x, y;
    int[] rep = new int[n];
    Human h;
    List<Human>[] list = new ArrayList[n];
    for(int i = 0; i < n; i++) {
      list[i] = new ArrayList<Human>();
      rep[i] = Integer.parseInt(sc.next());
      for(int j = 0; j < rep[i]; j++) {
        x = Integer.parseInt(sc.next());
        y = Integer.parseInt(sc.next());
        h = new Human(x, y);
        list[i].add(h);
      }
    }
    int ans = 0;
    boolean flag;
    for(int i = 0; i < (1 << n); i++) {
      int[] temp = new int[n];
      flag = true;
      for(int j = 0; j < n; j++) temp[j] = (1 & (i >> j));
      for(int j = 0; j < n; j++) {
        if(temp[j] == 1) {
          Human human;
          for(int k = 0; k < rep[j]; k++) {
            human = list[j].get(k);
            if(temp[human.a] == human.b) continue;
            else flag = false;
          }
        }
      }
      if(flag) {
        int t = 0;
        for(int k = 0; k < n; k++) if(temp[k] == 1) t++;
        ans = Math.max(ans, t);
      }
    }
    System.out.println(ans);
  }

  public static class Human {
    int a;
    int b;

    public Human(int x, int y) {
      this.a = x-1;
      this.b = y;
    }
  }
}


Measured memory_bytes: 25236
fun main(args: Array<String>) = println(run {
    val (s, t) = readLine()!!.split(" ")
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }
    val u = readLine()!!

    when (u) {
        s -> "${a-1} $b"
        t -> "$a ${b-1}"
        else -> "???"
    }
})

Measured memory_bytes: 37868
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long n;
	cin >> n;
	cout << 50 << endl;
	long long a = n % 50, b = n / 50;
	for (int i = 0; i < a; ++i) { cout << 100 + b - a << " "; }
	for (int i = a; i < 50; ++i) {
		cout << 49 + b - a;
		if (i != 49) { cout << " "; }
	}
	cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod (int)1000000007
#define MOD (int)10000000007
#define X 1001100011100001111ll
#define M 26388279066623ll
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for0e(i, n) for (int i = 0; i <= n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define ll long long
#define pb emplace_back
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define in(x) scanf("%d", &x)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define vi vector<int> 
#define F first
#define S second
#define pi pair<int, int>
#define ppi pair<pair<int,int> , int >
#define vii vector<pi>
#define int long long 
const int MAXN = (int)((1e5) + 100);
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a<b) return a; else return b;} 
int gcd(int a,int b) { if (a == 0) return b; return gcd(b%a, a);}
int cbrt(int x){ int lo=1,hi=min(2000000ll,x);while(hi-lo>1){int mid=(lo+hi)/2;if(mid*mid*mid<x){lo=mid;}else hi=mid;}if(hi*hi*hi<=x) return hi;else return lo;} 
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N =  (int)(1e6+5); 
// ========================================================
signed main(){
  #ifndef ONLINE_JUDGE
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  #endif
  fio;
    int n,d;
    cin>>n>>d;
    int x,y,cnt=0;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        if((x*x + y*y) <= d*d){
            cnt++;
        }
    }
    cout<<cnt<<endl;
  rr;
}



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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define MSGF(x, n) MSG(fixed << setprecision(n) << x)
#define END(x) cout << x << endl; return(0);
#define IPT(v, n) REP(i, 0, n){ cin >> v[i]; }
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<ull> vul;
typedef vector<vector<ull>> vvul;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
const static ll INF = 1LL << 30;

ll a, b, c, d, k, l, m, n, h, w, q, x, y;
string s, t;

ll ans = 0;
ll sum = 0;
ll cnt = 0;
ll cur = 0;
ll tmp = 0;
ll mini = INF;
ll maxi = 0;

double ave = 0.0;

ll mod_pow(ll base, ll power) {
    if (power == 0) return 1;
    if (power == 1) return base % MOD;
    if (power % 2 == 0) return ((mod_pow(base % MOD, (power / 2)) % MOD) * (mod_pow(base, (power / 2)) % MOD)) % MOD;
    return (base % MOD * (mod_pow(base % MOD, power - 1) % MOD)) % MOD;
}

ll mod_fact(ll number) {
    ll ret = 1;
    ll count = 1;
    while (count <= number) {
        ret *= (count % MOD);
        ret %= MOD;
        count++;
    }
    return ret % MOD;
}

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

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    ll m1, d1, m2, d2;
    cin >> m1 >> d1 >> m2 >> d2;
    if (m1 + 1 == m2) {
        MSG(1)
    } else {
        MSG(0)
    }
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define eps 0.000000001
using namespace std;
typedef long double ld;
typedef pair<int,int> p;
typedef pair<ld,p> P;

int n;
ld px[200],py[200],pz[200],vx[200],vy[200],vz[200],r[200],vr[200];

ld getlen(int a,int b,ld M){
  ld ax=px[a]+vx[a]*M,ay=py[a]+vy[a]*M,az=pz[a]+vz[a]*M,ar=r[a]-vr[a]*M;
  ld bx=px[b]+vx[b]*M,by=py[b]+vy[b]*M,bz=pz[b]+vz[b]*M,br=r[b]-vr[b]*M;
  ld dx=ax-bx,dy=ay-by,dz=az-bz;
  return sqrt(dx*dx+dy*dy+dz*dz)-(ar+br);
}

ld check(int a,int b){
  ld mt=min(r[a]/vr[a],r[b]/vr[b]);
  ld L=0,R=mt,M;
  int s=0;
  while(s++<50){
    M=(L+R)/2;
    ld len=getlen(a,b,M),len1=getlen(a,b,M+eps);
    if(len<len1||len<=0)R=M;
    else L=M;
  }
  if(R==mt||L==0||getlen(a,b,R)>0)return 1000;
  return R;
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<n;i++)
      cin>>px[i]>>py[i]>>pz[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    priority_queue<P,vector<P>,greater<P> > q;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++)
	q.push(P(check(i,j),p(i,j)));
      q.push(P(r[i]/vr[i],p(i,i)));
    }
    ld used[200]={};
    while(!q.empty()){
      ld t=q.top().first;
      int a=q.top().second.first,b=q.top().second.second;
      q.pop();
      if(used[a]||used[b])continue;
      used[a]=used[b]=t;
    }
    for(int i=0;i<n;i++)printf("%.10Lf\n",used[i]);
  }
  return 0;
}

Measured memory_bytes: 4560
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const map<S, T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;

int T, n, m;

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    while(cin >> n){
        vector<vi> w(n, vi(n));
        REP(u, n) {
            REP(v, n) {
                cin >> w[u][v];
            }
        }
        vector<ll> dp(1 << n, 0);
        dp.back() = 1;
        REP(i, n) {
            REP(b, 1 << n) {
                if (dp[b] > 0) {
                    REP(j, n) {
                        if ((b & (1 << j)) && w[i][j]) {
                            (dp[b - (1 << j)] += dp[b]) %= MOD;
                        }
                    }
                }
                dp[b] = 0;
            }
        }
        cout << dp[0] << endl;
    }
    return 0;
}


Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    char str1[6000];
    scanf("%d",&n);
    scanf("%s",str1);
    int max1=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(str1[j]==str1[i]&&str1[i-1]!=str1[j-1]){
                int l=0;
                for(int k=0;k<j-i;k++){
                    if(str1[i+k]==str1[j+k]){
                        l++;
                    }
                    else{
                        break;
                    }
                }
                if(l>max1)max1=l;
            }
        }
    }
    printf("%d\n",max1);
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
using namespace std;
using ll = long long;

int main() {
  ll N,Q,S=0,i;
  cin>>N;
  vector<ll> A(N);
  map<ll,ll> AC;
  for (i=0;i<N;i++) {
    cin>>A[i];
    if (AC.count(A[i])) {
      AC[A[i]]++;
    } else {
      AC[A[i]] = 1;
    }
    S+=A[i];
  }
  cin>>Q;
  vector<ll> B(Q), C(Q);
  for (i=0;i<Q;i++) cin>>B[i]>>C[i];
  for (i=0;i<Q;i++) {
    if(AC.count(B[i]) && AC[B[i]] > 0) {
      S+=(C[i]-B[i])*AC[B[i]];
      if (AC.count(C[i])) {
        AC[C[i]] += AC[B[i]];
      } else {
        AC[C[i]] = AC[B[i]];
      }
      AC[B[i]] = 0;
    }
    cout<<S<<endl;
  }
  return 0;
}


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

#define fl(k, n) for(int i = k; i < n; i++)
#define flr(k, n) for(int i = n - 1; i >= k; i--)
#define vi vector<int>
#define vp vector<pair<int, int>>
#define mp make_pair
#define ll long long

using namespace std;

int binary_search(vector<int> nums, int target_val){
  int begin = 0;
  int end = nums.size();
  int mid;

  while(begin <= end){
    mid = begin + (end - begin) / 2;
    if(nums[mid] == target_val)
      return mid;
    else if(nums[mid] <= target_val && nums[mid + 1] > target_val)
      return mid;
    else if(nums[mid] > target_val)
      end = mid - 1;
    else
      begin = mid + 1;
  }

  if(begin == 0)
    return -1;
  else 
    return nums.size();
}

void dfs(int curr, vi &in_degree, vector<vi> &edges, vi &dist, vector<bool> &visited){
  visited[curr] = true;
  for(int outv: edges[curr]){
    dist[outv] = max(dist[outv], dist[curr] + 1);
    in_degree[outv]--;
    if(in_degree[outv] == 0){
      dfs(outv, in_degree, edges, dist, visited);
    }
  }
}

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

  int n, m;
  cin >> n >> m;

  vector<vi> edges(n);
  vi in_degree(n);
  vi dist(n);
  vector<bool> visited(n);
  fl(0, m){
    int inv, outv;
    cin >> inv >> outv;
    inv--;
    outv--;
    edges[inv].push_back(outv);
    in_degree[outv]++;
  }

  fl(0, n){
    if(!visited[i] && in_degree[i] == 0){
      dfs(i, in_degree, edges, dist, visited);
    }
  }

  int max_path = dist[0];
  fl(0, n)
    max_path = max(max_path, dist[i]);

  cout << max_path << "\n";

}

Measured memory_bytes: 17100
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main() {
  int N; cin >> N;
  vector<P> r(N);
  for (int i = 0; i < N; ++i) {
    int a, b; cin >> a >> b;
    r[i] = {a, b};
  }
  vector<P> b(N);
  for (int i = 0; i < N; ++i) {
    int c, d; cin >> c >> d;
    b[i] = {c, d};
  }
  sort(begin(r), end(r));
  sort(begin(b), end(b));
  int ans = 0;
  for (int i = N - 1; i >= 0; --i) {
    int m_idx = N;
    for (int j = 0; j < N; ++j) {
      if (r[i].first > b[j].first || r[i].second > b[j].second) continue;
      if (m_idx == N || b[j].second < b[m_idx].second) m_idx = j;
    }
    if (m_idx != N) {
      ++ans;
      b.erase(begin(b) + m_idx);
      --N;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  i64 n;
  cin >> n;
  string s;
  cin >> s;
  char c = s.back();
  set<string> st;
  st.insert(s);
  for(int i = 1;i < n;i++) {
    string t;
    cin >> t;
    if(c == t.front()) {
    }
    else {
      cout << "No" << endl;
      return 0;
    }
    c = t.back();
    if(st.count(t)) {
      cout << "No" << endl;
      return 0;
    }
    st.insert(t);
  }
  cout << "Yes" << endl;
}


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

using namespace std;

typedef long long ll;

// combination
// O(n)

const ll MOD = 1e9 + 7;
const ll max_n = 202020;
ll fact[max_n];
bool fact_init = false;

ll pow(ll a, ll b){
	if(b == 0) return 1;
	if(b % 2 == 1) return a * pow(a, b - 1) % MOD;

	ll d = pow(a, b / 2) % MOD;
	return d * d % MOD;
}

ll comb(ll n, ll k){
	if(!fact_init){
		fact[0] = 1;
		fact[1] = 1;

		for(ll i = 2; i < max_n; i++){
			fact[i] = fact[i-1] * i;
			fact[i] %= MOD;
		}

		fact_init = true;
	}

	ll ret = fact[n];
	ret *= pow(fact[k],MOD-2);
	ret %= MOD;
	ret *= pow(fact[n-k],MOD-2);
	ret %= MOD;
	return ret;

	// X^(-1) = X^(p-2) (mod p) (Fermat's little theorem)
}


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

	ll n, k;
	cin >> n >> k;

	ll ans = 1;
	rep(i, min(n, k+1) - 1){
		ll t = comb(n, i + 1);
		t *= comb(n - 1, i + 1);
		t %= MOD;

		ans += t;
		ans %= MOD;
	}

	cout << ans << endl;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.StringTokenizer;

public class Main  implements Runnable {

    public static void main(String[] args) {
        Thread tt = new Thread(null, new Main(), "", 256 * 1024 * 1024);
        tt.start();
    }

    public void run() {
    	FastScanner sc = new FastScanner(System.in);
    	//int[] ar = new int[3];
    	//ar[0]=Integer.parseInt(sc.next());
    	//Arrays.parallelSort(ar);
		int n = Integer.parseInt(sc.next());

		//long a = Long.parseLong(sc.next());
		//String s = sc.next();
		//String str = sc.next();
		//char c[] = str.toCharArray();
		//char a[][] = new char[n];
		//ArrayList<Str_4> lists = new ArrayList<Str_4>();
		//lists = new ArrayList;
		int[] a = new int[n];
		double ans = 0; 
		PrintWriter out = new PrintWriter(System.out);
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sc.next());
		}
		double ans_tmp = 0;
		for (int i = 0; i < n; i++) {
			ans_tmp += (double)1/(double)a[i];
		}
		ans = 1/ans_tmp;
			
		out.println(ans);
		out.flush();
    }
    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
        public FastScanner(String in) {
        	StringReader sr = new StringReader(in);
            reader = new BufferedReader(new BufferedReader(sr));
            tokenizer = null;
        }
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long nextInt() {
            return Integer.parseInt(next());
        }

    }
}

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

int main(){
  int n,m;
  cin>>n>>m;
  int a[m+1];
  for(int i=0;i<=m;i++){
    a[i]=0;
  }
  for(int i=0;i<n;i++){
    int b;
    cin>>b;
    for(int j=0;j<b;j++){
      int c;
      cin>>c;
      a[c]++;
      //cout<<a[c]<<" ";
    }
  }
  int kotae=0;
  for(int i=1;i<=m;i++){
    if(a[i]==n)kotae++;
  }
  cout<<kotae<<endl;
  return 0;
}
    




Measured memory_bytes: 3544
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	num, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return num
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	k := nextInt()
	a := nextInt()
	b := nextInt()

	ans := func() string {
		for i := a; i <= b; i++ {
			if i%k == 0 {
				return "OK"
			}
		}
		return "NG"
	}()

	fmt.Println(ans)

}


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

using namespace std;

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

    int n, m;
    cin >> n >> m;
    vector<int> diff;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        sum += x;
        while (x) {
            diff.push_back(x - (x >> 1));
            x >>= 1;
        }
    }
    sort(diff.rbegin(), diff.rend());
    cout << sum - accumulate(diff.begin(), diff.begin() + min(m, (int)diff.size()), 0ll);

    return 0;
}

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

int main(){
    int sx,sy,tx,ty;
    int i;
    cin >> sx >> sy >> tx >> ty;
    for(i=0;i<(tx-sx);i++)
        cout << "R";
    for(i=0;i<(ty-sy);i++)
        cout << "U";
    for(i=0;i<(tx-sx);i++) 
        cout << "L";
    for(i=0;i<(ty-sy);i++)
        cout << "D";

    cout << "D";
    for(i=0;i<(tx-sx+1);i++)
        cout << "R";
    for(i=0;i<(ty-sy+1);i++)
        cout << "U";
    cout << "L";

    cout << "U";
    for(i=0;i<(tx-sx+1);i++) 
        cout << "L";
    for(i=0;i<(ty-sy+1);i++)
        cout << "D";
    cout << "R" << endl;

  return 0;
}

Measured memory_bytes: 256
package main
 
import(
  "fmt"
)
 
func main() {
  var a, b, c int
  fmt.Scan(&a, &b, &c)
  capa := a - b
  if capa >= c {
    fmt.Println(0)
  } else {
    fmt.Println(c- capa )
  }
}

Measured memory_bytes: 512
#include <cstdio>

using namespace std;

#define MAX 100
int n, AM[MAX][MAX];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int u, k;
        scanf("%d%d", &u, &k);
        for (int j = 1; j <= k; ++j) {
            int vi;
            scanf("%d", &vi);
            AM[i][vi - 1] = 1;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j)
                printf(" ");
            printf("%d", AM[i][j]);
        }
        printf("\n");
    }
}

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

int main() {

  int A, B, a, b, c, d, e = 0;
  int i;
  int count = 0;
  cin >> A;
  cin >> B;
  for (i=A; i <= B; i++) {
    a = i/10000;
    b = (i%10000)/1000;
    c = (i%1000)/100;
    d = (i%100)/10;
    e = (i%10);
      if(a == e && b  ==d ){
        count += 1;
      }
    
  }
  cout << count << endl;
  
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll MOD = 1000000007;
ll INF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "YES" << endl;}
void no(){ cout << "NO" << endl;}

//-----------------------------------------

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


  ll n;
  cin >> n;
  vll a(n);
  REP(i,n) cin >> a[i];
  sort(ALL(a));
  if(a[0] == 0){
    cout << 0 << endl;
    return 0;
  }

  ll ans = 1;
  for(ll i = 0; i < n; i++){
    if(ans > INF / a[i]){
      cout << -1 << endl;
      return 0;
    }
    ans *= a[i];
    if(ans > INF){
      cout << -1 << endl;
      return 0;
    }
  }

  cout << ans << endl;



  return 0;
}



Measured memory_bytes: 3972
import sys

N, K = (int(i) for i in raw_input().split())
ab_list = [[int(i) for i in raw_input().split()] for i in range(N)]
ab_list = sorted(ab_list, key=lambda ab: ab[0])

num = 0
for i in range(N):
    num += ab_list[i][1]
    if num >= K:
        print ab_list[i][0]
        break

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

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

typedef long long llong;
typedef pair<int, int> pii;

int dist(int a, int b){
	return (a - b) * (a - b);
}


void solve(){

	int n;
	cin >> n;
	vector<int> arr(n);
		
	int total_cost = 0;

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

	int target = (int)round((double)total_cost / n);
	int ans = 0;

	for(int val : arr){
		ans += dist(val, target);
	}

	cout << ans;

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();

	return 0;
}

Measured memory_bytes: 512
//
// Created by kuroneko on 2019-09-01.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

#define INF 1000000000000009LL
#define MOD 1000000007LL

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight):src(src), dst(dst), weight(weight) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

int main() {
    ll N; cin >> N;
    cout << (N-1) * N / ll(2)<< endl;
}


Measured memory_bytes: 888
// copied by Nurstan Duisengaliev
// skatal
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
 
#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define mp make_pair
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define boost() ios_base::sync_with_stdio(0), cin.tie(0)
#define sz(x) (int)x.size()
 
using namespace std;
//using namespace __gnu_pbds;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;                         
 
const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
int a[N];
void solve () {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	int f = 0;
	for (int i = 2; i <= n; i ++) {
		f ^= a[i];
	}             
	cout << f << " ";
	for (int i = 2; i <= n; i ++) {
		cout << ((f ^ a[i]) ^ a[1]);
		cout << " ";
	}
}   	

 
main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	boost ();
	int TT = 1;
//    cin >> TT;
	while (TT --) {
		solve ();
	}
	return 0;	
}

Measured memory_bytes: 4440
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long long N, S;
    cin >> N >> S;

    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    const long long mod = 998244353;

    vector<vector<long long>> dp(N+1, vector<long long>(S+1, 0));
    dp[0][0] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= S; j++) {
            dp[i + 1][j] += 2 * dp[i][j];
            dp[i + 1][j] %= mod;
            if (j + A[i] <= S) {
                dp[i + 1][j + A[i]] += dp[i][j];
                dp[i + 1][j + A[i]] %= mod;
            }
        }
    }

    cout << dp[N][S] << endl;

}

Measured memory_bytes: 73532
n = int(input())
cordinates = [list(map(float, input().split())) for _ in range(n)]

for cod in cordinates:
    x1, y1, x2, y2, x3, y3, x4, y4 = cod
    if abs((x2-x1) * (y4-y3) - (y2-y1) * (x4-x3)) < 1e-10:
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 5616
# dp[i][j]: i+1個の品物から価値がj以上になるように選んだときの重量の最小値
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    tmp = list(map(int, input().split()))
    w.append(tmp[0])
    v.append(tmp[1])
V = sum(v)
dp = [[float("inf") for _ in range(V+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
        else:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# dp[N][j]がW以下であるときのｊの最大値
ans = []
for j in range(V+1):
    if dp[N][j] <= W:
        ans.append(j)
print(max(ans))

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

#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif

//{{{
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
// clang-format off
#define debug(args...) {vector<string> _v = split(#args, ','); err(_v.begin(), args); cerr<<endl;}
vector<string> split(const string& s, char c) {vector<string> v; stringstream ss(s); string x; while
(getline(ss, x, c)) v.push_back(x); return v;} void err(vector<string>::iterator) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args)
{cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; err(++it, args...);}
// clang-format on
//}}}

const int N = 1e5 + 10;
struct E
{
    int v, next;
} edge[N << 1];
int head[N], e;
void addedge(int u, int v)
{
    edge[e].v = v;
    edge[e].next = head[u];
    head[u] = e++;
}

int n;
int mod;

LL dp1[N], dpf[N], dp2[N];

LL dfs1(int u, int f)
{
    LL ret = 1;
    for (int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].v;
        if (v == f) continue;
        LL val = dfs1(v, u);
        ret = ret * (1 + val) % mod;
    }
    return dp1[u] = ret;
}

LL pre[N], suf[N], val[N];
int idx[N];

void dfs2(int u, int f)
{
    int cnt = 0;
    for (int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].v;
        if (v == f) continue;
        ++cnt;
        idx[cnt] = v;
        val[cnt] = dp1[v];
    }

    if (cnt == 0) return;

    // assert(cnt >= 0);
    // assert(cnt <= n - 1);

    pre[0] = 1;
    for (int i = 1; i <= cnt; i++) pre[i] = pre[i - 1] * (1 + val[i]) % mod;
    suf[cnt + 1] = 1;
    for (int i = cnt; i >= 1; i--) suf[i] = suf[i + 1] * (1 + val[i]) % mod;

    for (int i = 1; i <= cnt; i++)
    {
        int p = idx[i];
        // assert(p >= 1);
        // assert(p <= n);

        LL v1 = pre[i - 1];
        LL v2 = suf[i + 1];
        LL v = v1 * v2 % mod;  // 同级

        dpf[p] = (dpf[u] * v + 1) % mod;
        dp2[p] = dpf[p] * dp1[p] % mod;
    }

    for (int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].v;
        if (v == f) continue;
        dfs2(v, u);
    }
}

int main()
{
#ifdef LOCAL
    freopen("in2", "r", stdin);
// freopen("out", "w", stdout);
#endif

    while (~scanf("%d%d", &n, &mod))
    {
        clr(head, -1), e = 0;
        int u, v;
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }

        int root = rand() % n + 1;
        dfs1(root, -1);
        dp2[root] = dp1[root];
        dpf[root] = 1;

        dfs2(root, -1);

        for (int i = 1; i <= n; i++) printf("%lld\n", dp2[i]);
    }

    return 0;
}


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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> p(m);
	vector<string> s(m);
	rep(i, m) {
		cin >> p[i] >> s[i];
		p[i]--;
	}
	vector<bool> jud(n);
	map<int, int> mp;
	rep(i, m) {
		if (jud[p[i]]) continue;
		if (s[i] == "WA") mp[p[i]]++;
		else jud[p[i]] = true;
	}
	int ans = 0;
	int cnt = 0;
	rep(i, n) if (jud[i]) ans++;
	for (auto& c : mp) if (jud[c.first]) cnt += c.second;
	printf("%d %d", ans, cnt);
	return 0;
}


Measured memory_bytes: 8960
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)





int main() {
    int n;
    scanf("%d", &n);
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++){
        scanf("%d %d", &x[i], &y[i]);
    }
    double theta = 0.0, lim = 2 * acos(-1), MAX = 2e5, d = lim / MAX;
    vector<double> ans(n);
    while(theta < lim){
        double mx = -INF;
        ll max_i = 0;
        REP(i, n){
            double tmp = x[i] * sin(theta) + y[i] * cos(theta);
            if(mx < tmp){
                mx = tmp;
                max_i = i;
            }
        }
        ans[max_i] += 1.0 / MAX;
        theta += d;
    }
    REP(i, n){
        printf("%.7lf\n", ans[i]);
    }
}


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

left = 0
right = sum(A)
for i in range(N):
    left_new = left + A[i]
    right_new = right - A[i]
    if left_new == right_new:
        print(0)
        exit()
    elif left_new > right_new:
        print(min(left_new - right_new, right - left))
        exit()
    left, right = left_new, right_new


Measured memory_bytes: 88784
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define hell1 1e9+7
#define hell2 1e9+9
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ll long long
#define ld long double 
#define no_of_digits(n) floor(log10(n)) + 1
#define see(x) cout << (#x) << " is " << (x) << endl
#define INF 1e9

using namespace std;

ll mult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
ll multbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=multbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;
}
ll add(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
ll sub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
int isPowerof2(ll x) { return (x && !(x & x-1)); } 
ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; } 

// max({a, b, c, d})

vector<ll>adj[200005];
ll update[200005];
ll ans[200005];

void dfs(ll s, ll cur_sum, ll parent)
{
    ans[s] = update[s] + cur_sum;
    for(auto u : adj[s])
    {
        if(u == parent) continue;
        dfs(u, update[s]+cur_sum, s);
    }
}

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

    map<string, int>mp;    
    string s[n];
    for(int i=0;i<n;i++)
    {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());

        mp[s[i]]++;
    }

    map<string, int>::iterator itr;
    ll ans=0;
    for(itr = mp.begin(); itr != mp.end(); ++itr)
    {
        ll x = itr -> se;

        ans += (x*(x-1))/2;
        // cout << itr -> fi << " " << itr -> se << "\n";
    }

    cout << ans << "\n";
}




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

int n;
const int N = 1e5+7;
int A[N];

LL solve() {
    stack<int> S;
    LL sum = 0, ans = 0;
    for( int i = 1; i <= n; ++i ) {
        while( !S.empty() && A[S.top()] < A[i] ) {
            int r = S.top(); S.pop();
            int l;
            if( S.empty() ) {
                l = 1;
            } else {
                l = S.top() + 1;
            }
            sum -= 1LL * ( r-l+1 ) * A[r];
        }
        int l;
        if( S.empty() ) {
            l = 1;
        } else {
            l = S.top() + 1;
        }
        sum += 1LL * ( i-l+1 ) * A[i];
        ans += sum;
        S.push( i );
    }
    return ans;
}

int main() {
    int n;
    cin>>n;
    int T, A;
    cin>>T>>A;
    double bb = 0x3f3f3f3f3f3f3f3f;
    int ans;
    for( int i = 0; i < n; ++i ) {
        int tmp;
        cin>>tmp;
        double res = T - tmp * 0.006;
        double aa = fabs( A - res );
        if( aa < bb ) {
            bb = aa;
            ans = i+1;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(), v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 1;
vector<int> g[N];
void solve(){
    int n, x, m;
    cin >> n >> x >> m;
    vector<int> dp;
    dp.push_back(x);
    if(n <= m){
        int sum = x;
        for(int i = 2; i <= n; i++){
            int val =(dp[(int)dp.size() - 1] * dp[(int)dp.size() - 1]) % m;
            sum += val;
            dp.push_back(val);
        }
        cout << sum << '\n';
        return;
    }
    vector<int> vis(m);
    int sum = x, idx1 = 0, idx2 = 0;
    vis[x] = 1;
    for(int i = 2; i <= n; i++){
        int val =(dp[(int)dp.size() - 1] * dp[(int)dp.size() - 1]) % m;
        if(!val){
            cout << sum << '\n';
            return;
        }
        if(vis[val]){
            idx1 = vis[val];
            idx2 = i - 1;
            break;
        }
        dp.push_back(val);
        vis[val] = i;
        sum += val;
    }
    int ans = 0;
    for(int i = 1; i < idx1; i++){
        ans += dp[i - 1];
    }
    n -= idx1 - 1;
    int len = idx2 - idx1 + 1;
    int curr = 0;
    for(int i = idx1; i <= idx1 + len; i++){
        curr += dp[i - 1];
    }
    for(int i = idx1; i < idx1 + (n % len); i++){
        ans += dp[i - 1];
    }
    cout << ans + curr * (n / len) << '\n';
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        solve();
    }
}

Measured memory_bytes: 28008
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(char &c){
  int i;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i;
  int sz = 0;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = my_getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
char S[22];
int main(){
  rd(S);
  S[3] = '\0';
  wt_L(S);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// char S[22];
// {
//   rd(S);
//   S[3] = '\0';
//   wt(S);
// }


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }
//ミョ(-ω- ?)
int main() {
    int a,b,c;
    cin >> c >> a >> b;
    if(abs(a - c) < abs(b - c))cout << "A\n";
    else cout << "B\n";
    return 0;
}

Measured memory_bytes: 3580
n=int(input())
ans=0
q=n//15
for i in range(q):
  ans+=1+15*i
  ans+=2+15*i
  ans+=4+15*i
  ans+=7+15*i
  ans+=8+15*i
  ans+=11+15*i
  ans+=13+15*i
  ans+=14+15*i
p=n%15
a=p//3
b=p//5
for i in range(1,p+1):
  ans+=i+15*q
for i in range(1,a+1):
  ans-=3*i+15*q
for i in range(1,b+1):
  ans-=5*i+15*q
print(ans)

Measured memory_bytes: 9216
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <math.h>
#include <assert.h>
#include <set>
#include <map>
#include <bitset>
#include <ctime>
#include <time.h>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <stack>
#include <ctype.h>
#include <numeric>
#include <sstream>
#include <unistd.h>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <random>
#include <chrono>
#include <iomanip>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define debug(name) DEBUG(#name, (name))
template<typename T>
void DEBUG(string label, T value) {
    cerr << "[" << label << " = " << value << "]\n";
}

vector<int> blue;
vector<int> red;
vector<int> colourless;
int A, B, C;

void solve(){
    int x, y;
    cin >> x >> y >> A >> B >> C;
    red.resize(A);
    blue.resize(B);
    colourless.resize(C);
    for(int i = 0; i < A; ++i){
        cin >> red[i];
    }
    for(int i = 0; i < B; ++i){
        cin >> blue[i];
    }

    for(int i = 0; i < C; ++i){
        cin >> colourless[i];
    }
    sort(red.rbegin(), red.rend());
    sort(blue.rbegin(), blue.rend());
    for(int i = 0; i < x; ++i){
        colourless.push_back(red[i]);
    }
    for(int i = 0; i < y; ++i){
        colourless.push_back(blue[i]);
    }
    sort(colourless.rbegin(), colourless.rend());
    cout << accumulate(colourless.begin(), colourless.begin() + x + y, 0LL) << endl;
}
int main(int argv, char **argc){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}


Measured memory_bytes: 5632
S = input()
mlist = ['01', '02', '03', '04', '05', '06', '07', '08', '09', '10', '11', '12']
if S[0:2] in mlist and S[2:] in mlist:
    print('AMBIGUOUS')
elif S[0:2] in mlist:
    print('MMYY')
elif S[2:] in mlist:
    print('YYMM')
else:
    print('NA')

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

using namespace std;

int main() {
    size_t n, k;
    cin >> n >> k;
    vector<long long> h(n);
    for(size_t i = 0; i < n; i++) cin >> h.at(i);
    if (n < k) 
    {
        cout << 0 << endl;
        return 0;
    }
    sort(h.begin(), h.end());
    long long ans = 0;
    for (size_t i = 0; i < n - k; i++) ans += h.at(i);
    cout << ans << endl;
    return 0;
}

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

typedef vector<double> vec;
typedef vector<vec> mat;
const double EPS=1E-9;

vec gauss_jordan(const mat& A,const vec& b){
  int n=A.size();
  mat B(n,vec(n+1));
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)B[i][j]=A[i][j];
  for(int i=0;i<n;i++)B[i][n]=b[i];
  for(int i=0;i<n;i++){
    int pivot=i;
    for(int j=i;j<n;j++)if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;
    swap(B[i],B[pivot]);
    if(abs(B[i][i])<EPS)return vec();
    for(int j=i+1;j<=n;j++)B[i][j]/=B[i][i];
    for(int j=0;j<n;j++)if(i!=j)for(int k=i+1;k<=n;k++)B[j][k]-=B[j][i]*B[i][k];
  }
  vec x(n);
  for(int i=0;i<n;i++)x[i]=B[i][n];
  return x;
}

int main(){
  int n,s,t,q[100],a[100][100],d[100][100];
  while(cin>>n>>s>>t,n){
    vector<int> v[2][100];
    s--,t--;
    for(int i=0;i<n;i++)cin>>q[i];
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++){
	cin>>a[i][j];
	if(!a[i][j])a[i][j]=d[i][j]=1e9;
	else v[0][i].push_back(j),d[i][j]=a[i][j];
      }
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	for(int k=0;k<n;k++)
	  d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
    if(d[s][t]==1e9){cout<<"impossible"<<endl;return 0;}
    mat A(n,vec(n));
    vec b(n);
    for(int i=0;i<n;i++){
      if(d[i][t]==a[i][t])v[1][i].push_back(t);
      for(int j=0;j<n;j++)
	if(d[i][t]==a[i][j]+d[j][t])v[1][i].push_back(j);
      }
    for(int i=0;i<n;i++){
      int sz=v[q[i]][i].size();
      if(i==t){A[i][i]=1;continue;}
      double cnt=0;
      for(int j=0;j<sz;j++){
	int p=v[q[i]][i][j];
	A[i][p]=1.0/sz;
	cnt+=a[i][p];
      }
      A[i][i]-=1;
      b[i]-=cnt/sz;
    }
    vec res=gauss_jordan(A,b);
    printf("%.9lf\n",res[s]);
  }
  return 0;
}


Measured memory_bytes: 3424
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> Paint;
int main(){
  int n,m;cin>>n>>m;
  vector<Paint> q;
  for(int i = 0; n > i; i++){
    int te,mp;cin>>te>>mp;
    q.push_back(make_pair(te,mp));
  }
  sort(q.begin(),q.end());
  long long nw = 0;
  long long ret = 0;
  for(int i = 0; n >i; i++){
    if(q[i].second+nw <= m){
      ret += (long long)q[i].second*q[i].first;
      nw+=q[i].second;
    }else{
      ret += (long long)(m-nw)*q[i].first;
      nw += m-nw;
    }
    if(nw == m)break;
  }
  cout << ret << endl;
}

Measured memory_bytes: 1400