#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())
void selfmax(ll& a, ll b)
{
a = max(a, b);
}
const int maxN = 100'000;
vpll fish[1 + maxN];
vll fishpref[1 + maxN];
vll tot(1 + maxN, 0);
ll max_weights(int N, int M, vi X, vi Y, vi W)
{
vvll sm(2, vll(N, 0));
for(int j = 0; j < M; j++)
if(X[j] < 2)
sm[X[j]][Y[j]] += W[j];
if(N == 2)
{
return max(sm[0][0] + sm[0][1], sm[1][0] + sm[1][1]);
}
int xmx = 0;
for(int j = 0; j < M; j++)
{
X[j]++;
xmx = max(xmx, X[j] + 2);
Y[j]++;
}
xmx = min(xmx, N);
// cerr << "xmx = " << xmx << '\n';
vpll fish[1+N];
ll* fishpref[1+N];
vpii fishbyY[1+N];
for(int j = 0; j < M; j++)
{
// fish[X[j]].push_back({Y[j], W[j]});
fishbyY[Y[j]].push_back({X[j], W[j]});
tot[X[j]] += W[j];
}
for(int y = 0; y <= N; y++)
for(pii z : fishbyY[y])
fish[z.first].push_back({y, z.second});
for(int r = 1; r <= xmx; r++)
{
fish[r].push_back({N+1, 0});
// sort(fish[r].begin(), fish[r].end());
if(fish[r][0].first != 1)
{
fish[r].insert(fish[r].begin(), {1, 0});
}
fishpref[r] = new ll[sz(fish[r])];
for(int i = 0; i < sz(fishpref[r]); i++)
{
fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second;
}
}
fish[0] = vpll{{0, 0}};
fishpref[0] = vll{0};
vvll inc(1+N), dec(1+N);
vvll incpref(1+N), decpref(1+N); //pref inc dec mx
inc[0] = dec[0] = vll{0};
// cerr << "done\n";
for(int r = 1; r <= xmx; r++)
{
incpref[r-1] = inc[r-1];
decpref[r-1] = dec[r-1];
for(int i = 1; i < sz(fish[r-1]); i++)
{
incpref[r-1][i] = max(incpref[r-1][i-1], inc[r-1][i]);
decpref[r-1][i] = max(decpref[r-1][i-1], dec[r-1][i]);
}
inc[r] = dec[r] = vll(sz(fish[r]), 0);
vll Csuff;
if(r >= 2)
{
Csuff = vll(sz(fish[r-2]));
int pi = sz(fish[r-1])-1;
ll pwt = tot[r-1];
for(int j = sz(fish[r-2])-1; j >= 0; j--)
{
while(pi >= 0 && fish[r-1][pi].first > fish[r-2][j].first - 1)
{
pwt -= fish[r-1][pi].second;
pi--;
}
// Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1);
Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + pwt;
if(j+1 < sz(fish[r-2]))
selfmax(Csuff[j], Csuff[j+1]);
}
}
ll Dmx = 0;
ll Did = -1;
int ppi = -1;
int qi = -1;
ll qwt = 0;
for(int i = 0; i < sz(fish[r]); i++)
{
ll basic = 0;
ll Bcatch = 0;
int Bk = -1;
while(qi+1 < sz(fish[r-1]) && fish[r-1][qi+1].first <= fish[r][i].first - 1)
{
qi++;
qwt += fish[r-1][qi].second;
}
ll prevpwt = qwt;
ll constD = -(tot[r-1] - prevpwt) + tot[r-1];
if(r >= 2)
{
//A
selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + prevpwt);
while(ppi+1 < sz(fish[r-2]) && fish[r-2][ppi+1].first <= fish[r][i].first)
ppi++;
int ploci = ppi;
while(Bk+1 < sz(fish[r-1]) && fish[r-1][Bk+1].first <= fish[r][i].first - 1)
{
Bk++;
Bcatch += fish[r-1][Bk].second;
}
selfmax(basic, Bcatch + max(incpref[r-2][ploci], decpref[r-2][ploci]));
if(ploci+1 < sz(fish[r-2]))
{
// cerr << ploci << " : " << sz(fish[r-2]) << '\n';
selfmax(basic, Csuff[ploci+1]);
}
}
selfmax(inc[r][i], basic);
selfmax(dec[r][i], basic);
//type D transition
while(Did+1 < sz(fish[r-1]) && fish[r-1][Did+1].first <= fish[r][i].first)
{
Did++;
Dmx = max(Dmx, inc[r-1][Did] - (Did >= 1 ? fishpref[r-1][Did-1] : 0));
}
selfmax(inc[r][i], Dmx + constD);
selfmax(dec[r][i], Dmx + constD);
}
int j = sz(fish[r-1]);
ll bestval = -1'000'000'000'000'000'000LL;
int ri = sz(fish[r]);
ll rwt = 0;
for(int i = sz(fish[r])-1; i >= 0; i--)
{
while(j-1 >= 0 && fish[r-1][j-1].first > fish[r][i].first)
{
j--;
while(ri-1 >= 0 && fish[r][ri-1].first >= fish[r-1][j].first)
{
ri--;
rwt += fish[r][ri].second;
}
bestval = max(bestval, dec[r-1][j] + tot[r] - rwt);
}
selfmax(dec[r][i], bestval - (i >= 1 ? fishpref[r][i-1] : 0));
}
}
ll res = 0;
for(vll x : inc)
for(ll y : x)
res = max(res, y);
for(vll x : dec)
for(ll y : x)
res = max(res, y);
return res;
}
Compilation message
fish.cpp: In function 'll max_weights(int, int, vi, vi, vi)':
fish.cpp:15:21: error: request for member 'size' in 'fishpref[r]', which is of non-class type 'll*' {aka 'long long int*'}
15 | #define sz(x) int(x.size())
| ^~~~
fish.cpp:79:22: note: in expansion of macro 'sz'
79 | for(int i = 0; i < sz(fishpref[r]); i++)
| ^~
fish.cpp:86:16: error: cannot convert 'vll' {aka 'std::vector<long long int>'} to 'll*' {aka 'long long int*'} in assignment
86 | fishpref[0] = vll{0};
| ^~~~~~
| |
| vll {aka std::vector<long long int>}
