Chia nhóm cân bằng

Buổi 33 — Bitmask DP & SOS DP
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ công việc, công việc thứ $i$ có thời gian thực hiện là $A_i$. Bạn cần chia $N$ công việc này thành đúng $K$ nhóm không rỗng sao cho mỗi công việc thuộc đúng một nhóm. Tổng thời gian của một nhóm là tổng thời gian các công việc trong nhóm đó. Hãy tìm cách chia sao cho tổng thời gian lớn nhất trong $K$ nhóm là nhỏ nhất có thể.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $K$ ($1 \le K \le N \le 16$).
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
Dữ liệu ra
  • In ra một số nguyên duy nhất là giá trị lớn nhất nhỏ nhất có thể của tổng thời gian một nhóm.
Ví dụ
Input Output
5 3
1 2 3 4 5
5
4 2
10 20 30 40
50
Giới hạn
  • $1 \le K \le N \le 16$
  • $1 \le A_i \le 10^9$
Draft saved