区間は \(r_i\) の昇順にソートしておく.

\(i\) 番目の区間まで見たときに (マス \(N\) の右側を除いて) 最も右側にある黒線がマス \(j\) の左側の位置にあるときの最大得点を \(S(i, j)\) とする. このとき,

\[S(i, r_i) = \max \{S(i-1, r_i), S(i-1, l_i) + p_i - A, \max_{1\leq j \lt l_i} \{ S(i-1, j) + p_i - 2A \} \}\]

となる. これを DP で計算する.

DP のメモリは区間を見るごとに使いまわし, 内側の \(\max\) はセグメントツリーを使う.