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

public class Main {
	public static void main (String[] args) {
//------------------------------------------------------------
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int s= sc.nextInt();
		int count =0;
		for (int x =0; x <= k ; x++){
			for (int y = 0; y<=k; y++) {
				int z =s-x-y;
				if(z>=0&&z<=k&&x+y+z==s) {
					count ++;
				}
			}
		}
		System.out.println(count);

//------------------------------------------------------------
	}
}

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

typedef long long ll;
typedef pair<int, int> ii;

const int N = 200005;
ii p[N];
const int MOD = 998244353;
int dp[N][2];
int f[N];

int n, x, d;

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

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x >> d;
        p[i] = ii(x, x + d);
    }
    sort(p, p + n);

    dp[n - 1][0] = 1;
    dp[n - 1][1] = 1;
    stack<int> s;
    f[n - 1] = n - 1;
    s.push(n - 1);
    for (int i = n - 2; i >= 0; --i) {
        f[i] = i;
        while (s.size() && p[i].second > p[s.top()].first) {
            f[i] = max(f[i], f[s.top()]);
            s.pop();
        }
        s.push(i);

        dp[i][0] = (dp[i + 1][0] + dp[i + 1][1]) % MOD;
        if (f[i] == n - 1)
            dp[i][1] = 1;
        else
            dp[i][1] = (dp[f[i] + 1][0] + dp[f[i] + 1][1]) % MOD;
    }

    cout << (dp[0][0] + dp[0][1]) % MOD << endl;

    return 0;
}



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

int main(){
    int a;
    string s;
    cin >>a>>s;
    if(a>=3200) cout << s << endl;
    else cout << "red" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;

typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#define	GE() printf(">----------\n")
#define	IN() freopen("in.txt","r",stdin)
#define	OUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;

LL data[maxn];
int n;
map<LL, LL> cnt;

int main()
{
    while(~scanf("%d", &n)){
        cnt.clear();
        for(int i=0;i<n;i++){
            scanf("%lld", &data[i]);
            cnt[data[i]]++;
        }
        sort(data, data+n);
        LL a=0, b=0;
        for(int i=n-1;i>=0;i--){
            if(cnt[data[i]]>=4){
                if(a)b=data[i];
                else a=b=data[i];
                break;
            }
            if(!a&&cnt[data[i]]>=2){
                a=data[i];
                cnt[a]=0;
                continue;
            }
            if(!b&&cnt[data[i]]>=2){
                b=data[i];
                break;
            }
        }
        printf("%lld\n", a*b);
    }
    return 0;
}


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

int main(){
  int input,i,S[3];
  cin >> input;
  for(i=0;i<3;i++){
    S[i]=input%60;
    input=input/60;
  }
  cout << S[2] << ":" << S[1] << ":" << S[0] << endl;
}

Measured memory_bytes: 3084
#include <iostream>

using namespace std;
typedef long long ll;

struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

const ll MAXN = 50;
const ll MAXK = 2500;
mint dp[MAXN][MAXN + 1][MAXK + 1];

int main(){
    ll n, k;
    cin >> n >> k;

    dp[0][1][2] = 1;
    dp[0][0][0] = 1;

    for(ll i = 0; i < n - 1; ++i){
        for(ll j = 0; j <= (i + 1); ++j){
            for(ll m = 0; m <= k; ++m){
                // a
                if(m + 2 * j <= MAXK){
                    dp[i + 1][j][m + 2 * j] += dp[i][j][m];
                }

                // b
                if(m + 2 * (j + 1) <= MAXK){
                    dp[i + 1][j + 1][m + 2 * (j + 1)] += dp[i][j][m];
                }

                // c and c'
                if(m + 2 * j <= MAXK){
                    dp[i + 1][j][m + 2 * j] += mint(2 * j) * dp[i][j][m];
                }

                // d
                if(j > 0 && m + 2 * (j - 1) <= MAXK){
                    dp[i + 1][j - 1][m + 2 * (j - 1)] += mint(j * j) * dp[i][j][m];
                }
            }
        }
    }

    // for(ll i = 0; i < n; ++i){
    //     for(ll j = 0; j <= (i + 1); ++j){
    //         for(ll m = 0; m <= k; ++m){
    //             cout << i + 1 << ' ' << j << ' ' << m << ' ' << dp[i][j][m].v << endl;
    //         }
    //     }
    // }

    cout << dp[n - 1][0][k].v << endl;
    return 0;
}


Measured memory_bytes: 50176
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int origin[3][3];
bool math[3][3];
 
void check(int a) {
  rep(i, 3) {
    rep(j, 3) {
      if(origin[i][j] == a) {
        math[i][j] = true;
        return;
      } 
    }
  }
}
 
bool is_pass() {
  rep(i, 3) {
    if(math[i][0] && math[i][1] && math[i][2]) {
      return true;
    }
    if(math[0][i] && math[1][i] && math[2][i]) {
      return true;
    }
  }
 
  if(math[0][0] && math[1][1] && math[2][2]) {
    return true;
  }
 
  if(math[0][2] && math[1][1] && math[2][0]) {
    return true;
  }
 
  return false;
}
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  rep(i, 3) {
    rep(j, 3) {
      cin >> origin[i][j];
      math[i][j] = false;
    }
  }
 
  int n;
  cin >> n;
 
  rep(i, n) {
    int b;
    cin >> b;
    check(b);
  }

  if(is_pass()) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

// konoshita kara kaku

int main(void){
	int n=in(),x[200000],y[200000],m,i;
	rep(i,n)y[i]=x[i]=in();
	sort(x,n);
	m=x[n/2];
	rep(i,n){
		if(y[i]<m)print(x[n/2]);
		else print(x[n/2-1]);
	}
	return 0;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  ll N, K, S;
  scanf("%lld %lld %lld", &N, &K, &S);

  ll val = S;
  for (ll i = 0; i < K; i++) {
    cout << val << " ";
  }

  if (S == 1000000000LL) {
    val--;
  } else {
    val++;
  }

  for (ll i = 0; i < (N - K); i++) {
    cout << val << " ";
  }
  cout << "" << endl;
}


Measured memory_bytes: 1280
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    def prime_factor(n):
        lst = []
        while n%2 == 0:
            n //= 2
            lst.append(2)
        f = 3
        while f**2 <= n:
            if n%f == 0:
                n //= f
                lst.append(f)
            else:
                f += 2
        if n != 1:
            lst.append(n)
        return lst

    n, p = LI()
    count = collections.Counter(prime_factor(p))

    ans = 1

    for key in count.keys():
        ans *= key**(count[key]//n)

    print(ans)

main()


Measured memory_bytes: 74796
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;


int main() {


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

    string sa;
    string sb;

    for (int i = 0; i < a; ++i) {
        sb += to_string(b);
    }

    for (int j = 0; j < b; ++j) {
        sa += to_string(a);
    }

    if (sa <= sb) {
        cout << sa << "\n";
    } else {
        cout << sb << "\n";
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
  int N, M, K;
  cin >> N >> M >> K;
  for (int i = 0; i <= N; i++)
  {
    for (int j = 0; j <= M; j++)
    {
      if (i * M + N * j - 2 * (i * j) == K)
      {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>

int main(){
  int n;
  std::cin>>n;
  int arr[n+1]={0};
  int k;

  for(int i=1; i<n; ++i){
    std::cin>>k;
    arr[k] += 1;
  }
  for(int i=1; i<=n; ++i){
    std::cout<<arr[i]<<std::endl;
  }
}


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

const int INF = 1000000000;

int main(){
	while(true){
		int n, m;
		cin >> n >> m;

		if(n==0 && m==0)
			break;

		int C[100][100];
		int T[100][100];
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				if(i==j){
					C[i][j] = T[i][j] = 0;
				}
				else{
					C[i][j] = T[i][j] = INF;
				}
			}
		}

		for(int i=0; i<n; i++){
			int a, b, c, t;
			cin >> a >> b >> c >> t;

			C[a-1][b-1] = C[b-1][a-1] = c;
			T[a-1][b-1] = T[b-1][a-1] = t;
		}

    for(int k=0; k<m; k++){
      for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
          if(C[i][j]>C[i][k]+C[k][j]){
            C[i][j] = C[i][k]+C[k][j];
          }
        }
      }
    }

    for(int k=0; k<m; k++){
      for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
          if(T[i][j]>T[i][k]+T[k][j]){
            T[i][j] = T[i][k]+T[k][j];
          }
        }
      }
    }

    int k;
    cin >> k;

    for(int i=0; i<k; i++){
      int p, q, r;
      cin >> p >> q >> r;
      if(r==0){
        cout << C[p-1][q-1] << endl;
      }else if(r==1){
        cout << T[p-1][q-1] << endl;
      }

    }

	}

	return 0;
}



Measured memory_bytes: 3092
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include<climits>
#include<set>
#include<bitset>
#include<random>
using namespace std;

typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define maxs(a,b) a = max(a,b)
#define mins(a,b) a = min(a,b)
#define rep(i,n) for(int i = 0;i < n;i++)

const double pie = 3.1415926535897932384626433;

//偏角
double argment(double x,double y){  
   // if(x == (double)0 && y == (double)0) continue;
   double length = sqrt(x*x + y*y);
   double ag = (double)180 * acos(x/length) / pie;
   if(y < 0) ag = (double)360 - ag;
   return ag;
}

int main(void){
   cout << fixed;
   int N;cin >> N;
   vector<pair<double,double>> H(N);
   for(int i = 0;i < N;i++){
      double x,y;cin >> x >> y;
      H[i] = make_pair(x,y);
   }
   
   ////////////////////////////////
   
   for(int i = 0;i < N;i++){
      vector<pair<double,double>> P;
      vector<double> A;
      vector<double> D;
      for(int j = 0;j < N;j++){
         if(j == i) continue;
         P.pb(mp(H[j].first - H[i].first,H[j].second - H[i].second));
      }
      for(int j = 0;j < N - 1;j++){
         A.pb(argment(P[j].first,P[j].second));
      }
      sort(all(A));
      
     
      //for(auto i : A)cout << i << endl;
      D.pb((double(360) - A[N-2]) + A[0]);
      for(int j = 1;j < N-1;j++){
         D.pb(A[j] - A[j-1]);
      }
      
      sort(all(D));
      reverse(all(D));
      // cout << setprecision(20) << D[0] << endl;
      cout << setprecision(20) << max((double)0,D[0] - (double)180) / (double)360 << endl;
   }
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<ll, ll>
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pd pair<double, double>
#define vp vector<pi>
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, a, n) for(int i = a; i < n; i++)
#define mod (1000*1000*1000+7)
#define sz(x) int((x).size())
#define all(x) x.begin(),x.end()
#define DBG(v) cerr << #v << " = " << (v) << endl;
ll INF = (1ll<<61);

using namespace std;

vi *g;
vi *gb;
int color[100005];

void dfs(int V, int c){
  color[V] = c;
  vi &adj = g[V];
  for(auto k : adj){
    if(color[k] != 0) continue;
    dfs(k, c);
  }
}

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
      ll n, m, k; cin >> n >> m >> k;
      g = new vi[n+1];
      gb = new vi[n+1];
      f(i, m){
        ll a,b ; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
      }
      f(i, k){
        ll a,b ; cin >> a >> b;
        gb[a].pb(b);
        gb[b].pb(a);
      }
      fo(i,1, n+1){
        if(!color[i]) dfs(i, i);
      }
      vi ccolor(n+1);
      fo(i, 1, n+1) ccolor[color[i]]++;
      vi ans(n+1);
      fo(i, 1, n+1) ans[i] = ccolor[color[i]]-1;
      fo(i, 1, n+1){
        for(auto k : g[i]){
          if(color[i] == color[k]){
            ans[i]--;
          }
        }
        for(auto k : gb[i]){
          if(color[i] == color[k]){
            ans[i]--;
          }
        }
      }
      fo(i, 1, n+1) cout << ans[i] << " ";
      cout << endl;
    }
    return 0;
}


Measured memory_bytes: 15104
#include<iostream>
#include<queue>
using namespace std;
int N;
int D[101],d[101][101];
void bfs(int src){
    int u[101],k[101],a[101];
    bool visit[101];
    for(int i=1;i<=N;++i){
        cin>>u[i]>>k[i];
        for(int j=0;j<k[i];++j){
            cin>>a[j];
            d[u[i]][a[j]]=1;
        }
        visit[i]=true;
    }
    queue<int>Q;
    Q.push(src);
    D[src]=0;
    visit[src]=false;
    while(!Q.empty()){
        int cur=Q.front();
        Q.pop();
        for(int i=1;i<=N;++i){
            if(d[cur][i]==1&&visit[i]){
                visit[cur]=false;
                visit[i]=false;
                D[i]=D[cur]+1;
                Q.push(i);
            }
        }
    }
    for(int i=1;i<=N;++i){
        if(i!=1&&D[i]==0){
            D[i]=-1;
        }
        cout<<i<<" "<<D[i]<<endl;
    }
}
int main(){
    cin>>N;
    int start=1;
    bfs(start);
}

Measured memory_bytes: 3076
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
typedef vector<int> vi;
typedef vector<ll> vl;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define IN cin >> 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (m-1); i >= (int)(n); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
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; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////


int main(){
    int n,k;
    cin >> n >> k;
    P((n%k)?1:0);
    return  0;
}


