# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
147798 | 2019-08-30T16:45:43 Z | HellAngel | Travelling Merchant (APIO17_merchant) | C++14 | 121 ms | 4216 KB |
#include <bits/stdc++.h> #define int long long const int maxn = 100 + 7; const int maxk = 1e3 + 7; const int Inf = 1e18; using namespace std; int dist[maxn][maxn], b[maxn][maxk], s[maxn][maxk], n, m, k, cost[maxn][maxn], gau[maxn][maxn]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout); fill_n(&dist[0][0], maxn * maxn, Inf); cin >> n >> m >> k; for(int i = 1; i <= n; i++) { for(int j = 1; j <= k; j++) cin >> b[i][j] >> s[i][j]; dist[i][i] = 0; } for(int i = 1; i <= m; i++) { int u, v, c; cin >> u >> v >> c; dist[u][v] = min(dist[u][v], c); } for(int k = 1; k <= n ; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { int gau = dist[i][k] + dist[k][j]; gau = min(gau, Inf); gau = max(gau, -Inf); dist[i][j] = min(dist[i][j], gau); } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int type = 1; type <= k; type++) { if(s[i][type] == -1 || b[j][type] == -1) continue; cost[j][i] = max(cost[j][i], s[i][type] - b[j][type]); } } } int l = 0; int r = 1e9; while(l <= r) { int mid = l + r >> 1; /// check(mid) for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(dist[i][j] != Inf) gau[i][j] = mid * dist[i][j] - cost[i][j]; else gau[i][j] = Inf; } } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { int meo =gau[i][k] + gau[k][j]; meo = max(meo, -Inf); meo = min(meo, Inf); gau[i][j] = min(gau[i][j], meo); } } } bool cac = false; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j) continue; if(gau[i][j] + gau[j][i] <= 0) cac = true; } } if(cac) l = mid + 1; else r = mid - 1; } cout << r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 89 ms | 2168 KB | Output is correct |
2 | Correct | 59 ms | 1272 KB | Output is correct |
3 | Correct | 60 ms | 1272 KB | Output is correct |
4 | Correct | 10 ms | 888 KB | Output is correct |
5 | Correct | 10 ms | 888 KB | Output is correct |
6 | Correct | 10 ms | 888 KB | Output is correct |
7 | Correct | 11 ms | 1016 KB | Output is correct |
8 | Correct | 2 ms | 504 KB | Output is correct |
9 | Correct | 10 ms | 888 KB | Output is correct |
10 | Correct | 10 ms | 888 KB | Output is correct |
11 | Correct | 10 ms | 896 KB | Output is correct |
12 | Correct | 2 ms | 504 KB | Output is correct |
13 | Correct | 11 ms | 1016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 888 KB | Output is correct |
2 | Correct | 10 ms | 888 KB | Output is correct |
3 | Correct | 10 ms | 1016 KB | Output is correct |
4 | Correct | 10 ms | 888 KB | Output is correct |
5 | Correct | 11 ms | 1016 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 10 ms | 888 KB | Output is correct |
8 | Correct | 11 ms | 1016 KB | Output is correct |
9 | Correct | 10 ms | 888 KB | Output is correct |
10 | Correct | 11 ms | 1144 KB | Output is correct |
11 | Correct | 11 ms | 1016 KB | Output is correct |
12 | Correct | 11 ms | 1016 KB | Output is correct |
13 | Correct | 11 ms | 988 KB | Output is correct |
14 | Correct | 11 ms | 888 KB | Output is correct |
15 | Correct | 12 ms | 1016 KB | Output is correct |
16 | Correct | 10 ms | 1016 KB | Output is correct |
17 | Correct | 11 ms | 1016 KB | Output is correct |
18 | Correct | 2 ms | 504 KB | Output is correct |
19 | Correct | 11 ms | 1016 KB | Output is correct |
20 | Correct | 11 ms | 1016 KB | Output is correct |
21 | Correct | 11 ms | 888 KB | Output is correct |
22 | Correct | 10 ms | 888 KB | Output is correct |
23 | Correct | 10 ms | 888 KB | Output is correct |
24 | Correct | 10 ms | 888 KB | Output is correct |
25 | Correct | 11 ms | 1016 KB | Output is correct |
26 | Correct | 2 ms | 504 KB | Output is correct |
27 | Correct | 10 ms | 888 KB | Output is correct |
28 | Correct | 10 ms | 888 KB | Output is correct |
29 | Correct | 10 ms | 896 KB | Output is correct |
30 | Correct | 2 ms | 504 KB | Output is correct |
31 | Correct | 11 ms | 1016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 1656 KB | Output is correct |
2 | Correct | 113 ms | 2232 KB | Output is correct |
3 | Correct | 61 ms | 1528 KB | Output is correct |
4 | Correct | 65 ms | 1656 KB | Output is correct |
5 | Correct | 65 ms | 1656 KB | Output is correct |
6 | Correct | 63 ms | 1516 KB | Output is correct |
7 | Correct | 11 ms | 1016 KB | Output is correct |
8 | Correct | 2 ms | 504 KB | Output is correct |
9 | Correct | 11 ms | 1016 KB | Output is correct |
10 | Correct | 11 ms | 1016 KB | Output is correct |
11 | Correct | 11 ms | 888 KB | Output is correct |
12 | Correct | 10 ms | 888 KB | Output is correct |
13 | Correct | 10 ms | 888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 888 KB | Output is correct |
2 | Correct | 10 ms | 888 KB | Output is correct |
3 | Correct | 10 ms | 1016 KB | Output is correct |
4 | Correct | 10 ms | 888 KB | Output is correct |
5 | Correct | 11 ms | 1016 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 10 ms | 888 KB | Output is correct |
8 | Correct | 11 ms | 1016 KB | Output is correct |
9 | Correct | 10 ms | 888 KB | Output is correct |
10 | Correct | 11 ms | 1144 KB | Output is correct |
11 | Correct | 11 ms | 1016 KB | Output is correct |
12 | Correct | 11 ms | 1016 KB | Output is correct |
13 | Correct | 11 ms | 988 KB | Output is correct |
14 | Correct | 11 ms | 888 KB | Output is correct |
15 | Correct | 12 ms | 1016 KB | Output is correct |
16 | Correct | 10 ms | 1016 KB | Output is correct |
17 | Correct | 65 ms | 1656 KB | Output is correct |
18 | Correct | 113 ms | 2232 KB | Output is correct |
19 | Correct | 61 ms | 1528 KB | Output is correct |
20 | Correct | 65 ms | 1656 KB | Output is correct |
21 | Correct | 65 ms | 1656 KB | Output is correct |
22 | Correct | 63 ms | 1516 KB | Output is correct |
23 | Correct | 11 ms | 1016 KB | Output is correct |
24 | Correct | 2 ms | 504 KB | Output is correct |
25 | Correct | 11 ms | 1016 KB | Output is correct |
26 | Correct | 11 ms | 1016 KB | Output is correct |
27 | Correct | 11 ms | 888 KB | Output is correct |
28 | Correct | 10 ms | 888 KB | Output is correct |
29 | Correct | 10 ms | 888 KB | Output is correct |
30 | Correct | 60 ms | 1400 KB | Output is correct |
31 | Correct | 62 ms | 1656 KB | Output is correct |
32 | Correct | 81 ms | 2760 KB | Output is correct |
33 | Correct | 63 ms | 1660 KB | Output is correct |
34 | Correct | 63 ms | 1692 KB | Output is correct |
35 | Correct | 62 ms | 1708 KB | Output is correct |
36 | Correct | 117 ms | 4216 KB | Output is correct |
37 | Correct | 2 ms | 504 KB | Output is correct |
38 | Correct | 2 ms | 504 KB | Output is correct |
39 | Correct | 59 ms | 1428 KB | Output is correct |
40 | Correct | 62 ms | 1528 KB | Output is correct |
41 | Correct | 60 ms | 1628 KB | Output is correct |
42 | Correct | 60 ms | 1528 KB | Output is correct |
43 | Correct | 60 ms | 1528 KB | Output is correct |
44 | Correct | 2 ms | 504 KB | Output is correct |
45 | Correct | 12 ms | 1144 KB | Output is correct |
46 | Correct | 13 ms | 1144 KB | Output is correct |
47 | Correct | 13 ms | 1272 KB | Output is correct |
48 | Correct | 121 ms | 4212 KB | Output is correct |
49 | Correct | 121 ms | 4188 KB | Output is correct |
50 | Correct | 2 ms | 504 KB | Output is correct |
51 | Correct | 89 ms | 2168 KB | Output is correct |
52 | Correct | 59 ms | 1272 KB | Output is correct |
53 | Correct | 60 ms | 1272 KB | Output is correct |
54 | Correct | 10 ms | 888 KB | Output is correct |
55 | Correct | 10 ms | 888 KB | Output is correct |
56 | Correct | 10 ms | 888 KB | Output is correct |
57 | Correct | 11 ms | 1016 KB | Output is correct |
58 | Correct | 2 ms | 504 KB | Output is correct |
59 | Correct | 10 ms | 888 KB | Output is correct |
60 | Correct | 10 ms | 888 KB | Output is correct |
61 | Correct | 10 ms | 896 KB | Output is correct |
62 | Correct | 2 ms | 504 KB | Output is correct |
63 | Correct | 11 ms | 1016 KB | Output is correct |