問題定義

特殊な錬成炉を用いて伝説の武器を鍛造する際、計 N 種類の素材を準備します。各素材 i には固有の強度パラメータ A[i] が割り当てられています。錬成規則により、素材は番号順（1 から N まで）に厳密に投入しなければなりません。

炉の容量は最大 W 個の素材までです。ここで重要な操作制限として、新しい素材を投入する直前 に限り、炉内に保管されている素材のうち最大 S 個までを選択的に取り除くことが可能です。

武器の最終的な耐久性は、各素材投入時における以下の値の総和として定義されます。

• 素材 i を投入した瞬間の炉内の素材総数（投入対象を含む）を C とすると、その段階で得られる耐久性寄与度は C × A[i] です。

素材の取出し方を戦略的に調整し、最終的な耐久性の総和を最大化するための計算手法を設計します。

入出力形式と制約条件

入力: 標準入力より、1行目に整数 N, W, S が、2行目に N 個の整数 A[1], A[2], …, A[N] が与えられます。

出力: 達成可能な最大耐久性を1行で出力してください。

制約:

• 1 ≤ S ≤ W ≤ N ≤ 5,000
• |A[i]| ≤ 10^9

動作例と状態遷移の検証

入力が以下の通りである場合の最適シナリオを確認します。

5 3 3
1 3 2 4 5

最適な操作パスは以下のように構成されます。

• 素材1投入: 炉内数=1, 耐久追加=1×1=1
• 素材2投入: 炉内数=2, 耐久追加=2×3=6
• 素材3投入: 炉内数=3, 耐久追加=3×2=6
• 素材1取出し→素材4投入: 炉内数=3, 耐久追加=3×4=12
• 素材4取出し→素材5投入: 炉内数=3, 耐久追加=3×5=15

累積耐久性: 1+6+6+12+15 = 40

アルゴリズム設計：単調队列最適化DP

この問題は動的計画法（DP）を用いて効率的に解くことができます。状態を「i番目の素材を処理し終えた時点において、炉内に j 個の素材が残っている場合の最大耐久性」と定義します。

遷移を考える際、炉内の素材数 j は、前の段階の素材数 k から、最大 S 個を除去し、1個追加した結果として決定されます。したがって、有効な k の範囲は j - S ≤ k ≤ j 程度に限定されます。単純な全探索では遷移計算に O(W) かかり全体で O(NW^2) となりますが、遷移式は単調队列（Monotonic Queue）を用いて最適化する余地があります。

具体的には、dp[k] + j × A[i] のうち dp[k] のみを比較対象とし、単調減少列を維持することで各状態の遷移を O(1) に圧縮します。これにより全体計算量は O(NW) に改善され、与えられた制約下で確実に動作します。

最適化実装 (C++)

単調队列を活用したメモリ効率の高いDP構造を反映したコードを示します。変数名は意図を明確にするため再定義し、読みやすさと計算ロジックの整合性を確保しています。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
using int64 = long long;

const int MAX_SIZE = 5005;
const int64 INF_NEG = -4e18;

int64 material_val[MAX_SIZE];
int64 dp_state[MAX_SIZE];
int64 mono_queue_val[MAX_SIZE];
int mono_queue_idx[MAX_SIZE];

int main() {
    int num_items, cap_limit, rem_limit;
    if (!(cin >> num_items >> cap_limit >> rem_limit)) return 0;

    for (int i = 1; i <= num_items; ++i) {
        cin >> material_val[i];
    }

    // DPテーブルの初期化
    fill(dp_state, dp_state + MAX_SIZE, INF_NEG);
    dp_state[0] = 0;

    // 各素材に対する順次処理
    for (int i = 1; i <= num_items; ++i) {
        int q_head = 0, q_tail = -1;

        // 炉内素材数 j を W から 1 まで逆順で更新
        // 逆順ループにより一時配列を使用せずに状態を遷移させる
        for (int j = cap_limit; j >= 1; --j) {
            int prev_k = j - 1; // 現在の素材投入直前の炉内数候補

            // 単調減少列の保守：後ろから小さなDP値を削除
            while (q_head <= q_tail && mono_queue_val[q_tail] <= dp_state[prev_k]) {
                --q_tail;
            }

            // 取出し制限 S のチェック：格納された候補 idx と現在の j の差が制限を超える場合、前方から削除
            while (q_head <= q_tail && mono_queue_idx[q_head] - j >= rem_limit) {
                ++q_head;
            }

            // 現在の候補を队列に登録
            ++q_tail;
            mono_queue_idx[q_tail] = prev_k;
            mono_queue_val[q_tail] = dp_state[prev_k];

            // DP状態の更新: 現在炉内の数が j 個なので、j * material_val[i] を加算
            dp_state[j] = mono_queue_val[q_head] + (int64)j * material_val[i];
        }
    }

    // 最終的な炉内素材数が 1〜W の範囲で最大値を検索
    int64 max_durability = INF_NEG;
    for (int j = 1; j <= cap_limit; ++j) {
        if (dp_state[j] > max_durability) {
            max_durability = dp_state[j];
        }
    }

    cout << max_durability << endl;
    return 0;
}