結果

問題 No.20 砂漠のオアシス
ユーザー hirokazu1020hirokazu1020
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0