Problem:


Score : 600 points

Problem Statement

In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short.

The name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.

Given a string S of length N and an integer k (k \geq 3),
he defines the k-DMC number of S as the number of triples (a, b, c) of integers that satisfy the following conditions:

0 \leq a < b < c \leq N - 1

S[a] = D

S[b] = M

S[c] = C

c-a < k

Here S[a] is the a-th character of the string S. Indexing is zero-based, that is, 0 \leq a \leq N - 1 holds.

For a string S and Q integers k_0, k_1, ..., k_{Q-1}, calculate the k_i-DMC number of S for each i (0 \leq i \leq Q-1).

Constraints

3 \leq N \leq 10^6

S consists of uppercase English letters

1 \leq Q \leq 75

3 \leq k_i \leq N

All numbers given in input are integers

Input

Input is given from Standard Input in the following format:

N
S
Q
k_{0} k_{1} ... k_{Q-1}

Output

Print Q lines.
The i-th line should contain the k_i-DMC number of the string S.

Sample Input 1

18
DWANGOMEDIACLUSTER
1
18

Sample Output 1

1

(a,b,c) = (0, 6, 11) satisfies the conditions.

Strangely, Dwango Media Cluster does not have so much DMC-ness by his definition.

Sample Input 2

18
DDDDDDMMMMMCCCCCCC
1
18

Sample Output 2

210

The number of triples can be calculated as 6\times 5\times 7.

Sample Input 3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

Sample Output 3

0
1
2

(a, b, c) = (0, 23, 36), (8, 23, 36) satisfy the conditions except the last one, namely, c-a < k_i.

By the way, DWANGO is an acronym for "Dial-up Wide Area Network Gaming Operation".

Sample Output 4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

Sample Output 4

10
52
110
140



Sample input:
18
DWANGOMEDIACLUSTER
1
18


Sample output:
1

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
using namespace std;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

template<typename ...Ts>
void show(Ts... ts){
  cout<<"#:";
  auto print=[](auto v){cout<<v<<" ";};
  initializer_list<int>{(void(print(ts)),0)...};
  cout<<endl;
}


