#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=4e5+5, kx=26;
struct node
{
ll loc, sm, mx;
node(): loc(0), sm(0), mx(0){}
node(ll loc, ll sm, ll mx): loc(loc), sm(sm), mx(mx){}
friend node operator+(const node &a, const node &b)
{
return node(b.loc, a.sm+b.sm, max(a.mx, b.mx-a.sm));
}
} dp[nx][kx];
ll N;
vector<ll> S(nx), L(nx);
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
for (int i=0; i<n; i++) S[i]=s[i], L[i]=l[i];
L[n]=n;
N=n;
//S[n]=LLONG_MAX;
for (int i=0; i<n; i++) dp[i][0]=node(w[i], s[i], s[i]);
dp[n][0]=node(n, 0, -1e18);
for (int i=1; i<kx; i++) for (int j=0; j<=n; j++) dp[j][i]=dp[j][i-1]+dp[dp[j][i-1].loc][i-1];
//for (int i=0; i<4; i++) for (int j=0; j<=n; j++) cout<<i<<' '<<j<<' '<<dp[j][i].loc<<' '<<dp[j][i].sm<<' '<<dp[j][i].mx<<'\n';
}
long long simulate(int x, int z) {
ll pw=z;
while (x!=N)
{
//cout<<"simulate "<<i<<' '<<x<<' '<<pw<<'\n';
if (pw<S[x])
{
pw+=S[x], x=L[x];
continue;
}
for (int j=kx-1; j>=0; j--) if (pw>=dp[x][j].mx) pw+=dp[x][j].sm, x=dp[x][j].loc;
pw+=S[x];
x=L[x];
}
return pw;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
102 ms |
250776 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
250808 KB |
Output is correct |
2 |
Correct |
420 ms |
271264 KB |
Output is correct |
3 |
Correct |
441 ms |
271028 KB |
Output is correct |
4 |
Correct |
388 ms |
272864 KB |
Output is correct |
5 |
Correct |
405 ms |
272468 KB |
Output is correct |
6 |
Correct |
440 ms |
271156 KB |
Output is correct |
7 |
Correct |
400 ms |
269552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
71 ms |
250964 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
71 ms |
250964 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
71 ms |
250964 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
250808 KB |
Output is correct |
2 |
Correct |
420 ms |
271264 KB |
Output is correct |
3 |
Correct |
441 ms |
271028 KB |
Output is correct |
4 |
Correct |
388 ms |
272864 KB |
Output is correct |
5 |
Correct |
405 ms |
272468 KB |
Output is correct |
6 |
Correct |
440 ms |
271156 KB |
Output is correct |
7 |
Correct |
400 ms |
269552 KB |
Output is correct |
8 |
Incorrect |
71 ms |
250964 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |