結果
問題 | No.2657 Falling Block Game |
ユーザー |
|
提出日時 | 2024-03-01 23:31:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,077 bytes |
コンパイル時間 | 2,943 ms |
コンパイル使用メモリ | 260,612 KB |
実行使用メモリ | 16,976 KB |
最終ジャッジ日時 | 2024-09-29 15:17:08 |
合計ジャッジ時間 | 9,686 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 WA * 11 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h,w; cin >> h >> w; vector<string> S(h); for (auto &s: S) cin >> s; vector<int> dp(w,0); const int INF = 1e9; for (int i = h-2; i >= 0; i--){ vector<int> ndp(w,INF); vector<vector<pair<int,int>>> event(w); for (int x = 0; x < w; x++){ int cost = dp[x]; event[max(0,x-cost)].push_back({cost,1}); } for (int x = 0; x < w; x++){ event[x].push_back({x,0}); } for (int x = 0; x < w; x++){ int cost = dp[x]; event[min(w-1,x+cost)].push_back({cost,-1}); } multiset<int> ms; ms.insert(INF); for (int x = 0; x < w; x++){ for (auto [c,t] : event[x]){ if (t == 1) { ms.insert(c); } else if (t == 0){ if (S[i][c] == '#') continue; ndp[c] = *ms.begin(); } else{ auto it = ms.find(c); // イテレータがマルチセットの終端でない、つまり要素が見つかった場合、その要素を削除 if (it != ms.end()) { ms.erase(it); } else{ assert (0); } } } } for (int x = 1; x < w; x++){ if (S[i][x] == '#') continue; ndp[x] = min(ndp[x],ndp[x-1]+1); } for (int x = w-2;x >= 0; x--){ if (S[i][x] == '#') continue; ndp[x] = min(ndp[x],ndp[x+1]+1); } for (int x = 0;x < w; x++){ if (S[i][x] == '#'){ ndp[x] = INF; } if (i > 0 && S[i-1][x] != '.'){ ndp[x] = INF; } } swap(dp,ndp); } for (auto a: dp){ cout << a << endl; } return 0; }