#include <bits/stdc++.h>
using namespace std;
set<pair<int, int>> chosen;
set<pair<int, int>, greater<>> have;
long long curSum = 0;
int lt = 1;
int rt = 0;
int n, d, start;
int du;
int arr[100001];
long long ans = -1e18;
void giveToHave()
{
du++;
have.insert(*chosen.begin());
curSum -= chosen.begin()->first;
chosen.erase(chosen.begin());
}
void giveToChosen()
{
du--;
chosen.insert(*have.begin());
curSum += have.begin()->first;
have.erase(have.begin());
}
void Add(int x)
{
have.insert(make_pair(arr[x], x));
}
void Del(int x)
{
if (chosen.find(make_pair(arr[x], x)) != chosen.end())
{
chosen.erase(make_pair(arr[x], x));
curSum -= arr[x];
du++;
}
else have.erase(make_pair(arr[x], x));
}
int calcDis(int l, int r)
{
if (l > r) return 0;
if (start <= l) return(l - start + (r - l));
if (start >= r) return(start - r + (r - l));
return (min(start - l, r - start) + (r - l));
}
void stable()
{
while (du < 0 && !chosen.empty()) giveToHave();
while ((du > 0 && !have.empty())) giveToChosen();
while (!have.empty() && !chosen.empty() && have.begin()->first > chosen.begin()->first) giveToHave(), giveToChosen();
}
long long cost(int l, int r)
{
while (lt != l || rt != r)
{
while (rt < r)
{
du += calcDis(lt, rt) - calcDis(lt, rt + 1);
rt++;
Add(rt);
stable();
}
while (rt > lt && rt > r)
{
du += calcDis(lt, rt) - calcDis(lt, rt - 1);
Del(rt);
rt--;
stable();
}
while (lt < rt && lt < l)
{
du += calcDis(lt, rt) - calcDis(lt + 1, rt);
Del(lt);
lt++;
stable();
}
while (lt > l)
{
du += calcDis(lt, rt) - calcDis(lt - 1, rt);
lt--;
Add(lt);
stable();
}
}
return curSum;
}
void divide(int l, int r, int gL, int gR)
{
if (l > r) return;
int mid = (l + r) / 2;
long long bestCost = -1e18;
int bestPos = gL;
for (int i = gL; i <= min(mid, gR); i++)
{
if (cost(i, mid) > bestCost)
{
bestCost = cost(i, mid);
bestPos = i;
}
}
ans = max(ans, bestCost);
divide(l, mid - 1, gL, bestPos);
divide(mid + 1, r, bestPos, gR);
}
long long findMaxAttraction(int _n, int _start, int _d, int *attraction)
{
n = _n;
d = _d;
start = _start + 1;
for (int i = 1; i <= n; i++) arr[i] = attraction[i - 1];
du = d;
divide(1, n, 1, n);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
406 ms |
6108 KB |
Output is correct |
2 |
Correct |
406 ms |
5848 KB |
Output is correct |
3 |
Correct |
429 ms |
5848 KB |
Output is correct |
4 |
Correct |
408 ms |
5712 KB |
Output is correct |
5 |
Correct |
887 ms |
5452 KB |
Output is correct |
6 |
Correct |
162 ms |
2128 KB |
Output is correct |
7 |
Correct |
403 ms |
3480 KB |
Output is correct |
8 |
Correct |
695 ms |
4120 KB |
Output is correct |
9 |
Correct |
111 ms |
1872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
860 KB |
Output is correct |
2 |
Correct |
8 ms |
860 KB |
Output is correct |
3 |
Correct |
7 ms |
860 KB |
Output is correct |
4 |
Correct |
17 ms |
856 KB |
Output is correct |
5 |
Correct |
14 ms |
860 KB |
Output is correct |
6 |
Correct |
4 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
5 ms |
860 KB |
Output is correct |
9 |
Correct |
5 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
409 ms |
6100 KB |
Output is correct |
2 |
Correct |
363 ms |
5876 KB |
Output is correct |
3 |
Correct |
294 ms |
2136 KB |
Output is correct |
4 |
Correct |
14 ms |
856 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
5 ms |
860 KB |
Output is correct |
7 |
Correct |
5 ms |
868 KB |
Output is correct |
8 |
Correct |
1140 ms |
4836 KB |
Output is correct |
9 |
Correct |
1151 ms |
4840 KB |
Output is correct |