# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
49669 | 2018-06-01T19:31:16 Z | gs14004 | Travelling Merchant (APIO17_merchant) | C++17 | 805 ms | 1788 KB |
#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef long double llf; typedef pair<lint, lint> pi; int n, m, k; int b[105][1005], s[105][1005]; int adj[105][105], dx[105][105]; llf gph[105][105]; bool trial(llf t){ // TotalProfit - t * TotalTime > 0 for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(adj[i][j] > 1e9 + 10) gph[i][j] = -1e12; else gph[i][j] = dx[i][j] - t * adj[i][j]; } } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ for(int k=1; k<=n; k++){ gph[j][k] = max(gph[j][k], gph[j][i] + gph[i][k]); } } } for(int i=1; i<=n; i++){ if(gph[i][i] >= 0) return 1; } return 0; } int main(){ scanf("%d %d %d",&n,&m,&k); for(int i=1; i<=n; i++){ for(int j=0; j<k; j++) scanf("%d %d",&b[i][j],&s[i][j]); } memset(adj, 0x3f, sizeof(adj)); for(int i=0; i<m; i++){ int s, e, x; scanf("%d %d %d",&s,&e,&x); adj[s][e] = x; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ for(int k=1; k<=n; k++){ adj[j][k] = min(adj[j][i] + adj[i][k], adj[j][k]); } } } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ for(int l=0; l<k; l++){ if(~s[j][l] && ~b[i][l]) dx[i][j] = max(dx[i][j], s[j][l] - b[i][l]); } } } llf s = 0, e = 2e9; for(int i=0; i<100; i++){ llf m = (s+e)/2; if(trial(m)) s = m; else e = m; } printf("%lld",(lint)floor(e)); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 694 ms | 1400 KB | Output is correct |
2 | Correct | 805 ms | 1512 KB | Output is correct |
3 | Correct | 650 ms | 1512 KB | Output is correct |
4 | Correct | 83 ms | 1512 KB | Output is correct |
5 | Correct | 83 ms | 1512 KB | Output is correct |
6 | Correct | 81 ms | 1512 KB | Output is correct |
7 | Correct | 133 ms | 1512 KB | Output is correct |
8 | Correct | 2 ms | 1512 KB | Output is correct |
9 | Correct | 85 ms | 1512 KB | Output is correct |
10 | Correct | 83 ms | 1512 KB | Output is correct |
11 | Correct | 85 ms | 1512 KB | Output is correct |
12 | Correct | 2 ms | 1512 KB | Output is correct |
13 | Correct | 84 ms | 1512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 1512 KB | Output is correct |
2 | Correct | 89 ms | 1512 KB | Output is correct |
3 | Correct | 85 ms | 1512 KB | Output is correct |
4 | Correct | 74 ms | 1512 KB | Output is correct |
5 | Correct | 84 ms | 1512 KB | Output is correct |
6 | Correct | 2 ms | 1512 KB | Output is correct |
7 | Correct | 90 ms | 1512 KB | Output is correct |
8 | Correct | 81 ms | 1512 KB | Output is correct |
9 | Correct | 85 ms | 1512 KB | Output is correct |
10 | Correct | 90 ms | 1512 KB | Output is correct |
11 | Correct | 82 ms | 1512 KB | Output is correct |
12 | Correct | 82 ms | 1512 KB | Output is correct |
13 | Correct | 88 ms | 1512 KB | Output is correct |
14 | Correct | 87 ms | 1512 KB | Output is correct |
15 | Correct | 89 ms | 1512 KB | Output is correct |
16 | Correct | 106 ms | 1512 KB | Output is correct |
17 | Correct | 88 ms | 1512 KB | Output is correct |
18 | Correct | 2 ms | 1512 KB | Output is correct |
19 | Correct | 92 ms | 1512 KB | Output is correct |
20 | Correct | 88 ms | 1512 KB | Output is correct |
21 | Correct | 84 ms | 1512 KB | Output is correct |
22 | Correct | 89 ms | 1512 KB | Output is correct |
23 | Correct | 81 ms | 1512 KB | Output is correct |
24 | Correct | 81 ms | 1512 KB | Output is correct |
25 | Correct | 133 ms | 1512 KB | Output is correct |
26 | Correct | 2 ms | 1512 KB | Output is correct |
27 | Correct | 85 ms | 1512 KB | Output is correct |
28 | Correct | 83 ms | 1512 KB | Output is correct |
29 | Correct | 85 ms | 1512 KB | Output is correct |
30 | Correct | 2 ms | 1512 KB | Output is correct |
31 | Correct | 84 ms | 1512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 676 ms | 1664 KB | Output is correct |
2 | Correct | 752 ms | 1788 KB | Output is correct |
3 | Correct | 666 ms | 1788 KB | Output is correct |
4 | Correct | 707 ms | 1788 KB | Output is correct |
5 | Correct | 679 ms | 1788 KB | Output is correct |
6 | Correct | 673 ms | 1788 KB | Output is correct |
7 | Correct | 88 ms | 1512 KB | Output is correct |
8 | Correct | 2 ms | 1512 KB | Output is correct |
9 | Correct | 92 ms | 1512 KB | Output is correct |
10 | Correct | 88 ms | 1512 KB | Output is correct |
11 | Correct | 84 ms | 1512 KB | Output is correct |
12 | Correct | 89 ms | 1512 KB | Output is correct |
13 | Correct | 81 ms | 1512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 1512 KB | Output is correct |
2 | Correct | 89 ms | 1512 KB | Output is correct |
3 | Correct | 85 ms | 1512 KB | Output is correct |
4 | Correct | 74 ms | 1512 KB | Output is correct |
5 | Correct | 84 ms | 1512 KB | Output is correct |
6 | Correct | 2 ms | 1512 KB | Output is correct |
7 | Correct | 90 ms | 1512 KB | Output is correct |
8 | Correct | 81 ms | 1512 KB | Output is correct |
9 | Correct | 85 ms | 1512 KB | Output is correct |
10 | Correct | 90 ms | 1512 KB | Output is correct |
11 | Correct | 82 ms | 1512 KB | Output is correct |
12 | Correct | 82 ms | 1512 KB | Output is correct |
13 | Correct | 88 ms | 1512 KB | Output is correct |
14 | Correct | 87 ms | 1512 KB | Output is correct |
15 | Correct | 89 ms | 1512 KB | Output is correct |
16 | Correct | 106 ms | 1512 KB | Output is correct |
17 | Correct | 676 ms | 1664 KB | Output is correct |
18 | Correct | 752 ms | 1788 KB | Output is correct |
19 | Correct | 666 ms | 1788 KB | Output is correct |
20 | Correct | 707 ms | 1788 KB | Output is correct |
21 | Correct | 679 ms | 1788 KB | Output is correct |
22 | Correct | 673 ms | 1788 KB | Output is correct |
23 | Correct | 88 ms | 1512 KB | Output is correct |
24 | Correct | 2 ms | 1512 KB | Output is correct |
25 | Correct | 92 ms | 1512 KB | Output is correct |
26 | Correct | 88 ms | 1512 KB | Output is correct |
27 | Correct | 84 ms | 1512 KB | Output is correct |
28 | Correct | 89 ms | 1512 KB | Output is correct |
29 | Correct | 81 ms | 1512 KB | Output is correct |
30 | Correct | 655 ms | 1788 KB | Output is correct |
31 | Correct | 670 ms | 1788 KB | Output is correct |
32 | Correct | 681 ms | 1788 KB | Output is correct |
33 | Correct | 672 ms | 1788 KB | Output is correct |
34 | Correct | 694 ms | 1788 KB | Output is correct |
35 | Correct | 675 ms | 1788 KB | Output is correct |
36 | Correct | 720 ms | 1788 KB | Output is correct |
37 | Correct | 3 ms | 1788 KB | Output is correct |
38 | Correct | 2 ms | 1788 KB | Output is correct |
39 | Correct | 660 ms | 1788 KB | Output is correct |
40 | Correct | 672 ms | 1788 KB | Output is correct |
41 | Correct | 729 ms | 1788 KB | Output is correct |
42 | Correct | 707 ms | 1788 KB | Output is correct |
43 | Correct | 696 ms | 1788 KB | Output is correct |
44 | Correct | 2 ms | 1788 KB | Output is correct |
45 | Correct | 86 ms | 1788 KB | Output is correct |
46 | Correct | 87 ms | 1788 KB | Output is correct |
47 | Correct | 91 ms | 1788 KB | Output is correct |
48 | Correct | 736 ms | 1788 KB | Output is correct |
49 | Correct | 749 ms | 1788 KB | Output is correct |
50 | Correct | 3 ms | 1788 KB | Output is correct |
51 | Correct | 694 ms | 1400 KB | Output is correct |
52 | Correct | 805 ms | 1512 KB | Output is correct |
53 | Correct | 650 ms | 1512 KB | Output is correct |
54 | Correct | 83 ms | 1512 KB | Output is correct |
55 | Correct | 83 ms | 1512 KB | Output is correct |
56 | Correct | 81 ms | 1512 KB | Output is correct |
57 | Correct | 133 ms | 1512 KB | Output is correct |
58 | Correct | 2 ms | 1512 KB | Output is correct |
59 | Correct | 85 ms | 1512 KB | Output is correct |
60 | Correct | 83 ms | 1512 KB | Output is correct |
61 | Correct | 85 ms | 1512 KB | Output is correct |
62 | Correct | 2 ms | 1512 KB | Output is correct |
63 | Correct | 84 ms | 1512 KB | Output is correct |