結果

問題 No.3368 トッピング
コンテスト
ユーザー noya2
提出日時 2025-11-10 01:49:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,303 bytes
コンパイル時間 3,204 ms
コンパイル使用メモリ 292,760 KB
実行使用メモリ 37,092 KB
最終ジャッジ日時 2025-11-17 20:44:46
合計ジャッジ時間 9,861 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*

O(NXM)

// N  2  M  X
dp[i][p][j][t] : 位置 i まで見た，次の位置では同じ種類を置くかどうか，直前の種類，ペナルティが発生した回数

*/
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll linf = 1e18;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m, c, x; cin >> n >> m >> c >> x;
    vector a(n,vector<ll>(m));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    vector dp(2,vector(m,vector<ll>(x+1,-linf)));
    for (int j = 0; j < m; j++){
        dp[0][j][0] = a[0][j];
        dp[1][j][1] = a[0][j] - c;
    }
    for (int i = 1; i < n; i++){
        vector ndp(2,vector(m,vector<ll>(x+1,-linf)));
        vector top1(2,vector<pair<ll,int>>(x+1,{-linf,0}));
        vector top2(2,vector<pair<ll,int>>(x+1,{-linf,0}));
        auto upd = [](pair<ll,int> &t1, pair<ll,int> &t2, ll v, int j){
            if (v > t1.first){
                t2 = t1;
                t1 = {v, j};
            }
            else if (v > t2.first){
                t2 = {v, j};
            }
        };
        for (int t = 0; t <= x; t++){
            for (int j = 0; j < m; j++){
                upd(top1[0][t],top2[0][t],dp[0][j][t],j);
                upd(top1[1][t],top2[1][t],dp[1][j][t],j);
            }
        }
        auto get = [](pair<ll,int> &t1, pair<ll,int> &t2, int except){
            if (t1.second == except) return t2.first;
            return t1.first;
        };
        for (int t = 0; t <= x; t++){
            for (int k = 0; k < m; k++){
                // 0 -> 0
                chmax(ndp[0][k][t],min(get(top1[0][t],top2[0][t],k),a[i][k]));
                // 0 -> 1
                chmax(ndp[1][k][min(t+1,x)],min(get(top1[0][t],top2[0][t],k),a[i][k]-c));
                // 1 -> 0
                chmax(ndp[0][k][min(t+1,x)],min(dp[1][k][t],a[i][k]-c));
                // 1 -> 1
                chmax(ndp[1][k][min(t+1,x)],min(dp[1][k][t],a[i][k]-c));
            }
        }
        swap(dp,ndp);
    }
    ll ans = -linf;
    for (int j = 0; j < m; j++){
        chmax(ans,dp[0][j][x]);
    }
    cout << ans << '\n';
}
0