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: Wrong Answer

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

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


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


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

Submission status: Wrong Answer

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

idx = {k:[] for k in ["D", "M", "C"]}
for i in range(len(S)):
    if S[i]=="D" or S[i]=="M" or S[i]=="C":
        idx[S[i]].append(i)

for k in ["D", "M", "C"]:
    idx[k].sort()

for Ki in K:
    cnt = 0
    for di in idx["D"]:
        for mi in idx["M"]:
            if mi<di: continue
            if mi-di>=Ki:
                break
            for ci in idx["C"]:
                if ci<mi: continue
                if ci-di>Ki:
                    break
                cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
S = list(input().strip())
Q = int(input().strip())
k_s = list(map(int,input().strip().split()))
answers = [0 for i in range(len(k_s))]
for numk,k in enumerate(k_s):
    for i in range(N):
        if S[i] == 'D':
            for j in range(i,N):
                if j-i > k:
                    break
                elif S[j] == 'M':
                    for l in range(j,N):
                        if l-i > k:
                            break
                        elif S[l] == 'C':
                            answers[numk] +=1

for answer in answers:
    print(answer)

Submission status: Wrong Answer

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

d_l = []
m_l = {}
c_l = []
k_n = [0] * Q

for i, s in enumerate(S):
    if s == "D":
        d_l.append(i)
    elif s == "M":
        d_l.sort(reverse=True)
        temp = []
        for l in d_l:
            if i - l > 76:
                break
            temp.append(l)
        m_l[i] = temp
    elif s == "C":
        for idx, ls in m_l.items():
            if i - idx > 76:
                continue
            for l in ls:
                r = i - l
                if r > 76:
                    break
                c_l.append(r)
                for j, ki in enumerate(k):
                    if r < ki:
                        k_n[j] += 1 

for n in k_n:
    print(n)

Submission status: Wrong Answer

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

d_l = []
m_l = []
c_l = []
k_n = [0] * Q

for i, s in enumerate(S):
    if s == "D":
        d_l.append(i)
    elif s == "M":
        d_l.sort(reverse=True)
        temp = []
        for l in d_l:
            if i - l > 76:
                break
            temp.append(l)
        m_l.append(temp)
    elif s == "C":
        for ls in m_l:
            for l in ls:
                r = i - l
                if r > 76:
                    continue
                c_l.append(r)
                for j, ki in enumerate(k):
                    if r < ki:
                        k_n[j] += 1 

for n in k_n:
    print(n)

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	S = input()
	Q = int(input())
	k = sorted([int(x) for x in input().split()])

	result = 0
	lstD = []
	lstM = []
	lstC = []

	for i in range(N):
		if S[i] == 'D':
			lstD.append(i)
		elif S[i] == 'M':
			lstM.append(i)
		elif S[i] == 'C':
			lstC.append(i)

	for d in lstD:
		for m in lstM:
			for c in lstC:
				for k_i in k:
					if d < m < c and c - d < k_i:
						result += 1

	print(result)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
S = input().strip()
Q = int(input())
K = list(map(int,input().split()))

m = [0] * 3
for k in K:
    ans = 0
    m = defaultdict(int)
    for i,s in enumerate(S):
        if i >= k:
            pre = S[i-k]
            if pre == 'D':
                m[0] -= 1 # m['D'] -= 1
                m[2] -= m[1] # m['DM'] -= m['M']
            elif pre == 'M':
                m[1] -= 1 # m['M'] -= 1
        if s == 'D':
            m[0] += 1 # m['D'] += 1
        if s == 'M': 
            m[2] += m[0] # m['DM'] += m['D']
            m[1] += 1# m['M'] += 1
        if s == 'C':
            ans += m[2] # ans += m['DM']
        #print(s,m)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
S = input().strip()
Q = int(input())
K = list(map(int,input().split()))

for k in K:
    ans = 0
    m = defaultdict(int)
    for i,s in enumerate(S):
        if i >= k:
            pre = S[i-k]
            if pre == 'D':
                m['D'] -= 1
                m['DM'] -= m['M']
            elif pre == 'M':
                m['M'] -= 1
        if s == 'D':
            m['D'] += 1
        if s == 'M': 
            m['DM'] += m['D']
            m['M'] += 1
        if s == 'C':
            ans += m['DM']
        #print(s,m)
    print(ans)

Submission status: Time Limit Exceeded

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

#print(D,M)

def solve(k):
  d = 0; m = 0; dm = 0
  ret = 0
  left = N-2; right = N-2
  #d = SD[right+1]-SD[left]
  #m = SM[right+1]-SM[left]
  for i in range(N):
    loc = N-1-i
    while left >= 0 and left >= loc-k+1:
      if S[left] == "D":
        d += 1
        dm += m
      elif S[left] == "M":
        m += 1
      left -= 1
      #if left < 0 or left <= loc-k+1:
      #  break
    #print(d,m,dm)
    while right >= 0 and right >= loc:
      if S[right] == "D":
        d -= 1
      elif S[right] == "M":
        m -=1
        dm -= d
      right -= 1
      #if right < left or right <= loc-1:
      #  break
    #print(left,right,d,m,dm)
    if S[loc] == "C":
      ret += dm
  return ret
for query in range(Q):
  ans = solve(K[query])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = str(input())
Q = int(input())
K = list(map(int,input().split()))
SD = [0];SM = [0]
for i in range(N):
  if S[i] == "D":
    SD.append(SD[-1]+1)
    SM.append(SM[-1])
  elif S[i] == "M":
    SD.append(SD[-1])
    SM.append(SM[-1]+1)
  else:
    SD.append(SD[-1])
    SM.append(SM[-1])
#print(D,M)

def solve(k):
  d = 0; m = 0; dm = 0
  ret = 0
  left = N-2; right = N-2
  #d = SD[right+1]-SD[left]
  #m = SM[right+1]-SM[left]
  for i in range(N):
    loc = N-1-i
    while left >= 0 and left >= loc-k+1:
      if S[left] == "D":
        d += 1
        dm += m
      elif S[left] == "M":
        m += 1
      left -= 1
      #if left < 0 or left <= loc-k+1:
      #  break
    #print(d,m,dm)
    while right >= 0 and right >= loc:
      if S[right] == "D":
        d -= 1
      elif S[right] == "M":
        m -=1
        dm -= d
      right -= 1
      #if right < left or right <= loc-1:
      #  break
    #print(left,right,d,m,dm)
    if S[loc] == "C":
      ret += dm
  return ret
for query in range(Q):
  ans = solve(K[query])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
Q = int(input())
K = list(map(int,input().split()))
SD = [0];SM = [0]
for i in range(N):
  if S[i] == "D":
    SD.append(SD[-1]+1)
    SM.append(SM[-1])
  elif S[i] == "M":
    SD.append(SD[-1])
    SM.append(SM[-1]+1)
  else:
    SD.append(SD[-1])
    SM.append(SM[-1])
#print(D,M)

def solve(k):
  d = 0; m = 0; dm = 0
  ret = 0
  left = N-2; right = N-2
  #d = SD[right+1]-SD[left]
  #m = SM[right+1]-SM[left]
  for i in range(N):
    loc = N-1-i
    while left >= 0 and left >= loc-k+1:
      if S[left] == "D":
        d += 1
        dm += m
      elif S[left] == "M":
        m += 1
      left -= 1
      #if left < 0 or left <= loc-k+1:
      #  break
    #print(d,m,dm)
    while right >= 0 and right >= loc:
      if S[right] == "D":
        d -= 1
      elif S[right] == "M":
        m -=1
        dm -= d
      right -= 1
      #if right < left or right <= loc-1:
      #  break
    #print(left,right,d,m,dm)
    if S[loc] == "C":
      ret += dm
  return ret
for query in range(Q):
  ans = solve(K[query])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

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

@njit
def solve(N, S, k):
    k -= 1

    # i-th of these counts the thing in [ max(0, i-k), i ).
    D_counts  = [0]
    M_counts  = [0]
    DM_counts = [0]

    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == 'D':
            D += 1
        elif S[i] == 'M':
            DM += D
            M += 1
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)
    for i in range(k, N):
        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':
            DM += D
            M += 1
            
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)

    ans = 0
    for i, c in enumerate(S):
        if c == 'C':
            ans += DM_counts[i]
    return ans

for k in ks:
    print(solve(N, S, k))

Submission status: Time Limit Exceeded

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

def solve(N, S, k):
    k -= 1
    
    # i-th of these counts the thing in [ max(0, i-k), i ).
    D_counts  = [0]
    M_counts  = [0]
    DM_counts = [0]

    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == 'D':
            D += 1
        elif S[i] == 'M':
            DM += D
            M += 1
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)
    for i in range(k, N):
        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':
            DM += D
            M += 1
            
        D_counts.append(D)
        M_counts.append(M)
        DM_counts.append(DM)

    ans = 0
    for i, c in enumerate(S):
        if c == 'C':
            ans += DM_counts[i]
    return ans

for k in ks:
    print(solve(N, S, k))

Submission status: Time Limit Exceeded

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

for ii in range(q):
    D = [[0] * 3 for i in range(n)]
    ans = 0
    k = K[ii]
    for i in range(n):
        for j in range(3):
            D[i][j] = D[i-1][j]
        
        if i-k >= 0:
            if s[i-k] == "D":
                D[i][0] -= 1
                D[i][2] -= D[i][1]
            if s[i-k] == "M":
                D[i][1] -= 1
        
        if s[i] == "D":
            D[i][0] += 1
        if s[i] == "M":
            D[i][1] += 1
            D[i][2] += D[i][0]
        if s[i] == "C":
            ans += D[i][2]
    print(ans)
    # print(D)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N = INT()
S = input()

