akhauriyash/Code-Regression huggingface dataset:
# 入力
B, W = map(int, input().split())

# ModInt定義
MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    def __repr__(self):
        return str(self.x)

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    __radd__ = __add__
    __rsub__ = __sub__
    __rmul__ = __mul__
    __rtruediv__ = __truediv__
    __rpow__ = __pow__


p = ModInt(0)
q = ModInt(0)
cp = ModInt(0)
cq = ModInt(0)
for i in range(1, B + W + 1):
    # i番目の解は i-1番目までに白チョコレートが枯渇している確率 +
    # i-1番目までにどちらのチョコレートも枯渇しない確率 / 2
    ans = (1 + q - p) / 2
    # 出力
    print(ans)
    cp = (
        ModInt(0) if i < B else
        ModInt(1) if i == B else
        cp * (i - 1) / (i - B)
    )
    p = (
        ModInt(0) if i < B else
        ModInt(1) / ModInt(2**i) if i == B else
        p + cp / pow(2, i, MOD)
    )
    cq = (
        ModInt(0) if i < W else
        ModInt(1) if i == W else
        cq * (i - 1) / (i - W)
    )
    q = (
        ModInt(0) if i < W else
        ModInt(1) / ModInt(2**i) if i == W else
        q + cq / pow(2, i, MOD)
    )


Measured memory_bytes: 59480
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()

a = ""
for _ in range(H):
	a += input()

A = Counter(a).values()
cnt_1 = 0
cnt_2 = 0
cnt_4 = 0

for x in A:
	if x%4 == 0:
		cnt_4 += 1
	elif x%2 == 0:
		cnt_2 += 1
	else:
		cnt_1 += 1

if H%2 and W%2 and cnt_1 == 1 and cnt_2 <= H//2 + W//2:
	print("Yes")
elif H%2 + W%2 == 0 and cnt_1 + cnt_2 == 0:
	print("Yes")
elif H%2 and cnt_1 == 0 and cnt_2 <= W//2:
	print("Yes")
elif W%2 and cnt_1 == 0 and cnt_2 <= H//2:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 10464
m = int(input())
n = len(str(m))
if n == 1:
  print(m)
elif n == 2:
  print(9)
elif n == 3:
  ans = 9 + m - 99
  print(ans)
elif n == 4:
  ans = 999 - 99 + 9
  print(ans)
elif n == 5:
  ans = m - 9999 + 999 - 99 + 9
  print(ans)
elif n == 6:
  print(90909)


Measured memory_bytes: 3060
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
if s == t[:-1]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 65420
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std ;

int n ;
long long ans ;
long long base = 1 ;

double s(long long x){
    int ret = 0 ; long long y = x ;
    while (x) ret += (x % 10ll), x /= 10ll ;
    return (1.0 * y) / (1.0 * ret) ;
}
int main(){
    cin >> n ;
    while (n --){
        while (1){
            if (s(ans + base) > s(ans + base * 10ll))
                base *= 10ll ; else break ;
        }
        ans += base ;
        printf("%lld\n", ans) ;
    }
}


Measured memory_bytes: 256
def insertion_sort(a, n, g, cnt):
    for i in range(g, n):
        v, j = a[i], i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j = j - g
            cnt += 1
        a[j + g] = v
    return cnt


n = int(input())
a = list(int(input()) for _ in range(n))

m, g, cnt = 0, n // 2 + 1, 0
glist = []

while g:
    m += 1
    glist.append(g)
    cnt = insertion_sort(a, n, g, cnt)
    g //= 2

print(m)
print(*glist)
print(cnt)
print('\n'.join(str(i) for i in a))

Measured memory_bytes: 127848
//Zero-Sum Ranges

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define YN(flag) (flag?"Yes":"No")
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll,ll>;
using graph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    nvarep(n,a);
    vector<int>t(n+1,0);
    rep(i,0,n)t[i+1]=t[i]+a[i];
    sort(range(t));
    map<int,int>m;
    rep(i,0,n+1)m[t[i]]++;
    int ans{};
    for(auto i:m)rep(j,1,i.second)ans+=j;
    cout<<ans<<nnn;
    return 0;
}

Measured memory_bytes: 18608
import math
import itertools


def intersections(T, x1, y1, c1, x2, y2, c2):
    # 2つの円 (x - x_i)**2 + (y - y_i)**2 = (T/c_i)**2 の交点を求める
    left = ((c1 * c2)**2) * ((x1 - x2)**2 + (y1 - y2)**2)
    right = (T**2) * ((c1 + c2)**2)
    # 交点なし
    if left > right:
        return list()
    # 交点1つ
    if left == right:
        return [((c1*x1 + c2*x2) / (c1 + c2), (c1*y1 + c2*y2) / (c1 + c2))]
    # 交点2つ
    r1, r2 = T / c1, T / c2
    p12 = (x2 - x1, y2 - y1)
    coef = (r1**2 + p12[0]**2 + p12[1]**2 - r2**2) / (2 * (p12[0]**2 + p12[1]**2))
    p1h = (coef * p12[0], coef * p12[1])
    coef = (r1**2 - p1h[0]**2 - p1h[1]**2) / (p12[0]**2 + p12[1]**2)
    coef = math.sqrt(max(0, coef))  # 誤差を吸収
    hq1 = (- coef * p12[1], coef * p12[0])
    hq2 = (coef * p12[1], - coef * p12[0])
    return [
        (x1 + p1h[0] + hq1[0], y1 + p1h[1] + hq1[1]),
        (x1 + p1h[0] + hq2[0], y1 + p1h[1] + hq2[1])
    ]


def check(T, K, points):
    N = len(points)
    target_points = [(p[0], p[1]) for p in points]
    for pair in itertools.combinations(range(N), 2):
        p1 = points[pair[0]]
        p2 = points[pair[1]]
        target_points += intersections(T, p1[0], p1[1], p1[2], p2[0], p2[1], p2[2])
    for tp in target_points:
        cnt = 0
        for p in points:
            d2 = (tp[0] - p[0])**2 + (tp[1] - p[1])**2
            if d2 <= (T/p[2])**2 + 10**(-6):  # 誤差を吸収
                cnt += 1
            if cnt >= K:
                return True
    return False


def main():
    eps = 10 ** (-10)
    N, K = list(map(int, input().split()))
    points = [list(map(int, input().split())) for _ in range(N)]
    ng, ok = 0, 3 * (10**5)  # Time
    while ok - ng > eps:
        mid = (ok + ng) / 2
        if check(mid, K, points):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    main()

Measured memory_bytes: 76784
def pr(t):
    for i in range(0,10):
        if t[i] == 0:
            print "-"
        else:
            print "*"*t[i]


while True:
    n = int(raw_input())
    t = {}
    for i in range(0,10):
        t[i] = 0

    if n == 0:
        break
    else:
        for i in range(0,n):
            c = int(raw_input())
            t[c] += 1
#        print t
        pr(t)

Measured memory_bytes: 6560
#include <iostream>
#include <string>
#include <algorithm>
#include <bitset>
#include <vector>

using namespace std;

#define MAXN 2000
#define MAXK 10000

bitset <MAXK+1> d[MAXN+1];
int r[MAXK+1];
string s[MAXN+1];

vector <int> u[MAXN+1];

char ans[MAXK+1];
int a[MAXN+1], b[MAXN+1];
int st[MAXN+1];

bool g[MAXN+1][MAXN+1];

bool cmp(const int &a, const int &b){
    return s[a]<s[b];
}

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

    for(int i=1; i<=n; i++)
        cin >> s[i];

    for(int i=1; i<=n; i++)
        a[i]=i;

    sort(a+1, a+n+1, cmp);

    int q=1;
    b[a[1]]=1;
    for(int i=2; i<=n; i++){
        q+=(s[a[i]]!=s[a[i-1]]);
        b[a[i]]=q;
    }

    int vf=1;
    st[1]=a[1];
    for(int i=2; i<=n; i++){
        int j=0, p=1;
        while((p<=vf)&&(j<(int)s[a[i]].size())&&(s[a[i]][j]==s[st[p]][j])){
            j++;
            while((p<=vf)&&(j==(int)s[st[p]].size()))
                p++;
        }
        st[p]=a[i];
        vf=p;
        for(int j=1; j<p; j++)
            g[a[i]][st[j]]=g[st[j]][a[i]]=1;
    }

    d[n+1][0]=1;
    for(int i=n; i>0; i--)
        d[i]=d[i+1]|(d[i+1]<<s[i].size());

    r[0]=1;
    int t=0;
    for(int i=0; i<k; i++) if(r[i]>0){
        int left=q+1, right=0;
        for(int j=r[i]; j<=n; j++)
            if((k-i-(int)s[j].size()>=0)&&(d[j+1][k-i-(int)s[j].size()]))
                u[b[j]].push_back(j), left=min(left, b[j]), right=max(right, b[j]);

        r[i]=0;

        vf=0;
        for(int j=left; j<=right; j++){
            for(auto x:u[j])
                if((vf==0)||(g[st[vf]][x]))
                    st[++vf]=x;
            u[j].clear();
        }

        int p=0, j=1;
        while((i+p<t)&&(j<=vf)&&(ans[i+p]==s[st[vf]][p])){
            p++;
            while((j<=vf)&&((int)s[st[j]].size()==p)){
                if((r[i+p]==0)||(st[j]+1<r[i+p]))
                    r[i+p]=st[j]+1;
                j++;
            }
        }

        if((j<=vf)&&((i+p==t)||(s[st[vf]][p]<ans[i+p]))){
            while(j<=vf){
                ans[i+p]=s[st[vf]][p];
                p++;
                r[i+p]=0;
                while((j<=vf)&&((int)s[st[j]].size()==p)){
                    if((r[i+p]==0)||(st[j]+1<r[i+p]))
                        r[i+p]=st[j]+1;
                    j++;
                }
            }
            while(i+p<t){
                p++;
                r[i+p]=0;
            }

            t=i+p;
        }
    }

    for(int i=0; i<k; i++)
        cout << ans[i];

    return 0;
}


Measured memory_bytes: 7552
def resolve():
    '''
    code here
    '''
    A, B = [int(item) for item in input().split()]
    S = input()

    if S[A] == '-' and len(S) >= 3:
        if '-' in S[:A] or '-' in S[-1*B:]:
            print('No')
        else:
            print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9172
def count_bigger(a, b):
    i = j = 0
    c = []
    while i < len(a) and j < len(b):
        if a[i] >= b[j]:
            j += 1
            continue
        c.append(len(b) - j)
        i += 1
    if len(c) < len(a):
        c += [0] * (len(a) - len(c))
    for i in range(len(c) - 1, 0, -1):
        c[i - 1] += c[i]
    return c


def f(a, b, c):
    bc = count_bigger(b, c)
    i = j = ans = 0
    while i < len(a) and j < len(b):
        if a[i] >= b[j]:
            j += 1
            continue
        ans += bc[j] - len(set(c) & set(2 * _b - a[i] for _b in b[j:]))
        i += 1
    return ans


def solve(string):
    n, s = string.split()
    r, g, b = [], [], []
    for i, _s in enumerate(s):
        if _s == "R":
            r.append(i)
        if _s == "G":
            g.append(i)
        if _s == "B":
            b.append(i)
    return str(f(r, g, b) + f(r, b, g) + f(b, r, g) + f(b, g, r) + f(g, r, b) + f(g, b, r))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 9292
#include<bits/stdc++.h>
using namespace std;
int a[50000],b,c,d,n,x,ans;
int main(){
    cin>>n>>d>>x;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        for(int u=1;u<=d;u+=a[i]){
            ans++;
        }
    }
    cout<<ans+x<<endl;
}


Measured memory_bytes: 256
N = int(input())
w = round(N / 1.08)
ans = int(w * 1.08)
if ans == N:
    print(w)
elif int((w + 1) * 1.08) == N:
    print(w + 1)
elif int((w - 1) * 1.08) == N:
    print(w - 1)
else:
    print(":(")

Measured memory_bytes: 3064
import math

n=int(input())

x = []
y = []
for i in range(n):
    H, W = map(int, input().split())
    x.append(H)
    y.append(W)

sum = 0
for i in range(1,n):
    sum += i 

kazu = math.factorial(n)*(n-1)
tori = kazu/sum

dis = 0
for i in range(n-1):
    for j in range(i, n-1):
        dis += math.sqrt((x[j+1]-x[i])*(x[j+1]-x[i]) + (y[j+1]-y[i])*(y[j+1]-y[i]))
    
print(round(dis*tori/math.factorial(n),10))

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<string>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;





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

	bool fl = 0;
	rep(i,0,s.size()) {
		if (i+1 <= s.size()-1 && s[i] == s[i + 1]) {
			cout << i + 1 << " " << i + 2 << endl;
			fl = 1;
			break;
		}
		if (i+2 <= s.size() - 1 && s[i] == s[i + 2]) {
			cout << i + 1 << " " << i + 3 << endl;
			fl = 1;
			break;
		}
	}

	if (!fl)cout << "-1 -1" << endl;
	
	
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(I,X,Y) for(int I=X;I<Y;I++)
#define REP(I,X,Y) for(int I=Y-1;I>=X;I--)
#define INF 1000000007
#define LINF 1000000000000000007
typedef long long ll;
using namespace std;

int main(){
  int V,E,r,s,t,d;
  cin >> V >> E >> r;
  vector<tuple<int,int,int>> edges;
  ll dmin[V];
  FOR(i,0,V)dmin[i] = LINF;
  dmin[r] = 0;
  FOR(i,0,E){
    cin >> s >> t >> d;
    edges.push_back(make_tuple(s,t,d));
  }
  FOR(i,0,V-1){
    FOR(j,0,E){
      int s=get<0>(edges[j]),t=get<1>(edges[j]),d=get<2>(edges[j]);
      if(dmin[s] != LINF)dmin[t] = min(dmin[t],dmin[s]+d);
    }
  }

  FOR(j,0,E){
    int s=get<0>(edges[j]),t=get<1>(edges[j]),d=get<2>(edges[j]);
    if(dmin[s] != LINF)if(dmin[t] > dmin[s]+d){
      puts("NEGATIVE CYCLE");
      return 0;
    }
  }

  for(auto x:dmin){
    if(x == LINF)puts("INF");
    else cout << x << endl;
  }
}



Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    int n;
    cin >> n;
    ll sum=1;
    int r=0;
    int g=0;
    int b=0;
    rep(i,n){
        int a;
        cin >> a;
        if(a==b){
            if(a==g){
                if(a==r){
                    r++;
                    sum*=3;
                    sum%=mod;
                    continue;
                }
                g++;
                sum*=2;
                sum%=mod;
                continue;
            }
            b++;
            continue;
        }
        if(a==g){
            if(a==r){
                r++;
                sum*=2;
                sum%=mod;
                continue;
            }
            g++;
            continue;
        }
        if(a==r){
            r++;
            continue;
        }
        sum=0;
    }
    cout << sum;
    


}

