akhauriyash/Code-Regression huggingface dataset:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)


def can_be_used(x):
    # x: 0-index
    if x < p:
        return True

    if a[x] + m < a[p-1]:
        return False

    vote_max = (p - 1 + n - x) * m
    for i in range(p-1, x):
        vote_max += a[x] + m - a[i]

    if vote_max < m * v:
        return False

    return True


l = 0
r = n

while r - l > 1:
    mid = (l + r) // 2

    if can_be_used(mid):
        l = mid
    else:
        r = mid

ans = l + 1
print(ans)


Measured memory_bytes: 14484
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
	reverse(s.begin(), s.end());
	if (s == t) cout << "YES";
	else cout << "NO"; 
}

Measured memory_bytes: 3612
n, d = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]


def dist(a, b):
    sm = 0
    for ea, eb in zip(a, b):
        sm += (ea - eb) ** 2

    return sm


ans = 0
for i in range(n):
    for j in range(i + 1, n):
        dst = dist(x[i], x[j])
        for k in range(int(dst ** 0.5) + 1):
            if k ** 2 == dst:
                ans += 1
                break

print(ans)


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

const int maxn = 200010;

int x[maxn];
int l[maxn], r[maxn];
int lb[18][maxn], rb[18][maxn], dpl[1<<18], dpr[1<<18];
int bound[maxn];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,v;
	cin >> n >> v;
	for(int i=1;i<=n;i++)
		cin >> x[i];
	for(int i=0;i<=n;i++)
		bound[i] = 1e9;
	l[1] = 1;
	for(int i=2;i<=n;i++)
		if(x[i] - x[i-1] <= v)
			l[i] = l[i-1];
		else
			l[i] = i;
	r[n] = n;
	for(int i=n-1;i>=1;i--)
		if(x[i+1] - x[i] <= v)
			r[i] = r[i+1];
		else
			r[i] = i;
	vector<int> cap;
	{
		int z = v/2;
		while(z){
			cap.emplace_back(z);
			z/=2;
		}
		cap.emplace_back(0);
	}
	int N = cap.size();
	for(int i=0;i<N;i++){
		lb[i][0] = lb[i][1] = 1;
		for(int j=2;j<=n;j++)
			if(x[j] - x[j-1] <= cap[i])
				lb[i][j] = lb[i][j-1];
			else
				lb[i][j] = j;
		rb[i][n+1] = rb[i][n] = n;
		for(int j=n-1;j>=1;j--)
			if(x[j+1] - x[j] <= cap[i])
				rb[i][j] = rb[i][j+1];
			else
				rb[i][j] = j;
	}
	dpl[0] = 0;
	for(int i=0;i<(1<<N);i++)
		for(int j=0;j<N;j++)
			if(!((i>>j)&1))
				dpl[1<<j|i] = max(dpl[1<<j|i], rb[j][dpl[i]+1]);
	for(int i=0;i<(1<<N);i++)
		dpr[i] = n+1;
	for(int i=0;i<(1<<N);i++)
		for(int j=0;j<N;j++)
			if(!((i>>j)&1))
				dpr[1<<j|i] = min(dpr[1<<j|i], lb[j][dpr[i]-1]);
	for(int i=0;i<(1<<N);i++)
		bound[dpl[i]] = min(bound[dpl[i]], dpr[(1<<N) - 1 - i]);
	for(int i=n-1;i>=0;i--)
		bound[i] = min(bound[i], bound[i+1]);
	for(int i=1;i<=n;i++)
		if(bound[l[i] - 1] <= r[i] + 1)
			cout << "Possible\n";
		else
			cout << "Impossible\n";
}


Measured memory_bytes: 36880
import java.util.*;
class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    
    int n1 = sc.nextInt();
    int n2 = 0;
    int n3 = n1;
    
    for(int i=0 ; i<10 ; i++){
      
      n2 += n3%10;
      n3 /=10;
      
      if(n3==0){
        break;
      }
    }
    
    if(n1%n2==0){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 23764
N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    for j in range(W+1):
        if j-w[i]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

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

#define reps(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   reps(i,0,n)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define PI (acos(-1))

int K[310][310];//K[i][j]=iからjまで行く最短経路のコスト合計
int N,G[310][310]={};
//G[i][j]にはiからjへの辺が存在するならその重み、無いなら0を入れる
//負の重みがあるときにも使えるようにするため

void WarshallFloyd(){

  //初期化
  rep(i,N){
    rep(j,N){
      if(G[i][j] >= 0)K[i][j]=G[i][j];
      else K[i][j]=INF;//辺が存在しなければコストINF
    }
  }

  rep(k,N){
    rep(i,N){
      rep(j,N){
        //辺ikとkjの存在を条件に入れておかないと負の重みの辺があるときバグる
        if(K[i][j] > K[i][k]+K[k][j] && G[i][k]!=0 && G[k][j] != 0){
          K[i][j] = K[i][k]+K[k][j];
        }
      }
    }
  }

}  

int main(){
  N=10;
  int H,W;
  cin >> H >> W;
  rep(i,10){
    rep(j,10){
      cin >> G[i][j];
    }
  }
  WarshallFloyd();

  /*rep(i,10){
    rep(j,10){
      cout << K[i][j] << " ";
    }
    cout << endl;
  }*/
  int cnt[10]={};
  rep(i,H*W){
    int a;
    cin >> a;
    if(a!=-1){
      cnt[a]++;
    }
  }

  int ans=0;
  rep(i,10){
    ans += K[i][1]*cnt[i];
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

int main(){
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double hd = h * 30 + m * 0.5, d;
    double md = m * 6;
    if (abs(hd - md) <= 180) d = abs(hd - md);
    else d = 360 - abs(hd - md);
    d = d * acos(-1) / 180;
    cout << fixed << setprecision(10) << sqrt(a * a + b * b - 2 * a * b * cos(d)) << endl;
}



Measured memory_bytes: 4228
#include<bits/stdc++.h>
using namespace std;
int main(){

int a,b,multi,pls,mins;
cin>>a>>b;
multi=a*b;
pls=a+b;
mins=a-b;
if (multi>pls&&multi>mins)
cout<<multi;
else if (pls>multi&&pls>mins)
cout<<pls ;
else cout<<mins;
return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n;
  cin >> n;
  vector<int> a(n);
  map<int,int> mp;
  ll sum =0 ;
  for(int i=0;i<n;i++)
  {
      cin >> a[i];
      mp[a[i]]++;
      sum += a[i];
  }
  ll q;
  cin >> q;
  for(int i=0;i<q;i++)
  {
       ll x,y;
       cin >> x >> y;
       mp[y] += mp[x];
       sum += mp[x]*(y-x);
       mp[x]=0; cout << sum << endl;
  }

}


Measured memory_bytes: 8076
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<map>
using namespace std;

int main()
{
	string s, t, u;

	cin >> s >> t >> u;
	if (s[s.length() - 1] == t[0] && t[t.length() - 1] == u[0])
		cout << "YES";
	else
		cout << "NO";
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, Integer> data = new HashMap<Integer, Integer>();
        ArrayList<Integer> scores = new ArrayList<Integer>();

        String line;
        while (!(line = br.readLine()).equals("0,0")) {
            String[] input = line.split(",");
            int p = Integer.parseInt(input[0]);
            int s = Integer.parseInt(input[1]);
            data.put(p, s);
            if (!scores.contains(s)) {
                scores.add(s);
            }
        }

        Object[] o = scores.toArray();
        int length = o.length;
        int[] score = new int[length];
        for (int i = 0; i < length; i++) {
            score[i] = (int) o[i];
        }

        Arrays.sort(score);

        while ((line = br.readLine()) != null) {
            int n = Integer.parseInt(line);
            int point = data.get(n);

            // 順位を探す
            int i = -1;
            while (point != score[++i])
                ;

            System.out.println((length - i));
        }

    }
}


Measured memory_bytes: 24268
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int N, M; cin >> N >> M;
    string S; cin >> S;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b; a--, b--;
        G[a].push_back(b);
        if (a != b) G[b].push_back(a);
    }
    vector<bool> okay(N, true), visited(N);
    auto recur = [&](auto rec, int i, vector<int>& A) -> void {
        if (visited[i]) return;
        visited[i] = true;
        if (!okay[i]) return;
        for (int next : G[i]) rec(rec, next, A);
        A.push_back(i);
        int a = 0;
        for (int next : G[i]) {
            if (okay[next] && S[next] == 'A') a |= 1;
            if (okay[next] && S[next] == 'B') a |= 2;
            if (a == 3) break;
        }
        okay[i] = a == 3;
    };
    vector<int> A, B;
    int n = 10;
    A.resize(N); iota(begin(A), end(A), 0);
    while (n--) {
        vector<int> B;
        fill(begin(visited), end(visited), false);
        for (auto i : A) recur(recur, i, B);
        swap(A, B);
    }
    bool ans = false;
    for (auto a : okay) ans |= a;
    cout << (ans ? "Yes\n" : "No\n");
    return 0;
}

Measured memory_bytes: 20736
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll N; cin >> N;
    vvll v(10, vll(10, 0));

    reprr(i, 1, N + 1) {
        string s = to_string(i);
        ll f = s[0] - '0';
        ll b = s[s.size()-1] - '0';
        v[f][b]++;
    }

    ll total = 0;
    rep(i, 10) rep(j, 10) {
        total += v[i][j] * v[j][i];
    }
    cout << total << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = sorted(Counter(A).items())
    ans = 0
    for t in m:
        if t[1] == 1 and erato[t[0]]:
            ans += 1
        for i in range(t[0],M+1,t[0]):
            erato[i] = False
            
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 50620
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  int AC = 0;
  int WA = 0;
  int TLE = 0;
  int RE = 0;
  string s;
  cin>>N;
  for(int i = 0;i < N;i++){
    cin>>s;
    if(s == "AC"){
      AC += 1;
    }else if(s == "WA"){
      WA += 1;
    }else if(s == "TLE"){
      TLE += 1;
    }else if(s == "RE"){
      RE += 1;
    }    
  }
  cout<<"AC "<<"x "<<AC<<'\n';
  cout<<"WA "<<"x "<<WA<<'\n';
  cout<<"TLE "<<"x "<<TLE<<'\n';
  cout<<"RE "<<"x "<<RE<<'\n';
}

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

int a[50];

int main(){
	int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a+n);
    double aux = (a[0]+a[1])/2.0;
    for(int i = 2; i < n; i++)
        aux = (aux+a[i])/2.0;
    printf("%.6f\n", aux);
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
typedef long long ll;
int main(){
    int x;
    cin >> x;
    if(x < 1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;
    return 0;
}


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

long dp[101][10001];

long max(long a, long b){
    return a > b ? a : b;
}

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

    vector<long> v(N);
    vector<long> w(N);
    for(int i = 0; i < N; i++){
        cin >> v[i] >> w[i];
    }
    for(int i = 0; i <= W; i++) dp[0][W] = 0;

    for(int i = 0; i < N; i++){
        for(int j = 0; j <= W; j++){
            if(j >= w[i]) dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
            else dp[i + 1][j] = dp[i][j];
        }
    }

    cout << dp[N][W] << endl;
    return 0;
}


Measured memory_bytes: 10920
n=int(input())
xy = []
check = 0
for i in range(n):
    a = int(input())
    if a ==0:
        check+=1
    for j in range(a):
        x,y=map(int,input().split())
        xy.append([i+1,x,y])
        
ans = 0
for i in range(2**n):
    temp=check
    se=set()
    for idx,x,y in xy:
        if i>>(idx-1) & 1:
            if i>>(x-1) & 1:
                if y==1 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==0:
                    break
            else:
                if y==0 and idx not in se:
                    temp+=1
                    se.add(idx)
                elif y==1:
                    break
    else:
        ans=max(ans,temp)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template <size_t I, class H, class... T> struct TupleReaderWriter{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple_cat(tuple<H>(v),TupleReaderWriter<sizeof...(T)-1,T...>::r(i));}static void w(ostream&o,tuple<H,T...>&t,string d){TupleReaderWriter<I-1,H,T...>::w(o,t,d);o<<d<<get<I>(t);}};
