Phân Trang

View as PDF

Submit solution


Points: 0.13 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Ðề thi chọn đội tuyển quốc gia 99
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Văn bản là một dãy gồm ~N~ từ, đánh số từ ~1~ đến ~N~. Từ thứ ~i~ có độ dài là ~w_i~ ~(i = 1~, ~2~, ...~N)~. Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng có độ dài ~L~, sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá ~L~. Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số ~(L-S)~, trong đó ~S~ là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng. Tìm cách phân trang với hệ số phạt nhỏ nhất.

Input

  • Dòng ~1~ chứa ~2~ số nguyên dương ~N~, ~L~ ~(N \le 6000~, ~L \le 1000)~
  • Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa số nguyên dương ~w_i~ ~(w_i \le L)~, ~i = 1~, ~2~, ..., ~N~

Output

  • In ra hệ số phạt nhỏ nhất

Sample Input

4 5
3
2
2
4

Sample Output

2

Comments

Please read the guidelines before commenting.



  • 6
    Duy_e   commented on May 29, 2021, 10:14 p.m.

    :< thì ra là làm tuần tự