QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #799961 | #8440. Toll Roads | cdx123456 | AC ✓ | 8438ms | 4372kb | C++14 | 1.7kb | 2024-12-05 19:48:01 | 2024-12-05 19:48:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,K,s,t,sum,ansm,anss,anst,d[5010],d2[5010],g[5010];
vector<int> v[5010];
void dfs(int x,int fa){
d[x]=0;
d2[x]=g[x]=-1e9;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
dfs(y,x);
g[x]=max(g[x],g[y]);
if(d[y]+1>d[x]) d2[x]=d[x],d[x]=d[y]+1;
else if(d[y]+1>d2[x]) d2[x]=d[y]+1;
}
g[x]=max(g[x],max(d[x],d2[x]+d[x]));
}
bool dfs2(int x,int fa,int z,int max_d){
int cnt=0,k=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
if(g[y]>z || d[y]>max_d-1) cnt++,k=y;
}
if(cnt>1) return 0;
if(!cnt && g[x]<=z) return 1;
if(cnt==0){
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
if(d[y]+1==d[x]) k=y;
}
}
int maxx=-1,maxx2=-1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==fa) continue;
if(y==k) continue;
if(d[y]>maxx) maxx2=maxx,maxx=d[y];
else if(d[y]>maxx2) maxx2=d[y];
}
if(maxx+maxx2+2>z) return 0;
if(dfs2(k,x,z,min(max_d,z-maxx-1))){
if(!t) t=k;
sum++;
return 1;
}
return 0;
}
bool check(int x){
int minn=1e9,mins=0,mint=0;
for(int i=1;i<=n;i++){
dfs(i,0);
s=i; t=sum=0;
if(dfs2(i,0,x,1e9) && sum<minn){
minn=sum;
mins=s;
mint=t;
}
}
if(minn>K) return 0;
ansm=minn;
anss=mins;
anst=mint;
return 1;
}
int main(){
int x,y,l=0,r=10000;
cin>>n>>K;
for(int i=1;i<n;i++){
cin>>x>>y;
v[x+1].push_back(y+1);
v[y+1].push_back(x+1);
}
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<r+1<<endl;
cout<<ansm<<endl;
if(ansm) cout<<anss-1<<' '<<anst-1<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3772kb
input:
8 3 0 2 0 5 2 3 5 1 4 5 5 6 6 7
output:
2 3 2 6
result:
ok n=8, K=3: cost=2, k=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
5 2 0 1 0 2 0 3 0 4
output:
2 0
result:
ok n=5, K=2: cost=2, k=0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
2 1 0 1
output:
0 1 0 1
result:
ok n=2, K=1: cost=0, k=1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
3 1 0 1 2 1
output:
1 1 0 1
result:
ok n=3, K=1: cost=1, k=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 1 0 2 1 2
output:
1 1 0 2
result:
ok n=3, K=1: cost=1, k=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
3 2 0 2 1 2
output:
0 2 0 1
result:
ok n=3, K=2: cost=0, k=2
Test #7:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
4 1 0 3 0 1 3 2
output:
2 1 0 3
result:
ok n=4, K=1: cost=2, k=1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 2 0 3 0 1 3 2
output:
1 2 0 2
result:
ok n=4, K=2: cost=1, k=2
Test #9:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 3 0 3 0 1 3 2
output:
0 3 1 2
result:
ok n=4, K=3: cost=0, k=3
Test #10:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 1 0 1 0 2 0 3
output:
2 0
result:
ok n=4, K=1: cost=2, k=0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
4 2 0 1 0 2 0 3
output:
1 2 1 3
result:
ok n=4, K=2: cost=1, k=2
Test #12:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
4 3 0 1 0 2 0 3
output:
1 2 1 3
result:
ok n=4, K=3: cost=1, k=2
Test #13:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 3 0 1 0 2 0 3 2 4 3 5
output:
2 2 2 3
result:
ok n=6, K=3: cost=2, k=2
Test #14:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
6 3 0 1 0 2 0 3 2 4 2 5
output:
2 1 0 2
result:
ok n=6, K=3: cost=2, k=1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
8 5 0 1 1 2 2 3 0 4 4 5 5 6 0 7
output:
2 4 2 5
result:
ok n=8, K=5: cost=2, k=4
Test #16:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
2 1 0 1
output:
0 1 0 1
result:
ok n=2, K=1: cost=0, k=1
Test #17:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 1 2 1 0 2
output:
1 1 0 2
result:
ok n=3, K=1: cost=1, k=1
Test #18:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 1 0 2 0 1
output:
1 1 0 1
result:
ok n=3, K=1: cost=1, k=1
Test #19:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 2 1 0 1 2
output:
0 2 0 2
result:
ok n=3, K=2: cost=0, k=2
Test #20:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
3 2 0 1 0 2
output:
0 2 1 2
result:
ok n=3, K=2: cost=0, k=2
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 1 2 1 2 0 1 3
output:
2 1 0 2
result:
ok n=4, K=1: cost=2, k=1
Test #22:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 1 2 0 0 3 1 0
output:
2 0
result:
ok n=4, K=1: cost=2, k=0
Test #23:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
4 2 3 0 1 2 2 3
output:
1 2 0 2
result:
ok n=4, K=2: cost=1, k=2
Test #24:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
4 2 1 0 0 3 0 2
output:
1 2 1 2
result:
ok n=4, K=2: cost=1, k=2
Test #25:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 3 3 0 3 2 2 1
output:
0 3 0 1
result:
ok n=4, K=3: cost=0, k=3
Test #26:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
4 3 1 0 3 0 2 0
output:
1 2 1 2
result:
ok n=4, K=3: cost=1, k=2
Test #27:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
10 3 3 0 8 1 9 5 0 4 0 1 7 5 6 8 2 8 5 8
output:
2 3 0 5
result:
ok n=10, K=3: cost=2, k=3
Test #28:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
100 4 32 66 29 26 86 0 71 83 26 70 62 84 51 9 37 0 0 62 83 96 86 88 40 1 37 6 70 34 13 19 65 8 0 43 39 65 99 77 33 0 84 65 64 95 60 64 83 56 26 89 0 25 92 33 63 42 45 73 66 84 24 21 36 11 52 15 9 92 3 17 80 48 88 97 23 54 28 5 46 98 42 20 5 93 84 89 56 23 97 73 36 99 0 35 97 90 76 18 50 27 26 75 50 ...
output:
12 4 86 89
result:
ok n=100, K=4: cost=12, k=4
Test #29:
score: 0
Accepted
time: 113ms
memory: 3900kb
input:
1000 1 155 994 213 449 582 440 277 0 307 84 51 445 69 133 740 538 538 912 480 346 282 611 258 846 105 264 303 604 447 400 89 105 815 885 819 344 844 234 14 288 753 518 109 985 70 417 175 694 125 661 8 303 788 333 780 468 565 986 312 601 246 548 204 370 995 287 327 989 253 918 17 33 710 352 755 22 53...
output:
22 1 1 330
result:
ok n=1000, K=1: cost=22, k=1
Test #30:
score: 0
Accepted
time: 959ms
memory: 3884kb
input:
2500 10 517 660 971 230 982 1721 2200 2124 2171 1468 61 1724 666 1745 821 1066 2281 387 2034 636 909 444 1547 96 2421 1862 563 1859 766 688 1706 1646 1211 986 1318 1970 2081 418 1406 2240 72 192 1597 2454 1148 2071 762 1298 618 198 1143 1012 2352 1975 210 885 2205 412 574 1558 400 1617 402 1062 516 ...
output:
23 4 294 943
result:
ok n=2500, K=10: cost=23, k=4
Test #31:
score: 0
Accepted
time: 5531ms
memory: 4000kb
input:
5000 1 1611 2785 2978 4796 3783 4548 1074 1256 1866 4595 1045 1496 2202 4174 356 449 3634 3477 449 4707 930 1014 3190 2963 4530 2516 3399 4303 75 1315 4612 2722 4449 1862 4718 3600 3323 17 1387 388 303 4516 1652 1608 3952 2847 3922 3994 4257 4856 2341 4626 16 103 400 1256 1634 731 3072 3274 2905 160...
output:
34 1 0 2352
result:
ok n=5000, K=1: cost=34, k=1
Test #32:
score: 0
Accepted
time: 5454ms
memory: 3928kb
input:
5000 2 3110 2737 2365 2830 2914 874 3720 2637 325 3662 2948 0 4026 591 4556 4347 566 586 2993 3297 4205 2131 3144 1190 1300 421 366 4275 2443 4465 3227 382 1874 550 1067 94 4250 1375 1200 987 3881 1644 90 3163 3406 625 794 3974 4063 482 4082 1711 688 4863 2698 2374 2357 925 3083 3398 3084 572 2028 1...
output:
30 2 844 1623
result:
ok n=5000, K=2: cost=30, k=2
Test #33:
score: 0
Accepted
time: 5955ms
memory: 3988kb
input:
5000 4 664 4317 295 764 4857 1869 1111 1915 1394 4735 1851 2001 2728 4694 987 986 4529 708 966 176 2645 2670 2365 1832 1517 2454 1135 1233 702 1052 4658 2524 453 1816 2826 4099 626 815 4869 924 645 4544 2881 2449 878 196 3294 2750 4495 515 4387 4404 2411 2079 2956 2716 1105 2629 2818 1484 4220 2010 ...
output:
33 4 541 2936
result:
ok n=5000, K=4: cost=33, k=4
Test #34:
score: 0
Accepted
time: 5433ms
memory: 3996kb
input:
5000 8 4033 4112 3295 1781 1623 933 2035 1665 4178 3082 4598 4675 2499 2355 4927 2284 1099 1879 2098 3210 3350 4001 3054 1374 3026 404 1552 551 3491 733 2806 2680 1077 1502 4147 3244 1876 4078 1813 3952 2371 4282 3657 1948 3910 2509 3871 2946 779 3606 738 1715 4476 3796 1659 968 390 501 3350 3934 29...
output:
30 7 2605 4351
result:
ok n=5000, K=8: cost=30, k=7
Test #35:
score: 0
Accepted
time: 5514ms
memory: 3936kb
input:
5000 20 2304 353 834 2090 1767 72 3026 4211 3550 3263 1034 1911 1058 2418 4327 776 1858 4328 3688 4037 3160 2734 587 1550 2114 3695 4083 4564 1072 2911 4275 4097 4521 4705 3490 1772 1770 2656 3850 531 1736 1072 1313 3466 54 4949 3683 4416 480 1545 305 4332 298 2969 736 2355 4570 159 2750 2194 1020 3...
output:
26 12 1708 3762
result:
ok n=5000, K=20: cost=26, k=12
Test #36:
score: 0
Accepted
time: 5467ms
memory: 3992kb
input:
5000 100 1688 3447 496 2607 1054 2586 4259 2671 1317 133 207 460 1259 4411 3668 4671 774 3717 956 1379 968 2312 3962 2454 2805 4687 2265 3821 1719 4327 2680 110 391 1921 4002 273 3693 3942 684 4498 2255 567 62 1025 3844 458 4343 318 479 4321 2704 4997 1132 3219 488 647 442 1794 1275 4152 1979 4767 3...
output:
29 5 1379 2879
result:
ok n=5000, K=100: cost=29, k=5
Test #37:
score: 0
Accepted
time: 5907ms
memory: 3916kb
input:
5000 1000 638 3198 3452 4568 2723 2277 1947 4539 2947 1481 1847 4318 2453 3916 3546 2812 3794 4205 3355 1316 1404 4643 274 2887 4222 3288 1370 1083 3795 3275 3336 350 3335 1211 2535 920 2465 4385 695 194 4923 4934 2455 4576 3124 3341 4852 4583 340 2654 2840 2323 1356 1176 153 4145 2703 1741 867 4656...
output:
28 6 4411 517
result:
ok n=5000, K=1000: cost=28, k=6
Test #38:
score: 0
Accepted
time: 5913ms
memory: 3928kb
input:
5000 2000 1451 4112 1730 1026 1556 1248 4723 678 2618 2658 1038 3223 3 4927 2239 563 3834 2334 645 2924 4290 3043 3714 677 4876 1906 3459 1793 68 2041 2668 12 1818 871 2371 4251 4090 551 1211 369 4239 3736 3502 64 3380 2508 390 895 4631 4907 3627 4030 916 2134 4903 831 3372 228 293 4601 418 2484 251...
output:
28 6 82 4161
result:
ok n=5000, K=2000: cost=28, k=6
Test #39:
score: 0
Accepted
time: 5973ms
memory: 4048kb
input:
5000 4000 3618 1301 2744 1363 1705 3118 2385 2886 632 701 1377 1811 3023 2387 4271 3312 3313 4071 3356 3272 1828 2086 3005 2897 3527 2614 2325 4083 372 4535 3223 221 3071 3121 757 2734 2428 3401 4510 3322 854 1033 3700 930 3320 4120 2022 3460 4694 1786 2290 156 2592 2073 2028 1907 3527 2783 2234 821...
output:
28 11 1526 2510
result:
ok n=5000, K=4000: cost=28, k=11
Test #40:
score: 0
Accepted
time: 5514ms
memory: 3984kb
input:
5000 4999 1647 992 3574 4278 2808 2380 3945 287 51 1431 2167 2902 3812 2551 2132 3223 3311 491 2866 3796 3868 2853 2515 375 895 2665 1959 2721 1195 1509 548 1644 2592 3299 1266 3956 3491 1548 3022 4843 3690 3296 3687 700 349 4936 4386 1254 2492 769 1369 4053 2028 1000 4681 4738 918 1940 2739 1553 16...
output:
25 10 510 839
result:
ok n=5000, K=4999: cost=25, k=10
Test #41:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
100 4 48 94 54 34 25 31 12 16 70 90 67 11 96 71 8 80 78 62 76 38 99 7 14 86 14 15 26 84 73 16 98 45 97 39 5 2 16 13 56 21 59 28 11 57 50 43 0 36 21 91 29 42 71 5 15 30 32 79 81 72 47 75 25 49 81 86 82 9 7 13 80 59 96 76 70 44 6 92 26 69 90 58 89 43 47 80 52 53 35 81 20 97 54 1 21 1 18 7 88 39 97 93 ...
output:
18 3 13 24
result:
ok n=100, K=4: cost=18, k=3
Test #42:
score: 0
Accepted
time: 116ms
memory: 3756kb
input:
1000 1 649 341 964 65 43 702 226 543 577 730 572 597 452 335 434 330 686 901 826 505 160 880 947 218 245 93 623 674 943 915 782 425 751 246 126 453 35 645 240 497 80 904 223 629 938 368 679 676 122 50 203 469 149 561 787 766 242 963 373 361 636 318 529 693 262 641 527 110 193 948 720 60 503 524 607 ...
output:
54 1 23 833
result:
ok n=1000, K=1: cost=54, k=1
Test #43:
score: 0
Accepted
time: 1109ms
memory: 3880kb
input:
2500 10 2238 1206 1470 365 1938 1220 962 2009 173 1538 17 2496 1722 1943 1926 420 2239 718 1215 374 1775 1878 1168 2329 314 1858 304 1709 363 516 695 669 432 1472 2019 2018 746 1289 57 571 1684 995 912 907 375 995 261 987 178 1528 2115 686 773 1928 2133 2243 370 2181 64 2004 298 171 424 253 1146 177...
output:
51 10 333 1068
result:
ok n=2500, K=10: cost=51, k=10
Test #44:
score: 0
Accepted
time: 6217ms
memory: 3980kb
input:
5000 1 1600 4821 4466 2988 261 1010 1777 2935 4739 3916 82 2226 4482 111 877 4562 1307 2736 2691 2394 4812 3144 785 4848 4527 1343 4586 899 3318 3202 2219 4496 628 867 781 2695 1055 2820 2911 1033 815 3212 420 3645 4178 1211 375 3879 2105 2646 4294 879 2599 83 1359 3257 3406 3271 162 3100 4628 1505 ...
output:
84 1 36 723
result:
ok n=5000, K=1: cost=84, k=1
Test #45:
score: 0
Accepted
time: 6350ms
memory: 3992kb
input:
5000 2 2161 2849 1729 1347 1763 2560 2098 2899 3695 1883 1070 2074 805 3041 3227 913 3480 1714 1360 1008 2117 4398 3961 2080 3023 3629 4405 81 3837 3805 1990 3047 4254 2943 2701 76 4112 2978 2723 3517 428 760 2015 2233 1558 2184 1486 1353 261 4992 3615 1285 3944 3263 4933 3839 653 2638 2543 3561 292...
output:
112 2 1 1769
result:
ok n=5000, K=2: cost=112, k=2
Test #46:
score: 0
Accepted
time: 6370ms
memory: 4064kb
input:
5000 4 3961 4831 2920 3199 4703 3118 201 1241 3774 2707 142 1099 2273 1098 963 34 1068 55 684 535 1020 4719 3531 77 2493 590 3544 2639 2161 1475 2954 1827 3266 3185 63 3535 3566 4126 113 2710 3518 653 3065 1294 4956 2385 2351 3280 2913 840 1411 2397 3524 161 2085 3040 313 2713 551 2062 2110 4766 271...
output:
112 4 43 3823
result:
ok n=5000, K=4: cost=112, k=4
Test #47:
score: 0
Accepted
time: 6351ms
memory: 3920kb
input:
5000 8 3226 1183 3536 3297 2501 261 3071 4107 2916 1273 3271 3803 1258 592 2611 2384 4144 2570 4487 922 4870 4150 3063 4162 4147 3543 2286 1836 1760 4104 3350 2553 4574 1879 3521 4148 813 725 2624 4930 3173 3454 4381 2818 854 3591 361 1647 1256 3130 1988 4716 906 4952 3742 2826 1898 2569 4816 4296 3...
output:
122 8 133 3667
result:
ok n=5000, K=8: cost=122, k=8
Test #48:
score: 0
Accepted
time: 6844ms
memory: 4064kb
input:
5000 20 1221 3603 3259 3147 3676 1561 4574 962 4590 491 4406 74 1830 264 2671 3203 3990 3318 1326 3050 4596 3031 3070 432 2365 1316 1391 2088 306 953 3312 2621 307 4473 1850 378 1610 915 1828 244 3570 2037 2661 1028 1063 4003 4059 1784 217 4397 4826 1064 379 2815 4251 4616 4434 110 2761 2865 2693 33...
output:
86 20 128 2391
result:
ok n=5000, K=20: cost=86, k=20
Test #49:
score: 0
Accepted
time: 6271ms
memory: 3924kb
input:
5000 100 50 2333 699 2904 4502 392 2177 3778 78 182 3021 2565 1534 1786 3124 2748 2712 3895 1399 1021 1682 179 3253 364 4722 4733 4350 3639 3638 1123 247 3337 3586 4484 1796 3978 4990 3613 206 3509 3486 2185 1849 458 2932 4060 1923 1091 3148 3188 3466 4694 4535 55 577 3974 455 9 4893 4032 908 2363 4...
output:
75 42 1627 3129
result:
ok n=5000, K=100: cost=75, k=42
Test #50:
score: 0
Accepted
time: 6271ms
memory: 4028kb
input:
5000 1000 1025 4349 3214 4639 4004 2506 652 4796 1396 2877 2808 48 2035 4015 61 2707 2381 4161 718 4075 1294 4402 1553 2464 4618 4170 2067 3920 2652 3258 2391 1747 72 3034 265 4445 4851 2174 2115 4745 4351 375 2077 2191 660 2893 414 2294 3332 4203 786 657 535 2737 708 3263 4186 2564 1003 1303 4696 1...
output:
38 10 2964 4732
result:
ok n=5000, K=1000: cost=38, k=10
Test #51:
score: 0
Accepted
time: 6057ms
memory: 4044kb
input:
5000 2000 4108 791 4770 1666 4203 4197 2566 728 4381 156 4830 4888 3266 1665 1275 2875 4186 4462 3206 999 2113 222 2273 439 3657 3777 762 216 3720 4869 4647 4444 4984 1049 618 864 2349 4374 3108 1666 703 3591 3764 3159 1932 3213 149 4482 4536 3821 1300 420 1382 2056 2361 293 3576 1209 2401 3675 2812...
output:
48 19 2640 4559
result:
ok n=5000, K=2000: cost=48, k=19
Test #52:
score: 0
Accepted
time: 6210ms
memory: 3980kb
input:
5000 4000 2183 3550 857 549 4752 3563 4198 4895 2936 3492 2020 3789 3996 1586 4371 954 3182 3441 1776 461 2556 50 676 4251 1560 4004 1254 1825 2784 4774 265 914 1239 1139 1118 4526 877 1765 3922 2887 838 4769 3025 3030 3720 3378 2976 1895 1301 2892 2617 3327 4772 3505 2400 3644 1424 1379 2231 1924 6...
output:
69 26 3244 4780
result:
ok n=5000, K=4000: cost=69, k=26
Test #53:
score: 0
Accepted
time: 6341ms
memory: 3980kb
input:
5000 4999 4282 2328 4163 653 929 3214 3631 4207 1259 4176 672 3399 3982 617 4662 291 3927 4950 1465 188 1777 3802 4444 3727 4771 68 4556 4303 54 36 1153 3250 1962 2452 3861 3077 3325 2754 231 4158 1886 1455 404 1720 628 3826 1689 3866 4840 770 1430 2044 1750 1600 3082 568 3413 570 3114 1135 1866 320...
output:
79 26 2794 4878
result:
ok n=5000, K=4999: cost=79, k=26
Test #54:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
100 4 51 84 32 89 92 51 67 4 52 88 14 96 75 9 51 61 0 64 76 0 24 70 58 14 41 79 72 85 42 0 76 15 51 28 4 59 19 0 0 14 14 13 54 68 35 51 68 31 0 41 68 51 11 41 62 84 23 93 80 0 76 74 34 93 42 82 57 0 4 63 27 76 22 94 0 93 16 14 66 35 6 14 78 50 52 40 96 47 0 33 89 71 46 0 56 41 51 26 45 41 51 0 29 94...
output:
5 3 14 50
result:
ok n=100, K=4: cost=5, k=3
Test #55:
score: 0
Accepted
time: 89ms
memory: 3844kb
input:
1000 1 942 999 402 534 533 278 228 908 735 535 200 332 274 265 369 328 496 456 272 407 185 478 609 850 950 211 674 59 822 265 784 667 107 514 27 784 819 431 683 345 121 898 185 341 572 522 728 910 703 402 72 378 962 378 256 966 300 590 735 621 613 985 466 712 641 990 222 406 784 266 932 630 278 570 ...
output:
10 1 0 968
result:
ok n=1000, K=1: cost=10, k=1
Test #56:
score: 0
Accepted
time: 639ms
memory: 3844kb
input:
2500 10 1639 991 640 223 1940 1067 801 257 625 1953 29 1577 2108 890 1269 2452 53 1792 567 2307 1486 1656 840 2308 1176 2072 1001 205 117 2232 1652 1230 753 2138 2032 1118 1786 2243 1180 537 149 1612 170 1042 857 201 1812 714 1324 1041 145 158 1043 1188 1857 867 2074 1504 2118 1782 678 620 2156 2163...
output:
12 2 2075 2395
result:
ok n=2500, K=10: cost=12, k=2
Test #57:
score: 0
Accepted
time: 3606ms
memory: 3936kb
input:
5000 1 1585 3293 3686 3851 1447 1604 392 2681 774 3592 3653 3192 2769 4343 1807 3005 3019 482 1860 3612 128 1604 2203 1717 3286 83 1078 2782 2523 3052 1256 445 3770 3296 3577 961 4668 3787 2208 2559 1343 4864 1912 2934 683 3150 1334 3573 2698 4658 959 872 827 4542 4050 2811 2981 4081 2530 4171 3900 ...
output:
14 0
result:
ok n=5000, K=1: cost=14, k=0
Test #58:
score: 0
Accepted
time: 3600ms
memory: 3932kb
input:
5000 2 626 3760 2593 3177 1343 889 1377 596 2569 261 4413 4530 3742 4704 978 4341 2671 1853 551 3691 4086 1162 37 1367 4366 4408 4457 3337 269 4098 480 1346 589 3759 4712 2488 3563 2031 1561 2974 3967 1192 4206 1385 3616 2813 4097 3837 778 649 4177 1056 107 4341 4284 2958 4936 4258 1289 139 1805 318...
output:
14 0
result:
ok n=5000, K=2: cost=14, k=0
Test #59:
score: 0
Accepted
time: 3749ms
memory: 4016kb
input:
5000 4 1462 182 3060 4479 3021 4111 3145 2887 2297 1946 2507 509 974 1828 3077 4242 2807 2674 2158 3136 4565 3690 4206 3051 2077 3323 581 4704 2501 69 1822 3560 4261 3795 2088 2269 80 4382 3377 3838 4761 2797 3391 1967 2732 4461 3560 864 1424 1441 1012 2866 3629 1603 806 595 4123 4222 2032 161 2246 ...
output:
12 2 2219 3145
result:
ok n=5000, K=4: cost=12, k=2
Test #60:
score: 0
Accepted
time: 2514ms
memory: 4004kb
input:
5000 8 671 2837 3952 4186 828 1632 3885 2545 4406 2324 3038 4598 2533 2522 2746 1238 4412 4512 776 1044 170 2119 4600 3780 2288 3424 3119 231 4919 1570 2745 4617 1276 2791 1892 3196 1473 1874 4468 3038 1611 3776 825 2127 1928 3370 478 839 1345 4135 4118 3744 4326 1656 991 3936 1032 4701 734 4152 479...
output:
10 1 0 2405
result:
ok n=5000, K=8: cost=10, k=1
Test #61:
score: 0
Accepted
time: 3541ms
memory: 3928kb
input:
5000 20 3274 1781 3151 566 1298 1210 495 4010 1590 4059 884 3950 1061 2280 2075 3785 2597 667 1089 4960 1789 2798 4101 3021 2736 1590 1408 660 4399 796 3607 314 3400 2032 520 1029 1702 3183 1212 3805 4939 2357 2617 1046 402 617 3935 2323 1010 383 2610 3670 434 657 1682 2489 3881 3739 1653 957 229 31...
output:
14 0
result:
ok n=5000, K=20: cost=14, k=0
Test #62:
score: 0
Accepted
time: 2482ms
memory: 4076kb
input:
5000 100 487 1275 4234 2960 1502 3713 2471 819 1744 3846 1666 4545 128 4513 1305 4376 2117 3287 3642 2648 3771 2439 934 2001 436 608 2764 4102 2226 3853 4498 1025 3308 964 1083 1588 2870 1301 1164 2370 2246 3901 771 2689 3424 3442 2506 608 4278 63 2149 4375 4685 0 3455 2008 3191 1498 3907 1753 892 4...
output:
10 1 0 4411
result:
ok n=5000, K=100: cost=10, k=1
Test #63:
score: 0
Accepted
time: 3375ms
memory: 3944kb
input:
5000 1000 2192 4468 4475 4665 81 4277 998 1960 2838 2008 3575 2872 651 2552 3853 947 1063 239 1416 380 3107 1665 1003 297 2754 2008 4021 3105 1550 42 3625 3296 4020 2790 4287 4148 2637 4647 4928 250 448 1989 383 1966 3626 2176 1229 2389 2855 475 4786 344 2583 4974 2276 4236 4802 1116 3882 611 102 43...
output:
12 1 0 910
result:
ok n=5000, K=1000: cost=12, k=1
Test #64:
score: 0
Accepted
time: 3625ms
memory: 4068kb
input:
5000 2000 686 0 3311 3404 176 2362 119 2765 548 828 4932 3007 2873 990 3340 1733 3186 990 1822 2546 2888 2122 1822 777 2071 3222 3321 1778 4304 2521 4346 4702 2929 3349 3355 1662 1131 1911 1053 828 1744 1229 2548 1255 3890 210 3105 4653 4876 3264 3888 4184 3879 941 740 4746 889 4867 1071 760 4194 35...
output:
14 1 0 3007
result:
ok n=5000, K=2000: cost=14, k=1
Test #65:
score: 0
Accepted
time: 4271ms
memory: 3992kb
input:
5000 4000 2848 3939 1514 2396 527 821 2586 4938 984 2105 2973 4829 1429 4757 2637 4474 3390 4214 4651 887 2037 2860 2508 1222 2306 2766 198 815 4198 2233 32 3473 3180 3424 2968 3213 3011 4890 2832 128 4440 721 801 1820 3173 2349 4976 1421 4797 4510 3283 2158 1684 3598 3571 1192 4807 1517 3974 1374 3...
output:
16 3 318 3675
result:
ok n=5000, K=4000: cost=16, k=3
Test #66:
score: 0
Accepted
time: 2463ms
memory: 3996kb
input:
5000 4999 2128 1367 1616 1575 4936 3022 339 4210 2521 3287 2425 3414 1831 383 4528 2735 1237 1254 1020 4379 2526 1640 474 3522 1642 519 4168 2896 2647 2596 474 3349 4519 4244 32 2805 4597 2742 606 2528 1226 4311 588 1095 588 3851 1270 4794 2550 339 4746 3133 2736 971 1838 16 1736 0 878 378 4771 4958...
output:
10 0
result:
ok n=5000, K=4999: cost=10, k=0
Test #67:
score: 0
Accepted
time: 8438ms
memory: 4372kb
input:
5000 4999 2858 558 4677 2444 3042 610 1950 4352 3060 3819 4912 1349 3545 4009 3943 742 3869 771 3231 391 4313 2531 1299 213 886 4380 1667 1720 1195 4003 3816 2488 3642 1127 324 1866 4062 182 4274 185 2415 2694 2742 4935 2741 1637 2972 4159 602 1432 2456 2588 1782 1851 2500 3429 2137 1656 4726 4297 3...
output:
0 4999 0 1971
result:
ok n=5000, K=4999: cost=0, k=4999
Test #68:
score: 0
Accepted
time: 1908ms
memory: 4008kb
input:
5000 4999 0 3957 0 2864 0 2018 2678 0 0 99 0 2126 2473 0 0 3819 4275 0 0 4774 0 626 986 0 0 4421 0 1393 2524 0 0 3185 4032 0 0 2590 202 0 0 1589 0 2212 3404 0 0 1466 0 4520 0 2504 0 2139 0 3555 1016 0 0 611 1903 0 0 2863 2918 0 0 2348 2283 0 0 1085 0 2235 3807 0 4858 0 0 4937 4274 0 4896 0 2677 0 14...
output:
2 0
result:
ok n=5000, K=4999: cost=2, k=0
Test #69:
score: 0
Accepted
time: 8250ms
memory: 4372kb
input:
5000 1 2654 1880 2560 3683 4613 596 4860 1233 569 2227 4863 3022 4947 3146 1098 3272 3572 1383 497 4937 1901 4570 734 1769 459 2352 3551 3913 3109 169 1290 3913 340 3072 50 1667 82 1842 309 4842 1365 713 1520 4593 2635 1553 4870 4125 1558 3754 4890 4901 3494 2824 1488 3407 3734 1083 4879 833 493 979...
output:
4998 1 0 1782
result:
ok n=5000, K=1: cost=4998, k=1
Test #70:
score: 0
Accepted
time: 1837ms
memory: 4012kb
input:
5000 1 3762 0 0 2803 0 1387 610 0 0 2603 4126 0 0 3907 0 866 2935 0 4503 0 0 1562 1420 0 3927 0 0 1461 0 172 0 2112 4166 0 0 1506 0 2600 3457 0 0 3847 0 3434 4568 0 718 0 0 4814 0 236 0 1744 0 10 31 0 192 0 4282 0 4656 0 1127 0 1755 0 3517 0 0 4205 3147 0 0 3499 0 608 0 1135 0 1156 1121 0 0 3750 313...
output:
2 0
result:
ok n=5000, K=1: cost=2, k=0
Test #71:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
10 4 3 0 8 4 5 7 3 8 2 9 1 7 8 2 9 5 7 6
output:
3 4 3 5
result:
ok n=10, K=4: cost=3, k=4
Test #72:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
10 5 1 3 5 9 9 2 6 3 6 8 7 1 2 0 3 4 1 5
output:
2 5 2 6
result:
ok n=10, K=5: cost=2, k=5