akhauriyash/Code-Regression huggingface dataset:
n, m = gets.strip.split.map(&:to_i)
holes = m.times.map { gets.to_i }
stairs = Hash.new { 0 }
holes.each do |hole|
  stairs[hole] = false
end

stairs[0] = 1

n.times do |i|
  if stairs[i]
    if stairs[i + 1]
      stairs[i + 1] += stairs[i]
    end
    if stairs[i + 2]
      stairs[i + 2] += stairs[i]
    end
  end
end

puts(stairs[n] % 1_000_000_007)


Measured memory_bytes: 871220
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define repD(i, a, n) for(ll i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
const long double PI = 3.141592653589793238462643383;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
long long int Ceil(int a, int b){
    if(a%b==0) return a/b;
    else return (a/b)+1;
}
ll p=1000000007;
int main() {

    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int ans=0;
    ll n;cin>>n;
    vector<pair<int,int> > v[n];
    rep(i,n){
        int y;cin>>y;
        vector<pair<int,int> > t(y);
        rep(i,y){
            int a,b;cin>>a>>b;a--;
            t[i]=mp(a,b);
        }
        v[i]=t;
    }
    int mask=pow(2,n);
    for(int i=0;i<mask;i++){
        int flag=1;
        int x=__builtin_popcount(i);
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                for(auto k : v[j]){

                    if(k.snd==1){
                        if((i&(1<<k.fst))==0){
                            flag=0;break;
                        }
                    }
                    else{
                        if((i&(1<<k.fst))!=0){
                            flag=0;break;
                        }
                    }
                }
            }
        }
        // if(flag)cout<<i<<endl;
        if(flag)ans=max(ans,x);
    }
    cout<<ans;
    return 0;
}   

Measured memory_bytes: 384
#include <stdio.h>
#define MAX 100000

int parent(int i){
  return i/2;}

int left(int i){
  return 2*i;}

int right(int i){
  return 2*i+1;}

int main(){
  int H,i,A[MAX+1];

  scanf("%d",&H);
  for(i=1;i<=H;i++){
    scanf("%d",&A[i]);
  }

  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,A[i]);
    
    if(parent(i)>=1){
      printf("parent key = %d, ",A[parent(i)]);
    }

    if(left(i)<=H){
      printf("left key = %d, ",A[left(i)]);
    }

    if(right(i)<=H){
      printf("right key = %d, ",A[right(i)]);
    }
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2100
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <functional>
#include <queue>
#include <vector>

#define MAX_N 100
#define MAX_M 3000

struct state {
	int v;
	int dist;
	state(int v = 0, int dist = 0):v(v), dist(dist){}
	bool operator>(const state &s) const {
		return dist > s.dist;
	}
};

typedef state value_type;

std::priority_queue<value_type, std::vector<value_type>, std::greater<value_type>> que;

bool empty() {
	return que.empty();
}

void enqueue(value_type value) {
	que.push(value);
}

value_type dequeue() {
	value_type res = que.top();
	que.pop();
	return res;
}

// graph
int n, m;
int num;
int head[MAX_N], next[MAX_M * 2], to[MAX_M * 2];
int costs[MAX_M * 2], times[MAX_M * 2];
int dist[MAX_N];

void init() {
	num = 0;
	memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int c, int t) {
	next[num] = head[u];
	head[u] = num;
	to[num] = v;
	costs[num] = c;
	times[num] = t;
	++num;
}

// calc dist
int dijkstra(int start, int goal, int r) {
	int i, e;
	const int *weight = (r ? times : costs);

	for(i = 0; i < n; ++i) dist[i] = INT_MAX;
	dist[start] = 0;
	while(!empty()) dequeue();
	enqueue((state){start, 0});

	while(!empty()) {
		state current = dequeue();
		if(dist[current.v] < current.dist)
			continue;

		if(current.v == goal)
			return dist[goal];

		for(e = head[current.v]; e != -1; e = next[e]) {
			int next_dist = current.dist + weight[e];
			if(dist[to[e]] > next_dist) {
				dist[to[e]] = next_dist;
				enqueue((state){to[e], next_dist});
			}
		}
	}
	assert(false);
}

int main(void) {
	int i;
	while(scanf("%d%d", &m, &n) == 2 && n) {
		init();
		for(i = 0; i < m; ++i) {
			int u, v, c, t;
			scanf("%d%d%d%d", &u, &v, &c, &t);
			--u; --v;
			add_edge(u, v, c, t);
			add_edge(v, u, c, t);
		}

		int query;
		scanf("%d", &query);

		while(query--) {
			int start, goal, r;
			scanf("%d%d%d", &start, &goal, &r);
			printf("%d\n", dijkstra(start - 1, goal - 1, r));
		}
	}
	return EXIT_SUCCESS;
}

Measured memory_bytes: 1116
// 標準入力から一行を読み取り、指定の型に変換する
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let n: u64 = read();
    let mut a: Vec<u64> = read_vec();

    let before_len = a.len();
    a.sort();
    a.dedup();
    let after_len = a.len();

    if before_len != after_len { println!("NO"); return; }
    println!("YES");
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

void solve(ll n,ll m){
	ll x,y,z,ans=0;
	vl u(m),v(m),d(m),c(m);
	vl dist(n,LINF);
	vvl g(n);
	rep(i,m){
		cin>>u[i]>>v[i]>>d[i]>>c[i];
		u[i]--;v[i]--;
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
	}
	priority_queue<tlll,vector<tlll>,greater<tlll>> q;
	q.push(tlll(0,0,0));
	while(!q.empty()){
		tie(x,y,z)=q.top();q.pop();
		//puta("pop",x,y,z);
		if(dist[z]!=LINF)continue;
		dist[z]=x;
		ans+=y;
		for(auto k:g[z]){
			ll frm=u[k],nxt=v[k];
			if(nxt==z)swap(frm,nxt);
			if((dist[nxt]<=dist[frm]+d[k]))continue;
			q.push(tlll(dist[frm]+d[k],c[k],nxt));
			//puta("!",dist[frm]+d[k],c[k],nxt);
		}
		//puta(dist);
	}
	//puta(dist);
	cout<<ans<<endl;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,m;
	while(cin>>n>>m,n)solve(n,m);
}



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

using namespace std;

#define ll long long



int main()
{
    int n, last = 0;
    bool ok = 1;
    cin >> n;
    vector <pair <int, int>> b;
    vector <int> time(n);
    for (int i=0; i<n; ++i) {
        int x, y;
        cin >> x >> y;
        b.push_back({y, x});
    }

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

    for (int i=0; i<n; ++i) {
        time[i] = last + b[i].second;
        last = time[i];
        if (time[i] > b[i].first)
            ok = 0;
    }

    if (ok)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}


Measured memory_bytes: 3188
N,M = map(int,input().split())
ab_list = []
c_bit_list = []
INF = 1000000000
for _ in range(M):
    a,b = list(map(int,input().split()))
    ab_list.append([a,b])
    c=0
    c_in = list(map(int,input().split()))
    for k in range(b):
        c |= 1<<(c_in[k]-1)
    c_bit_list.append([c,a])

dp_all_number = pow(2,N)
c_bit_list_len = len(c_bit_list)
dp = [INF for _ in range(dp_all_number)]
dp[0] = 0

for i in range(dp_all_number):
    for j in range(c_bit_list_len):
        #print(i,j)
        dp[i | c_bit_list[j][0]] = min(dp[i | c_bit_list[j][0]],dp[i]+c_bit_list[j][1])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Measured memory_bytes: 46552
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    cnt=defaultdict(int)
    n=II()
    aa=LI()
    pp=[]
    mm=[]
    for i,a in enumerate(aa):
        pp.append(i+aa[i])
        mm.append(i-aa[i])
    #print(pp)
    #print(mm)
    ans=0
    for p,m in zip(pp[::-1],mm[::-1]):
        ans+=cnt[p]
        if m>0:cnt[m]+=1
    print(ans)

main()

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> size;

    UnionFind(int N) : par(N), size(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) {
          par[i] = i;
          size[i] = 1;
        };
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

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

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        if(size[rx] < size[ry]){
          size[ry] += size[rx];
          par[rx] = ry;
        } else{
          size[rx] += size[ry];
          par[ry] = rx;
        }
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  int n, m, k;
  cin >> n >> m >> k;

  UnionFind tree(n + 1);

  vector<int> friends(n + 1);
  for(int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b;

    tree.unite(a, b);
    friends[a]++;
    friends[b]++;
  }

  vector<vector<int>> block(n + 1);
  for(int i = 0; i < k; i++){
    int a, b;
    cin >> a >> b;

    if(tree.same(a,b)){
    block[a].push_back(b);
    block[b].push_back(a);
    }
  }

  for(int i = 1; i <= n; i++){
    int num = tree.siz(i) - friends[i]- block[i].size() - 1;
    cout << num;
    if(i < n) cout << " ";
  }
  cout << endl;
  
}

Measured memory_bytes: 10240
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n = f.read_int()
    r = [tuple(f.read_int_list()) for _ in xrange(n)]
    b = [tuple(f.read_int_list()) for _ in xrange(n)]

    ans = 0
    b.sort()
    for bi in b:
        cand = None
        for ri in r:
            if ri[0] > bi[0] or ri[1] > bi[1]: continue
            if cand is None:
                cand = ri
            else:
                if ri[1] > cand[1]: cand = ri
        if cand is not None:
            ans += 1
            r.remove(cand)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


Measured memory_bytes: 6036
#include<bits/stdc++.h>
#define fori(j,n) for(ll i=j;i<n;i++)
#define forb(n,j) for(ll i=n-1;i>=0;i--)
#define endl "\n"
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll sgn(ll x){
    if(x>0)
        return 1;
    if(x==0)
        return 0;
    return -1;
}
const ll N = 2e5 + 5;
ll n;
ll a[N];
int32_t main()
{
    IOS;
    char c;
    cin>>c;
    if(c >= 65 and c <= 91)
    {
        cout<<"A";
    }
    else{
        cout<<"a";
    }
    return 0;
}




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

