# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77953 | 2018-10-01T11:47:26 Z | aquablitz11 | Travelling Merchant (APIO17_merchant) | C++14 | 158 ms | 1788 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 110; const int T = 1010; const ll INF = 1e18; int n, m, t; int B[N][T], S[N][T]; ll pro[N][N], dist[N][N], A[N][N]; bool check(ll r) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) A[i][j] = pro[i][j]-dist[i][j]*r; A[i][i] = -INF; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) A[i][j] = max(A[i][j], A[i][k]+A[k][j]); } } for (int i = 1; i <= n; ++i) { if (A[i][i] >= 0) return true; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) if (A[i][k]+A[k][j] > A[i][j]) return true; } } return false; } int main() { scanf("%d%d%d", &n, &m, &t); for (int i = 1; i <= n; ++i) { dist[i][i] = 0; for (int j = 1; j <= t; ++j) scanf("%d%d", &B[i][j], &S[i][j]); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dist[i][j] = INF; for (int k = 1; k <= t; ++k) { if (B[i][k] != -1 && S[j][k] != -1) pro[i][j] = max(pro[i][j], (ll)S[j][k]-B[i][k]); } } dist[i][i] = 0; } for (int i = 1; i <= m; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); dist[u][v] = w; } for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]); } } ll b = 0, e = 1e9; while (b < e) { ll m = (b+e+1)/2; if (check(m)) b = m; else e = m-1; } printf("%lld\n", b); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 1400 KB | Output is correct |
2 | Correct | 95 ms | 1400 KB | Output is correct |
3 | Correct | 59 ms | 1472 KB | Output is correct |
4 | Correct | 11 ms | 1472 KB | Output is correct |
5 | Correct | 11 ms | 1472 KB | Output is correct |
6 | Correct | 12 ms | 1472 KB | Output is correct |
7 | Correct | 12 ms | 1472 KB | Output is correct |
8 | Correct | 3 ms | 1472 KB | Output is correct |
9 | Correct | 10 ms | 1472 KB | Output is correct |
10 | Correct | 11 ms | 1472 KB | Output is correct |
11 | Correct | 17 ms | 1472 KB | Output is correct |
12 | Correct | 2 ms | 1472 KB | Output is correct |
13 | Incorrect | 12 ms | 1472 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1472 KB | Output is correct |
2 | Correct | 11 ms | 1472 KB | Output is correct |
3 | Correct | 12 ms | 1472 KB | Output is correct |
4 | Correct | 16 ms | 1472 KB | Output is correct |
5 | Correct | 12 ms | 1472 KB | Output is correct |
6 | Correct | 3 ms | 1472 KB | Output is correct |
7 | Incorrect | 10 ms | 1472 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 77 ms | 1680 KB | Output is correct |
2 | Correct | 158 ms | 1680 KB | Output is correct |
3 | Correct | 64 ms | 1680 KB | Output is correct |
4 | Correct | 73 ms | 1788 KB | Output is correct |
5 | Correct | 57 ms | 1788 KB | Output is correct |
6 | Correct | 64 ms | 1788 KB | Output is correct |
7 | Correct | 12 ms | 1788 KB | Output is correct |
8 | Correct | 2 ms | 1788 KB | Output is correct |
9 | Correct | 9 ms | 1788 KB | Output is correct |
10 | Correct | 12 ms | 1788 KB | Output is correct |
11 | Incorrect | 11 ms | 1788 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1472 KB | Output is correct |
2 | Correct | 11 ms | 1472 KB | Output is correct |
3 | Correct | 12 ms | 1472 KB | Output is correct |
4 | Correct | 16 ms | 1472 KB | Output is correct |
5 | Correct | 12 ms | 1472 KB | Output is correct |
6 | Correct | 3 ms | 1472 KB | Output is correct |
7 | Incorrect | 10 ms | 1472 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |