Một trò chơi bài được mệnh danh là bài kiểm tra trí tuệ có tên là “Kang”. Trong trò chơi này, mỗi lá bài có điểm số là một số nguyên dương. Khi bắt đầu, bạn nhận được $N$ lá bài để cầm trên tay, và có thêm $M$ lá bài khác được đặt ngửa trên bàn xếp từ trái sang phải. Bạn nhìn thấy điểm số của tất cả các lá bài, cả những lá bài nhận được trên tay lẫn những lá bài đặt trên bàn. Sau đó, bạn được rút thêm bài trên bàn trong $k$ lượt, mỗi lượt phải rút từng lá một theo thứ tự từ trái sang phải. Sau mỗi lượt rút bài, bạn có thể bỏ bài trên tay 1 lần gồm bao nhiêu lá bài trên tay có cùng điểm số tùy ý. Bạn phải lập kế hoạch chơi sao cho sau khi rút bài trên bàn và bỏ bài trên tay đủ $k$ lượt, các lá bài còn lại trên tay có tổng điểm nhỏ nhất.

Xét ví dụ sau đây:

Giả sử lúc bắt đầu bạn có năm lá bài với điểm số là $6, 3, 9, 6, 3$ và các lá bài đặt trên bàn có điểm số xếp từ trái sang phải là $4, 6, 9, 6$.

Trường hợp $k = 1$: Nếu bạn chỉ được rút 1 lá bài trên bàn, khi bạn rút lá bài đầu tiên, điểm số của các lá bài bạn có sẽ là $6, 3, 9, 6, 3, 4$. Sau đó bạn có thể chọn các lá bài có cùng điểm số để bỏ đi 1 lần; cách tốt nhất là chọn bỏ đi 2 lá bài có điểm số bằng $6$, để tổng điểm của các lá bài còn lại có giá trị nhỏ nhất bằng $3 + 9 + 3 + 4 = 19$.

Trường hợp $k = 2$: Nếu bạn được rút 2 lá bài trên bàn, cách tốt nhất là: sau khi rút lá bài đầu tiên có điểm số bằng $4$, bạn chọn bỏ đi một lá bài có điểm số bằng $9$, các lá bài còn lại trên tay có điểm số là $6, 3, 6, 3, 4$. Tiếp theo, khi rút lá bài thứ 2 có điểm số bằng $6$, bạn sẽ có thể bỏ đi 3 lá bài có điểm số bằng $6$, làm cho các lá bài còn lại có tổng điểm nhỏ nhất bằng $3 + 3 + 4 = 10$.

Trường hợp $k = 3$: Nếu bạn được rút 3 lá bài trên bàn, cách tốt nhất là: khi bạn rút lá bài đầu tiên, điểm số của các lá bài trên tay sẽ là $6, 3, 9, 6, 3, 4$. Sau đó chọn các lá bài có cùng điểm số để bỏ đi 1 lần; cách tốt nhất là chọn bỏ đi cả 2 lá bài có điểm số bằng $3$, trên tay sẽ còn lại các lá bài $6, 9, 6, 4$. Tiếp theo, khi rút lá bài thứ 2 có điểm số bằng $6$, bạn sẽ có thể bỏ đi 3 lá bài có điểm số bằng $6$, trên tay sẽ có các lá bài $9, 4$. Và khi bạn rút bài lần thứ 3 có điểm số bằng $9$, bạn sẽ có thể bỏ đi cả 2 lá bài có điểm số bằng $9$, làm cho lá bài còn lại có tổng điểm là $4$.

Trường hợp $k = 4$: Nếu bạn được rút 4 lá bài trên bàn, cách tốt nhất là: sau khi rút lá bài đầu tiên có điểm số bằng $4$, chọn bỏ đi một lá bài có điểm số bằng $4$, trên tay còn lại các lá bài có điểm số là $6, 3, 9, 6, 3$. Tiếp theo, ở lần rút thứ 2, lá bài có điểm số bằng $6$; cách tốt nhất là bạn chọn bỏ đi cả 2 lá bài có điểm số bằng $3$, trên tay sẽ còn lại các lá bài $6, 9, 6, 6$. Khi rút lần thứ 3, lá bài có điểm số bằng $9$, chọn bỏ đi cả 2 lá bài có điểm số bằng $9$. Và trong lần rút lá bài cuối cùng có điểm số bằng $6$, bạn sẽ có thể bỏ đi 4 lá bài có điểm số bằng $6$. Lần bỏ bài này dẫn đến việc không còn lá bài nào trên tay, nghĩa là tổng điểm của các lá bài bằng $0$.

Nhiệm vụ của bạn (Your Task)

Tìm “tổng điểm nhỏ nhất của các lá bài còn lại trên tay” sau khi kết thúc $k$ lượt với $k = 1, 2, 3, \ldots, M$.

Bài toán này có định dạng lập trình khác với định dạng thông thường và sẽ được sử dụng trong kỳ thi thực tế. Vui lòng xem phần cuối của đề bài này về cách sử dụng.

Chi tiết cài đặt

Bạn phải viết hàm sau đây:

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

Với các tham số là:

• $A$ là mảng có độ dài $N$ cho biết số ghi trên các lá bài trên tay lúc bắt đầu.
• $B$ là mảng có độ dài $M$ cho biết số ghi trên các lá bài đặt trên bàn theo thứ tự từ trái sang phải.
• Hàm này phải trả về mảng $C$ có độ dài $M$ biểu diễn tổng điểm của các lá bài trên tay có giá trị nhỏ nhất có thể sau $k$ lượt với $k = 1, 2, 3, \ldots, M$.

Ví dụ: nếu $A = [6, 3, 9, 6, 3]$ và $B = [4, 6, 9, 6]$, hàm phải trả về mảng $[19, 10, 4, 0]$.

Giới hạn

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ với mỗi $i$ thỏa mãn $1 \le i \le N$
• $1 \le B[i] \le 10^9$ với mỗi $i$ thỏa mãn $1 \le i \le M$

Nhiệm vụ con

Ghi chú

Hướng dẫn lập trình

Đối với bài toán này, cách viết chương trình và nộp chương trình vào hệ thống chấm bài (Grader) sẽ theo định dạng khác với định dạng lập trình thông thường vốn yêu cầu thí sinh phải viết cả phần đọc dữ liệu vào và phần in kết quả ra. Trong bài này, thí sinh chỉ cần viết phần tính toán cần thiết vào trong hàm được quy định. Các dữ liệu đầu vào có thể được sử dụng thông qua các tham số của hàm, và kết quả tính toán cũng phải được trả về thông qua hàm đó; thí sinh không cần viết phần đọc dữ liệu vào và không cần viết phần hiển thị kết quả.

Thí sinh sẽ nhận được nhiều tệp khác nhau như sau. Thí sinh chỉ phải chỉnh sửa một tệp duy nhất theo yêu cầu của đề bài và nộp tệp đó lên hệ thống:

• grader.cpp là tệp chính làm nhiệm vụ đọc dữ liệu vào và xuất dữ liệu ra.
• kang.cpp là tệp mà thí sinh phải viết các chương trình tính toán và là tệp mà thí sinh nộp lên hệ thống (trong tệp kang.cpp không được có hàm main(), nhưng có thể có các hàm khác).
• run_cpp.sh là tệp mà thí sinh có thể gọi để chạy toàn bộ chương trình.
• compile_cpp.sh là tệp mà thí sinh có thể gọi để biên dịch chương trình.

Thí sinh sẽ nhận được một tệp .zip có thể tải xuống từ hệ thống; khi giải nén (extract) tệp này sẽ có đủ cả 4 tệp trên. Thí sinh nên sử dụng trình soạn thảo văn bản (text editor) hoặc IDE để chỉnh sửa tệp kang.cpp, và thực hiện biên dịch hoặc chạy chương trình thông qua việc gọi compile_cpp.sh hoặc run_cpp.sh.

Khi thí sinh gọi tệp run_cpp.sh để chạy chương trình, chương trình sẽ hoạt động theo đúng những gì được quy định trong tệp grader.cpp, trong đó mục “Mô tả tệp Grader” giải thích về hoạt động của tệp này.