ccbeginner

UVa Q907

Dec 11th, 2019
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dis[601];
  5.  
  6. int32_t main(){
  7.     int n,k,sum = 0;
  8.     while(cin >> n >> k){
  9.         ++k;
  10.         for(int i = 0; i <= n; ++i){
  11.             cin >> dis[i];
  12.             sum += dis[i];
  13.         }
  14.         int small = 0, big = sum;
  15.         while(small <= big){
  16.             int mid = (small + big) / 2;
  17.             int days, idx = 0;
  18.             for(days = 0; days <= k && idx <= n; ++days){
  19.                 sum = 0;
  20.                 while(idx <= n && sum+dis[idx] <= mid){
  21.                     sum += dis[idx];
  22.                     ++idx;
  23.                 }
  24.             }
  25.             if(days <= k)big = mid - 1;
  26.             else small = mid + 1;
  27.         }
  28.         cout << small << '\n';
  29.     }
  30.     return 0;
  31. }
RAW Paste Data