Submission #1260625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260625		khoile08	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	45 ms	1352 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
#define ll long long

const int inf = 1e9;
const ll INF = 1e18;
const int N = 105;
const int K = 1005;

int n, m, k;
int a[N][K][2];
array<array<ll, N>, N> d, g, v;

void Floyd(array<array<ll, N>, N> &d) {
    FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    //freopen("task.inp", "r", stdin);
//    freopen("task.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    FOR(i, 1, n) FOR(j, 1, k) cin >> a[i][j][0] >> a[i][j][1];
    FOR(i, 1, n) FOR(j, 1, n) g[i][j] = INF;
    FOR(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], 1LL * w);
    }

    FOR(p, 1, k) FOR(i, 1, n) FOR(j, 1, n) if(a[i][p][0] != -1 && a[j][p][1] != -1) v[i][j] = max(v[i][j], 1LL * a[j][p][1] - a[i][p][0]);
    Floyd(g);
    int l = 0, r = inf, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        FOR(i, 1, n) FOR(j, 1, n) {
            if(g[i][j] != INF) d[i][j] = -g[i][j] * mid + v[i][j];
            else d[i][j] = -INF;
        }
        FOR(p, 1, n) FOR(i, 1, n) FOR(j, 1, n) d[i][j] = max(d[i][j], d[i][p] + d[p][j]);
        bool ok = 0;
        FOR(i, 1, n) ok |= (d[i][i] >= 0);
        if(ok) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << '\n';
}

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