#include "holiday.h"
#include <algorithm>
#include <iostream>
#include <utility>
// meow mrrow nya nya :3c
// play vivid/stasis. free on steam
using namespace std;
pair<int, int> sacl[100000];
pair<int, int> sacr[100000];
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
for (int i = 0; i < start; i++) sacl[i] = {attraction[i], start - i + 1};
sort(sacl, sacl + start, [](pair<int, int> a, pair<int, int> b) {
return (long long)a.first * (long long)b.second > (long long)b.first * (long long)a.second;
});
for (int i = 0; i < n - start; i++) sacr[i] = {attraction[start + i], i + 1};
sort(sacr, sacr + n - start, [](pair<int, int> a, pair<int, int> b) {
return (long long)a.first * (long long)b.second > (long long)b.first * (long long)a.second;
});
// for (int i = 0; i < start; i++) cout << sacl[i].first << '/' << sacl[i].second << ' ';
// cout << endl;
// for (int i = 0; i < n - start; i++) cout << sacr[i].first << '/' << sacr[i].second << ' ';
// cout << endl;
int furthestl = 0;
int furthestr = 0;
int selected = 0;
bool anyl = false;
bool anyr = false;
#define FURTHESTL (anyl ? furthestl : -furthestr)
#define FURTHESTR (anyr ? furthestr : -furthestl)
long long res = 0;
for (int i = 0, j = 0; i < n - start || j < start;) {
bool done_other = false;
if (j >= start || i < n - start && (long long)sacr[i].first * (long long)max(1, sacl[j].second - FURTHESTL) >
(long long)sacl[j].first * (long long)max(1, sacr[i].second - FURTHESTR)) {
if (false) {
r:
if (done_other) break;
done_other = true;
}
int nfurthestr = max(furthestr, sacr[i].second - 1);
if (furthestl + nfurthestr + min(furthestl, nfurthestr) + selected + 1 <= d) {
furthestr = nfurthestr;
selected++;
res += sacr[i++].first;
anyr = true;
} else goto l;
} else {
if (false) {
l:
if (done_other) break;
done_other = true;
}
int nfurthestl = max(furthestl, sacl[j].second - 1);
if (nfurthestl + furthestr + min(nfurthestl, furthestr) + selected + 1 <= d) {
furthestl = nfurthestl;
selected++;
res += sacl[j++].first;
anyl = true;
} else goto r;
}
}
return res;
}
