| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 696425 | vjudge1 | 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>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
template <typename __Tp> void read(__Tp &x) {
int f = 0; x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
if (f) x = -x;
}
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); }
#include <holiday.h>
const int maxn = 3e5 + 10;
namespace Holiday {
ll n, st, d, a[maxn], f[maxn][2], g[maxn][2], b[maxn], m;
struct SegTree {
#define mid ((l + r) >> 1)
int rt[maxn], ls[maxn << 5], rs[maxn << 5], cnt[maxn << 5], tot;
ll sum[maxn << 5];
void clr() { tot = 0; }
void push_up(int o) {
cnt[o] = cnt[ls[o]] + cnt[rs[o]];
sum[o] = sum[ls[o]] + sum[rs[o]];
}
void update(int &p, int q, int l, int r, int pos) {
p = ++tot, ls[p] = ls[q], rs[p] = rs[q], cnt[p] = cnt[q], sum[p] = sum[q];
if (l == r) return cnt[p]++, sum[p] += b[l], void();
pos <= b[mid] ? update(ls[p], ls[q], l, mid, pos) : update(rs[p], rs[q], mid + 1, r, pos), push_up(p);
}
ll query(int p, int q, int l, int r, int k) {
if (cnt[q] - cnt[p] <= k) return sum[q] - sum[p];
if (l == r) return k * b[l];
if (cnt[rs[q]] - cnt[rs[p]] >= k) return query(rs[p], rs[q], mid + 1, r, k);
return sum[rs[q]] - sum[rs[p]] + query(ls[p], ls[q], l, mid, k - (cnt[rs[q]] - cnt[rs[p]]));
}
#undef mid
} tr;
void calc(int flg) {
tr.clr();
for (int i = 1; i <= n; ++i) tr.update(tr.rt[i], tr.rt[i - 1], 0, m, a[i]);
auto qry = [&] (int l, int r, int k) {
k = max(0, min(k, r - l + 1));
return tr.query(tr.rt[l - 1], tr.rt[r], 0, m, k);
};
auto ask = [&] (int d, int r, int flg) {
if (!flg) return qry(st + 1, r, d - (r - st));
else return qry(st + 1, r, d - (r - st) * 2);
};
function <void(ll, ll, ll, ll, ll)> solve = [&] (ll l, ll r, ll L, ll R, ll fl) {
if (l > r || L == R) {
for (int i = l; i <= r; ++i)
if (!fl) f[i][flg] = ask(i, L, fl);
else g[i][flg] = ask(i, L, fl);
return;
}
ll mid = (l + r) >> 1, &val = (fl ? g[mid][flg] : f[mid][flg]), p = -1; val = -1;
for (int i = L; i <= R; ++i) {
ll tmp = ask(mid, i, fl);
if (tmp > val) val = tmp, p = i;
}
solve(l, mid - 1, L, p, fl), solve(mid + 1, r, p, R, fl);
};
solve(0, d, st, n, 0), solve(0, d, st, n, 1);
}
ll findMaxAttraction(int _n, int _st, int _d, int _a[]) {
++_st;
for (int i = _n; i >= 1; --i) _a[i] = _a[i - 1];
n = m = _n, st = _st, d = _d;
for (int i = 1; i <= n; ++i) a[i] = b[i] = _a[i];
sort(b + 1, b + m + 1), m = unique(b + 1, b + m + 1) - b - 1;
calc(0), reverse(a + 1, a + n + 1), st = n - st + 1, calc(1);
ll ans = 0;
for (int i = 0; i <= d; ++i)
for (int c : {0, 1}) {
ans = max(ans, f[i][c] + g[d - i][!c]);
if (i < d) ans = max(ans, f[i][c] + g[d - i - 1][!c] + _a[_st]);
}
return ans;
}
}
// int n, st, d, a[maxn];
// int main() {
// read(n, st, d);
// for (int i = 0; i < n; ++i) read(a[i]);
// write(Holiday :: findMaxAttraction(n, st, d, a), '\n');
// return 0;
// }