akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
int gcd(int n,int m){
    if(n<m)
        swap(n,m);
    if(m==0)
        return n;
    return gcd(m,n%m);
}
signed main(){
    int a,b,c;
    cin>>a>>b;
    c=gcd(a,b);
    int ans=1;
    for(int i=2;i<1e6;i++){
        if(c%i==0)
            ans++;
        while(c%i==0)
            c/=i;
    }
    if(c!=1)
        ans++;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#ABC118 B

n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(n)]
c = [0 for _ in range(m)]
for i in range(n):
    for j in range(1,s[i][0]+1):
        c[s[i][j]-1] += 1
ans = 0
for i in range(m):
    if c[i] == n:
        ans += 1
print(ans)


Measured memory_bytes: 3064
N, M = map(int,input().split())
dic = {}
P = []; Y = []
ans = ["" for i in range(M)]
for i in range(M):
    p, y = map(int,input().split())
    P.append(p)
    Y.append(y)
    if p not in dic:
        dic[p] = [[y,i]]
    else:
        dic[p].append([y,i])

for k,p in dic.items():
    p.sort()
    for pi in range(len(p)):
        ans[p[pi][1]] = "{:06d}{:06d}".format(k,pi+1)

for i in range(M):
    print(ans[i])


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

using namespace std;

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

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

    // put intervals in two groups
    // maximize intersection of each group
    //
    // iterate over first problem in first contest
    // can we quickly compute intersection of set of intervals?
    // yes: max(0, min r - max l)
    //
    // say we have fixed the leftmost point. As we sweep the rightmost point outwards, we lose
    // more intervals,

    int n;
    cin >> n;

    vi pts;
    vector<pii> a(n);
    int r = 1e9 + 7;
    multiset<int> ls, rs;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
        r = min(r, a[i].second);
        ls.insert(a[i].first);
        rs.insert(a[i].second);
    }

    vector<pii> lefts;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        auto lit = prev(end(ls));
        auto rit = begin(rs);
        if (*lit == a[i].first)
            --lit;
        if (*rit == a[i].second)
            ++rit;

        ans = max(ans, a[i].second - a[i].first + 1 + max(0, *rit - *lit + 1));

        if (a[i].first <= r) {
            assert(r <= a[i].second);
            lefts.push_back(a[i]);
        }
    }

    // otherwise, one of the intersections ends at r.
    // For all intervals that contain r, add them to the left intersection
    sort(all(lefts));
    int maxl = -1;
    for (auto& p : lefts) {
        maxl = max(maxl, p.first);
        ls.erase(ls.find(p.first));
        rs.erase(rs.find(p.second));
        int second = 0;
        if (!rs.empty()) {
            second = max(second, *begin(rs) - *prev(end(ls)) + 1);
        }
        ans = max(ans, r - maxl + 1 + second);
    }

    cout << ans << '\n';

    return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N=50;
int K=250;
int A[50][50];

int cnt;

int q(int y1,int x1,int y2,int x2){
    if((y2-y1)*(x2-x1)==0)return 0;
    /*int res=0;
    for(int y=y1;y<y2;y++)for(int x=x1;x<x2;x++)res+=A[y][x];
    return res;
*/

    cout<<"? "<<y1<<" "<<x1<<" "<<y2-1<<" "<<x2-1<<endl;
    int p;cin>>p;
    return p;
}

void dfs(int y1,int x1,int y2,int x2,int p){
    if(y1==y2)return;
    if(x1==x2)return;

    if((y2-y1)*(x2-x1)==p){
        for(int y=y1;y<y2;y++)for(int x=x1;x<x2;x++)A[y][x]=1;
        return;
    }
    
    if(p==0)return;
    int y3=(y1+y2)/2;
    int x3=(x1+x2)/2;

    int p11,p12,p21,p22;
    p11=q(y1,x1,y3,x3);
    p12=q(y1,x3,y3,x2);
    p21=q(y3,x1,y2,x3);
    p22=p-p11-p12-p21;
    dfs(y1,x1,y3,x3,p11);
    dfs(y1,x3,y3,x2,p12);
    dfs(y3,x1,y2,x3,p21);
    dfs(y3,x3,y2,x2,p22);
}

signed main(){
    /*
    vector<pint>v;
    rep(i,N)rep(j,N)v.pb({i,j});
    srand((unsigned)time(NULL));
    random_shuffle(all(v));

    for(int i=0;i<K;i++){
        A[v[i].fi][v[i].se]=1;
    }*/

    int tmp;
    cin>>tmp;cin>>tmp;cin>>tmp;
    int mod;cin>>mod;

    dfs(0,0,N,N,K);

    int p=1;
    int res=0;
    rep(i,N)rep(j,N){
        res=(res+p*A[i][j])%mod;
        p=p*2%mod;
    }

    cout<<"! "<<res<<endl;
    return 0;
}


Measured memory_bytes: 724
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#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 chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const ll mod = 998244353;
ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}

const int IMAX = 10000001;
ll fac[IMAX + 1], ifac[IMAX + 1], inv[IMAX + 1];
inline ll comb(int A, int B) {
	return fac[A] * ifac[B] % mod * ifac[A - B] % mod;
}

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


	int N;
	cin >> N;

	fac[0] = 1;
	rep1(i, IMAX) fac[i] = fac[i - 1] * i % mod;
	ifac[IMAX] = modpow(fac[IMAX], mod - 2);
	for (int i = IMAX; i > 0; i--) ifac[i - 1] = ifac[i] * i % mod;
	inv[0] = 1;
	rep1(i, IMAX) inv[i] = ifac[i] * fac[i - 1] % mod;


	ll kotae = 1;
	ll k = 1;
	rep1(i, N) {
		ll tmp = comb(N, i);
		k = k * 2 % mod;
		if (i > N / 2) {
			k = (k - comb(i - 1, i - 1 - N / 2) * 2 + mod * 2) % mod;
		}
		kotae += tmp * k % mod;
		kotae %= mod;
	}
	co(kotae% mod);

	Would you please return 0;
}

Measured memory_bytes: 234624
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

int main(void){
  int x, y, a, b, c, i;
  vector<ll> p, q, r;

  cin >> x >> y >> a >> b >> c;
  p.resize(a);
  q.resize(b);
  r.resize(c);

  for(i=0;i<a;i++){
    cin >> p[i];
  }
  for(i=0;i<b;i++){
    cin >> q[i];
  }
  for(i=0;i<c;i++){
    cin >> r[i];
  }

  sort(p.begin(),p.end());
  sort(q.begin(),q.end());
  sort(r.begin(),r.end());

  vector<ll> s;
  s.resize(x+y+c);

  int j = 0;
  for(i=a-x;i<a;i++){
    s[j] = p[i];
    j++;
  }
  for(i=b-y;i<b;i++){
    s[j] = q[i];
    j++;
  }
  for(i=0;i<c;i++){
    s[j] = r[i];
    j++;
  }

  sort(s.begin(),s.end());

  ll sum = 0;
  for(i=c;i<x+y+c;i++){
    sum += s[i];
  }

  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 4736
N, T = map(int, raw_input().split())
t = map(int, raw_input().split())

X = T

dur = T

# durs = map(

for i in range(0, N-1):
    if t[i+1] - t[i] < T:
        X += t[i+1] - t[i]
    else:
        X += T

print(X)


Measured memory_bytes: 20036
count = 0
ary = gets.chop.chars.map(&:to_i)
first = ary[0]
odd = ary.select.with_index{|e, i| i % 2 == 0}
even = ary.select.with_index{|e, i| i % 2 == 1}

if first == 1
  odd.each do |odd_ele|
    if odd_ele != 1
      count += 1
    end
  end
  even.each do |even_ele|
    if even_ele != 0
      count += 1
    end
  end
end

if first == 0
  odd.each do |odd_ele|
    if odd_ele != 0
      count += 1
    end
  end
  even.each do |even_ele|
    if even_ele != 1
      count += 1
    end
  end
end

p count

Measured memory_bytes: 8572
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int main(int argc, const char * argv[]) {
	int N,K,A,j,len;
	cin >> N >> K;
	REP(i,N){
		cin >> A;
	}
	j=1;
	len = K;
	while(N>len){
		j++;
		len += (K-1);
	}
	println(j);
}


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

int main(){
  string s;
  cin>>s;
  sort(s.begin(),s.end());
  if(s[0]==s[1]&&s[2]==s[3]&&s[1]!=s[2]){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)


const int inf = (1<<20);
const int N =50;
const int M = 4;
int dp[N][M];

void solve(int n,int *dist,int *time){
  rep(i,N)rep(j,M)dp[i][j]=inf;
  if (time[0] >= dist[0]){
    dp[0][1]=dist[0];
  }else {
    cout << "NG " << 1 << endl;
    return;
  }
  
  REP(i,1,n){
    REP(k,1,4){
      if (time[i-1]+(k+1)*(dist[i-1]) +dist[i] <= time[i]){
	dp[i][1]=min(dp[i][1],dp[i-1][k]+(dist[i-1]+dist[i]));
      }
    }
    REP(k,2,4){
      if (time[i-1]+(k)*abs(dist[i-1]-dist[i]) <= time[i]){
	dp[i][k]=min(dp[i][k],dp[i-1][k-1]+abs(dist[i-1]-dist[i]));
      }
    }
  }

  int last=0;
  rep(i,n){
    rep(k,4){
      if (dp[i][k] != inf)last=i;
    }
  }
  //cout << last << endl;
  if (last != n-1){
    cout << "NG " << last+2 << endl;
  }else {
    int ans=inf;
    rep(k,4){
      ans=min(ans,dp[n-1][k]+dist[n-1]);
    }
    cout << "OK " << ans << endl;
  }
}

main(){
  int n;
  int pos[N],time[N];


  while(cin>>n && n){
    rep(i,n)cin>>pos[i]>>time[i];
    solve(n,pos,time);
  }
}

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

int main(){
  int H, W;
  while(1){
    cin >>H>>W;
    if(H == 0 && W ==0)break;
    else
  for (int i = 0; i < H ;i++){
    for (int j = 0; j < W ;j++){
      if(i == 0 || i == H - 1 || j == 0 || j == W - 1)  cout << "#";
      else cout << ".";}
    cout << endl;}
  cout << endl;}
  return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include"custom_header.h"
#else
#define openfile 
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define ll long long
#define ld long double
#define fo(i,v,e) for(v=i;v<e;v++)
#define rfo(i,v,e) for(v=i;v>e;v--)
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define sz(x) (ll)x.size()
#define vvl vector<vl>
#define vpl vector<pll>
const ll mod = 1000000007;
void solve()
{
    ll n,a,b,c,i,j,k;cin>>a>>b>>c>>k;
    ll ans = 0;
    while(b<=a)
    {
        ans++;
        b*=2;
    }
    while(c<=b)
    {
        ans++;
        c*=2;
    }
    cout<<(ans<=k?"Yes":"No")<<endl;
}
int main()
{
    // openfile;fastio;
    ll T = 1; 
    // cin>>T;
    while(T--)
    {solve();}
}

Measured memory_bytes: 3632
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

edge = set()
INF = float('inf')
cost = [[INF]*n for _ in range(n)]
for i in range(n):
    cost[i][i] = 0
for a, b, c in abc:
    a, b = a-1, b-1
    cost[a][b] = c
    cost[b][a] = c
    edge.add((a, b, c))

for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = 0
for a, b, c in edge:
    if cost[a][b] < c:
        ans += 1
print(ans)

Measured memory_bytes: 9464
n=int(input())
ans=0
ab=[]
for i in range(n):
    ab.append(list(map(int, input().split())))
ab.reverse()
for i in range(n):
    a=ab[i][0]+ans
    b=ab[i][1]
    if a%b!=0:
        ans+=b-a%b
print(ans)

Measured memory_bytes: 27380
// dp[W]
#include <iostream>
using namespace std;
int n, W, v, w;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> n >> W;
	int dp[W+1] = {0};
	for (int i = 1; i <= n; ++i) {
		cin >> v >> w;
		for (int j = W; j >= w; --j)
			dp[j] = max(dp[j], dp[j-w]+v);
	}
	cout << dp[W] << "\n";
}

Measured memory_bytes: 3184
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; i++ )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;

int main(){
    int n;
    cin>>n;
    int a[n];
    rep(i,n)cin>>a[i];
    int cnt=0;
    rep(i,n-1){
        if(a[i+1]==a[i]){
            cnt++;
            a[i+1]=i+100000;
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
#include <unordered_map>
#define int long long

using namespace std;

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

const int mod = 1e9 + 7;

int pw(int a, int st) {
    if (st == 0) return 1;
    int b = pw(a, st / 2);
    b = (b * b) % mod;
    if (st % 2)
        return (a * b) % mod;
    return b;
}

const int N = 1e5;
int cnt[N + 1], answer[N + 1];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    int ans = 0;
    for (int val = k; val >= 1; --val) {
        answer[val] = (pw(k / val, n) % mod);
        for (int ml = 2; ml * val <= k; ++ml) {
            answer[val] = (answer[val] - answer[val * ml] + mod) % mod;
        }
        ans = (ans + answer[val] * val) % mod;
    }

    cout << ans;
}

Measured memory_bytes: 4360
// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

//PointBlank's code (⌐■_■)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define repp(I, A, B) for(int I = A; I <= B; I++)
#define rep(I, A, B) for(int I = A; I < B; I++)
#define rrep(I, B, A) for(int I = B; I >= A; I--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define LB lower_bound
#define UB upper_bound
#define MP make_pair
#define mem(A, B) memset(A, B, sizeof(A));
#define mem0(A) memset(A, 0, sizeof(A));
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define in_edges(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B), v[B].pb(A);}
#define in_edges2(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B);}
#define endl "\n"
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define bitsf(n) __builtin_popcount(n)
ll power(ll x, ll y); 

const ll MOD = 1000000007;
 
int main() //PointBlank's code ¯\_(ツ)_/¯
{
    int n, k;
    cin >> n >> k;
    set<int> st;
    rep(i, 0, k){
        int d;
        cin >> d;
        while(d--){
            int x;
            cin >> x;
            st.insert(x);
        }
    }
    cout << (n - st.size());
    }
 
ll power(ll x, ll y)
{ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}


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

#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define reps(i, s, n) for(int i = (int)s; i < (int)n; i++)
#define in(i) std::cin >> i;
#define print(i) std::cout << i;
#define println(i) std::cout << i << std::endl;

int main() {
    char c;
    in(c);
    if(isupper(c))
        print("A")
    else
        print("a")
    return 0;
}

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main()
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int x3=x1-(y2-y1),y3=y1+(x2-x1);
    int x4=x2-(y2-y1),y4=y2+(x2-x1);
    cout<<x4<<" "<<y4<<" "<<x3<<" "<<y3<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define vi vector<int>
#define MAX_N 200005
#define i197 1000000007

using namespace std;


typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,P1> P2;
const int inf=1000000000;
P1 xy[MAX_N]={};

int main() {
	int a[4];
	rep(i,4)cin>>a[i];
	sort(a,a+4);
	bool flg=false;
	if(a[0]==a[1]&&a[2]==a[3])flg=true;
	yesno(flg);
	return 0;
}



Measured memory_bytes: 6244
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <functional>

using namespace std;
using ll = long long;

#define FOR(i, m, n) for(int i = (m);i < (n);i++)
#define REP(i,n) for(int i = 0; i < int(n); i++)
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define PAIR pair<int,int>
#define MP make_pair
#define VP vector<pair<int,int>>
#define VS vector<string>
#define QUE queue<int>
#define DEQ deque<int>
#define PQUE priority_queue<int> //5,5,4,3,3,2,...
#define REPQUE priority_queue<int, vector<int>, greater<int>> //1,1,2,3,4,4,5,...
#define SUM(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SORT(obj) sort((obj).begin(), (obj).end()) // 1,2,3,4,5...
#define RESORT(obj) sort((obj).begin(), (obj).end(), greater<int>()) // 5,4,3,2,1...
#define UB(obj,n) upper_bound((obj).begin(), (obj).end(), n) //itr > n
#define LB(obj,n) lower_bound((obj).begin(), (obj).end(), n) //itr>= n

const ll MOD = (ll)1e9 + 7;

int main() {
	int N;
	cin >> N;
	VL a(N);
	REP(i, N) cin >> a[i];

	ll x = 0,y = accumulate(a.begin(), a.end(), 0LL);
	ll d = (ll)1e15;
	REP(i, N - 1) {
		x += a[i];
		y -= a[i];
		d = min(d, abs(x - y));
	}
	cout << d << endl;
	return 0;
}


Measured memory_bytes: 1792
"D Knapsack 1"
import numpy as np
N, W = map(int, input().split())

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])  # dp[:-w]はまだ重さwのものが入るナップサックの状態
    # outは戻り値を格納する配列を指定できる


