#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class F, class S>
bool chmax(F &u, const S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
long long int findMaxAttraction(int n, int s, int d, int attraction[]) {
vector <i64> a(n);
for ( int i = 0; i < n; i++ ) a[i] = attraction[i];
i64 opt = 0;
for ( int l = 0; l <= s; l++ ){
for ( int r = s; r < n; r++ ){
priority_queue <i64> q;
for ( int k = l; k <= r; k++ ) q.push(a[k]);
int step = max(0, d - (r - l + min(s - l, r - s)));
i64 cnt = 0;
while ( !q.empty() && step-- ){
cnt += q.top(); q.pop();
}
chmax(opt, cnt);
}
}
return opt;
for ( int l = 0; l <= s; l++ ){
multiset <i64> B, A;
for ( int i = l; i < s; i++ ) B.insert(a[i]);
i64 cnt = 0;
for ( int j = s; j < n; j++ ){
int step = j - l + min(s - l, j - s);
if ( step > d ) break;
B.insert(a[j]);
while ( !B.empty() && (int)A.size() + step < d ){
auto it = --B.end(); B.erase(it);
A.insert(*it); cnt += *it;
}
while ( (int)A.size() + step > d ){
auto it = A.begin(); A.erase(it);
B.insert(*it); cnt -= *it;
}
if ( !A.empty() && !B.empty() ){
while ( *A.begin() < *B.rbegin() ){
auto x = A.begin(); A.erase(x);
auto y = --B.end(); B.erase(y);
cnt += *y - *x;
A.insert(*y), B.insert(*x);
}
}
chmax(opt, cnt);
}
}
return opt;
}
