#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 3e5 + 1;
vector<ll> dp[MAX_N];
vector<ll> up[MAX_N];
vector<ll> down[MAX_N];
vector<ll> sum[MAX_N];
vector<int> h[MAX_N];
// f(rom), j'th block of x=i place
ll ps(int i, int j, int f) {
int H = h[i][j+1] - 1;
int idx = upper_bound(h[f].begin(), h[f].end(), H) - h[f].begin();
return sum[f][idx];
}
// ub() is minimum exceeding h
int ub(int i, int j, int f) {
int H = h[i][j+1];
int idx = upper_bound(h[f].begin(), h[f].end(), H) - h[f].begin();
return idx;
}
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for (int i=0; i<m; ++i) h[X[i]].push_back(Y[i]);
for (int i=0; i<n; ++i) {
h[i].push_back(n);
sort(h[i].begin(), h[i].end());
int sz = h[i].size() + 1;
dp[i].resize(sz, 0);
up[i].resize(sz, 0);
down[i].resize(sz, 0);
sum[i].resize(sz, 0);
}
for (int i=0; i<m; ++i) {
int y = lower_bound(h[X[i]].begin(), h[X[i]].end(), Y[i]) - h[X[i]].begin() + 1;
sum[X[i]][y] = W[i];
}
for (int i=0; i<n; ++i) {
for (int j=1; j<h[i].size(); ++j) {
sum[i][j] += sum[i][j-1];
}
}
// i = 1
{
int N = h[1].size(), n1 = h[0].size();
vector<ll> ps1(n1+2, 0), ps2(n1+1);
ps2[0] = up[0][0];
for (int j=n1; j>=0; --j) ps1[j] = max(ps1[j+1], dp[0][j] + ps(0, j, 1));
for (int j=1; j<=n1; ++j) ps2[j] = max(ps2[j-1], up[0][j] - sum[0][j]);
for (int j=0; j<=N; ++j) {
down[1][j] = ps1[ub(1, j, 0)] - sum[1][j];
up[1][j] = ps2[ub(1, j, 0)-1] + ps(1, j, 0);
dp[1][j] = max(down[1][j], up[1][j]);
}
}
for (int i=2; i<n; ++i) {
int N = h[i].size(), n1 = h[i-1].size(), n2 = h[i-2].size();
vector<ll> ps1(n1+2, 0), ps2(n1+1), ps3(n2+1), ps4(n2+2, 0);
ps2[0] = up[i-1][0];
ps3[0] = dp[i-2][0];
for (int j=n1; j>=0; --j) ps1[j] = max(ps1[j+1], dp[i-1][j] + ps(i-1, j, i));
for (int j=1; j<=n1; ++j) ps2[j] = max(ps2[j-1], up[i-1][j] - sum[i-1][j]);
for (int j=1; j<=n2; ++j) ps3[j] = max(ps3[j-1], dp[i-2][j]);
for (int j=n2; j>=0; --j) ps4[j] = max(ps4[j+1], dp[i-2][j] + ps(i-2, j, i-1));
for (int j=0; j<=N; ++j) {
down[i][j] = ps1[ub(i, j, i-1)] - sum[i][j];
up[i][j] = ps4[ub(i, j, i-2)];
if (ub(i, j, i-1) > 0) up[i][j] = max(up[i][j], ps2[ub(i, j, i-1)-1] + ps(i, j, i-1));
if (ub(i, j, i-2) > 0) up[i][j] = max(up[i][j], ps3[ub(i, j, i-2)-1] + ps(i, j, i-1));
dp[i][j] = max(down[i][j], up[i][j]);
}
}
ll ans = *max_element(dp[n-1].begin(), dp[n-1].end());
return ans;
}
Compilation message
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int j=1; j<h[i].size(); ++j) {
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
56940 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
35492 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
51164 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
35504 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
35504 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
35504 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
51164 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
56940 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
