Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTRANG - Phân Trang

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à wi (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<=6000,L<=1000)
  • Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương wi (wi<=L), i=1, 2,.., N

Output

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

Ví dụ

Input:
4 5
3
2
2
4
Output:
2 

Được gửi lên bởi:sieunhan
Ngày:2008-07-21
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ADA95 CLPS LISP sbcl LISP clisp D ERL FORTRAN GOSU HASK ICON ICK JS-RHINO LUA NEM NICE NODEJS OCAML PERL6 PERL PHP PIKE PRLG-swi PYPY RUST SCM qobi SCM guile SED ST VB.NET WHITESPACE
Nguồn bài:Đề thi chọn đội tuyển quốc gia 99

hide comments
2018-08-21 03:55:24
6 10
(7 2) (3 6) (5 4)
test này phải ra 1 chứ sao ra 7 dc nhỉ????
2017-11-01 16:58:56
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/247/ptrang-spoj/



2017-09-27 09:43:29
Code đã AC: http://123link.top/Phantrang
2017-09-22 09:45:38
Code AC: http://shink.in/JtcaL
2017-08-10 08:27:53
DP không cout << ans mà cout << A[N] vẫn AC :D
2017-04-07 11:43:05
ai giải thích đề này với ạ.
2016-12-31 04:23:05
trâu AC :)))
2016-09-30 14:11:07
Test yếu quá, không có dòng nào = L hêt.
2016-06-14 05:48:17 xin đừng quên tôi
Tham khảo thuật toán và code tại: http://yeulaptrinh.pw/247/ptrang-spoj/
2015-12-12 10:59:04
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/16/phan-trang-ptrang/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.