#pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=1e5+5;
int n;
ll dp[mxn];
int a[mxn];
int d;
int st;
int L,R;
multiset<ll> S;
multiset<ll> T;
ll sum=0;
int len=0;
void init(){
L=0,R=n-1;
len=-1;
sum=0;
S.clear();
T.clear();
for(int i=0;i<n;i++){
len++;
if(i<st) len++;
sum+=a[i];
S.insert(a[i]);
}
while(!S.empty() and (int)S.size()>d-len){
sum-=*S.begin();
T.insert(*S.begin());
S.erase(S.begin());
}
}
void sir(int l,int r){
while(L>l){
L--;
len++;
if(L<st) len++;
sum+=a[L];
S.insert(a[L]);
while(!S.empty() and (int)S.size()>d-len){
sum-=*S.begin();
T.insert(*S.begin());
S.erase(S.begin());
}
}
while(R<r){
R++;
len++;
if(R<st) len++;
sum+=a[R];
S.insert(a[R]);
while(!S.empty() and (int)S.size()>d-len){
sum-=*S.begin();
T.insert(*S.begin());
S.erase(S.begin());
}
}
while(L<l){
len--;
if(L<st) len--;
if(S.find(a[L])!=S.end()){
S.erase(S.find(a[L]));
sum-=a[L];
}
else if(T.find(a[L])!=T.end()){
T.erase(T.find(a[L]));
}
while(!T.empty() and (int)S.size()<d-len){
sum+=*T.rbegin();
S.insert(*T.rbegin());
T.erase(prev(T.end()));
}
L++;
}
while(R>r){
len--;
if(R<st) len--;
if(S.find(a[R])!=S.end()){
S.erase(S.find(a[R]));
sum-=a[R];
}
else if(T.find(a[R])!=T.end()){
T.erase(T.find(a[R]));
}
while(!T.empty() and (int)S.size()<d-len){
sum+=*T.rbegin();
S.insert(*T.rbegin());
T.erase(prev(T.end()));
}
R--;
}
}
void go(int l,int r,int tl,int tr){
if(l>r) return;
int mid=(l+r)/2;
int best=tr;
for(int i=tr;i>=tl;i--){
sir(i,mid);
if(sum>dp[mid]){
dp[mid]=sum;
best=i;
}
}
go(l,mid-1,tl,best);
go(mid+1,r,best,tr);
}
long long findMaxAttraction(int N, int start, int D, int attraction[]) {
d=D;
n=N;
st=start;
for(int i=0;i<n;i++){
a[i]=attraction[i];
}
init();
go(st,n-1,0,st);
ll ans=dp[st];
dp[st]=0;
reverse(a,a+n);
reverse(dp,dp+n);
st=n-st-1;
init();
go(st,n-1,0,st);
for(int i=0;i<n;i++){
//cout<<dp[i]<<' ';
ans=max(ans,dp[i]);
}
return ans;
}
/*signed main() {_
auto S=clock();
int q,qq,qqq;
cin>>q>>qq>>qqq;
int qqqq[q];
for(int i=0;i<q;i++){
cin>>qqqq[i];
}
cout<<findMaxAttraction(q,qq,qqq,qqqq);
return 0;
}*/
//maybe its multiset not set
Compilation message
holiday.cpp: In function 'void setIO(std::string)':
holiday.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
696 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
6736 KB |
Output is correct |
2 |
Correct |
181 ms |
6732 KB |
Output is correct |
3 |
Correct |
169 ms |
6736 KB |
Output is correct |
4 |
Correct |
186 ms |
6732 KB |
Output is correct |
5 |
Correct |
454 ms |
6256 KB |
Output is correct |
6 |
Correct |
72 ms |
2372 KB |
Output is correct |
7 |
Correct |
193 ms |
3772 KB |
Output is correct |
8 |
Correct |
292 ms |
4372 KB |
Output is correct |
9 |
Correct |
46 ms |
1900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
904 KB |
Output is correct |
2 |
Correct |
4 ms |
852 KB |
Output is correct |
3 |
Correct |
5 ms |
852 KB |
Output is correct |
4 |
Correct |
29 ms |
864 KB |
Output is correct |
5 |
Correct |
28 ms |
840 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
8 ms |
760 KB |
Output is correct |
8 |
Correct |
7 ms |
724 KB |
Output is correct |
9 |
Correct |
7 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
7360 KB |
Output is correct |
2 |
Correct |
169 ms |
7400 KB |
Output is correct |
3 |
Correct |
565 ms |
3756 KB |
Output is correct |
4 |
Correct |
25 ms |
860 KB |
Output is correct |
5 |
Correct |
8 ms |
724 KB |
Output is correct |
6 |
Correct |
9 ms |
696 KB |
Output is correct |
7 |
Correct |
8 ms |
756 KB |
Output is correct |
8 |
Correct |
2028 ms |
7356 KB |
Output is correct |
9 |
Correct |
2073 ms |
7368 KB |
Output is correct |