#include <bits/stdc++.h>
using namespace std;
using T = long long;
const int maxn = 100;
const int maxk = 1000;
const int maxm = 9900;
const T INF = 0x3fff'ffff'ffff;
int n, m, k; // n markets, m pathways, k items
T items[maxn][maxk][2]; // n markets, k items per market, buy/sell = price of buy/sell
T grid[maxn][maxn]; // adj matrix
T streaks[maxn][maxn];
T temp_streaks[maxn][maxn];
int main() {
cin.tie(nullptr)->ios::sync_with_stdio(false);
// freopen("main.in", "r", stdin);
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
for (int l = 0; l < 2; l++)
cin >> items[i][j][l];
fill(&grid[0][0], &grid[0][0] + sizeof(grid) / sizeof(grid[0][0]), INF);
for (int i = 0; i < m; i++) {
int a, b; T c; cin >> a >> b >> c; a--, b--;
grid[a][b] = min(grid[a][b], c);
}
// floyd warshall on grid
for (int l = 0; l < n; l++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
grid[i][j] = min(grid[i][j], grid[i][l] + grid[l][j]);
// creating streaks
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int l = 0; l < k; l++)
if (items[j][l][1] != -1 && items[i][l][0] != -1)
streaks[i][j] = max(streaks[i][j], items[j][l][1] - items[i][l][0]);
// bin search on answer
T lo = 0, hi = maxk * 1e9 * 10;
while (lo < hi) {
T mid = (lo + hi + 1) >> 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp_streaks[i][j] = (grid[i][j] == INF ? -INF : streaks[i][j] - mid * grid[i][j]);
// for (int i = 0; i < n; i++)
// temp_streaks[i][i] = -INF;
for (int l = 0; l < n; l++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp_streaks[i][j] = max(temp_streaks[i][j], temp_streaks[i][l] + temp_streaks[l][j]);
bool works = false;
for (int i = 0; i < n && !works; i++)
works |= temp_streaks[i][i] >= 0;
if (works)
lo = mid;
else
hi = mid - 1;
}
// output
cout << lo << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
62 ms |
2028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
596 KB |
Output is correct |
2 |
Correct |
6 ms |
596 KB |
Output is correct |
3 |
Correct |
10 ms |
724 KB |
Output is correct |
4 |
Correct |
8 ms |
596 KB |
Output is correct |
5 |
Correct |
7 ms |
732 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
8 ms |
596 KB |
Output is correct |
8 |
Correct |
12 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
696 KB |
Output is correct |
10 |
Correct |
7 ms |
724 KB |
Output is correct |
11 |
Correct |
7 ms |
676 KB |
Output is correct |
12 |
Correct |
8 ms |
720 KB |
Output is correct |
13 |
Correct |
7 ms |
596 KB |
Output is correct |
14 |
Correct |
7 ms |
724 KB |
Output is correct |
15 |
Correct |
8 ms |
724 KB |
Output is correct |
16 |
Correct |
6 ms |
596 KB |
Output is correct |
17 |
Correct |
7 ms |
724 KB |
Output is correct |
18 |
Correct |
1 ms |
328 KB |
Output is correct |
19 |
Correct |
7 ms |
700 KB |
Output is correct |
20 |
Correct |
8 ms |
724 KB |
Output is correct |
21 |
Correct |
8 ms |
780 KB |
Output is correct |
22 |
Correct |
6 ms |
596 KB |
Output is correct |
23 |
Correct |
6 ms |
580 KB |
Output is correct |
24 |
Correct |
7 ms |
584 KB |
Output is correct |
25 |
Correct |
7 ms |
720 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
6 ms |
596 KB |
Output is correct |
28 |
Correct |
6 ms |
596 KB |
Output is correct |
29 |
Correct |
7 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
7 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
7 ms |
700 KB |
Output is correct |
4 |
Correct |
8 ms |
724 KB |
Output is correct |
5 |
Correct |
8 ms |
780 KB |
Output is correct |
6 |
Correct |
6 ms |
596 KB |
Output is correct |
7 |
Correct |
6 ms |
580 KB |
Output is correct |
8 |
Correct |
47 ms |
1092 KB |
Output is correct |
9 |
Correct |
89 ms |
2096 KB |
Output is correct |
10 |
Correct |
45 ms |
1004 KB |
Output is correct |
11 |
Incorrect |
48 ms |
1108 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
596 KB |
Output is correct |
2 |
Correct |
6 ms |
596 KB |
Output is correct |
3 |
Correct |
10 ms |
724 KB |
Output is correct |
4 |
Correct |
8 ms |
596 KB |
Output is correct |
5 |
Correct |
7 ms |
732 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
8 ms |
596 KB |
Output is correct |
8 |
Correct |
12 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
696 KB |
Output is correct |
10 |
Correct |
7 ms |
724 KB |
Output is correct |
11 |
Correct |
7 ms |
676 KB |
Output is correct |
12 |
Correct |
8 ms |
720 KB |
Output is correct |
13 |
Correct |
7 ms |
596 KB |
Output is correct |
14 |
Correct |
7 ms |
724 KB |
Output is correct |
15 |
Correct |
8 ms |
724 KB |
Output is correct |
16 |
Correct |
6 ms |
596 KB |
Output is correct |
17 |
Correct |
47 ms |
1092 KB |
Output is correct |
18 |
Correct |
89 ms |
2096 KB |
Output is correct |
19 |
Correct |
45 ms |
1004 KB |
Output is correct |
20 |
Incorrect |
48 ms |
1108 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |