akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
string s;
int main()
{
	cin>>s;
	if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I')cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //数列Aの長さ
        int[] A = new int[n]; //数列A
        for (int i=0; i<n; i++) {
            A[i] = sc.nextInt();
        }
        int q = sc.nextInt(); //整数mの数
        for (int i=0; i<q; i++) {
            int m = sc.nextInt(); //整数m
            if(check(n,m,A)) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }            
        }
    }
    static boolean check(int n, int m, int[] A) {
        if(m==0) return true;
        else if(n==0) return false;
        else if(check(n-1,m,A)) return true;
        else if(check(n-1,m-A[n-1],A)) return true;
        else return false;
    }
}



Measured memory_bytes: 26820
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 20005;

int n, x[N << 1], id[N << 1], rnk[N << 1], tab[N << 1], t;

namespace Graph {
#define mid ((L + R) >> 1)
#define no ID(L, R)
#define lc ID(L, mid)
#define rc ID(mid + 1, R)
#define travel(x, i) for (int i = fir[x]; i; i = e[i].nxt)
  struct edge {
    int nxt, to;
  } e[N * 100];
  int fir[N * 10], cnt;
  int dfn[N * 10], low[N * 10], clo;
  int bel[N * 10], sta[N * 10], top, cnt_bcc;
  bool vis[N * 10];
  
  inline int ID(int L, int R) {
    return ((L + R) | (L != R));
  }
  
  inline void add(int x, int y) {
    if (x == y) return;
    e[++ cnt] = (edge){fir[x], y};
    fir[x] = cnt;
  }
  
  inline void Build(int L, int R) {
    if (L == R) return;
    add(no, lc);
    Build(L, mid);
    add(no, rc);
    Build(mid + 1, R);
  }
  
  inline void Init() {
    memset(fir, 0, sizeof fir);
    cnt = 0;
    Build(0, t - 1);
  }
  
  inline void Add_edge(int L, int R, int x, int l, int r) {
    if (l > r) return;
    if (r < L || l > R) return;
    if (l <= L && R <= r) {
      add(x, no);
      return;
    }
    if (L == R) return;
    Add_edge(L, mid, x, l, r);
    Add_edge(mid + 1, R, x, l, r);
  }
  
  inline void dfs(int x) {
    vis[x] = 1;
    dfn[x] = low[x] = ++ clo;
    sta[++ top] = x;
    travel(x, i) {
      if (!dfn[e[i].to]) {
	dfs(e[i].to);
	low[x] = min(low[x], low[e[i].to]);
      }
      else if (vis[e[i].to]) low[x] = min(low[x], dfn[e[i].to]);
    }
    if (low[x] == dfn[x]) {
      int cur = -1;
      cnt_bcc ++;
      while (cur != x) {
	cur = sta[top --];
	bel[cur] = cnt_bcc;
      }
    }
    vis[x] = 0;
  }
  
  inline void Tarjan() {
    memset(bel, 0, sizeof bel);
    memset(dfn, 0, sizeof dfn);
    memset(vis, 0, sizeof vis);
    clo = top = cnt_bcc = 0;
    for (int i = 0; i <= ID(t - 1, t - 1); i ++)
      if (!dfn[i]) dfs(i);
  }
  
#undef mid
#undef no
#undef lc
#undef rc
}
using namespace Graph;

inline bool cmp(int a, int b) {
  return x[a] < x[b];
}

inline bool check(int ans) {
  Init();
  for (int i = 0, l, r; i < t; i ++) {
    l = lower_bound(tab, tab + t, x[i] - ans) - tab;
    r = upper_bound(tab, tab + t, x[i] + ans) - tab - 1;
    if (rnk[i] < l || rnk[i] > r)
      Add_edge(0, t - 1, ID(rnk[i ^ 1], rnk[i ^ 1]), l, r);
    else {
      Add_edge(0, t - 1, ID(rnk[i ^ 1], rnk[i ^ 1]), l, rnk[i] - 1);
      Add_edge(0, t - 1, ID(rnk[i ^ 1], rnk[i ^ 1]), rnk[i] + 1, r);
    }
  }
  Tarjan();
  for (int i = 0; i < t; i += 2)
    if (bel[ID(rnk[i], rnk[i])] == bel[ID(rnk[i ^ 1], rnk[i ^ 1])]) return false;
  return true;
}

int main() {
  scanf("%d", &n);
  t = n + n;
  for (int i = 0; i < t; i ++) {
    scanf("%d", &x[i]);
    id[i] = i;
  }
  sort(id, id + t, cmp);
  for (int i = 0; i < t; i ++) {
    rnk[id[i]] = i;
    tab[i] = x[id[i]];
  }
  int l = 0, r = 1e9, mid, ans = -1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      ans = mid;
      l = mid + 1;
    }
    else r = mid - 1;
  }
  printf("%d\n", ans + 1);
  return 0;
}


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

