Subtask 1

Với $n,q\le 20$, ta có thể duyệt hết tất cả tập con của $n$ số, rồi kiểm tra xem tập đó có thỏa mãn hay không (tổng $t_i\le x$), sau đó lấy max tổng điểm của các tập thỏa mãn đó.

ĐPT: $O(q\cdot 2^n)$

Subtask 2

Nếu bài toán không cho dữ kiện gì thêm, thì việc tìm đáp án tối ưu sẽ rất khó. Tuy nhiên, chúng ta để ý một điều kiện ở đề bài:

với mỗi cặp $(i,j)$ sao cho $i\le j$ thì $t_i\le t_j$ và $v_i\ge v_j$.

Chúng ta có thể suy ra được từ điều kiện trên phương án tối ưu của Tèo là chọn làm các bài tập đầu tiên.

Chứng minh cũng khá đơn giản, giả sử tồn tại cặp $(i,j)$ $(i\le j)$ mà bài $j$ được chọn, bài $i$ không được chọn. Khi đó ta có thể bỏ chọn bài $j$ và chọn bài $i$ (vì $t_i\le t_j$) và nhận được tổng điểm cao hơn hoặc bằng với điểm trước đó (vì $v_i\ge v_j$).

Bài toán của chúng ta trở thành: Với mỗi truy vấn $i$, chúng ta cần tìm chỉ số $u$ lớn nhất sao cho $\sum _{j=1}^u{t}_j\le x_i$. Khi đó đáp án của bài toán là $\sum _{j=1}^u{v}_j$.

Vì $n,q\le {10}^3$, nên việc duyệt từ trái sang phải với mỗi truy vấn dễ dàng qua subtask này.

ĐPT: $O(q\cdot n)$

Subtask 3

Thay vì duyệt từ trái sang phải, ta có thể dùng kỹ thuật chặt nhị phân để giải quyết bài toán trong $O({\log }_{2}n)$ với mỗi truy vấn.

ĐPT: $O(q\cdot {\log }_{2}n)$