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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
d = {"D":0, "M":1, "C":2}
ss = [-1]*n
for i in range(n):
    if s[i] in d:
        ss[i] = d[s[i]]
for ki in k:
    D=M=DM=C=0
    for i, c in enumerate(ss):
        if c == 0:
            D += 1
        elif c == 1:
            M += 1
            DM += D
        elif c == 2:
            C += DM
        if i >= ki-1:
            j = i-ki+1
            if ss[j] == 0:
                D -= 1
                DM -= M
            elif ss[j] == 1:
                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
        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)

Submission status: Time Limit Exceeded

Solution code:
class Binary_Indexed_Tree():
    def __init__(self, n):
        self.bit = [0]*n
        self.n = n
    def add(self, ind, num):
        while(ind <= self.n):
            self.bit[ind - 1] += num
            ind += ind & -ind
    def sum(self, ind):
        ret = 0
        while(ind > 0):
            ret += self.bit[ind-1]
            ind -= ind & -ind
        return ret

class Binary_Indexed_Tree_RAQ_RSQ():
    def __init__(self,n):
        self.p = Binary_Indexed_Tree(n+1)
        self.q = Binary_Indexed_Tree(n+1)

    def add(self, s,t,x):
        t += 1
        self.p.add(s,-x*s)
        self.p.add(t, x*t)
        self.q.add(s,x)
        self.q.add(t,-x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t)*t - self.p.sum(s) - self.q.sum(s)*s

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
a = []
for i, c in enumerate(s):
    if c == "D":
        a.append(i)

BIT = Binary_Indexed_Tree_RAQ_RSQ(len(a))

ans = [0]*q

from bisect import bisect_left
for i, c in enumerate(s):
    if c == "M":
        j = bisect_left(a, i) - 1
        BIT.add(1, j+1, 1)
    elif c == "C":
        right = bisect_left(a, i) - 1
        for j, ki in enumerate(k):
            left = bisect_left(a, i-(ki-1))
            tmp = 0
            if left <= right:
                tmp = BIT.sum(left+1, right+1)
            ans[j] += tmp
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

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

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

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))

S = np.array(list(S), dtype=str)
RD = (S == 'D').cumsum()
RM = (S == 'M').cumsum()


def solve(k):
    D = RD.copy()
    D[k:] -= RD[:-k]
    M = RM.copy()
    M[k:] -= RM[:-k]

    DM = D * (S == 'M')
    DM[k:] -= M[k - 1:-1] * (S[:-k] == 'D')
    DM = DM.cumsum()
    return (DM * (S == 'C')).sum()


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

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

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

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

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))


def solve(k):
    ret = 0
    d = 0
    m = 0
    dm = 0
    l = 0
    r = 0
    while r < N:
        if k <= r:
            if S[l] == 'D':
                d -= 1
                dm -= m
            if S[l] == 'M':
                m -= 1
            l += 1

        if S[r] == 'D':
            d += 1
        if S[r] == 'M':
            m += 1
            dm += d
        if S[r] == 'C':
            ret += dm
        r += 1
    return ret


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

Submission status: Time Limit Exceeded

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

D_list=[]
M_list=[]
C_list=[]

for i in range(N):
  if S[i] == "D":
    D_list.append(i)
  if S[i] == "M":
    M_list.append(i)
  if S[i] == "C":
    C_list.append(i)
    
k_list=[0]*Q
  
M_sum=[0]*N  
for i in range(1,N):
  if i in M_list:
    M_sum[i]=M_sum[i-1]+1
  else:
    M_sum[i]=M_sum[i-1] 

num=0
c_start=0
for d in D_list:
  time=0
  c_loc=c_start
  while C_list[c_loc] <= d+max(k):
   # print(d,C_list[c_loc])
    if C_list[c_loc] > d:
      if time==0:
        c_start=c_loc
        time+=1
      num=M_sum[C_list[c_loc]]-M_sum[d]
      #print(M_sum[C_list[c_loc]],M_sum[d])
      for q in range(Q):
        if k[q] > C_list[c_loc] - d:
          k_list[q]+=num
    c_loc+=1
    if c_loc >= len(C_list):
        break

