#include <bits/stdc++.h>
using namespace std; using ll=int;
#define all(x) begin(x), end(x)
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
map<array<ll,2>, ll> fish; // Row sorted
for(ll i=0; i<M; ++i) fish[{Y[i], X[i]}] = W[i];
vector<map<ll,ll>> prefix(N);
for(auto& f : fish){
ll y=f.first[0], x=f.first[1], w=f.second;
auto it = prefix[x].end();
if(!prefix[x].size())
prefix[x][y]=w;
else
prefix[x][y]=w+prev(prefix[x].end())->first;
}
map<array<ll, 2>, ll> dp, prev;
prev[{0, 1}]=0; // Prev height and state [1: increasing, -1: decreasing, -5/-6: peak] = ans.
// -5 previously increased, -6 previously decreased.
set<array<ll,2>> vis;
ll ret=0;
for(ll i=0; i<N; ++i){
//cout << endl << endl;
if(!prefix[i].size()) continue;
for(auto& e : prev){
if(vis.count(e.first)) continue;
vis.insert(e.first);
// cout <<e.first[0] << " state : "<< e.first[1] << " ans : " << e.second << endl;
ll prevHeight=e.first[0], state=e.first[1], curr_ans=e.second;
ll taken=0;
ret=max(ret, curr_ans);
if(i && prefix[i-1].size()){
auto iter=(prefix[i-1].upper_bound(prevHeight))--;
ll taken=iter->second;
}
if(state==1){
dp[{0, 1}]=curr_ans;
dp[{N-1, -1}]=curr_ans+((prefix[i].upper_bound(N-1))--)->second - taken;
auto it=prefix[i].lower_bound(prevHeight);
while(it != prefix[i].end()){
ll currHeight=it->first;
currHeight-=1;
if(currHeight==prevHeight) dp[{currHeight, -5}]=curr_ans;
else {
ll new_ans=curr_ans+((prefix[i].upper_bound(currHeight))--)->second - taken;
dp[{currHeight, 1}]=new_ans;
dp[{currHeight, -1}]=new_ans;
}
++it;
}
} else if(state==-1){
dp[{0, 1}]=curr_ans;
auto it=prefix[i].lower_bound(prevHeight);
while(it != prefix[i].begin()){
ll currHeight=it->first;
if(currHeight==prevHeight) dp[{currHeight, -6}]=curr_ans;
else {
ll new_ans=curr_ans+max((ll)0,((prefix[i].upper_bound(currHeight))--)->second - taken);
dp[{currHeight, 1}]=new_ans;
dp[{currHeight, -1}]=new_ans;
}
--it;
}
} else { // state:saddle;
if(state==-5){ // was increasing
state=-1;
dp[{0, 1}]=curr_ans;
auto it=prefix[i].lower_bound(prevHeight);
while(it != prefix[i].begin()){
ll currHeight=it->first;
if(currHeight!=prevHeight) {
dp[{currHeight, state}]=curr_ans;
}
--it;
}
} else if(state==-6){ // was decreasing
state=1;
dp[{N-1, -1}]=curr_ans+((prefix[i].upper_bound(N-1))--)->second - taken;;
auto it=prefix[i].lower_bound(prevHeight);
while(it != prefix[i].end()){
ll currHeight=it->first;
if(currHeight!=prevHeight) {
dp[{currHeight, state}]=curr_ans+((prefix[i].upper_bound(currHeight))--)->second - taken;
}
++it;
}
}
}
}
prev=dp;
dp.clear();
vis.clear();
}
return ret;
}
Compilation message
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:13:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
13 | auto it = prefix[x].end();
| ^~
fish.cpp:45:20: warning: unused variable 'taken' [-Wunused-variable]
45 | ll taken=iter->second;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
36764 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 |
0 ms |
212 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 |
3 ms |
4948 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 |
1 ms |
212 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 |
1 ms |
212 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 |
1 ms |
212 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 |
3 ms |
4948 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 |
145 ms |
36764 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
