Submission #568818

#	Time	Username	Problem	Language	Result	Execution time	Memory
568818		joshjms	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	132 ms	4336 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const long long mod = 1e9 + 7;

int n, m, k, b[105][1005], s[105][1005];
int g[105][105], ng[105][105], nng[105][105];

int L, R, ans;

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

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            g[i][j] = 1e9;
        }
    }

    for(int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[u][v] = w;
    }

    for(int rep = 0; rep < 2; rep++) {
        for(int l = 1; l <= n; l++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
                }
            }
        }
    }   

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {

            int maxProfit = 0;

            for(int l = 1; l <= k; l++) {
                if(b[i][l] != -1 && s[j][l] != -1) {
                    maxProfit = max(maxProfit, s[j][l] - b[i][l]);
                }
            }

            if(maxProfit > 0) {
                ng[i][j] = maxProfit;
            }
        }
    }

    L = 1, R = 1e9, ans = 0;

    while(L <= R) {

        int mid = (L + R) / 2;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                nng[i][j] = -1e18;
            }
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                nng[i][j] = ng[i][j] - g[i][j] * mid;
            }
        }

        for(int rep = 0; rep < 2; rep++) {
            for(int l = 1; l <= n; l++) {
                for(int i = 1; i <= n; i++) {
                    for(int j = 1; j <= n; j++) {
                        nng[i][j] = max(nng[i][j], nng[i][l] + nng[l][j]);       
                    }
                }
            }
        }  

        bool possible = false;

        for(int i = 1; i <= n; i++)
            if(nng[i][i] >= 0) {possible = true; break;}

        if(possible)
            ans = mid, L = mid + 1;
        else R = mid - 1;
    }

    cout << ans << "\n";
}

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve ();
}

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