akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=998244353;
int main(){
    ll h,w;cin>>h>>w;
    vector<string>s(h);
    rep(i,h){
        cin>>s[i];
    }
    vector<vector<ll> >d(h,vector<ll>(w,inf));
    if(s[0][0]=='#')d[0][0]=1;
    else d[0][0]=0;
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#'){
                if(i<h-1)d[i+1][j]=min(d[i+1][j],d[i][j]);
                if(j<w-1){
                    d[i][j+1]=min(d[i][j+1],d[i][j]);
                }
            }else{
                if(i<h-1){
                    if(s[i+1][j]=='#'){
                        d[i+1][j]=min(d[i+1][j],d[i][j]+1);
                    }else{
                        d[i+1][j]=min(d[i+1][j],d[i][j]);
                    }
                }
                if(j<w-1){
                    if(s[i][j+1]=='#'){
                        d[i][j+1]=min(d[i][j+1],d[i][j]+1);
                    }else{
                        d[i][j+1]=min(d[i][j+1],d[i][j]);
                    }
                }
            }
        }
    }
    cout<<d[h-1][w-1]<<endl;
}

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

class fraction {
    ll numel;                  // ??????
    ll denom;                  // ??????

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

    pair<ll, ll> reduce(ll n, ll d) {
        map<ll, ll> pfs = prime_factor(d);
        for (auto it = pfs.begin(); it != pfs.end(); it++) {
            while ((*it).second > 0 && n%(*it).first == 0) {
                n /= (*it).first;
                d /= (*it).first;
                (*it).second--;
            }
        }
        return pair<ll, ll>(n, d);
    }

public:
    fraction() {
        this->numel = 0;
        this->denom = 1;
    }
    fraction(string s) {
        int pos = 0;
        while (s[pos] != '/') pos++;
        ll n = stoi(string(s.begin(), s.begin()+pos));
        ll d = stoi(string(s.begin()+pos+1, s.end()));

        pair<int, int> ret = reduce(n, d);
        this->numel = ret.first;
        this->denom = ret.second;
    }
    fraction (ll n, ll d) {
        pair<ll, ll> ret = reduce(n, d);
        this->numel = ret.first;
        this->denom = ret.second;
    }

    friend ostream& operator << (ostream &os, const fraction& fr);

    fraction operator + (const fraction& fr) const {
        ll n = this->numel*fr.denom + fr.numel*this->denom;
        ll d = this->denom * fr.denom;
        return fraction(n, d);
    }
    fraction operator - (const fraction& fr) const {
        ll n = this->numel*fr.denom - fr.numel*this->denom;
        ll d = this->denom * fr.denom;
        return fraction(n, d);
    }
};

ostream& operator << (ostream& os, const fraction& fr) {
    os << to_string(fr.numel);
    if (fr.denom != 1) os << "/" + to_string(fr.denom);
    return os;
}

fraction calc_dir(const vector<int>& dirs, int pos) {
    if (pos == dirs.size()-1) return fraction(dirs[pos], 1);

    int denom = pow(2, dirs.size() - pos - 1);
    if (dirs[pos] == 0) {
        return calc_dir(dirs, pos+1) - fraction(90, denom);
    }

    return calc_dir(dirs, pos+1) + fraction(90, denom);
}

int main(void) {

    string s;
    while (cin >> s) {
        if (s == "#") break;

        int pos = 0;
        vector<int> dirs;
        while (pos < s.size()) {
            if (s.substr(pos, 5) == "north") {
                dirs.push_back(0);
                pos += 5;
            } else {
                // west
                dirs.push_back(90);
                pos += 4;
            }
        }

        fraction ret = calc_dir(dirs, 0);
        cout << ret << endl;
    }

    return 0;
}

Measured memory_bytes: 3312
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define in insert
#define pi 3.14159265358979323846
#define rep(i,a,b) for(int i = a ; i < b ; i++)
#define repr(i,a,b) for(int i = b ; i > a ; i--)
  
long long fact(long long a, long long b){
    int r= max(a, b);
    int v= min(a, b);
    int l=1;
    // if(v==0)
    for(int i=r+1; i<=a+b; i++){
        l*=i;
    }
    for(int i=v; i>=2; i--){
        l/=i;
    }
    return l;
}

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

int powr(int a) { 
    int var=1;
    for(int i=0; i<a; i++){
        var*=2;
    }
    return var;
}

void func(int a, bool i){
    cout << a;
    if(a==100){
        i=1;
    }
    else if(a==0){
        return;
    }
    if(!i)
        func(a+1, i);
    else
        func(a-1, i);
}

signed main(){   
    fast;
    string s;
    string t;
    cin >>s >>t;
    int L[s.length()+1][t.length()+1];
    string res;
    memset(L, 0, sizeof(L));
    for(int i=1; i<=s.length(); i++){
        for(int j=1; j<=t.length(); j++){
            if(s[i-1]==t[j-1])
                L[i][j]=L[i-1][j-1]+1;
            else
                L[i][j]=max(L[i][j-1],L[i-1][j]);
        }
    }
    int i=s.length() , j = t.length();
    while(i>0&&j>0)
    {
        if(s[i-1]==t[j-1])
        res+=s[i-1], i--,j--;
        else if(L[i][j-1]>L[i-1][j])
        j--;
        else
        i--;
    }
    reverse(res.begin(), res.end());
    cout << res;
} 

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

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (int i = j; i < (n); i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1e9;

int main(){

  ll n;cin>>n;
  ll t[n+10],a[n+10];
  rep(i,0,n)cin>>t[i]>>a[i];

  ll pt=1,pa=1;
  rep(i,0,n){
    ll p=max((pt%t[i]?pt/t[i]+1:pt/t[i]),(pa%a[i]?pa/a[i]+1:pa/a[i]));
    pt=p*t[i],pa=p*a[i];
  }

  out(pt+pa);

  return 0;
}


Measured memory_bytes: 256
/*** 𝕒𝕜𝕤𝕙𝕒𝕪𝕜𝕦𝕞𝕒𝕣𝟡𝟡 ***/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
 
#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD=1e9+7;
const long double PI = acos(-1);
const long long INF=INT_MAX;
const long long LINF=LLONG_MAX;
const long long N=2e5+1;
 
typedef long long ll;
typedef long double ld;

ll n, length = 1, a[N], res[N];
vector<ll> v[N], seq, tail(N, INF);

// ll b_search(vector<ll> v, ll l, ll r, ll val)
// {
//     while(r - l > 1)
//     {
//         ll mid = (l+r)>>1;
//         if(v[mid] >= val)
//             r = mid;
//         else
//             l = mid;
//     }
//     return r;
// }

void dfs(ll s, ll p)
{
    ll val, ind=-1, mx = length;
    // if(a[s] < tail[0])
    // {
    //     val=tail[0];
    //     ind=0;
    //     tail[0] = a[s];
    // }
    // else if(a[s] > tail[length - 1])
    //     tail[length++] = a[s];
    // else
    {
        ind = lower_bound(tail.begin(), tail.begin()+length, a[s]) - tail.begin();
        // ind = b_search(tail, -1, length - 1, a[s]);
        if(ind==length)
            length++;
        val = tail[ind];
        tail[ind] = a[s];
    }
    res[s] = length;

    for(auto u : v[s])
        if(u!=p)
            dfs(u, s);

    length = mx;
    if(ind!=-1)
        tail[ind] = val;

}
void test_case()
{
    ll i,j;
    cin>>n;
    f(i,1,n+1)
    {
        cin>>a[i];
    }
    f(i,0,n)
    {
        ll x,y;
        cin>>x>>y;
        v[x].pu(y);
        v[y].pu(x);
    }
    tail[0] = a[1];
    dfs(1, 0);
    f(i,1,n+1)
    {
        cout<<res[i]<<'\n';
    }
}

int32_t main()
{
    IOS();
   
    int tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}


Measured memory_bytes: 33172
n,k,s = map(int,input().split())
ans = []
if s==10**9:
    for i in range(n):
        if i < k:
            ans.append(s)
        else:
            ans.append(1)
else:
    for i in range(n):
        if i < k:
            ans.append(s)
        else:
            ans.append(s+1)
print(*ans)

Measured memory_bytes: 49392
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
template <typename CT, typename T> inline void reset_container(CT &c, int sz, T v){c.resize(sz); for(auto &x: c) x=v;}
#define taskname "B"
int n;
int d[301];
const ll base=1000000007;
ll power(ll a, ll b){
    if(b==0) return 1;
    ll t=power(a, b/2);
    t=(t*t)%base;
    if(b%2) t=(t*a)%base;
    return t;
}
ll f[601];
ll r[601];
ll dp[301][601];
ll temp[301][601];
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    f[0]=1;
    FOR(i, 1, 600) f[i]=(f[i-1]*i)%base;
    r[600]=power(f[600], base-2);
    DFOR(i, 600, 1) r[i-1]=(r[i]*i)%base;
//    bug((((((f[12]*r[2])%base*r[2])%base*r[3])%base*r[3])%base*18)%base);
    read(n);
    FOR(i, 1, n) read(d[i]);
    dp[0][0]=r[2];
    FOR(i, 1, n){
        FOR(j, 0, n) FOR(k, j+j, n+n) temp[j][k]=0;
        FOR(j, 0, n) FOR(k, j+j, n+n) if(dp[j][k]){
            if(d[i]>=2) temp[j+1][k+d[i]]=(temp[j+1][k+d[i]]+dp[j][k]*r[d[i]-2])%base;
            temp[j][k]=(temp[j][k]+dp[j][k]*r[d[i]-1])%base;
        }
        FOR(j, 0, n) FOR(k, j+j, n+n) dp[j][k]=temp[j][k];
    }
//    bug()
    ll ans=(dp[n][n+n]*f[n-1])%base;
    FFOR(i, 3, n) FOR(k, i+i+1, n+n) if(dp[i][k]){
        ans=(ans+(((f[n-i-1]*(k-2*i))%base*f[i-1])%base)*dp[i][k])%base;
    }
//    ans=(ans*r[2])%base;
    writeln(ans);
}

Measured memory_bytes: 3072
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    deque<int>q;
    while(T--){
        int a,d,x,p;
        cin>>a;
        if(a==0){
            cin>>d>>x;
            if(d==0)
               q.push_front(x);
            else
                q.push_back(x);
        }
        else if(a==1){
            cin>>p;
            cout<<q[p]<<endl;
        }
        else{
            cin>>d;
            if(d==0)
                q.pop_front();
            else
                q.pop_back();
        }
    }
    return 0;
}



