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.buffer.readline

def main():
    N = int(input())
    S = input()
    Q = input()
    
    def count(k):
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            st = S[i]
            if st == "D":
                d += 1
            elif st == "M":
                m += 1
                dm += d
            elif st == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        return dmc
        
    x = list(map(int,input().split()))
    for k in x:
        print(count(k))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

N = ir()
S = sr()
Q = ir()
K = lr()
for k in K:
    answer = 0
    dp = [0, 0, 0] # 'D', 'M', count of M
    for i in range(N):
        s = S[i]
        if i >= k:
            t = S[i-k]
            if t == 'D':
                dp[0] -= 1
                if dp[2] > 0:
                    dp[1] -= dp[2]
            elif t == 'M':
                dp[2] -= 1
        if s == 'D':
            dp[0] += 1
        elif s == 'M':
            dp[1] += dp[0]
            dp[2] += 1
        elif s == 'C':
            answer += dp[1]        
    print(answer)        
# 50

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

# dp クエリには累積和を用意しておく
N = ir()
S = sr()
Q = ir()
K = lr()
dp_D = np.array([], np.int64)
dp_M = np.array([], np.int64)
cnt = np.zeros(N, np.int64)
for i in range(N):
    s = S[i]
    dp_D += 1
    dp_M += 1
    #print(s)
    if s == 'D':
        dp_D = np.append(dp_D, 0)
        #print(dp_D)
    elif s == 'M':        
        dp_M = np.concatenate([dp_M, dp_D])
    elif s == 'C':
        A = np.zeros(N, np.int64)
        #print(np.bincount(dp_M))
        B = np.bincount(dp_M)
        A[:len(B)] += B
        cnt += A

cnt_cum = cnt.cumsum()
#print(dp_D)
#print(cnt_cum)
for k in K:
    print(cnt_cum[k-1])
#

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input()
    _ = int(input())
    K = [int(i) for i in input().split()]

    def solve(k):
        cd = 0
        cm = 0
        cdm = 0
        ans = 0
        for i in range(N):
            if S[i] == 'D':
                cd += 1
            elif S[i] == 'M':
                cm += 1
                cdm += cd
            elif S[i] == 'C':
                ans += cdm
            if k - 1 <= i:
                if S[i-k+1] == 'D':
                    cdm -= cm
                    cd -= 1
                if S[i-k+1] == 'M':
                    cm -= 1
        return ans

    for k in K:
        print(solve(k))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [s for s in input()]
    _ = int(input())
    K = [int(i) for i in input().split()]

    def solve(k):
        cnt = {'D': 0, 'M': 0, 'DM': 0}
        ans = 0
        for i in range(N):
            if S[i] == 'D':
                cnt['D'] += 1
            elif S[i] == 'M':
                cnt['M'] += 1
                cnt['DM'] += cnt['D']
            elif S[i] == 'C':
                ans += cnt['DM']
            if k - 1 <= i:
                if S[i-k+1] == 'D':
                    cnt['DM'] -= cnt['M']
                    cnt['D'] -= 1
                if S[i-k+1] == 'M':
                    cnt['M'] -= 1
        return ans

    for k in K:
        print(solve(k))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n=int(input())
s=[ord(i)for i in input()]
t=[-1]*n
for i in range(n):
  if s[i]==68:
    t[i]=0
  elif s[i]==77:t[i]=1
  elif s[i]==67:t[i]=2

def solve(k):
  dd=mm=dm=dmc=0
  for i in range(n):
    if t[i]==0:dd+=1
    if i>=k and t[i-k]==0:dm-=mm;dd-=1
    if t[i]==1:dm+=dd;mm+=1
    if i>=k and t[i-k]==1:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
s=[ord(i)for i in input()]
t=[-1]*n
for i in range(n):
  if s[i]==68:
    t[i]=0
  elif s[i]==77:t[i]=1
  elif s[i]==67:t[i]=2

def solve(k):
  d_p=[0]*2*n
  d_m=[0]*2*n
  m_p=[0]*2*n
  m_m=[0]*2*n
  dd=mm=dm=dmc=0
  for i in range(n):
    if t[i]==0:dd+=1
    if i>=k and t[i-k]==0:dm-=mm;dd-=1
    if t[i]==1:dm+=dd;mm+=1
    if i>=k and t[i-k]==1:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[ord(i)for i in input()]
t=[-1]*n
for i in range(n):
  if s[i]==68:
    t[i]=0
  elif s[i]==77:t[i]=1
  elif s[i]==67:t[i]=2

