Submission #842362

#	Time	Username	Problem	Language	Result	Execution time	Memory
842362		popovicirobert	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	1043 ms	3408 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<pair<int, int>>> g(n + 1);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
    }

    auto Check = [&](ll C) {
        for (int source = 1; source <= n; source++) {
            queue<pair<int, int>> Q;
            Q.push({source, 0});

            vector<vector<bool>> inQ(n + 1, vector<bool>(k + 1));
            inQ[source][0] = true;

            vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -INF));
            dp[source][0] = 0;

            vector<vector<int>> cnt(n + 1, vector<int>(k + 1));
            vector<bool> mark(n + 1);

            auto Go = [&](int node, int item, ll cost) {
                if (cost > dp[node][item]) {
                    dp[node][item] = cost;
                    if (!inQ[node][item]) {
                        Q.push({node, item});
                        inQ[node][item] = true;
                    }
                } else if (cost == dp[node][item]) {
                    mark[node] = true;
                }
            };

            while (Q.size()) {
                int node, item;
                tie(node, item) = Q.front();
                Q.pop();

                inQ[node][item] = false;

                cnt[node][item]++;
                if (cnt[node][item] >= n * k) {
                    return true;    
                }

                for (auto edge : g[node]) {
                    Go(edge.first, item, dp[node][item] - 1LL * edge.second * C);
                }

                if (item == 0) {
                    for (int new_item = 1; new_item <= k; new_item++) {
                        if (buy[node][new_item] != -1) {
                            Go(node, new_item, dp[node][0] - buy[node][new_item]);
                        }
                    }
                } else {
                    if (sell[node][item] != -1) {
                        Go(node, 0, dp[node][item] + sell[node][item]);
                    }
                }
            }

            if (dp[source][0] > 0 || (dp[source][0] == 0 && mark[source])) {
                return true;
            }

            // cerr << "source: " << source << "\n";
            // for (int i = 1; i <= n; i++) {
            //     for (int j = 0; j <= k; j++) {
            //         cerr << dp[i][j] << " ";
            //     }
            //     cerr << "\n";
            // }
            // cerr << "\n";
        }

        return false;
    };

    ll result = 0;
    for (ll step = 1LL << 30; step; step >>= 1) {
        if (Check(result + step)) {
            result += step;
        }
    }

    cout << result;

    return 0;
}

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