Problem:


Score : 600 points

Problem Statement

In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short.

The name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.

Given a string S of length N and an integer k (k \geq 3),
he defines the k-DMC number of S as the number of triples (a, b, c) of integers that satisfy the following conditions:

0 \leq a < b < c \leq N - 1

S[a] = D

S[b] = M

S[c] = C

c-a < k

Here S[a] is the a-th character of the string S. Indexing is zero-based, that is, 0 \leq a \leq N - 1 holds.

For a string S and Q integers k_0, k_1, ..., k_{Q-1}, calculate the k_i-DMC number of S for each i (0 \leq i \leq Q-1).

Constraints

3 \leq N \leq 10^6

S consists of uppercase English letters

1 \leq Q \leq 75

3 \leq k_i \leq N

All numbers given in input are integers

Input

Input is given from Standard Input in the following format:

N
S
Q
k_{0} k_{1} ... k_{Q-1}

Output

Print Q lines.
The i-th line should contain the k_i-DMC number of the string S.

Sample Input 1

18
DWANGOMEDIACLUSTER
1
18

Sample Output 1

1

(a,b,c) = (0, 6, 11) satisfies the conditions.

Strangely, Dwango Media Cluster does not have so much DMC-ness by his definition.

Sample Input 2

18
DDDDDDMMMMMCCCCCCC
1
18

Sample Output 2

210

The number of triples can be calculated as 6\times 5\times 7.

Sample Input 3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

Sample Output 3

0
1
2

(a, b, c) = (0, 23, 36), (8, 23, 36) satisfy the conditions except the last one, namely, c-a < k_i.

By the way, DWANGO is an acronym for "Dial-up Wide Area Network Gaming Operation".

Sample Output 4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

Sample Output 4

10
52
110
140



Sample input:
18
DWANGOMEDIACLUSTER
1
18


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
S = LS2()
Q = I()
K = LI()


def query(k):
    res = 0
    a = 0  # (i-k,i] にあるDの個数
    b = 0  # (i-k,i] にあるMの個数
    c = 0  # (i-k,i] にある(D,M)の個数
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                a -= 1
                c -= b
            elif S[i-k] == 'M':
                b -= 1
        if S[i] == 'D':
            a += 1
        elif S[i] == 'M':
            b += 1
            c += a
        elif S[i] == 'C':
            res += c


print(*[query(k) for k in K],sep='\n')

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit

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

def func(ch):
    if ch == 'D':
        return 1
    if ch == 'M':
        return 2
    if ch == 'C':
        return 3
    return 0
    
S_arr = np.array([func(ch) for ch in S], dtype = np.int32)

@njit("i4(i4, i4[:], i4)", cache = True)
def solve(N, S_arr, k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM
    for i in range(k, N):
        if S_arr[i-k] == 1:
            D -= 1
            DM -= M
        elif S_arr[i-k] == 2:
            M -= 1

        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM

    return ans

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

Submission status: Wrong Answer

Solution code:
import os,io
from sys import stdout
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))
k = [[x,i] for i,x in enumerate(k)]
k.sort()

ans = [[0,-1] for i in range(q)]
for i in range(q):
    ans[i][1] = k[i][1]

def search(x):
    ind = x
    m = 0
    c = 0
    count = 0
    for num,i in enumerate(k):
        while ind+count < n and count < i[0]:
            if s[ind+count] == "M":
                m += 1
            elif s[ind+count] == "C":
                c += 1
                ans[num][0]+=m
            count += 1
    
for i in range(n):
    if s[i] == "D":
        search(i)

for i in range(1,q):
    ans[i][0] += ans[i-1][0]
ans.sort(key=lambda x: x[1])
for i,j in ans:
    print(i)

