oj.uz

Submission #551325

# Submission time Handle Problem Language Result Execution time Memory
551325 2022-04-20T10:07:06 Z topovik Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1789584 KB 
#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;
//    }
//}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory 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

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory 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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory 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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory 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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory 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

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory 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 -