#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
struct Treap {
struct Node {
lint sum; // sum of all nodes in subtree
int val; // real value, constant
int cnt; // size of subtree
int prior; // random priority
Node *l, *r;
Node(lint v = 0): val(v), l(NULL), r(NULL), cnt(1), sum(v), prior(rand()) {}
void update() {
sum = val, cnt = 1;
if (l) sum += l->sum, cnt += l->cnt;
if (r) sum += r->sum, cnt += r->cnt;
}
};
using node = Node *;
node root;
Treap(): root(NULL) {}
void split(node t, node &l, node &r, int key, int add) { // implicit split, l is key-largest elements
int cur_key = add + ((t && t->l)? t->l->cnt : 0) + 1;
if (!t)
l = r = NULL;
else if (key < cur_key)
split(t->l, l, t->l, key, add), r = t;
else
split(t->r, t->r, r, key, cur_key), l = t;
if (t) t->update();
}
void split(node t, node &l, node &r, lint key) { // split based on value
if (!t)
l = r = NULL;
else if (key >= t->val)
split(t->l, l, t->l, key), r = t;
else
split(t->r, t->r, r, key), l = t;
if (t) t->update();
}
void merge(node &t, node l, node r) {
if (!l || !r)
t = l ? l : r;
else if (l->prior > r->prior)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
if (t) t->update();
}
void insert(lint x) { // insert value x to the tree
node l, r;
split(root, l, r, x);
merge(l, l, new Node(x));
merge(root, l, r);
}
lint query(int d) { // find sum of d-largest elements in tree
node t;
split(root, root, t, d, 0);
lint res = (root)? root->sum : 0;
merge(root, root, t);
return res;
}
void erase(node &t, lint x) {
if (!t)
return;
else if (t->val < x)
erase(t->l, x);
else if (t->val > x)
erase(t->r, x);
else if (t->val == x) {
node tmp = t;
merge(t, t->l, t->r);
delete tmp;
}
if (t) t->update();
}
void erase(lint x) {
erase(root, x);
}
void clear(node t) {
if (!t) return void(delete(t));
node cur = t, l = t->l, r = t->r;
delete cur;
clear(l), clear(r);
}
void clear() {
clear(root);
root = NULL;
}
};
int N, D, start;
lint ans;
Treap treap;
vector<int> endpoint; // optimal endpoints with startpoint at index
vector<int> attraction;
void solve(int start_l, int start_r, int end_l, int end_r, int cur_d, int max_d, int &ptl, int &ptr) { // iterative DFS, to allow sliding window
if (cur_d > max_d) return;
if (start_l > start_r) return;
int start_mid = (start_l + start_r) / 2;
if (endpoint[start_mid] != -1) {
solve(start_l, start_mid - 1, end_l, endpoint[start_mid], cur_d + 1, max_d, ptl, ptr);
solve(start_mid + 1, start_r, endpoint[start_mid], end_r, cur_d + 1, max_d, ptl, ptr);
return;
}
lint cur_opt = -1;
while (ptr <= start_mid && ptr < N) treap.insert(attraction[ptr++]);
while (ptl < start_mid && ptl < N) treap.erase(attraction[ptl++]);
for (lint i = end_l; i <= end_r; i++) {
while (ptr <= i && ptr < N) treap.insert(attraction[ptr++]);
int cnt = D - (i - start_mid) - min(start - start_mid, (int)i - start);
lint now = treap.query(cnt);
if (now > cur_opt) cur_opt = now, endpoint[start_mid] = i;
ans = max(ans, now);
}
solve(start_l, start_mid - 1, end_l, endpoint[start_mid], cur_d + 1, max_d, ptl, ptr);
solve(start_mid + 1, start_r, endpoint[start_mid], end_r, cur_d + 1, max_d, ptl, ptr);
}
lint findMaxAttraction(int N, int start, int D, int attraction[]) {
srand(time(NULL));
::N = N, ::D = D, ::start = start;
for (int i = 0; i < N; i++) ::attraction.push_back(attraction[i]);
for (int i = 0; i <= start; i++) endpoint.push_back(-1);
for (int max_d = 0; count(endpoint.begin(), endpoint.end(), -1) > 0; max_d++) {
treap.clear();
int ptl = 0, ptr = 0; // pointer left and right, for sliding window on iterative DFS
solve(0, start, start, N - 1, 0, max_d, ptl, ptr);
}
return ans;
}
