結果

問題 No.3368 トッピング
コンテスト
ユーザー Naru820
提出日時 2025-11-14 15:13:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 279 ms / 2,000 ms
コード長 1,801 bytes
コンパイル時間 2,919 ms
コンパイル使用メモリ 279,608 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-17 20:46:12
合計ジャッジ時間 5,513 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

// サンプル3に嘘がおいてあってあり得ない！！！！！！！！！！テストケースに入ってないし！！！！！
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n,m,c,x,a[2000][200];
// 最小値をk以上にできるか？
bool isok(int k){
    vector<int> dp(m, -1e9), ep(m, -1e9);
    for(int j = 0; j < m; j++){
        if(a[0][j] >= k) ep[j] = 0;
    }
    for(int i = 1; i < n; i++){
        int best1 = -1e9, best2 = -1e9, idx = -1,ma = -1e9;
        for(int j = 0; j < m; j++){
            ma = max(dp[j], ep[j]);
            if(ma > best1){
                best2 = best1;
                best1 = ma;
                idx = j;
            } 
            else if(ma > best2){
                best2 = ma;
            }
        }
        vector<int> newdp(m, -1e9), newep(m, -1e9);
        for(int j = 0; j < m; j++){
            if(a[i][j] >= k){
                int use = (idx != j ? best1 : best2);
                newep[j] = max(newep[j], use);
            }
            if(min(a[i][j], a[i-1][j]) >= k + c){
                newdp[j] = max(newdp[j], ep[j] + 2);
                newdp[j] = max(newdp[j], dp[j] + 1);
            }
        }
        dp.swap(newdp);
        ep.swap(newep);
    }
    int best = -1e9;
    for(int j = 0; j < m; j++){
        best = max(best, dp[j]);
        best = max(best, ep[j]);
    }
    return best >= x;
}
int main(){
    cin >> n >> m >> c >> x;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    // 解を決め打つ二分探索
    int l = -1e9,r = 1e9 + 1;
    while(r - l > 1){
        int m = (r + l) / 2;
        if(isok(m)){
            l = m;
        }
        else{
            r = m;
        }
    }
    cout << l << '\n';
}
0