Submission #704704

#TimeUsernameProblemLanguageResultExecution timeMemory
704704four_specksTravelling Merchant (APIO17_merchant)C++17
0 / 100
1 ms596 KiB
#include <bits/stdc++.h> using namespace std; namespace { } // namespace void solve() { int n, m, k; cin >> n >> m >> k; vector<vector<array<long, 2>>> a(n); for (int u = 0; u < n; u++) { for (auto &[x, y] : a[u]) cin >> x >> y; } vector<tuple<int, int, long>> edges(m); for (auto &[u, v, w] : edges) cin >> u >> v >> w, --u, --v; vector util(n, vector<long>(n)); for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { for (int i = 0; i < k; i++) { if (min(a[u][i][0], a[v][i][1]) != -1) util[u][v] = max(util[u][v], a[v][i][1] - a[u][i][0]); } } } vector dist(n, vector<long>(n, 1l << 30)); for (auto [u, v, w] : edges) dist[u][v] = w; for (int s = 0; s < n; s++) { for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) dist[u][v] = min(dist[u][v], dist[u][s] + dist[s][v]); } } auto check = [&](long mid) -> bool { vector dp(n, vector<long>(n)); for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) dp[u][v] = util[u][v] - mid * dist[u][v]; } for (int s = 0; s < n; s++) { for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) dp[u][v] = max(dp[u][v], dp[u][s] + dp[s][v]); } } for (int u = 0; u < n; u++) { if (dp[u][u] >= 0) return 1; } return 0; }; long lo = 0, hi = 1l << 30; while (lo < hi) { long mid = (lo + hi + 1) / 2; if (check(mid)) lo = mid; else hi = mid - 1; } } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...