#include <bits/stdc++.h>
#ifndef LOCAL
#include"holiday.h"
#endif // LOCAL
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e5 + 5;
template<class T>
bool chkmax(T & x, T v) {
if (x < v) {
x = v;
return true;
}
return false;
}
ll res = 0;
int N, a[maxn], req;
int val[maxn], idx[maxn];
pair<ll, int> tr[4 * maxn];
int st;
#define lc id << 1
#define rc id << 1 | 1
void upd(int pos, int val, int v, int id = 1, int l = 0, int r = N - 1) {
if (l == r) {
if (v) tr[id] = mp(val, 1);
else tr[id] = mp(0, 0);
return;
}
int mid = (l + r) / 2;
if (pos <= mid) upd(pos, val, v, lc, l, mid);
else upd(pos, val, v, rc, mid + 1, r);
tr[id] = mp(tr[lc].fi + tr[rc].fi, tr[lc].se + tr[rc].se);
}
ll k_largest(int req, int id = 1) {
if (req <= 0) return 0;
if (tr[id].se <= req) return tr[id].fi;
if (tr[rc].se >= req)
return k_largest(req, rc);
req -= tr[rc].se;
return tr[rc].fi + k_largest(req, lc);
}
void dnc(int l, int r, int opl, int opr) {
//cerr << l << ' ' << r << ' ' << opl << ' ' << opr;
if (l > r)
return;
int mid = (l + r) / 2;
ll resmid = -1e18;
int opmid = 0;
for (int i = mid; i <= r; ++i)
upd(idx[i], a[i], 1);
for (int i = opl; i <= opr; ++i) {
upd(idx[i], a[i], 1);
int take = req - (2 * (i - st) + st - mid);
if (chkmax(resmid, k_largest(take))) {
opmid = i;
}
}
res = max(res, resmid);
for (int i = opl; i <= opr; ++i)
upd(idx[i], a[i], 0);
dnc(l, mid - 1, opl, opmid);
for(int i = mid; i <= r; ++i)
upd(idx[i], a[i], 0);
for (int i = opl; i < opmid; ++i)
upd(idx[i], a[i], 1);
dnc(mid + 1, r, opmid, opr);
for (int i = opl; i < opmid; ++i)
upd(idx[i], a[i], 0);
}
void solve(int _st, int attraction[]) {
for (int i = 0; i < N; ++i)
upd(i, 0, 0);
st = _st;
for (int i = 0; i < N; ++i)
a[i] = attraction[i];
vector<ii> v;
for (int i = 0; i < N; ++i)
v.eb(a[i], i);
sort(v.begin(), v.end());
for (int i = 0; i < N; ++i)
idx[v[i].se] = i;
dnc(0, st, st, N - 1);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
req = d;
solve(start, attraction);
reverse(attraction, attraction + N);
start = N - 1 - start;
solve(start, attraction);
return res;
}
#ifdef LOCAL
signed main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
#endif // LOCAL
int n, st, d;
cin >> n >> st >> d;
int a[n];
for (int i = 0 ; i < n; ++i)
cin >> a[i];
cout << findMaxAttraction(n, st, d, a);
}
#endif // LOCAL
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
371 ms |
7600 KB |
Output is correct |
2 |
Correct |
348 ms |
7384 KB |
Output is correct |
3 |
Correct |
383 ms |
7504 KB |
Output is correct |
4 |
Correct |
353 ms |
7384 KB |
Output is correct |
5 |
Correct |
447 ms |
7308 KB |
Output is correct |
6 |
Correct |
117 ms |
2200 KB |
Output is correct |
7 |
Correct |
233 ms |
3932 KB |
Output is correct |
8 |
Correct |
277 ms |
4220 KB |
Output is correct |
9 |
Correct |
79 ms |
2012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
512 KB |
Output is correct |
2 |
Correct |
7 ms |
640 KB |
Output is correct |
3 |
Correct |
7 ms |
640 KB |
Output is correct |
4 |
Correct |
18 ms |
640 KB |
Output is correct |
5 |
Correct |
16 ms |
512 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
383 ms |
7460 KB |
Output is correct |
2 |
Correct |
380 ms |
7756 KB |
Output is correct |
3 |
Correct |
453 ms |
3996 KB |
Output is correct |
4 |
Correct |
15 ms |
512 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
1370 ms |
8392 KB |
Output is correct |
9 |
Correct |
1360 ms |
8268 KB |
Output is correct |