/*



 */



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
 
int main()
{
  cout << setprecision(6);
  cout << setiosflags(ios::scientific);
  cout.flags(ios::fixed);
 
  while(true){
    int h, w;
    cin >> h >> w;
 
    if(h==0&&w==0)
      break;
 
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
    if((i+j)%2==0)
      cout << "#";
    else
      cout << ".";
      }
      cout << endl;
    }
    cout << endl;
  }
}

Measured memory_bytes: 3080
#include <iostream>
#include <string>
#include <math.h>
#include <cstdlib>

using namespace std;

int main()
{

    string S;    
    int min=10000;
    int temp;
   cin >> S;
   
   for(int i=0;i<S.length()-2;i++)
   {
       temp=abs(753-stoi(S.substr(i,3)));
       if(temp<min)min=temp;
       
   }
   cout << min  << endl;
   
   return 0;
}

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

import math
from collections import defaultdict
d = defaultdict(int)

def trial_division(n,d):
    flg=True
    #2から√n以下の数字で割っていく
    tmp = n//2 + 1
    for num in range(2,tmp):
        while n % num == 0:
            flg=False
            n //= num
            d[num]+=1

    #flgがTrueならそれは素数
    if flg:
        d[n]+=1

    return

for n in range(2,N+1):
    trial_division(n,d)

ans=1
for v in d.values():
    ans*=(v+1)

print(ans%(10**9+7))

Measured memory_bytes: 3316
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

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

  vector<int> v(3);
  cin>>v[0]>>v[1]>>v[2];
  SORT(v);
  cout<<(v[2]-v[0])<<endl;
}

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

int main(){
	int a,b,c,buf;
	cin >> a >> b >> c;
	if(a>b){
		buf=a;
		a=b;
		b=buf;
	}
	if(b>c){
		buf=b;
		b=c;
		c=buf;
	}
	if(a>b){
		buf=a;
		a=b;
		b=buf;
	}
	cout << a << " "<< b << " " << c << endl;
	
	return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);

    
    string s;
    cin >> s;
    for(auto a: s) {
        if (a == '9') {
            cout << 1;
        } else {
            cout << 9;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int h = sc.nextInt();
            int w = sc.nextInt();

            if(h == 0 && w == 0) {
                break;
            }

            for(int i=0; i<h; i++) {
                StringBuilder sb = new StringBuilder();
                boolean isSharp = false;

                if(i % 2 == 0) {
                    sb.append("#");
                    isSharp = true;
                } else {
                    sb.append(".");
                }
                for(int j=1; j<w; j++) {
                    if(isSharp && j%2 != 0) {
                        sb.append(".");
                    } else if(isSharp && j%2 == 0){
                        sb.append("#");
                    } else if(!isSharp && j%2 != 0){
                        sb.append("#");
                    } else if(!isSharp && j%2 == 0){
                        sb.append(".");
                    }
                }
                System.out.println(sb);
            }
            System.out.println("");
        }
        sc.close();
    }
}