Measured memory_bytes: 4568
#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef pair< int, int > P;

int Move( int, int, int );
int Get( int, int );
void Set( int&, int, int );

int main()
{
	const int dx[ 4 ] = { 1, 0, -1, 0 }, dy[ 4 ] = { 0, 1, 0, -1 };
	map< int, int > memo;
	queue< P > que;
	que.push( P( 01234567, 0 ) );
	while( !que.empty() ) {
		int p = que.front().first;
		int t = que.front().second;
		que.pop();
		if( memo.find( p ) != memo.end() ) { continue; }
		memo[ p ] = t;
		for( int i = 0; i < 4; ++i ) {
			int np = Move( p, dx[ i ], dy[ i ] );
			if( np == -1 ) { continue; }
			que.push( P( np, t + 1 ) );
		}
	}

	while( 1 ) {
		int p = 0;
		for( int i = 0; i < 8; ++i ) {
			int a;
			if( !( cin >> a ) ) { return 0; }
			Set( p, i, a );
		}
		cout << memo[ p ] << endl;
	}
	return 0;
}

int Move( int p, int dx, int dy ) {
	int res = p;
	int zx, zy, zp;
	for( int i = 0; i < 8; ++i ) {
		int a = Get( res, i );
		if( !a ) {
			zx = i % 4;
			zy = i / 4;
			zp = i;
			break;
		}
	}
	int nzx = zx + dx, nzy = zy + dy, nzp = nzy * 4 + nzx;
	if( nzx < 0 || nzx >= 4 || nzy < 0 || nzy >= 2 ) { return -1; }

	int num1 = Get( res, zp ), num2 = Get( res, nzp );
	Set( res, nzp, num1 );
	Set( res, zp, num2 );

	return res;
}

int Get( int p, int n ) {
	int shift = 3 * ( 7 - n );
	return ( ( p & ( 7 << shift ) ) >> shift );
}

void Set( int& p, int n, int a ) {
	int shift = 3 * ( 7 - n );
	p &= ~( 7 << shift );
	p |= ( a << shift );
}

Measured memory_bytes: 2168
#include<bits/stdc++.h>
#define rint register int
#define rep(i,a,b) for (rint i=(a),_E=(b); i<=_E; ++i)
#define per(i,a,b) for (rint i=(a),_E=(b); i>=_E; --i)
#define REP(i,n) for (rint i=0,_E=(n); i<_E; ++i)
#define pb push_back
#define cmin(x,y) (y<x?x=y:0)
#define cmax(x,y) (y>x?x=y:0)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

const int N = 10005;
const int mod = 1000000007;
int n, a, b, c, n1, n2, n3, n4, K, res, now;
int fac[N], rev[N];

inline int power(int x, int p) {
	int res = 1;
	while (p) {
		if (p & 1) res = 1ll * x * res % mod;
		x = 1ll * x * x % mod; p >>= 1;
	}
	return res;
}

inline int C(int n, int m) {
	if (m < 0 || m > n) return 0;
	return 1ll * fac[n] * rev[m] % mod * rev[n-m] % mod;
}

//将n划分为m份，可以为空
inline int calc(int n, int m) {
	if (!n && !m) return 1;
	return C(n + m - 1, m - 1);
}

