結果
| 問題 |
No.3368 トッピング
|
| コンテスト | |
| ユーザー |
 iro_
|
| 提出日時 | 2025-10-25 18:30:31 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,134 bytes |
| コンパイル時間 | 705 ms |
| コンパイル使用メモリ | 71,872 KB |
| 実行使用メモリ | 12,212 KB |
| 最終ジャッジ日時 | 2025-11-17 20:33:11 |
| 合計ジャッジ時間 | 3,579 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 2 RE * 12 |
ソースコード
//Gemini slow fast
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;
const int MAX_N = 105;
const int MAX_M = 105;
const int INF = MAX_N + 5;
ll N, M, X, C;
ll A[MAX_N][MAX_M];
// 空間計算量を O(M^3) にするため、i の次元を 2 にする (ローリング)
int dp[2][MAX_M][MAX_M][MAX_M];
int min_runs_p_eq_k[MAX_M][MAX_M];
int min_runs_p_neq_k[MAX_M][MAX_M];
// B, B_pen をグローバルにして check 関数で使い回す
bool B[MAX_N][MAX_M];
bool B_pen[MAX_N][MAX_M];
bool check(ll K) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
B[i][j] = (A[i][j] >= K);
B_pen[i][j] = (A[i][j] - C >= K);
}
}
// --- DPテーブル初期化 O(M^3) ---
// (i=0 と i=1 の分だけ)
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < M; ++j) {
for (int k = 0; k < M; ++k) {
for (int js = 0; js < M; ++js) {
dp[i][j][k][js] = INF;
}
}
}
}
// --- 始点(0, 1) を固定 O(M^2) ---
for (int j_start = 0; j_start < M; ++j_start) {
for (int k_start = 0; k_start < M; ++k_start) {
int start_run = (j_start == k_start) ? 2 : 1;
if (start_run <= X) {
// i=1 (1%2=1)
dp[1][k_start][j_start][j_start] = start_run;
}
}
}
// --- DP実行 (i = 2 から N-1) O(N M^3) ---
for (int i = 2; i < N; ++i) {
int curr = i % 2;
int prev = (i - 1) % 2;
// dp[curr] を INF で初期化
for (int j = 0; j < M; ++j) {
for (int k = 0; k < M; ++k) {
for (int js = 0; js < M; ++js) {
dp[curr][j][k][js] = INF;
}
}
}
// --- O(M^3) の前計算 (i-1 の行) ---
for (int k = 0; k < M; ++k) {
for (int js = 0; js < M; ++js) {
min_runs_p_eq_k[k][js] = INF;
min_runs_p_neq_k[k][js] = INF;
for (int p = 0; p < M; ++p) {
// prev を参照
int run = dp[prev][k][p][js];
if (run > X) continue;
if (k == p) {
min_runs_p_eq_k[k][js] = min(min_runs_p_eq_k[k][js], run);
} else {
min_runs_p_neq_k[k][js] = min(min_runs_p_neq_k[k][js], run);
}
}
}
}
// --- O(M^3) の遷移 ---
for (int j = 0; j < M; ++j) { // i のタイプ
for (int k = 0; k < M; ++k) { // i-1 のタイプ
for (int js = 0; js < M; ++js) { // 0 のタイプ
int best_run = INF;
if (j != k) { // Case 1: run length 1
if (min_runs_p_eq_k[k][js] <= X && B_pen[i - 1][k]) {
best_run = 1;
}
if (min_runs_p_neq_k[k][js] <= X && B[i - 1][k]) {
best_run = 1;
}
} else { // Case 2: run length + 1
if (!B_pen[i - 1][k]) continue;
if (min_runs_p_eq_k[k][js] < X) {
best_run = min(best_run, min_runs_p_eq_k[k][js] + 1);
}
if (min_runs_p_neq_k[k][js] < X) {
best_run = min(best_run, min_runs_p_neq_k[k][js] + 1);
}
}
// curr に書き込む
dp[curr][j][k][js] = best_run;
}
}
}
} // DP loop (i)
// --- 最終チェック O(M^3) ---
for (int j_start = 0; j_start < M; ++j_start) {
for (int j_final = 0; j_final < M; ++j_final) {
// --- 条件 1, 2 を満たす k_start が存在するか O(M) ---
bool exists_good_k_start = false;
for (int k_start = 0; k_start < M; ++k_start) {
bool check_init = ((j_start == k_start) ? 2 : 1) <= X;
bool penalized_0 = (j_start == j_final) || (j_start == k_start);
bool check_beauty0 = (penalized_0 ? B_pen[0][j_start] : B[0][j_start]);
if (check_init && check_beauty0) {
exists_good_k_start = true;
break;
}
}
if (!exists_good_k_start) continue;
// --- 条件 3, 4 を満たす k_final が存在するか O(M) ---
bool exists_good_k_final = false;
for (int k_final = 0; k_final < M; ++k_final) {
// N-1 の行 ( (N-1)%2 ) を参照
int final_run = dp[(N - 1) % 2][j_final][k_final][j_start];
bool check_dp = (final_run <= X);
bool penalized_N_1 = (j_final == k_final) || (j_final == j_start);
bool check_beautyN_1 = (penalized_N_1 ? B_pen[N - 1][j_final] : B[N - 1][j_final]);
if (check_dp && check_beautyN_1) {
exists_good_k_final = true;
break;
}
}
if (exists_good_k_final) {
return true;
}
}
}
return false;
}
int main() {
// 高速化
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> N >> M >> X >> C;
ll max_a = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> A[i][j];
max_a = max(max_a, A[i][j]);
}
}
ll low = 0;
ll high = max_a + 1;
ll ans = 0;
while (low <= high) {
ll mid = low + (high - low) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}