#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
knew beforehand that this problem could be solved with d&c dp optimization (opt[i] <= opt[i+1])
similar problem:
https://oj.uz/problem/view/JOI19_cake3 (copied some of the implementation from here)
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "holiday.h"
vector<int> oa(N);
struct wavelet_tree{
struct node{
node *l, *r;
vector<int> b;
vector<ll> pref;
};
node* root;
int siz;
wavelet_tree(){
}
node* build(vector<int> &a, vector<int> inds, int l, int r){
if(l > r) return NULL;
int mid = (l+r) >> 1;
vector<int> b(sz(inds)+1);
vector<int> la,ra;
rep(i,sz(inds)){
int x = a[inds[i]];
b[i+1] = b[i]+(x <= mid);
if(x <= mid){
la.pb(inds[i]);
}
else{
ra.pb(inds[i]);
}
}
node* curr = new node();
curr->b = b;
vector<ll> pref;
pref.pb(0);
trav(i,inds){
pref.pb(pref.back()+oa[i]);
}
curr->pref = pref;
if(l != r){
curr->l = build(a,la,l,mid);
curr->r = build(a,ra,mid+1,r);
}
return curr;
}
void build(vector<int> &a, int mx_siz){
siz = mx_siz;
vector<int> inds;
rep(i,sz(a)) inds.pb(i);
root = build(a,inds,0,siz);
}
int kth(node* u, int lx, int rx, int l, int r, int k){
if(lx == rx){
return lx;
}
int mid = (lx+rx) >> 1;
auto &b = u->b;
int cnt = b[r]-b[l-1];
if(k <= cnt){
return kth(u->l,lx,mid,b[l-1]+1,b[r],k);
}
else{
return kth(u->r,mid+1,rx,l-b[l-1],r-b[r],k-cnt);
}
}
int kth(int l, int r, int k){
return kth(root,0,siz,l+1,r+1,k);
}
pll get(node* u, int lx, int rx, int vl, int vr, int l, int r){
if(lx > vr or rx < vl) return {0,0};
if(!u) return {0,0};
if(lx > rx) return {0,0};
if(lx >= vl and rx <= vr){
return {r-l+1,u->pref[r]-u->pref[l-1]};
}
int mid = (lx+rx) >> 1;
auto &b = u->b;
pll p1 = get(u->l,lx,mid,vl,vr,b[l-1]+1,b[r]);
pll p2 = get(u->r,mid+1,rx,vl,vr,l-b[l-1],r-b[r]);
return {p1.ff+p2.ff,p1.ss+p2.ss};
}
pll get(int l, int r, int k){
return get(root,0,siz,k,siz,l+1,r+1);
}
};
vector<int> a(N);
vector<int> b;
wavelet_tree wt;
int k;
int start;
ll get_cost(int l, int r){
int move = min(start-l+r-l,r-start+r-l);
if(move >= k) return 0;
int pick = k-move;
int len = r-l+1;
amin(pick,len);
int mn_pick = wt.kth(l,r,len-pick+1);
auto [cnt,sum] = wt.get(l,r,mn_pick);
assert(cnt >= pick);
sum -= (cnt-pick)*b[mn_pick];
return sum;
}
ll go(int l, int r, int optl, int optr){
if(l > r) return 0;
int mid = (l+r) >> 1;
pll best = {-1,-1};
for(int i = optl; i <= optr; ++i){
pll px = {get_cost(mid,i),i};
amax(best,px);
}
auto [ans,opt_mid] = best;
amax(ans,go(l,mid-1,optl,opt_mid));
amax(ans,go(mid+1,r,opt_mid,optr));
return ans;
}
long long int findMaxAttraction(int n, int start_, int k_, int A[]) {
start = start_;
k = k_;
b = vector<int>(n);
rep(i,n) oa[i] = a[i] = b[i] = A[i];
sort(all(b));
b.resize(unique(all(b))-b.begin());
rep(i,n) a[i] = lower_bound(all(b),a[i])-b.begin();
wt.build(a,*max_element(all(a)));
ll ans = 0;
rep(l,start+1){
for(int r = start; r < n; ++r){
amax(ans,get_cost(l,r));
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
21908 KB |
Output is correct |
| 2 |
Correct |
14 ms |
21912 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21908 KB |
Output is correct |
| 4 |
Correct |
15 ms |
21752 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18584 KB |
Output is correct |
| 6 |
Correct |
12 ms |
18548 KB |
Output is correct |
| 7 |
Correct |
12 ms |
18620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
5592 KB |
Output is correct |
| 2 |
Correct |
12 ms |
5592 KB |
Output is correct |
| 3 |
Correct |
16 ms |
8736 KB |
Output is correct |
| 4 |
Correct |
13 ms |
8856 KB |
Output is correct |
| 5 |
Correct |
30 ms |
15296 KB |
Output is correct |
| 6 |
Correct |
20 ms |
22996 KB |
Output is correct |
| 7 |
Correct |
22 ms |
18684 KB |
Output is correct |
| 8 |
Correct |
26 ms |
17148 KB |
Output is correct |
| 9 |
Correct |
20 ms |
24280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
42136 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5224 KB |
Output is correct |
| 3 |
Correct |
28 ms |
42152 KB |
Output is correct |
| 4 |
Correct |
167 ms |
41952 KB |
Output is correct |
| 5 |
Correct |
136 ms |
42132 KB |
Output is correct |
| 6 |
Correct |
26 ms |
37260 KB |
Output is correct |
| 7 |
Correct |
30 ms |
37272 KB |
Output is correct |
| 8 |
Correct |
33 ms |
37272 KB |
Output is correct |
| 9 |
Correct |
23 ms |
27796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
5592 KB |
Output is correct |
| 2 |
Correct |
96 ms |
51656 KB |
Output is correct |
| 3 |
Execution timed out |
5039 ms |
35992 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
