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:
def main():
    # import sys
    # input = sys.stdin.readline
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]
    
    # print (d_list)
    # print (m_list)
    # print (c_list)
    # print (M_list)



    def calc(k):
        # d = 0
        # m = 0
        # c = 0
        # M = 0
        # for s in S[:k]:
        #     if s == 'D':
        #         d += 1
        #     elif s == 'M':
        #         m += d
        #         M += 1
        #     elif s == 'C':
        #         c += m
        # print (d, m, c)

        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            tmp = S[index]
            if tmp == 'D':
                m -= M
                d -= 1
            elif tmp == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
            # print (d, m, c)
                
        return c

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

    # print (calc(5))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S[:-1]):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]
    
    # print (d_list)
    # print (m_list)
    # print (c_list)
    # print (M_list)



    def calc(k):
        # d = 0
        # m = 0
        # c = 0
        # M = 0
        # for s in S[:k]:
        #     if s == 'D':
        #         d += 1
        #     elif s == 'M':
        #         m += d
        #         M += 1
        #     elif s == 'C':
        #         c += m
        # print (d, m, c)

        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            tmp = S[index]
            if tmp == 'D':
                m -= M
                d -= 1
            elif tmp == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
            # print (d, m, c)
                
        return c

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

    # print (calc(5))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = list(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]
    
    # print (d_list)
    # print (m_list)
    # print (c_list)
    # print (M_list)



    def calc(k):
        # d = 0
        # m = 0
        # c = 0
        # M = 0
        # for s in S[:k]:
        #     if s == 'D':
        #         d += 1
        #     elif s == 'M':
        #         m += d
        #         M += 1
        #     elif s == 'C':
        #         c += m
        # print (d, m, c)

        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
            # print (d, m, c)
                
        return c

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

    # print (calc(5))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    def calc(k):
        d = 0
        m = 0
        c = 0
        M = 0
        for s in S[:k]:
            if s == 'D':
                d += 1
            elif s == 'M':
                m += d
                M += 1
            elif s == 'C':
                c += m
        # print (d, m, c)
        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
            # print (d, m, c)
                
        return c

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

    # print (calc(5))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def calc(k):
    d = 0
    m = 0
    c = 0
    M = 0
    for s in S[:k]:
        if s == 'D':
            d += 1
        elif s == 'M':
            m += d
            M += 1
        elif s == 'C':
            c += m
    # print (d, m, c)
    for index, x in enumerate(S[k:]):
        if S[index] == 'D':
            m -= M
            d -= 1
        elif S[index] == 'M':
            M -= 1

        if x == 'D':
            d += 1
        elif x == 'M':
            m += d
            M += 1
        elif x == 'C':
            c += m            
        # print (d, m, c)
            
    return c

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

# print (calc(5))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [{"D":0,"M":0,"DM":0}]
C = []
for i in range(N):
    q = DP[i].copy()
    if S[i] == "D":
        q["D"] += 1
    elif S[i] == "M":
        q["M"] += 1
        q["DM"] += q["D"]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c]["DM"]
        else:
            ans += DP[c]["DM"] - DP[c-k]["DM"] - DP[c-k]["D"]*(DP[c]["M"] - DP[c-k]["M"])
    print(ans)

Submission status: Time Limit Exceeded

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

def func(k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S[i] == "D":
            D += 1
        elif S[i] == "M":
            M += 1
            DM += D
        elif S[i] == "C":
            ans += 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":
            M += 1
            DM += D
        elif S[i] == "C":
            ans += DM
    return ans
for i in K:
    print(func(i))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            dd, mm, dmm = dp[ll]
            As[j] += dm - dmm - dd*(m-mm)
    dp.append([d,m,dm])
for a in As:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from itertools import product
N=int(input())
S=input()
Q=int(input())
k = list(map(int,input().split()))

D = []
M = []
C = []
for i,s in enumerate(S):
    if s == 'D':
        D.append(i)
    if s == 'M':
        M.append(i)
    if s == 'C':
        C.append(i)
DC = []
for m in M:
    d = [i for i in D if i < m]
    c = [i for i in C if i > m]
    for i in product(d,c):
        DC.append(i[1]-i[0])
for i in k:
    ans = [j for j in DC if j < i]
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - dp[ll][2] - dp[ll][0]*(m-dp[ll][1])
    dp.append([d,m,dm])
for a in As:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dp = [[0,0,0] for _ in range(N+1)]
As = [0]*qn
for i, c in enumerate(S):
    i += 1
    dp[i][0] = dp[i-1][0] + (c=="D")
    dp[i][2] = dp[i-1][2] + (c=="M")
    dp[i][1] = dp[i-1][1] + (c=="M")*dp[i-1][0]
    if c != "C":
        continue
    for j, q in enumerate(qs):
        ll = max(i-q, 0)
        As[j] += dp[i-1][1] - dp[ll][1] - dp[ll][0]*(dp[i-1][2]-dp[ll][2])
for a in As:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))


dp = [[0,0,0,0] for _ in range(N+1)]
As = [0]*qn
for i, c in enumerate(S):
    i += 1
    if c == "D":
        dp[i][0] = dp[i-1][0] + 1
    else:
        dp[i][0] = dp[i-1][0]
    if c == "M":
        dp[i][1] = dp[i-1][1] + dp[i-1][0]
        dp[i][3] = dp[i-1][3] + 1
    else:
        dp[i][1] = dp[i-1][1]
        dp[i][3] = dp[i-1][3]
    if c == "C":
        dp[i][2] = dp[i-1][2] + dp[i-1][1]
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
#            print(i, i-1, i-q, q)
#            print(dp[i-1], dp[ll]) 
            As[j] += dp[i-1][1] - dp[ll][1] - (dp[ll][0]*(dp[i-1][3]-dp[ll][3]))
    else:
        dp[i][2] = dp[i-1][2]
for a in As:
    print(a)
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    s = input()
    q = I()
    K = LI()
    for k in K:
        ans = 0
        l = deque()
        sa = 0
        sb = 0
        ns = 0
        for i in range(n):
            if l:
                if i-l[0][0] >= k:
                    if l[0][1]:
                        sb -= 1
                    else:
                        ns -= sb
                        sa -= 1
                    l.popleft()
            if s[i] == "D":
                sa += 1
                l.append([i,0])
            elif s[i] == "M":
                sb += 1
                l.append([i,1])
                ns += sa
            elif s[i] == "C":
                ans += ns
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=tuple(map(ord,input()))
Q=int(input())
K=map(int,input().split())
D,M,C=map(ord,'DMC')

for k in K:
    ans=0
    d=m=dm=0
    for i in range(N):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
        if i>=k-1:
            c=S[i-(k-1)]
            if c==D:
                d-=1
                dm-=m
            elif c==M:
                m-=1
    print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
S=input()
Q=int(input())
K=map(int,input().split())

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

Submission status: Time Limit Exceeded

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

for k in K:
    D=[]
    M=[]
    C=[]
    for i in range(N):
        c=S[i]
        if c=='D':
            D.append(i)
        elif c=='M':
            M.append(i)
        elif c=='C':
            C.append(i)
    ans=0
    for d in D:
        for m in M:
            if m<=d or m-d>=k:
                continue
            for c in C:
                if c<=m or c-d>=k:
                    continue
                ans+=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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
s = input()
ns = np.array(list(s))
q = int(input())
k = list( map(int, input().split()) )

for ki in k:
	cnt = 0
	for i in range(0, n-2):
		d = ns[i]
		if d == 'D':
			kmax = min(n, i+ki )
			for j in range(i+1, kmax-1):
				m = ns[j]
				if ns[j] == 'M':
					tmp = np.count_nonzero(ns[j+1:kmax:] == 'C')
					cnt += tmp
	print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S, Q, K):

    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

            j = i-k+1
            if j < 0:
                continue

            if S[j] == 'D':
                d -= 1
                dm -= m
            elif S[j] == 'M':
                m -= 1
        print(ans)


def main():
    N = read_int()
    S = read_str()
    Q = read_int()
    K = read_int_n()
    (slv(N, S, Q, K))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
s=input()
q=int(input())
Q=map(int,input().split())
A=[]
data=[0]*(n+1)
for i,si in enumerate(s):
    if si == "D":
        A.append((i,count))
    elif si == "M":
        count+=1
    elif si == "C":
        for ai,ac in A:
            data[i-ai]+=count-ac
for i in range(len(data)-1):
    data[i+1]+=data[i] 
for qi in Q:
    print(data[qi-1])
# print(data)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

lid = []
lim = []
lic = []

for i in range(n):
    if s[i] == 'D':
        lid.append(i)
    elif s[i] == 'M':
        lim.append(i)
    elif s[i] == 'C':
        lic.append(i)

dmc = []
lid_r = 0
lic_l = 0

for i in lim:
    while lid_r < len(lid):
        if lid[lid_r] < i:
            lid_r += 1
        else:
            break
    while lic_l < len(lic):
        if lic[lic_l] < i:
            lic_l += 1
        else:
            break
    if lid_r != 0 and lic_l != len(lic):
        for j in range(lid_r):
            for kk in range(lic_l,len(lic)):
                dmc.append((lid[j], i, lic[kk]))

dis_dmc = []

for a,b,c in dmc:
    dis_dmc.append(c-a)

dis_dmc.sort()

for ki in k:
    print(bisect.bisect_left(dis_dmc, ki))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    s = S()
    q = II()
    k = LI()
    next_d = defaultdict(int)
    next_m = [0] * n
    next_c = [0] * n
    b = -1
    for i, si in enumerate(s):
        if si == "D":
            next_d[b] = i + 1
            b = i
        elif si == "M" and i != 0:
            next_m[i-1] = i
        elif si == "C":
            next_c[i] += 1
    for i in range(1, n):
        if next_m[-i - 1] == 0:
            next_m[-i - 1] = next_m[-i]
    next_c = list(itertools.accumulate(next_c))
    for ki in k:
        ans = 0
        d = -1
        while next_d[d]:
            d = next_d[d] - 1
            m = d
            x = ki + d- 1 if ki + d - 1 < n else n - 1
            while next_m[m]:
                m = next_m[m]
                if x <= m:
                    break
                ans += next_c[x] - next_c[m]

        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    S=input()
    input()
    for k in map(int,input().split()):
        d,m,c=0,0,0 # スライド内の D,M,C の個数
        cnt=0 # スライド内の D<M の個数
        ans=0
        for i in range(n):
            s=S[i]
            # push
            if(s=='D'):
                d+=1
            elif(s=='M'):
                m+=1
                cnt+=d
            elif(s=='C'):
                c+=1
                ans+=cnt

            # pop
            if(i-k+1<0): continue
            t=S[i-k+1]
            if(t=='D'):
                d-=1
                cnt-=m
            elif(t=='M'):
                m-=1
            elif(t=='C'):
                c-=1

        print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    S=input()
    input()
    for k in map(int,input().split()):
        DMC=[0]*3 # スライド内の D,M,C の個数
        cnt=0 # スライド内の D<M の個数
        ans=0
        for i in range(n):
            s=S[i]
            # push
            if(s=='D'):
                DMC[0]+=1
            elif(s=='M'):
                DMC[1]+=1
                cnt+=DMC[0]
            elif(s=='C'):
                DMC[2]+=1
                ans+=cnt

            # pop
            if(i-k+1<0): continue
            t=S[i-k+1]
            if(t=='D'):
                DMC[0]-=1
                cnt-=DMC[1]
            elif(t=='M'):
                DMC[1]-=1
            elif(t=='C'):
                DMC[2]-=1

        print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n=int(input())
    S=input()
    input()
    for k in map(int,input().split()):
        DMC=[0]*3 # スライド内の D,M,C の個数
        cnt=0 # スライド内の D<M の個数
        ans=0
        Q=deque()
        for s in S:
            # push
            if(s=='D'):
                DMC[0]+=1
            elif(s=='M'):
                DMC[1]+=1
                cnt+=DMC[0]
            elif(s=='C'):
                DMC[2]+=1
                ans+=cnt
            Q.append(s)

            # pop
            if(len(Q)<k): continue
            t=Q.popleft()
            if(t=='D'):
                DMC[0]-=1
                cnt-=DMC[1]
            elif(t=='M'):
                DMC[1]-=1
            elif(t=='C'):
                DMC[2]-=1

        print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right,bisect_left
N = int(input())
S = input().strip()
C = {"D":[],"M":[],"C":[]}
for i in range(N):
    if S[i] in C:
        C[S[i]].append(i)
Q = int(input())
K = list(map(int,input().split()))
for i in range(Q):
    k = K[i]
    cnt = 0
    for i in C["D"]:
        l = bisect_right(C["C"],i)
        r = bisect_left(C["C"],i+k)
        for j in range(l,r):
            low = bisect_right(C["M"],i)
            high = bisect_right(C["M"],C["C"][j])
            cnt += high-low
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right,bisect_left
def dmc(i):
    jmin = bisect_right(C["M"],i)
    for j in range(jmin,len(C["M"])):
        kmin = bisect_right(C["C"],C["M"][j])
        for k in range(kmin,len(C["C"])):
            A.append(C["C"][k]-i)
N = int(input())
S = input().strip()
C = {"D":[],"M":[],"C":[]}
for i in range(N):
    if S[i] in C:
        C[S[i]].append(i)
A = []
for i in C["D"]:
    dmc(i)
A = sorted(A)
Q = int(input())
K = list(map(int,input().split()))
for i in range(Q):
    k = K[i]
    print(bisect_left(A,k))

Submission status: Time Limit Exceeded

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

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

for ki in k :
    d = m = dm = dmc = 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

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

Submission status: Time Limit Exceeded

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

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

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

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