結果
問題 | No.971 いたずらっ子 |
ユーザー | WarToks |
提出日時 | 2020-01-17 21:48:28 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 584 ms / 2,000 ms |
コード長 | 3,709 bytes |
コンパイル時間 | 1,516 ms |
コンパイル使用メモリ | 111,420 KB |
実行使用メモリ | 38,956 KB |
最終ジャッジ日時 | 2023-08-07 07:53:07 |
合計ジャッジ時間 | 6,939 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 584 ms
38,956 KB |
testcase_01 | AC | 581 ms
38,884 KB |
testcase_02 | AC | 431 ms
38,884 KB |
testcase_03 | AC | 477 ms
38,824 KB |
testcase_04 | AC | 447 ms
37,120 KB |
testcase_05 | AC | 471 ms
38,880 KB |
testcase_06 | AC | 365 ms
35,996 KB |
testcase_07 | AC | 6 ms
5,824 KB |
testcase_08 | AC | 117 ms
24,420 KB |
testcase_09 | AC | 112 ms
24,108 KB |
testcase_10 | AC | 6 ms
5,704 KB |
testcase_11 | AC | 2 ms
5,704 KB |
testcase_12 | AC | 2 ms
5,672 KB |
testcase_13 | AC | 2 ms
5,680 KB |
testcase_14 | AC | 9 ms
37,684 KB |
testcase_15 | AC | 1 ms
5,664 KB |
testcase_16 | AC | 3 ms
10,556 KB |
testcase_17 | AC | 2 ms
5,632 KB |
testcase_18 | AC | 2 ms
5,712 KB |
testcase_19 | AC | 2 ms
5,712 KB |
testcase_20 | AC | 2 ms
5,568 KB |
testcase_21 | AC | 2 ms
5,604 KB |
testcase_22 | AC | 2 ms
5,716 KB |
testcase_23 | AC | 2 ms
5,576 KB |
testcase_24 | AC | 1 ms
5,704 KB |
ソースコード
#include <iostream> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cstring> #include <deque> #include <functional> #include <initializer_list> #include <math.h> #include <map> #include <random> #include <set> #include <stack> #include <tuple> #include <queue> #include <vector> #define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i)) #define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i)) #define REP(i, n) FOR(i, 0, n) #define rREP(i, n) rFOR(i, 0, (n-1)) #define SORT(A) std::sort((A).begin(), (A).end()) #define ALL(A) (A).begin(), (A).end() // 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A) #define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end()) using lli = long long int; using pii = std::pair<int, int>; // グリッド上の縦横移動 constexpr std::array<std::pair<int, int>, 4> dxdy = { std::pair<int, int>( 1, 0), std::pair<int, int>(-1, 0), std::pair<int, int>( 0, 1), std::pair<int, int>( 0, -1) }; void VintOut(std::vector<int>& A){ const int n = A.size(); if(n == 0){putchar('\n'); return;} printf("%d", A[0]); for(int i = 1; i < n; ++i) printf(" %d", A[i]); putchar('\n'); } void VintOut(std::vector<long long int>& A){ const int n = A.size(); if(n == 0){ putchar('\n'); return;} printf("%lld", A[0]); for(int i = 1; i < n; ++i) printf(" %lld", A[i]); putchar('\n'); } template <typename T> inline bool chmin(T& a, T b){ if(b < a){ a = b; return true;} return false; } template <typename T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true;} return false; } inline bool isIn(int x, int y, int H, int W){ return 0 <= x and x < H and 0 <= y and y < W; } inline bool bitUP(int state, int k){ return (state >> k) & 1; } inline bool bitUP(long long int state, int k){ return (state >> k) & 1;} // z-algorithm template <class T> std::vector<int> z_algorithm(const T &str) { const int n = str.size(); std::vector<int> resOfCP(n); resOfCP[0] = n; int i = 1, j = 0; while (i < n) { while (i + j < n and str[j] == str[i + j]) ++j; resOfCP[i] = j; if (j == 0) { ++i; continue;} int k = 1; while (i + k < n and k + resOfCP[k] < j) resOfCP[i + k] = resOfCP[k], ++k; i += k; j -= k; } return resOfCP; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ constexpr int N = 2000; char str[N+1][N+1]; constexpr lli inf = 1e18 + 334 + 810 + 1919; std::array<std::array<lli, N + 1>, N + 1> Dist; int main(void){ int H, W; scanf("%d%d", &H, &W); REP(i, H) scanf("%s", str[i]); REP(i, H) REP(j, W) Dist[i][j] = inf; Dist[0][0] = 0; using datum = std::tuple<lli, int, int> ; std::priority_queue<datum, std::vector<datum>, std::greater<datum>> PQ; PQ.emplace(0, 0, 0); while(not PQ.empty()){ lli dist; int x, y; std::tie(dist, x, y) = PQ.top(); PQ.pop(); if(Dist[x][y] < dist) continue; int d; if(x + 1 < H){ d = str[x+1][y] == 'k' ? (x + y + 1) : 0; if(Dist[x+1][y] > Dist[x][y] + d){ Dist[x+1][y] = Dist[x][y] + d; PQ.emplace(Dist[x+1][y], x+1, y); } } if(y + 1 < W){ d = (str[x][y+1] == 'k') ? (x + y + 1) : 0; if(Dist[x][y+1] > Dist[x][y] + d){ Dist[x][y+1] = Dist[x][y] + d; PQ.emplace(Dist[x][y+1], x, y + 1); } } } lli res = Dist[H-1][W-1] + (H - 1) + (W - 1); printf("%lld\n", res); return 0; }