#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll oo = 1e18;
const ld eps = (ld)1 / oo;
const ll N = 4e5 + 1;
const ll M = 25;
const int M1 = 8;
const int M2 = 9;
vector <int> s, p, w, l;
int n;
ll sum[M][N][M2];
ll mx[M][N][M2];
int nx[M][N][M2];
void init(int n1, vector <int> s1, vector <int> p1, vector <int> w1, vector <int> l1)
{
n = n1;
s = s1, p = p1, w = w1, l = l1;
for (int pw = 0; pw < M; pw++)
{
for (int i = 0; i < n; i++)
if (s[i] < (1ll << pw))
{
nx[pw][i][0] = w[i];
mx[pw][i][0] = -oo;
sum[pw][i][0] = s[i];
}
else
{
nx[pw][i][0] = l[i];
mx[pw][i][0] = -s[i];
sum[pw][i][0] = p[i];
}
nx[pw][n][0] = n;
mx[pw][n][0] = -oo;
sum[pw][n][0] = 0;
for (int j = 1; j < M2; j++)
{
for (int i = 0; i <= n; i++)
{
nx[pw][i][j] = nx[pw][i][j - 1];
mx[pw][i][j] = mx[pw][i][j - 1];
sum[pw][i][j] = sum[pw][i][j - 1];
for (int p = 1; p < M1; p++)
{
int c = nx[pw][i][j];
nx[pw][i][j] = nx[pw][c][j - 1];
mx[pw][i][j] = max(mx[pw][i][j], mx[pw][c][j - 1] + sum[pw][i][j]);
sum[pw][i][j] = sum[pw][i][j] + sum[pw][c][j - 1];
}
}
}
}
}
ll simulate(int x, int y1)
{
ll y = y1;
for (int i = 0; i < M; i++)
if (((1ll << i) <= y && (1ll << (i + 1)) > y) || i == M - 1)
{
for (int j = M2 - 1; j >= 0; j--)
{
for (int c = 0; c < M1 && mx[i][x][j] + y < 0; c++) y += sum[i][x][j], x = nx[i][x][j];
}
if (x == n) return y;
y += s[x];
x = w[x];
}
return y;
}
//int main()
//{
// srand(time(NULL));
// ll n, q;
// cin >> n >> q;
// vector <int> a(n), b(n), c(n), d(n);
// for (ll i = 0; i < n; i++) cin >> a[i];
// for (ll i = 0; i < n; i++) cin >> b[i];
// for (ll i = 0; i < n; i++) cin >> c[i];
// for (ll i = 0; i < n; i++) cin >> d[i];
// init(n, a, b, c, d);
// while (q--)
// {
// ll x, z;
// cin >> x >> z;
// cout << simulate(x, z) << endl;
// }
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
3 |
Correct |
16 ms |
9812 KB |
Output is correct |
4 |
Correct |
490 ms |
223700 KB |
Output is correct |
5 |
Correct |
18 ms |
9812 KB |
Output is correct |
6 |
Correct |
475 ms |
223684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5332 KB |
Output is correct |
2 |
Correct |
5680 ms |
1781136 KB |
Output is correct |
3 |
Correct |
5327 ms |
1788056 KB |
Output is correct |
4 |
Correct |
4921 ms |
1789496 KB |
Output is correct |
5 |
Correct |
4776 ms |
1789584 KB |
Output is correct |
6 |
Correct |
5995 ms |
1788032 KB |
Output is correct |
7 |
Correct |
4282 ms |
1786308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5332 KB |
Output is correct |
2 |
Correct |
646 ms |
224092 KB |
Output is correct |
3 |
Correct |
393 ms |
224116 KB |
Output is correct |
4 |
Correct |
464 ms |
224092 KB |
Output is correct |
5 |
Correct |
367 ms |
224108 KB |
Output is correct |
6 |
Correct |
651 ms |
224092 KB |
Output is correct |
7 |
Correct |
675 ms |
224208 KB |
Output is correct |
8 |
Correct |
397 ms |
224096 KB |
Output is correct |
9 |
Correct |
457 ms |
224104 KB |
Output is correct |
10 |
Correct |
441 ms |
224204 KB |
Output is correct |
11 |
Correct |
1094 ms |
224096 KB |
Output is correct |
12 |
Correct |
1827 ms |
224100 KB |
Output is correct |
13 |
Correct |
646 ms |
224168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5332 KB |
Output is correct |
2 |
Correct |
646 ms |
224092 KB |
Output is correct |
3 |
Correct |
393 ms |
224116 KB |
Output is correct |
4 |
Correct |
464 ms |
224092 KB |
Output is correct |
5 |
Correct |
367 ms |
224108 KB |
Output is correct |
6 |
Correct |
651 ms |
224092 KB |
Output is correct |
7 |
Correct |
675 ms |
224208 KB |
Output is correct |
8 |
Correct |
397 ms |
224096 KB |
Output is correct |
9 |
Correct |
457 ms |
224104 KB |
Output is correct |
10 |
Correct |
441 ms |
224204 KB |
Output is correct |
11 |
Correct |
1094 ms |
224096 KB |
Output is correct |
12 |
Correct |
1827 ms |
224100 KB |
Output is correct |
13 |
Correct |
646 ms |
224168 KB |
Output is correct |
14 |
Correct |
7 ms |
5332 KB |
Output is correct |
15 |
Correct |
544 ms |
224092 KB |
Output is correct |
16 |
Correct |
658 ms |
224132 KB |
Output is correct |
17 |
Correct |
465 ms |
224128 KB |
Output is correct |
18 |
Correct |
433 ms |
224112 KB |
Output is correct |
19 |
Correct |
686 ms |
224200 KB |
Output is correct |
20 |
Correct |
504 ms |
224080 KB |
Output is correct |
21 |
Correct |
525 ms |
224100 KB |
Output is correct |
22 |
Correct |
458 ms |
224128 KB |
Output is correct |
23 |
Correct |
1074 ms |
224124 KB |
Output is correct |
24 |
Correct |
1590 ms |
224080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5332 KB |
Output is correct |
2 |
Correct |
646 ms |
224092 KB |
Output is correct |
3 |
Correct |
393 ms |
224116 KB |
Output is correct |
4 |
Correct |
464 ms |
224092 KB |
Output is correct |
5 |
Correct |
367 ms |
224108 KB |
Output is correct |
6 |
Correct |
651 ms |
224092 KB |
Output is correct |
7 |
Correct |
675 ms |
224208 KB |
Output is correct |
8 |
Correct |
397 ms |
224096 KB |
Output is correct |
9 |
Correct |
457 ms |
224104 KB |
Output is correct |
10 |
Correct |
441 ms |
224204 KB |
Output is correct |
11 |
Correct |
1094 ms |
224096 KB |
Output is correct |
12 |
Correct |
1827 ms |
224100 KB |
Output is correct |
13 |
Correct |
646 ms |
224168 KB |
Output is correct |
14 |
Correct |
7 ms |
5332 KB |
Output is correct |
15 |
Correct |
544 ms |
224092 KB |
Output is correct |
16 |
Correct |
658 ms |
224132 KB |
Output is correct |
17 |
Correct |
465 ms |
224128 KB |
Output is correct |
18 |
Correct |
433 ms |
224112 KB |
Output is correct |
19 |
Correct |
686 ms |
224200 KB |
Output is correct |
20 |
Correct |
504 ms |
224080 KB |
Output is correct |
21 |
Correct |
525 ms |
224100 KB |
Output is correct |
22 |
Correct |
458 ms |
224128 KB |
Output is correct |
23 |
Correct |
1074 ms |
224124 KB |
Output is correct |
24 |
Correct |
1590 ms |
224080 KB |
Output is correct |
25 |
Correct |
619 ms |
223316 KB |
Output is correct |
26 |
Correct |
640 ms |
224100 KB |
Output is correct |
27 |
Correct |
453 ms |
224116 KB |
Output is correct |
28 |
Correct |
476 ms |
224088 KB |
Output is correct |
29 |
Correct |
633 ms |
224104 KB |
Output is correct |
30 |
Correct |
496 ms |
224088 KB |
Output is correct |
31 |
Correct |
493 ms |
224088 KB |
Output is correct |
32 |
Correct |
1331 ms |
224108 KB |
Output is correct |
33 |
Correct |
634 ms |
224068 KB |
Output is correct |
34 |
Correct |
1300 ms |
224196 KB |
Output is correct |
35 |
Correct |
915 ms |
224112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5332 KB |
Output is correct |
2 |
Correct |
5680 ms |
1781136 KB |
Output is correct |
3 |
Correct |
5327 ms |
1788056 KB |
Output is correct |
4 |
Correct |
4921 ms |
1789496 KB |
Output is correct |
5 |
Correct |
4776 ms |
1789584 KB |
Output is correct |
6 |
Correct |
5995 ms |
1788032 KB |
Output is correct |
7 |
Correct |
4282 ms |
1786308 KB |
Output is correct |
8 |
Correct |
8 ms |
5332 KB |
Output is correct |
9 |
Correct |
646 ms |
224092 KB |
Output is correct |
10 |
Correct |
393 ms |
224116 KB |
Output is correct |
11 |
Correct |
464 ms |
224092 KB |
Output is correct |
12 |
Correct |
367 ms |
224108 KB |
Output is correct |
13 |
Correct |
651 ms |
224092 KB |
Output is correct |
14 |
Correct |
675 ms |
224208 KB |
Output is correct |
15 |
Correct |
397 ms |
224096 KB |
Output is correct |
16 |
Correct |
457 ms |
224104 KB |
Output is correct |
17 |
Correct |
441 ms |
224204 KB |
Output is correct |
18 |
Correct |
1094 ms |
224096 KB |
Output is correct |
19 |
Correct |
1827 ms |
224100 KB |
Output is correct |
20 |
Correct |
646 ms |
224168 KB |
Output is correct |
21 |
Correct |
7 ms |
5332 KB |
Output is correct |
22 |
Correct |
544 ms |
224092 KB |
Output is correct |
23 |
Correct |
658 ms |
224132 KB |
Output is correct |
24 |
Correct |
465 ms |
224128 KB |
Output is correct |
25 |
Correct |
433 ms |
224112 KB |
Output is correct |
26 |
Correct |
686 ms |
224200 KB |
Output is correct |
27 |
Correct |
504 ms |
224080 KB |
Output is correct |
28 |
Correct |
525 ms |
224100 KB |
Output is correct |
29 |
Correct |
458 ms |
224128 KB |
Output is correct |
30 |
Correct |
1074 ms |
224124 KB |
Output is correct |
31 |
Correct |
1590 ms |
224080 KB |
Output is correct |
32 |
Correct |
619 ms |
223316 KB |
Output is correct |
33 |
Correct |
640 ms |
224100 KB |
Output is correct |
34 |
Correct |
453 ms |
224116 KB |
Output is correct |
35 |
Correct |
476 ms |
224088 KB |
Output is correct |
36 |
Correct |
633 ms |
224104 KB |
Output is correct |
37 |
Correct |
496 ms |
224088 KB |
Output is correct |
38 |
Correct |
493 ms |
224088 KB |
Output is correct |
39 |
Correct |
1331 ms |
224108 KB |
Output is correct |
40 |
Correct |
634 ms |
224068 KB |
Output is correct |
41 |
Correct |
1300 ms |
224196 KB |
Output is correct |
42 |
Correct |
915 ms |
224112 KB |
Output is correct |
43 |
Correct |
1 ms |
852 KB |
Output is correct |
44 |
Correct |
10 ms |
5316 KB |
Output is correct |
45 |
Execution timed out |
7069 ms |
1158788 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |