#include "fish.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Catfish{
int x, y, w;
Catfish() {}
Catfish(int X, int Y, int W): x(X), y(Y), w(W) {}
bool operator < (const Catfish &c2) {
return pair<int, int>{x, y} < pair<int, int>{c2.x, c2.y};
}
string str() {
return "(" + to_string(x) + "," + to_string(y) + "," + to_string(w) + ")";
}
};
const long long INF = 1e18;
bool testing = false;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<Catfish>> inCol(1+N);
for (int i = 0; i < M; ++i) {
++X[i], ++Y[i];
inCol[X[i]].emplace_back(X[i], Y[i], W[i]);
}
// for (int i = 1; i <= N; ++i) {
// for (int j = 1; j <= N; ++j) {
// bool found = false;
// for (Catfish &c : inCol[i]) {
// if (c.y == j) found = true;
// break;
// }
// if (!found) inCol[i].emplace_back(i, j, 0);
// }
// }
for (int i = 0; i <= N; ++i) inCol[i].emplace_back(i, 0, 0), sort(inCol[i].begin(), inCol[i].end());
if (testing) {
for (int i = 0; i <= N; ++i) {
for (int j = 0; j < (int)inCol[i].size(); ++j) cout << inCol[i][j].str() << ' ';
cout << endl;
}
}
vector<vector<long long>> sumBelow(1+N);
for (int i = 0; i <= N; ++i) {
sumBelow[i].resize(inCol[i].size());
for (size_t j = 0; j < sumBelow[i].size(); ++j) {
sumBelow[i][j] = (j == 0 ? 0 : sumBelow[i][j-1]) + inCol[i][j].w;
}
}
if (testing) {
for (int i = 0; i <= N; ++i) {
for (int j = 0; j < (int)sumBelow[i].size(); ++j) cout << sumBelow[i][j] << ' ';
cout << endl;
}
}
vector<vector<int>> heights(1+N);
for (int i = 1; i <= N; ++i) {
if (i) {
for (const Catfish &c : inCol[i-1]) heights[i].push_back(c.y);
}
if (i<N) {
for (const Catfish &c : inCol[i+1]) heights[i].push_back(c.y);
}
sort(heights[i].begin(), heights[i].end());
heights[i].resize(unique(heights[i].begin(), heights[i].end()) - heights[i].begin());
}
heights[0].push_back(0);
if (testing) {
cout << "HEIGHTS:" << endl;
for (int i = 0; i <= N; ++i) {
for (int j = 0; j < (int)heights[i].size(); ++j) cout << heights[i][j] << ' ';
cout << endl;
}
}
vector<vector<long long>> inside(1+N), insideLeft(1+N), insideRight(1+N);
for (int i = 0; i <= N; ++i) {
inside[i] = insideLeft[i] = insideRight[i] = vector<long long>(heights[i].size());
size_t nxt = 0, nxtLeft = 0, nxtRight = 0;
long long sum = 0, sumLeft = 0, sumRight = 0;
for (size_t j = 0; j < heights[i].size(); ++j) {
int h = heights[i][j];
while (nxt < inCol[i].size() && inCol[i][nxt].y <= h) sum += inCol[i][nxt++].w;
if (i) {
while (nxtLeft < inCol[i-1].size() && inCol[i-1][nxtLeft].y <= h) sumLeft += inCol[i-1][nxtLeft++].w;
}
if (i<N) {
while (nxtRight < inCol[i+1].size() && inCol[i+1][nxtRight].y <= h) sumRight += inCol[i+1][nxtRight++].w;
}
inside[i][j] = sum, insideLeft[i][j] = sumLeft, insideRight[i][j] = sumRight;
}
}
if (testing) {
cout << "INSIDE:" << endl;
for (int i = 0; i <= N; ++i) {
for (int j = 0; j < (int)inside[i].size(); ++j) cout << inside[i][j] << ' ';
cout << endl;
}
cout << " left:" << endl;
for (int i = 0; i <= N; ++i) {
for (int j = 0; j < (int)insideLeft[i].size(); ++j) cout << insideLeft[i][j] << ' ';
cout << endl;
}
cout << " right:" << endl;
for (int i = 0; i <= N; ++i) {
for (int j = 0; j < (int)insideRight[i].size(); ++j) cout << insideRight[i][j] << ' ';
cout << endl;
}
}
vector<vector<long long>> dp[2]; // 0 means >= previous, 1 means <= previous
dp[0] = dp[1] = vector<vector<long long>>(1+N);
/*
observation: exists solution in which all local minimums have height 0
and all local maximums have height effectively equal to N
*/
if (testing) cout << endl << "DP\n";
long long ans = 0;
dp[0][0] = dp[1][0] = {0};
for (int x = 1; x <= N; ++x) {
dp[0][x] = dp[1][x] = vector<long long>(heights[x].size());
{ // increasing
long long maxDif = -INF; // max score - inside
size_t nxtLeft = 0;
for (size_t j = 0; j < heights[x].size(); ++j) {
int y = heights[x][j];
while (nxtLeft < heights[x-1].size() && heights[x-1][nxtLeft] <= y) {
maxDif = max(maxDif, dp[0][x-1][nxtLeft] - inside[x-1][nxtLeft]);
++nxtLeft;
}
if (testing) cout << " for " << x << " " << j << " have dif " << maxDif << " giving " << insideLeft[x][j] + maxDif << endl;
dp[0][x][j] = max(dp[0][x][j], insideLeft[x][j] + maxDif);
}
}
{ // decreasing
long long maxSum = -INF; // max score + inside right
int nxtLeft = (int)heights[x-1].size()-1;
for (int j = (int)heights[x].size()-1; j >= 0; --j) {
int y = heights[x][j];
while (nxtLeft >= 0 && heights[x-1][nxtLeft] >= y) {
maxSum = max(maxSum, dp[1][x-1][nxtLeft] + insideRight[x-1][nxtLeft]);
--nxtLeft;
}
if (testing) cout << " for " << x << " " << j << " have sum " << maxSum << " giving " << maxSum - inside[x][j] << endl;
dp[1][x][j] = max(dp[1][x][j], maxSum - inside[x][j]);
}
}
{ // after local maximum
size_t j1 = heights[x-1].size()-1;
int h1 = heights[x-1][j1];
for (size_t j = 0; j < heights[x].size() && heights[x][j] <= h1; ++j) {
long long score = max(dp[0][x-1][j1], dp[1][x-1][j1]);
score += insideRight[x-1][j1] - inside[x][j];
dp[1][x][j] = max(dp[1][x][j], score);
if (heights[x][j] == h1) dp[0][x][j] = max(dp[0][x][j], score);
}
}
if (x > 1) { // after local minimum
// case: column before 0 is higher than column after
long long maxSum = 0;
for (size_t j = 0; j < heights[x-2].size(); ++j) {
maxSum = max(maxSum, max(dp[0][x-2][j], dp[1][x-2][j]) + insideRight[x-2][j]);
}
for (size_t j = 0; j < heights[x].size(); ++j) {
dp[0][x][j] = max(dp[0][x][j], maxSum);
if (!j) dp[1][x][j] = max(dp[1][x][j], maxSum);
}
// case: column after 0 is higher than column before
long long maxScore = 0;
for (size_t j = 0; j < heights[x-2].size(); ++j) {
maxScore = max(maxScore, max(dp[0][x-2][j], dp[1][x-2][j]));
}
for (size_t j = 0; j < heights[x].size(); ++j) {
dp[0][x][j] = max(dp[0][x][j], maxScore + insideLeft[x][j]);
if (!j) dp[1][x][j] = max(dp[1][x][j], maxScore + insideLeft[x][j]);
}
}
for (size_t j = 0; j < heights[x].size(); ++j) {
ans = max(ans, max(dp[0][x][j], dp[1][x][j]));
}
}
return ans;
}
