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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    for q in range(Q):
        k = K[q]
        res = 0
        cnt = [0] * 3
        for i in range(k):
            cur = S[i]
            if cur == "D":
                cnt[0] += 1
            elif cur == "M":
                cnt[1] += 1
                cnt[2] += cnt[0]
            elif cur == "C":
                res += cnt[2]

        for i in range(k, N):
            prev = S[i - k]
            cur = S[i]
            if prev == "D":
                cnt[0] -= 1
                cnt[2] -= cnt[1]
            elif prev == "M":
                cnt[1] -= 1

            if cur == "D":
                cnt[0] += 1
            elif cur == "M":
                cnt[1] += 1
                cnt[2] += cnt[0]
            elif cur == "C":
                res += cnt[2]
        print(res)


if __name__ == '__main__':
    main()

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

for k in K:
    numD = 0
    numM = 0
    numDM = 0
    ans = 0
    for i in range(N):
        c = S[i]
        if c == 'D':
            numD += 1
        elif c == 'M':
            numM += 1
            numDM += numD
        elif c == 'C':
            ans += numDM

        if i >= k-1:
            c = S[i-k+1]
            if c == 'D':
                numD -= 1
                numDM -= numM
            elif c == 'M':
                numM -= 1
    print(ans)

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

for k in K:
    ans = 0

    d = m = dm = 0
    for i, si in enumerate(S):
        if 0 <= i - k:
            if S[i - k] == "D":
                d -= 1
                dm -= m
            elif S[i - k] == "M":
                m -= 1

        if si == "D":
            d += 1
        elif si == "M":
            m += 1
            dm += d
        elif si == "C":
            ans += dm

    print(ans)

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i in range(N):
            s = S[i]
            if s == "D":
                D += 1
            elif s == "M":
                M += 1
                now += D
            elif s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                elif S[i-k+1] == "M":
                    M -= 1


        print(C)


    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Solution (Python):
n = int(input()) + 1
s = '?' + input()
q = int(input())
k = list(map(int,input().split()))

p_d = []
cnt_m = [0]*n
cnt_c = [0]*n

for i,si in enumerate(s[1:],1):
    cnt_m[i] = cnt_m[i-1]
    cnt_c[i] = cnt_c[i-1]
    if(si=='D'):
        p_d.append(i)
    elif(si=='M'):
        cnt_m[i] += 1
    elif(si=='C'):
        cnt_c[i] += 1

left_c = [0]*n
for i in range(1,n):
    left_c[i] = left_c[i-1]
    if(s[i]=='M'):
        left_c[i] += cnt_c[i]





ans = []
for ki in k:
    tmp = 0
    for di in p_d:
        x = cnt_m[min(di+ki-1,n-1)] - cnt_m[di-1]
        y = cnt_c[min(di+ki-1,n-1)]
        tmp += x*y - left_c[min(di+ki-1,n-1)] + left_c[di-1]
    ans.append(tmp)

print('\n'.join(map(str,ans)))

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

'''
import random
import string
S = "".join(random.choices(string.ascii_uppercase, k=10**6))
Q =75 
K = [random.randint(1,10**6) for i in range(Q)]
'''

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

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

for k in K:
    ANS=0
    D=M=DM=0
    
    for i in range(N):
        if i-k>=0:
            if S[i-k]=="D":
                D-=1
                DM-=M
            elif S[i-k]=="M":
                M-=1

        if S[i]=="D":
            D+=1
        elif S[i]=="M":
            DM+=D
            M+=1
        elif S[i]=="C":
            ANS+=DM

    print(ANS)

Solution (Python):
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  
    b = 0  
    c = 0  
    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
    return res


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

Solution (Python):
n = int(input())
s = input()
q = int(input())
kl = list(map(int, input().split()))
ansl = []
for k in kl:
    d_cnt = 0
    m_cnt = 0
    c_cnt = 0
    dm_cnt = 0
    dmc_cnt = 0
    for i in range(k):
        si = s[i]
        if si == 'D':
            d_cnt += 1
        elif si == 'M':
            m_cnt += 1
            dm_cnt += d_cnt
        elif si == 'C':
            c_cnt += 1
            dmc_cnt += dm_cnt   
    
    rem = n-k
    for i in range(rem):
        drop = s[i]
        new = s[i+k]
        if drop == 'D':
            d_cnt -= 1
            dm_cnt -= m_cnt
        elif drop == 'M':
            m_cnt -= 1
        elif drop == 'C':
            c_cnt -= 1
        
        if new == 'D':
            d_cnt += 1
        elif new == 'M':
            m_cnt += 1
            dm_cnt += d_cnt
        elif new == 'C':
            c_cnt += 1
            dmc_cnt += dm_cnt

    ansl.append(dmc_cnt)

for a in ansl: print(a)

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

