| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1042433 | lyis | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.shpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define mp make_pair
#define ii pair <int, int>
#define li pair <long long, int>
using namespace std;
//using namespace __gnu_pbds;
//mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef __int128 i128;
const ll mod = 1e9 + 7;
const ll MOD = 998245353;
const db esp = 1e-10;
const int dx[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dy[] = {1, 0, -1, 0, -1, -1, 1, 1};
//const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Moves
//const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Moves
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;
const int maxk = 5e5 + 10;
const int LOG = 20;
const int base = 311;
const int root = 1e9;
const int Block = 600;
template <class an, class lyis>
bool minimize(an &x, const lyis y){
if(x > y){
x = y;
return true;
} else return false;
}
template <class an, class lyis>
bool maximize(an &x, const lyis y){
if(x < y){
x = y;
return true;
} else return false;
}
#define int ll
int n, s, d;
int a[maxn];
int res;
bool del[maxn];
int solve() {
int ans = 0, cur = 0;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
for (int i = s; i <= n; i++) {
q.push({a[i], -i}), cur += a[i];
while (q.size() > 0 && i - s + q.size() > d) {
cur -= q.top().first;
q.pop();
}
ans = max(cur, ans);
}
while (q.size() > 0) q.pop();
cur = 0;
priority_queue <int> pos;
memset(del, 0, sizeof(del));
for (int i = s; i <= n; i++) {
q.push({a[i], -i}), pos.push(i), cur += a[i];
while (q.size() > 0 && i - s + q.size() > d) {
pair <int, int> x = q.top();
q.pop();
cur -= x.first;
del[-x.second] = 1;
}
if (cur == ans) break;
}
while (pos.size() > 0) {
int x = pos.top();
if (del[x]) pos.pop(), del[x] = 0;
else break;
}
for (int i = s - 1, j = d - 1; i >= 1 && j >= 1; --i, --j) {
q.push({a[i], -i}), pos.push(i), cur += a[i];
while (q.size() > 0 && pos.top() - i + q.size() > j) {
pair <int, int> x = q.top();
q.pop();
cur -= x.first;
del[-x.second] = 1;
while (pos.size() > 0) {
int x = pos.top();
if (del[x]) pos.pop(), del[x] = 0;
else break;
}
}
ans = max(cur, ans);
}
maximize(res, ans);
}
void init() {
cin >> n >> s >> d;
++s;
for (int i = 1; i <= n; i++) cin >> a[i];
}
int findMaxAttraction(int n, int s, int d, int attraction[]) {
for (int i = 1; i <= n; i++) a[i] = attraction[i - 1];
solve();
reverse(a + 1, a + n + 1);
s = n - s + 1;
solve();
return res;
}