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:
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1                
    return ans
for i in k:
    print(search(i))

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int,input().split()))
    k = [[x,i] for i,x in enumerate(k)]
    k.sort()

    ans = [[0,-1] for i in range(q)]
    for i in range(q):
        ans[i][1] = k[i][1]

    def search(x):
        ind = x
        m = 0
        c = 0
        count = 0
        for num,i in enumerate(k):
            while ind+count < n and count < i[0]:
                if s[ind+count] == "M":
                    m += 1
                elif s[ind+count] == "C":
                    c += 1
                    ans[num][0]+=m
                count += 1
        
    for i in range(n):
        if s[i] == "D":
            search(i)

    for i in range(1,q):
        ans[i][0] += ans[i-1][0]
    ans.sort(key=lambda x: x[1])
    for i,j in ans:
        print(i)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))
k = [[x,i] for i,x in enumerate(k)]
k.sort()

ans = [[0,-1] for i in range(q)]
for i in range(q):
    ans[i][1] = k[i][1]

def search(x):
    ind = x
    m = 0
    c = 0
    count = 0
    for num,i in enumerate(k):
        while ind+count < n and count < i[0]:
            if s[ind+count] == "M":
                m += 1
            elif s[ind+count] == "C":
                c += 1
                ans[num][0]+=m
            count += 1
    
for i in range(n):
    if s[i] == "D":
        search(i)

for i in range(1,q):
    ans[i][0] += ans[i-1][0]
ans.sort(key=lambda x: x[1])
for i,j in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))
k = [[x,i] for i,x in enumerate(k)]
k.sort()
MAX = k[-1][0]
ans = [[0,-1] for i in range(q)]
for i in range(q):
    ans[i][1] = k[i][1]

def search(x):
    ind = x
    m = 0
    c = 0
    count = 0
    for num,i in enumerate(k):
        while ind+count < n and count < i[0]:
            if s[ind+count] == "M":
                m += 1
            elif s[ind+count] == "C":
                c += 1
                ans[num][0]+=m
            count += 1
    
for i in range(n):
    if s[i] == "D":
        search(i)

for i in range(1,q):
    ans[i][0] += ans[i-1][0]
ans.sort(key=lambda x: x[1])
for i,j in ans:
    print(i)

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))

    # print(s)

    for i in range(q):
        ans = 0
        k = K[i]
        D = [[0] * 3 for j in range(n)]
        for j in range(n):
            D[j][:] = D[j-1][:]

            if j-k >= 0:
                if s[j-k] == "D":
                    D[j][0] -= 1
                    D[j][2] -= D[j][1]
                elif s[j-k] == "M":
                    D[j][1] -= 1

            if s[j] == "D":
                D[j][0] += 1
            elif s[j] == "M":
                D[j][1] += 1
                D[j][2] += D[j][0]
            elif s[j] == "C":
                ans += D[j][2]
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
q = int(input())
K = list(map(int,input().split()))

# print(s)

