#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int n,s,d,a[100001],idx[100001],pos[100001];
long long p[250001][2];
pair <long long, int> st[400001];
void update(int node, int l, int r, int i){
if (l>i||r<i||l>r)
return;
if (l==r){
st[node].second^=1;
st[node].first=st[node].second*a[i];
return;
}
int mid=(l+r)>>1;
update(node<<1,l,mid,i);
update(node<<1|1,mid+1,r,i);
st[node]={st[node<<1].first+st[node<<1|1].first,st[node<<1].second+st[node<<1|1].second};
}
long long get(int node, int l, int r, int x){
if (st[node].second<=x)
return st[node].first;
int mid=(l+r)>>1;
return (st[node<<1|1].second<x?get(node<<1,l,mid,x-st[node<<1|1].second)+st[node<<1|1].first:get(node<<1|1,mid+1,r,x));
}
void dnc(int l, int r, int optl, int optr, int idx){
if (l>r||optl>optr)
return;
int mid=(l+r)>>1;
pair <long long, int> tmp={0,-1e9};
for (int i=optl;i<=min(s+mid/(idx+1),optr);i++){
update(1,0,n-1,pos[i]);
tmp=max(tmp,make_pair(get(1,0,n-1,mid-(i-s)*(idx+1)),-i));
}
p[mid][idx]=tmp.first;
int opt=-tmp.second;
for (int i=opt;i<=min(s+mid/(idx+1),optr);i++)
update(1,0,n-1,pos[i]);
dnc(mid+1,r,opt,optr,idx);
for (int i=optl;i<opt;i++)
update(1,0,n-1,pos[i]);
dnc(l,mid-1,optl,opt,idx);
}
long long solve(){
for (int i=0;i<n;i++)
idx[i]=i;
for (int i=0;i<=d;i++)
p[i][0]=p[i][1]=0;
sort(idx,idx+n,[](int i, int j){return make_pair(a[i],i)<make_pair(a[j],j);});
sort(a,a+n);
for (int i=0;i<n;i++)
pos[idx[i]]=i;
if (s<n-1){
s++;
dnc(0,d,s,n-1,0);
s--;
}
reverse(pos,pos+n);
s=n-1-s;
dnc(0,d,s,n-1,1);
long long res=0;
for (int i=0;i<d;i++)
res=max(res,p[i][0]+p[d-i-1][1]);
return res;
}
long long findMaxAttraction(int N, int start, int D, int attraction[]){
n=N;
s=start;
d=D;
for (int i=0;i<n;i++)
a[i]=attraction[i];
long long res=solve();
for (int i=0;i<n;i++)
a[i]=attraction[n-i-1];
return max(res,solve());
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4952 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1204 ms |
11980 KB |
Output is correct |
2 |
Correct |
1158 ms |
11976 KB |
Output is correct |
3 |
Correct |
1207 ms |
12220 KB |
Output is correct |
4 |
Correct |
1235 ms |
11980 KB |
Output is correct |
5 |
Correct |
1122 ms |
11888 KB |
Output is correct |
6 |
Correct |
467 ms |
8236 KB |
Output is correct |
7 |
Correct |
633 ms |
9416 KB |
Output is correct |
8 |
Correct |
687 ms |
9504 KB |
Output is correct |
9 |
Correct |
395 ms |
8156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
7000 KB |
Output is correct |
2 |
Correct |
22 ms |
7004 KB |
Output is correct |
3 |
Correct |
22 ms |
7004 KB |
Output is correct |
4 |
Correct |
21 ms |
5084 KB |
Output is correct |
5 |
Correct |
19 ms |
4956 KB |
Output is correct |
6 |
Correct |
5 ms |
4956 KB |
Output is correct |
7 |
Correct |
4 ms |
4956 KB |
Output is correct |
8 |
Correct |
4 ms |
4956 KB |
Output is correct |
9 |
Correct |
4 ms |
4952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1254 ms |
12112 KB |
Output is correct |
2 |
Correct |
1332 ms |
11980 KB |
Output is correct |
3 |
Correct |
161 ms |
9560 KB |
Output is correct |
4 |
Correct |
12 ms |
4956 KB |
Output is correct |
5 |
Correct |
4 ms |
4956 KB |
Output is correct |
6 |
Correct |
4 ms |
4956 KB |
Output is correct |
7 |
Correct |
4 ms |
4956 KB |
Output is correct |
8 |
Correct |
925 ms |
11980 KB |
Output is correct |
9 |
Correct |
931 ms |
11976 KB |
Output is correct |