Phân chia công việc với chi phí chuyển đổi

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Trong $N$ ngày liên tiếp, mỗi ngày bạn phải chọn thực hiện một trong hai dự án: dự án A hoặc dự án B. Nếu chọn dự án A vào ngày thứ $i$, bạn nhận được lợi nhuận $A_i$; nếu chọn dự án B, bạn nhận được $B_i$.

Tuy nhiên, nếu vào ngày $i$ ($i \ge 2$) bạn làm dự án khác với ngày $i-1$, bạn sẽ phải trả thêm chi phí chuyển đổi là $K$. Ngày đầu tiên chọn dự án nào cũng không mất phí chuyển đổi. Hãy tìm tổng lợi nhuận lớn nhất có thể đạt được sau $N$ ngày.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le N \le 10^5$, $0 \le K \le 10^9$).
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^9$).
  • Dòng thứ ba chứa $N$ số nguyên $B_1, B_2, \dots, B_N$ ($0 \le B_i \le 10^9$).
Dữ liệu ra
  • In ra tổng lợi nhuận lớn nhất có thể đạt được.
Ví dụ
Input Output
4 3
5 2 8 4
3 9 1 7
21
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le K, A_i, B_i \le 10^9$
Draft saved