DMOPC '14 Exam Time P5 - Happy Teachers

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Since you managed to cancel all of the exams, the teachers no longer have to spend the day before Exam Review marking them! However, they are still forced to come to school as their employment contract assumes they have exams to mark. This means that the teachers must be in the school for the entire day and since there are no students in class, they must stay at their desks in their respective department office.

Inspired by other schools where teachers dance to "Happy" by Pharrell Williams, you along with other friends decide to go to some teachers and record them happily dancing to the song.

Fortunately, this will prove to be an easy task, as the teachers are already happy due to the cancellation of exams. Since you want the video to make it seem that the teachers at your school are happier than those at other schools, you decide to maximize the total happiness of the video.

To achieve this, you assign a happiness value, H_i to each teacher. For every second the i^{th} teacher is in the video, the total happiness, H_t, increases by H_i.

However, relying only on happiness values means that one teacher would appear for most of the video, which is not very realistic. Rather than setting a time limit for each teacher, you notice that some teachers have more energy than others. By this, we mean that some teachers might dance for ten seconds while others may simply smile for one second, even if they both have the same happiness level.

To model this, an energy consumption value, E_i, is assigned to each teacher. For every second the i^{th} teacher is in the video he or she loses E_i of their happiness, with a lower happiness bound of 0. This in turn makes the total happiness lower than it could be and means that it might be time to visit the next teacher.

Unfortunately, you find out that there is a staff meeting in the afternoon where the Principal will ask the teachers why the exams were cancelled thereby reducing the happiness of every teacher to zero. This means that you have a limited time to record the video. Knowing that some teachers are more spontaneous than others, you assign a preparation time, P_i which is the time it takes for them to prepare for every second they appear plus that one second. That is, if P_i of the i^{th} teacher is 3, then they will spend 2 seconds preparing for every second they are in the video.

In the case that there are multiple optimum solutions, choose the one that will yield a video with the shortest duration — for more happiness per second.

Input Specification

The next line will consist of n, the number of teachers in the school.

The next n lines will consist of three integers separated by a space: H_i, E_i, and P_i.

The last line of input will consist of s, the amount of time, in seconds, that you have until the Staff Meeting begins. You do not necessarily have to visit each teacher.

Output Specification

The first line of output should consist of the maximum total happiness possible for the video.

The second line of output should contain the minimum duration of the video for the maximum happiness level.


1 \le n \le 50

1 \le E_i \le H_i \le 100

1 \le P_i \le 1\,000

1 \le s \le 1\,000

Sample Input

80 50 20
31 1 10

Sample Output


Explanation for Sample Output

The first teacher contributes to the total happiness by 80 and adds to the preparation time by 20. The second teacher contributes by 90 and adds to the production time by 30. Adding these, we obtain 170, the maximum possible total happiness of the 4 second video, which is also the minimum duration for the maximum happiness level.


  • 1
    Xue_Alex  commented on July 6, 2017, 2:45 a.m. edited

    "you assign a preparation time, Pi which is the time it takes for them to prepare for every second they appear plus that one second."

    If this remains true, why is it that in the sample in/out 20 + 10 +10 + 10 +5 doesn't go over the 50 second limit, because wouldn't you need to add 1 second for each to account for the teacher being in the video?

    edit: i cant read

  • 2
    Jackzhang  commented on July 29, 2015, 3:39 a.m.

    wait why is it 31 tho..

    • 2
      xXxP0t4t0MStRxXx  commented on Sept. 25, 2016, 12:49 a.m.

      Yea the sample case doesn't make any sense

      • 2
        TheZombieCloud  commented on Sept. 30, 2016, 10:41 p.m.

        Agreed. Author should fix sample case.

        • 2
          Kevin_Pan  commented on Oct. 1, 2016, 10:12 p.m. edited

          For every second the i^{th} teacher is in the video he or she loses E_i of their happiness

          31 + (31 - 1) + (31 - 2) = 90 minutes

          • 2
            xXxP0t4t0MStRxXx  commented on Oct. 1, 2016, 11:02 p.m.

            ahhhh... i totally misunderstood the question