oj.uz

Submission #714966

# Submission time Handle Problem Language Result Execution time Memory
714966 2023-03-25T15:36:10 Z Charizard2021 Toll (BOI17_toll) C++17
100 / 100
 246 ms 85632 KB 
#include <bits/stdc++.h>
using namespace std;
int k, n, m, o;
int dp[50000][17][5][5], ans[5][5], tmp[5][5];
int main() {
	cin >> k >> n >> m >> o;
    for(int i = 0; i < 50000; i++){
        for(int j = 0; j < 17; j++){
            for(int k1 = 0; k1 < 5; k1++){
                for(int l = 0; l < 5; l++){
                    dp[i][j][k1][l] = 1000000000;
                }
            }
        }
    }
	while (m--) {
		int a, b, t;
		cin >> a >> b >> t;
		dp[a / k][0][a % k][b % k] = t;
	}
	for (int j = 1; j < 17; j++) {
		for (int i = 0; i + (1 << j) < (n + k - 1) / k; i++) {
            for (int x = 0; x < k; x++) {
                for (int y = 0; y < k; y++) {
                    for (int z = 0; z < k; z++) {
                        dp[i][j][x][y] = min(dp[i][j][x][y], dp[i][j - 1][x][z] + dp[i + (1 << j - 1)][j - 1][z][y]);
                    }
                }
            }
		}
	}
	while (o--) {
		int a, b;
		cin >> a >> b;
        for(int k1 = 0; k1 < 5; k1++){
            for(int l = 0; l < 5; l++){
                ans[k1][l] = 1000000000;
            }
        }
		for (int i = 0; i < 5; i++){
            ans[i][i] = 0;
        }
		for (int curr = a / k, dest = b / k, i = 16; ~i; i--) {
			if (curr + (1 << i) <= dest) {
				for(int k1 = 0; k1 < 5; k1++){
                    for(int l = 0; l < 5; l++){
                        tmp[k1][l] = 1000000000;
                    }
                }
                for (int x = 0; x < k; x++) {
                    for (int y = 0; y < k; y++) {
                        for (int z = 0; z < k; z++) {
                            tmp[x][y] = min(tmp[x][y], ans[x][z] + dp[curr][i][z][y]);
                        }
                    }
                }
				memcpy(ans, tmp, sizeof ans);
				curr += (1 << i);
			}
		}
		cout << (ans[a % k][b % k] == 1000000000 ? -1 : ans[a % k][b % k]) << '\n';
	}
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:26:98: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 |                         dp[i][j][x][y] = min(dp[i][j][x][y], dp[i][j - 1][x][z] + dp[i + (1 << j - 1)][j - 1][z][y]);
      |                                                                                                ~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 84460 KB Output is correct
2 Correct 42 ms 83396 KB Output is correct
3 Correct 38 ms 83428 KB Output is correct
4 Correct 38 ms 83420 KB Output is correct
5 Correct 46 ms 83452 KB Output is correct
6 Correct 41 ms 83368 KB Output is correct
7 Correct 43 ms 83376 KB Output is correct
8 Correct 122 ms 84504 KB Output is correct
9 Correct 118 ms 84344 KB Output is correct
10 Correct 81 ms 83576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 85096 KB Output is correct
2 Correct 40 ms 83344 KB Output is correct
3 Correct 43 ms 83440 KB Output is correct
4 Correct 41 ms 83440 KB Output is correct
5 Correct 47 ms 83332 KB Output is correct
6 Correct 41 ms 83436 KB Output is correct
7 Correct 68 ms 83512 KB Output is correct
8 Correct 63 ms 83536 KB Output is correct
9 Correct 117 ms 84348 KB Output is correct
10 Correct 197 ms 85452 KB Output is correct
11 Correct 166 ms 85220 KB Output is correct
12 Correct 157 ms 84712 KB Output is correct
13 Correct 178 ms 85456 KB Output is correct
14 Correct 129 ms 84864 KB Output is correct
15 Correct 111 ms 84628 KB Output is correct
16 Correct 111 ms 84668 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 83400 KB Output is correct
2 Correct 42 ms 83388 KB Output is correct
3 Correct 44 ms 83452 KB Output is correct
4 Correct 39 ms 83404 KB Output is correct
5 Correct 38 ms 83340 KB Output is correct
6 Correct 39 ms 83388 KB Output is correct
7 Correct 43 ms 83432 KB Output is correct
8 Correct 45 ms 83508 KB Output is correct
9 Correct 43 ms 83476 KB Output is correct
10 Correct 92 ms 84200 KB Output is correct
11 Correct 136 ms 84968 KB Output is correct
12 Correct 184 ms 85448 KB Output is correct
13 Correct 191 ms 85352 KB Output is correct
14 Correct 148 ms 85196 KB Output is correct
15 Correct 132 ms 84584 KB Output is correct
16 Correct 119 ms 84532 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 83400 KB Output is correct
2 Correct 42 ms 83388 KB Output is correct
3 Correct 44 ms 83452 KB Output is correct
4 Correct 39 ms 83404 KB Output is correct
5 Correct 38 ms 83340 KB Output is correct
6 Correct 39 ms 83388 KB Output is correct
7 Correct 43 ms 83432 KB Output is correct
8 Correct 45 ms 83508 KB Output is correct
9 Correct 43 ms 83476 KB Output is correct
10 Correct 92 ms 84200 KB Output is correct
11 Correct 136 ms 84968 KB Output is correct
12 Correct 184 ms 85448 KB Output is correct
13 Correct 191 ms 85352 KB Output is correct
14 Correct 148 ms 85196 KB Output is correct
15 Correct 132 ms 84584 KB Output is correct
16 Correct 119 ms 84532 KB Output is correct
17 Correct 142 ms 85068 KB Output is correct
18 Correct 39 ms 83440 KB Output is correct
19 Correct 40 ms 83384 KB Output is correct
20 Correct 40 ms 83348 KB Output is correct
21 Correct 37 ms 83412 KB Output is correct
22 Correct 39 ms 83332 KB Output is correct
23 Correct 46 ms 83484 KB Output is correct
24 Correct 46 ms 83496 KB Output is correct
25 Correct 46 ms 83428 KB Output is correct
26 Correct 63 ms 83476 KB Output is correct
27 Correct 113 ms 84328 KB Output is correct
28 Correct 182 ms 85580 KB Output is correct
29 Correct 190 ms 85612 KB Output is correct
30 Correct 156 ms 85220 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 84460 KB Output is correct
2 Correct 42 ms 83396 KB Output is correct
3 Correct 38 ms 83428 KB Output is correct
4 Correct 38 ms 83420 KB Output is correct
5 Correct 46 ms 83452 KB Output is correct
6 Correct 41 ms 83368 KB Output is correct
7 Correct 43 ms 83376 KB Output is correct
8 Correct 122 ms 84504 KB Output is correct
9 Correct 118 ms 84344 KB Output is correct
10 Correct 81 ms 83576 KB Output is correct
11 Correct 166 ms 85096 KB Output is correct
12 Correct 40 ms 83344 KB Output is correct
13 Correct 43 ms 83440 KB Output is correct
14 Correct 41 ms 83440 KB Output is correct
15 Correct 47 ms 83332 KB Output is correct
16 Correct 41 ms 83436 KB Output is correct
17 Correct 68 ms 83512 KB Output is correct
18 Correct 63 ms 83536 KB Output is correct
19 Correct 117 ms 84348 KB Output is correct
20 Correct 197 ms 85452 KB Output is correct
21 Correct 166 ms 85220 KB Output is correct
22 Correct 157 ms 84712 KB Output is correct
23 Correct 178 ms 85456 KB Output is correct
24 Correct 129 ms 84864 KB Output is correct
25 Correct 111 ms 84628 KB Output is correct
26 Correct 111 ms 84668 KB Output is correct
27 Correct 43 ms 83400 KB Output is correct
28 Correct 42 ms 83388 KB Output is correct
29 Correct 44 ms 83452 KB Output is correct
30 Correct 39 ms 83404 KB Output is correct
31 Correct 38 ms 83340 KB Output is correct
32 Correct 39 ms 83388 KB Output is correct
33 Correct 43 ms 83432 KB Output is correct
34 Correct 45 ms 83508 KB Output is correct
35 Correct 43 ms 83476 KB Output is correct
36 Correct 92 ms 84200 KB Output is correct
37 Correct 136 ms 84968 KB Output is correct
38 Correct 184 ms 85448 KB Output is correct
39 Correct 191 ms 85352 KB Output is correct
40 Correct 148 ms 85196 KB Output is correct
41 Correct 132 ms 84584 KB Output is correct
42 Correct 119 ms 84532 KB Output is correct
43 Correct 142 ms 85068 KB Output is correct
44 Correct 39 ms 83440 KB Output is correct
45 Correct 40 ms 83384 KB Output is correct
46 Correct 40 ms 83348 KB Output is correct
47 Correct 37 ms 83412 KB Output is correct
48 Correct 39 ms 83332 KB Output is correct
49 Correct 46 ms 83484 KB Output is correct
50 Correct 46 ms 83496 KB Output is correct
51 Correct 46 ms 83428 KB Output is correct
52 Correct 63 ms 83476 KB Output is correct
53 Correct 113 ms 84328 KB Output is correct
54 Correct 182 ms 85580 KB Output is correct
55 Correct 190 ms 85612 KB Output is correct
56 Correct 156 ms 85220 KB Output is correct
57 Correct 246 ms 85632 KB Output is correct
58 Correct 131 ms 84460 KB Output is correct
59 Correct 178 ms 85228 KB Output is correct