Submission #847883

#	Time	Username	Problem	Language	Result	Execution time	Memory
847883		popovicirobert	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	91 ms	3504 KiB

merchant

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

constexpr ll INF = (ll) 1e18;


int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> buy(n + 1, vector<int>(k + 1));
    vector<vector<int>> sell(n + 1, vector<int>(k + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> buy[i][j] >> sell[i][j];
        }
    }

    vector<vector<ll>> travel_time(n + 1, vector<ll>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        travel_time[i][i] = 0;
    }

    while (m--) {
        int x, y, t;
        cin >> x >> y >> t;
        travel_time[x][y] = t;
    }

    for (int z = 1; z <= n; z++) {
        auto temp = travel_time;
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                temp[x][y] = min(temp[x][y], travel_time[x][z] + travel_time[z][y]);
            }
        }
        travel_time = move(temp);
    }

    vector<vector<ll>> best_profit(n + 1, vector<ll>(n + 1));
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            for (int item = 1; item <= k; item++) {
                if (buy[x][item] != -1 && sell[y][item] != -1) {
                    best_profit[x][y] = max(best_profit[x][y], 1LL * sell[y][item] - buy[x][item]);
                }
            }
        }
    }

    auto Check = [&](ll coef) {
        vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, -INF));
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                if (x != y && travel_time[x][y] != INF) {
                    dp[x][y] = best_profit[x][y] - travel_time[x][y] * coef;
                }
            }
        }

        for (int z = 1; z <= n; z++) {
            auto temp = dp;
            for (int x = 1; x <= n; x++) {
                for (int y = 1; y <= n; y++) {
                    temp[x][y] = max(temp[x][y], dp[x][z] + dp[z][y]);            
                }
            }
            dp = move(temp);
        }  

        for (int i = 1; i <= n; i++) {
            if (dp[i][i] >= 0) {
                return false;
            }
        }

        return true;
    };

    ll result = (1LL << 31);
    for (int step = 1 << 30; step; step >>= 1) {
        if (result >= step && Check(result - step)) {
            result -= step;
        }
    }

    cout << result - 1;

    return 0;
}

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