Submission #748173

#	Time	Username	Problem	Language	Result	Execution time	Memory
748173		c2zi6	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	155 ms	4272 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
using ld = long double;
using ll = long long;

ll n;
vector<vector<ll>> cst, prf;

bool can(ll ans) {
    vector<vector<ll>> gp(n, vector<ll>(n));
    for (ll u = 0; u < n; u++) {
        for (ll v = 0; v < n; v++) {
            if (cst[u][v] >= 5e17 / ans) gp[u][v] = -1e18;
            else gp[u][v] = prf[u][v] - cst[u][v] * ans;
        }
    }
    for (ll k = 0; k < n; k++) {
        for (ll u = 0; u < n; u++) {
            for (ll v = 0; v < n; v++) {
                gp[u][v] = max(gp[u][v], gp[u][k] + gp[k][v]);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (gp[i][i] >= 0) return true;
    }
    return false;
}

void solve() {
    ll m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> b(n), s(n);
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < k; j++) {
            ll x, y;
            cin >> x >> y;
            b[i].push_back(x);
            s[i].push_back(y);
        }
    }
    cst = vector<vector<ll>>(n, vector<ll>(n, 1e18));
    for (ll i = 0; i < m; i++) {
        ll u, v, t;
        cin >> u >> v >> t;
        u--, v--;
        cst[u][v] = t;
    }
    for (ll k = 0; k < n; k++) {
        for (ll u = 0; u < n; u++) {
            for (ll v = 0; v < n; v++) {
                cst[u][v] = min(cst[u][v], cst[u][k] + cst[k][v]);
            }
        }
    }
    prf = vector<vector<ll>>(n, vector<ll>(n, 0));
    for (ll u = 0; u < n; u++) {
        for (ll v = 0; v < n; v++) {
            for (ll i = 0; i < k; i++) {
                if (s[v][i] == -1 || b[u][i] == -1) continue;
                prf[u][v] = max(prf[u][v], s[v][i] - b[u][i]);
            }
        }
    }

    /*
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            cout << cst[u][v] << " ";
        }
        cout << endl;
    }
    cout << endl;
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            cout << prf[u][v] << " ";
        }
        cout << endl;
    }
    cout << endl;
    */
    ll l = 0, r = 1e11;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (can(m)) l = m;
        else r = m;
    }
    cout << l << endl;
}

int main() {
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

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