結果

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

ソースコード

diff # 

#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(m,vector(x+1,vector<ll>(2,-linf)));
    for (int j = 0; j < m; j++){
        dp[j][0][0] = a[0][j];
        dp[j][1][1] = a[0][j] - c;
    }
    for (int i = 1; i < n; i++){
        vector ndp(m,vector(x+1,vector<ll>(2,-linf)));
        for (int j = 0; j < m; j++){
            for (int t = 0; t <= x; t++){
                for (int k = 0; k < m; k++){
                    if (j != k){
                        // 0 -> 0
                        chmax(ndp[k][t][0],min(dp[j][t][0],a[i][k]));
                        // 0 -> 1
                        chmax(ndp[k][min(t+1,x)][1],min(dp[j][t][0],a[i][k]-c));
                    }
                    else {
                        // 1 -> 0
                        chmax(ndp[k][min(t+1,x)][0],min(dp[j][t][1],a[i][k]-c));
                        // 1 -> 1
                        chmax(ndp[k][min(t+1,x)][1],min(dp[j][t][1],a[i][k]-c));
                    }
                }
            }
        }
        swap(dp,ndp);
    }
    ll ans = -linf;
    for (int j = 0; j < m; j++){
        chmax(ans,dp[j][x][0]);
    }
    cout << ans << '\n';
}
0