# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
111456 | 2019-05-15T11:55:03 Z | diamond_duke | Travelling Merchant (APIO17_merchant) | C++11 | 74 ms | 1280 KB |
#include <algorithm> #include <cstring> #include <cstdio> using ll = long long; inline void floyd(ll dis[][105], int n) { for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]); } } } int buy[105][1005], sell[105][1005], profit[105][105]; ll dis[105][105], cost[105][105]; int main() { // freopen("APIO2017-T3.in", "r", stdin); int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) scanf("%d", buy[i] + j); for (int j = 0; j < k; j++) scanf("%d", sell[i] + j); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int x = 0; x < k; x++) { if (~buy[i][x] && ~sell[j][x]) profit[i][j] = std::max(profit[i][j], sell[j][x] - buy[i][x]); } } } memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dis[--u][--v] = w; } floyd(dis, n); int l = 0, r = 1e9, res = -1; while (l <= r) { int mid = l + r >> 1; memset(cost, 0x3f, sizeof(cost)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dis[i][j] < 1e18) cost[i][j] = (ll)dis[i][j] * mid - profit[i][j]; } } floyd(cost, n); bool flg = false; for (int i = 0; i < n; i++) flg |= cost[i][i] <= 0; if (flg) { res = mid; l = mid + 1; } else r = mid - 1; } printf("%d\n", res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 74 ms | 1272 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 896 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 43 ms | 1280 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 896 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |