Not sure if this is your case, but I also used the same technique and got WA on test no.17 Maybe this test case might help you?

2 3
3
5
1 4 1
2 100000 2
1 4 3

My code outputs 2 but now I see that it should be 1...T_T

NSA wants to know your location

That's true. Thank you.

Binary Search/Two Pointers. But I think it is more helpful to view it as adhoc where you have to make observations. In this case main observation based on vertical lines span the whole grid, and no horiztonal touching.

E and F aren't great either. My understanding is that CF wants to encourage problem writers and the bar for problem quality isn't set too high, so unless contest organizers want high quality original problems (which wasn't the case this time but in the past for this reason some companies had problems set by their own engineers and not outsourced) you should not have high expectations.

Hey,

I did not intend to copy/steal a problem by any means. Neither me nor the testers knew of this problem (and also no other task that is similar to div1D), otherwise it would be brought up. I'm sure you understand that we want to have tasks with as high quality as we can, and also being original. Still, I'll try to look deeper for tasks similar to mine, but honestly, I think it's impossible to assure my problems are original.

Anyway, I hope you still managed to enjoy some other tasks from the round :).

The problemis that you need to run a bfs to find the closest vertex instead of finding any vertex like you do with your dfs.

Добавил такой тест, будет использоваться в дорешке/вирт контестах.

In the presented solution, we look at the subarray by its end borders. So,

update: I fixed my error, a pretty big one, actually. I was updating the subtrees with p[l]^p[r] instead of x^p[l]^p[r].

We need to find 3 points, such that |x1 — x2| + |y1 — y2| + |x2 — x3| + |y2 — y3| + |x3 — x1| + |y3 — y1| is maximal. We are going to try all possibilities of assigning + or — to each of these pairs. For example if we have +--+-+, we are going to have (x1 — x2) — (y1 — y2) — (x2 — x3) + (y2 — y3) — (x3 — x1) + (y3 — y1), which evaluates to 2*x1 — 2*y1 — 2*x2 + 2*y2 + 0*x3 + 0*y3. c1 here is the coefficient next to x1, c2 is the coefficient next to y1...c6 is the coefficient next to y3. So we calculate arrays P, Q, R as in the editorial and then do dp to get the maximum for such combination. The dp state is [current point][taken points]. You can also check out my implementation 45365331.

Thank you :)