Input File: divain.txt
Output File: divaout.txt
Time Limit: 2 seconds
Memory Limit: 32 MB
You are planning a charity event involving the well-known Italian opera star, Dame Angelina Di Pasquale. She needs accompaniment, and the local symphony orchestra have volunteered to perform free of charge. However, this orchestra is highly unpredictable — on some evenings they are in top form, but on other evenings nobody can bear to listen to them. This is because on different evenings the musicians play at different qualities depending on the events in their lives.
Dame Angelina is extremely temperamental — if the orchestra is not good enough, she will storm off the stage during the concert and you will have to refund all the tickets. You therefore resolve to find the evening on which the orchestra will give its best performance.
The orchestra performs every evening. On any given evening, the orchestra has an overall quality value. This value is calculated by adding up the individual qualities of each musician.
Before the performance every evening, the quality of each individual musician may either increase or decrease relative to the previous evening. This change in quality is affected by significant events that take place in the musician's life, such as pay days, breaking a leg or having a cello stuck in the elevator door.
Specifically, a musician's quality changes each evening according to the most recent significant event in their life. Each event has an associated effect, which is a number that may be positive or negative. After the event occurs, the quality of the musician will change by this number every evening until a new event occurs (at which point this older event will be forgotten). Before a musician has their first significant event, their quality remains fixed at zero.
If a musician has an event on day d with effect r, that effect begins immediately. That is, the quality of the musician will change by r on the evening of day d and every subsequent day, until some other event happens to that musician.
The table below illustrates this for a four-member orchestra over nine days. Each row lists the effects of any events during a single day, and the subsequent quality of each musician that evening. In this case, the best overall performance of the orchestra occurs on the evening of day 8.
|Musician 1||Musician 2||Musician 3||Musician 4||Total|
Your fortune teller has told you precisely what significant events will happen to each musician within the next T days. You must use this information to determine on which evening within the next T days the orchestra will give their best performance, i.e., when the sum of qualities for all musicians is largest.
The first line of input will contain the two integers N T separated by a single space, where N is the number of musicians (1 <= N <= 100,000) and T is the number of days you must consider (1 <= T <= 100,000,000). The second line will contain the single integer K, representing the total number of significant events in the musicians' lives (0 <= K <= 1,000,000). Musicians are numbered 1,2,...,N and days are numbered 1,2,...,T.
Each of the following K lines describes a single event. Each such line will contain three integers d m r separated by spaces, where d is the day of the event (1 <= d <= T), m is the number of the affected musician (1 <= m <= N), and r is the effect of the event (-100,000 <= r <= 100,000).
The events will be listed in chronological order, i.e., in ascending order of d. Two events will never happen to the same musician on the same day. It is guaranteed that the quality of every musician and also the quality of the entire orchestra will remain between -2,000,000,000 and 2,000,000,000 inclusive on the evening of each day 1,...,T.
Your program should output a single line containing the two integers D Q separated by a space.
The integer D indicates that the orchestra will give its best performance on the evening of day D. You must consider the evenings of all days 1,2,...,T (but nothing after this), and you must also consider the evening of day 0 (before any events occur at all). If there are several days on which the orchestra gives its best performance, you must output the last such day.
The integer Q is the quality of the orchestra's performance on the evening of this best day D.
4 9 7 1 1 4 1 2 -2 2 3 -4 5 1 6 7 4 6 8 4 10 9 3 -15
5 8 4 1 3 -3 2 1 -1 2 2 1 3 1 1
The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.