#define ll long long
#define pll pair<ll, ll>
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct fish
{
ll height;
ll weight;
ll below;
ll above; //Sums of weights in column
ll bigPier; //No bigger pier in the previous column -> first one to be caught
ll noPier; //No pier in this column -> first one to be caught
ll smallPier; //Bigger pier in the previous column -> first one not below a pier
};
bool operator < (fish a, fish b)
{
return (a.height < b.height);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W)
{
bool sub1 = true;
bool sub2 = true;
bool sub3 = true;
for(ll i = 0; i < M; i++)
{
if(X[i] % 2 == 1)
{
sub1 = false;
}
if(X[i] > 1)
{
sub2 = false;
}
if(Y[i] != 0)
{
sub3 = false;
}
}
if(sub1)
{
ll sum = 0;
for(int i : W)
{
sum += (ll) i;
}
return sum;
}
if(sub2)
{
vector<pll> left(0);
vector<pll> right(0); //Height, weight
ll lsum = 0;
ll rsum = 0;
for(ll i = 0; i < M; i++)
{
if(X[i] == 0)
{
left.push_back({Y[i], W[i]});
lsum += W[i];
}
else
{
right.push_back({Y[i], W[i]});
rsum += W[i];
}
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
ll output = max(lsum, rsum);
if(N > 2)
{
ll lindex = -1;
ll rindex = -1;
ll shadow = 0;
ll roof = 0;
for(ll i = 0; i < N; i++)
{
while(lindex+1 < (ll) left.size() && left[lindex+1].first <= i)
{
lindex++;
shadow += left[lindex].second;
}
while(rindex+1 < (ll) right.size() && right[rindex+1].first <= i)
{
rindex++;
roof += right[rindex].second;
}
output = max(output, shadow + rsum - roof);
}
}
return output;
}
if(sub3)
{
vector<ll> w(N, 0);
for(ll i = 0; i < M; i++)
{
w[X[i]] = W[i];
}
vector<vector<ll>> dp(N, vector<ll> (3, 0)); //Pier, no pier + uncaught, no pier + caught
for(ll i = 1; i < N; i++)
{
//Pier:
dp[i][0] = dp[i-1][0];
dp[i][0] = max(dp[i][0], dp[i-1][1]+w[i-1]);
dp[i][0] = max(dp[i][0], dp[i-1][2]);
//no pier + uncaught:
dp[i][1] = dp[i-1][1];
dp[i][1] = max(dp[i][1], dp[i-1][2]);
//no pier + caught:
dp[i][2] = dp[i-1][0]+w[i];
}
return max(max(dp[N-1][0], dp[N-1][1]), dp[N-1][2]);
}
vector<vector<fish>> grid(N, vector<fish> (0));
for(ll i = 0; i < M; i++)
{
fish f;
f.height = Y[i];
f.weight = W[i];
f.bigPier = 0;
f.smallPier = 0;
f.noPier = 0;
grid[X[i]].push_back(f);
}
fish top, bottom;
top.height = N;
top.weight = 0;
top.noPier = 0;
top.bigPier = 0;
top.smallPier = 0;
bottom.height = -1;
bottom.weight = 0;
bottom.smallPier = 0;
bottom.bigPier = 0;
bottom.noPier = 0;
for(ll i = 0; i < N; i++)
{
grid[i].push_back(top);
grid[i].push_back(bottom);
sort(grid[i].begin(), grid[i].end());
ll sum = 0;
for(ll j = 0; j < (ll) grid[i].size(); j++)
{
grid[i][j].below = sum;
sum += grid[i][j].weight;
}
sum = 0;
for(ll j = grid[i].size()-1; j >= 0; j--)
{
grid[i][j].above = sum;
sum += grid[i][j].weight;
}
}
for(ll i = 0; i < (ll) grid[0].size(); i++)
{
grid[0][i].bigPier = 0;
grid[0][i].smallPier = 0;
grid[0][i].noPier = 0;
}
for(ll i = 1; i < N; i++)
{
//no pier:
ll preind = 0;
ll postind = 0;
ll premax = 0;
while(preind < (ll) grid[i-1].size())
{
while(postind < (ll) grid[i].size() && grid[i-1][preind].height >= grid[i][postind].height)
{
grid[i][postind].noPier = max(grid[i-1][preind].bigPier, grid[i-1][preind].smallPier)+grid[i][postind].below;
postind++;
}
premax = max(premax, grid[i-1][preind].noPier);
preind++;
}
for(ll j = 0; j < (ll) grid[i].size(); j++)
{
grid[i][j].noPier = max(grid[i][j].noPier, premax);
}
//calculate DP[i][j]:
for(ll j = 0; j < (ll) grid[i].size(); j++)
{
//bigPier
grid[i][j].bigPier = 0;
ll sum = 0;
ll index = grid[i-1].size()-1; //Index of first lower fish in previous column
while(index >= 0 && grid[i-1][index].height > grid[i][j].height)
{
index--;
}
if(index >= 0 && grid[i-1][index].height == grid[i][j].height)
{
grid[i][j].bigPier = max(grid[i-1][index].bigPier, max(grid[i-1][index].noPier, 0LL));
index--;
}
while(index >= 0)
{
sum += grid[i-1][index].weight;
grid[i][j].bigPier = max(grid[i][j].bigPier, max(grid[i-1][index].bigPier, grid[i-1][index].noPier)+sum);
index--;
}
//smallPier
grid[i][j].smallPier = 0;
sum = grid[i][j].weight;
index = 0;
ll shadowIndex = j;
while(index < (ll) grid[i-1].size() && grid[i-1][index].height <= grid[i][j].height)
{
index++;
}
while(index < (ll) grid[i-1].size())
{
while(shadowIndex+1 < (ll) grid[i].size() && grid[i][shadowIndex+1].height < grid[i-1][index].height)
{
shadowIndex++;
sum += grid[i][shadowIndex].weight;
}
grid[i][j].smallPier = max(grid[i][j].smallPier, max(grid[i-1][index].bigPier, grid[i-1][index].smallPier)+sum);
index++;
}
}
}
ll output = 0;
for(fish f : grid[N-1])
{
ll val = max(max(f.noPier, f.bigPier), f.smallPier);
output = max(output, val);
}
return output;
}
