#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll inf = LLONG_MAX / 2;
const int MAXN = 100 + 25;
ll s[MAXN][1001], b[MAXN][1001]; int n, m, k;
ll adj[MAXN][MAXN], adj2[MAXN][MAXN], val[MAXN][MAXN];
bool check (ll x) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj2[i][j] = x * min(inf / x, adj[i][j]) - val[i][j];
}
}
bool flag = 0;
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj2[i][j] = min(adj2[i][j], adj2[i][l] + adj2[l][j]);
}
}
}
for (int i = 1; i <= n; i++) flag |= adj2[i][i] <= 0;
return flag;
}
int main () {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int x, y; cin >> x >> y;
b[i][j] = x, s[i][j] = y;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj[i][j] = inf;
}
}
while (m--) {
int a, b, c; cin >> a >> b >> c;
adj[a][b] = c;
}
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj[i][j] = min(adj[i][j], adj[i][l] + adj[l][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int l = 1; l <= k; l++) {
if (b[i][l] != -1 && s[j][l] != -1) {
val[i][j] = max(val[i][j], s[j][l] - b[i][l]);
}
}
}
}
ll l = 1, r = 1e9, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1; ans = mid;
} else {
r = mid - 1;
}
}
cout << (long long)(ans) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
4444 KB |
Output is correct |
2 |
Incorrect |
49 ms |
4444 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4444 KB |
Output is correct |
2 |
Correct |
7 ms |
4588 KB |
Output is correct |
3 |
Correct |
8 ms |
4444 KB |
Output is correct |
4 |
Correct |
7 ms |
4440 KB |
Output is correct |
5 |
Correct |
9 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
7 ms |
4612 KB |
Output is correct |
8 |
Correct |
7 ms |
4444 KB |
Output is correct |
9 |
Correct |
7 ms |
4592 KB |
Output is correct |
10 |
Correct |
7 ms |
4444 KB |
Output is correct |
11 |
Correct |
9 ms |
4444 KB |
Output is correct |
12 |
Correct |
8 ms |
4444 KB |
Output is correct |
13 |
Correct |
8 ms |
4444 KB |
Output is correct |
14 |
Correct |
8 ms |
4440 KB |
Output is correct |
15 |
Correct |
10 ms |
4444 KB |
Output is correct |
16 |
Correct |
7 ms |
4444 KB |
Output is correct |
17 |
Correct |
8 ms |
4640 KB |
Output is correct |
18 |
Correct |
1 ms |
4440 KB |
Output is correct |
19 |
Correct |
9 ms |
4444 KB |
Output is correct |
20 |
Correct |
9 ms |
4644 KB |
Output is correct |
21 |
Correct |
9 ms |
4444 KB |
Output is correct |
22 |
Correct |
8 ms |
4444 KB |
Output is correct |
23 |
Correct |
7 ms |
4444 KB |
Output is correct |
24 |
Incorrect |
7 ms |
4544 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4640 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
9 ms |
4444 KB |
Output is correct |
4 |
Correct |
9 ms |
4644 KB |
Output is correct |
5 |
Correct |
9 ms |
4444 KB |
Output is correct |
6 |
Correct |
8 ms |
4444 KB |
Output is correct |
7 |
Correct |
7 ms |
4444 KB |
Output is correct |
8 |
Correct |
59 ms |
4864 KB |
Output is correct |
9 |
Correct |
122 ms |
4692 KB |
Output is correct |
10 |
Correct |
53 ms |
4696 KB |
Output is correct |
11 |
Correct |
58 ms |
4700 KB |
Output is correct |
12 |
Correct |
58 ms |
4700 KB |
Output is correct |
13 |
Correct |
63 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4444 KB |
Output is correct |
2 |
Correct |
7 ms |
4588 KB |
Output is correct |
3 |
Correct |
8 ms |
4444 KB |
Output is correct |
4 |
Correct |
7 ms |
4440 KB |
Output is correct |
5 |
Correct |
9 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
7 ms |
4612 KB |
Output is correct |
8 |
Correct |
7 ms |
4444 KB |
Output is correct |
9 |
Correct |
7 ms |
4592 KB |
Output is correct |
10 |
Correct |
7 ms |
4444 KB |
Output is correct |
11 |
Correct |
9 ms |
4444 KB |
Output is correct |
12 |
Correct |
8 ms |
4444 KB |
Output is correct |
13 |
Correct |
8 ms |
4444 KB |
Output is correct |
14 |
Correct |
8 ms |
4440 KB |
Output is correct |
15 |
Correct |
10 ms |
4444 KB |
Output is correct |
16 |
Correct |
7 ms |
4444 KB |
Output is correct |
17 |
Correct |
59 ms |
4864 KB |
Output is correct |
18 |
Correct |
122 ms |
4692 KB |
Output is correct |
19 |
Correct |
53 ms |
4696 KB |
Output is correct |
20 |
Correct |
58 ms |
4700 KB |
Output is correct |
21 |
Correct |
58 ms |
4700 KB |
Output is correct |
22 |
Correct |
63 ms |
4700 KB |
Output is correct |
23 |
Correct |
8 ms |
4640 KB |
Output is correct |
24 |
Correct |
1 ms |
4440 KB |
Output is correct |
25 |
Correct |
9 ms |
4444 KB |
Output is correct |
26 |
Correct |
9 ms |
4644 KB |
Output is correct |
27 |
Correct |
9 ms |
4444 KB |
Output is correct |
28 |
Correct |
8 ms |
4444 KB |
Output is correct |
29 |
Correct |
7 ms |
4444 KB |
Output is correct |
30 |
Correct |
99 ms |
4444 KB |
Output is correct |
31 |
Incorrect |
49 ms |
4444 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |