oj.uz

답안 #538999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538999 2022-03-18T07:33:28 Z 79brue 던전 (IOI21_dungeons) C++17
100 / 100
 3692 ms 1549624 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
const int LIM = 25;

int n;
int arr[400002], power[400002];
int w[400002], l[400002];

int nxt[350][400002]; /// 계속 지기만 했을 때의 최종 위치
int sum[350][400002]; /// 계속 지기만 했을 때의 체력 변화
int lim[350][400002]; /// 계속 지기만 할 수 있기 위한 최초 체력의 최댓값
ll bonus[400002];

int idxArr[30];
int idx[30][30];

void init(int N, vector<int> s, vector<int> p, vector<int> W, vector<int> L){
    for(int i=1; i<=26; i++) idxArr[i] = idxArr[i-1] + i;
    for(int i=0; i<30; i++) for(int j=0; j<30; j++) idx[i][j] = idxArr[i]+j;

	n = N;
	for(int i=0; i<n; i++) arr[i] = s[i];
	for(int i=0; i<n; i++) power[i] = p[i], w[i]=W[i], l[i]=L[i];
	l[n]=w[n]=n;
	arr[n] = 1e9, power[n]=1e9;

    for(int f=0; f<LIM; f++){
        for(int i=0; i<=n; i++){
            int tmp = idx[f][0];
            if((1<<f) <= arr[i]){
                nxt[tmp][i] = l[i];
                sum[tmp][i] = power[i];
                lim[tmp][i] = arr[i]-1;
            }
            else{
                nxt[tmp][i] = w[i];
                sum[tmp][i] = arr[i];
                lim[tmp][i] = 1e9;
            }
        }
        for(int d=1; d<=f; d++){
            for(int i=0; i<=n; i++){
                int tmp = idx[f][d];
                nxt[tmp][i] = nxt[tmp-1][nxt[tmp-1][i]];
                sum[tmp][i] = min(1000000000, sum[tmp-1][i] + sum[tmp-1][nxt[tmp-1][i]]);
                lim[tmp][i] = min(lim[tmp-1][i], lim[tmp-1][nxt[tmp-1][i]] - sum[tmp-1][i]);
            }
        }
    }

    for(int i=n-1; i>=0; i--){
        bonus[i] = ll(arr[i]) + bonus[w[i]];
    }
}

