Elearning CodePath – CTP Online Judge

Tối ưu hóa điểm số

MAXSCORE

🟢 Easy #Greedy #Priority Queue #Data Structure

### 📌 Thông tin chung

### Bài toán

Cho dãy $A$ gồm $3 \times N$ phần tử. Bạn cần xóa đúng $N$ phần tử khỏi dãy $A$ để thu được dãy mới $A'$ có độ dài $2 \times N$.

Điểm số của dãy $A'$ được tính bằng:
$$Điểm = (Tổng\ N\ phần\ tử\ đầu\ của\ A') - (Tổng\ N\ phần\ tử\ cuối\ của\ A')$$

Yêu cầu: Tìm cách xóa $N$ phần tử sao cho điểm số của dãy $A'$ đạt giá trị lớn nhất có thể.

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

Dữ liệu vào từ file MAXSCORE.INP:
* Dòng 1: Số nguyên dương $N$.
* Dòng 2: Gồm $3 \times N$ số nguyên $A_1, A_2, \dots, A_{3N}$.

### Giới hạn

* $1 \le N \le 10^5$.
* $1 \le A_i \le 10^9$.

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

Ghi ra file MAXSCORE.OUT một số nguyên duy nhất là điểm số lớn nhất tìm được.

### ✨ Ví dụ

| MAXSCORE.INP | MAXSCORE.OUT | Giải thích |
| :--- | :--- | :--- |
| 2 6 2 7 4 3 8 | 6 | Xóa phần tử thứ 2 (giá trị 2) và thứ 6 (giá trị 8). Dãy $A' = [6, 7, 4, 3]$. Điểm = (6+7) - (4+3) = 6. |
| 1 4 5 3 | 2 | Xóa phần tử thứ 1 (giá trị 4). Dãy $A' = [5, 3]$. Điểm = 5 - 3 = 2. |

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $N \le 7$ | 30% |
| 2 | $N \le 1000$ | 30% |
| 3 | $N \le 10^5$ | 40% |

✅ Đã AC: 2 / 5 submissions