#include <bits/stdc++.h>
#define int long long
template<typename T> void domax(T &a, T b) { if (b > a) a = b; }
template<typename T> void domin(T &a, T b) { if (b < a) a = b; }
using namespace std;
const long long inf = 3e18, MaxT = 10ll*1000*1000;
const int MaxN = 105, MaxK = 1005;
int n, m, K;
long long b[MaxN][MaxK], s[MaxN][MaxK], dist[MaxN][MaxN], best[MaxN][MaxN], cost[MaxN][MaxN];
bool can(long long eff) {
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cost[i][j]=-3e18;
if(dist[i][j]==3e18) continue;
cost[i][j]=best[i][j]-dist[i][j]*eff;
}
}
for (int m = 0; m < n; m++) {
for (int s = 0; s < n; s++) {
for (int e = 0; e < n; e++) {
cost[s][e]=max(cost[s][e],cost[s][m]+cost[m][e]);
if (cost[s][e] >inf) {
cost[s][e] = inf;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cost[i][j] + cost[j][i] >= 0) {
return true;
}
}
}
return false;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>K;
for (int i = 0; i < n; i++) {
for (int k = 0; k < K; k++) {
cin>>b[i][k]>>s[i][k];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++) dist[i][j]=3e18;
}
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
u--;
v--;
dist[u][v]=w;
}
for(int u=0;u<n;u++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int val=dist[i][u]+dist[u][j];
dist[i][j]=min(dist[i][j],val);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
best[i][j] = 0; // carrying no item
for (int k = 0; k < K; k++) {
if(b[i][k]==-1||s[j][k]==-1) continue;
best[i][j]=max(best[i][j],s[j][k] - b[i][k]);
}
}
}
long long lo = 1ll, hi = 1000ll * 1000 * 1000;
long long ans = 0ll;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
if (can(mid)) {
lo = mid + 1;
ans = mid;
} else {
hi = mid - 1;
}
}
assert(!can(ans+1));
printf("%lld\n", ans);
}
Compilation message
merchant.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main()
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
2168 KB |
Output is correct |
2 |
Correct |
51 ms |
1408 KB |
Output is correct |
3 |
Correct |
52 ms |
1408 KB |
Output is correct |
4 |
Correct |
8 ms |
896 KB |
Output is correct |
5 |
Correct |
8 ms |
896 KB |
Output is correct |
6 |
Correct |
8 ms |
1024 KB |
Output is correct |
7 |
Correct |
8 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
8 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
896 KB |
Output is correct |
11 |
Correct |
8 ms |
896 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
8 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
896 KB |
Output is correct |
2 |
Correct |
8 ms |
896 KB |
Output is correct |
3 |
Correct |
8 ms |
928 KB |
Output is correct |
4 |
Correct |
7 ms |
896 KB |
Output is correct |
5 |
Correct |
9 ms |
896 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
8 ms |
896 KB |
Output is correct |
8 |
Correct |
8 ms |
896 KB |
Output is correct |
9 |
Correct |
8 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
896 KB |
Output is correct |
11 |
Correct |
9 ms |
896 KB |
Output is correct |
12 |
Correct |
9 ms |
896 KB |
Output is correct |
13 |
Correct |
11 ms |
896 KB |
Output is correct |
14 |
Correct |
8 ms |
944 KB |
Output is correct |
15 |
Correct |
9 ms |
896 KB |
Output is correct |
16 |
Correct |
8 ms |
896 KB |
Output is correct |
17 |
Correct |
10 ms |
896 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
9 ms |
896 KB |
Output is correct |
20 |
Correct |
9 ms |
896 KB |
Output is correct |
21 |
Correct |
9 ms |
896 KB |
Output is correct |
22 |
Correct |
8 ms |
896 KB |
Output is correct |
23 |
Correct |
8 ms |
896 KB |
Output is correct |
24 |
Correct |
8 ms |
1024 KB |
Output is correct |
25 |
Correct |
8 ms |
896 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
8 ms |
896 KB |
Output is correct |
28 |
Correct |
8 ms |
896 KB |
Output is correct |
29 |
Correct |
8 ms |
896 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
8 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
1536 KB |
Output is correct |
2 |
Correct |
110 ms |
2168 KB |
Output is correct |
3 |
Correct |
55 ms |
1408 KB |
Output is correct |
4 |
Correct |
61 ms |
1536 KB |
Output is correct |
5 |
Correct |
58 ms |
1664 KB |
Output is correct |
6 |
Correct |
54 ms |
1408 KB |
Output is correct |
7 |
Correct |
10 ms |
896 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
9 ms |
896 KB |
Output is correct |
10 |
Correct |
9 ms |
896 KB |
Output is correct |
11 |
Correct |
9 ms |
896 KB |
Output is correct |
12 |
Correct |
8 ms |
896 KB |
Output is correct |
13 |
Correct |
8 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
896 KB |
Output is correct |
2 |
Correct |
8 ms |
896 KB |
Output is correct |
3 |
Correct |
8 ms |
928 KB |
Output is correct |
4 |
Correct |
7 ms |
896 KB |
Output is correct |
5 |
Correct |
9 ms |
896 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
8 ms |
896 KB |
Output is correct |
8 |
Correct |
8 ms |
896 KB |
Output is correct |
9 |
Correct |
8 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
896 KB |
Output is correct |
11 |
Correct |
9 ms |
896 KB |
Output is correct |
12 |
Correct |
9 ms |
896 KB |
Output is correct |
13 |
Correct |
11 ms |
896 KB |
Output is correct |
14 |
Correct |
8 ms |
944 KB |
Output is correct |
15 |
Correct |
9 ms |
896 KB |
Output is correct |
16 |
Correct |
8 ms |
896 KB |
Output is correct |
17 |
Correct |
59 ms |
1536 KB |
Output is correct |
18 |
Correct |
110 ms |
2168 KB |
Output is correct |
19 |
Correct |
55 ms |
1408 KB |
Output is correct |
20 |
Correct |
61 ms |
1536 KB |
Output is correct |
21 |
Correct |
58 ms |
1664 KB |
Output is correct |
22 |
Correct |
54 ms |
1408 KB |
Output is correct |
23 |
Correct |
10 ms |
896 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
9 ms |
896 KB |
Output is correct |
26 |
Correct |
9 ms |
896 KB |
Output is correct |
27 |
Correct |
9 ms |
896 KB |
Output is correct |
28 |
Correct |
8 ms |
896 KB |
Output is correct |
29 |
Correct |
8 ms |
896 KB |
Output is correct |
30 |
Correct |
53 ms |
1476 KB |
Output is correct |
31 |
Correct |
57 ms |
1536 KB |
Output is correct |
32 |
Correct |
73 ms |
2176 KB |
Output is correct |
33 |
Correct |
54 ms |
1536 KB |
Output is correct |
34 |
Correct |
55 ms |
1664 KB |
Output is correct |
35 |
Correct |
55 ms |
1620 KB |
Output is correct |
36 |
Correct |
111 ms |
2296 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
53 ms |
1528 KB |
Output is correct |
40 |
Correct |
55 ms |
1408 KB |
Output is correct |
41 |
Correct |
53 ms |
1408 KB |
Output is correct |
42 |
Correct |
54 ms |
1408 KB |
Output is correct |
43 |
Correct |
55 ms |
1408 KB |
Output is correct |
44 |
Correct |
1 ms |
512 KB |
Output is correct |
45 |
Correct |
10 ms |
896 KB |
Output is correct |
46 |
Correct |
10 ms |
896 KB |
Output is correct |
47 |
Correct |
11 ms |
896 KB |
Output is correct |
48 |
Correct |
115 ms |
2168 KB |
Output is correct |
49 |
Correct |
118 ms |
2296 KB |
Output is correct |
50 |
Correct |
1 ms |
384 KB |
Output is correct |
51 |
Correct |
79 ms |
2168 KB |
Output is correct |
52 |
Correct |
51 ms |
1408 KB |
Output is correct |
53 |
Correct |
52 ms |
1408 KB |
Output is correct |
54 |
Correct |
8 ms |
896 KB |
Output is correct |
55 |
Correct |
8 ms |
896 KB |
Output is correct |
56 |
Correct |
8 ms |
1024 KB |
Output is correct |
57 |
Correct |
8 ms |
896 KB |
Output is correct |
58 |
Correct |
1 ms |
384 KB |
Output is correct |
59 |
Correct |
8 ms |
896 KB |
Output is correct |
60 |
Correct |
8 ms |
896 KB |
Output is correct |
61 |
Correct |
8 ms |
896 KB |
Output is correct |
62 |
Correct |
1 ms |
384 KB |
Output is correct |
63 |
Correct |
8 ms |
896 KB |
Output is correct |