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 = [int(_) for _ in input().split()]

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

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:
        if c > 1:
            ans += DM[c-1]
            if c-k+1 > 0:
                ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)

Submission status: Time Limit Exceeded

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

    for k in ks:
        ans = 0
        cnt = 0
        d = 0
        m = 0
        for i in range(n):
            if s[i] == 'D':
                d += 1
            elif s[i] == 'M':
                m += 1
                cnt += d
            elif s[i] == 'C':
                ans += cnt

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

        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

ans = []
Dcnt = [0 for i in range(len(kL))]
Mcnt = [0 for i in range(len(kL))]
DMcnt = [0 for i in range(len(kL))]
DMCcnt = [0 for i in range(len(kL))]
for i in range(len(S)):
    for j in range(len(kL)):
        k = kL[j]
        if i-k >= 0 and S[i-k] == 'D':
            Dcnt[j] -= 1
            DMcnt[j] -= Mcnt[j]
        elif i-k >= 0 and S[i-k] == 'M':
            Mcnt[j] -= 1

        if S[i] == 'D':
            Dcnt[j] += 1
        elif S[i] == 'M':
            Mcnt[j] += 1
            DMcnt[j] += Dcnt[j]
        elif S[i] == 'C':
            DMCcnt[j] += DMcnt[j]

for a in DMCcnt:
    print(a)

Submission status: Time Limit Exceeded

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

ans = []
for k in kL:
    Dcnt = 0
    Mcnt = 0
    DMcnt = 0
    DMCcnt = 0
    for i in range(len(S)):
        if i-k >= 0 and S[i-k] == 'D':
            Dcnt -= 1
            DMcnt -= Mcnt
        elif i-k >= 0 and S[i-k] == 'M':
            Mcnt -= 1

        if S[i] == 'D':
            Dcnt += 1
        elif S[i] == 'M':
            Mcnt += 1
            DMcnt += Dcnt
        elif S[i] == 'C':
            DMCcnt += DMcnt
    ans.append(DMCcnt)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict

input = sys.stdin.readline


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

for k in K:
    ret = 0
    d = 0
    m = 0
    dm = 0

    for i in range(N):
        s = S[i]

        if s == "C":
            ret += dm

        if s == "D":
            d += 1
        elif s == "M":
            m += 1
            dm += d

        j = i - k + 1
        if j >= 0:
            s2 = S[j]
            if s2 == "D":
                d -= 1
                dm -= m
            elif s2 == "M":
                m -= 1
    print(ret)



sys.exit(0)

Submission status: Time Limit Exceeded

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

anss = []
for K in Ks:
    cnt_d, cnt_m, sum_dm, ans = 0,0,0,0
    for i in range(N):
        if i-K>=0:
            if S[i-K]=="D":
                cnt_d -= 1
                sum_dm -= cnt_m
            elif S[i-K]=="M":
                cnt_m -= 1

        if S[i]=="D":
            cnt_d += 1
        elif S[i]=="M":
            sum_dm += cnt_d
            cnt_m += 1
        elif S[i]=="C":
            ans += sum_dm
    anss.append(ans)
    
