Submission #739588

#	Time	Username	Problem	Language	Result	Execution time	Memory
739588		vjudge1	여행하는 상인 (APIO17_merchant)	C++17	100 / 100	472 ms	3060 KiB

merchant

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

int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, m, K;
        cin >> n >> m >> K;
        vector<vector<int>> buy(n, vector<int>(K));
        vector<vector<int>> sell(n, vector<int>(K));

        for (int i = 0; i < n; i++) {
                for (int j = 0; j < K; j++) {
                        cin >> buy[i][j] >> sell[i][j];
                }
        }

        vector<vector<int64_t>> d(n, vector<int64_t>(n, 1e18));
        vector<vector<bool>> cant(n, vector<bool>(n, 0));
        for (int i = 0; i < m; i++) {
                int u, v, c;
                cin >> u >> v >> c;
                u--, v--;
                d[u][v] = c;
        }
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int k = 0; k < n; k++) {
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                                d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
                        }
                }
        }

        for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                        cant[i][j] = d[i][j] > 5e17;
                }
        }
        int64_t l = 1, r = 1e10, res = 0;
        const int64_t LIMIT = 1e12 + 1;
        while (l <= r) {
                int64_t mid = l + r >> 1;
                auto dd = d;
                auto cantt = cant;
                for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                                if (cantt[i][j]) continue;
                                int64_t best = 0;
                                for (int k = 0; k < K; k++) {
                                        if (buy[i][k] != -1 && sell[j][k] != -1) best = max<int64_t>(best, sell[j][k] - buy[i][k]);
                                }
                                if (dd[i][j] > (LIMIT + best) / mid) cantt[i][j] = 1;
                                if (!cantt[i][j]) dd[i][j] = 1ll * d[i][j] * mid - best;
                        }
                }

                for (int i = 0; i < n; i++) dd[i][i] = 1;
                for (int k = 0; k < n; k++) {
                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < n; j++) {
                                        if (cantt[i][k] || cantt[k][j]) continue;
                                        dd[i][j] = min(dd[i][k] + dd[k][j], dd[i][j]);
                                }
                        }
                }

                bool ok = 0;
                for (int i = 0; i < n; i++) {
                        ok |= dd[i][i] <= 0;
                }
                if (ok) {
                        res = mid;
                        l = mid + 1;
                } else {
                        r = mid - 1;
                }
        }
        cout << res;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:43:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |                 int64_t mid = l + r >> 1;
      |                               ~~^~~

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