All submissions for this problem are available.
After Virat Kohli, it’s time for India to think about it’s bowlers. The team selector visits the MRF Pace academy in Chennai.
There are a total of N bowlers in the academy who are described by the number of overs they can bowl in a day. Let this be denoted by Oi. Owing to fatigue, there are lower and upper limits Li and Ri for every bowler, Oi (both inclusive). The performance of a bowler is judged by a metric which is defined differently for every bowler by the expert. This metric is a quadratic function and performance is evaluated as fi(Oi) where fi is the function for ith bowler.
There are certain relations like Ou<= Ov + d, where u and v are different bowlers and d is an integer.
The coach at the Academy wants to show that his academy is performing good, so maximize the total output of bowlers for him.
The first line of input contains integer T denoting number of testcases.
The first line of each testcase contains two integers N and M, the number of bowlers and the number of relations.
Then follow N lines, each containing three integers pi, qi and ri, the coefficients of the quadratic function fi(x). That is, fi(x) = pix2 + qix +ri
Then follow N lines, each containing li and ri.
Then follow M lines, each containing three integers ui, vi and di, describing a relation.
For each test case, print the maximum output of all bowlers in the academy in separate line. If there is no possible combination that satisfies the constraints, output "-1".
- |pi|<=10, and |qi|,|ri|<=1000
- 1<=ui,vi<=n, ui is different from vi, and |di|<=200
Input: 1 3 3 0 1 0 0 1 1 0 1 2 0 3 1 2 -100 100 1 2 0 2 3 0 3 1 0 Output: 9
|Tags||algophobic, alph2016, daga_07, maxflow, medium-hard|
|Time Limit:||1 - 2 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.