CHECKPOINT - Đánh giá hiệu quả làm việc
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: admin

Một công ty kinh doanh tiến hành đánh giá hiệu quả làm việc của nhân viên A (check point) dựa trên tình hình doanh thu và chi phí của họ theo thời gian trong 1 giai đoạn công tác. Một giai đoạn công tác bao gồm một chuỗi các ngày làm việc được đánh số 1, 2, ..., N. Ngày làm việc thứ i của nhân viên A được đặc trưng bởi 1 con số (doanh thu hoặc chi phí) ai trong đó ai>0 có nghĩa ngày đó nhân viên thu được lượng tiền là ai (doanh thu), ai < 0 có nghĩa nhân viên cần chi tiêu một khoản −ai (chi phí). Hiệu quả làm việc của nhân viên A được đo bằng tổng lợi nhuận (tổng doanh thu - tổng chi phí) lớn nhất thu được trong số các chuỗi gồm một số liên tiếp các ngày mà trong đó có không quá K ngày nhân viên phải chi tiêu.

Ví dụ: giai đoạn kinh doanh gồm 9 ngày, trong đó lượng thu, chi của nhân viên được mô tả bởi dãy gồm 9 số: 100, -1, -2, -3, 60, -4, -5, 50, -10. Việc thu chi được thể hiện trong Bảng 1

        Ngày   1   2   3   4   5   6   7   8   9
        Thu   100             60          50
        Chi        1   2   3       4   5      10

                              Bảng 1: Tình hình thu và chi của nhân viên A

Yêu cầu: cho giá trị N, K và dãy a1, ..., aN. Hãy tính hiệu quả công việc của nhân viên A.

Dữ liệu vào

- Dòng thứ nhất chứa 2 số nguyên dương NK (1 ≤ N ≤ 105 , 0 ≤ K ≤ 100)
- Dòng thứ 2 chứa N số nguyên a1, . . . , aN

Kết quả

Ghi ra một số nguyên là hiệu quả làm việc của nhân viên A

Ví dụ

Input

9 2
100 -1 -2 -3 60 -4 -5 50 -10

Output

101

Giải thích Hiệu quả công việc là tổng lợi nhuận thu được trong giai đoạn 4 ngày: 5, 6, 7, 8 và bằng 60 - 4 - 5 + 50 = 101.

 


Nguồn: ĐPT 20172018

Back to Top