for i in range(Q):
  print(k_list[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
mo=10**9+7
n=int(input())
s=list(input())
q=int(input())
kin=[int(i) for i in input().split()]

for i in range(q):
    k=kin[i]
    nd=0
    nm=0
    ndm=0
    ans=0
    st=deque()

    for j in range(n):
        ch=s[j]
        
        if ch=='C':
            ans+=ndm
        if j<k-1:
            st.append(ch)   
            if ch=='M':
                ndm+=nd
                nm+=1
            if ch=='D':
                nd+=1
        else:
            pre=st.popleft()
            st.append(ch)
            if pre=='D':
                nd-=1
                ndm-=nm
            if pre=='M':
                nm-=1
            if ch=='M':
                ndm+=nd
                nm+=1
            if ch=='D':
                nd+=1
        
        #print(len(st),st,ans,nd,nm,ndm)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

mo=10**9+7
n=int(input())
s=list(input())
q=int(input())
kin=[int(i) for i in input().split()]

for i in range(q):
    k=kin[i]
    nd=0
    nm=0
    ndm=0
    ans=0
    st=deque()

    for j in range(n):
        ch=s[j]
        
        if ch=='C':
            ans+=ndm
        if j<k-1:
            st.append(ch)   
            if ch=='M':
                ndm+=nd
                nm+=1
            if ch=='D':
                nd+=1
        else:
            pre=st.popleft()
            st.append(ch)
            if pre=='D':
                nd-=1
                ndm-=nm
            if pre=='M':
                nm-=1
            if ch=='M':
                ndm+=nd
                nm+=1
            if ch=='D':
                nd+=1
        
        #print(len(st),st,ans,nd,nm,ndm)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

mo=10**9+7
n=int(input())
s=input()
q=int(input())
kin=[int(i) for i in input().split()]

for i in range(q):
    k=kin[i]
    nd=0
    nm=0
    ndm=0
    ans=0
    st=deque()

    for j in range(n):
        ch=s[j]
        
        if ch=='C':
            ans+=ndm
        if j<k-1:
            st.append(ch)   
            if ch=='M':
                ndm+=nd
                nm+=1
            if ch=='D':
                nd+=1
        else:
            pre=st.popleft()
            st.append(ch)
            if pre=='D':
                nd-=1
                ndm-=nm
            if pre=='M':
                nm-=1
            if ch=='M':
                ndm+=nd
                nm+=1
            if ch=='D':
                nd+=1
        
        #print(len(st),st,ans,nd,nm,ndm)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
kk = [int(i) for i in input().split()]

a =[]
b =[]
c =[]

for i in range(n):
  if s[i] == 'D':
    a.append(i)
  
  elif s[i] == 'M':
    b.append(i)
  
  elif s[i] == 'C':
    c.append(i)
    
for m in range(len(kk)):
  count = 0
  for k in range(len(a)):
    for j in range(len(b)):
      for i in range(len(c)):

        if (0 <= a[k] and a[k] < b[j] and b[j] < c[i] and c[i] <= n) and c[i] - a[k] < kk[m]:
            count += 1
  #print(a,b,c)
  print(count)

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):
    k = K[i]
    D = 0
    M = 0
    DM = 0
    num = 0
    for j in range(N):
        if S[j] == 'D':
            D += 1
        elif S[j] == 'M':
            DM += D
            M += 1
        elif S[j] == 'C':
            num += DM
        if j >= k - 1:
            if S[j - k + 1] == 'D':
                D -= 1
                DM -= M
            elif S[j - k + 1] == 'M':
                M -= 1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
k=[int(i) for i in input().split()]

for z in k:
    d=0
    m=0
    c=0
    ans=0
    for i in range(n):
        
        if i-z>=0:
            if s[i-z]=='D':
                d-=1
                c-=m
            elif s[i-z]=='M':
                m-=1
        if s[i]=='D':
            d+=1
        elif s[i]=='M':
            m+=1
            c+=d
        elif s[i]=='C':
            ans+=c
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
S = input()
Q = int(input())
ks = [int(k) for k in input().split()]
sorted_ks = sorted(ks)
counts = [0 for _ in range(len(ks))]

candidate_a = []
candidate_b = []
candidate_c = []
for i,char in enumerate(S):
  if char == "D":
    candidate_a.append(i)
  elif char == "M":
    candidate_b.append(i)
  elif char == "C":
    candidate_c.append(i)
candidate_a.sort(reverse=True)
candidate_b.sort(reverse=True)
candidate_c.sort(reverse=True)

for index_a in candidate_a:
  for index_b in candidate_b:
    if index_b <= index_a:
        break
    else:
      for index_c in candidate_c:
        if index_c <= index_b:
            break
        else:
          for i, k in enumerate(sorted_ks):
            if (index_c - index_a) < k:
              counts[i:] = [c + 1 for c in counts[i:]]
              break

for i in range(Q):
  index = sorted_ks.index(ks[i])
  print(counts[index])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
ks = [int(k) for k in input().split()]
sorted_ks = sorted(ks)
counts = [0 for _ in range(len(ks))]

candidate_a = []
candidate_b = []
candidate_c = []
for i,char in enumerate(S):
  if char == "D":
    candidate_a.append(i)
  elif char == "M":
    candidate_b.append(i)
  elif char == "C":
    candidate_c.append(i)

for index_a in candidate_a:
  for index_b in candidate_b:
    if index_b > index_a:
      for index_c in candidate_c:
        if index_c > index_b:
          for i, k in enumerate(sorted_ks):
            if (index_c - index_a) < k:
              counts = [(e + 1) if j >= i else e for j, e in enumerate(counts)]
              break

for i in range(Q):
  index = sorted_ks.index(ks[i])
  print(counts[index])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(lambda x: int(x), input().split(' ')))
    for k in ks:
        count = 0
        for di in range(n):
            if s[di] == 'D':
                for mi in range(di+1, n):
                    if s[mi] == 'M':
                        for ci in range(mi+1, n):
                            if s[ci] == 'C' and ci - di < k:
                                count += 1
        print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(lambda x: int(x), input().split(' ')))
    for k in ks:
        ds = []
        ms = []
        cs = []
        for i, char in enumerate(s):
            if char == 'D':
                ds.append(i)
            elif char == 'M':
                ms.append(i)
            elif char == 'C':
                cs.append(i)

        count = 0

        for d in ds:
            for m in ms:
                for c in cs:
                    if (d < m) and (m < c) and (c-d) < k:
                        count += 1
        print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
