Submission #704137

#TimeUsernameProblemLanguageResultExecution timeMemory
704137four_specksTravelling Merchant (APIO17_merchant)C++17
0 / 100
30 ms2128 KiB
#include <bits/stdc++.h> using namespace std; namespace { } // namespace void solve() { int n, m, k; cin >> n >> m >> k; vector a(n, vector<array<long, 2>>(k)); 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 dist(n, vector<long>(n, LONG_MAX >> 32)); 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 frac = [&](const array<long, 2> &lhs, const array<long, 2> &rhs) -> array<long, 2> { return {lhs[0] + rhs[0], lhs[1] + rhs[1]}; }; auto comp = [&](const array<long, 2> &lhs, const array<long, 2> &rhs) -> bool { return lhs[0] * rhs[1] < rhs[0] * lhs[1]; }; vector dp(n, vector<array<long, 2>>(n, {0, LONG_MAX >> 32})); for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { long x = 0; for (int i = 0; i < k; i++) { if (min(a[u][i][0], a[v][i][1]) != -1 && a[v][i][1] > a[u][i][0]) x = max(x, a[v][i][1] - a[u][i][0]); } dp[u][v] = {x, 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], frac(dp[u][s], dp[s][v]), comp); } } long res = 0; for (int u = 0; u < n; u++) res = max(res, dp[u][u][0] / dp[u][u][1]); cout << res << '\n'; } 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...