#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
const ll inf = 1e18+9;
ll b[109][1009];
ll s[109][1009];
ll dis[109][109];
pii edge[109][109];
pii dp[109][109][109];
ll n, m, k;
ll check(ll val){
vector<pair<ld, pll>> edges;
vector<ld> dis(n+1);
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j){
if(edge[i][j].ff < 0)
continue;
ld len = val*edge[i][j].ss-edge[i][j].ff-0.00000001;
edges.pb({len, {i, j}});
}
ll x = -1;
for(ll i = 0; i < n; ++i){
x = -1;
for(auto u : edges){
ll v1 = u.ss.ff;
ll v2 = u.ss.ss;
ld d = u.ff;
if(dis[v1] + d < dis[v2]){
dis[v2] = dis[v1] + d;
x = v2;
}
}
}
return (x != -1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> m >> k;
for(ll i = 1; i <= n; ++i)
for(ll j = 0; j < k; ++j)
cin >> b[i][j] >> s[i][j];
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j)
if(i != j)
dis[i][j] = inf;
while(m--){
ll x, y, z;
cin >> x >> y >> z;
dis[x][y] = min(dis[x][y], z);
}
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j)
for(ll z = 1; z <= n; ++z)
dis[j][z] = min(dis[j][z], dis[j][i] + dis[i][z]);
for(ll i = 1; i <= n; ++i)
for(ll j = 1; j <= n; ++j){
if(i == j || dis[i][j] == inf){
edge[i][j] = {-1, -1};
continue;
}
edge[i][j].ss = dis[i][j];
for(ll z = 0; z < k; ++z)
if(b[i][z] != -1 && s[j][z] != -1)
edge[i][j].ff = max(edge[i][j].ff, s[j][z]-b[i][z]);
}
ll l = 0, r = 1e9;
while(l < r){
ll m = (l+r+1)/2;
if(check(m))
l = m;
else
r = m-1;
}
cout << l << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
219 ms |
3100 KB |
Output is correct |
2 |
Correct |
163 ms |
2312 KB |
Output is correct |
3 |
Correct |
187 ms |
2320 KB |
Output is correct |
4 |
Correct |
25 ms |
1152 KB |
Output is correct |
5 |
Correct |
25 ms |
1152 KB |
Output is correct |
6 |
Correct |
25 ms |
1152 KB |
Output is correct |
7 |
Correct |
27 ms |
1232 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
28 ms |
1152 KB |
Output is correct |
10 |
Correct |
28 ms |
1168 KB |
Output is correct |
11 |
Correct |
26 ms |
1184 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
13 |
Correct |
17 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
1168 KB |
Output is correct |
2 |
Correct |
26 ms |
1184 KB |
Output is correct |
3 |
Correct |
27 ms |
1248 KB |
Output is correct |
4 |
Correct |
25 ms |
1220 KB |
Output is correct |
5 |
Correct |
32 ms |
1280 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
12 ms |
896 KB |
Output is correct |
8 |
Correct |
21 ms |
1024 KB |
Output is correct |
9 |
Correct |
11 ms |
896 KB |
Output is correct |
10 |
Correct |
15 ms |
1024 KB |
Output is correct |
11 |
Correct |
27 ms |
1264 KB |
Output is correct |
12 |
Correct |
19 ms |
1152 KB |
Output is correct |
13 |
Correct |
29 ms |
1200 KB |
Output is correct |
14 |
Correct |
28 ms |
1188 KB |
Output is correct |
15 |
Correct |
28 ms |
1264 KB |
Output is correct |
16 |
Correct |
27 ms |
1152 KB |
Output is correct |
17 |
Correct |
27 ms |
1264 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
27 ms |
1248 KB |
Output is correct |
20 |
Correct |
28 ms |
1248 KB |
Output is correct |
21 |
Correct |
19 ms |
1152 KB |
Output is correct |
22 |
Correct |
29 ms |
1264 KB |
Output is correct |
23 |
Correct |
17 ms |
1024 KB |
Output is correct |
24 |
Correct |
25 ms |
1152 KB |
Output is correct |
25 |
Correct |
27 ms |
1232 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
28 ms |
1152 KB |
Output is correct |
28 |
Correct |
28 ms |
1168 KB |
Output is correct |
29 |
Correct |
26 ms |
1184 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
17 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
177 ms |
2472 KB |
Output is correct |
2 |
Correct |
221 ms |
4812 KB |
Output is correct |
3 |
Correct |
169 ms |
2624 KB |
Output is correct |
4 |
Correct |
172 ms |
2704 KB |
Output is correct |
5 |
Correct |
182 ms |
2704 KB |
Output is correct |
6 |
Correct |
176 ms |
2548 KB |
Output is correct |
7 |
Correct |
27 ms |
1264 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
27 ms |
1248 KB |
Output is correct |
10 |
Correct |
28 ms |
1248 KB |
Output is correct |
11 |
Correct |
19 ms |
1152 KB |
Output is correct |
12 |
Correct |
29 ms |
1264 KB |
Output is correct |
13 |
Correct |
17 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
1168 KB |
Output is correct |
2 |
Correct |
26 ms |
1184 KB |
Output is correct |
3 |
Correct |
27 ms |
1248 KB |
Output is correct |
4 |
Correct |
25 ms |
1220 KB |
Output is correct |
5 |
Correct |
32 ms |
1280 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
12 ms |
896 KB |
Output is correct |
8 |
Correct |
21 ms |
1024 KB |
Output is correct |
9 |
Correct |
11 ms |
896 KB |
Output is correct |
10 |
Correct |
15 ms |
1024 KB |
Output is correct |
11 |
Correct |
27 ms |
1264 KB |
Output is correct |
12 |
Correct |
19 ms |
1152 KB |
Output is correct |
13 |
Correct |
29 ms |
1200 KB |
Output is correct |
14 |
Correct |
28 ms |
1188 KB |
Output is correct |
15 |
Correct |
28 ms |
1264 KB |
Output is correct |
16 |
Correct |
27 ms |
1152 KB |
Output is correct |
17 |
Correct |
177 ms |
2472 KB |
Output is correct |
18 |
Correct |
221 ms |
4812 KB |
Output is correct |
19 |
Correct |
169 ms |
2624 KB |
Output is correct |
20 |
Correct |
172 ms |
2704 KB |
Output is correct |
21 |
Correct |
182 ms |
2704 KB |
Output is correct |
22 |
Correct |
176 ms |
2548 KB |
Output is correct |
23 |
Correct |
27 ms |
1264 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
27 ms |
1248 KB |
Output is correct |
26 |
Correct |
28 ms |
1248 KB |
Output is correct |
27 |
Correct |
19 ms |
1152 KB |
Output is correct |
28 |
Correct |
29 ms |
1264 KB |
Output is correct |
29 |
Correct |
17 ms |
1024 KB |
Output is correct |
30 |
Correct |
172 ms |
2320 KB |
Output is correct |
31 |
Correct |
182 ms |
2500 KB |
Output is correct |
32 |
Correct |
192 ms |
3692 KB |
Output is correct |
33 |
Correct |
178 ms |
2644 KB |
Output is correct |
34 |
Correct |
175 ms |
2628 KB |
Output is correct |
35 |
Correct |
175 ms |
2516 KB |
Output is correct |
36 |
Correct |
232 ms |
5164 KB |
Output is correct |
37 |
Correct |
5 ms |
384 KB |
Output is correct |
38 |
Correct |
5 ms |
384 KB |
Output is correct |
39 |
Correct |
166 ms |
2372 KB |
Output is correct |
40 |
Correct |
173 ms |
2564 KB |
Output is correct |
41 |
Correct |
113 ms |
2004 KB |
Output is correct |
42 |
Correct |
146 ms |
2300 KB |
Output is correct |
43 |
Correct |
166 ms |
2328 KB |
Output is correct |
44 |
Correct |
5 ms |
384 KB |
Output is correct |
45 |
Correct |
22 ms |
1152 KB |
Output is correct |
46 |
Correct |
21 ms |
1280 KB |
Output is correct |
47 |
Correct |
16 ms |
1152 KB |
Output is correct |
48 |
Correct |
237 ms |
5272 KB |
Output is correct |
49 |
Correct |
233 ms |
5180 KB |
Output is correct |
50 |
Correct |
5 ms |
384 KB |
Output is correct |
51 |
Correct |
219 ms |
3100 KB |
Output is correct |
52 |
Correct |
163 ms |
2312 KB |
Output is correct |
53 |
Correct |
187 ms |
2320 KB |
Output is correct |
54 |
Correct |
25 ms |
1152 KB |
Output is correct |
55 |
Correct |
25 ms |
1152 KB |
Output is correct |
56 |
Correct |
25 ms |
1152 KB |
Output is correct |
57 |
Correct |
27 ms |
1232 KB |
Output is correct |
58 |
Correct |
5 ms |
384 KB |
Output is correct |
59 |
Correct |
28 ms |
1152 KB |
Output is correct |
60 |
Correct |
28 ms |
1168 KB |
Output is correct |
61 |
Correct |
26 ms |
1184 KB |
Output is correct |
62 |
Correct |
5 ms |
512 KB |
Output is correct |
63 |
Correct |
17 ms |
1152 KB |
Output is correct |