#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))), H = *max_element(begin(Y), end(Y)) + 2;
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:57: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]
57 | for (int xc = 0; xc < columnSum.size(); ++xc) {
| ~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
27 ms |
3788 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
84 ms |
10848 KB |
Output is correct |
| 6 |
Correct |
86 ms |
10848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
31 ms |
23004 KB |
Output is correct |
| 3 |
Correct |
44 ms |
21680 KB |
Output is correct |
| 4 |
Incorrect |
41 ms |
21960 KB |
1st lines differ - on the 1st token, expected: '14486631352875', found: '14486568777930' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
31 ms |
23004 KB |
Output is correct |
| 3 |
Correct |
44 ms |
21680 KB |
Output is correct |
| 4 |
Incorrect |
41 ms |
21960 KB |
1st lines differ - on the 1st token, expected: '14486631352875', found: '14486568777930' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
27 ms |
3788 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
84 ms |
10848 KB |
Output is correct |
| 6 |
Correct |
86 ms |
10848 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
