[QNOI 2015] Xếp lịch

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M

Tác giả:
Dạng bài

Một giáo viên cần giảng \(N\) vấn đề được đánh số từ \(1\) đến \(N\ (N\leq1000)\). Mỗi một vấn đề \(i\) có thời gian là \(A_i\ (i=1..N)\). Mỗi vấn đề chỉ giảng không quá \(1\) buổi. Thời gian tối đa của một buổi là \(L\ (L\leq500)\). Vấn đề \(i\) phải được giảng trước vấn đề \(i+1\).

Trong một buổi có thể bố trí giảng vài vấn đề nhưng nếu thừa lượng thời gian \(t\) thì buổi đó được đánh giá là lãng phí thời gian với mức \(d= \left\{ \begin{array}{ll} 0,\ t=0\\ -c,\ 1\leq t\leq10 \\ (t-10)^2,\ t>10 \end{array} \right.\)

Trong đó \(c\) là hằng số nguyên dương cho trước.

Yêu cầu: Hãy xếp lịch dạy sao cho số buổi dạy ít nhất và tổng các lãng phí thời gian là nhỏ nhất có thể được.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\ (N\leq1000)\);
  • Dòng thứ hai chứa số nguyên dương \(L\) và \(C\);
  • Dòng thứ ba chứa \(N\) số nguyên dương \(A_1,\ A_2,\ldots,\ A_N\).

Output

  • Dòng đầu tiên in ra một số nguyên là số buổi của lịch dạy tối ưu;
  • Dòng thứ hai in ra một số nguyên là tổng thời gian lãng phí ít nhất đạt được.

Ví dụ

Sample input
10
120 10
80 80 10 50 30 20 40 30 120 100
Sample output
6
2700