#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define MAXN 305
#define MAXM (MAXN*MAXN)
/*
this is a nice dp problem
so here's the thing, we only care about the previous two columns when deciding the current column right
suppose the current column i has height j, then we are continuing column i-1:
- if column i-1 has height less than or equal to j
- we must also consider the height of column i-2, as it can now be greater than the height of column i-1
to do this we use a separate type of dp
- if column i-1 has height greater than or equal to j
there are two types of dp that can represent a column:
- a "normal" DP
this stores the normal "what is the highest we can achieve if we only have up to i, and at i we build j"
- a "continuation" DP
this store something weirder, "what is the highest we can achieve if we only have up to i, and at i we build some k <= j, BUT at i-1 we build j"
huh wait the second DP is just a DP thats tied to i-2 then?
"what is the highest we can achieve, if we have up to i+1, the at i has height j, and at i+1 we have some height lower than j
wait but thats.. redundant?
ok nevermind yeah the continuation dp is actually unnecessary
the conclusion is this:
at index i, if it continues i-1, and it is already greater than i, then we have all the information we need
however if it is less than i, then it is NEVER the case that i-2 is greater than i
*/
int N, M;
std::vector<signed> X, Y, W;
int dp[MAXN][MAXN];
int dpls[MAXN][MAXN];
int dpmm[MAXN][MAXN];
int dpm;
int dpt[MAXN];
int WA[MAXN][MAXN];
int pfr(int *arr, int l, int r) { return arr[r] - (l == 0 ? 0 : arr[l-1]); }
void contribute(int dpi)
{
for (int i = 0; i < N; ++i)
dpm = std::max(dpm, dp[dpi][i] + (dpi+1 < N ? WA[dpi+1][i] : 0));
}
long long max_weights(signed _N, signed _M, std::vector<signed> _X, std::vector<signed> _Y,
std::vector<signed> _W) {
N = _N; M = _M;
X = std::move(_X);
Y = std::move(_Y);
W = std::move(_W);
for (int i = 0; i < M; ++i)
WA[X[i]][Y[i]] = W[i];
for (int i = 0; i < N; ++i)
for (int j = 1; j < N; ++j)
WA[i][j] += WA[i][j-1];
for (int i = 0; i < N; ++i)
{
dp[0][i] = 0;//N > 1 ? WA[1][i] : 0;
dpm = std::max(dpm, dp[0][i]);
dpmm[0][i] = std::max(i > 0 ? dpmm[0][i-1] : 0, dp[0][i]);
}
for (int i = 1; i < N; ++i)
{
//printf("%i: ", i);
for (int j = 0; j < N; ++j)
{
dp[i][j] = dpm + WA[i-1][j];
dpls[i][j] = dp[i][j];
for (int l = 0; l < N; ++l)
{
if (l <= j)
{
dp[i][j] = std::max(dp[i][j], dpls[i-1][l] + pfr(WA[i-1], l+1, j));
dpls[i][j] = std::max(dpls[i][j], dpls[i-1][l] + pfr(WA[i-1], l+1, j));
}
else
dp[i][j] = std::max(dp[i][j], dp[i-1][l] + pfr(WA[i], j+1, l));
if (i-2 >= 0)
{
dp[i][j] = std::max(dp[i][j], dp[i-2][l] + WA[i-1][j]);
}
}
//printf("%i(%i,%i,%i) ", dp[i][j], dpls[i][j], dpm, WA[i-1][j]);
}
//printf("\n");
if (i >= 2)
contribute(i-2);
}
contribute(N-1);
contribute(N-2);
return dpm;
}
