Elearning CodePath – CTP Online Judge

Dãy con tăng tổng quát

INCWSEQ

🟢 Easy #Dynamic Programming #Segment Tree #Fenwick Tree

### 📌 Thông tin chung

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

Cho dãy số nguyên dương $A = (A_1, A_2, \dots, A_N)$. Phần tử $A_i$ có trọng số $W_i$.

Một dãy $A_{i_1}, A_{i_2}, \dots, A_{i_k}$ thỏa mãn:
$1 \le i_1 < i_2 < \dots < i_k \le N$
và
$A_{i_1} < A_{i_2} < \dots < A_{i_k}$
được gọi là một **dãy con tăng** của dãy $A$. Dãy chỉ gồm duy nhất một phần tử của $A$ cũng được gọi là một dãy con tăng của $A$.

Yêu cầu: Trong các dãy con tăng của $A$, hãy chỉ ra một dãy có **tổng trọng số lớn nhất** có thể.

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

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

* Dòng 1: Chứa số nguyên dương $N$.
* Dòng 2: Chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ (giá trị phần tử) theo đúng thứ tự đó.
* Dòng 3: Chứa $N$ số nguyên dương $W_1, W_2, \dots, W_N$ (trọng số tương ứng) theo đúng thứ tự đó.

Giới hạn (Không được cho rõ, giả định theo mức độ phức tạp phổ biến):
* $1 \le N \le 10^5$.
* $1 \le A_i \le 10^9$.
* $1 \le W_i \le 10^9$.

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

Ghi ra file `INCWSEQ.OUT`:

* Dòng 1: Ghi số phần tử của dãy con tìm được ($k$).
* Dòng 2: Ghi $k$ chỉ số $i_1, i_2, \dots, i_k$ của các phần tử được chọn theo thứ tự tăng dần.

Các số trên một dòng của Input/Output được/phải ghi cách nhau ít nhất một dấu cách.

---
### ✨ Ví dụ

| Input (`INCWSEQ.INP`) | Output (`INCWSEQ.OUT`) |
| :--- | :--- |
| `10` <br> `1 2 3 6 4 5 9 6 7 8` <br> `11 22 33 66 44 55 999 66 77 88` | `6` <br> `1 2 3 5 6 7` |

Giải thích:
* Dãy $A$: $(1, 2, 3, 6, 4, 5, 9, 6, 7, 8)$.
* Dãy $W$: $(11, 22, 33, 66, 44, 55, 999, 66, 77, 88)$.
* Dãy con tăng được chọn có chỉ số $(1, 2, 3, 5, 6, 7)$.
    * Các giá trị: $(A_1, A_2, A_3, A_5, A_6, A_7) = (1, 2, 3, 4, 5, 9)$. (Thỏa mãn $1 < 2 < 3 < 4 < 5 < 9$).
    * Các trọng số tương ứng: $(11, 22, 33, 44, 55, 999)$.
    * Tổng trọng số: $11 + 22 + 33 + 44 + 55 + 999 = 1164$.

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions