#include<cstdio>
#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
long long dp_right[260000],dp_left[260000],sum;
int pointer;
multiset<long long,greater<long long> > trash;
multiset<long long> sel;
void dpopt_right(int tl,int tr,int left,int right,int start,int attraction[])
{
int mid=(tl+tr)/2;
if(tl>tr)
return;
if(sel.size()<mid-left+start)
{
while(sel.size()<mid-left+start&&!trash.empty())
{
sum+=*trash.begin();
sel.insert(*trash.begin());
trash.erase(trash.begin());
}
}
if(sel.size()>mid-left+start)
{
while(sel.size()>mid-left+start)
{
sum-=*sel.begin();
trash.insert(*sel.begin());
sel.erase(sel.begin());
}
}
dp_right[mid]=sum;
int max_ind=left;
pointer=left+1;//need this?
for(;pointer<=right&&mid-pointer+start>0;pointer++)
{
sel.insert(attraction[pointer]);
sum+=attraction[pointer];
while(sel.size()>mid-pointer+start)
{
sum-=*sel.begin();
trash.insert(*sel.begin());
sel.erase(sel.begin());
}
if(dp_right[mid]<sum)
{
max_ind=pointer;
dp_right[mid]=sum;
}
}
pointer-=1;
if(tl==tr)
return;
for(;pointer>max_ind;pointer--)
{
if(sel.find(attraction[pointer])==sel.end())
trash.erase(trash.find(attraction[pointer]));
else
{
sum-=attraction[pointer];
sel.erase(sel.find(attraction[pointer]));
}
}
dpopt_right(mid+1,tr,max_ind,right,start,attraction);
for(;pointer>left;pointer--)
{
if(sel.find(attraction[pointer])==sel.end())
trash.erase(trash.find(attraction[pointer]));
else
{
sum-=attraction[pointer];
sel.erase(sel.find(attraction[pointer]));
}
}
dpopt_right(tl,mid-1,left,max_ind,start,attraction);
}
void dpopt_left(int tl,int tr,int left,int right,int start,int attraction[])
{
if(start==-1||tl>tr)
return;
int mid=(tl+tr)/2;
if(sel.size()<mid-(start-right)*2)
{
while(sel.size()<mid-(start-right)*2&&!trash.empty())
{
sum+=*trash.begin();
sel.insert(*trash.begin());
trash.erase(trash.begin());
}
}
if(sel.size()>mid-(start-right)*2)
{
while(sel.size()>mid-(start-right)*2)
{
sum-=*sel.begin();
trash.insert(*sel.begin());
sel.erase(sel.begin());
}
}
dp_left[mid+2]=sum;
int max_ind=right;
pointer=right-1;
for(;pointer>=left&&mid-(start-pointer)*2>0;pointer--)
{
sel.insert(attraction[pointer]);
sum+=attraction[pointer];
while(sel.size()>mid-(start-pointer)*2)
{
sum-=*sel.begin();
trash.insert(*sel.begin());
sel.erase(sel.begin());
}
if(dp_left[mid+2]<sum)
{
max_ind=pointer;
dp_left[mid+2]=sum;
}
}
pointer++;
if(tl==tr)
return;
for(;pointer<max_ind;pointer++)
{
if(sel.find(attraction[pointer])==sel.end())
trash.erase(trash.find(attraction[pointer]));
else
{
sum-=attraction[pointer];
sel.erase(sel.find(attraction[pointer]));
}
}
dpopt_left(mid+1,tr,left,max_ind,start,attraction);
for(;pointer<right;pointer++)
{
if(sel.find(attraction[pointer])==sel.end())
trash.erase(trash.find(attraction[pointer]));
else
{
sum-=attraction[pointer];
sel.erase(sel.find(attraction[pointer]));
}
}
dpopt_left(tl,mid-1,max_ind,right,start,attraction);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
long long ret=0;
sel.insert(attraction[start]);
pointer=start;
sum=attraction[start];
dpopt_right(1,d,start,n-1,start,attraction);
if(start!=0)
{
sel.clear();
trash.clear();
sel.insert(attraction[start-1]);
sum=attraction[start-1];
pointer=start-1;
dpopt_left(1,d-2,0,start-1,start-1,attraction);
}
for(int i=0;i<=d;i++)
{
ret=max(ret,dp_right[i]+dp_left[d-i]);
//printf("%lld %lld\n",dp_right[i],dp_left[d-i]);
}
for(int i=0;i<n-i-1;i++)
{
long long tmp=attraction[i];
attraction[i]=attraction[n-i-1];
attraction[n-i-1]=tmp;
}
start=n-1-start;
sel.clear();
trash.clear();
sel.insert(attraction[start]);
pointer=start;
sum=attraction[start];
dpopt_right(1,d,start,n-1,start,attraction);
if(start!=0)
{
sel.clear();
trash.clear();
sel.insert(attraction[start-1]);
sum=attraction[start-1];
pointer=start-1;
dpopt_left(1,d-2,0,start-1,start-1,attraction);
}
else
for(int i=0;i<=d;i++)
dp_left[i]=0;
for(int i=0;i<=d;i++)
ret=max(ret,dp_right[i]+dp_left[d-i]);
for(int i=0;i<=d;i++)
{
ret=max(ret,dp_right[i]+dp_left[d-i]);
//printf("%lld %lld\n",dp_right[i],dp_left[d-i]);
}
return ret;
}
Compilation message
holiday.cpp: In function 'void dpopt_right(int, int, int, int, int, int*)':
holiday.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sel.size()<mid-left+start)
~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:16:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sel.size()<mid-left+start&&!trash.empty())
~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sel.size()>mid-left+start)
~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:25:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sel.size()>mid-left+start)
~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sel.size()>mid-pointer+start)
~~~~~~~~~~^~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'void dpopt_left(int, int, int, int, int, int*)':
holiday.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sel.size()<mid-(start-right)*2)
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sel.size()<mid-(start-right)*2&&!trash.empty())
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sel.size()>mid-(start-right)*2)
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:93:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sel.size()>mid-(start-right)*2)
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:107:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(sel.size()>mid-(start-pointer)*2)
~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2425 ms |
8760 KB |
Output is correct |
| 2 |
Correct |
1231 ms |
8944 KB |
Output is correct |
| 3 |
Correct |
2565 ms |
8936 KB |
Output is correct |
| 4 |
Correct |
1319 ms |
8664 KB |
Output is correct |
| 5 |
Correct |
4125 ms |
7384 KB |
Output is correct |
| 6 |
Correct |
1335 ms |
4824 KB |
Output is correct |
| 7 |
Correct |
2282 ms |
4416 KB |
Output is correct |
| 8 |
Correct |
2481 ms |
5096 KB |
Output is correct |
| 9 |
Correct |
879 ms |
5108 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
62 ms |
764 KB |
Output is correct |
| 2 |
Correct |
34 ms |
632 KB |
Output is correct |
| 3 |
Correct |
29 ms |
632 KB |
Output is correct |
| 4 |
Correct |
48 ms |
632 KB |
Output is correct |
| 5 |
Correct |
42 ms |
596 KB |
Output is correct |
| 6 |
Correct |
11 ms |
376 KB |
Output is correct |
| 7 |
Correct |
9 ms |
348 KB |
Output is correct |
| 8 |
Correct |
10 ms |
376 KB |
Output is correct |
| 9 |
Correct |
10 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2422 ms |
10352 KB |
Output is correct |
| 2 |
Correct |
3298 ms |
10156 KB |
Output is correct |
| 3 |
Correct |
324 ms |
1528 KB |
Output is correct |
| 4 |
Correct |
25 ms |
376 KB |
Output is correct |
| 5 |
Correct |
8 ms |
376 KB |
Output is correct |
| 6 |
Correct |
10 ms |
376 KB |
Output is correct |
| 7 |
Correct |
10 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2482 ms |
4832 KB |
Output is correct |
| 9 |
Correct |
2455 ms |
4652 KB |
Output is correct |
