제출 #633693

#제출 시각아이디문제언어결과실행 시간메모리
633693tabr던전 (IOI21_dungeons)C++17
63 / 100
1851 ms416312 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif // editorial const int N = 50001; int n; int s[N]; int p[N]; int w[N]; int l[N]; vector<vector<int>> nxt[25]; vector<vector<int>> lim[25]; vector<vector<int>> inc[25]; /* int nxt[25][25][N]; int lim[25][25][N]; int inc[25][25][N]; */ long long d[N]; void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) { for (int i = 0; i < 25; i++) { nxt[i] = vector<vector<int>>(i + 1, vector<int>(N)); lim[i] = vector<vector<int>>(i + 1, vector<int>(N)); inc[i] = vector<vector<int>>(i + 1, vector<int>(N)); } n = n_; for (int i = 0; i < n; i++) { s[i] = s_[i]; p[i] = p_[i]; w[i] = w_[i]; l[i] = l_[i]; } for (int i = n - 1; i >= 0; i--) { d[i] = d[w[i]] + s[i]; } for (int i = 0; i < 25; i++) { for (int x = 0; x < n; x++) { if (s[x] >= (1 << i)) { nxt[i][0][x] = l[x]; lim[i][0][x] = max(0, min((1 << (i + 1)) - p[x], s[x])); inc[i][0][x] = p[x]; } else { nxt[i][0][x] = w[x]; lim[i][0][x] = (1 << (i + 1)) - s[x]; inc[i][0][x] = s[x]; } } nxt[i][0][n] = n; for (int j = 1; j <= i; j++) { nxt[i][j][n] = n; for (int x = 0; x < n; x++) { int y = nxt[i][j - 1][x]; nxt[i][j][x] = nxt[i][j - 1][y]; lim[i][j][x] = max(0, min(lim[i][j - 1][x], lim[i][j - 1][y] - inc[i][j - 1][x])); inc[i][j][x] = min(1 << 27, inc[i][j - 1][x] + inc[i][j - 1][y]); } } } } long long simulate(int x, int z) { long long res = z; for (int i = 0; i < 25; i++) { if (x == n) { break; } if (res < (1 << i)) { if (res >= s[x]) { res += s[x]; x = w[x]; } else { res += p[x]; x = l[x]; } } assert(res >= (1 << i)); for (int j = i; j >= 0; j--) { if (lim[i][j][x] > res) { res += inc[i][j][x]; x = nxt[i][j][x]; } } } res += d[x]; return res; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1}); debug(simulate(0, 1)); // 24 debug(simulate(2, 3)); // 25 return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...