Task: | Gondolas |
Sender: | Game of Nolife |
Submission time: | 2016-11-12 13:41:46 +0200 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.06 s | details |
#3 | ACCEPTED | 0.07 s | details |
#4 | ACCEPTED | 0.06 s | details |
#5 | ACCEPTED | 0.06 s | details |
#6 | ACCEPTED | 0.06 s | details |
#7 | ACCEPTED | 0.29 s | details |
#8 | ACCEPTED | 0.30 s | details |
#9 | ACCEPTED | 0.22 s | details |
#10 | ACCEPTED | 0.29 s | details |
#11 | ACCEPTED | 0.20 s | details |
#12 | ACCEPTED | 0.06 s | details |
#13 | ACCEPTED | 0.07 s | details |
#14 | ACCEPTED | 0.09 s | details |
#15 | ACCEPTED | 0.15 s | details |
#16 | ACCEPTED | 0.10 s | details |
#17 | ACCEPTED | 0.06 s | details |
#18 | ACCEPTED | 0.08 s | details |
#19 | ACCEPTED | 0.06 s | details |
#20 | ACCEPTED | 0.10 s | details |
#21 | ACCEPTED | 0.10 s | details |
#22 | ACCEPTED | 0.32 s | details |
#23 | ACCEPTED | 0.06 s | details |
#24 | ACCEPTED | 0.42 s | details |
#25 | ACCEPTED | 0.39 s | details |
#26 | ACCEPTED | 0.16 s | details |
#27 | ACCEPTED | 0.50 s | details |
#28 | ACCEPTED | 0.23 s | details |
#29 | ACCEPTED | 0.41 s | details |
#30 | ACCEPTED | 0.41 s | details |
#31 | ACCEPTED | 0.53 s | details |
#32 | ACCEPTED | 0.52 s | details |
#33 | ACCEPTED | 0.06 s | details |
#34 | ACCEPTED | 0.44 s | details |
#35 | ACCEPTED | 0.42 s | details |
#36 | ACCEPTED | 0.41 s | details |
#37 | ACCEPTED | 0.43 s | details |
#38 | ACCEPTED | 0.52 s | details |
#39 | ACCEPTED | 0.52 s | details |
#40 | ACCEPTED | 0.06 s | details |
#41 | ACCEPTED | 0.06 s | details |
#42 | ACCEPTED | 0.06 s | details |
#43 | ACCEPTED | 0.05 s | details |
#44 | ACCEPTED | 0.06 s | details |
Code
#include <bits/stdc++.h> #define F first #define S second #define X real() #define Y imag() using namespace std; typedef long long ll; typedef long double ld; int dp[444][444]; int f[444][444]; int n,t,g; pair<int, vector<int> > solve(vector<int> xs){ for (int i=0;i<=n+1;i++){ for (int ii=0;ii<=g+1;ii++){ dp[i][ii]=1e8; } } dp[0][0]=0; for (int i=0;i<n;i++){ for (int ii=0;ii<g;ii++){ int c=0; int su=0; for (int j=i;j<n;j++){ c++; su+=xs[j]; if (dp[i][ii]+xs[j]*c-su<dp[j+1][ii+1]){ dp[j+1][ii+1]=dp[i][ii]+xs[j]*c-su; f[j+1][ii+1]=i; } } } } assert(dp[n][g]<1e8); int v=dp[n][g]; vector<int> vv; int ti=n; for (int a=g;a>0;a--){ vv.push_back(xs[ti-1]); ti=f[ti][a]; } return {v, vv}; } int solve2(vector<int> xs, int offs){ vector<int> ys; for (int x:xs){ ys.push_back((x-offs+8*t)%(2*t)); } sort(ys.begin(), ys.end()); auto v=solve(ys); return v.F; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>t>>g; g=min(g, n); vector<int> xs; for (int i=0;i<n;i++){ int x; cin>>x; xs.push_back(x%(2*t)); } sort(xs.begin(), xs.end()); auto aa=solve(xs); int v=aa.F; sort(aa.S.begin(), aa.S.end()); int mi=1e9; int mii=0; for (int i=0;i<(int)aa.S.size();i++){ if (i+1==(int)aa.S.size()){ if (aa.S[0]+t*2-aa.S[i]<mi){ mi=aa.S[0]+t*2-aa.S[i]; mii=i; } } else if (aa.S[i+1]-aa.S[i]<mi){ mi=aa.S[i+1]-aa.S[i]; mii=i; } } if (mii+1==(int)aa.S.size()){ for (int j=aa.S.back();j<2*t;j++){ v=min(v, solve2(xs, j)); v=min(v, solve2(xs, -j)); } for (int j=0;j<=aa.S[0];j++){ v=min(v, solve2(xs, j)); v=min(v, solve2(xs, -j)); } } else{ for (int j=aa.S[mii];j<=aa.S[mii+1];j++){ v=min(v, solve2(xs, j)); v=min(v, solve2(xs, -j)); } } cout<<v<<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: ACCEPTED
input |
---|
315 442 326 750778 381993 661296 156508 ... |
correct output |
---|
0 |
user output |
---|
0 |
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 |