Task: | Gondolas |
Sender: | #dt-lapset |
Submission time: | 2016-11-12 17:23:47 +0200 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 1.39 s | details |
#2 | ACCEPTED | 1.12 s | details |
#3 | ACCEPTED | 1.16 s | details |
#4 | ACCEPTED | 1.14 s | details |
#5 | ACCEPTED | 1.13 s | details |
#6 | ACCEPTED | 1.19 s | details |
#7 | ACCEPTED | 1.06 s | details |
#8 | ACCEPTED | 1.04 s | details |
#9 | ACCEPTED | 1.08 s | details |
#10 | ACCEPTED | 1.09 s | details |
#11 | ACCEPTED | 1.07 s | details |
#12 | ACCEPTED | 1.22 s | details |
#13 | ACCEPTED | 1.09 s | details |
#14 | ACCEPTED | 1.09 s | details |
#15 | WRONG ANSWER | 1.08 s | details |
#16 | ACCEPTED | 1.07 s | details |
#17 | ACCEPTED | 1.13 s | details |
#18 | ACCEPTED | 1.11 s | details |
#19 | ACCEPTED | 1.17 s | details |
#20 | ACCEPTED | 1.21 s | details |
#21 | ACCEPTED | 1.09 s | details |
#22 | ACCEPTED | 1.07 s | details |
#23 | ACCEPTED | 1.43 s | details |
#24 | ACCEPTED | 1.06 s | details |
#25 | ACCEPTED | 1.07 s | details |
#26 | ACCEPTED | 1.07 s | details |
#27 | ACCEPTED | 1.07 s | details |
#28 | ACCEPTED | 1.08 s | details |
#29 | ACCEPTED | 1.06 s | details |
#30 | ACCEPTED | 1.08 s | details |
#31 | ACCEPTED | 1.06 s | details |
#32 | ACCEPTED | 1.07 s | details |
#33 | ACCEPTED | 1.40 s | details |
#34 | ACCEPTED | 1.11 s | details |
#35 | ACCEPTED | 1.20 s | details |
#36 | ACCEPTED | 1.09 s | details |
#37 | ACCEPTED | 1.11 s | details |
#38 | ACCEPTED | 1.06 s | details |
#39 | ACCEPTED | 1.07 s | details |
#40 | ACCEPTED | 1.38 s | details |
#41 | ACCEPTED | 1.63 s | details |
#42 | ACCEPTED | 1.16 s | details |
#43 | ACCEPTED | 1.13 s | details |
#44 | ACCEPTED | 1.13 s | details |
Code
#include <bits/stdc++.h> #define INF 999999999999999LL #define F first #define S second #define ll long long #define ld long double using namespace std; ll dp[444][444]; int main () { int n, t, g; cin>>n>>t>>g; ll v[n]; ll ans = INF; for (int i = 0; i < n; i++) cin>>v[i]; int op = 0; while (op < 600000000) { int k = rand(); for (int i = 0; i < n; i++) v[i] = (v[i] + k) % (2 * t); sort(v, v + n); for (int y = 0; y <= g; y++) { for (int x = 1; x <= 2 * n; x++) dp[y][x] = INF, op++; } dp[0][0] = 0; for (int y = 1; y <= g; y++) { for (int x = 1; x <= n; x++) { ll t = 0; for (int z = x; z >= 1; z--) { t += v[x - 1] - v[z - 1]; dp[y][x] = min(dp[y][x], t + dp[y - 1][z - 1]); op++; } } } ans = min(ans, dp[g][n]); } cout<<ans<<endl; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
32 39 4 681306 435214 1554 470233 ... |
correct output |
---|
183 |
user output |
---|
183 |
Test 2
Verdict: ACCEPTED
input |
---|
94 205 25 154150 167683 411531 64924 ... |
correct output |
---|
328 |
user output |
---|
328 |
Test 3
Verdict: ACCEPTED
input |
---|
63 329 33 791965 121438 487872 197074 ... |
correct output |
---|
133 |
user output |
---|
133 |
Test 4
Verdict: ACCEPTED
input |
---|
70 253 28 853321 662592 538431 311761 ... |
correct output |
---|
203 |
user output |
---|
203 |
Test 5
Verdict: ACCEPTED
input |
---|
75 146 58 71431 174034 198572 717231 ... |
correct output |
---|
6 |
user output |
---|
6 |
Test 6
Verdict: ACCEPTED
input |
---|
50 210 38 508372 208598 621692 276794 ... |
correct output |
---|
11 |
user output |
---|
11 |
Test 7
Verdict: ACCEPTED
input |
---|
400 261 30 122770 252639 652115 865847 ... |
correct output |
---|
2438 |
user output |
---|
2438 |
Test 8
Verdict: ACCEPTED
input |
---|
400 309 128 415910 619728 298494 977650 ... |
correct output |
---|
333 |
user output |
---|
333 |
Test 9
Verdict: ACCEPTED
input |
---|
400 356 162 104184 601951 422624 370531 ... |
correct output |
---|
265 |
user output |
---|
265 |
Test 10
Verdict: ACCEPTED
input |
---|
400 312 215 359148 808684 945274 604226 ... |
correct output |
---|
76 |
user output |
---|
76 |
Test 11
Verdict: ACCEPTED
input |
---|
325 713 168 826229 196639 317967 8558 ... |
correct output |
---|
294 |
user output |
---|
294 |
Test 12
Verdict: ACCEPTED
input |
---|
42 2 42 683073 532140 174856 51368 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 13
Verdict: ACCEPTED
input |
---|
203 516 366 125553 642375 63137 608569 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 14
Verdict: ACCEPTED
input |
---|
199 234 251 281253 491509 139389 436824 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 15
Verdict: WRONG ANSWER
input |
---|
315 442 326 750778 381993 661296 156508 ... |
correct output |
---|
0 |
user output |
---|
999999999999999 |
Test 16
Verdict: ACCEPTED
input |
---|
328 150 7 43275 248257 847043 99790 ... |
correct output |
---|
5990 |
user output |
---|
5990 |
Test 17
Verdict: ACCEPTED
input |
---|
109 139 17 756544 653138 951489 311818 ... |
correct output |
---|
519 |
user output |
---|
519 |
Test 18
Verdict: ACCEPTED
input |
---|
134 553 27 147387 129153 719770 427935 ... |
correct output |
---|
1291 |
user output |
---|
1291 |
Test 19
Verdict: ACCEPTED
input |
---|
145 241 2 676743 605609 180247 181812 ... |
correct output |
---|
16132 |
user output |
---|
16132 |
Test 20
Verdict: ACCEPTED
input |
---|
199 345 1 860055 518304 632757 227941 ... |
correct output |
---|
63718 |
user output |
---|
63718 |
Test 21
Verdict: ACCEPTED
input |
---|
237 305 50 322166 709644 908880 898007 ... |
correct output |
---|
732 |
user output |
---|
732 |
Test 22
Verdict: ACCEPTED
input |
---|
400 448 110 759554 617824 923199 28933 ... |
correct output |
---|
682 |
user output |
---|
682 |
Test 23
Verdict: ACCEPTED
input |
---|
20 43 22 227704 798839 578770 318490 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 24
Verdict: ACCEPTED
input |
---|
400 571 70 450921 468211 132387 47354 ... |
correct output |
---|
1770 |
user output |
---|
1770 |
Test 25
Verdict: ACCEPTED
input |
---|
400 511 70 858453 872050 610960 953293 ... |
correct output |
---|
1591 |
user output |
---|
1591 |
Test 26
Verdict: ACCEPTED
input |
---|
400 168 70 4459 674845 367823 294137 ... |
correct output |
---|
490 |
user output |
---|
490 |
Test 27
Verdict: ACCEPTED
input |
---|
400 680 70 30654 191088 801200 207158 ... |
correct output |
---|
2102 |
user output |
---|
2102 |
Test 28
Verdict: ACCEPTED
input |
---|
400 248 9 470894 893438 325348 641558 ... |
correct output |
---|
9158 |
user output |
---|
9158 |
Test 29
Verdict: ACCEPTED
input |
---|
400 382 9 199594 909749 628471 402271 ... |
correct output |
---|
14426 |
user output |
---|
14426 |
Test 30
Verdict: ACCEPTED
input |
---|
400 428 9 482354 949600 607474 999204 ... |
correct output |
---|
16028 |
user output |
---|
16028 |
Test 31
Verdict: ACCEPTED
input |
---|
400 720 29 188913 504810 623401 693477 ... |
correct output |
---|
6872 |
user output |
---|
6872 |
Test 32
Verdict: ACCEPTED
input |
---|
400 720 29 665160 117237 952099 664974 ... |
correct output |
---|
6875 |
user output |
---|
6875 |
Test 33
Verdict: ACCEPTED
input |
---|
17 15 34 930291 502763 967298 799893 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 34
Verdict: ACCEPTED
input |
---|
400 720 255 248532 531967 568554 368539 ... |
correct output |
---|
207 |
user output |
---|
207 |
Test 35
Verdict: ACCEPTED
input |
---|
400 720 383 587057 127300 561898 335689 ... |
correct output |
---|
17 |
user output |
---|
17 |
Test 36
Verdict: ACCEPTED
input |
---|
400 720 127 587057 127300 561898 335689 ... |
correct output |
---|
1007 |
user output |
---|
1007 |
Test 37
Verdict: ACCEPTED
input |
---|
400 720 399 554238 475586 539758 602129 ... |
correct output |
---|
1 |
user output |
---|
1 |
Test 38
Verdict: ACCEPTED
input |
---|
400 720 67 498986 209095 87086 627358 ... |
correct output |
---|
2576 |
user output |
---|
2576 |
Test 39
Verdict: ACCEPTED
input |
---|
400 720 25 52948 388352 380718 137663 ... |
correct output |
---|
9211 |
user output |
---|
9211 |
Test 40
Verdict: ACCEPTED
input |
---|
13 34 8 663490 977749 760140 95431 ... |
correct output |
---|
5 |
user output |
---|
5 |
Test 41
Verdict: ACCEPTED
input |
---|
12 20 3 193357 939494 993606 22131 ... |
correct output |
---|
37 |
user output |
---|
37 |
Test 42
Verdict: ACCEPTED
input |
---|
58 281 30 980435 768397 647975 798884 ... |
correct output |
---|
99 |
user output |
---|
99 |
Test 43
Verdict: ACCEPTED
input |
---|
96 72 69 567259 416559 401648 673446 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 44
Verdict: ACCEPTED
input |
---|
96 249 90 666268 812077 949656 878404 ... |
correct output |
---|
0 |
user output |
---|
0 |