All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef loves to prepare delicious dishes. He has prepared N dishes numbered from 1 to N for this year's MasterChef contest. He has presented all the N dishes to a panel of judges. Judging panel consists of M judges numbered from 1 to M. Rating for each dish was decided by voting from all the judges. Rating for the dishes has been given by a 1-indexed array A where Ai denotes rating of the ith dish.
Some dishes prepared by chef are extraordinary delicious, but unfortunately, some are not. Chef has been given a chance to improve the total rating of his dishes. By total rating of dishes, we mean the sum of the ratings of his dishes. Each of the M judges has administrative power to remove some (zero or more) dishes from a specified range. The ith judge takes Ci rupees for removing each dish of Chef's choice from the dishes numbered from Li to Ri (both inclusive). Once a dish is removed by any of the M judges it will not be considered for calculating total rating of the dishes. Chef has spent a large portion of his money preparing mouth watering dishes and has only K rupees left for now. Now chef is worried about maximizing total rating of his dishes by dropping some of the N dishes.
Please Help chef by finding the maximum total rating he can achieve such that the total expenditure does not exceed his budget of K rupees.
- First line of input contains a single integer T denoting the number of test cases.
- First line of each test case contains three space separated integers N, K and M denoting the number of dishes prepared by chef, chef's budget, and number of judges in judging panel respectively.
- Next line of each test case contains N space separated integers where ith integer denotes the rating received by the ith dish.
- Next M lines of each test case contain three space separated integers each: L, R and C, where the integers in the ith line denotes the value of Li, Ri and Ci respectively.
For each test case, print a single integer in a line corresponding to the answer.
- 1 ≤ T ≤ 105
- 1 ≤ N,M ≤ 105
- 1 ≤ K ≤ 500
- 1 ≤ Li ≤ Ri ≤ N
- 1 ≤ Ci ≤ 200
- -109 ≤ Ai ≤ 109
- Sum of N and M over all test cases does not exceed 5*105
- Subtask 1 : Sum of all N's across the test cases in a file does not exceed 5000. Sum of all M's is also at most 5000. (33 points).
- Subtask 2 : Sum of all N's across the test cases in a file does not exceed 5*105. Sum of all M's is also at most 5*105. ( 67 points ).
1 5 10 5 10 -2 -5 7 -10 1 1 5 2 4 10 4 4 12 3 4 10 1 5 15 output 5
- Chef can drop dish numbered 3rd with rating -5 by paying 10 rupees to the 4th judge, and get the maximum possible total rating of 5.
|Tags||data-structure, dynamic-programming, easy-medium, july15, ma5termind|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.