Problem:


Score : 400 points

Problem Statement

At an arcade, Takahashi is playing a game called RPS Battle, which is played as follows:

The player plays N rounds of Rock Paper Scissors against the machine. (See Notes for the description of Rock Paper Scissors. A draw also counts as a round.)

Each time the player wins a round, depending on which hand he/she uses, he/she earns the following score (no points for a draw or a loss):

R points for winning with Rock;

S points for winning with Scissors;

P points for winning with Paper.

However, in the i-th round, the player cannot use the hand he/she used in the (i-K)-th round. (In the first K rounds, the player can use any hand.)

Before the start of the game, the machine decides the hand it will play in each round. With supernatural power, Takahashi managed to read all of those hands.

The information Takahashi obtained is given as a string T. If the i-th character of T (1 \leq i \leq N) is r, the machine will play Rock in the i-th round. Similarly, p and s stand for Paper and Scissors, respectively.

What is the maximum total score earned in the game by adequately choosing the hand to play in each round?

Notes

In this problem, Rock Paper Scissors can be thought of as a two-player game, in which each player simultaneously forms Rock, Paper, or Scissors with a hand.

If a player chooses Rock and the other chooses Scissors, the player choosing Rock wins;

if a player chooses Scissors and the other chooses Paper, the player choosing Scissors wins;

if a player chooses Paper and the other chooses Rock, the player choosing Paper wins;

if both players play the same hand, it is a draw.

Constraints

2 \leq N \leq 10^5

1 \leq K \leq N-1

1 \leq R,S,P \leq 10^4

N,K,R,S, and P are all integers.

|T| = N

T consists of r, p, and s.

Input

Input is given from Standard Input in the following format:

N K
R S P
T

Output

Print the maximum total score earned in the game.

Sample Input 1

5 2
8 7 6
rsrpr

Sample Output 1

27

The machine will play {Rock, Scissors, Rock, Paper, Rock}.

We can, for example, play {Paper, Rock, Rock, Scissors, Paper} against it to earn 27 points.
We cannot earn more points, so the answer is 27.

Sample Input 2

7 1
100 10 1
ssssppr

Sample Output 2

211

Sample Input 3

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

Sample Output 3

4996



Sample input:
5 2
8 7 6
rsrpr


Sample output:
27

Submission status: Accepted

Solution code:
###Prediction and Restriction
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
win=[False]*n
def janken(char):
    if char=='r':
        return p
    elif char=='s':
        return r
    else:
        return s
cnt=0
for i in range(n):
    if i-k<0:
        point=janken(t[i])
        cnt+=point
        win[i]=True
    else:
        if t[i]!=t[i-k]:
            point=janken(t[i])
            cnt+=point
            win[i]=True
        else:
            if not win[i-k]:
                point=janken(t[i])
                cnt+=point
                win[i]=True

print(cnt)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = list(input())
dic = {'r':P,'s':R,'p':S}
ans  = 0
for i in range(K):
    ans += dic[T[i]]
for i in range(K,N):
    if T[i-K] != T[i]:
        ans += dic[T[i]]
    else:
        T[i] = 'e'
print(ans)

Submission status: Accepted

Solution code:

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,K=MI()
    R,S,P=MI()
    T=input()
    L=[]
    
    ans=0
    for i in range(N):
        pre="z"
        if i-K>=0:
            pre=L[i-K]
            
        if T[i]=="r":
            if pre!="p":
                ans+=P
                L.append("p")
            else:
                L.append("z")
                
        if T[i]=="s":
            if pre!="r":
                ans+=R
                L.append("r")
            else:
                L.append("z")

        if T[i]=="p":
            if pre!="s":
                ans+=S
                L.append("s")
            else:
                L.append("z")
                
    print(ans)
                
    

main()

Submission status: Accepted

Solution code:
from math import ceil
def point(x,y,r,s,p):
    if y == 'r':
        y = p
    if y == 's':
        y = r
    if y == 'p':
        y = s
    return ceil(x/2) * y
n,k = map(int,input().split())
r,s,p = map(int,input().split())
t = list(input())
ans = 0
for _ in range(k):
    l = t[_::k]
    x = 1
    y = l[0]
    for i in l[1:]:
        if i != y:
            ans += point(x,y,r,s,p)
            x = 1
            y = i
        else:
            x += 1
    ans += point(x,y,r,s,p)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def calc(t, r, s, p):
    if t == "r":
        return p
    elif t == "s":
        return r
    else:
        return s


n, k = map(int, input().split())
r, s, p = map(int, input().split())
T = input()
d = deque()
ans = 0
for i, t in enumerate(T):
    if i < k:
        ans += calc(t, r, s, p)
        d.append(t)
    else:
        x = d.popleft()
        if x == t:
            d.append(0)
        else:
            ans += calc(t, r, s, p)
            d.append(t)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
r,s,p = map(int,input().split())
t = input()

point = {"r":(p,"p"), "s":(r,"r"), "p":(s,"s")}
ans = 0

hand = ""
for i in range(n):
  if i < k:
    ans += point[t[i]][0]
    hand += point[t[i]][1]
  else:
    if (t[i-k] != t[i]):
      ans += point[t[i]][0]
      hand += point[t[i]][1]
    else:
      if hand[i-k] != point[t[i]][1]:
        ans += point[t[i]][0]
        hand += point[t[i]][1]
      else:
        if (i+k) < n:
          hand += "rsp".replace(point[t[i+k]][1],"").replace(hand[i-k],"")[0]
        else:
          hand += "rsp".replace(hand[i-k],"")[0]
  
      
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 22:36:36 2020

@author: liang
"""

N, K = map(int,input().split())
R, S, P = map(int,input().split())
T = input()
hand = {"r":P, "s":R, "p":S}
ans = 0
for i in range(K):
    s = str()
    tmp = i
    while tmp < N:
        s += T[tmp]
        tmp += K
    #print(s)
    count = 1
    prev = str()
    for j in range(len(s)):
        if s[j] == prev:
            count += 1
        else:
            count = 1
        if count%2 == 0:
            continue
        prev = s[j]
        """
        if s[j] == "r":
            ans += P
        elif s[j] == "s":
            ans += R
        else:
            ans += S
        """
        ans += hand[s[j]]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 22:36:36 2020

@author: liang
"""

N, K = map(int,input().split())
R, S, P = map(int,input().split())
T = input()

ans = 0
for i in range(0,K):
    s = str()
    tmp = i
    while tmp < N:
        s += T[tmp]
        tmp += K
    #print(s)
    count = 1
    prev = str()
    for j in range(len(s)):
        if s[j] == prev:
            count += 1
        else:
            count = 1
        if count%2 == 0:
            continue
        prev = s[j]
        if s[j] == "r":
            ans += P
        elif s[j] == "s":
            ans += R
        else:
            ans += S
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,K = mint()
R,S,P = mint()
T = input()
win = [False]*K
ans = 0
score = {'r':P, 's':R, 'p':S}
for i in range(N):
    if win[i] and T[i]==T[i-K]:
        win.append(False)
    else:
        win.append(True)
        ans += score[T[i]]
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,k = i_map()
    r,s,p = i_map()
    dic = {"r":p,"s":r,"p":s}
    t = list(s_input())
    ans = 0

    for i,j in enumerate(t):
        if i < k:
            ans += dic[j]
        else:
            if j != t[i-k]:
                ans += dic[j]
            else:
                t[i] = "z"
    print(ans)



if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
scores = list(map(int, input().split()))
tables = {'s': 0, 'p': 1, 'r': 2}

patterns = input()
answer = 0
losers = [0 for _ in range(N)]
for i in range(N):
  if i - K < 0:
    answer += scores[tables[patterns[i]]]
  else:
    if patterns[i] == patterns[i-K]:
      if losers[i-K] == 0:
        losers[i] = 1
      else:
        answer += scores[tables[patterns[i]]]
    else:
      answer += scores[tables[patterns[i]]]
print(answer)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

T_split = [[] for i in range(K)]
for i in range(N):
    T_split[i%K].append(T[i])
#print(T_split)

ans = 0
flag = 0

for i in range(len(T_split)):
    for j in range(len(T_split[i])):
        if flag == 1:
            flag = 0
            continue
        if T_split[i][j] == 'r':
            point = P
        elif T_split[i][j] == 's':
            point = R
        elif T_split[i][j] == 'p':
            point = S
        ans += point
        if j != len(T_split[i]) - 1:
            if T_split[i][j] == T_split[i][j+1]:
                flag = 1
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
dp = [0] * (len(t) + 1)
dp[0] = 0

def pon(d):
 if d  == 'r':
    return p
 elif d == 's':
    return r
 else:
    return s

m = []
for i,j in enumerate(t):
    m.append(j)
    if i >= k:
        if m[i-k] == j:
            dp[i+1] = dp[i]
            m[i] = 'skip'
        else:
            dp[i+1] = dp[i]+pon(j)
    else:
        dp[i+1] = dp[i] + pon(j)
print(dp[-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())  
r, s, p = map(int, input().split())  
read_data = input()

res = 0
log = []
for i in range(len(read_data)):
    # k = 2
    if len(log) < k:
        if read_data[i] == 'r':
            res+=p
        if read_data[i] == 's':
            res+=r
        if read_data[i] == 'p':
            res+=s

        log.append(read_data[i])

    else:
        tmp = log.pop(0)
        if tmp != read_data[i]:
            if read_data[i] == 'r':
                res+=p
            if read_data[i] == 's':
                res+=r
            if read_data[i] == 'p':
                res+=s
            log.append(read_data[i])
        else:
            log.append('-')
    
    
print(res)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

c = [''] * n
ans = 0
for i in range(n):
    if t[i] == 'r':
        rsp = 'p'
        point = p
    elif t[i] == 's':
        rsp = 'r'
        point = r
    elif t[i] == 'p':
        rsp = 's'
        point = s
    
    if i >= k and c[i-k] == rsp:
        rsp = ''
        point = 0
    
    c[i] = rsp
    ans += point
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
R, S, P = map(int,input().split())
T = input()

ans = 0
check = [0] * N

for i in range(N):
  j = T[i]
  if i >= K:
    if j == check[i-K]: continue
  if j == "r": ans += P
  elif j == "s": ans += R
  else: ans += S
  check[i] = j

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools


def resolve(in_):
    N, K = map(int, next(in_).split())
    R, S, P = map(int, next(in_).split())
    T = next(in_).rstrip()
    r = ord(b'r')
    s = ord(b's')
    p = ord(b'p')

    temp = [0] * (N + 1)

    ans = 0
    for i, v in enumerate(T):
        j = i - K
        if j < 0:
            if v == r:
                ans += P
                temp[i] = p
            elif v == s:
                ans += R
                temp[i] = r
            elif v == p:
                ans += S
                temp[i] = s
        else:
            if v == r and temp[j] != p:
                ans += P
                temp[i] = p
            elif v == s and temp[j] != r:
                ans += R
                temp[i] = r
            elif v == p and temp[j] != s:
                ans += S
                temp[i] = s
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = (int(x) for x in input().split())
r,s,p = (int(x) for x in input().split())
t = input()
a = []
ans = 0

for i in range(0,n):
    a.append(t[i])

for j in range(0,n):
    if j - k >= 0 and a[j - k] == a[j]:
           a[j] = "o"
    p
    if a[j] == "r":
        ans = ans + p
    if a[j] == "s":
        ans = ans + r
    if a[j] == "p":
        ans = ans + s


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    t = input()
    c = ""
    ans = 0

    for i in range(n):
        if t[i] == "r":
            if i >= k and c[i-k] == 'p':
                c += 'x'
            else:
                c += "p"
                ans += p
        elif t[i] == "s":
            if i >= k and c[i-k] == 'r':
                c += 'x'
            else:
                c += "r"
                ans += r
        else:
            if i >= k and c[i-k] == 's':
                c += 'x'
            else:
                c += "s"
                ans += s
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  t=input()
  s='rsp'
  dp=[[-10**10]*(n+k) for _ in range(3)]
  for i in range(k):
    for j in range(3):
      dp[j][i]=0
  for i in range(n):
    for j in range(3):
      for l in range(3):
        if j==l:
          continue
        res=((s.index(t[i])-l+3)%3==1)*p[l]
        if dp[l][i+k]<dp[j][i]+res:
          dp[l][i+k]=dp[j][i]+res
  ans=0
  for i in range(n,n+k):
    ans+=max(dp[0][i],dp[1][i],dp[2][i])
  print(ans)
main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
t=input()
s='rsp'
dp=[[-10**10]*(n+k) for _ in range(3)]
for i in range(k):
  for j in range(3):
    dp[j][i]=0
for i in range(n):
  for j in range(3):
    for l in range(3):
      if j==l:
        continue
      res=((s.index(t[i])-l+3)%3==1)*p[l]
      if dp[l][i+k]<dp[j][i]+res:
        dp[l][i+k]=dp[j][i]+res
ans=0
for i in range(n,n+k):
  ans+=max(dp[0][i],dp[1][i],dp[2][i])
print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
RSP = list(map(int, input().split()))
D = {'r': 0, 's': 1, 'p': 2}
T = input()

M = N//K
dp = [[[0]*3 for _ in range(M+(i < (N % K)))] for i in range(K)]
# print(dp)


def wins(i, s):
    j = D[s]
    return i % 3 == (j-1) % 3


ans = 0
for i in range(K):
    L = dp[i]
    for k in range(3):
        L[0][k] = RSP[k]*wins(k, T[i])
    for j in range(1, len(L)):
        for k in range(3):
            L[j][k] = max(L[j-1][l] + RSP[k]*wins(k, T[i+j*K])
                          for l in range(3) if k != l)
    # print(L)
    ans += max(L[-1][k] for k in range(3))
print(ans)

Submission status: Accepted

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

rsp = {"r":p, "s":r, "p":s}
ans = 0
for i in range(n):
  if i < k: ans += rsp[t[i]]
  else:
    if t[i] != t[i-k]: ans += rsp[t[i]]
    else: t[i] = "a"
print(ans)

Submission status: Accepted

Solution code:
# D - Prediction and Restriction 
N,K = map(int,input().split())
RSP = tuple(map(int,input().split()))
T = input()

# じゃんけんの勝敗を返す関数
def judge(a,b):
    if a == 'r' and b == 2:
        return True
    elif a == 's' and b == 0:
        return True
    elif a == 'p' and b == 1:
        return True
    return False

# dp[i][j]: i 回目のじゃんけんで j を出したときの最大値
# グー:0, チョキ:1, パー:2
dp = [[0]*3 for _ in range(N+1)]

# 初期条件 v < K のときは全て勝つ
for i in range(1,K+1):
    for j in range(3):
        if judge(T[i-1],j):
            dp[i][j] = RSP[j]

# K 以下の数字について
for v in range(1,K+1):
    # w = v, v+K, v+2K,...
    for w in range(v+K,N+1,K):
        # w 回目に出した手
        for l in range(3):
            # w-K 回目に出した手 
            for m in range(3):
                if l == m:
                    continue
                # じゃんけんで勝ったとき
                if judge(T[w-1],l):
                    if w-K>=0:
                        dp[w][l] = max(dp[w][l],dp[w-K][m] + RSP[l])
                # じゃんけんで負けか引き分けたとき
                dp[w][l] = max(dp[w][l],dp[w-K][m])
                     
# K 個に分けた各グループの部分和の最大値の総和を求める
ans = 0
for a in range(1,K+1):
    ans += max(dp[-a])
print(ans)

Submission status: Accepted

Solution code:
# D - Prediction and Restriction 
N,K = map(int,input().split())
RSP = tuple(map(int,input().split()))
T = input()

# じゃんけんの勝敗を返す関数
def judge(a,b):
    if a == 'r' and b == 2:
        return True
    elif a == 's' and b == 0:
        return True
    elif a == 'p' and b == 1:
        return True
    return False

# dp[i][j]: i 回目のじゃんけんで j を出したときの最大値
# グー:0, チョキ:1, パー:2
dp = [[0]*3 for _ in range(N+1)]

# v 回目のじゃんけん
for v in range(1,N+1):
    # v 回目に出した手
    for w in range(3):
        # v-K 回目に出した手 
        for k in range(3):
            if w == k:
                continue
            # じゃんけんで勝ったとき
            if judge(T[v-1],w):
                dp[v][w] = max(dp[v][w],dp[v-K][k] + RSP[w])
            # じゃんけんで負けか引き分けたとき
            else:
                dp[v][w] = max(dp[v][w],dp[v-K][k])         
# K 個に分けた各グループの部分和の最大値の総和を求める
ans = 0
for a in range(1,K+1):
    ans += max(dp[-a])
print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,k = LI()
    r,s,p = LI()
    t = list(S())
    ans = 0

    for i in t[:k]:
        if i=="r":
            ans += p
        elif i == "s":
            ans += r
        elif i == "p":
            ans += s
    
    for i in range(k,n):
        if t[i]=="r":
            if t[i-k]=="r":
                t[i] = ""
            else:
                ans += p
        elif t[i]=="s":
            if t[i-k]=="s":
                t[i] = ""
            else:
                ans += r
        elif t[i]=="p":
            if t[i-k]=="p":
                t[i] = ""
            else:
                ans += s
        
    print(ans)
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

def janken(n):
    if n == "r":
        return P
    elif n == "s":
        return R
    else:
        return S

ans = 0

for i in range(K):
    h = T[i::K]
    l = len(h)
    f = 1
    a = ""
    for j in range(l):
        if a != h[j]:
            a = h[j]
            f = 0
            ans += janken(h[j])
        else:
            ans += f * janken(h[j])
            f = - (f - 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,K = map(int,input().split())
R,S,P = map(int,input().split())
Tlist = input()
Answer = 0
def po(x):
    if x == 's':
        return R
    elif x == 'r':
        return P
    else:
        return S
for i in range(K):
    TK = list(Tlist[i::K]).copy()
    TK.append('')
    T2 = TK[0]
    sig = 2
    for i in range(1,len(TK)):
        T1 = T2
        T2 = TK[i]
        if T1 == T2 and i != len(TK)-1:
            sig += 1
        else:
            Answer += po(T1)*(sig//2)
            sig = 2
print(Answer)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()

dp=[[0]*3 for i in range(n+1)]

for i in range(n):
    if t[i]=='r':
      dp[i+1][2]=max(dp[i+1-k][0],dp[i+1-k][1])+p
      dp[i+1][1]=max(dp[i+1-k][0],dp[i+1-k][2])
      dp[i+1][0]=max(dp[i+1-k][1],dp[i+1-k][2])
    

    elif t[i]=='s':
      dp[i+1][0]=max(dp[i+1-k][1],dp[i+1-k][2])+r
      dp[i+1][1]=max(dp[i+1-k][0],dp[i+1-k][2])
      dp[i+1][2]=max(dp[i+1-k][0],dp[i+1-k][1])
      
      
    else:
      dp[i+1][1]=max(dp[i+1-k][0],dp[i+1-k][2])+s
      dp[i+1][0]=max(dp[i+1-k][1],dp[i+1-k][2])
      dp[i+1][2]=max(dp[i+1-k][0],dp[i+1-k][1])
      


ans=0

for i in range(1,k+1):
  ans+=max(dp[-i])


print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
r,s,p = map(int,input().split())
T = input()

#dp[i][j]:i回目にjを出した時のそれまでの合計点の最大値。j:0グー1チョキ2パー
dp = [[0 for j in range(3)] for i in range(n)]
for i in range(0,k):
    if T[i] == 'r':
        dp[i][2] = p 
    elif T[i] == 's':
        dp[i][0] = r 
    else:
        dp[i][1] = s 
    for j in range(k,n-i,k):
        if T[i+j] == 'r':
            dp[i+j][2] = max(dp[i+j-k][0]+p,dp[i+j-k][1]+p)
            dp[i+j][1] = max(dp[i+j-k][0],dp[i+j-k][2])
            dp[i+j][0] = max(dp[i+j-k][1],dp[i+j-k][2])
        elif T[i+j] == 's':
            dp[i+j][0] = max(dp[i+j-k][1]+r,dp[i+j-k][2]+r)
            dp[i+j][1] = max(dp[i+j-k][0],dp[i+j-k][2])
            dp[i+j][2] = max(dp[i+j-k][0],dp[i+j-k][1])
        else:
            dp[i+j][1] = max(dp[i+j-k][2]+s,dp[i+j-k][0]+s)
            dp[i+j][0] = max(dp[i+j-k][1],dp[i+j-k][2])
            dp[i+j][2] = max(dp[i+j-k][0],dp[i+j-k][1])
    
total = 0
#print(dp)
for i in range(n-1,max(0,n-1-k),-1):
    total += max(dp[i])
print(total)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s,p,r=map(int,input().split())
a=list(input())
count={}
count["s"]=s
count["p"]=p
count["r"]=r
ans=0

for i in range(k):
    for j in range(i,n,k):
        if j-k>=0 and a[j-k]!=a[j]:
            ans+=count[a[j]]
        if j-k>=0 and a[j-k]==a[j]:
            a[j]="q"
        elif j-k<0:
            ans+=count[a[j]]
        
print(ans)

Submission status: Accepted

Solution code:

N, K = list(map(int, input().split()))
point= list(map(int, input().split()))
T = list(input())
d = dict()
d['s'] = point[0]
d['p'] = point[1]
d['r'] = point[2]
res = 0
ans = []
flag = [0,0,0]

for i in range(K):
  res += d[T[i]]
  ans.append(T[i])
for i in range(K,N):
  if ans[i-K] == T[i]:
    ans.append("n")
  else:
    res += d[T[i]]
    ans.append(T[i])
print(res)

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
score = dict(r=P, s=R, p=S)
ans = 0
q = deque()
for i in range(K):
    s = T[i]
    ans += score[s]
    q.append(s)
for i in range(K, N):
    s = T[i]
    s_pre_k = q.popleft()
    if s == s_pre_k:
        q.append('n')
    else:
        ans += score[s]
        q.append(s)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
r,s,p=map(int,input().split())
d={'r':p,'s':r,'p':s}
t=input()
ans=0
for i in range(k):
  x=t[i]
  ans+=d[x]
  for j in range(i+k,n,k):
    if t[j]!=x:
      x=t[j]
      ans+=d[x]
    else:
      x='z'
print(ans)

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, K = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

R, S, P = map(int, input().split())
T = input()
win = {"r": ["p", P], "s": ["r", R], "p": ["s", S]}

hands = []
tot = 0
for i, c in enumerate(T):
    if i >= K and win[c][0] == hands[i - K]:
        hands.append("anything")
        continue
    hands.append(win[c][0])
    tot += win[c][1]
        
print(tot)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()

ans=0
chk=[0]*N
for n in range(N):
  c=T[n]
  if n>=K and T[n-K]==c and chk[n-K]==0:
    chk[n]=1 # not used
    continue
  if c=='r':
    ans+=P
  elif c=='s':
    ans+=R
  else:
    ans+=S

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
G=[[] for n in range(K)]

for n in range(N):
  G[n%K].append(T[n])

cnt=0
for g in G:
  r,s,p=True,True,True
  for g2 in g:
    if g2=='r':
      if p:
        p=False
        r,s=True,True
        cnt+=P
      else:
        r,s,p=True,True,True
    if g2=='s':
      if r:
        r=False
        p,s=True,True
        cnt+=R
      else:
        r,s,p=True,True,True
    if g2=='p':
      if s:
        s=False
        r,p=True,True
        cnt+=S
      else:
        r,s,p=True,True,True

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-30 13:56:28 +0900
# LastModified: 2020-08-30 14:22:16 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import Counter


def main():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = input()
    takahashi = ''
    for t in T:
        if t == 's':
            takahashi += 'r'
        elif t == 'p':
            takahashi += 's'
        else:
            takahashi += 'p'

    for i in range(K, N):
        if takahashi[i-K] == takahashi[i]:
            takahashi = takahashi[:i] + '_' + takahashi[i+1:]
    ans = takahashi.count('r')*R + takahashi.count('s')*S + takahashi.count('p')*P
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
R, S, P = [int(x) for x in input().split()]
T = input()


point = {'r':P, 's':R, 'p':S}
win = [False] * N
total = 0
for i in range(N):
    if i < K or T[i] != T[i - K] or win[i - K] == False:
        total += point[T[i]]
        win[i] = True

print(total)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
T = input()

bestmove = {'r':2, 's':0, 'p':1}

ans = 0
for k in range(K):
    t = T[k::K]
    prev = -1
    for opp in t:
        me = bestmove[opp]
        if prev != me:
            prev = me
            ans += A[me]
        else:
            prev = -1

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()

ans=0
for i in range(K):
    tt=T[i:N:K]
    l=len(tt)
    dp = [[0]*l for _ in range(3)]
    if tt[0]=="r":
        dp[2][0]=P
    if tt[0]=="s":
        dp[0][0]=R
    if tt[0]=="p":
        dp[1][0]=S
    
    for i in range(1,l):
        if tt[i]=="r":
            dp[0][i] = max(dp[1][i-1],dp[2][i-1])
            dp[1][i] = max(dp[2][i-1],dp[0][i-1])
            dp[2][i] = max(dp[0][i-1],dp[1][i-1])+P
        if tt[i]=="s":
            dp[0][i] = max(dp[1][i-1],dp[2][i-1])+R
            dp[1][i] = max(dp[2][i-1],dp[0][i-1])
            dp[2][i] = max(dp[0][i-1],dp[1][i-1])
        if tt[i]=="p":
            dp[0][i] = max(dp[1][i-1],dp[2][i-1])
            dp[1][i] = max(dp[2][i-1],dp[0][i-1])+S
            dp[2][i] = max(dp[0][i-1],dp[1][i-1])
    ans+= max(dp[h][-1] for h in range(3))
print(ans)