Elearning CodePath – CTP Online Judge

Đánh giá hiệu quả làm việc

CHECKPOINT

🟢 Hard #Two Pointers #Priority Queue #Data Structure

### 📌 Thông tin chung

---
### 📝 Bài toán

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 dựa trên tình hình doanh thu và chi phí của họ theo thời gian trong một 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 một con số ai (doanh thu hoặc chi phí):
- 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 ngày đó 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.

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

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file văn bản CHECKPOINT.INP:
- Dòng thứ nhất chứa hai số nguyên dương N và K (1 <= N <= 10^5, 0 <= K <= 100).
- Dòng thứ hai chứa N số nguyên a1, a2, ..., an (|ai| <= 10^9).

### 📤 Định dạng Đầu ra

Ghi ra file văn bản CHECKPOINT.OUT một số nguyên duy nhất là hiệu quả làm việc lớn nhất của nhân viên A.

### ✨ Ví dụ

| CHECKPOINT.INP | CHECKPOINT.OUT |
| :--- | :--- |
| 9 2 | 101 |
| 100 -1 -2 -3 60 -4 -5 50 -10 | |

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.

### 🏷 Subtasks

Subtask 1 (40%): N <= 1000, K <= 10.
Subtask 2 (60%): N <= 10^5, K <= 100.

✅ Đã AC: 2 / 8 submissions