Trucks and Cities
Contest: Educational Codeforces Round 58 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, dp

There are $$$n$$$ cities along the road, which can be represented as a straight line. The $$$i$$$-th city is situated at the distance of $$$a_i$$$ kilometers from the origin. All cities are situated in the same direction from the origin. There are $$$m$$$ trucks travelling from one city to another.

Each truck can be described by $$$4$$$ integers: starting city $$$s_i$$$, finishing city $$$f_i$$$, fuel consumption $$$c_i$$$ and number of possible refuelings $$$r_i$$$. The $$$i$$$-th truck will spend $$$c_i$$$ litres of fuel per one kilometer.

When a truck arrives in some city, it can be refueled (but refueling is impossible in the middle of nowhere). The $$$i$$$-th truck can be refueled at most $$$r_i$$$ times. Each refueling makes truck's gas-tank full. All trucks start with full gas-tank.

All trucks will have gas-tanks of the same size $$$V$$$ litres. You should find minimum possible $$$V$$$ such that all trucks can reach their destinations without refueling more times than allowed.

Input format:
First line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 400$$$, $$$1 \le m \le 250000$$$) — the number of cities and trucks.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i < a_{i+1}$$$) — positions of cities in the ascending order.

Next $$$m$$$ lines contains $$$4$$$ integers each. The $$$i$$$-th line contains integers $$$s_i$$$, $$$f_i$$$, $$$c_i$$$, $$$r_i$$$ ($$$1 \le s_i < f_i \le n$$$, $$$1 \le c_i \le 10^9$$$, $$$0 \le r_i \le n$$$) — the description of the $$$i$$$-th truck.

Output format:
Print the only integer — minimum possible size of gas-tanks $$$V$$$ such that all trucks can reach their destinations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's look at queries in details:

1. the $$$1$$$-st truck must arrive at position $$$7$$$ from $$$2$$$ without refuelling, so it needs gas-tank of volume at least $$$50$$$.
2. the $$$2$$$-nd truck must arrive at position $$$17$$$ from $$$2$$$ and can be refueled at any city (if it is on the path between starting point and ending point), so it needs gas-tank of volume at least $$$48$$$.
3. the $$$3$$$-rd truck must arrive at position $$$14$$$ from $$$10$$$, there is no city between, so it needs gas-tank of volume at least $$$52$$$.
4. the $$$4$$$-th truck must arrive at position $$$17$$$ from $$$10$$$ and can be refueled only one time: it's optimal to refuel at $$$5$$$-th city (position $$$14$$$) so it needs gas-tank of volume at least $$$40$$$.
5. the $$$5$$$-th truck has the same description, so it also needs gas-tank of volume at least $$$40$$$.
6. the $$$6$$$-th truck must arrive at position $$$14$$$ from $$$2$$$ and can be refueled two times: first time in city $$$2$$$ or $$$3$$$ and second time in city $$$4$$$ so it needs gas-tank of volume at least $$$55$$$.

Example input:
7 6
2 5 7 10 14 15 17
1 3 10 0
1 7 12 7
4 5 13 3
4 7 10 1
4 7 10 1
1 5 11 2

Example output:
55

Editorial:
First (bonus) solution: implement idea from Blogewoosh #6. Time complexity will be somewhat $$$O((q + \log{q} \log{\text{MAX}})n)$$$ and space complexity is $$$O(n + q)$$$.
Honest solution: Note, that for each truck lower bound on the answer is $$$\max(c_i \cdot (a[p_{j + 1}] - a[p_{j}])) = c_i \cdot \max(a[p_{j + 1}] - a[p_j])$$$, where $$$p_0 = s_i, p_1, p_2, \dots, p_{r_i + 1} = f_i$$$ is optimal partition of $$$[a[s_i], a[f_i]]$$$ on $$$r_i + 1$$$ segments (partition which minimize maximum length of segment) and doesn't depend on $$$c_i$$$ of truck.
So, it enough to calculate $$$d[l][r][k]$$$ — optimal partition of segment $$$[a[l], a[r]]$$$ on $$$k$$$ segments.
Let $$$opt[l][r][k]$$$ be position, where last segment starts in partition with value $$$d[l][r][k]$$$. Note, that $$$opt[l][r][k] \le opt[l][r + 1][k]$$$.
On the other hand, $$$d[l][r][k] = \min\limits_{l \le j \le r}(\max(d[l][j][k - 1], a[r] - a[j]))$$$. But $$$d[l][j][k - 1] \le d[l][j + 1][k - 1]$$$ and $$$a[r] - a[j] > a[r] - a[j + 1]$$$, then $$$\max(d[l][j][k - 1], a[r] - a[j])$$$ is somewhat "convex".
Finally, best $$$j$$$ is no more than $$$opt[l][r][k]$$$, And we can look at $$$j$$$ as second pointer (along with $$$r$$$ as first pointer). So we can for each $$$r$$$ move $$$j$$$ while answer "relaxes" (while answer is decreasing or staying same). In result, for each $$$l$$$ and $$$k$$$ there will be $$$O(n)$$$ operations in total.
Optimizing memory consumption is easy, if we notice that we can iterate over $$$l$$$ but not save it as state of dp.
In the end, time complexity is $$$O(n^3 + q)$$$ and space complexity is $$$O(n^2 + q)$$$.