#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 4000000000000000000ll
#define M 10000002
#define N 105
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
int n,m,k,x,y,z;
int b[N][N*10],s[N][N*10];
ll p[N][N],d1[N][N],d2[N][N];
bool neg(int pro) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(d1[i][j]==inf) d2[i][j]=inf;
else d2[i][j]=1ll*d1[i][j]*pro-p[i][j];
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
umin(d2[j][k],d2[j][i]+d2[i][k]);
}
}
}
for(int i=1;i<=n;i++) {
if(d2[i][i]<=0) return true;
}
return false;
}
int main() {
#if 0
freopen("input.txt","r",stdin);
#endif
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++) {
for(int j=1;j<=k;j++) {
scanf("%d %d",&b[i][j],&s[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
d1[i][j]=inf;
}
}
for(int i=1;i<=m;i++) {
scanf("%d %d %d",&x,&y,&z);
umin(d1[x][y],1ll*z);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
umin(d1[j][k],d1[j][i]+d1[i][k]);
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int g=1;g<=k;g++) {
if(~s[j][g] && ~b[i][g]) {
umax(p[i][j],1ll*s[j][g]-b[i][g]);
}
}
}
}
/*for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%d ",p[i][j]);
printf("\n\n\n\n");
for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%lld ",d1[i][j]);*/
int bas=1,son=1e9;
while(bas<=son) {
if(neg(orta)) bas=orta+1;
else son=orta-1;
}
printf("%d",son);
//printf("%lld",LONG_LONG_MAX);
}
Compilation message
merchant.cpp: In function 'int main()':
merchant.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&m,&k);
~~~~~^~~~~~~~~~~~~~~~~~~~~
merchant.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&b[i][j],&s[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
1272 KB |
Output is correct |
2 |
Correct |
46 ms |
1384 KB |
Output is correct |
3 |
Correct |
54 ms |
1588 KB |
Output is correct |
4 |
Correct |
8 ms |
1588 KB |
Output is correct |
5 |
Correct |
9 ms |
1588 KB |
Output is correct |
6 |
Correct |
9 ms |
1588 KB |
Output is correct |
7 |
Correct |
9 ms |
1588 KB |
Output is correct |
8 |
Correct |
2 ms |
1588 KB |
Output is correct |
9 |
Correct |
8 ms |
1588 KB |
Output is correct |
10 |
Correct |
8 ms |
1588 KB |
Output is correct |
11 |
Correct |
9 ms |
1588 KB |
Output is correct |
12 |
Correct |
2 ms |
1588 KB |
Output is correct |
13 |
Correct |
9 ms |
1588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1588 KB |
Output is correct |
2 |
Correct |
7 ms |
1588 KB |
Output is correct |
3 |
Correct |
13 ms |
1588 KB |
Output is correct |
4 |
Correct |
8 ms |
1588 KB |
Output is correct |
5 |
Correct |
9 ms |
1588 KB |
Output is correct |
6 |
Correct |
2 ms |
1588 KB |
Output is correct |
7 |
Correct |
8 ms |
1588 KB |
Output is correct |
8 |
Correct |
8 ms |
1588 KB |
Output is correct |
9 |
Correct |
8 ms |
1588 KB |
Output is correct |
10 |
Correct |
8 ms |
1588 KB |
Output is correct |
11 |
Correct |
9 ms |
1588 KB |
Output is correct |
12 |
Correct |
9 ms |
1588 KB |
Output is correct |
13 |
Correct |
9 ms |
1588 KB |
Output is correct |
14 |
Correct |
12 ms |
1588 KB |
Output is correct |
15 |
Correct |
12 ms |
1588 KB |
Output is correct |
16 |
Correct |
9 ms |
1588 KB |
Output is correct |
17 |
Correct |
11 ms |
1588 KB |
Output is correct |
18 |
Correct |
2 ms |
1588 KB |
Output is correct |
19 |
Correct |
14 ms |
1588 KB |
Output is correct |
20 |
Correct |
10 ms |
1588 KB |
Output is correct |
21 |
Correct |
9 ms |
1588 KB |
Output is correct |
22 |
Correct |
10 ms |
1588 KB |
Output is correct |
23 |
Correct |
9 ms |
1588 KB |
Output is correct |
24 |
Correct |
9 ms |
1588 KB |
Output is correct |
25 |
Correct |
9 ms |
1588 KB |
Output is correct |
26 |
Correct |
2 ms |
1588 KB |
Output is correct |
27 |
Correct |
8 ms |
1588 KB |
Output is correct |
28 |
Correct |
8 ms |
1588 KB |
Output is correct |
29 |
Correct |
9 ms |
1588 KB |
Output is correct |
30 |
Correct |
2 ms |
1588 KB |
Output is correct |
31 |
Correct |
9 ms |
1588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
1660 KB |
Output is correct |
2 |
Correct |
107 ms |
1708 KB |
Output is correct |
3 |
Correct |
46 ms |
1788 KB |
Output is correct |
4 |
Correct |
54 ms |
1788 KB |
Output is correct |
5 |
Correct |
49 ms |
1788 KB |
Output is correct |
6 |
Correct |
45 ms |
1788 KB |
Output is correct |
7 |
Correct |
11 ms |
1588 KB |
Output is correct |
8 |
Correct |
2 ms |
1588 KB |
Output is correct |
9 |
Correct |
14 ms |
1588 KB |
Output is correct |
10 |
Correct |
10 ms |
1588 KB |
Output is correct |
11 |
Correct |
9 ms |
1588 KB |
Output is correct |
12 |
Correct |
10 ms |
1588 KB |
Output is correct |
13 |
Correct |
9 ms |
1588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1588 KB |
Output is correct |
2 |
Correct |
7 ms |
1588 KB |
Output is correct |
3 |
Correct |
13 ms |
1588 KB |
Output is correct |
4 |
Correct |
8 ms |
1588 KB |
Output is correct |
5 |
Correct |
9 ms |
1588 KB |
Output is correct |
6 |
Correct |
2 ms |
1588 KB |
Output is correct |
7 |
Correct |
8 ms |
1588 KB |
Output is correct |
8 |
Correct |
8 ms |
1588 KB |
Output is correct |
9 |
Correct |
8 ms |
1588 KB |
Output is correct |
10 |
Correct |
8 ms |
1588 KB |
Output is correct |
11 |
Correct |
9 ms |
1588 KB |
Output is correct |
12 |
Correct |
9 ms |
1588 KB |
Output is correct |
13 |
Correct |
9 ms |
1588 KB |
Output is correct |
14 |
Correct |
12 ms |
1588 KB |
Output is correct |
15 |
Correct |
12 ms |
1588 KB |
Output is correct |
16 |
Correct |
9 ms |
1588 KB |
Output is correct |
17 |
Correct |
49 ms |
1660 KB |
Output is correct |
18 |
Correct |
107 ms |
1708 KB |
Output is correct |
19 |
Correct |
46 ms |
1788 KB |
Output is correct |
20 |
Correct |
54 ms |
1788 KB |
Output is correct |
21 |
Correct |
49 ms |
1788 KB |
Output is correct |
22 |
Correct |
45 ms |
1788 KB |
Output is correct |
23 |
Correct |
11 ms |
1588 KB |
Output is correct |
24 |
Correct |
2 ms |
1588 KB |
Output is correct |
25 |
Correct |
14 ms |
1588 KB |
Output is correct |
26 |
Correct |
10 ms |
1588 KB |
Output is correct |
27 |
Correct |
9 ms |
1588 KB |
Output is correct |
28 |
Correct |
10 ms |
1588 KB |
Output is correct |
29 |
Correct |
9 ms |
1588 KB |
Output is correct |
30 |
Correct |
58 ms |
1788 KB |
Output is correct |
31 |
Correct |
45 ms |
1788 KB |
Output is correct |
32 |
Correct |
66 ms |
1788 KB |
Output is correct |
33 |
Correct |
45 ms |
1788 KB |
Output is correct |
34 |
Correct |
48 ms |
1788 KB |
Output is correct |
35 |
Correct |
47 ms |
1788 KB |
Output is correct |
36 |
Correct |
119 ms |
1788 KB |
Output is correct |
37 |
Correct |
2 ms |
1788 KB |
Output is correct |
38 |
Correct |
2 ms |
1788 KB |
Output is correct |
39 |
Correct |
48 ms |
1788 KB |
Output is correct |
40 |
Correct |
53 ms |
1788 KB |
Output is correct |
41 |
Correct |
52 ms |
1788 KB |
Output is correct |
42 |
Correct |
51 ms |
1788 KB |
Output is correct |
43 |
Correct |
49 ms |
1788 KB |
Output is correct |
44 |
Correct |
2 ms |
1788 KB |
Output is correct |
45 |
Correct |
10 ms |
1788 KB |
Output is correct |
46 |
Correct |
10 ms |
1788 KB |
Output is correct |
47 |
Correct |
10 ms |
1788 KB |
Output is correct |
48 |
Correct |
116 ms |
1788 KB |
Output is correct |
49 |
Correct |
117 ms |
1788 KB |
Output is correct |
50 |
Correct |
3 ms |
1788 KB |
Output is correct |
51 |
Correct |
85 ms |
1272 KB |
Output is correct |
52 |
Correct |
46 ms |
1384 KB |
Output is correct |
53 |
Correct |
54 ms |
1588 KB |
Output is correct |
54 |
Correct |
8 ms |
1588 KB |
Output is correct |
55 |
Correct |
9 ms |
1588 KB |
Output is correct |
56 |
Correct |
9 ms |
1588 KB |
Output is correct |
57 |
Correct |
9 ms |
1588 KB |
Output is correct |
58 |
Correct |
2 ms |
1588 KB |
Output is correct |
59 |
Correct |
8 ms |
1588 KB |
Output is correct |
60 |
Correct |
8 ms |
1588 KB |
Output is correct |
61 |
Correct |
9 ms |
1588 KB |
Output is correct |
62 |
Correct |
2 ms |
1588 KB |
Output is correct |
63 |
Correct |
9 ms |
1588 KB |
Output is correct |