RGPC '18 P3 - Chocolate Day

View as PDF

Submit solution

Points: 10
Time limit: 1.4s
Memory limit: 128M

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 cups numbered in order from 1 to N, and you fill them T times. More specifically, for each filling, you add c chocolates to all the cups between cup a and cup 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 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 and T. Each of the next T lines will contain three space-separated integers a, b, and c, representing a fill operation on cups a to b inclusive, adding c chocolates to each. Finally, the last line of input will contain the single integer L.


  • 1 \le N, T \le 10^6
  • 1 \le a \le b \le N
  • 1 \le c \le 10^3
  • 0 \le L \le 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

6 5
1 4 4
1 3 2
4 5 4
2 3 1
6 6 1

Sample Output



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


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

    does L restrict the maximum amount of cups or candies?

  • 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?

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

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