#include"holiday.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,x,i,j,ki[8080],ka[8080],a[101010],has;
long long int findMaxAttraction(int N, int start, int D, int attraction[])
{
n=N;
x=start;
for(i=0;i<n;i++)
a[i]=attraction[i];
if(x==0)
{
ll hz=0,sz=0;
priority_queue<ll> pq;
for(i=0;i<min(n,(ll)D);i++)
{
pq.push(-a[i]);
hz+=a[i];
sz++;
while(sz>(D-i))
{
sz--;
hz+=pq.top();
pq.pop();
}
has=max(has,hz);
}
return has;
}
for(i=x+1;i<n;i++)
{
vector<ll> tem;
for(j=x+1;j<=i;j++)
tem.pb(a[j]);
sort(tem.begin(),tem.end());
reverse(tem.begin(),tem.end());
ll hz=0;
for(j=0;j<tem.size();j++)
{
hz+=tem[j];
ka[j+(i-x)+1]=max(ka[j+(i-x)+1],hz);
}
}
for(i=x-1;i>=0;i--)
{
vector<ll> tem;
for(j=x-1;j>=i;j--)
tem.pb(a[j]);
sort(tem.begin(),tem.end());
reverse(tem.begin(),tem.end());
ll hz=0;
for(j=0;j<tem.size();j++)
{
hz+=tem[j];
ki[j+(x-i)+1]=max(ki[j+(x-i)+1],hz);
}
}
for(i=1;i<=D;i++)
{
ki[i]=max(ki[i-1],ki[i]);
ka[i]=max(ka[i-1],ka[i]);
}
has=max(has,ki[D]);
has=max(has,ka[D]);
if(D>1)
has=max(has,ki[D-1]+a[x]);
if(D>1)
has=max(has,ka[D-1]+a[x]);
for(i=x+1;i<n;i++)
{
vector<ll> tem;
for(j=x+1;j<=i;j++)
tem.pb(a[j]);
sort(tem.begin(),tem.end());
reverse(tem.begin(),tem.end());
ll hz=0;
for(j=0;j<tem.size();j++)
{
hz+=tem[j];
ll sisa=D-((i-x)*2+(j+1));
if(sisa>=0)
has=max(has,ki[sisa]+hz);
if(sisa>=1)
has=max(has,ki[sisa-1]+hz+a[x]);
}
}
for(i=x-1;i>=0;i--)
{
vector<ll> tem;
for(j=x-1;j>=i;j--)
tem.pb(a[j]);
sort(tem.begin(),tem.end());
reverse(tem.begin(),tem.end());
ll hz=0;
for(j=0;j<tem.size();j++)
{
hz+=tem[j];
ll sisa=D-((x-i)*2+(j+1));
if(sisa>=0)
has=max(has,ka[sisa]+hz);
if(sisa>=1)
has=max(has,ka[sisa-1]+hz+a[x]);
}
}
// for(i=0;i<=D;i++)
// cout<<i<<" "<<ki[i]<<"\n";
// for(i=0;i<=D;i++)
// cout<<i<<" "<<ka[i]<<"\n";
return has;
}
Compilation message
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:43:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tem.size();j++)
~^~~~~~~~~~~
holiday.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tem.size();j++)
~^~~~~~~~~~~
holiday.cpp:82:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tem.size();j++)
~^~~~~~~~~~~
holiday.cpp:100:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tem.size();j++)
~^~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
2680 KB |
Output is correct |
2 |
Correct |
13 ms |
2780 KB |
Output is correct |
3 |
Correct |
14 ms |
2800 KB |
Output is correct |
4 |
Correct |
14 ms |
2808 KB |
Output is correct |
5 |
Correct |
19 ms |
2300 KB |
Output is correct |
6 |
Correct |
6 ms |
1152 KB |
Output is correct |
7 |
Correct |
11 ms |
1660 KB |
Output is correct |
8 |
Correct |
17 ms |
1916 KB |
Output is correct |
9 |
Correct |
5 ms |
1024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
549 ms |
644 KB |
Output is correct |
2 |
Correct |
136 ms |
632 KB |
Output is correct |
3 |
Correct |
133 ms |
508 KB |
Output is correct |
4 |
Correct |
271 ms |
504 KB |
Output is correct |
5 |
Correct |
226 ms |
508 KB |
Output is correct |
6 |
Correct |
41 ms |
384 KB |
Output is correct |
7 |
Correct |
28 ms |
384 KB |
Output is correct |
8 |
Correct |
26 ms |
384 KB |
Output is correct |
9 |
Correct |
26 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
141 ms |
3064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |