akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<unordered_map>
#define ll long long
using namespace std;
#define sd(n) scanf("%d",&n)
#define clr(a) memset(a,0,sizeof(a))
int h[110];
int main(){int sum=0;int a;
int k;cin>>k;for(int i=1;i<=k;++i){
	cin>>a;sum+=a;h[i]=a;
}
int d=sum/k;int e=sum/k+1;int r=sum/k-1;
if(sum-d*k>e*k-sum)d=e;if(abs(sum-d*k)>abs(sum-r*k))d=r;
sum=0;
for(int i=1;i<=k;++i){
	sum+=pow(h[i]-d,2);
}
cout<<sum<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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







int main(){
    int N; std::cin >> N;
    std::cout << N*(N-1)/2 - N/2 << "\n";
    for(int i(1); i <= N; ++i){
        for(int j(i+1); j <= N; ++j){
            if(N % 2){//奇数
                if(i + j == N) continue;
            }else{
                if(i + j == N+1) continue;
            }
            std::cout << i << " " << j << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

int main(){
  int N,A,B;
  cin>>N>>A>>B;
  string S;
  cin>>S;
  int X=1;
  int C=1;
  rep(i,N){
    if(S[i]=='a'){
      if(C<=A+B){
        cout<<"Yes"<<endl;
        C++;
      }else cout<<"No"<<endl;
    }else if(S[i]=='b'){
      if(C<=A+B&&X<=B){
        cout<<"Yes"<<endl;
        C++;
        X++;
      }else cout<<"No"<<endl;
    }else cout<<"No"<<endl;
  }
}

Measured memory_bytes: 896
import sys
input=sys.stdin.readline
h,w,m=map(int,input().split())
p=[0]*h
q=[0]*w
lis=set()
for i in range(m):
	a,b=map(int,input().split())
	p[a-1]+=1
	q[b-1]+=1
	lis.add(10**6*(a-1)+b-1)
P=max(p)
Q=max(q)
r=[]
l=[]
for i in range(h):
	if p[i]==P:
		r.append(i)
for i in range(w):
	if q[i]==Q:
		l.append(i)
if len(r)*len(l)>m:
	print(P+Q)
	exit()
f=0
for x in r:
	for y in l:
		if x*10**6+y in lis:
			continue
		else:
			f=1
			break
print(P+Q-1+f)



Measured memory_bytes: 157244
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 1010101010101010;
const int INF = 1010101010;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(){
  int n,m,Q; cin>>n>>m>>Q;
  vvi x(n+1,vi(n+1));
  rep(i,m){
    int l,r; cin>>l>>r;
    x[l][r]++;
  }
  vvi c(n+1,vi(n+1));
  //rep(i,n)rep(j,n) c[i+1][j+1]+=c[i+1][j]+x[i+1][j+1];
  rep(i,n)rep(j,n) c[i+1][j+1]+=c[i+1][j]+c[i][j+1]-c[i][j]+x[i+1][j+1];
  rep(i,Q){
    int p,q; cin>>p>>q;
    int ans=0;
    //for(int j=p;j<q+1;j++) ans+=c[j][q]-c[j][p-1];
    ans=c[q][q]-c[p-1][q]-c[q][p-1]+c[p-1][p-1];
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 5600
#include<cstdio>
#define buf 1000
using namespace std;

int Search(int sum,int w);

int main(void){
	int num,sum,i,n,x,y,h,w;
	char str[buf];

	for( ; ; ){
		fgets(str,sizeof(str),stdin);
		sscanf(str,"%d",&n);
		if(n==0) break; sum=0; num=0;
		for(i=0;i<n;i++){
			fgets(str,sizeof(str),stdin);
			sscanf(str,"%d %d %d %d",&x,&y,&h,&w);
			sum=x+y+h;
			num+=Search(sum,w);
		}
		printf("%d\n",num);
	}
	return 0;
}

int Search(int sum,int w){
	int num;

	if(sum<=60 && w<=2)        num=600;
	else if(sum<=80 && w<=5)   num=800;
	else if(sum<=100 && w<=10) num=1000;
	else if(sum<=120 && w<=15) num=1200;
	else if(sum<=140 && w<=20) num=1400;
	else if(sum<=160 && w<=25) num=1600;
	else if(sum>160 || w>25)   num=0;

	return num;
}

Measured memory_bytes: 2608
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define REPW(i,n) for(i=0;i<(int)(n);++i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    int n;
    cin>>n;
    cout<<n*800-(n/15)*200<<endl;
    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 < (int)(n); i++)
const int MOD = 1000000007;
const long long INF = 1LL << 60;
using Graph = vector<vector<ll>>;
Graph G;

ll ans = 0;
ll n, m;
int dfs(int start, vector<int> houmon)
{
    houmon[start] = 1;
    ll tmp = 0;
    rep(i, n)
    {
        tmp += houmon[i];
    }
    if (tmp == n)
    {
        ans++;
        return 0;
    }
    else
    {
        for (auto g : G[start])
        {
            if (houmon[g] == 0)
            {
                dfs(g, houmon);
            }
        }
    }
    return 0;
}

int main()
{

    cin >> n >> m;
    G.resize(n);
    rep(i, m)
    {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<int> houmon(n); //0で未訪問
    dfs(0, houmon);
    cout << ans << endl;
}

Measured memory_bytes: 3620
# 0123の周期でXORはリセットされるため剰余だけ考える
def solve(x):
    if x % 4 == 3:
        return 0
    elif x % 4 == 0:
        return x
    elif x % 4 == 1:
        return x ^ (x - 1)
    elif x % 4 == 2:
        return x ^ (x - 1) ^ (x - 2)


a, b = map(int, input().split())


print(solve(a - 1) ^ solve(b))

Measured memory_bytes: 9192
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

a,b,c = inm()
print('Yes' if a+b<c and 4*a*b<(c-a-b)**2 else 'No')


Measured memory_bytes: 38256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int sum[1000005],val[1000005];
ll ans;
int n,a[200005];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
vector<int>d[1000005];
int main(){
	scanf("%d",&n);
	rep(i,n) scanf("%d",&a[i]);
	for(int i=1;i<=1000000;i++) for(int j=i;j<=1000000;j+=i) d[j].pb(i);
	for(int ii=n-1;ii>=0;ii--){
		vector<int>&dv = d[a[ii]];
		rep(i,dv.size()){
		        val[dv[i]] += (int)(1LL*sum[dv[i]]*a[ii]%mod);
		        if(val[dv[i]] >= mod) val[dv[i]] -= mod;
		        sum[dv[i]] += a[ii];
		        if(sum[dv[i]] >= mod) sum[dv[i]] -= mod;
		}
	}
	for(int i=1000000;i>=1;i--){
	    for(int j=2*i;j<=1000000;j+=i){
	        val[i] -= val[j];
        	if(val[i] < 0) val[i] += mod;
	    }
	    ans += 1LL * val[i] * modpow(1LL*i,mod-2) % mod;
	}
	cout << (ans%mod+mod)%mod << endl;
}


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

using namespace std;

#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){std::cerr << name << " = " << arg1 << endl;}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

double w, h, x, y;

int main()
{
	IOS;
	cin >> w >> h >> x >> y;
	cout << fixed << setprecision(10);
	cout << w * h * 0.5 << ' ' << (x * 2 == w && y * 2 == h) << endl;
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using std::swap;
using std::max;
using std::min;
using std::sort;

typedef long long LL;

int n;

int main() {
  scanf("%d", &n);
  printf("%d\n", n * n * n);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define long long long
using namespace std;
const int N=3e3;
int aa[N+2],n;long dp[N+2][N+2];
long dfs(int i,int j)
{
  if(i>j)return 0;
  if(dp[i][j]!=-1)return dp[i][j];
  return dp[i][j]=max(aa[i]-dfs(i+1,j),aa[j]-dfs(i,j-1));
}
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  cin>>n;for(int i=1;i<=n;i++)cin>>aa[i];
  memset(dp,-1,sizeof(dp));
  cout<<dfs(1,n)<<endl;
  return 0;
}

Measured memory_bytes: 70912
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define loop(k) rep(author_is_masa,k)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const long long INF = 1e18+10;

/*--------------------------------------------------------------------*/
signed main(){
	int n;
	cin>>n;
	vi a(n);
	rep(i,n)cin>>a[i];
	int ans=0;
	int top=-1;
	rep(i,n){
		if(i>0) {
			ans+=max(0ll,a[i-1]-a[i]);
			chmax(a[i],a[i-1]);		
		}
		chmax(top,a[i])
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 4752
#include<stdio.h>
#include<math.h>

typedef struct{
  double x;
  double y;
} P;

void kock(int n, P p1, P p2){
  P s,t,u;
  
  if (n == 0) return;

  s.x = ((2*p1.x)+(1*p2.x))/3;
  s.y = ((2*p1.y)+(1*p2.y))/3;
  t.x = ((1*p1.x)+(2*p2.x))/3;
  t.y = ((1*p1.y)+(2*p2.y))/3;

  u.x = (t.x - s.x)*cos(M_PI/3)-(t.y - s.y)*sin(M_PI/3)+s.x;
  u.y = (t.x - s.x)*sin(M_PI/3)+(t.y - s.y)*cos(M_PI/3)+s.y;
  
  kock(n-1,p1,s);
  printf("%.8f %.8f\n",s.x,s.y);
  
  kock(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);

  kock(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  
  kock(n-1,t,p2);
}

int main(){
  int n;
  P p1 = {0,0};
  P p2 = {100,0};

  scanf("%d",&n);
  
 printf("%.8f %.8f\n",p1.x,p1.y);
 
  kock(n,p1,p2);
  
 printf("%.8f %.8f\n",p2.x,p2.y);
 
  return 0;

}



Measured memory_bytes: 2108
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int>V[MAX];
int color[MAX];

void dfs(int r, int c) {
	stack<int>S;
	S.push(r);
	color[r] = c;
	while (!S.empty()) {
		int u = S.top(); S.pop();
		for (int i = 0; i < V[u].size(); i++) {
			int v = V[u][i];
			if (color[v] == NIL) {
				color[v] = c;
				S.push(v);
			}
		}
	}
}

void assignColor() {
	int id = 1;
	for (int i = 0; i < n; i++) {
		color[i] = NIL;
	}
	for (int u = 0; u < n; u++) {
		if (color[u] == NIL) {
			dfs(u, id++);
		}
	}
}
int main() {
	int s, t, m, q;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> s >> t;
		V[s].push_back(t);
		V[t].push_back(s);
	}
	assignColor();
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> s >> t;
		if (color[s] == color[t]) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 9032
from decimal import Decimal
n,m = map(int,input().split())
A = list(map(int,input().split()))
border = float(sum(A)*(1/(4*m)))
border2 = str(border)
border3 = Decimal(border2)
ans = 0
judge = 0
for i in range(n):
  if A[i] >= border3:
    ans+=1
if ans >= m:
  print("Yes")
else:
  print("No")

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

int main(){
  string s;
  
  cin >> s;
  int count = 0;
  for (int i = 0; i < s.size(); i++){
    if (s.at(i) == '1'){
      count++;
    }
  }
  cout << count << endl;
}

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

//ほんとD全然わからなかったし大混乱だった

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


	int N;
	cin >> N;
	int L[2001] = {};
	rep(i, N) {
		int l;
		cin >> l;
		L[l]++;
	}
	int S[2002] = {};
	rep1(i, 2001) S[i] = S[i - 1] + L[i];

	int kotae = 0;
	for (int ab = 2; ab <= 2000; ab++) {
		for (int a = 1; a + a < ab; a++) {
			int b = ab - a;
			int kazu = L[a] * L[b];
			kotae += kazu * (S[ab - 1] - S[b]) + L[b] * (L[b] - 1) / 2 * L[a];
		}
		if (ab % 2 == 0) {
			int a = ab / 2;
			int kazu = L[a] * (L[a] - 1) / 2;
			kotae += kazu * (S[ab - 1] - S[a]) + (ll)L[a] * (L[a] - 1) * (L[a] - 2) / 6;
		}
	}

	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
        v = [e] * (size * 2 - 1)
        for i in range(n):
            # size-1個の上段の次、size個目からn個が元の配列の代入位置
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  # 元の配列の長さ
        self.size = size  # 元の配列サイズ以上の最小の二冪 == 最下段の要素数
        self.v = v  # Segtreeの配列
        self.e = e  # 初期値
        self.f = f  # 比較関数

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  # 最下段のindexに変更する
        self.v[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        # 区間が重ならない

        if a <= l and r <= b:
            return self.v[k]
        # 完全被覆

        m = (l + r) // 2
        return self.f(self.get(a, b, k * 2 + 1, l, m), self.get(a, b, k * 2 + 2, m, r))
        # 部分被覆


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        seg.update(h[i], seg.get(0, h[i]) + a[i])
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return seg.get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
# classやめた方が遅かった
# 比較関数minがグローバルにあるから、遅くなっていた？



Measured memory_bytes: 126588
#include<iostream>
using namespace std;
int main() {
	int a, b;
	int i = 0;
	while (cin >> a >> b) {
	a = a + b;
		if (a != 0) {
			while (a > 0) {
				a = a / 10;
				i++;
			}
		}
		else if (a == 0) {
			i = 1;
		}
		cout << i << endl;
		i = 0;
	}
}

Measured memory_bytes: 1160
#import sys
#input = sys.stdin.readline
from itertools import accumulate
Q = 10**9+7

def getFactorials(N):
    ret = [0]*(N+1)
    ret[0] = 1
    for i in range(1, N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def getInv(N):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

def getCmb(N):
    inv = getInv(N)
    nCr = [1] * (N + 1)
    for i in range(1, N + 1):
        nCr[i] = (nCr[i - 1] * (N - i + 1) * inv[i]) % Q
    return nCr


def main():
    N = int( input())
    X = list( map( int, input().split()))
    if N == 2:
        print(X[0])
        return
    factorials = getFactorials(N)
    combs = getCmb(N-1)
    accX = list( accumulate(X))
    # print(accX)
    ans = 0
    for i in range(N-1):
        z = X[N-1] - X[N-2-i]
        c = factorials[N-2-i]*combs[i+1]%Q*factorials[i]%Q
        ans += z*c%Q
        ans %= Q
        # print(i, "hashi", z, c, z*c)
        if i == N-2:
            continue
        x = (accX[N-1] - accX[i]) - (accX[N-2-i]) - z
        y = factorials[N-3-i]*combs[i+2]%Q*factorials[i]%Q
        # print(i, x, y)
        ans += x*y%Q
        ans %= Q
        # (N-k-1)!*C(N-1,k)*(k-2)!
    print(ans)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 26992
#define _CRT_SECURE_NO_WARNINGS // #pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <sstream>
#include <cmath>
using namespace std; 

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()

typedef pair<int, int> Pii;
typedef vector<int> V;
typedef long long ll;
const int inf = 1e9;
const int mod = 1e9 + 7;

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

int main()
{
	ll N, X;
	cin >> N >> X;

	cout << 3*(N - gcd(N,X)) << endl;

	return 0;
}

Measured memory_bytes: 256
/*---------------------------------- NEVER GIVE UP --------------------------------------------*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pii;
typedef tree<ll, null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fastt ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug1(x) cerr<<#x<<" : "<<x<<endl
#define debug2(x,y) cerr<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl
#define debug3(x,y,z) cerr<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<" "<<#z<<" : "<<z<<endl

const ll modd=1e9+7;
const ll inf=1e18;

ll poww(ll a,ll b){
  ll ans=1;
  while(b){
    if(b&1LL) ans=(ans*a);
    a=(a*a);
    b=b>>1LL;
  }
  return ans;
}

/*    
         -> mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
         -> cout<<"Case #"<<casee<<": "<<ans<<endl; // for google kickstart

*/

/*-----------------------------------------------------------------------------------------------*/

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

   if(k == 1){
     cout<<0<<endl;
     return  0;
   }

   cout<<(n-k)<<endl;
 
   return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stdio.h>
#include<deque>
#include<map>
#include<queue>
#include<cmath>

typedef long long ll;

#define debug(x) cout << #x << '=' << x << endl;
#define debug_arr(a, n) for(ll i = 0; i < n; i++)cout << a[i] << ' '
#define inf 100000000000
#define loop(i,n) for(ll i = 0; i < n; i++)
#define graph vector<vector<ll>>
#define P pair<ll,ll>

using namespace std;

int mod = 1000000007;
struct acgt{
    int ans[4][4][4]={{{0}}};

    int sum(){
        int result = 0;
        loop(i,4){
            loop(j,4){
                loop(k,4){
                    if(i == 2 && j == 0 && k == 1) continue;
                    if(i == 0 && j == 1 && k == 2) continue;
                    if(i == 0 && j == 2 && k == 1) continue;
                    result += ans[i][j][k];
                    result %= mod;
                }
            }
        }

        return result;
    };
};


acgt three(){
    acgt tmp = acgt();
    loop(i,4){
        loop(j,4){
            loop(k,4){
                if(i == 2 && j == 0 && k == 1) continue;
                if(i == 0 && j == 1 && k == 2) continue;
                if(i == 0 && j == 2 && k == 1) continue;
                tmp.ans[i][j][k] = 1;
            }
        }
    }

    return tmp;
}

acgt dp(acgt prev){
    acgt newAcgt = acgt();
    loop(i,4){
        loop(j,4){
            loop(k,4){
                loop(l,4){
                    if(j == 2 && k == 0 && l == 1) continue;
                    if(j == 0 && k == 1 && l == 2) continue;
                    if(j == 0 && k == 2 && l == 1) continue;
                    if(i == 0 && j == 2 && l == 1) continue;
                    if(i == 0 && k == 2 && l == 1) continue;
                    newAcgt.ans[j][k][l] += prev.ans[i][j][k];
                    newAcgt.ans[j][k][l] %= mod;
                }
            }
        }
    }
    return newAcgt;
}

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

    acgt tmp = three();
    if(n == 3){
        cout << tmp.sum() << endl;
        return 0;
    }

    for(int i = 4; i <= n; i++){
        tmp = dp(tmp);
    }

    cout << tmp.sum() << endl;
    return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
using namespace std;

//ABC130 B
int main() {
	int N, X;
	cin >> N >> X;
	int A[200];
	for (int i=0; i<N; i++) {
		cin >> A[i];
	}

	int cnt = 1;
	int pos = 0;
	for (int i=0; i<N; i++) {
		pos += A[i];
		if (pos <= X) {
			cnt++;
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll h,w,ans=0,num;
    cin>>w>>h;
    ll p[w],q[h];
    for(int i=0;i<w;i++){
        cin>>p[i];
        ans+=p[i];
    }
    for(int i=0;i<h;i++){
        cin>>q[i];
        ans+=q[i];
    }
    sort(p,p+w);
    sort(q,q+h);
    ll ps[w+1],qs[h+1];
    ps[0]=qs[0]=0;
    for(int i=1;i<=w;i++){
        ps[i]=ps[i-1]+p[i-1];
    }
    for(int i=0;i<h;i++){
        num=(lower_bound(p,p+w,q[i])-p);
        ans+=(w-num)*q[i]+ps[num];
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main() {
	ll x, y; cin >> x >> y;

	ll cnt = 0;
	while (x <= y) {
		x *= 2;
		cnt++;
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cstdio>
#include<string.h>
#include<cmath>
int lst[110] = {1,2,4,8,16,32,64,128};
int main() {
	int n;
	int ans;
	cin >> n;
	for (int i = 0; i < 10; i++) {
		if (n >= lst[i])ans = lst[i];
		else break;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3640
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner scn=new Scanner(System.in);
    String s=scn.next();
    if(Character.isUpperCase(s.charAt(0))) {
  	  	System.out.println("A");
	}else {
    	System.out.println("a");
	}
  }
}

Measured memory_bytes: 35720
<?php
  $n = trim(fgets(STDIN));
  for($i=0; $i<3; $i++){
      if($n[$i] == 1){
          $n[$i] = 9;
      }else if($n[$i] == 9){
          $n[$i] = 1;
      }
  }
  echo $n;

Measured memory_bytes: 4856
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
#include <map>
#include <climits>
#include <bitset>
using namespace std;
#define MATH_PI 3.14159265358979323846
inline bool IsAddable(int iNum, int iLBound, int iUBound){
	int iSum = 0;
	while (iNum){
		iSum += iNum % 10;
		iNum /= 10;
	}
	return (iLBound <= iSum && iSum <= iUBound);
}
int main(){
	ios::sync_with_stdio(false);
	int iEnd, iLB, iUB;
	cin >> iEnd >> iLB >> iUB;
	register int i;
	register long long iSum = 0;
	for (i = 1; i <= iEnd; ++i){
		if (IsAddable(i, iLB, iUB))
			iSum += i;
	}
	cout << iSum << endl;
endapp:
	//system("pause > nul");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define all(cont) cont.begin(), cont.end()
#define unique(a)  sort(all(a)) , (a).erase(unique((a).begin(), (a).end()),(a).end())
#define rall(cont) cont.rbegin(), cont.rend()
#define sz(x) (int)(x).size()
#define fastio          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define PB push_back
#define endl "\n"
#define F first
#define S second
#define mod 1000000007
const int N = 2e5 + 5;
#define PI acos(-1.0)
typedef long long ll;
#define int long long
typedef long double ld;
typedef vector<int> VI;
inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x; }
inline ll sub(ll a, ll b) { if (a < b)swap(a, b); return (((a%mod) - (b%mod) + mod) % mod); }
inline ll mul(ll x, ll y) { return (x%mod * 1ll * y%mod) % mod; }
inline ll pwr(ll a, ll b) { ll x = 1 % mod; while (b) { if (b & 1) x = mul(x, a); a = mul(a, a); b >>= 1; }return x % mod; }
inline ll inv(ll a) { return pwr(a, mod - 2) % mod; }
ll gcd(ll a, ll b) { if (!a)return b % mod; return gcd(b%a, a) % mod; }
#define debug(x) cout << #x << " = " << x << endl;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
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...);
}
#define in(container) for (auto &it : container) cin>>it;
#define out(container) for (auto it : container){ cout << it << " "; cout << endl;}
vector<string>ans;
void recur(int curr, int n,string s) {
	if (curr == n ) {
		ans.PB(s);
		return;
	}
	if (sz(s) == 0) {
		recur(curr + 1, n, "a");
		
	}
	else
	{
		string p = s;
		sort(all(p));
		for (int i = 0; i <= (int)(p[sz(p) - 1] + 1 - 'a'); i++) {
			string s1;
			s1 = s + (char)(i + 'a');
			recur(curr + 1, n, s1);
		}
	}

}
signed main()
{
	fastio;
	int n;
	cin >> n;
	string emp="";
	recur(0,n,emp);
	sort(all(ans));
	out(ans);

}


Measured memory_bytes: 7924
import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    T,A = map(int, input().split())
    HS = list(map(int, input().split()))
    temps = [T-h*0.006 for h in HS]

    ans = 0
    tmp = float('inf')
    for idx, temp in enumerate(temps):
        if abs(A-temp) < tmp:
            ans = idx+1
            tmp = abs(A-temp)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 4080
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
typedef long long int ll;
using namespace std;
#define P 1000000007
#define rep(i,n) for(i=0;i<n;++i)
#define repp(i,a,n) for(i=a;i<n;++i)
#define repr(i,a,n) for(i=a;i>=n;--i)

ll binpowmod(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll modInverse(ll n, ll p)
{
    return binpowmod(n, p-2, p);
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,f,t,k,w,j;
    cin >> n >> w;
    pair<ll,ll> v[n+1];
    repp(i,1,n+1) cin >> v[i].first >> v[i].second;
    ll dp[n+1][w+1];
    memset(dp,0,sizeof(dp));
    repp(i,1,n+1)
    {
        repp(j,1,w+1)
        {
           dp[i][j]=dp[i-1][j];
           if(v[i].first<=j) dp[i][j]=std::max(dp[i][j],v[i].second+dp[i-1][j-v[i].first]) ;
           //cout << dp[i][j] << " " ;
        }
        //cout << endl ;
    }
    cout << dp[n][w];
    return 0;
}

Measured memory_bytes: 79232
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(20)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define test int t; cin >> t; while(t--)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;

void solve() {
	int n, k;
	cin >> n >> k;
	vi v(n);
	rep(i, 0, n - 1) cin >> v[i];
	sort(all(v));
	int ans = 0;
	rep(i, 0, min(n - 1, k - 1))
	ans += v[i];
	cout << ans;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// test
	solve();

	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define repi(i, x) \
	for (auto i = (x).begin(), i##_fin = (x).end(); i != i##_fin; i++)
#define all(x) (x).begin(), (x).end()
#define input(array) \
	repi(array##_itr, array) { cin >> *(array##_itr); }
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int, int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long, long long> P;
typedef vector<P> VP;
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 INFLL = 1LL << 50;
const int INF         = 1 << 30;
const double PI       = acos(-1);
int main() {
	int a, b, q;
	ll ans = 0LL;
	cin >> a >> b >> q;
	V s(a + 2,0LL);
	V t(b + 2,0LL);
	V x(q);
	rep(i, a) { cin >> s[i + 1]; }
	rep(i, b) { cin >> t[i + 1]; }
	rep(i, q) { cin >> x[i]; }
	s[0] = -INFLL;
	s[a+1] = INFLL;
	t[0] = -INFLL;
	t[b+1] = INFLL;
	//repi(itr, s) { clog << *itr << endl; }
	ll ter1[2];
	auto bef = s.begin();
	auto bef2 = t.begin();
	ll ter2[2];
	ll cnt              = 0LL;
	rep(i, q) {
		ans     = INFLL;
		bef     = lower_bound(all(s), x[i]);
	//	clog << (*bef) << endl;
	//	clog << (bef == s.end()) << endl;
		ter1[0] = *bef;
		bef     = upper_bound(all(s), x[i]);
	//	clog << (*bef) << endl;
		if (bef != s.begin()) {
			bef--;
		}
		ter1[1] = *bef;
	//	clog << "dis::"<<distance(s.begin(), bef) << endl;

		bef2 = lower_bound(all(t), x[i]);
	//	clog << (*bef) << endl;
	//	clog << (bef == t.end()) << endl;
		ter2[0] = *bef2;
		bef2     = upper_bound(all(t), x[i]);
	//	clog << (*bef) << endl;
		if (bef2 != t.begin()) {
			bef2--;
		}
		ter2[1] = *bef2;
	//	clog << "dis::" << distance(s.begin(), bef) << endl;
		rep(A, 2) {
			rep(B, 2) {
				if (abs(ter1[A] )== INFLL or abs(ter2[B]) == INFLL) continue;
				cnt = 0LL;
				if (((ter1[A]) > x[i]) == ((ter2[B]) > x[i])) {
					cnt = max(abs(x[i] - (ter1[A])), abs(x[i] - (ter2[B])));
				} else {
					cnt = abs(x[i] - (ter1[A])) + abs(x[i] - (ter2[B])) +
					      min(abs(x[i] - (ter1[A])) , abs(x[i] - (ter2[B])));
				}
			//	clog << ter1[A] << " " << ter2[B] << " " << x[i] << "::" << cnt
			//	     << endl;
				chmin(ans, cnt);
			}
		}
		//clog << "out;;";
		cout << ans << endl;
	}
	//	cout << ans << endl;
}

Measured memory_bytes: 5644
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007

using namespace std;
using ll = long long;
using ldb = long double;


int main() {
	ll N; cin >> N;
	map<ll, ll> mp;
	vector<ll> sums(1001);
	for (int i = 1; i <= 1000; i++) {
		sums[i] = sums[i - 1] + i;
	}
	for (long long i = 2; i <= sqrt(N); i++) {
		while (N % i == 0) {
			N /= i;
			mp[i]++;
		}	
	}
	if (N > 1)mp[N]++;
	ll ans = 0;
	for (auto x : mp) {
		for (int i = 1; i <= 1000; i++) {
			if (mp[x.first] < sums[i]) {
				ans += i - 1;
				break;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;



int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  set<int> s;
  rep(i,m) {
    int a,b;
    scanf("%d%d",&a,&b);
    int x = -1;
    if (a == 1) x = b;
    else if (b == n) x = a;
    if (x == -1) continue;
    if (s.count(x)) {
      cout<<"POSSIBLE"<<endl;
      return 0;
    }
    s.insert(x);
  }
  cout<<"IMPOSSIBLE"<<endl;
  return 0;
}






















Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	string s;
	cin>>s;
	bool f=1;
	for(int i=0;i<s.size();i++){
		if(i%2){
			if(s[i]=='R')f=0;
		}else{
			if(s[i]=='L')f=0;
		}
	}
	cout<<(f?"Yes":"No")<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b;
  char op;
cin>>a>>op>>b;
  while(op!='?'){
    int c;
    if(op=='+') c=a+b;
    if(op=='-') c=a-b;
    if(op=='*') c=a*b;
    if(op=='/') c=a/b;
    cout << c << endl;
cin>>a>>op>>b;
  }
}



Measured memory_bytes: 3096
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	ll N, W;
	cin>>N>>W;
	vector<ll> w(N);
	vector<ll> v(N);
	vector<vector<vector<ll> > > dp(N + 1, vector<vector<ll> >(N + 1, vector<ll>(4 * N)));
	ll ans = 0;
	REP(i, N) cin>>w[i]>>v[i];
	REP(i, N + 1) {
		REP(j, N + 1) {
			REP(k, 4 * N) {
				if(i == 0 || j == 0) dp[i][j][k] = 0;
				else if(k - (w[i - 1] - w[0]) < 0) {
					dp[i][j][k] = dp[i - 1][j][k];
				} else {
					dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - (w[i - 1] - w[0])] + v[i - 1]);
				}
				if(j * w[0] + k <= W) ans = max(ans, dp[i][j][k]);
			}
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 32896
// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int ll
#define loop(__x, __start, __end) for(Int __x = __start; __x < __end; __x++)
#define loopdown(__x, __start, __end) for(Int __x = __start; __x > __end; __x--)
#define rep(__n) for(Int __x = 0; __x < __n; __x++)
#define span(__a,__x,__y) __a.begin()+__x,__a.begin()+__y
#define span_all(__a) __a.begin(),__a.end()
#define len(__x) (__x.size())
#define last(__x) (__x[__x.size()-1])

using namespace std;

struct Point {
  Int x, y;
  Point(Int x, Int y): x(x), y(y) {}
  Point(): x(0), y(0) {}

  bool operator< (const Point &p1) const {
    return x < p1.x && y < p1.y;
  }
};
ostream & operator << (ostream & out, Point const & v) {
  out << "Point(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Point & v) {
  Int x, y;
  in >> x; in >> y; v.x = x; v.y = y;
  return in;
}

// Geometry

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

int N;
vector<Vector2> A;

void input() {
  cin >> N;
  Vector2 v;
  rep(N) {
    cin >> v;
    A.push_back(v);
  }
}

void solve() {
  sort(span_all(A));
  double avg = 0.0;
  int nban = 0;
  do {
    for (int i=0; i<N-1; i++) {
      avg += (A.at(i+1) - A.at(i)).length();
    }
    nban++;
  } while (next_permutation(span_all(A)));
  avg /= nban;
  cout << avg << endl;
}

int main() {
  cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
using System;
using static System.Console;
using System.Collections.Generic;
using static System.Math;

public class Hello{
    public static void Main(){
        var nums = ReadLine().Split(' ');
        var n = int.Parse(nums[0]);
        var k = int.Parse(nums[1]);
        var scores = ReadLine().Split(' ');
        var sr = int.Parse(scores[0]);
        var ss = int.Parse(scores[1]);
        var sp = int.Parse(scores[2]);
        var s = ReadLine();
        var point = 0;
        var ps = "";
        for(int i=0;i<n;i++){
            if(i < k){
                if(s[i] == 'r'){
                    ps += "p";
                    point += sp;
                }else if(s[i] == 's'){
                    ps += "r";
                    point += sr;
                }else{
                    ps += "s";
                    point += ss;
                }
            }else{
                if(s[i] == 'r'){
                    if(ps[i-k] == 'p'){
                        ps += "z";
                    }else{
                        ps += "p";
                        point += sp;
                    }
                }else if(s[i] == 's'){
                    if(ps[i-k] == 'r'){
                        ps += "z";
                    }else{
                        ps += "r";
                        point += sr;
                    }
                }else{
                    if(ps[i-k] == 's'){
                        ps += "z";
                    }else{
                        ps += "s";
                        point += ss;
                    }
                }
            }
            //WriteLine(point);
        }
        //WriteLine(ps);
        WriteLine(point);
    }
}

Measured memory_bytes: 50000
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 0


int main(){

	lli n;
	vector<lli> a;
	lli data[3]={0};
	cin>>n;
	a.resize(n);
	REP(i,n){
		cin>>a[i];
		if(a[i]%4==0)data[0]++;
		else if(a[i]%2==0)data[1]++;
		else data[2]++;
	}
	if( data[2] <= data[0] +1 - (data[1]>0)){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#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 all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define bit(k) (1LL<<(k))
typedef long long ll;

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);

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

/*------------------------------------/
for library*/
template<class T> class Dijkstra {
public:
    int N;
    T inf;
    vector<T> cost;
    vector<vector<pair<T, int>>> edge;
 
    Dijkstra(const int N, T inf) : N(N), inf(inf),cost(N), edge(N) {
    }
 
    void make_edge(int from, int to, T w) {
        edge[from].push_back({ w,to });
    }
 
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf;
 
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
 
        while (!pq.empty()) {
            T v = pq.top().first;
            int from = pq.top().second;
            pq.pop();
            for (auto u : edge[from]) {
                T w = v + u.first;
                int to = u.second;
                if (w < cost[to]) {
                    cost[to] = w;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
};

/*
使い方
1. まずインスタンス生成
重みの型、頂点の数、距離の無限大のINFLL
Dijkstra<ll> d(N, INFLL);

2. 辺を貼る
iからjに重みwの辺を貼る場合
d.make_edge(i,j,w);

3. 頂点sから解く
d.solve(s);

4. sからgの距離
d.cost[g]

GigaCode2019 E - 車の乗り継ぎ
https://atcoder.jp/contests/gigacode-2019/submissions/8651446

*/
/*------------------------------------*/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N,M;
    cin>>N>>M;
    Dijkstra<ll> G(N,INFLL);
    rep(i,M){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G.make_edge(a,b,1);
        G.make_edge(b,a,1);
    }
    G.solve(0);
    cout<<((G.cost[N-1] <= 2) ? "POSSIBLE" : "IMPOSSIBLE")<<endl;
}

Measured memory_bytes: 18912
import itertools
N = int(input())
P = tuple(map(lambda x: int(x)-1, input().split()))
Q = tuple(map(lambda x: int(x)-1, input().split()))
permu_list = itertools.permutations(range(N))
p,q = 0,0
c = 0
for l in sorted(permu_list):
  if l == P:
    p = c
  if l == Q:
    q = c
  c += 1
print(abs(p-q))

Measured memory_bytes: 8052
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 1e5 + 10;
int mod = 1e9 + 7;
typedef long long ll;
char s1[55], s2[55];

int main()  
{
  // freopen("in.txt", "r", stdin);
    int n;
    while (~scanf("%d", &n))
    {
    	scanf("%s%s", s1, s2);
    	ll ans = 1;
    	int i = 1;
    	if (s1[0] == s2[0])
    	{
    		ans = 3;
    	}else if (s1[0] != s2[0])
    	{
    		i = 2;
    		ans = 6;
    	}
    	for (; i < n;)
    	{
    		if (s1[i] == s2[i])
    		{
    			if (s1[i-1] == s2[i-1])
    			{
    				ans <<= 1;
    				if (ans >= mod)
    					ans %= mod;
    			}
    			i++;
    		}else
    		{
    			if (s1[i-1] == s2[i-1])
    			{
    				ans <<= 1;
    				if (ans >= mod)
    					ans %= mod;
    			}else
    			{
    				ans *= 3;
    				if (ans >= mod)
    					ans %= mod;
    			}
    			i+=2;
    		}
    	}
    	cout<<ans<<endl;
    }

    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> hashmap;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        hashmap[a]++;
    }
    ll ans = 0;
    for (auto& p : hashmap) {
        ans += p.second >= p.first ? p.second - p.first : p.second;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4260