#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long long long int
#define sz(x) int((x).size())
const int bsize = 1200, maxn = 1e5 + 5, maxb = maxn / bsize + 5;
struct DS {
int n;
vector<int> sorted[maxb];
vector<long> spsum[maxb];
vector<pair<long, int>> gaps[maxb];
DS(const vector<int>& arr) : n(sz(arr)) {
for (int i = 0, ind = 0; ind <= sz(arr); i++, ind += bsize) {
sorted[i] = vector<int>(arr.begin(), arr.begin() + ind);
sort(begin(sorted[i]), end(sorted[i]), greater<>());
spsum[i].resize(sz(sorted[i]) + 1);
for (int j = 0; j < sz(sorted[i]); j++) {
spsum[i][j + 1] = spsum[i][j] + sorted[i][j];
}
for (int j = ind; j < min(sz(arr), ind + bsize); j++) {
gaps[i].emplace_back(arr[j], j);
}
sort(begin(gaps[i]), end(gaps[i]), greater<>());
}
}
long query(int i, int k) {
if (k < 0) {
return 0;
}
int ind = min(k, i + 1), bucket = i / bsize;
long ans = 0;
for (auto& [x, j] : gaps[bucket]) {
if (!ind) {
break;
}
if (j <= i) {
if (ind - 1 >= sz(sorted[bucket]) || x > sorted[bucket][ind - 1]) {
ind--;
ans += x;
} else {
break;
}
}
}
return ans + spsum[bucket][ind];
}
};
int m;
struct Pref {
int mul;
vector<int> arr;
DS ds;
vector<long> ans;
Pref(int mul, const vector<int>& arr)
: mul(mul), arr(arr), ds(arr), ans(m + 1) {}
void dp(int l, int r, int ql, int qr) {
if (l > r) {
return;
}
int mid = (l + r) / 2;
pair<long, int> opt {-1, -1};
for (int i = ql; i <= qr; i++) {
opt = max(opt,
pair<long, int> {ds.query(i, mid - (i + 1) * mul), -i});
}
auto& [cans, qmid] = opt;
qmid = -qmid;
ans[mid] = cans;
dp(l, mid - 1, ql, qmid);
dp(mid + 1, r, qmid, qr);
}
vector<long> solve() {
if (sz(arr)) {
dp(0, m, 0, sz(arr) - 1);
}
return ans;
}
};
template <typename T>
T reversed(T t) {
reverse(begin(t), end(t));
return t;
}
long solve(int start, const vector<int>& arr) {
auto suff =
Pref(2, vector<int>(arr.begin() + start + 1, arr.end())).solve();
auto pref = Pref(1, reversed(vector<int>(arr.begin(), arr.begin() + start)))
.solve();
long ans = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j <= m; j++) {
int k = m - j - i;
if (k >= 0) {
ans = max(ans, i * arr[start] + suff[j] + pref[k]);
}
}
}
return ans;
}
long findMaxAttraction(int n, int start, int _m, int inarr[]) {
m = _m;
vector<int> arr(inarr, inarr + n);
return max(solve(start, arr), solve(n - start - 1, reversed(arr)));
}
# |
결과 |
실행 시간 |
메모리 |
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 |
684 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 |
3582 ms |
58184 KB |
Output is correct |
2 |
Correct |
4043 ms |
58180 KB |
Output is correct |
3 |
Correct |
3555 ms |
58160 KB |
Output is correct |
4 |
Correct |
4073 ms |
58292 KB |
Output is correct |
5 |
Correct |
4278 ms |
48336 KB |
Output is correct |
6 |
Correct |
1974 ms |
9928 KB |
Output is correct |
7 |
Correct |
2519 ms |
17372 KB |
Output is correct |
8 |
Correct |
2706 ms |
23680 KB |
Output is correct |
9 |
Correct |
1654 ms |
8912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
928 KB |
Output is correct |
2 |
Correct |
94 ms |
980 KB |
Output is correct |
3 |
Correct |
70 ms |
948 KB |
Output is correct |
4 |
Correct |
94 ms |
1108 KB |
Output is correct |
5 |
Correct |
83 ms |
852 KB |
Output is correct |
6 |
Correct |
15 ms |
756 KB |
Output is correct |
7 |
Correct |
8 ms |
724 KB |
Output is correct |
8 |
Correct |
8 ms |
724 KB |
Output is correct |
9 |
Correct |
9 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3752 ms |
60136 KB |
Output is correct |
2 |
Correct |
4606 ms |
59560 KB |
Output is correct |
3 |
Correct |
591 ms |
7520 KB |
Output is correct |
4 |
Correct |
43 ms |
724 KB |
Output is correct |
5 |
Correct |
8 ms |
684 KB |
Output is correct |
6 |
Correct |
8 ms |
724 KB |
Output is correct |
7 |
Correct |
7 ms |
724 KB |
Output is correct |
8 |
Correct |
2047 ms |
16776 KB |
Output is correct |
9 |
Correct |
2029 ms |
17040 KB |
Output is correct |