結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0