Submission #704082

#	Time	Username	Problem	Language	Result	Execution time	Memory
704082		Cyanmond	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	81 ms	2132 KiB

merchant

#include <bits/stdc++.h>

using i64 = long long;
constexpr int inf32 = 1 << 30;
constexpr i64 inf = 1ll << 50;

void calcMinDist(std::vector<std::vector<i64>> &graph) {
    const int n = (int)graph.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

void calcMaxDist(std::vector<std::vector<i64>> &graph) {
    const int n = (int)graph.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                graph[i][j] = std::max(graph[i][j], graph[i][k] + graph[k][j]);
                graph[i][j] = std::min(graph[i][j], inf / 10);
            }
        }
    }
}

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>> buyList(N, std::vector<i64>(K)), sellList(N, std::vector<i64>(K));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < K; ++j) {
            std::cin >> buyList[i][j] >> sellList[i][j];
        }
    }
    std::vector<std::vector<i64>> baseGraph(N, std::vector<i64>(N, inf32));
    for (int i = 0; i < M; ++i) {
        int v, w;
        i64 t;
        std::cin >> v >> w >> t;
        --v, --w;
        baseGraph[v][w] = t;
    }
    calcMinDist(baseGraph);
    std::vector<std::vector<i64>> profitList(N, std::vector<i64>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            i64 ma = 0;
            for (int k = 0; k < K; ++k) {
                if (buyList[i][k] == -1 or sellList[j][k] == -1) {
                    continue;
                }
                ma = std::max(ma, sellList[j][k] - buyList[i][k]);
            }
            profitList[i][j] = ma;
        }
    }

    i64 ok = 0, ng = inf32;
    while (ng - ok > 1) {
        const auto mid = (ok + ng) / 2;
        std::vector<std::vector<i64>> realGraph(N, std::vector<i64>(N));
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                realGraph[i][j] = (profitList[i][j] - mid * baseGraph[i][j]);
                realGraph[i][j] = std::max(realGraph[i][j], -inf);
            }
        }
        for (int i = 0; i < N; ++i) {
            realGraph[i][i] = -inf;
        }
        calcMaxDist(realGraph);
        bool isOk = false;
        for (int i = 0; i < N; ++i) {
            if (realGraph[i][i] >= 0) {
                isOk = true;
            }
        }
        if (isOk) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    std::cout << ok << std::endl;
}

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