Measured memory_bytes: 28976
/*

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

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

signed main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int q;
	cin>>q;
	vi w(q);
	rep(i,q)cin>>w[i];
	
	vi dp(n+1);
	rep(i,n){
		if(s[i]=='C')dp[i]=1;
	}
	for(int i=n-1;i>=0;i--)dp[i]+=dp[i+1];
	vvi d(2,vi(n+1));
	rep(i,n){
		if(s[i]=='M'){
			d[0][i+1]=1;
			d[1][i+1]=dp[i];
		}
	}
	rep(i,2)rep(j,n)d[i][j+1]+=d[i][j];
	rep(Q,q){
		int co=0;
		rep(i,n)if(s[i]=='D'){
			int t=i+w[Q];
			t=min(t,n);
			int c=d[1][t]-d[1][i];
			c-=(d[0][t]-d[0][i])*dp[t];
			co+=c;
		}
		cout<<co<<endl;
	}
}


















Measured memory_bytes: 32644
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &a[i])
	}
	for cnt := 0; ; cnt += 1 {
		flag := true
		for i := 0; i < n; i++ {
			if a[i] % 2 != 0 {
				flag = false
				break
			}
		}
		if flag {
			for i := 0; i < n; i++ {
				a[i] /= 2
			}
		} else {
			fmt.Println(cnt)
			break
		}
	}
}


Measured memory_bytes: 512
def cal(a):
 	return ((1 + a) / 2)
 
N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []
sum_raw = []
sum_cal = 0
 
for i in range(0, N):
    p[i] = cal(p[i])


for i in range(0, N):
	sum_cal += p[i]
	sum_raw.append(sum_cal)

for i in range(0, N - K):
	ans = sum_raw[i + K] - sum_raw[i]
	ans_raw.append(ans)

ans_0 = sum_raw[K - 1]
ans_raw.append(ans_0)

print(max(ans_raw))

Measured memory_bytes: 24804
N = int(input())
lista = []
for n in range(N):
    listan = []
    an = int(input())
    for n in range(an):
        listxy = tuple(map(int, input().split()))
        listan.append(listxy)
    listset = tuple(listan)
    lista.append(listset)    
tuplea = tuple(lista)    
#print(lista)
ansfin = 0
for n in range(2**N):
    bin2 = list(bin(n))[2:]
    bin2.reverse()
    #print(bin2)
    l = len(bin2)
    rightwrong = set()
    #print(l)
    setright = set()
    for n in range(N):
        if n<l:
            #print(bin2[n])
            if bin2[n] == str(1):
                rightwrong.add((n+1, 1))
                lo = len(tuplea[n])
                for m in range(lo):
                    setright.add(tuplea[n][m])
            else:
                rightwrong.add((n+1, 0))
        else:
            rightwrong.add((n+1, 0))  
    #print('a')                     
    #print(setright)
    #print(rightwrong)
    if setright.issubset(rightwrong):
        ans = bin2.count(str(1))
        if ansfin>=ans:
            pass
        else:
            ansfin = ans
    #print(ans)    
print(ansfin)    


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ROUNDUP(divisor,dividend) (divisor + (dividend - 1)) / dividend
int e,y;
int main(){
  cin >> e >> y;
  if(e == 0){
    if(1868 <= y && y <= 1911){
      cout << 'M' << y-1867 << endl;
    }
    if(1912 <= y && y <= 1925){
      cout << 'T' << y-1911 << endl;
    }
    if(1926 <= y && y <= 1988){
      cout << 'S' << y-1925 << endl;
    }
    if(1989 <= y && y <= 2016){
      cout << 'H' << y-1988 << endl;
    }
  }

  if(e == 1){
    cout << y+1867 << endl;
  }
  if(e == 2){
    cout << y+1911 << endl;
  }
  if(e == 3){
    cout << y+1925 << endl;
  }
  if(e == 4){
    cout << y+1988 << endl;
  }
}



Measured memory_bytes: 3116
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<memory.h>
#include<ctime>
#include<cstdio>
#include<map>
#include<stack>

using namespace std;

int main()
{
	int n;
	int tmp;
	cin>>n;
	if(n==1)
	{
		cout<<1<<endl;
		return 0;
	}
	for(int i=6;i>0;i--)
	{
		if(pow(2,i)<=n)
		{
			cout<<pow(2,i)<<endl;
			return 0;		
		}
	}
	return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){

	int left[4] = {0,0,0,0},right[4] = {0,0,0,0};
	double l_e,r_e;

	while(scanf("%lf %lf",&l_e,&r_e)!=EOF){
		if(l_e >= 1.1){
			left[0]++;
		}else if(l_e >= 0.6){
			left[1]++;
		}else if(l_e >= 0.2){
			left[2]++;
		}else{
			left[3]++;
		}

		if(r_e >= 1.1){
			right[0]++;
		}else if(r_e >= 0.6){
			right[1]++;
		}else if(r_e >= 0.2){
			right[2]++;
		}else{
			right[3]++;
		}
	}

	printf("%d %d\n%d %d\n%d %d\n%d %d\n",left[0],right[0],left[1],right[1],left[2],right[2],left[3],right[3]);

    return 0;
}

Measured memory_bytes: 2556
#include <bits/stdc++.h>
typedef long long l1;
#define mod 1000000007
#define f first
#define se second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define set(a,b) memset(a,b,sizeof(a))
#define mn *min_element
#define mx *max_element
#define input l1 t; cin>>t; while(t--)
using namespace std;

int main()
{
 	ios_base::sync_with_stdio(false);
  	cin.tie(NULL);cout.tie(NULL);
  	l1 n,x,y;
 	cin>>n>>x>>y;
    l1 d[n]={},l;
    for(l1 i=1;i<=n-1;++i)
    {
        for(l1 j=i+1;j<=n;++j)
        {
            l=min(j-i,abs(i-x)+abs(j-y)+1);
            l--;
            d[l]++;
        }
    }
    for(l1 i=0;i<n-1;++i)
        cout<<d[i]<<endl;
  	return 0;
}

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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define pll         pair<long,long>
#define vi          vector<int>
#define vll         vector<ll>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define mod        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rem(i,a,b)  for(int i=a;i>b;i--)
#define mp(a,b)     make_pair(a,b)
#define vvi(a,b,name)    vector<vector<int>> name(a,vector<int>(b,-1))




void solve(){
    string s;cin>>s;
    int l=s.length();
    if(l&1!=0)l--;
    else l-=2;
    bool brake=true;
    while(brake){
        brake=false;
        rep(i,0,l/2){
            if(s[i]!=s[l/2+i]){
                brake=true;
                break;
            }
        }
        l-=2;
    }
    cout<<l+2;


}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long t=1;
    //cin>>t;

    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#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, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
	string s;cin >> s;
    int ans=0;
    int cnt=0;
    REP(i,3){
        if(s[i]=='R'){
            cnt++;
        }
        else{
            chmax(ans,cnt);
            cnt=0;
        }
    }
    chmax(ans,cnt);
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define eps 1e-3
#define pi acos(-1.0)
#define inf 0x3f
#define INF 0x3f3f3f3f
#define pb push_back
#define debug1 cout<<"&&";
#define debug2 cout<<"**";
#define ms(a, x) memset(a, x, sizeof(a))
#define for0(i, n) for(int i = 0; i < n; ++i)
#define for1(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
const int mod = 1e9 + 7;
const int N = 3e3 + 10;
const int M = 1e6+10;
/*=================================================================================*/