print(dp[-1])


"""
dp[:-w]は後ろからw個より前の要素、つまり（N-w）個
dp[w:]は前からw個より後ろの要素、つまり（N-w）個
よって形状が一致する
"""

"""
dp[:-w]は今見ている重さw、価値vの荷物を入れることのできる状態のナップサック
dp[:-w]+vをすることで、今見ている荷物を入れた時の価値の総和になる。
今、重さw、価値vの荷物を入れたナップサックと、dp[w:]を比較する。
それぞれの要素について大きい方が新しい要素となり、out=dp[w:]によって上書きされる。
maximumが返すのはnp配列。形状は比較対象となっている配列の形状と一致する
"""


Measured memory_bytes: 14556
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin >> n;
    char suit;
    bool s[14],h[14],d[14],c[14];
    for(int i=1;i<=13;i++){
        s[i]=h[i]=d[i]=c[i]=true;
    }
    int num;
    for(int i=0;i<n;i++){
        cin >> suit >> num;
        if(suit=='S'){
            s[num]=false;
        }
        if(suit=='H'){
            h[num]=false;
        }
        if (suit=='D'){
            d[num]=false;
        }
        if(suit=='C'){
            c[num]=false;
        }
    }
    
    for (int i=1;i<=13;i++){
        if(s[i]){
            cout << "S " << i << endl;
        }
    }
    for (int i=1;i<=13;i++){
        if(h[i]){
            cout << "H " << i << endl;
        }
    }
    for (int i=1;i<=13;i++){
        if(c[i]){
            cout << "C " << i << endl;
        }
    }
    for (int i=1;i<=13;i++){
        if(d[i]){
            cout << "D " << i << endl;
        }
    }
}


