Music Game 2

以下のような解法は正しくないため注意してください。

• $t$ の中央値付近を $x$ として全探索する。

2
1 1
0 100

• $x$ について三分探索を行う。

5
10 9 10 9 10
100 200 300 400 500

正しい解法

この問題の制約より、スコアが最大化される $x$ が $0 \leq x \leq 10^5$ であることは明らかです。

この問題の以下のケースについて、各 $x$ のスコアを観察してみましょう。

1
3
4

x = 0: 0
x = 1: 0
x = 2: 1
x = 3: 2
x = 4: 3
x = 5: 2
x = 6: 1
x = 7: 0
...

$x = A_1$ を中心として一次関数でスコアが表せそうなことが分かります。

よって、各 $i$ について、以下の加算を行い、前から累積和をとることによって各 $x$ についての増加分を求めることができます。

• $t_i - A_i + 1$ に $+1$ をする。
• $t_i + 1$ に $-2$ をする。
• $t_i + A_i + 1$ に $+1$ をする。

以上の手順により、各 $x$ についての増加分を求め、再び累積和を取ることにより 各 $x$ についてのスコアを求めることができ、その最大値を出力すればよいです。