Points Selection

Let Alice keep some nonempty set of points $S$. Everything else gets removed.

If $C=\sum c_i$, then the final score for this kept set is

$$C-\sum_{i\in S} c_i + 2\left((\max_S x-\min_S x)+(\max_S y-\min_S y)\right).$$

So $C$ is fixed, and we only need to maximize

$$2\left((\max_S x-\min_S x)+(\max_S y-\min_S y)\right)-\sum_{i\in S} c_i.$$

Call that value $g(S)$.

The Important Rewrite

The rectangle part can be split into four independent-looking extremes:

$$2(\max x-\min x+\max y-\min y) = \max(2x)+\max(-2x)+\max(2y)+\max(-2y).$$

All maxes are over points in $S$.

So each kept point can contribute to any subset of these four roles:

• role $0$: maximize $2x$
• role $1$: maximize $-2x$
• role $2$: maximize $2y$
• role $3$: maximize $-2y$

A selected point may cover multiple roles. For example, if one point is both the rightmost and topmost kept point, it can provide both $2x$ and $2y$, and we should pay its cost only once.

That “pay once, cover several roles” part is the whole problem. The rest is bookkeeping.

Why This Is Enough

Suppose we already know which points provide the four extreme values. Any other kept point does not change $\max x$, $\min x$, $\max y$, or $\min y$. Since costs are nonnegative, keeping that extra point only subtracts more cost. So optimal play never needs useless passengers. No freeloaders. Rectangle math is ruthless like that.

Therefore the optimal kept set can be described by assigning each of the four roles to some points. There are only four roles, so we can DP over role masks.

DP Definition

Let

$$v_i = [2x_i, -2x_i, 2y_i, -2y_i].$$

For a mask $m$, define $dp[m]$ as the best value achievable after covering exactly the set of roles in $m$ using some selected points, where selected point costs are already subtracted.

Initially:

$$dp[0]=0,$$

and all other states are impossible.

When considering point $i$, we may use it to cover any nonempty subset $s$ of the four roles. Its contribution is

$$\sum_{k\in s} v_i[k] - c_i.$$

Then we transition:

$$ndp[m\cup s] = \max(ndp[m\cup s], dp[m]+\sum_{k\in s}v_i[k]-c_i).$$

We also keep the option of not using this point.

At the end, all four roles must be covered, so the best kept-set bonus is $dp[15]$.

The answer is

$$C+dp[15].$$

One Subtle Point

For $n=1$, this still works. The only point covers all four roles, contributing

$$2x-2x+2y-2y-c_i=-c_i.$$

Then $C+dp[15]=c_i-c_i=0$, which matches the rule that Alice cannot remove all points.

Complexity

There are $16$ masks and $15$ nonempty role subsets per point, so the runtime is

$$O(16\cdot 15\cdot n),$$

which is easily fine for $3\cdot 10^5$ points. Memory is $O(16)$.