409616: GYM103643 S Gin-chan's Odd Jobs

At Gin-chan's Odd Jobs, Gintoki and his crew will do any job! Whether it be finding lost giant alien pets for aliens, tiling roofs, or running a hair salon, they do it all.

The city of Edo is represented as a $$$3 \cdot 10^6 \times 3 \cdot 10^6$$$ square grid initially containing no jobs. There are $$$N$$$ $$$(1 \leq N \leq 700)$$$ Amanto (space aliens) who are paying for jobs in Edo. The $$$i$$$th Amanto goes through each location $$$(r, c)$$$ such that $$$X_{1,\,i} \leq r \leq X_{2,\,i}$$$ and $$$Y_{1,\,i} \leq c \leq Y_{2,\,i}$$$ $$$(1 \leq X_{1,\,i} \leq X_{2,\,i} \leq 3 \cdot 10^6$$$ and $$$1 \leq Y_{1,\,i} \leq Y_{2,\,i} \leq 3 \cdot 10^6)$$$. If there is not a job at $$$(r,c)$$$, she posts one worth $$$A_i$$$ $$$(1 \leq A_i \leq 1000)$$$ yen. Otherwise, she still wants the job done, so she increases the job's worth by $$$A_i$$$ yen.

To complete the jobs, Gintoki and his crew, $$$M$$$ $$$(1 \leq M \leq 10^6)$$$ people in total, are each assigned a region. The $$$i$$$th person is assigned all locations $$$(r, c)$$$ such that $$$X_{1,\,B_i} \leq r \leq X_{1,\,D_i}$$$ and $$$Y_{1,\,C_i} \leq c \leq Y_{1,\,E_i}$$$ $$$(1 \leq B_i, C_i, D_i, E_i \leq N$$$, $$$X_{1,\,B_i} \leq X_{1,\,D_i}$$$, and $$$Y_{1,\,C_i} \leq Y_{1,\,E_i})$$$.

Let a team be composed of at least $$$1$$$ person. This team goes to each location such that the people assigned to the location are exactly equal to the people on the team. For each location, if there is a job, they do it. The team earns $$$v$$$ yen after completing a job worth $$$v$$$ yen.

Over all possible teams that complete at least $$$1$$$ job, Gintoki wants to find the team with the highest average job worth. If there are multiple, he wants any amongst these teams which earned the most yen. Then, he wants to know how much yen this team earned so he can force them to pay for his Shonen Jump and strawberry milk. However, that's not his job, it's yours!

The first line contains $$$2$$$ integers, $$$N$$$, $$$M$$$.

The next $$$N$$$ lines describe the Amanto. The $$$i$$$th of which contains $$$5$$$ integers, $$$X_{1,\,i}$$$, $$$Y_{1,\,i}$$$, $$$X_{2,\,i}$$$, $$$Y_{2,\,i}$$$, $$$A_i$$$.

The final $$$M$$$ lines describe Gintoki and his crew. The $$$i$$$th of which contains $$$4$$$ integers, $$$B_i$$$, $$$C_i$$$, $$$D_i$$$, $$$E_i$$$.

Print how much yen the team with the highest average job worth earned.

3 2
1 2 2 4 3
1 4 1 4 1
1 1 1 2 2
1 1 3 2
3 3 2 1

5

Example Explanation:

$$$---------------------------------------------$$$

Person $$$1$$$ is assigned locations $$$(r,c)$$$ such that $$$X_{1,\,1} \leq r \leq X_{1,\,3}$$$ and $$$Y_{1,\,1} \leq c \leq Y_{1,\,2}$$$ $$$=$$$ $$$(1,2)$$$, $$$(1,3)$$$, and $$$(1,4)$$$.

Person $$$2$$$ is assigned locations $$$(r,c)$$$ such that $$$X_{1,\,3} \leq r \leq X_{1,\,2}$$$ and $$$Y_{1,\,3} \leq c \leq Y_{1,\,1}$$$ $$$=$$$ $$$(1,1)$$$ and $$$(1,2)$$$.

$$$---------------------------------------------$$$

Denote $$$\{a,b,\dots,c\}$$$ as the team with person $$$a$$$, person $$$b$$$, ... person $$$c$$$.

Team $$$\{1\}$$$ completed the jobs at locations $$$(1, 3)$$$ and $$$(1,4)$$$. Thus, the team earned $$$3 + 4 = 7$$$ yen and completed $$$2$$$ jobs. Team $$$\{1\}$$$ has an average job worth of $$$\frac{7}{2} = 3.5$$$ yen.

Team $$$\{2\}$$$ completed the job at location $$$(1,1)$$$. Thus, the team earned $$$2$$$ yen and completed $$$1$$$ job. Team $$$\{2\}$$$ has an average job worth of $$$\frac{2}{1} = 2$$$ yen.

Team $$$\{1,2\}$$$ completed the job at location $$$(1,2)$$$. Thus, the team earned $$$5$$$ yen and completed $$$1$$$ job. Team $$$\{1,2\}$$$ has an average job worth of $$$\frac{5}{1} = 5$$$ yen.

Team $$$\{1,2\}$$$ has the highest average job worth at $$$5$$$ yen. Since no other team has the same average, the answer is the amount of yen team $$$\{1,2\}$$$ made, $$$5$$$.

$$$---------------------------------------------$$$

Problem Idea: codicon

Problem Preparation: codicon

Occurrences: Advanced 9, Intermediate 11