結果
| 問題 |
No.3368 トッピング
|
| コンテスト | |
| ユーザー |
 iro_
|
| 提出日時 | 2025-10-25 18:34:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,261 bytes |
| コンパイル時間 | 2,090 ms |
| コンパイル使用メモリ | 208,804 KB |
| 実行使用メモリ | 24,512 KB |
| 最終ジャッジ日時 | 2025-11-17 20:33:21 |
| 合計ジャッジ時間 | 8,655 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 13 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
long long C;
int X;
if(!(cin >> N >> M >> C >> X)) return 0;
vector<vector<long long>> A(N, vector<long long>(M));
long long lo = (1LL<<60), hi = -(1LL<<60);
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin >> A[i][j];
lo = min(lo, A[i][j]);
hi = max(hi, A[i][j]);
}
}
// search range: possible min beauty between lo-C and hi
long long L = - (1LL<<60), R = hi; // we binary search T in [L, R]
// But safe to set L = lo - C (lower bound), R = hi.
L = lo - C;
long long ans = L;
auto feasible = [&](long long T)->bool{
// build usable/fragile/robust
vector<vector<char>> usable(N, vector<char>(M, 0));
vector<vector<char>> fragile(N, vector<char>(M, 0));
vector<vector<char>> robust(N, vector<char>(M, 0));
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(A[i][j] >= T){
usable[i][j] = 1;
if(A[i][j] - C >= T){
robust[i][j] = 1;
} else {
fragile[i][j] = 1;
}
}
}
}
// If any position has zero usable types -> impossible
for(int i=0;i<N;i++){
bool ok=false;
for(int j=0;j<M;j++) if(usable[i][j]) { ok=true; break; }
if(!ok) return false;
}
// Try fixing starting color s (at pos 0) among usable[0][s]
// For each start color, DP forward positions 1..N-1
// state: map (color -> set of possible run lengths). We store as vector<bitset/X> or vector<bool>.
// Because X might be up to N, but we keep small memory by using unordered_set or bitset per color.
// We'll implement as vector<vector<char>> cur(M, vector<char>(X+1))
for(int start=0; start<M; ++start){
if(!usable[0][start]) continue;
// start run = 1, but check if fragile at pos0 prevents adjacency to pos1 later; we'll handle when extending.
// Initialize DP for position 0
vector<vector<char>> cur(M, vector<char>(X+1, 0));
cur[start][1] = 1;
// propagate positions 1..N-1
for(int i=1;i<N;i++){
vector<vector<char>> nxt(M, vector<char>(X+1, 0));
for(int prev_color=0; prev_color<M; ++prev_color){
for(int run=1; run<=X; ++run){
if(!cur[prev_color][run]) continue;
// try choose color q at position i
for(int q=0;q<M;++q){
if(!usable[i][q]) continue;
if(q == prev_color){
// can extend only if run < X and this position allows adjacency (i,q) must be robust
if(run < X && robust[i][q]){
int nr = run+1;
if(!nxt[q][nr]) nxt[q][nr] = 1;
}
// else cannot
} else {
// different color: always allowed as long as usable
if(!nxt[q][1]) nxt[q][1] = 1;
}
}
}
}
// if no state possible -> break early
bool any=false;
for(int q=0;q<M && !any;q++) for(int r=1;r<=X;r++) if(nxt[q][r]) { any=true; break; }
if(!any){
// this start fails
cur.clear();
break;
}
cur.swap(nxt);
}
if(cur.empty()) continue; // failed early for this start
// Now cur contains states at position N-1.
// Need to check circular wrap with start at position 0.
// Starting run at pos0 is 1 (we fixed). But there might be other ways to pick pos0 if we allowed different run? We only started with run=1.
// We must ensure adjacency between posN-1 and pos0 is allowed:
// For any end state (end_color, end_run) with cur[end_color][end_run]==1, check:
// - if end_color != start: adjacency different -> always fine, but also must ensure pos0 fragile still ok w.r.t pos1 (that was enforced earlier), and posN-1 fragile w.r.t posN-2 was enforced earlier. The wrap is different so no extra constraint.
// - if end_color == start: combined run = start_run(=1) + end_run must be <= X, AND pos0 and posN-1 must allow adjacency:
// * pos0: if fragile[0][start] then it disallows any neighbor same -> cannot have posN-1 same.
// * posN-1: if fragile[N-1][start] then it disallows neighbor same -> cannot have pos0 same.
bool ok_any = false;
for(int end_color=0; end_color<M && !ok_any; ++end_color){
for(int end_run=1; end_run<=X && !ok_any; ++end_run){
if(!cur[end_color][end_run]) continue;
if(end_color != start){
// also need to ensure adjacency between pos0 and pos1 (pos1 was handled in DP) and between posN-1 and posN-2 (handled),
// and adjacency posN-1 vs pos0 is different => fine.
ok_any = true;
break;
} else {
// same color across wrap:
if(1 + end_run <= X){
// but fragility at pos0 or posN-1 may forbid adjacency
if(fragile[0][start]) continue; // pos0 cannot have same neighbor
if(fragile[N-1][start]) continue;
// Also need to ensure that positions contributing to runs had robustness where adjacency exists.
// Those were enforced in DP for internal adjacencies. For wrap, adjacency between posN-1 and pos0 means pos0's adjacency with posN-1 must be allowed:
// pos0 adjacency to same was not enforced earlier (we only enforced pos0 vs pos1 indirectly),
// but we already checked fragile[0] above. For posN-1, if it was counted as part of end_run>1 then posN-1 needed robust (checked). If end_run==1 and posN-1 had same neighbor posN-2? that's already handled.
ok_any = true;
break;
}
}
}
}
if(ok_any) return true;
}
return false;
};
// binary search for maximum T with feasible(T) == true
long long low = L, high = R;
while(low <= high){
long long mid = (low + high) / 2;
if(feasible(mid)){
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << "\n";
return 0;
}