#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "fish.h"
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
using ll = long long;
ll solve(vector<vector<pair<int, ll>>> &fish, int n)
{
ll res = 0;
vector<vector<ll>> dp0(fish.size()), dp1(fish.size());
ll sum = 0;
for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
for (int i = 0; i < fish.size(); ++i)
{
fish[i].emplace_back(n, 0);
dp0[i].resize(fish[i].size());
ll mx = 0;
if (i != 0)
{
for (int j = 0; j < fish[i - 1].size(); ++j)
{
mx = max(mx, dp1[i - 1][j]);
}
fill(dp0[i].begin(), dp0[i].end(), mx);
mx = 0;
}
for (int j = 0, k = 0; j < fish[i].size(); ++j)
{
if (i != 0)
{
while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
{
mx = max(mx, dp0[i - 1][k]);
mx += fish[i - 1][k].second;
++k;
}
}
dp0[i][j] = max(mx, dp0[i][j]);
}
dp1 = dp0;
if (i != 0)
{
ll mx = 0;
for (int j = (int)fish[i].size() - 1, k = (int)fish[i - 1].size() - 1; j >= 0; --j)
{
while (k >= 0 && fish[i - 1][k].first > fish[i][j].first)
{
mx = max(mx, dp1[i - 1][k]);
--k;
}
mx += fish[i][j].second;
dp1[i][j] = max(dp1[i][j], mx);
res = max(dp1[i][j], res);
}
}
}
return res;
}
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{
vector<tuple<int, int, ll>> xyw(m);
for (int i = 0; i < m; ++i) xyw[i] = {X[i], Y[i], W[i]};
sort(xyw.begin(), xyw.end());
ll res = 0;
vector<vector<pair<int, ll>>> tos;
int prevX = -1;
ll sum = 0;
vector<ll> a(n);
for (auto [x, y, w] : xyw)
{
a[x] = w;
sum += w;
if (x > prevX + 1)
{
tos.push_back(vector<pair<int, ll>>());
//res += solve(tos, n);
tos.clear();
tos.push_back(vector<pair<int, ll>>());
prevX = x - 1;
}
if (x == prevX + 1)
{
tos.push_back(vector<pair<int, ll>>());
}
tos.back().emplace_back(y, w);
prevX = x;
}
if (prevX != n - 1) tos.push_back(vector<pair<int, ll>>());
res += solve(tos, n);
//assert(res <= sum);
return res;
}
/*
5 6
4 2 1
2 0 2
2 2 4
2 4 8
4 3 16
2 1 32
*/
/*
5 5
0 0 4
1 0 8
2 0 5
3 0 1
4 0 9
*/