Measured memory_bytes: 3096
/* be name khoda */

#define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 998244353;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

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

const ll maxn = 10000010;

ll n, pow2[maxn], fact[maxn], ifact[maxn];

/*
    change A and B in odd indices (now each A need an other letter for remove and the same for B)
    Condition: 
    Ca <= Cb + Cc (Ca <= n / 2)
    Cb <= Ca + Cc (Cb <= n / 2)
   */

ll poww(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) Mul(r, a);
        Mul(a, a);
        b >>= 1;
    }
    return r;
}

ll ent(ll a, ll b) {
    return fact[b] * ifact[a] % MOD * ifact[b - a] % MOD;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // ifstream cin(".in");

    fact[0] = 1;
    fori (i, maxn - 1) fact[i + 1] = fact[i] * (i + 1) % MOD;
    ifact[maxn - 1] = poww(fact[maxn - 1], MOD - 2);
    forir (i, maxn - 1) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
    pow2[0] = 1;
    fori (i, maxn - 1) pow2[i + 1] = pow2[i] * 2 % MOD;

    cin >> n;
    ll bad = 0;
    fori (i, n / 2) {
        Add(bad, ent(i, n) * pow2[i]);
    }
    ll ans = (poww(3, n) + (MOD - bad) * 2) % MOD;
    cout << ans << '\n';

}


