Bài 15.5. Phân Bổ Nhiệm Vụ Tối Ưu - [Độ khó: Khó]

Trong một công ty phần mềm, bạn là người quản lý dự án và đang đối mặt với việc phân bổ N nhiệm vụ cho K công nhân. Mỗi nhiệm vụ i có một "độ phức tạp" P_i nhất định. Các nhiệm vụ được sắp xếp theo thứ tự ưu tiên và phải được thực hiện theo đúng trình tự đó. Mỗi công nhân sẽ được giao một chuỗi các nhiệm vụ liên tiếp trong danh sách tổng thể. Mục tiêu của bạn là phân chia các nhiệm vụ sao cho tổng độ phức tạp lớn nhất mà một công nhân phải xử lý là nhỏ nhất có thể.

Ví dụ: nếu có 5 nhiệm vụ [10, 20, 30, 40, 50] và 3 công nhân. Cách chia 1: [10], [20, 30], [40, 50]. Tổng phức tạp của từng công nhân: 10, 50, 90. Max = 90. Cách chia 2: [10, 20], [30, 40], [50]. Tổng phức tạp của từng công nhân: 30, 70, 50. Max = 70. Cách chia 3: [10, 20, 30], [40], [50]. Tổng phức tạp của từng công nhân: 60, 40, 50. Max = 60.

Bạn cần tìm giá trị nhỏ nhất của "độ phức tạp lớn nhất" này.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên N (1 <= N <= 10^5) và K (1 <= K <= N) – lần lượt là số lượng nhiệm vụ và số lượng công nhân. Dòng thứ hai chứa N số nguyên P_0, P_1, ..., P_{N-1} (1 <= P_i <= 10^9) – độ phức tạp của từng nhiệm vụ.

OUTPUT FORMAT

In ra một số nguyên duy nhất – giá trị nhỏ nhất của tổng độ phức tạp lớn nhất mà một công nhân phải xử lý.

Ví dụ 1:

Input:

5 3
10 20 30 40 50

Output:

60

Giải thích:

• N=5 nhiệm vụ, K=3 công nhân. Độ phức tạp: [10, 20, 30, 40, 50].
• Phân chia tốt nhất để tổng phức tạp lớn nhất là nhỏ nhất là:
  • Công nhân 1: nhiệm vụ [10, 20, 30] (tổng = 60)
  • Công nhân 2: nhiệm vụ [40] (tổng = 40)
  • Công nhân 3: nhiệm vụ [50] (tổng = 50)
• Tổng độ phức tạp lớn nhất mà một công nhân phải xử lý trong trường hợp này là max(60, 40, 50) = 60. Không có cách chia nào khác có thể đạt được tổng lớn nhất nhỏ hơn 60.

Ví dụ 2:

Input:

3 1
100 200 300

Output:

600

Giải thích:

• N=3 nhiệm vụ, K=1 công nhân.
• Một công nhân phải làm tất cả các nhiệm vụ. Tổng độ phức tạp là 100 + 200 + 300 = 600.

Ví dụ 3:

Input:

4 4
1 2 3 4

Output:

4

Giải thích:

• N=4 nhiệm vụ, K=4 công nhân.
• Mỗi công nhân có thể làm 1 nhiệm vụ.
  • Công nhân 1: [1] (tổng = 1)
  • Công nhân 2: [2] (tổng = 2)
  • Công nhân 3: [3] (tổng = 3)
  • Công nhân 4: [4] (tổng = 4)
• Tổng độ phức tạp lớn nhất là max(1, 2, 3, 4) = 4. Đây là giá trị nhỏ nhất có thể.