Elearning CodePath – CTP Online Judge

Quay Số Siêu Trúng Thưởng

ARR001

🟢 Hard #Hash #Binary Search #Set / Map

### 📌 Thông tin chung

Các bài chấm online chỉ cần dùng luồng vào/ra chuẩn
---
### 📝 Bài toán

Có một bảng điện tử gồm $N$ ô, mỗi ô hiển thị một số nguyên dương $A_i$.
Người chơi quay số $M$ lần, tạo ra dãy số $B_1, B_2, \dots, B_M$.

Quy trình:
* Sau mỗi lần quay $B_j$, tất cả các ô trên bảng điện tử có giá trị **trùng với $B_j$ sẽ bị xóa** (không còn hiển thị).
* **Tiền thưởng** của khách hàng là **tổng lớn nhất** của một loại số trong các số **còn hiển thị** trên bảng điện tử.

Yêu cầu:
1. Liệt kê các số còn hiển thị trên bảng điện tử theo **thứ tự ban đầu**.
2. Tính tổng tiền thưởng lớn nhất có thể.

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

Dữ liệu vào từ file `THUONG.INP`:

* Dòng 1: Ghi hai số nguyên dương $N$ và $M$.
* Dòng 2: Ghi $N$ số nguyên dương $A_1, A_2, \dots, A_N$.
* Dòng 3: Ghi $M$ số nguyên dương $B_1, B_2, \dots, B_M$.

Giới hạn:
* $1 \le N, M \le 3 \times 10^6$.
* $1 \le A_i, B_j \le 10^9$.

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

Ghi ra file `THUONG.OUT`:

* Dòng 1: Các số còn hiển thị trên bảng điện tử theo thứ tự ban đầu. Nếu không còn số nào, in ra `0`.
* Dòng 2: Tổng tiền thưởng lớn nhất có thể được.

---
### ✨ Ví dụ

| Input (`THUONG.INP`) | Output (`THUONG.OUT`) |
| :--- | :--- |
| `8 5` <br> `1 7 5 3 2 5 7 5` <br> `3 1 4 6 4` | `7 5 2 5 7 5` <br> `15` |

Giải thích:
* Bảng ban đầu $A = [1, 7, 5, 3, 2, 5, 7, 5]$.
* Số bị xóa (Deleted\_Set): $\{3, 1, 4, 6\}$.
* Số bị xóa khỏi $A$: $1$ và $3$.
* Số còn lại (theo thứ tự ban đầu): $[7, 5, 2, 5, 7, 5]$.
* Tiền thưởng (Tính tổng của mỗi loại số):
    * Số 7: $7 + 7 = 14$.
    * Số 5: $5 + 5 + 5 = 15$.
    * Số 2: $2$.
* Tiền thưởng lớn nhất là $15$.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N, M \le 5000$ | $30\%$ | 
| 2 | $N, M \le 3 \times 10^6$ | $70\%$ |

---

✅ Đã AC: 0 / 70 submissions