Thuê Máy Chủ Đám Mây

Buổi 37 — Convex Hull Trick greedy
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một hệ thống cần xử lý $N$ tác vụ theo đúng thứ tự từ $1$ đến $N$. Tác vụ thứ $i$ có thời lượng $a_i > 0$.

Các tác vụ được gom thành các lô liên tiếp. Nếu một lô gồm các tác vụ có tổng thời lượng là $S$, chi phí xử lý lô đó là $S^2 + C$, trong đó $C$ là chi phí khởi tạo cố định cho mỗi lô. Hãy chia $N$ tác vụ thành một hoặc nhiều lô liên tiếp sao cho tổng chi phí xử lý tất cả các lô là nhỏ nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $C$ ($1 \le N \le 10^5$, $0 \le C \le 10^{12}$).
  • Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^4$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
Input Output
4 5
1 2 3 4
49
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le C \le 10^{12}$, $1 \le a_i \le 10^4$
Draft saved