editorialよりオーダーよかった & これよりいい計算量あるか知りたかったので (書いてるうちにそもそも解答の正当性が怪しくなってしまった)
言い換えて効率でソートする(ここでは昇順にします)ところまでは同じです。
k 番目を分けて考えることにして、 k を全探索します。
このとき、以下の場合のみ考えれば良いです。(大胆予想)
・k - 1 番目以前に取った価値の総和は N^2 以下
・k + 1 番目以降を考慮して、全て D 個ずつ取るときと比較したときに取らなかった価値の総和は N^2 以下
この仮定のもとだと、k 番目以外を考慮して、価値の総和が j になるときの最小の重みが dp とスライド最小値を用いて O(N^3) で求められます。( X - N^2 <= j <= X + N^2 のような範囲)
あとは上の j, k を全探索して、k 番目は取れるだけ取ったときの価値の総和の最大値を出力すると AC が取れます。
計算量は O(N^4) です。
大胆予想で最適解がカバーされているという主張なのですが、本当でしょうか？
1 つだけは無制限に取ることができるというのが効いてきてもおかしくない気もしています。
実装
大体同じですが、制約に甘えて k - 1 番目以前の dpl, k + 1 番目以降の dpr を前計算してから O(N^4) かけて全探索しているので O(N^5) になっています。
