Subtask 1 (30% số điểm): ~k = 0~

Vì không được bỏ qua khổ thơ nào, nên số lượng khổ thơ lớn nhất đọc được là chỉ số ~i~ lớn nhất sao cho: ~\sum_{j=1}^{i} t_j \le s~

Độ phức tạp: ~O(n)~

Subtask 2 (30% số điểm): ~k = 1~

Ở subtask này, ta có thể duyệt qua tất cả các trường hợp Tý có thể bỏ qua 1 khổ thơ, rồi lựa chọn trường hợp tốt nhất. Việc tính toán số lượng khổ thơ lớn nhất đọc được của mỗi trường hợp có thể thực hiện bằng tìm kiếm nhị phân.

Lưu ý rằng có thể xảy ra trường hợp Tý không cần bỏ qua khổ thơ nào.

Độ phức tạp: ~O(n \times \log_2{n})~

Subtask 3 (40% số điểm): không có ràng buộc gì thêm

Ta sẽ quy hoạch động ~dp(i, j)~ (~0 \le i \le n,~ ~0 \le j \le k,~ ~i \ge j~) là thời gian đọc ít nhất khi đã duyệt đến khổ thơ thứ ~i~ và đã bỏ qua ~j~ khổ thơ.

Để tính ~dp(i, j)~, ta xét hai trường hợp:

• Nếu Tý đọc khổ thơ thứ ~i~ ⇒ ~dp(i, j) = dp(i - 1, j) + t_i~
• Nếu Tý không đọc khổ thơ thứ ~i~ ⇒ ~dp(i, j) = dp(i - 1, j - 1)~

Khi đó, lấy min giữa hai trường hợp trên.

Độ phức tạp: ~O(n \times k)~

Subtask 1 (50% số điểm): ~n \le 1000~

Vì ~n \le 1000~, nên ta có thể duyệt qua toàn bộ và đếm xem có bao nhiêu cặp ~(i, j)~ thỏa mãn: ~a_i + a_j > b_i + b_j~

Độ phức tạp: ~O(n^2)~

Subtask 2 (50% số điểm): Không có ràng buộc gì thêm

Đặt ~c_i = a_i - b_i~, thay vì đếm số cặp ~(i, j)~ thỏa mãn ~a_i + a_j > b_i + b_j~, thì ta đếm số cặp ~(i, j)~ thỏa mãn ~c_i + c_j > 0~ (vì điều kiện tương đương ~a_i - b_i + a_j - b_j > 0~).

Đến đây có nhiều cách giải, một trong những cách đơn giản nhất là:

• Sắp xếp mảng ~c~,
• Sau đó dùng hai con trỏ để đếm số cặp thỏa mãn điều kiện.

Độ phức tạp: ~O(n \times \log_2{n})~

Trước hết, ta sắp xếp mảng đã cho. Nhận thấy rằng, nếu ta sử dụng ~a~ lần thao tác xóa 2 phần tử nhỏ nhất, ~b~ lần thao tác xóa 1 phần tử lớn nhất (~a + b = k~) thì thứ tự thực hiện các thao tác là không quan trọng. Do đó, với mỗi bộ (~a, b~), thì tổng của các số còn lại sẽ là tổng của các số từ ~a \times 2 + 1~ đến ~n - b~ của dãy đã sắp xếp. Ta chỉ cần duyệt qua tất cả các bộ (~a, b~) có thể và lấy kết quả tốt nhất.

Độ phức tạp: ~O(n \times \log_2{n})~

Ta xét các trường hợp sau. Nếu n là số lẻ, thì bất kì cách đặt dấu + hoặc - nào thì sẽ luôn thu được tổng là một số lẻ, sẽ không thể bằng 0, do đó trong trường hợp này ta in ra NO.

Còn với n là số chẵn, ta xét tiếp trường hợp m là số chẵn, khi đó ta có chiến thuật đặt dấu sao cho các số 1 triệt tiêu lẫn nhau và các số 2 triệt tiêu lẫn nhau. Như vậy, kết quả của trường hợp này luôn là YES.

Trường hợp còn lại là n chẵn và m lẻ. Xét n = 0 thì ta thấy không có cách nào để điền dấu sao cho tổng bằng 0; còn với n ≠ 0 thì ta sẽ có chiến thuật như sau. Vì m lẻ nên ta sẽ điền dấu + cho một số 2, các số 2 còn lại ta điền dấu để triệt tiêu lẫn nhau hết. Đến đây, tổng của các số 2 đã được điền dấu bằng 2, và vì n là số chẵn khác 0 nên ta sẽ luôn có cách để điền dấu cho các số 1 để tổng của chúng bằng -2 (điền 2 dấu trừ, và cho triệt tiêu lẫn nhau hết các số còn lại). Như vậy, luôn có cách để điền dấu sao cho tổng bằng 0 trong trường hợp này.

Độ phức tạp: 𝑂(t)