# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
206067 | 2020-03-02T05:47:32 Z | DodgeBallMan | Toll (BOI17_toll) | C++14 | 264 ms | 123512 KB |
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; const int N = 5e4+10; const int K = 6; int k, n, m, o, dp[N][K][17][K], all; int main() { for( int i = 0 ; i < N ; i++ ) for( int j = 0 ; j < K ; j++ ) for( int x = 0 ; x < 17 ; x++ ) for( int y = 0 ; y < K ; y++ ) dp[i][j][x][y] = INF; scanf("%d %d %d %d",&k,&n,&m,&o); for( int i = 1 ; i <= m ; i++ ) { int a, b, c; scanf("%d %d %d",&a,&b,&c); dp[a/k][a%k][0][b%k] = c; } all = n / k; for( int z = 1 ; z < 16 ; z++ ) for( int i = 0 ; i < all ; i++ ) for( int x = 0 ; x < k ; x++ ) for( int y = 0 ; y < k ; y++ ) for( int j = 0 ; j < k ; j++ ) { if( i + (1<<(z-1)) <= all ) dp[i][x][z][y] = min( dp[i][x][z][y], dp[i][x][z-1][j] + dp[i+(1<<(z-1))][j][z-1][y] ); //if( !i ) printf("%d ", dp[i][x][z][y] ); } for( int i = 0 ; i < o ; i++ ) { int a, b; scanf("%d %d",&a,&b); if( a/k >= b/k ) { printf("-1\n"); continue ; } int f = a%k, t = b%k; int ret[K]; for( int j = 0 ; j < k ; j++ ) ret[j] = dp[a/k][f][0][j]; a = a/k+1, b = b/k; for( int j = 15 ; j >= 0 ; j-- ) if( a + ( 1 << j ) <= b ) { int nret[K]; for( int x = 0 ; x < K ; x++ ) nret[x] = INF; for( int x = 0 ; x < k ; x++ ) for( int y = 0 ; y < k ; y++ ) nret[y] = min( nret[y], ret[x] + dp[a][x][j][y] ); a += ( 1 << j ); for( int z = 0 ; z < k ; z++ ) ret[z] = nret[z]; } printf("%d\n",ret[t] == INF ? -1 : ret[t]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 125 ms | 121080 KB | Output is correct |
2 | Correct | 76 ms | 120184 KB | Output is correct |
3 | Correct | 71 ms | 120188 KB | Output is correct |
4 | Correct | 69 ms | 120056 KB | Output is correct |
5 | Correct | 71 ms | 120176 KB | Output is correct |
6 | Correct | 71 ms | 120056 KB | Output is correct |
7 | Correct | 78 ms | 120184 KB | Output is correct |
8 | Correct | 119 ms | 121080 KB | Output is correct |
9 | Correct | 120 ms | 120952 KB | Output is correct |
10 | Correct | 106 ms | 120312 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 173 ms | 121752 KB | Output is correct |
2 | Correct | 73 ms | 120056 KB | Output is correct |
3 | Correct | 84 ms | 120056 KB | Output is correct |
4 | Correct | 69 ms | 120056 KB | Output is correct |
5 | Correct | 70 ms | 120056 KB | Output is correct |
6 | Correct | 70 ms | 120056 KB | Output is correct |
7 | Correct | 73 ms | 120184 KB | Output is correct |
8 | Correct | 75 ms | 120184 KB | Output is correct |
9 | Correct | 120 ms | 121080 KB | Output is correct |
10 | Correct | 187 ms | 122488 KB | Output is correct |
11 | Correct | 157 ms | 121848 KB | Output is correct |
12 | Correct | 164 ms | 121464 KB | Output is correct |
13 | Correct | 179 ms | 122488 KB | Output is correct |
14 | Correct | 138 ms | 121592 KB | Output is correct |
15 | Correct | 143 ms | 121408 KB | Output is correct |
16 | Correct | 150 ms | 121336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 72 ms | 120184 KB | Output is correct |
2 | Correct | 74 ms | 120060 KB | Output is correct |
3 | Correct | 73 ms | 120184 KB | Output is correct |
4 | Correct | 70 ms | 120056 KB | Output is correct |
5 | Correct | 69 ms | 120056 KB | Output is correct |
6 | Correct | 72 ms | 120056 KB | Output is correct |
7 | Correct | 70 ms | 120068 KB | Output is correct |
8 | Correct | 72 ms | 120312 KB | Output is correct |
9 | Correct | 74 ms | 120184 KB | Output is correct |
10 | Correct | 115 ms | 120952 KB | Output is correct |
11 | Correct | 165 ms | 121720 KB | Output is correct |
12 | Correct | 200 ms | 122360 KB | Output is correct |
13 | Correct | 200 ms | 122592 KB | Output is correct |
14 | Correct | 179 ms | 121848 KB | Output is correct |
15 | Correct | 160 ms | 121464 KB | Output is correct |
16 | Correct | 150 ms | 121208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 72 ms | 120184 KB | Output is correct |
2 | Correct | 74 ms | 120060 KB | Output is correct |
3 | Correct | 73 ms | 120184 KB | Output is correct |
4 | Correct | 70 ms | 120056 KB | Output is correct |
5 | Correct | 69 ms | 120056 KB | Output is correct |
6 | Correct | 72 ms | 120056 KB | Output is correct |
7 | Correct | 70 ms | 120068 KB | Output is correct |
8 | Correct | 72 ms | 120312 KB | Output is correct |
9 | Correct | 74 ms | 120184 KB | Output is correct |
10 | Correct | 115 ms | 120952 KB | Output is correct |
11 | Correct | 165 ms | 121720 KB | Output is correct |
12 | Correct | 200 ms | 122360 KB | Output is correct |
13 | Correct | 200 ms | 122592 KB | Output is correct |
14 | Correct | 179 ms | 121848 KB | Output is correct |
15 | Correct | 160 ms | 121464 KB | Output is correct |
16 | Correct | 150 ms | 121208 KB | Output is correct |
17 | Correct | 160 ms | 121848 KB | Output is correct |
18 | Correct | 84 ms | 120144 KB | Output is correct |
19 | Correct | 78 ms | 120056 KB | Output is correct |
20 | Correct | 75 ms | 120056 KB | Output is correct |
21 | Correct | 81 ms | 120080 KB | Output is correct |
22 | Correct | 76 ms | 120184 KB | Output is correct |
23 | Correct | 75 ms | 120184 KB | Output is correct |
24 | Correct | 73 ms | 120184 KB | Output is correct |
25 | Correct | 77 ms | 120184 KB | Output is correct |
26 | Correct | 79 ms | 120188 KB | Output is correct |
27 | Correct | 118 ms | 120952 KB | Output is correct |
28 | Correct | 196 ms | 122488 KB | Output is correct |
29 | Correct | 210 ms | 122744 KB | Output is correct |
30 | Correct | 186 ms | 121976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 125 ms | 121080 KB | Output is correct |
2 | Correct | 76 ms | 120184 KB | Output is correct |
3 | Correct | 71 ms | 120188 KB | Output is correct |
4 | Correct | 69 ms | 120056 KB | Output is correct |
5 | Correct | 71 ms | 120176 KB | Output is correct |
6 | Correct | 71 ms | 120056 KB | Output is correct |
7 | Correct | 78 ms | 120184 KB | Output is correct |
8 | Correct | 119 ms | 121080 KB | Output is correct |
9 | Correct | 120 ms | 120952 KB | Output is correct |
10 | Correct | 106 ms | 120312 KB | Output is correct |
11 | Correct | 173 ms | 121752 KB | Output is correct |
12 | Correct | 73 ms | 120056 KB | Output is correct |
13 | Correct | 84 ms | 120056 KB | Output is correct |
14 | Correct | 69 ms | 120056 KB | Output is correct |
15 | Correct | 70 ms | 120056 KB | Output is correct |
16 | Correct | 70 ms | 120056 KB | Output is correct |
17 | Correct | 73 ms | 120184 KB | Output is correct |
18 | Correct | 75 ms | 120184 KB | Output is correct |
19 | Correct | 120 ms | 121080 KB | Output is correct |
20 | Correct | 187 ms | 122488 KB | Output is correct |
21 | Correct | 157 ms | 121848 KB | Output is correct |
22 | Correct | 164 ms | 121464 KB | Output is correct |
23 | Correct | 179 ms | 122488 KB | Output is correct |
24 | Correct | 138 ms | 121592 KB | Output is correct |
25 | Correct | 143 ms | 121408 KB | Output is correct |
26 | Correct | 150 ms | 121336 KB | Output is correct |
27 | Correct | 72 ms | 120184 KB | Output is correct |
28 | Correct | 74 ms | 120060 KB | Output is correct |
29 | Correct | 73 ms | 120184 KB | Output is correct |
30 | Correct | 70 ms | 120056 KB | Output is correct |
31 | Correct | 69 ms | 120056 KB | Output is correct |
32 | Correct | 72 ms | 120056 KB | Output is correct |
33 | Correct | 70 ms | 120068 KB | Output is correct |
34 | Correct | 72 ms | 120312 KB | Output is correct |
35 | Correct | 74 ms | 120184 KB | Output is correct |
36 | Correct | 115 ms | 120952 KB | Output is correct |
37 | Correct | 165 ms | 121720 KB | Output is correct |
38 | Correct | 200 ms | 122360 KB | Output is correct |
39 | Correct | 200 ms | 122592 KB | Output is correct |
40 | Correct | 179 ms | 121848 KB | Output is correct |
41 | Correct | 160 ms | 121464 KB | Output is correct |
42 | Correct | 150 ms | 121208 KB | Output is correct |
43 | Correct | 160 ms | 121848 KB | Output is correct |
44 | Correct | 84 ms | 120144 KB | Output is correct |
45 | Correct | 78 ms | 120056 KB | Output is correct |
46 | Correct | 75 ms | 120056 KB | Output is correct |
47 | Correct | 81 ms | 120080 KB | Output is correct |
48 | Correct | 76 ms | 120184 KB | Output is correct |
49 | Correct | 75 ms | 120184 KB | Output is correct |
50 | Correct | 73 ms | 120184 KB | Output is correct |
51 | Correct | 77 ms | 120184 KB | Output is correct |
52 | Correct | 79 ms | 120188 KB | Output is correct |
53 | Correct | 118 ms | 120952 KB | Output is correct |
54 | Correct | 196 ms | 122488 KB | Output is correct |
55 | Correct | 210 ms | 122744 KB | Output is correct |
56 | Correct | 186 ms | 121976 KB | Output is correct |
57 | Correct | 264 ms | 123512 KB | Output is correct |
58 | Correct | 127 ms | 121080 KB | Output is correct |
59 | Correct | 172 ms | 121976 KB | Output is correct |