ans = []
for k in K:
    d = m = dm = dmc = 0
    for i in range(N):
        if i >= k:
            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':
            dmc += dm
    ans.append(dmc)
print(*ans, sep='\n')

Solution (Python):
n=int(input())
s=input()
q=int(input())
k=list(map(int,input().split()))
for i in range(q):
  curr=k[i]
  dcount=0
  dmcount=0
  mcount=0
  ans=0
  for j in range(n):
    if j>=curr:
      if s[j-curr]=='D':
        dcount-=1
        dmcount-=mcount
      elif s[j-curr]=='M':
        mcount-=1
    if s[j]=='D':
      dcount+=1
    elif s[j]=='M':
      mcount+=1
      dmcount+=dcount
    elif s[j]=='C':
      ans+=dmcount
  print(ans)

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

Solution (Python):
   
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 = [func(ch) for ch in S]

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

Solution (Python):
import numpy as np
from numba import njit

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

def main():
    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)
    for k in ks:
        print(solve(N, S_arr, k))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', "i8(i8, i4[:], i8)")(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Solution (Python):
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("i8(i8, i4[:], i8)", 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))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
q = int(input())
ks = list(map(int, input().split()))
ans = [None]*q

for ind,k in enumerate(ks):
    ms = 1 if s[0]=="M" else 0
    cs = 1 if s[0]=="C" else 0
    mcs = 0
    j = 0
    val = 0
    for i in range(n):
        if s[i]!="D":
            if s[i]=="M":
                ms -= 1
                mcs -= cs
            elif s[i]=="C":
                cs -= 1
            continue
        if j<i:
            j = i
            ms = 0
            cs = 0
            mcs = 0
        while j+1<n and j+1-i<k:
            j += 1
            if s[j]=="M":
                ms += 1
            elif s[j]=="C":
                cs += 1
                mcs += ms
        val += mcs

    ans[ind] = val
write("\n".join(map(str, ans)))

Solution (Python):
n=int(input())
s=input()
q=int(input())
query=list(map(int,input().split()))
for k in query:
  ds=0
  ms=0
  dms=0
  ans=0
  for i in range(n):
    if s[i]=='D':
      ds+=1
    elif s[i]=='M':
      ms+=1
      dms+=ds
    elif s[i]=='C':
      ans+=dms
    if i>=k-1:
      if s[i-k+1]=='D':
        dms-=ms
        ds-=1
      elif s[i-k+1]=='M':
        ms-=1
  print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate

n = int(input())
S = input().rstrip()
q = int(input())
K = tuple(map(int, input().split()))
L = [0]*q
M = [0]*n
C = [0]*n
cnt_M = [0]*n
cnt = 0
for i in range(n-1, -1, -1):
  s = S[i]
  if s == "M":
    M[i] = cnt
    cnt_M[i] = 1
  elif s == "C":
    C[i] = 1
    cnt += 1
M = tuple(accumulate(M))
C = list(accumulate(C[::-1]))[::-1]
cnt_M = tuple(accumulate(cnt_M))
for i, s in enumerate(S):
  if s == "D":
    for j, k in enumerate(K):
      temp = M[min(i+k-1, n-1)] - M[i]
      if i+k < n:
        temp -= C[i+k] * (cnt_M[i+k-1]-cnt_M[i])
      L[j] += temp
print(*L, sep="\n")

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

for ii in range(q):
    
    d = 0
    m = 0
    dm = 0
    ans = 0
    k = K[ii]
    for i in range(n):
        
        
        
        if i-k >= 0:
            if s[i-k] == "D":
                d -= 1
                dm -= m
            if s[i-k] == "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)

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

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


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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


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


if __name__ == "__main__":
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


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


if __name__ == "__main__":
	main()

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

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

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

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

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

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

for i in range(q):
    k=kin[i]
    nd=nm=ndm=ans=0
    st=deque()
 
    for j in range(n):
        ch=s[j]
        if ch==C:
            ans+=ndm
        if j<k-1:
            if ch==M:
                ndm+=nd
                nm+=1
            elif ch==D:
                nd+=1
        else:
            pre=s[j-k+1]
            if pre==D:
                nd-=1
                ndm-=nm
            elif pre==M:
                nm-=1
            if ch==M:
                ndm+=nd
                nm+=1
            elif ch==D:
                nd+=1
    print(ans)

Solution (Python):
from collections import deque
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    q = deque([])
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
            q.append(d)
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1
                
        
    return ans
