# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77952 | 2018-10-01T11:39:59 Z | aquablitz11 | Travelling Merchant (APIO17_merchant) | C++14 | 105 ms | 5904 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 = 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 | 76 ms | 2552 KB | Output is correct |
2 | Correct | 44 ms | 2780 KB | Output is correct |
3 | Correct | 42 ms | 2780 KB | Output is correct |
4 | Correct | 9 ms | 2780 KB | Output is correct |
5 | Correct | 9 ms | 2780 KB | Output is correct |
6 | Correct | 9 ms | 2780 KB | Output is correct |
7 | Correct | 9 ms | 2780 KB | Output is correct |
8 | Correct | 2 ms | 2780 KB | Output is correct |
9 | Correct | 8 ms | 2780 KB | Output is correct |
10 | Correct | 8 ms | 2780 KB | Output is correct |
11 | Correct | 8 ms | 2780 KB | Output is correct |
12 | Correct | 2 ms | 2780 KB | Output is correct |
13 | Incorrect | 9 ms | 2780 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 2780 KB | Output is correct |
2 | Correct | 8 ms | 2780 KB | Output is correct |
3 | Correct | 8 ms | 2784 KB | Output is correct |
4 | Correct | 10 ms | 2944 KB | Output is correct |
5 | Correct | 10 ms | 2944 KB | Output is correct |
6 | Correct | 2 ms | 2944 KB | Output is correct |
7 | Incorrect | 8 ms | 2944 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 3540 KB | Output is correct |
2 | Correct | 105 ms | 5344 KB | Output is correct |
3 | Correct | 47 ms | 5344 KB | Output is correct |
4 | Correct | 49 ms | 5528 KB | Output is correct |
5 | Correct | 50 ms | 5904 KB | Output is correct |
6 | Correct | 45 ms | 5904 KB | Output is correct |
7 | Correct | 9 ms | 5904 KB | Output is correct |
8 | Correct | 2 ms | 5904 KB | Output is correct |
9 | Correct | 10 ms | 5904 KB | Output is correct |
10 | Correct | 9 ms | 5904 KB | Output is correct |
11 | Incorrect | 9 ms | 5904 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 2780 KB | Output is correct |
2 | Correct | 8 ms | 2780 KB | Output is correct |
3 | Correct | 8 ms | 2784 KB | Output is correct |
4 | Correct | 10 ms | 2944 KB | Output is correct |
5 | Correct | 10 ms | 2944 KB | Output is correct |
6 | Correct | 2 ms | 2944 KB | Output is correct |
7 | Incorrect | 8 ms | 2944 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |