解説そのままやってみて、時間切れのパターン。ここまでは様式美です。ここからバイナリサーチをどう使うのだろう?
現時点でひとつだけ工夫したところは、入力時の最大値を覚えておいて、そこから P を増やしていく部分です。最大値が入らない積載量の探索は意味がないですからね。
#include <iostream> #include <vector> using namespace std; static int inputArray(int A[], int num) { int max = 0; for (int i = 0; i < num; i++) { cin >> A[i]; if (A[i] > max) { max = A[i]; } } return max; } static inline int f(int A[], int num, int P, int k) { int i = 0, v = 0; for (int total = 0; (v < k) && (i < num); i++) { total += A[i]; if (total > P) { total = 0; i--; v++; } } return i; } int main() { int n, k; cin >> n >> k; vector<int> w(n); int P = inputArray(&w[0], n); for (int v = 0; v < n; P++) { v = f(&w[0], n, P, k); } cout << (P - 1) << endl; return 0; }