Overview

This problem asks for the minimum number of days required to make all fields harvestable (i.e., assign at least \(D_i\) units of work to each field \(i\)). Although it may appear to be a complex scheduling problem at first glance, because there is a high degree of freedom in assigning workers, it can actually be solved with a very simple formula.

Analysis

1. Consider the lower bound on the minimum number of days

Let \(S\) be the total required work across all fields needed to make them all harvestable. $\(S = \sum_{i=1}^{N} D_i\)$

The total amount of work that all workers can complete in one day is exactly \(M\). Since workers cannot rest, the total work progress across all farms each day is always \(M\).

Therefore, the minimum number of days required is at least: $\(\lceil S / M \rceil \text{ days} \quad \text{(the smallest integer greater than or equal to } S / M \text{, i.e., ceiling)}\)$

2. Can this number of days actually be achieved?

Because of the condition that “workers can be freely assigned,” it is actually possible to proceed without generating any wasted work.

The intuition is like lining up cells of lengths \(D_1, D_2, \ldots, D_N\) in a row, and stamping \(M\) cells from the front each day.

• Day 1: Assign workers starting from field 1. Once field 1’s target \(D_1\) is reached, assign the remaining workers to field 2. Once field 2 is also reached, move to field 3… and so on, assigning a total of \(M\) workers sequentially.
• Day 2: Continue assigning workers from where day 1 left off, in the same manner.

With this approach (a greedy method), we can consume exactly \(M\) units of required work every day (except possibly the last day), without wasting any work on fields that have already become harvestable.

On the last day alone, the remaining required work may be less than \(M\), but in that case, we can simply assign the surplus workers to fields that are already completed, so there is no problem.

Therefore, the minimum number of days required is exactly “the total work \(S\) divided by \(M\), rounded up.”

Algorithm

1. Compute the sum \(S\) of the required work \(D_i\) for all fields.
2. Compute \(\lceil S / M \rceil\), the value of \(S\) divided by \(M\) rounded up.
   • In programming, ceiling division of positive integers \(S, M\) can be computed using integer arithmetic with the formula (S + M - 1) / M.
3. Output the computed value as the answer.

Complexity

• Time Complexity: \(O(N)\) We simply read \(N\) inputs sequentially and compute their sum, so it runs in linear time with respect to the number of fields \(N\). This is sufficiently fast for the constraint \(N \le 10^6\).

• Space Complexity: \(O(1)\) There is no need to store the \(D_i\) values in an array; we can accumulate the sum as we read each input, so no extra memory is needed.

Implementation Notes

• Overflow prevention Since \(N \le 10^6\) and \(D_i \le 10^9\), the sum \(S\) can reach up to \(10^{15}\). This far exceeds the maximum value of a typical 32-bit integer type (such as int in C++, which is approximately \(2 \times 10^9\)), so be sure to use a 64-bit integer type (long long in C++).

• Fast I/O Since \(N\) can be as large as \(10^6\), in C++ it is advisable to use cin.tie(nullptr) and ios_base::sync_with_stdio(false) to speed up input/output.

  Source Code

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    if (!(cin >> n >> m)) return 0;

    long long sum_d = 0;
    for (int i = 0; i < n; ++i) {
        long long d;
        cin >> d;
        sum_d += d;
    }

    long long ans = (sum_d + m - 1) / m;
    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.