# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
111457 | 2019-05-15T11:58:12 Z | diamond_duke | Travelling Merchant (APIO17_merchant) | C++11 | 103 ms | 3448 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%d", buy[i] + j, 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 | Correct | 71 ms | 1212 KB | Output is correct |
2 | Correct | 36 ms | 1280 KB | Output is correct |
3 | Correct | 33 ms | 1280 KB | Output is correct |
4 | Correct | 9 ms | 896 KB | Output is correct |
5 | Correct | 11 ms | 896 KB | Output is correct |
6 | Correct | 7 ms | 896 KB | Output is correct |
7 | Correct | 7 ms | 896 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 7 ms | 896 KB | Output is correct |
10 | Correct | 7 ms | 896 KB | Output is correct |
11 | Correct | 11 ms | 1024 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 7 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 896 KB | Output is correct |
2 | Correct | 8 ms | 896 KB | Output is correct |
3 | Correct | 7 ms | 896 KB | Output is correct |
4 | Correct | 6 ms | 896 KB | Output is correct |
5 | Correct | 15 ms | 988 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 7 ms | 896 KB | Output is correct |
8 | Correct | 8 ms | 896 KB | Output is correct |
9 | Correct | 10 ms | 896 KB | Output is correct |
10 | Correct | 8 ms | 896 KB | Output is correct |
11 | Correct | 10 ms | 884 KB | Output is correct |
12 | Correct | 10 ms | 1024 KB | Output is correct |
13 | Correct | 9 ms | 896 KB | Output is correct |
14 | Correct | 11 ms | 896 KB | Output is correct |
15 | Correct | 11 ms | 896 KB | Output is correct |
16 | Correct | 8 ms | 896 KB | Output is correct |
17 | Correct | 7 ms | 896 KB | Output is correct |
18 | Correct | 2 ms | 516 KB | Output is correct |
19 | Correct | 7 ms | 1024 KB | Output is correct |
20 | Correct | 8 ms | 1024 KB | Output is correct |
21 | Correct | 9 ms | 896 KB | Output is correct |
22 | Correct | 8 ms | 896 KB | Output is correct |
23 | Correct | 7 ms | 896 KB | Output is correct |
24 | Correct | 7 ms | 896 KB | Output is correct |
25 | Correct | 7 ms | 896 KB | Output is correct |
26 | Correct | 2 ms | 512 KB | Output is correct |
27 | Correct | 7 ms | 896 KB | Output is correct |
28 | Correct | 7 ms | 896 KB | Output is correct |
29 | Correct | 11 ms | 1024 KB | Output is correct |
30 | Correct | 2 ms | 512 KB | Output is correct |
31 | Correct | 7 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 1336 KB | Output is correct |
2 | Correct | 96 ms | 3152 KB | Output is correct |
3 | Correct | 46 ms | 1408 KB | Output is correct |
4 | Correct | 38 ms | 1536 KB | Output is correct |
5 | Correct | 38 ms | 1536 KB | Output is correct |
6 | Correct | 50 ms | 1408 KB | Output is correct |
7 | Correct | 7 ms | 896 KB | Output is correct |
8 | Correct | 2 ms | 516 KB | Output is correct |
9 | Correct | 7 ms | 1024 KB | Output is correct |
10 | Correct | 8 ms | 1024 KB | Output is correct |
11 | Correct | 9 ms | 896 KB | Output is correct |
12 | Correct | 8 ms | 896 KB | Output is correct |
13 | Correct | 7 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 896 KB | Output is correct |
2 | Correct | 8 ms | 896 KB | Output is correct |
3 | Correct | 7 ms | 896 KB | Output is correct |
4 | Correct | 6 ms | 896 KB | Output is correct |
5 | Correct | 15 ms | 988 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 7 ms | 896 KB | Output is correct |
8 | Correct | 8 ms | 896 KB | Output is correct |
9 | Correct | 10 ms | 896 KB | Output is correct |
10 | Correct | 8 ms | 896 KB | Output is correct |
11 | Correct | 10 ms | 884 KB | Output is correct |
12 | Correct | 10 ms | 1024 KB | Output is correct |
13 | Correct | 9 ms | 896 KB | Output is correct |
14 | Correct | 11 ms | 896 KB | Output is correct |
15 | Correct | 11 ms | 896 KB | Output is correct |
16 | Correct | 8 ms | 896 KB | Output is correct |
17 | Correct | 39 ms | 1336 KB | Output is correct |
18 | Correct | 96 ms | 3152 KB | Output is correct |
19 | Correct | 46 ms | 1408 KB | Output is correct |
20 | Correct | 38 ms | 1536 KB | Output is correct |
21 | Correct | 38 ms | 1536 KB | Output is correct |
22 | Correct | 50 ms | 1408 KB | Output is correct |
23 | Correct | 7 ms | 896 KB | Output is correct |
24 | Correct | 2 ms | 516 KB | Output is correct |
25 | Correct | 7 ms | 1024 KB | Output is correct |
26 | Correct | 8 ms | 1024 KB | Output is correct |
27 | Correct | 9 ms | 896 KB | Output is correct |
28 | Correct | 8 ms | 896 KB | Output is correct |
29 | Correct | 7 ms | 896 KB | Output is correct |
30 | Correct | 41 ms | 1360 KB | Output is correct |
31 | Correct | 38 ms | 1408 KB | Output is correct |
32 | Correct | 85 ms | 1784 KB | Output is correct |
33 | Correct | 41 ms | 1400 KB | Output is correct |
34 | Correct | 41 ms | 1408 KB | Output is correct |
35 | Correct | 43 ms | 1408 KB | Output is correct |
36 | Correct | 96 ms | 3192 KB | Output is correct |
37 | Correct | 3 ms | 512 KB | Output is correct |
38 | Correct | 3 ms | 512 KB | Output is correct |
39 | Correct | 38 ms | 1372 KB | Output is correct |
40 | Correct | 42 ms | 1528 KB | Output is correct |
41 | Correct | 40 ms | 1280 KB | Output is correct |
42 | Correct | 38 ms | 1400 KB | Output is correct |
43 | Correct | 42 ms | 1280 KB | Output is correct |
44 | Correct | 2 ms | 512 KB | Output is correct |
45 | Correct | 11 ms | 1024 KB | Output is correct |
46 | Correct | 9 ms | 1024 KB | Output is correct |
47 | Correct | 13 ms | 1024 KB | Output is correct |
48 | Correct | 103 ms | 3448 KB | Output is correct |
49 | Correct | 93 ms | 3320 KB | Output is correct |
50 | Correct | 3 ms | 512 KB | Output is correct |
51 | Correct | 71 ms | 1212 KB | Output is correct |
52 | Correct | 36 ms | 1280 KB | Output is correct |
53 | Correct | 33 ms | 1280 KB | Output is correct |
54 | Correct | 9 ms | 896 KB | Output is correct |
55 | Correct | 11 ms | 896 KB | Output is correct |
56 | Correct | 7 ms | 896 KB | Output is correct |
57 | Correct | 7 ms | 896 KB | Output is correct |
58 | Correct | 2 ms | 512 KB | Output is correct |
59 | Correct | 7 ms | 896 KB | Output is correct |
60 | Correct | 7 ms | 896 KB | Output is correct |
61 | Correct | 11 ms | 1024 KB | Output is correct |
62 | Correct | 2 ms | 512 KB | Output is correct |
63 | Correct | 7 ms | 896 KB | Output is correct |