for i in k:
    print(search(i))

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = int(input())
    
    
    
    
    
    s=input()
    Q=int(input())
    A = tuple(map(int, input().split()))
    for k in A:
        dmc=0
        d=0
        m=0
        c=0
        dm=0
        mc=0
        
        for i in range(k):
            if s[i]=="D":
                d+=1
            elif s[i]=="C":
                c+=1
                mc+=m
                dmc+=dm
            
            elif s[i]=="M":
                m+=1
                dm+=d

        for i in range(1,N-k+1):
            if s[i-1]=="D":
                dm-=m
                d-=1
            elif s[i-1]=="M":
                mc-=c
                m-=1
            elif s[i-1]=="C":
                c-=1
            se=s[i+k-1]
            if se=="D":
                d+=1
            elif se=="C":
                c+=1
                mc+=m
                dmc+=dm
            
            elif se=="M":
                m+=1
                dm+=d

        print(dmc)

            




if __name__ == "__main__":
    main()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
q = inn()
kl = inl()
accd = [0]*(n+1)
accm = [0]*(n+1)
for i in range(n):
    accd[i] = accd[i-1] + (1 if s[i]=='D' else 0)
    accm[i] = accm[i-1] + (1 if s[i]=='M' else 0)


for k in kl:
    
    dm = 0
    dmc = 0
    for i in range(1,n):
        if i>=k and s[i-k]=='D':
            dm -= accm[i-1]-accm[i-k]
        if s[i]=='M':
            dm += accd[i-1]-accd[max(-1,i-k)]
        if s[i]=='C':
            dmc += dm
        
    print(dmc)

Solution (Python):
import sys
input = sys.stdin.readline

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

    for i in range(q):
        ans = 0
        d = 0
        m = 0
        dm = 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()

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    S=input()
    Q=I()
    K=LI()
    ans=0
    
    
    
    for k in K:
        d=0
        m=0
        temp=0
        ans=0
        for i in range(k):
            if S[i]=="D":
                d+=1
            elif S[i]=="M":
                m+=1
                temp+=d
            elif S[i]=="C":
                ans+=temp
                
        
        for i in range(k,N):
            if S[i-k]=="D":
                d-=1
                temp-=m
            elif S[i-k]=="M":
                m-=1
            
            if S[i]=="D":
                d+=1
            elif S[i]=="M":
                m+=1
                temp+=d
            elif S[i]=="C":
                ans+=temp
                
                
        print(ans)
            
                
                
            
            
            

main()

Solution (Python):
import sys
input=sys.stdin.readline


def solve():
    N = int(input())
    S = input()
    Q = int(input())
    *k, = map(int, input().split())

    acd = [0]*(N+1)
    acm = [0]*(N+1)
    acc = [0]*(N+1)
    acmc = [0]*(N+2)

    for i in range(1, N+1):
        acd[i] = acd[i-1] + (S[i-1]=="D")
        acm[i] = acm[i-1] + (S[i-1]=="M")
        acc[i] = acc[i-1] + (S[i-1]=="C")

    ans = 0
    for i in range(1, N+1):
        if S[i-1]=="M":
            ans += acd[i-1]*(acc[N]-acc[i])

    for i in range(1, N)[::-1]:
        acmc[i] += acmc[i+1]
        if S[i-1]=="M":
            acmc[i] += acc[N]-acc[i]

    for i in k:
        v = 0
        for j in range(1, N+1):
            if S[j-1]=="D":
                v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
        print(ans-v)


if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

acd = [0]*(N+1)
acm = [0]*(N+1)
acc = [0]*(N+1)
acmc = [0]*(N+2)

for i in range(1, N+1):
    acd[i] = acd[i-1] + (S[i-1]=="D")
    acm[i] = acm[i-1] + (S[i-1]=="M")
    acc[i] = acc[i-1] + (S[i-1]=="C")

ans = 0
for i in range(1, N+1):
    if S[i-1]=="M":
        ans += acd[i-1]*(acc[N]-acc[i])

for i in range(1, N)[::-1]:
    acmc[i] += acmc[i+1]
    if S[i-1]=="M":
        acmc[i] += acc[N]-acc[i]

for i in k:
    v = 0
    for j in range(1, N+1):
        if S[j-1]=="D":
            v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
    print(ans-v)

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
q = int(input())
query = list(map(int,input().split()))
for k in query:
  ans = 0
  dp0,dp1,dp2 = 0,0,0
  for i in range(n):
    if s[i] == "D":
      dp0 += 1
    elif s[i] == "M":
      dp1 += 1
      dp2 += dp0
    elif s[i] == "C":
      ans += dp2
    if i >= k-1:
      if s[i-k+1] == "D":
        dp0 -= 1
        dp2 -= dp1
      elif s[i-k+1] == "M":
        dp1 -= 1
  print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
  n = int(input())
  S = input()[:-1]
  q = int(input())
  K = map(int, input().split())
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()

Solution (Python):
N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))
 
for k in K:
    res = 0
    d = 0
    m = 0
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            dm += d
            m += 1
        elif S[i] == 'C':
            res += dm
        if i + 1 - k >= 0:
            if S[i + 1 - k] == 'D':
                d -= 1
                dm -= m
            elif S[i + 1 - k] == 'M':
                m -= 1
 
    print(res)