def f(x):
    DM = [0] * N
    mcnt = 0
    for i in range(N-1, -1, -1):
        if i+x < N:
            if S[i+x] == 'M':
                mcnt -= 1
        if S[i] == 'M':
            mcnt += 1
        elif S[i] == 'D':
            DM[i] = mcnt

    res = dcnt = dmcnt = 0
    for i in range(N):
        if i-x >= 0:
            if S[i-x] == 'D':
                dcnt -= 1
                dmcnt -= DM[i-x]
        if S[i] == 'D':
            dcnt += 1
        elif S[i] == 'M':
            dmcnt += dcnt
        elif S[i] == 'C':
            res += dmcnt
    return res

INT()
for q in LIST():
    print(f(q))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()
d = S.find('D')
e = S.rfind('D')
ans = []
for k in K:
    m = 0
    c = 0
    a = 0
    for i in range(d+1,min(N,d+k)):
        m += S[i]=='M'
        c += S[i]=='C'
        a += m*(S[i]=='C')
    b = a
    for i in range(d+1,N):
        if i+k-1<N:
            m += S[i+k-1]=='M'
            c += S[i+k-1]=='C'
            a += m*(S[i+k-1]=='C')
        m -= S[i-1]=='M'
        a -= c*(S[i-1]=='M')
        c -= S[i-1]=='C'
        b += a*(S[i]=='D')
        if S[i]=='D' and i==e:
            break
    ans.append(b)
printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()

ans = []
for k in K:
    m = 0
    c = 0
    a = [0]
    d = S.find('D')
    e = S.rfind('D')
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a[-1] += m
    a.append(a[-1])
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a[-1] += m
        if S[i-1]=='M':
            m -= 1
            a[-1] -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            if i==e:
                break
            else:
                a.append(a[-1])
    ans.append(sum(a))
printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

ans = []
for k in K:
    m = 0
    c = 0
    a = [0]
    if 'D' not in S:
        ans.append(0)
        break
    d = S.find('D')
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a[-1] += m
    a.append(a[-1])
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a[-1] += m
        if S[i-1]=='M':
            m -= 1
            a[-1] -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            a.append(a[-1])
    ans.append(sum(a[:-1]))
printrows(ans)

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

def main():
	n=II()
	s=input().rstrip().decode()
	li=[0]*n
	
	q=II()
	K=LI()
	for k in K:
		D=0
		M=0
		DM=0
		ans=0
		
		for i in range(n):
			if s[i]=="D":
				D+=1
			elif s[i]=="M":
				M+=1
				DM+=D
			elif 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
		print(ans)
		


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

def main():
	n=II()
	s=input().rstrip().decode()
	li=[0]*n
	for i in range(n):
		if s[i]=="D":
			li[i]=1
		elif s[i]=="M":
			li[i]=2
		elif s[i]=="C":
			li[i]=3
	
	q=II()
	K=LI()
	for k in K:
		D=0
		M=0
		DM=0
		ans=0
		
		for i in range(n):
			if li[i]==1:
				D+=1
			elif li[i]==2:
				M+=1
				DM+=D
			elif li[i]==3:
				ans+=DM
			
			if i-k+1>=0:
				if li[i-k+1]==1:
					D-=1
					DM-=M
				elif li[i-k+1]==2:
					M-=1
		print(ans)
		


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
query = tuple(map(int, input().split()))

for k in query:
    D = 0
    M = 0
    DM = 0
    res = 0
    for i, s in enumerate(S):
        if i >= k:
            if S[i - k] == "D":
                DM -= M
                D -= 1
            elif S[i - k] == "M":
                M -= 1
        if s == "D":
            D += 1
        elif s == "M":
            M += 1
            DM += D
        elif s == "C":
            res += DM
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

n=int(input())
s=[ord(i) for i in input()]
q=int(input())
kin=[int(i) for i in input().split()]

D,M,C=[ord(i) for i in 'DMC']

for i in range(q):
    k=kin[i]
    nd=nm=ndm=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
            elif ch==D:
                nd+=1
        else:
            pre=st.popleft()
            st.append(ch)
            if pre==D:
                nd-=1
                ndm-=nm
            elif pre==M:
                nm-=1
            if ch==M:
                ndm+=nd
                nm+=1
            elif ch==D:
                nd+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

n=int(input())
s=[ord(i) for i in input()]
q=int(input())
kin=[int(i) for i in input().split()]

D,M,C=[ord(i) for i in 'DMC']

for i in range(q):
    k=kin[i]
    nd=nm=ndm=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
            elif ch==D:
                nd+=1
        else:
            pre=st.popleft()
            st.append(ch)
            if pre==D:
                nd-=1
                ndm-=nm
            elif pre==M:
                nm-=1
            if ch==M:
                ndm+=nd
                nm+=1
            elif ch==D:
                nd+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

n=int(input())
s=[ord(i) for i in input()]
q=int(input())
kin=[int(i) for i in input().split()]

D,M,C=[ord(i) for i in 'DMC']

for i in range(q):
    k=kin[i]
    nd=nm=ndm=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(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
import fractions
#gcd=fractions.gcd
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
show_flg=False
show_flg=True

ans=0

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