#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define il pair<int,ll>
#define li pair<ll,int>
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define plli pair<pll,ll>
#define vv vector
using namespace std;
const ld INF = 1e18;
const int MAXN = 100 + 10;
const int MAXK = 1000 + 10;
vv<ll> B[MAXN];
vv<ll> S[MAXN];
ll mat[MAXN][MAXN];
ll dist1[MAXN][MAXN];
ll profit[MAXN][MAXN];
int n,m,k;
void precomp(){
FOR(i,n)FOR(j,n)dist1[i][j] = mat[i][j];
FOR(conn,n){
FOR(i,n){
FOR(j,n){
if(dist1[i][conn] + dist1[conn][j] < dist1[i][j]){
dist1[i][j] = dist1[i][conn] + dist1[conn][j];
}
}
}
}
FOR(i,n){
FOR(j,n){
FOR(item,k){
if(B[i][item] == -1 or S[j][item] == -1)continue;
profit[i][j] = max(profit[i][j] , S[j][item] - B[i][item]);
}
}
}
}
ld route[MAXN][MAXN];
bool isPoss(ld x){
FOR(i,n){
FOR(j,n){
if(i == j) route[i][j] = -INF;
else route[i][j] = profit[i][j] - x*dist1[i][j];
}
}
FOR(conn,n){
FOR(i,n){
FOR(j,n){
if(route[i][conn] + route[conn][j] > route[i][j]){
route[i][j] = route[i][conn] + route[conn][j];
}
}
}
}
FOR(i,n)if(route[i][i] >= 0)return 1;
return 0;
}
int main(){
cin >> n >> m >> k;
FOR(i,n){
FOR(j,k){
int a,b;
cin >> a >> b;
B[i].pb(a);
S[i].pb(b);
}
}
FOR(i,n)FOR(j,n)mat[i][j] = INF;
FOR(i,m){
int a,b,c;
cin >> a >> b >> c;
a--;b--;
mat[a][b] = c;
}
precomp();
//cout << isPoss(2) << endl;
FOR(i,n){
FOR(j,n){
//cout << dist1[i][j] << " ";
}
//cout << endl;
}
ld lo = 0;
ld hi = INF;
ld eps = 0.0001;
ld best = 0;
while(hi-lo > eps){
ld mid = (hi + lo)/2;
//cout << setprecision(10) << hi << " " << mid << " " << lo << endl;
if(isPoss(mid)){
best = max(best,mid);
lo = mid;
}else{
hi = mid;
}
}
if(isPoss((ll)hi))best = max(best,(ld)((ll)hi));
cout << (ll)best << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
441 ms |
3620 KB |
Output is correct |
2 |
Correct |
329 ms |
732 KB |
Output is correct |
3 |
Correct |
324 ms |
860 KB |
Output is correct |
4 |
Correct |
39 ms |
504 KB |
Output is correct |
5 |
Correct |
40 ms |
504 KB |
Output is correct |
6 |
Correct |
38 ms |
508 KB |
Output is correct |
7 |
Correct |
46 ms |
632 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
45 ms |
560 KB |
Output is correct |
10 |
Correct |
45 ms |
504 KB |
Output is correct |
11 |
Correct |
41 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
43 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
632 KB |
Output is correct |
2 |
Correct |
43 ms |
764 KB |
Output is correct |
3 |
Correct |
41 ms |
656 KB |
Output is correct |
4 |
Correct |
38 ms |
632 KB |
Output is correct |
5 |
Correct |
69 ms |
760 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
39 ms |
504 KB |
Output is correct |
8 |
Correct |
43 ms |
760 KB |
Output is correct |
9 |
Correct |
41 ms |
648 KB |
Output is correct |
10 |
Correct |
43 ms |
632 KB |
Output is correct |
11 |
Correct |
51 ms |
632 KB |
Output is correct |
12 |
Correct |
50 ms |
632 KB |
Output is correct |
13 |
Correct |
41 ms |
648 KB |
Output is correct |
14 |
Correct |
48 ms |
760 KB |
Output is correct |
15 |
Correct |
50 ms |
632 KB |
Output is correct |
16 |
Correct |
40 ms |
632 KB |
Output is correct |
17 |
Correct |
84 ms |
760 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
84 ms |
696 KB |
Output is correct |
20 |
Correct |
55 ms |
696 KB |
Output is correct |
21 |
Correct |
52 ms |
632 KB |
Output is correct |
22 |
Correct |
43 ms |
632 KB |
Output is correct |
23 |
Correct |
46 ms |
504 KB |
Output is correct |
24 |
Correct |
38 ms |
508 KB |
Output is correct |
25 |
Correct |
46 ms |
632 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
45 ms |
560 KB |
Output is correct |
28 |
Correct |
45 ms |
504 KB |
Output is correct |
29 |
Correct |
41 ms |
604 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
43 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
621 ms |
1144 KB |
Output is correct |
2 |
Correct |
784 ms |
4188 KB |
Output is correct |
3 |
Correct |
475 ms |
1016 KB |
Output is correct |
4 |
Correct |
659 ms |
1272 KB |
Output is correct |
5 |
Correct |
618 ms |
1224 KB |
Output is correct |
6 |
Correct |
353 ms |
1016 KB |
Output is correct |
7 |
Correct |
84 ms |
760 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
84 ms |
696 KB |
Output is correct |
10 |
Correct |
55 ms |
696 KB |
Output is correct |
11 |
Correct |
52 ms |
632 KB |
Output is correct |
12 |
Correct |
43 ms |
632 KB |
Output is correct |
13 |
Correct |
46 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
632 KB |
Output is correct |
2 |
Correct |
43 ms |
764 KB |
Output is correct |
3 |
Correct |
41 ms |
656 KB |
Output is correct |
4 |
Correct |
38 ms |
632 KB |
Output is correct |
5 |
Correct |
69 ms |
760 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
39 ms |
504 KB |
Output is correct |
8 |
Correct |
43 ms |
760 KB |
Output is correct |
9 |
Correct |
41 ms |
648 KB |
Output is correct |
10 |
Correct |
43 ms |
632 KB |
Output is correct |
11 |
Correct |
51 ms |
632 KB |
Output is correct |
12 |
Correct |
50 ms |
632 KB |
Output is correct |
13 |
Correct |
41 ms |
648 KB |
Output is correct |
14 |
Correct |
48 ms |
760 KB |
Output is correct |
15 |
Correct |
50 ms |
632 KB |
Output is correct |
16 |
Correct |
40 ms |
632 KB |
Output is correct |
17 |
Correct |
621 ms |
1144 KB |
Output is correct |
18 |
Correct |
784 ms |
4188 KB |
Output is correct |
19 |
Correct |
475 ms |
1016 KB |
Output is correct |
20 |
Correct |
659 ms |
1272 KB |
Output is correct |
21 |
Correct |
618 ms |
1224 KB |
Output is correct |
22 |
Correct |
353 ms |
1016 KB |
Output is correct |
23 |
Correct |
84 ms |
760 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
84 ms |
696 KB |
Output is correct |
26 |
Correct |
55 ms |
696 KB |
Output is correct |
27 |
Correct |
52 ms |
632 KB |
Output is correct |
28 |
Correct |
43 ms |
632 KB |
Output is correct |
29 |
Correct |
46 ms |
504 KB |
Output is correct |
30 |
Correct |
318 ms |
888 KB |
Output is correct |
31 |
Correct |
324 ms |
1016 KB |
Output is correct |
32 |
Correct |
376 ms |
2936 KB |
Output is correct |
33 |
Correct |
290 ms |
1016 KB |
Output is correct |
34 |
Correct |
330 ms |
1096 KB |
Output is correct |
35 |
Correct |
294 ms |
1144 KB |
Output is correct |
36 |
Correct |
618 ms |
4368 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
2 ms |
376 KB |
Output is correct |
39 |
Correct |
286 ms |
760 KB |
Output is correct |
40 |
Correct |
276 ms |
968 KB |
Output is correct |
41 |
Correct |
311 ms |
888 KB |
Output is correct |
42 |
Correct |
282 ms |
888 KB |
Output is correct |
43 |
Correct |
275 ms |
888 KB |
Output is correct |
44 |
Correct |
2 ms |
376 KB |
Output is correct |
45 |
Correct |
56 ms |
760 KB |
Output is correct |
46 |
Correct |
56 ms |
792 KB |
Output is correct |
47 |
Correct |
56 ms |
760 KB |
Output is correct |
48 |
Correct |
531 ms |
4572 KB |
Output is correct |
49 |
Correct |
540 ms |
4584 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
441 ms |
3620 KB |
Output is correct |
52 |
Correct |
329 ms |
732 KB |
Output is correct |
53 |
Correct |
324 ms |
860 KB |
Output is correct |
54 |
Correct |
39 ms |
504 KB |
Output is correct |
55 |
Correct |
40 ms |
504 KB |
Output is correct |
56 |
Correct |
38 ms |
508 KB |
Output is correct |
57 |
Correct |
46 ms |
632 KB |
Output is correct |
58 |
Correct |
2 ms |
376 KB |
Output is correct |
59 |
Correct |
45 ms |
560 KB |
Output is correct |
60 |
Correct |
45 ms |
504 KB |
Output is correct |
61 |
Correct |
41 ms |
604 KB |
Output is correct |
62 |
Correct |
2 ms |
376 KB |
Output is correct |
63 |
Correct |
43 ms |
632 KB |
Output is correct |