#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi22/debug.h"
#else
#define debug(...) void(37)
#endif
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vector<int> ord(M);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
return pair{X[x], Y[x]} < pair{X[y], Y[y]};
});
vector<pair<int, vector<array<int, 2>>>> gs;
vector<vector<long long>> pref;
gs.emplace_back(-1, vector<array<int, 2>>{});
pref.push_back(vector<long long>{0});
for (int i = 0; i < M; ++i) {
if (i == 0 || X[ord[i - 1]] != X[ord[i]]) {
gs.emplace_back(X[ord[i]], vector<array<int, 2>>{});
pref.push_back(vector<long long>{0});
}
gs.back().second.push_back({Y[ord[i]], W[ord[i]]});
pref.back().push_back(pref.back().back() + W[ord[i]]);
}
gs.emplace_back(N, vector<array<int, 2>>{});
pref.push_back(vector<long long>{0});
debug(gs, pref);
const long long inf = (long long) 1e16;
vector<long long> inc(1);
vector<long long> dec(1, -inf);
vector<long long> valley(1, -inf);
long long ans = 0;
for (int i = 1; i < int(gs.size()); ++i) {
auto& a = gs[i].second;
//auto& next = gs[i + 1].second;
auto& prev = gs[i - 1].second;
int s = int(a.size());
debug(a, prev);
//int next_s = int(next.size());
int prev_s = int(prev.size());
vector<long long> new_inc(s + 1);
vector<long long> new_dec(s + 1);
vector<long long> new_valley(s + 1);
vector<int> need(s + 1);
for (int j = 0; j < s; ++j) {
int p = need[j];
while (p < prev_s && prev[p][0] < a[j][0]) {
++p;
}
need[j + 1] = p + 1;
}
vector<int> takes(s + 1);
for (int j = 0; j < s; ++j) {
int p = takes[j];
while (p < prev_s && prev[p][0] <= a[j][0]) {
++p;
}
takes[j + 1] = p;
}
takes.back() = prev_s;
debug(need, takes);
if (gs[i].first != gs[i - 1].first + 1) {
long long mx = 0;
for (auto x : valley) {
mx = max(mx, x + pref[i - 1].back());
}
for (int j = 0; j <= prev_s; ++j) {
mx = max(mx, pref[i - 1].back() - pref[i - 1][j] + inc[j]);
}
ans += mx;
for (int j = 0; j <= s; ++j) {
new_valley[j] = 0;
}
for (int j = 0; j <= s; ++j) {
new_dec[j] = pref[i].back() - pref[i][j];
}
for (int j = 0; j <= s; ++j) {
new_inc[j] = 0;
}
debug(ans, new_valley, new_dec, new_inc);
} else {
//valley case
{
int p = prev_s;
long long mx = -inf;
for (int j = s; j >= 0; --j) {
while (p >= need[j]) {
mx = max(mx, dec[p]);
--p;
}
new_valley[j] = mx;
}
}
//inc
{
{
long long mx = 0;
long long val = 0;
int p = 0;
for (int j = 0; j <= s; ++j) {
while (p <= takes[j]) {
mx = max(mx, inc[p] - pref[i - 1][p]);
val = max(val, valley[p]);
++p;
}
new_inc[j] = max(new_inc[j], max(val, mx) + pref[i - 1][takes[j]]);
}
}
debug(new_inc);
{
int p = prev_s;
long long down = 0;
for (int j = s; j >= 0; --j) {
while (p >= takes[j]) {
down = max(down, valley[p] + pref[i - 1][p]);
--p;
}
new_inc[j] = max(new_inc[j], down);
}
}
}
//dec
{
int p = prev_s;
long long prev_mx = -inf;
for (int j = s; j >= 0; --j) {
while (p >= need[j]) {
prev_mx = max(prev_mx, dec[p] + pref[i][j]);
--p;
}
new_dec[j] = prev_mx - pref[i][j];
}
}
debug(new_valley);
debug(new_dec);
debug(new_inc);
}
swap(inc, new_inc);
swap(dec, new_dec);
swap(valley, new_valley);
}
//dont forget the end case
long long add = 0;
debug(ans);
return ans + dec[0];
}
Compilation message
towers.cpp:1:10: fatal error: fish.h: No such file or directory
1 | #include "fish.h"
| ^~~~~~~~
compilation terminated.