Measured memory_bytes: 237952
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

int n,d[105];

int main(){
	int i;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> d[i];
	}
	sort(d,d+n);
	int ans=1;
	for(i=1;i<n;i++){
		if(d[i]!=d[i-1]) ans++;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define int long long
#define ll long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;


int N, K;
int a[123456], sum[123456], sumplus[123456];

signed main(){

	cin >> N >> K;

	rep(i, N)
		cin >> a[i];

	rep(i, N){
		sum[i + 1] = sum[i] + a[i];
		sumplus[i + 1] = sumplus[i] + max(0LL, a[i]);
	}

	int ans = -INF;
	rep(i, N - K+1){
		ans = max(ans, sumplus[i] + (sum[i + K] - sum[i]) + sumplus[N] - sumplus[i + K]);
		ans = max(ans, sumplus[i] + sumplus[N] - sumplus[i + K]);
	}

	cout << ans << endl;



	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ub upper_bound
#define int long long
#define vbe(sdk) sdk.begin(), sdk.end()
#define pb push_back
#define loop(i, a, b) for (int i = a; i < b; ++i)
#define rloop(i, a, b) for (int i = a; i >= b; --i)
#define mp make_pair
#define mod 1000000007
#define endl '\n'
#define vvll vector<vector<int>>
#define vll vector<int>
#define mint map<int, int>
#define arry(x) (int)x.size()
#define sll set<int>
#define pll pair<int, int>
#define F first
#define S second
#define pi 3.14159265358979323846
using namespace std;
const int MAX = 100001;


void solve()
{
        int n;
        cin>>n;
        string s;
        cin>>s;
        // cout<<s<<"\n";
        int i=0,j=n-1;
        int cnt=0;
        while( i<j)
        {
            if(s[i]=='W' && s[j]=='R')
            {
                s[i]='R';
                s[j]='W';
                cnt++;
                i++;
                j--;
            }
            else if(s[i]=='R')
            i++;
            else if(s[j]=='W')
            j--;
        }
        bool flag=0;
        int cnt1=0,cnt2=0;
        for(int i=n-1;i>=0;i--)
        {
            if(s[i]=='R')
            {
                flag=1;
            }
            if(flag==1)
            {
                if(s[i]=='W')
                {
                    cnt1++;
                }
                else
                {
                    cnt2++;
                }
                
            }
        }
        // cout<<cnt<<"\n";
        cout<<cnt + min(cnt1,cnt2)<<"\n";

}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #else
    // // online submission
    // #endif


    int t = 1;
    //    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#define INF 1000001
using namespace std;

int main() {
    int n = 0, k = 0, buf1 = 0;
    cin >> n >> k;
    int* dp = new int[n+1];
    dp[0] = 0;
    dp[1] = 0;
    int* h = new int[n+1];
    h[0] = INF;
    for (int i = 1; i < n+1; ++i) {
        cin >> buf1;
        h[i] = buf1;
    }
    for (int i = 2; i < n+1; ++i) {
        dp[i] = dp[i-1]+abs(h[i]-h[i-1]);
        for (int j = 2; j < k+1; ++j) {
            dp[i] = min(dp[i], dp[max(i-j, 0)]+abs(h[i]-h[max(i-j, 0)]));
        }
    }
    cout << dp[n];
    delete[] dp;
    delete[] h;
    return 0;
}


Measured memory_bytes: 3996
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();

		String[] S1 = W.split(" ");

		W = in.readLine();
		String[] S2 = W.split(" ");

		String ans = "0";
		if(S1[0].equals(S2[0])){
			ans = "0";
		}else{
			ans ="1";
		}

		System.out.println(ans);



	}


}


Measured memory_bytes: 23124
import numpy as np

N = int(input())
x_list = list(map(lambda x: int(x), input().split(" ")))
M = np.sum(x_list)
L = np.sum(list(map(lambda x: int(x)**2, x_list)))

if M % N == 0:
    print(int(L - M**2 / N))
else:
    rest = M % N
    if rest <= N / 2:
        print(int(rest**2 / N - M**2 / N + L))
    else:
        print(int(N * (1 - rest / N)**2 - M**2 / N + L))


Measured memory_bytes: 27268
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define rg register
#define ll long long
#define LDB long double
#define ull unsigned long long
#define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt)
#define go(i,x,a) for(rg int i=a;i<x;i++)
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
using namespace std;

const int maxn=5e3+5;
int n,a[maxn];
ll A,B,f[maxn][maxn],sf[maxn][maxn];

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

inline void gmin(ll &a,ll b){
	if(a > b) a=b; return ;
}

int main(){
	#ifndef ONLINE_JUDGE
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	#endif
	n=rd(); A=rd(); B=rd(); int x;
	go(i,n+1,1) x=rd(),a[x]=i;
	memset(sf,7,sizeof(sf)); memset(f,7,sizeof(f));
	go(i,n+1,1) sf[0][i]=0;
	go(i,n+1,1){
		go(j,n+1,1){
			if(j < a[i]) gmin(f[i][j],sf[i-1][j]+B);
			if(j == a[i]) gmin(f[i][j],sf[i-1][j]);
			if(j > a[i]) gmin(f[i][j],sf[i-1][j]+A);
			sf[i][j]=sf[i][j-1];
			gmin(sf[i][j],f[i][j]);
		}
	}
	ll ans=1e18;
	go(i,n+1,1) gmin(ans,f[n][i]);
	printf("%lld",ans);
	return 0;
}//Faze


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

using namespace std;
typedef long long ll;

int n;
int a[401];
ll dp[401][401];

ll solve(int l, int r)
{
    if(dp[l][r] != -1) return dp[l][r];
    
    ll sum = 0;
    if(l == r) return 0;
    for(int i = l; i <= r; i++)
    {
        sum += a[i];
    }
    
    ll mn = 1e18;
    for(int i = l; i < r; i++)
    {
        mn = min(mn, solve(l, i) + solve(i+1, r));
    }
    
    sum += mn;
    return dp[l][r] = sum;
}

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

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++) dp[i][j] = -1;
    }
    // solve(0, n-1);
    // for(int i = 0; i < n; i++)
    // {
    //     for(int j = 0; j < n; j++)
    //     {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    cout << solve(0, n-1) << endl;
}

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

const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

ll powmod(ll n, ll x)
{
    vector<ll> vll(32);
    vll[0] = n;
    FOR(i, 1, 32)
    {
        vll[i] = (vll[i - 1] * vll[i - 1]) % MOD;
    }
    ll ret = 1;
    int cnt = 0;
    while (x > 0) {
        if (x & 1) {
            ret = (ret * vll[cnt]) % MOD;
        }
        x >>= 1;
        cnt++;
    }
    return ret;
}

int main()
{
    int n;
    cin >> n;
    map<pair<ll, ll>, int> mplli;
    int zero = 0;
    REP(i, n)
    {
        ll a, b;
        cin >> a >> b;
        if (a == 0 && b == 0) {
            zero++;
            continue;
        }
        if (a < 0) {
            a *= -1;
            b *= -1;
        }
        if (a == 0 && b != 0)
            b = 1;
        if (b == 0 && a != 0)
            a = 1;
        ll g = gcd(abs(a), abs(b));
        a /= g;
        b /= g;
        mplli[{ a, b }]++;
    }
    ll ans = 1;
    set<pair<ll, ll>> spll;
    spll.insert({ 0, 0 });
    for (auto i = mplli.begin(); i != mplli.end(); i++) {
        if (spll.find(i->first) != spll.end())
            continue;
        pair<ll, ll> pll;
        if ((i->first.second) < 0)
            pll = { -(i->first).second, (i->first).first };
        else
            pll = { (i->first).second, -(i->first).first };
        int p = i->second;
        int q = mplli[pll];
        ans = (ans * (powmod(2, p) + powmod(2, q) - 1 + MOD)) % MOD;
        spll.insert(i->first);
        spll.insert(pll);
    }
    cout << (ans + zero - 1 + MOD) % MOD << endl;
}

Measured memory_bytes: 53524
//https://atcoder.jp/contests/agc011/tasks/agc011_a
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#endif
    ll N,C,K; cin>>N>>C>>K;
    vector<ll> tn(N);
    for(auto&& t:tn){
        cin>>t;
    }
    sort(tn.begin(),tn.end());
    ll ans=1;
    ll tm=tn[0]+K;
    ll cnt=C;
    FOR(i,1,N){
        --cnt;
        if(cnt<=0||tn[i]>tm){
            //新しいbus
            ++ans;
            tm=tn[i]+K;
            cnt=C;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define Set setprecision 
double dp[3000][3000];
double p[3000];
signed main(){
  int N;
  double  sum=0;
  cin>>N;
  for(int i=0;i<N;i++) cin>>p[i];
  dp[0][0]=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      dp[i+1][j+1]+=dp[i][j]*p[i];
      dp[i+1][j]+=dp[i][j]*(1-p[i]);
    }
    
  }
  for(int i=(N+1)/2;i<=N;i++){
    sum+=dp[N][i];
  }
  /*for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++) cout<<dp[i][j]<<" ";
    cout<<"\n";
    }*/
cout<<fixed<<Set(20)<<sum<<"\n";
}
	


Measured memory_bytes: 70528
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	string s;
	cin>>s;
	bool h[2]={0};
	rep(i,s.size())if(s[i]=='C')h[0]=true;
	else if(s[i]=='F'&&h[0])h[1]=true;
	if(h[0]+h[1]==2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}









Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> gcd_asc(n), gcd_desc(n);
  rep(i, 0, n) {
    cin >> a[i];
    if (i == 0)
      gcd_asc[i] = a[i];
    else
      gcd_asc[i] = __gcd(gcd_asc[i - 1], a[i]);
  }

  repr(i, 0, n) {
    if (i == n - 1)
      gcd_desc[i] = a[i];
    else
      gcd_desc[i] = __gcd(gcd_desc[i + 1], a[i]);
  }

  int ans = 0;
  rep(i, 0, n) {
    if (i == 0)
      ans = gcd_desc[i + 1];
    else if (i == n - 1)
      chmax(ans, gcd_asc[n - 2]);
    else
      chmax(ans, __gcd(gcd_asc[i - 1], gcd_desc[i + 1]));
  }

  cout << ans << endl;
}


Measured memory_bytes: 1408
use std::io::*;
use std::str::FromStr;

//https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn rec(
    n: usize,
    m: usize,
    status: &mut Vec<usize>,
    mut ans: u32,
    switch: &Vec<Vec<usize>>,
    p: &Vec<u32>,
) -> u32 {
    //最深まで探索し、状態を判定する
    if status.len() == n {
        let mut light = vec![false; m];
        for i in 0..m {
            let mut on = 0;
            for j in switch[i].iter() {
                if (status[*j - 1]) == 1 {
                    on += 1;
                }
            }
            //点灯の確認
            //println!("on{}",on);
            if on % 2 == p[i]{
                light[i] = true;
            }
        }
        //全点灯の確認
        if light.iter().all(|c| *c == true) {
            ans += 1;
        }
        //println!("ans{} status{:?}",ans,status);
    } else {
        //再帰全探索
        for c in 0..2 {
            status.push(c);
            ans = rec(n, m, status, ans, switch, p);
            status.pop();
        }
    }

    return ans;
}
fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut switch: Vec<Vec<usize>> = vec![vec![0; 0]; m]; //m個の空のvecを用意

    for i in 0..m {
        let k: usize = read();
        for _ in 0..k {
            let s: usize = read();
            switch[i].push(s);
        }
    }
    let p: Vec<u32> = (0..m).map(|_| read()).collect();

    let mut status = Vec::new();
    let ans = rec(n, m, &mut status, 0, &switch, &p);
    print!("{}", ans);
}


Measured memory_bytes: 4476
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  int m, k;
  cin >> m >> k;

  if ((m == 1 && k == 1) || (k >= (1 << m))) {
    cout << -1 << endl;
    return 0;
  }
  else if (m == 1 && k == 0) {
    cout << "0 0 1 1" << endl;
    return 0;
  }

  vector<int> ans;
  for (int i = 0; i < (1 << m); i++) {
    if (i != k) ans.push_back(i);
  }
  ans.push_back(k);
  for (int i = (1 << m) - 1; i >= 0; i--) {
    if (i != k) ans.push_back(i);
  }
  ans.push_back(k);

  for (auto &x: ans) cout << x << " ";
  cout << endl;

  return 0;
}


Measured memory_bytes: 4260
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int h, w;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        h = sc.nextInt();
        w = sc.nextInt();
        for (int i = 0; i <= h + 1; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append('#');
            if (i == 0 || i == h + 1) {
                for (int j = 0; j < w; j++) {
                    sb.append('#');
                }
            } else {
                sb.append(sc.next());
            }
            sb.append('#');
            System.out.println(sb);
        }
        solve();
    }

    void solve() {

    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

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

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 21716
#include<iostream>

using namespace std;

typedef long long ll;

namespace comb {
	ll fact[500001];
	ll fact_inv[500001];
	const ll MOD = 1000000007;

	ll modpow(ll a, ll b) {
		ll base = 1, kakeru = a;
		while (b > 0) {
			if (b & 1)base *= kakeru, base %= MOD;
			kakeru *= kakeru, kakeru %= MOD;
			b >>= 1;
		}
		return base;
	}

	void setup() {
		fact[0] = 1, fact[1] = 1;
		for (int i = 2; i <= 500000; i++) {
			fact[i] = (fact[i - 1] * i) % MOD;
		}

		fact_inv[500000] = modpow(fact[500000], MOD - 2);

		for (int i = 499999; i >= 0; i--) {
			fact_inv[i] = fact_inv[i + 1] * (i + 1);
			fact_inv[i] %= MOD;
		}

	}

	ll combination(int a, int b) {
		if (a - b < 0)return 0;
		ll ret = fact[a];
		ret *= fact_inv[b], ret %= MOD;
		ret *= fact_inv[a - b], ret %= MOD;
		return ret;
	}

	ll permutation(int a, int b) {
		if (a - b < 0)return 0;
		ll ret = fact[a];
		ret *= fact_inv[a - b], ret %= MOD;
		return ret;
	}

	ll homogeneous(int a, int b) {
		return combination(a + b - 1, b);
	}

}

int N, A, B, C, D;

ll dp[1000 + 10][1000 + 10];//dp[i][j] := (i > 0)ならi + A - 1人のグループを作り終えて、合計j人使った時, i == 0の時はなにも使ってないとき

int main() {
	comb::setup();
	cin >> N >> A >> B >> C >> D;

	dp[0][0] = comb::fact[N];

	for (int i = 1; i <= (B - A + 1); i++) {
		for (int j = 0; j <= N; j++) {
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= comb::MOD;
			for (int k = C; k <= D; k++) {
				if (k * (A + i - 1) <= j) {
					dp[i][j] += (((dp[i - 1][j - k * (A + i - 1)] * comb::modpow(comb::fact_inv[A + i - 1], k)) 
						% comb::MOD) * comb::fact_inv[k]) % comb::MOD;
					dp[i][j] %= comb::MOD;
				}
			}
			//cout << i << " " << j << " " << dp[i][j] << endl;
		}
	}
	cout << dp[B - A + 1][N] << endl;
	return 0;
}

Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main() {
    ll n, m, d; cin >> n >> m >> d;
    double ans = 0;
    if(d==0) ans = 1.0*(m-1)/n;
    else ans = 2.0*(n-d)/n * (m-1)/n;
    printf("%.10f\n", ans);
}


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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto n = load<int>();
    auto w = load<int>();
    auto dyn = vector<long long>(w+1, 0ll);
    for (auto i=0; i<n; ++i) {
        auto weight = load<int>();
        auto value = load<int>();
        for (auto j=w; j-weight>=0; --j)
            dyn[j] = max(dyn[j], dyn[j-weight] + value);
    }
    cout << dyn[w] << '\n';
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
  
  string s = "";
  int n;
  cin >> n;
  for (int i = 0; i<n; i++){
    int d, dd;
    cin >> d >> dd;
    if ( d == dd) s = s + "Y";
    else s = s + "N";
  }
  int find = s.find("YYY");
  if ( find >= 0 )cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
  
}



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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;
const long long MOD = (long long)1e9 + 7;