int main(void){
    ll n,q,k;
    string s;
    cin>>n;
    cin>>s;
    cin>>q;
    vector<int> kin(n,0);
    rep(i,n)cin>>kin[i];


    rep(i,q){
        k=kin[i];
        ll nd=0;
        ll nm=0;
        ll ndm=0;
        ll ans=0;
        std::deque<int> st;
        char ch;
        ll pre;
        rep(j,n){
            ch=s[j];
            if (ch=='C')ans+=ndm;
            if (j<k-1){
                st.push_back(ch);
                if (ch=='M'){ndm+=nd;nm+=1;}
                if (ch=='D')nd+=1;
            }else{
                pre=st.front();
                st.pop_front();
                st.push_back(ch);
                if (pre=='D'){nd-=1;ndm-=nm;}
                if (pre=='M')nm-=1;
                if (ch=='M'){ndm+=nd;nm+=1;}
                if (ch=='D')nd+=1;
            }
        }
    cout<<ans;
    }
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

# solve
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = input().rstrip()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            if i >= ki:
                if s[-ki +i] == "D":
                    d -= 1
                    dm -= m
                    dm%=mod
                if s[-ki + i] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            if s[i] == "M":
                m += 1
                dm += d
                dm%=dm
            if s[i] == "C":
                ans += dm
            ans %= mod
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#"""
import sys
input = sys.stdin.readline
#"""

import scipy as sp

N = int(input())
S = input()
Q = int(input())
*K, = map(int,input().split())

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

S = "A" + S
cs = sp.cumsum
ans = sp.zeros(Q,int)
D = sp.zeros(N+1,int)
cntM = sp.zeros(N+1,int)
sumM = sp.zeros(N+1,int)
M = []
C = []
for i,s in enumerate(S):
    if s=="D":
        D[i] = 1
    elif s=="M":
        M.append(i)
    elif s=="C":
        C.append(i-1)
D = cs(D)
for i in M:
    cntM[i] = 1
    sumM[i] = D[i]
cntM = cs(cntM)
sumM = cs(sumM)

for i in C:
    sMi = sumM[i]
    cMi = cntM[i]
    for j,k in enumerate(K):
        ik = max(0,i-k+1)
        ans[j] += (sMi-sumM[ik]) - D[ik]*(cMi-cntM[ik])
for out in ans:
    print(out)

Submission status: Runtime Error

Solution code:
from numpy import*
_,s,_,k=open(0)
s=array(list('='+s[:-1]))
d,m,c=[s==t for t in'DMC']
x,y=map(cumsum,(d,m))
for k in int32(k.split()):
  t=copy(x)
  t[k:]-=x[:-k]
  t*=m
  t[k+1:]-=d[1:-k]*(y[k:-1]-y[:~k])
  print(sum(cumsum(t)*c))

Submission status: Runtime Error

Solution code:
e=enumerate
n,s,q,*k=open(0).read().split()
m,c,x=eval('[0]*-~int(n),'*3)
for i,t in e(s,1):
  m[i]=m[i-1]+(t=='M')
  f=t=='C'
  c[i]=c[i-1]+f
  x[i]=x[i-1]+f*m[i]
for k in map(int,k):
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    if t=='D':a+=x[j]-x[i]-(c[j]-c[i])*m[i]
  print(a)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
N = int(readline())
S = np.empty(N+1,'S1')
S[1:] = np.frombuffer(list(readline()),dtype='S1')[:N]
Q = int(readline())
query = map(int,readline().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
S = np.frombuffer('-'+input().rstrip(),'S1')
Q = int(input())
query = map(int,input().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
S = np.frombuffer('-'+readline().rstrip(),'S1')
Q = int(input())
query = map(int,input().split())

isD = S == 'D'
isM = S == 'M'
isC = S == 'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(b'-'+readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print(x.cumsum() * isC).sum()

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    ans = 0
    DMC = [0]*3
    for i in range(n):
        if s[i] == "D":
            DMC[0] += 1
        elif s[i] == "M":
            DMC[1] += 1
            DMC[2] += DMC[0]
        if i >= ki:
            j = i-ki
            if s[j] == "D":
                DMC[0] -= 1
                DMC[2] -= DMC[1]
            elif s[j] == "M":
                DMC[1] -= 1
        if c == "C":
            ans += DMC[2]
    print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
using namespace std;

int main() {
  int N, Q;
  string S;
  cin >> N;
  cin >> S;
  cin >> Q;
  
  int K[Q];
  for(int i=0;i<Q;i++){
    cin >> K[i];
  }
  for(int q=0;q<Q;q++){
    int k = K[q];
    int ans = 0;
    for(int i = 1;i<N-1;i++){
      if(S[i]=='M'){
//cout << i << endl;
        int c = 0;
        for(int j = 1;j<k-1;j++){
          if(i+j<N){
            if(S[i+j]=='C'){
              c += 1;
            }
          }
          if(i+j-k+1>=0){
            if(S[i+j-k+1]=='D'){
              ans += c;
            }
          }
        }
      }
    }
    cout << ans << endl;
    
    
  }
  
  return 0;
}

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
Q=int(input())
K=[int(i) for i in input().split()
def f(k):
    num=0
    L=[0,0,0]
    for i in range(N):
        if i-k>=0:
            if S[i-k]=='D':
                L[0]-=1
                L[2]-=L[1]
            elif S[i-k]=='M':
                L[1]-=1
        if S[i]=='D':
            L[0]+=1
        elif S[i]=='M':
            L[1]+=1
            L[2]+=L[0]
        elif S[i]=='C':
            num+=L[2]
        #print(i,':',L,':',num)
    return num
for k in K:
    print(f(k))

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n = int(input())
s = input()
cp = []
count_a = 0
accsum_ab = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
        count_a += 1
    elif c == 'M':
        cp.append((1, i))
        accsum_ab.append(count_a)
    elif c == 'C':
        cp.append((2, i))

i, j = 0, 0
while i < len(cp) and cp[i][0] != 0:
    if cp[i][0] == 1:
        j += 1
    i += 1
cp = cp[i:]
accsum_ab = accsum_ab[j:]
i, j = -1, -1
while -i <= len(cp) and cp[i][0] != 2:
    if cp[i][0] == 1:
        j -= 1
    i -= 1
if i < -1:
    cp = cp[:i + 1]
    if j < -1:
        accsum_ab = accsum_ab[:i + 1]
accsum_ab = [0] + list(accumulate(accsum_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_b = 0
    rejected_a = 0
    rejected_b = 0
    for r, item in enumerate(cp):
        if item[0] == 1:
            count_b += 1
        elif item[0] == 2:
            left_limit = item[1] - k
            while l < r and cp[l][1] <= left_limit:
                old_item = cp[l]
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    rejected_b += 1
                l += 1
            ans += accsum_ab[count_b] - accsum_ab[rejected_b] - rejected_a * (count_b - rejected_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
s = input()
cp = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
    elif c == 'M':
        cp.append((1, i))
    elif c == 'C':
        cp.append((2, i))

i = 0
while cp[i][0] != 0:
    i += 1
cp = cp[i:]
while cp[-1][0] != 2:
    cp.pop()

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    deq = deque()
    count_a = 0
    rejected_a = 0
    count_internal_b = 0
    sum_internal_b = 0
    for item in cp:
        # print(deq, count_a, rejected_a, count_internal_b, sum_internal_b)
        if item[0] == 0:
            count_a += 1
            deq.append(item)
        elif item[0] == 1:
            count_internal_b += 1
            sum_internal_b += count_a
            deq.append((*item, count_a))
        else:
            left_limit = item[1] - k
            while deq and deq[0][1] <= left_limit:
                old_item = deq.popleft()
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    count_internal_b -= 1
                    sum_internal_b -= old_item[2]
            ans += sum_internal_b - rejected_a * count_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
N = int(input())
S = [i for i in list(input())]
Q = int(input())
k = [int(i) for i in input().split()]
S = np.array(S, dtype=None)
 
index_D = np.where(S == 'D')[0]
index_M = np.where(S == 'M')[0]
index_C = np.where(S == 'C')[0]
xx, yy, zz = np.meshgrid(index_D, index_M, index_C)
a_b_c = np.c_[xx.ravel(), yy.ravel(), zz.ravel()]

for k_i in k:
    count = 0
    for abc in a_b_c:
        if abc[0] < abc[1] < abc[2] and abc[2] - abc[0] < k_i:
            count += 1
    print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
Ks = list(map(int, input().split()))

for K in Ks:
    cnt_d, cnt_m, sum_dm = 0,0,0
    ans = 0
    for i in range(N):
        if i-K>=0:
            if Q[i-K]=="D":
                cnt_d -= 1
                sum_dm -= cnt_m
            elif Q[i-K]=="M":
                cnt_m -= 1

        if Q[i]=="D":
            cnt_d += 1
        elif Q[i]=="M":
            sum_dm += cnt_d
            cnt_m += 1
        elif Q[i]=="C":
            ans += sum_dm

    print(ans)

Submission status: Runtime Error

Solution code:
s=re.sub('[ABEFGHIJKLNOPQRSTUVWXYZ]', '', s)
n=len(s)
for x in k:
    cnt=0
    for i in range(n-1,1,-1):
        if s[i] =='C':
            c=i
            for j in range(i,0,-1):
                if s[j] =='M':
                    b=j
                    for k in range(j,-1,-1):
                        if s[k] =='D':
                            a=k
                            if 0<=a<b<c and c-a<x:
                                cnt+=1
    print(cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s)
    ans = [sum(dmcmap[:k]) for k in ks]
    print(*ans, sep='\n', flush=True)

def dmc(src):
    ret = [0 for _ in range(len(src))]

    dmap = [i for i, x in enumerate(src) if x == 'D']
    mmap = [i for i, x in enumerate(src) if x == 'M']
    cmap = [i for i, x in enumerate(src) if x == 'C']

    for d in dmap:
        for m in filter(lambda x: x > d, mmap):
            for c in filter(lambda x: x > m, cmap):
                ret[c-d] += 1
    return ret

stdin = open('data.txt')
s, ks = load()
calc(s,ks)

Submission status: Runtime Error

Solution code:
import re
n=int(input())
s=input()
q=int(input())
k=list(map(int,input().split()))

for x in k:
    cnt=0
    s=re.sub('[ABEFGHIJKLNOPQRSTUVWXYZ]', '', s)
    for i in range(n-1,1,-1):
        if s[i] =='C':
            c=i
            for j in range(i,0,-1):
                if s[j] =='M':
                    b=j
                    for k in range(j,-1,-1):
                        if s[k] =='D':
                            a=k
                            if 0<=a<b<c and c-a<x:
                                cnt+=1
    print(cnt)

Submission status: Runtime Error

Solution code:

n = int(input());
mystr = input();
qn = int(input());
qlist = list(map(int, input().split()));

lenq = len(mystr);
d = [];
m = [];
t = [];
res = [];
for i in range(lenq):
	d.append([0] * lenq);
	m.append([0] * lenq);
	t.append([0] * lenq);
for i in range(lenq):
	if mystr[i]=='D':
		d[i][i] = 1;
	if mystr[i]=='M':
		m[i][i] = 1;
	for step in range(1, lenq):
		if i + step >= lenq:
			continue;
		t[i][i + step] = t[i][i + step - 1] + d[i][i + step - 1] * m[i + step - 1][i + step];

for q in qlist:
	sumc = 0;
	for i in range(0, lenq):
		if mystr[i] == 'C':
			st = 0;
			if (i - q + 1> 0):
				st = i - q + 1;
			ed = 0;
			if (i > 0):
				ed = i - 1;
			sumc += t[st][ed];
	res.append(sumc);

print(" ".join([str(x) for x in res]));

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()

while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)
D = []
C = []
M = [0]*N
for i in range(1,N):
    M[i] = M[i-1]
    if S[i] == 'M':
        M[i] += 1
    elif S[i] == 'D':
        D.append(i)
    elif S[i] == 'C':
        C.append(i)

def cal(k): 
    j = 0
    c = C[0]
    nc = len(C)
    res = 0
    for i in range(len(D)):
        a = D[i]
        while c-a < k:
            res += M[c]-M[a]
            if j < nc-1:
                j += 1
                c = C[j
            else:
                break
    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

if __name__ == "__main__":
    n = int(input())
    s = np.unicode(input())
    q = int(input())
    ks = list(map(int, input().split()))

    d_site = np.array(string == "D")
    m_site = np.array(string == "M")
    c_site = np.array(string == "C")

    c_site = np.where(c_site)[0].reshape(-1)

    nums = [0 for _ in range(q)]

    for main_i in c_site:
        for i in range(q):
            start = main_i - ks[i] + 1
            if start < 0:
                start = 0

            m_site_dum = np.where(m_site[start:main_i])[0].reshape(-1)

            for m_dum in m_site_dum:
                nums[i] += np.sum(d_site[start:main_i][:m_dum])

    for i in range(q):
        print(nums[i])

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()

while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)
D = []
C = []
M = [0]*N
for i in range(1,N):
    M[i] = M[i-1]
    if S[i] == 'M':
        M[i] += 1
    elif S[i] == 'D':
        D.append(i)
    elif S[i] == 'C':
        C.append(i)

def cal(k): 
    j = 0
    c = C[0]
    nc = len(C)
    res = 0
    for i in range(len(D)):
        a = D[i]
        while c-a < k:
            res += M[c]-M[a]
            if j < nc:
                j += 1
                c = C[j]
    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
q = int(input())

k_list = []
for i in range(q):
    k_list.append(int(input()))

d_num = []
m_num = []
c_num = []
for i, char in enumerate(s):
    if char == 'D':
        d_num.append(i)
    if char == 'M':
        m_num.append(i)
    if char == 'C':
        c_num.append(i)

for k in k_list:
    ans = 0
    for a in d_num:
        for b in m_num:
            for c in c_num:
                if a < b & b < c:
                    if (c - a) < k:
                        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def dmc(s, k):
  if s.find("M") >= s.find("C"):
    return [0,0]
  elif k > len(s):
    return dmc(s, len(s))
  elif k == 3:
    if s[0:3] == "DMC":
      return [1, 1]
    else:
      return [0, s[0:2].count("M")]
  elif s[k-1] == "C":
    return [dmc(s, k-1)[0] + dmc(s, k-1)[1], dmc(s, k-1)[1]]
  elif s[k-1] == "M":
    return [dmc(s, k-1)[0], dmc(s, k-1)[1] +1]
  else:
    return dmc(s, k-1)

n = int(input())
s = input()
q = int(input())
k_list = list(map(int, input().split()))

for k in k_list:
  r = 0
  for i in range(n - 2):
    if s[i] == "D":
      r += dmc(s[i:], k)[0]
  print(r)

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())
a = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

def counter(S, ki):
  count = 0
  for i in range(0, len(S)): 
    if S[i] != 'D':
      continue
    for j in range( i+2, len(S)):
      if j - i <=1 or j - i >= ki or S[j] != 'C':
        continue
      for l in range(i+1, j):
        if S == 'M'
          count += 1
  return count
  
for ki in k:
  print(counter(S, ki))

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline())
S = list(sys.stdin.readline())
Q = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split(' ')))

chache = []

oms = [(i, S[i]) for i in range(N) if S[i] == 'D' or S[i] == 'M' or S[i] == 'C']
oml = len(oms)

def process(ki, index, selected = 'n'):
    global cache

    if index == oml:
      return []

    if cache[index][selected] is not None:
        return cache[index][selected]

    rets = []
    char = oms[index][1]
    if selected == 'b':
        if char == 'C':
            rets.append(oms[index][0])
    elif selected == 'a':
        if char == 'M':
            rets += process(ki,index+1, 'b')
    else:
      if char == 'D':
          cind = process(ki,index+1, 'a')
          ret = []
          for v in cind:
               if v != False and ((v - oms[index][0]) < ki):
                ret.append(True)
          rets += ret

    rets += process(ki,index+1, selected)

    cache[index][selected] = rets
    return rets


for ki in k:
    cache = [{'a': None, 'b': None, 'c': None, 'n': None} for i in range(N)]
    ret = process(ki, 0)
    print(len(ret))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from functools import reduce

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s, max(ks))
    for k in ks:
        print(sum(dmcmap[:k]), flush=True)

def dmc(src, kmax):
    ret = [0 for _ in range(kmax)]

    for ind in range(len(src)):
        if src[ind] == 'D':
            for inm in range(ind+1, len(src)):
                if src[inm] == 'M':
                    for inc in range(inm+1, len(src)):
                        if src[inc] == 'C':
                            ret[inc-ind] += 1
    return ret

s, ks = load()
calc(s,ks)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split(" ")))

