# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
567732 | 2022-05-24T06:04:18 Z | shahriarkhan | Travelling Merchant (APIO17_merchant) | C++14 | 95 ms | 4284 KB |
#include<bits/stdc++.h> using namespace std ; const int MX_N = 105 , MX_K = 1005 ; const long long INF = 1e18 + 5 ; int n , m , k ; long long dist[MX_N][MX_N] , best[MX_N][MX_N] , buy[MX_N][MX_K] , sell[MX_N][MX_K] , profit[MX_N][MX_N] ; void floyd_warshall(long long dst[MX_N][MX_N]) { for(int l = 1 ; l <= n ; ++l) { for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { dst[i][j] = min(dst[i][j],dst[i][l]+dst[l][j]) ; } } } } int main() { scanf("%d%d%d",&n,&m,&k) ; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= k ; ++j) { scanf("%lld%lld",&buy[i][j],&sell[i][j]) ; } } for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { dist[i][j] = INF ; } } for(int i = 1 ; i <= m ; ++i) { long long v , w , t ; scanf("%lld%lld%lld",&v,&w,&t) ; dist[v][w] = t ; } floyd_warshall(dist) ; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { for(int l = 1 ; l <= k ; ++l) { if(buy[i][l]<0) continue ; if(sell[j][l]<0) continue ; best[i][j] = max(best[i][j],sell[j][l]-buy[i][l]) ; } } } long long low = 0 , high = 1e9 + 5 ; while(low<high) { long long mid = (low+high+1)/2 , good = 0 ; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= n ; ++j) { profit[i][j] = mid*min(INF/mid,dist[i][j]) - best[i][j] ; } } floyd_warshall(profit) ; for(int i = 1 ; i <= n ; ++i) { if(profit[i][i]<=0) good = 1 ; } if(good) low = mid ; else high = mid - 1 ; } printf("%lld\n",low) ; return 0 ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 55 ms | 1976 KB | Output is correct |
2 | Correct | 31 ms | 1236 KB | Output is correct |
3 | Correct | 33 ms | 1236 KB | Output is correct |
4 | Correct | 6 ms | 724 KB | Output is correct |
5 | Correct | 5 ms | 724 KB | Output is correct |
6 | Correct | 5 ms | 724 KB | Output is correct |
7 | Correct | 6 ms | 852 KB | Output is correct |
8 | Correct | 1 ms | 312 KB | Output is correct |
9 | Correct | 5 ms | 800 KB | Output is correct |
10 | Correct | 6 ms | 808 KB | Output is correct |
11 | Correct | 6 ms | 724 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 5 ms | 832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 724 KB | Output is correct |
2 | Correct | 6 ms | 852 KB | Output is correct |
3 | Correct | 1 ms | 312 KB | Output is correct |
4 | Correct | 5 ms | 800 KB | Output is correct |
5 | Correct | 6 ms | 808 KB | Output is correct |
6 | Correct | 6 ms | 724 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 5 ms | 832 KB | Output is correct |
9 | Correct | 5 ms | 848 KB | Output is correct |
10 | Correct | 7 ms | 724 KB | Output is correct |
11 | Correct | 6 ms | 836 KB | Output is correct |
12 | Correct | 6 ms | 852 KB | Output is correct |
13 | Correct | 6 ms | 852 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 5 ms | 828 KB | Output is correct |
16 | Correct | 6 ms | 852 KB | Output is correct |
17 | Correct | 6 ms | 948 KB | Output is correct |
18 | Correct | 5 ms | 852 KB | Output is correct |
19 | Correct | 6 ms | 852 KB | Output is correct |
20 | Correct | 6 ms | 828 KB | Output is correct |
21 | Correct | 6 ms | 852 KB | Output is correct |
22 | Correct | 6 ms | 872 KB | Output is correct |
23 | Correct | 7 ms | 852 KB | Output is correct |
24 | Correct | 5 ms | 760 KB | Output is correct |
25 | Correct | 7 ms | 852 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
27 | Correct | 6 ms | 916 KB | Output is correct |
28 | Correct | 6 ms | 832 KB | Output is correct |
29 | Correct | 6 ms | 852 KB | Output is correct |
30 | Correct | 6 ms | 852 KB | Output is correct |
31 | Correct | 5 ms | 724 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 | 6 ms | 916 KB | Output is correct |
4 | Correct | 6 ms | 832 KB | Output is correct |
5 | Correct | 6 ms | 852 KB | Output is correct |
6 | Correct | 6 ms | 852 KB | Output is correct |
7 | Correct | 5 ms | 724 KB | Output is correct |
8 | Correct | 38 ms | 1492 KB | Output is correct |
9 | Correct | 86 ms | 3788 KB | Output is correct |
10 | Correct | 32 ms | 1492 KB | Output is correct |
11 | Correct | 36 ms | 1636 KB | Output is correct |
12 | Correct | 39 ms | 1800 KB | Output is correct |
13 | Correct | 32 ms | 1492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 848 KB | Output is correct |
2 | Correct | 7 ms | 724 KB | Output is correct |
3 | Correct | 6 ms | 836 KB | Output is correct |
4 | Correct | 6 ms | 852 KB | Output is correct |
5 | Correct | 6 ms | 852 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 5 ms | 828 KB | Output is correct |
8 | Correct | 6 ms | 852 KB | Output is correct |
9 | Correct | 6 ms | 948 KB | Output is correct |
10 | Correct | 5 ms | 852 KB | Output is correct |
11 | Correct | 6 ms | 852 KB | Output is correct |
12 | Correct | 6 ms | 828 KB | Output is correct |
13 | Correct | 6 ms | 852 KB | Output is correct |
14 | Correct | 6 ms | 872 KB | Output is correct |
15 | Correct | 7 ms | 852 KB | Output is correct |
16 | Correct | 5 ms | 760 KB | Output is correct |
17 | Correct | 38 ms | 1492 KB | Output is correct |
18 | Correct | 86 ms | 3788 KB | Output is correct |
19 | Correct | 32 ms | 1492 KB | Output is correct |
20 | Correct | 36 ms | 1636 KB | Output is correct |
21 | Correct | 39 ms | 1800 KB | Output is correct |
22 | Correct | 32 ms | 1492 KB | Output is correct |
23 | Correct | 7 ms | 852 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 6 ms | 916 KB | Output is correct |
26 | Correct | 6 ms | 832 KB | Output is correct |
27 | Correct | 6 ms | 852 KB | Output is correct |
28 | Correct | 6 ms | 852 KB | Output is correct |
29 | Correct | 5 ms | 724 KB | Output is correct |
30 | Correct | 55 ms | 1976 KB | Output is correct |
31 | Correct | 31 ms | 1236 KB | Output is correct |
32 | Correct | 33 ms | 1236 KB | Output is correct |
33 | Correct | 6 ms | 724 KB | Output is correct |
34 | Correct | 5 ms | 724 KB | Output is correct |
35 | Correct | 5 ms | 724 KB | Output is correct |
36 | Correct | 6 ms | 852 KB | Output is correct |
37 | Correct | 1 ms | 312 KB | Output is correct |
38 | Correct | 5 ms | 800 KB | Output is correct |
39 | Correct | 6 ms | 808 KB | Output is correct |
40 | Correct | 6 ms | 724 KB | Output is correct |
41 | Correct | 1 ms | 340 KB | Output is correct |
42 | Correct | 5 ms | 832 KB | Output is correct |
43 | Correct | 32 ms | 1364 KB | Output is correct |
44 | Correct | 40 ms | 1576 KB | Output is correct |
45 | Correct | 51 ms | 2600 KB | Output is correct |
46 | Correct | 32 ms | 1492 KB | Output is correct |
47 | Correct | 33 ms | 1492 KB | Output is correct |
48 | Correct | 32 ms | 1492 KB | Output is correct |
49 | Correct | 85 ms | 4080 KB | Output is correct |
50 | Correct | 1 ms | 340 KB | Output is correct |
51 | Correct | 1 ms | 340 KB | Output is correct |
52 | Correct | 33 ms | 1324 KB | Output is correct |
53 | Correct | 36 ms | 1432 KB | Output is correct |
54 | Correct | 31 ms | 1432 KB | Output is correct |
55 | Correct | 31 ms | 1364 KB | Output is correct |
56 | Correct | 32 ms | 1236 KB | Output is correct |
57 | Correct | 1 ms | 340 KB | Output is correct |
58 | Correct | 7 ms | 960 KB | Output is correct |
59 | Correct | 7 ms | 1004 KB | Output is correct |
60 | Correct | 8 ms | 980 KB | Output is correct |
61 | Correct | 95 ms | 4284 KB | Output is correct |
62 | Correct | 84 ms | 4164 KB | Output is correct |
63 | Correct | 1 ms | 340 KB | Output is correct |