# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
838484 | 2023-08-27T08:41:28 Z | nonono | Travelling Merchant (APIO17_merchant) | C++14 | 59 ms | 5400 KB |
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 1e18; const int mxN = 1005; int N, M, K; int b[mxN][mxN], s[mxN][mxN]; int d[mxN][mxN], dd[mxN][mxN], f[mxN][mxN]; bool find_path(int x) { for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { f[i][j] = dd[i][j] - d[i][j] * x; } } for(int k = 1; k <= N; k ++) { for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { f[i][j] = max(f[i][j], f[i][k] + f[k][j]); } } } int max_Dist = - INF; for(int i = 1; i <= N; i ++) max_Dist = max(max_Dist, f[i][i]); return max_Dist >= 0; } signed main() { #define taskname "" if(fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); 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 <= N; i ++) { for(int j = 1; j <= N; j ++) { d[i][j] = (long long) 1E9; } } for(int i = 1; i <= M; i ++) { int u, v, w; cin >> u >> v >> w; d[u][v] = min(d[u][v], w); } for(int k = 1; k <= N; k ++) { for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(int i = 1; i <= K; i ++) { for(int j = 1; j <= N; j ++) { if(b[j][i] == -1) continue ; for(int k = 1; k <= N; k ++) { if(s[k][i] == -1) continue ; dd[j][k] = max(dd[j][k], s[k][i] - b[j][i]); } } } int low = 1, high = (long long) 1E9; while(low <= high) { int mid = (low + high) / 2; if(find_path(mid) == true) low = mid + 1; else high = mid - 1; } cout << low - 1 << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 4180 KB | Output is correct |
2 | Correct | 30 ms | 2088 KB | Output is correct |
3 | Correct | 30 ms | 2004 KB | Output is correct |
4 | Correct | 4 ms | 1108 KB | Output is correct |
5 | Correct | 4 ms | 1108 KB | Output is correct |
6 | Correct | 4 ms | 1228 KB | Output is correct |
7 | Correct | 4 ms | 1236 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 4 ms | 1108 KB | Output is correct |
10 | Correct | 4 ms | 1108 KB | Output is correct |
11 | Correct | 6 ms | 1104 KB | Output is correct |
12 | Correct | 1 ms | 460 KB | Output is correct |
13 | Correct | 4 ms | 1268 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1228 KB | Output is correct |
2 | Correct | 4 ms | 1236 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 4 ms | 1108 KB | Output is correct |
5 | Correct | 4 ms | 1108 KB | Output is correct |
6 | Correct | 6 ms | 1104 KB | Output is correct |
7 | Correct | 1 ms | 460 KB | Output is correct |
8 | Correct | 4 ms | 1268 KB | Output is correct |
9 | Correct | 4 ms | 1364 KB | Output is correct |
10 | Correct | 4 ms | 1228 KB | Output is correct |
11 | Correct | 5 ms | 1496 KB | Output is correct |
12 | Correct | 4 ms | 1364 KB | Output is correct |
13 | Correct | 5 ms | 1496 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 4 ms | 1236 KB | Output is correct |
16 | Correct | 4 ms | 1364 KB | Output is correct |
17 | Correct | 4 ms | 1236 KB | Output is correct |
18 | Correct | 4 ms | 1236 KB | Output is correct |
19 | Correct | 5 ms | 1508 KB | Output is correct |
20 | Correct | 4 ms | 1492 KB | Output is correct |
21 | Correct | 6 ms | 1440 KB | Output is correct |
22 | Correct | 5 ms | 1364 KB | Output is correct |
23 | Correct | 5 ms | 1492 KB | Output is correct |
24 | Correct | 4 ms | 1236 KB | Output is correct |
25 | Correct | 5 ms | 1364 KB | Output is correct |
26 | Correct | 1 ms | 384 KB | Output is correct |
27 | Correct | 5 ms | 1496 KB | Output is correct |
28 | Correct | 5 ms | 1492 KB | Output is correct |
29 | Correct | 4 ms | 1492 KB | Output is correct |
30 | Correct | 4 ms | 1440 KB | Output is correct |
31 | Correct | 4 ms | 1364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1364 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 1496 KB | Output is correct |
4 | Correct | 5 ms | 1492 KB | Output is correct |
5 | Correct | 4 ms | 1492 KB | Output is correct |
6 | Correct | 4 ms | 1440 KB | Output is correct |
7 | Correct | 4 ms | 1364 KB | Output is correct |
8 | Correct | 36 ms | 2900 KB | Output is correct |
9 | Correct | 53 ms | 5036 KB | Output is correct |
10 | Correct | 34 ms | 2644 KB | Output is correct |
11 | Correct | 38 ms | 2900 KB | Output is correct |
12 | Correct | 33 ms | 2904 KB | Output is correct |
13 | Correct | 32 ms | 2764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1364 KB | Output is correct |
2 | Correct | 4 ms | 1228 KB | Output is correct |
3 | Correct | 5 ms | 1496 KB | Output is correct |
4 | Correct | 4 ms | 1364 KB | Output is correct |
5 | Correct | 5 ms | 1496 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 4 ms | 1236 KB | Output is correct |
8 | Correct | 4 ms | 1364 KB | Output is correct |
9 | Correct | 4 ms | 1236 KB | Output is correct |
10 | Correct | 4 ms | 1236 KB | Output is correct |
11 | Correct | 5 ms | 1508 KB | Output is correct |
12 | Correct | 4 ms | 1492 KB | Output is correct |
13 | Correct | 6 ms | 1440 KB | Output is correct |
14 | Correct | 5 ms | 1364 KB | Output is correct |
15 | Correct | 5 ms | 1492 KB | Output is correct |
16 | Correct | 4 ms | 1236 KB | Output is correct |
17 | Correct | 36 ms | 2900 KB | Output is correct |
18 | Correct | 53 ms | 5036 KB | Output is correct |
19 | Correct | 34 ms | 2644 KB | Output is correct |
20 | Correct | 38 ms | 2900 KB | Output is correct |
21 | Correct | 33 ms | 2904 KB | Output is correct |
22 | Correct | 32 ms | 2764 KB | Output is correct |
23 | Correct | 5 ms | 1364 KB | Output is correct |
24 | Correct | 1 ms | 384 KB | Output is correct |
25 | Correct | 5 ms | 1496 KB | Output is correct |
26 | Correct | 5 ms | 1492 KB | Output is correct |
27 | Correct | 4 ms | 1492 KB | Output is correct |
28 | Correct | 4 ms | 1440 KB | Output is correct |
29 | Correct | 4 ms | 1364 KB | Output is correct |
30 | Correct | 43 ms | 4180 KB | Output is correct |
31 | Correct | 30 ms | 2088 KB | Output is correct |
32 | Correct | 30 ms | 2004 KB | Output is correct |
33 | Correct | 4 ms | 1108 KB | Output is correct |
34 | Correct | 4 ms | 1108 KB | Output is correct |
35 | Correct | 4 ms | 1228 KB | Output is correct |
36 | Correct | 4 ms | 1236 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 4 ms | 1108 KB | Output is correct |
39 | Correct | 4 ms | 1108 KB | Output is correct |
40 | Correct | 6 ms | 1104 KB | Output is correct |
41 | Correct | 1 ms | 460 KB | Output is correct |
42 | Correct | 4 ms | 1268 KB | Output is correct |
43 | Correct | 30 ms | 2260 KB | Output is correct |
44 | Correct | 32 ms | 2772 KB | Output is correct |
45 | Correct | 38 ms | 3816 KB | Output is correct |
46 | Correct | 32 ms | 2644 KB | Output is correct |
47 | Correct | 31 ms | 2652 KB | Output is correct |
48 | Correct | 31 ms | 2724 KB | Output is correct |
49 | Correct | 58 ms | 5356 KB | Output is correct |
50 | Correct | 1 ms | 456 KB | Output is correct |
51 | Correct | 1 ms | 464 KB | Output is correct |
52 | Correct | 30 ms | 2204 KB | Output is correct |
53 | Correct | 31 ms | 2268 KB | Output is correct |
54 | Correct | 31 ms | 2396 KB | Output is correct |
55 | Correct | 30 ms | 2136 KB | Output is correct |
56 | Correct | 30 ms | 2132 KB | Output is correct |
57 | Correct | 1 ms | 340 KB | Output is correct |
58 | Correct | 5 ms | 1492 KB | Output is correct |
59 | Correct | 5 ms | 1492 KB | Output is correct |
60 | Correct | 5 ms | 1508 KB | Output is correct |
61 | Correct | 57 ms | 5312 KB | Output is correct |
62 | Correct | 59 ms | 5400 KB | Output is correct |
63 | Correct | 1 ms | 340 KB | Output is correct |