int main(){
  long int a,b,c;
  cin >> a >> b >> c;
  long int out = 0;
  if((a * b * c) % 2 != 0){
    long int max = a;
    if(max < b) max = b;
    if(max < c) max = c;
    if(max == a){
      out = b * c;
    }else if(max == b){
      out = a * c;
    }else{
      out = a * b;
    }
  }
  cout << out;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> data(n);
  for(int i=0;i<n;i++)cin>>data[i];
  int ans=0;
  for(int i=0;i<n;i++){
    bool view=true;
    for(int j=0;j<i;j++){
      if(data[j]>data[i])view=false;
    }
    if(view)ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	ll n, m;
	cin >> n >> m;
	vl x(n), y(m);
	rep(i, n) cin >> x[i];
	rep(i, m) cin >> y[i];
	ll xsum = 0LL, ysum = 0LL;
	for(int i = 1; i < n; i++) {
		ll len = min(i-1LL, n-i-1LL);
		len = (n-1)/2LL-len;
		ll k = (n-1)/2LL;
		ll dif = (ll)k * (k+1) / 2LL;
		dif *= 2LL;
		if(n % 2 == 0) dif += n /2LL - len * len;
		else dif -= len*(len-1LL);
		//cout << i << " " << dif << endl;
		(xsum += ((dif%MOD)*((x[i]-x[i-1]))%MOD)%MOD)%=MOD;
	}
	for(int i = 1; i < m; i++) {
		ll len = min(i-1LL, m-i-1LL);
		len = (m-1)/2LL-len;
		ll k = (m-1)/2LL;
		ll dif = (ll)k * (k+1) / 2LL;
		dif *= 2LL;
		if(m % 2 == 0) dif += m /2LL - len * len;
		else dif -= len*(len-1LL);
		//cout << i << " " << dif << endl;
		(ysum += ((dif%MOD)*((y[i]-y[i-1])%MOD))%MOD)%=MOD;
	}
	cout << (xsum * ysum) % MOD << endl;
}


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
}*/

signed main()
{
  int n, Q;
  string s;
  cin >> n >> Q >> s;
  
  vi L(n+1), R(n+1);
  rep(i, 0, n-1){
    if(s[i] == 'A' and s[i+1] == 'C'){
      L[i+1]++;
      R[i+2]++;
    }
  }

  rep(i, 0, n){
    L[i+1] += L[i];
    R[i+1] += R[i];
  }

  while(Q--){
    int l, r;
    cin >> l >> r;
    int t = R[r]-L[l-1];
    cout << t << endl;
  }

  return 0;
}


Measured memory_bytes: 2688
#include <iostream>
#include <bits/stdc++.h>    //vectorを使う
using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
    	cin >> a.at(i);
  	}
  	
  	while(a.size()> 1){
    	sort(a.begin(),a.end());
  		reverse(a.begin(),a.end());
        a.erase(remove(a.begin(), a.end(), 0), a.end());
        for(int i = 0; i < a.size()-1; i++){
        	a.at(i)=a.at(i) % a.at(a.size()-1);
    	}
    }
  	cout << a.at(0) << endl;
}


