#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1e5 + 100;
vector<ll> dp[N][2], pref[N][3], dp_pref[N], dp_suf[N], dp_pref_max[N]; //pref: 0 : itself, 1 : left one, 2 : right one
vector<int> v[N], p[N];
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w){
for(int i = 0; i < m; ++i){
v[x[i]].pb(i);
if(x[i] > 0) v[x[i] - 1].pb(i);
if(x[i] < n - 1) v[x[i] + 1].pb(i);
}
for(int i = 0; i <= n; ++i){
int s = v[i].size() + 1;
for(int a: v[i]) p[i].pb(y[a] + 1);
sort(p[i].begin(), p[i].end());
for(int k = 0; k < 3; ++k){
pref[i][k].resize(s);
}
dp[i][0].resize(s);
dp[i][1].resize(s);
dp_pref[i].resize(s);
dp_suf[i].resize(s);
dp_pref_max[i].resize(s);
vector<pair<int, int>> all;
for(int a: v[i]) all.pb({y[a] + 1, a});
sort(all.begin(), all.end());
for(pair<int, int> &a: all){
a.first = lower_bound(all.begin(), all.end(), make_pair(a.first, -1)) - all.begin() + 1;
if(x[a.second] == i) pref[i][0][a.first] += w[a.second];
else if(x[a.second] == i - 1) pref[i][1][a.first] += w[a.second];
else pref[i][2][a.first] += w[a.second];
assert(a.first <= s - 1);
}
for(int k = 0; k < 3; ++k)
for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
}
for(int i = 0; i <= n; ++i){
int s = pref[i][0].size();
for(int j = 0; j < s; ++j){
if(i == 0){
dp[i][0][j] = dp[i][1][j] = pref[i][2][j];
continue;
}
dp[i][0][j] = pref[i][2][j];
int pos = upper_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin();
if(i == 1){
dp[i][0][j] += dp_pref[i - 1][pos] + pref[i][1][j];
}else{
int pos2 = upper_bound(p[i - 2].begin(), p[i - 2].end(), p[i][j]) - p[i - 2].begin();
dp[i][0][j] += max({dp_pref[i - 1][pos] + pref[i][1][j],
dp_suf[i - 2][0],
dp_pref_max[i - 2][pos2] + pref[i][1][j]
});
}
int pos3 = lower_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin();
dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos3 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos3]);
}
for(int j = 0; j < s; ++j){
if(j == 0){
dp_pref[i][j] = dp[i][0][j] - pref[i][2][j] - pref[i][0][j];
dp_pref_max[i][j] = max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j];
}
else{
dp_pref[i][j] = max(dp_pref[i][j - 1], dp[i][0][j] - pref[i][2][j] - pref[i][0][j]);
dp_pref_max[i][j] = max(dp_pref_max[i][j - 1], max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j]);
}
}
for(int j = s - 1; j >= 0; --j){
if(j == s - 1){
dp_suf[i][j] = max(dp[i][0][j], dp[i][1][j]);
}
else{
dp_suf[i][j] = max({dp_suf[i][j + 1], dp[i][0][j], dp[i][1][j]});
}
}
}
return dp_suf[n][0];
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos3 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos3]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
153 ms |
120616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48012 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
98768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
47948 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
47948 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
47948 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
98768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
153 ms |
120616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
