fork download
  1. import sys
  2. sys.setrecursionlimit(1000000)
  3. input = sys.stdin.readline
  4. N,M = map(int,input().split())
  5. L = list(map(int,input().split()))
  6.  
  7. def binarySearch(a, m, M):
  8. low,sum = 0,0
  9. high = m
  10. tf = False
  11. while low <= high:
  12. mid = (low + high) // 2
  13. for i in a:
  14. if(i > mid):
  15. sum += i-mid
  16. if(sum == M):
  17. tf = True
  18. print(mid)
  19. break
  20. elif(sum > M):
  21. low = mid + 1
  22. sum = 0
  23. else:
  24. high = mid - 1
  25. sum = 0
  26. if(tf == False):
  27. M += 1
  28. binarySearch(L, max(L), M)
  29.  
  30. binarySearch(L, max(L), M)
Success #stdin #stdout 0.03s 9444KB
stdin
1000 555555
6654 3217 5739 308 6210 1544 3483 6503 3090 4599 1416 1171 1199 2374 4834 5605 5584 738 2814 207 5083 4532 5526 1923 4176 2606 6562 4057 2544 192 6231 2542 3957 2943 4540 2867 144 3407 5049 1886 5592 6159 2182 177 135 6545 3655 4032 4770 3199 2185 2838 2663 4850 1476 6555 542 4065 5782 5884 4686 3686 3760 618 1601 2912 5900 134 1054 1894 2882 5766 1186 1974 2510 3163 4583 5196 1131 4342 6214 3168 5031 1540 4563 1146 959 169 2206 4093 855 2189 2810 4044 4858 691 2313 4735 4541 3893 377 5499 1430 3750 2784 4189 937 5891 4146 1693 4503 6614 5682 2520 4923 5258 1362 6174 173 4110 100 1311 3516 5497 1699 2123 760 2276 543 4341 5387 2398 1726 5264 3991 3913 1480 6046 1838 4716 309 1015 4209 1154 3596 3053 6383 6075 1063 5726 6408 2598 4164 3017 847 2493 1124 2440 3128 1357 2980 2380 4181 4329 6307 3475 5643 3214 4645 1777 4475 4607 3234 1443 825 3812 3807 3081 1003 5309 1368 937 4382 6085 2495 207 5146 2139 5703 2583 3095 1013 4798 2305 1722 4045 2154 3781 3740 1021 2914 6204 2729 5878 3617 831 1787 5163 4756 4403 534 2108 5302 5550 4779 477 5992 5826 6600 5015 917 110 2093 1912 1897 640 2105 4683 1825 2631 2008 294 6095 4914 3650 5018 4955 1586 6150 5475 65 541 3526 3039 4297 1263 5651 1770 2085 2223 2194 5066 5839 2838 5712 6114 6183 545 4441 1163 3687 4987 3906 107 2282 5500 6368 196 2629 2979 2873 5656 4050 1190 877 3583 1275 4656 4913 2532 3923 3198 2968 2577 1263 1658 3073 956 946 3525 1477 4146 6403 3738 3492 5401 2806 4174 1335 4068 6239 5436 3780 6538 4688 5015 6451 2058 145 3800 54 2991 3457 1891 1386 3700 5139 2242 4287 6411 3636 6635 276 4426 5798 2988 4226 3793 2589 3551 2591 3322 3939 2125 5518 1693 2400 6234 1934 5298 2246 817 902 696 4522 457 2947 3473 1927 5149 5702 4109 5170 589 86 5601 4494 3149 63 6137 3488 862 2276 6490 2892 1557 3578 2391 2160 5493 1754 2414 2279 5758 1117 3560 3863 3223 6616 5611 932 2423 4098 6502 5704 4880 4306 2132 5709 1660 670 5594 1652 701 5059 1117 354 1022 3814 2101 4390 5821 2910 2780 458 4014 6568 1151 3169 6135 37 6171 6507 4394 1366 4325 1699 6364 6640 5700 3818 1076 1125 5227 2498 1424 3536 420 6594 4052 4718 4301 6275 4862 3954 4155 5379 387 1809 1677 204 751 1612 2201 3376 3401 4219 4323 3080 871 4384 434 913 6462 3765 5423 6597 6501 4625 3857 3555 2691 3498 4252 2132 856 4991 2182 5048 2247 3795 3811 3325 4140 1528 5633 18 5251 5737 4623 1223 1758 909 261 2161 1956 3208 2583 2176 2643 1779 2505 381 6571 1751 2223 497 2343 4572 2807 2814 6312 2327 2800 2608 3173 894 4870 4715 5386 5406 4741 3910 1456 5822 4626 6653 5956 5354 2340 6138 4403 2477 1363 138 3216 5330 4662 4897 331 3259 4674 1596 6622 6111 5858 5451 4586 4646 1909 4929 6510 993 2079 1099 2989 4077 6332 5661 2998 6508 1950 4565 2615 733 4441 57 4801 519 193 3306 820 5250 5940 618 2329 4845 6547 5891 335 0 1190 3860 6608 629 2983 6115 4435 1158 3405 4943 5437 3197 1506 1591 292 2904 805 4327 2514 4819 4931 2814 1027 5566 1392 5342 5597 5360 1560 6345 4549 2787 5835 4278 4821 2642 1294 4229 1592 3998 3962 2896 454 432 2386 2899 2351 1585 2713 408 5722 6199 3936 1166 6285 3613 5518 6347 103 3456 2770 1307 5059 221 3685 3281 3819 5956 2795 5929 3886 6330 381 5380 697 3488 6103 3250 5700 2569 2794 5822 2776 2723 3554 2451 1602 2765 5420 2428 2592 4842 3307 4946 1373 803 5 5058 5182 2234 764 448 5137 2420 4446 3 2721 1048 1263 5888 3611 2977 5619 1364 2022 111 4721 4871 4624 2992 2151 37 406 4461 1713 1527 3067 2640 2071 3869 6039 5711 2109 3815 2296 4210 288 5855 6402 425 5816 3327 1534 4640 713 6535 2896 4779 1571 5288 1380 4396 5351 5095 5605 2210 6033 3133 5068 1462 4922 2781 5825 2507 109 4406 5617 987 2690 5560 506 2907 3848 956 3636 3554 5416 3815 5660 2450 2166 5571 5952 2427 4990 4616 4572 1388 3456 1365 2495 2899 3062 3574 5793 5734 3089 1253 6510 6214 5154 754 3327 601 1849 201 4014 1094 4836 2374 3647 4519 5725 2019 3247 3854 2358 6044 6202 766 1568 6618 1626 4367 4301 4336 3958 1971 6471 2273 4898 427 4447 3164 2209 5185 5989 6185 2606 4044 3838 2148 3222 5060 3414 3728 2824 1125 4419 3518 5125 3081 6035 4846 5665 4728 40 3287 2995 5557 1125 2830 6084 757 3277 72 2574 1375 3885 4001 1007 2887 4422 3499 6364 2700 722 2770 4443 3449 6257 3625 2153 1561 5302 5988 6141 5060 630 2073 2041 2508 5576 6156 782 6612 3098 6475 3517 850 2163 5437 2551 3549 6475 817 4125 3158 5544 2242 666 3835 943 5025 2543 2506 4281 2662 6257 4789 6385 2478 1522 5478 5047 1219 4923 5918 810 1302 5478 239 2335 2417 5730 3578 3643 4694 1589 1498 1390 2463 6272 1825 1120 3974 1459 2811 6627 4808 5625 5850 327 6149 2263 5732 6148 5331 4801 3168 111 2091 2763 2868 2218 2900 5234 1674 1062 5397 37 898 6488 3719 3489 6199 1838 258 3140 984 5899 1941 4449 5688 3167 6620 5250 2029 4998 4004 5454 2887 1465 2228 2583 388 4343 4455 1531 5315 4692 4871 3989 546 3225 330 5411 3730 6533 4879 207 4712 5457 6542 6068 695 4298 4122 6519 4611 3683 259 5947 6299 4343 5358 3263 5331 984
stdout
3961