RGPC '18 P3 - Chocolate Day - DMOJ: Modern Online Judge

RGPC '18 P3 - Chocolate Day

Points: 10

Time limit: 1.4s

Memory limit: 128M

Authors:

Problem types

Valentine's Day, which coincidentally falls on the same day as the CCC this year, is rapidly approaching! You, having sorted out your priorities, are preparing sweets to give out to your classmates. You have $N$ $N$ cups numbered in order from $1$ $1$ to $N$ $N$ , and you fill them $T$ $T$ times. More specifically, for each filling, you add $c$ $c$ chocolates to all the cups between cup $a$ $a$ and cup $b$ $b$ inclusive.

However, before you spread happiness throughout the classroom, you decide to give some chocolates to your "special someone" before anyone else. Since you don't want things to get out of hand, you set up some rules for yourself. Firstly, you can give this person more than one cup of chocolates, but if you do, they must be numbered in order. For example, you may give this person cups 1, 2, and 3, but not cups 4, 5, and 7.

Additionally, you want to limit the total sweetness that you give out, so that this person doesn't get diabetes. Thus, after filling all the cups, you decide upon an inclusive upper limit $L$ $L$ for the number of chocolates that you will give out, and now you want to know the maximum number of cups that this person can get.

Input Specification

The first line of input will contain two space-separated integers $N$ $N$ and $T$ $T$ . Each of the next $T$ $T$ lines will contain three space-separated integers $a$ $a$ , $b$ $b$ , and $c$ $c$ , representing a fill operation on cups $a$ $a$ to $b$ $b$ inclusive, adding $c$ $c$ chocolates to each. Finally, the last line of input will contain the single integer $L$ $L$ .

Constraints

$1 \le N, T \le 10^6$ $1 \leq N, T \leq 10^{6}$
$1 \le a \le b \le N$ $1 \leq a \leq b \leq N$
$1 \le c \le 10^3$ $1 \leq c \leq 10^{3}$
$0 \le L \le 10^9$ $0 \leq L \leq 10^{9}$

Output Specification

Output a single integer representing the maximum number of cups of chocolate that you could give to your "special someone".

Sample Input

Copy

Sample Output

Copy

Explanation

You have $6$ $6$ cups, and perform $5$ $5$ filling operations. After all of the fillings, the cups have $6$ $6$ , $7$ $7$ , $7$ $7$ , $8$ $8$ , $4$ $4$ , and $1$ $1$ chocolates respectively. The possible ways to give them out are (with $1$ $1$ -indexed cups): $\{1\}$ ${1}$ , $\{2\}$ ${2}$ , $\{3\}$ ${3}$ , $\{4\}$ ${4}$ , $\{5\}$ ${5}$ , $\{6\}$ ${6}$ , $\{1, 2\}$ ${1, 2}$ , $\{4, 5\}$ ${4, 5}$ , $\{5, 6\}$ ${5, 6}$ , and $\{4, 5, 6\}$ ${4, 5, 6}$ , so thus, the maximum number of cups is $3$ $3$ .

Comments

0

WuWill commented on Feb. 24, 2024, 6:28 p.m.

does $L$ $L$ restrict the maximum amount of cups or candies?

1

EthanHardie commented 77 days ago ← edited →

$L$ $L$ represents the upper limit for the number of total chocolates you will give out (inclusive).

1

RedcXca commented on Feb. 13, 2021, 11:14 p.m.

the cups you give out must be consecutive? so 4 5 6 works but not 4 5 7?

2

Lost commented on Oct. 19, 2021, 9:18 p.m.

Yes for this problem, "numbered in order" would mean consecutive.