結果
| 問題 |
No.3289 Make More Happy Connection
|
| コンテスト | |
| ユーザー |
norioc
|
| 提出日時 | 2025-10-04 03:52:07 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 562 ms / 2,000 ms |
| コード長 | 1,558 bytes |
| コンパイル時間 | 475 ms |
| コンパイル使用メモリ | 82,440 KB |
| 実行使用メモリ | 107,844 KB |
| 最終ジャッジ日時 | 2025-10-04 03:52:21 |
| 合計ジャッジ時間 | 12,584 ms |
|
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
from collections.abc import Iterable
from enum import IntEnum, auto
from functools import cache
from unittest import case
class E(IntEnum):
S = 0
X_Y = auto()
Y_X = auto()
def nexts(self):
match self:
case E.S:return [E.X_Y, E.Y_X]
case E.X_Y:return [E.X_Y, E.Y_X]
case E.Y_X:return [E.X_Y, E.Y_X]
assert False
@staticmethod
@cache
def states():
res = []
for fm in E:
for to in fm.nexts():
res.append((fm, to))
return res
def state_dp(xs: Iterable, op, e, init: dict, *, is_reset=True):
dp = [e] * len(E)
for k, v in init.items():
dp[k] = v
for x in xs:
pp = [e] * len(E) if is_reset else dp.copy()
dp, pp = pp, dp
for fm, to in E.states():
if not is_valid(to, pp[fm], x): continue
dp[to] = op(to, dp[to], fm, pp[fm], x)
return dp
def is_valid(to: E, fm_v, v) -> bool:
return True
def op(to: E, to_v, fm: E, fm_v, v):
s, e = fm_v # (スコア, 選択要素)
x, y = v
if x == y:
s += x
match to:
case E.X_Y:
if x == e:
s += x
return max(to_v, (s, y))
case E.Y_X:
if y == e:
s += y
return max(to_v, (s, x))
assert False
N = int(input())
xs = []
for _ in range(N):
X, Y = map(int, input().split())
xs.append((X, Y))
dp = state_dp(xs, op, (0, 0), {E.S: (0, 0)})
ans = max(s for s, _ in dp)
print(ans)
norioc