Measured memory_bytes: 640
/*_BELIEVE_*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int          long long int
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     __gcd((a),(b))
#define     lcm(a,b)     ((a)*(b))/gcd((a),(b))
#define     pb           push_back
#define     ins          insert
#define     F            first
#define     S            second

const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int a,b;
    cin>>a>>b;
    cout<<max({a+b,a-b,a*b});
}

int32_t main()
{
    fast();

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

    return 0;
}



Measured memory_bytes: 256
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<numeric>
#include <string.h>
#include <unordered_map>
#include <set>

using namespace std;

typedef long long ll;

int r;

void solve() {
    cin >> r;
    cout << r * r;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}





Measured memory_bytes: 256
#define REP(i, t, n)	for (int i = t; i < n; i++)
#define ALL(n)				(n).begin(),(n).end()
#include <limits.h>
#include <stdio.h>
#include <cmath>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <functional>
#include <algorithm>
#include <cstring>
#include <unordered_map>

using namespace std;

typedef bool							 BOOL;
typedef short							 WORD;
typedef unsigned short		 U_WORD;
typedef long							 DWORD;
typedef unsigned long			 U_DWORD;
typedef long long					 QWORD;
typedef unsigned long long U_QWORD;

#define N_MAX  (100)
#define C_NUM  (4)
#define MOD    (1000000000 + 7)
#define INF    (10000000000)

typedef enum {
	A = 0,
	C = 1,
	G = 2,
	T = 3,
	ASTA = 4,
} ACGT;

int N;
DWORD dp[N_MAX + 1][C_NUM + 1][C_NUM + 1][C_NUM + 1] = {};

bool Check(const ACGT *prev_char, ACGT now_char)
{
	//AGC
	if ((prev_char[0] == A && prev_char[1] == G && prev_char[2] == C) ||
	    (prev_char[1] == A && prev_char[2] == G && now_char == C)) {
		return false;
	}

	//GAC
	if ((prev_char[0] == G && prev_char[1] == A && prev_char[2] == C) ||
	    (prev_char[1] == G && prev_char[2] == A && now_char == C)) {
		return false;
	}

	//ACG
	if ((prev_char[0] == A && prev_char[1] == C && prev_char[2] == G) ||
		  (prev_char[1] == A && prev_char[2] == C && now_char == G)) {
		return false;
	}

	//A*GC || AG*C
	if ((prev_char[0] == A && prev_char[2] == G && now_char == C) ||
	    (prev_char[0] == A && prev_char[1] == G && now_char == C )) {
		return false;
	}

	return true;
}

DWORD rec(int n, ACGT *prev_char)
{
	if (n == 0) return 1;

	if (dp[n][prev_char[0]][prev_char[1]][prev_char[2]] != -1) {
		return dp[n][prev_char[0]][prev_char[1]][prev_char[2]];
	}


	DWORD ret = 0;
	ACGT now_char[C_NUM] = {A, C, G, T};
	REP(i, 0, C_NUM) {
		if (Check(prev_char, now_char[i])) {
			ACGT next_prev[C_NUM - 1] = {prev_char[1], prev_char[2], now_char[i]};
			ret = (ret + rec(n - 1, next_prev)) % MOD;
		}
	}

	dp[n][prev_char[0]][prev_char[1]][prev_char[2]] = ret;
	return ret;
}

void solve_main()
{

	cin >> N;
	
	ACGT prev_char[C_NUM - 1] = {ASTA, ASTA, ASTA};
	memset(dp, -1, sizeof(dp));
	cout << rec(N, prev_char) << endl;
}
int main()		
{
#ifdef FOR_IDE
	ifstream in("input.txt");
	cin.rdbuf(in.rdbuf());
#endif

	solve_main();
	return 0;
}

Measured memory_bytes: 384
from collections import Counter
from functools import reduce
import fractions
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


s, t = IS(), IS()
for i in range(len(s)):
    a = [] 
    for j in range(len(s)):
        a.append(s[(i+j) % len(s)])
        if ''.join(a) == t:
            print('Yes')
            exit()
print('No')


Measured memory_bytes: 5180
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <algorithm>
#include <limits.h>
#include <bits/stdc++.h>
#define fw(x) freopen("x.txt","w",stdout)
#define For(i,a,b,c) for(int i = a;i < b;i+=c)
#define REP(i,n) for(int i = 0;i < n;++i)
#define REP1(i,n) for(int i = 1; i<=n;i++)
#define mem(a,s) memset(a,s,sizeof a)
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
#define pf printf
#define sc scanf
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define vii vector<int>
#define vll vector<ll>
#define vss vector<string>
#define debug(x)  cout<<#x"="<<(x)<<endl
#define pb push_back


using namespace std;


// moves

//int dx[]= {0,0,1,-1};/*4 side move*/
//int dy[]= {-1,1,0,0};/*4 side move*/
//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/
//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/


//big_mod

//ll bigmod(ll a,ll b,ll m)
//{if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a)% m;return x;}
//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M

//ll getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1ll;}
//ll setBit1(ll num, int idx) {return num or (1ll<<idx);}
//ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
//ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}

const int mod = 1000000007;
ll qpow(ll n,ll k)
{
    ll ans=1;
    assert(k>=0);
    n%=mod;
    while(k>0)
    {
        if(k&1)
            ans=(ans*n)%mod;
        n=(n*n)%mod;
        k>>=1;
    }
    return ans%mod;
}
int main()
{
    fast;
    int n, k;
    cin>>n>>k;
    int arr[n+1];
    ll dp[k+1][n+1];
    ll cum[k+1][n+1];
    REP1(i, n) cin>>arr[i];
    dp[0][0] = 1;
    cum[0][0] = 1;
    REP(i, k+1){
      REP(j, n+1){
        if(i==0) {
          dp[i][j] = 1;
          cum[i][j] = 1;
        }
        else if(j==0) {
          dp[i][j] = 0;
          cum[i][j] = 0;
        }
        else{
          dp[i][j] = 0;
          /*
          REP(k, arr[j]+1){
            if(i>=k) sum += dp[i-k][j-1];
            else break;
            sum %= mod;
          }
          */
          ll right = i;
          ll left = i - min(i, arr[j]);
          ll cumSum = cum[right][j-1];
          if(left>0) {
            if(cumSum<cum[left-1][j-1]) cumSum+=mod;
            cumSum -= cum[left-1][j-1];
          }
          dp[i][j] = cumSum;
        }
        if(i>0) {
          cum[i][j] = cum[i-1][j] + dp[i][j];
          cum[i][j] %= mod;
        }
        else cum[i][j] = dp[i][j];
      }
    }
    cout<<dp[k][n]<<'\n';
    return 0;
}


Measured memory_bytes: 161296
import heapq

N = int(input())
A = list(map(int, input().split()))

max_heap = []
plus_min = 100000
min_heap = []
minus_max = -100000
ope = []

for i in range(N):
    if A[i] >= 0:
        plus_min = min(plus_min, A[i])
        heapq.heappush(max_heap,(-A[i], A[i]))
    else:
        minus_max = max(minus_max, A[i])
        heapq.heappush(min_heap,(A[i], A[i]))

