結果
問題 |
No.3289 Make More Happy Connection
|
ユーザー |
![]() |
提出日時 | 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)