Submission status: Wrong Answer

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

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))
    d = 0
    m = 0
    dm = 0

    # print(s)

    for i in range(q):
        ans = 0
        k = K[i]
        for j in range(n):

            if j-k >= 0:
                if s[j-k] == "D":
                    d -= 1
                    dm -= m
                elif s[j-k] == "M":
                    m -= 1

            if s[j] == "D":
                d += 1
            elif s[j] == "M":
                m += 1
                dm += d
            elif s[j] == "C":
                ans += dm
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for k in K:
    res = 0
    D = deque()
    M = deque()
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            D.append(i)
        if S[i] == 'M':
            dm += len(D)
            M.append(i)
        if S[i] == 'C':
            res += dm
        if D and D[0] + k <= i + 1:
            d = D.popleft()
            dm -= len(M)
            if D:
                while M and D[0] > M[0]:
                    M.popleft()
            else:
                M = deque()
                dm = 0

    print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = 0
    m = 0
    dm = 0
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if s == "D":
            d += 1
        if s == "M":
            m += 1
            dm += d
        if s == "C":
            ans += dm

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=tuple(input())
q=int(input())
kl=tuple(map(int,input().split()))
for i in range(q):
    k=kl[i]
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k:
            if l[j-k]=='D':
                dm-=m
                d-=1
            if l[j-k]=='M':
                m-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(input())
q=int(input())
kl=list(map(int,input().split()))
for i in range(q):
    k=kl[i]
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k:
            if l[j-k]=='D':
                dm-=m
                d-=1
            if l[j-k]=='M':
                m-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(input())
q=int(input())
kl=list(map(int,input().split()))
for i in range(q):
    k=kl[i]
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        if l[j]=='M':
            m+=1
            dm+=d
        if l[j]=='C':
            ans+=dm
        if j>=k:
            if l[j-k]=='D':
                dm-=m
                d-=1
            if l[j-k]=='M':
                m-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (len(c) + 1)
ls = [0] * N
for i in range(len(c)):
  ccs[i + 1] = ccs[i] + cs[c[i]]
for i in range(len(d)):
  if S[i] == "D": ls[i] = bl(c, d[i])

#print(c, ccs)
for k in qs:
  res = 0
  for i in d:
    if S[i] != "D": continue
    l = ls[i]
    r = bl(c, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (r - l))
  print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
dp = [[0,0,0]]
d=m=dm=dmc=0
xs = set()
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        xs.add(i)
        dmc += dm
    dp.append([d,m,dm])
for q in map(int, input().split()):
    r = 0
    for i, (d, m, dm) in enumerate(dp):
        if i in xs:
            ll = i-q+1
            if ll > 0:
                dd, mm, dmm = dp[ll]
                r += dmm + dd*m-dd*mm
    print(dmc-r)

Submission status: Wrong Answer

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)
    dp.append([d,m,dm])
for a in As:
    print(a)

Submission status: Wrong Answer

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
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = input().rstrip()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            si = s[i]
            if i >= ki:
                if s[-ki +i] == "D":
                    d -= 1
                    dm -= m
                    dm%=mod
                if s[-ki + i] == "M":
                    m -= 1
            if si == "D":
                d += 1
            if si== "M":
                m += 1
                dm += d
                dm%=mod
            if si == "C":
                ans += dm
            ans %= mod
        print(ans)
    return


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

Submission status: Wrong Answer

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
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = input().rstrip()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            if i >= ki:
                if s[-ki +i] == "D":
                    d -= 1
                    dm -= m
                if s[-ki + i] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            if s[i] == "M":
                m += 1
                dm += d
            if s[i] == "C":
                ans += dm
            ans %= mod
        print(ans)
    return


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

Submission status: Wrong Answer

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
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = input().rstrip()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            if i >= ki:
                if s[ki - i] == "D":
                    d -= 1
                    dm -= m
                if s[ki - i] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            if s[i] == "M":
                m += 1
                dm += d
            if s[i] == "C":
                ans += dm
            ans %= mod
        print(ans)
    return


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

Submission status: Wrong Answer

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
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = input().rstrip()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            if i >= ki:
                if s[ki - i] == "D":
                    d -= 1
                    dm -= m
                if s[ki - i] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            if s[i] == "M":
                m += 1
                dm += d
            if s[i] == "C":
                ans += dm
        print(ans)
    return


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

Submission status: Wrong Answer

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
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = S()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            if i >= ki:
                if s[ki - i] == "D":
                    d -= 1
                    dm -= m
                if s[ki - i] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            if s[i] == "M":
                m += 1
                dm += d
            if s[i] == "C":
                ans += dm
        print(ans)
    return


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

Submission status: Wrong Answer