template <class H, class... T> struct TupleReaderWriter<0,H,T...>{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple<H>(v);}static void w(ostream&o,tuple<H,T...>&t,string d){o<<get<0>(t);}};
template<class T>istream&operator>>(istream&i,vector<T>&v){for(auto&x:v)i>>x;return i;}
template<class T>ostream&operator<<(ostream&o,vector<T>&v){string delim="";for(auto&x:v)o<<delim<<x,delim=" ";return o;}
template <class... T> istream& operator>>(istream&i,tuple<T...>& t) { t = TupleReaderWriter<sizeof...(T), T...>::r(i); return i; }
template <class... T> ostream& operator<<(ostream& o, tuple<T...>& t) { string delim = " "; TupleReaderWriter<sizeof...(T) - 1, T...>::w(o, t, delim); return o; }
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using vector2d = vector<vector<T>>;
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }
int main() {
    int N;
    i64 C;
    cin >> N >> C;
    vector<i64> X(N), V(N);
    for(int i = 0; i < N; i++) {
        cin >> X[i] >> V[i];
    }
    i64 ans = 0;
    for(int b = 0; b < 2; b++) {
        vector<i64> F(N, 0), B(N, 0);
        i64 e = 0;
        for(int i = 0; i < N; i++) {
            e += V[i] - (X[i] - (i ? X[i - 1] : 0));
            F[i] = max(i ? F[i - 1] : 0, e);
        }
        e = 0;
        for(int i = N - 1; i >= 0; i--) {
            e += V[i] - ((i < N - 1 ? X[i + 1] : C) - X[i]);
            B[i] = max(i < N - 1 ? B[i + 1] : 0, e);
        }

        for(int i = 0; i < N - 1; i++) {
            ans = max({ans, F[i], F[i] - X[i] + B[i + 1]});
        }

        ans = max(ans, F.back());

        reverse(WHOLE(X)), reverse(WHOLE(V));
        for(auto &x : X) x = C - x;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3424
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            bool ans = true;
            for (int i = 0; i < s.Length; i++) {
                if ((i % 2 == 0 && s[i] == 'L') || (i % 2 != 0 && s[i] == 'R')) {
                    ans = false;
                }
            }
            Console.WriteLine(ans ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
using namespace std;
 
#define li long long int
#define ld long double
const int MX1=1e5+5;
const int MX2=1e6+5;
const li inf=4e18;
const li mod=1e9+7;

li power(li a,li b){li res=1;while(b){if(b%2)res=(res*a)%mod;
a=(a*a)%mod;b/=2;}return res;}
 
li mmi(li a){return power(a,mod-2);}
 
li cntbit(li n){li cnt=0;while(n){n&=(n-1);cnt++;}return cnt;}

int n,k;

void solve(){
	cin>>n>>k;
	li ans=0;
	if(k==0){
		cout<<n*1ll*n;
		return ;
	}
	for(int b=k+1;b<=n;b++){
		ans+=(b-k)*1ll*(n/b);
		ans+=max(0ll,n%b-k+1ll);
	}
	cout<<ans;
}

int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <algorithm>
#include <utility>
using namespace std;

using ll = long long;

int main(){
  int n, x; cin >> n >> x;
  int m[n];
  for(int i=0; i<n; i++) cin >> m[i];

  int ans = n;
  int mind = 1000;
  for(int i=0; i<n; i++){
    x -= m[i];
    mind = min(mind, m[i]);
  }

  ans += x/mind;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,N=1e6;
vector<int>a(N);

int main(){
	cin>>n;
	int x;
	for(int i=0;i<n;i++){
		cin>>x;
		a[x]++;
	}
	int ans=0;
	for(int i=1;i<=N;i++){
		if(a[i]){
			if(a[i]==1)ans++;
			for(int j=i+i;j<=N;j+=i)a[j]=0;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7080
/* AtCoder Panasonic Programming Contest 2020. Task D. */
#include <bits/stdc++.h>

using namespace std;

#define COUT_PRECISION 10

namespace abreto {

struct nform {
    string form;
    int used;
    nform(string f = "", int u = 0)
        : form(f), used(u)
    {}
};

void main(void)
{
    int N;
    vector<nform> *v = new vector<nform>();

    cin >> N;
    v->push_back(nform("a", 1));
    while (--N) {
        vector<nform> *nv = new vector<nform>();

        for (auto it = v->begin(); it != v->end(); it++) {
            int alphabet = it->used + 1;
            for (int i = 0; i < alphabet; i++) {
                char append = 'a' + i;
                nv->push_back(nform(
                    it->form + append,
                    it->used + (i == it->used)
                ));
            }
        }

        delete v; v = nv;
    }

    for (auto it = v->begin(); it != v->end(); it++) {
        cout << (it->form) << '\n';
    }
}

}

int main(void) {
    cin.sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(COUT_PRECISION);
    abreto::main();
    return 0;
}


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

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);


int main() {
    ll a, b;
    cin >> a >> b;
    cout << a*b/2 << endl;
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


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

#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cerr << #x " = " << (x) << '\n'
#define DBG         cerr << "Hi" << '\n'
#define pb          push_back
#define PI          acos(-1.00)
#define xx          first
#define yy          second
#define eps         1e-9

typedef unsigned long long int ULL;
typedef long long int LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
map<int,int>freq;
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n, a;
    sf(n);
    for(int i = 1; i<=n; i++)
    {
        sf(a);
        freq[a]++;
    }
    int ans = 0;
    for(auto u: freq)
    {
        if(u.xx <= u.yy)
            ans += u.yy - u.xx;
        else
            ans += u.yy;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 4736
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }

int main() {
	int n,m;
	cin >> n >> m;
	priority_queue<P> q;
	REP(i, n) {
		int a;
		cin >> a;
		q.push(P(a, 1));
	}
	REP(i, m) {
		int b, c;
		cin >> b >> c;
		q.push(P(c, b));
	}
	ll res = 0;
	REP(i, n) {
		P p = q.top();
		q.pop();
		res += p.first;
		if (p.second > 1) {
			p.second--;
			q.push(p);
		}
	}
	put(res);
	return 0;
}



Measured memory_bytes: 2420
// CODE FESTIVAL 2016 qual B
// E - Lexicographical disorder

#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#define MAX_N 100000
#define MAX_SUM_S 400000
#define MAX_V (MAX_SUM_S + MAX_N + 1) // 文字 + 終端文字 + root
#define ALPH 26
using namespace std;


int N, Q;
string ss[MAX_N];
vector<int> g[MAX_V];
char node_c[MAX_V];
int node_i[MAX_V];
int q_order[ALPH + 1];
int new_node_id, node_id, next_node_id;
int cnt[MAX_N][ALPH + 1][ALPH + 1];
int ans;

int main() {

  char buff[MAX_SUM_S + 2];
  bool found;
  int k;

  scanf("%d", &N);
  node_c[0] = ' ';
  node_i[0] = 0;
  new_node_id = 1;
  for (int i = 0; i < N; i++) {
    scanf("%s", buff);
    ss[i] = string(buff);
    ss[i] += '{';
    node_i[0]++;
    node_id = 0;
    for (int j = 0; j < (int)ss[i].size(); j++) {
      found = false;
      for (int e = 0; e < (int)g[node_id].size(); e++) {
        if (node_c[g[node_id][e]] == ss[i][j]) {
          node_i[g[node_id][e]]++;
          node_id = g[node_id][e];
          found = true;
          break;
        }
      }
      if (!found) {
        g[node_id].push_back(new_node_id);
        node_c[new_node_id] = ss[i][j];
        node_i[new_node_id] = 1;
        node_id = new_node_id;
        new_node_id++;
      }
    }
  }

  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < N; i++) {
    node_id = 0;
    for (int j = 0; j < (int)ss[i].size(); j++) {
      for (int e = 0; e < (int)g[node_id].size(); e++) {
        cnt[i][node_c[g[node_id][e]] - 'a'][ss[i][j] - 'a'] += node_i[g[node_id][e]];
        if (node_c[g[node_id][e]] == ss[i][j]) {
          next_node_id = g[node_id][e];
        }
      }
      node_id = next_node_id;
    }
  }

  q_order[ALPH] = -1;
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    scanf("%d %s", &k, buff);
    k--;
    for (int j = 0; j < ALPH; j++) {
      q_order[buff[j] - 'a'] = j;
    }

    ans = 0;
    for (int c1 = 0; c1 < ALPH + 1; c1++) {
      for (int c2 = 0; c2 < ALPH + 1; c2++) {
        if (q_order[c1] < q_order[c2]) {
          ans += cnt[k][c1][c2];
        }
      }
    }
    ans++;
    printf("%d\n", ans);
  }

  return 0;

}




Measured memory_bytes: 313216
#include <iostream>
using namespace std;
int main(){
    int n;
    while(cin >>n){
        if(n==0)
            break;
        int a[n];
        for(int i=0;i<n;i++)
            cin >> a[i];
        int time=0;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){
                if(a[j]>a[j+1]){
                    int tmp;
                    tmp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=tmp;
                    time++;
                }
            }
        }
        cout << time << endl;
    }
}

Measured memory_bytes: 1160
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main()
{
  stack<int> num;
  int x;
	vector<int> ans;

  while (cin >> x) {
    if (x != 0) {
      num.push(x);
    } else {
      ans.push_back(num.top());
      num.pop();
    }
  }

  x = ans.size();
  for (int i = 0; i < x; i++) {
    cout << ans[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 1220
import java.util.Map.Entry;
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		int K = sc.nextInt();
		int T = sc.nextInt();
		int max = 0;
		for(int i = 0; i < T; i++){
			int a = sc.nextInt();
			max = Math.max(max, a);
		}
		
		int ans = (max - 1) - (K - max);
		if(ans >= 0) System.out.println(ans);
		else System.out.println(0);
	}
}

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
    	if (hasNextByte()) return buffer[ptr++];
    	else return -1;
    }
    private static boolean isPrintableChar(int c){
    	return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
    	while(hasNextByte() && !isPrintableChar(buffer[ptr]))
    		ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define forn2(i,a,n) for(int i=a;i<n;i++)
#define fore(i,n) for(int i=1;i<=n;i++)
#define fore2(i,a,n) for(int i=a;i<=n;i++)
#define forp(i,n) for(int i=n;i>0;i--)
#define fort(i,n) for(int i=n;i>=0;i--)
int sz,sz2;
string small="~";
string s,t,s2;
bool check()
{
	fore2(i,0,sz-sz2)
	{
		bool ok=0;
		forn(c,sz2)
		{
			if(s2[i+c]!=t[c])
				ok=1;
		}
		if(ok==0)
			return true;
	}
	return false;
}
void b()
{
	forn(c,sz)
		if(s2[c]=='?')
			s2[c]='a';
}
int main()
{
	cin>>s>>t;
	sz=s.size();sz2=t.size();
	s2=s;
	forn(i,sz)
		if(s2[i]=='?')
			s2[i]='a';
	if(check())
	{
		cout<<s2<<endl;
		return 0;
	}
	fore2(i,0,sz-sz2)
	{
		s2=s;
		forn(c,sz2)
			if(s2[c+i]=='?')
				s2[c+i]=t[c];
		b();
		if(check())
			small=min(small,s2);
	}
	if(small=="~")
	{
		cout<<"UNRESTORABLE"<<endl;
		return 0;
	}
	else
	{
		cout<<small<<endl;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 3604
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve(sc *scanner, wr *bufio.Writer) {
	rs := sc.getRunes()

	ans := "Yes"
	if rs[0] == rs[1] && rs[0] == rs[2] {
		ans = "No"
	}
	fmt.Fprintln(wr, ans)
}

func main() {
	sc := newScanner()
	wr := bufio.NewWriter(os.Stdout)
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)

	solve(sc, wr)
	wr.Flush()
}

// input ------------------------
type scanner struct {
	*bufio.Scanner
}

func newScanner() *scanner {
	sc := bufio.NewScanner(os.Stdin)
	return &scanner{sc}
}
func (sc *scanner) getInt() int {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return ret
}
func (sc *scanner) getInt2() (int, int) {
	return sc.getInt(), sc.getInt()
}
func (sc *scanner) getInt3() (int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *scanner) getInt4() (int, int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *scanner) getInts(n int) []int {
	ret := make([]int, n)
	for i := range ret {
		ret[i] = sc.getInt()
	}
	return ret
}
func (sc *scanner) getString() string {
	sc.Scan()
	return sc.Text()
}
func (sc *scanner) getRunes() []rune {
	return []rune(sc.getString())
}
func (sc *scanner) getFloat() float64 {
	sc.Scan()
	ret, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return ret
}
func (sc *scanner) getFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := range ret {
		ret[i] = sc.getFloat()
	}
	return ret
}

// math ----------------------------
func sum(ns ...int) int {
	var sum int
	for _, n := range ns {
		sum += n
	}
	return sum
}

func max(ns ...int) int {
	max := ns[0]
	for i := 1; i < len(ns); i++ {
		if max < ns[i] {
			max = ns[i]
		}
	}
	return max
}

func min(ns ...int) int {
	min := ns[0]
	for i := 1; i < len(ns); i++ {
		if min > ns[i] {
			min = ns[i]
		}
	}
	return min
}

func pow(a, b int) int {
	ret := 1
	for b > 0 {
		if b&1 > 0 {
			ret = ret * a
		}
		a = a * a
		b >>= 1
	}
	return ret
}


Measured memory_bytes: 1772
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static ArrayList<ArrayList<Integer>> g = new ArrayList<>();
	static int N;
	static boolean[] S;

	public static void main(String[] args) {
		N = sc.nextInt();
		char[] s = sc.next().toCharArray();
		S = new boolean[N];
		for (int i = 0; i < N; i++) {
			S[i] = s[i] == '1';
		}
		for (int i = 0; i < N; i++) {
			g.add(new ArrayList<>());
		}
		for (int i = 0; i < N - 1; i++) {
			int A = sc.nextInt() - 1;
			int B = sc.nextInt() - 1;
			g.get(A).add(B);
			g.get(B).add(A);
		}
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			Partial res = dfs(i, -1);
//			System.err.println(i + " " + res.max + " " + res.min + " " + res.count);
			if (res.min == 0) {
				ans = Math.min(ans, res.max / 2);
			}
		}
		System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
	}

	static Partial dfs(int cur, int from) {
		Partial ret = new Partial(0, 0, 0);
		Partial minMax = null;
		int minSum = 0;
		int diffSum = 0;
		for (int i = 0; i < g.get(cur).size(); i++) {
			int n = g.get(cur).get(i);
			if (n == from) continue;
			Partial p = dfs(n, cur);
			minSum += p.min + p.count;
			ret.max += p.max + p.count;
			ret.count += p.count;
			diffSum += p.max - p.min;
			if (minMax == null || p.min + p.count > minMax.min) {
				p.max += p.count;
				p.min += p.count;
				minMax = p;
			}
		}
		if (minMax == null) {
			//
		} else if (minMax.min > minSum - minMax.min) {
			diffSum -= minMax.max - minMax.min;
			int rest = minMax.min - (minSum - minMax.min);
			if (rest < diffSum) {
				ret.min = rest % 2;
			} else {
				ret.min = rest - diffSum;
			}
		} else {
			ret.min = minSum % 2;
		}
		if (S[cur]) {
			ret.count += 1;
		}
//		System.err.println(cur + " " + ret.max + " " + ret.min + " " + ret.count);
		return ret;
	}

	static class Partial {
		int min, max, count;

		public Partial(int min, int max, int count) {
			this.min = min;
			this.max = max;
			this.count = count;
		}
	}

}


Measured memory_bytes: 64788
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

int par[100500];

void init(int x){
  rep(i,x) par[i]=i;
}

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

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

void unite(int x,int y){
  x=root(x);
  y=root(y);
  if(x==y) return;
  par[x]=y;
}
 
int main(void){
    int N,M;
    int Fsave;
    cin >> N >> M;
    init(M);
    set<int> lang[M];
    bool exist[M]={};
    rep(i,N){
        int X;
        cin >> X;
        rep(j,X){
            int Y;
            cin >> Y;
            Y--;
            if(j==0) Fsave=Y;
            exist[Y]=true;
            unite(Fsave,Y);
        }
    }
    bool ans=true;
    int base;
    rep(i,M) if(exist[i]) base=root(i);
    rep(i,M) if(exist[i]) if(root(i)!=base) ans=false;

    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

int main() {
  int N;
  cin >> N;
  int a = N / 100;
  int b = (N - a * 100)/ 10;
  int c = N % 10;
  if(a != 7 & b != 7 & c != 7){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main(){
  int n,sum=0,nc;
  cin >> n;
  nc=n;
  while(n!=0){
    sum+=n%10;
    n/=10;
  }
  if(nc%sum==0)cout << "Yes"<<endl;
  else cout << "No"<< endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int>oe(2);
  int i;
  long a;
  for(i=0;i<n;i++){
    cin >> a;
    oe[a%2]++;
  }
  if(oe[1]%2==0)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

}


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

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

	int n,k;

	cin >> n >> k;

	if(n%k==0)
	{
		cout << 0 << '\n';
	}
	else
	{
		cout << 1 << '\n';
	}
	
	return 0;	
}


Measured memory_bytes: 256
(defmacro defsolver (name vars &body body)
  `(defun ,name ()
     (let (,@(mapcar #'list
            vars
            (mapcar (constantly '(read))
                vars)))
       ,@body)))

(defsolver solution-a (n)
  (format t "~a"
	  (if (< n 100)
	      "Bad"
	      (do
	       ((a 10)
		(ok "Good"))
	       ((< n 1) ok)
		(when (= a (mod n 10))
		  (setf ok "Bad"))
		(setf a (mod n 10))
		(setf n (floor n 10))))))

(solution-a)

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

int main(){
  int x1,x2,x3,x4,x5;
  cin >> x1 >> x2 >> x3 >> x4 >> x5;
  vector<int>x(6);
  x.at(1)=x1;
  x.at(2)=x2;
  x.at(3)=x3;
  x.at(4)=x4;
  x.at(5)=x5;
  for(int i=1;i<6;i++){
    if(x.at(i)==0){
      cout << i << endl;
    }
  }
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=5005,INF=1<<30;

ll rui(ll a,ll b){
    ll ans=1;
    while(b>0){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}

ll dp[MAX][MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    string S;cin>>S;
    int M=S.size();
    
    dp[0][0]=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dp[i+1][max(0,j-1)]+=dp[i][j];
            dp[i+1][max(0,j-1)]%=mod;
            
            dp[i+1][j+1]+=2*dp[i][j];
            dp[i+1][j+1]%=mod;
        }
    }
    
    cout<<dp[N][M]*rui(rui(2,mod-2),M)%mod<<endl;
}


Measured memory_bytes: 195840
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0

Measured memory_bytes: 134620
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;

string s;

bool reach(int start, int goal){
	int pos=start;
	while(pos<goal){
		if(pos+2 == goal || pos+1 == goal)return true;
		if(s[pos+2] == '.')pos+=2;
		else if(s[pos+1] == '.')pos++;
		else return false;
	}
}

int main(void){
	int n,a,b,c,d;

	cin>>n>>a>>b>>c>>d>>s;

	if(c<d){
		if(reach(a-1,c-1) && reach(b-1,d-1))cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	else{
		bool flag=false;
		for(int i=b-1;i<d;i++){
			if(s[i-1]=='.' && s[i]=='.' && s[i+1]=='.')flag=true;
		}
		if(reach(a-1,c-1) && flag)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 640
import java.util.*;


public class Main
{
	
	public static void main(String[] atgs) {
		Scanner s=new Scanner(System.in);
		String str=s.nextLine();
		str=str.replaceAll("eraser", "");
		str=str.replaceAll("erase","");
		str=str.replaceAll("dreamer","");
		str=str.replaceAll("dream","");
		if(str.equals(""))
			System.out.println("YES");
		else System.out.println("NO");
	}
}



Measured memory_bytes: 42296
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

n,m=get_i
a=array(n,1)
n.times do|i|
  a[i]=get_i
end
b=array(m,1)
m.times do|i|
  b[i]=gets.to_i
end
n.times do|i|
  ans=0
  m.times do|j|
    ans+=b[j]*a[i][j]
  end
  puts ans
end


Measured memory_bytes: 8896
#pragma region _head

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>
#include<regex>

#pragma region _define

#define f(i,a,b) for(int i=a;i<b;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n) f(i,0,n)cout<<v[i]<<endl
#define all(a) a.begin(),a.end()
#define size(s) s.size()
#define check() cout<<"! ! !"
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vc = vector<char>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using si = stack<LL>;
using ss = stack<st>;
using pi = pair<LL, LL>;
using v_pi = vector<pi>;

#pragma endregion

#pragma region _graph

#define node 50  //グラフの最大位数　適宜変更
//bool graph[node][node]; bool visited[node] = { false };
#define link(a,b,m) f(i,0,m){cin>>a[i]>>b[i]; a[i]--; b[i]--; graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;}

#pragma endregion

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}

//階乗計算
LL factorial(LL n) {
	LL a = 1, ret = 1;
	while (a < n) {
		a++;
		ret *= a;
		//ret %= 1000000007;
	}
	return ret;
}

#pragma endregion 

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

	int a[3], b[3];
	map<LL, LL>m;
	f(i, 0, 3) {
		cin >> a[i] >> b[i];
		m[a[i]]++;
		m[b[i]]++;
	}
	f(i, 0, 3) {
		if (m[a[i]] >= 3 || m[b[i]] >= 3) {
			_N();
			return 0;
		}
	}
	_Y();
	return 0;
}

Measured memory_bytes: 256
from collections import deque
K, N = map(int, input().split())
A = deque(map(int, input().split()))
A.appendleft(K - A[-1] + A[0])
sa_max = A[0]
for i in range(1, N):
    sa = A[i + 1] - A[i]
    if sa_max < sa:
        sa_max = sa
print(A[-1] + A[0] - (sa_max + A[1]))


Measured memory_bytes: 24012
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>

#include <sstream>
#include <string>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;




int main(){
    int n;
    cin >> n;
    if (n%2 == 1) cout << (n/2);
    else cout << (n/2-1);
    rn 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MAX = 100;
const int INF = 1e9;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L

int main() {
	int X, Y, Z;

	cin >> X >> Y >> Z;
	swap(X, Y);
	swap(X, Z);

	cout << X << " " << Y << " " << Z << endl;
}

Measured memory_bytes: 3604
#include<stdio.h>
int main(void)
{
    int A,B,C,D;
    int L,R;
  
    scanf("%d%d%d%d",&A,&B,&C,&D);
    L=A+B;
    R=C+D;
  
    if(L==R) printf("Balanced\n");
    else if(L>R) printf("Left\n");
    else if(L<R) printf("Right\n");
  
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll m = 1000000007;

ll fn(ll n, ll a, ll mod = m) {
    ll res = 1, x = a%mod;
    ll ans = 0;
    while(n) {
        if(n&1) ans = (x*ans + res)%mod;
        res = ((res*x)%mod + res%mod)%mod;
        x = (x*x)%mod;
        n = n/2;
    }
    return ans;
}

ll mul(ll a, ll b, ll mod = m) {
    ll r = 0;
    a %= mod;
    while (b) {
        if (b & 1) r = (r+a)%mod;
        a = (a+a)%mod;
        b = b/2;
    }
    return r;
}

ll power(ll x, ll n, ll mod = m) {
    ll res = 1;
    x %= mod;
    while (n)  
    {  
        if (n & 1)  res = (res*x)%mod;  
        n = n/2; 
        x = (x*x)%mod;  
    }  
    return res;
}

ll power2(ll x, ll n) {
    ll res = 1;
    while (n)  
    {  
        if (n & 1)  res = (res*x);  
        n = n/2; 
        x = (x*x);  
    }  
    return res;
}

bool is_prime(long long x) {
    if(x == 1 || x == 0) return false;
    for(int i=2; i*i <= x; i++) {
        if(x%i == 0) return false;
    }
    return true;
}

ll compgcd(ll n, vector<ll> primes) 
{ 
    ll res = n; 
    for (ll i=0; primes[i]*primes[i] <= n; i++) {
        if (n % primes[i]== 0) { 
            res -= (res / primes[i]); 
            while (n%primes[i]== 0) {
               n/=primes[i]; 
            }
        } 
    } 
    if (n > 1) {
       res -= (res / n); 
    }
    return res; 
} 

vector<bool> sieve(vector<bool> &prime, vector<ll> &primes, ll lim) {
    for(int i = 2; i*i <= lim; i++) {
        if(prime[i]) {
            for(int j = 2; j*i <= lim; j++) {
                prime[j*i] = false;
            }
        }
    }
    for(int i = 2; i <= lim; i++) {
        if(prime[i]) {
            primes.push_back(i);
        }
    }
    return prime;
}

void sieveGCD(ll lim, vector<ll> &tab, vector<ll> primes) {
    for(int  i = 1; i <= lim; i++) {
        tab[i] = i;
    }
    for(int i = 0; i<primes.size() && primes[i] <= lim; i++) {
        tab[primes[i]] = primes[i]-1;
        for(int j = 2; primes[i]*j <= lim; j++) {
            tab[primes[i]*j] = (tab[primes[i]*j]/primes[i])*(primes[i]-1);
        }
    }
}

int main() 
{ 
    ios_base::sync_with_stdio(false);
    ll k, sum = 0;
    cin >> k;
    for(int i = 1; i <= k; i++) {
        for(int j = 1; j <= k; j++) {
            for(int l = 1; l <= k; l++) {
                ll tmp = __gcd(i,j);
                sum += __gcd((ll)l, tmp);
            }
        }
    }
    cout << sum << "\n";
    return 0;
} 

Measured memory_bytes: 3648
function Main(input) {
	splited = input.split("\n");
  	var numbers = splited[1].split(" ");
	var count = 0;

  	while (numbers.every(number => (number%2) === 0)){
          numbers = numbers.map(n => n/2);
  		  //console.log(numbers);
      	  count++;
			}
    console.log(count);
  	
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
  int n; cin >>n;
  ll sum = 0;
  map<int, int> mp;
  rep(i,n) {
    int a; cin >>a;
    sum += a;
    mp[a]++;
  }
  int q; cin >>q;
  rep(i,q){
    int b,c;
    cin >>b >>c;
    if(mp[b]!=0){
      sum += (c-b)*mp[b];
      mp[c] += mp[b];
      mp[b] = 0;
    }
    cout << sum << endl;
  }
  return 0; 
}

Measured memory_bytes: 7896