結果
問題 | No.20 砂漠のオアシス |
ユーザー | mai |
提出日時 | 2017-02-25 11:29:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 10 ms / 5,000 ms |
コード長 | 5,840 bytes |
コンパイル時間 | 1,653 ms |
コンパイル使用メモリ | 168,620 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 05:49:47 |
合計ジャッジ時間 | 2,217 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 6 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 7 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 10 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 3 ms
5,248 KB |
testcase_17 | AC | 3 ms
5,248 KB |
testcase_18 | AC | 3 ms
5,248 KB |
testcase_19 | AC | 4 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef unsigned int uint; typedef long long int ll; typedef unsigned long long int ull; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl; #define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;} #define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl; #define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;} #define debugaa0(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y][0]<<" ";}cout<<endl;} #define debugaa1(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y][1]<<" ";}cout<<endl;} #define ALL(v) (v).begin(),(v).end() #define BIGINT 0x7FFFFFFF #define E107 1000000007 template<typename T1,typename T2> ostream& operator <<(ostream &o,const pair<T1,T2> p){o<<"("<<p.first<<":"<<p.second<<")";return o;} // TODO: codeIQSandboxでは動くけれどCygwinでは動かず namespace{ class MaiScanner{ public: template<typename T> void input_integer(T& var){ var = 0; T sign = 1; int cc = getchar_unlocked(); for (;cc<'0'||'9'<cc; cc=getchar_unlocked()) if (cc=='-') sign=-1; for (;'0'<=cc&&cc<='9'; cc=getchar_unlocked()) var = (var<<3)+(var<<1) + cc-'0'; var=var*sign; } void ign(){getchar_unlocked();} MaiScanner& operator>>(int& var){ input_integer<int>(var); return *this; } MaiScanner& operator>>(long long& var){ input_integer<long long>(var); return *this; } }; class MaiPrinter{ int stack_p; char stack[32]; public: template<typename T> void output_integer(T var){ if (var == 0){ putchar_unlocked('0'); return; } if (var < 0){ putchar_unlocked('-'); var = -var; } stack_p=0; while (var){ stack[stack_p++]='0'+(var%10); var /= 10; } while(stack_p) putchar_unlocked(stack[--stack_p]); } MaiPrinter& operator<<(char c){ putchar_unlocked(c); return *this; } MaiPrinter& operator<<(int var){ output_integer<int>(var); return *this; } MaiPrinter& operator<<(long long var){ output_integer<long long>(var); return *this; } }; } MaiScanner scanner; MaiPrinter printer; template <size_t maxsize, typename T> class p_queue { T data[maxsize]; int size = 0; public: p_queue() {} // 一番大きい要素 const T& top() { return data[0]; } void pop() { int now = 0; int l = 1; int r = 2; swap(data[--size], data[0]); while (l < size) { if (data[now] < data[l]) { if (r < size && data[l] < data[r]) goto _l_pqpop_rswp; swap(data[now], data[l]); now = l; l = (now << 1) + 1; r = (now << 1) + 2; continue; } if (r < size && data[now] < data[r]) { _l_pqpop_rswp: swap(data[now], data[r]); now = r; l = (now << 1) + 1; r = (now << 1) + 2; continue; } break; } } void push(const T& val) { int p; int now = size++; data[now] = val; while (0 < now) { p = (now - 1) >> 1; if (data[now] > data[p]) { swap(data[now], data[p]); now = p; } else { break; } } } bool empty() { return size == 0; } }; int maze[250][250]; int dp[250][250][2]; int n; int main(){ int i,j,k,l,x,y; int hp,ox,oy; cin>>n>>hp>>ox>>oy; for (y=1;y<=n;++y) for (x=1;x<=n;++x){ scanner >> maze[x][y]; ++maze[x][y]; } // ------------------------------------------------------------------------------------------- hp+=maze[1][1]-1; // 次のマスへ移動すると、移動した先の砂漠レベル分の体力が減る。-> スタート地点は減算しない!! p_queue<50000,int> q; q.push((hp<<16)|(1<<8)|(1)); dp[1][1][0]=1; //int sushi=0; while (!q.empty()){ l=q.top();q.pop(); k= (l>>28); hp=(l>>16)&0xFFF; x =(l>> 8)&0xFF; y =(l )&0xFF; hp-=maze[x][y]-1; if (hp<=0) continue; if (x==n&&y==n){puts("YES");return 0;} if (ox==x && oy==y && !k){hp*=2;k=1;} if (dp[x-1][y][k]<hp && maze[x-1][y] && maze[x-1][y]<=hp){ dp[x-1][y][k]=hp;q.push((k<<28)|(hp<<16)|((x-1)<<8)|(y)); } if (dp[x+1][y][k]<hp && maze[x+1][y] && maze[x+1][y]<=hp){ dp[x+1][y][k]=hp;q.push((k<<28)|(hp<<16)|((x+1)<<8)|(y)); } if (dp[x][y-1][k]<hp && maze[x][y-1] && maze[x][y-1]<=hp){ dp[x][y-1][k]=hp;q.push((k<<28)|(hp<<16)|((x)<<8)|(y-1)); } if (dp[x][y+1][k]<hp && maze[x][y+1] && maze[x][y+1]<=hp){ dp[x][y+1][k]=hp;q.push((k<<28)|(hp<<16)|((x)<<8)|(y+1)); } } puts("NO"); // debugaa0(dp,n+1,n+1); // debugaa1(dp,n+1,n+1); return 0; }