# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
549775 | 2022-04-16T13:41:50 Z | Pherokung | Travelling Merchant (APIO17_merchant) | C++14 | 123 ms | 4228 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long ll n,m,k,b[1005][105],s[1005][105],u,v,w,dis[105][105],val[105][105],cost[105][105],INF = 3e18; bool valid(ll eff){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cost[i][j] = dis[i][j] < INF ? (ll)(dis[i][j] * eff) - val[i][j] : INF; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cost[i][j] = max(-INF,min(cost[i][j],cost[i][k] + cost[k][j])); for(int i=1;i<=n;i++) if(cost[i][i] <= 0) return true; return false; } int main(){ scanf("%lld%lld%lld",&n,&m,&k); for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ scanf("%lld%lld",&b[j][i],&s[j][i]); if(b[j][i] == -1) b[j][i] = INF; if(s[j][i] == -1) s[j][i] = -INF; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j] = INF; for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&u,&v,&w); dis[u][v] = w; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int t=1;t<=k;t++) val[i][j] = max(val[i][j], s[t][j] - b[t][i]); ll be = 1, ed = 1e9; while(be <= ed){ ll mid = (be+ed)/2; if(valid(mid)) be = mid+1; else ed = mid-1; } printf("%lld",ed); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 68 ms | 2172 KB | Output is correct |
2 | Correct | 37 ms | 568 KB | Output is correct |
3 | Correct | 38 ms | 468 KB | Output is correct |
4 | Correct | 5 ms | 340 KB | Output is correct |
5 | Correct | 6 ms | 340 KB | Output is correct |
6 | Correct | 6 ms | 340 KB | Output is correct |
7 | Correct | 7 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 5 ms | 340 KB | Output is correct |
10 | Correct | 6 ms | 468 KB | Output is correct |
11 | Correct | 6 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 6 ms | 520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 340 KB | Output is correct |
2 | Correct | 7 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 5 ms | 340 KB | Output is correct |
5 | Correct | 6 ms | 468 KB | Output is correct |
6 | Correct | 6 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 6 ms | 520 KB | Output is correct |
9 | Correct | 6 ms | 472 KB | Output is correct |
10 | Correct | 6 ms | 460 KB | Output is correct |
11 | Correct | 6 ms | 468 KB | Output is correct |
12 | Correct | 6 ms | 468 KB | Output is correct |
13 | Correct | 11 ms | 524 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 6 ms | 340 KB | Output is correct |
16 | Correct | 7 ms | 468 KB | Output is correct |
17 | Correct | 6 ms | 468 KB | Output is correct |
18 | Correct | 6 ms | 508 KB | Output is correct |
19 | Correct | 8 ms | 480 KB | Output is correct |
20 | Correct | 7 ms | 468 KB | Output is correct |
21 | Correct | 6 ms | 440 KB | Output is correct |
22 | Correct | 7 ms | 468 KB | Output is correct |
23 | Correct | 8 ms | 468 KB | Output is correct |
24 | Correct | 5 ms | 340 KB | Output is correct |
25 | Correct | 13 ms | 520 KB | Output is correct |
26 | Correct | 0 ms | 212 KB | Output is correct |
27 | Correct | 13 ms | 520 KB | Output is correct |
28 | Correct | 9 ms | 468 KB | Output is correct |
29 | Correct | 8 ms | 528 KB | Output is correct |
30 | Correct | 6 ms | 340 KB | Output is correct |
31 | Correct | 6 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 520 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 13 ms | 520 KB | Output is correct |
4 | Correct | 9 ms | 468 KB | Output is correct |
5 | Correct | 8 ms | 528 KB | Output is correct |
6 | Correct | 6 ms | 340 KB | Output is correct |
7 | Correct | 6 ms | 340 KB | Output is correct |
8 | Correct | 84 ms | 724 KB | Output is correct |
9 | Correct | 123 ms | 2020 KB | Output is correct |
10 | Correct | 71 ms | 596 KB | Output is correct |
11 | Correct | 93 ms | 724 KB | Output is correct |
12 | Correct | 86 ms | 596 KB | Output is correct |
13 | Correct | 48 ms | 616 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 472 KB | Output is correct |
2 | Correct | 6 ms | 460 KB | Output is correct |
3 | Correct | 6 ms | 468 KB | Output is correct |
4 | Correct | 6 ms | 468 KB | Output is correct |
5 | Correct | 11 ms | 524 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 6 ms | 340 KB | Output is correct |
8 | Correct | 7 ms | 468 KB | Output is correct |
9 | Correct | 6 ms | 468 KB | Output is correct |
10 | Correct | 6 ms | 508 KB | Output is correct |
11 | Correct | 8 ms | 480 KB | Output is correct |
12 | Correct | 7 ms | 468 KB | Output is correct |
13 | Correct | 6 ms | 440 KB | Output is correct |
14 | Correct | 7 ms | 468 KB | Output is correct |
15 | Correct | 8 ms | 468 KB | Output is correct |
16 | Correct | 5 ms | 340 KB | Output is correct |
17 | Correct | 84 ms | 724 KB | Output is correct |
18 | Correct | 123 ms | 2020 KB | Output is correct |
19 | Correct | 71 ms | 596 KB | Output is correct |
20 | Correct | 93 ms | 724 KB | Output is correct |
21 | Correct | 86 ms | 596 KB | Output is correct |
22 | Correct | 48 ms | 616 KB | Output is correct |
23 | Correct | 13 ms | 520 KB | Output is correct |
24 | Correct | 0 ms | 212 KB | Output is correct |
25 | Correct | 13 ms | 520 KB | Output is correct |
26 | Correct | 9 ms | 468 KB | Output is correct |
27 | Correct | 8 ms | 528 KB | Output is correct |
28 | Correct | 6 ms | 340 KB | Output is correct |
29 | Correct | 6 ms | 340 KB | Output is correct |
30 | Correct | 68 ms | 2172 KB | Output is correct |
31 | Correct | 37 ms | 568 KB | Output is correct |
32 | Correct | 38 ms | 468 KB | Output is correct |
33 | Correct | 5 ms | 340 KB | Output is correct |
34 | Correct | 6 ms | 340 KB | Output is correct |
35 | Correct | 6 ms | 340 KB | Output is correct |
36 | Correct | 7 ms | 468 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 5 ms | 340 KB | Output is correct |
39 | Correct | 6 ms | 468 KB | Output is correct |
40 | Correct | 6 ms | 340 KB | Output is correct |
41 | Correct | 0 ms | 340 KB | Output is correct |
42 | Correct | 6 ms | 520 KB | Output is correct |
43 | Correct | 47 ms | 596 KB | Output is correct |
44 | Correct | 45 ms | 704 KB | Output is correct |
45 | Correct | 63 ms | 1856 KB | Output is correct |
46 | Correct | 39 ms | 724 KB | Output is correct |
47 | Correct | 40 ms | 724 KB | Output is correct |
48 | Correct | 40 ms | 892 KB | Output is correct |
49 | Correct | 102 ms | 4124 KB | Output is correct |
50 | Correct | 1 ms | 340 KB | Output is correct |
51 | Correct | 1 ms | 340 KB | Output is correct |
52 | Correct | 39 ms | 596 KB | Output is correct |
53 | Correct | 39 ms | 652 KB | Output is correct |
54 | Correct | 38 ms | 576 KB | Output is correct |
55 | Correct | 39 ms | 596 KB | Output is correct |
56 | Correct | 37 ms | 596 KB | Output is correct |
57 | Correct | 1 ms | 340 KB | Output is correct |
58 | Correct | 8 ms | 704 KB | Output is correct |
59 | Correct | 9 ms | 700 KB | Output is correct |
60 | Correct | 8 ms | 700 KB | Output is correct |
61 | Correct | 83 ms | 4156 KB | Output is correct |
62 | Correct | 86 ms | 4228 KB | Output is correct |
63 | Correct | 1 ms | 212 KB | Output is correct |