提出 #45437738

---

ソースコード 拡げる

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
       long long n, m, mx=0;
       cin >> n >> m;
       long long a[n];
       long long b[n];
       for(int i = 0; i < n; i++){
           cin >> a[i];
           b[i] = a[i];
           mx = max(mx, a[i]);
       }
       sort(b, b + n);
       long long line = n / m + (n % m != 0);
       long long w = 0;
       for(int i = n - 1; i >= n - line; i--){
           w += (long long)b[i] + 1;
       }
       long long l = mx;
       long long r = w;
       while(l <= r){
           bool flag = true;
           long long mid = l + (r - l) / 2;
           //long long mid = (long long)10000000008;
           long long cur_sum = 0;
           int cur_line = m;
           for(int i = 0; i < n; i++){
               if(cur_sum == 0 && cur_sum + a[i] <= mid){
                   cur_sum += a[i];
               }
               else if(cur_sum + 1 + a[i] <= mid){
                   cur_sum += a[i] + 1;
               }
               else{
                   cur_line--;
                   if(cur_sum == 0 || cur_line == 0){
                       flag = false;
                       break;
                   }
                   cur_sum = a[i];
               }
           }
           if(flag == true){
               w = mid;
               r = mid - 1;
           }
           else{
               l = mid + 1;
           }
       }
       cout << w;

    }
    return 0;
}

提出情報

ジャッジ結果