int n, a[N];
ll dp[N][N];

int main() {
   cin>>n;
   for1(i, n) scanf("%d", &a[i]);
   for(int i = n; i; --i)
      for(int j = i; j <= n; ++j) {
         dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]);
      }
   cout<<dp[1][n]<<endl;
}

Measured memory_bytes: 49868
// Standard I/O
#include <iostream>
#include <sstream>
#include <cstdio>
// Standard Library
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
// Template Class
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
// Container Control
#include <algorithm>

using namespace std;

#define rep( i, n ) for( int i = 0; i < n; ++i )
#define irep( i, n ) for( int i = n-1; i >= 0; --i )
#define reep( i, s, n ) for ( int i = s; i < n; ++i )
#define ireep( i, n, s ) for ( int i = n-1; i >= s; --i )
#define foreach(itr, x) for( typeof(x.begin()) itr = x.begin(); itr != x.end(); ++itr)

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all( v ) v.begin(), v.end()
#define fs first
#define sc second
#define vc vector

// for visualizer.html
double SCALE = 1.0;
double OFFSET_X = 0.0;
double OFFSET_Y = 0.0;
#define LINE(x,y,a,b) cerr << "line(" << SCALE*(x) + OFFSET_X << ","	\
	<< SCALE*(y) + OFFSET_Y << ","										\
	<< SCALE*(a) + OFFSET_X << ","										\
	<< SCALE*(b) + OFFSET_Y << ")" << endl;
#define CIRCLE(x,y,r) cerr << "circle(" << SCALE*(x) + OFFSET_X << ","	\
	<< SCALE*(y) + OFFSET_Y << ","										\
	<< SCALE*(r) << ")" << endl;

typedef long long ll;
typedef complex<double> Point;

typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector< vector<int> > vii;
typedef vector< vector<double> > vdd;

typedef vector<int>::iterator vi_itr;

const int IINF = 1 << 28;
const int MOD = 1e9+7;
const double INF = 1e30;
const double EPS = 1e-10;
const double PI = acos(-1.0);

// Direction : L U R D
const int dx[] = { -1, 0, 1, 0};
const int dy[] = { 0, -1, 0, 1 };

struct Node {
    vi edge;
};

Node node[100000];
int dim[100000];
int ans[100000];

void dfs ( int idx ) {
    vector<int> next_idx;
    
    rep(i, node[idx].edge.size()) {
        if ( dim[node[idx].edge[i]] > 1 ) {
            --dim[node[idx].edge[i]];
        } else {
            ans[node[idx].edge[i]] = idx+1;
            next_idx.emplace_back(node[idx].edge[i]);
        }
    }

    rep(i, next_idx.size()) {
        dfs(next_idx[i]);
    }
}

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

    rep(i, n+m-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        node[a].edge.emplace_back(b);
    }

    rep(i, n) {
        rep(j, node[i].edge.size()) dim[node[i].edge[j]]++;
    }

    int root = -1;
    rep(i, n) if ( dim[i] == 0 ) root = i;

    rep(i, n) ans[i] = -1;
    ans[root] = 0;

    dfs(root);

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


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

const int BUCKET = 400,SIZE = 300;
int N,Q;
bool updateFlag [BUCKET];
ll lazyUpdate [BUCKET];
ll bucketMin [BUCKET];
ll A [100000];
const ll INF = (1ll << 31) - 1;

void update(int l,int r,ll val)
{
	FOR(i,0,BUCKET){
		int bucketL = i * SIZE,bucketR = (i + 1) * SIZE;
		if(r <= bucketL || bucketR <= l) continue;
		if(l <= bucketL && bucketR <= r){
			lazyUpdate [i] = val;
			updateFlag [i] = true;
			continue;
		}
		if(updateFlag [i]){
			FOR(j,bucketL,bucketR){
				A [j] = lazyUpdate [i];
			}
			updateFlag [i] = false;
		}
		bucketMin [i] = INF;
		FOR(j,bucketL,bucketR){
			if(l <= j && j < r){
				A [j] = val;
			}
			chmin(bucketMin [i],A [j]);
		}
	}
}

ll getMin(int l,int r)
{
	ll res = INF;
	FOR(i,0,BUCKET){
		int bucketL = i * SIZE,bucketR = (i + 1) * SIZE;
		if(r <= bucketL || bucketR <= l) continue;
		if(l <= bucketL && bucketR <= r){
			if(updateFlag [i]){
				chmin(res,lazyUpdate [i]);
			}
			else{
				chmin(res,bucketMin [i]);
			}
			continue;
		}
		if(updateFlag [i]){
			FOR(j,bucketL,bucketR){
				A [j] = lazyUpdate [i];
			}
			updateFlag [i] = false;
		}
		bucketMin [i] = INF;
		FOR(j,bucketL,bucketR){
			if(l <= j && j < r){
				chmin(res,A [j]);
			}
			chmin(bucketMin [i],A [j]);
		}
	}
	return res;
}