def solve(k):
  d_p=[0]*2*n
  d_m=[0]*2*n
  m_p=[0]*2*n
  m_m=[0]*2*n
  dd=mm=dm=dmc=0
  for i in range(n):
    if t[i]==0:dd+=1
    if i>=k and t[i-k]==0:dm-=mm;dd-=1
    if t[i]==1:dm+=dd;mm+=1
    if i>=k and t[i-k]==1:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
t=[-1]*n
for i in range(n):
  if s[i]=="D":t[i]=0
  elif s[i]=="M":t[i]=1
  elif s[i]=="C":t[i]=2

def solve(k):
  d_p=[0]*2*n
  d_m=[0]*2*n
  m_p=[0]*2*n
  m_m=[0]*2*n
  for i in range(n):
    if t[i]==0:
      d_p[i]+=1
      d_m[i+k]-=1
    if t[i]==1:
      m_p[i]+=1
      m_m[i+k]-=1
  dd=mm=dm=dmc=0
  for i in range(n):
    if d_p[i]:dd+=1
    if d_m[i]:dm-=mm;dd-=1
    if m_p[i]:dm+=dd;mm+=1
    if m_m[i]:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l1 = 0
    l2 = 0
    l3 = 0
    for j in range(n):
        a = s[j-k1]
        b = s[j]
        if j >= k1:
            if a == "D":
                l1 -= 1
                l2 -= l3
            elif a == "M":
                l3 -= 1
        if b == "D":
            l1 += 1
        elif b == "M":
            l2 += l1
            l3 += 1
        elif b == "C":
            ans += l2
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l1 = 0
    l2 = 0
    l3 = 0
    for j in range(n):
        a = s[j-k1]
        b = s[j]
        if j >= k1:
            if a == "D":
                l1 -= 1
                l2 -= l3
            elif a == "M":
                l3 -= 1
        if b == "D":
            l1 += 1
        elif b == "M":
            l2 += l1
            l3 += 1
        elif b == "C":
            ans += l2
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l1 = 0
    l2 = 0
    l3 = 0
    for j in range(n):
        a = s[j-k1]
        b = s[j]
        if j >= k1:
            if a == "D":
                l1 -= 1
                l2 -= l3
            elif a == "M":
                l3 -= 1
        if b == "D":
            l1 += 1
        elif b == "M":
            l2 += l1
            l3 += 1
        elif b == "C":
            ans += l2
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l1 = 0
    l2 = 0
    l3 = 0
    for j in range(n):
        if j >= k1:
            if s[j-k1] == "D":
                l1 -= 1
                l2 -= l3
            elif s[j-k1] == "M":
                l3 -= 1
        if s[j] == "D":
            l1 += 1
        elif s[j] == "M":
            l2 += l1
            l3 += 1
        elif s[j] == "C":
            ans += l2
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
d = []
m = []
c = []
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l1 = 0
    l2 = 0
    l3 = 0
    for j in range(n):
        if j >= k1:
            if s[j-k1] == "D":
                l1 -= 1
                l2 -= l3
            elif s[j-k1] == "M":
                l3 -= 1
        if s[j] == "D":
            l1 += 1
        elif s[j] == "M":
            l2 += l1
            l3 += 1
        elif s[j] == "C":
            ans += l2
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
d = []
m = []
c = []
for i in range(n):
    if s[i] == "D":
        d.append(i)
    elif s[i] == "M":
        m.append(i)
    elif s[i] == "C":
        c.append(i)
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l1 = 0
    l2 = 0
    l3 = 0
    for j in range(n):
        if j >= k1:
            if s[j-k1] == "D":
                l1 -= 1
                l2 -= l3
            elif s[j-k1] == "M":
                l3 -= 1
        if s[j] == "D":
            l1 += 1
        elif s[j] == "M":
            l2 += l1
            l3 += 1
        elif s[j] == "C":
            ans += l2
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
d = []
m = []
c = []
for i in range(n):
    if s[i] == "D":
        d.append(i)
    elif s[i] == "M":
        m.append(i)
    elif s[i] == "C":
        c.append(i)
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l = [0,0,0]
    for j in range(n):
        if j >= k1:
            if s[j-k1] == "D":
                l[0] -= 1
                l[1] -= l[2]
            elif s[j-k1] == "M":
                l[2] -= 1
        if s[j] == "D":
            l[0] += 1
        elif s[j] == "M":
            l[1] += l[0]
            l[2] += 1
        elif s[j] == "C":
            ans += l[1]
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
s = list(input())
q = int(input())
k = list(map(int,input().split()))
d = []
m = []
c = []
for i in range(n):
    if s[i] == "D":
        d.append(i)
    elif s[i] == "M":
        m.append(i)
    elif s[i] == "C":
        c.append(i)
