提出 #18766903

---

ソースコード 拡げる

#include <atcoder/mincostflow>

#include <iostream>
#include <vector>

using namespace std;
using namespace atcoder;
using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> x(n), y(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> v[i];
    }

    int m;
    cin >> m;
    const int TEN9 = (int)(1e9);
    vector<int> le(n + 1, -1), ri(n + 1, TEN9), dw(n + 1, -1), up(n + 1, TEN9);
    for (int i = 0; i < m; i++) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'L') le[b] = max(le[b], a);
        if (c == 'R') ri[b] = min(ri[b], a);
        if (c == 'D') dw[b] = max(dw[b], a);
        if (c == 'U') up[b] = min(up[b], a);
    }
    for (int i = 1; i <= n; i++) {
        le[i] = max(le[i], le[i - 1]);
        ri[i] = min(ri[i], ri[i - 1]);
        dw[i] = max(dw[i], dw[i - 1]);
        up[i] = min(up[i], up[i - 1]);
    }

    ll ans = 0;
    const ll BIG = ll(1e15);

    for (int k = 1; k <= n; k++) {
        mcf_graph<int, ll> g(2 * n + 2 * k + 2);
        int sv = 2 * n + 2 * k, tv = sv + 1;

        for (int i = 0; i < n; i++) {
            g.add_edge(i, n + i, 1, BIG - v[i]);
        }

        for (int i = 0; i < k; i++) {
            g.add_edge(sv, 2 * n + i, 1, 0);
            for (int j = 0; j < n; j++) {
                if (le[i] < x[j] && x[j] < ri[k - 1 - i]) {
                    g.add_edge(2 * n + i, j, 1, 0);
                }
                if (dw[i] < y[j] && y[j] < up[k - 1 - i]) {
                    g.add_edge(n + j, 2 * n + k + i, 1, 0);
                }
            }
            g.add_edge(2 * n + k + i, tv, 1, 0);
        }

        auto mcf = g.flow(sv, tv, TEN9);
        if (mcf.first == k) {
            ans = max(ans, k * BIG - mcf.second);
        }
    }
    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果