#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000;
/*
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
so ???? a dp here
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
*/
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<ll>> weights(N + 3, vector<ll>(N));
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 < N; ++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(N + 3, -INF);
vector<vector<ll>> backFaceOpt(N+3, vector<ll>(N, -INF)), frontFaceOpt(N+3, vector<ll>(N, -INF));
stasisOpt[N+2] = 0;
for (int xc = N+1; xc >= 0; --xc) {
for (int yc = 0; yc < N; ++yc) {
ll &b = backFaceOpt[xc][yc], &f = frontFaceOpt[xc][yc], &s = stasisOpt[xc];
if (0 < xc && xc <= N) {
// 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));
}
}
if (2 <= xc && xc <= N + 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));
}
for (int nyc = yc; nyc < N; ++nyc) {
f = max(f, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 0));
}
}
// find value for the stasis path here
s = max(s, stasisOpt[xc+1]);
for (int nyc = 0; nyc < N; ++nyc) {
s = max(s, backFaceOpt[xc+1][nyc]);
}
/*
printf("%d %d: back %lld front %lld stasis %lld ", xc, yc, b, f, s);
if (xc > 0) printf("(raw values) %lld %lld\n", columnSum[xc-1][yc], columnSum[xc][yc]);
*/
}
}
return stasisOpt[0];
}
