Submission #704705

#	Time	Username	Problem	Language	Result	Execution time	Memory
704705		four_specks	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	86 ms	4428 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector a(n, vector<array<long, 2>>(k));
    for (int u = 0; u < n; u++)
    {
        for (auto &[x, y] : a[u])
            cin >> x >> y;
    }

    vector<tuple<int, int, long>> edges(m);
    for (auto &[u, v, w] : edges)
        cin >> u >> v >> w, --u, --v;

    vector util(n, vector<long>(n));
    for (int u = 0; u < n; u++)
    {
        for (int v = 0; v < n; v++)
        {
            for (int i = 0; i < k; i++)
            {
                if (min(a[u][i][0], a[v][i][1]) != -1)
                    util[u][v] = max(util[u][v], a[v][i][1] - a[u][i][0]);
            }
        }
    }

    vector dist(n, vector<long>(n, 1l << 30));
    for (auto [u, v, w] : edges)
        dist[u][v] = w;
    for (int s = 0; s < n; s++)
    {
        for (int u = 0; u < n; u++)
        {
            for (int v = 0; v < n; v++)
                dist[u][v] = min(dist[u][v], dist[u][s] + dist[s][v]);
        }
    }

    auto check = [&](long mid) -> bool
    {
        vector dp(n, vector<long>(n));
        for (int u = 0; u < n; u++)
        {
            for (int v = 0; v < n; v++)
                dp[u][v] = util[u][v] - mid * dist[u][v];
        }
        for (int s = 0; s < n; s++)
        {
            for (int u = 0; u < n; u++)
            {
                for (int v = 0; v < n; v++)
                    dp[u][v] = max(dp[u][v], dp[u][s] + dp[s][v]);
            }
        }

        for (int u = 0; u < n; u++)
        {
            if (dp[u][u] >= 0)
                return 1;
        }

        return 0;
    };

    long lo = 0, hi = 1l << 30;
    while (lo < hi)
    {
        long mid = (lo + hi + 1) / 2;
        if (check(mid))
            lo = mid;
        else
            hi = mid - 1;
    }

    cout << lo << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34