#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MN = 1e5;
vector<ll> calc(int n, int src, int ld, const vector<ll> &a){
vector<ll> ret(4 * MN + 1);
if (src == n - 1) return ret;
struct Seg{ int dl, dr, r; };
vector<Seg> q, nxt = {{1, 3 * (n - 1 - src), n - 1}};
// nxt[0] = {7, 7, n - 1};
priority_queue<ll> off;
priority_queue<ll, vector<ll>, greater<ll>> on;
while (!nxt.empty()){
swap(nxt, q);
// for (auto [dl, dr, r] : q) cout << dl << " " << dr << " " << r << '\n';
// cout << '\n';
nxt.clear();
while (!off.empty()) off.pop();
while (!on.empty()) on.pop();
int i = src;
ll cur = 0;
for (auto [dl, dr, r] : q){
int d = (dl + dr) >> 1;
int k = r;
while (true){
while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
if (cur > ret[d]) k = i, ret[d] = cur;
// cout << cur << " ";
if (i == r) break;
cur += a[++i], on.push(a[i]);
}
// cout << d << " -> " << ret[d] << '\n';
if (d != dl) nxt.push_back({dl, d - 1, k});
if (d != dr) nxt.push_back({d + 1, dr, r});
}
}
// cout << "done" << '\n';
return ret;
}
ll solve(int n, int start, int d, vector<ll> a){
vector<ll> r = calc(n, start, 1, a);
reverse(a.begin(), a.end()); start = n - start - 1;
vector<ll> l = calc(n, start, 2, a);
ll ans = 0;
for (int i = 0; i <= d; ++i){
ans = max(ans, l[i] + r[d - i]);
}
for (int i = 0; i <= d - 1; ++i){
ans = max(ans, l[i] + r[(d - 1) - i] + a[start]);
}
// for (int i = 0; i <= 10; ++i) cout << i << ": " << r[i] << '\n';
return ans;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]){
vector<ll> vec;
for (int i = 0; i < n; ++i) vec.push_back(attraction[i]);
ll ans = solve(n, start, d, vec);
// cout << ans << " ";
start = n - start - 1;
reverse(vec.begin(), vec.end());
ans = max(ans, solve(n, start, d, vec));
// cout << solve(n, start, d, vec) << '\n';
return ans;
}
Compilation message
holiday.cpp: In function 'std::vector<long long int> calc(int, int, int, const std::vector<long long int>&)':
holiday.cpp:31:67: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
31 | while (!off.empty() && (i - src) * ld + on.size() < d) cur += off.top(), on.push(off.top()), off.pop();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:32:66: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | while (!on.empty() && (i - src) * ld + on.size() > d) cur -= on.top(), off.push(on.top()), on.pop();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6884 KB |
Output is correct |
2 |
Correct |
5 ms |
6884 KB |
Output is correct |
3 |
Correct |
5 ms |
6884 KB |
Output is correct |
4 |
Correct |
5 ms |
6868 KB |
Output is correct |
5 |
Correct |
5 ms |
6880 KB |
Output is correct |
6 |
Correct |
5 ms |
7028 KB |
Output is correct |
7 |
Correct |
5 ms |
6884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
317 ms |
14744 KB |
Output is correct |
2 |
Correct |
224 ms |
14904 KB |
Output is correct |
3 |
Correct |
302 ms |
14888 KB |
Output is correct |
4 |
Correct |
231 ms |
14888 KB |
Output is correct |
5 |
Correct |
1486 ms |
14816 KB |
Output is correct |
6 |
Correct |
422 ms |
9176 KB |
Output is correct |
7 |
Correct |
806 ms |
11012 KB |
Output is correct |
8 |
Correct |
963 ms |
12092 KB |
Output is correct |
9 |
Correct |
273 ms |
8644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
7160 KB |
Output is correct |
2 |
Correct |
10 ms |
7124 KB |
Output is correct |
3 |
Correct |
19 ms |
7124 KB |
Output is correct |
4 |
Correct |
30 ms |
7156 KB |
Output is correct |
5 |
Correct |
26 ms |
7124 KB |
Output is correct |
6 |
Correct |
12 ms |
7012 KB |
Output is correct |
7 |
Correct |
13 ms |
7016 KB |
Output is correct |
8 |
Correct |
12 ms |
7012 KB |
Output is correct |
9 |
Correct |
12 ms |
6964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
297 ms |
12788 KB |
Output is correct |
2 |
Correct |
1602 ms |
14940 KB |
Output is correct |
3 |
Correct |
621 ms |
9920 KB |
Output is correct |
4 |
Correct |
27 ms |
7036 KB |
Output is correct |
5 |
Correct |
12 ms |
6968 KB |
Output is correct |
6 |
Correct |
12 ms |
7024 KB |
Output is correct |
7 |
Correct |
14 ms |
6996 KB |
Output is correct |
8 |
Correct |
1627 ms |
11980 KB |
Output is correct |
9 |
Correct |
1629 ms |
11840 KB |
Output is correct |