ans = 0
d = {0:0}
for i in range(n):
    if(s[i] == "D"):
        tmp = 0
        for j in range(i+1, n, 1):
            if(s[j] == "M"): tmp += 1
            if(s[j] == "C"):
                if(((j-i) in d) == True):
                    d[j-i] += tmp
                else: d[j-i] = tmp
            elif(((j-i) in d) == False): d[j-i] = 0
    break


#for i in range(1, n, 1):
#    d[i] += d[i-1]


for i in k:
    print(d[i-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from functools import reduce

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s, max(ks))
    for k in ks:
        print(sum(dmcmap[:k]))

def dmc(src, kmax):
    ret = [0 for _ in range(kmax)]

    for ind in range(len(src)):
        if src[ind] == 'D':
            for inm in range(ind+1, len(src)):
                if src[inm] == 'M':
                    for inc in range(inm+1, len(src)):
                        if src[inc] == 'C':
                            ret[inc-ind] += 1
    return ret

s, ks = load()
calc(s,ks)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from functools import reduce

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s, max(ks))
    for k in ks:
        print(sum(dmcmap[:k]))

def dmc(src, kmax):
    ret = [0 for _ in range(kmax)]

    for ind in range(len(src)):
        if src[ind] == 'D':
            for inm in range(ind+1, len(src)):
                if src[inm] == 'M':
                    for inc in range(inm+1, len(src)):
                        if src[inc] == 'C':
                            ret[inc-ind] += 1
    return ret

