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=list(input())
q=int(input())
k=list(map(int,input().split()))
h=[0]*q
di=s.count("D")
for r in range(di):
    f=s.index("D")
    s=s[f+1:]
    a=0
    l=0
    sp=min(len(s),max(k))
    for c in range(sp):
        if s[c]=="M":
            a+=1
        elif s[c]=="C":
            l+=a
        if c+2 in k:
            h[k.index(c+2)]+=l
    else:
        for i in k:
            if i>len(s)+1:
                h[k.index(i)]+=l 
for i in range(q):
    print(h[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s)
    ans = [sum(dmcmap[:k]) for k in ks]
    print(*ans, sep='\n', flush=True)

def dmc(src):
    ret = [0 for _ in range(len(src))]

    dmap = [i for i, x in enumerate(src) if x == 'D']
    mmap = [i for i, x in enumerate(src) if x == 'M']
    cmap = [i for i, x in enumerate(src) if x == 'C']

    for d in dmap:
        for m in filter(lambda x: x > d, mmap):
            for c in filter(lambda x: x > m, cmap):
                ret[c-d] += 1
    return ret

s, ks = load()
calc(s,ks)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

	dp = np.zeros((n, 3))
	for i in range(n):
		#print("at", i, s[i])
		if(s[i] == "D"):
			for j in range(n-1):
				dp[n-1-j] = dp[n-1-j-1]
			dp[0][0] = 1
		elif(s[i] == "M"):
			for j in range(n-1):
				dp[n-1-j][0] = dp[n-1-j-1][0]
				dp[n-1-j][1] = dp[n-1-j-1][1]+dp[n-1-j-1][0]
				dp[n-1-j][2] = dp[n-1-j-1][2]
			dp[0][0] = 0
		elif(s[i] == "C"):
			for j in range(n-1):
				dp[n-1-j][0] = dp[n-1-j-1][0]
				dp[n-1-j][1] = dp[n-1-j-1][1]
				dp[n-1-j][2] = dp[n-1-j-1][2]+dp[n-1-j-1][1]
			dp[0][0] = 0
		else:
			for j in range(n-1):
				dp[n-1-j] = dp[n-1-j-1]
			dp[0][0] = 0
		#print(dp.T)
		
		for j in range(q):
			r[j] += dp[k[j]-1][2]
		#print(r, "r")
	for i in range(q):
		#print(dp[:k[i]])
		print(int(r[i]+np.sum(((dp[:k[i]-1]).T)[2])))
	
main()

Submission status: Time Limit Exceeded

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

import collections

class VR:
    def __init__(self):
        self.ranges = []
    def add(self, rng):
        self.ranges.append(rng)
    def count(self, n):
        ret = 0
        for l, r in self.ranges:
            ret += (l <= n and n < r)
        return ret

def f(k):
    ret = 0

    evr = VR()    
    pd = pm = 0
    qd = collections.deque()
    for i, s in enumerate(S):
        cd = pd
        cm = pm
        if len(qd) and qd[0][1] <= i:
            e = qd.popleft()
            cd -= e[2]
            cm -= e[2] * evr.count(e[0])

        if s == 'D':
            cd += 1
            qd.append((i, i+k, 1))
        elif s == 'M':
            cm += cd
            evr.add((max(0, i - k), i))
        elif s == 'C':
            ret += cm
        pd = cd
        pm = cm

    return ret

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

if __name__ == "__main__":
    n = int(input())
    s = np.unicode(input())
    q = int(input())
    ks = list(map(int, input().split()))

    string = [None for _ in range(n)]
    for i in range(n):
        string[i] = s[i]
    string = np.array(string)

    d_site = np.array(string == "D")
    m_site = np.array(string == "M")
    c_site = np.array(string == "C")
    c_site = np.where(c_site)[0].reshape(-1)

    nums = [0 for _ in range(q)]

    for main_i in c_site:
        for i in range(q):
            start = main_i - ks[i] + 1
            if start < 0:
                start = 0

            m_site_dum = np.where(m_site[start:main_i])[0].reshape(-1)

            for m_dum in m_site_dum:
                nums[i] += np.sum(d_site[start:main_i][:m_dum])

    for i in range(q):
        print(nums[i])

Submission status: Time Limit Exceeded

Solution code:
"""n,k=map(int,input().split())
a=[int(i) for i in input().split()]
lis=[]
for i in range(len(a)):
    for j in range(len(a)-i):
        lis.append(sum(a[i:i+j+1]))
lis.sort(reverse=True)
ans=lis[0]
for i in range(k-1):
    ans=ans&lis[i+1]
print(ans)"""
n=int(input())
s=input()
q=int(input())
k=map(int,input().split())
for i in k:
    ans=0
    for cnt,l in enumerate(s):
        if l=="D":
            for cnt2,m in enumerate(s[cnt:cnt+i]):
                if m=="M":
                    for o in s[cnt+cnt2:cnt+i]:
                        if o=="C":
                            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline())
