#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
const int maxn = 1e5 + 20;
struct tree {
vector<long long> *A;
vector<long long> *B;
int tree[maxn * 16];
void build(int id, int lt, int rt) {
tree[id] = -1;
if (lt == rt) {
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
}
long long eval(int off, int pos) {
if (off == -1) {
return -inf;
}
else {
return (*A)[off] + (*B)[pos - off];
}
}
void update(int id, int lt, int rt, int off, int ql, int qr) {
if (qr < lt || ql > rt) {
return;
}
if (lt == rt) {
if (eval(off, lt) > eval(tree[id], lt)) {
tree[id] = off;
}
return;
}
int mt = (lt + rt) / 2;
if (ql <= lt && rt <= qr) {
bool cmp1 = eval(off, lt) > eval(tree[id], lt);
bool cmp2 = eval(off, mt) > eval(tree[id], mt);
if (cmp1 != cmp2) {
if (cmp2) {
swap(tree[id], off);
}
update(id * 2, lt, mt, off, ql, qr);
}
else {
if (cmp1) {
swap(tree[id], off);
}
update(id * 2 + 1, mt + 1, rt, off, ql, qr);
}
return;
}
update(id * 2, lt, mt, off, ql, qr);
update(id * 2 + 1, mt + 1, rt, off, ql, qr);
}
long long get(int id, int lt, int rt, int pos) {
if (lt == rt) {
return eval(tree[id], pos);
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
return max(eval(tree[id], pos), get(id * 2, lt, mt, pos));
}
else {
return max(eval(tree[id], pos), get(id * 2 + 1, mt + 1, rt, pos));
}
}
} T;
vector<long long> calc(vector<int> a) {
int n = a.size();
vector<long long> res(n * 2 + 1);
if (n == 0) {
return res;
}
if (n == 1) {
res[2] = a[0];
return res;
}
vector<int> left(a.begin(), a.begin() + n / 2);
vector<int> right(a.begin() + n / 2, a.end());
vector<long long> best_l = calc(left);
vector<long long> best_r = calc(right);
for (int i = 0; i <= (n / 2) * 2; i++) {
res[i] = best_l[i];
}
for (int i = 0; i < n / 2; i++) {
best_l[i] = -inf;
}
best_l[n / 2] = 0;
sort(left.begin(), left.end(), greater<int>());
for (int i = n / 2 + 1; i <= (n / 2) * 2; i++) {
best_l[i] = best_l[i - 1] + left[i - n / 2 - 1];
}
T.A = &best_r;
T.B = &best_l;
T.build(1, n / 2, n * 2);
for (int i = 0; i <= (n - n / 2) * 2; i++) {
T.update(1, n / 2, n * 2, i, i + n / 2, i + (n / 2) * 2);
}
for (int i = n / 2; i <= n * 2; i++) {
res[i] = max(res[i], T.get(1, n / 2, n * 2, i));
}
for (int i = 1; i <= n / 2; i++) {
res[i] = max(res[i], res[i - 1]);
}
return res;
}
long long solve(int n, int start, int d, int attraction[]) {
vector<int> left(start * 2);
for (int i = 0; i < start; i++) {
left[i * 2] = 0;
left[i * 2 + 1] = attraction[start - 1 - i];
}
vector<int> right(n - 1 - start);
for (int i = start + 1; i < n; i++) {
right[i - start - 1] = attraction[i];
}
vector<long long> best_l = calc(left);
vector<long long> best_r = calc(right);
best_l.resize(d + 1);
best_r.resize(d + 1);
for (int i = 1; i <= d; i++) {
best_l[i] = max(best_l[i], best_l[i - 1]);
best_r[i] = max(best_r[i], best_r[i - 1]);
}
long long res = 0;
for (int i = 0; i <= d; i++) {
res = max(res, best_l[i] + best_r[d - i]);
}
for (int i = 0; i <= d - 1; i++) {
res = max(res, best_l[i] + best_r[d - 1 - i] + attraction[start]);
}
return res;
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
long long res1 = solve(n, start, d, attraction);
for (int i = 0; i < n - 1 - i; i++) {
swap(attraction[i], attraction[n - 1 - i]);
}
start = n - 1 - start;
long long res2 = solve(n, start, d, attraction);
return max(res1, res2);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2332 ms |
17980 KB |
Output is correct |
2 |
Correct |
2218 ms |
18388 KB |
Output is correct |
3 |
Correct |
2416 ms |
18292 KB |
Output is correct |
4 |
Correct |
2144 ms |
18332 KB |
Output is correct |
5 |
Correct |
2149 ms |
15172 KB |
Output is correct |
6 |
Correct |
513 ms |
6536 KB |
Output is correct |
7 |
Correct |
1055 ms |
8680 KB |
Output is correct |
8 |
Correct |
1307 ms |
10104 KB |
Output is correct |
9 |
Correct |
336 ms |
6216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
1224 KB |
Output is correct |
2 |
Correct |
32 ms |
1228 KB |
Output is correct |
3 |
Correct |
34 ms |
1124 KB |
Output is correct |
4 |
Correct |
27 ms |
1040 KB |
Output is correct |
5 |
Correct |
25 ms |
980 KB |
Output is correct |
6 |
Correct |
8 ms |
852 KB |
Output is correct |
7 |
Correct |
8 ms |
820 KB |
Output is correct |
8 |
Correct |
8 ms |
724 KB |
Output is correct |
9 |
Correct |
10 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2308 ms |
16072 KB |
Output is correct |
2 |
Correct |
2292 ms |
19008 KB |
Output is correct |
3 |
Correct |
771 ms |
5748 KB |
Output is correct |
4 |
Correct |
26 ms |
980 KB |
Output is correct |
5 |
Correct |
9 ms |
824 KB |
Output is correct |
6 |
Correct |
8 ms |
692 KB |
Output is correct |
7 |
Correct |
8 ms |
696 KB |
Output is correct |
8 |
Correct |
2143 ms |
10508 KB |
Output is correct |
9 |
Correct |
2092 ms |
10436 KB |
Output is correct |