# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77955 | 2018-10-01T11:53:58 Z | aquablitz11 | Travelling Merchant (APIO17_merchant) | C++14 | 122 ms | 9500 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 110; const int T = 1010; const ll INF = 1e18; int n, m, t; int B[N][T], S[N][T]; ll pro[N][N], dist[N][N], A[N][N]; bool check(ll r) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) A[i][j] = pro[i][j]-dist[i][j]*r; A[i][i] = -INF; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) A[i][j] = max(A[i][j], A[i][k]+A[k][j]); } } /*printf("check(%lld):\n", r); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) printf("%lld ", A[i][j]); printf("\n"); } printf("\n");*/ for (int i = 1; i <= n; ++i) { if (A[i][i] >= 0) return true; } return false; } int main() { scanf("%d%d%d", &n, &m, &t); for (int i = 1; i <= n; ++i) { dist[i][i] = 0; for (int j = 1; j <= t; ++j) scanf("%d%d", &B[i][j], &S[i][j]); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = 1e9; for (int k = 1; k <= t; ++k) { if (B[i][k] != -1 && S[j][k] != -1) pro[i][j] = max(pro[i][j], (ll)S[j][k]-B[i][k]); } } dist[i][i] = 0; } for (int i = 1; i <= m; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dist[u][v] = w; } 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]); } } ll b = 0, e = 1e9; while (b < e) { ll m = (b+e+1)/2; if (check(m)) b = m; else e = m-1; } printf("%lld\n", b); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 90 ms | 1272 KB | Output is correct |
2 | Correct | 47 ms | 1416 KB | Output is correct |
3 | Correct | 44 ms | 1416 KB | Output is correct |
4 | Correct | 9 ms | 1416 KB | Output is correct |
5 | Correct | 8 ms | 1416 KB | Output is correct |
6 | Correct | 8 ms | 1416 KB | Output is correct |
7 | Correct | 9 ms | 1416 KB | Output is correct |
8 | Correct | 2 ms | 1416 KB | Output is correct |
9 | Correct | 8 ms | 1416 KB | Output is correct |
10 | Correct | 10 ms | 1416 KB | Output is correct |
11 | Correct | 8 ms | 1416 KB | Output is correct |
12 | Correct | 2 ms | 1416 KB | Output is correct |
13 | Correct | 9 ms | 1416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1416 KB | Output is correct |
2 | Correct | 9 ms | 1416 KB | Output is correct |
3 | Correct | 9 ms | 1416 KB | Output is correct |
4 | Correct | 10 ms | 1416 KB | Output is correct |
5 | Correct | 10 ms | 1416 KB | Output is correct |
6 | Correct | 2 ms | 1416 KB | Output is correct |
7 | Correct | 8 ms | 1416 KB | Output is correct |
8 | Correct | 8 ms | 1416 KB | Output is correct |
9 | Correct | 9 ms | 1416 KB | Output is correct |
10 | Correct | 8 ms | 1416 KB | Output is correct |
11 | Correct | 9 ms | 1416 KB | Output is correct |
12 | Correct | 9 ms | 1416 KB | Output is correct |
13 | Correct | 9 ms | 1416 KB | Output is correct |
14 | Correct | 9 ms | 1432 KB | Output is correct |
15 | Correct | 11 ms | 1488 KB | Output is correct |
16 | Correct | 8 ms | 1556 KB | Output is correct |
17 | Correct | 9 ms | 1560 KB | Output is correct |
18 | Correct | 2 ms | 1560 KB | Output is correct |
19 | Correct | 10 ms | 1560 KB | Output is correct |
20 | Correct | 9 ms | 1668 KB | Output is correct |
21 | Correct | 9 ms | 1668 KB | Output is correct |
22 | Correct | 9 ms | 1668 KB | Output is correct |
23 | Correct | 8 ms | 1668 KB | Output is correct |
24 | Correct | 8 ms | 1416 KB | Output is correct |
25 | Correct | 9 ms | 1416 KB | Output is correct |
26 | Correct | 2 ms | 1416 KB | Output is correct |
27 | Correct | 8 ms | 1416 KB | Output is correct |
28 | Correct | 10 ms | 1416 KB | Output is correct |
29 | Correct | 8 ms | 1416 KB | Output is correct |
30 | Correct | 2 ms | 1416 KB | Output is correct |
31 | Correct | 9 ms | 1416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 71 ms | 2120 KB | Output is correct |
2 | Correct | 107 ms | 2128 KB | Output is correct |
3 | Correct | 45 ms | 2128 KB | Output is correct |
4 | Correct | 49 ms | 2128 KB | Output is correct |
5 | Correct | 49 ms | 2228 KB | Output is correct |
6 | Correct | 48 ms | 2228 KB | Output is correct |
7 | Correct | 9 ms | 1560 KB | Output is correct |
8 | Correct | 2 ms | 1560 KB | Output is correct |
9 | Correct | 10 ms | 1560 KB | Output is correct |
10 | Correct | 9 ms | 1668 KB | Output is correct |
11 | Correct | 9 ms | 1668 KB | Output is correct |
12 | Correct | 9 ms | 1668 KB | Output is correct |
13 | Correct | 8 ms | 1668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1416 KB | Output is correct |
2 | Correct | 9 ms | 1416 KB | Output is correct |
3 | Correct | 9 ms | 1416 KB | Output is correct |
4 | Correct | 10 ms | 1416 KB | Output is correct |
5 | Correct | 10 ms | 1416 KB | Output is correct |
6 | Correct | 2 ms | 1416 KB | Output is correct |
7 | Correct | 8 ms | 1416 KB | Output is correct |
8 | Correct | 8 ms | 1416 KB | Output is correct |
9 | Correct | 9 ms | 1416 KB | Output is correct |
10 | Correct | 8 ms | 1416 KB | Output is correct |
11 | Correct | 9 ms | 1416 KB | Output is correct |
12 | Correct | 9 ms | 1416 KB | Output is correct |
13 | Correct | 9 ms | 1416 KB | Output is correct |
14 | Correct | 9 ms | 1432 KB | Output is correct |
15 | Correct | 11 ms | 1488 KB | Output is correct |
16 | Correct | 8 ms | 1556 KB | Output is correct |
17 | Correct | 71 ms | 2120 KB | Output is correct |
18 | Correct | 107 ms | 2128 KB | Output is correct |
19 | Correct | 45 ms | 2128 KB | Output is correct |
20 | Correct | 49 ms | 2128 KB | Output is correct |
21 | Correct | 49 ms | 2228 KB | Output is correct |
22 | Correct | 48 ms | 2228 KB | Output is correct |
23 | Correct | 9 ms | 1560 KB | Output is correct |
24 | Correct | 2 ms | 1560 KB | Output is correct |
25 | Correct | 10 ms | 1560 KB | Output is correct |
26 | Correct | 9 ms | 1668 KB | Output is correct |
27 | Correct | 9 ms | 1668 KB | Output is correct |
28 | Correct | 9 ms | 1668 KB | Output is correct |
29 | Correct | 8 ms | 1668 KB | Output is correct |
30 | Correct | 47 ms | 2228 KB | Output is correct |
31 | Correct | 47 ms | 2228 KB | Output is correct |
32 | Correct | 65 ms | 2720 KB | Output is correct |
33 | Correct | 45 ms | 2824 KB | Output is correct |
34 | Correct | 60 ms | 2888 KB | Output is correct |
35 | Correct | 45 ms | 2932 KB | Output is correct |
36 | Correct | 117 ms | 4832 KB | Output is correct |
37 | Correct | 2 ms | 4832 KB | Output is correct |
38 | Correct | 2 ms | 4832 KB | Output is correct |
39 | Correct | 45 ms | 4872 KB | Output is correct |
40 | Correct | 45 ms | 4876 KB | Output is correct |
41 | Correct | 55 ms | 5064 KB | Output is correct |
42 | Correct | 44 ms | 5064 KB | Output is correct |
43 | Correct | 44 ms | 5064 KB | Output is correct |
44 | Correct | 2 ms | 5064 KB | Output is correct |
45 | Correct | 10 ms | 5064 KB | Output is correct |
46 | Correct | 10 ms | 5064 KB | Output is correct |
47 | Correct | 10 ms | 5064 KB | Output is correct |
48 | Correct | 113 ms | 7440 KB | Output is correct |
49 | Correct | 122 ms | 9500 KB | Output is correct |
50 | Correct | 2 ms | 9500 KB | Output is correct |
51 | Correct | 90 ms | 1272 KB | Output is correct |
52 | Correct | 47 ms | 1416 KB | Output is correct |
53 | Correct | 44 ms | 1416 KB | Output is correct |
54 | Correct | 9 ms | 1416 KB | Output is correct |
55 | Correct | 8 ms | 1416 KB | Output is correct |
56 | Correct | 8 ms | 1416 KB | Output is correct |
57 | Correct | 9 ms | 1416 KB | Output is correct |
58 | Correct | 2 ms | 1416 KB | Output is correct |
59 | Correct | 8 ms | 1416 KB | Output is correct |
60 | Correct | 10 ms | 1416 KB | Output is correct |
61 | Correct | 8 ms | 1416 KB | Output is correct |
62 | Correct | 2 ms | 1416 KB | Output is correct |
63 | Correct | 9 ms | 1416 KB | Output is correct |