# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106197 | 2019-04-17T09:10:21 Z | ekrem | Travelling Merchant (APIO17_merchant) | C++ | 421 ms | 1368 KB |
#include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define orta ((bas+son+1)/2) #define linf 10000000000000000ll #define inf 1000000007 #define N 1005 using namespace std; typedef long long ll; typedef pair < int , int > ii; ll n, m, k, mx, bas, son, a[N][N], d[105][105], dd[105][105]; bool yap(int x){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ if(i == j){ dd[i][i] = -linf; continue; } mx = 0; for(int y = 1; y <= k+k; y += 2) if(a[i][y] != -1 and a[j][y + 1] != -1) mx = max(mx, a[j][y + 1] - a[i][y]); dd[i][j] = mx - x*d[i][j]; // cout << i << " " << j << " " << d[i][j] << " " << mx << endl; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dd[i][j] = max(dd[i][j], dd[i][k] + dd[k][j] ); // for(int i = 1; i <= n; i++) // for(int j = 1; j <= n; j++) // cout << i << " " << j << " " << dd[i][j] << endl; for(int i = 1; i <= n; i++) if(dd[i][i] >= 0) return true; return false; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%lld %lld %lld",&n ,&m ,&k); for(int i = 1; i <= n; i++) for(int j = 1; j <= k+k; j++) scanf("%lld",&a[i][j]); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ d[i][j] = inf; d[i][i] = 0; } for(int i = 1; i <= m; i++){ ll x, y, z; scanf("%lld %lld %lld",&x ,&y ,&z); d[x][y] = min(d[x][y], z); } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // yap(2); // cout << yap(4) << endl; bas = 0, son = 1000000007; while(bas < son){ if(yap(orta)) bas = orta; else son = orta - 1; } printf("%lld\n", bas); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 342 ms | 1280 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 640 KB | Output is correct |
2 | Correct | 7 ms | 640 KB | Output is correct |
3 | Correct | 13 ms | 640 KB | Output is correct |
4 | Correct | 11 ms | 640 KB | Output is correct |
5 | Correct | 13 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 8 ms | 640 KB | Output is correct |
8 | Correct | 13 ms | 640 KB | Output is correct |
9 | Correct | 10 ms | 640 KB | Output is correct |
10 | Correct | 12 ms | 640 KB | Output is correct |
11 | Correct | 14 ms | 612 KB | Output is correct |
12 | Correct | 13 ms | 692 KB | Output is correct |
13 | Correct | 9 ms | 640 KB | Output is correct |
14 | Correct | 13 ms | 640 KB | Output is correct |
15 | Correct | 20 ms | 640 KB | Output is correct |
16 | Correct | 9 ms | 640 KB | Output is correct |
17 | Correct | 14 ms | 724 KB | Output is correct |
18 | Correct | 2 ms | 384 KB | Output is correct |
19 | Correct | 14 ms | 640 KB | Output is correct |
20 | Correct | 14 ms | 640 KB | Output is correct |
21 | Correct | 20 ms | 640 KB | Output is correct |
22 | Correct | 8 ms | 640 KB | Output is correct |
23 | Correct | 8 ms | 640 KB | Output is correct |
24 | Correct | 7 ms | 640 KB | Output is correct |
25 | Correct | 15 ms | 684 KB | Output is correct |
26 | Correct | 2 ms | 384 KB | Output is correct |
27 | Correct | 7 ms | 640 KB | Output is correct |
28 | Correct | 8 ms | 640 KB | Output is correct |
29 | Correct | 9 ms | 640 KB | Output is correct |
30 | Correct | 3 ms | 384 KB | Output is correct |
31 | Correct | 11 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 1024 KB | Output is correct |
2 | Incorrect | 421 ms | 1368 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 640 KB | Output is correct |
2 | Correct | 7 ms | 640 KB | Output is correct |
3 | Correct | 13 ms | 640 KB | Output is correct |
4 | Correct | 11 ms | 640 KB | Output is correct |
5 | Correct | 13 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 8 ms | 640 KB | Output is correct |
8 | Correct | 13 ms | 640 KB | Output is correct |
9 | Correct | 10 ms | 640 KB | Output is correct |
10 | Correct | 12 ms | 640 KB | Output is correct |
11 | Correct | 14 ms | 612 KB | Output is correct |
12 | Correct | 13 ms | 692 KB | Output is correct |
13 | Correct | 9 ms | 640 KB | Output is correct |
14 | Correct | 13 ms | 640 KB | Output is correct |
15 | Correct | 20 ms | 640 KB | Output is correct |
16 | Correct | 9 ms | 640 KB | Output is correct |
17 | Correct | 76 ms | 1024 KB | Output is correct |
18 | Incorrect | 421 ms | 1368 KB | Output isn't correct |
19 | Halted | 0 ms | 0 KB | - |