# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
906105 | 2024-01-13T14:01:47 Z | nguyentunglam | 여행하는 상인 (APIO17_merchant) | C++17 | 98 ms | 3624 KB |
#include<bits/stdc++.h> #define all(v) v.begin(), v.end() #define endl "\n" using namespace std; const int N = 110, M = 1e3 + 10; int n, m, K; int x[N * N], y[N * N], z[N * N]; long long f[N][N], g[N][N]; int cost[N][N]; int s[N][M], b[N][M]; int32_t main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen("task.inp", "r")) { freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } if (fopen(task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } 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]; } for(int i = 1; i <= m; i++) cin >> x[i] >> y[i] >> z[i]; auto calc = [&] (int mid) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = 1e16; for(int i = 1; i <= n; i++) f[i][i] = 0; for(int i = 1; i <= m; i++) f[x[i]][y[i]] = min(f[x[i]][y[i]], 1LL * z[i] * mid); for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { g[i][j] = cost[i][j] - f[i][j]; if (i == j) g[i][j] = -1e16; } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { // cout << i << " " << j << " " << g[i][j] << " " << f[i][j] << " " << cost[i][j] << endl; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { g[i][j] = max(g[i][j], g[i][k] + g[k][j]); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { // cout << i << " " << j << " " << g[i][j] << endl; } for(int i = 1; i <= n; i++) if (g[i][i] >= 0) return true; return false; }; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { for(int k = 1; k <= K; k++) if (s[j][k] != -1 && b[i][k] != -1) { cost[i][j] = max(cost[i][j], s[j][k] - b[i][k]); } } // cout << calc(2);return 0; int l = 1, r = 1e9, ans = 0; while (l <= r) { int mid = l + r >> 1; if (calc(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } cout << ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 75 ms | 1360 KB | Output is correct |
2 | Correct | 56 ms | 1372 KB | Output is correct |
3 | Correct | 55 ms | 1368 KB | Output is correct |
4 | Correct | 10 ms | 860 KB | Output is correct |
5 | Correct | 7 ms | 860 KB | Output is correct |
6 | Correct | 7 ms | 860 KB | Output is correct |
7 | Correct | 8 ms | 860 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 7 ms | 860 KB | Output is correct |
10 | Correct | 8 ms | 860 KB | Output is correct |
11 | Correct | 7 ms | 856 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 8 ms | 856 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 860 KB | Output is correct |
2 | Correct | 8 ms | 860 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 7 ms | 860 KB | Output is correct |
5 | Correct | 8 ms | 860 KB | Output is correct |
6 | Correct | 7 ms | 856 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 8 ms | 856 KB | Output is correct |
9 | Correct | 9 ms | 860 KB | Output is correct |
10 | Correct | 7 ms | 860 KB | Output is correct |
11 | Correct | 8 ms | 860 KB | Output is correct |
12 | Correct | 7 ms | 1112 KB | Output is correct |
13 | Correct | 8 ms | 856 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
15 | Correct | 8 ms | 864 KB | Output is correct |
16 | Correct | 8 ms | 788 KB | Output is correct |
17 | Correct | 7 ms | 856 KB | Output is correct |
18 | Correct | 8 ms | 860 KB | Output is correct |
19 | Correct | 8 ms | 860 KB | Output is correct |
20 | Correct | 10 ms | 856 KB | Output is correct |
21 | Correct | 10 ms | 868 KB | Output is correct |
22 | Correct | 11 ms | 860 KB | Output is correct |
23 | Correct | 8 ms | 860 KB | Output is correct |
24 | Correct | 7 ms | 860 KB | Output is correct |
25 | Correct | 8 ms | 860 KB | Output is correct |
26 | Correct | 1 ms | 348 KB | Output is correct |
27 | Correct | 8 ms | 860 KB | Output is correct |
28 | Correct | 7 ms | 992 KB | Output is correct |
29 | Correct | 8 ms | 1040 KB | Output is correct |
30 | Correct | 8 ms | 856 KB | Output is correct |
31 | Correct | 8 ms | 1008 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 860 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 8 ms | 860 KB | Output is correct |
4 | Correct | 7 ms | 992 KB | Output is correct |
5 | Correct | 8 ms | 1040 KB | Output is correct |
6 | Correct | 8 ms | 856 KB | Output is correct |
7 | Correct | 8 ms | 1008 KB | Output is correct |
8 | Correct | 59 ms | 1372 KB | Output is correct |
9 | Correct | 83 ms | 2496 KB | Output is correct |
10 | Correct | 66 ms | 1624 KB | Output is correct |
11 | Correct | 59 ms | 1688 KB | Output is correct |
12 | Correct | 64 ms | 1704 KB | Output is correct |
13 | Correct | 56 ms | 1372 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 860 KB | Output is correct |
2 | Correct | 7 ms | 860 KB | Output is correct |
3 | Correct | 8 ms | 860 KB | Output is correct |
4 | Correct | 7 ms | 1112 KB | Output is correct |
5 | Correct | 8 ms | 856 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 8 ms | 864 KB | Output is correct |
8 | Correct | 8 ms | 788 KB | Output is correct |
9 | Correct | 7 ms | 856 KB | Output is correct |
10 | Correct | 8 ms | 860 KB | Output is correct |
11 | Correct | 8 ms | 860 KB | Output is correct |
12 | Correct | 10 ms | 856 KB | Output is correct |
13 | Correct | 10 ms | 868 KB | Output is correct |
14 | Correct | 11 ms | 860 KB | Output is correct |
15 | Correct | 8 ms | 860 KB | Output is correct |
16 | Correct | 7 ms | 860 KB | Output is correct |
17 | Correct | 59 ms | 1372 KB | Output is correct |
18 | Correct | 83 ms | 2496 KB | Output is correct |
19 | Correct | 66 ms | 1624 KB | Output is correct |
20 | Correct | 59 ms | 1688 KB | Output is correct |
21 | Correct | 64 ms | 1704 KB | Output is correct |
22 | Correct | 56 ms | 1372 KB | Output is correct |
23 | Correct | 8 ms | 860 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 8 ms | 860 KB | Output is correct |
26 | Correct | 7 ms | 992 KB | Output is correct |
27 | Correct | 8 ms | 1040 KB | Output is correct |
28 | Correct | 8 ms | 856 KB | Output is correct |
29 | Correct | 8 ms | 1008 KB | Output is correct |
30 | Correct | 75 ms | 1360 KB | Output is correct |
31 | Correct | 56 ms | 1372 KB | Output is correct |
32 | Correct | 55 ms | 1368 KB | Output is correct |
33 | Correct | 10 ms | 860 KB | Output is correct |
34 | Correct | 7 ms | 860 KB | Output is correct |
35 | Correct | 7 ms | 860 KB | Output is correct |
36 | Correct | 8 ms | 860 KB | Output is correct |
37 | Correct | 0 ms | 348 KB | Output is correct |
38 | Correct | 7 ms | 860 KB | Output is correct |
39 | Correct | 8 ms | 860 KB | Output is correct |
40 | Correct | 7 ms | 856 KB | Output is correct |
41 | Correct | 1 ms | 348 KB | Output is correct |
42 | Correct | 8 ms | 856 KB | Output is correct |
43 | Correct | 57 ms | 1480 KB | Output is correct |
44 | Correct | 65 ms | 1372 KB | Output is correct |
45 | Correct | 70 ms | 1884 KB | Output is correct |
46 | Correct | 63 ms | 1536 KB | Output is correct |
47 | Correct | 57 ms | 1372 KB | Output is correct |
48 | Correct | 70 ms | 1552 KB | Output is correct |
49 | Correct | 81 ms | 3420 KB | Output is correct |
50 | Correct | 1 ms | 348 KB | Output is correct |
51 | Correct | 1 ms | 348 KB | Output is correct |
52 | Correct | 56 ms | 1368 KB | Output is correct |
53 | Correct | 60 ms | 1624 KB | Output is correct |
54 | Correct | 56 ms | 1368 KB | Output is correct |
55 | Correct | 56 ms | 1368 KB | Output is correct |
56 | Correct | 58 ms | 1484 KB | Output is correct |
57 | Correct | 1 ms | 348 KB | Output is correct |
58 | Correct | 8 ms | 1096 KB | Output is correct |
59 | Correct | 8 ms | 860 KB | Output is correct |
60 | Correct | 8 ms | 856 KB | Output is correct |
61 | Correct | 87 ms | 3480 KB | Output is correct |
62 | Correct | 98 ms | 3624 KB | Output is correct |
63 | Correct | 1 ms | 348 KB | Output is correct |