結果
問題 | No.20 砂漠のオアシス |
ユーザー | Mister |
提出日時 | 2020-08-22 04:58:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 5,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 1,499 ms |
コンパイル使用メモリ | 92,388 KB |
最終ジャッジ日時 | 2025-01-13 06:45:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <tuple> #include <queue> template <class T> std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); } template <class T> using MaxHeap = std::priority_queue<T>; const std::vector<std::pair<int, int>> dxys{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; void solve() { int n, m, ox, oy; std::cin >> n >> m >> ox >> oy; --ox, --oy; std::swap(ox, oy); auto xss = vec(n, vec(n, 0)); for (auto& xs : xss) { for (auto& x : xs) std::cin >> x; } auto dp = vec(2, vec(n, vec(n, 0))); dp[0][0][0] = m; MaxHeap<std::tuple<int, int, int, int>> heap; heap.emplace(dp[0][0][0], 0, 0, 0); while (!heap.empty()) { auto [d, t, x, y] = heap.top(); heap.pop(); if (d < dp[t][x][y]) continue; if (t == 0 && x == ox && y == oy) { dp[1][x][y] = dp[0][x][y] * 2; heap.emplace(dp[1][x][y], 1, x, y); } for (auto [dx, dy] : dxys) { int nx = x + dx, ny = y + dy; if (nx < 0 || n <= nx || ny < 0 || n <= ny || dp[t][nx][ny] >= dp[t][x][y] - xss[nx][ny]) continue; dp[t][nx][ny] = dp[t][x][y] - xss[nx][ny]; heap.emplace(dp[t][nx][ny], t, nx, ny); } } std::cout << (dp[0][n - 1][n - 1] == 0 && dp[1][n - 1][n - 1] == 0 ? "NO" : "YES") << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }