#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
struct segtree {
private:
struct node {
int maxd;
};
node single(int v) {
return {v};
}
node neutral = {INT_MIN};
node merge(node a, node b) {
return {max(a.maxd, b.maxd)};
}
public:
int size;
V<node> query;
void init(int n) {
size = 1;
while (size < n)size *= 2;
query.assign(2 * size, neutral);
}
void build(V<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size()) {
query[x] = single(a[lx]);
}
return;
}
int m = (lx + rx) / 2;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
query[x] = merge(query[2 * x + 1], query[2 * x + 2]);
}
void build(V<int> &a) {
build(a, 0, 0, size);
}
node calc(int l, int r, int x, int lx, int rx) {
if (lx >= r || rx <= l)
return neutral;
if (l <= lx && rx <= r)
return query[x];
int m = (lx + rx) / 2;
node a = calc(l, r, 2 * x + 1, lx, m);
node b = calc(l, r, 2 * x + 2, m, rx);
return merge(a, b);
}
int calc(int l, int r) {
return calc(l, r, 0, 0, size).maxd;
}
};
int max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
vector<vector<int >> grid(N + 1, vector<int>(N + 1, 0));
for (int i = 0; i < M; i++) {
grid[X[i]][Y[i] + 1] += W[i];
}
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
grid[i][j] += grid[i][j - 1];
}
}
V<V<V<int>>> dp(N, V<V<int>>(N + 1, V<int>(N + 1, 0)));
V<V<V<int>>> vp(N, V<V<int>>(N + 1, V<int>(N + 1, 0)));
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
dp[0][i][j] = max(0, grid[0][j] - grid[0][i]);
vp[0][i][j] = dp[0][i][j] + max(0, grid[1][i] - grid[1][j]);
}
}
for (int i = 1; i < N; i++) {
for (int j = 0; j <=N; j++) {
V<int> a;
for (int g = 0; g <=N; g++)
a.pb(dp[i - 1][g][j]);
segtree tree_dp;
tree_dp.init(N + 1);
tree_dp.build(a);
V<int> b;
for (int g = 0; g <= N; g++)
b.pb(vp[i - 1][g][j]);
segtree tree_vp;
tree_vp.init(N + 1);
tree_vp.build(b);
for (int g = 0; g <= N; g++) {
if (g <= j) {
dp[i][j][g] = tree_vp.calc(0, N + 1);
} else {
dp[i][j][g] = max(tree_dp.calc(0, g + 1) + grid[i][g] - grid[i][j], tree_vp.calc(g, N + 1));
}
vp[i][j][g] = dp[i][j][g] + max(0, grid[i + 1][j] - grid[i + 1][g]);
}
}
}
int ans = INT_MIN;
for (int i = 0; i <= N; i++) {
ans = max(ans, dp[N - 1][i][0]);
}
return ans;
}
Compilation message
fish.cpp: In member function 'void segtree::build(std::vector<int>&, int, int, int)':
fish.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if (lx < a.size()) {
| ~~~^~~~~~~~~~
fish.cpp: At global scope:
fish.cpp:64:5: error: ambiguating new declaration of 'int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)'
64 | int max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
| ^~~~~~~~~~~
In file included from fish.cpp:1:
fish.h:3:11: note: old declaration 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)'
3 | long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
| ^~~~~~~~~~~