int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n)
        cin >> a.at(i);
    
    int ans = 1;
    rep(i, n) {
        if (a.at(i) %2 == 0) {
            if (a.at(i) %3 == 0 || a.at(i) % 5 == 0) {
                continue;
            }
            else {
                ans = 0;
                break;
            }
        }
    }
    if (ans == 1)
        puts("APPROVED");
    else {
        puts("DENIED");
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>
#include <bitset>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

int main(int argc, char const* argv[])
{
  string s;
  cin >> s;
  int n = s.size();
  unordered_map<int, int> mp;
  vector<bool> used;
  int res = 0;
  if(s[0] == s[n - 1]){
    for(int i = 0; i < n; i++){
      if(s[i] == s[0]){
        if(i != 0){
          for(int j = 0; j < 26; j++){
            if(used[j])mp[j]++;
          }
        }
        used = vector<bool>(26, false);
      }else{
        used[s[i] - 'a'] = true;
      }
    }
    for(int i = 0; i < 26; i++){
      res = max(res, mp[i]);
    }
    res = 2 * res + 1;
  }else{
    bool used = false;
    for(int i = 0; i < n; i++){
      if(s[i] == s[0]){
        if(used)res++;
        used = false;
      }else{
        if(s[i] == s[n - 1])used = true;
      }
    }
    res = 2 * res;
  }
  if((n - res) % 2 == 0)cout << "Second" << endl;
  else cout << "First" << endl;
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll MOD = 1000000007;
const double PI = 3.141592653589793238463;
const ll N=2e5+9;
set<int>s[26];
int main()
{
    FASTINOUT;
    int ls;
    cin>>ls;
    string t;
    cin>>t;
    for (int i=0;i<ls;i++)
        s[t[i]-'a'].insert(i);
    int q;
    cin>>q;
    int type,l,k;
    char r;
    set<int>::iterator it;
    while (q--){
        cin>>type;
        if (type==1){
            cin>>l>>r;
            l--;
            s[t[l]-'a'].erase(s[t[l]-'a'].find(l));
            t[l]=r;
            s[t[l]-'a'].insert(l);
        }
        else{
            cin>>l>>k;
            l--,k--;
            int cnt=0;
            for (int i=0;i<26;i++){
                it=s[i].lower_bound(l);
                if (it!=s[i].end()&&*it<=k)
                    cnt++;
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 24348
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()

  if h%3==0 or w%3==0:
    return 0

  ans=inf
  for i in range(1,h):
    a=i*w
    b=(h-i)*(w//2)
    c=(h-i)*(-(-w//2))
    ans=min(ans,max([a,b,c])-min([a,b,c]))

    a=i*w
    b=(h-i)//2*w
    c=-(-(h-i)//2)*w
    ans=min(ans,max([a,b,c])-min([a,b,c]))

  for i in range(1,w):
    a=i*h
    b=(w-i)*(h//2)
    c=(w-i)*(-(-h//2))
    ans=min(ans,max([a,b,c])-min([a,b,c]))

    a=i*h
    b=(w-i)//2*h
    c=-(-(w-i)//2)*h
    ans=min(ans,max([a,b,c])-min([a,b,c]))

  return ans

# main()
print(main())


Measured memory_bytes: 5556
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvl vector<vector<ll>>
#define vvi vector<vector<int>>
#define print(n) cout<<n<<endl
const int M=100111;
const ll inf=1000000007;
const ll MOD=1000000007;
const long long INF=1000000000000000007;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int ddx[8]={1,-1,0,0,1,-1,-1,1},ddy[8]={0,0,1,-1,1,-1,1,-1};

struct UnionFind {
	vector<int> par;
	UnionFind(int n) : par(n, -1) { }

	int root(int x) {
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y); // merge technique
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};

int main(){
	ll N,T,t[2*M];
	cin>>N>>T;
	rep(i,0,N)cin>>t[i];
	ll ans=0;
	rep(i,0,N-1){
		if(t[i+1]-t[i]<=T)ans+=t[i+1]-t[i];
		else ans+=T;
	}
	ans+=T;
	print(ans);
}


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

const int mxN=1e5+1;
vector<string>op(mxN);

vector<char>ans;

bool recur(int a,int b,int c,int n,int i){
//    cout<<a<<" "<<b<<" "<<c<<endl;
    if(i==(n) && a>=0 && b>=0 && c>=0)
        return true;
    if(i>=(n) && (a<0 || b<0 || c<0))
        return false;
    if(a<0 || b<0 || c<0)
        return false;
    string s=op[i];
    if(s=="AB"){
//        if(a-1<0 && b-1>=0)
//        {
            if(recur(a+1,b-1,c,n,i+1))
            {
                ans.push_back('A');
                return true;
            }
//        }
//        else if(a-1>=0 && b-1<0)
//        {
            if(recur(a-1,b+1,c,n,i+1))
            {
                ans.push_back('B');
                return true;
            }
//        }
//        else if(a-1>=0 && b-1>=0)
//        {
//            if(a>=b){
//                if(recur(a-1,b+1,c,n,i+1))
//                    ans.push_back('B');
//            }
//            else{
//                if(recur(a+1,b-1,c,n,i+1))
//                    ans.push_back('A');
//            }
//        }
//        else if(a-1<0 && b-1<0)
//            return false;
    }
    if(s=="AC"){
//        if(a-1<0 && c-1>=0)
//        {
            if(recur(a+1,b,c-1,n,i+1))
            {
                ans.push_back('A');
                return true;
            }
//        }
//        else if(a-1>=0 && c-1<0)
//        {
            if(recur(a-1,b,c+1,n,i+1))
            {
                ans.push_back('C');
                return true;
            }
//        }
//        else if(a-1>=0 && c-1>=0)
//        {
//            if(a>=c){
//                if(recur(a-1,b,c+1,n,i+1))
//                    ans.push_back('C');
//            }
//            else{
//                if(recur(a+1,b,c-1,n,i+1))
//                    ans.push_back('A');
//            }
//        }
//        else if(a-1<0 && c-1<0)
//            return false;
    }
    if(s=="BC"){
//        if(b-1<0 && c-1>=0)
//        {
            if(recur(a,b+1,c-1,n,i+1))
            {
                ans.push_back('B');
                return true;
            }
//        }
//        else if(b-1>=0 && c-1<0)
//        {
            if(recur(a,b-1,c+1,n,i+1))
            {
                ans.push_back('C');
                return true;
            }
//        }
//        else if(b-1>=0 && c-1>=0)
//        {
//            if(b>=c){
//                if(recur(a,b-1,c+1,n,i+1))
//                    ans.push_back('C');
//            }
//            else{
//                if(recur(a,b+1,c-1,n,i+1))
//                    ans.push_back('B');
//            }
//        }
//        else if(b-1<0 && c-1<0)
//            return false;
    }
    return false;
}

signed main(){
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    for(int i=0;i<n;i++)
    {
        cin>>op[i];
    }
    if(!recur(a,b,c,n,0))
        cout<<"No"<<endl;
    else {
        reverse(ans.begin(),ans.end());
        cout << "Yes" << endl;
        for(char chh:ans)
            cout<<chh<<endl;
    }
}

Measured memory_bytes: 22364
#include<iostream>
#include<string>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

int main()
{
	string s;
	cin >> s;
	
	int cnt = 0;
	REP(i, 0, s.size()) {
		if (s[i] == '1') cnt++;
	}
	cout << cnt << endl;
	return 0;
}

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

//#define int long long
//#define ll int long long
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(vec) (vec).begin(),(vec).end()
#define vint vector<int>
#define pint pair<int,int>
#define vpint vector<pint>

int par[100002];
int rnk[100002];
void init(int n){REP(i,n){par[i]=i;rnk[i]=0;}}
int find(int x){if(par[x]==x){return x;}else{return par[x]=find(par[x]);}}
void unite(int x,int y){x=find(x);y=find(y);if(x==y)return;if(rnk[x]<rnk[y]){par[x]=y;}else{par[y]=x;if(rnk[x]==rnk[y])rnk[x]++;}}
bool same(int x,int y){return find(x)==find(y);}


int n,m;
vint p,x,y;

signed main(){
    cin>>n>>m;
    p.resize(n);
    init(n+2);
    REP(i,n)cin>>p[i];
    x.resize(m);y.resize(m);
    REP(i,m){
        cin>>x[i]>>y[i];
        unite(x[i],y[i]);
    }
    int ans=0;
    REP(i,n){
        if(p[i]==p[p[i]-1])ans++;
        else if(same(p[i],p[p[i]-1]))ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl 
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl 
#define no cout<<"no"<<endl
#define vec(a,y,x)  vector<vector<char>> a (y,vector<char>(x))
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
const vector<int> dx={1,0,-1,0};
const vector<int> dy={0,1,0,-1};

int main(){
  int n;
  cin>>n;
  vector<string> num={};
  int ans=1;
  rep(i,n){
    string a;
    cin>>a;
   
      num.push_back(a);
      
  }
  sort(all(num));
  for(int i=1;i<n;i++){
    if(num.at(i-1)!=num.at(i))
      ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 11556
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function main()
	n,p = readline() |> split |> parseMap
	a = readline() |> split |> parseMap
	dp = zeros(Int,n,2)
	a[1]%2==0?dp[1,1]=1:dp[1,2]=1
	dp[1,1]+=1
	for i in 2:n
		if a[i]%2==0
			dp[i,1]=dp[i-1,1]*2
			dp[i,2]=dp[i-1,2]*2
		else
			dp[i,1]=dp[i-1,2]+dp[i-1,1]
			dp[i,2]=dp[i-1,2]+dp[i-1,1]
		end
	end
	if p==0
		println(dp[n,1])
	else
		println(dp[n,2])
	end
end

main()

Measured memory_bytes: 166164
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, inf = 1e9;
int n, P[N], Q[N];
int S, T, final[N], nex[N * 8], to[N * 8], tot = 1, f[N * 8];
void _link(int x, int y, int w) {
	to[++tot] = y, nex[tot] = final[x], final[x] = tot;
	f[tot] = w;
}

void link(int x, int y, int w) {
	_link(x, y, w), _link(y, x, 0);
}

int vis[N], ans;
int dis[N], cur[N];
void dinic() {
	static queue<int> Q;
	memset(cur, 0, sizeof cur);
	memset(dis, 127, sizeof dis);
	dis[S] = 0; Q.push(S);
	while (Q.size()) {
		int x = Q.front(); Q.pop();
		for(int i = final[x]; i; i = nex[i]) if(f[i]){
			int y = to[i];
			if(dis[x] + 1 < dis[y]) {
				dis[y] = dis[x] + 1;
				Q.push(y);
			}
		}
	}
}

int go(int x, int w) {
	if (x == T) return w;
	int used = 0;
	if (cur[x] == 0) cur[x] = final[x];
	for(int i = cur[x]; i; i = nex[i]) {
		if (f[i]) {
			int y = to[i];
			if (dis[x] + 1 == dis[y]) {
				int take = go(y, min(w - used, f[i]));
				f[i] -= take;
				f[i ^ 1] += take;
				used += take; 
				if (used == w) return w;
			}
		}
		cur[x] = i;
	}
	return used;
}

int lab[N], lab2[N];
int labcnt;
int main() {
	int g = clock(); 
	cin >> n;
	for(int i = 1; i <= n; i++) scanf("%d", &P[i]), P[i]++;
	for(int i = 1; i <= n; i++) scanf("%d", &Q[i]), Q[i]++;
	S = n + n + 1, T = S + 1;
	for(int i = 1; i <= n; i++) if(!vis[i]) {
		labcnt++;
		int t = i;
		vis[t] = 1;
		lab[t] = labcnt;
		while (vis[P[t]] == 0) {
			// _link(P[t], t, inf);
			// _link(t, P[t], inf);
			t = P[t];
			vis[t] = 1;
			lab[t] = labcnt;
		}
	}

	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i++) if(!vis[i]) {
		labcnt++;
		int t = i; vis[t] = 1;
		lab2[t] = labcnt;
		while (vis[Q[t]] == 0) {
			// _link(Q[t] + n, t + n, inf);
			// _link(t + n, Q[t] + n, inf);
			t = Q[t];
			vis[t] = 1;
			lab2[t] = labcnt;
		}
	}

	ans = n;
	for(int i = 1; i <= n; i++) {
		if (P[i] == i && Q[i] == i) {
			ans --;
		} else {
			if (P[i] == i && Q[i] != i) { //n+i默认Q[i]（在S集合），否则就有1的代价
				link(S, lab2[i], 1);
			} else 
			if (P[i] != i && Q[i] == i) { //i默认P[i]（在T集合）
				link(lab[i], T, 1);
			} else
			if (P[i] != i && Q[i] != i && P[i] != Q[i]) { //同时选i有1的代价
				link(lab[i], lab2[i], 1);
			} else { // P[i] == Q[i] 选法相同有1的代价
				_link(lab[i], lab2[i], 1);
				_link(lab2[i], lab[i], 1);
			}
		}
	}
	cerr << labcnt << endl;
	while (dinic(), dis[T] <= inf) {
		ans -= go(S, inf);
		// cerr << ans << endl;
	}
	cout << ans << endl;
	cerr << clock() - g << endl;
}


Measured memory_bytes: 17024
#include <iostream>

using namespace std;

int n,w[101],W;long long v[101],f[101][100001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> W;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
        f[i][0]==0;
    }
    for (int i = 0;i <= W; i++)
    {
        f[0][i]=0;
    }
    for (int i=1; i <= n; i++)
    {
        for(int j=1; j <= W;j++)
        {
            if(w[i]>j)
            {
                f[i][j]=f[i-1][j];
            }
            else
            {
                f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
            }
        }
    }
    cout << f[n][W];
    return 0;
}


Measured memory_bytes: 79232
#include <iostream>
#include <iomanip>
#include <bitset>
#include <set>
using namespace std;

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

int N, M;
int k[11];
int s[11][11];
int p[11];
int ans;

void solve(int n, int v)
{
    if(n > 0) {
        solve(n - 1, v << 1);
        solve(n - 1, (v << 1) + 1);
    } else {
        IFD cout << bitset<10>(v) << endl;
        bool ok = true;
        for(int i = 1; i <= M; i++) {
            int c = 0;
            for(int kk = 1; kk <= k[i]; kk++) {
                int b = 1 << (s[i][kk] - 1);
                if(b & v) {
                    c++;
                }
            }
            ok &= (c % 2 == p[i]);
            if(c % 2 == p[i]) {
                IFD cout << "v: " << bitset<10>(v) << endl;
            }
        }
        if(ok) {
            ans++;
        }
    }
}

int main()
{
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> k[i];
        for(int kk = 1; kk <= k[i]; kk++) {
            cin >> s[i][kk];
        }
    }
    for(int i = 1; i <= M; i++) {
        cin >> p[i];
    }

    solve(N, 0);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
#define allof(a) (a).begin(),(a).end()
#define minit(a,b) memset(a,b,sizeof(a))

using lint = long long;
using pii = pair< int, int >;

template< typename T > using Vec = vector< T >;

template< typename T > bool in_range(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool in_range(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }

template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }

int bitCount(int x) { return __builtin_popcount(x); }
int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double EPS = 1e-9;
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//

int N, a[100005];

int main() {
	cin >> N;
	for_(i,0,N) cin >> a[i];
	
	int cnt = 0;
	for_(i,0,N) cnt += (a[a[i]-1] == i+1);
	cout << cnt / 2 << endl;
}
//--------------8---------------->> coding space <<-----------------8-------------//


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

#define rep(i,z) for(int i = 0; i<(int)(z); i++)
#define rep1(i,z) for(int i = 1; i<=(int)(z); i++)
 
using namespace std;

typedef long long ll;
const ll MOD=1e9+7;
using pear = pair<int,int>;

vector<bool> seen;
void dfs(const vector<vector<int>> &g, int v, vector<ll> &ans){
    seen[v] = true;
    for(auto next_v : g[v]){
        ans[next_v]+= ans[v];
        if(seen[next_v]) continue;
        dfs(g,next_v,ans);
    }
}

int main(){
    ll n; cin>>n;
    cout<<n*(n-1)/2<<endl;
}

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

typedef long long int ll;
typedef pair<ll, ll> pii;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define vll vector<ll>
#define sz(a) ll(a.size())
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front 
#define MAXN 100010
#define N 100010
#define MOD 1000000007
#define mod 998244353
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define debug(x) cout << '>' << #x << ':' << x << " ";
#define nl '\n'
#define MS(x,y) fill_n(*x, sizeof x / sizeof **x, y);
#define mem(x,y) memset(x,y,sizeof(x));
#define INF 1000000000000000000
#define IO                 \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0);
#define int long long int
main()
{
    IO;
	int n, x, t;
    cin >> n >> x >> t;
    int res = ceil(1.0*n/x) * t;
    cout << res;
    return 0;
}

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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010, M = 2 * N;

int n, k;
int h[N], e[M], ne[M], idx;
int color[M], d[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa)
{
	int cnt = 0;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		cnt ++ ;
		if (j == fa) continue;
		dfs(j, u);
	}
	d[u] = cnt;
}

void paint(int u, int fa, int c)
{
	// cout << u << ' ' << fa << ' ' << c << ' ' << k << endl;
	for (int i = h[u]; ~i; i = ne[i])	
	{
		int j = e[i];
		if (j == fa) continue;
		if ( ++ c > k) c = 1;
		color[i] = c;
		// cout << j << ' ' << u << ' ' << c << endl;
		paint(j, u, c);
	}
}

int main()
{
	memset(h, -1, sizeof h);
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i ++ )
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	
	dfs(1, -1);
	for (int i = 1; i <= n; i ++ ) k = max(k, d[i]);
	paint(1, -1, 0);
	
	printf("%d\n", k);	
	for (int i = 0; i < idx - 1; i += 2)
		printf("%d\n", max(color[i], color[i + 1]));
	return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007


int main() {
	
	int N,M,C;
	cin>>N>>M>>C;
	vector<int> A(M);
	vec(B)
	
	fx(M){
		vecp(B)
	}
	
	int sum=0;
	
	fx(N){
		fy(M){
			int a;
			cin>>a;
			A.at(y)=a;
		}
		
		ll ans=0;
		fy(M){
			ans+=A.at(y)*B.at(y);
		}
		
		if(ans+C>0){
			sum++;
		}
		
	}
	ce(sum)

}


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


int main() {
	int n, q,C;
	C = 0;
	cin >> n;
	vector<int> S(n);
	for (int i = 0; i < n; i++) {
		cin >> S.at(i);
	}
	cin >> q;
	vector<int> T(q);
	for (int i = 0; i < q; i++) {
		cin >> T.at(i);
	}
	sort(T.begin(), T.end());
	int rate = 0;
	for (int i =0; i < q; i++) {
		for (int j = rate; j < n; j++) {
			if (T.at(i) == S.at(j)) {
				C++;
				rate = j+1;
				break;
			}
			else if (T.at(i) < S.at(j)) {
				rate = j - 1;
				break;
			}
		}
	}
	cout << C << endl;
}


Measured memory_bytes: 3344
#2009_A
def solve(n,p):
    a = [0]*n
    for _ in range(1000000):
        for i in range(n):
            if p:
                p -= 1
                a[i] += 1
                if p == 0:
                    if sum(a)-a[i] == 0:
                        return i
            else:
                p += a[i]
                a[i] = 0

while 1:
    n,p = [int(x) for x in input().split()]
    if n == 0:
        break
    print(solve(n,p))



Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;
 
const int mod = 1000000007;
 
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a, b;
    vector<int> num(n);
    rep(i,n) {
        cin >> num[i];
        if(num[i]<0) b.push_back(num[i]);
        else a.push_back(num[i]);
    }
    bool ok = false;
    int s = a.size();
    int t = b.size();
 
    if(s>0){
        if(n==k){
            if(t%2==0) ok = true;
        }
        else ok = true;
 
    } else {
        if(k%2==0) ok = true;
    }
    mint ans = 1;
    if(!ok) {
        sort(all(num), [](int x, int y) {
            return abs(x) < abs(y);
        });
        rep(i,k) ans *= num[i];
    } else {
        sort(all(a));
        sort(b.rbegin(), b.rend());
        if(k%2==1){
            ans *= a.back();
            a.pop_back();
        }
        vector<ll> P;
        while(a.size() >= 2){
            ll x = a.back();
            a.pop_back();
            ll y = a.back();
            a.pop_back();
            P.push_back(x*y);
        }
        while(b.size() >= 2){
            ll x = b.back();
            b.pop_back();
            ll y = b.back();
            b.pop_back();
            P.push_back(x*y);
        }
        sort(P.rbegin(), P.rend());
        rep(i,k/2) ans *= P[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6312
L, R = map(int, input().split())
if R - L >= 2019:
  print(0)
else:
  L1 = L % 2019
  R1 = R % 2019
  if L1 > R1:
    print(0)
  else:
    ans = 2 * 10 ** 9
    for i in range(L, R):
      for j in range(i + 1, R + 1):
        ans = min(ans, (i * j) % 2019)
    print(ans)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pb push_back
#define mp make_pair
bool isPrime(ll n) 
{ 
    
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
   
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
ll minthis(ll a, ll b){
if(a < b){
return a;
}
return b;
}
ll maxthis(ll a, ll b){
if(a > b){
return a;
}
return b;
}
int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}
ll lcm(ll a, ll b) {  
    return (a*b)/gcd(a, b);  
 }  
ll largestDivisor(ll n){
	int max = 1;
for(int i = 2 ; i*i <= n ; i++){
			if(n%i == 0) {
				max = n/i;break;
			}
		}
	return max;
}
 
 
ll power(ll x, ll y)  
{  
    ll temp;  
    if(y == 0)  
        return 1;  
    temp = power(x, y / 2);  
    if (y % 2 == 0)  
        return temp * temp;  
    else
    {  
        if(y > 0)  
            return x * temp * temp;  
        else
            return (temp * temp) / x;  
    }  
}  
bool sortbysec(const pair<int, int>& a, 
               const pair<int, int>& b) 
{ 
    return (a.second < b.second); 
} 
 
 
 
void solve(){	
	
	int n;
	cin >> n;
	int arr[n+1];int ans = 0;
	for(int i = 1 ; i <= n ; i++){
		int x; cin >> x;
		if(i%2 != 0 && x%2 != 0){
			ans++;
		}
	}
	cout << ans << "\n";
}
  
int main(){ 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;    
    //cin >> t;
    while(t--){
		solve();
	}
    return 0; 
}


Measured memory_bytes: 3612
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

ans = A[0]-1
tmp = 2
for i in range(1, N):
    if A[i] == tmp:
        tmp += 1
    elif A[i] > tmp:
        ans += (A[i]-1)//tmp

print(ans)

Measured memory_bytes: 7208
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define INF      (int)1e9
#define MOD      (int)1e9+7
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;

int main(){
	int n;
	cin>>n;
	
	vector<pii > a(n);
	REP(i,n){
		int x;
		cin>>x;
		a[i]=make_pair(x,i);
	}
	sort(ALL(a));
	
	vi ans(n);
	REP(i,n){
		if(i<n/2) ans[a[i].second]=a[n/2].first;
		else ans[a[i].second]=a[n/2-1].first;
	}
	
	REP(i,n) cout<<ans[i]<<endl;
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
int main(){
  int Q,A,F;
  string S;
  char C;
  cin>>S>>Q;
  bool flag=true;
  for(int i=0;i<Q;i++){
    cin>>A;
    if(A==1){
      flag=!flag;
    }else{
      cin>>F>>C;
      if(flag){
        if(F==1){
          S.insert(S.begin(),C);
        }else{
          S.push_back(C);
        }
      }else{
        if(F==1){
          S.push_back(C);
        }else{         
          S.insert(S.begin(),C);
        }
      }
    }
  }
  if(flag){
    for(auto itr=S.begin();itr!=S.end();itr++){
      cout<<*itr;
    }
    cout<<endl;
  }else{
    for(auto itr=S.end()-1;itr!=S.begin()-1;itr--){
      cout<<*itr;
    }
    cout<<endl;
  }
}


Measured memory_bytes: 1028
#include <stdio.h>
typedef long long ll;

const ll offset  = (ll)(1e9);
const ll modulus = (ll)(1e9) + 7;

ll n, m;
ll x[100005];
ll y[100005];
ll sum_x[100005];
ll sum_y[100005];

int main()
{
    // input
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", x + i);

        x[i] += offset;
    }
    for (ll i = 1; i <= m; i++) {
        scanf("%lld", y + i);

        y[i] += offset;
    }

    // calc sum
    for (ll i = 1; i <= n; i++) {
        sum_x[i] = sum_x[i - 1] + x[i];
    }

    for (ll i = 1; i <= m; i++) {
        sum_y[i] = sum_y[i - 1] + y[i];
    }

    // calc rectangle
    ll mul_x = 0;
    ll mul_y = 0;

    for (ll i = 1; i <= n - 1; i++) {
        mul_x += sum_x[n] - sum_x[i];
        mul_x -= (n - i) * x[i];
    }
    
    for (ll i = 1; i <= m - 1; i++) {
        mul_y += sum_y[m] - sum_y[i];
        mul_y -= (m - i) * y[i];
    }

    printf("%lld\n", ((mul_x % modulus) * (mul_y % modulus)) % modulus);

    return 0;
}


Measured memory_bytes: 3328
def main():
    N=int(input())
    H=list(map(int, input().split()))
    max_count=0
    count=0
    for i in range(1,N):
        if H[i-1]>=H[i]:
            count+=1
        else:
            if max_count < count:
                max_count = count
            count = 0
    else:
        if max_count < count:
            max_count = count
    print(max_count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 14252
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

class Edge
{
public:
    int to;
    ll cost;

    Edge(int to, ll cost)
    {
        this->to = to;
        this->cost = cost;
    }
};

typedef vector<vector<Edge>> Graph;


typedef pair<int, int> P;

vll dijkstra(int s, Graph& G)
{
    vll d(G.size(), INF);

    priority_queue<P, vector<P>, greater<P>> q;

    d[s] = 0;
    q.emplace(0, s);

    while (!q.empty())
    {
        auto p = q.top(); q.pop();
        int v = p.second;
        if (d[v] < p.first) continue;

        for (auto e : G[v])
        {
            if (d[e.to] > d[v] + e.cost)
            {
                d[e.to] = d[v] + e.cost;
                q.emplace(d[e.to], e.to);
            }
        }
    }

    return d;
}

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

    int N;
    cin >> N;

    Graph G(N);
    rep(_, N - 1)
    {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a--;
        b--;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }

    int Q, K;
    cin >> Q >> K;
    K--;

    auto d = dijkstra(K, G);

    rep(_, Q)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        cout << d[x] + d[y] << endl;
    }

    return 0;
}

Measured memory_bytes: 12668
import sys
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))
N = int(input())
B = [0] * N
for i in range(N):
    B[i] = int(input())

R1 = [False] * 3
R2 = [False] * 3
R3 = [False] * 3

for b in B:
    if b in A1:
        R1[A1.index(b)] = True
    if b in A2:
        R2[A2.index(b)] = True
    if b in A3:
        R3[A3.index(b)] = True

if R1[0] and R1[1] and R1[2]:
    print("Yes")
    sys.exit(0)

if R2[0] and R2[1] and R2[2]:
    print("Yes")
    sys.exit(0)

if R3[0] and R3[1] and R3[2]:
    print("Yes")
    sys.exit(0)

if R1[0] and R2[0] and R3[0]:
    print("Yes")
    sys.exit(0)

if R1[1] and R2[1] and R3[1]:
    print("Yes")
    sys.exit(0)

if R1[2] and R2[2] and R3[2]:
    print("Yes")
    sys.exit(0)

if R1[0] and R2[1] and R3[2]:
    print("Yes")
    sys.exit(0)

if R1[2] and R2[1] and R3[0]:
    print("Yes")
    sys.exit(0)
    
print("No")

Measured memory_bytes: 3064
fun main(args: Array<String>) {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val h = readLine()!!.split(" ").map { it.toLong() }
    var g = Array<MutableList<Int>>(n){ mutableListOf() }
    for(i in 0 until m){
        val (a,b) = readLine()!!.split(" ").map { it.toInt() }
        g[a-1].add(b-1)
        g[b-1].add(a-1)
    }
    var cnt = 0
    loop@for(i in 0 until n){
        for(el in g[i]){
            if(h[i] <= h[el] )
                continue@loop
        }
        cnt++
    }
    println(cnt)
}

Measured memory_bytes: 74376
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 998244353;

int main() {
  int H,W,h,w;cin >> H >>W >> h >> w;
  if(H%h==0&&W%w==0){
    cout <<"No" <<endl;
    return 0;
  }
  cout << "Yes" <<endl;
  ll out=1e6;
  repeat(i,H){
    repeat(j,W){
      if(H%h!=0){
        if(i%h==h-1){
          cout << -(h-1)*out-1;
        }else{
          cout << out;
        }
      }else{
        if(j%w==w-1){
          cout << -(w-1)*out-1;
        }else{
          cout << out;
        }
      }
      cout <<(j<W-1? " ":"\n");
    }
  }
  return 0;
}


Measured memory_bytes: 2304
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

int dp[200020][2],ok[200020][2];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

    string s,t;
    cin>>s>>t;
    int MOD=1000000007;
    ok[0][0]=1;
    rep(i,s.size())rep(j,2)rep(x,10)if(t[i]=='?'||t[i]-'0'==x){
        int I=i+1,J=j|s[i]-'0'>x;
        if(!J&&s[i]-'0'<x)continue;
        // cout<<i<<" "<<j<<" "<<x<<" "<<dp[i][j]<<" "<<I<<" "<<J<<endl;
        (ok[I][J]+=ok[i][j])%=MOD;
        (dp[I][J]+=dp[i][j]*10+ok[i][j]*x%MOD)%=MOD;
    }
    cout<<(dp[s.size()][0]+dp[s.size()][1])%MOD<<endl;
}



Measured memory_bytes: 9784
#include <iostream>
#include <string>
#include <sstream>
#include <cstdio>

using namespace std;

int main(void){
	string str;
	while(getline(cin,str)){
		istringstream iss(str);
		string n;
		int a,p;
		iss >> n >> a >> p;
		printf("%s %d %d\n",n.c_str(),a+p,200*a+300*p);
	}
}

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

void solve() {
    int N, T;
    cin >> N >> T;
    vector<pair<int, int>> pairs;
    for(int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        pairs.emplace_back(A, B);
    }
    auto f = [&]() {
        vector<vector<int>> dp(N + 1, vector<int>(T + 1));
        for(int i = 0; i < N; ++i) {
            int cost = pairs[i].first, val = pairs[i].second;
            for(int j = T; j >= 0; --j) {
                dp[i + 1][j] = dp[i][j];
                if(j + cost <= T) {
                    dp[i + 1][j + cost] = max(dp[i + 1][j + cost], dp[i][j] + val);
                }
            }
        }
        return dp;
    };
    auto ldp = f();
    reverse(pairs.begin(), pairs.end());
    auto rdp = f();
    reverse(pairs.begin(), pairs.end());
    int ans = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < T; ++j) {
           ans = max(ans, ldp[i][j] + rdp[N - i - 1][T - 1 - j] + pairs[i].second);
        }
    }
    cout << ans << '\n';
}

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


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

int main()
{
    int N, pointer = 0;
    string S;
    cin >> N >> S;

    for (int i = 0; i < int(S.size() - 2); i++)
    {
        if (S.compare(i, 3, "ABC") == 0)
        {
            ++pointer;
        }
        
    }

    cout << pointer;
    

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	string s;
	cin >> s;
	int co = 0, ans = 0;
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'S') {
			if (ans < co) {
				ans = co;
			}
			co = 0;
		}
		else {
			co++;
		}
	}
	if (ans < co) {
		ans = co;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int max_n = 1e6;
ll a[2][200];
int main(){
  ll x,y;
  cin >> x >> y;
  ll cnt = 0;
  while(y >= x){
    cnt++;
    x *= 2;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,x) for (register int (i)=(1);(i)<=(x);(i)++)
#define repd(i,x) for (register int (i)=(x);(i)>=(1);(i)--)
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
using namespace std;
int n,m,i,j,p[100005],vis[100005],x,cnt;
struct _
{
	int x,id;
}a[100005],b[100005];
bool cmp(_ x,_ y){return x.x<y.x;}
int main()
{
	scanf("%d",&n);
	rep(i,n){scanf("%d",&a[i].x);a[i].id=i;}
	rep(i,n){scanf("%d",&b[i].x);b[i].id=i;}
	sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
	rep(i,n)if(a[i].x>b[i].x){puts("No");return 0;}
	rep(i,n-1)if(a[i+1].x<=b[i].x){puts("Yes");return 0;}
	rep(i,n)p[a[i].id]=b[i].id;
	x=1;while(!vis[x]){cnt++;vis[x]=1;x=p[x];}
	if(cnt==n)puts("No"); else puts("Yes");
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".txt","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
struct node {
	int to,next;
}a[200011];
int head[100011],cnt,x[100010],bin[101];
int fa[100011][32],ans=0,dep[100010];
void add(int x,int y){
	a[++cnt].next=head[x];
	a[cnt].to=y;
	head[x]=cnt;
}
void dfs(int x,int f){
	fa[x][0]=f;
	dep[x]=dep[f]+1;
	for(int i=1;i<=31;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=head[x];i;i=a[i].next){
		int v=a[i].to;
		if(v==f) continue;
		dfs(v,x);
	}
}
main(){
	int n=read(),y;
	for(int i=1;i<=n;i++)
		x[i]=read();
	bin[0]=1;
	for(int i=1;i<=31;i++)
		bin[i]=bin[i-1]*2;
	x[n+1]=214748364700;
	int L=read();
	for(int i=1;i<n;i++)
		y=lower_bound(x+1,x+2+n,L+x[i]+1)-x-1,add(y,i);
	dfs(n,0);
	int Q=read();
	//cout<<fa[2][1];
//	cout<<bin[30];
	while(Q--){
		int A=read(),B=read(),p=min(A,B);
		if(A>B) swap(A,B);
		int ans=0;
		//cout<<B;
		for(int i=31;i>=0;i--)
			if(fa[A][i]<=B&&fa[A][i])
					A=fa[A][i],ans+=bin[i];//cout<<A<<" ";
//cout<<ans<<endl;
		if(A<B) ans++;
		cout<<ans<<endl;
//		if(ans==0) cout<<fa[p][0]<<" "<<dep[B]<<endl;
	}
    return 0;
}

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

using namespace std;

long gcd(long x, long y) {
    if(x < y) return gcd(y, x);
    if(y==0) return x;
    return gcd(y, x%y);
}

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

    long r = b-a+1;
    r -= (b/c - (a-1)/c);
    r -= (b/d - (a-1)/d);

    long g = gcd(c, d);
    long l = c*d / g;
    r += (b/l - (a-1)/l);

    cout << r << endl;
}


Measured memory_bytes: 256