提出 #18769236

---

ソースコード 拡げる

#include <atcoder/mincostflow>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;
using namespace atcoder;
using uint = unsigned int;
using ll = long long;

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

    int n;
    cin >> n;
    struct Stone {
        ll size, num;
        int cost;
    };
    vector<int> offset(n + 1);
    vector<vector<Stone>> stones(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        offset[i + 1] = offset[i] + k;
        stones[i] = vector<Stone>(k);
        for (int j = 0; j < k; j++) {
            cin >> stones[i][j].size >> stones[i][j].cost >> stones[i][j].num;
        }
        sort(stones[i].begin(), stones[i].end(),
             [&](const Stone& l, const Stone& r) { return l.size < r.size; });
    }
    int sv = offset[n], tv = sv + 1;

    struct E {
        int to, rev, cap;
        ll dist;
    };
    mcf_graph<int, ll> g(tv + 1);

    const int INF_CAP = int(1e9);
    for (int i = 0; i < n; i++) {
        int k = int(stones[i].size());
        int bk = sv;
        for (int j = 0; j < k; j++) {
            // x_ij >= x_i{j-1}
            int nw = offset[i] + j;
            g.add_edge(nw, bk, INF_CAP, 0);
            g.add_edge(bk, nw, INF_CAP, stones[i][j].num);
            g.add_edge(bk, nw, stones[i][j].cost, 0);
            bk = nw;
        }
        g.add_edge(bk, tv, INF_CAP, 0);
        g.add_edge(tv, bk, INF_CAP, 0);
    }

    int m;
    cin >> m;
    for (int ph = 0; ph < m; ph++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--;
        v--;
        int ku = int(stones[u].size());
        int kv = int(stones[v].size());
        for (int i = 0; i < ku; i++) {
            for (int j = 0; j < kv; j++) {
                if (stones[u][i].size + w < stones[v][j].size) {
                    // x_ui <= x_v(j-1)
                    int vjn1 = (j == 0 ? sv : offset[v] + j - 1);
                    g.add_edge(vjn1, offset[u] + i, INF_CAP, 0);
                    break;
                }
            }
        }
    }

    auto slope = g.slope(sv, tv, 30000);
    using Line = tuple<ll, int, ll>;
    vector<Line> lines;
    for (int i = 0; i < int(slope.size()) - 1; i++) {
        auto a = slope[i], b = slope[i + 1];
        lines.push_back(Line{(b.second - a.second) / (b.first - a.first), a.first, a.second});
    }

    int q;
    cin >> q;
    for (int ph = 0; ph < q; ph++) {
        ll a;
        cin >> a;
        auto it = lower_bound(lines.begin(), lines.end(), Line{a, -1, -1});
        if (it == lines.end()) {
            cout << -1 << "\n";
            continue;
        }
        int cap_flow;
        ll flow;
        tie(ignore, cap_flow, flow) = *it;
        ll sum = cap_flow * a - flow;
        cout << sum << "\n";
    }
    return 0;
}

提出情報

ジャッジ結果