S = list(sys.stdin.readline())
Q = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split(' ')))

# chache = []

oms = [(i, S[i]) for i in range(N) if S[i] == 'D' or S[i] == 'M' or S[i] == 'C']
oml = len(oms)

def process(ki, index, selected = 'n'):
    global cache

    if index == oml:
      return []

    if cache[index][selected] is not None:
        # print('use cache')
        return cache[index][selected]

    rets = []
    # char = oms[index][1]
    if selected == 'b':
        for ind in range(index, oml):
            char = oms[ind][1]
            if char == 'C':
                rets.append(oms[ind][0])
    elif selected == 'a':
        for ind in range(index, oml):
            char = oms[ind][1]
            if char == 'M':
                rets += process(ki,ind+1, 'b')
    else:
        for ind in range(index, oml):
            char = oms[ind][1]
            if char == 'D':
                cind = process(ki,ind+1, 'a')
                ret = []
                for v in cind:
                    if v != False and ((v - oms[ind][0]) < ki):
                      ret.append(True)
                rets += ret

    cache[index][selected] = rets

    return rets


for ki in k:
    cache = [{'a': None, 'b': None, 'c': None, 'n': None} for i in range(N)]
    ret = process(ki, 0)
    print(len(ret))

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:
    count = 0
    for i in range(S.count('D')):
        if i == 0:
            a = S.find('D')
        else:
            a = S.find('D', a+1)

        for j in range(S.count('M', a+1)):
            if j == 0:
                b = S.find('M', a+1)
            else:
                b = S.find('M', b+1)
            if b == -1:
                break

            if (b - a) >= k:
                break

            for m in range(S.count('C', b+1)):
                if m == 0:
                    c = S.find('C', b + 1)
                else:
                    c = S.find('C', c + 1)
                if c == -1:
                    break

                if (c - a) < k:
                    count += 1
                else:
                    break
    print(count)

Submission status: Time Limit Exceeded

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

d_num = []
m_num = []
c_num = []
for i in range(len(s)):
    if s[i] == 'D':
        d_num.append(i)
    if s[i] == 'M':
        m_num.append(i)
    if s[i] == 'C':
        c_num.append(i)

for k in k_list:
    ans = 0
    for a in d_num:
        for b in m_num:
            for c in c_num:
                if a < b & b < c:
                    if (c - a) < k:
                        ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline())
S = list(sys.stdin.readline())
Q = int(sys.stdin.readline())
k = list(map(int, sys.stdin.readline().split(' ')))

# chache = []

oms = [(i, S[i]) for i in range(N) if S[i] == 'D' or S[i] == 'M' or S[i] == 'C']
oml = len(oms)

def process(ki, index, selected = 'n'):
    # global cache

    if index == oml:
      return []

    rets = []
    # char = oms[index][1]
    if selected == 'b':
        for ind in range(index, oml):
            char = oms[ind][1]
            if char == 'C':
                rets.append(oms[ind][0])
    elif selected == 'a':
        for ind in range(index, oml):
            char = oms[ind][1]
            if char == 'M':
                rets += process(ki,ind+1, 'b')
    else:
        for ind in range(index, oml):
            char = oms[ind][1]
            if char == 'D':
                cind = process(ki,ind+1, 'a')
                ret = []
                for v in cind:
                    if v != False and ((v - oms[ind][0]) < ki):
                      ret.append(True)
                rets += ret

    return rets


