「JOISC 2017 Day 1」开荒者

单独一个点，假如固定每个操作的数目，则得到的草呈矩形，且形状不会应操作顺序变化而变化。所以最后的结果与操作顺序无关。同时发现当向上、下次数总和一定时，若无上下边界，则草地形状一样。

考虑枚举向上、向下次数和，可以通过差分扫描线的方式维护出草地的形状（由于一个点只会被加入一次，删除一次，所以扫描线点数 \On)\) 级别）。

考虑对于每一行对答案的贡献，设第 \i\) 每一株草的位置时 \a1 \dots a_m\) ，则向左向右对答案的贡献为 \f_i = maxa_1 – 1, c – a_m, max_{i = 1}^{m – 1}a{i + 1} – a{i})\) ，现在考虑上下的边界，答案为 \min_{i}max_{i \leq j \leq i + r – 1} f_j)\) ，可以用单调队列维护。
时间复杂度 \On^3)\) .

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

typedef long long ll;

const int N = 605;

int R, C, n, lim, m, f[N][3], q[3][N], l[3], r[3];

bool vis[N][N];

set <int> s;

ll ans;

struct Node {
    int x, y;
} a[N], b[N];

bool cmpx_Node a, Node b) {
    return a.x < b.x;
}

bool cmpy_Node a, Node b) {
    return a.y < b.y;
}

void solve_int k) {
    for int i = 1; i <= n; i++)
        vis[k][i] = vis[k - 1][i];

    if b[k].y > 0)
        vis[k][b[k].y] = 1;
    else
        vis[k][-b[k].y] = 0;

    f[k][0] = f[k][1] = f[k][2] = 0;

    for int i = 1, j = 0; i <= n; i++)
        if vis[k][i]) {
            f[k][2] = C - a[i].y;

            if j)
                f[k][0] = maxf[k][0], a[i].y - a[j].y - 1);
            else
                f[k][1] = a[i].y - 1;

            j = i;
        }
}

void init_int d) {
    sorta + 1, a + n + 1, cmpy_);

    for int i = 1; i <= n; i++) {
        b[++m] = Node) {
            a[i].x - d, i
        };
        b[++m] = Node) {
            a[i].x + 1, -i
        };
    }

    sortb + 1, b + m + 1, cmpx_);

    for int i = 1; i < m; i++)
        solve_i);
}

ll calc_int d) {
    for int i = 1; i <= m; i++)
        if b[i].y > 0)
            b[i].x -= d;

    bool ok = 1;

    while ok) {
        ok = 0;

        for int i = 1; i < m; i++)
            if b[i].x > b[i + 1].x) {
                ok = 1, swapb[i], b[i + 1]);
                solve_i), solve_i + 1);
            }
    }

    ll res = 4e9;

    for int i = 0; i < 3; i++)
        l[i] = 1, r[i] = 0;

    for int i = 1, j = 1; ; i++) {
        while j < m && b[j].x - b[i].x < R) {
            if b[j].x < b[j + 1].x) {
                for int k = 0; k < 3; k++) {
                    while l[k] <= r[k] && f[q[k][r[k]]][k] <= f[j][k])
                        r[k]--;

                    q[k][++r[k]] = j;
                }
            }

            j++;
        }

        if b[j].x - b[i].x < R)
            break;

        for int k = 0; k < 3; k++)
            while l[k] <= r[k] && q[k][l[k]] < i)
                l[k]++;

        res = minres, max1ll * f[q[0][l[0]]][0], 1ll * f[q[1][l[1]]][1] + f[q[2][l[2]]][2]));
    }

    return res;
}

int main) {
    scanf"%d%d%d", &R, &C, &n), ans = R + C - 2;

    for int i = 1; i <= n; i++)
        scanf"%d%d", &a[i].x, &a[i].y);

    sorta + 1, a + n + 1, cmpx_);

    lim = a[1].x - 1 + R - a[n].x;

    for int i = 1; i < n; i++)
        lim = maxlim, a[i + 1].x - a[i].x - 1);

    for int i = 1; i <= n; i++)
        for int j = 1; j <= n; j++) {
            if a[i].x - 1 + R - a[j].x >= lim)
                s.inserta[i].x - 1 + R - a[j].x);

            if a[j].x - a[i].x - 1 >= lim)
                s.inserta[j].x - a[i].x - 1);
        }

    init_*s.begin));

    int last = *s.begin);

    for int x : s) {
        ans = minans, x + calc_x - last)), last = x;

        if ans <= last)
            break;
    }

    printf"%lld\n", ans);
}