제출 #213513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
213513		tatyam	Miners (IOI07_miners)	Cpython 3	60 / 100	1600 ms	4348 KiB

miners

def kinds(a, b, c):
    if a > b: a, b = b, a
    if b > c: b, c = c, b
    if a > b: a, b = b, a
    ans = 3
    if not a or a == b: ans -= 1
    if not b or b == c: ans -= 1
    return ans
INF = 0x3fffffff
input()
s = [1 if i == 'B' else 2 if i == 'F' else 3 for i in input()]
dp1 = [-INF] * 2 ** 8
dp1[0] = 0
for c in s:
    dp2 = [-INF] * 2 ** 8
    for i in range(2 ** 8):
        a1 = i >> 6 & 3
        a2 = i >> 4 & 3
        b1 = i >> 2 & 3
        b2 = i & 3
        j = a2 << 6 | c << 4 | b1 << 2 | b2
        dp2[j] = max(dp2[j], dp1[i] + kinds(a1, a2, c))
        j = a1 << 6 | a2 << 4 | b2 << 2 | c
        dp2[j] = max(dp2[j], dp1[i] + kinds(b1, b2, c))
    dp1 = dp2
print(max(dp1))

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8