akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <string.h>
#include <string>
#include <cmath>
#include <cstdio>
#include <functional>
#include <map>
#include <typeinfo>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;


int main()
{
  char c;
  scanf("%c", &c);
  
  printf("%c\n", c+1);
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using LL = long long;
using P = pair<int,int>;


int main(){
	LL N;cin >>N;
	vector<LL> A(100050);
	LL ans = 0;
	rep(i,N) {
		int tmp;cin >> tmp;
		++A[tmp];
		ans += tmp;
	}
	int Q;cin >> Q;
	rep(i,Q){
		int B, C;
		cin >> B >> C;
		A[C] += A[B];
		ans += (C-B)*A[B];	
		A[B] = 0;
		cout << ans << endl;
	}	
}













Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
 
//Made with <3 by MinumCoklatPanas
typedef long long ll;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAXN = 510;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double INFD = 1E9;
const double EPS = 1e-9;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	if (s.find('7') != string::npos)
		cout << "Yes\n";
	else
		cout << "No\n";
	return 0;
}

Measured memory_bytes: 3652
def test():
    n = int(input())
    d,x = map(int,input().split())
    count = 0
    for i in range(n):
        a = int(input())
        b = [i*a+1 for i in range(d)]
        for j in range(d):
            if b[j]<=d:
                count += 1
    print(count+x)


if __name__ == "__main__":
    test()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int N, A;
int x[50];
long p[100][100][10000];
//-----------------------------------------------------------------
int main() 
{
	
	cin >> N >> A;
	for (int i = 0; i < N; i++) cin >> x[i];
 
	p[0][0][0] = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < 2500; k++)
			{
				if(p[i][j][k])
				{
					p[i + 1][j][k] += p[i][j][k];
					p[i + 1][j + 1][k + x[i]] += p[i][j][k];
				}
			}
		}
	}  
 
	long ans = 0;
	for(int i = 1; i < N + 1; i++) ans += p[N][i][i*A];
	cout << ans << endl;
}

Measured memory_bytes: 203008
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

int n,k;
map<int,int> mp;
int x;
 
bool check(int x){
	while(x){
		int tmp=x%10;
		if(mp[tmp]){
			return false;
		}
		x/=10;
	}
	return true;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
  	cin>>n>>k;
  	 for(int i=1;i<=k;++i){
  	 	cin>>x;
  	 	mp[x]++;
  	 }

  	 for(int i=n;i<=1000000;++i){
  	 	if(check(i)){
  	 		cout<<i<<endl;
  	 		return 0;
  	 	}
  	 }



    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <utility>
using namespace std;

typedef pair<int,int> P;

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back

struct edge {
  int to, cost, time;
  edge(int a, int b, int c): to(a), cost(b), time(c) {}
};

const int MAX_M = 100, INF = 10000000;
int n, m;

vector<edge> E[MAX_M+1];

void solve() {
  rep(i,MAX_M+1) E[i].clear();
  
  rep(i,n) {
    int a, b, cost, time; cin>>a>>b>>cost>>time;
    E[a].push_back(edge(b, cost, time));
    E[b].push_back(edge(a, cost, time));
  }
  int zz; cin>>zz;
  rep(z,zz) {
    int p, q, r; cin>>p>>q>>r;
    // dijkstra
    int d[MAX_M+1];
    fill(d, d+MAX_M+1, INF);
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, p));
    d[p] = 0;
    while (!que.empty()) {
      P p = que.top(); que.pop();
      int td = p.first, ti = p.second;
      if (d[ti] < td) continue;
      rep(i,E[ti].size()) {
        edge e = E[ti][i];
        if (r == 0) {
          if (d[e.to] > d[ti] + e.cost) {
            d[e.to] = d[ti] + e.cost;
            que.push(P(d[e.to], e.to));
          } 
        } else {
          if (d[e.to] > d[ti] + e.time) {
            d[e.to] = d[ti] + e.time;
            que.push(P(d[e.to], e.to));
          }
        }
      }
    }
    cout<<d[q]<<endl;
  }
}

int main (int argc, char const* argv[]) {
  while (cin>>n>>m, n||m) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 996
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  ll int n,w1;
  cin>>n>>w1;
  ll int  w[n+1],v[n+1],sum=0;
  for(int i=1;i<=n;i++)
  {
    cin>>w[i]>>v[i];
    sum+=v[i];
  }
  vector<ll int>dp(sum+1,1000000000);
  dp[0]=0;
   for(int i=1;i<=n;i++)
   {
     for(ll int j=sum-v[i];j>=0;j-=1)
     {
       dp[j+v[i]]=min(dp[j+v[i]],w[i]+dp[j]);
     }
   }
  ll int ans=0;
  for(ll int i=sum;i>=0;i-=1)
  {
    if(dp[i]<=w1)
    {
    ans=max(ans,i);
    }
  }
  cout<<ans;
  return 0;
}
    
  


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const int maxn=305;
const int M=998244353;
int n,ans;
char s[maxn];
bool f[maxn][maxn][maxn],g[maxn][maxn][maxn];
int dp[maxn][maxn][maxn];

void add(int &x,int y){
    x+=y; if(x>=M) x-=M;
}

int main(){
    scanf("%s",s+1); n=strlen(s+1);
    f[0][0][0]=1;
    for (int i=0;i<=n-1;i++)
    for (int j=0;j<=n;j++)
    for (int k=0;k<=n;k++) if (f[i][j][k]){
        // x:0   y:1
        int x=k,y=j-i-k;
        g[n-j][x][y]=1;
        if (i==n-1) continue;
        if (x>=2) f[i+1][j][k-1]=1;
        if (x>=1&&y>=1) f[i+1][j][k-1]=1,f[i+1][j][k]=1;
        if (y>=2) f[i+1][j][k]=1;
        if (j<n){
            if (s[j+1]=='0'){
                if (x>=1) f[i+1][j+1][k]=1;
                if (y>=1) f[i+1][j+1][k]=f[i+1][j+1][k+1]=1;
            } else {
                if (x>=1) f[i+1][j+1][k-1]=f[i+1][j+1][k]=1;
                if (y>=1) f[i+1][j+1][k]=1;
            }
        }
        if (j<n-1){
            int zeros=(s[j+1]=='0')+(s[j+2]=='0');
            if (zeros==2){
                f[i+1][j+2][k+1]=1;
            } else if (zeros==1){
                f[i+1][j+2][k]=f[i+1][j+2][k+1]=1;
            } else {
                f[i+1][j+2][k]=1;
            }
        }
    }
    for (int i=1;i<=n;i++)
    for (int j=0;j<=n;j++)
    for (int k=0;k<=n;k++){
        if (s[n-i+1]=='0') g[i][j][k]|=g[i-1][j+1][k];
        else g[i][j][k]|=g[i-1][j][k+1];
    }
    dp[0][0][0]=1;
    for (int i=0;i<=n;i++)
    for (int j=0;j<=n;j++)
    for (int k=0;k<=n;k++){
        if (s[n-i]=='0'){
            add(dp[i][j][k+1],dp[i][j][k]);
        } else if (s[n-i]=='1') {
            add(dp[i][j+1][k],dp[i][j][k]);
        }
        add(dp[i+1][j][k],dp[i][j][k]);
        if (g[i][j][k]) {
            if (i+j+k) add(ans,dp[i][j][k]);
            //cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<endl;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 148436
s = input()
t = s[::-1]
rf = rb = 0 
for i in range(len(s)):
    if s[i] =="A":
        rf = i
        break
for i in range(len(s)):
    if t[i] =="Z":
        rb = len(s)-i-1
        break
print(rb-rf+1)

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

int a[100];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    long long p = 1000;
    for(int i = 1; i < n; i ++) {
        if(a[i] < a[i + 1]) p = (p / a[i]) * a[i + 1] + p % a[i];
    }
    printf("%lld\n", p);
}


Measured memory_bytes: 3864
#include <iostream>
#include <vector>
#include <iomanip>
#include <stack>
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <time.h>
#include <complex>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n;i>0;i--)
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define SORT(v) sort((v).begin(),(v).end())
#define TEMP(type,x,y) do {temp temp=x,x=y,y=temp}while(0)
const ll INF = (1LL << 50);
const ll mod = 1'000'000'007;

int main() {

	int N, M;
	cin >> N >> M;

	vector<ll>isSafe(N + 1, 1);

	REP(i, M) {
		int a;
		cin >> a;
		isSafe[a] = 0;
	}


	vector<ll>dp(N + 1, 0);

	dp[0] = 1;
	if (isSafe[1]) dp[1] = 1;//初期値として２つの値が必要
	
	for (int i = 2; i <= N; i++) {
		if (isSafe[i - 1]) dp[i] += dp[i - 1];
		if (isSafe[i - 2]) dp[i] += dp[i - 2];//i-1,i-2ともに0であると、dp[i]=0となり、dp[N]も0となる
		dp[i] %= mod;
	}

	cout << dp[N] << endl;

}

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

int main()
{
    ll n;
    cin>>n;
    ll arr[n+1],b[n+1];
    for(ll i=0;i<=n;i++)
        arr[i]=0;
    for(ll i=2;i<=n;i++)
        {
            cin>>b[i];
            arr[b[i]]++;
        }
    for(ll i=1;i<=n;i++)
    cout<<arr[i]<<endl;
   return 0; 
}

Measured memory_bytes: 6712
#include <stdio.h>
#include <string.h>
#define MAX 1001

int main() {
  int q, k, c[MAX][MAX], i, j, m, n;
  char X[MAX], Y[MAX];
  
  scanf( "%d" , &q );
  for ( k=0; k<q; k++ ) {
    scanf( "%s" , X );
    scanf( "%s" , Y );
    m = strlen(X);
    n = strlen(Y);

    for ( i=1; i<=m; i++ ) c[i][0] = 0;
    for ( j=1; j<=n; j++ ) c[0][j] = 0;
    for ( i=1; i<=m; i++ )
      for ( j=1; j<=n; j++ ) {
	if ( X[i-1] == Y[j-1] ) c[i][j] = c[i-1][j-1] + 1;
	else if ( c[i-1][j] >= c[i][j-1] ) c[i][j] = c[i-1][j];
	else c[i][j] = c[i][j-1];
      }

    printf( "%d\n" , c[m][n] );
  }
  
  return 0;
}





Measured memory_bytes: 5756
N = int(input())
As = [int(input()) for i in range(N)] + [0]

ans = 0
for i in range(N):
    # As[i]内でペアを作る
    ans += As[i] // 2
    As[i] %= 2

    # As[i]が1つ残って、As[i+1]も1つ以上あるならば、ペアを1つ作る
    if As[i] and As[i + 1]:
        ans += 1
        As[i] -= 1
        As[i + 1] -= 1

print(ans)


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

using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n); i > 0; i--)
#define all(n) n.begin(), n.end()
#define print(n) cout << n << endl

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    ll s,w;
    cin >> s >> w;
    if(w>=s) print("unsafe");
    else print("safe");
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// string to int : -48
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll k, n;
    cin >> k >> n;

    vector<long long> vec(n);
    vector<long long> res(n);

    rep(i,n){
        cin >> vec[i];
        if(i == 0){
            res[i] = vec[i];
        }else{
            res[i] = vec[i] - vec[i-1];
        }
    }
    res[0] += (k - vec[n-1]);

    ll tmp = 0;


    rep(i,n){
        chmax(tmp, res[i]);
    }

    /*
    rep(i,n){
        cout << res[i] << " ";
    }
    br;
    */
    cout << k - tmp << endl;

    

}

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

using namespace std;

const int MAX=100;
const int INF=1<<25;

class edge
{
public:
	int to,cap,cost,rev;
	edge(){}
	edge(int to,int cap,int cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
};

int V;
vector<edge> G[MAX];
int dist[MAX];
int prevv[MAX],preve[MAX];

void add_edge(int from,int to,int cap,int cost)
{
	G[from].push_back(edge(to,cap,cost,G[to].size()));
	G[to].push_back(edge(from,0,-cost,G[from].size()-1));
	return;
}

int mincostflow(int s,int t,int f)
{
	int res=0;
	while(f>0)
	{
		fill(dist,dist+V,INF);
		dist[s]=0;
		bool update=true;
		while(update)
		{
			update=false;
			for(int v=0;v<V;v++)
			{
				if(dist[v]==INF)continue;
				for(int i=0;i<G[v].size();i++)
				{
					edge &e=G[v][i];
					if(e.cap>0&&dist[e.to]>dist[v]+e.cost)
					{
						dist[e.to]=dist[v]+e.cost;
						prevv[e.to]=v;
						preve[e.to]=i;
						update=true;
					}
				}
			}
		}
		
		if(dist[t]==INF)return -1;
		
		int d=f;
		for(int v=t;v!=s;v=prevv[v])d=min(d,G[prevv[v]][preve[v]].cap);
		f-=d;
		res+=d*dist[t];
		
		for(int v=t;v!=s;v=prevv[v])
		{
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}

int main()
{
	int E,F;cin>>V>>E>>F;
	int u,v,c,d;
	for(int i=0;i<E;i++)
	{
		cin>>u>>v>>c>>d;
		add_edge(u,v,c,d);
	}
	cout<<mincostflow(0,V-1,F)<<endl;
	return 0;
}

Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
#define rep(i,b) for(i=0;i<b;++i)
#define repp(i,a,b) for(i=a;i<b;++i)
#define endl "\n"
//#define LLONG_MAX 99999999999999
typedef long long int lli;
int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    lli n,i,j,b,a,q,m;
    lli t=1;
    //cin>>t;
    while(t--){
        cin>>n;
        a=ceil(double(n)/1000.0);
        b=a*1000-n;
        cout<<b<<endl;
    }


}



Measured memory_bytes: 3712
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define PI 3.14159265359
#define MOD 1000000007
typedef long long LL;

template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> void print_vector(vector<T> vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << "]" << endl;
}
template<class T> void print_pair_vector(vector<pair<T, T> > vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << "(" << vec[i].first << "," << vec[i].second << ") ";
	}
	cout << "]" << endl;
}

const int INF = 1 << 30;

int main(void) {
	LL N, M;
	cin >> N >> M;

	vector<vector<LL> > energydrink(N, vector<LL>(2));
	rep(i, N) cin >> energydrink[i][0] >> energydrink[i][1];
	sort(ALL(energydrink));

	LL sum = 0;
	LL required_money = 0;
	rep(i, N) {
		if (energydrink[i][1] + sum <= M) {
			sum += energydrink[i][1];
			required_money += energydrink[i][0] * energydrink[i][1];
		}
		else {
			required_money += (M - sum) * energydrink[i][0];
			break;
		}
	}

	cout << required_money << endl;
	return 0;
}

Measured memory_bytes: 5760
k = int(input())
a = list(map(int, input().split()))

def solve(num, checker):
    return checker*(num//checker)

left, right = 0, max(a)*k + 2
while left+1 < right:
    middle = (left+right)//2
    num = middle
    for i in a:
        num = solve(num, i)
    if num <= 2:
        left = middle
    else:
        right = middle
x = left

left, right = 0, max(a)*k + 2
while left+1 < right:
    middle = (left+right)//2
    num = middle
    for i in a:
        num = solve(num, i)
    if num < 2:
        left = middle
    else:
        right = middle
        
y = right
if x < y:
    print(-1)
else:
    print(y, x)

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

bool find(string s, string p) {
    if (s.size() < p.size()) {
        swap(s, p);
    }
    for (int i = 0; i < s.size()-p.size()+1; i++) {
        for (int j = 0; j < p.size(); j++) {
            if (s.at(i+j) != p.at(j)) {
                break;
            }
            if (j == p.size()-1) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    string s, p;
    cin >> s >> p;
    s += s;
    if (find(s,p)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    // if (s.find(p) != -1) {
    //     printf("Yes\n");
    // } else {
    //     printf("No\n");
    // }
}


Measured memory_bytes: 3220
#include <stdio.h>
#include <string.h>

int main(void)
{
    char a[20], b[20];
    int i, len;

    scanf("%s", a);
    len = strlen(a);
    for (i = 0; i < len; i++)
        b[i] = a[len - i - 1];
    b[len] = '\0';
    printf("%s\n", b);

    return 0;
}

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

// clang-format off
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); --(i))

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define endl '\n'
#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

void solver() {
    string s;
    cin >> s;
    
    cout << string(s.size(), 'x') << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
const ll fact_table = 5000000;
double Pi = 3.1415926535897932384626;
 
//vector<ll> G[550010];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
//ll mod = 998244353;
ll mod = 1000000007;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
 */
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k;
ll ans;
ll x[500005], y[500005], z[500005];
char s[400004];

int main(){
    cin >> n;
    bool ok = false;
    for(int i=1;i<=n;i++){
        // 合計がi個
        ll reside = n - i * 100;
        if(0 <= reside && reside <= 5 * i){
            ok = true;
        }
    }
    p(ok);
    return 0;
    
}


















Measured memory_bytes: 13952
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000
#define MAX_M 100000
#define vec vector<int>
#define vecst vector<string>
#define vecch vector<char>
#define vecf vector<float>
#define vecvec vector<vector<int>>
#define vecHvec vector<vector<char>>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int INF = 1e9;
#define PI 3.141592653589793
// cout << setprecision(15) << std::fixed;

int main(){
    string s;
    cin>>s;
    int n=s.size();
    ll ans=0;
    for(int bit=0;bit<1<<(n-1);bit++){
        ll sm=0;
        ll a=s[0]-'0';
        for(int i=0;i<n-1;++i){
            if(bit & (1<<i)){
                sm+=a;
                a=0;
            }
            a=a*10+s[i+1]-'0';
        }
        sm+=a;
        ans+=sm;
    }
    cout<<ans<<endl;
 }


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#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()
{
	int n, h;
	cin >> n >> h;
	int ans = 0;
	vector<P> p(n);
	int second_max = 0;
	rep(i, n) {
		cin >> p[i].second >> p[i].first;
		second_max = max(second_max, p[i].second);
	}
	sort(p.rbegin(), p.rend());
	int index = 0;
	while (second_max < p[index].first) {
		index++;
		if (index == n)	break;
	}
	int tmp_i = 0;
	while (0 < h && tmp_i < index) {
		h -= p[tmp_i].first;
		tmp_i++;
		ans++;
	}
	if (h <= 0) {
		cout << ans << endl;
		return 0;
	}
	ans += h / second_max;
	if (h % second_max != 0)	ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4036
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int check(vector<int> hoge,vector<int> flower){
    int ans=0;
    
    for(int i=0;i<hoge.size();i++){
        if(flower.at(i)>=hoge.at(i)) ans++;
    }
    
    return ans;
}

int main(){
    int n;
    cin>>n;
    vector<int> hoge(n);
    vector<int> flower(n,0);
    long long ans=0;
    
    for(int i=0;i<n;i++) cin>>hoge.at(i);
    
    while(check(hoge,flower)<n){
        int wall=0;
        if(flower.at(0)>=hoge.at(0)) wall--;
        bool flag=false;
        
        for(int i=0;i<n;i++){
            if(flower.at(i)>=hoge.at(i)){
                if(!flag) flag=true;
            }else{
                if(flag){
                    wall++;
                    flag=false;
                }
            }
        }
        
        ans+=wall+1;
        
        for(int i=0;i<n;i++) flower.at(i)++;
    }
    
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc111/tasks/arc103_a
from collections import Counter
n = int(input())
nums = [int(i) for i in input().split()]

odd = Counter(nums[1::2]).most_common()
even = Counter(nums[::2]).most_common()
odd.append((0, 0))
even.append((0, 0))
if odd[0][0] != even[0][0]:
    ans = n - (odd[0][1] + even[0][1])
else:
    s = n - (odd[0][1] + even[1][1])
    t = n - (odd[1][1] + even[0][1])
    ans = min(s, t)
print(ans)
'''
6
1 1 1 1 2 1
'''

Measured memory_bytes: 95744
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;
    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    int a = 0;
    int b = 2;
    long sa1 = A[0];
    long sa2 = A[1];
    long sb1 = A[2];
    long sb2 = B[N] - B[3];
    long ans = 1L << 59;
    
    foreach (i; 2..N-1) {
        while (a < i-1 && sa1 + A[a+1] <= sa2 - A[a+1]) sa1 += A[a+1], sa2 -= A[a+1], a += 1;
        while (b < N-1 && sb1 + A[b+1] <= sb2 - A[b+1]) sb1 += A[b+1], sb2 -= A[b+1], b += 1;
        Tuple!(long, long)[] x = [tuple(sa1, sa2)];
        Tuple!(long, long)[] y = [tuple(sb1, sb2)];
        if (a < i - 1) x ~= tuple(sa1 + A[a+1], sa2 - A[a+1]);
        if (b < N - 1) y ~= tuple(sb1 + A[b+1], sb2 - A[b+1]);
        foreach (u; x) foreach (v; y) ans = min(ans, max(u[0], u[1], v[0], v[1]) - min(u[0], u[1], v[0], v[1]));

        sa2 += A[i];
        sb1 -= A[i];
        if (b == i) {
            b = i + 1;
            sb1 = A[i+1];
            sb2 = B[N] - B[i+2];
        }
    }

    ans.writeln;
}


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

using ll = long long;
using ii = pair<int, int>;

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

  int x, a;

  cin >> x >> a;

  if (x < a) cout << 0;
  else cout << 10;
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 3592
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using namespace std;
long long f[100][10];
long long p[100][11];
long long d[10];
long long n;

int main() {
	int m;
	cin >> n >> m;
	cout << int((100 * (n - m) + m * 1900) * pow(2,m)) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b;
    cin >> a >> b;
    int r = a * b;
    if( r % 2 ) cout << "Odd";
    else cout << "Even";
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
int main(){
  int n,m,p,y,t,c=0;
  std::pair<int,int> v[100001],w[100001];
  std::map<std::pair<int,int>,std::string> mp;
  std::cin>>n>>m;
  for(int i=0;i!=m;++i){
    std::cin>>p>>y;
    v[i] = {p,y};
    w[i] = v[i];
  }
  std::sort(w,w+m);
  t=w[0].first;
  for(int i=0;i!=m;++i){
    std::string s(12,'0');
    if(t!=w[i].first){
      c = 0;
      t = w[i].first;
    }
    ++c;
    for(int i=0;i<=std::log10(t);++i)s[5-i] = '0' + (int)(t/std::pow(10,i))%10;
    for(int i=0;i<=std::log10(c);++i)s[11-i] = '0' + (int)(c/std::pow(10,i))%10;
    mp[std::make_pair(t,w[i].second)]=s;
  }
  for(int i=0;i<m;++i){
    std::cout<<mp[v[i]]<<"\n";
  }
}

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

int main(){
  int a,b,c,N;
  cin>>N>>c;
  vector<int> X(100010,0);
  vector<pair<int,pair<int,int>>> Q;
  for(int i=0;i<N;i++){
    cin>>a>>b>>c;
    Q.push_back({c,{a,b}});
  }
  sort(Q.begin(),Q.end());
  
  for(int i=0;i<N;i++){
    a=Q[i].second.first;
    b=Q[i].second.second;
    c=Q[i].first;
    if(i<N-1&&Q[i+1].first==c){
      if(Q[i+1].second.first==b){
        X[b]--;X[b+1]++;
      }
    }
    X[a]++;X[b+1]--;
  }
  c=0;
  for(int i=1;i<100010;i++){
    X[i]+=X[i-1];
    c=max(c,X[i]);
  }
  cout<<c<<endl;
}

Measured memory_bytes: 2424
iS = int(input())

def fF(n):
    if n % 2 :
        return 3*n + 1
    else:
        return n//2
dS={iS}
for i in range(2,1000001):
    iN = fF(iS)
    if iN in dS:
        print(i)
        exit()
    dS.add(iN)
    iS = iN


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ll n,k;
    cin>>n>>k;
    cout<<min(n%k,k-n%k);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const ll INF = 1e18 + 10;

int N;
bool app[2000200];

int main() {
    cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    sort(ALL(A));
    rep(i,N-1) if (A[i] == A[i+1]) app[A[i]] =true;
    rep(i,N) {
        for (int j = 2*A[i]; j <= A[N-1]; j += A[i]) { app[j] = true; }
    }
    int count = 0;
    rep(i,N) {
        if ( !app[A[i]] ) count++;
    }
    cout << count << endl;
}

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

using namespace std;

long long int max(long long int a, long long int b){
	if(a > b) return a;
	else return b;
}

int main(){
	int n, w, i, j;
	scanf("%d%d", &n, &w);
	long long int ans[n+1][w+1], weight[n+1][2];

	for(i=0; i<n; i++) scanf("%lld%lld", &weight[i][0], &weight[i][1]);

	for(i=0; i<n; i++) ans[i][0] = 0;

	for(i=0; i<=w; i++){
		if(i >= weight[0][0]) ans[0][i] = weight[0][1];
		else ans[0][i] = 0;
	}

	for(i=1; i<n; i++){
		for(j=1;j<=w;j++){
			if(j<weight[i][0]) ans[i][j] = ans[i-1][j];
			else{
	/*			if(j==w-2)
				printf("=>%lld %lld %lld\n", ans[i-1][j], ans[i-1][w-weight[i][0]] + weight[i][1], max(ans[i-1][j], ans[i-1][w-weight[i][0]] + weight[i][1]));*/
				ans[i][j] = max(ans[i-1][j], ans[i-1][j-weight[i][0]] + weight[i][1]);
			}
		}
	}
	/*printf("    ");
	for(i=0; i<w; i++) printf("%d ", i);
		printf("\n");
	for(i=0; i<n; i++){
		printf("%lld %lld|", weight[i][0], weight[i][1]);
		for(j=0;j<=w;j++)
			printf("%lld ", ans[i][j]);
		printf("\n");
	}*/

	printf("%lld\n", ans[n-1][w]);
	return 0;
}

Measured memory_bytes: 78720
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int n,ans,a[21];
const int INF = 1e+9;

int solve(int i, int A, int B){
	if( i == n ){
		ans = min( ans , abs(A-B) );
	}else{
		solve( i+1 , A+a[i] , B );
		solve( i+1 , A , B+a[i] );
	}
}

int main(){
	while( cin >> n , n ){
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
		}
		ans = INF;
		solve( 0 , 0 , 0 );
		cout << ans << endl;
	}
}

Measured memory_bytes: 868
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int main() {
	int W, a, b;
	cin >> W >> a >> b;
	if ((a > b&&b + W >= a) || (a < b&&a + W >= b) || a == b)cout << 0;
	else cout << min(abs(a + W - b), abs(b + W - a));
}


Measured memory_bytes: 256
import sys
n = int(input())

if(n == 1):
    print('0')
    sys.exit()

maxi = int(n**0.5)
sets = []
for i in range(2,maxi+1):
    aset = 0
    while(n%i == 0):
        aset += 1
        n /= i
    if(aset != 0):
        sets.append(aset)

count = 0
if(n > maxi):
    count += 1
for i in sets:
    start = 1
    while(i >= start):
        i -= start
        count += 1
        start += 1

print(count)


Measured memory_bytes: 9464
#include<iostream>
#include<cmath>
#include<algorithm>
#include <cassert>
#include<string>
#include<vector>
#include <utility>
using namespace std;
int a = 0, b = 0, c = 0, d = 0, e[60][60], f[120], g[101000], h[10100], counto = 0, ans = 1000, x[100] = {}, y, z;
int64_t ab[10000] = {}, abc = 0, abcd = 0;
pair<int, int>manji[101] = {};
char rikka, toka[150][150] = {};
vector<int> train,code;
vector<char>aka,ao;
string saya, homu, kyok, mami[108], mado[100];
bool gg;
bool exist[1000];
int main() {
	cin >> saya;
	for (int i = 0; i < saya.length()-2; i++) {
		a += (saya[i] -'0')* 100 + (saya[i + 1]-'0' )* 10 + (saya[i + 2]-'0');
		b = abs(a- 753);
		ans = min(b, ans);
		a = 0;
		b = 0;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    long long N, A, B;
    cin >> N >> A >> B;

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

    long long ans = N / (A + B) * A;
    long long rem = N % (A + B);
    ans += min(rem, A);

    cout << ans << endl;
}


Measured memory_bytes: 256
N=int(input())
S,T=map(str,input().split())
lS=list(S)
lT=list(T)
lAns=[0]*2*N

for i in range(N):
	lAns[2*i]=lS[i]
	lAns[2*i+1]=lT[i]

Ans=''.join(lAns)
print(Ans)

Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
void func(char x,char y){
	char i;
	int n=0;
	for(i='0';i<='9';i++){
		if(i-x==0)
			break;
		n++;
	}
	for(i=0;i<n;i++)
		putchar(y);
}
	int main(){
		int h,i;
		char s[1000];
		while(scanf("%s",s)!=EOF){
			h=strlen(s);
			for(i=0;i<h;i++){
				if(s[i]-'@'==0){
					func(s[i+1],s[i+2]);
					i=i+2;
				}
				else putchar(s[i]);
			}
			putchar('\n');
		}
		return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
using namespace std;
#include<vector>
#include<algorithm>

pair<int, vector<int> > min_score(int A, vector<int> Banboo, int left) {
    pair<int, vector<int> > ret;
    ret.first = 100000; // mp : large number
    for (size_t i = 0; i < Banboo.size(); i++)
    {
        int mp_temp = abs(Banboo[i] - A);
        vector<int> banboo_temp = Banboo;
        banboo_temp.erase(banboo_temp.begin() + i);
        if (mp_temp < ret.first) {
            ret.first = mp_temp;
            ret.second = banboo_temp;
        }
        if (banboo_temp.size() > left) {
            pair<int, vector<int> > inner_ret = min_score(A - Banboo[i], banboo_temp, left);
            if (inner_ret.first + 10 < ret.first) {
                ret.first = inner_ret.first + 10;
                ret.second = inner_ret.second;
            }
        }
    }
    return ret;
}

int main() {
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<int> Banboo(N, 0);
    for (size_t i = 0; i < N; i++)
    {
        cin >> Banboo[i];
    }

    // 3!...
    int ret = 1000000;
    pair<int, vector<int> > temp;
    int temp_score=0;

    temp_score = 0;
    temp = min_score(A, Banboo, 2);
    temp_score += temp.first;
    temp = min_score(B, temp.second, 1);
    temp_score += temp.first;
    temp = min_score(C, temp.second, 0);
    temp_score += temp.first;
    ret = min(temp_score, ret);

    temp_score = 0;
    temp = min_score(A, Banboo, 2);
    temp_score += temp.first;
    temp = min_score(C, temp.second, 1);
    temp_score += temp.first;
    temp = min_score(B, temp.second, 0);
    temp_score += temp.first;
    ret = min(temp_score, ret);

    temp_score = 0;
    temp = min_score(B, Banboo, 2);
    temp_score += temp.first;
    temp = min_score(A, temp.second, 1);
    temp_score += temp.first;
    temp = min_score(C, temp.second, 0);
    temp_score += temp.first;
    ret = min(temp_score, ret);

    temp_score = 0;
    temp = min_score(B, Banboo, 2);
    temp_score += temp.first;
    temp = min_score(C, temp.second, 1);
    temp_score += temp.first;
    temp = min_score(A, temp.second, 0);
    temp_score += temp.first;
    ret = min(temp_score, ret);

    temp_score = 0;
    temp = min_score(C, Banboo, 2);
    temp_score += temp.first;
    temp = min_score(A, temp.second, 1);
    temp_score += temp.first;
    temp = min_score(B, temp.second, 0);
    temp_score += temp.first;
    ret = min(temp_score, ret);

    temp_score = 0;
    temp = min_score(C, Banboo, 2);
    temp_score += temp.first;
    temp = min_score(B, temp.second, 1);
    temp_score += temp.first;
    temp = min_score(A, temp.second, 0);
    temp_score += temp.first;
    ret = min(temp_score, ret);

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    // スペース区切りの整数の入力
    int N = sc.nextInt();
    int K = sc.nextInt();

    List<Integer> nList = IntStream.range(1, N + 1).boxed().collect(Collectors.toList());

    for (int i = 0; i < K; i++) {
      // 整数の入力
      int di = sc.nextInt();
      for (int j = 0; j < di; j++) {
        int A = sc.nextInt();
        int index = nList.indexOf(A);
        if (index != -1) {
          nList.remove(index);
        }
      }
    }

    System.out.println(nList.size());
  }
}


Measured memory_bytes: 46920
#include<stdio.h>
#include<string.h>
#include<math.h>
#define pr(x) printf("%s %lld\n", #x , x)
int main()
{
    //freopen("in.txt", "w", stdout);
    double volume , side;
    int n;
    scanf("%d",&n);
    side = n / 3.0;
    volume = pow(n / 3.0 , 3);
    printf("%.12lf\n",volume);
        
}   

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

int main() {
  int x, y;
  cin>>x>>y;
  if(y%2 == 1){
    cout<<"No";
    return 0;
  }
  if(y<x*2){
    cout<<"No";
    return 0;
  }
  if(y>x*4){
    cout<<"No";
  }
  else{
    cout<<"Yes";
  }
  return 0;
}

Measured memory_bytes: 3628
import itertools as it
n = int(input())
l = len(str(n))

res = []
for i in range(3, l + 1):
    for gen in it.product("357", repeat=i):
        gen_s = "".join(gen)
        if int(gen_s) <= n:
            res.append(gen_s)

cnt = 0
for r in res:
    if all(r.count(c) for c in "357"):
        cnt += 1
print(cnt)


Measured memory_bytes: 5236
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
      	String T = sc.next();
      	int n = S.length();
      	String T2 = T.substring(0,n);
        if(T2.equals(S))
 	      System.out.println("Yes");
     	else
          System.out.println("No");
    }
}

Measured memory_bytes: 35704
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,m;
ll s[2005],t[2005],dp[2005][2005];
ll M=1000000007;
int main(void){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        //dp[i][0]=1;
    }
    for(int i=0;i<m;i++){
        cin>>t[i];
        //dp[0][i]=1;
    }
    //dp[n][0]=1; dp[0][m]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i-1]==t[j-1]){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1]+1)%M;
            }else{
                dp[i][j]=(-dp[i-1][j-1]+dp[i-1][j]+dp[i][j-1])%M;
            }
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }
    if(dp[n][m]+1<0){
        cout<<dp[n][m]+1+M<<endl;
    }else{
        cout<<dp[n][m]+1<<endl;
    }
    
    
}


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

int main(){
  int i,j,n,m,a,temp,h[1001],p[1001],q[1001],now[1001];
  while(1){
    cin >> n >> m >> a;
    if(n==0 && m==0 && n==0)break;
    for(i = 1; i <= m; i++){
      cin >> h[i] >> p[i] >> q[i];
    }
  
    for(i = 1; i <= 1000; i++)now[i]=0;

    for(i = 1; i <= m; i++){
      for(j = 1; j <= m-1; j++){
	if(h[j] < h[j+1]){
	  swap(h[j],h[j+1]);
	  swap(p[j],p[j+1]);
	  swap(q[j],q[j+1]);
	}
      }
    }
  
    now[a] = 1;
    for(i = 1; i <= m; i++){
      swap(now[p[i]],now[q[i]]);
      // cout << "now[p[i]]" << now[p[i]] << " " << "now[q[i]]" << " " << now[q[i]] << endl;
    }
    
    for(i = 1; i <= n; i++){
      if(now[i]==1)cout << i << endl;
    }

  }
  return 0;
}

Measured memory_bytes: 1176
#include <iostream>
using namespace std;
int getsum(int n)
{
	int ans=0;
	if(n==0)
	return 0;
	return n%10+getsum(n/10);
}
int main() {
	// your code goes here
int n,a,b;
cin>>n>>a>>b;
int ans=0;
for(int i=1;i<=n;i++)
{
	if(a<=getsum(i)&&getsum(i)<=b)
	ans+=i;
}
cout<<ans;
}

Measured memory_bytes: 256
S = input()
l = len(S)
D = dict()
for i in range(l):
    if S[i] not in D:
        D[S[i]] = []
    D[S[i]].append(i)
res = 1000
for v in D.values():
    v = [-1]+v+[l]
    lv = len(v)
    tmp = 0
    for i in range(1,lv):
        tmp = max(tmp,v[i]-v[i-1]-1)
    res = min(res,tmp)
print(res)

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> set_t;
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pdd pair<double,double>
#define pb push_back
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-6
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
#define pi acos(-1)
#define index Index
#define Line pll
typedef long long LL;
int main(){
    int n;
    scanf("%d",&n);
    int h[200005];
    int a[200005];
    for(int i=0;i<n;i++){
        scanf("%d",&h[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    map<int,LL> m;
    m[0]=0;
    for(int i=0;i<n;i++){
        auto it=m.upper_bound(h[i]);
        it--;
        LL now;
        now=m[h[i]]=it->y+a[i];
        it=m.find(h[i]);
        it++;
        vector<int> er;
        while(it!=m.end()){
            if(it->y<now){
                er.pb(it->x);
            }
            else{
                break;
            }
            it++;
        }
        for(auto it:er){
            m.erase(it);
        }
    }
    printf("%lld\n",m.rbegin()->y);
}


Measured memory_bytes: 14336
#include <iostream>
#include <cstdlib>

using namespace std;

int main( void )
{
	int n;
	cin >> n;
	while(n--) {
		int y, m, d;
		cin >> y >> m >> d;
		
		int count = 0;
		int md[] = {19, 20};
		if(y%3)	{ // ３で割れない年
			count += (md[m++ % 2] - d + 1);				// 今月分
			while(m <= 10) { count += md[m % 2]; ++m; }	// 残った今年分
		}
		else{ // ３で割れる年
			count += (20 - d + 1);				//今月分
			++m;
			while(m <= 10) { count += 20; ++m; }// 残った今年分
		}

		const int mod3 = 20 * 10;			// ３で割れる年の日数
		const int nmod = 20 * 5 + 19 * 5;	// ３で割れない年の日数
		// 残りの年数分
		for(int i=y+1; i < 1000; ++i) {
			if(i%3) count += nmod;  // ３で割れない年
			else	count += mod3;  // ３で割れる年
		}

		cout << count << endl;
	}
	return 0;
}

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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
constexpr double EPS = 1e-10;
constexpr int INF = 1001001001;
//constexpr ll INF = 1001001001001001001ll;

struct Unionfind {
    vector<int> par, num;
    //vector<bool> done;
    Unionfind(int n): par(n), num(n, 1) {
        iota(par.begin(), par.end(), 0);
        //done.assign(n,false);
    }
    int root(int v) {
        return (par[v] == v) ? v : (par[v] = root(par[v]));
    }
    bool same(int u, int v) {
        return root(u) == root(v);
    }
    void unite(int u, int v) {
        u = root(u), v = root(v);
        if (u == v)return;
        if (num[u] < num[v])swap(u, v);
        num[u] += num[v];
        par[v] = u;
        //done[u] = done[u] | done[v];
    }
    int size(int v) {
        return num[root(v)];
    }
};

int main() {
    ll N, M; cin >> N >> M;
    vll A(M), B(M);
    vll ans(M, 0);
    rep(i, M) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
    }

    Unionfind uf(N);

    ans[M - 1] = (N * (N - 1)) / 2;

    for (int i = M - 1; i >= 1; i--) {
        if (uf.same(A[i], B[i])) {
            ans[i - 1] = ans[i];
        }
        else {
            ans[i - 1] = ans[i] - (ll)uf.size(A[i]) * (ll)uf.size(B[i]);
            uf.unite(A[i], B[i]);
        }
    }

    rep(i, M) cout << ans[i] << endl;

}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;

int n, mod, dp[N], ans[N];
vector<int> adj[N], prefix[N], suffix[N];

int add(int a, int b){
    a = (a + mod) % mod;
    b = (b + mod) % mod;
    return (a + b) % mod;
}

int mul(int a, int b){
    a = (a + mod) % mod;
    b = (b + mod) % mod;
    return 1ll * a * b % mod;
}

void dfs(int node, int par){
    prefix[node] = vector<int>(adj[node].size());
    suffix[node] = vector<int> (adj[node].size());
    int cur = 1;
    for(int i = 0; i < adj[node].size(); i++){
        int child = adj[node][i];
        if(child != par){
            dfs(child, node);
            cur = mul(cur, dp[child] + 1);
        }
        prefix[node][i] = cur;
    }
    dp[node] = cur;
    cur = 1;
    for(int i = (int) adj[node].size() - 1; i >= 0; i--){
        int child = adj[node][i];
        if(child != par){
            cur = mul(cur, dp[child] + 1);
        }
        suffix[node][i] = cur;
     }
}

void solve(int node, int par){
    ans[node] = dp[node];
    for(int i = 0; i < adj[node].size(); i++){
        int child = adj[node][i];
        if(child == par) continue;
        int dp_node = dp[node], dp_child = dp[child];
        dp[node] = 1;
        if(i){
            dp[node] = mul(dp[node], prefix[node][i - 1]);
        }
        if(i + 1 < adj[node].size()){
            dp[node] = mul(dp[node], suffix[node][i + 1]);
        }
        dp[node] = mul(dp[node], dp[par] + 1);
        // dp[node] = add(1, dp[node]);

        dp[child] = mul(dp[child], 1 + dp[node]);

        solve(child, node);

        dp[node] = dp_node;
        dp[child] = dp_child;
    }
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> mod;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    // dp[0] = 1;
    solve(1, 0);
    for(int i = 1; i <= n; i++){
        cout << ans[i] << '\n';
    }

    return 0;
}


Measured memory_bytes: 33280
#include<iostream>
#include<cstring>
#define ll long long
#define ld long double
using namespace std;
ll n;
ll C;
ll w[100001],v[100001];
ll dp[101][100001];
ll ans=0;
ll solve(ll x,ll W)
{

if(x==0 || W<=0)
{
return 0;	
}
if(dp[x][W]!=-1)
{
return dp[x][W];	
}

if(W-w[x]>=0)
dp[x][W]=max( v[x]+solve(x-1,W-w[x]),solve(x-1,W) );	
else
dp[x][W]= solve(x-1,W);	

return dp[x][W];
}
	

int main()
{
cin>>n>>C;
memset(dp,-1,sizeof(dp));
for(ll i=1;i<=n;i++)
{
cin>>w[i]>>v[i];	
}
ans=0;
solve(n,C);
ans=dp[n][C];
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 80128