# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
589408 |
2022-07-04T15:30:47 Z |
yutabi |
Holiday (IOI14_holiday) |
C++14 |
|
5000 ms |
15184 KB |
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll subtask(int n, int start, int d, int attraction[])
{
ll ans=attraction[0];
multiset <int> st;
st.insert(attraction[0]);
ll sum=attraction[0];
for(int i=1;i<n;i++)
{
sum+=attraction[i];
st.insert(attraction[i]);
while(st.size()>d-i)
{
sum-=*(st.begin());
st.erase(st.begin());
}
//printf("%lld\n",sum);
ans=max(ans,sum);
}
return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
if(d==0)
{
return 0;
}
if(start==0)
{
return subtask(n,start,d,attraction);
}
ll left_low[4*n];
ll left_high[4*n];
ll right_low[4*n];
ll right_high[4*n];
for(int i=0;i<=d;i++)
{
left_low[i]=left_high[i]=right_low[i]=right_high[i]=0;
}
multiset <int> st;
for(int i=start-1;i>=0;i--)
{
st.insert(-attraction[i]);
int j=1;
ll sum=0;
for(multiset <int>::iterator it=st.begin();it!=st.end();j++,it++)
{
sum+=-(*it);
left_low[(start-i)+j]=max(left_low[(start-i)+j],sum);
left_high[(start-i)*2+j]=max(left_high[(start-i)*2+j],sum);
}
}
st.clear();
for(int i=start+1;i<n;i++)
{
st.insert(-attraction[i]);
int j=1;
ll sum=0;
for(multiset <int>::iterator it=st.begin();it!=st.end();j++,it++)
{
sum+=-(*it);
right_low[(i-start)+j]=max(right_low[(i-start)+j],sum);
right_high[(i-start)*2+j]=max(right_high[(i-start)*2+j],sum);
}
}
for(int i=1;i<4*n;i++)
{
left_low[i]=max(left_low[i],left_low[i-1]);
left_high[i]=max(left_high[i],left_high[i-1]);
right_low[i]=max(right_low[i],right_low[i-1]);
right_high[i]=max(right_high[i],right_high[i-1]);
}
ll best=0;
for(int i=0;i<=d;i++)
{
best=max(best,max(left_low[i]+right_high[d-i],left_high[i]+right_low[d-i]));
}
for(int i=0;i<d;i++)
{
best=max(best,max(left_low[i]+right_high[d-i-1]+attraction[start],left_high[i]+right_low[d-i-1]+attraction[start]));
}
return best;
}
Compilation message
holiday.cpp: In function 'll subtask(int, int, int, int*)':
holiday.cpp:32:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | while(st.size()>d-i)
| ~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 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 |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
5356 KB |
Output is correct |
2 |
Correct |
30 ms |
5384 KB |
Output is correct |
3 |
Correct |
28 ms |
5300 KB |
Output is correct |
4 |
Correct |
28 ms |
5272 KB |
Output is correct |
5 |
Correct |
28 ms |
3664 KB |
Output is correct |
6 |
Correct |
9 ms |
1968 KB |
Output is correct |
7 |
Correct |
16 ms |
2764 KB |
Output is correct |
8 |
Correct |
18 ms |
2600 KB |
Output is correct |
9 |
Correct |
6 ms |
1620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
1152 KB |
Output is correct |
2 |
Correct |
23 ms |
1108 KB |
Output is correct |
3 |
Correct |
22 ms |
1204 KB |
Output is correct |
4 |
Correct |
21 ms |
1128 KB |
Output is correct |
5 |
Correct |
19 ms |
1108 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
3 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5039 ms |
15184 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |