# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77954 | 2018-10-01T11:49:39 Z | aquablitz11 | Travelling Merchant (APIO17_merchant) | C++14 | 129 ms | 1712 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; } 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 = 1e13; 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 | Incorrect | 98 ms | 1272 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1272 KB | Output is correct |
2 | Correct | 11 ms | 1272 KB | Output is correct |
3 | Correct | 12 ms | 1272 KB | Output is correct |
4 | Correct | 10 ms | 1272 KB | Output is correct |
5 | Correct | 13 ms | 1272 KB | Output is correct |
6 | Correct | 2 ms | 1272 KB | Output is correct |
7 | Incorrect | 11 ms | 1272 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 1600 KB | Output is correct |
2 | Correct | 129 ms | 1624 KB | Output is correct |
3 | Correct | 75 ms | 1712 KB | Output is correct |
4 | Incorrect | 73 ms | 1712 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1272 KB | Output is correct |
2 | Correct | 11 ms | 1272 KB | Output is correct |
3 | Correct | 12 ms | 1272 KB | Output is correct |
4 | Correct | 10 ms | 1272 KB | Output is correct |
5 | Correct | 13 ms | 1272 KB | Output is correct |
6 | Correct | 2 ms | 1272 KB | Output is correct |
7 | Incorrect | 11 ms | 1272 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |