#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 F[N][2];
ll Q[N];
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]));
Q[X[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)1e16, -(ll)1e16));
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 - 1].size() - 1;
take = 0ll;
for(int j = cand[i].size() - 1; j >= 0 ; j -- ){
while(pp >= 0 && cand[i - 1][pp] > cand[i][j]){
ll A = max(dp[i - 1][pp].fi, dp[i - 1][pp].se);
ll B = get_sum(i, cand[i - 1][pp]);
current = (ll)max(dp[i - 1][pp].fi, dp[i - 1][pp].se) + (ll)get_sum(i, cand[i - 1][pp]);
maxi(take, current);
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);
}
}
/*
cout << i << ": ";
for(int j = 0; j < cand[i].size(); j ++ ){
cout << "(" << cand[i][j] << ": " << dp[i][j].fi << " : " << dp[i][j].se << ") ";
}
cout << "\n";
*/
}
for(int i = 2; i <= n; i ++ ){
// i taken
F[i][1] = max(Q[i - 1] + max(F[i - 2][0], F[i - 2][1]), F[i - 1][1]);
F[i][0] = max(Q[i] + F[i - 1][1], F[i - 1][0]);
}
ll chomp = max(F[n][1], F[n][0]);
//cout << meow << "/" << chomp << "\n";
return chomp;
}
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:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int j = 0 ;j < cand[i].size(); j ++ ){
| ~~^~~~~~~~~~~~~~~~
fish.cpp:89:20: warning: unused variable 'A' [-Wunused-variable]
89 | ll A = max(dp[i - 1][pp].fi, dp[i - 1][pp].se);
| ^
fish.cpp:90:20: warning: unused variable 'B' [-Wunused-variable]
90 | ll B = get_sum(i, cand[i - 1][pp]);
| ^
fish.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j = 0; j < cand[i].size(); j ++ ){
| ~~^~~~~~~~~~~~~~~~
fish.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while(pp < cand[i - 1].size() && cand[i - 1][pp] <= cand[i][j]){
| ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:120:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int j = 0 ; j < cand[i].size(); j ++ ){
| ~~^~~~~~~~~~~~~~~~
fish.cpp:121:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] <= cand[i][j]){
| ~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
23916 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '803213453' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9692 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 |
38 ms |
19020 KB |
Output is correct |
| 2 |
Correct |
28 ms |
19060 KB |
Output is correct |
| 3 |
Correct |
61 ms |
23820 KB |
Output is correct |
| 4 |
Correct |
51 ms |
23180 KB |
Output is correct |
| 5 |
Correct |
93 ms |
30084 KB |
Output is correct |
| 6 |
Correct |
104 ms |
29336 KB |
Output is correct |
| 7 |
Correct |
112 ms |
29920 KB |
Output is correct |
| 8 |
Correct |
89 ms |
29964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 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 |
7 ms |
9684 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 |
7 ms |
9684 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 |
Correct |
38 ms |
19020 KB |
Output is correct |
| 2 |
Correct |
28 ms |
19060 KB |
Output is correct |
| 3 |
Correct |
61 ms |
23820 KB |
Output is correct |
| 4 |
Correct |
51 ms |
23180 KB |
Output is correct |
| 5 |
Correct |
93 ms |
30084 KB |
Output is correct |
| 6 |
Correct |
104 ms |
29336 KB |
Output is correct |
| 7 |
Correct |
112 ms |
29920 KB |
Output is correct |
| 8 |
Correct |
89 ms |
29964 KB |
Output is correct |
| 9 |
Incorrect |
119 ms |
31320 KB |
1st lines differ - on the 1st token, expected: '99999', found: '66666' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
23916 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '803213453' |
| 2 |
Halted |
0 ms |
0 KB |
- |