al = []
for i in range(q):
    ans = 0
    k1 = k[i]
    l = [0,0]
    for j in range(n):
        if j >= k1:
            if s[j-k1] == "D":
                l[0] -= 1
                a0 = bisect.bisect_left(m,j-k1)
                a1 = bisect.bisect_left(m,j)
                l[1] -= (a1-a0)
        if s[j] == "D":
            l[0] += 1
        elif s[j] == "M":
            l[1] += l[0]
        elif s[j] == "C":
            ans += l[1]
        
        #print(l)
    al.append(ans)
for i in al:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ss = input()
    Q = int(input())
    ks = list(map(int, input().split()))

    anss = []
    for k in ks:
        numD = numM = numDM = numDMC = 0
        for i in range(N):
            S = Ss[i]
            if S == 'D':
                numD += 1
            elif S == 'M':
                numM += 1
                numDM += numD
            elif S == 'C':
                numDMC += numDM

            if i >= k-1:
                S = Ss[i-k+1]
                if S == 'D':
                    numD -= 1
                    numDM -= numM
                elif S == 'M':
                    numM -= 1

        anss.append(numDMC)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Ss = input()
Q = int(input())
ks = list(map(int, input().split()))

anss = []
for k in ks:
    numD = numM = numDM = numDMC = 0
    for i, S in enumerate(Ss):
        if S == 'D':
            numD += 1
        elif S == 'M':
            numM += 1
            numDM += numD
        elif S == 'C':
            numDMC += numDM

        if i >= k-1:
            S = Ss[i-k+1]
            if S == 'D':
                numD -= 1
                numDM -= numM
            elif S == 'M':
                numM -= 1
            elif S == 'C':
                pass

    anss.append(numDMC)