Measured memory_bytes: 256
class Combi
  def initialize(max_n, mod = 10**9+7)
      @mod = mod
      @max_n = max_n

      @fac = Array.new(@max_n+1)
      @inv = Array.new(@max_n+1)
      @finv = Array.new(@max_n+1)

      @fac[0] = @fac[1] = 1
      @finv[0] = @finv[1] = 1
      @inv[1] = 1
      2.upto(@max_n) do |i|
          @fac[i] = @fac[i-1] * i % @mod
          @inv[i] = @mod - @inv[@mod%i] * (@mod/i) % @mod
          @finv[i] = @finv[i-1] * @inv[i] % @mod
      end
  end

  def nCk(n,k)
      @fac[n] * @finv[n - k] * @finv[k] % @mod
  end
end

MOD=10**9+7
combi = Combi.new(1000001)

N=gets.to_i
a=gets.chomp.split.map(&:to_i)

cnt = Hash.new(0)
a.each {|v| cnt[v]+=1}

m = nil
cnt.each {|k,v| m = k if v == 2}
pos=[]
a.each_with_index do |v,i|
  pos << i if v == m
end 
puts N
2.upto(N+1) do |i|
  if N+1-(pos[1]-pos[0]+1) >= i-1
    puts (combi.nCk(N+1,i) - combi.nCk(N+1-(pos[1]-pos[0]+1), i-1)) % MOD
  else
    puts combi.nCk(N+1,i)
  end
end


Measured memory_bytes: 42644
#include<bits/stdc++.h>
using namespace std;
long long const MAX= 1e9 + 7;
int main()
{long long t,i,n,k,j;
cin>>n;
long long a[n+1][3];
long long dp[n+1][3];
dp[0][0]=0;dp[0][1]=0;dp[0][2]=0;
for(i=1;i<n+1;i++)
{   for(j=0;j<3;j++)
    cin>>a[i][j];}
for(j=1;j<=n;j++)
{ dp[j][0]=max(dp[j-1][1]+a[j][1],dp[j-1][2]+a[j][2]);
dp[j][1]=max(dp[j-1][0]+a[j][0],dp[j-1][2]+a[j][2]);
dp[j][2]=max(dp[j-1][1]+a[j][1],dp[j-1][0]+a[j][0]);}
k=max(dp[n][0],dp[n][1]);
k=max(k,dp[n][2]);
cout<<k;
return 0;}


Measured memory_bytes: 4992
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}



int main(){
    int a,b;cin>>a>>b;
    int n = b-a;
    cout<<n*(n+1)/2-b;
}



Measured memory_bytes: 256
/* "miles to go before I sleep." */


#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define mod 1000000007
#define pi  3.14159265358979323846
#define pb push_back
#define mk make_pair
#define popcnt(a) _Generic((a), int: __builtin_popcount(a), \  long long: __builtin_popcountll(a))  
#define precise(x) cout<<fixed<<setprecision(10)<<x
#define test cout<<"#";
#define input freopen("input.txt", "r", stdin)
#define output freopen("output.txt", "w", stdout) 

const ll inf = 1e18L + 2;

ll ans[100001];
ll n, k;
ll solve(vector<ll> &v, ll k)
{
    if(k == 0)
        return 0;
    if(ans[k]!=-1)
        return ans[k];
    ll d = 1;
    for(ll x = 0; x < n; x++)
    {
        if(v[x]<=k)
            d&=solve(v, k-v[x]);
    }
    return ans[k] = 1 - d;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    vector<ll> v(n);
    for(ll x = 0; x < n; x++)
        cin>>v[x];
    memset(ans, -1, sizeof(ans));
    cout<<(solve(v, k)?"First":"Second");
}

Measured memory_bytes: 9108
import java.util.*;

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

    int n = sc.nextInt();
    int g = sc.nextInt();
    int a[] = new int[n];
    int count = 0;
    int sum = 0;
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
      sum += a[i];
      count++;
    }
    Arrays.sort(a);
    System.out.println(count + ((g - sum) / a[0]));
  }
}


Measured memory_bytes: 21844
n   = gets.to_i
ary = []
n.times do
  ary << gets.to_i
end
ary.sort!

cnt = 1
ans = 0

(n - 1).times do |i|
  if ary[i] == ary[i + 1]
    cnt = (cnt + 1) % 2
  else
    ans += cnt
    cnt = 1
  end
  if i == n - 2
    ans += cnt
  end
end

puts ans


Measured memory_bytes: 4016
n = int(input())
a = input()
b = input()
c = input()

#%%
# n = 4
# a = "west"
# b = "east"
# c = "wait"


#%%
(a[0] == b[0]) + (a[0]==c[0]) + (b[0]==c[0])

#%%
ans = 0
for i in range(n):
    if (a[i] == b[i]) + (a[i] == c[i]) + (b[i] == c[i]) == 1:
        ans+=1
    if (a[i] == b[i]) + (a[i] == c[i]) + (b[i] == c[i]) == 3:
        pass
    if (a[i] == b[i]) + (a[i] == c[i]) + (b[i] == c[i]) == 0:
        ans+=2
print(ans)



#%%


Measured memory_bytes: 3064
import bisect
n = int(input())
l = list(map(int,input().split()))
l = sorted(l)
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        x = bisect.bisect_left(l, l[i] + l[j], j+1)
        ans += x -j -1
print(ans)


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

using namespace std;

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;

#define all(c) begin(c),end(c)

#define D(x) do { std::cerr << x << " "; } while (0)
#define D2(x) do { std::cerr << #x << ": " << x << std::endl; } while (0)


template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    if (!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}


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

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


auto solve() {
    string s;
    cin>>s;
    return (s <= "2019/04/30");
}


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

    cout << (solve() ? "Heisei" : "TBD") << endl;
//    cout << (solve() ? "YES" : "NO") << endl;
//    cout << solve() << endl;
//    solve();

    return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
// clang-format off
#define FOR(i, n) for (int i=0; i<(int)n; ++i)
#define RFOR(i, n) for (int i=n-1; i>=0; --i)
#define FORR(x,arr) for(auto& x:arr)
#define OUTV(x) FOR(j,x.size()) cerr<<x[j]<<(x.size()-j-1?' ':'\n');
#define OUTM(x) FOR(i,x.size()) {OUTV(x[i])}
#define DEBUG(x) cerr<<"DEBUG: "<<#x<<" = "<<x<<endl;
#define PB push_back
#define MP make_pair
#define INF 0x3f3f3f3f
using namespace std;
typedef signed long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
// clang-format on

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  // std::random_device rd;
  //  std::mt19937 ran(rd());

  
  int n;
  cin >> n;
  vi A(n);
  FOR(i,n) cin >> A[i];

  if(n == 2){
    cout << max(A[0], A[1]) << endl;
    exit(0);
  }

  vi gcd_first(n), gcd_second(n);

  gcd_first[0] = A[0];
  gcd_second[n-1] = A[n-1];

  for(int i = 1; i + 1 < n; ++i){
    gcd_first[i] = __gcd(gcd_first[i-1], A[i]);
    gcd_second[n-1-i] = __gcd(gcd_second[n - i], A[n-1-i]);
  }
  
  int ans = 0;
  for(int i = 1; i + 1 < n; ++i){
    ans = max(ans, __gcd(gcd_first[i-1], gcd_second[i+1]) );
  }

  ans = max(ans, gcd_second[1]);
  ans = max(ans, gcd_first[n-2]);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1408
#pragma region ヘッダー
#define _CRT_SECURE_NO_WARNINGS

#ifdef _____MY_DEBUG_____
#define VS_ENDPAUSE()	(system("pause"))
#else
#define VS_ENDPAUSE()
#endif

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
typedef signed char int8;
typedef signed short int16;
typedef signed int int32;
typedef signed long long int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long long uint64;
#define int int64

#ifndef INT8_MIN
#define INT8_MIN	(-127)
#endif
#ifndef INT8_MAX
#define INT8_MAX	( 128)
#endif
#ifndef UINT8_MAX
#define UINT8_MAX	( 255)
#endif
#ifndef INT16_MIN
#define INT16_MIN	(-32768)
#endif
#ifndef INT16_MAX
#define INT16_MAX	( 32767)
#endif
#ifndef UINT16_MAX
#define UINT16_MAX	( 65535)
#endif
#ifndef INT32_MIN
#define INT32_MIN	(-2147483648)	// -2 * 10^9
#endif
#ifndef INT32_MAX
#define INT32_MAX	( 2147483647)	//  2 * 10^9
#endif
#ifndef UINT32_MAX
#define UINT32_MAX	( 4294967295)	//  4 * 10^9
#endif
#ifndef INT64_MIN
#define INT64_MIN	(-9223372036854775808)	// -9 * 10^18
#endif
#ifndef INT64_MAX
#define INT64_MAX	( 9223372036854775807)	//  9 * 10^18
#endif
#ifndef UINT64_MAX
#define UINT64_MAX	( 18446744073709551615)	// 18 * 10^18
#endif

void func(void);
#pragma endregion

int32 main(void)
{
	func();
	VS_ENDPAUSE();
	return 0;
}


void func(void)
{
	int n;
	cin >> n;
	vector< int > a(n);
	for(int i=0; i<n; i++){
		cin >> a[i];
	}

	int cnt = 0;
	int pos = 0;
	int i;
	for(i=0; i<n; i++){
		if(a[pos] == 2){
			cnt++;
			break;
		}
		cnt++;
		pos = a[pos]-1;
	}
	if(i==n){
		cout << -1 << endl;
	}else{
		cout << cnt << endl;
	}

	return;
}




Measured memory_bytes: 1152
#include <iostream>
#include <cmath>
#include <string>
using namespace std;

int main()
{
	int N = 0;
	cin >> N;
	string W[N];
	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
	}
	bool flag = true;
	for (int i = 0; i < N; i++)
	{
		if(i!=0){if(W[i-1][W[i-1].size()-1]!=W[i][0]){flag = false;}}
		for (int x = 0; x < i; x++)
		{
			if(W[i]==W[x]){flag = false;}
		}
	}
	if(flag){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t=1;
    //cin >> t;
    while (t--)
    {
        ll h1,m1,h2,m2,k;
        cin>>h1>>m1>>h2>>m2>>k;
        ll temp = h2*60+m2 - h1*60-m1;
        if(temp >=k)
            cout<<temp-k<<endl;
        else
            cout<<"0\n";
    }
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
using ll = long long;
const int MM = 2e5+2;

map<ll, ll> cnt;
int n;
ll k, a[MM], ans;
ll rm[MM];

int main(){
    
    scan(n, k);
    cnt[0] = 1;
    for(int i = 1;i <= n; i++){
        if(i-k >= 0){
            //print(i, i-k);
            cnt[rm[i-k]]--;
        }
        scan(a[i]);
        a[i] = (a[i] + a[i-1]) % k;
        ll v = ((a[i]-i)%k+k)%k;
        ans += cnt[v];
        //need to shift according to length
        //length at all times is i-j+1
        //when adding values, do
        //print(i, a[i], v, cnt[v]);
        cnt[v]++;
        rm[i] = v;
    }
    
    print(ans);
    
    return 0;
}

Measured memory_bytes: 15872
#include<stdio.h>

int main(void){
	int N, a[100], i, j, Alice = 0, Bob = 0, max, m;
	scanf("%d", &N);

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

	for(i = 0; i < N; i++){
		max = 0;	m = 0;
		for(j = 0; j < N; j++){
			if(a[j] > max)	{max = a[j];	m = j;}
		}
		if(i % 2 == 0)	Alice += a[m];
		else	Bob += a[m];
		a[m] = 0;
	}

	printf("%d\n", Alice - Bob);

	return 0;
}

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

int num[9];
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  num[a - 1]++; num[b - 1]++; num[c - 1]++;
  for (int i = 0; i < 9; i++) {
    if (num[i] == 2) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;    
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i;
	int n;
	int c = 0;
	int mv[1000] = {0};
	
	while (scanf("%d", &n) != EOF){
		mv[n]++;
		if (c <= mv[n]){
			c = mv[n];
		}
	}
	
	for (i = 0; i < 1000; i++){
		if (c == mv[i]){
			printf("%d\n", i);
		}
	}
	
	return (0);
}

Measured memory_bytes: 596
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

// map<int, int> prime_factor(int n) {
//   map<int, int> res;
//   for (int i = 2; i * i <= n; ++i) {
//     while (n % i == 0) {
//       res[i]++;
//       n /= i;
//     }
//   }
//   if (n != 1) res[n] = 1;
//   return res;
// }

int main() {
  int n;
  cin >> n;
  map<int, int> prime;
  for (int f = 1; f <= n; ++f) {
    int num = f;
    for (int i = 2; i * i <= num; ++i) {
      while (num % i == 0) {
        prime[i]++;
        num /= i;
      }
    }
    if (num != 1) prime[num]++;
  }
  vector<int> cnt(5);
  for (auto a : prime) {
    if (74 <= a.second) cnt[0]++;
    if (24 <= a.second) cnt[1]++;
    if (14 <= a.second) cnt[2]++;
    if (4 <= a.second) cnt[3]++;
    if (2 <= a.second) cnt[4]++;
  }
  int ans = 0;
  ans += cnt[0];
  ans += cnt[1] * (cnt[4] - 1);
  ans += cnt[2] * (cnt[3] - 1);
  ans += (cnt[3] * (cnt[3] - 1)) / 2 * (cnt[4] - 2);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
// Always have fun - aNONYMOUS //

#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define mod 1e9+7
#define inf 1e18
#define pb push_back
#define mp make_pair
#define vll vector<ll>

int main(){
	IOS;
	ll t,n,i,j,k,ans;
	t=1;//cin >> t;
	while(t--){
		ans=0;
		cin >> n;
		cout << n+n*n+n*n*n;
	}
	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

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;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    while(true){
        int n,r; 
        cin>>n>>r; 
        if(n==0&&r==0)
            break; 
        vi res(n); 
        rep(i,0,n)
            res[i]=n-i; 
        rep(i,0,r){
            int p,c; 
            cin>>p>>c; 
            vi st(p-1); 
            //上からp-1枚保管
            rep(j,0,p-1){
                st[j]=res[j]; 
            }
            //c枚を上に
            rep(j,0,c){
                res[j]=res[p-1+j];
            }
            //p-1枚を下に
            rep(j,0,p-1){
                res[j+c]=st[j]; 
            }
        }
        cout<<res[0]<<endl; 
    }
       
    return 0;
}




Measured memory_bytes: 3088
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())

using namespace std;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

using ll = long long;
constexpr int mod = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T gcd(T u, T v) {
    ll r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T lcm(T u, T v) {
    return u * v / gcd(u, v);
}

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

    string S;
    cin >> S;
    int r = 0;
    REP(i, S.length()) {
        if (S[i] == '0')r++;
    }
    int b = S.length() - r;
    cout << min(r, b) * 2 << endl;
    return 0;

}

Measured memory_bytes: 512
#include <iostream>
    #include <utility>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <set>
    #include <cmath>
             
    typedef long long ll;
    using namespace std;
    const ll INF = 1000000000000000000ll;
    const ll MOD = 1000000007ll;
       
    #define PI 3.14159265358979323846
             
    const double EPS = 1e-8;
            
    int main()
    {
       	ll N,K;
     
    	cin >> N>>K;
     
    	vector<pair<ll,ll>> A(N);
     
    	for(ll i=0;i<N;i++){
			cin >> A[i].first >> A[i].second;
    	}
     
    	sort(A.begin(),A.end());
     
    	ll sum=0,l;
    	for(l=0;l<N;l++){
			sum=sum+A[l].second;
    		if(sum>=K) break;
    	}
     
		cout << A[l].first << endl;
     
       	return 0;
    }

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007; // 998244353
using ll = long long;
using namespace std;

int main(){
	ll a, b, c; cin >> a >> b >> c;
	cout << min(a+b+1, c)+b << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define Mod 1000000007
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;

typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll n,m;cin>>n>>m;
	pii a[m];For(i,0,m) cin>>a[i].fi>>a[i].se;

	pii ans(1,n);

	For(i,0,m){
		if(a[i].fi>ans.se || a[i].se<ans.fi){
			cout<<0<<endl;return 0;
		}else{
			ans.fi = max(ans.fi,a[i].fi);
			ans.se = min(ans.se,a[i].se);
		}
	}
	cout<<ans.se-ans.fi+1<<endl;










	
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
long long const MX = 2e5 + 2, MOD = 1e9 + 7;
long long c[MX], p[MX];
int main()
{
    long long t = 1;
//    cin>>t;
    while(t--){
        long long n , k;
        cin>>n>>k;
        long long mx = -1e9 - 1;
        for(long long i = 0; i < n; i++) cin>>p[i],p[i]--;
        for(long long i = 0; i < n; i++){
            cin>>c[i];
            mx = max(mx, c[i]);
        }
        if(mx <= 0) {
            cout<<mx;
            continue;
        }
        mx = -1e15;
        for(long long i = 0; i < n; i++){
            long long cntp = 0, sum = 0, x = i;
            while(true){
                sum += c[p[x]];
                x = p[x];
                cntp++;
                if(x == i) break;
            }
            //cout<<sum<<endl;
            long long l = k, ans = 0;
                //ans += max(0ll, sum) * ((long long)k/cntp);
                //l = k % cntp;

//            for(long long j = 0; j < l; j++){
//                ans = ans + c[p[x]];
//                x = p[x];
//                mx = max(mx, ans);
//            }
//            mx = max(mx, ans);
            long long cnt = 0, path = 0;
            x = i;
            //cout<<"i = "<<i<<" :\n";
            while(true){
                cnt++;
                path += c[x];
                if(cnt > k) break;
                int num = (k - cnt)/cntp;
                long long score = path + max(0ll, sum)*num;
                //cout<<score<<endl;
                mx = max(mx, score);
                x = p[x];
                if(x == i) break;
            }
        }
        cout<<mx;
    }
}





Measured memory_bytes: 3724
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;



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

	vector<string> s(n + 1);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		s[i] += '#';
	}
	s[n] = string(m + 1, '#');

	int num = n * m;
	int st = num;
	int go = num + 1;
	mf_graph<int> g(num + 2);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] == '#') {
				continue;
			}

			int p = i * m + j;

			if ((i + j) % 2) {
				g.add_edge(st, p, 1);
			}
			else {
				g.add_edge(p, go, 1);
			}

			if (s[i + 1][j] != '#') {
				if ((i + j) % 2) {
					g.add_edge(p, p + m, 1);
				}
				else {

					g.add_edge(p + m, p, 1);
				}
			}

			if (s[i][j + 1] != '#') {
				if ((i + j) % 2) {
					g.add_edge(p, p + 1, 1);
				}
				else {

					g.add_edge(p + 1, p, 1);
				}
			}


		}
	}


	cout << g.flow(st, go) << endl;

	vector<string> ans(n, string(m, '.'));
	vector<mf_graph<int>::edge> e(g.edges());
	for (auto it = e.begin(); it != e.end(); it++) {
		int fr = it->from;
		int to = it->to;
		int fl = it->flow;
		//cout <<fr << to << fl << endl;
		if (fr == st || to == go || fl == 0) {
			continue;
		}

		int x0 = fr / m;
		int y0 = fr % m;
		int x1 = to / m;
		int y1 = to % m;



		if (x0 < x1) {
			ans[x0][y0] = 'v';
			ans[x1][y1] = '^';
		}
		if (x0 > x1) {
			ans[x0][y0] = '^';
			ans[x1][y1] = 'v';
		}
		if (y0 < y1) {
			ans[x0][y0] = '>';
			ans[x1][y1] = '<';
		}
		if (y0 > y1) {

			ans[x0][y0] = '<';
			ans[x1][y1] = '>';
		}



	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] == '#') {
				ans[i][j] = '#';
			}
		}
	}

	for (string ai : ans) {
		cout << ai << endl;
	}
}

