#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const MAXN = 1e5;
long long subtask1(int n, int start, int d, int arrraction[]){
long long ans = 0;
for(int mask = 1; mask < (1<<n); mask++){
vector<int> cities;
for(int bit = 0; bit < n; bit++){
if(mask&(1<<bit)){
cities.push_back(bit);
}
}
int curr_city = start;
int tour_days = 0;
long long ans_curr = 0;
for(auto city : cities){
tour_days += abs(curr_city-city)+1;
ans_curr += arrraction[city];
curr_city = city;
}
if(tour_days <= d)
ans = max(ans, ans_curr);
reverse(cities.begin(), cities.end());
curr_city = start;
tour_days = 0;
ans_curr = 0;
for(auto city : cities){
tour_days += abs(curr_city-city)+1;
ans_curr += arrraction[city];
curr_city = city;
}
if(tour_days <= d)
ans = max(ans, ans_curr);
}
return ans;
}
struct city{
int attractions;
int idx;
int sorted_idx;
};
struct stree_node{
int visited;
long long attractions;
};
#define lc v<<1
#define rc (v<<1)+1
struct stree{
vector<stree_node>tree;
stree(vector<city> &cities){
tree = vector<stree_node>(cities.size()*4);
build(1,0,cities.size()-1,cities);
}
void build(int v, int tl, int tr, vector<city> &cities){
if(tl == tr){
tree[v].attractions = cities[tl].attractions;
}else{
int tm = (tl+tr)>>1;
build(lc,tl,tm,cities);
build(rc,tm+1,tr,cities);
pushup(v);
}
}
void pushup(int v){
tree[v].visited = combine_visited(tree[lc].visited,tree[rc].visited);
tree[v].attractions = combine_attractions(tree[lc].visited ? tree[lc].attractions : 0,
tree[rc].visited ? tree[rc].attractions : 0);
}
long long combine_attractions(long long left_val, long long right_val){
return left_val+right_val;
}
int combine_visited(int left_val, int right_val){
return left_val+right_val;
}
void visit(int v, int tl, int tr, int pos){
if(tl==tr){
tree[v].visited = 1;
}else{
int tm = (tl+tr)>>1;
if(pos <= tm)
visit(lc,tl,tm,pos);
else
visit(rc,tm+1,tr,pos);
pushup(v);
}
}
long long query(int v, int visits){
if(visits <= 0)
return 0;
if(tree[v].visited <= visits)
return tree[v].attractions;
else{
return query(lc,visits) + query(rc,visits-tree[lc].visited);
}
}
};
bool sort_by_idx(city const &a, city const &b){
return a.idx < b.idx;
}
bool sort_by_attractions(city const &a, city const &b){
return a.attractions > b.attractions;
}
long long subtask2(int n, int start, int d, int arrraction[]){
vector<city> cities(n);
for(int i = 0; i < n; i++){
cities[i].idx = i;
cities[i].attractions = arrraction[i];
}
sort(cities.begin(), cities.end(),sort_by_attractions);
for(int i = 0; i < n; i++)
cities[i].sorted_idx = i;
stree st = stree(cities);
sort(cities.begin(), cities.end(), sort_by_idx);
long long ans = 0;
for(int r = 0; r < n; r++){
int max_visits = d-r; //min(r+1,d-r);
st.visit(1,0,n-1,cities[r].sorted_idx);
ans = max(ans,st.query(1,max_visits));
}
return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if(n <= 20){
return subtask1(n,start,d,attraction);
}else if(start == 0){
return subtask2(n,start,d,attraction);
}
return 0;
}
