#define _DE132BUG
// #include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
// using namespace atcoder;
#define endl "\n"
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<pii> vii;
const long double pi = acos(-1.0);
const int INF = 1987654321;
const ll LLINF = 2e18;
const double eps = 1e-9;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//
ll buy[104][2004];
ll sell[104][2004];
ll dist[104][104];
ll bs[104][104];
ld newdist[104][104];
struct Edge{
int u, v, weight;
bool operator<(Edge const& other){
return weight < other.weight;
}
};
int main(){
#ifdef _DEBUG
freopen ("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K; cin >> N >> M >> K;
for(int i = 1; i <= N; i++){
for(int k = 0; k < K; k++){
cin >> buy[i][k] >> sell[i][k];
}
}
memset(dist, 0x3f, sizeof(dist));
while(M--){
ll u, v, w; cin >> u >> v >> w;
dist[u][v] = w;
}
for(int k = 1; k <= N; k++){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
chmin(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// item
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
for(int k = 0; k < K; k++){
if(sell[j][k] != -1 && buy[i][k] != -1){
chmax(bs[i][j], 1LL* sell[j][k]-buy[i][k]);
}
}
}
}
ld lo = 0, hi = 2e9;
for(int it = 0; it < 100; it++){
ld mid = (lo + hi) / 2;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(dist[i][j] > 1e9+5) newdist[i][j] = -1e12;
else newdist[i][j] = bs[i][j]-mid*dist[i][j];
}
}
for(int k = 1; k <= N; k++){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
chmax(newdist[i][j], newdist[i][k] + newdist[k][j]);
}
}
}
bool flag = false;
for(int i = 1; i <= N; i++){
if(newdist[i][i] >= 0){
flag = true;
break;
}
}
if(flag) lo = mid;
else hi = mid;
// cout << hi << endl;
}
// cout << hi d<< endl;
cout << (ll)floor(hi) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
474 ms |
4920 KB |
Output is correct |
2 |
Correct |
446 ms |
3028 KB |
Output is correct |
3 |
Correct |
468 ms |
3156 KB |
Output is correct |
4 |
Correct |
51 ms |
2652 KB |
Output is correct |
5 |
Correct |
52 ms |
2904 KB |
Output is correct |
6 |
Correct |
52 ms |
2648 KB |
Output is correct |
7 |
Correct |
58 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
61 ms |
2652 KB |
Output is correct |
10 |
Correct |
51 ms |
2652 KB |
Output is correct |
11 |
Correct |
52 ms |
2716 KB |
Output is correct |
12 |
Correct |
1 ms |
2392 KB |
Output is correct |
13 |
Correct |
51 ms |
2648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
2648 KB |
Output is correct |
2 |
Correct |
58 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
61 ms |
2652 KB |
Output is correct |
5 |
Correct |
51 ms |
2652 KB |
Output is correct |
6 |
Correct |
52 ms |
2716 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
51 ms |
2648 KB |
Output is correct |
9 |
Correct |
61 ms |
2756 KB |
Output is correct |
10 |
Correct |
59 ms |
2724 KB |
Output is correct |
11 |
Correct |
56 ms |
2756 KB |
Output is correct |
12 |
Correct |
47 ms |
2648 KB |
Output is correct |
13 |
Correct |
75 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
56 ms |
2744 KB |
Output is correct |
16 |
Correct |
52 ms |
2760 KB |
Output is correct |
17 |
Correct |
50 ms |
2740 KB |
Output is correct |
18 |
Correct |
52 ms |
2652 KB |
Output is correct |
19 |
Correct |
66 ms |
2648 KB |
Output is correct |
20 |
Correct |
58 ms |
2652 KB |
Output is correct |
21 |
Correct |
57 ms |
2900 KB |
Output is correct |
22 |
Correct |
55 ms |
2652 KB |
Output is correct |
23 |
Correct |
63 ms |
2660 KB |
Output is correct |
24 |
Correct |
53 ms |
2648 KB |
Output is correct |
25 |
Correct |
89 ms |
2772 KB |
Output is correct |
26 |
Correct |
1 ms |
2396 KB |
Output is correct |
27 |
Correct |
92 ms |
2792 KB |
Output is correct |
28 |
Correct |
63 ms |
2648 KB |
Output is correct |
29 |
Correct |
58 ms |
2792 KB |
Output is correct |
30 |
Correct |
54 ms |
2648 KB |
Output is correct |
31 |
Correct |
57 ms |
2728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
2772 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
92 ms |
2792 KB |
Output is correct |
4 |
Correct |
63 ms |
2648 KB |
Output is correct |
5 |
Correct |
58 ms |
2792 KB |
Output is correct |
6 |
Correct |
54 ms |
2648 KB |
Output is correct |
7 |
Correct |
57 ms |
2728 KB |
Output is correct |
8 |
Correct |
675 ms |
3208 KB |
Output is correct |
9 |
Correct |
703 ms |
5456 KB |
Output is correct |
10 |
Correct |
559 ms |
3152 KB |
Output is correct |
11 |
Correct |
682 ms |
3288 KB |
Output is correct |
12 |
Correct |
657 ms |
3296 KB |
Output is correct |
13 |
Correct |
431 ms |
2908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
2756 KB |
Output is correct |
2 |
Correct |
59 ms |
2724 KB |
Output is correct |
3 |
Correct |
56 ms |
2756 KB |
Output is correct |
4 |
Correct |
47 ms |
2648 KB |
Output is correct |
5 |
Correct |
75 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
56 ms |
2744 KB |
Output is correct |
8 |
Correct |
52 ms |
2760 KB |
Output is correct |
9 |
Correct |
50 ms |
2740 KB |
Output is correct |
10 |
Correct |
52 ms |
2652 KB |
Output is correct |
11 |
Correct |
66 ms |
2648 KB |
Output is correct |
12 |
Correct |
58 ms |
2652 KB |
Output is correct |
13 |
Correct |
57 ms |
2900 KB |
Output is correct |
14 |
Correct |
55 ms |
2652 KB |
Output is correct |
15 |
Correct |
63 ms |
2660 KB |
Output is correct |
16 |
Correct |
53 ms |
2648 KB |
Output is correct |
17 |
Correct |
675 ms |
3208 KB |
Output is correct |
18 |
Correct |
703 ms |
5456 KB |
Output is correct |
19 |
Correct |
559 ms |
3152 KB |
Output is correct |
20 |
Correct |
682 ms |
3288 KB |
Output is correct |
21 |
Correct |
657 ms |
3296 KB |
Output is correct |
22 |
Correct |
431 ms |
2908 KB |
Output is correct |
23 |
Correct |
89 ms |
2772 KB |
Output is correct |
24 |
Correct |
1 ms |
2396 KB |
Output is correct |
25 |
Correct |
92 ms |
2792 KB |
Output is correct |
26 |
Correct |
63 ms |
2648 KB |
Output is correct |
27 |
Correct |
58 ms |
2792 KB |
Output is correct |
28 |
Correct |
54 ms |
2648 KB |
Output is correct |
29 |
Correct |
57 ms |
2728 KB |
Output is correct |
30 |
Correct |
474 ms |
4920 KB |
Output is correct |
31 |
Correct |
446 ms |
3028 KB |
Output is correct |
32 |
Correct |
468 ms |
3156 KB |
Output is correct |
33 |
Correct |
51 ms |
2652 KB |
Output is correct |
34 |
Correct |
52 ms |
2904 KB |
Output is correct |
35 |
Correct |
52 ms |
2648 KB |
Output is correct |
36 |
Correct |
58 ms |
2652 KB |
Output is correct |
37 |
Correct |
1 ms |
2396 KB |
Output is correct |
38 |
Correct |
61 ms |
2652 KB |
Output is correct |
39 |
Correct |
51 ms |
2652 KB |
Output is correct |
40 |
Correct |
52 ms |
2716 KB |
Output is correct |
41 |
Correct |
1 ms |
2392 KB |
Output is correct |
42 |
Correct |
51 ms |
2648 KB |
Output is correct |
43 |
Correct |
428 ms |
3032 KB |
Output is correct |
44 |
Correct |
412 ms |
3160 KB |
Output is correct |
45 |
Correct |
433 ms |
3932 KB |
Output is correct |
46 |
Correct |
402 ms |
2908 KB |
Output is correct |
47 |
Correct |
403 ms |
3164 KB |
Output is correct |
48 |
Correct |
434 ms |
3160 KB |
Output is correct |
49 |
Correct |
551 ms |
5612 KB |
Output is correct |
50 |
Correct |
1 ms |
2396 KB |
Output is correct |
51 |
Correct |
1 ms |
2396 KB |
Output is correct |
52 |
Correct |
406 ms |
3020 KB |
Output is correct |
53 |
Correct |
389 ms |
3124 KB |
Output is correct |
54 |
Correct |
410 ms |
3072 KB |
Output is correct |
55 |
Correct |
401 ms |
3036 KB |
Output is correct |
56 |
Correct |
386 ms |
3020 KB |
Output is correct |
57 |
Correct |
1 ms |
2392 KB |
Output is correct |
58 |
Correct |
63 ms |
2652 KB |
Output is correct |
59 |
Correct |
57 ms |
2652 KB |
Output is correct |
60 |
Correct |
54 ms |
2652 KB |
Output is correct |
61 |
Correct |
456 ms |
5752 KB |
Output is correct |
62 |
Correct |
458 ms |
5708 KB |
Output is correct |
63 |
Correct |
1 ms |
2396 KB |
Output is correct |