#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 10;
vector<int> cand[N];
vector<pii> fish[N];
vector<ll> fish_cum[N];
vector<pii> dp[N];
int fin_index(int id, int h){
int ii = lower_bound(cand[id].begin(), cand[id].end(), h) - cand[id].begin();
if(ii >= cand[id].size() || cand[id][ii] != h) return -1;
else return ii;
}
void maxi(ll &u, ll v){
u=max(u, v);
}
ll get_sum(int id, ll pre){
int jj = lower_bound(fish[id].begin(), fish[id].end(), mp(pre + 1, -1ll)) - fish[id].begin();
jj -- ;
if(jj < 0) return 0ll;
return fish_cum[id][jj];
}
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for(auto &x : X){
x ++ ;
} // assume x is in range [1; n]
for(int i = 0 ; i < m ; i ++ ){
if(Y[i] > 0){
cand[X[i]].push_back(Y[i] - 1);
}
fish[X[i]].push_back(mp(Y[i], W[i]));
}
ll tot;
for(int i = 0; i <= n; i ++ ){
cand[i].push_back(n - 1);
cand[i].push_back(-1);
sort(cand[i].begin(), cand[i].end());
dp[i].resize(cand[i].size(), mp(-(ll)1e18, -(ll)1e18));
sort(fish[i].begin(), fish[i].end());
for(auto x : fish[i]){
tot = x.se;
if(!fish_cum[i].empty()) tot += fish_cum[i].back();
fish_cum[i].push_back(tot);
}
}
dp[0][0] = mp(0ll,0ll);
ll meow = 0ll;
// .fi means increasing direction, .se means decreasing direction
int las;
ll val;
int pp;
ll take;
ll current;
for(int i = 1; i <= n; i ++){
// ----------------- SAME HEIGHT HANDLING -----------
for(int j = 0 ;j < cand[i].size(); j ++ ){
las = fin_index(i - 1, cand[i][j]);
if(las != -1){
val = max(dp[i - 1][las].fi, dp[i - 1][las].se);
maxi(dp[i][j].fi, val);
maxi(dp[i][j].se, val);
}
}
// DECREASING HEIGHT HANDLING
pp = cand[i].size() - 2;
take = 0ll;
for(int j = cand[i].size() - 1; j >= 0 ; j -- ){
while(pp >= 0 && cand[i - 1][pp] > cand[i][j]){
maxi(take, max(dp[i - 1][pp].fi, dp[i - 1][pp].se) + get_sum(i, cand[i - 1][pp]));
pp -- ;
}
current = take - get_sum(i, cand[i][j]);
maxi(dp[i][j].se, current);
}
// INCREASING HEIGHT HANDLING
pp = 0; // transition from 0 is different
take = -(ll)1e18;
for(int j = 0; j < cand[i].size(); j ++ ){
while(pp < cand[i - 1].size() && cand[i - 1][pp] < cand[i][j]){
maxi(take, dp[i - 1][pp].fi - get_sum(i - 1, cand[i - 1][pp]));
pp ++ ;
}
current = take + get_sum(i - 1, cand[i][j]);
maxi(dp[i][j].fi, current);
maxi(dp[i][j].se, current);
maxi(meow, dp[i][j].fi);
maxi(meow, dp[i][j].se);
}
// INCREASING HEIGHT IF PREV IS EMPTY
pp = 0;
take = 0ll;
for(int j = 0 ; j < cand[i].size(); j ++ ){
while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] < cand[i][j]){
maxi(take, dp[i - 2][pp].fi);
maxi(take, dp[i - 2][pp].se);
pp ++ ;
}
current = take + get_sum(i - 1, cand[i][j]);
maxi(dp[i][j].fi, current);
maxi(dp[i][j].se, current);
}
if(i >= 2){
pp = cand[i - 2].size() - 1;
take = 0ll;
for(int j = cand[i].size() - 1; j >= 0 ; j -- ){
while(pp >= 0 && cand[i - 2][pp] > cand[i][j]){
maxi(take, max(dp[i - 2][pp].fi, dp[i - 2][pp].se) + get_sum(i - 1, cand[i - 2][pp]));
pp -- ;
}
maxi(dp[i][j].fi, take);
maxi(dp[i][j].se, take);
}
}
/*
for(int j = 0 ; j < cand[i].size(); j ++ ){
cout << "(" << cand[i][j] << ": " << dp[i][j].fi << "," << dp[i][j].se << ") ";
}
cout << "\n";
*/
}
return meow;
}
Compilation message
fish.cpp: In function 'int fin_index(int, int)':
fish.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | if(ii >= cand[id].size() || cand[id][ii] != h) return -1;
| ~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int j = 0 ;j < cand[i].size(); j ++ ){
| ~~^~~~~~~~~~~~~~~~
fish.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int j = 0; j < cand[i].size(); j ++ ){
| ~~^~~~~~~~~~~~~~~~
fish.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | while(pp < cand[i - 1].size() && cand[i - 1][pp] < cand[i][j]){
| ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int j = 0 ; j < cand[i].size(); j ++ ){
| ~~^~~~~~~~~~~~~~~~
fish.cpp:114:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] < cand[i][j]){
| ~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
23532 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '55466559120977' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9696 KB |
Output is correct |
| 2 |
Incorrect |
145 ms |
30624 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '463985234342812' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
17416 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
17464 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 |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9692 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9700 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
9700 KB |
1st lines differ - on the 1st token, expected: '8866', found: '7755' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9692 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9700 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
9700 KB |
1st lines differ - on the 1st token, expected: '8866', found: '7755' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9692 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9700 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
9700 KB |
1st lines differ - on the 1st token, expected: '8866', found: '7755' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
17416 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
17464 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 |
72 ms |
23532 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '55466559120977' |
| 2 |
Halted |
0 ms |
0 KB |
- |
