USACO

USACO 2019 December Contest, Platinum

Problem 1. Greedy Pie Eaters

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John has

$M$ cows, conveniently labeled

$1 \ldots M$ , who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked

$N$ pies (

$1 \leq N \leq 300$ ), labeled

$1 \ldots N$ . Cow

$i$ enjoys pies with labels in the range

$[l_i, r_i]$ (from

$l_i$ to

$r_i$ inclusive), and no two cows enjoy the exact same range of pies. Cow

$i$ also has a weight,

$w_i$ , which is an integer in the range

$1 \ldots 10^6$ .

Farmer John may choose a sequence of cows $c_1,c_2,\ldots, c_K,$ after which the selected cows will take turns eating in that order. Unfortunately, the cows don't know how to share! When it is cow $c_i$ 's turn to eat, she will consume all of the pies that she enjoys --- that is, all remaining pies in the interval $[l_{c_i},r_{c_i}]$ . Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed. Therefore, he wants you to compute the largest possible total weight ( $w_{c_1}+w_{c_2}+\ldots+w_{c_K}$ ) of a sequence $c_1,c_2,\ldots, c_K$ for which each cow in the sequence eats at least one pie.

SCORING:

Test cases 2-5 satisfy $N\le 50$ and $M\le 20$ .
Test cases 6-9 satisfy $N\le 50.$

INPUT FORMAT (file pieaters.in):

The first line contains two integers

$N$ and

$M$

$\left(1\le M\le \frac{N(N+1)}{2}\right)$ .

The next $M$ lines each describe a cow in terms of the integers $w_i, l_i$ , and $r_i$ .

OUTPUT FORMAT (file pieaters.out):

Print the maximum possible total weight of a valid sequence.

SAMPLE INPUT:

2 2
100 1 2
100 1 1

SAMPLE OUTPUT:

In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However, if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.