The goal of this blog is to provide an alternative editorial to AtCoder Regular Contest 231 Problem A which will hopefully be easier, for at least some people, to reason about compared to the official editorial.

For the sake of simplicity, we will have that the $$$ \min $$$ of the empty set is $$$ 10^{100} $$$ as a convention.

First, let us define a sequence $$$ ( a_0, a_1, \ldots, a_N ) $$$ as follows: $$$ a_0 = 0 $$$, and for $$$ k \gt 0 $$$, $$$ a_k $$$ is the minimum possible total cost immediately after event $$$ k $$$ on the condition that the sword is used on event $$$ k $$$. The answer is then

Now, let $$$ (X_0, Y_0) = (0, 0) $$$. For $$$ k \gt 0 $$$, we have

which can be seen by considering the cases when the sword was most recently used on event $$$ j $$$ (with $$$ j \gt 0 $$$), or the sword was never used previously with $$$ j = 0 $$$. If we try to naively implement this into a program, we will probably end up with a time complexity that is quadratic in $$$ N $$$, which is too slow. To help with this, we define a family of functions $$$ g_{k, X} $$$ as follows:

for $$$ X \in \{ 0, 1, \ldots, 499 \} $$$ and $$$ k \in \{ 0, 1, \ldots, N \} $$$. Then for $$$ k \gt 0 $$$, we have

so if we can compute $$$ g_{k, X}(Y_k) $$$ in constant time, we are done. The trick is to notice that for $$$ k \lt N $$$, we have

when $$$ X \neq X_k $$$, and

for $$$ Y \in \{ 0, 1, \ldots, 499 \} $$$.

Below is an implementation that uses this idea.

#include<bits/stdc++.h>
using namespace std;

long long a[250001];
long long gx[500][500];

long long INF = 1e18;

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i != 250001; ++i) {
        a[i] = INF;
    }
    for (int i = 0; i != 500; ++i) for (int j = 0; j != 500; ++j) gx[i][j] = ((i == 0) ? j * j : INF);

    queue<int> Z;
    long long sumz = 0;
    for (int k = 1; k <= n; ++k) {
        long long x, y, z;
        cin >> x >> y >> z;
        Z.push(z);

        long long mi = INF;
        for (int X = 0; X != 500; ++X) mi = min(mi, (X - x) * (X - x) + gx[X][y]);
        a[k] = sumz + mi;

        sumz += z;
        for (int Y = 0; Y != 500; ++Y) gx[x][Y] = min(gx[x][Y], a[k] - sumz + (Y - y) * (Y - y));
    }

    long long ans = sumz;
    for (int k = 1; k <= n; ++k) {
        sumz -= Z.front();
        ans = min(ans, a[k] + sumz);
        Z.pop();
    }

    cout << ans << '\n';
}

signed main() {
    int t;
    cin >> t;

    while (t--) solve();

    return 0;
}