#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
/*
Time log:
- first start: 1048am
- 3/100: 1100am
- first stop: 1128am
- second start: 337pm
- 416pm finally stopped being stupid and got 9/100 (+6 points)
- second end:
- overall time used:
*/
/*
NxN grid of cells
grid[c][r] = the cell at column c row r
grid[0][r] is the westernmost point, and grid[N-1][r] is the easternmost point
grid[c][0] = southernmost point, grid[c][N-1] northermost point
M catfishes
X[i], Y[i] for i < M are column and row of fish i
W[i] = weight of fish i
a catfish can be caught if grid[ci][ri] is empty and grid[ci-1][ri] or grid[ci+1][ri] has a pier tile
a pier extends from grid[cP][0] to grid[cP][rP]
*/
int N, M;
vi X, Y; vector<ll> W;
bool cmp(int a, int b) { // compare two fish in the same col
return X[a] == X[b] ? Y[a] < Y[b] : X[a] < X[b];
}
void output_grid(vector<vl> &grid) {
for (int i = 0; i < sz(grid); i++) {
for (int j = 0; j < sz(grid[i]); j++) {
cout << grid[i][j] << " ";
}
cout << "\n";
}
}
// I think if i stop being stupid about implementation a simple DP will get 70/100
ll max_weights(int _N, int _M, vi _X, vi _Y, vi _W) {
N = _N; M = _M; X = _X; Y = _Y; for (int i = 0; i < M; i++) W.pb(ll(_W[i]));
vl fish(M); iota(all(fish), 0);
sort(all(fish), cmp);
vector<vl> grid(N+2, vl(N+2, 0LL));
for (int i = 0; i < M; i++) grid[X[fish[i]]+1][Y[fish[i]]+1] = W[fish[i]];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
grid[i][j] = grid[i][j - 1] + grid[i][j];
}
}
int prev[N+1][N+1];
vector<vl> DP(N+1, vl(N+1, 0LL)); // DP[i][j] = best score if we extend pier at position i by j places
ll ans = 0;
for (int i = 1; i <= N; i++) {
for (int nex = 0; nex <= N; nex++) {
DP[i][nex] = 0;
int bestOex = 0;
for (int oex = 0; oex <= N; oex++) {
ll prevContrib = DP[i - 1][oex] - grid[i][min(oex, nex)]; // answer from before, but we have to remove what we newly cover
ll ourContrib = grid[i-1][nex] - grid[i-1][min(oex, nex)]; // new adjacent except whats covered by oex
if (i == N - 1) ourContrib += grid[i+1][nex];
ll here = prevContrib + ourContrib;
if (here > DP[i][nex]) {
DP[i][nex] = here;
bestOex = i;
}
}
prev[i][nex] = bestOex;
ans = max(ans, DP[i][nex]);
}
}
int bfirst = 0; for (int i = 0; i <= N; i++) {if (DP[N][i] > DP[N][bfirst]) bfirst = i;}
vi hist;
int cur = N, ex = bfirst;
while (cur > 0) {
hist.push_back(ex);
ex = prev[cur][ex];
cur --;
}
// output_grid(grid);
// cout << "\n\n";
// output_grid(DP);
// cout << "\n";
// reverse(all(hist));
// for (int i = 0; i < N; i++) {
// cout << "Extend " << i << " by " << hist[i] << "\n";
// }
return ans;
}