ll simulate(int x, int z){
    for(int f=0; f<LIM; f++){
        if((1<<(f+1)) <= z || x==n) continue;

        /// 1. 계속 지다가 결국 탈출하기
        int tx = x, cnt1 = 0;
        int tz = z;
        for(int d=f; d>=0; d--){
            int tmp = idx[f][d];
            if(tz + sum[tmp][tx] < (1<<(f+1))){
                tz += sum[tmp][tx];
                tx = nxt[tmp][tx];
                cnt1 += (1<<d);
            }
        }

        /// 2. 이겨서 탈출하기
        int cnt2 = 0;
        tx = x;
        tz = z;
        for(int d=f; d>=0; d--){
            int tmp = idx[f][d];
            if(lim[tmp][tx] >= tz){
                tz += sum[tmp][tx];
                tx = nxt[tmp][tx];
                cnt2 += (1<<d);
            }
        }

        int cnt = min(cnt1, cnt2);
        for(int d=0; d<LIM; d++){
            if((cnt>>d)&1){
                int tmp = idx[f][d];
                z += sum[tmp][x];
                x = nxt[tmp][x];
            }
        }

        if(x==n) break;

        assert(z < (1<<(f+1)));
        if(z >= arr[x]) z += arr[x], x = w[x];
        else z += power[x], x = l[x];
        assert(z >= (1<<(f+1)));
    }

    return ll(z) + bonus[x];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7124 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 10 ms 14916 KB Output is correct
4 Correct 148 ms 200268 KB Output is correct
5 Correct 10 ms 14932 KB Output is correct
6 Correct 155 ms 200360 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 1301 ms 1549428 KB Output is correct
3 Correct 1332 ms 1549516 KB Output is correct
4 Correct 1659 ms 1549480 KB Output is correct
5 Correct 1249 ms 1549524 KB Output is correct
6 Correct 3493 ms 1549516 KB Output is correct
7 Correct 3136 ms 1549460 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 280 ms 201052 KB Output is correct
3 Correct 293 ms 201176 KB Output is correct
4 Correct 275 ms 201112 KB Output is correct
5 Correct 243 ms 201048 KB Output is correct
6 Correct 1107 ms 201160 KB Output is correct
7 Correct 1508 ms 201156 KB Output is correct
8 Correct 917 ms 201040 KB Output is correct
9 Correct 192 ms 201152 KB Output is correct
10 Correct 776 ms 201036 KB Output is correct
11 Correct 1208 ms 201156 KB Output is correct
12 Correct 3592 ms 201124 KB Output is correct
13 Correct 3593 ms 201036 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 280 ms 201052 KB Output is correct
3 Correct 293 ms 201176 KB Output is correct
4 Correct 275 ms 201112 KB Output is correct
5 Correct 243 ms 201048 KB Output is correct
6 Correct 1107 ms 201160 KB Output is correct
7 Correct 1508 ms 201156 KB Output is correct
8 Correct 917 ms 201040 KB Output is correct
9 Correct 192 ms 201152 KB Output is correct
10 Correct 776 ms 201036 KB Output is correct
11 Correct 1208 ms 201156 KB Output is correct
12 Correct 3592 ms 201124 KB Output is correct
13 Correct 3593 ms 201036 KB Output is correct
14 Correct 7 ms 11092 KB Output is correct
15 Correct 235 ms 201052 KB Output is correct
16 Correct 295 ms 201048 KB Output is correct
17 Correct 438 ms 201036 KB Output is correct
18 Correct 434 ms 201036 KB Output is correct
19 Correct 1040 ms 201112 KB Output is correct
20 Correct 911 ms 201068 KB Output is correct
21 Correct 1102 ms 201152 KB Output is correct
22 Correct 842 ms 201236 KB Output is correct
23 Correct 1443 ms 201120 KB Output is correct
24 Correct 1808 ms 201116 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 280 ms 201052 KB Output is correct
3 Correct 293 ms 201176 KB Output is correct
4 Correct 275 ms 201112 KB Output is correct
5 Correct 243 ms 201048 KB Output is correct
6 Correct 1107 ms 201160 KB Output is correct
7 Correct 1508 ms 201156 KB Output is correct
8 Correct 917 ms 201040 KB Output is correct
9 Correct 192 ms 201152 KB Output is correct
10 Correct 776 ms 201036 KB Output is correct
11 Correct 1208 ms 201156 KB Output is correct
12 Correct 3592 ms 201124 KB Output is correct
13 Correct 3593 ms 201036 KB Output is correct
14 Correct 7 ms 11092 KB Output is correct
15 Correct 235 ms 201052 KB Output is correct
16 Correct 295 ms 201048 KB Output is correct
17 Correct 438 ms 201036 KB Output is correct
18 Correct 434 ms 201036 KB Output is correct
19 Correct 1040 ms 201112 KB Output is correct
20 Correct 911 ms 201068 KB Output is correct
21 Correct 1102 ms 201152 KB Output is correct
22 Correct 842 ms 201236 KB Output is correct
23 Correct 1443 ms 201120 KB Output is correct
24 Correct 1808 ms 201116 KB Output is correct
25 Correct 142 ms 200292 KB Output is correct
26 Correct 299 ms 201088 KB Output is correct
27 Correct 220 ms 201100 KB Output is correct
28 Correct 208 ms 201152 KB Output is correct
29 Correct 341 ms 201084 KB Output is correct
30 Correct 834 ms 201236 KB Output is correct
31 Correct 1152 ms 201108 KB Output is correct
32 Correct 1407 ms 201140 KB Output is correct
33 Correct 1507 ms 201056 KB Output is correct
34 Correct 2387 ms 201048 KB Output is correct
35 Correct 1453 ms 201052 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 1301 ms 1549428 KB Output is correct
3 Correct 1332 ms 1549516 KB Output is correct
4 Correct 1659 ms 1549480 KB Output is correct
5 Correct 1249 ms 1549524 KB Output is correct
6 Correct 3493 ms 1549516 KB Output is correct
7 Correct 3136 ms 1549460 KB Output is correct
8 Correct 7 ms 11092 KB Output is correct
9 Correct 280 ms 201052 KB Output is correct
10 Correct 293 ms 201176 KB Output is correct
11 Correct 275 ms 201112 KB Output is correct
12 Correct 243 ms 201048 KB Output is correct
13 Correct 1107 ms 201160 KB Output is correct
14 Correct 1508 ms 201156 KB Output is correct
15 Correct 917 ms 201040 KB Output is correct
16 Correct 192 ms 201152 KB Output is correct
17 Correct 776 ms 201036 KB Output is correct
18 Correct 1208 ms 201156 KB Output is correct
19 Correct 3592 ms 201124 KB Output is correct
20 Correct 3593 ms 201036 KB Output is correct
21 Correct 7 ms 11092 KB Output is correct
22 Correct 235 ms 201052 KB Output is correct
23 Correct 295 ms 201048 KB Output is correct
24 Correct 438 ms 201036 KB Output is correct
25 Correct 434 ms 201036 KB Output is correct
26 Correct 1040 ms 201112 KB Output is correct
27 Correct 911 ms 201068 KB Output is correct
28 Correct 1102 ms 201152 KB Output is correct
29 Correct 842 ms 201236 KB Output is correct
30 Correct 1443 ms 201120 KB Output is correct
31 Correct 1808 ms 201116 KB Output is correct
32 Correct 142 ms 200292 KB Output is correct
33 Correct 299 ms 201088 KB Output is correct
34 Correct 220 ms 201100 KB Output is correct
35 Correct 208 ms 201152 KB Output is correct
36 Correct 341 ms 201084 KB Output is correct
37 Correct 834 ms 201236 KB Output is correct
38 Correct 1152 ms 201108 KB Output is correct
39 Correct 1407 ms 201140 KB Output is correct
40 Correct 1507 ms 201056 KB Output is correct
41 Correct 2387 ms 201048 KB Output is correct
42 Correct 1453 ms 201052 KB Output is correct
43 Correct 3 ms 7124 KB Output is correct
44 Correct 6 ms 11092 KB Output is correct
45 Correct 1514 ms 1549380 KB Output is correct
46 Correct 1223 ms 1549496 KB Output is correct
47 Correct 1128 ms 1549464 KB Output is correct
48 Correct 1273 ms 1549388 KB Output is correct
49 Correct 1563 ms 1549516 KB Output is correct
50 Correct 2147 ms 1549592 KB Output is correct
51 Correct 1403 ms 1549388 KB Output is correct
52 Correct 2406 ms 1549384 KB Output is correct
53 Correct 3067 ms 1549584 KB Output is correct
54 Correct 2786 ms 1549504 KB Output is correct
55 Correct 3692 ms 1549364 KB Output is correct
56 Correct 3588 ms 1549476 KB Output is correct
57 Correct 3486 ms 1549392 KB Output is correct
58 Correct 3353 ms 1549624 KB Output is correct
59 Correct 3291 ms 1549496 KB Output is correct
60 Correct 2609 ms 1549488 KB Output is correct
61 Correct 2537 ms 1549344 KB Output is correct