int main()
{
	scanf("%d%d",&N,&Q);
	vector<ll> ans;
	fill(A,A + N,INF);
	fill(bucketMin,bucketMin + BUCKET,INF);
	FOR(i,0,Q){
		int com;
		scanf("%d",&com);
		if(com == 0){
			int s,t,x;
			scanf("%d%d%d",&s,&t,&x);
			update(s,t + 1,x);
		}
		else{
			int s,t;
			scanf("%d%d",&s,&t);
			ans.push_back(getMin(s,t + 1));
		}
	}

	FOR(i,0,ans.size()){
		printf("%lld\n",ans [i]);
	}

	return 0;
}

Measured memory_bytes: 4680
#include<bits/stdc++.h>
typedef long long ll;
#define cle(n) memset(n,0,sizeof(n))
using namespace std;
const int maxn=1000005;
#define inf 1000000009
const long long  mod=1e9+7;
int t;
ll n,a,b;
ll num[maxn];
ll c[maxn];


int check(ll t)
{
    ll res = 0;
    memcpy(c,num,sizeof(num));
    for(ll i=0; i<n; i++)
        c[i] -= t*b;
    ll m = a-b;
    for(ll i=0; i<n; i++){
        if(c[i] > 0){
            res += (c[i]%m==0) ? (c[i]/m) : (c[i]/m+1);
        }
    }
    return res <= t;

}


int bina()
{
      int low=1,high=1e9;
  int mid=0;
  for(int i=1; i<=100; i++)
  {
     mid=(low+high)/2;

     ll tttt=check(mid);
    // cout<<tttt<<"  "<<mid<<"  "<<endl;
     if(tttt==0)
        low=mid+1;
     else if(tttt==1)
        high=mid;
  }
  return mid;
}



int main()
{

   while(~scanf("%lld",&n))
   {
       scanf("%lld%lld",&a,&b);

      for(int i=0;i<n;i++)
       {
        scanf("%lld",&num[i]);

       }
int ans=bina();
cout<<ans<<endl;









   }



    return 0;
}


Measured memory_bytes: 10496
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,M,ans = 1;
    cin >> N >> M;
    vector<pair<int,int>> p(M);
    for(int i = 0;i < M;i ++){
        cin >> p[i].second >> p[i].first;
    }
    sort(p.begin(),p.end());
    int plc = p[0].first;
    for(int i = 1;i < M;i ++){
        if(p[i].second >= plc){
            ans ++;
            plc = p[i].first;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<(int)(r); i++)
#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)
#define all(vec) vec.begin(),vec.end()
#define allr(vec) vec.rbegin(),vec.rend()
using namespace std;

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

using ll=long long;

using vb=vector<bool>;
using vc=vector<char>;
using vs=vector<string>;
using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;

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

  int N; cin >>N;
  string S; cin >>S;

  string ans;
  rep(i,0,S.size()) {
    char temp=S[i]+N;
    if ('Z'<temp) {
      temp-=26;
    }
    ans+=temp;
  }

  cout <<ans <<'\n';
  return 0;
}


Measured memory_bytes: 3504
import sys
input = sys.stdin.readline

n = int(input())
MOD = 10 ** 9 + 7

factorial = [0] * (n+1)
factorial[0] = 1

for i in range(1, n+1):
    factorial[i] = factorial[i-1] * i
target = factorial[n]

prime_factors = []

i = 2
while i ** 2 <= target:
    if target % i != 0:
        i += 1
        continue
    ext = 0
    while target % i == 0:
        ext += 1
        target //= i

    prime_factors.append((i, ext))
    i += 1

if target != 1:
    prime_factors.append((target, 1))

ans = 1
for pf in prime_factors:
    ans = (ans * (pf[1]+1)) % MOD

print(ans)


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

map<string,long long> mp;
int main() {

    ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    long long n;
    cin>>n;

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

    long long max = 0;
    for(auto i=mp.begin();i!=mp.end();i++){
        if(i->second>max){
            max = i->second;
        }
    }

    for(auto i=mp.begin();i!=mp.end();i++){
        if(i->second==max){
            cout<<i->first<<"\n";
        }
    }




    return 0;
}

Measured memory_bytes: 19260
import operator
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N, M = list(map(int, sys.stdin.readline().split()))
LRC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

LRC.sort()
LRC = [(l - 1, r - 1, c) for l, r, c in LRC]
i = 0

# dp[pos]: pos までの最短距離
dp = SegmentTree(N, fn=min, initial_values=[INF] * N)
dp.set(0, 0)
for pos in range(N):
    d = dp.get(pos, N)
    while i < M and LRC[i][0] == pos:
        l, r, c = LRC[i]
        dp.set(r, min(d + c, dp.get(r)))
        i += 1
