JOI 2026 - Seats 3
Xem PDFCó \(N\) nhóm khách, mỗi nhóm gồm hai người và phải ngồi ở hai ghế kề nhau, cùng hai khách VIP đi một mình. Có \(2N+2\) ghế trên một hàng, được đánh số từ \(1\) đến \(2N+2\) theo thứ tự từ trái sang phải; độ thoải mái ghế \(i\) là \(A_i\). Mỗi khách được xếp vào đúng một ghế và mỗi ghế có đúng một khách, không có hai khách ngồi chung ghế. Hãy xếp tất cả khách để tổng độ thoải mái của hai ghế dành cho VIP là lớn nhất.
Dữ liệu vào
Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1,\ldots,A_{2N+2}\).
Dữ liệu ra
In tổng độ thoải mái lớn nhất của hai ghế VIP.
Ràng buộc
- \(1\le N\le200000\).
- \(1\le A_i\le10^9\).
- Mọi giá trị số trong dữ liệu vào đều là số nguyên.
Phân nhóm
- \(10\) điểm: \(N=1\).
- \(10\) điểm: \(N\le2\).
- \(10\) điểm: \(N\le3\).
- \(30\) điểm: \(N\le2000\).
- \(40\) điểm: không có ràng buộc thêm.
Ví dụ
Ví dụ 1
Input
2
20 60 40 30 10 50Output
90Giải thích
Có thể xếp nhóm thứ nhất vào các ghế \(1,2\) tính từ trái sang, nhóm thứ hai vào các ghế \(4,5\), và hai khách VIP vào các ghế \(3,6\). Tổng độ thoải mái của hai ghế VIP là \(40+50=90\). Không thể đạt tổng lớn hơn \(90\), nên in \(90\).
Ví dụ này thỏa mãn các nhóm \(2\), \(3\), \(4\), \(5\).
Ví dụ 2
Input
1
1000000000 1000000000 1 1Output
2000000000Giải thích
Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(4\), \(5\).
Ví dụ 3
Input
4
4 10 8 6 7 6 7 8 12 3Output
16Giải thích
Ví dụ này thỏa mãn các nhóm \(4\), \(5\).
Nguồn
JOI 2025/2026 Semifinal Stage, bài Seats 3. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.
Kỳ thi:
- JOI 2026 - Bán kết (1 Tháng 2., 2026)
Bình luận