Subtask 1

Với ~n, q \leq 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 \leq 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 \leq j~ thì ~t_i \leq t_j~ và ~v_i \geq 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 \leq 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 \leq 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 \geq 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 \leq x_i~. Khi đó đáp án của bài toán là ~\sum_{j = 1}^{u} v_j~.

Vì ~n, q \leq 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})~