int main() {
	scanf("%d%d%d%d", &n, &a, &b, &c);
	if (b & 1) return puts("0"), 0;
	fac[0] = rev[0] = 1;
	rep (i, 1, 10000) {
		fac[i] = 1ll * i * fac[i-1] % mod;
		rev[i] = power(fac[i], mod - 2);
	}
	rep (x, 0, min(a, c)) rep (y, 0, (c - x) / 3) {
		n1 = b / 2, n2 = y, n3 = a - x, n4 = x, K = c - x - 3 * y;
		if (n1 < 0 || n2 < 0 || n3 < 0 || n4 < 0 || K < 0) continue;
		now = 1ll * fac[n1 + n2 + n3 + n4] * calc(K, n1) % mod;
		now = 1ll * now * rev[n1] % mod * rev[n2] % mod;
		now = 1ll * now * rev[n3] % mod * rev[n4] % mod;
		res = (res + now) % mod;
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  if (N % 1000 % 111 == 0 || N / 10 % 111 == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;

/*----------------------------------------------------------------*/
signed main(){

	int n;
	cin >>n;
    vector<pair<int,int>> p(n);
    rep(i,n){
        int x,l;
        cin >> x >> l;
        p[i] = MP(x+l,x-l);
    }
    SORT(p);
    int cnt = 0;
    int rmax = -INF;
    rep(i,n){
        if(rmax <= p[i].se){
            cnt++;
            rmax = p[i].fi;
        }
    }
    cout << cnt << endl;
    
 	
	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://ddcc2020-qual.contest.atcoder.jp/tasks/ddcc2020_qual_b
// rm -r -f test;oj dl https://keyence2020.contest.atcoder.jp/tasks/keyence2020_b


Measured memory_bytes: 1920
#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())

#define ull unsigned long long
#define ll long long



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

#define pb(a) push_back(a)

ull now,n;


int main(){
  ull ans=0;
  cin >> n;

  vector<ull> u(2*n,-1),v(2*n,-1),w(2*n,-1);
  vector<ull> uv(2*n-2);
  REP(i,n-1) cin>>u[i]>>v[i]>>w[i];
  
  REP(i,n-1){
    u[i]--;
    v[i]--;
    uv[2*i]=(u[i]*100001LL+v[i])*1000000001LL+w[i];
    uv[2*i+1]=(v[i]*100001LL+u[i])*1000000001LL+w[i];
  }
  sort(uv.begin(), uv.end());
  vector<int> saisyonoindex(n+1,-1);
  
  ull mtmp=-1,tmp;
  //vector<ull> u(2*n,-1),v(2*n,-1),w(2*n,-1);
  REP(i,2*n-2){
    tmp=uv[i]/(100001LL*1000000001LL);
    if (mtmp!=tmp){
      saisyonoindex[tmp]=i;
    }
    mtmp=tmp;
    u[i]=tmp;
    v[i]=(uv[i]/(1000000001LL))%100001LL;
    w[i]=uv[i]%(1000000001LL);
  }
  
  
  vector<ull> qq(n);//探しに行きたいところリスト1
  vector<ull> dqq(n);//探しに行きたいところリスト2
  vector<ull> wqq(n);//探しに行きたいところリスト3
  
  vector<ull> qqqq(n);//探しに行きたいところリスト4
  vector<ull> qqdqq(n);//探しに行きたいところリスト5
  vector<ull> qqwqq(n);//探しに行きたいところリスト6
  
  vector<ull> col(n,-1);//0からの距離
  
  col[0]=0;
  //0を基準にする
  tmp=0;
  REP(i,saisyonoindex[1]-saisyonoindex[0]){
    dqq[i]=u[i];//探すもと
    qq[i]=v[i];//探す先
    wqq[i]=w[i];
    tmp=i;
  }
  
  int qqlen=tmp+1;
  int qqwidx=0;
  REP(i,2*n){
    //qqのリストを検索
    REP(j,qqlen){
      col[qq[j]]=col[dqq[j]]+wqq[j];
    }
    
    qqwidx=0;
    REP(j,qqlen){
      tmp=saisyonoindex[qq[j]];
      REP(k,100001){
        if (u[tmp]!=qq[j])break;
        if (col[v[tmp]]==-1){
          //追加
          dqq[qqwidx]=u[tmp];//探すもと
          qqqq[qqwidx]=v[tmp];//探す先
          wqq[qqwidx]=w[tmp];
          qqwidx++;
        }
        tmp++;
      }
      
    }
    qqlen=qqwidx;
    REP(j,qqlen)qq[j]=qqqq[j];
    if (qqlen==0)break;
  }
    




  REP(i,n){
    cout<<(col[i]%2)<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 14592
a, b = map(int, input().split())
a1 = a
a2 = a-1
b1 = b
b2 = b-1

if a == b:
    ans = a1 + b1
elif a > b:
    ans = a1 + a2
elif b > a:
    ans = b1 + b2
print(ans) 


Measured memory_bytes: 2940
N,P=gets.split.map(&:to_i)
S=gets.chop.chars.map(&:to_i).reverse

if P==2 || P==5
  p S.each.with_index.inject(0){|s,(x,i)|(x%P).zero? ? s+N-i : s}
  exit
end

s=[0]
S.inject(1) do |p,i|
  s<<(s[-1]+i*p)%P
  (10*p)%P
end

n=Array.new(P){0}
s.each do |i| n[i]+=1 end

ans=0
s.each do |i|
  n[i]-=1
  ans+=n[i]
end
p ans


Measured memory_bytes: 19964
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>  // https://boostjp.github.io/tips/math.html
#include <boost/dynamic_bitset.hpp>  // https://boostjp.github.io/tips/dynamic_bitset.html

constexpr int64_t DIV1097 = 1000000007LL;

using namespace std;

int main()
{
    int64_t N, T;
    std::cin >> N >> T;

    std::vector<int64_t> V;
    for (decltype(N) i = 0; i < N; ++i) {
        int64_t t;
        std::cin >> t;
        V.push_back(t);
    }

    int64_t start, end, sum;
    start = end = sum = 0;

    for (int64_t i = 0; i < N; ++i) {
        if (V[i] <= end) {
            end = V[i] + T;
        }
        else {
            sum += end - start;
            start = V[i];
            end = start + T;
        }
    }

    sum += end - start;

    std::cout << sum << std::endl;

    return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long

int n;
int c[200001];

int main(void)
{
    int mx = -inf;
    cin >> n;
    rep(i,n)
    {
        int p;
        cin >> p;
        c[p] = c[p - 1] + 1;
        mx = max(mx, c[p]);
    }
    int res = n - mx;

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
     
     using namespace std;
     
     int main() {
     	int n;
     	int a[111];
     	memset(a, 0, sizeof(a));
     	scanf("%d", &n);
     	int ans = 0;
     	while (n--) {
     		int x;
     		scanf("%d", &x);
     		a[x]++;
     		if (a[x] == 1)
     			ans++;
    	 }
    	 printf("%d\n", ans);
    	 return 0;
     }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll count=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='R')
        {
            count++;
        }
    }
    ll white=s.size()-count;
    ll red = count;
    ll ans=0;
    for(ll i=0;i<count;i++)
    {
        if(s[i]!='R')
        {
            ans++;
        }
    }
    cout << ans;
    
    
} 


Measured memory_bytes: 3716
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 1000000000000001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  lli n;
  lli Nums[5];
  lli min = MAX;
  scanf("%lld", &n);
  rep(i, 0, 5) {
    scanf("%lld", &Nums[i]);
    min = min(min, Nums[i]);
  }

  lli ans = 5 + (n - 1) / min;
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define per(i,n,k) for(int i=n;i>=k;i--)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ll long long
using namespace std;
const int maxn=100005;
ll f[maxn];
ll n,w,ans;
int main()
{
	cin>>n>>w;
	rep(i,0,n-1)
	{
		int x,y;
		cin>>x>>y;
		per(j,w,x)
		{
			f[j]=max(f[j],f[j-x]+y);
		}
	}
	rep(i,0,w)
	{
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int n,m,t[500],p[500],x[500],sum,ans;
	while(scanf("%d",&n)!=EOF)
	{
	
	for(int i=1; i<=n; i++)
	scanf("%d",&t[i]);
	scanf("%d",&m);
	for(int i=1; i<=m; i++)
	{
		sum=0;
	scanf("%d%d",&p[i],&x[i]);
	ans=t[p[i]];
	t[p[i]]=x[i];
	for(int j=1; j<=n; j++)
	sum+=t[j];
	printf("%d\n",sum);
	t[p[i]]=ans;
}
}

	return 0;
	
}

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

int main()
{
    int N;
    int i, j;
    cin >> N;
    for(i = 1; i <= 9; i++) {
        for(j = 1; j <= 9; j++) {
            if((i*j) == N) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int a;
	string s;
	cin >> a >> s;
	if(a < 3200) {
		cout << "red" << endl;
	} else {
		cout << s << endl;
	}
}


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

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;

pair<int, int> next_v(int x, int y) {
    return make_pair(-y, x);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int x3 = next_v(x2 - x1, y2 - y1).first + x2;
    int y3 = next_v(x2 - x1, y2 - y1).second + y2;
    int x4 = next_v(x3 - x2, y3 - y2).first + x3;
    int y4 = next_v(x3 - x2, y3 - y2).second + y3;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pii pair<int,int> 
#define fi first
#define pb push_back
#define si second
#define int long long int
using namespace std;

int32_t main(){
	int a,b,c,r;
	cin>>a>>b>>c>>r;
	int ans=0;
	ans+=min(a,r);
	r-=a;
	r-=b;
	if(r>0)
	{
		ans-=r;
	}	
	cout<<ans<<"\n";
}

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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

#define ll long long
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)

#define xx first
#define yy second
#define mp make_pair
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define pdd pair<double,double>
#define ALL(v) (v).begin(), (v).end()

const ll MOD=1e9+7;
const ll inf=1e10;

#define MODSET(d) if ((d) >= MOD) d %= MOD;
#define MODNEGSET(d) if ((d) < 0) d = ((d % MOD) + MOD) % MOD;


ll power(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)
            ans=(ans*a);
        n>>=1;
        a=(a*a);
    }
    return ans;
}



ll powerMod(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)
            ans=(ans*a)%MOD;
        n>>=1;
        a=(a*a)%MOD;
    }
    return ans;
}

ll powerMod1(ll a,ll n,ll mod){
    ll ans=1;
    while(n){
        if(n&1)
            ans=(ans*a)%mod;
        n>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

ll lcm(ll a,ll b){
    return a*(b/__gcd(a,b));
}

ll sumdigit(ll n){
    ll sum=0;
    while(n){
        sum++;
        n=n/10;
    }
    return sum;
}

ll countSetBit(ll a){
    return __builtin_popcount(a);
}



ll length(ll a){
    ll ans=0;
    while(a){
        ans++;
        a=a/10;
    }
    return ans;
}

//const long sz=1e6+10;
int main()
{
    fast;
    ll t;
    //cin>>t;
    t=1;
    while(t--){
        ll n;
        cin>>n;
        ll ans=0;
        for(int i=1;i<=n;i++){
            if(sumdigit(i)&1)
                ans++;
        }
        cout<<ans;

    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	
	int count;
	int i,j,k;
	int target_value;
	
	scanf("%d", &count);
	
	int *input_data = (int *)malloc(sizeof(int) * count);
	
	for(i = 0; i < count; i++){
		scanf("%d", input_data + i);
	}
	
	for(i = 1; i < count; i++){
		
		for(k = 0; k < count; k++){
			
			if(k == count - 1){
				printf("%d\n", input_data[k]);
			}
			else{
				printf("%d ", input_data[k]);
			}
		}
		
		
		
		target_value = input_data[i];
		j = i - 1;
		
		while(j >= 0 && input_data[j] > target_value){
			input_data[j + 1] = input_data[j];
			j--;
		}
		
		input_data[j + 1] = target_value;
		

	
	}
	
	for(k = 0; k < count; k++){
		if(k == count - 1){
			printf("%d\n", input_data[k]);
		}
		else{
			printf("%d ", input_data[k]);
		}
	}
			
	
	free(input_data);
	
	return 0;
	
}

Measured memory_bytes: 600
N = int(input())
a = list(map(int, input().split()))


def remainder(a):
    a.sort()
    for i in range(1, len(a)):
        a[i] = a[i] % a[0]
    count = a.count(0)
    for i in range(count):
        a.remove(0)
    if len(a) == 1:
        return a
    return remainder(a)


print(remainder(a)[0])


Measured memory_bytes: 14224
#include <stdio.h>

int main()
{
    int n, x, i, j, k;
    while (scanf("%d %d", &n, &x) != EOF)
    {
        int ans = 0;
   if(n == 0 && x == 0)
    {
        break;
    }
        for(i = 1; i < n-1; i++)
        {
            for(j = i + 1; j < n; j++)
            {
                for(k = j+1; k < n+1; k++)
                {
                    if(x == i + j + k)
                    {
                        ans++;
                    }
                }
                
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}



Measured memory_bytes: 2748
#include <iostream>
#include <queue>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    int k, t; cin >> k >> t;
    priority_queue<pair<int,int> > que;
    repeat (i, t) {
        int a; cin >> a;
        que.emplace(a, i);
    }
    int ans = 0;
    int last = -1;
    while (not que.empty()) {
        int a, i; tie(a, i) = que.top(); que.pop();
        if (i != last) {
            last = i;
            a -= 1;
            if (a) que.emplace(a, i);
        } else {
            if (que.empty()) { ans += a; break; }
            int b, j; tie(b, j) = que.top(); que.pop();
            last = j;
            b -= 1;
            que.emplace(a, i);
            if (b) que.emplace(b, j);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll N,M;
	cin>>N>>M;
	vector<ll>v;
	for(ll i=1;i*i<=M; i++){
		if(M%i==0){
			v.push_back(i);
          	v.push_back(M/i);
		}
	}
  	ll n=v.size();
  	sort(v.rbegin(),v.rend());
	for(ll i=0; i<n; i++){
      		if(v[i]*N<=M){
			cout<<v[i]<<endl;
			return 0;
		}
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
    long long n,m;
    scanf("%lld %lld",&n,&m);
    long long ans = min(n, m/2);
    m -= ans*2;
    printf("%lld\n",ans + m/4);
}

Measured memory_bytes: 256
from collections import defaultdict
mod=10**9+7
n=int(input())
sosu_list=[2]
for i in range(3,1002, 2):
    flag=0
    for j in range(2,int(i**.5)+1):
        if i%j==0:
            flag+=1
            break
    if flag==0:
        sosu_list.append(i)
shukei=defaultdict(int)
for i in range(1,n+1):
    soinsu=defaultdict(int)
    for sosu in sosu_list:
        t=i
        while t>0:
            if t%sosu==0:
                soinsu[sosu]+=1
                t//=sosu
            else:
                break
    for a,b in soinsu.items():
        shukei[a]+=b
ans=1
for a in shukei.values():
    ans*=(a+1)
    ans%=mod
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

ll pow5(ll x){
    ll ret = 1;
    REP(i,5) ret *= x;
    return ret;
}

int main(void){
    ll x = in();
    map<ll, ll> mp;
    for (ll a = 0; a <= 1000; a++){
        ll a5 = pow5(a);
        ll b5 = a5 - x;
        if (b5 >= 0){
            if (mp.count(b5)){
                cout << a << " " << mp[b5] << endl;
                return 0;
            }
        }else{
            if (mp.count(-b5)){
                cout << a << " " << -mp[-b5] << endl;
                return 0;
            }
        }
        mp[a5] = a;
    }
    return 0;
}


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

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

int main(){
  long long Q,H,S,D,N;
  cin >> Q >> H >> S >> D >> N;

  long long one=min({Q*4,H*2,S});
  cout << min(one*N,D*(N/2)+one*(N%2)) << endl;

  return 0;
}


Measured memory_bytes: 256
def main():
    X, K, D = (int(i) for i in input().split())

    if X > 0:
        t = X // D
        if t <= K:
            X -= D*t
            K -= t
        else:
            X -= D*K
            print(X)
            return
        if K % 2 == 0:
            print(X)
        else:
            print(min(abs(X-D), X+D))
    elif X < 0:
        X = -X
        t = X // D
        if t <= K:
            X -= D*t
            K -= t
        else:
            X -= D*K
            print(abs(-X))
            return
        if K % 2 == 0:
            print(abs(-X))
        else:
            print(abs(min(abs(-X-D), abs(-X+D))))
    else:
        # X == 0
        if K % 2 == 0:
            print(0)
        else:
            print(D)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61968
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
double a,b,h,m;
int main(){
	ios::sync_with_stdio(0);
	cin>>a>>b>>h>>m;
	double c=h*30+m*0.5;
	double d=m*6;
	double cha=abs(c-d);
	if(cha>180)
	cha=360-cha;
	double ans=a*a+b*b-2*a*b*cos(cha*acos(-1)/(double)(180));
	cout<<fixed<<setprecision(20)<<sqrt(ans);
	re 0;
}

Measured memory_bytes: 4240
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int cards[4][13];

    for(int i=0;i<4;i++){
        for(int j=0;j<13;j++){
            cards[i][j] = 0;
        }
    }
    for(int i=0;i<n;i++){
        string SHCD;
        int num;

        cin >> SHCD >> num;

        if(SHCD == "S"){
            cards[0][num-1] = 1;
        }else if (SHCD == "H")
        {
            cards[1][num-1] = 1;
        }else if (SHCD == "C")
        {
            cards[2][num-1] = 1;
        }else if (SHCD == "D")
        {
            cards[3][num-1] = 1;
        }
    }
    
    for(int i=0;i<4;i++){
        for(int j=0;j<13;j++){
            if(cards[i][j] == 0){
                if(i==0){
                    cout << "S";
                }else if (i==1)
                {
                    cout << "H";
                }else if (i==2)
                {
                    cout << "C";
                }else if (i==3)
                {
                    cout << "D";
                }
                
                cout << " " << j+1 << endl;
                
                
            }
        }
    }
}


Measured memory_bytes: 3144
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    s = [ii() for i in range(N)]
    s.sort()
    ans = sum(s)
    if ans%10:
        print(ans)
        return
    for i in range(N):
        if (ans-s[i])%10!=0:
            print(ans-s[i])
            return
    print(0)

if __name__ == '__main__':
    main()


Measured memory_bytes: 62232
L = int(input())
A_list = [0]*L
for i in range(L):
    A_list[i] = int(input())

DP = [0]*5
for i in range(L):
    # 全て
    r0 = A_list[i]
    # 通過する場合
    r1 = (A_list[i] + 1) % 2
    # 往復する場合
    if A_list[i] == 0:
        r2 = 2
    else:
        r2 = A_list[i] % 2
    
    DP[4] = min(DP[0], DP[1], DP[2], DP[3], DP[4]) + r0
    DP[3] = min(DP[0], DP[1], DP[2], DP[3]) + r2
    DP[2] = min(DP[0], DP[1], DP[2]) + r1
    DP[1] = min(DP[0], DP[1]) + r2
    DP[0] = DP[0] + r0
    
print(min(DP))

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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  if (A >= K) {
    cout << K << endl;
  } else if ( (A < K) && ( (A + B) >= K ) ) {
    cout << A << endl;
  } else {
    cout << 2*A + B - K << endl;
  }
}

Measured memory_bytes: 3636
import queue
import sys
sys.setrecursionlimit(1000000)

n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
    
P=[-1]*n #親格納配列
q=queue.Queue()
q.put(0)
while not q.empty(): #qが空になるまで(BFS:幅優先探索)
    now=q.get() #取り出す
    for i in G[now]:
        if P[i]==-1 and i!=0: #未探索の場合
            P[i]=now #親を記録
            q.put(i) #親としてqに入れる
print("Yes")
for i in range(1,n):
    print(P[i]+1)

Measured memory_bytes: 97124
from collections import  *
def io():
    return map(int,input().split())
def op():
    return list(map(int,input().split()))
# for _ in range(int(input())):
k=int(input())
a,b=io()
for i in range(a,b+1):
    if i%k==0:
        print('OK')
        break
else:
    print('NG')

Measured memory_bytes: 9484
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
using namespace std;


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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF;
    string str;
    cin>>n;
    ll sum=0;
    vector<ll> v(n);
    //m=n;
    m=1;
    rep(i,n) {
        cin>>a;
        if(a%2==0) m*=2;
    }
    sum=1;
    for(ll i=1;i<=n;i++) sum*=3;
    cout<<sum-m<<endl;


    return 0;
}


Measured memory_bytes: 256
N = int(input())
D = {}
for x in range(2, N+1):
    y = 2
    while y*y <= x:
        if x % y == 0:
            c = 0
            while x % y == 0:
                x //= y
                c += 1
            D[y] = D.get(y, 0) + c
        y += 1
    if x > 1:
        D[x] = D.get(x, 0) + 1

*P, = D.items()
M = len(P)
memo = {}
def dfs(i, c):
    key = (i, c)
    if key in memo:
        return memo[key]
    if c == 75:
        return 1
    if i == M:
        return 0
    k, v = P[i]
    r = 0
    for j in range(v+1):
        if c*(j+1) <= 75:
            r += dfs(i+1, c*(j+1))
    memo[key] = r
    return r
print(dfs(0, 1))

Measured memory_bytes: 3316
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 1
    mod = 10 ** 9 + 7
    for i in range(n):
        A[i] += 1

    cnt = [0] * (n + 1)  # cnt[i]は、Aのなかでこれまでに何個iが登場したか。つまりiの候補数。
    cnt[0] = 3

    for j in range(n):
        i = A[j]
        ans *= cnt[i - 1]
        cnt[i - 1] -= 1
        cnt[i] += 1
        if cnt[i] > 3:
            ans = 0
        if cnt[i - 1] < 0:
            ans = 0
    print(ans % mod)


resolve()

Measured memory_bytes: 53868
from __future__ import print_function

import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# import math
# import string
# import fractions
# from fractions import Fraction
# from fractions import gcd

# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
# import itertools
# import bisect
# import heapq


# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# def reduce(p, q):
#     common = fractions.gcd(p, q)
#     return (p//common , q//common )
# # from itertools import accumulate
# # from collections import deque

# from operator import mul
# from functools import reduce

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# import random

def crange(m,n):
    return range(m,n+1)

def main():
    n,m = map(int, input().strip().split())
    a = [0 for _ in range(m)]
    for i in range(m):
       a[i]  = int(input().strip())
    a = set(a)
    #eprint("a ",end=": ")
    #eprint(a)
    l=[0 for _ in crange(0,n)]
    l[0]=1
    l[1]=0 if 1 in a else 1
    for i in crange(2,n):
        l[i] = 0 if i in a else l[i-2] + l[i-1]
        #eprint("l[",i,"] ",end=": ")
        #eprint(l[i])
    print(l[n]%(10**9 + 7))


    return

if __name__ == '__main__':
    main()


'''
find a_cnt such that
for given
n (1<=n<=10**5),
m (0<=m<=n-1),
when m>=1 then 列[a_i] ( 1<=i<=m<=n-1,1<= a[i]<=n-1),

let T := { (i,j) in [0...n]**2 | i + 2*j == n and } # i,j はそれぞれ「1段登る」「2段登る」コマンドﾞを使った回数

let 列 B :=[b[i] \in {1,2}] and sum(B)==n and \forall i in [0...].sum(B[0:i]) \notin





n=|T|


'''


Measured memory_bytes: 471476
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <tuple>
#include <numeric>

using namespace std;

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

    int memo[101] = {0};
    memo[a] = 1;
    memo[b] = 1;
    memo[c] = 1;

    // cout << accumulate(memo, memo + SIZE_OF_ARRAY(memo), 0) << endl;
    cout << accumulate(begin(memo), end(memo), 0) << endl; // c++11以降の記述

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 1;
		while (true) {
			int x = i;
			if (x % 3 == 0) {
				System.out.print(" " + i);
			} else {
				while (true) {
					if (x % 10 == 3) {
						System.out.print(" " + i);
						break;
					}
					x /= 10;
					if (x != 0)
						continue;
					else
						break;
				}
			}
			if (++i <= n)
				continue;
			else
				break;
		}
		System.out.println();
	}
}

Measured memory_bytes: 28400
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, k, a[5001], dp[2][5001];

bool noneed(ll nowi){
	for(ll i = 1; i <= k; i++){dp[0][i] = 0;}
	dp[0][0] = 1;
		
	for(ll i = 1; i <= n; i++){
		if(i != nowi){
			for(ll j = 0; j <= k; j++){dp[1][j] = 0;}
			
			for(ll j = 0; j <= k; j++){
				if(dp[0][j] == 1){
					dp[1][j] = 1;
					if(j+a[i] <= k){dp[1][j+a[i]] = 1;}
				}
			}
			for(ll j = 0; j <= k; j++){dp[0][j] = dp[1][j];}
		}
	}
	
	for(ll i = max((ll) 0, k-a[nowi]); i <= k-1; i++){
		if(dp[0][i] == 1){return false;}
	}
	return true;
}

int main() {
	cin >> n >> k;
	for(ll i = 1; i <= n; i++){cin >> a[i];}
	sort(a+1, a+n+1);
	
	ll ansmax = n+1;
	ll ansmin = 0;
	while(ansmin+1 != ansmax){
		ll mid = (ansmax+ansmin)/2;
		if(noneed(mid)){ansmin = mid;}
		else{ansmax = mid;}
		//cout << ansmin << endl;
	}
	
	cout << ansmin << endl;
	return 0;
}

Measured memory_bytes: 384
h, w = map(int, input().split())
a = [input() for i in range(h)]
for i in range(h-1):
    for j in range(1,w):
        if a[i][j] == "#":
            if a[i+1][j-1] == "#":
                print("Impossible")
                exit()
print("Possible")


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	
	private static int[] sequence;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		int length = 1;
		while(length < n){
			length <<= 1;
		}
		sequence = new int[length + 1];
		for(int i = 0; i < q; i++){
			int com = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			if(com == 0){
				add(x, y);
			}else{
				System.out.println(getSum(x, y));
			}
		}
		sc.close();
	}
	
	private static void add(int index, int num){
		if(index > 0 && index < sequence.length){
			sequence[index] += num;
			int nextIndex = index + (index & -index);
			add(nextIndex, num);
		}
	}
	
	private static int getSum(int s, int t){
		return getSum(t) - getSum(s - 1);
	}
	
	private static int getSum(int index){
		if(index > 0 && index < sequence.length){
			int prevIndex = index - (index & -index);
			return sequence[index] + getSum(prevIndex);
		}else{
			return 0;
		}
	}
}

Measured memory_bytes: 96160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
  string str;
  cin>>str;
  ll N=str.size(),count=0;
  for(ll i=0;i<N;i++){
    if(str.at(i)==str.at(N-i-1)){count++;}
  }
  for(ll i=0;i<(N-1)/2;i++){
    if(str.at(i)==str.at((N-1)/2-i-1)){count++;}
  }
  for(ll i=0;i<(N-1)/2;i++){
    if(str.at(N-i-1)==str.at((N+3)/2+i-1)){count++;}
  }
  if(count==2*N-1){cout<<"Yes"<<endl;}
  else{cout<<"No"<<endl;}
}

Measured memory_bytes: 256