print(*anss, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
q = int(input())

k = list(map(int,input().split(' ')))

chars = ['D','M','C']

idx = 0
bmin = s.find('M')
bmax = s.rfind('M')

#print ("bmax-min:" + str(bmax) +  " " + str(bmin))

clist = []
for c in chars :
    idx = 0
    tlist = []
    while True:
        tmp = s.find(c, idx)
        if tmp < 0 :
            break
        else :
            tlist.append(tmp)
        idx = tmp + 1
    clist.append(tlist)

#print(clist)
clist[1].sort()

aclen = []
count = 0
for c in clist[2][::-1]:
    if bmin < c :
        for a in clist[0]:
            if bmax > a :
                #print("a:c " + str(a) + " " + str(c) )
                bcount = 0
                for b in clist[1]:
                    if a < b and b < c :
                        bcount += 1
                aclen.append([c-a,bcount])

#print(aclen)          
aclen.sort()
#print("len: " + str(aclen))

for lk in k :
    count = 0
    for acl in aclen:
        if acl[0] < lk :
            count += acl[1]
    print(count)

Submission status: Time Limit Exceeded

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

def cal(k):
    ans=0
    for i in range(N): 
        if(S[i]=="D"):
            j=i+1
            while(j<i+k and j<N):
                if(S[j]=="M"):
                    ans+=S[j:i+k].count("C")
                j+=1
    return ans

for i in k:
    print(cal(i))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            c = S[i]
            prevc = S[i-k]
            if i-k >= 0 and prevc == "D":
                d_cnt -= 1
                dm_cnt -= m_cnt
            elif i-k >= 0 and prevc == "M":
                m_cnt -= 1
            if c == "D":
                d_cnt += 1
            elif c == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif c == "C":
                answer += dm_cnt
        print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for k in karr:
    D=0
    M=0
    DM=0
    ans=0
    for i,x in enumerate(S):
        if x=='D':
            D+=1
        elif x=='M':
            M+=1
            DM+=D
        elif x=='C':
            ans+=DM
        
        if i >=k-1:
            y=S[i-k+1]
            if y=='D':
                D-=1
                DM-=M
            elif y=='M':
                M-=1
    print(ans)

Submission status: Time Limit Exceeded

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


def kDMC(k):
    count_dmc = 0
    count_d = 0
    count_dm = 0
    count_m = 0

    for i_append in range(n):
        i_remove = i_append - k
        if 0 <= i_remove:
            if s[i_remove] == 'D':
                count_d -= 1
                count_dm -= count_m
            elif s[i_remove] == 'M':
                count_m -= 1

        if s[i_append] == 'D':
            count_d += 1
        elif s[i_append] == 'M':
            count_m += 1
            count_dm += count_d
        elif s[i_append] == 'C':
            count_dmc += count_dm

    return count_dmc


for k in ks:
    print(kDMC(k))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict

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


for k in K:
    ret = 0
    d = 0
    m = 0
    dm = 0

    for i in range(N):
        s = S[i]

        if s == "C":
            ret += dm

        if s == "D":
            d += 1
        elif s == "M":
            m += 1
            dm += d

        j = i - k + 1
        if j >= 0:
            s2 = S[j]
            if s2 == "D":
                d -= 1
                dm -= m
            elif s2 == "M":
                m -= 1
    print(ret)



sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict

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


for k in K:
    ret = 0
    d = 0
    m = 0
    dm = 0

    for i in range(N):
        s = S[i]

        if s == "C":
            ret += dm

        if s == "D":
            d += 1
        elif s == "M":
            m += 1
            dm += d

        j = i - k + 1
        if j >= 0:
            s2 = S[j]
            if s2 == "D":
                d -= 1
                dm -= m
            elif s2 == "M":
                m -= 1
    print(ret)








sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from itertools import accumulate

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

ri = bisect.bisect(a_loc, b_loc[-1])
q = int(input())
b_acc = [0] + list(accumulate(c_acc[b] for b in b_loc))
buf = []
for k in map(int, input().split()):
    ans = 0
    pi = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a, pi)
        j = bisect.bisect(b_loc, a + k - 1, i)
        ans += c_acc[min(n, a + k)] * (j - i) - (b_acc[j] - b_acc[i])
        pi = i
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
import bisect
from itertools import accumulate

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
b_acc = [0] + list(accumulate(c_acc[b] for b in b_loc))
buf = []
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        ans += c_acc[min(n, a + k)] * (j - i) - (b_acc[j] - b_acc[i])
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

b_rightest = b_loc[-1]
ri = bisect.bisect(a_loc, b_rightest)
q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0]
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc.append(c_cnt)

q = int(input())
for k in map(int, input().split()):
    ans = 0
    for a in a_loc:
        i = bisect.bisect(b_loc, a)
        j = bisect.bisect(b_loc, a + k - 1, i)
        cn = c_acc[min(n, a + k)]
        for b in b_loc[i:j]:
            ans += cn - c_acc[b]
    print(ans)

Submission status: Time Limit Exceeded

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

anss = []
for K in Ks:
    cnt_d, cnt_m, sum_dm, ans = 0,0,0,0
    for i in range(N):
        if i-K>=0:
            if S[i-K]=="D":
                cnt_d -= 1
                sum_dm -= cnt_m
            elif S[i-K]=="M":
                cnt_m -= 1

        if S[i]=="D":
            cnt_d += 1
        elif S[i]=="M":
            sum_dm += cnt_d
            cnt_m += 1
        elif S[i]=="C":
            ans += sum_dm
    anss.append(ans)
    
for a in anss:
  print(a)

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:
    cnt_d, cnt_m, sum_dm = 0,0,0
    ans = 0
    for i in range(N):
        if i-K>=0:
            if S[i-K]=="D":
                cnt_d -= 1
                sum_dm -= cnt_m
            elif S[i-K]=="M":
                cnt_m -= 1

        if S[i]=="D":
            cnt_d += 1
        elif S[i]=="M":
            sum_dm += cnt_d
            cnt_m += 1
        elif S[i]=="C":
            ans += sum_dm

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    d = {}
    for i in range(N):
        if S[i] == 'D':
            d[i] = MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M
    res = 0
    for i in d:
        res += d[i]

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
while S[0] != 'D':
    S = S[1:]
S = S[::-1]
while S[0] != 'C':
    S = S[1:]
S = S[::-1]

N = len(S)

