# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
932812 | 2024-02-24T09:32:29 Z | vjudge1 | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; #define F first #define S second #define ll long long #define int ll #define pb push_back #define sz(s) (int)s.size() #define pii pair<int,int> #define all(v) v.begin(),v.end() #define mem(a,i) memset(a,i,sizeof(a)) #define in insert #define lb lower_bound #define ub upper_bound #define y1 yy #define ppb pop_back #define ull unsigned ll const int MAX=1e5+55; const int inf=1e9; const int N=2e5; const int C=331; const int C1=431; const int mod=1e9+9; const int mod1=1e9+9; #include "holiday.h" int dpL[MAX],dpR[MAX]; int dp1L[MAX],dp1R[MAX]; int findMaxAttraction(int n, int start, int d, int attraction[]) { if(start==0){ multiset<int> st; int ans=0; int cur=0; for(int i=0;i<n;i++){ st.in(attraction[i]); cur+=attraction[i]; while(!st.empty()&&sz(st)>d-i){ cur-=*st.begin(); st.erase(st.begin()); } ans=max(ans,cur); } return ans; } for(int ds=0;ds<=d;ds++){ multiset<int> st; int ans=0; int cur=0; for(int i=start;i<n;i++){ st.in(attraction[i]); cur+=attraction[i]; while(!st.empty()&&sz(st)>ds-(i-start)){ cur-=*st.begin(); st.erase(st.begin()); } ans=max(ans,cur); } dpR[ds]=ans; st.clear(); ans=cur=0; for(int i=start;i<n;i++){ st.in(attraction[i]); cur+=attraction[i]; while(!st.empty()&&sz(st)>ds-2*(i-start)){ cur-=*st.begin(); st.erase(st.begin()); } ans=max(ans,cur); } dp1R[ds]=ans; } for(int ds=0;ds<=d;ds++){ multiset<int> st; int ans=0; int cur=0; for(int i=start-1;i>=0;i--){ st.in(attraction[i]); cur+=attraction[i]; while(!st.empty()&&sz(st)>ds-(start-i-1)){ cur-=*st.begin(); st.erase(st.begin()); } ans=max(ans,cur); } dpL[ds]=ans; st.clear(); ans=cur=0; for(int i=start-1;i>=0;i--){ st.in(attraction[i]); cur+=attraction[i]; while(!st.empty()&&sz(st)>ds-2*(start-i-1)){ cur-=*st.begin(); st.erase(st.begin()); } ans=max(ans,cur); } dp1L[ds]=ans; } // cout<<dpR[4]<<"\n"; int ans=0; for(int i=0;i<=d;i++){ ans=max(ans,dpR[i]+dp1L[d-i-1]); ans=max(ans,dp1R[i]+dpL[d-i-1]); } return ans; }