제출 #815160

#제출 시각아이디문제언어결과실행 시간메모리
815160eltu0815던전 (IOI21_dungeons)C++17
89 / 100
7174 ms1794332 KiB
#include "dungeons.h" #include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; int N; const int MX = 25; int pos[MX][400001][9]; ll sum[MX][400001][9], mx[MX][400001][9]; int tmp1[400001]; ll tmp2[400001], tmp3[400001]; void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) { N = n; for(int j = 0; j < MX; ++j) { for(int i = 0; i < N; ++i) { pos[j][i][0] = (1 << j) <= S[i] ? L[i] : W[i]; sum[j][i][0] = (1 << j) <= S[i] ? P[i] : S[i]; mx[j][i][0] = (1 << j) <= S[i] ? -S[i] : -(ll)(1e16); } pos[j][N][0] = N, sum[j][N][0] = 0; } for(int k = 0; k < MX; ++k) for(int j = 1; j <= 8; ++j) { for(int i = 0; i <= N; ++i) { pos[k][i][j] = pos[k][pos[k][i][j - 1]][j - 1]; sum[k][i][j] = sum[k][pos[k][i][j - 1]][j - 1] + sum[k][i][j - 1]; mx[k][i][j] = max(mx[k][i][j - 1], sum[k][i][j - 1] + mx[k][pos[k][i][j - 1]][j - 1]); tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j]; } for(int i = 0; i <= N; ++i) { mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]); sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i]; pos[k][i][j] = tmp1[tmp1[i]]; } for(int i = 0; i <= N; ++i) tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j]; for(int i = 0; i <= N; ++i) { mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]); sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i]; pos[k][i][j] = tmp1[tmp1[i]]; } } return; } long long simulate(int x, int z) { ll ans = z; for(int k = 0; k < MX - 1; ++k) { for(int j = 8; j >= 0; --j) for(int t = 0; t < 7; ++t) { if(!(pos[k][x][j] == N || mx[k][x][j] + ans >= 0ll)) ans += sum[k][x][j], x = pos[k][x][j]; else break; } if(ans < (1 << k)) ans += sum[k][x][0], x = pos[k][x][0]; if(x == N) return ans; } for(int j = 8; j >= 0; --j) { for(int t = 0; t < 7; ++t) { if(pos[t - 1][x][j] != N) ans += sum[MX - 1][x][j], x = pos[MX - 1][x][j]; else break; } } ans += sum[MX - 1][x][0], x = pos[MX - 1][x][0]; return ans; } /* 3 2 2 2 2 3 1 2 2 2 3 1 0 1 0 1 2 3 16 4 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 1 1 1 1 1 1 1 10000000 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 8 10 2 10000000 3 1 */

컴파일 시 표준 에러 (stderr) 메시지

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:66:25: warning: array subscript -1 is below array bounds of 'int [25][400001][9]' [-Warray-bounds]
   66 |             if(pos[t - 1][x][j] != N) ans += sum[MX - 1][x][j], x = pos[MX - 1][x][j];
      |                ~~~~~~~~~^
dungeons.cpp:13:5: note: while referencing 'pos'
   13 | int pos[MX][400001][9];
      |     ^~~
#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...