#pragma GCC optimize "trapv"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll INF = 1'000'000'001LL;
// const ll INF = 100;
int main()
{
int N, M, K;
cin >> N >> M >> K;
vvll B(1+N, vll(1+K, INF));
vvll S(1+N, vll(1+K, 0));
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= K; j++)
{
ll b, s;
cin >> b >> s;
if(b != -1) B[i][j] = b;
if(s != -1) S[i][j] = s;
}
}
vvll dist(1+N, vll(1+N, INF));
for(int i = 1; i <= N; i++) dist[i][i] = 0;
for(int e = 1; e <= M; e++)
{
int V, W;
ll T;
cin >> V >> W >> T;
dist[V][W] = min(dist[V][W], T);
}
for(int k = 1; k <= N; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
vvll profit(1+N, vll(1+N, 0));
for(int u = 1; u <= N; u++)
for(int v = 1; v <= N; v++)
for(int j = 1; j <= K; j++)
profit[u][v] = max(profit[u][v], S[v][j] - B[u][j]);
// cerr << "read\n";
//
// for(int u = 1; u <= N; u++)
// for(int v = 1; v <= N; v++)
// cerr << u << ' ' << v << " : " << dist[u][v] << ' ' << profit[u][v] << '\n';
// for(int u = 1; u <= N; u++)
// for(int v = 1; v <= N; v++)
// cout << u << ' ' << v << ' ' << dist[u][v] << ' ' << profit[u][v] << '\n';
ll basic_res = 0;
for(int v = 2; v <= N; v++)
basic_res = max(basic_res, profit[1][v]/(dist[1][v] + dist[v][1]));
// cerr << "basic res = " << basic_res << '\n';
// for(int v = 2; v <= N; v++) cerr << v << " : " << dist[1][v] << ' ' << dist[v][1] << ' ' << profit[1][v] << '\n';
ll lo = 0, hi = INF;
while(lo != hi)
{
// cerr << "\n\n\n\n\n\n";
// cerr << lo << ' ' << hi << " : ";
ll aim = (lo+hi)/2 + 1;
// cerr << aim << '\n';
vvll newdist(1+N, vll(1+N, -INF*INF));
for(int u = 1; u <= N; u++)
for(int v = 1; v <= N; v++)
newdist[u][v] = max(newdist[u][v], profit[u][v] - aim*dist[u][v]);
for(int k = 1; k <= N; k++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
{
newdist[i][j] = max({newdist[i][j], min(INF*INF, newdist[i][k] + newdist[k][j]), -INF*INF});
}
// for(int v = 2; v <= N; v++)
// cerr << v << " : " << newdist[1][v] << ' ' << newdist[v][1] << '\n';
// cerr << "\n\n\n\n\n searching " << aim << '\n';
// for(int u = 1; u <= N; u++)
// for(int v = 1; v <= N; v++)
// cerr << u << ' ' << v << " : " << newdist[u][v] << '\n';
ll mx = -1;
for(int u = 1; u <= N; u++)
for(int v = u+1; v <= N; v++)
mx = max(mx, newdist[u][v] + newdist[v][u]);
if(mx >= 0)
lo = aim;
else
hi = aim-1;
}
cout << lo << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
188 ms |
2968 KB |
Output is correct |
2 |
Correct |
113 ms |
540 KB |
Output is correct |
3 |
Correct |
117 ms |
528 KB |
Output is correct |
4 |
Correct |
14 ms |
360 KB |
Output is correct |
5 |
Correct |
14 ms |
332 KB |
Output is correct |
6 |
Correct |
14 ms |
292 KB |
Output is correct |
7 |
Correct |
16 ms |
436 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
18 ms |
332 KB |
Output is correct |
10 |
Correct |
15 ms |
332 KB |
Output is correct |
11 |
Correct |
15 ms |
368 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
17 ms |
432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
292 KB |
Output is correct |
2 |
Correct |
16 ms |
436 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
18 ms |
332 KB |
Output is correct |
5 |
Correct |
15 ms |
332 KB |
Output is correct |
6 |
Correct |
15 ms |
368 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
17 ms |
432 KB |
Output is correct |
9 |
Correct |
19 ms |
348 KB |
Output is correct |
10 |
Correct |
13 ms |
332 KB |
Output is correct |
11 |
Correct |
15 ms |
396 KB |
Output is correct |
12 |
Correct |
14 ms |
408 KB |
Output is correct |
13 |
Correct |
17 ms |
432 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
14 ms |
372 KB |
Output is correct |
16 |
Correct |
15 ms |
416 KB |
Output is correct |
17 |
Correct |
14 ms |
384 KB |
Output is correct |
18 |
Correct |
16 ms |
304 KB |
Output is correct |
19 |
Correct |
16 ms |
444 KB |
Output is correct |
20 |
Correct |
16 ms |
444 KB |
Output is correct |
21 |
Correct |
15 ms |
384 KB |
Output is correct |
22 |
Correct |
16 ms |
404 KB |
Output is correct |
23 |
Correct |
18 ms |
460 KB |
Output is correct |
24 |
Correct |
16 ms |
372 KB |
Output is correct |
25 |
Correct |
18 ms |
432 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
23 ms |
332 KB |
Output is correct |
28 |
Correct |
19 ms |
444 KB |
Output is correct |
29 |
Correct |
18 ms |
332 KB |
Output is correct |
30 |
Correct |
18 ms |
380 KB |
Output is correct |
31 |
Correct |
15 ms |
288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
432 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
23 ms |
332 KB |
Output is correct |
4 |
Correct |
19 ms |
444 KB |
Output is correct |
5 |
Correct |
18 ms |
332 KB |
Output is correct |
6 |
Correct |
18 ms |
380 KB |
Output is correct |
7 |
Correct |
15 ms |
288 KB |
Output is correct |
8 |
Correct |
119 ms |
820 KB |
Output is correct |
9 |
Correct |
213 ms |
3204 KB |
Output is correct |
10 |
Correct |
127 ms |
680 KB |
Output is correct |
11 |
Correct |
119 ms |
900 KB |
Output is correct |
12 |
Correct |
120 ms |
804 KB |
Output is correct |
13 |
Correct |
119 ms |
688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
348 KB |
Output is correct |
2 |
Correct |
13 ms |
332 KB |
Output is correct |
3 |
Correct |
15 ms |
396 KB |
Output is correct |
4 |
Correct |
14 ms |
408 KB |
Output is correct |
5 |
Correct |
17 ms |
432 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
14 ms |
372 KB |
Output is correct |
8 |
Correct |
15 ms |
416 KB |
Output is correct |
9 |
Correct |
14 ms |
384 KB |
Output is correct |
10 |
Correct |
16 ms |
304 KB |
Output is correct |
11 |
Correct |
16 ms |
444 KB |
Output is correct |
12 |
Correct |
16 ms |
444 KB |
Output is correct |
13 |
Correct |
15 ms |
384 KB |
Output is correct |
14 |
Correct |
16 ms |
404 KB |
Output is correct |
15 |
Correct |
18 ms |
460 KB |
Output is correct |
16 |
Correct |
16 ms |
372 KB |
Output is correct |
17 |
Correct |
119 ms |
820 KB |
Output is correct |
18 |
Correct |
213 ms |
3204 KB |
Output is correct |
19 |
Correct |
127 ms |
680 KB |
Output is correct |
20 |
Correct |
119 ms |
900 KB |
Output is correct |
21 |
Correct |
120 ms |
804 KB |
Output is correct |
22 |
Correct |
119 ms |
688 KB |
Output is correct |
23 |
Correct |
18 ms |
432 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
23 ms |
332 KB |
Output is correct |
26 |
Correct |
19 ms |
444 KB |
Output is correct |
27 |
Correct |
18 ms |
332 KB |
Output is correct |
28 |
Correct |
18 ms |
380 KB |
Output is correct |
29 |
Correct |
15 ms |
288 KB |
Output is correct |
30 |
Correct |
188 ms |
2968 KB |
Output is correct |
31 |
Correct |
113 ms |
540 KB |
Output is correct |
32 |
Correct |
117 ms |
528 KB |
Output is correct |
33 |
Correct |
14 ms |
360 KB |
Output is correct |
34 |
Correct |
14 ms |
332 KB |
Output is correct |
35 |
Correct |
14 ms |
292 KB |
Output is correct |
36 |
Correct |
16 ms |
436 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
18 ms |
332 KB |
Output is correct |
39 |
Correct |
15 ms |
332 KB |
Output is correct |
40 |
Correct |
15 ms |
368 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
17 ms |
432 KB |
Output is correct |
43 |
Correct |
105 ms |
460 KB |
Output is correct |
44 |
Correct |
108 ms |
716 KB |
Output is correct |
45 |
Correct |
159 ms |
2280 KB |
Output is correct |
46 |
Correct |
125 ms |
716 KB |
Output is correct |
47 |
Correct |
133 ms |
716 KB |
Output is correct |
48 |
Correct |
113 ms |
836 KB |
Output is correct |
49 |
Correct |
201 ms |
4044 KB |
Output is correct |
50 |
Correct |
1 ms |
204 KB |
Output is correct |
51 |
Correct |
0 ms |
204 KB |
Output is correct |
52 |
Correct |
102 ms |
460 KB |
Output is correct |
53 |
Correct |
113 ms |
668 KB |
Output is correct |
54 |
Correct |
119 ms |
636 KB |
Output is correct |
55 |
Correct |
109 ms |
588 KB |
Output is correct |
56 |
Correct |
102 ms |
552 KB |
Output is correct |
57 |
Correct |
0 ms |
204 KB |
Output is correct |
58 |
Correct |
19 ms |
540 KB |
Output is correct |
59 |
Correct |
19 ms |
460 KB |
Output is correct |
60 |
Correct |
19 ms |
460 KB |
Output is correct |
61 |
Correct |
224 ms |
4160 KB |
Output is correct |
62 |
Correct |
218 ms |
4032 KB |
Output is correct |
63 |
Correct |
1 ms |
292 KB |
Output is correct |