akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

using Graph = vector<vector<pair<int,ll>>>;
int N;
Graph G;

void dijkstra(int p,vector<ll> &dist,vector<bool> visited){
	priority_queue<pair<ll,int>> q;
	dist[p] = 0;
	q.push(make_pair(0,p));
	while(!q.empty()){
		pair<ll,int> f = q.top();
		q.pop();
		int u = f.second;

		if(dist[u] < f.first*(-1)) continue;
		visited[u] = true;

		rep(i,G[u].size()){
			int v = G[u][i].first;
			if(visited[v] == true) continue;

			if(dist[v] > dist[u] + G[u][i].second){
				dist[v] = dist[u] + G[u][i].second;
				q.push(make_pair(dist[v]*(-1),v));
			}
		}


	}

}

int main(){
	cin >> N;
	G.resize(N);
	rep(i,N-1){
		int a,b,c; cin >> a >> b >> c;
		a--; b--;
		G[a].emplace_back(b,c);
		G[b].emplace_back(a,c);
	}
	int Q,K; cin >> Q >> K;
	K--;
	vector<ll> dist(N,LINF);
	vector<bool> visited(N,false);
	dijkstra(K,dist,visited);
	rep(i,Q){
		int x,y; cin >> x >> y;
		x--; y--;
		ll ans = dist[y] + dist[x];
		cout << ans << endl;
	}
}



Measured memory_bytes: 11120
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const long long INF = 1LL << 60;
const ll C = 1000000000+7;

int main() {
  int a,b;
  cin >> a >> b;
  cout << max(a+b,max(a-b,a*b)) << endl;
}

Measured memory_bytes: 3612
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(X: int, Y: int, Z: int):

    N = X // (Y+Z)
    if (Y+Z)*N + Z <= X:
        print(N)
    else:
        print(N-1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    solve(X, Y, Z)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;

int main() {
  int n;
  char str[10], com[13];
  map<string, bool>  T;

  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    scanf("%s%s", com, str);
    if ( com[0] == 'i' ) T[string(str)] = true;
    else {
      if ( T[string(str)] ) printf("yes\n");
      else printf("no\n");
    }
  }

  return 0;
}


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

int main(void) {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> x(n, vector<int> (n)), y(n, vector<int> (n));
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
        for (int j = 0; j < a.at(i); j++) {
            cin >> x.at(i).at(j) >> y.at(i).at(j);
            x.at(i).at(j)--; // ビット演算のために減らしておく
        }
    }
    int ans = 0;
    for (int bits = 0; bits < (1<<n); bits++) {
        int ok = true;
        for (int i = 0; i < n; i++) {
            // 正直者以外の証言は無視
            if (((bits>>i) & 1) == 1) {
                for (int j = 0; j < a.at(i); j++) {
                    // 矛盾を探す
                    if (((bits>>x.at(i).at(j)) & 1) != y.at(i).at(j)) {
                        ok = false;
                    }
                }
            }
        }
        if (ok == true) {
            int tmp = __builtin_popcount(bits);
            ans = max (ans, tmp);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
//  zukonit14 - Kunal Raut

#include<bits/stdc++.h>
using namespace std;
#define ll                  long long
#define int                 long long
#define ld                  long double
#define pb                  push_back
#define mp                  make_pair
#define fi                  first
#define se                  second
#define mod                 1000000007
#define pi                  3.1415926535
#define MAXN                2*100000+10
#define MAX2N               1*1000+10
const   ll INF              = 1e18;
#define all(v)              v.begin(), v.end()
#define allr(v)             v.rbegin(), v.rend()
#define ms(s, n)            memset(s, n, sizeof(s))
#define prec(n)             fixed<<setprecision(n)
#define forci(p,n)          for(ll i=p;i<(ll)n;i++)
#define forcj(p,n)          for(ll j=p;j<(ll)n;j++)
#define bolt                ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a)             __builtin_popcountll(a)
#define djokovic            freopen("input00.txt", "r", stdin);freopen("output00.txt", "w", stdout);
clock_t time_p              = clock();
void rtime()                {time_p = clock() - time_p; cout << "\nTime Taken : " << fixed << (float)(time_p) / CLOCKS_PER_SEC << "s\n";}
ll gcd(ll a, ll b)          {if (b == 0) return a;    return gcd(b, a % b);}
ll lcm(ll a, ll b)          {return (a / gcd(a, b) * b);}
ll expo(ll x, ll y)         {ll res = 1; x = x % mod; while (y > 0) {if (y & 1)res = (1ll * res * x) % mod; y = y >> 1; x = (1ll * x * x) % mod;} return res % mod;}
ll inv_mod(ll q, ll m = mod)   {return (expo(q, m - 2) % m);}
ll ncr(ll n, ll r)          {ll res = 1; if (r > n - r)r = n - r; for (ll i = 0; i < r; i++) {  res *= n - i;  res /= i + 1; } return res;}
ll max(ll a, ll b)          {return (a > b) ? a : b;}
bool prime(ll n)            {ll i; for (i = 2; i <= sqrt(n); i++) {if (n % i == 0)return false;} return true;}
//https://www.youtube.com/watch?v=WTJSt4wP2ME

ll rr[] = {0, 1, 1, 1, 0, -1, -1, -1};
ll cc[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll n, m, k, x, q, a[MAXN], b[MAXN], c[MAXN], best;
void solve()
{
    cin >> n;
    ll aa = 0, bb = 0, cc = 0;
    for (ll i = 1; i <= n; i++)
    {
        ll a, b, c; cin >> a >> b >> c;
        a += max(bb, cc);
        b += max(aa, cc);
        c += max(aa, bb);
        aa = a; bb = b; cc = c;
    }
    cout << max(aa, max(bb, cc));
}
signed main()
{
    bolt;
#ifndef ONLINE_JUDGE
    djokovic;
#endif
    ll t;
    t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    //rtime();
}




Measured memory_bytes: 3624
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>

using namespace std;


/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back


/*---  Type ---*/
typedef long long ll;


/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;


// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

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

int solve(int x) {
  rep1(i, x+2) {
    if((i*(i-1))/2 >= x) return i-1;
  }
  return 0;
}

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

  cout << solve(x) << endl;

  return 0;
}

Measured memory_bytes: 256
/*----------------by syr----------------*/
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<deque>
#include<fstream>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<limits>
#include<list>
#include<map>
#include<math.h>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<sstream>
#include<string>
#include<time.h>
#include<utility>
#include<vector>

using namespace std;

const int INF=1e9+7;

int n,m,c,sz;
int fa[100005],rk[100005],id[100005],dis[2000005];
bool used[100005];
vector<int> g[2000005];
vector<pair<int,int> > ve[2000005];

int getF(int x){return ((x==fa[x])?x:(fa[x]=getF(fa[x])));}

void combine(int a,int b){
	a=getF(a);
	b=getF(b);
	if(rk[a]<rk[b]) fa[a]=b;
	else if(rk[a]>rk[b]) fa[b]=a;
	else{
		fa[a]=b;
		rk[b]++;
	}
	return;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		ve[w].push_back(make_pair(u,v));
		c=max(c,w);
	}
	sz=n;
	for(int i=1;i<=c;i++){
		for(int j=0;j<ve[i].size();j++){
			int u=ve[i][j].first;
			int v=ve[i][j].second;
			id[u]=id[v]=-1;
			used[u]=used[v]=0;
			rk[u]=rk[v]=1;
			fa[u]=u;fa[v]=v;
		}
		for(int j=0;j<ve[i].size();j++){
			int u=ve[i][j].first;
			int v=ve[i][j].second;
			combine(u,v);
		}
		for(int j=0;j<ve[i].size();j++){
			int u=ve[i][j].first;
			int v=ve[i][j].second;
			if(used[u]==0){
				used[u]=1;
				int fu=getF(u);
//				printf("%d %d\n",u,fu);
				if(id[fu]==-1) id[fu]=++sz;
				g[u].push_back(id[fu]);
				g[id[fu]].push_back(u);
			}
			if(used[v]==0){
				used[v]=1;
				int fv=getF(v);
//				printf("%d %d\n",v,fv);
				if(id[fv]==-1) id[fv]=++sz;
				g[v].push_back(id[fv]);
				g[id[fv]].push_back(v);
			}
		}
	}
/*	for(int i=1;i<=sz;i++){
		for(int j=0;j<g[i].size();j++) printf("%d ",g[i][j]);
		puts("");
	}
*/	queue<int> q;
	q.push(1);
	memset(dis,-1,sizeof(dis));
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(dis[v]==-1){
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
	if(dis[n]==-1) puts("-1");
	else printf("%d\n",dis[n]/2);
	return 0;
}

Measured memory_bytes: 119040
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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

const long long INF = 1LL << 60;

int main(){
  int n, m; cin >> n >> m;
  vector<int> cnt(m);

  rep(i, n){
    int k; cin >> k;
    rep(j, k){
      int a; cin >> a; a--;
      cnt[a]++;
    }
  }

  int ans = 0;
  rep(i, m) if(cnt[i] == n) ans++; 

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(){
    double a,b,c;
    double PI=acos(-1);
    scanf("%lf %lf %lf",&a,&b,&c);
    c/=180.0;
    c*=PI;
    printf("%lf\n%lf\n%lf\n",a*b*0.5*sin(c),a+b+sqrt(a*a+b*b-2.0*a*b*cos(c)),a*b*sin(c)/a);
    return 0;
}


Measured memory_bytes: 2144
def solve():
  ans = float('inf')
  N = int(input())
  A = list(map(int, input().split()))
  if A[0]==0:
    lis = [1,-1]
  else:
    lis = [A[0],-A[0]//abs(A[0])]
  for l in lis:
    cnt = abs(A[0]-l)
    total = l
    for i in range(1,N):
      new_total = total+A[i]
      if total*(new_total)>=0:
        new_total = (-1)*total//abs(total)
        cnt += abs(new_total-(total+A[i]))
      total = new_total
    ans = min(ans,cnt)
  return ans
print(solve())

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

int main(){
    int N, C, K;
    cin >> N >> C >> K;
    int T[N];
    for(int i =0; i < N; i++){
        cin >> T[i];
    }
    sort(T, T + N);
    int left = 0;
    int bus = 1;
    for(int i =0; i < N; i++){
        if(T[i] > T[left] + K || (i - left + 1)> C){
            left = i;
            bus ++;
        }
    }
    cout << bus << endl;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct var{
	int fr,to,nxt;
}edge[101001];
int n,size[101001],cnt,head[101001];
LL d[101001],dis[101001];
map<LL,int>num;
void add(int u,int v)
{
	cnt++;
	edge[cnt].to=v;
	edge[cnt].fr=u;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs(int o,int f)
{
	for(int i=head[o];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==f)continue;
		dis[v]=dis[o]+1;
		dfs(v,o);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&d[i]);
		num[d[i]]=i;
		size[i]=1;
	}
	sort(d+1,d+n+1);
	for(int i=n;i>1;i--)
	{
		int u=num[d[i]];
		LL tmp=n-2*size[u],f=d[i]-tmp;
		if(tmp<0)
		{
			printf("-1");
			return 0;
		}
		if(!num.count(f))
		{
			printf("-1");
			return 0;
		}
		int x=num[f];
		add(x,u);
		size[x]+=size[u];
	}
	dfs(num[d[1]],0);
	LL sum=0;
	for(int i=1;i<=n;i++)sum+=dis[i];
	if(sum!=d[1])
	{
		printf("-1");
		return 0;
	}
	for(int i=1;i<=cnt;i++)
	{
		printf("%d %d\n",edge[i].fr,edge[i].to);
	}
}

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

bool tong[301]; 

int main()
{
	string s;
	cin>>s;
	int len = s.length();
	for(int i = 0; i < len; i++)
	{
		tong[s[i]] = true;	
	}
	if(tong['W'] == tong['E'] && tong['N'] == tong['S']) printf("Yes");
	else printf("No");
 } 

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

int main(){
	/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
   #endif*/
	int p,q,r;
	cin>>p>>q>>r;
	int a,b;
	 a = min(p,q);
	if(a!=q){
		 b = min(q,r); 
	}   
	else {
		b = min(p,r);
	}
	cout<<a+b;
	return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn.{readInt, readLine};

object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        for (i <- (0 until n)) {
            val a = readLine;
            val b = readLine;
            println(lcs(a, b).length);
        }
    }
    def lcs(a: String, b: String): String = {
        val arr = Array.ofDim[String](a.length + 1, b.length + 1);
        for (i <- (0 to a.length)) { arr(i)(0) = ""};
        for (i <- (0 to b.length)) { arr(0)(i) = "" };
        def go(row: Int, col: Int): String = {
            if (arr(row)(col) != null) {
                arr(row)(col)
            } else {
                val c1 = go(row - 1, col);
                val c2 = go(row, col - 1);
                val c3 = go(row - 1, col - 1);
                arr(row)(col) = if (a(row - 1) == b(col - 1)) {
                    max(c1, c2, c3 + a(row - 1));
                } else {
                    max(c1, c2, c3);
                }
                arr(row)(col); 
            }
        }
        go(a.length, b.length);
    }
    
    def max(a: String, b: String, c: String): String = {
        val lenA = a.length; val lenB = b.length; val lenC = c.length;
        if (lenA > lenB) {
            if (lenC > lenA) c else a;
        } else {
            if (lenC > lenB) c else b;
        }
    }
}


Measured memory_bytes: 578648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n;
  cin >> n;
  vec p(n);
  for(ll i=0;i<n;i++) cin >> p[i];
  sort(p.rbegin(),p.rend());
  ll ans=-p[0]/2;
  for(ll i=0;i<n;i++) {
    ans+=p[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define inf 10000000000000000
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
lli dp[100][100005];
int main(){
IOS;
lli n,w,x,y,i,j;
cin>>n>>w;
vector<pair<lli,lli> > v;
for(i=0;i<n;i++){
    cin>>x;
    cin>>y;
    v.pb(mp(x,y));
}
for(i=0;i<n;i++){
    for(j=0;j<=100004;j++){
        dp[i][j]=inf;
    }
}
for(j=0;j<=100004;j++){
    if(j==v[0].second)
        dp[0][j]=v[0].first;
    else dp[0][j]=inf;
}
for(i=0;i<n;i++){
    dp[i][0]={0};
}
for(i=1;i<n;i++){
    for(j=1;j<=100004;j++){
        if(j<v[i].second)
        dp[i][j]=dp[i-1][j];
        else{
            dp[i][j]=min(v[i].first+dp[i-1][j-v[i].second],dp[i-1][j]);
        }
    }
}
lli maxi=0;
for(i=0;i<n;i++){
    for(j=0;j<=100000;j++){
        if(dp[i][j]<=w){
            maxi=max(maxi,j);
        }
    }
}
cout<<maxi<<endl;
}


Measured memory_bytes: 78336
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

// --------------------------------------
int n, a[21];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  REP(i, n) {
    cin >> a[i];
  }

  int sum = 0;
  int ma = a[0];
  REP(i, n) {
    if(ma <= a[i]) {
      sum++;
      ma = a[i];
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,a[109];
ll dp[100009][109],v[109];
ll bt(int x,int i)
{
    if(dp[x][i]!=-1)return dp[x][i];
    ll &ret=dp[x][i];
    ret=max(ret,bt(x,i-1));
    if(x-a[i]>=0)ret=max(ret,v[i]+bt(x-a[i],i-1));
    return ret;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>v[i];
    }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=k;i++)dp[i][0]=0;
    cout<<bt(k,n);
}


Measured memory_bytes: 85376
<?php
	fscanf(STDIN, "%d", $n);
	$ans = 100000;
	for($i = 0; $i < $n; $i++) {
		$ans *= 1.05;
		if($ans % 1000) {
			$ans -= $ans % 1000;
			$ans += 1000;
		}
	}
	print $ans . "\n";
?>

Measured memory_bytes: 6556
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
//#define int long long
#define INF 1e9
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

const int MAX = 510000;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int pre[100010];
signed main(){
 int h,w,a,b;
 cin>>h>>w>>a>>b;
 ll ans=0;
 COMinit();
 //ans+=COM(h+w-2,h-1);
 //cerr<<ans<<endl;
 for (int i = b; i < w; i++)
 {
     ll tmp=COM(h-(a+1)+i,i)*COM(a-1+w-(i+1),a-1)%MOD;
    // cerr<<tmp<<endl;
     ans+=tmp;
     ans%=MOD;
 }
 cout<<ans<<endl;
   
    return 0;
}

Measured memory_bytes: 12288
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class B
{
    static void Main()
    {
        int[] intRecord = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
        var N = intRecord[0];
        var M = intRecord[1];

        var answer = string.Empty;
        if(N >= M)
        {
            answer = M.ToString();
            for (int i = 1; i < N; i++)
            {
                answer += M.ToString();
            }
        }
        else
        {
            answer = N.ToString();
            for (int i = 1; i < M; i++)
            {
                answer += N.ToString();
            }
        }


        Console.WriteLine(answer);
    }
}

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

int main(){
  ll k;
  cin >> k;
  ll seven = 7;
  for(int i=1; i<=k; i++){
    if(seven%k == 0){
      cout << i << endl;
      return 0;
    }
    seven = seven*10 + 7;
    seven %= k;
  }
  cout << -1 << endl;
}


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

int main() {
  string s;
  cin >> s;
  ll q;
  cin >> q;
  bool r=false;
  vector<char> first;
  vector<char> end; 
  for(ll i=0;i<q;i++) {
    ll temp;
    cin >> temp;
    if(temp==1) {
      r=!r;
    }
    else if(temp==2) {
      ll f;
      char c;
      cin >> f >> c;
      if(!r) {
        if(f==1) {
          first.push_back(c);
        }
        else if(f==2) {
          end.push_back(c);
        }
      }
      else {
        if(f==2) {
          first.push_back(c);
        }
        else if(f==1) {
          end.push_back(c);
        }
      }
    }
  }
  if(r) {
    for(ll i=end.size()-1;i>-1;i--) {
      cout << end[i];
    }
    reverse(s.begin(),s.end());
    cout << s;
    for(ll i=0;i<first.size();i++) {
      cout << first[i];
    }
  }
  else {
    for(ll i=first.size()-1;i>-1;i--) {
      cout << first[i];
    }
    cout << s;
    for(ll i=0;i<end.size();i++) {
      cout << end[i];
    }
  }
  cout << endl;
}

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  int d = 0;
  if(a == b) d++;
  if(a == c) d++;
  if(b == c) d++;
  if(a == b && a == c) d--;
  cout << 3 - d << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  	cin.tie(0);
	ios::sync_with_stdio(false);
	int a, b, k;
  	cin >> a >> b >> k;
	for (int i = a; i < min(a+k, b+1); i++) cout << i << endl;
	for (int i = max(b-k+1, a+k); i <= b; i++) cout << i << endl;
  	cout << endl;
  	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
int main() {
	string s;
	char c;
	cin >> s;
	vector<int> alpha(26, 0);
	for (int i = 0; i < s.size(); i++) {
		alpha.at(s.at(i) - 'a') = 1;
	}
	for (int i = 0; i < 26; i++) {
		if (alpha.at(i) == 0) {
			c = 'a' + i;
			cout << c << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;

}

Measured memory_bytes: 3756
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = (int) 2e5 + 100;
int a[N];

int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i] );
    bool good = (a[0] == 0);
    for (int i = 1; i < n; i++)
        if (a[i] > a[i - 1] + 1)
            good = false;
    if (!good)
    {
        printf("-1\n");
        return 0;
    }
    long long ans = 0;
    for (int i = 1; i < n; i++)
        if (a[i + 1] != a[i] + 1)
            ans += a[i];
    printf("%lld\n", ans);


	return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
struct dog {
	string a;
	int b;
};
int main()
{
	//int n, m;
	//cin >> n >> m;
	//if (n == m)cout << "Yes";
	//else cout << "No";

	int a;
	int b;
	cin >> a >> b;
	
	if (a > b)
		for (int i = 0; i < a; i++)
			cout << b;
	else
		for (int i = 0; i < b; i++)
			cout << a;
}



Measured memory_bytes: 3560
class Tree:
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]
        self.root = -1

    def set_tree(self):
        for _ in range(self.n):
            i_str = [int(i) for i in input().split()]
            for i in range(2):
                if i_str[i+1] != -1:
                    if i == 0:
                        self.nodes[i_str[0]].left = i_str[1]
                    else:
                        self.nodes[i_str[0]].right = i_str[2]
                    self.nodes[i_str[i+1]].parent = i_str[0]

    def set_root(self):
        for tn in self.nodes:
            if tn.parent == -1:
                self.root = tn.id
                return tn.id

    def preorder(self, node):
        print(' ' + str(self.nodes[node].id), end='')
        if self.nodes[node].left != -1:
            self.preorder(self.nodes[node].left)
        if self.nodes[node].right != -1:
            self.preorder(self.nodes[node].right)

    def inorder(self, node):
        if self.nodes[node].left != -1:
            self.inorder(self.nodes[node].left)
        print(' ' + str(self.nodes[node].id), end='')
        if self.nodes[node].right != -1:
            self.inorder(self.nodes[node].right)

    def postorder(self, node):
        if self.nodes[node].left != -1:
            self.postorder(self.nodes[node].left)
        if self.nodes[node].right != -1:
            self.postorder(self.nodes[node].right)
        print(' ' + str(self.nodes[node].id), end='')

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = -1
        self.left = -1
        self.right = -1

if __name__ == '__main__':
    tree = Tree(int(input()))
    tree.set_tree()
    root = tree.set_root()
    print("Preorder")
    tree.preorder(root)
    print()
    print('Inorder')
    tree.inorder(root)
    print()
    print('Postorder')
    tree.postorder(root)
    print()

Measured memory_bytes: 7720
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7
    d = dict()
    if N % 2 == 0:
        for i in range(1, N, 2):
            d[i] = 0
    else:
        for i in range(0, N, 2):
            d[i] = 0
    # print(d)
    # print(A)
    for a in A:
        if a not in d: return 0
        else: d[a] += 1
    # print(d)

    if N % 2 == 0:
        if all(d[a] == 2 for a in d):
            return pow(2, len(d.keys())) % div
        else:
            return 0
    else:
        if d[0] != 1: return 0
        else:
            del d[0]
            if all(d[a] == 2 for a in d):
                return pow(2, len(d.keys())) % div
            else:
                return 0

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 14692
n = input()
a = [int(i) for i in n]
#print(a)
e = []
for i in [-1,1]:
    for j in [-1,1]:
        for k in [-1,1]:
            if a[0] + a[1]*i + a[2]*j + a[3]*k == 7:    
                e.append([i,j,k])
ans = []
for i in e[0]:
    if i == -1:
        ans.append("-")
    else:
        ans.append("+")
print(str(a[0]) + ans[0] + str(a[1]) + ans[1] + str(a[2]) + ans[2] + str(a[3]) + "=7")


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(z) for(int i=1;i<=z;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define pb push_back
#define si set<int>
#define mod  1000000007
#define cl(n,m) (int)(ceil(double(n)/double(m)))
#define T() int TT; cin>>TT; while(TT--)
#define P pair<int,int>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dp[200005][3] ;
signed main(){
	int n ,k;
	string s="0" ,t;
	cin>>n>>t ;
	s+=t ;
	for(int i=1 ;i<=n ;i++){
		dp[i][1] = min(dp[i-1][0] , dp[i-1][1]) + (s[i]=='.'); 
		dp[i][0] = dp[i-1][0] + (s[i] == '#') ;
		//cout<<dp[i][0] << " "<<dp[i][1]<<endl ;
	}
	cout<<min(dp[n][1] , dp[n][0]) ;
}


Measured memory_bytes: 5508
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(vs) vs.begin(), vs.end()
using ll = long long;
using ii = pair<ll, ll>;

int32_t main(){
	string st;
	cin >> st;
	bool ans = true;
	ll res = 0;
	for(auto &c:st){
		ll x = c-'9';
		res += x;
	}
	if(res%3==0)
		cout << "Yes\n";
	else
		cout << "No\n";

}



Measured memory_bytes: 3752
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <math.h>
#include <bitset>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

typedef long long ll;

const ll INF = 1e18, MOD = 1e9 + 7;
const int INT_MAX = 1e9;

ll n, W;

ll w[100], v[100], d[100][100001];

int mx;

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

	for (int i = 0; i < n; i++)
	{
		scanf ("%lld%lld", &w[i], &v[i]);
	}

	ll sum = 0;

	for (int i = 0; i <= n * 1000; i++)
		d[0][i] = INF;

	d[0][v[0]] = w[0];
	if (w[0] <= W) mx = v[0];
	d[0][0] = 0;

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= n * 1000; j++)
		{
			d[i][j] = d[i-1][j];

			if (j - v[i] >= 0 && d[i-1][j - v[i]] + w[i] <= W)
			{
				d[i][j] = min (d[i][j], d[i-1][j - v[i]] + w[i]);
			}

			if (d[i][j] <= W)
				mx = max (mx, j);
		}
	}

	cout << mx;

}

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

const int MAX_N = 2*1e5+100;
char s[MAX_N];
typedef long long LL;

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> s){
        LL cnt = 0;
        LL ans = 0;
        for(int i = 0; s[i]; ++i){
            if(s[i] == 'B'){
                ++cnt;
            } else {
                ans += cnt;
            }
        }
        cout << ans;
    }
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
// #include <atcoder/all> // NOTE: AtCoderライブラリ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
// using namespace atcoder; // NOTE: AtCoderライブラリ
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef pair<int, int> pii;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__

const ll MOD = 1e9 + 7;

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

    vl dp(S + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= S; i++) {
        for (int j = i - 3; j >= 0; j--) {
            dp[i] += dp[j];
            dp[i] %= MOD;
        }
    }

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


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

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr <<">>>>>>"<< #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif
int d[256];
int main()
{
	
string s;
cin>>s;
for(auto i:s)d[i]=1;
for(int i='a';i<='z';i++)if(d[i]==0){cout<<(char)i<<endl;return 0;}
puts("None");


}



Measured memory_bytes: 3712
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
import sys

""""
import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
N = int(input())
A = list(map(int, input().split()))

def main():
    Aabs = [0]*N
    cnt_n=0
    for i,a in enumerate(A):
        Aabs[i] = abs(a)
        if a <0:
            cnt_n+=1
    if cnt_n%2 ==0:
        print(sum(Aabs))
    else:
        print(sum(Aabs)- min(Aabs)*2)
            
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 23340
import bisect

n = int(input())
l = list(map(int, input().split()))

l.sort()
ans_set = set()
ans = 0

for i in range(n):
    if i + 1 == n:
        break
    for j in range(i+1, n):
        ans += max(bisect.bisect_left(l, l[i]+l[j]) - j-1, 0)

print(ans)


Measured memory_bytes: 3188
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> inputs = new ArrayList<>();
        int n,m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        long all = 0;
        scanner.nextLine();
        int a;
        for (int i = 0; i < n; i++) {
            a = scanner.nextInt();
            inputs.add(a);
            all += a;
        }
        inputs.sort(Collections.reverseOrder());
        int c = 0;
        double b = all / 4.0;
        b /= m;
        for (Integer input : inputs) {
            if (c == m-1) {
                if (b <= (double) input) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
                return;
            }
            c++;
        }
    }

}

Measured memory_bytes: 24020
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans = 0;
vl A, B;
int main() {
	cin >> x >> n >> m;
	if (abs(n - m) % 2 == 0)cout << abs(n - m) / 2 << endl;
	else {
		if (n > m)swap(n, m);
		cout << min(n + (m - n - 1) / 2, x - m + 1  + (m - n - 1) / 2) << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int>> A(M, vector<int>(2,0));
  for(int i=0; i<M; i++){
    int a,b;
    cin>>a>>b;
    A[i][0]=a;
    A[i][1]=b;
  }
  sort(A.begin(), A.end(), [](auto& x, auto& y){return x[1] < y[1];});
  int keep=0, ans=0;
  for(int i=0; i<M; i++){
    if(ans==0 || A[i][0]>=keep){
      ans++;
      keep=A[i][1];
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 5760
#include<iostream>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,1)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a==b)return false;
		if(rank[a]<rank[b])
		{
			parent[a]=b;
			rank[b]+=rank[a];
		}
		else
		{
			parent[b]=a;
			rank[a]+=rank[b];
		}
		return true;
	}
};
long n;
int m,a[1<<17],b[1<<17];
long ans[1<<17];
main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)cin>>a[i]>>b[i];
	ans[m]=n*(n-1)/2;
	UF uf(n);
	for(int i=m;i--;)
	{
		int A=uf.find(a[i]-1),B=uf.find(b[i]-1);
		if(uf.same(A,B))
		{
			ans[i]=ans[i+1];
			continue;
		}
		ans[i]=ans[i+1]-uf.rank[A]*uf.rank[B];
		uf.unite(A,B);
	}
	for(int i=0;i++<m;)cout<<ans[i]<<endl;
}

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

int main(){
    int a, b;
    cin >> a >> b;
    if(a < b){
        for(int i=0;i<b;i++) cout << a;
    }else{
        for(int i=0;i<a;i++) cout << b;
    }
    cout << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 
int main()
{
  ll N, A, B;
  cin >> N >> A >> B;

  ll a = N/(A+B);
  ll b = N%(A+B);
  if(b-A>=0){
    cout << a*A+A << endl;
  }else{
    cout << a*A + b << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
# a, b = map(int, input().split())
X = list(map(int, input().split()))

minV = float('inf')
for i in range(1, 100 + 1):
    temp = 0
    for j in range(N):
        temp += (i - X[j]) ** 2
    minV = min(minV, temp)

print(minV)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }
const double PI = 3.14159265358979323846;
int main() {
  int k, a, b;
  int f = 0;
  cin >> k >> a >> b;
  for (int i = 0; i <= b - a; i++) {
    if ((a + i) % k == 0) {
      f++;
    }
  }
  if (f != 0) cout << "OK";
  if (f == 0) cout << "NG";
  return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
    long long h, w, n;
    cin >> h >> w >> n;

    map<int, set<int>> cell, cell_n;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        cell[a].insert(b);

        for (int j = max(1LL, a - 2); j <= min(a, h - 2); j++) {
            for (int k = max(1LL, b - 2); k <= min(b, w - 2); k++) {
                cell_n[j].insert(k);
            }
        }
    }

    vector<long long> res(10, 0);
    res[0] = (h - 2) * (w - 2);

    for (map<int, set<int>>::iterator i = cell_n.begin(); i != cell_n.end(); i++) {
        for (set<int>::iterator j = i->second.begin(); j != i->second.end(); j++) {
            int cnt = 0;
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l < 3; l++) {
                    if (cell.find(i->first + k) != cell.end()
                            && cell[i->first + k].find(*j + l) != cell[i->first + k].end()) {
                        cnt++;
                    }
                }
            }

            res[0]--;
            res[cnt]++;
        }
    }

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


Measured memory_bytes: 86656
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	long k=sc.nextLong();
  	int n=sc.nextInt();
  	long[] ai=new long[n];
  	for(int i=0;i<n;i++){
  		ai[i]=sc.nextLong();
  	}
  	long s=0;
  	long[] si=new long[n];
  	for(int i=0;i<n;i++){
  		if(i==n-1){
  			si[i]=k+ai[0]-ai[i];
  		}else{
  			si[i]=ai[i+1]-ai[i];
  		}
  	}
  	Arrays.sort(si);
  	for(int i=0;i<n-1;i++){
  		s+=si[i];
  	}
  	System.out.print(s);
  }
}

Measured memory_bytes: 79492
#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#define IFD(...)
#ifndef NDEBUG
#define NDEBUG
#endif
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <cassert>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <boost/hana/functional/fix.hpp>
using boost::hana::fix;
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repd(i, n) for (int i = (n)-1; i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, b, a) for (int i = (b); i >= (a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    string s;
    cin >> s;
    cout << s;
    if (*s.rbegin() == 's')
    {
        cout << "es\n";
    }
    else
    {
        cout << "s\n";
    }

    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#include <numeric>
#include <queue>
#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001001000
#define mod 1000000007
//#define mod 998244353
#define pi 3.1415926535
using namespace std;
struct __INIT{
    __INIT(){
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout<<fixed<<setprecision(15);
    }
}__init;

ll d;


vl f(vvl s,vl c,vl last,ll depth,ll hukasa){
    if(hukasa >= 2 || depth >= d) return {0,0,0,0};
    ll ret = -inf;
    ll retind = 0;
    ll ret2 = -inf;
    ll retind2 = 0;
    rep(i,26){
        ll minus = 0;
        rep(j,26){
            if(j != i) minus += c[j]*(depth-last[j]);
        }
        ll moto = last[i];
        last[i] = depth;
        vl saki = {0,0,0,0};
        if(depth >= d-3) saki = f(s,c,last,depth+1,hukasa+1);
        last[i] = moto;
        if(ret < s[depth][i]-minus+saki[1]){
            ret = s[depth][i]-minus+saki[1];
            retind = i;
            ret2 = saki[1];
            retind2 = saki[0];
        }
    }
    return {retind,ret,retind2,ret2};
}

void score(vvl s,vl c,vl t){
    vl last(26);
    ll ans = 0;
    rep(i,d){
        ans += s[i][t[i]];
        ll minus = 0;
        last[t[i]] = i;
        rep(j,26) minus += c[j]*(i-last[j]);
        ans -= minus;
    }
    cout<<ans<<endl;
}

int main(){
    cin>>d;
    vl c(26);
    rep(i,26) cin>>c[i];
    vvl s(d,vl(26));
    rep(i,d) rep(j,26) cin>>s[i][j];
    vl last(26,0);
    vl t(d);
    rep(i,d){
        vl tmp = f(s,c,last,i,0);
        last[tmp[0]] = i;
        cout<<tmp[0]+1<<endl;
        t[i] = tmp[0];
        i++;
        if(i >= d) break;
        last[tmp[2]] = i;
        cout<<tmp[2]+1<<endl;
        t[i] = tmp[2];
    }
    //score(s,c,t);
    return 0;
}


Measured memory_bytes: 4000
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 101;
const int V = 100010;

int n, k;
int a[N];
int dp[V];

int main()
{
  cin >> n >> k;
  for(int i = 0 ; i < n ; i++)
    cin >> a[i];
  dp[0] = 0;
  for(int i = 1 ; i <= k ; i++) {
    dp[i] = 0;
    for(int j = 0 ; j < n ; j++) {
      if(i - a[j] >= 0 && !dp[i - a[j]]) {
        dp[i] = 1;
        break;
      }
    }
  }
  cout << (dp[k] ? "First" : "Second") << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mem(arr,v) memset(arr,v,sizeof(arr))
/*bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
} */
int main()
{
     ll t,arr[100005];
     cin>>t;
     for(int i=0;i<t;i++)
     {
         cin>>arr[i];
     }
     ll cnt=0,mx=0;
     for(int i=0;i<t-1;i++)
     {
         if(arr[i]>=arr[i+1])
            cnt++;
         else
            cnt=0;
         mx=max(mx,cnt);
     }
     cout<<mx<<endl;
}


Measured memory_bytes: 1024
from itertools import permutations
n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))


count = 0
a, b = 0, 0
for index, i in enumerate(permutations(range(1, n+1))):
    if i in [P, Q]:
        if count == 0:
            count += 1
            a = index
        else:
            b = index
            break
if P != Q:
    print(abs(a - b))
else:
    print(0)


Measured memory_bytes: 3064
#include<stdlib.h>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<cstring>
#include<time.h>
#include<queue>
using namespace std;

int t[101];
int main(){
	int n;
	double a,b,c,cal,pr;
	cin>>n;
	cin>>a>>b;
	cin>>c;
	for(int i=0;i<n;i++){
		cin>>t[i];
	}
	std::sort(t,t+n);
	cal=c;pr=a;
	for(int i=n-1;i>=0;i--){
		if(cal/pr<=t[i]/b){
			cal+=t[i];
			pr+=b;
		}
	}
	cout<<(int)(cal/pr)<<endl;
	return 0;
}	

Measured memory_bytes: 1244
using System;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using System.Runtime.CompilerServices;

class P
{
    static void Main()
    {
        var nc = Console.ReadLine().Split().Select(int.Parse).ToList();
        int[] imos = new int[100001];

        var g = Enumerable.Repeat(0, nc[0]).Select(_ => Console.ReadLine().Split().Select(int.Parse).ToList()).GroupBy(x => x[2]).Select(x => x.OrderBy(y => y[0]).ToArray()).ToList();
        foreach (var sts in g)
        {
            Dictionary<int, int> endTimes = new Dictionary<int, int>();
            foreach (var st in sts)
            {
                if (endTimes.ContainsKey(st[0]))
                {
                    imos[st[0]]++;
                    endTimes[st[0]]--;
                    if (endTimes[st[0]] == 0) endTimes.Remove(st[0]);
                }
                else imos[st[0] - 1]++;
                imos[st[1]]--;
                if (!endTimes.ContainsKey(st[1])) endTimes.Add(st[1], 0);
                endTimes[st[1]]++;
            }
        }
        int current = 0;
        int res = 0;
        foreach (var item in imos)
        {
            current += item;
            res = Max(res, current);
        }
        Console.WriteLine(res);
    }
}

Measured memory_bytes: 36568
from copy import deepcopy
fact = []
def init():
  fact.append(0)
  for i in range(1,101):
    fact.append(0)

def solve(n):
  cnt = 0
  for i in range(1,n+1):
    tp = i
    di = 2
    while tp != 1:
      if tp % di == 0:
        fact[di] += 1
        cnt += 1
        tp /= di
      else:
        di += 1
  sf = []
  tf = [] 
  ft = []
  f = []
  t = []
  for i in range(1,101):
    if fact[i] >= 74:
      sf.append(i)
    if fact[i] >= 24:
      tf.append(i)
    if fact[i] >= 14:
      ft.append(i)
    if fact[i] >= 4:
      f.append(i)
    if fact[i] >= 2:
      t.append(i)
  ans = len(sf)
  for i in tf:
    for j in t:
      if i != j:
        ans += 1
  for i in ft:
    for j in f:
      if i != j:
        ans += 1
  for i in f:
    for j in f:
      if i < j:
        for k in t:
          if i != k and j != k:
            ans += 1  
  return ans

n = int(input())
init()
print(solve(n))


Measured memory_bytes: 3444