Solution code:
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s):
  m[i+1]=m[i]+(t>'D')
  f=t<'D'
  c[i+1]=c[i]+f
  x[i+1]=x[i]+f*m[i+1]
for k in k:
  k=int(k)
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    a+=t=='D'and(c[i]-c[j])*m[i]+x[j]-x[i]
  print(a)

Submission status: Wrong Answer

Solution code:
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s):
  m[i+1]=m[i]+(t>'D')
  f=t<'D'
  c[i+1]=c[i]+f
  x[i+1]=x[i]+f*m[i+1]
for k in k:
  a=0
  for i,t in e(s):
    j=min(n,i+int(k))
    a+=t=='D'and(c[i]-c[j])*m[i]+x[j]-x[i]
  print(a)

Submission status: Wrong Answer

Solution code:
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=[0],[0],[0]
for t in s:
  m+=m[-1]+(t>'D'),
  f=t<'D'
  c+=c[-1]+f,
  x+=x[-1]+f*m[-1],
for k in k:
  a=0
  for i in range(n):
    j=min(n,i+int(k))
    a+=s[i]=='D'and(c[i]-c[j])*m[i]+x[j]-x[i]
  print(a)

Submission status: Wrong Answer

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

import numpy as np
N = int(readline())
S = np.empty(N+1,'S1')
S[1:] = np.array(list(readline()),dtype='S1')[:N]
Q = int(readline())
query = map(int,readline().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Wrong Answer

Solution code:
from numpy import *
I=input
N=int(I())
S=array(list(I()))
Q=int(I())
query = map(int,I().split())
D=S=='D';M=S=='M';C=S=='C'
d=D.cumsum(dtype=int64);m=M.cumsum(dtype=int64)
for K in query:
  x=d.copy();x[K:]-=d[:-K];x*=M
  x[K+1:]-=D[1:-K]*(m[K:-1]-m[:-K-1])
  print(sum(cumsum(x)*C))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

    for j in range(n):
        ch=s[j]
        if 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
        
        if ch=='C':
            ans+=ndm
        print(len(st),st,ans,nd,nm,ndm)
    print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ans = []
cnt = 0
for k in kL:
    if cnt > 0:
      break
    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)
    cnt += 1

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
#code

def count_triplets(d,m,c):
    for idx,i in enumerate(d):
        for jdx,j in enumerate(m):
            if i < j:
                for ldx,l in enumerate(c):
                    if j < l:
                        return (len(d) - idx) * (len(m) - jdx) * (len(c) - ldx),idx,ldx

n = int(input())
s = input()
d = []
m = []
c = []
for i in range(len(s) - 1,-1,-1):
    if s[i] == 'D':
        d.append(i)
    elif s[i] == 'M':
        m.append(i)
    elif s[i] == 'C':
        c.append(i)
print(d)
print(m)
print(c)
cnt,didx,cldx = count_triplets(d,m,c)
q = int(input())
k = [int(x) for x in input().split(" ")]
for ki in k:
    temp = cnt
    for i in range(didx,len(d)):
        for j in range(cldx,len(c)):
            if c[j] - d[i] > ki:
                temp -= 1
    print(temp)

Submission status: Wrong Answer

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':
                            print(j, k, i)
                            ans += 1
    print(ans)

Submission status: Wrong Answer

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')
index_M = np.where(S == 'M')
index_C = np.where(S == 'C')

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

Submission status: Wrong Answer

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

s=re.sub('[ABEFGHIJKLNOPQRSTUVWXYZ]', '', s)

Submission status: Wrong Answer

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

s=re.sub('[ABEFGHIJKLNOPQRSTUVWXYZ]', '', s)
n=len(s)
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: Wrong Answer

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

for x in k:
    cnt=0
    s=re.sub('[ABEFGHIJKLNOPQRSTUVWXYZ]', '', s)
    n=len(s)
    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: Wrong Answer

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

def cal(k): 
    j = 0
    c = C[0]
    nc = len(C)
    res = 0
    for i in range(len(D)):
        a = D[i]
        while c-a < k:
            res += M[c]-M[a]
            if j < nc-1:
                j += 1
                c = C[j]
            else:
                break
    return res

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

Submission status: Wrong Answer

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

Dindex=[]
Mindex=[]
Cindex=[]
for i in range(N):
  if S[i]=='D':
    Dindex.append([[i,0,0] for k in range(Q)])
    continue;
  elif S[i]=='M':
    for j in range(len(Dindex)):
      for h in range(len(Dindex[j])):
        DDindex=Dindex[j][h][0]
        Mindex.append([[DDindex,i,0] for k in range(Q)])
  elif S[i]=='C':
    for a in range(len(Mindex)):
      for b in range(len(Mindex[a])):
        if i-Mindex[a][b][0]<k[b] and i>Mindex[a][b][1]:
          Mindex[a][b][2]+=1

answer=0

#print(Dindex)

for i in range(Q):
  for j in range(len(Mindex)):
    answer+=Mindex[j][i][1]*Mindex[j][i][2]
  print(answer)
  answer=0

Submission status: Wrong Answer

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

def cal(k): 
    j = 0
    c = C[0]
    nc = len(C)
    res = 0
    for i in range(len(D)):
        a = D[i]
        while c-a < k:
            res += M[c]-M[a]
            if j < nc-1:
                j += 1
                c = C[j]
    return res

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

Submission status: Wrong Answer

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

Dnumber=[i for i, x in enumerate(s) if x == 'D']
Mnumber=[i for i, x in enumerate(s) if x == 'M']
Cnumber=[i for i, x in enumerate(s) if x == 'C']
#print(Dnumber)
#print(Mnumber)
#print(Cnumber)


for k in kList:
  ans=0
  for a in Dnumber:
    Mcount=len([i for i, x in enumerate(Mnumber) if a <x <a+k])
    Ccount=len([i for i, x in enumerate(Cnumber) if a< x <a+k])
    ans+=1*Mcount*Ccount
  print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
s = input()
q = int(input())
k_list = list(map(int,input().split()))

d_rec = []
m_rec = []
c_rec = []
for i, ss in enumerate(s):
    if ss == 'D':
        d_rec.append(i)
    if ss == 'M':
        m_rec.append(i)
    if ss == 'C':
        c_rec.append(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
s = input()
q = int(input())
k_list = list(map(int,input().split()))

d_rec = []
m_rec = []
c_rec = []
for i, ss in enumerate(s):
    if ss == 'D':
        d_rec.append(i)
    if ss == 'M':
        m_rec.append(i)
    if ss == 'C':
        c_rec.append(i)
    

d_rec = np.array(d_rec)
m_rec = np.array(m_rec)
c_rec = np.array(c_rec)

# %%time
dic = {}
for d in d_rec:

    mk_start = 0
    su = 0

    for c in c_rec:
        if d > c:
            continue
        for mk in range(mk_start, len(m_rec)):
            m = m_rec[mk]
            if m < d:
                continue
            if m > c:
                break
            
            su += 1
#         print(d,m,c,su)
        try:
            dic[c - d] += su
        except:
            dic[c - d] = su
#         if su > 0:
#         su -= 1
        
        mk_start = mk


a = dic.keys()
a = np.array(list(a))

for k in k_list:
    key_here = a[a < k]
    su = 0
    for key in key_here:
        su += dic[key]
    print(su)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
k = [int(m) for m in input().split()]
dmc = []
dc = 0
for i in range(n):
    if s[i] == "D" or s[i] == "M" or s[i] == "C":
        dmc.append([s[i], i])
    if s[i] == "D":
        dc += 1
d = []
m = []
rm = []
c = []
for h in range(dc):
    m.append(0)
    rm.append(0)
    c.append(0)
for i in range(q):
    for j in range(len(dmc)):
        if dmc[j][0] == "D":
            d.append(dmc[j][1])
        if dmc[j][0] == "M":
            for v in range(len(d)):
                if dmc[j][1] - d[v] < k[i]:
                    rm[v] += 1
        if dmc[j][0] == "C":
            for v in range(len(d)):
                if dmc[j][1] - d[v] < k[i]:
                    c[v] += 1
                    m[v] = rm[v]
    combined1 = [x * y for (x, y) in zip(m, c)]
    print(sum(combined1))
    d = []
    m = []
    rm = []
    c = []
    for h in range(dc):
        m.append(0)
        rm.append(0)
        c.append(0)

Submission status: Wrong Answer

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 & c - a < k:
                    ans += 1
    print(ans)