Elearning CodePath – CTP Online Judge

Thả xốp

SPONGE

🟢 Medium #Priority Queue #Data Structure

### 📌 Thông tin chung

### Bài toán

Có $N$ hạt xốp, hạt thứ $i$ có khối lượng $w_i$. Các hạt xốp được thả lần lượt theo thứ tự từ $1$ đến $N$ vào một ống nước đặc biệt.

Cơ chế của ống nước như sau:
Tại mỗi thời điểm, chỉ có duy nhất một hạt xốp nhẹ nhất nổi lên trên bề mặt. Trước khi thả hạt xốp tiếp theo vào ống, hạt xốp đang nổi trên bề mặt sẽ bị ngấm nước và tăng gấp đôi khối lượng.

Yêu cầu: Tính tổng khối lượng xốp đã tăng thêm so với tổng khối lượng ban đầu sau khi hạt xốp cuối cùng được thả vào ống.

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

Dữ liệu vào từ file SPONGE.IN:
* Dòng 1: Số nguyên dương $N$.
* Dòng 2: $N$ số nguyên dương $w_1, w_2, \dots, w_n$ là khối lượng ban đầu của các hạt xốp.

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

Ghi ra file SPONGE.OUT một số nguyên duy nhất là tổng khối lượng tăng thêm.

### Ví dụ

| SPONGE.IN | SPONGE.OUT |
| :--- | :--- |
| 3 <br> 2 1 3 | 3 |

Giải thích ví dụ:
- Bước 1: Thả hạt 2. Hạt nổi là 2.
- Bước 2: Trước khi thả hạt 1, hạt 2 tăng gấp đôi: $2 \times 2 = 4$. Khối lượng tăng thêm: 2. Lúc này trong ống có {4, 1}. Hạt nổi là 1.
- Bước 3: Trước khi thả hạt 3, hạt 1 tăng gấp đôi: $1 \times 2 = 2$. Khối lượng tăng thêm: 1. Lúc này trong ống có {4, 2, 3}.
- Tổng tăng thêm: $2 + 1 = 3$.

### Subtasks

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

✅ Đã AC: 6 / 9 submissions