for ki in k:
    # cache = [{'a': None, 'b': None, 'c': None, 'n': None} for i in range(N)]
    ret = process(ki, 0)
    print(len(ret))

Submission status: Time Limit Exceeded

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

#%%
# n = 54
# s = "DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED"
# q = 3
# k = [20, 30, 40]


#%%
idx_a = []
idx_b = []
idx_c = []

#%%
for i in range(len(s)):
    if s[i] == "D":
        idx_a.append(i)
    if s[i] == "M":
        idx_b.append(i)
    if s[i] == "C":
        idx_c.append(i)
        



#%%
ans = [0 for _ in range(q)]
for a in idx_a[::-1]:
    for c in idx_c:
        if a < c:
            if c - a < k[-1]:
                for b in idx_b:
                    if a<b:
                        if b<c:
                            for i in range(q):
                                if c-a<k[i]:
                                    ans[i] += 1
                        else:
                            break
            else:
                break
for ans_i in ans:
    print(ans_i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
q = int(input())
K = list(map(int, input().split()))
s = list(s)
Dlist = [i for i, v in enumerate(s) if v == 'D']
Mlist = [i for i, v in enumerate(s) if v == 'M']
Clist = [i for i, v in enumerate(s) if v == 'C']
for i in K:
  count_i = 0
  for j in Dlist:
    for k in Mlist:
      if j < k and k - j < i:   
        for l in Clist:
          if k < l:
            if l - j < i:
              count_i += 1
  print(count_i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s)
    ans = [sum(dmcmap[:k]) for k in ks]
    print(*ans, sep='\n', flush=True)

def dmc(src):
    ret = [0 for _ in range(len(src))]

    for ind in range(len(src)):
        if src[ind] == 'D':
            for inm in range(ind+1, len(src)):
                if src[inm] == 'M':
                    for inc in range(inm+1, len(src)):
                        if src[inc] == 'C':
                            ret[inc-ind] += 1
    return ret

s, ks = load()
calc(s,ks)

Submission status: Time Limit Exceeded

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

d_num = []
m_num = []
c_num = []
for i, char in enumerate(s):
    if char == 'D':
        d_num.append(i)
    if char == 'M':
        m_num.append(i)
    if char == 'C':
        c_num.append(i)

for k in k_list:
    ans = 0
    for a in d_num:
        for b in m_num:
            for c in c_num:
                if a < b & b < c:
                    if (c - a) < k:
                        ans += 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 k in K:
    count = 0
    for i in range(S.count('D')):
        if i == 0:
            a = S.find('D')
        else:
            a = S.find('D', a+1)

        for j in range(S.count('M')):
            if j == 0:
                b = S.find('M', a+1)
            else:
                b = S.find('M', b+1)
            if b == -1:
                break

            if (b - a) >= k:
                break

            for m in range(S.count('C')):
                if m == 0:
                    c = S.find('C', b + 1)
                else:
                    c = S.find('C', c + 1)
                if c == -1:
                    break

                if (c - a) < k:
                    count += 1
                else:
                    break
    print(count)

Submission status: Time Limit Exceeded

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

D = [i for i in range(N) if S[i] == "D"]
for k in K:
    m = 0
    c = 0
    cm = 0
    mc = 0
    ans = 0
    for i in range(k-1):
        if S[i] == "M":
            m += 1
            cm += c
        elif S[i] == "C":
            c += 1
            mc += m
    #print(m, c, mc, cm)
    for i in range(N-2):
        #print(i+k-1)
        right = i+k-1
        if right < N:
            if S[right] == "M":
                m += 1
                cm += c
            elif S[right] == "C":
                c += 1
                mc += m
        if S[i] == "D":
            ans += mc
        elif S[i] == "M":
            m -= 1
            mc -= c
        elif S[i] == "C":
            c -= 1
            cm -= m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re

def literalIndexArray(inputStr,searchStr):
    result = []
    for index,chr in enumerate(inputStr):
        if chr == searchStr:
            result.append(index)
    return result

def checkRuleA(d,c,k):
    return c - d < k

def checkRuleB(d,m,c):
    return d < m < c


n = int(input()) #文字列の長さ
s = str(input()) #文字列
q = int(input()) #kの数
ks = str(input()) #kの配列
k_array = [int(k) for k in ks.split()]

patternD = literalIndexArray(s,'D')
patternM = literalIndexArray(s,'M')
patternC = literalIndexArray(s,'C')

for k in k_array:
    answer = 0
    for d in patternD:
        for c in patternC:
            if checkRuleA(d,c,k):
                for m in patternM:
                    if checkRuleB(d,m,c):
                        answer+= 1
    print(answer)

Submission status: Time Limit Exceeded

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

for x in k:
    cnt=0
    for i in range(n-1,1,-1):
        if s[i] =='C':
            c=i
            for j in range(i,0,-1):
                if s[j] =='M':
                    b=j
                    for k in range(j,-1,-1):
                        if s[k] =='D':
                            a=k
                            if 0<=a<b<c and c-a<x:
                                cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())
k = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

def counter(S, ki):
  count = 0
  for i in range(0, len(S)):
    if S[i] != 'D':
      continue
    for j in range( i+2, len(S)):
      if j - i <=1 or j - i >= ki or S[j] != 'C' or not 'M' in S[i:j]:
        continue
      for l in range(i+1, j):
        if S[l] == 'M':
          count += 1
  return count
  
for ki in k:
  print(counter(S, ki))

Submission status: Time Limit Exceeded

Solution code:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
S = input()
Q, = getIntList()
zk = getIntList()


for K in zk:
    tm = 0
    tc = 0
    tmc = 0
    re = 0
    for i in range(K-1):
        if S[i] == 'M':
            tm+=1
        elif S[i] =='C':
            tc +=1
            tmc += tm
    tail = K-2
    for i in range(N-2):
        # move
        tail += 1

        if S[i] == 'M':
            tm -=1
            tmc -= tc
        elif S[i] =='C':
            tc -=1
            
        if tail <N:
            if S[tail]=='M':
                tm += 1 
            elif S[tail] =='C':
                tc += 1
                tmc += tm
        #dprint(i, tmc)                
        if S[i] =='D':
            re += tmc
    print(re)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())
k = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

def counter(S, ki):
  count = 0
  for i in range(0, len(S)): 
    if S[i] != 'D':
      continue
    for j in range( i+2, len(S)):
      if j - i <=1 or j - i >= ki or S[j] != 'C':
        continue
      for l in range(i+1, j):
        if S[l] == 'M':
          count += 1
  return count
  
for ki in k:
  print(counter(S, ki))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin

def load():
    n = int(stdin.readline())
    s = stdin.readline()
    q = int(stdin.readline())
    k = [int(x) for x in stdin.readline().split()]
    
    return (s, k)

def calc(s, ks):
    dmcmap = dmc(s)
    for k in ks:
        print(sum(dmcmap[:k]), flush=True)

def dmc(src):
    ret = [0 for _ in range(len(src))]

    for ind in range(len(src)):
        if src[ind] == 'D':
            for inm in range(ind+1, len(src)):
                if src[inm] == 'M':
                    for inc in range(inm+1, len(src)):
                        if src[inc] == 'C':
                            ret[inc-ind] += 1
    return ret

s, ks = load()
calc(s,ks)

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:
    count = 0
    for i in range(S.count('D')):
        if i == 0:
            a = S.find('D')
        else:
            a = S.find('D', a+1)

        for j in range(S.count('M')):
            if j == 0:
                b = S.find('M', a+1)
            else:
                b = S.find('M', b+1)
            if b == -1:
                break

            for m in range(S.count('C')):
                if m == 0:
                    c = S.find('C', b + 1)
                else:
                    c = S.find('C', c + 1)
                if c == -1:
                    break

                if (c - a) < k:
                    count += 1
                else:
                    break
    print(count)

Submission status: Time Limit Exceeded

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