int pop_count(long long bits){
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

struct segtree{
    int n;
    vector<int> d;
    function<int(int, int)> f;
    segtree(int mx){
        n = 1;
        while(n < mx) n <<= 1;
        d = vector<int>(n << 1);
    }
    int query(int a, int b, int i = 1, int l = 0, int r = -1){
        if(r == -1) r = n;
        if(a <= l && r <= b){
            return d[i];
        }
        int res = 0;
        int c = (l + r) >> 1;
        if(a < c) res |= query(a, b, i << 1, l, c);
        if(c < b) res |= query(a, b, i << 1 | 1, c, r);
        return res;
    }
    void update(int i, int x){
        i += n;
        d[i] = x;
        while(i){
            i >>= 1;
            d[i] = d[2 * i] | d[2 * i + 1];
        }
    }
    void set(int i, char c){
        d[i + n] = 1 << (c - 'a');
        update(i, d[i + n]);
    }
};

int main(){
    int n;
    string s;
    cin >> n >> s;
    segtree st(n);
    for(int i = 0; i < n; i++){
        st.set(i, s[i]);
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int t;
        cin >> t;
        if(t == 1){
            int x;
            char c;
            cin >> x >> c;
            x--;
            st.set(x, c);
        }else{
            int x, y;
            cin >> x >> y;
            x--;
            cout << pop_count(st.query(x, y)) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4996
#include<bits/stdc++.h>
using namespace std;
#define faster_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
#define bug(a)       cerr << #a << " : " << a << endl;
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
template<class T>void ExEuclid(T n, T m, T &a, T &b, T &gcd){if(m==0){gcd=n;a=1;b=0;return;}ExEuclid(m,n%m,a,b,gcd);T x=a;a=b;b=x-(n/m)*a;}
template<class T>T gcd(T n, T m){if(m==0){return n;}gcd(m,n%m);}
template<class T>T lcm(T n, T m){return (n*m)/gcd(n,m);}
template<class T>string to_string(T n){string s="";while(n)s+=((n%10)+'0'),n/=10;reverse(s.begin(),s.end());return s;}
template<class T>ll to_int(T s){ll num=0,power=0;for(int i=s.size()-1; i>=0; i--)num+=(pow(10.0,power++)*(s[i]-'0'));return num;}
template<class T>bool is_mod(T n, T m){if(n%m==0)return true;return false;}
template<class T>bool is_upper(T s){for(int i=0; i<s.size(); i++)if(s[i]>90 || s[i]<65)return false;return true;}
template<class T>bool is_lower(T s){for(int i=0; i<s.size(); i++)if(s[i]>122 || s[i]<97)return false;return true;}
template<class T>bool is_palindrome(T s){T s1=s;reverse(s1.begin(),s1.end());if(s==s1)return true;return false;}
template<class T>T mod(T n, T m){return ((n%m)+m)%m;}
template<class T>T Big_mod(T base, T power, T MOD){
    if(power==1)return base;
    if(power & 1)return ((base%MOD)*(Big_mod(base,power-1,MOD))%MOD)%MOD;
    else {T temp=(Big_mod(base,power>>1,MOD));return ((temp%MOD)*(temp%MOD))%MOD;}
}



int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    faster_io;
    ll t,mx=1000000000,ans=0,k;
    scl(t);
    scl(k);
    ll a[t+5];
    for(int i=0; i<t; i++){
        scl(a[i]);
    }
    sort(a,a+t);
    for(int i=0; i<=t-k; i++){
        mx=min(mx,a[i+k-1]-a[i]);
    }
    cout<<mx<<endl;
    return 0;
}



Measured memory_bytes: 1024