#include "fish.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
// <|°_°|>
// M. Broccoli
// The hardest choices require the strongest wills
// What is better - to be born good, or to overcome your evil nature with great effort ?
const int MAX_ROWS = (1e5 + 1);
vector <long long> DP_Built[MAX_ROWS];
vector <long long> DP_Free[MAX_ROWS];
vector <pair <int, long long>> CatFishs[MAX_ROWS];
long long max_weights(int nbRows, int nbCatfishs, vector <int> Col, vector <int> Row,
vector <int> Weight) {
for (int i = 0; i < nbCatfishs; i ++)
{
CatFishs[Col[i] + 1].push_back({Row[i], Weight[i]});
}
for (int i = 0; i <= nbRows; i ++)
{
CatFishs[i].push_back({-1, 0});
if (i)
CatFishs[i].push_back({MAX_ROWS, 0});
sort(CatFishs[i].begin(), CatFishs[i].end());
DP_Built[i].resize(CatFishs[i].size());
DP_Free[i].resize(CatFishs[i].size());
}
DP_Built[0] = {0};
DP_Free[0] = {0};
for (int i = 1; i <= nbRows; i ++)
{
long long maxiFree = - (1LL << 60);
long long maxiBuilt = - (1LL << 60);
int prev = 0;
int sz = CatFishs[i - 1].size();
int curSz = CatFishs[i].size();
for (int fish = 0; fish < curSz - 1; fish ++)
{
while (prev < sz && CatFishs[i - 1][prev].first < CatFishs[i][fish + 1].first)
{
maxiBuilt = max(maxiBuilt, DP_Built[i - 1][prev]);
maxiFree = max(maxiFree, DP_Free[i - 1][prev]);
maxiFree += CatFishs[i - 1][prev ++].second;
}
DP_Built[i][fish] = max(maxiBuilt, maxiFree);
DP_Free[i][fish + 1] = max(maxiBuilt, maxiFree);
}
maxiBuilt = - (1LL << 60);
prev = sz - 1;
for (int fish = curSz - 2; fish >= 0; fish --)
{
while (prev && CatFishs[i - 1][prev].first > CatFishs[i][fish + 1].first)
maxiBuilt = max(maxiBuilt, DP_Built[i - 1][-- prev]);
maxiBuilt += CatFishs[i][fish + 1].second;
DP_Built[i][fish] = max(DP_Built[i][fish], maxiBuilt);
}
prev = 1;
maxiFree = 0;
for (int fish = 1; fish < curSz; fish ++)
{
maxiBuilt = - (1LL << 60);
while (prev < sz && CatFishs[i - 1][prev + 1].first <= CatFishs[i][fish].first)
maxiBuilt = max(maxiBuilt, DP_Built[i - 1][prev ++]);
maxiFree += CatFishs[i][fish - 1].second;
DP_Free[i][fish] = max(DP_Free[i][fish], maxiBuilt + maxiFree);
}
}
long long ans = 0;
for (long long a : DP_Built[nbRows])
ans = max(ans, a);
return ans;
}
