Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#2037 · Lịch xem World Cup 2026

MÔ TẢ BÀI TOÁN

Avatar
Đề tạo bởi
GV. Bùi Phú Khuyên

Là một fan cuồng bóng đá nhưng bị hạn chế về thời gian, trong kỳ World Cup 2026 anh Long đã lên kế hoạch xem N trận đấu. Mỗi trận đấu bắt đầu tại thời điểm S_i và kéo dài đúng 2 giờ (đã bao gồm thời gian nghỉ giữa hiệp và bù giờ).

Vì chỉ có thể theo dõi một trận tại một thời điểm, anh Long không thể xem đồng thời hai trận có khoảng thời gian giao nhau. Mỗi trận có độ hấp dẫn W_i (số nguyên dương), thể hiện mức độ kịch tính của trận đấu đó. Hai trận đấu i và j chỉ có thể được xem liên tiếp nếu: S_i+2≤S_j tức là trận đấu j bắt đầu sau hoặc đúng thời điểm trận đấu i kết thúc.

Hãy giúp anh Long lựa chọn các trận đấu sao cho tổng độ hấp dẫn nhận được là lớn nhất.

Dữ liệu vào

  • Dòng 1: Số nguyên dương N trận đấu muốn xem.
  • N dòng tiếp: mỗi dòng thứ i gồm 2 số nguyên S_i, W_i là thời gian bắt đầu và độ hấp dẫn của trận đấu thứ i.

Dữ liệu ra

Một số nguyên duy nhất — tổng độ hấp dẫn lớn nhất có thể đạt được.

Ràng buộc

  • 1 ≤ N ≤ 10^5
  • 0 ≤ S_i ≤ 10^4
  • 1 ≤ W_i ≤ 10^6

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
Nguyễn Trung Tuyến @2011064511
43 ms 2500 KB
890 Bytes
30/05/2026
10:59
2
B
Mắt bão @codewar2026_ck15
55 ms 1796 KB
1209 Bytes
29/05/2026
14:09
3
H
CLB Olympic Tin Học Hutech @olympictinhoc
94 ms 2172 KB
743 Bytes
28/05/2026
09:32
4
N
TowsT Newbies @codewar2026_ck8
107 ms 1848 KB
614 Bytes
29/05/2026
14:41
5
T
Đoàn Anh Tuấn @25800600750
709 ms 8184 KB
804 Bytes
29/05/2026
22:14
6
T
Đoàn Anh Tuấn @25800600750
731 ms 8184 KB
831 Bytes
29/05/2026
22:13

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

Giải thích: Các phương án có thể chọn để không trùng lịch cho ví dụ 1:

  • Phương án 1: Trận 1 → 3 → 5, tổng độ hấp dẫn là 5 + 4 + 6 = 15
  • Phương án 2: Trận 2 → 5, Tổng độ hấp dẫn là 7 + 6 = 13
  • Phương án 3: Trận 2 → 4, Tổng độ hấp dẫn là 7 + 3= 10
  • Phương án 4: Trận 1 → 4, Tổng độ hấp dẫn là 5 + 3 = 8
  • Phương án 5: Trận 1 → 5, Tổng độ hấp dẫn là 5 +6 = 11

Kết luận: Chọn trận 1 → 3 → 5 thì tổng 15 — lớn nhất.

Viết code