#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef map<ll, ll> mii;
typedef vector<mii> vmii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const ll INF = 3e5 * 1e9 + 100;
void updateIdx(ll y, ll &ny, vpii::iterator &itpref0, ll &pref0)
{
while (itpref0->first <= y)
{
pref0 = itpref0->second;
++itpref0;
}
ny = min(itpref0->first, ny);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
vvpii grid(N + 4); // becomes prefix grid
for (int x = 0; x < sz(grid); ++x)
grid[x].push_back({0, 0});
for (int i = 0; i < M; ++i)
grid[X[i] + 3].push_back({Y[i] + 1, W[i]}); // Transformation in Y Richtung...
for (int x = 0; x < sz(grid); ++x)
sort(all(grid[x]));
for (int x = 0; x < sz(grid); ++x)
{
ll pref = 0;
for (int i = 0; i < sz(grid[x]); ++i)
{
grid[x][i].second += pref;
pref = grid[x][i].second;
}
grid[x].push_back({N + 1, pref});
}
vvpii dpg(sz(grid)); // growth stack thing
vvpii dp(sz(grid)); // normal all dp
vi dpm(sz(grid), 0); // maximum einer Spaltes
for (int i = 0; i < 3; ++i)
{
dp[i].push_back({0, 0});
dp[i].push_back({N + 1, 0});
dpg[i].push_back({0, 0});
dpg[i].push_back({N + 1, 0});
}
for (int x = 3; x < sz(grid) - 1; ++x) // so i choose the borders
{
ll c1 = -INF, c2 = -INF; // running variables for case 1 and 2 // TODO: INIT
ll ndp = 0, ndpg = 0;
dp[x].push_back({0, 0}), dpg[x].push_back({0, 0});
ll y = 1, ny;
ll pref0 = 0, pref1 = 0, pref2 = 0, dp0 = 0, dpg1 = 0;
auto itpref0 = grid[x - 1].begin(); // idx for pref x-1
auto itpref1 = grid[x].begin(); // idx for pref x
auto itpref2 = grid[x + 1].begin(); // idx for pref x+1
auto itdp0 = dp[x - 2].begin(); // idx for dp x-2
auto itdpg1 = dpg[x - 1].begin(); // idx for dpg x-1
while (y <= N)
{
// update indices
ny = INT_MAX;
updateIdx(y, ny, itpref0, pref0);
updateIdx(y, ny, itpref1, pref1);
updateIdx(y, ny, itpref2, pref2);
updateIdx(y, ny, itdp0, dp0);
updateIdx(y, ny, itdpg1, dpg1);
// Case 1 - last tower in x-1 and smaller y
c1 = max(c1, dpg1 - pref0 - pref1);
ndpg = max(ndpg, pref0 + pref2 + c1);
// Case 2 - last tower in x-2 and smaller y
c2 = max(c2, dp0 - pref0);
ndpg = max(ndpg, pref0 + pref2 + c2);
// Case 3 - last tower in x-1 and larger y (or if it is smaller, case 1 performs better)
// here the last tower might be larger than the current one
ndp = max(ndp, dpm[x - 1] - pref1 + pref2);
// Case 4 - Last Tower in x-2 and larger y (or if it is smaller, case 2 performs better)
ndpg = max(ndpg, dpm[x - 2] + pref2);
// Case 5 - Last Tower in x-3
ndpg = max(ndpg, dpm[x - 3] + pref0 + pref2);
// keep track for dpg & dpm
ndp = max(ndp, ndpg);
dpm[x] = max(dpm[x], ndp);
if (ndpg != dpg[x].back().second)
dpg[x].push_back({y, ndpg});
if (ndp != dp[x].back().second)
dp[x].push_back({y, ndp});
y = ny;
}
dp[x].push_back({N + 1, dp[x].back().second});
dpg[x].push_back({N + 1, dpg[x].back().second});
}
return *max_element(all(dpm));
}
