All submissions for this problem are available.
Bob, a famous foodie of IIT Kanpur, tired of studying, decides to go into catering startup. Bob plans to cater to the offices located in Kanpur. In Kanpur, all the offices are in some or other apartments. Also, the offices in the same building have same lunch time. Bob, being a good negotiator, acquired contracts for round the clock catering from all offices of N apartments in the city.
For the N apartments in the city, i-th apartment housing X[i] offices and and each office is charged P[i] rupees every day for catering at their lunch time, i.e., for time S[i] to E[i]. Each employee in the startup can cater to atmost one office at a time and one employee is enough to complete the catering needs of an office. An employee earns C rupees a day. Also, there are M one way roads in the city, each motorable by bike. The average speed of bike in Kanpur is 1km per V minutes.
Since Bob would want to maximize his profit, he would want to hire minimum number of employees. So, he would send a employee to some office, who after completing his duty, can cater to another office. Thereby, decreasing the number of employees, if possible.
Now, Alice, a very close friend and business partner of Bob, advises him against catering to a specific apartment J. Now Bob cannot refuse her. So, he decided to cater to as many offices of Jth apartment, till his profit does not decrease. Help Bob to find out how many offices of Jth apartment he would serve and also, the maximum profit that he would reap.
First line contains T, number of test cases.
Each Test case begins with line containing N M J C V.
Next N lines follows, each line contain 4 space separated integers, X[i] S[i] E[i] P[i],, for the i-th line.
The following M lines contain 3 space separated integers each, I, J and Di j, such that I and J represent apartments and the distance between them is equal to Di j.
The output consists of T lines.
For each test case, print, in different lines, the number of offices catered in apartment J and maximum profit that can be earned.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 100
- 0 ≤ N ≤ 10
- 1 ≤ C ≤ 105
- 1 ≤ X ≤ 106
- 1 ≤ S[i] < E[i] ≤ 109
- 1 ≤ P[i] ≤ 106
- Di j ≤ 104
3 6 1 100 1
10 40 50 90
4 15 35 110
5 10 20 50
1 2 1
2 1 1
1 3 1
3 1 1
2 3 1
3 2 1
Since Bob has to cater apartment 2 and 3, so atleast 9 employees are required, as lunch time of apartment 2 and 3 are overlapping.
For apartment 1, the same 9 employees can be used for catering as the lunch times do not overlap with apartments 2 and 3 and since employing more people will reduce the profit, total of 9 people are employed.
Hence 9 offices are catered in apartment 1.
The equation for profit is X * P + X * P + 9 * P - 9 * C = 600
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.