#include "fish.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
vector<vector<pair<int, ll>>> fishes;
vector<map<int, ll>> prefixWeight;
vector<ll> totals;
inline ll weightSum(int x, int y1, int y2) {
if (x >= fishes.size() || y2 <= y1)
return 0;
auto it1 = prefixWeight[x].upper_bound(y2 - 1);
auto it2 = prefixWeight[x].upper_bound(y1 - 1);
ll res = (--it1)->second - (--it2)->second;
//cout << x << ' ' << y1 << ' ' << y2 << " = " << res << endl;
return res;
}
long long max_weights(signed N, signed M, vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
fishes = vector<vector<pair<int, ll>>>(N);
loop(i, M) {
fishes[X[i]].push_back({Y[i], W[i]});
}
fishes.push_back({});
prefixWeight = vector<map<int, ll>>(N + 1);
totals = vector<ll>(N + 1);
loop(x, N + 1) {
sort(all(fishes[x]));
ll total = 0;
prefixWeight[x][-2] = 0;
for (auto [y, w] : fishes[x]) {
total += w;
prefixWeight[x][y] = total;
}
totals[x] = total;
}
vector<map<int, ll>> beforeDp(N);
vector<map<int, ll>> bothDp(N);
vector<ll> maxBefore(N);
vector<ll> maxBoth(N);
//bestBefore, bestBeforeAndAfter
int counter = 0;
loop(x, N) {
if (x == 0) {
for (const auto& [y, w] : fishes[x + 1]) {
bothDp[0][y + 1] = weightSum(x + 1, 0, y + 1);
maxBoth[x] = max(maxBoth[x], bothDp[0][y + 1]);
}
beforeDp[0][0] = 0;
maxBefore[0] = 0;
continue;
}
ll bestBefore2 = 0;
if (x >= 2) {
bestBefore2 = maxBefore[x - 2];
}
if (x >= 3) {
bestBefore2 = max(bestBefore2, maxBoth[x - 3]);
}
for (const auto& [y, w] : fishes.at(x - 1)) {
int height = y + 1;
ll& both = bothDp[x][height];
ll& before = beforeDp[x][height];
both = LLONG_MIN;
before = LLONG_MIN;
for (const auto& [prevHeight, prevScore] : beforeDp.at(x - 1)) {
counter++;
//ll prevCur = weightSum(x - 1, prevHeight, height);
ll prevCur = -weightSum(x - 1, 0, prevHeight);
both = max(both, prevScore + prevCur);
before = max(before, prevScore + prevCur);
}
both += weightSum(x - 1, 0, height);
before += weightSum(x - 1, 0, height);
for (const auto& [prevY, prevScore] : bothDp.at(x - 1)) {
counter++;
if (prevY <= height)
continue;
ll prevCur = -weightSum(x, 0, height);
both = max(both, prevScore + prevCur);
}
ll prevWeight = weightSum(x - 1, 0, height);
both = max(both, bestBefore2 + prevWeight);
before = max(before, bestBefore2 + prevWeight);
maxBefore[x] = max(maxBefore[x], before);
}
for (const auto& [y, w] : fishes.at(x + 1)) {
int height = y + 1;
ll& both = bothDp[x][height];
both = LLONG_MIN;
for (const auto& [prevHeight, prevScore] : beforeDp.at(x - 1)) {
counter++;
ll prevCur = weightSum(x - 1, prevHeight, height);
both = max(both, prevScore + prevCur);
}
for (const auto& [prevY, prevScore] : bothDp.at(x - 1)) {
counter++;
if (prevY <= height)
continue;
ll prevCur = -weightSum(x, 0, height);
both = max(both, prevScore + prevCur);
}
ll prevWeight = weightSum(x - 1, 0, height);
both = max(both, bestBefore2 + prevWeight);
}
for (const auto& [height, score] : bothDp.at(x)) {
counter++;
ll nextWeight = weightSum(x + 1, 0, height);
bothDp[x][height] += nextWeight;
maxBoth[x] = max(maxBoth[x], bothDp[x][height]);
}
ll& both = bothDp[x][0];
ll& before = beforeDp[x][0];
both = max({ both, maxBefore[x - 1], bestBefore2 });
before = max(before, both);
maxBefore[x] = max(maxBefore[x], before);
maxBoth[x] = max(maxBoth[x], both);
}
//cout << "Counter: " << counter << endl;
ll res = 0;
loop(x, N) {
for (auto [y, score] : beforeDp[x]) {
res = max(res, score);
}
for (auto [y, score] : bothDp[x]) {
res = max(res, score);
}
}
return res;
}
Compilation message
towers.cpp:1:10: fatal error: fish.h: No such file or directory
1 | #include "fish.h"
| ^~~~~~~~
compilation terminated.