S=input()
D_stack=[]
D,C=[-1]*(N+1),[-1]*(N+1)
m=0
for i in range(N):
  if S[i]=="D":
    D_stack.append((i,m))
    D[i]=m
  if S[i]=="C":
    C[i]=m
  if S[i]=="M":
    m+=1
Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  r,c,s,pre_m=0,1,0,0
  for p,m in D_stack:
    if r<=p:
      r=p+1
      c,s=1,0
    else:
      s-=(c-1)*(m-pre_m)
      c-=1
    pre_m=m
    while r-p<k and r<=N:
      if C[r]>=0:
        ans+=c*(C[r]-m)-s
      if D[r]>=0:
        c+=1
        s+=D[r]-m
      r+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
D_stack=[]
D,C=[-1]*(N+1),[-1]*(N+1)
m=0
for i in range(N):
  if S[i]=="D":
    D_stack.append((i,m))
    D[i]=m
  if S[i]=="C":
    C[i]=m
  if S[i]=="M":
    m+=1
Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  l,r,c,s,pre_m=0,0,1,0,0
  for p,m in D_stack:
    if r<=p:
      r=p+1
      c,s=1,0
    else:
      s-=(c-1)*(m-pre_m)
      c-=1
    pre_m=m
    while r-p<k and r<=N:
      if C[r]>=0:
        ans+=c*(C[r]-m)-s
      if D[r]>=0:
        c+=1
        s+=D[r]-m
      r+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
s = raw_input()
q = int(raw_input())
arr = map(int,(raw_input().split()))

nc = 0
nc_arr = []
nm = 0
nd = 0
nd_arr = []
arr_in_b = []
k = 10
for i in range(n):
    if s[i] == "D":
        nd += 1
        nd_arr.append(i)
    elif s[i] == "M":
        nm += 1
        new = []
        for id in nd_arr:
            new.append(id)
        arr_in_b.append(new)
bi = len(arr_in_b)-1
# print arr_in_b
ans = [0 for i in range(q)]
for i in range(n):
    if s[n-1-i] == "C":
        nc += 1
        nc_arr.append(n-1-i)
    elif s[n-1-i] == "M":
        for z in range(q):
            for y in range(len(arr_in_b[bi])-1, -1, -1):
                state = 0
                for x in range(len(nc_arr)):
                        if nc_arr[x] - arr_in_b[bi][y] < arr[z]:
                            ans[z] += len(nc_arr[x:])
                            state = 1
                            break
                if state == 0:
                    break
        bi -= 1
for a in ans:
    print a

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
s = raw_input()
q = int(raw_input())
arr = map(int,(raw_input().split()))

nc = 0
nc_arr = []
nm = 0
nd = 0
nd_arr = []
arr_in_b = []
k = 10
for i in range(n):
    if s[i] == "D":
        nd += 1
        nd_arr.append(i)
    elif s[i] == "M":
        nm += 1
        new = []
        for id in nd_arr:
            new.append(id)
        arr_in_b.append(new)
bi = len(arr_in_b)-1
# print arr_in_b
ans = [0 for i in range(q)]
for i in range(n):
    if s[n-1-i] == "C":
        nc += 1
        nc_arr.append(n-1-i)
    elif s[n-1-i] == "M":
        for z in range(q):
            for y in range(len(arr_in_b[bi])):
                for x in range(len(nc_arr)):
                        if nc_arr[x] - arr_in_b[bi][y] < arr[z]:
                            ans[z] += len(nc_arr[x:])
                            break
        bi -= 1
for a in ans:
    print a

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
def main():
	n = int(input())
	s = input()
	q = int(input())
	klist = list(map(int, input().split()))
	
	for times in range(q):
		r = 0
		k = klist[times]
		nowd, nowm, nowdm = 0, 0, 0
		for i in range(n):
			c = s[i]
			if (c == "D"):
				nowd += 1
			elif (c == "M"):
				nowm += 1
				nowdm += nowd
			elif(c == "C"):
				r += nowdm
			if(i >= k-1):
				cc = s[i-k+1]
				if (cc == "D"):
					nowd -= 1
					nowdm -= nowm
				elif (cc == "M"):
					nowm -= 1
		print(r)
main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

p = [(S[i] == 'D') for i in range(N)] + [0] * N
q = [(S[i] == 'M') for i in range(N)] + [0] * N
r = [(S[i] == 'C') for i in range(N)] + [0] * N

P = [0] + list(itertools.accumulate(p))
R = [0] + list(itertools.accumulate(r))

def DMC(k):
    f = [p[i] * R[i + k] for i in range(N)]
    F = [0] + list(itertools.accumulate(f))
    ans = 0
    for y in range(N):
        ans += q[y] * (F[y] - F[max(0, y - k + 2)] - R[y + 1] * (P[y] - P[max(0, y - k + 2)]))
    return ans

for i in range(Q):
    print(DMC(k[i]))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = [" "] + lc()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))

Submission status: Time Limit Exceeded

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



def find_ans(k:int):
    d__ = 0
    dm_ = 0
    _m_ = 0
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += dm_

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                d__ -= 1
                dm_ -= _m_
                
            elif s[i-k+1] == 'M':
                _m_ -= 1
                
        if s[i] == 'D':
            d__ += 1    
        
        elif s[i] == 'M':
            dm_ += d__
            _m_ += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = [" "] + lc()
q = ni()
k = list(li())



def find_ans(k:int):
    d__ = 0
    dm_ = 0
    _m_ = 0
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += dm_

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                d__ -= 1
                dm_ -= _m_
                
            elif s[i-k+1] == 'M':
                _m_ -= 1
                
        if s[i] == 'D':
            d__ += 1    
        
        elif s[i] == 'M':
            dm_ += d__
            _m_ += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i + 1] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i + 1] += 1
        acc_cnt_ab[i + 1] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = list(accumulate(acc_cnt_a))
acc_cnt_b = list(accumulate(acc_cnt_b))
acc_cnt_ab = list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = max(0, r - k)
        rejected_a = acc_cnt_a[l]
        cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
        cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
        ans += cnt_internal_ab - rejected_a * cnt_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i + 1] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i + 1] += 1
        acc_cnt_ab[i + 1] += cnt_a
acc_cnt_a = list(accumulate(acc_cnt_a))
acc_cnt_b = list(accumulate(acc_cnt_b))
acc_cnt_ab = list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r, c in enumerate(s):
        if c != 'C':
            continue
        r += 1
        l = max(0, r - k)
        rejected_a = acc_cnt_a[l]
        cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
        cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
        ans += cnt_internal_ab - rejected_a * cnt_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
s = input()
q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    l = 0
    count_a = 0
    rejected_a = 0
    count_internal_b = deque()
    sum_internal_b = 0
    for r, c in enumerate(s):
        if c == 'D':
            count_a += 1
        elif c == 'M':
            count_internal_b.append(count_a)
            sum_internal_b += count_a
        elif c == 'C':
            left_limit = r - k
            while l <= left_limit:
                old_c = s[l]
                if old_c == 'D':
                    rejected_a += 1
                elif old_c == 'M':
                    sum_internal_b -= count_internal_b.popleft()
                l += 1
            ans += sum_internal_b - rejected_a * len(count_internal_b)
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

Submission status: Time Limit Exceeded

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

def Counter(S, k):
    Total = 0
    count = [0, 0, 0] #D, M, DMの数
    for i in range(N):    
        if S[i] == "D": count[0] += 1
        elif S[i] == "M": 
            count[1] += + 1
            count[2] += count[0]
        elif S[i] == "C":
            Total += count[2]
        if i >= k - 1:
            if S[i-k+1] == "D":
                count[0] -= 1
                count[2] -= count[1]
            elif S[i-k+1] == "M":
                count[1] -= 1
    return Total

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
S = sys.stdin.readline()
Q = int(input())
ks = list(map(int,input().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            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
    ans.append(dmc)

print(*ans,sep='\n')

Submission status: Time Limit Exceeded

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

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            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
    ans.append(dmc)

print(*ans,sep='\n')

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:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            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
    print(dmc)

Submission status: Time Limit Exceeded

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

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)