時刻 \(i\) にボタンを押したときの収支を \(W_i\) 円とします。\(W\) から間隔が \(Y\) 以上になるように要素をいくつか選んで総和を最大化する問題となります。

\(dp[i] = W_i\) までを考慮した際の問題の答えとすると、\(dp[i] = \max(dp[i-1],dp[i-Y]+W_i)\) となります。この遷移を高速に行いましょう。

\(\mathrm{dp}\) の末尾 \(Y\) 個を管理することを考えます。今 \(dp[i-Y+1],dp[i-Y+2],\dots,dp[i]\) を持っていて、これから \(W_{i+1} = W_{i+2} = \dots = W_{i+k} = V\) となっている区間を処理したいとします。(\(dp\) が単調増加であることに注意してください。) まず、\(V \le 0\) の場合は \(dp[i+1]\) から \(dp[i+k]\) は全て \(dp[i]\) となります。そうでないとき、簡単のため \(k \le Y\) とします。(もしそうでないとしても、長さが \(Y\) 以下の区間いくつかに分割すればよいです。この操作をしても区間数は \(\mathrm{O}(N)\) で抑えられます。) すると、\(dp[i+j] = \max(dp[i+j-Y] + V,dp[i-1])\) となります。

上記の操作は全て、数列の rotate と区間加算と区間更新によって処理することが出来ます。rotate は現在どれだけ rotate しているかを管理することにすると、結局数列への区間加算と区間更新だけが出来ればよいです。

このままだと長さ \(Y\) の数列へのクエリ処理をすることになりますが、この部分については必要な \(dp\) の部分は \(W\) の値が変わる部分のみであることに注意すると結局 \(\mathrm{O}(N)\) 箇所の値を管理すればよくなります。よって、この問題を \(\mathrm{O}(N \log N)\) で解くことが出来ます。