Bedao Regular Contest 05 - FACTORY

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.