Submission #1147469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147469		Nelt	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	84 ms	2112 KiB

merchant

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 105, K = 1005;
__int128 dist[N][N], best[N][N], d[N][N];
ll s[N][K], b[N][K];

void solve()
{
    ll n, m, k;
    cin >> n >> m >> k;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= k; j++) cin >> b[i][j] >> s[i][j];
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++) dist[i][j] = i == j ? 0 : 1e18;
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++)
    for (ll x = 1; x <= k; x++) if (b[i][x] != -1 and s[j][x] != -1) best[i][j] = max(best[i][j], (__int128)b[i][x] - s[j][x]);
    while (m--)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = c;
    }
    for (ll k = 1; k <= n; k++)
    for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    // for (ll i = 1; i <= n; i++)
    // for (ll j = 1; j <= n; j++) cout << (ll)dist[i][j] << " \n"[j == n];
    ll l = 0, r = 1e13;
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) d[i][j] = best[i][j] - dist[i][j] * mid;
        for (ll k = 1; k <= n; k++)
        for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) d[i][j] = max(d[i][j], d[i][k] + d[k][j]);
        bool ok = false;
        for (ll k = 1; k <= n and !ok; k++)
        for (ll i = 1; i <= n and !ok; i++)
        for (ll j = 1; j <= n and !ok; j++) if (d[i][j] < d[i][k] + d[k][j]) ok = true;
        if (ok) l = mid + 1;
        else r = mid - 1;
    }
    cout << --l << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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