for i in range(q):
    ans = 0
    k = K[i]
    D = [[0] * 3 for j in range(n)]
    for j in range(n):
        D[j][:] = D[j-1][:]

        if j-k >= 0:
            if s[j-k] == "D":
                D[j][0] -= 1
                D[j][2] -= D[j][1]
            elif s[j-k] == "M":
                D[j][1] -= 1

        if s[j] == "D":
            D[j][0] += 1
        elif s[j] == "M":
            D[j][1] += 1
            D[j][2] += D[j][0]
        elif s[j] == "C":
            ans += D[j][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 i in range(q):
    ans = 0
    k = K[i]
    D = [[0] * 3 for j in range(n)]
    for j in range(n):
        D[j][:] = D[j-1][:]

        if j-k >= 0:
            if s[j-k] == "D":
                D[j][0] -= 1
                D[j][2] -= D[j][1]
            elif s[j-k] == "M":
                D[j][1] -= 1

        if s[j] == "D":
            D[j][0] += 1
        elif s[j] == "M":
            D[j][1] += 1
            D[j][2] += D[j][0]
        elif s[j] == "C":
            ans += D[j][2]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

lc = [1 if s=="C" else 0 for s in S]
ld = [1 if s=="D" else 0 for s in S]

ac = [0]*(N+1)
for i in range(1, N+1):
    ac[i] = ac[i-1] + lc[i-1]

ans = 0

for a in k:
    ans = 0
    for i, s in enumerate(S):
        if s!="M":
            continue
        for j in range(max(i-a, 0), i):
            ans += ld[j]*(ac[min(a+j, N)]-ac[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


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

l = [1 if s=="C" else 0 for s in S]
tree = SegTree(N, 0)
tree.set_list(l)

ans = 0

for a in k:
    ans = 0
    for i, s in enumerate(S):
        if s!="M":
            continue
        for j in range(max(i-a, 0), i):
            if S[j]=="D":
                ans += tree.get(i, min(a+j, N))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
q = int(input())
K = list(map(int, input().split()))
for k in K:
  d = 0
  m = 0
  dm = 0
  dmc = 0
  for s in S[:k-1]:
    if s == "D":
      d += 1
    elif s == "M":
      m += 1
      dm += d
    elif s == "C":
      dmc += dm
  for s,e in zip(S[k-1:],S):
    if s == "D":
      d += 1
    elif s == "M":
      m += 1
      dm += d
    elif s == "C":
      dmc += dm
    if e == "D":
      d -= 1
      dm -= m
    elif e == "M":
      m -= 1
  print(dmc)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  S = input()
  q = int(input())
  K = list(map(int, input().split()))
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
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 k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for i,s in enumerate(S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      end = i - k + 1
      if end >= 0:
        e = S[end]
        if e == "D":
          d -= 1
          dm -= m
        elif e == "M":
          m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for k in K:
    res = 0
    D = deque()
    M = deque()
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            D.append(i)
        elif S[i] == 'M':
            dm += len(D)
            if D:
                M.append(i)
        elif S[i] == 'C':
            res += dm
        if D and D[0] + k <= i + 1:
            D.popleft()
            dm -= len(M)
            if D:
                while M and D[0] > M[0]:
                    M.popleft()
            else:
                M = deque()
                dm = 0

    print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for k in K:
    res = 0
    D = deque()
    M = deque()
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            D.append(i)
        if S[i] == 'M':
            dm += len(D)
            if D:
                M.append(i)
        if S[i] == 'C':
            res += dm
        if D and D[0] + k <= i + 1:
            d = D.popleft()
            dm -= len(M)
            if D:
                while M and D[0] > M[0]:
                    M.popleft()
            else:
                M = deque()
                dm = 0

    print(res)

Submission status: Time Limit Exceeded

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

N = int(input())
S = [ord(c) for c in input().rstrip()]
Q = int(input())
k = list(map(int, input().split()))

dd = ord('D')
mm = ord('M')
cc = ord('C')

for l in k:
    D = M = tmp = ans = 0
    for i in range(N):
        if i >= l:
            if S[i-l] == dd:
                tmp -= M
                D -= 1
            if S[i-l] == mm:
                M -= 1
        if S[i] == dd:
            D += 1
        if S[i] == mm:
            M += 1
            tmp += D
        if S[i] == cc:
            ans += tmp
    print(ans)

Submission status: Time Limit Exceeded

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

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

for l in k:
    D = 0
    M = 0
    tmp = 0
    ans = 0
    for i in range(N):
        if i >= l:
            if S[i-l] == 'D':
                tmp -= M
                D -= 1
            if S[i-l] == 'M':
                M -= 1
        if S[i] == 'D':
            D += 1
        if S[i] == 'M':
            M += 1
            tmp += D
        if S[i] == 'C':
            ans += tmp
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
K=list(map(int,input().split()))
for _ in range(Q):
    k=K[_]
    d=0
    m=0
    dm=0
    ans=0
    for i in range(0,N-1):
        d+=(S[i]=="D")
        m+=(S[i]=="M")
        dm+=d*(S[i]=="M")
        d-=(i>k-2)*(S[i+1-k]=="D")
        dm-=(i>k-2)*m*(S[i+1-k]=="D")
        m-=(i>k-2)*(S[i+1-k]=="M")
        ans+=dm*(S[i+1]=="C")
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,S,Q,*k = open(0).read().split()
N,Q = map(int, (N,Q))
K = map(int, k)
for k in K:
  D = 0
  M = 0
  DM = 0
  DMC = 0
  for i in range(k):
    if S[i]=='D':
      D += 1
    elif S[i]=='M':
      DM += D
      M += 1
    elif S[i]=='C':
      DMC += DM
  for i in range(N-k):
    if S[i]=='D':
      DM -= M
      D -= 1
    elif S[i]=='M':
      M -= 1
    if S[i+k]=='D':
      D += 1
    elif S[i+k]=='M':
      DM += D
      M += 1
    elif S[i+k]=='C':
      DMC += DM
  print(DMC)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
K=list(map(int,input().split()))
for _ in range(Q):
    k=K[_]
    DM=[0 for i in range(0,N)]
    d=0
    m=0
    dm=0
    for i in range(0,N):
        d+=(S[i]=="D")
        m+=(S[i]=="M")
        dm+=d*(S[i]=="M")
        if i>k-2:
            d-=(S[i+1-k]=="D")
            dm-=m*(S[i+1-k]=="D")
            m-=(S[i+1-k]=="M")
        DM[i]=dm
    ans=0
    for i in range(1,N):
        ans+=DM[i-1]*(S[i]=="C")
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
Q=int(input())
K=list(map(int,input().split()))
for _ in range(Q):
    k=K[_]
    DM=[0 for i in range(0,N)]
    d=0
    m=0
    dm=0
    for i in range(0,N):
        if S[i]=="D":
            d+=1
        if S[i]=="M":
            m+=1
            dm+=d
        if i>k-2:
            if S[i+1-k]=="D":
                d-=1
                dm-=m
            if S[i+1-k]=="M":
                m-=1
        DM[i]=dm
    ans=0
    for i in range(1,N):
        if S[i]=="C":
            ans+=DM[i-1]
    print(ans)

Submission status: Time Limit Exceeded

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

def count_DMC(k):
  num_d = [0] * (N+1)
  num_m = [0] * (N+1)
  num_dm = [0] * (N+1)
  res = 0
  for i, s in enumerate(S, 1):
    num_d[i] += num_d[i-1]
    num_m[i] += num_m[i-1]
    num_dm[i] += num_dm[i-1]
    if i - k - 1 >= 0 and S[i-k-1]=='D':
      num_dm[i] -= num_m[i]
    if s == 'D':
      num_d[i] += 1
      if i + k <= N:
        num_d[i+k] -= 1
    if s == 'M':
      num_m[i] += 1
      if i + k <= N:
        num_m[i+k] -= 1
      num_dm[i] += num_d[i]
    if s == 'C':
      res += num_dm[i]
  return res

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

n = int(input())
sl = input()
q = int(input())
kl = tuple(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数

    d = m = dm = ans = 0
    for i in range(n):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if sl[i] == "D":
            d += 1
        if sl[i] == "M":
            m += 1
            dm += d
        if sl[i] == "C":
            ans += dm

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    sl = list(input())
    sl.pop()

    q = int(input())
    kl = tuple(map(int,input().split()))

    for k in kl:
        # i文字目までのdとmとdmの数

        d = m = dm = ans = 0
        for i in range(n):
            if i - k >= 0:
                if sl[i-k] == "D":
                    d -= 1
                    dm -= m
                if sl[i-k] == "M":
                    m -= 1
            if sl[i] == "D":
                d += 1
            if sl[i] == "M":
                m += 1
                dm += d
            if sl[i] == "C":
                ans += dm

        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    sl = list(input())
    sl.pop()

    q = int(input())
    kl = list(map(int,input().split()))

    for k in kl:
        # i文字目までのdとmとdmの数

        d = m = dm = ans = 0
        for i in range(n):
            if i - k >= 0:
                if sl[i-k] == "D":
                    d -= 1
                    dm -= m
                if sl[i-k] == "M":
                    m -= 1
            if sl[i] == "D":
                d += 1
            if sl[i] == "M":
                m += 1
                dm += d
            if sl[i] == "C":
                ans += dm

        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())
sl.pop()

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = m = dm = ans = 0
    for i in range(n):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if sl[i] == "D":
            d += 1
        if sl[i] == "M":
            m += 1
            dm += d
        if sl[i] == "C":
            ans += dm

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = m = dm = ans = 0
    for i in range(n):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if sl[i] == "D":
            d += 1
        if sl[i] == "M":
            m += 1
            dm += d
        if sl[i] == "C":
            ans += dm

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = 0
    m = 0
    dm = 0
    ans = 0
    for i in range(n):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if sl[i] == "D":
            d += 1
        if sl[i] == "M":
            m += 1
            dm += d
        if sl[i] == "C":
            ans += dm

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = 0
    m = 0
    dm = 0
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if s == "D":
            d += 1
        if s == "M":
            m += 1
            dm += d
        if s == "C":
            ans += dm

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数

    dp = [[0, 0, 0] for i in range(n+1)]
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                dp[i][0] -= 1
                dp[i][2] -= dp[i][1]
            if sl[i-k] == "M":
                dp[i][1] -= 1
        if s == "D":
            dp[i+1][0] = dp[i][0] + 1
        else:
            dp[i+1][0] = dp[i][0]
        if s == "M":
            dp[i+1][1] = dp[i][1] + 1
            dp[i+1][2] = dp[i][2] + dp[i][0]
        else:
            dp[i+1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
        if s == "C":
            ans += dp[i][2]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
sl = list(input())

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数

    dp = [[0, 0, 0] for i in range(n+1)]
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                dp[i][0] -= 1
                dp[i][2] -= dp[i][1]
            if sl[i-k] == "M":
                dp[i][1] -= 1
        if s == "D":
            dp[i+1][0] = dp[i][0] + 1
        else:
            dp[i+1][0] = dp[i][0]
        if s == "M":
            dp[i+1][1] = dp[i][1] + 1
            dp[i+1][2] = dp[i][2] + dp[i][0]
        else:
            dp[i+1][1] = dp[i][1]
            dp[i + 1][2] = dp[i][2]
        if s == "C":
            ans += dp[i][2]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
_ = input()
K = list(map(int, input().split()))

def sol(k):
    ret = 0

    right = 0
    c = 0
    m = 0
    mc = 0
    nx = 0
    for left, s in enumerate(S):
        while right < N and right - left < k:
            if S[right] == 'M':
                nx += 1
            elif S[right] == 'C':
                m += nx
                mc += m
                nx = 0
                c += 1
            right += 1

        if s == 'D':
            ret += mc
        elif s == 'M':
            mc -= c
            m -= 1
        elif s == 'C':
            c -= 1

    return ret

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:

def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))

    ans = [0] * q
    for i in range(q):
        d = 0
        m = 0
        p = 0
        m_total = 0
        m_delta = []
        for j, x in enumerate(s):
            if j-k[i] >= 0:
                if s[j-k[i]] == 'D':
                    d -= 1
                    m -= m_total - m_delta[p]
                    p += 1
            if x == 'D':
                d += 1
                m_delta.append(m_total)
            elif x == 'M':
                m += d
                m_total += 1
            elif x == 'C':
                ans[i] += m

    for x in ans:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))

    ans = [0] * q
    for i in range(q):
        d = 0
        m = 0
        m_total = 0
        m_delta = deque()
        for j, x in enumerate(s):
            if j-k[i] >= 0:
                if s[j-k[i]] == 'D':
                    d -= 1
                    m_first = m_delta.popleft()
                    m -= m_total - m_first
            if x == 'D':
                d += 1
                m_delta.append(m_total)
            elif x == 'M':
                m += d
                m_total += 1
            elif x == 'C':
                ans[i] += m

    for x in ans:
        print(x)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n=int(input())
s=input().rsplit()[0]
d=[x=="D" for x in s]
m=[x=="M" for x in s]
c=[x=="C" for x in s]

def calc(k):
	D=M=DM=DMC=0
	for i,fd,fm,fc in zip(range(n),d,m,c):
		if k<=i:
			if d[i-k]:
				D-=1
				DM-=M
			elif m[i-k]:
				M-=1
		if fd:
			D+=1
		elif fm:
			M+=1
			DM+=D
		elif fc:
			DMC+=DM
	return DMC

q=int(input())
ans=[calc(x) for x in map(int,input().split())]
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

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

n=int(input())
s=input().rsplit()[0]

def calc(k):
	D=M=DM=DMC=0
	for i in range(n):
		if k<=i:
			if s[i-k]=="D":
				D-=1
				DM-=M
			elif s[i-k]=="M":
				M-=1
		if s[i]=="D":
			D+=1
		elif s[i]=="M":
			M+=1
			DM+=D
		elif s[i]=="C":
			DMC+=DM
	return DMC

q=int(input())
*k,=map(int,input().split())
ans=[calc(x) for x in k]
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S,Q,*K = open(0).read().split()
N = int(N)
K = map(int,K)
S = np.array(list(S))
C = S=='C'
M = S=='M'
Ms = np.cumsum(M)
for k in K:
  kMs = np.copy(Ms)
  kMs[k:] = Ms[k:] - Ms[:-k]
  CMS = C*kMs
  SDMC = 0
  SMC = 0
  SC = 0
  for i in range(N-1,-1,-1):
    if i<=N-1-k:
      SC -= C[i+k]
      SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

Submission status: Time Limit Exceeded

Solution code:
N,S,Q,*K = open(0).read().split()
N = int(N)
K = map(int,K)
C = [0]*N
M = [0]*N
for i in range(N):
  if S[i]=='C':
    C[i] = 1
  elif S[i]=='M':
    M[i] = 1
for k in K:
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(N):
    if i>=k:
      Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
  for i in range(N-1,-1,-1):
    if i<=N-1-k:
      SC -= C[i+k]
      SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S,Q,*K = open(0).read().split()
N = int(N)
Q = int(Q)
K = map(int,K)
S = np.array(list(S))
C = S=='C'
M = S=='M'

for k in K:
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(N):
    if i>=k:
      Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
  for i in range(N-1,-1,-1):
    if i<=N-1-k:
      SC -= C[i+k]
      SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

Submission status: Time Limit Exceeded

Solution code:
N,S,Q,*K = open(0).read().split()
N = int(N)
K = map(int,K)
for k in K:
  C = [0]*N
  M = [0]*N
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(N):
    if i>=k:
      Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
      M[i] = 1
  for i in range(N-1,-1,-1):
    if i<=N-1-k:
      SC -= C[i+k]
      SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
      C[i] = 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

Submission status: Time Limit Exceeded

Solution code:
N,S,Q,*K = open(0).read().split()
N = int(N)
Q = int(Q)
K = map(int,K)
for k in K:
  C = [0]*N
  M = [0]*N
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(k):
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
      M[i] = 1
  for i in range(k,N):
    Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
      M[i] = 1
  for i in range(N-1,N-1-k,-1):
    if S[i]=='C':
      SC += 1
      C[i] = 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  for i in range(N-1-k,-1,-1):
    SC -= C[i+k]
    SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
      C[i] = 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

Submission status: Time Limit Exceeded

Solution code:
N,S,Q,*K = open(0).read().split()
N = int(N)
Q = int(Q)
K = map(int,K)
for k in K:
  C = [0]*N
  M = [0]*N
  CMS = [0]*N
  SDMC = 0
  SMC = 0
  SC = 0
  Ms = 0
  for i in range(k):
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
      M[i] = 1
  for i in range(k,N):
    Ms -= M[i-k]
    if S[i]=='C':
      CMS[i] = Ms
    elif S[i]=='M':
      Ms += 1
      M[i] = 1
  for i in range(N-1,N-1-k,-1):
    if S[i]=='C':
      SC += 1
      C[i] = 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  for i in range(N-1-k,-1,-1):
    SC -= C[i+k]
    SMC -= CMS[i+k]
    if S[i]=='C':
      SC += 1
      C[i] = 1
    elif S[i]=='M':
      SMC += SC
    elif S[i]=='D':
      SDMC += SMC
  print(SDMC)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d = 0
        m = 0
        dm = 0
        dmc = 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
        print(dmc)
    
if __name__ == "__main__":
    main()

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 = tuple(map(int,input().split()))
    for k in x:
        print(count(k))
    
if __name__ == "__main__":
    main()