stdin = open('data.txt')
s, ks = load()
calc(s,ks)

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline())
S = list(sys.stdin.readline())
Q = int(sys.stdin.readline())
k = map(int, sys.stdin.readline().split(' '))

chache = []

def process(k, index, selected = 'n'):
    global cache

    if index == N:
      return []

    if cache[index][selected] is not None:
        return cache[index][selected]

    rets = []
    char = S[index]
    if selected == 'b':
        if char == 'C':
            rets.append(index)
    elif selected == 'a':
        if char == 'M':
            rets += process(k,index+1, 'b')
    else:
      if char == 'D':
          cind = process(k,index+1, 'a')
          ret = []
          for v in cind:
              if v != False and ((v - index) < k):
                ret.append(True)
          rets += ret

    rets += process(k,index+1, selected)

    cache[index][selected] = rets
    return rets


for ki in k:
    cache = [{'a': None, 'b': None, 'c': None, 'n': None} for i in range(N)]
    ret = process(ki, 0)
    print(len(ret))

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
q = int(input())
k_list = list(map(int,input().split()))

d_rec = []
m_rec = []
c_rec = []
for i, ss in enumerate(s):
    if ss == 'D':
        d_rec.append(i)
    if ss == 'M':
        m_rec.append(i)
    if ss == 'C':
        c_rec.append(i)
    

d_rec = np.array(d_rec)
m_rec = np.array(m_rec)
c_rec = np.array(c_rec)


dic = {}
for d in d_rec:
    for c in c_rec:
        if d > c:
            continue
        m = np.sum((m_rec < c) * (m_rec > d))
        if m > 0:
            try:
                dic[c - d] += m
            except:
                dic[c - d] = m

a = dic.keys()
a = np.array(list(a))

for k in k_list:
    key_here = a[a < k]
    su = 0
    for key in key_here:
        su += dic[key]
    print(su)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

N=int(input())
S=input()
Q=input()
k=list(map(int,input().split()))

arr=[]
flag=0
DRC=[0 for _ in range(N)]
flag=[0 for _ in range(N//2)]

for i,x in enumerate(S):
    if x=='D':
        arr.append(i)
    elif x=='M':
        for j in range(len(arr)):
            flag[j]+=1
    elif x=='C':
        for j,d in enumerate(arr):
            if flag[j]==0:
                break
            DRC[i-d]+=flag[j]

DRC=list(accumulate(DRC))

for x in k:
    print(DRC[x-1])

Submission status: Runtime Error

Solution code:
n, k = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))

b = []
for i in range(n):
    for j in range(i, n, 1):
        b.append(sum(a[i:j+1]))

b.sort(reverse=True)

ans = 0
for i in range(int(n*(n+1)/2)-k+1):
    tmp = b[i]
    for j in b[i:k]:
        tmp = tmp & j
    if(ans < tmp): ans = tmp

print(ans)