QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #690538 | #6242. 道路 | propane | 100 ✓ | 108ms | 288216kb | C++20 | 1.0kb | 2024-10-30 22:59:00 | 2024-10-30 22:59:05 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int maxn = 4e4 + 5;
int g[maxn][2];
int a[maxn], b[maxn], c[maxn];
LL f[maxn][41][41];
int n;
LL dp(int u, int x, int y){
if (f[u][x][y] != 0) return f[u][x][y];
if (u >= n){
return f[u][x][y] = 1LL * c[u] * (a[u] + x) * (b[u] + y);
}
return f[u][x][y] = min(dp(g[u][0], x, y) + dp(g[u][1], x, y + 1), dp(g[u][0], x + 1, y) + dp(g[u][1], x, y));
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
auto get = [&](int x){
return x > 0 ? x : -x + n - 1;
};
for(int i = 1; i <= n - 1; i++){
int a, b;
cin >> a >> b;
g[i][0] = get(a);
g[i][1] = get(b);
}
for(int i = n; i <= 2 * n - 1; i++){
cin >> a[i] >> b[i] >> c[i];
}
cout << dp(1, 0, 0) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 5816kb
input:
7 2 3 -7 4 5 -5 -3 -6 6 -2 -4 -1 2 1 1 3 1 2 1 2 3 1 2 2 3 2 3 2 2 3 2 3 2
output:
106
result:
ok 1 number(s): "106"
Test #2:
score: 5
Accepted
time: 1ms
memory: 3692kb
input:
12 2 3 5 4 6 9 -7 -1 -6 8 11 7 -12 -11 -3 10 -10 -8 -4 -9 -5 -2 16 8 282716555 43 8 676470132 5 25 448936174 24 19 294834513 3 11 283245161 34 33 44141195 50 31 553681258 15 40 51344897 12 39 626117706 31 14 98501949 40 18 176189362 49 1 919532877
output:
2050442770084
result:
ok 1 number(s): "2050442770084"
Test #3:
score: 5
Accepted
time: 1ms
memory: 3812kb
input:
16 2 5 4 3 -4 12 7 6 15 8 -8 -10 9 10 -1 13 14 -7 11 -5 -13 -9 -16 -15 -2 -14 -12 -11 -3 -6 38 22 17199016 38 39 359928508 2 12 166770799 4 43 64609818 42 45 76568848 17 7 611955507 45 32 445177244 38 2 35878276 35 2 691352194 42 11 415149201 15 28 797085373 5 37 720439162 17 35 146856251 9 5 924604...
output:
2542556841254
result:
ok 1 number(s): "2542556841254"
Test #4:
score: 5
Accepted
time: 1ms
memory: 5884kb
input:
20 2 4 3 7 6 5 12 -1 15 -7 10 16 8 9 -4 -3 -17 -20 13 11 -16 -19 -5 -2 -18 14 -12 17 -6 -10 -9 -13 18 19 -8 -15 -11 -14 7 48 222987844 41 50 972656837 11 8 666511315 9 37 115037505 19 32 514563881 37 2 906892887 19 33 783934648 50 49 867528509 30 11 370412902 25 19 151687934 22 12 285594940 24 50 69...
output:
11060274345296
result:
ok 1 number(s): "11060274345296"
Test #5:
score: 5
Accepted
time: 1ms
memory: 3936kb
input:
35 2 6 5 3 -4 4 -6 7 -2 -14 15 24 9 8 10 -15 12 11 26 13 18 19 20 14 -33 -29 16 17 -18 -31 23 21 -25 -17 32 -1 -10 22 -30 -32 -19 31 -26 -21 27 25 -22 -9 -7 29 30 28 -11 -8 -23 -28 -13 -12 -27 -20 -24 -16 34 33 -35 -34 -3 -5 2 1 5 4 4 1 1 5 4 3 1 4 1 1 4 3 3 3 5 3 1 2 5 3 2 2 3 4 3 4 1 4 2 4 5 5 5 5...
output:
1367
result:
ok 1 number(s): "1367"
Test #6:
score: 5
Accepted
time: 1ms
memory: 4000kb
input:
40 3 2 9 4 19 5 10 18 7 6 14 21 8 12 29 24 30 -7 11 13 -33 -34 -2 -6 20 15 16 17 -21 -37 -38 -36 -23 -16 25 23 26 -10 -8 -25 -26 22 32 36 34 27 33 -24 -40 -39 -30 -27 -5 28 -18 -4 -1 31 -35 38 39 -9 35 -14 -3 -11 -22 -17 37 -32 -29 -19 -13 -20 -12 -31 -28 -15 4 2 4 2 5 2 4 4 1 1 3 5 1 1 2 2 3 1 2 3 ...
output:
1672
result:
ok 1 number(s): "1672"
Test #7:
score: 5
Accepted
time: 0ms
memory: 6108kb
input:
45 2 3 4 5 -19 15 6 12 7 8 18 23 30 21 11 9 10 33 14 43 36 13 19 22 25 20 16 37 17 -2 -43 -41 41 -5 28 27 29 40 26 32 -40 -36 24 31 -37 34 -17 38 -18 -24 -1 -28 35 44 39 -27 -44 -45 -4 -39 -16 -29 -11 -13 -33 -32 -8 -7 -3 -14 -23 -22 -34 -30 -21 -12 42 -42 -35 -31 -6 -26 -38 -20 -10 -25 -15 -9 5 4 3...
output:
2178
result:
ok 1 number(s): "2178"
Test #8:
score: 5
Accepted
time: 0ms
memory: 4156kb
input:
50 5 2 3 4 21 8 14 9 6 7 20 29 19 11 16 33 18 10 39 13 -10 12 -48 41 25 43 26 15 22 17 -29 -40 -36 45 -43 -38 23 -45 35 -17 31 28 -8 24 -41 -50 27 -9 -23 38 32 40 34 42 47 -2 30 46 -25 -4 -33 -15 -6 37 -22 -28 44 -35 36 -44 -12 -13 48 -31 -46 -21 -32 -37 49 -3 -5 -16 -20 -11 -49 -1 -30 -18 -39 -14 -...
output:
3006
result:
ok 1 number(s): "3006"
Test #9:
score: 5
Accepted
time: 0ms
memory: 9348kb
input:
500 2 6 14 3 4 5 8 148 7 13 26 39 10 27 11 9 12 17 15 18 47 20 36 25 16 24 19 70 28 23 72 45 32 73 51 43 30 46 22 21 394 215 29 40 133 42 33 35 41 63 31 76 37 49 105 61 155 115 130 117 50 38 106 101 34 53 65 52 495 59 67 123 54 48 100 84 57 44 113 92 95 55 78 60 56 151 257 297 129 87 62 86 93 89 310...
output:
175236166030235
result:
ok 1 number(s): "175236166030235"
Test #10:
score: 5
Accepted
time: 0ms
memory: 15420kb
input:
1000 3 2 16 4 6 5 19 63 22 8 9 7 10 12 56 34 29 166 11 13 20 39 14 15 27 21 28 17 70 73 30 18 31 36 23 25 69 67 24 52 59 134 45 84 140 26 32 77 68 90 44 35 38 932 37 61 102 113 91 33 40 76 42 169 86 49 162 83 41 135 48 71 122 197 47 43 410 66 115 249 116 104 106 46 72 174 316 79 53 50 -246 715 60 62...
output:
360352096428906
result:
ok 1 number(s): "360352096428906"
Test #11:
score: 5
Accepted
time: 4ms
memory: 23680kb
input:
1500 23 2 6 3 4 7 21 5 8 10 12 13 33 93 11 9 15 22 105 14 20 27 19 58 43 16 18 56 28 17 24 26 54 155 25 32 29 47 36 99 67 90 69 39 40 51 924 1025 37 50 31 30 253 46 35 72 75 61 83 41 34 209 173 156 44 64 38 48 53 77 42 60 147 70 63 355 52 104 164 81 45 121 49 59 382 212 82 62 68 87 78 91 109 324 323...
output:
536614110838462
result:
ok 1 number(s): "536614110838462"
Test #12:
score: 5
Accepted
time: 8ms
memory: 30368kb
input:
2000 2 3 5 4 6 12 8 39 42 7 44 23 9 11 18 17 25 10 26 13 24 20 41 105 48 14 16 15 19 21 36 128 27 77 33 113 28 34 38 47 22 46 125 203 64 63 29 54 30 147 32 43 74 58 45 49 65 109 31 37 202 279 156 283 197 35 50 69 66 98 93 85 68 153 55 82 40 53 70 60 87 160 101 51 71 106 89 52 76 413 73 229 453 310 5...
output:
696660470751572
result:
ok 1 number(s): "696660470751572"
Test #13:
score: 5
Accepted
time: 24ms
memory: 137044kb
input:
10000 2 3 5 4 6 7 26 27 136 188 29 8 12 24 9 11 10 34 20 16 13 18 15 14 115 167 17 59 19 22 25 89 53 30 79 31 23 38 37 21 46 57 262 39 49 33 42 119 107 47 36 28 273 35 245 74 145 238 32 126 184 162 45 44 65 114 40 43 68 41 64 129 333 108 86 83 51 60 52 61 102 113 443 250 158 90 55 77 125 62 56 72 48...
output:
3704167089913010
result:
ok 1 number(s): "3704167089913010"
Test #14:
score: 5
Accepted
time: 39ms
memory: 159436kb
input:
12000 6 2 7 3 4 5 253 47 10 8 9 11 39 13 12 14 15 19 21 16 26 17 30 31 20 27 38 54 18 25 36 29 266 97 418 23 28 32 61 22 40 24 37 49 34 52 828 186 68 50 67 74 84 71 1203 442 43 51 33 48 57 42 53 44 45 1015 124 35 56 138 388 111 160 87 122 107 96 59 190 41 66 141 79 209 100 210 72 46 193 211 89 95 31...
output:
4372335253688518
result:
ok 1 number(s): "4372335253688518"
Test #15:
score: 5
Accepted
time: 48ms
memory: 187920kb
input:
14000 4 2 7 3 6 66 15 5 11 8 29 17 12 10 23 9 80 18 14 13 179 548 26 16 28 22 32 27 19 20 61 21 35 24 92 70 3329 1950 153 95 104 39 38 48 25 926 54 49 37 58 34 44 33 67 30 31 81 60 73 146 41 36 64 174 1706 126 55 40 52 43 85 115 42 45 155 116 105 171 57 59 46 53 237 675 89 65 114 50 62 79 47 94 83 1...
output:
5083034878302913
result:
ok 1 number(s): "5083034878302913"
Test #16:
score: 5
Accepted
time: 77ms
memory: 215344kb
input:
16000 3 2 21 4 10 25 7 5 6 8 18 64 11 22 9 15 58 86 17 26 12 16 13 40 23 14 99 20 27 59 51 31 70 43 19 24 42 63 56 44 293 343 351 36 72 35 65 30 28 38 128 171 29 33 45 32 392 119 53 34 93 41 39 74 37 47 67 62 149 2471 52 80 60 48 49 66 157 115 73 50 76 147 94 81 46 85 87 117 57 110 55 90 196 61 75 7...
output:
5887937461322102
result:
ok 1 number(s): "5887937461322102"
Test #17:
score: 5
Accepted
time: 91ms
memory: 239452kb
input:
17000 2 23 3 6 4 5 7 9 12 19 8 11 17 134 29 15 26 10 28 14 72 40 18 13 20 21 27 16 76 90 30 25 42 92 56 37 22 46 66 162 24 165 43 41 145 55 205 1367 31 33 68 54 39 213 299 45 47 35 183 32 151 86 49 36 34 61 62 84 53 52 88 103 38 71 559 305 123 243 44 58 48 190 164 141 331 115 195 117 229 155 59 50 6...
output:
6252981250656105
result:
ok 1 number(s): "6252981250656105"
Test #18:
score: 5
Accepted
time: 59ms
memory: 237180kb
input:
18000 2 3 18 13 5 4 6 21 8 9 7 11 12 17 28 48 19 10 54 24 14 15 39 25 20 23 40 29 16 31 45 42 55 58 26 53 22 34 35 64 33 27 86 155 61 30 104 133 49 46 52 43 38 41 60 93 50 32 141 80 37 36 135 168 47 107 102 44 88 100 84 126 192 110 66 56 120 428 139 94 63 136 99 347 73 232 68 89 147 65 338 451 78 51...
output:
6586141694831507
result:
ok 1 number(s): "6586141694831507"
Test #19:
score: 5
Accepted
time: 84ms
memory: 261256kb
input:
19000 4 2 3 34 7 5 10 6 8 12 23 27 35 9 37 49 14 16 11 21 77 64 13 20 47 26 127 15 19 18 17 115 96 41 22 54 68 89 33 30 24 32 38 31 73 39 28 25 40 65 29 45 46 61 151 104 124 111 36 92 55 166 145 374 98 167 90 43 44 261 188 109 3858 193 637 93 81 42 63 48 126 57 67 82 50 53 71 226 182 84 72 66 156 56...
output:
6929877042896973
result:
ok 1 number(s): "6929877042896973"
Test #20:
score: 5
Accepted
time: 108ms
memory: 288216kb
input:
20000 2 9 3 7 4 126 5 15 6 8 20 18 14 10 12 50 16 21 11 24 25 35 19 13 17 28 247 67 44 34 48 27 53 26 205 199 29 30 32 40 60 22 52 23 47 31 39 49 76 37 33 70 75 55 82 59 330 66 394 112 38 73 652 1255 41 36 51 42 310 509 61 43 57 118 396 63 127 54 425 635 177 153 80 144 92 77 45 72 58 46 71 79 234 10...
output:
7249256499186593
result:
ok 1 number(s): "7249256499186593"