#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <unordered_map>
using namespace std;
int const MAXN = 1e5;
long long subtask1(int n, int start, int d, int attraction[]){
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 += attraction[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 += attraction[city];
curr_city = city;
}
if(tour_days <= d)
ans = max(ans, ans_curr);
}
return ans;
}
int max_city, max_day;
unordered_map<int,unordered_map<int, long long>> dp[2];
long long solve(int city, int day, bool visited, int attraction[]){
if(city == max_city)
return 0;
if(day > max_day)
return 0;
if(max_day-day >= (max_city-city)*2-1)
return accumulate(attraction+city, attraction+max_city,0);
auto it_city = dp[visited].find(city);
if(it_city != dp[visited].end()){
auto it_day = dp[visited][city].find(day);
if(it_day != dp[visited][city].end())
return dp[visited][city][day];
}
long long ans = 0;
if(visited){
ans += solve(city+1,day+1,false,attraction);
}else{
long long visit = attraction[city] + solve(city,day+1,true,attraction);
long long travel = solve(city+1,day+1,false,attraction);
ans += max(visit,travel);
}
dp[visited][city][day] = ans;
return ans;
}
long long subtask2(int n, int start, int d, int attraction[]){
max_city = n;
max_day = d;
return solve(0,0,false,attraction);
}
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;
}