def solve(k):
    Dlive = 0
    Dn = 0
    Dpos = []
    DM = []
    tmp = 0
    DMs = 0
    DMC = 0

    pos = 0
    for c in s:
        if c == 'D':
            Dn += 1
            Dpos.append(pos)
            DM.append(0)
        elif c == 'M':
            if Dn > 0:
                DM[Dn - 1] += 1
                tmp += 1
            DMs += Dn - Dlive
        elif c == 'C':
            DMC += DMs

        pos += 1
        if Dlive < Dn:
            if pos - Dpos[Dlive] >= k:
                DMs -= tmp
                tmp -= DM[Dlive]
                Dlive += 1
    
    return DMC

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

if __name__ == "__main__":
    n = int(input())
    s = str(input())
    q = int(input())
    ks = list(map(int, input().split()))

    string = [None for _ in range(n)]
    for i in range(n):
        string[i] = s[i]
    string = np.array(string)

    d_site = np.array(string == "D")
    m_site = np.array(string == "M")
    c_site = np.array(string == "C")

    nums = [0 for _ in range(q)]

    for main_i in range(n):
        if c_site[main_i]:
            for i in range(q):
                start = main_i - ks[i] +1
                if start < 0:
                    start = 0

                m_site_dum = np.where(m_site[start:main_i])[0].reshape(-1)

                for j in range(len(m_site_dum)):
                    m_dum = m_site_dum[j]
                    nums[i] += np.sum(d_site[start:main_i][:m_dum]==True)

    for i in range(q):
        print(nums[i])

Submission status: Time Limit Exceeded

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

#%%
# n = 54
# s = "DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED"
# q = 3
# k = [20, 30, 40]


#%%
idx_a = []
idx_b = []
idx_c = []

#%%
for i in range(len(s)):
    if s[i] == "D":
        idx_a.append(i)
    if s[i] == "M":
        idx_b.append(i)
    if s[i] == "C":
        idx_c.append(i)


#%%
import itertools

for ki in k:
    ans=0
    for i in itertools.product(idx_a, idx_b, idx_c):
        if i[2]-i[0]<ki and i[0]<i[1] and i[1]<i[2]:
            ans += 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 k in K:
    count = 0
    for i in range(S.count('D')):
        if i == 0:
            a = S.find('D')
        else:
            a = S.find('D', a+1)

        for j in range(S.count('M')):
            if j == 0:
                b = S.find('M', a+1)
            else:
                b = S.find('M', b+1)
            if b == -1:
                break

            for m in range(S.count('C')):
                if m == 0:
                    c = S.find('C', b + 1)
                else:
                    c = S.find('C', c + 1)
                if c == -1:
                    break

                if (c - a) < k:
                    count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
ks = [int(x) for x in input().split()]

for k in ks:
    res = 0
    for i, d in enumerate(S[:len(S)-2]):
        if d == 'D':
            for j, m in enumerate(S[i+1:i+k]):
                if m == 'M':
                    res += S[i+j+1:i+k].count('C')
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
	n = int(input())
	s = input()
	q = int(input())
	k = list(map(int, input().split()))
	#print(n, s, q, k)
	
	
	for times in range(q):
		know = k[times]
		dp = np.zeros((know, 3))
		r = 0
		for i in range(n):
			#print("at", i, s[i])
			if(s[i] == "D"):
				r += dp[-1][-1]
				for j in range(know-1):
					dp[know-1-j] = dp[know-1-j-1]
				dp[0][0] = 1
			elif(s[i] == "M"):
				r += dp[-1][-1]
				for j in range(know-1):
					dp[know-1-j][0] = dp[know-1-j-1][0]
					dp[know-1-j][1] = dp[know-1-j-1][1]+dp[know-1-j-1][0]
					dp[know-1-j][2] = dp[know-1-j-1][2]
				dp[0][0] = 0
			elif(s[i] == "C"):
				r += dp[-1][-1]
				for j in range(know-1):
					dp[know-1-j][0] = dp[know-1-j-1][0]
					dp[know-1-j][1] = dp[know-1-j-1][1]
					dp[know-1-j][2] = dp[know-1-j-1][2]+dp[know-1-j-1][1]
				dp[0][0] = 0
			else:
				r += dp[-1][-1]
				for j in range(know-1):
					dp[know-1-j] = dp[know-1-j-1]
				dp[0][0] = 0
			#print(dp.T)
		r += np.sum((dp.T)[2])	
		print(int(r))
		#print(know)

	
main()

Submission status: Time Limit Exceeded

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

for x in k:
    a,b,c=[],[],[]
    cnt=0
    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 i in a:
        for j in b:
            for k in c:
                if 0<=i<j<k and k-i<x:
                    cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
for i in k:
  dp = [[0]*4 for _ in range(n)]
  dp[-1][0] = 1
  for j in range(n):
    dp[j][0] += dp[j-1][0]
    dp[j][1] += dp[j-1][1]
    dp[j][2] += dp[j-1][2]
    dp[j][3] += dp[j-1][3]
    if x[j] == 1:
      dp[j][1] += dp[j-1][0]
    elif x[j] == 2:
      dp[j][2] += dp[j-1][1]
    elif x[j] == 3:
      dp[j][3] += dp[j-1][2]
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[j][1] -= 1
        dp[j][2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp[n-1][3])

Submission status: Time Limit Exceeded

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

for k in K:
    count = 0
    prev_d = 0
    for i in range(S.count('D')):
        index_d = prev_d + S[prev_d:].index('D')
        prev_m = index_d
        for j in range(S[index_d:index_d+k].count('M')):
            index_m = prev_m + S[prev_m:index_d+k].index('M')

            if S[index_m:index_d+k].count('C') == 0:
                break

            count += S[index_m:index_d+k].count('C')
            prev_m = index_m+1
        prev_d = index_d+1

    print(count)

Submission status: Time Limit Exceeded

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

# #%%
# n = 54
# s = "DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED"
# q = 3
# k = [20, 30, 40]


#%%
idx_a = []
idx_b = []
idx_c = []

#%%
for i in range(len(s)):
    if s[i] == "D":
        idx_a.append(i)
    if s[i] == "M":
        idx_b.append(i)
    if s[i] == "C":
        idx_c.append(i)
        



#%%
for ki in k:
    ans = 0
    for a in idx_a[::-1]:
        for c in idx_c:
            if a < c:
                if c - a < ki:
                    for b in idx_b:
                        if a<b:
                            if b<c:
                                ans += 1
                            else:
                                break
                else:
                    break
    print(ans)            

#%%

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
q = int(input())
K = list(map(int, input().split()))
s = list(s)
Dlist = [i for i, v in enumerate(s) if v == 'D']
Mlist = [i for i, v in enumerate(s) if v == 'M']
Clist = [i for i, v in enumerate(s) if v == 'C']
for i in K:
  count_i = 0
  for j in Dlist:
    for k in Mlist:
      if j < k:   
        for l in Clist:
          if k < l:
            if l - j < i:
              count_i += 1
  print(count_i)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())
k = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

def counter(S, ki):
  count = 0
  for i in range(0, len(S)): 
    for j in range( i+2, len(S)):
      if j - i <=1 or j - i >= ki:
        continue
      for l in range(i+1, j):
        if (S[i], S[l], S[j]  ) == ('D', 'M', 'C'):
          count += 1
  return count
  
for ki in k:
  print(counter(S, ki))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
Q = int(input())
num = [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)

count = [0] * Q


for str_d in a:
    for str_m in b:
        for str_c in c:
            for j in range(Q):
                if str_c - str_d < num[j] and str_d < str_m and str_m < str_c:
                    count[j] += 1


for str in count:
    print(str)

Submission status: Time Limit Exceeded

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

Solution code:
n = int(input())
s = str(input())
q = int(input())
K = list(map(int, input().split()))
s = list(s)
Dlist = [i for i, v in enumerate(s) if v == 'D']
Mlist = [i for i, v in enumerate(s) if v == 'M']
Clist = [i for i, v in enumerate(s) if v == 'C']
for i in K:
  count_i = 0
  for j in Dlist:
    for k in Mlist:
      for l in Clist:
        if j < k < l and l - j < i:
          count_i += 1
  print(count_i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
Q = int(input())
num = [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)

count = [0] * Q

for j in range(Q):
    for str_d in a:
        for str_m in b:
            for str_c in c:
                if str_c - str_d < num[j] and str_d < str_m and str_m < str_c:
                    count[j] += 1


for str in count:
    print(str)