k = 0
for i in range(N-1):
    if len(min_heap)==0:
        x, y = plus_min, heapq.heappop(max_heap)[1]
        m = x - y
        ope.append("" + str(x) + " " + str(y))
        k+=1
        heapq.heappush(min_heap,(m, m))
    elif len(max_heap)==0:
        x, y = heapq.heappop(min_heap)[1], minus_max
        m = y - x
        ope.append("" + str(y) + " " + str(x))
        heapq.heappush(max_heap,(-m, m))
    elif len(max_heap)>1+k:
        x, y = heapq.heappop(min_heap)[1], heapq.heappop(max_heap)[1]
        m = x - y
        ope.append("" + str(x) + " " + str(y))
        heapq.heappush(min_heap,(m, m))
    else:
        x, y = heapq.heappop(min_heap)[1], heapq.heappop(max_heap)[1]
        m = y - x
        ope.append("" + str(y) + " " + str(x))
        heapq.heappush(max_heap,(-m, m))

print(heapq.heappop(max_heap)[1])
print("\n".join(ope))

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

VI g[100010];
int h[100010];
signed main(void)
{
  int v, e;
  cin >> v >> e;
  REP(i, e) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
    h[t]++;
  }

  stack<int> st;

  REP(i, v) if(h[i] == 0) st.push(i);

  VI ans;
  while(st.size()) {
    int i = st.top(); st.pop();
    ans.push_back(i);
    for(auto& j: g[i]) {
      h[j]--;
      if(h[j] == 0) st.push(j);
    }
  }

  for(int i: ans) cout << i << endl;

  return 0;
}

Measured memory_bytes: 6032
#include<bits/stdc++.h>
using namespace std; 
int main(){
 ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int t;
   cin>>t;
   map<string,int> mp; 
   while(t--){
    string s;
    cin>>s;
    mp[s]++;
   }
   cout<<"AC x "<<mp["AC"]<<"\n";
   cout<<"WA x "<<mp["WA"]<<"\n";
   cout<<"TLE x "<<mp["TLE"]<<"\n";
   cout<<"RE x "<<mp["RE"]<<"\n";
 return 0;
}

Measured memory_bytes: 3668
#!/usr/bin/env python
# -*- coding: utf-8 -*-

s = list(map(int, input().split()))

W = s[0]
H = s[1]
x = s[2]
y = s[3]


small_area = W * H /2.
if x == W/2. and y == H/2.:
    MultipleSeparation = 1
else:
    MultipleSeparation = 0

print(small_area, MultipleSeparation)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, m, n) for (int i = m; i < n; ++i)
const int MOD = 1000000007;
template<class T> void add(T &a, T b) { a = (a + b) % MOD; }

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> S(N);
  rep(i, 0, N) cin >> S[i];
  sort(S.begin(), S.end());
  vector<vector<ll>> dp(N+1,vector<ll>(X+1));
  rep(i, 0, X+1) dp[0][i] = i;
  rep(i, 0, N) rep(j, 0, X+1) {
    add(dp[i+1][j], dp[i][j%S[i]] + i * dp[i][j]);
  }
  cout << dp[N][X] << endl;
  return 0;
}


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

const int MAX_N = 200010;
int dp[MAX_N][2];
char S[MAX_N];
// dp[i][0] := i文字目まで確定したときに、直前の部分文字列が1文字である場合の最大分割数
// dp[i][1] := i文字目まで確定したときに、直前の部分文字列が2文字である場合の最大分割数
// dp[0][0] = 1, dp[0][1] = 0, dp[1][1] = 1;
// dp[1][0] = (S[1] != S[0]) ? 2: 0;
// (dp[i-1][0]からの遷移)
// if(S[i] != S[i-1]) dp[i][0] = max(dp[i][0], dp[i-1][0] + 1);
// dp[i+1][1] = max(dp[i+1][1], dp[i-1][0] + 1);
// (dp[i-1][1]からの遷移)
// dp[i][0] = max(dp[i][0], dp[i-1][1] + 1);
// if(S[i-2] != S[i] || S[i-1] != S[i+1]) dp[i+1][1] = max(dp[i+1][1], dp[i-1][1] + 1);

int main() {
    scanf("%s",S);
    int n = strlen(S);
    dp[0][0] = 1, dp[1][1] = 1;
    for(int i = 1; i < n; ++i) {
        if(S[i] != S[i-1]) dp[i][0] = max(dp[i][0], dp[i-1][0] + 1);
        dp[i+1][1] = max(dp[i+1][1], dp[i-1][0] + 1);

        dp[i][0] = max(dp[i][0], dp[i-1][1] + 1);
        if(i-2>=0 && i+1 < n && (S[i-2] != S[i] || S[i-1] != S[i+1]))
            dp[i+1][1] = max(dp[i+1][1], dp[i-1][1] + 1);
    }
    printf("%d\n", max(dp[n-1][0], dp[n-1][1]));
    return 0;
}

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

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

