Trang Trí Đèn Lồng

Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có $N$ vị trí treo đèn lồng dọc theo một con phố, đánh số từ $1$ đến $N$. Vị trí thứ $i$ có độ sáng $a_i$ và loại đèn $t_i \in {0, 1}$.

Bạn cần chọn một tập hợp các vị trí để treo đèn sao cho:

  • Nếu chọn hai vị trí liên tiếp trong tập được chọn là $j < i$, thì $i - j \ge K$ và $t_i \neq t_j$ (hai đèn liên tiếp được chọn phải khác loại và cách nhau ít nhất $K$ vị trí).
  • Tổng độ sáng của các đèn được chọn là lớn nhất.
Dữ liệu vào
  • Dòng đầu tiên gồm hai số nguyên $N, K$ ($1 \le K \le N \le 10^5$).
  • Dòng thứ hai gồm $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^9$).
  • Dòng thứ ba gồm $N$ số nguyên $t_1, t_2, \dots, t_N$ ($t_i \in {0, 1}$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng độ sáng lớn nhất có thể đạt được.
Ví dụ
Input Output
5 2
4 8 5 7 6
0 1 0 1 0
14
Giới hạn
  • $1 \le K \le N \le 10^5$
  • $1 \le a_i \le 10^9$
Draft saved