def cal(k):
    M = 0
    C = 0
    MC = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    d = {}
    for i in range(N):
        if S[i] == 'D':
            d[i] = MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M
    res = 0
    for i in d:
        res += d[i]

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

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:
    m = 0
    c = 0
    mc = 0
    ans = 0
    for s in S[:k-1]:
        if s == "M":
            m += 1
        elif s == "C":
            c += 1
            mc += m
    for i in range(N-2):
        right = i+k-1
        if right < N:
            s = S[right]
            if s == "M":
                m += 1
            elif s == "C":
                c += 1
                mc += m
        s = S[i]
        if s == "D":
            ans += mc
        elif s == "M":
            m -= 1
            mc -= c
        elif s == "C":
            c -= 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))

for k in K:
    m = 0
    c = 0
    mc = 0
    ans = 0
    for s in S[:k-1]:
        if s == "M":
            m += 1
        elif s == "C":
            c += 1
            mc += m
    for i in range(N-2):
        right = i+k-1
        if right < N:
            s = S[right]
            if s == "M":
                m += 1
            elif s == "C":
                c += 1
                mc += m
        s = S[i]
        if s == "D":
            ans += mc
        elif s == "M":
            m -= 1
            mc -= c
        elif s == "C":
            c -= 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:
    m = 0
    c = 0
    mc = 0
    ans = 0
    for i in range(k-1):
        if S[i] == "M":
            m += 1
        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
            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
    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_list:
    ans = 0
    d_count = 0
    m_count = 0
    dm_count = 0
    for i in range(len(s)):
        if s[i] == 'D':
            d_count += 1
        if s[i] == 'M':
            m_count += 1
            dm_count += d_count
        if s[i] == 'C':
            ans += dm_count

        if i >= k - 1:
            if s[i - k + 1] == 'D':
                d_count -= 1
                dm_count -= m_count
            if s[i - k + 1] == 'M':
                m_count -= 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            if i-k >= 0 and S[i-k] == "D":
                d_cnt -= 1
                dm_cnt -= m_cnt
            elif i-k >= 0 and S[i-k] == "M":
                m_cnt -= 1
            if S[i] == "D":
                d_cnt += 1
            elif S[i] == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif S[i] == "C":
                answer += dm_cnt
        print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a = []
for k in ks:
    t = 0
    cnt, d, m = 0, 0, 0
    for i in range(k):
        if s[i] == 'D':
            d += 1
        elif s[i] == 'M':
            cnt += d
            m += 1
        elif s[i] == 'C':
            t += cnt
    for i in range(k, n):
        if s[i - k] == 'D':
            cnt -= m
            d -= 1
        elif s[i - k] == 'M':
            m -= 1

        if s[i] == 'D':
            d += 1
        elif s[i] == 'M':
            cnt += d
            m += 1
        elif s[i] == 'C':
            t += cnt
    a.append(t)

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

Submission status: Time Limit Exceeded

Solution code:
#! length of string
length_input = input()
length = int(length_input)
#! content of string
test_str = input()
#! number of gaps
gaps_num_input = input()
gaps_num = int(gaps_num_input)
#! gaps
gaps_str = input()
#! get the gaps list
gaps_list = gaps_str.split(" ")
count = 0

list_D = []
list_M = []
list_C = []

#! get all the indexs of D,M,C
for char in test_str:
    if char == "D" :
        list_D.append(count)
        count += 1        
    elif char == "M" :    
        list_M.append(count)
        count += 1
    elif char == "C" :
        list_C.append(count)
        count += 1
    else :
        count += 1
        continue    
   
for gap_str in gaps_list:
    n = 0
    gap = int(gap_str)
    for i in list_D :
        for j in list_M :
            if i < j :
                for k in list_C :
                    if j < k :
                        if k-i < gap :
                            n += 1
                        else :
                            break
                    else :
                        continue
            else :
                continue
    
    print(n)

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_list:
    ans = 0
    d_count = 0
    m_count = 0
    dm_count = 0
    for i in range(len(s)):
        if s[i] == 'D':
            d_count += 1
        if s[i] == 'M':
            m_count += 1
            dm_count += d_count
        if s[i] == 'C':
            ans += dm_count

        if i >= k - 1:
            if s[i - k + 1] == 'D':
                d_count -= 1
                dm_count -= m_count
            if s[i - k + 1] == 'M':
                m_count -= 1

    print(ans)

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
dp = [[0]*4 for _ in range(n)]
for i in k:
  dp[-1] = [1,0,0,0]
  for j in range(n):
    dp[j] = dp[j-1]
    kon = x[j]
    if kon:
      dp[j][kon] += dp[j-1][kon-1]
    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:
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] = dp[j-1]
    kon = x[j]
    if kon:
      dp[j][kon] += dp[j-1][kon-1]
    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:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict

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

def calcD(start, end):
    if S[start] != "D":
        return 0
    return calcM(start,end)