#define rep(i, a, b) for(auto i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back

struct edge{int to;};
using graph = vector<vector<edge>>;

const int MOD = 1000000007;
auto add(auto a, auto b){return (a + b) % MOD;}

const int MAXN = 21;
bool a[MAXN][MAXN];
ll dp[2][1 << MAXN];

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

  int n;
  cin >> n;
  rep(i, 0, n) rep(j, 0, n)
    cin >> a[i][j];

  dp[0][0] = 1;
  rep(it, 0, n) {
    int i = ~it & 1;
    int prv = 1 - i;
    rep(bm, 0, (1 << n)) {
      if (__builtin_popcount(bm) != it + 1) continue;
      rep(matched, 0, n) {
	if (a[it][matched] and ((1 << matched) & bm) != 0) {
	  dp[i][bm] = add(dp[i][bm], dp[prv][bm - (1 << matched)]);
	}
      }
    }
  }
  cout << dp[n & 1][(1 << n) - 1] << '\n';
}


Measured memory_bytes: 33024
#include<iostream>
#include<algorithm>

using namespace std;

void printArray(int * arr, int num) {
	for(int i=0; i<num; i++) {
		if (i == 0) {
			cout<<arr[i];
		} else {
			cout<<" "<<arr[i];
		}
	}
	cout<<endl;
}


int main(int argc, char const *argv[])
{
	int n;
	int arr[100] = {0};

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

	printArray(arr, n);
	for(int i=1; i<n; i++) {
		int v = arr[i];
		int j = i - 1;
		while (j >=0 && arr[j]>v) {
			arr[j+1] = arr[j]; 
			j--;
		}
		arr[j+1] = v;
		printArray(arr, n);
	}
	return 0;
}


Measured memory_bytes: 3092
#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, V):
    M = N // 2

    def build(off):
        d = dict()
        for i in range(off, N, 2):
            if V[i] not in d:
                d[V[i]] = 0
            d[V[i]] += 1

        arr = []
        for k, v in d.items():
            arr.append((M - v, k))

        arr.append((M, -1))

        arr.sort()
        return arr

    A = build(0)
    B = build(1)

    best = N
    for c1, v1 in A:
        for c2, v2 in B:
            if v1 != v2:
                best = min(best, c1 + c2)
                break
    return best


def main():
    N = int(inp())
    V = [int(e) for e in inp().split()]
    assert len(V) == N
    print(solve(N, V))


if __name__ == '__main__':
    main()


Measured memory_bytes: 23260
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define deb(x) cerr << #x <<": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;

int main(){
    ios;
    int n; cin >> n;
    vector<int> v(n+1);
    int cnt = 0;
    rep1(i,n){
        cin >> v[i];
        if( (i&1) && (v[i]&1) ) cnt++;
    }
    cout << cnt;
    return 0;
}


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

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main() {
    long long N;
    scanf("%lld", &N);
    long long M;
    scanf("%lld", &M);

    vpll a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(all(a));
    ll ans = 0;
    for (int i = 0; i < N && M > 0; i++) {
        ans += a[i].first * min(M, a[i].second);
        M -= min(M, a[i].second);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

typedef struct Node {
	int val;
	Node *parent = NULL;
	Node *left = NULL;
	Node *right = NULL;
} Node;


Node *Tree = NULL; //树 

void insert(int key) {
	Node *cur = Tree;
	Node *parent = NULL;
	while (cur != NULL) {
		parent = cur;
		if (key < cur->val) {
			cur = cur->left;
		} else {
			cur = cur->right;
		}
	}
	if (parent == NULL) {
		Tree = new Node;
		Tree->val = key;
		return;
	}
	Node *t = new Node;
	t->val = key;
	t->parent = parent;
	if (key < parent->val) {
	   parent->left = t;
    } else {
    	parent->right = t;
	}
}

Node* find(int key) {
	Node *cur = Tree;
	bool found = false;
	while (cur != NULL && !found) {
		if (key < cur->val) {
			cur = cur->left;
		} else if (key > cur->val) {
			cur = cur->right;
		} else {
			return cur;
		}
	}
	return NULL;
}

Node *findMin(Node *node) {
	Node *cur = node;
	while (cur->left != NULL) {
		cur = cur->left;
	}
	return cur;
}

void del(Node *node) {
	if (node != NULL) {
		if (node->left == NULL && node->right == NULL) { //无子节点 
			Node *parent = node->parent;
			if (parent->left == node) {
				parent->left = NULL;
			} else {
				parent->right = NULL;
			}
			delete node;
		} else if (node->left != NULL && node->right != NULL) { //有两个子节点 ,在右子树中找到最小的节点，将其值与当前节点交换，然后，删除那个最小的节点位置的节点，情况则变成1和3情况 
			Node * rminNode = findMin(node->right);
			int t = node->val;
			node->val = rminNode->val;
			rminNode->val = t;
			//情况变为其他两种情况 
			//接下来，删除minNode
			 del(rminNode);
		} else { //有一个子节点 
			Node * child;
			if (node->left != NULL) {
				child = node->left;
			} else {
				child = node->right;
			}
			Node *parent = node->parent;
			child->parent = parent;
			if (parent->left == node) {
				parent->left = child;
			} else {
				parent->right = child;
			}
			delete node;
		}
	}
}

void printPre(Node * node) {
	cout  << " " << node->val;
	if (node->left != NULL) {
		printPre(node->left);
	}
	
	if (node->right != NULL) {
		printPre(node->right);
	}
}

void printIn(Node * node) {

	if (node->left != NULL) {
		printIn(node->left);
	}
	cout  << " " << node->val;
	if (node->right != NULL) {
		printIn(node->right);
	}
}

int main() {
	int n;
	cin >> n;
	for (int i=0;i<n;i++) {
		string s;
		cin >> s;
		if (s[0] == 'i') {
			long long key;
			cin >> key;
			insert(key);
		} else if (s[0] == 'f') {
			long long key;
			cin >> key;
			Node * f = find(key);
			if (f != NULL) {
		     cout << "yes" << endl;
	       } else {
		     cout << "no" << endl;
	       }
		} else if (s[0] == 'd') {
			long long key;
			cin >> key;
			del(find(key));
		} else if (s[0] == 'p') {
			printIn(Tree);
			cout << endl;
			printPre(Tree);
			cout << endl;
		}
	}
	return 0;
	
}


Measured memory_bytes: 21884
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn=1e5+100;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, ans=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int a;
        cin>>a;
        ans+=a-1;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
  int n,r,x,y;
  cin>>n>>r;
  y=r;
  int i,c;
  for(i=0;i<n;i++){
    cin>>x;
    r-=x;
    c++;
    y=min(x,y);
  }
  while(r-y>=0){
    r-=y;
    c++;
  }
  cout<<c;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

#define INF 1000000001

using namespace std;

typedef struct{
    int t;
    bool in;
    int x;
} event;

bool cmp(const event &a, const event &b){
    if(a.t == b.t) return b.in;
    else return (a.t) < (b.t);
}

int main(){
    int N, Q;
    cin >> N >> Q;

    int s, t, x;
    vector< event > E(2*N + 2);
    int cnt = 0;
    for(int i=0; i<N; i++){
        cin >> s >> t >> x;
        E[cnt] = event{s-x, true, x};
        cnt ++;
        E[cnt] = event{t-x, false, x};
        cnt++;
    }
    E[cnt] = event{-1, true, INF};
    E[cnt+1] = event{INF+1, false, INF};

    sort(E.begin(), E.end(), cmp);

    set<int> blkd;
    int D[Q];
    for(int i=0; i<Q; i++){
        cin >> D[i];
    }

    int d;
    int pre = INF;
    cnt = 0;
    bool brk = false;

    for(int i=0; i<Q; i++){
        d = D[i];
        brk = false;
        while(1){
            auto e = E[cnt];
            t = e.t;
            if(t <= d){
                if(e.in){
                    blkd.insert(e.x);
                }
                else{
                    blkd.erase(e.x);
                }
            }
            else{
                if(*blkd.begin() != INF) cout << *blkd.begin() << endl;
                else cout << -1 << endl;
                break;
            }
            cnt++;
        }
    }
    return 0;
}

Measured memory_bytes: 16128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication50
{
    class Program
    {
        static void Main()
        {
            while (true)
            {
                string r = Console.ReadLine();
                if (r == null) break;
                decimal s = decimal.Parse(r), k = s;
                for (int a = 0; a < 9; a++)
                {
                    if (a % 2 == 0) { s *= 2; k += s; }
                    else { s /= 3; k += s; }
                }
                Console.WriteLine(k);
            }
        }
    }
}

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

long gcd(long a, long b)
{
    if(a < b) {
        swap(a, b);
    }

    long r = a % b;
    while(r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

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

    cin >> a >> b >> c >> d;

    long can_divite_c = (b / c - (a - 1) / c);
    long can_divite_d = (b / d - (a - 1) / d);

    long cd = c * d / gcd(c, d);
    long can_divite_cd = (b / cd - (a - 1) / cd);

    cout << b - a + 1 - (can_divite_c + can_divite_d - can_divite_cd) << endl;

    return 0;
}


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

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

    int now = 0, c = 0;
    while(true){
        if(now == 1){
            cout << c << endl;
            break;
        }

        if(c >= n){
            cout << -1 << endl;
            break;
        }

        c++;
        now = a[now];
    }
}

Measured memory_bytes: 3780
use std::io;
use std::str::FromStr;
use std::collections::HashSet;

fn input<T:FromStr>() -> T {
  let mut line: String = String::new();
  io::stdin().read_line(&mut line);
  line.trim().parse().ok().unwrap()
}

fn main() {
  let n: i32 = input();
  let s: String = input();
  let mut max = 0;
  for i in 1..s.len() {
    let mut j = 0;
    let mut set1 = HashSet::new();
    let mut set2 = HashSet::new();
    for c in s.chars() {
      if j < i {
        set1.insert(c);
      } else {
        set2.insert(c);
      }
     j += 1;
    }
    let sum = set1.intersection(&set2).count();
    if sum > max {
      max = sum;
    }
    //println!("{:?}", set1);
    //println!("{:?}", set2);
    //println!("{}", sum);
  }
  println!("{}", max);
}

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

int main(){
    char str[200003]; cin >> str;
    int t=0;
    char *c = str;
    while(*c!='\0'){
        t += *c-'0';
        t %= 9;
        c++;
    }
    if(t){
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 3716
n,A,B,C=map(int,input().split())
l=[int(input()) for i in range(n)]
def calc(r,a,b,c):
    if r == n:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a,b,c) > 0 else 10**9
    else:
        root1 = calc(r+1,a,b,c)
        root2 = calc(r+1,a+l[r],b,c) +10
        root3 = calc(r+1,a,b+l[r],c) +10
        root4 = calc(r+1,a,b,c+l[r]) +10
        return min(root1,root2,root3,root4)
print(calc(0,0,0,0))

Measured memory_bytes: 3064
#line 2 "header.hpp"

//%snippet.set('header')%
//%snippet.fold()%
#ifndef HEADER_H
#define HEADER_H

// template version 2.0
using namespace std;
#include <bits/stdc++.h>

// varibable settings
const long long INF = 1e18;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (ll i = (ll)((b)-1); i >= (ll)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T>
inline void chmax(T &a, const T &b) {
    if ((a) < (b)) (a) = (b);
}
template <class T>
inline void chmin(T &a, const T &b) {
    if ((a) > (b)) (a) = (b);
}

#define divceil(a, b) ((a) + (b)-1) / (b)
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x)    \
    sort(all(x)); \
    x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef long double ld;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
    }
} fast;
void check_input() {
    assert(cin.eof() == 0);
    int tmp;
    cin >> tmp;
    assert(cin.eof() == 1);
}

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H */
//%snippet.end()%
#line 2 "solve.cpp"
template<class T=ll> using vec = vector<T>;
using lint = long long;

template<class T>/*{{{*/
void pairsort(vector<T>& x, vector<T>& y){
    int n = sz(x);
    vector<tuple<T, T>> t(n);
    rep(i, n){
        t[i] = make_tuple(x[i], y[i]);
    }
    sort(all(t), [&](auto &l, auto &r){return get<0>(l)+get<1>(l) < get<0>(r)+get<1>(r);});
    rep(i, n){
        x[i] = get<0>(t[i]);
        y[i] = get<1>(t[i]);
    }
}/*}}}*/

int solve() {
    lint n;cin>>n;
    vec<lint> h(n), p(n);
    rep(i, n){
        cin>>h[i]>>p[i];
    }
    pairsort(h, p);
    dump(h);
    dump(p);

    vector<vector<ll>> dp(n+1, vector<ll>(n+1, INF));
    dp[0][0] = 0;
    rep(i, 1, n+1){
        rep(c, 0, n+1){
            chmin(dp[i][c], dp[i-1][c]);
            if (dp[i-1][c]<=h[i-1]){
                chmin(dp[i][c+1], dp[i-1][c]+p[i-1]);
            }
        }
    }
    r_rep(c, 0, n+1){
        if (dp[n][c]<INF) {
            cout << c << endl;
            return 0;
        }
    }

    return 0; 
}


int main(){/*{{{*/
    solve();
    check_input();
    return 0;
}/*}}}*/


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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int i=0;i<(n);i++)        //repeat n times
#define REP2(i,s,n) for(int i=(s);i<(n);i++)   //repeat from s to n 
#define REPD(i,n) for(int i=(n);i>=0;i--)      //repeat from n to 0
#define REPD2(i,s,e) for(int i=(s);i>=(e);i--) //repeat from s to e
#define RANGE(i,v) for(auto &i:v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

