結果
問題 | No.20 砂漠のオアシス |
ユーザー | hirokazu1020 |
提出日時 | 2015-07-20 17:19:08 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,288 bytes |
コンパイル時間 | 752 ms |
コンパイル使用メモリ | 87,392 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-13 05:20:37 |
合計ジャッジ時間 | 1,564 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<sstream>#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<numeric>#include<functional>#include<algorithm>#include<bitset>using namespace std;#define INF (1<<29)#define rep(i,n) for(int i=0;i<(int)(n);i++)#define all(v) v.begin(),v.end()#define uniq(v) v.erase(unique(all(v)),v.end())#define indexOf(v,x) (find(all(v),x)-v.begin())int n,v,ox,oy;int L[200][200];int maxv[200][200][2];struct S{int v,y,x,u;S(){}S(int a,int b,int c,int d):v(a),y(b),x(c),u(d){}bool operator <(const S &s)const {return v<s.v;}};int dy[]={-1,0,1,0};int dx[]={0,1,0,-1};int main(){cin>>n>>v>>ox>>oy;ox--;oy--;rep(i,n)rep(j,n)cin>>L[i][j];fill(maxv[0][0],maxv[200][0],0);priority_queue<S> pq;pq.push(S(v,0,0,0));maxv[0][0][0]=v;while(!pq.empty()){S a,b;a=pq.top();pq.pop();rep(j,4){b=a;b.y+=dy[j];b.x+=dx[j];if(b.y<0||n<=b.y||b.x<0||n<=b.x)continue;b.v-=L[b.y][b.x];if(b.y==oy&&b.x==ox && b.u==0){b.v*=2;b.u=1;}if(0<b.v && b.v>maxv[b.y][b.x][b.u]){maxv[b.y][b.x][b.u]=b.v;pq.push(b);}}}cout<<(0<maxv[n-1][n-1][0]||0<maxv[n-1][n-1][1]?"YES":"NO")<<endl;return 0;}