#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
int n,m,k;
int buy[101][1001],sell[101][1001];
vector <pii> g[101];
int p[101][101],d[101][101],nw[101][101];
signed main(){
cin>>n>>m>>k;
for (int i=1; i<=n; i++){
for (int j=1; j<=k; j++) cin>>buy[i][j]>>sell[i][j];
}
for (int i=0; i<m; i++){
int u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
}
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
p[i][j]=0;
for (int l=1; l<=k; l++){
if (buy[i][l]!=-1&&sell[j][l]!=-1) p[i][j]=max(p[i][j],-buy[i][l]+sell[j][l]);
}
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++) d[i][j]=1e18;
d[i][i]=0;
}
for (int i=1; i<=n; i++){
for (auto j:g[i]) d[i][j.x]=min(d[i][j.x],j.y);
}
for (int l=1; l<=n; l++){
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++) d[i][j]=min(d[i][j],d[i][l]+d[l][j]);
}
}
int l=0,r=2e9;
while (l<r){
int mid=(l+r+1)/2;
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
if (i==j) nw[i][j]=-1e13;
else if (d[i][j]!=1e18) nw[i][j]=p[i][j]-mid*d[i][j];
else nw[i][j]=-1e13;
}
}
for (int l=1; l<=n; l++){
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++) nw[i][j]=max(nw[i][j],nw[i][l]+nw[l][j]);
}
}
bool found=0;
for (int i=1; i<=n; i++){
if (nw[i][i]>=0) found=1;
}
if (found) l=mid;
else r=mid-1;
}
cout<<l<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
119 ms |
3364 KB |
Output is correct |
2 |
Correct |
36 ms |
1236 KB |
Output is correct |
3 |
Correct |
39 ms |
1332 KB |
Output is correct |
4 |
Correct |
6 ms |
852 KB |
Output is correct |
5 |
Correct |
6 ms |
852 KB |
Output is correct |
6 |
Correct |
6 ms |
832 KB |
Output is correct |
7 |
Correct |
7 ms |
836 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
5 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
852 KB |
Output is correct |
11 |
Correct |
6 ms |
852 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
7 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
832 KB |
Output is correct |
2 |
Correct |
7 ms |
836 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
5 ms |
724 KB |
Output is correct |
5 |
Correct |
6 ms |
852 KB |
Output is correct |
6 |
Correct |
6 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
7 ms |
852 KB |
Output is correct |
9 |
Correct |
8 ms |
868 KB |
Output is correct |
10 |
Correct |
5 ms |
832 KB |
Output is correct |
11 |
Correct |
7 ms |
852 KB |
Output is correct |
12 |
Correct |
6 ms |
836 KB |
Output is correct |
13 |
Correct |
7 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
5 ms |
852 KB |
Output is correct |
16 |
Correct |
6 ms |
840 KB |
Output is correct |
17 |
Correct |
6 ms |
852 KB |
Output is correct |
18 |
Correct |
7 ms |
840 KB |
Output is correct |
19 |
Correct |
7 ms |
928 KB |
Output is correct |
20 |
Correct |
7 ms |
852 KB |
Output is correct |
21 |
Correct |
7 ms |
852 KB |
Output is correct |
22 |
Correct |
9 ms |
852 KB |
Output is correct |
23 |
Correct |
10 ms |
1000 KB |
Output is correct |
24 |
Correct |
6 ms |
852 KB |
Output is correct |
25 |
Correct |
7 ms |
852 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
9 ms |
932 KB |
Output is correct |
28 |
Correct |
8 ms |
852 KB |
Output is correct |
29 |
Correct |
8 ms |
836 KB |
Output is correct |
30 |
Correct |
7 ms |
852 KB |
Output is correct |
31 |
Correct |
6 ms |
828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
852 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
9 ms |
932 KB |
Output is correct |
4 |
Correct |
8 ms |
852 KB |
Output is correct |
5 |
Correct |
8 ms |
836 KB |
Output is correct |
6 |
Correct |
7 ms |
852 KB |
Output is correct |
7 |
Correct |
6 ms |
828 KB |
Output is correct |
8 |
Correct |
44 ms |
1548 KB |
Output is correct |
9 |
Correct |
130 ms |
3764 KB |
Output is correct |
10 |
Correct |
39 ms |
1480 KB |
Output is correct |
11 |
Correct |
45 ms |
1832 KB |
Output is correct |
12 |
Correct |
45 ms |
1708 KB |
Output is correct |
13 |
Correct |
41 ms |
1496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
868 KB |
Output is correct |
2 |
Correct |
5 ms |
832 KB |
Output is correct |
3 |
Correct |
7 ms |
852 KB |
Output is correct |
4 |
Correct |
6 ms |
836 KB |
Output is correct |
5 |
Correct |
7 ms |
852 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
5 ms |
852 KB |
Output is correct |
8 |
Correct |
6 ms |
840 KB |
Output is correct |
9 |
Correct |
6 ms |
852 KB |
Output is correct |
10 |
Correct |
7 ms |
840 KB |
Output is correct |
11 |
Correct |
7 ms |
928 KB |
Output is correct |
12 |
Correct |
7 ms |
852 KB |
Output is correct |
13 |
Correct |
7 ms |
852 KB |
Output is correct |
14 |
Correct |
9 ms |
852 KB |
Output is correct |
15 |
Correct |
10 ms |
1000 KB |
Output is correct |
16 |
Correct |
6 ms |
852 KB |
Output is correct |
17 |
Correct |
44 ms |
1548 KB |
Output is correct |
18 |
Correct |
130 ms |
3764 KB |
Output is correct |
19 |
Correct |
39 ms |
1480 KB |
Output is correct |
20 |
Correct |
45 ms |
1832 KB |
Output is correct |
21 |
Correct |
45 ms |
1708 KB |
Output is correct |
22 |
Correct |
41 ms |
1496 KB |
Output is correct |
23 |
Correct |
7 ms |
852 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
9 ms |
932 KB |
Output is correct |
26 |
Correct |
8 ms |
852 KB |
Output is correct |
27 |
Correct |
8 ms |
836 KB |
Output is correct |
28 |
Correct |
7 ms |
852 KB |
Output is correct |
29 |
Correct |
6 ms |
828 KB |
Output is correct |
30 |
Correct |
119 ms |
3364 KB |
Output is correct |
31 |
Correct |
36 ms |
1236 KB |
Output is correct |
32 |
Correct |
39 ms |
1332 KB |
Output is correct |
33 |
Correct |
6 ms |
852 KB |
Output is correct |
34 |
Correct |
6 ms |
852 KB |
Output is correct |
35 |
Correct |
6 ms |
832 KB |
Output is correct |
36 |
Correct |
7 ms |
836 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
5 ms |
724 KB |
Output is correct |
39 |
Correct |
6 ms |
852 KB |
Output is correct |
40 |
Correct |
6 ms |
852 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
7 ms |
852 KB |
Output is correct |
43 |
Correct |
36 ms |
1320 KB |
Output is correct |
44 |
Correct |
42 ms |
1504 KB |
Output is correct |
45 |
Correct |
75 ms |
2504 KB |
Output is correct |
46 |
Correct |
39 ms |
1492 KB |
Output is correct |
47 |
Correct |
43 ms |
1608 KB |
Output is correct |
48 |
Correct |
42 ms |
1600 KB |
Output is correct |
49 |
Correct |
142 ms |
3952 KB |
Output is correct |
50 |
Correct |
1 ms |
312 KB |
Output is correct |
51 |
Correct |
1 ms |
340 KB |
Output is correct |
52 |
Correct |
40 ms |
1392 KB |
Output is correct |
53 |
Correct |
42 ms |
1668 KB |
Output is correct |
54 |
Correct |
37 ms |
1364 KB |
Output is correct |
55 |
Correct |
36 ms |
1404 KB |
Output is correct |
56 |
Correct |
35 ms |
1352 KB |
Output is correct |
57 |
Correct |
1 ms |
340 KB |
Output is correct |
58 |
Correct |
10 ms |
980 KB |
Output is correct |
59 |
Correct |
10 ms |
980 KB |
Output is correct |
60 |
Correct |
10 ms |
980 KB |
Output is correct |
61 |
Correct |
147 ms |
4376 KB |
Output is correct |
62 |
Correct |
152 ms |
4448 KB |
Output is correct |
63 |
Correct |
1 ms |
340 KB |
Output is correct |