/* todo: debug */
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
int sz[N];
vector<int> v[N];
vector<pair<int, int>> my[N];
vector<ll> dpinc[N];
vector<ll> dpdec[N];
vector<ll> pref[N];
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
std::vector<int> w) {
for (int i = 1; i <= n; i++)
v[i].push_back(0);
for (int i = 0; i < m; i++) {
x[i]++; y[i]++;
v[x[i] - 1].push_back(y[i]);
v[x[i] + 1].push_back(y[i]);
v[x[i]].push_back(y[i]);
my[x[i]].emplace_back(y[i], w[i]);
}
for (int i = 1; i <= n; i++) {
sort(v[i].begin(), v[i].end());
v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
sz[i] = (int) v[i].size();
dpinc[i].resize(sz[i]);
dpdec[i].resize(sz[i]);
pref[i].resize(sz[i]);
for (auto& p : my[i]) {
int idx = (int) (lower_bound(v[i].begin(), v[i].end(), p.first) - v[i].begin());
pref[i][idx] += p.second;
}
for (int j = 1; j < sz[i]; j++) pref[i][j] += pref[i][j - 1];
}
{
// build dpdec 1
int ptr = 0;
ll s = 0;
for (int j = 0; j < sz[1]; j++) {
while (ptr < sz[2] && v[2][ptr] <= v[1][j]) {
s = pref[2][ptr];
ptr++;
}
dpdec[1][j] = s;
}
}
for (int i = 2; i <= n; i++) {
{
// inc -> inc
ll mx = 0;
ll s = 0;
int ptr = 0;
for (int j = 0; j < sz[i]; j++) {
while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
s = pref[i - 1][ptr];
mx = max(mx, dpinc[i - 1][ptr] - pref[i - 1][ptr]);
ptr++;
}
dpinc[i][j] = mx + s;
}
}
{
// dec -> dec
ll mx = 0;
int ptr = sz[i - 1];
for (int j = sz[i] - 1; j >= 0; j--) {
while (ptr >= 0 && v[i - 1][ptr] >= v[i][j]) {
mx = max(mx, dpdec[i - 1][ptr]);
ptr++;
}
dpdec[i][j] = mx - pref[i][j];
}
}
{
// my inc -> my dec
for (int j = 0; j < sz[i]; j++) dpdec[i][j] = max(dpdec[i][j], dpinc[i][j]);
}
{
// add right to dpdec
int ptr = 0;
ll s = 0;
for (int j = 0; j < sz[i]; j++) {
while (ptr < sz[i + 1] && v[i + 1][ptr] <= v[i][j]) {
s = pref[i + 1][ptr];
ptr++;
}
dpdec[i][j] += s;
}
}
if (i > 2) {
// connect with i - 2
{
// i - 2 is greater
ll mx = 0;
for (int j = 0; j < sz[i - 2]; j++) mx = max(mx, dpdec[i - 2][j]);
int ptr = 0;
ll s = 0;
for (int j = 0; j < sz[i]; j++) {
while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
s = pref[i - 1][ptr];
ptr++;
}
dpdec[i][j] = max(dpdec[i][j], mx - s);
}
}
{
ll mx = 0;
int ptr = 0;
ll s = 0;
for (int j = 0; j < sz[i - 2]; j++) {
while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i - 2][j]) {
s = pref[i - 1][ptr];
ptr++;
}
mx = max(mx, dpdec[i - 2][j] - s);
}
ptr = 0;
s = 0;
for (int j = 0; j < sz[i]; j++) {
while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
s = pref[i - 1][ptr];
ptr++;
}
dpdec[i][j] = max(dpdec[i][j], mx + s);
}
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < sz[i]; j++)
ans = max(ans, dpdec[i][j]);
return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
124 ms |
111560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
53 ms |
71820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
98032 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
71756 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
71756 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
71756 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
98032 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
124 ms |
111560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
