akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, M = map(int, input().split())
uf = UnionFind(N)
plist = list(map(int, input().split()))
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x-1, y-1)
ans = 0
for i in range(N):
    if uf.same(i, plist[i]-1):
        ans += 1
print(ans)

Measured memory_bytes: 15220
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template<Int MOD = 1000000007>
struct Mod{
  Int prev=0;
  vector<Int> fact,inv,finv;
  Mod(){}
  Mod(Int n){init(n);}
  
  Int pow(Int x,Int n){
    Int res=1;
    while(n){
      if(n&1) (res*=x)%=MOD;
      (x*=x)%=MOD;
      n>>=1;
    }
    return res;
  }
  
  Int inverse(Int a){
    return pow(a,MOD-2);
  }
  
  void init(Int n){
    if(prev>=n) return;
    prev=n;
    fact=inv=finv=vector<Int>(n);
    
    fact[0]=1;
    for(Int i=1;i<n;i++)
      fact[i]=(fact[i-1]*i)%MOD;
    
    inv[1]=1;
    for(Int i=2;i<n;i++)
      inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    
    finv[0]=1;
    for(Int i=1;i<n;i++)
      finv[i]=finv[i-1]*inv[i]%MOD;
  }
  
  Int comb(Int n,Int k){
    Int res=1;
    for(Int i=0;i<k;i++){
      res*=(n-i)%MOD;
      res%=MOD;
      res*=inverse(i+1);
      res%=MOD;
    }
    return res;
  }
  
  //only for prime MOD
  Int C(Int n,Int k){
    if(k<0||k>n) return 0;
    return fact[n]*finv[k]%MOD*finv[n-k]%MOD;
  }

  Int H(Int n,Int k){
    return C(n+k-1,n);
  }
  
  Int montmort(Int n){
    Int res=0,rinv=1;
    for(Int k=2;k<=n;k++){
      (rinv*=inverse(k))%=MOD;
      if(k%2) (res+=MOD-rinv)%=MOD;
      else (res+=rinv)%=MOD;
    }
    for(Int i=1;i<=n;i++)
      (res*=i)%=MOD;
    return res;
  }
  
  // calculate P(t) from given points in [0,N]
  Int LagrangePolynomial(vector<Int> &y,Int t){
    Int n=y.size()-1;
    init(n+1);
    Int num=1;
    for(Int i=0;i<=n;i++)
      num=num*((t-i)%MOD)%MOD;
    Int res=0;
    for(Int i=0;i<=n;i++){
      Int tmp=(y[i]*num%MOD)*inverse((t-i)%MOD)%MOD;
      tmp=tmp*finv[i]%MOD;
      tmp=tmp*finv[n-i]%MOD;
      if((n-i)&1) tmp=MOD-tmp;
      res=(res+tmp)%MOD;
    }
    return res;
  }
};

//INSERT ABOVE HERE
signed main(){
  const Int MOD = 1e9+7;
  Mod<MOD> mod(2e5);
  Int n,k;
  cin>>n>>k;
  cout<<mod.H(n,k)<<endl;
  return 0;
}



Measured memory_bytes: 7476
#include <iostream>
#include <math.h> 
#include <vector>
#include <algorithm>
#include <iomanip>      // std::setprecision
#include <map>

using namespace std;

int main()
{

	double N, D, A, X, H, bomb_counter = 0;
	std::cin >> N >> D >> A;
	std::map<double, std::pair<double, double>> monster; //<x, <health, -bomb_effect>>
	std::vector<std::pair<double, double>> bomb_range;
	for (int i = 0; i < N; ++i)
	{
		std::cin >> X >> H;
		monster[X] = std::make_pair(H, 0);
	}
	double bomb_effect = 0;
	auto fast_runner = monster.begin();
	for (auto it = monster.begin(); it != monster.end(); ++it)
	{
		double monster_x = it->first;
		double monster_health = it->second.first;
		double bombs_to_kill = ceil(monster_health / A);
		double negative_bomb_effect = it->second.second;
		bomb_effect -= negative_bomb_effect;
		if (bombs_to_kill > bomb_effect)
		{
			//drop bombs
			double bombs_to_drop = (bombs_to_kill - bomb_effect);
			bomb_counter += bombs_to_drop;
			bomb_effect += bombs_to_drop;
			for (; fast_runner != monster.end(); ++fast_runner)
			{
				double fast_monster_x = fast_runner->first;
				if (fast_monster_x > (monster_x + (D * 2)))
				{
					fast_runner->second.second += bombs_to_drop; // add negative bomb effect
					break;
				}
			}
		}
	}
	std::cout << fixed << std::setprecision(0) << bomb_counter << std::endl;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFLL = LLONG_MAX / 3;
const double eps = (1e-9);

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

  int n;
  ll  m;
  cin >> n >> m;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(ALL(a));
  vector<pair<ll, int>> cb;
  rep(i, m) {
    ll c; int b;
    cin >> b >> c;
    cb.emplace_back(c, b);
  }
  sort(ALL(cb));

  ll ans = 0;
  int idx = 0;
  for (auto itr = cb.rbegin(); itr != cb.rend(); itr++) {
    for (int i = 0; i < itr->second; i++) {
      if (idx >= a.size() || a[idx] >= itr->first) {
        break;
      }
      a[idx] = itr->first;
      idx++;
    }
    if (idx >= a.size()) break;
  }

  cout << SUM(a) << endl;

  return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<long long> B(N - 1);

    for(int i = 0; i < N - 1; ++i) {
        cin >> B[i];
    }

    long long res = B[0] + B.back();
    for(int i = 0; i + 1 < B.size(); ++i) {
        res += min(B[i], B[i + 1]);
    }
    cout << res << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int left(int x) {
        int i = 1;
        while(i <= x) {
            i <<= 1;
        }
        return i - x;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 11];
        int[] used = new int[n + 11];
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            used[i] = 0;
            if (cnt.containsKey(a[i])) {
                cnt.put(a[i], cnt.get(a[i]) + 1);
            } else {
                cnt.put(a[i], 1);
            }
        }
        Arrays.sort(a, 0, n);
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = a[i];
            if (cnt.get(x) == 0) {
                continue;
            }
            cnt.put(x, cnt.get(x) - 1);
            int match = left(x);
            // System.out.println(x);
            // System.out.println(match);
            if (cnt.containsKey(match) && cnt.get(match) > 0) {
                ans += 1;
                cnt.put(match, cnt.get(match) - 1);
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 103732
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

x = INT()
ans500 = x // 500
x -= ans500 * 500
ans5 = x // 5
print(ans500 * 1000 + ans5 * 5)

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

#define ll   long long int
#define rep(i,n)    for(int i=0;i<(int)n;i++)
#define show(s)     cout<<s<<endl

int main() {

    int A,B,T;
    cin >> A >> B >> T;

    int ans = T / A * B;

    show(ans);

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int array[] = new int[Integer.parseInt(br.readLine())];
		for(int i=0; i<array.length; i++) {
			array[i] = Integer.parseInt(br.readLine());
		}

		int prime = 0;
		boolean p;
		for(int n : array) {
			p = true;
			for(int i=2; i<=Math.sqrt(n); i++) {
				if(n%i==0) {
					p = false;
					break;
				}
			}
			if(p) prime++;
		}
		System.out.println(prime);
	}

}



Measured memory_bytes: 30360
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INF 10000000000
#define mod 1000000007
typedef long long int ll;
ll u(const void *a, const void *b){return *(ll*)a-*(ll*)b;}
ll d(const void *a, const void *b){return *(ll*)b-*(ll*)a;}
ll min(ll a,ll b){
  if(a>b)return b;
  return a;
}
ll max(ll a,ll b){
  if(a>b)return a;
  return b;
}
ll gcd(ll a,ll b){
  if(!b)return a;
  return gcd(b,a%b);
}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int kt(ll a){
  int sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
int ks(ll a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
int main(void){
  int ans=0,n,sum=0;
  scanf("%d",&n);
  int a[n];
  FOR(n){
    scanf("%d",&a[i]);
    sum+=a[i];
  }
  FOR(n){
    ans+=(sum-=a[i])*a[i];
  }
  PRN(ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

struct ST {
  int y, x;
  int d;
};

int vy[4] = {-1,1,0,0};
int vx[4] = {0,0,-1,1};

int solve(int sy, int sx, const vector<string>& field){
  int H = field.size();
  int W = field[0].size();
  
  vector<vector<int>> dist(H, vector<int>(W, -1));

  queue<ST> que;
  que.push((ST){sy,sx,0});
  while(!que.empty()){
    ST p = que.front(); que.pop();

    int y = p.y;
    int x = p.x;
    int d = p.d;

    if(dist[y][x] != -1) continue;
    dist[y][x] = d; 

    rep(k,4){
      int ny = y + vy[k];
      int nx = x + vx[k];
      if(0<=ny&&ny<H&&0<=nx&&nx<W && field[ny][nx] == '.'){
        if(dist[ny][nx] == -1){
          que.push((ST){ny,nx,d+1});
        }
      }
    }
  }

  int ret = 0;
  rep(i,H){
    rep(j,W){
      if(dist[i][j] != -1){
        ret = max(ret, dist[i][j]);
      }
    }
  }
  return ret;
}


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

  vector<string> field;
  rep(i,H){
    string s;
    cin >> s;
    field.push_back(s);
  }

  int ret = 0;
  rep(i,H){
    rep(j,W){
      if(field[i][j] == '.'){
        ret = max(ret, solve(i,j,field));
      }
    }
  }

  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int T,H,S,t,ans1,ans2,ans3;
	while(1){
		scanf("%d %d %d",&T,&H,&S);
		if(T==-1 && H==-1 && S==-1){
		    break;
		}
		t=7200-(3600*T+60*H+S);
		ans1=t/3600; ans2=(t%3600)/60; ans3=t%60;
		printf("%02d:%02d:%02d\n",ans1,ans2,ans3);
		t=t*3;
		ans1=t/3600; ans2=(t%3600)/60; ans3=t%60;
		printf("%02d:%02d:%02d\n",ans1,ans2,ans3);
	}
	return 0;
}


Measured memory_bytes: 1988
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans = 0
if N%2==0:
  for i in range(N//2):
    ans += A[N//2 + i] - A[i]
  for i in range(N//2 - 1):
    ans += A[N//2 + i + 1] - A[i]
else:
  for i in range(N//2):
    ans += A[N//2 + i + 1] - A[i]
  for i in range(N//2 - 1):
    ans += A[N//2 + i + 2] - A[i]
  ans += max(A[N//2 + 1] - A[N//2], A[N//2] - A[N//2 - 1])
print(ans)


Measured memory_bytes: 7504
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // ll は long long　と同じとする。(int64_t)
int main() {
    int a , b;
    cin >> a >> b;
    if(0 < a && a <= b){
        cout << "Positive" << endl;
    }
    if(a <= b && b < 0){
        if((b - a + 1) % 2 == 0){
            cout << "Positive" << endl;
        }
        else{
            cout << "Negative" << endl;
        }
    }
    if(a <= 0 && 0 <= b){
        cout << "Zero" << endl;
    }
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    A, B, C, D = map(int, input().split())
    if A + B == C + D:
        print('Balanced')
    elif A + B < C + D:
        print('Right')
    else:
        print('Left')


if __name__ == "__main__":
    main()


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

int main(){
    ll a,b;
    cin>>a>>b;
    vector<char> s(a+b+1);
    for(ll i=0;i<a+b+1;++i){
        cin>>s[i];
    }
    for(ll i=0;i<a;++i){
        if(s[i]=='-'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    if(s[a] != '-'){
        cout<<"No"<<endl;
        return 0;
    }
    for(ll i=a+1;i<a+b+1;++i){
        if(s[i]=='-'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 384
N = int(input())

P = [list(map(int,input().split())) for _ in range(N)]

count = [0]
for p in P:
    if p[0] == p[1]:
        count.append(count[-1]+1)
    else:
        count.append(0)

if max(count) >= 3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9176
#include<iostream>

int N,M,C,B[20],A,res,t;

int main(){

    std::cin>>N>>M>>C;

    for(int i=0;i<M;i++)
    std::cin>>B[i];

    for(int i=0;i<N;i++){
        t=0;
    for(int j=0;j<M;j++){
    std::cin>>A;
    t+=A*B[j];
    }
    if(t+C>0)res++;
    }

    std::cout<<res<<std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
    string s;
    cin >> s;
    int l=s.length();
    int cnt=0;
    for(int i=0;i<l;++i) {
        if(s[i]!=s[l-i-1]) ++cnt;
    }
    cout << cnt/2 << endl;
}





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

int main() {
  int k, a, b;
  string  ans= "NG";
  cin >> k >> a >> b;

  for (int i = a;  i <= b; i++) {
    if (i % k == 0) {
      ans = "OK";
      break;
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;

void solve()
{
	int a,b,c;
	cin>>a>>b>>c;
	int k;
	cin>>k;
	int cnt=0;
	while(a>=b){
		++cnt;
		b*=2;
	}
	while(b>=c){
		++cnt;
		c*=2;
	}
	if(cnt<=k)cout<<"Yes";
	else cout<<"No";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


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

string s,t,ans;
int main()
{
    cin>>s>>t;
    if(s.size()<t.size())
	{
        cout<<"UNRESTORABLE";
        return 0;
    }
    for(int i=0;i<=s.size()-t.size();i++)
	{
        int k=i;
        string s1=s;
        int j=0;
        while(j<t.size())
		{
            if(s1[k]=='?')
                s1[k]=t[j];
            else if(s[k]!=t[j])
                break;
            k++;
            j++;
        }
        if(j==t.size())
		{
            for(int p=0;p<s1.size();p++)
                if(s1[p]=='?')
                    s1[p]='a';
            if(ans=="")
                ans=s1;
            else
				ans=min(ans,s1);
        }
    }
    if(ans=="")
        cout<<"UNRESTORABLE";
    else
		cout<<ans;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
public class Main{  
    public static void main(String[] args) throws IOException{
        BufferedReader bf = 
            new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int A = Integer.parseInt(str[0]),
            B = Integer.parseInt(str[1]),
            C = Integer.parseInt(str[2]);
        boolean b = A < C && C < B || B < C && C < A;
        if(b){
            System.out.println("Yes");
        } else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 22612
#include"bits/stdc++.h"
using namespace std;
const int N=2e5+3;
int a[N],n,ans[N];
vector<int> ad[N];
multiset<int> s;
void dfs(int node,int par=-1)
{
	s.insert(a[node]);
	int del=-1;
	auto it=s.lower_bound(a[node]);
	if(++it!=s.end())
	{
		del=*it,s.erase(it);
	}
	ans[node]=s.size();
	for(auto u:ad[node])
	{
		if(u==par)continue;
		dfs(u,node);
	}
	if(del!=-1)s.insert(del);
	s.erase(s.find(a[node]));
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
	#endif
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	int u,v;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;u--;v--;
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	dfs(0);
	for(int i=0;i<n;i++)cout<<ans[i]<<"\n";
	

}


Measured memory_bytes: 30324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll a;
    double b;
    cin >> a >> b;
    ll b2 = b * 100 + 0.5;
    ll ans = a * b2 / 100;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3724
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    vector<int>vec(N);
    for (int i=0; i<N; i++) {
        cin >> vec.at(i);
    }

    sort(vec.begin(), vec.end());
    int sum = 0;
    for (int i=0; i<K; i++) {
        sum += vec[i];
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char* argv[]) {
  string s;
  cin >> s;

  long long K;
  cin >> K;

  s += s + s;

  long long base = 0;
  bool changed[s.size()];
  changed[0] = false;
  for (int i = 1; i < s.size() / 3; ++i) {
    if (s[i] == s[i - 1] && !changed[i - 1]) {
      ++base;
      changed[i] = true;
    } else
      changed[i] = false;
  }

  long long sec = 0;
  for (int i = s.size() / 3; i <  2 * s.size() / 3; ++i) {
    if (s[i] == s[i - 1] && !changed[i - 1]) {
      ++sec;
      changed[i] = true;
    } else
      changed[i] = false;
  }

  long long thi = 0;
  for (int i = 2 * s.size() / 3; i <  s.size(); ++i) {
    if (s[i] == s[i - 1] && !changed[i - 1]) {
      ++thi;
      changed[i] = true;
    } else
      changed[i] = false;
  }

  long long ret = base;
  if (K - 1 > 0) {
    if ((K - 1) % 2 == 0)
      ret += (sec + thi) * (K - 1) / 2;
    else
      ret += (sec + thi) * (K - 2) / 2 + sec;
  }

  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int nLen = String.valueOf(n).length();
    
    long count = 0;
    for (int i=1; i<=n; i++) {
      int afirst = Integer.parseInt(String.valueOf(i).substring(0, 1));
      int alast = i%10;
      if (alast==0) {
        continue;
      }
      
      
      for (int j=1; j<=nLen; j++) {
        int mid = 0;
        if (j==1) {
          if (afirst==alast) {
            count++;
          }
        }
        else if (j==2) {
          if (alast*10+afirst<=n) {
            count++;
          }
        }
        else if (j==3) {
          mid = 90;
        }
        else if (j==4) {
          mid = 990;
        }
        else if (j==5) {
          mid = 9990;
        }
        else if (j==6) {
          mid = 99990;
        }
        
        if (j>2) {
          int bmax = alast*(int)Math.pow(10,j-1) + mid + afirst;
          if (bmax<=n) {
            count += Math.pow(10, j-2);
          }
          else {
            int b = alast*(int)Math.pow(10, j-1) + afirst;
            while (b<=n) {
              count ++;
              b += 10;
            }
          }
        }
      }
    }
    System.out.println(count);
    
  }
}

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

using namespace std;

#define F first
#define S second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define endl '\n'

typedef long long int ll;
typedef pair<ll,ll> ii;
typedef pair<string,ll> si;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<si> vsi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vsi> vvsi;

const int INF = 2000000000;
const ll INFLL = 1LL * INF * INF;
ll mod = (int)pow(10,9)+7;
// ll mulmod(ll a, ll b, ll mod) 
// { 
//     ll res = 0; // Initialize result 
//     a = a % mod; 
//     while (b > 0) 
//     { 
//         // If b is odd, add 'a' to result 
//         if (b % 2 == 1) 
//             res = (res + a) % mod; 
  
//         // Multiply 'a' with 2 
//         a = (a * 2) % mod; 
  
//         // Divide b by 2 
//         b /= 2; 
//     } 
  
//     // Return result 
//     return res % mod; 
// } 
// bool sieve[100005];

// void sieveoferat()
// {
// 	for(ll p = 2; p*p<100005 ; p++)
// 	{
// 		if(sieve[p])
// 		{
// 			for(int j = p*p; j<100005; j+=p)
// 				sieve[j] = false;
// 		}
// 	}
// }

// void dp(sp_1, sp_2.....)
// {
// 	if()//exit statement
// 	if()//using the memoization 
// 	ll ans = //default/dummy answer
// 	//recursions
// 			//max/min
// 	return memo[][].. = ans;

// }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 	cout.tie(NULL);
 	//memset(memo, -1, sizeof memo);
 	// memset(sieve, true, sizeof sieve);
 	// sieveoferat();
 	int n; cin>>n;
 	vii a(n);
 	for(int i = 0; i < n ;i++)
 		cin>>a[i].S>>a[i].F;
 	sort(a.begin(), a.end());
 	ll curr = 0;
 	bool cant = false;
 	for(int i =0 ; i < n ;i++)
 	{
 		curr +=a[i].S;
 		if(curr>a[i].F)
 		{
 			cant = true;
 			break;
 		}

 	}
 	if(!cant)
 		cout<<"Yes\n";
 	else
 		cout<<"No\n";
 	
 	
	return 0;
}

Measured memory_bytes: 3328
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
# define MSG(x) std::cout << #x << " : " << x << "\n";
using namespace std;
using lint = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    string S; cin >> S;

    int times = SZ(S);
    int win = 0;
    rep (i, times)
    {
        if (S[i] == 'o')
        {
            win++;
        }
    }

    if (win + 15 - times >= 8)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();

        int[] ans = new int[3];

        ans[0] = a*x + b*y;
        if(x >= y){
            ans[1] = c*y*2 + (x-y) * a;
            ans[2] = c*x*2;
        }else{
            ans[1] = c*x*2 + (y-x) * b;
            ans[2] = c*y*2;
        }

        Arrays.sort(ans);

        System.out.println(ans[0]);
    }
}

Measured memory_bytes: 23636
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>	// upper_bound(A, A+N, num), lower_bound(A, A+N, num)
#include <functional>
#include <string>
#include <sstream>
#include <complex>
#include <vector>		// V[i],  push_back(x), pop_back(), insert(index, x), erase(index), sort(v.begin(), v.end(), greater<int>())
#include <list>			// push_front(x), push_back(x), pop_front(), pop_back(), insert(index, x)
#include <queue>		// push(x), front(), pop()
#include <deque>
#include <stack>		// push(x), top(), pop()
#include <map>			// M[key],  insert(key, val), erase(key), find(key), 
#include <set>			// insert(key), erase(key), find(key)

using namespace std;
typedef long long ll;
// typedef pair<int, int> P;

#define PI 3.141592653589793)
#define MOD 1000000007
#define REP(i, n) for(int i = 0; i < n; i++)

int N;

void solve() {
	cin >> N;
	ll ans = 0LL;
	ll tmp = 0LL;
	for (int i = 0; i < N; i++) {
		ll a; cin >> a;
		if (a == 0) {
			tmp = 0LL;
			continue;
		}
		a += tmp;
		if (a % 2) {
			ans += a / 2;
			tmp = 1LL;
		}
		else {
			ans += a / 2;
			tmp = 0LL;
		}
	}
	cout << ans << endl;
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 256
*n[]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};main(y,m,d,i){for(;scanf("%d%d",&m,&d)*m;printf("%s\n",n[(y+y/4-y/100+y/400+(13*m+8)/5+d)%7]))y=m<3?m+=12,2003:2004;}

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;

const ll MOD=1000000007ll;
const int MAX=5100000;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    for(int i=0;i<a;i++){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    for(int i=0;i<a;i++){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

ll fact[MAX], fact_inv[MAX];

ll power(ll a, ll b){
	ll res=1;
	while(b>0){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

// nCr
ll comb(ll n, ll r){
	ll t=1000000;
	fact[0]=1;
	    for(int i=0;i<t;i++){ fact[i+1]=fact[i]*(i+1)%MOD;}
	fact_inv[t]=power(fact[t], MOD-2);
	for(int i=0;i<t;i++){ fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;}
	return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}
  
int main()
{
	cin.tie(0);	ios::sync_with_stdio(false);

  int N,i; cin >> N;
  vector <ll>A(N,0);
  ll ans = 0;
  rep(i,N){cin >> A[i];}
  sort(ALL(A),std::greater<ll>());
  ans+=A[0];
  int idx = 1;
  for(i=1;i<N-1;i++){
      ans+=A[idx];
      if(i%2==0){idx++;}
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 4728
#coding:utf-8

            
def main():
    k, n = map(int, input().split())
    li = list(map(int, input().split()))
    maxv = li[0]
    for i in range(1, n):
        sub = abs(li[i] - li[i-1])
        maxv = max(maxv, sub)
    maxv = max(maxv, k + li[0] - li[n-1])
    print(k - maxv)
    
        
        
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 26444
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = np.array(lr())
A.sort()

def shake_cnt(x):
    Y = np.searchsorted(A, x-A)
    return N*N - Y.sum()

right = 10 ** 6
left = 0
while right > left + 1:
    mid = (right+left) // 2
    if shake_cnt(mid) >= M:
        left = mid
    else:
        right = mid

Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()
Y = np.searchsorted(A, right-A)
happy = (Acum[-1]-Acum[Y]).sum() + (A * (N-Y)).sum()
happy += left * (M-shake_cnt(right))
print(happy)
# 32

Measured memory_bytes: 23380
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

bool cmp(int x,int y) {
    return x>y;
}

int a[101];

int main() {
    int n;
    cin>>n;
    int ans1=0,ans2=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) {
        if(i%2!=0) ans1+=a[i];
        if(i%2==0) ans2+=a[i];
    }
    cout<<ans1-ans2<<endl;
    return 0;
}

Measured memory_bytes: 256
N,Y=map(int,input().split())

for a in range(N+1):
  for b in range(N-a+1):
    c = N - a - b
    if (10000*a + 5000*b + 1000*c) == Y:
      print(a,b,c,sep=' ')
      exit()
    
print(-1,-1,-1,sep=' ') 


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N;
  string S;
  cin>>N>>S;
  vector<int> A(26);
  for(char c:S)
    A[c-'a']++;
  int ans=1;
  for(int i:A)
    ans=ans*(i+1)%1000000007;
  cout<<ans-1<<endl;
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using ll = long long;
using P = pair<int,int>;
static const int INF = 1000000000;
static const ll MOD = 1000000007;

int main(){
	int x, n;
	cin >> x >> n;
	vector<bool> p(102, false);
	rep(i, n){
		int tmp;
		cin >> tmp;
		p[tmp] = true;
	}
	
	int ans = INF;
	int dif = INF;
	for(int i = 0; i <= 101; ++i){
		if(!p[i]){
			if(dif > abs(i - x)){
				ans = i;
				dif = abs(i - x);
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3596
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    d = defaultdict(int)
    for a in ipt().split():
        d[int(a)] += 1

    ans = 0
    for dk,dv in d.items():
        if dk > dv:
            ans += dv
        elif dk < dv:
            ans += (dv-dk)
    print(ans)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 62628
#include <iostream>
#include <string>
#include <vector>

#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)

using lint = long int;
using llint = long long int;
using namespace std;

int main() {
    fastIO;
    int n;
    string s, t;

    cin >> n >> s >> t;

    rep(i, n) cout << s.at(i) << t.at(i);
    cout << endl;
}



Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
signed  main(){
  int a,b,c,d,e,f,z=0;
  cin>>a>>b>>c>>d>>e>>f;
  if(b-a>f){
    z++;
  }if(c-a>f){
    z++;
  }if(d-a>f){
    z++;
  }if(e-a>f){
    z++;
  }if(c-b>f){
    z++;
  }if(d-b>f){
    z++;
  }if(e-b>f){
    z++;
  }if(d-c>f){
    z++;
  }if(e-c>f){
    z++;
  }if(e-d>f){
    z++;
  }
  if(z==0){
    cout<<"Yay!\n";
  }else{
    cout<<":(\n";
  }
}


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

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

const int INF = 100000000;
const double PI=3.14159265358979323846;


int main () {
    int N;
    cin >> N;
    int A[N];
    vector<int> ans(N+1,0);
    rep(i,1,N+1) {
        cin >> A[i];
    }

    int M=0;
    for(int i=N; i>0; i--) {
        int tmp = i;
        int now = 0;
        int b = i;
        rep(j,1,N+10) {
            now+=ans[tmp];
            tmp+=b;
            if (tmp>N) {
                break;
            }
        }
        if(now%2==A[i]) {
            continue;
        }
        else {
            ans[i]++;
            M++;
        }
    }
    cout << M << endl;

    if (M>0) {

        rep(i,1,N+1) {
            if(ans[i]!=0) {
                cout << i << " ";
            }
        }
        cout << endl;
    }

}

Measured memory_bytes: 2432
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int num[500005];
int main(){
  string s;
  cin >> s;

  for(int i=0; i<s.size(); i++){
    if(s[i] == '<'){
      num[i+1] = num[i]+1;
    }
  }

  for(int i=s.size()-1; i>=0; i--){
    if(s[i] == '>'){
      num[i] = max(num[i], num[i+1]+1);
    }
  }

  long long ans = 0;
  for(int i=0; i<=s.size(); i++){
    ans += num[i];
  }

  cout << ans << endl;

  return 0;
}

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

using namespace std;

int main() {
	int N, M, X;
	int ans1 = 0;
	int ans2 = 0;
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A;
		cin >> A;
		if (A < X) {
			ans1++;
		}
		else if (A > X){
			ans2++;
		}
	}

	cout << min(ans1, ans2);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define rrep(i,a,b) for(int i = a;i >= b;i--)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << #x << ": " << x << endl;
typedef long long ll;
using namespace std;

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

   int a,b;
   cin >> a >> b;

   if(a != b){
      cout << max(a,b) + max(a,b) - 1 << endl;
   }else{
      cout << a + b << endl;
   }

   return 0;
}

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

int main() {
  lint N;
  cin >> N;

  vector<lint> A(N);
  for(auto& elem : A) cin >> elem;
  sort(A.rbegin(), A.rend());

  // 最大の要素は1回・その他は2回選べる
  vector<lint> B;
  for(lint i=0; i<N; i++) {
    B.push_back(A[i]);
    B.push_back(A[i]);
  }
  B.erase(B.begin());

  lint ans = 0;
  for(lint i=0; i<N-1; i++) {
    ans += B[i];
  }

  cout << ans << endl;
}

Measured memory_bytes: 8948
//	@Author : Gaurang_Kothiya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#include <bitset>
#include <cstdint>
#include <initializer_list>
 
using namespace std;
using namespace __gnu_pbds;  

#define data_set(type) tree<type,null_type,less<type>,rb_tree_tag,tree_order_statistics_node_update>
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long int
#define ld long double
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fe(x,v)   for(auto &x :v)
#define nf(i,x,n) for(int i=n;i>=x;i--)
#define all(a)   a.begin(),a.end()
#define rall(a)  a.rbegin(),a.rend()
#define ook(num) order_of_key(num)
#define fbo(num) find_by_order(num)
#define gcd(a,b) __gcd(a,b)
#define bits(n) __builtin_popcountll(n)
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define RE rend()
#define RB rbegin()
#define B begin()
#define E end()
#define acc(v, x) accumulate(all(v), x)
#define p(a,b) pair<a,b>
#define F first
#define S second
#define sz size()
#define v(x) vector<x>
#define m(a,b) map<a,b>
#define u_m(a,b) unordered_map<a,b>
#define mm(a,b) multimap<a,b>
#define s(a) set<a>
#define us(a) unordered_set<a>
#define ms(a) multiset<a>
#define maxy __LONG_LONG_MAX__
#define miny INT_MIN
#define PI 3.14159265358979323846

const int inf= 1e9 +1;
const int inf64= 1e18 -1;
const int MOD= 1e9 +7;
const int MOD2= 998244353;



void Solve()
{
	string s,t;
	cin>>s>>t;
	int n=s.length(),m=t.length();
	int ans=n;
	f(i,0,n-m)
	{
		int i1=i;
		int res=0;
		f(j,0,m-1)
		{
			if(s[i1]!=t[j]) res++;
			i1++;	
		}
		ans=min(ans,res);
	}
	cout<<ans;
}
 
signed main() 
{
	//speed		

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);	

	int q=1;
	//cin>>q;
	
	while(q--)
	Solve();
		
	return 0;
} 

Measured memory_bytes: 3628
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}
ll X[100000];
ll A[100000];

int main() {
   int N;
   cin >> N;
   ll Asum = 0;
   for (int i = 0; i < N; i++) {
      cin >> A[i];
      Asum += A[i];
   }
   memset(X, 0, sizeof(X));
   X[0] = 0;
   ll sum = 0;
   for (int i = 2; i < N; i++) {
      if (i % 2 != 0) continue;
      X[i] = A[i - 1] - A[i - 2] + X[i - 2];
      sum += X[i];
   }
   X[1] = A[0] - A[N - 1] + X[N - 1];
   sum += X[1];
   for (int i = 3; i < N; i++) {
      if (i % 2 == 0) continue;
      X[i] = A[i - 1] - A[i - 2] + X[i - 2];
      sum += X[i];
   }
   ll x = (Asum / 2 - sum) / N;

   for (int i = 0; i < N; i++) {
      cout << (x + X[i]) * 2 << endl;
   }
   return 0;
}


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

typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=100005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string S, T; cin>>S>>T;
	FOR(i,1,255){
		string Sprime = S + (char) i;
		if (Sprime==T){
			cout<<"Yes";
			exit(0);
		}
	}
	cout << "No";
}


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

int main(){
    int n, m=0, cnt=0;
    cin >> n;

    vector<int>h(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
        if(h[i]>=m) cnt++;
        m = max(h[i], m);
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
using namespace std;
string OPTS[4] = {"dream","dreamer","erase","eraser"};

inline bool ends_with(std::string const & value, std::string const & ending)
{
        if (ending.size() > value.size())
                return false;
        else
                return std::equal(ending.rbegin(), ending.rend(), value.rbegin());
}

int find_match(string const &str){
        for(int i = 0;i < 4;i++){
                if(ends_with(str,OPTS[i])){
                        return i;
                }
        }
        return -1;
}

bool solve(string input){
        string tmp = input;
        while(true){
//              cout << tmp << endl;
                if(tmp.length() == 0)
                        return true;
                int res = find_match(tmp);
//              cout << res << endl;
                if(res < 0)
                        return false;
                else
                        tmp = tmp.substr(0,tmp.length() - OPTS[res].length());
        }
}


int main(){
        string input;
        cin >> input;
        if(solve(input))
                cout << "YES" << endl;
        else
                cout << "NO" << endl;
}


Measured memory_bytes: 512
import java.io.*;
import java.util.*;

public class Main {

	int[][] go = new int[N][];
	boolean[] stop = new boolean[N];
	static final int N = 1_000_000;

	int sz = 0;

	int newNode() {
		go[sz] = new int[] { -1, -1 };
		return sz++;
	}
	
	long getVal(long maxL) {
		if (maxL < 0) {
			throw new AssertionError();
		}
		return Long.lowestOneBit(maxL);
	}

	void submit() {
		int root = newNode();

		int n = nextInt();
		long l = nextLong();

		for (int i = 0; i < n; i++) {
			int v = root;
			String s = nextToken();
			for (char c : s.toCharArray()) {
				int dig = c - '0';
				if (go[v][dig] == -1) {
					go[v][dig] = newNode();
				}
				v = go[v][dig];
			}
			stop[v] = true;
		}

		int[] que = new int[sz];
		int[] depth = new int[sz];
		int qh = 0, qt = 0;

		depth[qt] = 0;
		que[qt++] = root;

		long xor = 0;

		while (qh < qt) {
			int nowD = depth[qh];
			int v = que[qh++];
			
			if (stop[v]) {
				continue;
			}
			for (int i = 0; i < 2; i++) {
				if (go[v][i] == -1) {
					xor ^= getVal(l - nowD);
				} else {
					depth[qt] = nowD + 1;
					que[qt++] = go[v][i];
				}
			}
		}
		
		out.println(xor == 0 ? "Bob" : "Alice");
	}

	int mex(HashSet<Integer> set) {
		int ret = 0;
		while (set.contains(ret)) {
			ret++;
		}
		return ret;
	}

	void preCalc() {

	}

	void stress() {

	}

	void test() {

	}

	Main() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		preCalc();
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	int nextInt() {
		return Integer.parseInt(nextToken());
	}

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}
}


Measured memory_bytes: 33364
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		do {
			String str = sc.nextLine();
			if(str.equals("0") || str.length() > 1000) {
				break;
			}
			long num = 0;
			for(int i=0; i<str.length(); i++) {
				num += Character.getNumericValue(str.charAt(i));
			}
			System.out.println(num);
		}while(sc.hasNextLine());
		sc.close();
	}
}



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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    int N;
    cin >> N;
    vector<int> A(N, -1);
    rep(i, N) cin >> A[i];
    vector<int> M(N + 1, -1);
    for (int i = N - 1; 0 <= i; i--) {
        // dd(A[i], M[i - 1]);
        M[i] = max(M[i + 1], A[i]);
    }
    int ma = -2000000000;
    rep(i, N-1) { ma = max(ma, M[i + 1] - A[i]); }
    cout << ma << endl;
    return 0;
}


Measured memory_bytes: 4344
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;

int seiyaku_check(long i,long Min,long Max){
	if(Min <= i && i <= Max){
		return 1;
	}else{
		exit(1);
		//return 0;
	}
}

int main(){
	
	int n;
	int i,j,k;//counter
	int temp1=0,temp2=0;
	int a[100];//in
	int b[100];//sum
	cin >> n;
	seiyaku_check(n,1,100);
	
	for(i=0;i<n;i++){
		cin >> a[i];
		seiyaku_check(a[i],1,100);
		//cout << " a[i] = " <<  a[i] << endl;
	}
	
	if(i != n)exit(1);
	
	for(k=0;k<100;k++){
		b[k]=0;
		for(j=0;j<n;j++){
			//cout << " k=" << k << " b[k]= " << b[k] << endl;	
			b[k]+=((k+1)-a[j])*((k+1)-a[j]);
		}
		//cout << " k=" << k << " b[k]= " << b[k] << endl;	
	}
	
	for(k=0;k<100;k++){
		if(k == 0){
			temp1 = b[k];
			//cout << " k=" << k << " b[k]= " << b[k] << " temp1 = " << temp1 <<  endl;
		}else{
			if(temp1 > b[k]){
				temp1 = b[k];
			}
			//cout << " k=" << k << " b[k]= " << b[k] << " temp1 = " << temp1 <<  endl;
		}
	}	
	
	cout << temp1 << endl;
	
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <numeric>


int main() {
	int a;

	std::string s;

	std::cin >> a >> s;

	if (a < 3200) {
		std::cout << "red" << std::endl;
	}
	else {
		std::cout << s << std::endl;
	}

	return 0;
}

Measured memory_bytes: 256
a,b=map(int,input().split())
if a<=1 and b<=1:
    print(0)
if a<=1 and 1<b:
    print((b*(b-1))//2)
if 1<a and b<=1:
    print((a*(a-1))//2)
if 1<a and 1<b:
    print(((a*(a-1))//2)+((b*(b-1))//2))

Measured memory_bytes: 3064
#include<stdio.h>

int main()
{
 int N;
 int K;
 long x[100005];
 long dist;
 long mindist=200000005;
 long distp;
 long distm;
 int i;

 scanf("%d %d",&N,&K);
 for(i=0;i<N;i++) scanf("%ld",&x[i]);
 mindist=2*(x[N-1]-x[0]);

 for(i=K-1;i<N;i++)
 {
  if(x[i]<0) dist=-x[i-K+1];
  if(x[i-K+1]>0) dist=x[i];
  if((x[i]>=0)&(x[i-K+1]<=0))
  {
   distp=2*x[i]-x[i-K+1];
   distm=x[i]-2*x[i-K+1];
   if(distp<distm)
   {
    dist=distp;
   }else{
    dist=distm;
   }
  }
  if(mindist>dist) mindist=dist;
 }
 printf("%ld\n",mindist);
 return 0;
}


Measured memory_bytes: 896
from collections import deque

def search_maze(maze, start, goal, size):
    TO_NEXT_CELL = [(1,0), (0,1), (-1,0), (0,-1)]
    h = size[0]
    w = size[1]
    distance = [[float("inf") for _ in range(w)] for _ in range(h)]
    min_step = -1
    queue = deque([start])
    distance[start[0]][start[1]] = 1
    while len(queue) != 0:
        i, j = queue.popleft()
        d = distance[i][j]
        if i == goal[0] and j == goal[1]:
            min_step = d
            break
        for next_cell in TO_NEXT_CELL:
            next = (i + next_cell[0], j + next_cell[1])
            if (0 <= next[0] and next[0] < h and 0 <= next[1] and next[1] < w and distance[next[0]][next[1]] == float('inf')):
                if maze[next[0]][next[1]] == '.':
                    queue.append(next)
                    distance[next[0]][next[1]] = d + 1
    return min_step

if __name__ == '__main__':
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input().strip()))
    white_count = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                white_count += 1
    min_step = search_maze(maze, (0,0), (h-1,w-1), (h,w))
    if min_step == -1:
        print ('-1')
    else:
        ans = white_count - min_step
        print(ans)



Measured memory_bytes: 3436