#include "fish.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
using namespace std;
const int N_MAX = 1e5 + 11;
const int INC = 0;
const int DEC = 1;
const int ZERO = 2;
vector<pair<int, long long>> fish[N_MAX];
int N;
void chmax(long long& x, long long y){
x = max(x, y);
}
long long g(int x, int y){ // [x, x] times [0, y)
if(x < 0 || x >= N) return 0;
auto ptr = lower_bound(fish[x].begin(), fish[x].end(), pair<int, long long>{y, -1LL});
if(ptr == fish[x].begin()) return 0;
return (--ptr)->se;
}
vector<long long> dp[N_MAX][3];
vector<int> sp[N_MAX];
int L[N_MAX];
int at(int x, int y){
if(y < sp[x].size())
return sp[x][y];
return 1 << 30;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
::N = N;
for(int i = 0; i < M; i++) X[i]++;
for(int i = 0; i < M; i++){
fish[X[i]].push_back({Y[i], W[i]});
}
for(int i = 1; i <= N; i++){
sort(fish[i].begin(), fish[i].end());
for(int j = 1; j < fish[i].size(); j++){
fish[i][j].se += fish[i][j - 1].se;
}
}
for(int i = 0; i < M; i++){
int x = X[i], y = Y[i];
sp[x].push_back(y + 1);
if(x > 0) sp[x - 1].push_back(y + 1);
if(x < N - 1) sp[x + 1].push_back(y + 1);
}
for(int i = 0; i <= N; i++){
sp[i].push_back(0);
sort(sp[i].begin(), sp[i].end());
sp[i].resize(unique(sp[i].begin(), sp[i].end()) - sp[i].begin());
for(int j = 0; j < 3; j++){
dp[i][j].resize(sp[i].size());
fill(all(dp[i][j]), -1E18);
}
L[i] = sp[i].size();
}
dp[0][ZERO][0] = 0;
for(int x = 1; x <= N; x++){
// ZERO
{
for(int y = 0; y < L[x - 1]; y++){
chmax(dp[x][ZERO][0], dp[x - 1][ZERO][y]);
}
int y1 = 0;
for(int y2 = 0; y2 < L[x]; y2++){
while (at(x - 1, y1) <= at(x, y2)) {
chmax(dp[x][ZERO][y2], dp[x - 1][INC][y1]);
chmax(dp[x][ZERO][y2], dp[x - 1][DEC][y1]);
y1++;
}
}
for(int y = 0; y < L[x] - 1; y++){
chmax(dp[x][ZERO][y + 1], dp[x][ZERO][y]);
}
}
long long value = -(1LL << 60);
// INC
{
int y1 = 0;
for(int y2 = 0; y2 < L[x]; y2++){
while (at(x - 1, y1) <= at(x, y2)) {
chmax(value, dp[x - 1][INC][y1] - g(x, at(x - 1, y1)) - g(x - 1, at(x - 1, y1)));
y1++;
}
chmax(dp[x][INC][y2], value + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
}
value = -(1LL << 60);
y1 = 0;
for(int y2 = 0; y2 < L[x]; y2++){
while (at(x - 1, y1) <= at(x, y2)) {
chmax(value, dp[x - 1][ZERO][y1] - g(x - 1, at(x - 1, y1)));
y1++;
}
chmax(dp[x][INC][y2], dp[x - 1][ZERO][y2] - g(x - 1, at(x, y2)) + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
chmax(dp[x][INC][y2], value + g(x + 1, at(x, y2)) + g(x - 1, at(x, y2)));
}
}
// DEC
{
value = -(1LL << 60);
int y1 = L[x - 1] - 1;
for(int y2 = L[x] - 1; y2 >= 0; y2--){
while (y1 >= 0 && at(x - 1, y1) >= at(x, y2)) {
chmax(value, dp[x - 1][DEC][y1]); chmax(value, dp[x - 1][INC][y1]);
y1--;
}
chmax(dp[x][DEC][y2], value + g(x + 1, at(x, y2)) - g(x, at(x, y2)));
}
}
}
long long ans = 0;
for(int k = 0; k < 3; k++){
for(int y = 0; y < L[N]; y++){
ans = max(ans, dp[N][k][y]);
}
}
return ans;
}
Compilation message
fish.cpp: In function 'int at(int, int)':
fish.cpp:34:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if(y < sp[x].size())
| ~~^~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int j = 1; j < fish[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
35072 KB |
Output is correct |
| 2 |
Correct |
142 ms |
38976 KB |
Output is correct |
| 3 |
Correct |
35 ms |
24900 KB |
Output is correct |
| 4 |
Correct |
35 ms |
24916 KB |
Output is correct |
| 5 |
Incorrect |
404 ms |
68360 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '1571252609096450358' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11988 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 |
Correct |
31 ms |
24916 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
24916 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
1st lines differ - on the 1st token, expected: '3', found: '50' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
1st lines differ - on the 1st token, expected: '3', found: '50' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
1st lines differ - on the 1st token, expected: '3', found: '50' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
24916 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
24916 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
35072 KB |
Output is correct |
| 2 |
Correct |
142 ms |
38976 KB |
Output is correct |
| 3 |
Correct |
35 ms |
24900 KB |
Output is correct |
| 4 |
Correct |
35 ms |
24916 KB |
Output is correct |
| 5 |
Incorrect |
404 ms |
68360 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '1571252609096450358' |
| 6 |
Halted |
0 ms |
0 KB |
- |
