Overview

This problem asks you to find the total amount of work needed to make all fields harvestable, and then calculate the minimum number of days required based on the total work capacity \(M\) that all workers can complete per day.

Analysis

At first glance, it might seem like you need to devise a complex schedule determining “which day, which field, and how many workers to assign,” but by organizing the problem’s conditions, you can think about it very simply.

1. Total required work To make each field \(i\) harvestable, at least \(D_i\) units of work must be assigned to field \(i\). Therefore, the total work required across the entire farm is the sum of the required work for each field: \(S = \sum_{i=1}^N D_i\).

2. Work capacity per day There are \(M\) workers, and all of them must be assigned to some field. Since each worker completes \(1\) unit of work per day, the entire farm produces exactly \(M\) units of work every day.

3. Lower bound on the number of days Let the required number of days be \(X\). The total work that can be completed in \(X\) days is \(X \times M\). Since this must be at least the total required work \(S\), the following inequality holds: $\(X \times M \geq S \implies X \geq \frac{S}{M}\)\( Since the number of days \)X\( must be an integer, the minimum number of days required is the ceiling of \)\frac{S}{M}\(, i.e., \)\lceil \frac{S}{M} \rceil$ days.

4. Why this lower bound is always achievable According to the problem statement, the following flexible rules are permitted:

   • Any number of workers (up to \(M\)) can be simultaneously assigned to a single field.
   • Workers may be assigned to fields that are already harvestable (surplus work is allowed).
   • Assignments can be freely changed from day to day.

Because of this, for example, by greedily assigning work in order — \(D_1\) to field 1, \(D_2\) to field 2, and so on — carrying over to the next day any amount exceeding the daily limit \(M\), you can distribute the total work \(S\) across \(X\) days without any waste.

Therefore, there is no need to worry about the individual values of \(D_i\) in detail. You can arrive at the correct answer simply by calculating “how many days does it take to complete total work \(S\) at a rate of \(M\) per day?”

Algorithm

1. Compute the sum \(S\) of the given \(D_1, D_2, \ldots, D_N\).
2. Compute the minimum number of days \(X = \lceil S / M \rceil\).
   • To perform ceiling division using only integer types, in many programming languages you can use the expression (S + M - 1) // M.
3. Output the computed \(X\).

Complexity

• Time complexity: \(O(N)\) The bottleneck is scanning the input array once to compute the sum of \(D_i\). Since \(N \leq 10^6\), this runs sufficiently fast.
• Space complexity: \(O(N)\) \(O(N)\) memory is used to store all input in an array.

Implementation Notes

• Beware of overflow Since \(N \leq 10^6\) and \(D_i \leq 10^9\), the sum \(S\) can reach up to \(10^{15}\). In languages like C++ that use 32-bit integer types (int), overflow will occur, so you must use a 64-bit integer type (such as long long). (In Python, this is not a concern as integers are automatically handled as arbitrary-precision integers.)

• Fast I/O Since \(N\) can be large, in Python you can significantly reduce execution time by reading all input at once using sys.stdin.read.

  Source Code

import sys

def main():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # D_i の総和を計算
    total_D = sum(map(int, input_data[2:]))
    
    # 最小日数を計算
    ans = (total_D + M - 1) // M
    print(ans)

if __name__ == '__main__':
    main()

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