THE QUESTION
Text from the official booklet. Refer to the PDF for original mathematical notation, formatting, and linked input files. Printed samples and inputs are reproduced as published.
Oh no! While seeking a safe space to hide from the robots, you have fallen right into
their human trap. Luckily, you are an incredibly smart hacker and have found a way to
bypass the system.
You are given an array a of n real numbers and an integer k (1 ≤ k ≤ n). You want to
select exactly k pairwise disjoint, non-empty contiguous subarrays. Let avg( S) denote
the arithmetic mean of elements inside subarray S. Your score is the minimum average
among the k chosen subarrays:
score = min{avg(S1), avg(S2), . . . ,avg(Sk)}.
In order to escape the human trap, you have to find the maximum possible score (to
the nearest integer) achievable by choosing k disjoint contiguous subarrays.
Input format:
Each test contains multiple test cases. The first line contains the number of test cases
t (1 ≤ t ≤ 104). The description of the test cases follows.
• The first line of each test case contains integers n, k(1 ≤ n ≤ 2 · 105, 1 ≤ k ≤ n)
• The second line contains n integers a1, a2, . . . , an (|ai| ≤109)
Output format:
Print a single integer: the maximum possible score.
Sample Input:
1
7 2
6 6 2 3 7 7 1
Sample Output:
7
Question input:
50
21 2
802 1203 4777 2191 9123 659 8357 4838 6963 6973
5211 5401 8077 9251 6264 9879 9080 3754 5757 8539
3653 13 9
9934 6866 4178 4061 1124 687 2983 3177 113 2607
9354 5488 6085
21 15
6895 5101 5268 385 9274 5432 7989 750 18 9550
9374 6994 7980 680 5702 9023 7982 8999 2174 4265
2081 18 14
3905 758 8769 9802 262 2424 4803 4537 4025 9200
2087 1041 6747 3462 7042 270 7930 9475
18 2
3062 9443 4302 195 3755 5568 3265 9444 7442 6672
4030 4755 3156 9030 9931 9581 2846 3173
18 9
2042 9731 5315 6293 8126 6225 2924 9578 2738 7514
8252 7834 2606 2734 1454 620 1308 3083
26 17
8645 1633 1080 6099 5539 7195 4245 9482 1749 1756
5298 5122 8881 4559 5846 4759 1252 5529 9145 4383
2730 1483 2015 5709 4707 2858
22 14
2556 5049 8827 9510 7583 896 5318 4163 2282 4521
2643 3710 8777 659 1605 9400 5859 7866 8309 2175
5196 315
26 16
4536 1762 4294 7022 4154 667 8027 8866 9543 7042
8024 8442 779 3558 7851 6611 9088 8 1375 2383
9734 5905 1410 7288 6099 1547
26 11
3422 6179 1472 6489 2121 5510 7659 6763 5416 6800
9678 2413 7694 1482 499 5675 891 4598 5652 3273
5270 7216 3125 526 9868 8982
22 13
9215 4739 4757 9744 397 6670 5968 6543 675 8172
4183 9664 1347 6542 2710 7106 2003 5304 3062 2580
8319 3270
20 16
1316 8434 8890 648 8082 3723 263 8040 1435 6424
6092 2401 533 6877 4908 6692 556 2796 1975 9767
20 12
4325 8175 2261 611 5820 227 7361 3164 1812 6747
8067 5023 3820 882 5733 7114 5525 5666 4102 7713
19 8
7796 2320 3445 7840 5899 8393 3615 798 9740 8932
5945 3140 3533 1855 9273 365 1902 2349 8758
24 16
1596 6207 9748 5394 4774 2118 4347 379 1143 172 6103
8217 5472 6993 9066 6654 9337 6863 1768 4497
1293 2371 3580 8766
23 11
853 524 5801 964 6122 3195 7116 4858 8075 6214 8587
7491 9264 5096 584 2048 7983 9932 6640 183
3776 2642 2035
28 4
8705 869 4138 7437 1518 1048 8894 3816 7179 6340
2987 4002 5959 6722 9273 9276 5903 4880 5739 5990
4870 660 9172 1972 8207 4033 8741 4877
17 9
4098 4405 8895 9452 6092 2753 4000 1368 6126 3874
5805 4927 9027 5093 3014 9145 3548
20 8
3373 6496 1312 5117 9690 6871 1468 9935 9142
1972 3280 6726
16 5252 4013 3467 9335 2675 6551 2543
16 2
5110 2392 2864 4977 6459 7004 4255 376 1880 9475
9466 5799 8985 9900 5917 5825
17 2
400 943 1824 7249 5278 1893 3166 8689 5658 7292 8253
810 7134 4051 8476 7926 3664
15 15
1388 5116 4136 9979 6044 9498 8148 4949 227 3852
3707 1292 1557 8823 5254
15 8
5964 5261 8845 7623 87 7235 6940 8903 6378 9237
4710 5636 1840 9165 2588
24 23
9463 3707 1705 5276 3724 6696 5554 9708 9169 1676
5415 7563 8538 3538 8595 2397 6305 2165 419
5351 3805 9121 3324 7504
16 1
3509 2973 2258 7517 690 8663 2679 9819 5451 4667
50 958 1645 2852 731 6179
23 18
8180 9861 2267 6809 2016 7199 7820 3849 6876 5015
8049 2736 9702 8182 3562 1951 7870
6859 3593 8748 1910 3876 9650
21 6
4237 3685 4697 3243 187 4794 6935 8140 2047
613 2228 2566 7021 5464 9229
1253 9611 1775 223 2554 1941
15 10
2189 6540 3595 9370 7526 1855 6388 1168 1688 6582
1090 4592 9687 9079 1312
19 18
5888 4605 393 8884 5115 8614 36 1242 9378 6603
6309 8297 573 4693 3963 1065 8600
2294 8709
15 5
7549 4394 6626 9215 5720 5875 36 9843 5284 2253
4579 6296 2023 5986 9096
21 17
5056 8975 2003 9825 1788 7433 3678 3704 4274
2871 7291 1634 9515 4732 3449 9185
7367 728 2184 2644 6423
15 9
2267 8597 6499 283 4823 230 277 5394 7189 1740
2587 9403 8534 9604 4836
25 21
1960 7610 683 8878 2956 276 3949 794 3166
4978 9127 3884 1134 6371 9913 9478
2979 6792 7844 1127 2192 8028 5997 7643 6583
24 16
1955 493 5030 7167 9083 4659 6216 5307 3586 780
5400 4439 8760 6306 4296 2853 1482 3432 3789
5791 6554 1435 3776 9493
20 16
3500 4845 2535 9244 8302 8937 3867 9330 7218
203 5174 2252 600 9799 9549 3231 9014
3511 406 9902
15 10
3268 2070 1378 9134 2012 1343 7630 4092 553
9986 7470 5148 5482 2243 4676
17 16
7082 3565 1322 9071 3650 9509 3520 9422 9037
2392 8953 5502 2236 8636 604 2092 6667
23 20
5946 1546 5592 1072 3482 7941 2490 6646 2139
8110 4993 8060 2528 2375 4392 1943 9051
4858 7040 3204 7374 9545 9191
17 12
9060 12 6977 6934 3917 5171 578 2589 1220 230
1385 2341 8024 7520 3361 6823 4179
31 16
1599 2421 8984 3852 9476 9869 718 624 8575 8237
6620 361 3614 9947 2255 530 6298 3706
8371 8795 4663 7526 7682 2479 995 3496 7755 2210
798 9898 1608
25 9
6676 9744 6267 4058 9906 4590 8348 984 113 4433
2138 3814 5181 2093 2102 3889 6455 1372 3634
6439 7945 9668 9804 7001 5731