#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<17;
struct SegTree{
int rl,rr;
SegTree*ch1,*ch2;
ll sum; // sum of active
int num; // num of active
SegTree(int l,int r){
rl=l;
rr=r;
ch1=nullptr;
ch2=nullptr;
sum=0;
num=0;
}
};
ll get_sum(SegTree*node){
if(node==nullptr)
return 0;
return node->sum;
}
int get_num(SegTree*node){
if(node==nullptr)
return 0;
return node->num;
}
SegTree*activate(SegTree*node,int idx,int val){
SegTree*node2=new SegTree(node->rl,node->rr);
node2->ch1=node->ch1;
node2->ch2=node->ch2;
if(node2->rl==node2->rr-1){
node2->sum=val;
node2->num=1;
return node2;
}
int mid=(node2->rl+node2->rr)/2;
if(idx<mid){
if(node2->ch1==nullptr)
node2->ch1=new SegTree(node2->rl,mid);
node2->ch1=activate(node2->ch1,idx,val);
}else{
if(node2->ch2==nullptr)
node2->ch2=new SegTree(mid,node2->rr);
node2->ch2=activate(node2->ch2,idx,val);
}
node2->sum=get_sum(node2->ch1)+get_sum(node2->ch2);
node2->num=get_num(node2->ch1)+get_num(node2->ch2);
return node2;
}
// get sum of biggest k cities
ll get(SegTree*node,int k){
//cout<<node<<" "<<node->ch1<<" "<<node->ch2<<" "<<k<<endl;
k=min(k,get_num(node));
if(k==0)
return 0;
if(k==get_num(node))
return get_sum(node);
if(get_num(node->ch1)<=k)
return get_sum(node->ch1)+get(node->ch2,k-get_num(node->ch1));
return get(node->ch1,k);
}
vector<SegTree*>gen_trees(vector<int>arr){
int n=(int)arr.size();
vector<pair<int,int>>sorted(n);
for(int i=0;i<n;i++)
sorted[i]={arr[i],i};
sort(sorted.begin(),sorted.end());
reverse(sorted.begin(),sorted.end());
vector<int>in_sorted(n);
for(int i=0;i<n;i++)
in_sorted[sorted[i].second]=i;
vector<SegTree*>trees;
trees.push_back(new SegTree(0,TREE_SIZE));
for(int i=0;i<n;i++)
trees.push_back(activate(trees.back(),in_sorted[i],sorted[in_sorted[i]].first));
return trees;
}
// if you can only walk in one direction
// return a[d] = most score if you have d days
vector<ll>get3(vector<int>arr){
int n=(int)arr.size();
vector<SegTree*>trees=gen_trees(arr);
vector<ll>res;
for(int d=0;d<=2*n;d++){
// r = how far you go
ll res1=0;
for(int r=0;r<=d&&r<=n;r++){
// c = how many cities you actually visit
int c=d-r;
res1=max(res1,get(trees[r],c));
}
res.push_back(res1);
}
return res;
}
// if you can only walk in one direction and have to go back
// return a[d] = most score if you have d days
vector<ll>get2(vector<int>arr){
int n=(int)arr.size();
vector<SegTree*>trees=gen_trees(arr);
vector<ll>res;
for(int d=0;d<=3*n;d++){
// r = how far you go
ll res1=0;
for(int r=0;2*(r-1)<=d&&r<=n;r++){
// c = how many cities you actually visit
int c=d-2*(r-1);
res1=max(res1,get(trees[r],c));
}
res.push_back(res1);
}
return res;
}
// if you first start walking to the left and then right
ll get1(vector<int>arr,int d,int s){
int n=(int)arr.size();
vector<int>arr1,arr2;
for(int i=s;i>=0;i--)
arr1.push_back(arr[i]);
for(int i=s+1;i<n;i++)
arr2.push_back(arr[i]);
vector<ll>val1=get2(arr1),val2=get3(arr2);
/*if(n==5){
cout<<"val1 ";
for(ll i:val1)
cout<<i<<" ";
cout<<"\n";
cout<<"val2 ";
for(ll i:val2)
cout<<i<<" ";
cout<<"\n";
}*/
ll res=0;
for(int d1=0;d1<=d;d1++){
int d2=d-d1;
res=max(res,val1[min(d1,(int)val1.size()-1)]+val2[min(d2,(int)val2.size()-1)]);
}
return res;
}
ll findMaxAttraction(int n,int start,int d,int attraction[]){
vector<int>arr;
for(int i=0;i<n;i++)
arr.push_back(attraction[i]);
ll res=get1(arr,d,start);
reverse(arr.begin(),arr.end());
return max(res,get1(arr,d,n-start-1));
}
