Xét dãy số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1 \leq a_{i} \leq n)\). Một dãy chỉ số \(1 \leq i_{1} < i_{2} < \cdots < i_{k} \leq n\) mà \(a_{i_{1}} < a_{i_{2}}\ < \ \cdots\ < \ a_{i_{k}}\) thì dãy \(a_{i_{1}},\ a_{i_{2}},\ \ldots,\ a_{i_{k}}\) được gọi là một dãy con tăng của dãy 𝑎1, 𝑎2, …, 𝑎𝑛 với độ dài của dãy là \(k\) và tổng \(a_{i_{1}},\ a_{i_{2}},\ \ldots,\ a_{i_{k}}\)được gọi là trọng số của dãy con tăng.
Yêu cầu: Cho dãy số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) và số nguyên dương \(w\), hãy tìm dãy con tăng của dãy \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) có độ dài lớn nhất và trọng số không vượt quá \(w\).
Dữ liệu:
+ Dòng đầu chứa hai số nguyên dương \(n,\ w\ (n\ \leq \ 50000)\)
+ Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1\ \leq \ a_{i}\ \leq \ n)\)
Kết quả:
+ Một số nguyên là độ dài dãy con tăng lớn nhất tìm được thỏa mãn yêu cầu.
Ví dụ
Input | Output | Input | Output | |
---|---|---|---|---|
5 10 4 2 3 1 5 | 3 | 5 5 4 2 3 1 5 | 2 |
Giới hạn: Đặt \(S\ = \ a_{1} + a_{2} + \cdots + a_{n}\ \)
+ Subtask 1: \(n \leq 20;\ w \leq \ S\);
+ Subtask 2: \(n\ \leq \ 50;\ w\ = \ S\);
+ Subtask 3: \(n\ \leq \ 50;\ w\ \leq \ S\);
+ Subtask 4: \(n\ \leq \ 500;w\ \leq \ S\);
+ Subtask 5: 𝑛 ≤ 50000; w = 𝑆;
Code tích cực |
---|
Trong 24h |
|
Trong 7 ngày |
|
Trong 30 ngày |
|
Thống kê |
---|
AC/Sub: 97887/180710 Pascal: 17121 C++: 130348 Python: 33199 Lượt xem/tải tests: 38907 |