[HSG-QH_KA_HT_24] Chọn quà
Xem dạng PDFNoel năm nay, trường của Bon sẽ tặng quà cho n học sinh. Có tất cả ~2n~ phần quà, được xếp thành 2 hàng ngang a và b. Trên mỗi hàng ngang có n phần quà, từ phần quà thứ ~1~ đến phần quà thứ ~n~. Giá trị của các phần quà trên mỗi hàng ngang là một hoán vị của các số từ ~1~ đến ~n~ (hoán vị được hiểu đơn giản là hoán đổi vị trí của ~n~ số nguyên, mỗi số xuất hiện một lần duy nhất. Giá trị của mỗi phần quà tương ứng với một số duy nhất trong các số từ ~1~ đến ~n~). Mỗi học sinh được nhận một phần quà trong hàng ngang ~a~ và một phần quà trong hàng ngang ~b~, nguyên tắc nhận quà như sau: Mỗi học sinh được chọn một phần quà bất kì ở hàng ngang ~a~ hoặc ~b~, khi đó giá trị của phần quà đã chọn chính là thứ tự của phần quà thứ hai trong hàng ngang còn lại.
Yêu cầu
Hãy cho biết tổng giá trị lớn nhất của hai phần quà mà Bon có thể nhận được.
Dữ liệu đầu vào
Gồm hai dòng:
- Dòng đầu tiên ghi số nguyên ~n~ ~(0 < n \le 10^5)~;
- Dòng thứ hai ghi ~n~ số nguyên, là một hoán vị của các số từ ~1~ đến ~n~;
- Dòng thứ ba ghi ~n~ số nguyên, là một hoán vị của các số từ ~1~ đến ~n~.
Dữ liệu đầu ra
Gồm một số duy nhất thể hiện phần quà lớn nhất mà Bon có thể nhận.
Ràng buộc dữ liệu
- Có 60% số test ứng với 60% số điểm thỏa mãn: ~1 \le n \le 10^3~;
- 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì thêm.
Ví dụ
Ví dụ 1
INPUT
4
3 1 2 4
1 3 4 2
OUTPUT
8
Giải thích: Học sinh Bon chọn phần quà ở hàng ~b~ có giá trị là ~4~ + thứ tự của ~4~ ở hàng ~a~ là ~4~ nên kết quả là ~4 + 4 = 8~.
Ví dụ 2
INPUT
3
3 2 1
2 3 1
OUTPUT
5
Giải thích: Học sinh Bon chọn phần quà ở hàng ~a~ có giá trị là ~3~ + thứ tự của ~3~ ở hàng ~b~ là ~2~ nên kết quả là ~3 + 2 = 5~.
Bình luận
1 upvote nguyenminhquang=1robux
hi ae