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:
N, K = map(int, input().split())
RSP = list(map(int, input().split())) #TSP[0]が'r'に対応
T = input()

dp = [[0]*3 for _ in range (N+1)]
#print(dp, sep="\n")
winsum = 0

Ti = [""]*K
for i in range(N):
    Ti[i%K] += T[i]

#print(Ti)
for Ts in Ti:
    dp = [[0]*3 for _ in range (len(Ts)+1)]
    for i in range(1,len(Ts)+1):
        for j in range(3): #0,1,2でr,s,p，次に選ぶ行動
            for k in range(3): #前に選んだ行動
                #print(Ts[i-1], i, j, k)
                if j == k:
                    continue
                elif j == 2 and Ts[i-1] == 'r':
                    dp[i][j] = max(dp[i][j], dp[i-1][k]+RSP[j])
                elif j == 0 and Ts[i-1] == 's':
                    dp[i][j] = max(dp[i][j], dp[i-1][k]+RSP[j])
                elif j == 1 and Ts[i-1] == 'p':
                    dp[i][j] = max(dp[i][j], dp[i-1][k]+RSP[j])
                else: #じゃんけんで勝っていないと，前の状態を保持
                    dp[i][j] = max(dp[i][j], dp[i-1][k])
        #print(*dp,sep="\n")
    winsum += max(dp[i])
print(winsum)

Submission status: Accepted

Solution code:

def win(n):
	if n=='r':
		return p
	elif n=='s':
		return r
	else:
		return s

n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
score=0
for i in t:
	score += win(i)

hands=list(t)

for i in range(n):
	if i+k<n:
		if hands[i]==hands[i+k]:
			score-=win(hands[i+k])
			hands[i+k]='x'
print(score)

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import numpy as np
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():

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

    def score(s): #相手に勝ったときの手のスコア
        if s == "r":
            return P
        elif s == "s":
            return R
        return S

    for i in range(K):
        X.append(T[i::K])

    ans = 0
    for x in X:
        # print(x)
        dp = [[0] * 2 for _ in range(len(x)+1)]
        dp[0][True] = score(x[0])
        for i in range(1,len(x)):
            if x[i] == x[i-1]:
                dp[i][True] = dp[i-1][False] + score(x[i])
                dp[i][False] = dp[i-1][True]
            else:
                dp[i][True] = max(dp[i-1][True],dp[i-1][False]) + score(x[i]) #ん？？？
                dp[i][False] = max(dp[i-1][True],dp[i-1][False])

        ans += max(dp[len(x)-1][True],dp[len(x)-1][False])
        # print(dp)

    print(ans)


if __name__ == "__main__":
  main()

Submission status: Accepted

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

ans = 0
M = []
for i in range(N):
	if i >= K and M[i-K] == T[i]:
		M.append('x')
		continue
	else:
		if T[i] == 'r':
			ans += P
			M.append('r')
		if T[i] == 's':
			ans += R
			M.append('s')
		if T[i] == 'p':
			ans += S
			M.append('p')
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

N, K = input_nums()
R, S, P = input_nums()
T = input()

hands = {'r':P, 's':R, 'p':S}
b = [1] * N
score = 0
for i in range(N):
    if i > K - 1 and T[i] == T[i-K]:
        b[i] = 1 - b[i-K]
    score += hands[T[i]] if b[i] == 1 else 0
print(score)

Submission status: Accepted

Solution code:
[N,K] = list(map(int,input().split()))
[R,S,P] = list(map(int,input().split()))
T = input()
H = []
output = 0
for i in range(N):
    if T[i]=="r":
        H.append("P")
        output += P
    elif T[i]=="s":
        H.append("R")
        output += R
    elif T[i]=="p":
        H.append("S")
        output += S
for i in range(0,N-K):
    if H[i]==H[i+K]:
        if H[i]=="R":
            output += -1*R
            H[i+K] = str(i)
        elif H[i]=="S":
            output += -1*S
            H[i+K] = str(i)
        elif H[i]=="P":
            output += -1*P
            H[i+K] = str(i)

print(output)

Submission status: Accepted

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

win = {"r": 2, "s": 0, "p": 1}
lost = [False] * n

ans = 0
for i in range(n):
    score = rsp[win[t[i]]]
    ans += score
    if i >= k and t[i - k] == t[i] and not lost[i - k]:
        lost[i] = True
        ans -= score

print(ans)

Submission status: Accepted

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

dp = [[0] * 3 for _ in range(N + 1)]


def point(hand, n):
    n -= 1
    if hand == T[n]:
        return 0
    elif hand == "r" and T[n] == "p" or hand == "s" and T[n] == "r" or hand == "p" and T[n] == "s":
        return 0
    elif T[n] == "r":
        return P
    elif T[n] == "s":
        return R
    elif T[n] == "p":
        return S


for n in range(1, N + 1):
    if n <= K:
        dp[n][0] = point("r", n)
        dp[n][1] = point("s", n)
        dp[n][2] = point("p", n)
    else:
        dp[n][0] = max(dp[n-K][1], dp[n-K][2]) + point("r", n)
        dp[n][1] = max(dp[n-K][2], dp[n-K][0]) + point("s", n)
        dp[n][2] = max(dp[n-K][1], dp[n-K][0]) + point("p", n)

MaxPoint = 0
for k in range(K):
    MaxPoint += max(dp[N-k])

print(MaxPoint)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	R,S,P = inputMap()
	T = input()
	T = T[:-1]

	ans = 0
	hantei = {}
	hantei["r"] = R
	hantei["s"] = S
	hantei["p"] = P

	TE = [[] for i in range(K)]
	cnts = 0
	for s in T:
		tmp = ""
		if s == "r":
			tmp = "p"
		elif s == "s":
			tmp = "r"
		else:
			tmp = "s"
		TE[cnts].append(tmp)
		cnts += 1
		cnts %= K

	for i,val in enumerate(TE):
		flg = False
		for j, vol in enumerate(val):
			if flg == False:
				ans += hantei[vol]
			else:
				flg = False
				continue

			if j == len(val)-1:
				break

			if vol == val[j+1]:
				flg = True

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n, k = [int(_) for _ in input().split()]
    r, s, p = [int(_) for _ in input().split()]
    t = input()

    #相手と同じ手を出したら勝ち
    point = {'p': s, 'r': p, 's': r}
    prevhand = ['o'] * k
    score = 0

    for i in range(n):
        if i + 1 <= k:
            prevhand[i%k] = t[i]
            score += point[t[i]]
        elif prevhand[i%k] != t[i]:
            prevhand[i%k] = t[i]
            score += point[t[i]]
        else:
            prevhand[i%k] = 'o'

    print(score)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

hand = {'r':p, 's':r, 'p':s}
win = {'r':'p', 's':'r', 'p':'s'}

ans = 0
u = []
for i,tt in enumerate(t):
    if i >= k and tt == t[i-k] and u[i-k] == win[tt]:
            u.append(tt)
    else:
        u.append(win[tt])
        ans += hand[tt]
print(ans)

Submission status: Accepted

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

res = [0]*N
hands = ["r", "s", "p"]

for i in range(N):
    res[i] = hands[hands.index(T[i])-1]

for i in range(N):
    if i >= K and res[i-K] == res[i]:
        res[i] = 0

score = R*res.count("r") + S*res.count("s") + P*res.count("p")
print(score)

Submission status: Accepted

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

scores = {'r':p,'s':r,'p':s}


ans = 0
memo = []

for i in range(n):
  if i < k:
    ans += scores[T[i]]
    memo.append(T[i])
  else:
    if memo[i-k] == T[i]:
      memo.append('N')
    else:
      ans += scores[T[i]]
      memo.append(T[i])
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
r,s,p = map(int,input().split())
hands = {'r':r,'s':s,'p':p}
win = {'r':p,'s':r,'p':s}
t = input()

score =[]
for i in range(n):
    enemy = t[i]
    if i - k >= 0 and t[i - k] == enemy and score[i-k]:
        score.append(0)
    else:
        score.append(win[enemy])
print(sum(score))

Submission status: Accepted

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

#r, s, pで勝つ時のスコア
dp = [[0] * 3 for _ in range(K)]


for i in range(K):
    if T[i] == 's':
        dp[i][0] = R
    elif T[i] == 'p':
        dp[i][1] = S
    else:
        dp[i][2] = P
# print (dp)
for i in range(K, N):
    k = i % K
    if T[i] == 's': #筐体がチョキを出す時
        dp[k][0], dp[k][1], dp[k][2] = max(dp[k][1], dp[k][2]) + R, max(dp[k][0], dp[k][2]), max(dp[k][0], dp[k][1])
    elif T[i] == 'p': #筐体がパーを出す時
        dp[k][0], dp[k][1], dp[k][2] = max(dp[k][1], dp[k][2]), max(dp[k][0], dp[k][2]) + S, max(dp[k][0], dp[k][1])
    else:
        dp[k][0], dp[k][1], dp[k][2] = max(dp[k][1], dp[k][2]), max(dp[k][0], dp[k][2]), max(dp[k][0], dp[k][1]) + P
    # print (dp)
ans = 0
for tmp in dp:
    ans += max(tmp)
# print (dp)
print (ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def wins(c):
    if c == "r":
        return "p"
    elif c == "s":
        return "r"
    else:
        return "s"

n,k = get_nums_l()
r,s,p = get_nums_l()
point = {
    "r": r,
    "s": s,
    "p": p
}
t = input()

won = [False] * n

ans = 0
for i,c in enumerate(t):
    if i >= k and t[i-k] == c and won[i-k]:
        # 勝てる手が出せない
        # log("lose:", i, c)
        pass
    else:
        # log("win:", i, c, wins(c), point[wins(c)])
        won[i] = True
        ans += point[wins(c)]

print(ans)

Submission status: Accepted

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

Ts=[[] for _ in range(K)]
for i in range(N):
    Ts[i%K]+=T[i]

def sub(L):
    L.append(0)
    pre = 0
    s=0
    for i in range(len(L)-1):
        if pre != L[i]:
            if L[i] == "r":
                s+=P
            elif L[i] == 's':
                s+=R
            else:
                s+=S
            pre=L[i]
        else:
            if L[i+1]!='r':
                pre='r'
            elif L[i+1]!='s':
                pre='s'
            else:
                pre='p'
    return s

s=0
for t in Ts:
    s+=sub(t)
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main(N,K,R,S,P,T):
    T_takahashi = T.replace('r','x').replace('s','y').replace('p','z').replace('x','p').replace('y','r').replace('z','s')
    ans = 0
    i = 0
    for i in range(N):
        if i+K <= N-1:
            if T_takahashi[i] in 'spr' and T_takahashi[i] == T_takahashi[i+K]:
                T_takahashi = T_takahashi[:i+K] + T_takahashi[i+K].replace(T_takahashi[i], 'w') + T_takahashi[i+K+1:]
    for hand in T_takahashi:
        if hand == 'r':
            ans += R
        elif hand == 's':
            ans += S
        elif hand == 'p':
            ans += P
        else:
            ans += 0
    return ans

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict

def main(n,k,r,s,p,t):
    score = 0
    for i in range(len(t)):
        if i < k:
            continue
        if t[i] == t[i-k]:
            t[i] = "N"
    c = Counter(t)
    i = defaultdict(int,c)
    score += i["r"]*p + i["s"]*r + i["p"]*s
    return score
    
n,k = map(int, input().split())
r,s,p = map(int, input().split())
t = list(input())
print(main(n,k,r,s,p,t))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
r,s,p = map(int,input().split())
t = input()
score = {'r':p, 's':r ,'p':s}
from collections import deque
past = deque([])

ans = 0
for i in range(n):
  if i < k:
    ans += score[t[i]]
    past.append(t[i])
  else:
    if past.popleft() != t[i]:
      ans += score[t[i]]
      past.append(t[i])
    else:
      past.append('nn')
      
  
print(ans)

Submission status: Accepted

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

flag = [0] * N
score = 0
for i in range(N):
    if i >= K and flag[i-K] == 0 and T[i] == T[i-K]:
        flag[i] = 1
        continue
    if T[i] == 'r':
        score += P
    if T[i] == 's':
        score += R
    if T[i] == 'p':
        score += S
print(score)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s,p,r = map(int, input().split())
point={'s':s, 'p':p, 'r':r}

T = input()

group = [[] for i in range(K)]

for i in range(N):
    group[i%K].append(T[i])
    
def score(l):
    s=0
    ex = ''
    for i in l:
        if ex == i:
            ex =''
        else:
            s += point[i]
            ex = i
    return s

ans = 0
            
for sub in group:
    ans += score(sub)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
r, s, p = map(int, input().split())
T = np.array(list(input()))

ans = 0
for i in range(k):
  sli = T[list(range(i, n, k))]
  rc = sc = pc = 0
  for t in sli:
    if t == 'r':
      if rc+sc != 0:
        ans += (rc+1)//2 * r + (sc+1)//2 * s
        rc = sc = 0
      pc += 1
    elif t == 's':
      if sc+pc != 0:
        ans += (sc+1)//2 * s + (pc+1)//2 * p
        sc = pc = 0
      rc += 1
    elif t == 'p':
      if rc+pc !=0:
        ans += (rc+1)//2 * r + (pc+1)//2 * p
        rc = pc = 0
      sc += 1
      
  if rc+sc+pc != 0:
    ans += (rc+1)//2 * r + (sc+1)//2 * s + (pc+1)//2 *p
   
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
scores=list(map(int,input().split()))
t=input()
winner={'r':2,'s':0,'p':1}
ans=0
for i in range(k):
  ts=''
  for j in range(n):
    if k*j+i>=n:
      break
    ts+=t[k*j+i]
  ts+='?'
  l=len(ts)
  hand=ts[0]
  cnt=1
  for j in range(1,l):
    if hand==ts[j]:
      cnt+=1
    else:
      ans+=scores[winner[hand]]*((cnt+1)//2)
      hand=ts[j]
      cnt=1
print(ans)

Submission status: Accepted

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

def calc(te):
   if te=="r":
      point=p
   elif te=="s":
      point=r
   else:
      point=s
   return point

ans=0
L=[]
for i in range(n):
   if i>=k and t[i]==L[i-k]:
      L.append("b")
      continue
   else:
      ans+=calc(t[i])
      L.append(t[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


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


def read_str():
    return input()


def solve(t, R, S, P):
    n = len(t)
    m = [[0] * 3 for i in range(n)]
    m[0][0] = R if t[0] == 's' else 0
    m[0][1] = S if t[0] == 'p' else 0
    m[0][2] = P if t[0] == 'r' else 0

    for i in range(1, n):
      m[i][0] = max(m[i-1][1], m[i-1][2])
      m[i][0] += R if t[i] == 's' else 0
      m[i][1] = max(m[i-1][0], m[i-1][2])
      m[i][1] += S if t[i] == 'p' else 0
      m[i][2] = max(m[i-1][0], m[i-1][1])
      m[i][2] += P if t[i] == 'r' else 0

    return max([m[n-1][0], m[n-1][1], m[n-1][2]])


def bigger(l):
  if l == 'r':
    return 'p'
  if l == 'p':
    return 's'
  if l == 's':
    return 'r'


def solve_greedy(t, R, S, P):
    n = len(t)
    res = 0
    l = ''
    score = {'r': R, 's': S, 'p': P}
    for i in range(n):
      for k in 'rps':
        if t[i] == k:
          if l != bigger(k):
            l = bigger(k)
            res += score[bigger(k)]
          else:
            for q in 'rps':
              if q != bigger(k):
                if i+1 < n and bigger(t[i+1]) != q:
                  l = q
    return res


def main():
    N, K = read_int_list()
    R, S, P = read_int_list()
    T = read_str()

    res = 0
    for i in range(K):
      # res += solve(T[i::K], R, S, P)
      res += solve_greedy(T[i::K], R, S, P)
    
    print(res)


main()

Submission status: Accepted

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


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


def read_str():
    return input()


def solve(t, R, S, P):
    n = len(t)
    m = [[0] * 3 for i in range(n)]
    m[0][0] = R if t[0] == 's' else 0
    m[0][1] = S if t[0] == 'p' else 0
    m[0][2] = P if t[0] == 'r' else 0

    for i in range(1, n):
      m[i][0] = max(m[i-1][1], m[i-1][2])
      m[i][0] += R if t[i] == 's' else 0
      m[i][1] = max(m[i-1][0], m[i-1][2])
      m[i][1] += S if t[i] == 'p' else 0
      m[i][2] = max(m[i-1][0], m[i-1][1])
      m[i][2] += P if t[i] == 'r' else 0

    return max([m[n-1][0], m[n-1][1], m[n-1][2]])


def main():
    N, K = read_int_list()
    R, S, P = read_int_list()
    T = read_str()

    res = 0
    for i in range(K):
      res += solve(T[i::K], R, S, P)
    
    print(res)


main()

Submission status: Accepted

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

def point(str1,str2): 
    if str1=="s" and str2=="r":
        return R
    elif str1=="r" and str2=="p":
        return P
    elif str1=="p" and str2=="s":
        return S
    else:
        return 0

T=[[] for i in range(K)]

for i in range(N):
    T[i%K].append(Ti[i])

ans=0
for i in range(K):
    L=len(T[i])
    DP=[[0]*3 for i in range(L+1)]
    for j in range(L):
        DP[j+1][0]=max(DP[j][1],DP[j][2])+point(T[i][j],"r")
        DP[j+1][1]=max(DP[j][2],DP[j][0])+point(T[i][j],"s")
        DP[j+1][2]=max(DP[j][0],DP[j][1])+point(T[i][j],"p")
    ans += max(DP[L])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K = map(int, input().split())
r, s, p = map(int, input().split())
score = {}
score['s'] = r
score['p'] = s
score['r'] = p
T = input()
dic = defaultdict(int)
ans = 0
for i in range(N):
  c = T[i]
  if i<K:
    ans += score[c]
    dic[i] = c
    continue
  d = dic[i%K]
  if d==c:
    dic[i%K] = 0
    continue
  ans += score[c]
  dic[i%K] = c
print(ans)

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()
ans = 0
flg = [0] * k
for i in range(n):
    if t[i] == 'r':
        v = p
    elif t[i] == 's':
        v = r
    else:
        v = s
    if i < k:
        ans += v
    else:
        if t[i] == t[i - k]:
            if flg[i % k] == 0:
                flg[i % k] = 1
            else:
                ans += v
                flg[i % k] = 0
        else:
            ans += v
            flg[i % k] = 0
print(ans)

Submission status: Accepted

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

j_l = "rsp"
kachi = lambda k : j_l[ (j_l.find(T[k]) + 2) % 3 ]#勝つ手を表示する

rireki = []#出した手の履歴
score = [0,0,0] #出した手の回数を記録

for i in range(N): 
  if i-K >= 0: #K番目以降
    if kachi(i) != rireki[i-K]: #K回前の出した手と比べて、被ってない時、勝ち手を出す
      score[ (j_l.find(T[i])+ 2) % 3 ] += 1#出した手をスコアに足す
      rireki.append(kachi(i)) #履歴に出した手を加える
      #print(score)
    else: #引き分けの時
      rireki.append("hikiwake_or_make") #Kこ先の勝ち手ではないものを履歴に加える？
      #print(score)
  else: #K番以前
    score[ (j_l.find(T[i])+ 2) % 3 ] += 1 #勝つ手を出すだけ
    rireki.append(kachi(i)) #履歴に加える
    #print(score) 
tortal_score = R*score[0] + S*score[1] + P*score[2]

#print(rireki)

print(tortal_score)

Submission status: Accepted

Solution code:
from math import ceil

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

rows, cols = ceil(n / k), k
ans = 0
for j in range(cols):
    dp = [[0, 0, 0] for _ in range(rows + 1)]
    for i in range(rows):
        ri, si, pi = dp[i]
        if i * k + j < n:
            c = t[i * k + j]
        else:
            c = ''
        dp[i + 1][0] = max(si, pi) + r * (c == 's')
        dp[i + 1][1] = max(pi, ri) + s * (c == 'p')
        dp[i + 1][2] = max(ri, si) + p * (c == 'r')
    ans += max(dp[rows])

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy

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

SUM = 0

for i in range(1, K + 1):
    p = 0
    t = []
    for l in range(10 ** 9):
        t.append(T[i + K * l - 1])
        if (i + K * (l + 1) -1 ) >= N:
            break
    dp = [[-1, -1, -1] for _ in range(len(t) + 1)]
    dp[0] = [0, 0, 0]
    for l in range(1, len(t) + 1):
        if t[l - 1] == "r":
            dp[l][0] = max(dp[l - 1][1], dp[l - 1][2])
            dp[l][1] = max(dp[l - 1][0], dp[l - 1][2])
            dp[l][2] = max(dp[l - 1][0], dp[l - 1][1]) + P
        elif t[l - 1] == "s":
            dp[l][0] = max(dp[l - 1][1], dp[l - 1][2]) + R
            dp[l][1] = max(dp[l - 1][0], dp[l - 1][2])
            dp[l][2] = max(dp[l - 1][0], dp[l - 1][1])
        else:
            dp[l][0] = max(dp[l - 1][1], dp[l - 1][2])
            dp[l][1] = max(dp[l - 1][0], dp[l - 1][2]) + S
            dp[l][2] = max(dp[l - 1][0], dp[l - 1][1])
    SUM += max(dp[len(t)])
print(SUM)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
pt_dict = {"r":P, "s":R, "p":S}
pt = 0
result = []
for i in range(N):
    if i <K:
        pt += pt_dict[T[i]]
        result.append("win")
    elif T[i] == T[i-K] and result[i-K]=="win":
            result.append("lose")
    else:
        pt += pt_dict[T[i]]
        result.append("win")
print(pt)

Submission status: Accepted

Solution code:
from itertools import groupby

N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
ans=0
X=[[] for i in range(0,K)]
for i in range(0,N):
    X[i%K].append(T[i])
for i in range(0,K):
    X[i]=groupby(X[i])
    for key,group in X[i]:
        g=len(list(group))
        if key=='r':
            ans+=P*((g+1)//2)
        elif key=='s':
            ans+=R*((g+1)//2)
        else:
            ans+=S*((g+1)//2)
print(ans)

Submission status: Accepted

Solution code:
from array import array
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = array("u", list(input()))

for i in range(k, n):
    if t[i] == t[i-k]:
        t[i] = "*"

ans = (t.count("r") * p +
       t.count("s") * r +
       t.count("p") * s)

print(ans)

Submission status: Accepted

Solution code:
from array import array
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = array("u", list(input()))

for i in range(k, n-1):
    if t[i] == t[i-k]:
        t[i] = "*"
        
if t[n-1] == t[n-1-k]:
    t[n-1] = "*"

ans = (t.count("r") * p +
       t.count("s") * r +
       t.count("p") * s)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    N,K=mis()
    R,S,P=mis()
    T=input()
    #
    ans = 0
    for i in range(K):
        r,s,p = 0,0,0
        for t in T[i::K]:
            r,s,p = max(s, p), max(r, p), max(r, s)
            if t=='r':
                p += P
            elif t=='s':
                r += R
            else:
                s += S
        ans += max(r,s,p)
    print(ans)

main()