# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
797376 |
2023-07-29T10:10:28 Z |
Sohsoh84 |
Holiday (IOI14_holiday) |
C++17 |
|
1053 ms |
17240 KB |
#include "holiday.h"
#include <bits/stdc++.h>
typedef long long ll;
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
const int MAXN = 2e5 + 10;
using namespace std;
ll A[MAXN], n;
namespace sack {
ll score = 0;
int len, d;
multiset<int> st;
vector<pair<int, vector<int>>> history;
inline void init(int d_) {
d = d_;
st.clear();
history.clear();
}
inline void add(int x) {
len++;
vector<int> er_vec;
st.insert(x);
score += x;
while (int(st.size()) > max(0, d - len + 1)) {
er_vec.push_back(*st.begin());
score -= *st.begin();
st.erase(st.begin());
}
history.push_back({x, er_vec});
}
inline void rollback() {
len--;
auto [x, y] = history.back();
history.pop_back();
for (int e : y) {
st.insert(e);
score += e;
}
st.erase(st.find(x));
score -= x;
}
inline void rollback(int k) {
while (k--) rollback();
}
}
ll divide(int l, int r, int optl, int optr) { // (r, optl]
if (r < l) return 0;
int mid = (l + r) >> 1;
for (int i = r; i >= mid; i--) sack::add(A[i]);
ll ans = sack::score, opt = optl;
for (int i = optl + 1; i <= optr; i++) {
sack::add(A[i]);
if (sack::score > ans) {
ans = sack::score;
opt = i;
}
}
sack::rollback(optr - optl);
ans = max(ans, divide(l, mid - 1, optl, opt));
sack::rollback(r - mid + 1);
for (int i = optl + 1; i <= opt; i++) sack::add(A[i]);
ans = max(ans, divide(mid + 1, r, opt, optr));
sack::rollback(opt - optl);
return ans;
}
inline ll solve(int n_, int start, int d, int attraction[]) {
memset(A, 0, sizeof A);
n = 0;
for (int i = 0; i < n_; i++) {
if (i > start) A[n++] = 0;
A[n++] = attraction[i];
}
sack::init(d);
return divide(max(0, start - d), start, start, min(ll(start + d), n - 1));
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
ll ans = solve(n, start, d, attraction);
reverse(attraction, attraction + n);
ans = max(ans, solve(n, n - 1 - start, d, attraction));
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2260 KB |
Output is correct |
2 |
Correct |
1 ms |
2260 KB |
Output is correct |
3 |
Correct |
1 ms |
2260 KB |
Output is correct |
4 |
Correct |
1 ms |
2260 KB |
Output is correct |
5 |
Correct |
1 ms |
2232 KB |
Output is correct |
6 |
Correct |
1 ms |
2260 KB |
Output is correct |
7 |
Correct |
1 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
221 ms |
15256 KB |
Output is correct |
2 |
Correct |
194 ms |
15236 KB |
Output is correct |
3 |
Correct |
234 ms |
15252 KB |
Output is correct |
4 |
Correct |
209 ms |
15316 KB |
Output is correct |
5 |
Correct |
402 ms |
9720 KB |
Output is correct |
6 |
Correct |
85 ms |
6724 KB |
Output is correct |
7 |
Correct |
205 ms |
8696 KB |
Output is correct |
8 |
Correct |
242 ms |
8532 KB |
Output is correct |
9 |
Correct |
56 ms |
5816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2644 KB |
Output is correct |
2 |
Correct |
5 ms |
2624 KB |
Output is correct |
3 |
Correct |
5 ms |
2644 KB |
Output is correct |
4 |
Correct |
28 ms |
2500 KB |
Output is correct |
5 |
Correct |
23 ms |
2516 KB |
Output is correct |
6 |
Correct |
4 ms |
2260 KB |
Output is correct |
7 |
Correct |
5 ms |
2260 KB |
Output is correct |
8 |
Correct |
6 ms |
2224 KB |
Output is correct |
9 |
Correct |
6 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
17240 KB |
Output is correct |
2 |
Correct |
252 ms |
17112 KB |
Output is correct |
3 |
Correct |
166 ms |
3408 KB |
Output is correct |
4 |
Correct |
13 ms |
2388 KB |
Output is correct |
5 |
Correct |
5 ms |
2320 KB |
Output is correct |
6 |
Correct |
6 ms |
2316 KB |
Output is correct |
7 |
Correct |
7 ms |
2304 KB |
Output is correct |
8 |
Correct |
1052 ms |
8760 KB |
Output is correct |
9 |
Correct |
1053 ms |
8668 KB |
Output is correct |