結果
問題 |
No.838 Noelちゃんと星々3
|
ユーザー |
![]() |
提出日時 | 2025-06-06 03:23:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 1,272 bytes |
コンパイル時間 | 551 ms |
コンパイル使用メモリ | 83,016 KB |
実行使用メモリ | 94,472 KB |
最終ジャッジ日時 | 2025-06-06 03:23:41 |
合計ジャッジ時間 | 3,872 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
from collections.abc import Iterable from enum import IntEnum, auto from functools import cache class E(IntEnum): A = 0 B = auto() def nexts(self): match self: case E.A: return [E.A, E.B] case E.B: return [E.A] 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): dp = [e] * len(E) for k, v in init.items(): dp[k] = v for x in xs: pp = [e] * len(E) 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, iv): i, v = iv match to: case E.A: # 合わせる return min(to_v, fm_v + abs(Y[i] - Y[i-1])) case E.B: # 合わせない return min(to_v, fm_v) assert False INF = 1 << 60 N = int(input()) Y = list(map(int, input().split())) Y.sort() ivs = list(enumerate(Y)) dp = state_dp(ivs[1:], op, INF, {E.B: 0}) ans = dp[E.A] print(ans)