print('\n'.join(map(str, anss)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Ss = input()
Q = int(input())
ks = list(map(int, input().split()))

anss = []
for k in ks:
    numD = numM = numDM = numDMC = 0
    for i, S in enumerate(Ss):
        if S == 'D':
            numD += 1
        elif S == 'M':
            numM += 1
            numDM += numD
        elif S == 'C':
            numDMC += numDM

        if i >= k-1:
            S = Ss[i-k+1]
            if S == 'D':
                numD -= 1
                numDM -= numM
            elif S == 'M':
                numM -= 1
            elif S == 'C':
                pass

    anss.append(numDMC)

print('\n'.join(map(str, anss)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for i in kl:
    k=i
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for i in kl:
    k=i
    d=0
    m=0
    dm=0
    ans=0
    j=0
    for lj in l:
        if lj=='D':
            d+=1
        elif lj=='M':
            m+=1
            dm+=d
        elif lj=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            if l[j-k+1]=='M':
                m-=1
        j+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for i in kl:
    k=i
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            if l[j-k+1]=='M':
                m-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=tuple(input())
q=int(input())
kl=tuple(map(int,input().split()))
for i in range(q):
    k=kl[i]
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            if l[j-k+1]=='M':
                m-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説を見た
# よく理解していない

def main():
    n = int(input())
    s = input()
    q = int(input())
    *ks, = map(int, input().split())

    for k in ks:
        cnt = 0
        d, m, dm = 0, 0, 0
        for char in s[:k]:
            if char == 'D':
                d += 1
            elif char == 'M':
                m += 1
                dm += d
            elif char == 'C':
                cnt += dm

        for p_char, char in zip(s, s[k:]):
            if p_char == 'D':
                dm -= m
                d -= 1
            elif p_char == 'M':
                m -= 1

            if char == 'D':
                d += 1
            elif char == 'M':
                m += 1
                dm += d
            elif char == 'C':
                cnt += dm

        print(cnt)


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 shakutori(N,S,k):
    out=0
    cntM=[0]*N
    for i in range(N):
        if S[i]=='M':
            cntM[i]+=1+cntM[i-1]
        else:
            cntM[i]=cntM[i-1]
    #print(cntM)
    for a in range(N):
        if S[a]=='D':
            for c in range(a+1, a+k):
                if c<N and S[c]=='C':
                    out+=cntM[c]-cntM[a]
    return out

for i in range(Q):
    print(shakutori(N,S,K[i]))

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i in range(N):
            s = S[i]
            if s == "D":
                D += 1
            elif s == "M":
                M += 1
                now += D
            elif s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                elif S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
#        ans.append(C)
        print(C)
#    for v in ans:
#        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i, s in enumerate(S):
            if s == "D":
                D += 1
            elif s == "M":
                M += 1
                now += D
            elif s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                elif S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
#        ans.append(C)
        print(C)
#    for v in ans:
#        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i, s in enumerate(S):
            if s == "D":
                D += 1
            if s == "M":
                M += 1
                now += D
            if s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                if S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
        ans.append(C)
    for v in ans:
        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (len(c) + 1)
ls = [0] * N
for i in range(len(c)):
  ccs[i + 1] = ccs[i] + cs[c[i]]
for i in range(N):
  if S[i] == "D": ls[i] = bl(c, i)

#print(c, ccs)
#print(d)
for k in qs:
  res = 0
  for i in d:
    l = ls[i]
    r = bl(c, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (r - l))
  print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (len(c) + 1)
for i in range(len(c)):
  ccs[i + 1] = ccs[i] + cs[c[i]]
#print(c, ccs)
for k in qs:
  res = 0
  for i in d:
    if S[i] != "D": continue
    l = bl(c, i)
    r = bl(c, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (r - l))
  print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
ccs = [0] * (len(c) + 1)
for i in range(len(c)):
  ccs[i + 1] = ccs[i] + cs[c[i]]
#print(c, ccs)
for k in qs:
  res = 0
  for i in range(N):
    if S[i] != "D": continue
    l = bl(c, i)
    r = bl(c, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (r - l))
  print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
ks = list(map(int, input().split()))
for k in ks:
	ans = 0
	d, m, cnt = 0, 0, 0
	for i in range(n):
		t = s[i]
		if i >= k:
			if s[i-k] == "D":
				cnt -= m
				d -= 1
			elif s[i-k] == "M":
				m -= 1

		if t == "D":
			d += 1
		elif t == "M":
			m += 1
			cnt += d
		elif t == "C":
			ans += cnt
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i in range(n,n*2):
    x,y = s[i],s[i-k]
    if y == 68:
      d -= 1
      dm -= m
    elif y == 77:
      m -= 1
    if x == 68:
      d += 1
    elif x == 77:
      m += 1
      dm += d
    elif x == 67:
      dmc += dm
  return dmc

def main():
  n = int(input())
  s = [0]*n + list(map(ord, list(input())))
  _ = input()
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()

Submission status: Time Limit Exceeded

Solution code:
def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i,j in zip(s[n:],s[n-k:]):
    if j == 1:
      d -= 1
      dm -= m
    elif j == 2:
      m -= 1
    if i == 1:
      d += 1
    elif i == 2:
      m += 1
      dm += d
    elif i == 3:
      dmc += dm
  return dmc

def main():
  n = int(input())
  t = input()
  _ = input()
  s = [0]*n + [(x=='D') + (x=='M')*2 + (x=='C')*3 for x in t]
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = input()
_ = input()
mk = str.maketrans('DMCYQWERTUIOPASFGHJKLZXVBN','123' + '0'*23)
s = [0]*n + list(map(int, list(t.translate(mk))))

l = list(map(int, input().split()))
for k in l:
  d,m,dm,dmc = 0,0,0,0
  for i,j in zip(s[n:],s[n-k:]):
    if j == 1:
      d -= 1
      dm -= m
    elif j == 2:
      m -= 1
    if i == 1:
      d += 1
    elif i == 2:
      m += 1
      dm += d
    elif i == 3:
      dmc += dm
  print(dmc)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = input()
q = int(input())
s = [0]*(n*2)
for i in range(n):
  if t[i] == 'D':
    s[i+n] = 1
  elif t[i] == 'M':
    s[i+n] = 2
  elif t[i] == 'C':
    s[i+n] = 3

l = list(map(int, input().split()))
for k in l:
  d,m,dm,dmc = 0,0,0,0
  for i in range(n,n*2):
    j = i-k
    if s[j] == 1:
      d -= 1
      dm -= m
    elif s[j] == 2:
      m -= 1
    if s[i] == 1:
      d += 1
    elif s[i] == 2:
      m += 1
      dm += d
    elif s[i] == 3:
      dmc += dm
  print(dmc)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = input()
s = [0]*n
for i in range(n):
  if t[i] == 'D':
    s[i] = 1
  elif t[i] == 'M':
    s[i] = 2
  elif t[i] == 'C':
    s[i] = 3
_ = input()
l = list(map(int, input().split()))
for k in l:
  d,m,dm,dmc = 0,0,0,0
  for i in range(n):
    if i > k-1:
      j = i-k
      if s[j] == 1:
        d -= 1
        dm -= m
      elif s[j] == 2:
        m -= 1
    if s[i] == 1:
      d += 1
    elif s[i] == 2:
      m += 1
      dm += d
    elif s[i] == 3:
      dmc += dm
  print(dmc)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
_ = input()
l = list(map(int, input().split()))
for k in l:
  d,m,dm,dmc = 0,0,0,0
  for i in range(n):
    if i > k-1:
      j = i-k
      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':
      dmc += dm
  print(dmc)

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_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]



    for k in K:
        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
        print (c)                


if __name__ == "__main__":
    main()