結果

問題 No.20 砂漠のオアシス
ユーザー hirokazu1020hirokazu1020
提出日時 2015-07-20 17:19:08
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 1,288 bytes
コンパイル時間 813 ms
コンパイル使用メモリ 86,612 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-21 06:38:33
合計ジャッジ時間 1,382 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 11 ms
6,940 KB
testcase_06 AC 7 ms
6,940 KB
testcase_07 AC 11 ms
6,940 KB
testcase_08 AC 8 ms
6,944 KB
testcase_09 AC 11 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 4 ms
6,944 KB
testcase_17 AC 3 ms
6,940 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 4 ms
6,940 KB
testcase_20 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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