#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
// if you can only walk in one direction
// return a[d] = most score if you have d days
vector<ll>get3(vector<int>arr){
vector<ll>res;
for(int d=0;d<=2*(int)arr.size();d++){
// r = how far you go
ll res1=0;
for(int r=0;r<=d&&r<=(int)arr.size();r++){
// c = how many cities you actually visit
int c=d-r;
vector<ll>vals;
for(int i=0;i<r;i++){
vals.push_back(arr[i]);
}
sort(vals.begin(),vals.end());
reverse(vals.begin(),vals.end());
ll res2=0;
for(int i=0;i<c&&i<(int)vals.size();i++)
res2+=vals[i];
res1=max(res1,res2);
}
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){
vector<ll>res;
for(int d=0;d<=3*(int)arr.size();d++){
// r = how far you go
ll res1=0;
for(int r=0;2*(r-1)<=d&&r<=(int)arr.size();r++){
// c = how many cities you actually visit
int c=d-2*(r-1);
vector<ll>vals;
for(int i=0;i<r;i++){
vals.push_back(arr[i]);
}
sort(vals.begin(),vals.end());
reverse(vals.begin(),vals.end());
ll res2=0;
for(int i=0;i<c&&i<(int)vals.size();i++)
res2+=vals[i];
res1=max(res1,res2);
}
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);
/*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;
if(d1<(int)val1.size()&&d2<(int)val2.size()){
res=max(res,val1[d1]+val2[d2]);
}
}
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));
}
