結果
| 問題 |
No.3368 トッピング
|
| コンテスト | |
| ユーザー |
 iro_
|
| 提出日時 | 2025-10-25 16:54:13 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,902 bytes |
| コンパイル時間 | 619 ms |
| コンパイル使用メモリ | 72,588 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-11-17 20:31:56 |
| 合計ジャッジ時間 | 29,615 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | RE * 6 TLE * 6 -- * 2 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;
// N, M は 100 までなので、105 確保
const int MAX_N = 105;
const int MAX_M = 105;
// INF は N+1 より大きければよい
const int INF = MAX_N + 5;
ll N, M, X, C;
ll A[MAX_N][MAX_M];
// dp[i][j][k][j_start]
// i: 位置 (0..N-1)
// j: i のタイプ (0..M-1)
// k: i-1 のタイプ (0..M-1)
// j_start: 0 のタイプ (0..M-1)
// 値: i で終わるタイプ j の最小連続長
int dp[MAX_N][MAX_M][MAX_M][MAX_M];
// DP高速化のためのヘルパー配列
// min_runs_p_eq_k[k][j_start] = min(dp[i-1][k][p][j_start]) (p == k の場合)
// min_runs_p_neq_k[k][j_start] = min(dp[i-1][k][p][j_start]) (p != k の場合)
int min_runs_p_eq_k[MAX_M][MAX_M];
int min_runs_p_neq_k[MAX_M][MAX_M];
// 美しさ K を達成できるか
bool check(ll K) {
// B[i][j]: (i, j) がペナルティなしで K 以上か
// B_pen[i][j]: (i, j) がペナルティありで K 以上か
bool B[MAX_N][MAX_M];
bool B_pen[MAX_N][MAX_M];
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(N M^3) ---
for (int i = 0; i < N; ++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, j=k_start, k=j_start, j_start=j_start
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) {
// --- 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) {
int run = dp[i - 1][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;
// (i-1)の美しさチェック
// (i-1)の隣は(i-2)=p と (i)=j
// Case 1: j != k (run length が 1 にリセット)
if (j != k) {
// (i-2)=p=k の場合 (ペナルティあり)
if (min_runs_p_eq_k[k][js] <= X && B_pen[i - 1][k]) {
best_run = 1;
}
// (i-2)=p!=k の場合 (ペナルティなし)
if (min_runs_p_neq_k[k][js] <= X && B[i - 1][k]) {
best_run = 1;
}
}
// Case 2: j == k (run length が +1)
else {
// (i-1)の隣は(i-2)=p と (i)=j=k
// (i-1)は p に関わらずペナルティ
if (!B_pen[i - 1][k]) {
continue; // この (j, k, js) の組合せは不可
}
// (i-2)=p=k の場合
if (min_runs_p_eq_k[k][js] < X) { // +1 するので < X
best_run = min(best_run, min_runs_p_eq_k[k][js] + 1);
}
// (i-2)=p!=k の場合
if (min_runs_p_neq_k[k][js] < X) {
best_run = min(best_run, min_runs_p_neq_k[k][js] + 1);
}
}
dp[i][j][k][js] = best_run;
}
}
}
} // DP loop (i)
// --- 最終チェック O(M^4) ---
// (j_start, k_start, j_final, k_final) を全探索
for (int j_start = 0; j_start < M; ++j_start) {
for (int k_start = 0; k_start < M; ++k_start) {
// (0, 1) の初期run lengthを再確認
int start_run_check = (j_start == k_start) ? 2 : 1;
if (start_run_check > X) continue;
for (int j_final = 0; j_final < M; ++j_final) { // N-1 のタイプ
for (int k_final = 0; k_final < M; ++k_final) { // N-2 のタイプ
int final_run = dp[N - 1][j_final][k_final][j_start];
if (final_run > X) continue;
// (N-1) の美しさチェック
// 隣は (N-2, k_final) と (0, j_start)
bool penalized_N_1 = (j_final == k_final) || (j_final == j_start);
if (penalized_N_1 && !B_pen[N - 1][j_final]) continue;
if (!penalized_N_1 && !B[N - 1][j_final]) continue;
// (0) の美しさチェック
// 隣は (N-1, j_final) と (1, k_start)
bool penalized_0 = (j_start == j_final) || (j_start == k_start);
if (penalized_0 && !B_pen[0][j_start]) continue;
if (!penalized_0 && !B[0][j_start]) continue;
// すべてのチェックをパスした
return true;
}
}
}
}
return false; // M^4 通りの組合せすべてが失敗
}
int main() {
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; // 答えの最大値は Aij の最大値
ll ans = 0;
// 二分探索
while (low <= high) {
ll mid = low + (high - low) / 2;
if (check(mid)) {
ans = mid; // mid は達成可能
low = mid + 1; // もっと上を探す
} else {
high = mid - 1; // mid は達成不可能
}
}
cout << ans << endl;
return 0;
}