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: Time Limit Exceeded

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

N = int(input())
S = [ord(i) for i in input()]
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 68 :
                d -= 1
                dm -= m
            elif S[j] == 77 :
                m -= 1

        if S[i] == 68 :
            d += 1
        elif S[i] == 77 :
            m += 1
            dm += d
        elif S[i] == 67 :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
S = list(input())
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
S = input()[:-1]
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            T = S[i-ki]
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            T = S[i-ki]
            if T == 'D' :
                d -= 1
                dm -= m
            elif T == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    d, m, dm = 0, 0, 0
    for i in range(N) :
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                d -= 1
                dm -= m
            elif S[i-ki] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            ret += dm
            
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
k = [int(i) for i in input().split()]

for ki in k :
    ret = 0
    dp = [[0] * 3 for _ in range(ki)]
    for i in range(N) :
        j = i % ki
        dp[j][0] = dp[j-1][0]
        dp[j][1] = dp[j-1][1]
        dp[j][2] = dp[j-1][2]
        
        j = i % ki
        if i >= ki :
            if S[i-ki] == 'D' :
                dp[j][0] -= 1
                dp[j][2] -= dp[j][1]
            elif S[i-ki] == 'M' :
                dp[j][1] -= 1

        if S[i] == 'D' :
            dp[j][0] += 1
        elif S[i] == 'M' :
            dp[j][1] += 1
            dp[j][2] += dp[j][0]
        elif S[i] == 'C' :
            ret += dp[j][2]
            
    print(ret)

Submission status: Time Limit Exceeded

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())

D,M,C = [],[],[]
for i,s in enumerate(S):
    if s=="D":
        D.append(i+1)
    elif s=="M":
        M.append(i+1)
    elif s=="C":
        C.append(i+1)
if len(D)<len(C):
    D,C = [N+1-c for c in C],[N+1-d for d in D]
    M = [N+1-m for m in M]

cs = sp.cumsum
ans = sp.zeros(Q,sp.int64)
cntD = sp.zeros(N+1,sp.int64)
cntM = sp.zeros(N+1,sp.int64)
sumM = sp.zeros(N+1,sp.int64)
for i in D:
    cntD[i] = 1
cntD = cs(cntD)
for i in M:
    cntM[i] = 1
    sumM[i] = cntD[i]
cntM = cs(cntM)
sumM = cs(sumM)

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
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
D = sp.cumsum([s=="D" for s in S])
cntM = sp.cumsum([s=="M" for s in S])
sumM = sp.cumsum([d if s=="M" else 0 for s,d in zip(S,D)])
ans = sp.zeros(Q,int)

for i,s in enumerate(S[1:]):
    if s=="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: Time Limit Exceeded

Solution code:
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
D = sp.cumsum([s=="D" for s in S])
cntM = sp.cumsum([s=="M" for s in S])
sumM = sp.cumsum([d if s=="M" else 0 for s,d in zip(S,D)])
ans = sp.zeros(Q,int)

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

Submission status: Time Limit Exceeded

Solution code:
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()
"""

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)

Submission status: Time Limit Exceeded

Solution code:
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()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=list(input())
    q=int(input())
    k=list(map(int,input().split()))
    for p in k:
        d_l=[]
        m_l=[]
        l=0
        now=0
        d,m,a,ans=0,0,0,0
        for i in range(n):
            j=s[i]
            if j=="D":
                d+=1
                l+=1
                d_l.append(i)
                m_l.append(0)
            elif j=="C":
                ans+=a
            if l>now:
                if j=="M":
                    m+=1
                    a+=d
                    m_l[-1]+=1
                if d_l[now]==i-p+1:
                    d-=1
                    a-=m
                    m-=m_l[now]
                    now+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=list(input())
    q=int(input())
    k=list(map(int,input().split()))
    d_l=[]
    m_l=[]
    da=d_l.append
    ma=m_l.append
    for p in k:
        l=0
        now=0
        d,m,a,ans=0,0,0,0
        for i in range(n):
            j=s[i]
            if j=="D":
                d+=1
                l+=1
                da(i)
                ma(0)
            elif j=="C":
                ans+=a
            if l>now:
                if j=="M":
                    m+=1
                    a+=d
                    m_l[-1]+=1
                if d_l[now]==i-p+1:
                    d-=1
                    a-=m
                    m-=m_l[now]
                    now+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    q=int(input())
    k=list(map(int,input().split()))
    d_l=[]
    m_l=[]
    da=d_l.append
    ma=m_l.append
    for p in k:
        l=0
        now=0
        d,m,a,ans=0,0,0,0
        for i in range(n):
            j=s[i]
            if j=="D":
                d+=1
                l+=1
                da(i)
                ma(0)
            elif j=="C":
                ans+=a
            if l>now:
                if j=="M":
                    m+=1
                    a+=d
                    m_l[-1]+=1
                if d_l[now]==i-p+1:
                    d-=1
                    a-=m
                    m-=m_l[now]
                    now+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    t=input()
    q=int(input())
    k=list(map(int,input().split()))
    s=[]
    sa=s.append
    for i in t:
        if i=="D":
            sa(1)
        elif i=="M":
            sa(2)
        elif i=="C":
            sa(3)
        else:
            sa(0)
    d_l=[]
    m_l=[]
    da=d_l.append
    ma=m_l.append
    for p in k:
        l=0
        now=0
        d,m,a,ans=0,0,0,0
        for i,j in enumerate(s):
            if j==1:
                d+=1
                l+=1
                da(i)
                ma(0)
            elif j==3:
                ans+=a
            if l>now:
                if j==2:
                    m+=1
                    a+=d
                    m_l[-1]+=1
                if d_l[now]==i-p+1:
                    d-=1
                    a-=m
                    m-=m_l[now]
                    now+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    q=int(input())
    k=list(map(int,input().split()))
    #s=[]
    #for i in t:
    #    if i=="D":
    #        s.append(1)
    #    elif i=="M":
    #        s.append(2)
    #    elif i=="C":
    #        s.append(3)
    #    else:
    #        s.append(0)
    d_l=[]
    m_l=[]
    da=d_l.append
    ma=m_l.append
    for p in k:
        l=0
        now=0
        d,m,a,ans=0,0,0,0
        for i,j in enumerate(s):
            if j=="D":
                d+=1
                l+=1
                da(i)
                ma(0)
            elif j=="C":
                ans+=a
            if l>now:
                if j=="M":
                    m+=1
                    a+=d
                    m_l[-1]+=1
                if d_l[now]==i-p+1:
                    d-=1
                    a-=m
                    m-=m_l[now]
                    now+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    q=int(input())
    k=list(map(int,input().split()))
    d_l=[]
    m_l=[]
    da=d_l.append
    ma=m_l.append
    for p in k:
        l=0
        now=0
        d,m,a,ans=0,0,0,0
        for i in range(n):
            if s[i]=="D":
                d+=1
                l+=1
                da(i)
                ma(0)
            elif s[i]=="M":
                if l>now:
                    m+=1
                    a+=d
                    m_l[-1]+=1
            elif s[i]=="C":
                ans+=a
            if l>now:
                if d_l[now]==i-p+1:
                    d-=1
                    a-=m
                    m-=m_l[now]
                    now+=1
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    n=int(input())
    s=input()
    q=int(input())
    k=list(map(int,input().split()))
    for p in k:
        dm=deque([])
        d,m,a,ans=0,0,0,0
        for i in range(n):
            if s[i]=="D":
                d+=1
                dm.append([i,0])
            elif s[i]=="M":
                if len(dm)>0:
                    m+=1
                    a+=d
                    dm[-1][1]+=1
            elif s[i]=="C":
                ans+=a
            if len(dm)>0:
                if dm[0][0]==i-p+1:
                    d-=1
                    a-=m
                    m-=dm[0][1]
                    dm.popleft()
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

S = input()
Q = int(input())

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


for i in range(Q):

    ans = 0
    Dnum = 0
    Mnum = 0
    DMnum = 0

    for j in range(N):

        if j >= k[i]:

            if S[j - k[i]] == "D":
                Dnum -= 1
                DMnum -= Mnum

            elif S[j - k[i]] == "M":
                Mnum -= 1

        if S[j] == "D":
            Dnum += 1

        elif S[j] == "M":
            Mnum += 1
            DMnum += Dnum

        elif S[j] == "C":
            ans += DMnum

    print (ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
S = input().strip()
Q = int(input().strip())
K = list(map(int, input().strip().split()))
# print(N)
# print(S)
# print(Q)
# print(K)
# print()
for k in K:
    result = []
    total = 0
    for i in range(len(S)):
        if S[i] == 'D':
            for j in range(i, len(S)):
                if S[j] == 'M':
                    for m in range(j, len(S)):
                        if S[m] == 'C':
                            if m - i < k:
                                total += 1
                            # if [[S[i], i], [S[j], j], [S[m], m]] not in result and m - i < k:
                            #     result.append([[S[i], i], [S[j], j], [S[m], m]])
    # print(result)
    # print(len(result))
    print(total)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right

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

for K in Ks:
    # [D, M, DM, DMC]
    dp = [[0]*4 for _ in range(N+1)]
    for i in range(N):
        if i-K >= 0:
            sk = S[i-K]
            if sk == 'D':
                dp[i][0] -= 1
                dp[i][2] -= dp[i][1]
            elif sk == "M":
                dp[i][1] -= 1
        s = S[i]
        if s == "D":
            dp[i+1][0] = dp[i][0] + 1
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3]
        elif s == 'M':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1] + 1
            dp[i+1][2] = dp[i][2] + dp[i+1][0]
            dp[i+1][3] = dp[i][3]
        elif s == 'C':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3] + dp[i][2]
        else:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3]
    
    print(dp[N][3])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
D,M,C=map(ord,'DMC')
S=[ord(c) for c in input()]
input()
K=map(int,input().split())
for k in K:
    d,m,c,dm=0,0,0,0
    a=0
    for i,s in enumerate(S):
        if i>=k:
            if S[i-k]==D:
                d-=1
                dm-=m
            elif S[i-k]==M:
                m-=1
            elif S[i-k]==C:
                c-=1
        if s==D:
            d+=1
        elif s==M:
            m+=1
            dm+=d
        elif s==C:
            c+=1
            a+=dm
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
D,M,C,A=map(ord,'DMCA')
S=[ord(c)-A for c in input()]
Q=int(input())
K=list(map(int,input().split()))
DMC=[D-A,M-A,C-A]
for k in K:
    dmc=[0,0,0]
    dm=0
    a=0
    for i,s in enumerate(S):
        if i>=k:
            if S[i-k] in DMC:
                m=DMC.index(S[i-k])
                dmc[m]-=1
                if m==0:
                    dm-=dmc[1]
        if s in DMC:
            p=DMC.index(s)
            dmc[p]+=1
            if p==1:
                dm+=dmc[0]
            if p==2:
                a+=dm
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
dp_D,dp_M=[0]*(N+1),[0]*(N+1)
dp_DM=[0]*(N+1)
C=[]

for i in range(N):
  dp_D[i+1]=dp_D[i]
  dp_M[i+1]=dp_M[i]
  dp_DM[i+1]=dp_DM[i]
  if S[i]=="D":
    dp_D[i+1]+=1
  if S[i]=="M":
    dp_M[i+1]+=1
    dp_DM[i+1]+=dp_D[i]
  if S[i]=="C":
    C.append(i+1)
    
Q=int(input())
K=[int(k) for k in input().split()]
for k in K:
  ans=0
  for c in C:
    ans+=dp_DM[c-1]-dp_D[max(c-k,0)]*(dp_M[c-1]-dp_M[max(c-k,0)])-dp_DM[max(c-k,0)]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    s = [ord(c) for c in input()[:-1]]
    q = int(input())
    kk = list(map(int, input().split()))
    od = ord("D")
    om = ord("M")
    oc = ord("C")
    for k in kk:
        ans = 0
        d = 0
        m = 0
        dm = 0
        for i, a in enumerate(s):
            if a == od: d += 1
            elif a == om:
                m += 1
                dm += d
            if i - k >= 0:
                l = s[i - k]
                if l == od:
                    d -= 1
                    dm -= m
                elif l == om:
                    m -= 1
            if a == oc:
                ans += dm
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    s = [ord(c) for c in input()[:-1]]
    q = int(input())
    kk = list(map(int, input().split()))
    od = ord("D")
    om = ord("M")
    oc = ord("C")
    for k in kk:
        ans = 0
        d = 0
        m = 0
        dm = 0
        for i, a in enumerate(s):
            if a == od: d += 1
            if a == om:
                m += 1
                dm += d
            if i - k >= 0:
                l = s[i - k]
                if l == od:
                    d -= 1
                    dm -= m
                if l == om:
                    m -= 1
            if a == oc:
                ans += dm
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()[:-1]
    q = int(input())
    kk = list(map(int, input().split()))
    for k in kk:
        ans = 0
        d = 0
        m = 0
        dm = 0
        for i, c in enumerate(s):
            if c == "D": d += 1
            if c == "M":
                m += 1
                dm += d
            if i - k >= 0:
                l = s[i - k]
                if l == "D":
                    d -= 1
                    dm -= m
                if l == "M":
                    m -= 1
            if c == "C":
                ans += dm
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()[:-1]
    q = int(input())
    kk = list(map(int, input().split()))
    cnt_m = [0] * (n + 1)
    cnt = 0
    for i, c in enumerate(s):
        cnt_m[i] = cnt
        if c == "M": cnt += 1
    cnt_m[-1] = cnt
    # print(cnt_m)
    for k in kk:
        ans = 0
        for i, c0 in enumerate(s):
            if c0 != "D": continue
            for j in range(i + 2, min(i + k, n)):
                if s[j] == "C":
                    ans += cnt_m[j] - cnt_m[i]
        print(ans)

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input()
    _q = int(input())
    
    for k in map(int,input().split()):
        res = 0
        p = 0
        cnt = 0
        q = 0
        for i in range(n):
            if i >= k:
                if s[i-k] == 'D':
                    cnt -= 1
                    p -= q
                elif s[i-k] == 'M':
                    q -= 1

            if s[i] == 'D':
                cnt += 1
            elif s[i] == 'M':
                p += cnt
                q += 1
            elif s[i] == 'C':
                res += p
        print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        D=M=DM=C=0
        for i, c in enumerate(s):
            if c == "D":
                D += 1
            elif c == "M":
                M += 1
                DM += D
            if i >= ki:
                j = i-ki
                if s[j] == "D":
                    D -= 1
                    DM -= M
                elif s[j] == "M":
                    M -= 1
            if c == "C":
                C += DM
        print(C)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        D=M=DM=C=0
        for i, c in enumerate(s):
            if c == "D":
                D += 1
            elif c == "M":
                M += 1
                DM += D
            elif c == "C":
                C += DM
            if i >= ki-1:
                j = i-ki+1
                if s[j] == "D":
                    D -= 1
                    DM -= M
                elif s[j] == "M":
                    M -= 1
        print(C)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
def solve(ki):
    D=M=DM=C=0
    for i, c in enumerate(s):
        if c == "D":
            D += 1
        elif c == "M":
            M += 1
            DM += D
        elif c == "C":
            C += DM
        if i >= ki-1:
            j = i-ki+1
            if s[j] == "D":
                D -= 1
                DM -= M
            elif s[j] == "M":
                M -= 1
    return C
for ki in k:
    print(solve(ki))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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, c in enumerate(s):
    for i in range(n):
        c = s[i]
        if c == "D":
            DMC[0] += 1
        elif c == "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: Time Limit Exceeded

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, c in enumerate(s):
        if c == "D":
            DMC[0] += 1
        elif c == "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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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