Measured memory_bytes: 5636
#include <iostream>
using namespace std;
int main(void) {
    int h, w;
    cin >> h >> w;
    string board[50];
    for (int i = 0; i < h; ++i) cin >> board[i];
    const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
    const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (board[i][j] == '#') continue;
            int num = 0;
            for (int d = 0; d < 8; ++ d) {
                const int ni = i + dy[d];
                const int nj = j + dx[d];
                if (ni < 0 or h <= ni) continue;
                if (nj < 0 or w <= nj) continue;
                if (board[ni][nj] == '#') num++;
            }
        board[i][j] = char(num + '0');
        }
    }
    for (int i = 0; i < h; ++i) cout << board[i] << endl;
    return 0;
}

Measured memory_bytes: 256
import collections
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def combi(a,b):
	num = 1
	for j in range(b):
		num = num*(a-j)//(j+1)
	return num

N,P = IL()
A = IL()

odd = 0
even = 0
for i in A:
	if i%2 != 0:
		odd += 1
	else:
		even += 1

zero = 1
if even != 0:
	for i in range(1,even+1):
		zero += combi(even,i)

if P == 1:
	ans = 0
	for i in range(1,odd+1,2):
		ans += combi(odd,i)*zero
else:
	ans = 0
	for i in range(0,odd+1,2):
		ans += combi(odd,i)*zero

print(ans)

Measured memory_bytes: 12516
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
#define vpl vector<pair<ll,ll>>
#define vvl vector<vector<ll>> //a(縦行,vector<ll>(横列));
#include<algorithm>//__gcd(a,b)
#include <iostream>
#include <vector>
#include <cstdlib>
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; }

const long long INF = 1LL << 60;

int main(){
    ll n,k;cin>>n>>k;
    vl h(n);rep(i,n)cin>>h[i];
    vl dp(n);rep(i,n)dp[i]=INF;dp[0]=0;

   for(ll i=0;i<n;i++){ 
       for(ll j=1;j<k+1;j++){chmin(dp[i+j],dp[i]+abs(h[i+j]-h[i]));}}


cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::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>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

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

    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
}


Measured memory_bytes: 3596