Trang Trí Đèn Lồng
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion