Bedao Regular Contest 05 - FACTORY
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Ở xưởng xí nghiệp Bedao, có ~k~ người thợ và có ~n~ tấm bảng cần tô được đặt cạnh nhau, tấm bảng thứ ~i~ tô tốn mất ~a_i~ đơn vị thời gian. Tại một thời điểm, mỗi người thợ chỉ được tô một tấm bảng.
Để hoàn thành công việc này trong thời gian nhanh nhất có thể, ~k~ người thợ đã thống nhất chia ~n~ tấm bảng thành ~k~ phần phân biệt, mỗi phần gồm một hoặc một số tấm bảng bất kì trong ~n~ tấm bảng.
Dưới vai trò là một chủ xưởng xí nghiệp, bạn cần phải chia ~n~ tấm bảng thành ~k~ phần sao cho thời gian hoàn thành công việc là sớm nhất.
Input
- Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~( 1 \leq k \leq n \leq 12 )~
- ~n~ dòng tiếp theo là các số ~a_i~ là thời gian để tô tấm bảng thứ ~i~ ( ~1 \leq a_i \leq 10^3~ )
Output
- Một số nguyên là thời gian sớm nhất để hoàn thành công việc yêu cầu
Sample Input
4 3
1
5
3
5
Sample Output
5
Note
Ta có thể chia ~4~ tấm bảng thành ~3~ phần như sau: ~{[1,3],[5],[5]}~ và có thời gian hoàn thành công việc là ~5~, cũng là thời gian hoàn thành sớm nhất
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.