#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5, dx=250005;
int id[nx], st, N, D;
ll ans, dp[4][dx];
vector<pair<ll, int>> v;
struct segtree
{
int f[4*nx];
ll sm[4*nx];
void build(int l, int r, int i)
{
f[i]=sm[i]=0;
if (l==r) return;
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
}
void update(int l, int r, int i, int idx, ll val)
{
if (idx<l||r<idx) return;
if (l==r)
{
if (val>=0) return f[i]=1, sm[i]=val, void();
else return f[i]=sm[i]=0, void();
}
int md=(l+r)/2;
update(l, md, 2*i, idx, val);
update(md+1, r, 2*i+1, idx, val);
f[i]=f[2*i]+f[2*i+1];
sm[i]=sm[2*i]+sm[2*i+1];
}
ll query(int l, int r, int i, int cnt)
{
if (cnt>=f[i]) return sm[i];
if (cnt<=0) return 0;
int md=(l+r)/2;
if (f[2*i]>cnt) return query(l, md, 2*i, cnt);
return sm[2*i]+query(md+1, r, 2*i+1, cnt-f[2*i]);
}
} s;
void solver(int st, int ml, int sl)
{
int lst=st-1+(ml==2);
queue<tuple<int, int, int, int>> q;
q.push({0, D, st+(ml==2), N-1});
if ((st+(ml==2))>N-1) return;
while (!q.empty())
{
auto [l, r, optl, optr]=q.front();
q.pop();
if (r<l) continue;
int md=(l+r+1)/2;
pair<ll, int> p={-1, -1};
for (int i=optl; i<=optr; i++)
{
while (lst<i) ++lst, s.update(0, N-1, 1, id[lst], v[id[lst]].first);
while (lst>i) s.update(0, N-1, 1, id[lst], -1), lst--;
p=max(p, make_pair(s.query(0, N-1, 1, md-ml*(i-st)), i));
}
dp[sl][md]=p.first;
q.push({l, md-1, optl, p.second});
q.push({md+1, r, p.second, optr});
}
s.build(0, N-1, 1);
}
void solvel(int st, int ml, int sl)
{
int lst=st+1-(ml==2);
queue<tuple<int, int, int, int>> q;
q.push({0, D, 0, st-(ml==2)});
if ((st-(ml==2))<0) return;
while (!q.empty())
{
auto [l, r, optl, optr]=q.front();
q.pop();
if (r<l) continue;
int md=(l+r+1)/2;
pair<ll, int> p={-1, -1};
for (int i=optl; i<=optr; i++)
{
while (lst>i) --lst, s.update(0, N-1, 1, id[lst], v[id[lst]].first);
while (lst<i) s.update(0, N-1, 1, id[lst], -1), lst++;
p=max(p, make_pair(s.query(0, N-1, 1, md-ml*(st-i)), i));
}
dp[sl][md]=p.first;
q.push({l, md-1, p.second, optr});
q.push({md+1, r, optl, p.second});
}
s.build(0, N-1, 1);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
v.resize(n);
for (int i=0; i<n; i++) v[i]={attraction[i], i};
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (int i=0; i<n; i++) id[v[i].second]=i;
N=n; D=d; st=start;
solver(st, 1, 0);
solver(st, 2, 1);
solvel(st, 1, 2);
solvel(st, 2, 3);
for (int i=0; i<=D; i++) ans=max(ans, dp[0][i]+dp[3][D-i]);
for (int i=0; i<=D; i++) ans=max(ans, dp[1][i]+dp[2][D-i]);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
8796 KB |
Output is correct |
2 |
Correct |
1 ms |
9052 KB |
Output is correct |
3 |
Correct |
1 ms |
9052 KB |
Output is correct |
4 |
Correct |
1 ms |
8796 KB |
Output is correct |
5 |
Correct |
2 ms |
10840 KB |
Output is correct |
6 |
Correct |
1 ms |
10844 KB |
Output is correct |
7 |
Correct |
1 ms |
10844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
725 ms |
15220 KB |
Output is correct |
2 |
Correct |
609 ms |
15456 KB |
Output is correct |
3 |
Correct |
713 ms |
15468 KB |
Output is correct |
4 |
Correct |
653 ms |
15464 KB |
Output is correct |
5 |
Correct |
874 ms |
15352 KB |
Output is correct |
6 |
Correct |
273 ms |
11888 KB |
Output is correct |
7 |
Correct |
475 ms |
13312 KB |
Output is correct |
8 |
Correct |
557 ms |
13472 KB |
Output is correct |
9 |
Correct |
215 ms |
15064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
9048 KB |
Output is correct |
2 |
Correct |
20 ms |
9052 KB |
Output is correct |
3 |
Correct |
20 ms |
9052 KB |
Output is correct |
4 |
Correct |
18 ms |
11228 KB |
Output is correct |
5 |
Correct |
19 ms |
11100 KB |
Output is correct |
6 |
Correct |
5 ms |
11100 KB |
Output is correct |
7 |
Correct |
5 ms |
11100 KB |
Output is correct |
8 |
Correct |
5 ms |
11100 KB |
Output is correct |
9 |
Correct |
5 ms |
11116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1142 ms |
19164 KB |
Output is correct |
2 |
Correct |
792 ms |
19004 KB |
Output is correct |
3 |
Correct |
351 ms |
14160 KB |
Output is correct |
4 |
Correct |
14 ms |
11100 KB |
Output is correct |
5 |
Correct |
5 ms |
11096 KB |
Output is correct |
6 |
Correct |
5 ms |
11096 KB |
Output is correct |
7 |
Correct |
5 ms |
11100 KB |
Output is correct |
8 |
Correct |
1117 ms |
15664 KB |
Output is correct |
9 |
Correct |
1129 ms |
16056 KB |
Output is correct |