Submission #696563

#TimeUsernameProblemLanguageResultExecution timeMemory
696563BobCompetitiveProgrammingCatfish Farm (IOI22_fish)C++17
0 / 100
145 ms36764 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...