제출 #62883

#제출 시각아이디문제언어결과실행 시간메모리
62883fallingstar여행하는 상인 (APIO17_merchant)C++17
0 / 100
155 ms1692 KiB
#include <iostream> #include <algorithm> #define long long long using namespace std; const int N = 100 + 2; const int K = 1000 + 2; const long INF = 1e18; struct TFrac { long num, den; double val() { return den != 0 ? (double) num / den : 0; } }; auto maxDen = [](TFrac a, TFrac b) { return a.val() < b.val() || (a.val() == b.val() && a.den < b.den); }; auto minDen = [](TFrac a, TFrac b) { return a.val() < b.val() || (a.val() == b.val() && a.den > b.den); }; struct TState { TFrac f[2]; TFrac& operator[] (int id) { return f[id]; } TFrac operator[] (int id) const { return f[id]; } TState() {} TState(const TFrac &frac): f{frac, frac} {} TState(const TFrac &f0, const TFrac &f1): f{f0, f1} {} }; TState operator + (const TState &a, const TState &b) { TFrac p[4]; double maxVal = 0; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) { p[i * 2 + j] = {a[i].num + b[j].num, a[i].den + b[j].den}; maxVal = max(maxVal, p[i * 2 + j].val()); } return {*max_element(p, p + 4, minDen), *max_element(p, p + 4, maxDen)}; } int n, m, k; int priceBuy[N][K]; int priceSell[N][K]; long dist[N][N]; TState f[N][N]; int main() { cin >> n >> m >> k; for (int i = 1; i <= n; ++i) for (int j = 0; j < k * 2; ++j) if (j & 1) cin >> priceSell[i][j / 2]; else cin >> priceBuy[i][j / 2]; for (int i = 1; i <= n; ++i) { fill(dist[i] + 1, dist[i] + 1 + n, INF); dist[i][i] = 0; } for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; dist[u][v] = min(dist[u][v], (long) w); } // Floyd-Warshall algorithm for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { if (i == j || dist[i][j] == INF) continue; long num = 0, den = dist[i][j]; for (int l = 0; l < k; ++l) if (priceBuy[i][l] != -1 && priceBuy[i][l] < priceSell[j][l]) { num = max(num, (long) priceSell[j][l] - priceBuy[i][l]); } f[i][j] = TFrac{num, den}; } for (int l = 1; l <= n; ++l) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (dist[i][l] != INF && dist[l][j] != INF) { TState new_state = f[i][l] + f[l][j]; TFrac p[4] = {f[i][j][0], f[i][j][1], new_state[0], new_state[1]}; f[i][j] = TState {*max_element(p, p + 4, minDen), *max_element(p, p + 4, maxDen)}; } long ans = 0; for (int i = 1; i <= n; ++i) ans = max(ans, (long) f[i][i][0].val()); // for (int l = 0; l < k; ++l) // for (int j = 2; j <= n; ++j) // if (priceSell[j][l] > priceBuy[1][l] && priceBuy[1][l] != -1 && dist[1][j] != INF && dist[j][1] != INF) // ans = max(ans, (priceSell[j][l] - priceBuy[1][l]) / (dist[1][j] + dist[j][1])); cout << ans; 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...