ĐOẠN CON CÓ TỔNG LỚN NHẤT
Xem dạng PDFCho dãy số ~a_1, a_2, ..., a_N~ và dãy số ~b_1, b_2, ..., b_N~ trọng số của một đoạn con ~[l, r]~ là ~a_l + a_{l + 1} + ... + a_r~. Giá trị của cả dãy là trọng số lớn nhất của một đoạn con bất kỳ. Bạn được phép thực hiện thao tác sau tối đa ~k~ lần: Chọn hai chỉ số ~x, y~ ~(x≤y)~ với mỗi ~x≤i≤y~ gán ~a_i = a_i \times b_i~.
Yêu cầu: Hãy thực hiện không quá ~k~ thao tác để giá trị của dãy là lớn nhất.
Input
Gồm ba dòng:
- Dòng đầu tiên là hai số nguyên ~N~ và ~k~ ~(1≤N≤10^5, 1≤k≤10).~
- Dòng thứ hai là dãy số ~a_1, a_2, ..., a_N~ ~(|a_i|≤1000).~
- Dòng thứ ba là dãy số ~b_1, b_2, ..., b_N~ ~(|b_i|≤10).~
Output
Gồm một số nguyên duy nhất là giá trị của dãy ~a~ sau khi thực hiện không quá ~k~ thao tác.
Scoring
Subtask 1: Có ~15~% số test ứng với ~k = 0~.
Subtask 2: Có ~15~% số test khác ứng với ~k = 1~ và ~n ≤ 5000~.
Subtask 3: Có ~20~% số test khác ứng với ~k = 1~.
Subtask 4: Có ~25~% số test khác ứng với ~k = 2~.
Subtask 5: ~25~% số test còn lại không có ràng buộc gì thêm
Sample Input 1
5 1
-3 4 -5 2 -2
1 -2 -1 2 1
Sample Output 1
13
Sample Input 2
3 0
-4 -10 -8
2 2 -1
Sample Output 2
-4
Bình luận
có bạn nào xài chat nộp kìa đại ca ơiii