akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>

typedef long long int int64;

typedef struct point2d{
  int x,y;
} point;

typedef struct rectangle{
  point a,b;
} rectangle;

int cmp(const void *a,const void *b){
  return *(int *)a-*(int *)b;
}

int compress(int *a,int n){
  qsort(a,n,sizeof(int),cmp);
  int i,j;
  i=j=0;
  while(i<n){
    a[j++]=a[i++];
    while(i<n && cmp(a+j-1,a+i)==0) i++;
  }
  return j;
}

int toIndex(int *a,int n,int v){
  int l=0;
  int r=n;
  while(r-l>1){
    int m=(l+r)/2;
    int c=cmp(a+m,&v);
    if(c==0) return m;
    if(c<0){
      l=m;
    } else {
      r=m;
    }
  }
  return l;
}

void run(void){
  int n;
  scanf("%d",&n);
  rectangle *r=(rectangle *)calloc(n,sizeof(rectangle));
  int *x=(int *)calloc(2*n,sizeof(int));
  int *y=(int *)calloc(2*n,sizeof(int));
  int i,j;
  for(i=0;i<n;i++){
    scanf("%d%d%d%d",&r[i].a.x,&r[i].a.y,&r[i].b.x,&r[i].b.y);
    x[2*i]=r[i].a.x;
    x[2*i+1]=r[i].b.x;
    y[2*i]=r[i].a.y;
    y[2*i+1]=r[i].b.y;
  }
  int xlen=compress(x,2*n);
  int ylen=compress(y,2*n);
  int *dp=(int *)calloc(xlen*ylen,sizeof(int));
  for(i=0;i<n;i++){
    dp[toIndex(x,xlen,r[i].a.x)*ylen+toIndex(y,ylen,r[i].a.y)]++;
    dp[toIndex(x,xlen,r[i].a.x)*ylen+toIndex(y,ylen,r[i].b.y)]--;
    dp[toIndex(x,xlen,r[i].b.x)*ylen+toIndex(y,ylen,r[i].a.y)]--;
    dp[toIndex(x,xlen,r[i].b.x)*ylen+toIndex(y,ylen,r[i].b.y)]++;
  }
  for(i=0;i<xlen;i++) for(j=1;j<ylen;j++) dp[i*ylen+j]+=dp[i*ylen+j-1];
  for(j=0;j<ylen;j++) for(i=1;i<xlen;i++) dp[i*ylen+j]+=dp[(i-1)*ylen+j];
  int64 ans=0;
  for(i=0;i+1<xlen;i++){
    for(j=0;j+1<ylen;j++){
      if(dp[i*ylen+j]>0){
	ans+=(int64)(x[i+1]-x[i])*(y[j+1]-y[j]);
      }
    }
  }
  printf("%lld\n",ans);
}

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



Measured memory_bytes: 64392
#include        "algorithm"
#include        "iostream"
#include        "numeric"
#include        "iomanip"
#include        "cstring"
#include        "math.h"
#include        "bitset"
#include        "string"
#include        "vector"
#include        "ctime"
#include        "queue"
#include        "stack"
#include        "map"
#include        "set"

#include        "ext/pb_ds/assoc_container.hpp" // Common file
#include        "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include        "ext/pb_ds/detail/standard_policies.hpp"

using namespace std;
using namespace __gnu_pbds;


#define          f first
#define          lgn 25
#define          endl '\n'
#define          sc second
#define          N (int)2e5+5
#define          pb push_back
#define          mod 1000000007
#define          ld long double
#define          vi vector<int>
#define          eb emplace_back
#define          vpii vector<pii>
#define          mii map<int,int>
#define          int long long 
#define          pii pair<int,int>
#define          pq priority_queue
#define          BLOCK (int)sqrt(N)
#define          test(x) while(x--)
#define          all(x) begin(x),end(x)
#define          allr(x) rbegin(x),rend(x)
#define          fo(i,a,n) for(int i=a;i<n;i++)
#define          rfo(i,n,a) for(int i=n;i>=a;i--)
#define          FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define          time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define          PI acos(-1.0)
#define 		 bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > 
OS ;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

inline void INP()
{
	#ifndef ONLINE_JUDGE
	    freopen("input.txt","r",stdin);   
	    freopen("output.txt","w",stdout);
	#endif 
}

const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n,m,k,q;
string s;
vi adj[N];
int vis[N],par[N],a[N];

void go()
{
	cin >> n >> k;

	int ans = INF;

	if( n >= k )
	{
		ans = n%k;
		n %= k;
	}

	if( n <= k )
	{
		ans = min( ans , n%k );
		while( abs( n - k ) < ans )
		{
			ans = abs( n - k );
			n -= k;
		}
	}

	cout << ans << endl;
}

int32_t main()
{
	//INP(); 
	FAST;     
	int t=1; 
	// cin>>t;
	test(t) go();
}

 

Measured memory_bytes: 5504
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.14159265358979323846;


// ****************************************CODE***************************************//





vector<vector<int>> to, co;
vector<int> ans;
void dfs(int x){
        for(int i = 0; i < to[x].size(); i++){
                int u = to[x][i];
                int w = co[x][i];

                if(ans[u] == -1){
                        ans[u] = (ans[x] + w) % 2;
                        dfs(u);
                }
        }

}




int main(){
        int n;
        cin >> n;
        ans.resize(n,-1);
        to.resize(n);
        co.resize(n);

        //隣接リスト
        //グラフ構造を持つ
        for(int i = 0; i < n-1; i++)
        {
                int a, b, w;
                cin >> a >> b >> w;
                a--;
                b--;
                to[a].push_back(b);
                co[a].push_back(w);
                to[b].push_back(a);
                co[b].push_back(w);
        }

        ans[0] = 0;
        dfs(0);

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

















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

int main() {
  int N,M;
  cin >> N >> M;
  vector<int> vec(M * 2);
  
  for(int i = 0; i < vec.size(); i++){
    cin >> vec.at(i);
  }
  
  for(int i = 1; i <= N; i++){
    int count = 0;
    for(int j = 0; j < vec.size(); j++){
      if(vec.at(j) == i){
        count++;
      }
    }
    cout << count << endl;
  }
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5005,mod=1000000007;
int n,u,v,cnt,ans,head[N],to[N*2],nxt[N*2],f[N][N],g[N],t[N],siz[N];
void adde(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void dfs(int pre,int u){
	siz[u]=1;
	f[u][1]=1;
	if(u==3){
		u++;
		u--;
	}
	int v;
	for(int i=head[u];i;i=nxt[i]){
		v=to[i];
		if(v!=pre){
			dfs(u,v);
			for(int j=1;j<=siz[u];j++){
				for(int k=1;k<=siz[v];k++){
					t[j]=(t[j]-1LL*f[u][j]*f[v][k]%mod*g[k]%mod+mod)%mod;
					t[j+k]=(t[j+k]+1LL*f[u][j]*f[v][k])%mod;
				}
			}
			siz[u]+=siz[v];
			for(int j=1;j<=siz[u];j++){
				f[u][j]=t[j];
				t[j]=0;
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	g[0]=1;
	for(int i=2;i<=n;i++){
		if((i&1)^1){
			g[i]=1LL*g[i-2]*(i-1)%mod;
		}
		scanf("%d%d",&u,&v);
		adde(u,v);
		adde(v,u);
	}
	dfs(0,1);
	for(int i=1;i<=n;i++){
		ans=(ans+1LL*f[1][i]*g[i])%mod;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 56456
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    int a,b; cin>>a>>b;
    if(a%3==0||b%3==0||(a+b)%3==0){
        cout<<"Possible"<<endl;
    }
    else cout<<"Impossible"<<endl;
}





Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<pair<string, int>> restaurant(N);
	for (int i = 0; i < N; i++) {
		cin >> restaurant[i].first >> restaurant[i].second;
		restaurant[i].second *= -1;
	}
	vector<pair<string, int>> T = restaurant;
	sort(T.begin(), T.end());
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (T[i] == restaurant[j]) cout << j + 1 << endl;
		}
	}

	return 0;
}

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

const int DIM = 200005;

long long pos[DIM], dp1[DIM], dp2[DIM];

int main(void)
{
    int n, e, t;
    cin >> n >> e >> t;
    
    for (int i = 1; i <= n; ++i)
        cin >> pos[i];
    
    dp2[0] = 1e17;
    for (int i = 1, p = 1; i <= n; ++i) {
        while ((pos[i] - pos[p]) * 2 >= t)
            ++p;
        
        dp1[i] = min(dp1[p - 1] + t, dp2[p - 1] + pos[i] * 2);
        dp2[i] = min(dp2[i - 1], dp1[i - 1] - pos[i] * 2);
    }
    
    cout << dp1[n] + e << endl;
    return 0;
}

Measured memory_bytes: 3584
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <random>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
const string MINUSINF = "-";

typedef pair<int, int> P;
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
#define OUTPUT(i) (cout << (ll)i << endl)
#define ALL(a) ((a).begin(), (a).end())

bool operator<(const pair<ll, ll> &a, const pair<ll, ll> &b)
{

    if (a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}

ll N, K, M;
ll A[100010];
ll ans = 0;

void calc(ll depth, ll bit, ll sum)
{
    for (; depth >= 0; depth--)
    {
        ll a = 1LL << depth;

        int f1 = 0, f0 = 0;

        for (int i = 0; i < N; ++i)
        {
            if (A[i] >> depth & 1)
                f1++;
            else
                f0++;
        }

        if (f0 >= f1)
        {
            sum += f0 * a;
        }
        else
        {
            sum += f1 * a;
        }
    }

    ans = max(ans, sum);
}

void dfs(ll depth, ll bit, ll sum)
{
    if (depth < 0)
    {
        ans = max(ans, sum);
        return;
    }

    ll a = 1LL << depth;

    ll f0 = 0, f1 = 0;
    for (int i = 0; i < N; ++i)
    {
        if ((A[i] >> depth) & 1)
            f1++;
        else
            f0++;
    }

    if (bit + a > K)
    {
        //0しか入らない

        dfs(depth - 1, bit, sum + f1 * a);
    }
    else
    {
        calc(depth - 1, bit, sum + f1 * a);
        //depth番目に0が入る
        //このときdepth-1番目以降にはどの0/1のどちらの数字が入ってもよい
        dfs(depth - 1, bit + a, sum + f0 * a); //depth番目に1を立てる
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);

    cin >> N >> K;

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

    dfs(40, 0, 0);

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;


ll i,j,k;


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


Measured memory_bytes: 3788
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int head[100111],nxt[200111],from[200111],to[200111],l[200111],tot,sz[100111];
int n;
void addedge(int u,int v,int w)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	from[tot]=u;
	l[tot]=w;
}

void dfs(int x,int f=0)
{
	sz[x]=1;
	for(int i=head[x];i;i=nxt[i])
		if(to[i]!=f)
		{
			dfs(to[i],x);
			sz[x]+=sz[to[i]];
		}
}
LL ans;
int main()
{
	get1(n);
	for(int i=1,u,v,w;i<n;i++)
	{
		get3(u,v,w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	dfs(1);
	for(int i=1;i<=tot;i++)
	{
		if(sz[from[i]]<sz[to[i]])continue;
		ans+=1ll*min(n-sz[to[i]],sz[to[i]])*2*l[i];
	}
	for(int i=1;i<=tot;i++)if((sz[from[i]]*2==n||sz[to[i]]*2==n)&&sz[from[i]]+sz[to[i]]>n)
	{
		printendl(ans-l[i]);
		return 0;
	}
	int cen=0,mxsz=0;
	for(int i=1;i<=n;i++)
	{
		int mx=0;
		for(int j=head[i];j;j=nxt[j])
			if(sz[to[j]]<sz[i])mx=max(mx,sz[to[j]]);
			else mx=max(mx,n-sz[i]);
		if(cen==0||mxsz>mx)
		{
			cen=i;
			mxsz=mx;
		}
	}
//	printf("centroid= %d\n",cen);
	int mn=inf;
	for(int i=head[cen];i;i=nxt[i])mn=min(mn,l[i]);
	printendl(ans-mn);
	return 0;
}

Measured memory_bytes: 8192
using System;
using System.Linq;

class Program {
    static void Main() {
        int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int a = input[0];
        int b = input[1];
        int x = input[2];
        int v = a * a * b;
        if (x * 2 == a * a * b) {
            Console.WriteLine(45);
        } else if (x * 2 > a * a * b) {
            double w = (v - x) * 2.0 / (a * a);
            Console.WriteLine(Math.Atan(w / a) * 180 / Math.PI);
        } else {
            double w = x * 2.0 / (a * b);
            Console.WriteLine(Math.Atan(b / w) * 180 / Math.PI);
        }
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
int main(){
  int i, q;
  scanf("%d", &q);
  bitset<64> bit(0);
  for(i = 0; i < q; i++){
    int query, val;
    scanf("%d", &query);
    switch(query){
      case 0:
        scanf("%d", &val);
        cout << bit.test(val) << endl;
        break;
        
      case 1:
        scanf("%d", &val);
        bit.set(val);
        break;
        
      case 2:
        scanf("%d", &val);
        bit.reset(val);
        break;
        
      case 3:
        scanf("%d", &val);
        bit.flip(val);
        break;
        
      case 4:
        cout << bit.all() << endl;
        break;
        
      case 5:
        cout << bit.any() << endl;
        break;
        
      case 6:
        cout << bit.none() << endl;
        break;
        
      case 7:
        cout << bit.count() << endl;
        break;
        
      case 8:
        cout << bit.to_ulong() << endl;
        break;
    }
  }
}


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

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double EPS = 1e-6;
const int MAX_N = 3005;

int N;
double prob[MAX_N];
double dp[MAX_N];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> prob[i];
	}

	dp[0] = 1;
	for (int i = 1; i <= N; ++i) {
		for (int j = i; j >= 0; --j) {
			dp[j] = (j == 0 ? 0 : dp[j - 1] * prob[i]) + dp[j] * (1 - prob[i]);
		}
	}

	double ans = 0;
	for (int i = 0; i <= N; ++i) {
		int tails = N - i;
		if (i > tails) ans += dp[i];
	}

	cout << fixed << setprecision(30) << ans << '\n';

	return 0;
}

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

int main() {
    double N, K;
    cin >> N >> K;
    double p = 1.0 / N;
    double sum = 0;

    for (double i = 1; i <= N; i++) {
        for (double j = 0; j < 20; j++) {
            if (i * pow(2.0, j) >= K) {
                sum += p * pow(2.0, -j);
                break;
            }
        }
    }
    printf("%.10f\n", sum);
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        int c1 = 0, c2 = 0;
        for (int x : a) {
            if (x % 4 == 0) {
                c1++;
            } else if (x % 2 == 0) {
                c2++;
            }
        }
        System.out.println((c1 + c2 / 2 >= n / 2 ? "Yes" : "No"));
    }
}

Measured memory_bytes: 48048
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int main() {
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  ll range = b - a + 1;
  ll div_c, div_d, div_cd;
  {
    ll bb = b / c;
    ll aa = a / c;
    if (a % c == 0) aa--;
    div_c = bb - aa;
  }
  {
    ll bb = b / d;
    ll aa = a / d;
    if (a % d == 0) aa--;
    div_d = bb - aa;
  }
  {
    ll lcm = c / __gcd(c,d) * d;
    ll bb = b / lcm;
    ll aa = a / lcm;
    if (a % lcm == 0) aa--;
    div_cd = bb - aa;
  }
  
  range = range - div_c - div_d + div_cd;
  cout << range << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
using namespace std;
#define int long long


signed main() {
	int n,w;
	cin >> n >> w;
	int w1[n],v[n];
	for(int i=0;i<n;i++){
		cin >> w1[i] >> v[i]; 
	}
	int dp[n+1][w+1];
	for(int i=0;i<w+1;i++){
		dp[0][i]=0;
	}
	for(int i=0;i<n+1;i++){
		dp[i][0]=0;
	}
	for(int i=1;i<n+1;i++){
		for(int j=1;j<w+1;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=w1[i-1]){
				dp[i][j]=max(dp[i][j],dp[i-1][j-w1[i-1]]+v[i-1]);
			}
		}
	}
	cout << dp[n][w];
	// your code goes here
	return 0;
}

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

int main() {
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;

  int sum = 0;

  int price1;

  if (a + b < 2 * c) {
    price1 = a + b;
  } else {
    price1 = 2 * c;
  }

  while (x != 0 && y != 0) {
    sum += price1;
    x--;
    y--;
  }

  if (x != 0) {
    if (x * a < 2 * x * c) {
      sum += x * a;
    } else {
      sum += 2 * x * c;
    }
  } else if (y != 0) {
    if (y * b < 2 * y * c) {
      sum += y * b;
    } else {
      sum += 2 * y * c;
    }
  }

  cout << sum << "\n";
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

inline int getint_mae() {
	char C = getchar_unlocked();
	int A = C - '0';
	while (isdigit(C = getchar())) A = A * 10 + C - '0';
	return A;
}

const int cm = 1 << 17;
char cn[cm], *ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[dm], *di = dn, dt;
inline void putint(int X) {
	if (X == 0) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--) *di++ = (*(C + i));
	*di++ = '\n';
}

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


	int N = getint_mae(), M = getint_mae(), Q = getint_mae();
	char S[2001][2002];
	rep(i, N + 1) S[i][0] = '0';
	rep(i, M + 1) S[0][i] = '0';
	rep1(i, N) fread_unlocked(S[i] + 1, 1, M + 1, stdin);
	int B[2001][2001], C[2001][2001], D[2001][2001];
	rep(i, N) {
		rep(j, M) {
			B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + S[i + 1][j + 1] - '0';
			C[i + 1][j + 1] = C[i + 1][j] + C[i][j + 1] - C[i][j] + ((S[i][j + 1] - '0') & (S[i + 1][j + 1] - '0'));
			D[i + 1][j + 1] = D[i + 1][j] + D[i][j + 1] - D[i][j] + ((S[i + 1][j] - '0') & (S[i + 1][j + 1] - '0'));
		}
	}

	rep(q, Q) {
		int a = getint(), b = getint(), c = getint(), d = getint();

		int kotae = B[c][d] - B[c][b - 1] - B[a - 1][d] + B[a - 1][b - 1] - C[c][d] + C[c][b - 1] + C[a][d] - C[a][b - 1] - D[c][d] + D[c][b] + D[a - 1][d] - D[a - 1][b];
		putint(kotae);

	}

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 54400
using System;
using System.Linq;
 
class DP {
    static void Main(string[] args) {
        var st = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int N = st[0];
        int W = st[1];
        var w = new int[N];
        var v = new int[N];
        for (int i = 0; i < N; i++) {
            var x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            w[i] = x[0];
            v[i] = x[1];
        }
 
        //考えうる価値の最大値
        int max_value = N * 1000 + 100;
 
        //少し大きめに配列を確保
        var dp = new long[N + 2, max_value + 10];
 
        long max_weight = 1000000000L * N + 100;
 
        //値は全て大きな値で初期化する
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= max_value; j++) {
                dp[i, j] = max_weight;
            }
        }
        dp[0, 0] = 0;
        for (int j = 1; j <= v[0]; j++) {
            dp[0, j] = w[0];
        }
 
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j <= max_value; j++) {
                long kari = max_weight;
                if (j - v[i + 1] >= 0) {
                    kari = Math.Min(kari, dp[i, j - v[i + 1]] + w[i + 1]);
                }
                kari = Math.Min(kari, dp[i, j]);
                dp[i + 1, j] = kari;
            }
        }
 
        long ans = 0;
 
        for (int j = 0; j <= max_value; j++) {
            if (dp[N - 1, j] <= W) {
                ans = j;
            }
        }
 
        Console.WriteLine(ans);
    }
}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define reps(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end()))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N;
signed main() {
    cin >> N;
    if (N == 3) { fin("2 5 63"); }
    if (N == 4) { fin("2 5 20 63"); }
    if (N == 5) { fin("2 5 20 63 90"); }
    vint a = {2, 3, 4, 8, 9, 10};
    int cnt = 0;
    while (N >= 6 && a[0] + cnt * 12 < 30000) {
        rep(i, a.size()) { cout << a[i] + cnt * 12 << " "; }
        N -= 6;
        cnt++;
    }
    reps(i, N) { cout << 6 * i << " "; }
    cout << endl;

}


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

int main(){
  int H,W;
  cin>>H>>W;
  char S[H][W];
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      char c;
      cin>>c;
      S[i][j]=c;
    }
  }

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S[i][j]=='.'){
        int ans=0;
        for(int k=i-1;k<=i+1;k++){
          for(int l=j-1;l<=j+1;l++){
            if((k!=i||l!=j)&&0<=k&&k<=H-1&&0<=l&&l<=W-1){
              if(S[k][l]=='#'){
                ans+=1;
              }
            }
          }
        }
        cout<<ans;
      }else{
        cout<<'#';
      }
    }
    cout<<endl;
  }


  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        String nn = Integer.toString(n);
        int a = Integer.parseInt(String.valueOf(nn.charAt(nn.length()-1)));
        String ans = "";
        if (a == 3) ans = "bon";
        else if (a == 0 || a == 1 || a == 6 || a == 8) {
            ans = "pon";
        }
        else {
            ans = "hon";
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 35696
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

const int mod=(int)1e9+7;
int n,m,y[1000][2];
vector<vi> e;
int deg[1000];
bool v[1000],loop[1000];

void rec(int c,int p){
	v[c]=1;
	rep(i,e[c].size())if(!v[e[c][i]]){
		rep(j,2)rep(k,2)if(abs(y[c][j])==abs(y[e[c][i]][k])){
			if(j==0)swap(y[c][0],y[c][1]);
			if(k==1)swap(y[e[c][i]][0],y[e[c][i]][1]);
		}
		rec(e[c][i],c);
	}
}
ll dp[1000][2][2];
ll calc(int c,int lv,int p,int s,int sv){
	//cerr<<"c: "<<c<<" lv: "<<lv<<" p: "<<p<<" s: "<<s<<" sv: "<<sv<<endl;
	ll &res=dp[c][lv][sv];
	if(res>=0)return res;
	v[c]=1;
	
	int nxt=e[c][p==e[c][0]?1:0];
	if(nxt==s)return res=lv?1:sv==(y[c][1]==y[nxt][0]);
	
	res=calc(nxt,y[c][1]==y[nxt][0],c,s,sv);
	if(lv)res+=calc(nxt,y[c][1]!=y[nxt][0],c,s,sv);
	res%=mod;
	return res;
}
ll dp2[1000][2];
ll calc2(int c,int lv,int p){
	//cerr<<"c: "<<c<<" lv: "<<lv<<" p: "<<p<<endl;
	ll &res=dp2[c][lv];
	if(res>=0)return res;
	v[c]=1;
	
	if(e[c].size()==1&&e[c][0]==p)return lv?2:1;
	int nxt=e[c][p==e[c][0]?1:0];
	res=calc2(nxt,y[c][1]==y[nxt][0],c);
	if(lv)res+=calc2(nxt,y[c][1]!=y[nxt][0],c);
	res%=mod;
	return res;
}
int main(){
	cin>>n>>m;
	ll ans=1;
	rep(i,m){
		cin>>y[i][0]>>y[i][1];
		if(abs(y[i][0])==abs(y[i][1])){
			if(y[i][0]!=y[i][1])ans*=2, ans%=mod;
			m--; i--;
		}
	}
	e.resize(m);
	rep(i,m)rep(j,i)rep(k,2)rep(l,2){
		if(abs(y[i][k])==abs(y[j][l])){
			e[i].pb(j); e[j].pb(i);
		}
	}
	
	rep(i,m)v[i]=0;
	rep(i,m)if(!v[i]&&e[i].size()==1)rec(i,-1);
	rep(i,m)if(!v[i])rec(i,-1);
	rep(i,m)v[i]=0;
	
	//rep(i,m)cerr<<"i: "<<i<<" : "<<y[i][0]<<" "<<y[i][1]<<" sz:"<<e[i].size()<<endl;
	
	memset(dp2,-1,sizeof(dp2));
	rep(i,m)if(e[i].size()==1&&!v[i]){
		ll tmp=calc2(i,0,-1)+calc2(i,1,-1);
		ans*=tmp; ans%=mod;
	}
	memset(dp,-1,sizeof(dp));
	rep(i,m)if(e[i].size()==2&&!v[i]){
		ll tmp=calc(i,0,-1,i,0)+calc(i,1,-1,i,1);
		ans*=tmp; ans%=mod;
	}
	rep(i,m)if(e[i].empty())ans*=3, ans%=mod;
	
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 0
def main():
    import sys
    input = sys.stdin.readline
    N, M, C = map(int, input().split())
    B = list(map(int, input().split()))
    ans = 0
    for _ in range(N):
        A = list(map(int, input().split()))
        x = C
        for i in range(M):
            x += A[i]*B[i]
        if x > 0:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

int main(void){
	int n, a;
	string s;
	bool ans = true;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> s;
		if(s == "A"){
			a++;
		}else{
			a--;
		}
		if(a<0) ans = false;
	}
	if(a != 0) ans = false;
	if(ans){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
	return 0;
}


Measured memory_bytes: 3156
import sys
import os


def calc(x, p):
    return pow(x - p, 2)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())
    X = list(map(int, sys.stdin.readline().split()))

    ret = float('inf')
    for p in range(100):
        tmp = 0
        for n in range(N):
            tmp += calc(X[n], p)
        ret = min(tmp, ret)

    print(ret)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define mod 1000000007
#define bitcount __builtin_popcountll
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<pi,int>
#define mp make_pair
int main()
{
	int i,j,k;
	int n,a,b;
	cin>>n>>a>>b;
	if(a%2==b%2)
		printf("Alice\n");
	else
		printf("Borys\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

cat pow(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pow(a, e/2, mod);
	x = x * x % mod;
	if(e&1) x = x * a % mod;
	return x;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	cat ans = 1, mod = 998244353;
	for(int i = 0; i < N; i++) {
		ans += 2*ans;
		if(ans >= mod) ans -= mod;
		if(ans >= mod) ans -= mod;
	}
	vector<cat> pow2(N+2, 1);
	for(int i = 1; i <= N+1; i++) {
		pow2[i] = 2 * pow2[i-1];
		if(pow2[i] >= mod) pow2[i] -= mod;
	}
	vector<cat> binom(N/2+1, 1), inv(N/2+1);
	for(int i = 1; i <= N/2; i++) {
		if(N/2-i < i) break;
		if(i > 2 && i%2 == 0) inv[i] = inv[2] * inv[i/2] % mod;
		else inv[i] = pow(i, mod-2, mod);
	}
	for(int i = 1; i <= N/2; i++) {
		if(N/2-i < i) binom[i] = binom[N/2-i];
		else binom[i] = binom[i-1] * (N/2-i+1) % mod * inv[i] % mod;
	}
	cat sum = 0;
	for(int nAL = 0; nAL <= N/2; nAL++) {
		ans = (ans - binom[nAL] * pow2[N/2-nAL+1] % mod * sum) % mod;
		sum = (sum + pow2[nAL] * binom[nAL]) % mod;
	}
	if(ans < 0) ans += mod;
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 156544
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

vector<vector<int>> v;

int N;
bool used[8] = {};
int temp[8];
void dfs(int level) {
	if (level == N) {
		vector<int> buf;
		for (int i = 0; i < N; i++) {
			buf.push_back(temp[i]);
		}
		v.push_back(buf);
	}
	else {
		for (int i = 0; i < N; i++) {
			if (used[i] == false) {
				used[i] = true;
				temp[level] = i;
				dfs(level + 1);
				used[i] = false;
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) { used[i] = false; }
	dfs(0);
	vector<int> a, b;
	int A = 0, B = 0;
	for (int i = 0; i < N; i++) {
		int x; cin >> x; x--;
		a.push_back(x);
	}
	for (int i = 0; i < N; i++) {
		int x; cin >> x; x--;
		b.push_back(x);
	}
	int c = 0;
	for (auto itr = v.begin(); itr != v.end(); itr++, c++) {
		bool f1 = true, f2=true;
		for (int i = 0; i < N; i++) {
			if (itr->at(i) != a[i]) { f1 = false; }
			if (itr->at(i) != b[i]) { f2 = false; }
		}
		if (f1 == true) { A = c; }
		if (f2 == true) { B = c; }
	}
	cout << abs(A - B) << endl;
	return 0;
}

Measured memory_bytes: 3256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#include<set>
using namespace std ;

#define MAXN 100007

int n ;
int a[ MAXN ] ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    int ans = 0 ;
    int f = 0 ;
    for ( int i = n - 1 ; i >= 1 ; -- i ) {
        if ( ans < f ) { ans = f ; }
        if ( a[ i ] >= a[ i + 1 ] ) {
            ++ f ;
        }
        else { f = 0 ; }
        if ( ans < f ) { ans = f ; }
    }
    if ( ans < f ) { ans = f ; }
    printf ( "%d\n" , ans ) ;
}

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



Measured memory_bytes: 640
import fractions

def lcm(x,y):
    return (x*y) // fractions.gcd(x,y)

N = int(input())
a = list(map(int,input().split()))

#aの最小公倍数を求める
lcm_t = a[0]

for j in range(1,N):
    lcm_t = lcm(lcm_t,a[j])

lcm_t = max(1,lcm_t-1)

ans = 0

for k in a:
    ans += lcm_t % k

print(ans)

Measured memory_bytes: 5344
n, k = map(int, input().split())
telport_from = {source: to for source, to in zip(range(1, n+1), map(int, input().split()))}

trajectory = [1]
visited = set((1,))
current = 1
has_loop = False
for _ in range(k):
  next_city = telport_from[current]

  trajectory.append(next_city)
  if next_city in visited:
    has_loop = True
    break
  current = next_city
  visited.add(current)

if not has_loop:
  print(next_city)
else:
  loop_start = trajectory.index(next_city)
  loop_length = (len(trajectory)) - loop_start - 1
  remain_step = (k - loop_start) % loop_length
  #print(trajectory)
  
  #print(f'{loop_start=} {loop_length=} {remain_step=}')
  # fix index
  last_city = trajectory[loop_start+remain_step]
  print(last_city)

Measured memory_bytes: 50704
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 15 + 2;
const int MAXM = 1 << 15;
const int MOD = 1000000000 + 7;

int fpow(int x, int p)
{
	int ret = 1;
	for(; p; p >>= 1, x = (long long)x * x % MOD)
		if(p & 1)
			ret = (long long)ret * x % MOD;
	return ret;
}

int n, m;
vector<int> edg[MAXN];
int cnt[MAXN][MAXM], f[MAXM];

void init()
{
	for(int i = 0; i < n; i++)
		for(int s = 0; s < (1 << n); s++)
		{
			cnt[i][s] = 1;
			for(int j = 0; j < edg[i].size(); j++)
				if((s >> edg[i][j]) & 1)
					cnt[i][s] = cnt[i][s] * 2 % MOD;
		}
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		x -= 1, y -= 1;
		edg[x].push_back(y);
	}
	init();
	f[0] = 1;
	for(int i = 1; i < (1 << n); i++)
		if(i % 4 == 0 || i % 4 == 3)
		{
			f[i] = 0;
			for(int s = (i - 1) & i; s != i; s = (s - 1) & i)
			{
				int t = i ^ s;
				if((s & 1) ^ ((s >> 1) & 1))
					continue;
				// cerr << s << endl;
				int tmp = f[s];
				for(int j = 0; j < n; j++)
					if((s >> j) & 1)
						tmp = (long long)tmp * (cnt[j][t] - 1 + MOD) % MOD;
					else if((t >> j) & 1)
						tmp = (long long)tmp * cnt[j][s] % MOD;
				f[i] = (f[i] + tmp) % MOD;
			}
			// cerr << i << ' ' << f[i] << endl;
		}

	int ans = (fpow(2, m) - f[(1 << n) - 1] + MOD) % MOD;

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 2304
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var q = new int[n].Select(_ => Console.ReadLine())
			.GroupBy(x => x)
			.GroupBy(g => g.Count(), g => g.Key)
			.OrderByDescending(g => g.Key)
			.First()
			.OrderBy(x => x);
		Console.WriteLine(string.Join("\n", q));
	}
}


Measured memory_bytes: 71528
N, M = list(map(int, input().split()))
a = [int(input()) for _ in range(M)]

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


MOD = 10 ** 9 + 7

for i in range(1, M):
  if a[i] - a[i - 1] == 1:
    print(0)
    exit()

com = comb(N, MOD)
ans = 1
x = 0
a = a + [N + 1]

for i in a:
  t = i - 1 - x
  at = 0
  for j in range(t // 2 + 1):
    k = t - j
    at = at + com.com(k, j) % MOD
  ans = ans * at % MOD
  x = i + 1
  

print(ans)

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

// GCD, LCM
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;}

ll f(ll x,ll A,ll B){
    return floor(A*x/B) - A*floor(x/B);
}

int main()
{
    ll A,B,N,M=0,temp;
    cin>>A>>B>>N;


    if(N>=B){
        M=f(B-1,A,B);
    }else{
        M=f(N,A,B);
    }
    
    cout<<M<<endl;

    return 0;
}

Measured memory_bytes: 3592
from collections import defaultdict

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 20000
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])

    for k in d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

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

        #define ll long long
        #define pb push_back
        #define printV(v) for(int i=0;i<(int)v.size();i++){cout << v[i]<< " ";} cout << endl
        #define printRev(v) for(int i=(int)v.size()-1;i >= 0;i--){cout << v[i] << " ";} cout << endl
        #define sortV(v) sort(v.begin(),v.end())
        #define revV(v) reverse(v.begin(),v.end())
    

        ll a,b,c,d,e,f,g,n,m,k,t,x,h,w,p,q,y;
        string str = "";
        ll mod = 1e9 + 7;
        const int N = 3009;
        ll dp0[N][N];
        ll dp1[N][N];
        ll dp2[N][N];
        ll dp3[N][N];
        ll grid[N][N];
        
        void solve(){
            ll R,C;
            cin >> R >> C >> k;
            for(int i=1;i<=k;i++){
                cin >> a >> b >> x;
                grid[a][b] = x;
            }
           

            ll answer = 0;

            
            for(int i=1; i <= R; i++){
                for(int ii=1; ii<=C; ii++){
                    dp0[i][ii] = max(dp0[i][ii],max(max(dp0[i-1][ii],dp1[i-1][ii]), max(dp2[i-1][ii], dp3[i-1][ii])));
                }
                for(int j=1; j<=C;j++){
                    dp1[i][j] = max(max(dp1[i][j-1],dp1[i][j]), grid[i][j] + dp0[i][j]);
                    dp2[i][j] = max(max(dp2[i][j-1],dp2[i][j]), grid[i][j] + dp1[i][j-1]);
                    dp3[i][j] = max(max(dp3[i][j-1], dp3[i][j]), grid[i][j] + dp2[i][j-1]);
                }
            }

                for(int i=1;i<=R;i++){
                    for(int j=1;j<=C;j++){
                        answer = max(answer, max(dp0[i][j], dp1[i][j]));
                        answer = max(answer, max(dp2[i][j], dp3[i][j]));
                    }
                }
                
                

            
/*
                for(int i=1;i<=R;i++){
                    for(int j=1;j<=C;j++){
                        cout << dp0[i][j] << " ";
                        //cout << " (" << i << "," << j << ") "; 
                    }cout << endl;
                }
            
*/






            cout << answer << endl;

            
            
        }



        int main(){
            ios_base::sync_with_stdio(false);

            
          


            int cases = 1;
            //cin >> cases;

            while(cases--) solve();
            return 0;

        }


Measured memory_bytes: 356120
from bisect import bisect_right
n,m=map(int,input().split())
p,y=[],[]
l={}
for i in range(m):
 p_,y_=map(int,input().split())
 p.append(p_)
 y.append(y_)
 if not p_ in l:l[p_] = []
 l[p_].append(y_)
for i in l:
 l[i].sort()
for i in range(m):
 print(str(p[i]).zfill(6)+str(bisect_right(l[p[i]],y[i])).zfill(6))

Measured memory_bytes: 30436
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
#define mod 1000000007
#define aint(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(int)a;i<(int)b;i++)
#define revrep(i,a,b) for(i=(int)a;i>=(int)b;i--)
#define ii pair<int,int>
#define pb push_back
#define f first
#define s second
#define ll long long int
#define vi vector<int>
#define rs resize
int main()
{  std::ios::sync_with_stdio(false);
   ll n,i,sum=0,ans,h;
   cin>>n;
   ll a[n];
   rep(i,0,n)
     cin>>a[i],sum+=a[i];
   if(sum%10 !=0)
    cout<<sum;
   else
   {
     ans =-mod;
     rep(i,0,n)
     {
        h = sum - a[i];
        if(h%10 ==0)
         h = 0;
        ans = max(ans,h);
     }
     cout<<ans;
   }
   return 0;
}


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

using namespace std;

long long a[100];

int main()
{
	int n = 50;
	long long k;
	cin >> k;
	long long tmp = k / n;
	k %= n;
	for (int i = 1; i <= n; ++i) a[i] = n - 1 + tmp;
	for (int i = 1; i <= n - k; ++i) a[i] -= k;
	for (int i = n - k + 1; i <= n; ++i) a[i] += n - k + 1;
	cout << n << endl;
	for (int i = 1; i <= n; ++i) cout << a[i] << " "; cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
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 int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}
 

void solve() {
    int n, k;
    cin >> n >> k;
    vector<pair<ll, int>> s(n);
    int t;
    ll d;
    REP(i, n) {
        cin >> t >> d;
        s[i] = make_pair(d, t);
    }
    sort(ALL(s));
    reverse(ALL(s));
    map<int, ll> v;
    deque<ll> q;
    ll tmp = 0;
    REP(i, k) {
        if (v.count(s[i].second) == 0) {
            v[s[i].second] = s[i].first;
        } else {
            q.push_front(s[i].first);
        }
        tmp += s[i].first;
    }
    ll x = sz(v);
    tmp += x * x;
    ll ans = tmp;
    FOR(i, k, n) {
        if (q.empty()) break;
        if (v.count(s[i].second) != 0) continue;
        ll r = q.front();
        tmp = tmp - r - (x * x) + s[i].first + ((x + 1) * (x + 1));
        q.pop_front();
        v[s[i].second] = s[i].first;
        x++;
        chmax(ans, tmp);
    }
    cout << ans << EOL;
}


Measured memory_bytes: 6016
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define frw(i, a, b) for(int i = a; i < b; i++)
#define fi first
#define se second
#define pb push_back
#define in insert
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) int(a.size())
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define vpii vector<pii>
#define vpiii vector<piii>
#define vpll vector<pll>
#define vplll vector<plll>
#define mod 1000000007

int modInverse(ll a, ll m) 
{ 
    ll m0 = m; 
    ll y = 0, x = 1; 
    if (m == 1) 
      return 0; 
    while (a > 1) 
    { 
        ll q = a / m; 
        ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    } 
    if (x < 0) 
       x += m0; 
    return x; 
} 

int main()
{
	int n,p;
	cin>>n>>p;
	string s;
	cin>>s;
	ll ans=0;
	map<ll,ll>m;
	m[0]++;
	ll b=1;
	ll nu=0;
	if(p==2||p==5)
	{
		for(int i=0;i<n;i++)
		{
			if((s[i]-'0')%p==0)
				ans+=i+1;
		}
	}
	else
	{
		for(int i=n-1;i>=0;i--)
		{
			nu=(nu+(s[i]-'0')*b)%p;
			ans+=m[nu];
			m[nu]++;
			b=(b*10)%p;
		}
	}
	cout<<ans;
	
	
}

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

using namespace std;

typedef pair<int, int> pii;
#define x first
#define y second

const int maxn = 2e5 + 20;

int n, m;
vector<pii> adj[maxn];
int bio[maxn];
int dsu[maxn];
map<int, int> loc;

int dsu_find(int x) {
//    if(x == dsu[x])
        return x;
    return dsu[x] = dsu_find(dsu[x]);
}

void dsu_merge(int x, int y) {
    x = dsu[x];
    y = dsu[y];

    if(x != y) {
        if(rand() & 1)
            swap(x, y);
        dsu[x] = y;
    }
}

bool dfs(int u, int par) {
    int v = dsu_find(u);
    bio[v] = 1;

    bool ret = false;

    for(pii e : adj[v]) {
        int w = dsu_find(e.x);

        if(w != dsu_find(par)) {
            if(bio[w] == 0) {
                loc[w] = loc[v] + e.y;
                ret |= dfs(w, v);
            } else if(bio[w] == 1) {
                if(loc[w] != loc[v] + e.y) {
//                    cout << "problem " << u << ' ' << w << endl << loc[w] << ' ' << loc[u] << ' ' << e.y << endl;
                    return true;
                }
            }
        }
    }

    return ret;
}

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

    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        dsu[i] = i;
    }

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

        if(d >= 0) {
            adj[u].push_back(pii(v,  d));
            adj[v].push_back(pii(u, -d));
        } else {
            dsu_merge(u, v);
        }
    }

    for(int i = 1; i <= n; i++) {
        int j = dsu_find(i);

        if(!bio[j]) {
            loc[j] = 0;

            if(dfs(j, 0)) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 24064