# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
249203 | 2020-07-14T13:28:01 Z | SamAnd | Travelling Merchant (APIO17_merchant) | C++17 | 114 ms | 3448 KB |
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 102, M = 9903, K = 1003; const int INF = 1000000009; const ll LINF = M * 1LL * INF; int n, m, k; int b[N][K], s[N][K]; ll sd[N][N]; int maxu[N][N]; ll d[N][N]; bool stg(int u) { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { ll t; if (sd[x][y] > (long double)LINF / u) t = 2 * LINF; else t = sd[x][y] * u; d[x][y] = t - maxu[x][y]; /*for (int i = 1; i <= k; ++i) { if (b[x][i] != -1 && s[y][i] != -1) d[x][y] = min(d[x][y], t - (-b[x][i] + s[y][i])); }*/ } } for (int z = 1; z <= n; ++z) { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { d[x][y] = min(d[x][y], d[x][z] + d[z][y]); } } } for (int x = 1; x <= n; ++x) { if (d[x][x] <= 0) return true; } return false; } void solv() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { scanf("%d%d", &b[i][j], &s[i][j]); } } for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { sd[x][y] = LINF; } } for (int i = 1; i <= m; ++i) { int x, y, d; scanf("%d%d%d", &x, &y, &d); sd[x][y] = min(sd[x][y], (ll)d); } for (int z = 1; z <= n; ++z) { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { sd[x][y] = min(sd[x][y], sd[x][z] + sd[z][y]); } } } for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { maxu[x][y] = 0; for (int i = 1; i <= k; ++i) { if (b[x][i] != -1 && s[y][i] != -1) maxu[x][y] = max(maxu[x][y], -b[x][i] + s[y][i]); } } } int l = 1, r = INF; int ans = 0; while (l <= r) { int m = (l + r) / 2; if (stg(m)) { ans = m; l = m + 1; } else r = m - 1; } printf("%d\n", ans); } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING solv(); return 0; } //while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 2552 KB | Output is correct |
2 | Correct | 35 ms | 1280 KB | Output is correct |
3 | Correct | 35 ms | 1280 KB | Output is correct |
4 | Correct | 5 ms | 896 KB | Output is correct |
5 | Correct | 5 ms | 768 KB | Output is correct |
6 | Correct | 5 ms | 768 KB | Output is correct |
7 | Correct | 6 ms | 896 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 6 ms | 768 KB | Output is correct |
10 | Correct | 5 ms | 768 KB | Output is correct |
11 | Correct | 5 ms | 768 KB | Output is correct |
12 | Correct | 0 ms | 384 KB | Output is correct |
13 | Correct | 7 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 896 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
3 | Correct | 6 ms | 896 KB | Output is correct |
4 | Correct | 6 ms | 768 KB | Output is correct |
5 | Correct | 7 ms | 896 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 6 ms | 896 KB | Output is correct |
8 | Correct | 6 ms | 896 KB | Output is correct |
9 | Correct | 7 ms | 768 KB | Output is correct |
10 | Correct | 6 ms | 896 KB | Output is correct |
11 | Correct | 7 ms | 896 KB | Output is correct |
12 | Correct | 7 ms | 896 KB | Output is correct |
13 | Correct | 6 ms | 896 KB | Output is correct |
14 | Correct | 6 ms | 908 KB | Output is correct |
15 | Correct | 8 ms | 896 KB | Output is correct |
16 | Correct | 6 ms | 768 KB | Output is correct |
17 | Correct | 7 ms | 896 KB | Output is correct |
18 | Correct | 0 ms | 384 KB | Output is correct |
19 | Correct | 7 ms | 940 KB | Output is correct |
20 | Correct | 7 ms | 896 KB | Output is correct |
21 | Correct | 7 ms | 896 KB | Output is correct |
22 | Correct | 7 ms | 896 KB | Output is correct |
23 | Correct | 6 ms | 896 KB | Output is correct |
24 | Correct | 5 ms | 768 KB | Output is correct |
25 | Correct | 6 ms | 896 KB | Output is correct |
26 | Correct | 0 ms | 384 KB | Output is correct |
27 | Correct | 6 ms | 768 KB | Output is correct |
28 | Correct | 5 ms | 768 KB | Output is correct |
29 | Correct | 5 ms | 768 KB | Output is correct |
30 | Correct | 0 ms | 384 KB | Output is correct |
31 | Correct | 7 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 1408 KB | Output is correct |
2 | Correct | 100 ms | 3136 KB | Output is correct |
3 | Correct | 38 ms | 1408 KB | Output is correct |
4 | Correct | 42 ms | 1536 KB | Output is correct |
5 | Correct | 43 ms | 1660 KB | Output is correct |
6 | Correct | 38 ms | 1408 KB | Output is correct |
7 | Correct | 7 ms | 896 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 7 ms | 940 KB | Output is correct |
10 | Correct | 7 ms | 896 KB | Output is correct |
11 | Correct | 7 ms | 896 KB | Output is correct |
12 | Correct | 7 ms | 896 KB | Output is correct |
13 | Correct | 6 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 896 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
3 | Correct | 6 ms | 896 KB | Output is correct |
4 | Correct | 6 ms | 768 KB | Output is correct |
5 | Correct | 7 ms | 896 KB | Output is correct |
6 | Correct | 0 ms | 384 KB | Output is correct |
7 | Correct | 6 ms | 896 KB | Output is correct |
8 | Correct | 6 ms | 896 KB | Output is correct |
9 | Correct | 7 ms | 768 KB | Output is correct |
10 | Correct | 6 ms | 896 KB | Output is correct |
11 | Correct | 7 ms | 896 KB | Output is correct |
12 | Correct | 7 ms | 896 KB | Output is correct |
13 | Correct | 6 ms | 896 KB | Output is correct |
14 | Correct | 6 ms | 908 KB | Output is correct |
15 | Correct | 8 ms | 896 KB | Output is correct |
16 | Correct | 6 ms | 768 KB | Output is correct |
17 | Correct | 46 ms | 1408 KB | Output is correct |
18 | Correct | 100 ms | 3136 KB | Output is correct |
19 | Correct | 38 ms | 1408 KB | Output is correct |
20 | Correct | 42 ms | 1536 KB | Output is correct |
21 | Correct | 43 ms | 1660 KB | Output is correct |
22 | Correct | 38 ms | 1408 KB | Output is correct |
23 | Correct | 7 ms | 896 KB | Output is correct |
24 | Correct | 0 ms | 384 KB | Output is correct |
25 | Correct | 7 ms | 940 KB | Output is correct |
26 | Correct | 7 ms | 896 KB | Output is correct |
27 | Correct | 7 ms | 896 KB | Output is correct |
28 | Correct | 7 ms | 896 KB | Output is correct |
29 | Correct | 6 ms | 896 KB | Output is correct |
30 | Correct | 36 ms | 1384 KB | Output is correct |
31 | Correct | 41 ms | 1444 KB | Output is correct |
32 | Correct | 59 ms | 1784 KB | Output is correct |
33 | Correct | 39 ms | 1408 KB | Output is correct |
34 | Correct | 40 ms | 1408 KB | Output is correct |
35 | Correct | 43 ms | 1408 KB | Output is correct |
36 | Correct | 108 ms | 3192 KB | Output is correct |
37 | Correct | 0 ms | 384 KB | Output is correct |
38 | Correct | 1 ms | 384 KB | Output is correct |
39 | Correct | 37 ms | 1280 KB | Output is correct |
40 | Correct | 39 ms | 1408 KB | Output is correct |
41 | Correct | 37 ms | 1400 KB | Output is correct |
42 | Correct | 40 ms | 1280 KB | Output is correct |
43 | Correct | 36 ms | 1280 KB | Output is correct |
44 | Correct | 0 ms | 384 KB | Output is correct |
45 | Correct | 8 ms | 896 KB | Output is correct |
46 | Correct | 8 ms | 896 KB | Output is correct |
47 | Correct | 8 ms | 896 KB | Output is correct |
48 | Correct | 114 ms | 3448 KB | Output is correct |
49 | Correct | 112 ms | 3320 KB | Output is correct |
50 | Correct | 0 ms | 384 KB | Output is correct |
51 | Correct | 67 ms | 2552 KB | Output is correct |
52 | Correct | 35 ms | 1280 KB | Output is correct |
53 | Correct | 35 ms | 1280 KB | Output is correct |
54 | Correct | 5 ms | 896 KB | Output is correct |
55 | Correct | 5 ms | 768 KB | Output is correct |
56 | Correct | 5 ms | 768 KB | Output is correct |
57 | Correct | 6 ms | 896 KB | Output is correct |
58 | Correct | 0 ms | 384 KB | Output is correct |
59 | Correct | 6 ms | 768 KB | Output is correct |
60 | Correct | 5 ms | 768 KB | Output is correct |
61 | Correct | 5 ms | 768 KB | Output is correct |
62 | Correct | 0 ms | 384 KB | Output is correct |
63 | Correct | 7 ms | 896 KB | Output is correct |