# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
56546 | 2018-07-11T15:21:59 Z | andremfq | Travelling Merchant (APIO17_merchant) | C++17 | 208 ms | 14616 KB |
#include <bits/stdc++.h> template<typename T> void domax(T &a, T b) { if (b > a) a = b; } template<typename T> void domin(T &a, T b) { if (b < a) a = b; } const long long inf = 3e18, MaxT = 10ll*1000*1000; const int MaxN = 105, MaxK = 1005; int n, m, K; long long b[MaxN][MaxK], s[MaxN][MaxK], dist[MaxN][MaxN], best[MaxN][MaxN], cost[MaxN][MaxN]; bool can(long long eff) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dist[i][j] < inf) { assert(dist[i][j] <= 1000ll*1000*1000); // MaxT * MaxN assert(eff <= 1000ll*1000*1000 + 1); cost[i][j] = dist[i][j] * eff - best[i][j]; assert(-1000ll*1000*1000 <= cost[i][j]); assert(cost[i][j] <= (1000*1000*1000ll + 1) * 1000ll*1000*1000); } else { cost[i][j] = inf; } } } for (int m = 0; m < n; m++) { for (int s = 0; s < n; s++) { for (int e = 0; e < n; e++) { domin(cost[s][e], cost[s][m] + cost[m][e]); if (cost[s][e] < -inf) { cost[s][e] = -inf; } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (cost[i][j] + cost[j][i] <= 0) { return true; } } } return false; } int main() { scanf("%d%d%d", &n, &m, &K); for (int i = 0; i < n; i++) { for (int k = 0; k < K; k++) { scanf("%lld%lld", b[i]+k, s[i]+k); if (b[i][k] == -1) b[i][k] = inf; if (s[i][k] == -1) s[i][k] = -inf; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = inf; } } for (int i = 0; i < m; i++) { int v, w; long long t; scanf("%d%d%lld", &v, &w, &t); v--; w--; dist[v][w] = t; assert(t <= 10ll*1000*1000); } for (int m = 0; m < n; m++) { for (int s = 0; s < n; s++) { for (int e = 0; e < n; e++) { domin(dist[s][e], dist[s][m] + dist[m][e]); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { best[i][j] = 0; // carrying no item for (int k = 0; k < K; k++) { domax(best[i][j], s[j][k] - b[i][k]); } } } long long lo = 1ll, hi = 1000ll * 1000 * 1000; long long ans = 0ll; while (lo <= hi) { long long mid = (lo + hi) / 2; if (can(mid)) { lo = mid + 1; ans = mid; } else { hi = mid - 1; } } assert(!can(ans+1)); printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 3448 KB | Output is correct |
2 | Correct | 51 ms | 3448 KB | Output is correct |
3 | Correct | 50 ms | 3448 KB | Output is correct |
4 | Correct | 10 ms | 3448 KB | Output is correct |
5 | Correct | 10 ms | 3448 KB | Output is correct |
6 | Correct | 10 ms | 3448 KB | Output is correct |
7 | Correct | 13 ms | 3448 KB | Output is correct |
8 | Correct | 3 ms | 3448 KB | Output is correct |
9 | Correct | 10 ms | 3448 KB | Output is correct |
10 | Correct | 13 ms | 3448 KB | Output is correct |
11 | Correct | 12 ms | 3448 KB | Output is correct |
12 | Correct | 3 ms | 3448 KB | Output is correct |
13 | Correct | 17 ms | 3448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 3448 KB | Output is correct |
2 | Correct | 10 ms | 3448 KB | Output is correct |
3 | Correct | 11 ms | 3448 KB | Output is correct |
4 | Correct | 11 ms | 3448 KB | Output is correct |
5 | Correct | 23 ms | 3448 KB | Output is correct |
6 | Correct | 3 ms | 3448 KB | Output is correct |
7 | Correct | 10 ms | 3448 KB | Output is correct |
8 | Correct | 10 ms | 3448 KB | Output is correct |
9 | Correct | 13 ms | 3448 KB | Output is correct |
10 | Correct | 13 ms | 3448 KB | Output is correct |
11 | Correct | 13 ms | 3448 KB | Output is correct |
12 | Correct | 15 ms | 3448 KB | Output is correct |
13 | Correct | 12 ms | 3448 KB | Output is correct |
14 | Correct | 14 ms | 3448 KB | Output is correct |
15 | Correct | 15 ms | 3448 KB | Output is correct |
16 | Correct | 11 ms | 3448 KB | Output is correct |
17 | Correct | 23 ms | 3448 KB | Output is correct |
18 | Correct | 3 ms | 3448 KB | Output is correct |
19 | Correct | 26 ms | 3448 KB | Output is correct |
20 | Correct | 23 ms | 3448 KB | Output is correct |
21 | Correct | 16 ms | 3448 KB | Output is correct |
22 | Correct | 10 ms | 3448 KB | Output is correct |
23 | Correct | 12 ms | 3448 KB | Output is correct |
24 | Correct | 10 ms | 3448 KB | Output is correct |
25 | Correct | 13 ms | 3448 KB | Output is correct |
26 | Correct | 3 ms | 3448 KB | Output is correct |
27 | Correct | 10 ms | 3448 KB | Output is correct |
28 | Correct | 13 ms | 3448 KB | Output is correct |
29 | Correct | 12 ms | 3448 KB | Output is correct |
30 | Correct | 3 ms | 3448 KB | Output is correct |
31 | Correct | 17 ms | 3448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 147 ms | 4032 KB | Output is correct |
2 | Correct | 208 ms | 6472 KB | Output is correct |
3 | Correct | 119 ms | 6472 KB | Output is correct |
4 | Correct | 148 ms | 6472 KB | Output is correct |
5 | Correct | 164 ms | 6492 KB | Output is correct |
6 | Correct | 110 ms | 6492 KB | Output is correct |
7 | Correct | 23 ms | 3448 KB | Output is correct |
8 | Correct | 3 ms | 3448 KB | Output is correct |
9 | Correct | 26 ms | 3448 KB | Output is correct |
10 | Correct | 23 ms | 3448 KB | Output is correct |
11 | Correct | 16 ms | 3448 KB | Output is correct |
12 | Correct | 10 ms | 3448 KB | Output is correct |
13 | Correct | 12 ms | 3448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 3448 KB | Output is correct |
2 | Correct | 10 ms | 3448 KB | Output is correct |
3 | Correct | 11 ms | 3448 KB | Output is correct |
4 | Correct | 11 ms | 3448 KB | Output is correct |
5 | Correct | 23 ms | 3448 KB | Output is correct |
6 | Correct | 3 ms | 3448 KB | Output is correct |
7 | Correct | 10 ms | 3448 KB | Output is correct |
8 | Correct | 10 ms | 3448 KB | Output is correct |
9 | Correct | 13 ms | 3448 KB | Output is correct |
10 | Correct | 13 ms | 3448 KB | Output is correct |
11 | Correct | 13 ms | 3448 KB | Output is correct |
12 | Correct | 15 ms | 3448 KB | Output is correct |
13 | Correct | 12 ms | 3448 KB | Output is correct |
14 | Correct | 14 ms | 3448 KB | Output is correct |
15 | Correct | 15 ms | 3448 KB | Output is correct |
16 | Correct | 11 ms | 3448 KB | Output is correct |
17 | Correct | 147 ms | 4032 KB | Output is correct |
18 | Correct | 208 ms | 6472 KB | Output is correct |
19 | Correct | 119 ms | 6472 KB | Output is correct |
20 | Correct | 148 ms | 6472 KB | Output is correct |
21 | Correct | 164 ms | 6492 KB | Output is correct |
22 | Correct | 110 ms | 6492 KB | Output is correct |
23 | Correct | 23 ms | 3448 KB | Output is correct |
24 | Correct | 3 ms | 3448 KB | Output is correct |
25 | Correct | 26 ms | 3448 KB | Output is correct |
26 | Correct | 23 ms | 3448 KB | Output is correct |
27 | Correct | 16 ms | 3448 KB | Output is correct |
28 | Correct | 10 ms | 3448 KB | Output is correct |
29 | Correct | 12 ms | 3448 KB | Output is correct |
30 | Correct | 75 ms | 6492 KB | Output is correct |
31 | Correct | 94 ms | 6572 KB | Output is correct |
32 | Correct | 100 ms | 7676 KB | Output is correct |
33 | Correct | 67 ms | 7676 KB | Output is correct |
34 | Correct | 64 ms | 7676 KB | Output is correct |
35 | Correct | 99 ms | 7676 KB | Output is correct |
36 | Correct | 150 ms | 9796 KB | Output is correct |
37 | Correct | 2 ms | 9796 KB | Output is correct |
38 | Correct | 2 ms | 9796 KB | Output is correct |
39 | Correct | 67 ms | 9796 KB | Output is correct |
40 | Correct | 59 ms | 9796 KB | Output is correct |
41 | Correct | 66 ms | 9796 KB | Output is correct |
42 | Correct | 66 ms | 9796 KB | Output is correct |
43 | Correct | 69 ms | 9796 KB | Output is correct |
44 | Correct | 2 ms | 9796 KB | Output is correct |
45 | Correct | 15 ms | 9796 KB | Output is correct |
46 | Correct | 16 ms | 9796 KB | Output is correct |
47 | Correct | 15 ms | 9796 KB | Output is correct |
48 | Correct | 141 ms | 12404 KB | Output is correct |
49 | Correct | 119 ms | 14616 KB | Output is correct |
50 | Correct | 3 ms | 14616 KB | Output is correct |
51 | Correct | 86 ms | 3448 KB | Output is correct |
52 | Correct | 51 ms | 3448 KB | Output is correct |
53 | Correct | 50 ms | 3448 KB | Output is correct |
54 | Correct | 10 ms | 3448 KB | Output is correct |
55 | Correct | 10 ms | 3448 KB | Output is correct |
56 | Correct | 10 ms | 3448 KB | Output is correct |
57 | Correct | 13 ms | 3448 KB | Output is correct |
58 | Correct | 3 ms | 3448 KB | Output is correct |
59 | Correct | 10 ms | 3448 KB | Output is correct |
60 | Correct | 13 ms | 3448 KB | Output is correct |
61 | Correct | 12 ms | 3448 KB | Output is correct |
62 | Correct | 3 ms | 3448 KB | Output is correct |
63 | Correct | 17 ms | 3448 KB | Output is correct |