Lịch Trình Lợi Nhuận

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

Bạn bắt đầu kinh doanh vào ngày $0$ với số vốn ban đầu là $C$ đồng. Có $N$ chiếc máy được rao bán trong khoảng thời gian từ ngày $1$ đến ngày $D$.

Chiếc máy thứ $i$ chỉ được bán duy nhất vào ngày $d_i$ với giá mua $p_i$. Nếu mua được nó, bạn có thể bán lại nó vào bất kỳ ngày $t > d_i$ nào với giá $r_i$ ($r_i \le p_i$), đồng thời mỗi ngày từ $d_i + 1$ đến $t - 1$ (tức là $t - d_i - 1$ ngày trọn vẹn), chiếc máy sinh ra lợi nhuận $g_i$ đồng/ngày.

Tại mỗi thời điểm bạn chỉ có thể sở hữu tối đa một chiếc máy (muốn mua máy mới vào ngày $d_i$, bạn phải bán chiếc máy đang giữ trước đó vào ngày $d_i$ hoặc sớm hơn, rồi dùng tổng số tiền hiện có để mua). Vào cuối cùng ở ngày $D + 1$, nếu đang giữ máy bạn phải bán nó đi.

Hãy tìm số tiền lớn nhất bạn có thể sở hữu vào ngày $D + 1$.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, C, D$ ($1 \le N \le 10^5$, $0 \le C \le 10^9$, $1 \le D \le 10^6$).
  • $N$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $d_i, p_i, r_i, g_i$ ($1 \le d_i \le D$, $1 \le r_i \le p_i \le 10^9$, $1 \le g_i \le 10^6$).
Dữ liệu ra
  • Một số nguyên duy nhất là số tiền lớn nhất có được vào ngày $D + 1$.
Ví dụ
Input Output
3 10 10
2 10 5 3
6 12 8 5
4 8 4 2
30
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le D \le 10^6$, $1 \le g_i \le 10^6$
Draft saved