#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000;
long long subtask_bypass(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
if (all_of(begin(X), end(X), [] (int v) {return v%2 == 0;})) {
// subtask 1
return accumulate(begin(W), end(W), 0LL);
}
return -1; // this is full problem
}
/*
to make life easier, the value of a pier is (wt of fish behind/in front) - (wt of fish on pier)
the path can be in a few states;
- back-facing (pier at x=i that catches some fish at i-1)
- front-facing (pier at x=i-1 that catches some fish at i)
a back-facing path at y=h can move to
- a back-facing path at some higher/same y value
- a front-facing path at the same y value (do NOT count the - value of this pier, and ADD it to cancel the - of the ff path)
a front-facing path at y=h can move to
- a front-facing path at some lower/(same) y value
- a back-facing path at some lower/same y value (do NOT count the + value of the first back-facing pier)
- a back-facing path at a higher/(same) y value (do NOT count the + value of this pier)
- stasis
stasis can move to any back-facing path, or to stasis
start the x-coordinates at 1; starting state is stasis at x=0
pad 2 columns to the right; end state is stasis on last column
then dp to get max weight path from start to end state
*/
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> _W) {
// solve subtask 1 manually
ll bypass = subtask_bypass(N, M, X, Y, _W);
if (bypass != -1) return bypass;
// otherwise
int W = min(N, *max_element(begin(X), end(X)) + 2);
int H = *max_element(begin(Y), end(Y)) + 1;
vector<vector<ll>> weights(W + 3, vector<ll>(H));
for (int i = 0; i < M; ++i) {
weights[X[i] + 1][Y[i]] = _W[i];
}
vector<vector<ll>> columnSum = weights;
for (int xc = 0; xc < columnSum.size(); ++xc) {
for (int yc = 1; yc < H; ++yc) {
columnSum[xc][yc] += columnSum[xc][yc-1];
}
}
// needs xc > 0
auto pierValue = [&] (int xc, int yc, int c1, int c2) {
return c1 * columnSum[xc-1][yc] + c2 * columnSum[xc][yc];
};
vector<ll> stasisOpt(W + 3, -INF);
vector<vector<ll>> backFaceOpt(W+3, vector<ll>(H, -INF)), frontFaceOpt(W+3, vector<ll>(H, -INF));
// mod = -pierValue(xc, yc, 1, 0) is added to the entries
vector<ll> nxtBackFaceModPrefMax(H, -INF), nxtBackFaceSufMax(H, -INF), nxtFrontFacePrefMax(H, -INF);
stasisOpt[W+2] = 0;
for (int xc = W+1; xc >= 0; --xc) {
ll &s = stasisOpt[xc];
for (int yc = 0; yc < H; ++yc) {
ll &b = backFaceOpt[xc][yc], &f = frontFaceOpt[xc][yc];
if (0 < xc && xc <= W) {
// find value for the back-facing path here
b = max(b, frontFaceOpt[xc+1][yc] + pierValue(xc, yc, 1, 1));
/*
for (int nyc = yc; nyc < N; ++nyc) {
b = max(b, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, 1, -1));
}
*/
b = max(b, nxtBackFaceSufMax[yc] + pierValue(xc, yc, 1, -1));
}
if (2 <= xc && xc <= W + 1) {
// find value for the front-facing path here
f = max(f, stasisOpt[xc+1] + pierValue(xc, yc, -1, 1));
/*
for (int nyc = 0; nyc <= yc; ++nyc) {
f = max(f, frontFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 1));
f = max(f, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 1) - pierValue(xc+1, nyc, 1, 0));
}
*/
f = max(f, nxtFrontFacePrefMax[yc] + pierValue(xc, yc, -1, 1));
f = max(f, nxtBackFaceModPrefMax[yc] + pierValue(xc, yc, -1, 1));
/*
for (int nyc = yc; nyc < N; ++nyc) {
f = max(f, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 0));
}
*/
f = max(f, nxtBackFaceSufMax[yc] + pierValue(xc, yc, -1, 0));
}
}
// find value for the stasis path here
s = max(s, stasisOpt[xc+1]);
for (int nyc = 0; nyc < H; ++nyc) {
s = max(s, backFaceOpt[xc+1][nyc]);
}
// compute the prefix/suffix max arrays
if (xc > 0) {
nxtFrontFacePrefMax = frontFaceOpt[xc];
for (int i = 1; i < H; ++i) nxtFrontFacePrefMax[i] = max(nxtFrontFacePrefMax[i-1], nxtFrontFacePrefMax[i]);
nxtBackFaceModPrefMax = backFaceOpt[xc];
for (int i = 0; i < H; ++i) nxtBackFaceModPrefMax[i] -= pierValue(xc, i, 1, 0);
for (int i = 1; i < H; ++i) nxtBackFaceModPrefMax[i] = max(nxtBackFaceModPrefMax[i-1], nxtBackFaceModPrefMax[i]);
nxtBackFaceSufMax = backFaceOpt[xc];
for (int i = H - 2; i >= 0; --i) nxtBackFaceSufMax[i] = max(nxtBackFaceSufMax[i+1], nxtBackFaceSufMax[i]);
}
}
return stasisOpt[0];
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int xc = 0; xc < columnSum.size(); ++xc) {
| ~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3344 KB |
Output is correct |
2 |
Correct |
29 ms |
5556 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
87 ms |
12592 KB |
Output is correct |
6 |
Correct |
84 ms |
12620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
70 ms |
23476 KB |
Output is correct |
3 |
Correct |
84 ms |
28720 KB |
Output is correct |
4 |
Correct |
22 ms |
4436 KB |
Output is correct |
5 |
Correct |
29 ms |
5556 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
41 ms |
22604 KB |
Output is correct |
13 |
Correct |
53 ms |
25488 KB |
Output is correct |
14 |
Correct |
47 ms |
22604 KB |
Output is correct |
15 |
Correct |
45 ms |
25176 KB |
Output is correct |
16 |
Correct |
40 ms |
22620 KB |
Output is correct |
17 |
Correct |
48 ms |
25104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
35 ms |
22904 KB |
Output is correct |
3 |
Correct |
43 ms |
21852 KB |
Output is correct |
4 |
Correct |
41 ms |
21992 KB |
Output is correct |
5 |
Correct |
58 ms |
25420 KB |
Output is correct |
6 |
Correct |
60 ms |
26292 KB |
Output is correct |
7 |
Correct |
59 ms |
26900 KB |
Output is correct |
8 |
Correct |
61 ms |
26804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
4 ms |
3156 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
16 ms |
4272 KB |
Output is correct |
18 |
Correct |
17 ms |
4164 KB |
Output is correct |
19 |
Correct |
16 ms |
4148 KB |
Output is correct |
20 |
Correct |
15 ms |
4164 KB |
Output is correct |
21 |
Correct |
17 ms |
2740 KB |
Output is correct |
22 |
Correct |
26 ms |
5300 KB |
Output is correct |
23 |
Correct |
6 ms |
3412 KB |
Output is correct |
24 |
Correct |
11 ms |
3828 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
5 ms |
3284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
4 ms |
3156 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
16 ms |
4272 KB |
Output is correct |
18 |
Correct |
17 ms |
4164 KB |
Output is correct |
19 |
Correct |
16 ms |
4148 KB |
Output is correct |
20 |
Correct |
15 ms |
4164 KB |
Output is correct |
21 |
Correct |
17 ms |
2740 KB |
Output is correct |
22 |
Correct |
26 ms |
5300 KB |
Output is correct |
23 |
Correct |
6 ms |
3412 KB |
Output is correct |
24 |
Correct |
11 ms |
3828 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
5 ms |
3284 KB |
Output is correct |
27 |
Correct |
302 ms |
282800 KB |
Output is correct |
28 |
Correct |
73 ms |
23088 KB |
Output is correct |
29 |
Correct |
342 ms |
245840 KB |
Output is correct |
30 |
Correct |
388 ms |
289984 KB |
Output is correct |
31 |
Correct |
389 ms |
289980 KB |
Output is correct |
32 |
Correct |
84 ms |
16828 KB |
Output is correct |
33 |
Correct |
394 ms |
289976 KB |
Output is correct |
34 |
Correct |
370 ms |
289908 KB |
Output is correct |
35 |
Correct |
49 ms |
18380 KB |
Output is correct |
36 |
Correct |
193 ms |
115744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
35 ms |
22904 KB |
Output is correct |
3 |
Correct |
43 ms |
21852 KB |
Output is correct |
4 |
Correct |
41 ms |
21992 KB |
Output is correct |
5 |
Correct |
58 ms |
25420 KB |
Output is correct |
6 |
Correct |
60 ms |
26292 KB |
Output is correct |
7 |
Correct |
59 ms |
26900 KB |
Output is correct |
8 |
Correct |
61 ms |
26804 KB |
Output is correct |
9 |
Runtime error |
750 ms |
2097152 KB |
Execution killed with signal 9 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3344 KB |
Output is correct |
2 |
Correct |
29 ms |
5556 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
87 ms |
12592 KB |
Output is correct |
6 |
Correct |
84 ms |
12620 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
70 ms |
23476 KB |
Output is correct |
9 |
Correct |
84 ms |
28720 KB |
Output is correct |
10 |
Correct |
22 ms |
4436 KB |
Output is correct |
11 |
Correct |
29 ms |
5556 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
41 ms |
22604 KB |
Output is correct |
19 |
Correct |
53 ms |
25488 KB |
Output is correct |
20 |
Correct |
47 ms |
22604 KB |
Output is correct |
21 |
Correct |
45 ms |
25176 KB |
Output is correct |
22 |
Correct |
40 ms |
22620 KB |
Output is correct |
23 |
Correct |
48 ms |
25104 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
35 ms |
22904 KB |
Output is correct |
26 |
Correct |
43 ms |
21852 KB |
Output is correct |
27 |
Correct |
41 ms |
21992 KB |
Output is correct |
28 |
Correct |
58 ms |
25420 KB |
Output is correct |
29 |
Correct |
60 ms |
26292 KB |
Output is correct |
30 |
Correct |
59 ms |
26900 KB |
Output is correct |
31 |
Correct |
61 ms |
26804 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
468 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
0 ms |
212 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
4 ms |
3156 KB |
Output is correct |
47 |
Correct |
1 ms |
468 KB |
Output is correct |
48 |
Correct |
16 ms |
4272 KB |
Output is correct |
49 |
Correct |
17 ms |
4164 KB |
Output is correct |
50 |
Correct |
16 ms |
4148 KB |
Output is correct |
51 |
Correct |
15 ms |
4164 KB |
Output is correct |
52 |
Correct |
17 ms |
2740 KB |
Output is correct |
53 |
Correct |
26 ms |
5300 KB |
Output is correct |
54 |
Correct |
6 ms |
3412 KB |
Output is correct |
55 |
Correct |
11 ms |
3828 KB |
Output is correct |
56 |
Correct |
1 ms |
468 KB |
Output is correct |
57 |
Correct |
5 ms |
3284 KB |
Output is correct |
58 |
Correct |
302 ms |
282800 KB |
Output is correct |
59 |
Correct |
73 ms |
23088 KB |
Output is correct |
60 |
Correct |
342 ms |
245840 KB |
Output is correct |
61 |
Correct |
388 ms |
289984 KB |
Output is correct |
62 |
Correct |
389 ms |
289980 KB |
Output is correct |
63 |
Correct |
84 ms |
16828 KB |
Output is correct |
64 |
Correct |
394 ms |
289976 KB |
Output is correct |
65 |
Correct |
370 ms |
289908 KB |
Output is correct |
66 |
Correct |
49 ms |
18380 KB |
Output is correct |
67 |
Correct |
193 ms |
115744 KB |
Output is correct |
68 |
Runtime error |
750 ms |
2097152 KB |
Execution killed with signal 9 |
69 |
Halted |
0 ms |
0 KB |
- |