def calcM(start,end):
    cnt = 0
    for i in range(start,end):
        if S[i] == "M":
            cnt += calcC(i+1,end)
    return cnt

def calcC(start,end):
    cnt = 0
    for i in range(start, end):
        if S[i] == "C":
            cnt += 1
    return cnt



for k in K:
    cnt = 0
    for start in range(N):
        cnt += calcD(start,min(start+k, N))
    print("{} ".format(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
S = [i for i in list(input())]
Q = int(input())
k = [int(i) for i in input().split()]
S = np.array(S, dtype=None)
 
index_D = np.where(S == 'D')[0]
index_M = np.where(S == 'M')[0]
index_C = np.where(S == 'C')[0]

for k_i in k:
    count = 0
    for c in index_C:
        for b in index_M[index_M - c < 0]:
            for a in index_D[index_D - b < 0]:
                if c-a < k_i:
                    count += 1
    print(count)

Submission status: Time Limit Exceeded

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

a = []
for k in ks:
    t = 0
    for i in range(n):
        if s[i] == 'C':
            p = s[max(0, i - k + 1):i]
            d = p.count('D')
            m = p.count('M')
            for j in range(len(p)):
                if p[j] == 'M': m -= 1
                if p[j] == 'D': t += m
    a.append(t)

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

Submission status: Time Limit Exceeded

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

for j in range(Q):
  threshold=k[j]
  answer=0
  nofD=0
  nofM=0
  combinationDM=0
  for i in range(N):
    if S[i]=='D':
      nofD+=1
    elif S[i]=='M':
      nofM+=1
      combinationDM+=nofD
    elif S[i]=='C':
      answer+=combinationDM
    if i>=threshold-1:
      if S[i-threshold+1]=='D':
        nofD-=1
        combinationDM-=nofM
      if S[i-threshold+1]=='M':
        nofM-=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 k in k_list:
    ans = 0
    for i in range(len(s)):
        if s[i] == 'C':
            j_start = i - k + 1 if i - k + 1 > 0 else 0
            d_amount = 0
            for j in range(j_start, i):
                if s[j] == 'D':
                    d_amount += 1
                if s[j] == 'M':
                    ans += d_amount
    print(ans)

Submission status: Time Limit Exceeded

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

for j in range(Q):
  threshold=k[j]
  answer=0
  for i in range(N):
    if S[i]=='C':
      nofD=0
      nofM=0
      combinationDM=0
      for a in range(max(0,i-threshold+1),i):
        if S[a]=='D':
          nofD+=1
        elif S[a]=='M':
          nofM+=1
          combinationDM+=nofD
      answer+=combinationDM
      #print(nofD,nofM,combinationDM,answer)
  print(answer)

Submission status: Time Limit Exceeded

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

for key in k_list:
    ans = 0
    for i in range(len(s)):
        if s[i] == 'C':
            j_start = i - key + 1 if i - key + 1 > 0 else 0
            for j in range(j_start, i):
                if s[j] == 'D':
                    for k in range(j + 1, i):
                        if s[k] == 'M':
                            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
k=list(map(int,input().split()))
di=s.count("D")
ma=max(k)
h=[]
for r in range(di):
    f=s.index("D")
    p=s[:]
    p=p[f+1:]
    s=s[f+1:]
    while p.count("C")!=0:
        j=p.index("C")
        if j+1<ma:
            h.append([j+1,p[:j].count("M")])
            p[j]="0"
        else:
            break
h.sort()
for i in range(q):
    c=0
    for t in range(len(h)):
        if h[t][0]<k[i]:
            c+=h[t][1]
        else:
            print(c)
            break
print(c)

Submission status: Time Limit Exceeded

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


for j in range(Q):
  threshold=k[j]
  answer=0
  Dindex=[]
  Mindex=[]
  Cindex=[]
  for i in range(N):
    if S[i]=='D':
      Dindex.append([i,0,0])
      continue;
    elif S[i]=='M':
      for j in range(len(Dindex)):
        Dindex[j][1]+=1
    elif S[i]=='C':
      for a in range(len(Dindex)):
        if i-Dindex[a][0]<threshold:
          Dindex[a][2]+=1
          answer+=Dindex[a][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 key in k_list:
    ans = 0
    for i in range(len(s) - 2):
        if s[i] == 'D':
            for j in range(i + 1, len(s) - 1):
                if s[j] == 'M':
                    for k in range(j + 1, len(s)):
                        if s[k] == 'C':
                            if (k - i) < key:
                                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 key in k_list:
    ans = 0
    for i in range(len(s)):
        if s[i] == 'D':
            for j in range(i, len(s)):
                if s[j] == 'M':
                    for k in range(j, len(s)):
                        if s[k] == 'C':
                            if (k - i) < key:
                                ans += 1
    print(ans)