Submission #409211

#	Time	Username	Problem	Language	Result	Execution time	Memory
409211		tengiz05	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	209 ms	3224 KiB

merchant

#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1e18 + 1999;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<i64>> e(n, std::vector<i64>(n, inf)), prof(n, std::vector<i64>(n, 0));
    std::vector<std::vector<i64>> b(n, std::vector<i64>(k)), s(n, std::vector<i64>(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++)
            std::cin >> b[i][j] >> s[i][j];
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        u--;
        v--;
        e[u][v] = std::min(e[u][v], i64(w));
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                e[i][j] = std::min(e[i][j], e[i][k] + e[k][j]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int c = 0; c < k; c++) {
                if (~b[i][c] && ~s[j][c]) {
                    prof[i][j] = std::max(prof[i][j], s[j][c] - b[i][c]);
                }
            }
        }
    }
    auto check = [&](int times) -> bool {
        std::vector<std::vector<i64>> a(n, std::vector<i64>(n, -inf));
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (e[i][j] != inf)
                        a[i][j] = std::max(a[i][j], prof[i][j] - e[i][j] * times);
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    a[i][j] = std::max(a[i][j], a[i][k] + a[k][j]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i][i] >= 0) {
                return true;
            }
        }
        return false;
    };
    i64 l = -1, r = 1e9 + 10;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    std::cout << l << '\n';
    return 0;
}

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