int main(){
    int N;
    cin>>N;
    V<LL> A(N);
    REP(i,N) cin>>A[i];

    sort(ALL(A));

    LL ans = 0;
    REP(i,N-1){
        ans += A[N-((i+1)/2)-1];
    }

    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4844
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;

int N, M, V, P; 
vector<int> A;

bool f(int x){
  // M人がV問の点数を1上げる
  // 上位P-1個と自分に点数を上げる
  // 残りは小さいところから上げていく
  if(N-P <= x) return true;
  
  if(A[x]+M < A[N-P]) return false;
  // 残りM*Vまで上げなければいけない
  // 1個につき上げれる点数はM
  // A[x]+Mになるまで上げれば良い
  int cnt = 0;
  REP(i, N-P+1){
    if(i == x) continue;
    cnt += min(M, A[x]+M-A[i]);
  }
  if(cnt >= M*(V-P)) return true;
  return false;
}

signed main() {
  cin >> N >> M >> V >> P;

  A.resize(N);
  REP(i, N) cin >> A[i];

  sort(ALL(A));

  int ok = N-1;
  int ng = -1;
  while(ok-ng > 1){
    int mid = (ok+ng)/2;
    if(f(mid)) ok = mid;
    else ng = mid;
  }

  cout << A.end()-lower_bound(ALL(A), A[ok]) << endl;

  return 0;
}

Measured memory_bytes: 1024