結果
問題 | No.20 砂漠のオアシス |
ユーザー |
![]() |
提出日時 | 2014-11-05 15:19:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,971 bytes |
コンパイル時間 | 1,159 ms |
コンパイル使用メモリ | 104,072 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 04:57:36 |
合計ジャッジ時間 | 2,451 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 1 |
ソースコード
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <fstream> #include <queue> #define INF 100000000 #define EPS 1e-9 using namespace std; typedef pair<int, int> P; typedef long long ll; #define MAX_N 200 int N, V, Ox, Oy; int L[MAX_N][MAX_N]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1, -1 }; int dp[MAX_N][MAX_N]; void solve(){ queue<P> que; queue<int> l; queue<bool> oasis; que.push(P(0, 0)); l.push(V); oasis.push(true); dp[0][0] = V; while (que.size()){ P p = que.front(); int life = l.front(); bool flag = oasis.front(); que.pop(); l.pop(); oasis.pop(); int x = p.first; int y = p.second; if (x == N - 1 && y == N - 1 && dp[y][x] > 0) break; for (int i = 0; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < N && ny >= 0 && ny < N){ if (nx == Ox-1 && ny == Oy-1 && Ox != 0 && Oy != 0 && flag){ if (dp[ny][nx] < (life - L[ny][nx]) * 2){ dp[ny][nx] = (life - L[ny][nx]) * 2; que.push(P(nx, ny)); l.push((life - L[ny][nx]) * 2); oasis.push(false); } } else{ if (dp[ny][nx] < life - L[ny][nx]){ dp[ny][nx] = life - L[ny][nx]; que.push(P(nx, ny)); l.push(life - L[ny][nx]); oasis.push(flag); } } } } } } int main() { cin >> N >> V >> Ox >> Oy; for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ cin >> L[i][j]; } } solve(); if (dp[N - 1][N - 1] > 0) cout << "YES" << endl; else cout << "NO" << endl; return 0; }