Người Ăn Bánh

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ chiếc bánh đặt tại các vị trí $1, 2, \dots, N$ trên một hàng thẳng, và $M$ người ăn bánh. Người thứ $i$ có trọng số $w_{i}$ và thích ăn bánh trong đoạn $[l_{i}, r_{i}]$ — tức là người này sẽ ăn đúng một chiếc bánh nằm trong khoảng từ $l_{i}$ đến $r_{i}$ .

Mỗi chiếc bánh chỉ có thể được ăn bởi tối đa một người. Hãy chọn một tập con các người và phân công mỗi người trong tập đó ăn một chiếc bánh (không có hai người cùng ăn một chiếc), sao cho tổng trọng số của những người được chọn là lớn nhất có thể.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $M$ ( $1 \leq N \leq 300$ , $1 \leq M \leq N (N + 1) / 2$ ).
$M$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $w_{i}$ , $l_{i}$ , $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq N$ , $1 \leq w_{i} \leq 10^{6}$ ).

Dữ liệu ra

Một số nguyên duy nhất — tổng trọng số lớn nhất có thể.

Ví dụ

Input	Output	Giải thích
2 2 100 1 2 100 1 1	200	Người 2 ăn bánh tại vị trí 1 ( $w = 100$ ), người 1 ăn bánh tại vị trí 2 ( $w = 100$ ). Tổng = 200.
50 20 204414 14 38 862492 2 25 361742 13 31 324259 16 42 489157 9 48 624174 17 47 871391 23 25 747770 15 47 746949 5 19 266344 13 45 48574 36 38 44042 19 40 95178 1 12 787097 1 42 631770 14 48 368457 19 25 63010 26 39 291017 33 38 333941 1 23 534191 9 14	7511349

Bình luận

Không có bình luận tại thời điểm này.