ans = dp.get(N - 1)
if ans == INF:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 122332
n = int(input())
a = list(map(int, input().split()))
if n < 3:
    print(1)
    exit(0)
cnt = 1

increase = a[1] - a[0];
for i in range(2, len(a)):
    new_inc = a[i] - a[i-1];
    if increase * new_inc < 0:
        cnt += 1
        increase = 0
    elif increase == 0:
        increase = new_inc
print(cnt)


Measured memory_bytes: 15020
require "set"
MAX = 100_000
n = gets.chomp.to_i
dp = Hash.new{MAX}

6.times do |i|
  dp[i + 1] = i + 1
end
dp[7], dp[8] = 2, 3

set_for_once = Set.new({})
(Math.log(MAX, 6).ceil).times.reduce(set_for_once){|memo, attr| memo.add 6 ** attr}
(Math.log(MAX, 9).ceil).times.reduce(set_for_once){|memo, attr| memo.add 9 ** attr}
set_for_once = set_for_once.sort
set_for_once.each{|attr| dp[attr] = 1}

10.upto(n) do |i|
  next if dp[i] != MAX
  idx = set_for_once.index{|attr| attr > i} || set_for_once.size - 1
  idx.times do |j|
    dp[i] = [dp[i - set_for_once[j]] + 1, dp[i]].min
  end
end
puts dp[n]

Measured memory_bytes: 8316
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<string> S(N);
  rep(i,N)
  {
    cin >> S[i];
  }
  vector<ll> vec(5);
  rep(i,N)
  {
    if(S[i][0]=='M')
    {
      vec[0] ++;
    }
    if(S[i][0]=='A')
    {
      vec[1] ++;
    }
    if(S[i][0]=='R')
    {
      vec[2] ++;
    }
    if(S[i][0]=='C')
    {
      vec[3] ++;
    }
    if(S[i][0]=='H')
    {
      vec[4] ++;
    }
  }
  ll product = 0;
  rep(i,5)
  {
    for(int j=i+1;j<5;j++)
    {
      for(int k=j+1;k<5;k++)
      {
        product += vec[i]*vec[j]*vec[k];
      }
    }
  }
  cout << product << endl;
  return 0;
}


Measured memory_bytes: 6652
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
n,p = ma()

def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

fct = factorize(p)
tmp = 1
for num,cnt in fct:
    tmp*= num**(cnt//n)
print(tmp)


Measured memory_bytes: 9384
#include<bits/stdc++.h>
using namespace std;
int main()
{long long int r=0;
  string s;
  getline(cin,s);
  for(int i=0;i<s.size();i++)
  {
   r=s[i]-48+r;
  }
  if(r%9==0)
    cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
 return 0;
}



Measured memory_bytes: 3700
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = 105;
int n, x;
int a[maxn];

int read() {
  if (scanf("%d%d", &n, &x) < 2) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  return true;
}

void solve() {
  sort(a, a + n);
  int k = 0;
  int sum = 0;
  while (k < n && sum + a[k] <= x) {
    sum += a[k];
    k++;
  }
  int res = k;
  if (k == n && sum < x) {
    res--;
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
 
bool isMale() {
    string result;
    cin >> result;
    if (result == "Vacant") {
        exit(0);
    }
    return result == "Male";
}
 
int main() {
    int N;
    cin >> N;
    int left = 0;
    int right = N - 1;
    cout << 0 << endl;
    bool leftMale = isMale();
    while (left < right) {
        int mid = (left + right + 1) / 2;
        cout << mid << endl;
        bool midMale = isMale();
        if ((mid - left) % 2 == (leftMale == midMale)) {
            right = mid;
        } else {
            left = mid;
            leftMale = midMale;
        }
    }
}

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

const int maxn = 1e6+5;

double k[maxn];
int main() {
    double sum = 0;
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> k[i], sum += k[i];
    double a = 1.00 / 4.0 / m;
    sort(k+1, k+n+1, greater<int>());
    double b = k[m] / sum;
    if(a <= b) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

typedef long long ll;

ll LevenshteinDistance(const string& s1, const string& s2){

    const ll N1 = s1.size();
    const ll N2 = s2.size();

    ll dp[N1+1][N2+1] = {};

    for(int i=0; i<=N1; i++) {
	dp[i][0] = i;
    }
    for(int j=0; j<=N2; j++) {
	dp[0][j] = j;
    }

    for(int i=0; i<N1; i++) {
	for(int j=0; j<N2; j++) {
	    ll a = (s1[i] == s2[j] ? 0 : 1);
	    dp[i+1][j+1] = min( dp[i][j] + a, dp[i][j+1]+1);
	    dp[i+1][j+1] = min( dp[i+1][j+1], dp[i+1][j]+1);
	}
    }
    return dp[N1][N2];
    
}

int main () {

    string s1,s2;
    cin >> s1 >> s2;
    cout << LevenshteinDistance(s1,s2) << endl;

    return 0;
}

Measured memory_bytes: 10924