結果

問題 No.3368 トッピング
コンテスト
ユーザー noya2
提出日時 2025-11-10 02:36:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 2,154 bytes
コンパイル時間 3,023 ms
コンパイル使用メモリ 281,956 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-17 20:44:41
合計ジャッジ時間 4,701 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*

答えで二分探索

dpdiff[i][j] : 位置 i まで見て，直前の種類が j で，次は j 以外と決めたときの，ペナルティが発生しない回数の最小値
dpsame[i][j] : 位置 i まで見て，直前の種類が j で，次も j と決めたときの，ペナルティが発生しない回数の最小値

next dp で次元を減らす

dpdiff は top2 しか持たなくて良い

*/
#include<bits/stdc++.h>
using namespace std;
const int iinf = 1001001007;
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; }

struct top2 {
    int v1, i1;
    int v2, i2;
    top2 () : v1(iinf), i1(-1), v2(iinf), i2(-1) {}
    void upd(int v, int i){
        if (v < v1){
            v2 = v1;
            i2 = i1;
            v1 = v;
            i1 = i;
        }
        else if (v < v2){
            v2 = v;
            i2 = i;
        }
    }
    int get(int except){
        return (i1 == except ? v2 : v1);
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m, c, x; cin >> n >> m >> c >> x;
    vector a(n,vector<int>(m));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    int le = -iinf, ri = iinf;
    while (ri - le > 1){
        int md = midpoint(le, ri);
        top2 dpdiff;
        vector<int> dpsame(m,iinf);
        dpdiff.upd(0,-1);
        for (int i = 0; i < n; i++){
            top2 ndpdiff;
            vector<int> ndpsame(m,iinf);
            for (int j = 0; j < m; j++){
                // diff
                if (a[i][j] >= md){
                    ndpdiff.upd(dpdiff.get(j)+1,j);
                }
                // same
                if (a[i][j] >= md+c){
                    ndpdiff.upd(dpsame[j],j);
                    chmin(ndpsame[j],dpsame[j]);
                    chmin(ndpsame[j],dpdiff.get(j));
                }
            }
            swap(ndpdiff,dpdiff);
            swap(ndpsame,dpsame);
        }
        if (dpdiff.v1 <= n-x){
            le = md;
        }
        else {
            ri = md;
        }
    }
    cout << le << endl;
}
0