UVa11413 Fill the Containers

問題
http://uva.onlinejudge.org/external/114/11413.html

概要

解法

#include <bits/stdc++.h>
using namespace std;

#define LLINF (LONG_LONG_MAX/4)

#define ALL(c) (c).begin(), (c).end()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;

int N, M;
vector<ll> vessel;

bool eval(ll x) {
  
  int c_cnt = 1;
  ll sum = 0;
  rep(i, N) {
    if(sum + vessel[i] > x) {
      c_cnt ++;
      sum = 0;
    }
    sum += vessel[i];
  }
  
  return c_cnt <= M;
}

int main() {
  
  while(cin >> N >> M) {
    
    vessel.resize(N);
    rep(i, N) cin >> vessel[i];
    
    ll l = *max_element(ALL(vessel)), r = LLINF;
    
    rep(i, 100) {
      ll mid = (l+r)/2;
      if(eval(mid)) {
        r = mid;
      }
      else {
        l = mid;
      }
    }
    
    cout << r << endl;
    
  }
  
  return 0;
}