#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define int long long
//method:
//consider only going right, we'll try to compute the max obtainable with d days going to the right for each d
//now, let k be the number of cities we ever visit, and thus we get to actually see attractions of d-k cities
//we obviously visit the d-k cities with maximum attraction counts
//let visit(k,d) = max sum of visits for d with visiting the first k cities and actually opening d-k of them
//let opk[d] be the optimal number of cities to visit for d days
//note that opk[d+1]>=opk[d] (proved on paper)
//thus, for each d, there's a minimum k such that visit(k,d)<=visit(k+1,d), and from now we can use k+1 instead
//so binary search on this minimum k
//ok but we can't binary search this way round since that leads to too many insertions and erasures
//so we need to do a binary search on, for each k, the minimum d such that visit(k,d)<=visit(k+1,d)
//to do this, we need a data structure that can insert values, also query the sum of the maximum t values for any t
//this can be done with a segment tree of suffix sums with lazy propagation with coordinate compression
//since we know all the attraction values in advance
//keep a PBDS of what values are currently in the set
const int sz = 262144;
vector<int> revcoords;
class SegmentTree {
public:
vector<int> tree;
int n;
ordered_set current_indices;
SegmentTree(int numelem) {
tree=vector<int>(sz,0);
n=numelem;
//cout << "making segtree " << n << endl;
}
void update(int v, int l, int r, int tl, int tr, int addend) {
if (l>tr || r<tl) return;
if (l<=tl && tr<=r) {
assert(l==r);
tree[v]+=addend;
return;
}
int m = (tl+tr)/2;
update(2*v,l,r,tl,m,addend);
update(2*v+1,l,r,m+1,tr,addend);
tree[v] = tree[2*v]+tree[2*v+1];
}
int query(int v, int l, int r, int tl, int tr) {
if (l>tr || r<tl) return 0;
if (l<=tl && tr<=r) {
//cout << "qend " << tl <<" " << tr <<" " << tree[v] << endl;
return tree[v];
}
int m = (tl+tr)/2;
return query(2*v,l,r,tl,m)+query(2*v+1,l,r,m+1,tr);
}
void ins(int index, int weight) {
//weight must be weights[index]
int rc = revcoords[index];
current_indices.insert(rc);
//cout << "updating " << rc <<" " << weight << endl;
update(1,rc,rc,0,131071,weight);
}
void era(int index, int weight) {
//weight must be weights[index]
int rc = revcoords[index];
current_indices.erase(rc);
update(1,rc,rc,0,131071,-weight);
}
int get_sum_maximals(int k) {
//(1 indexed, so k=1 means you just want max etc)
if (current_indices.size()<k) {
return tree[1]; //sum of everything
}
if (k<=0) return 0;
int reqcid = current_indices.size();
reqcid-=k;
int req_index = *current_indices.find_by_order(reqcid);
int ans = query(1,req_index,131071,0,131071);
//cout << "getting " << k <<" " << current_indices.size() <<" " << reqcid <<" " << req_index << " " << ans << endl;
return ans;
}
};
long long findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
revcoords=vector<int>(n,-1);
vector<int> coords(n); iota(coords.begin(), coords.end(), (int)0);
for (int i=0; i<n; i++) {
//cout << weights[i] <<" ";
}
//cout << endl << endl;
sort(coords.begin(), coords.end(),[&](const int i1, const int i2) {
return attraction[i1]<attraction[i2];
});
for (int i=0; i<coords.size(); i++) {
//revcoords is what position this index takes in the sorted list by weight
revcoords[coords[i]] = i;
}
reverse(coords.begin(), coords.end());
SegmentTree st(n);
int ans = -1;
for (int i=0; i<n; i++) {
st.ins(i,attraction[i]);
int rem = d-i;
ans = max(ans,st.get_sum_maximals(rem));
}
return ans;
}
