#2037 · Lịch xem World Cup 2026

HUTECH CODE WAR 2026 1s 128MB

Đăng nhập

MÔ TẢ BÀI TOÁ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$ là thời gian bắt đầu và độ hấp dẫn củ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	Phạm Trần Minh Hiếu @2280600972	35 ms 456 KB 646 Bytes	10/06/2026 08:18
2	Lê Duy Hải @2280600799	35 ms 2500 KB 641 Bytes	07/06/2026 00:13
3	Phạm Trần Minh Hiếu @2280600972	37 ms 460 KB 646 Bytes	10/06/2026 08:23
4	Lê Văn Nguyên @35261020087	39 ms 380 KB 1066 Bytes	05/06/2026 09:50
5	Nguyễn Trung Tuyến @2011064511	43 ms 2500 KB 890 Bytes	30/05/2026 10:59
6	B Mắt bão @codewar2026_ck15	55 ms 1796 KB 1209 Bytes	29/05/2026 14:09
7	H CLB Olympic Tin Học Hutech @olympictinhoc	94 ms 2172 KB 743 Bytes	28/05/2026 09:32
8	Lê Duy Hải @2280600799	101 ms 2484 KB 584 Bytes	07/06/2026 00:12
9	N TowsT Newbies @codewar2026_ck8	107 ms 1848 KB 614 Bytes	29/05/2026 14:41
10	T Đoàn Anh Tuấn @25800600750	709 ms 8184 KB 804 Bytes	29/05/2026 22:14
11	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

Phạm Trần Minh Hiếu @2280600972

9 ngày trước

Hello mọi người, code tham khảo đây

include <stdio.h>

long long mhd[10000]; long long kq[10000];

int main() {

int st;
if (scanf("%d", &st) != 1) 
return 0;

int mxtg = 0;
for (int i = 0; i < st; i++) {
    int bd;
    long long hd;
    scanf("%d %lld", &bd, &hd);
    if (hd > mhd[bd]) {
        mhd[bd] = hd;
    }
    if (bd > mxtg) {
        mxtg = bd;
    }
}

for (int i = 2; i <= mxtg + 2; i++) {
    long long tt = kq[i - 1];
    long long tc = kq[i - 2] + mhd[i - 2];
    kq[i] = tt > tc ? tt : tc;
}

printf("%lld\n", kq[mxtg + 2]);
return 0;

}

Vào thảo luận 0 Phản hồi

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

Giải thích: Các phương án có thể chọn để không trùng lịch cho ví dụ $1$ :

Phương án 1: Trận $1 → 3 → 5$ , tổng độ hấp dẫn là $5 + 4 + 6 = 15$
Phương án 2: Trận $2 → 5$ , Tổng độ hấp dẫn là $7 + 6 = 13$
Phương án 3: Trận $2 → 4$ , Tổng độ hấp dẫn là $7 + 3= 10$
Phương án 4: Trận $1 → 4$ , Tổng độ hấp dẫn là $5 + 3 = 8$
Phương án 5: Trận $1 → 5$ , Tổng độ hấp dẫn là $5 +6 = 11$

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

Đăng nhập

Đang chạy thử nghiệm...

Vui lòng chờ tiến trình hoàn tất

KIỂM THỬ

Không có dữ liệu kiểm thử

Viết code

Không hỗ trợ Mobile