fork download
copy 
  1. n, m = map(int, input().split())
  2. money_need = []
  3. for i in range(n):
  4.     money_need.append(int(input()))
  5. def run_case(money_reset):
  6.     times = 1
  7.     left_money = money_reset
  8.     for i in money_need:
  9.         if i > left_money:
  10.             times += 1
  11.             left_money = money_reset - i
  12.         else:
  13.             left_money -= i
  14.     return times
  15.  
  16. def lower_bound():
  17.     low = 0
  18.     high = sum(money_need)
  19.     ans = 0
  20.     while low <= high:
  21.         mid = (low + high) // 2
  22.         if run_case(mid) == m:
  23.             ans = mid
  24.             high = mid - 1
  25.             # print(1, low, high, mid, ans, run_case(mid))
  26.         elif run_case(mid) < m:
  27.             high = mid - 1
  28.             # print(2, low, high, mid, ans, run_case(mid))
  29.         elif run_case(mid) > m:
  30.             low = mid + 1
  31.             # print(3, low, high, mid, ans, run_case(mid))
  32.     # print(1)
  33.     return ans
  34. print(lower_bound())
Success #stdin #stdout 0.04s 9808KB
comments (?)
stdin
copy 
2 2
500
501
stdout
copy 
500
https://ideone.com/TLaInN
language:
Python 3 (python  3.12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!