結果

問題 No.3368 トッピング
コンテスト
ユーザー iro_
提出日時 2025-10-29 17:39:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,381 bytes
コンパイル時間 828 ms
コンパイル使用メモリ 84,520 KB
実行使用メモリ 350,528 KB
最終ジャッジ日時 2025-11-17 20:37:51
合計ジャッジ時間 7,544 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

using namespace std;
using ll = long long;

int N, M;
ll X, C;
vector<vector<ll>> A;

// 判定関数: 満足度の最小値を K 以上にできるか？
bool check(ll K) {
    // dp[i][j][k]:
    // 位置 i にカテゴリ j (0..M-1)
    // 位置 i-1 にカテゴリ k (0..M-1)
    // とした時の、位置 0..i-1 までのペナルティ回数の最大値
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(M, vector<int>(M, -1)));

    // --- ベースケース: i = 1 (位置 0 と 1) ---
    for (int j = 0; j < M; ++j) { // cat[1]
        for (int k = 0; k < M; ++k) { // cat[0]
            // 位置 0 のペナルティを確定
            int pen0 = (k == j) ? 1 : 0;
            ll B0 = A[0][k] - (ll)pen0 * C;

            if (B0 >= K) {
                dp[1][j][k] = pen0;
            }
        }
    }

    // --- DPループ: i = 2 から N-1 まで ---
    for (int i = 2; i < N; ++i) {
        for (int j = 0; j < M; ++j) { // cat[i]
            for (int k = 0; k < M; ++k) { // cat[i-1]
                for (int prev_k = 0; prev_k < M; ++prev_k) { // cat[i-2]
                    
                    int p_prev = dp[i - 1][k][prev_k];
                    if (p_prev == -1) continue; // 不可能な状態

                    // 位置 i-1 のペナルティを確定
                    int pen_i_minus_1 = ((k == prev_k) || (k == j)) ? 1 : 0;
                    ll B_i_minus_1 = A[i - 1][k] - (ll)pen_i_minus_1 * C;

                    if (B_i_minus_1 < K) continue; // K未満は不可

                    int p_current = p_prev + pen_i_minus_1;
                    dp[i][j][k] = max(dp[i][j][k], p_current);
                }
            }
        }
    }

    // --- 最終判定: i = N-1 (最後の位置) ---
    for (int j = 0; j < M; ++j) { // cat[N-1]
        for (int k = 0; k < M; ++k) { // cat[N-2]
            
            int p_prev = dp[N - 1][j][k];
            if (p_prev == -1) continue;

            // 位置 N-1 のペナルティを確定
            int pen_N_minus_1 = (j == k) ? 1 : 0;
            ll B_N_minus_1 = A[N - 1][j] - (ll)pen_N_minus_1 * C;

            if (B_N_minus_1 < K) continue;

            int total_penalties = p_prev + pen_N_minus_1;
            
            if (total_penalties >= X) {
                return true; // K以上、X回以上を達成可能
            }
        }
    }

    return false; // すべての配置で達成不可
}

int main() {
    // 高速化
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N >> M >> X >> C;
    A.resize(N, vector<ll>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> A[i][j];
        }
    }

    // 答え K の範囲で二分探索
    ll low = 0;
    ll high = 1e9 + 7; // A[i][j]の最大値より少し大きければOK
    ll ans = 0;

    while (low <= high) {
        ll mid = low + (high - low) / 2;
        if (check(mid)) {
            // mid が達成可能なら、答えは mid かもしれない
            // (より大きい値を探す)
            ans = mid;
            low = mid + 1;
        } else {
            // mid が達成不可能なら、mid より小さい値を探す
            high = mid - 1;
        }
    }

    cout << ans << endl;

    return 0;
}
0