SRM610 Div2 Hard MiningGoldEasy
問題
TopCoder Statistics - Problem Statement
解法
xとyを独立に考える。
任意の動き方に対してx,yのそれぞれに対して座標の変化が起こらないような区間を考える。 すると関数 は のうちのどれかを最小値としてとるような凸関数であるので、 event_i、event_jに含まれるような座標の組み合わせに対する動き方のみ考えればよい。
よって座標圧縮してDPすればよい。
コード
証明が本質?