| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 286853 | tcm | Holiday (IOI14_holiday) | C++14 | 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>
#define fname "holiday"
#define cerr if(false)cerr
#define bug(x) cerr << (#x) << " = " << (x) << endl
#define ll long long
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ARR0(a, n) {cerr <<(#a)<< ": ["; REP0(i, n) cerr<< ' ' << a[i] <<','; cerr<<']'<<endl;}
#define ARR1(a, n) {cerr <<(#a)<< ": ["; REP1(i, n) cerr<< ' ' << a[i] <<','; cerr<<']'<<endl;}
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define LB lower_bound
#define UB upper_bound
#define X first
#define Y second
using namespace std;
template<typename T, typename V>
inline void bugp(const pair<T, V> &x) {cerr << '{' << x.X << ", " << x.Y << '}' << endl;}
template<typename T, typename U, typename V>
inline void bugpp(const pair<T, pair<U, V> > &x) {cerr << '{' << x.X << ", {" << x.Y.X << ", " << x.Y.Y << "}}" << endl;}
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ll, int> li;
typedef pair<ll, ii> lii;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int N = 100001, D = 2*N + N/2;
int n, s, sz, lg, arr[N], val[N];
ll d, R[D], RR[D], L[D], LL[D];
li fen[N];
void compress()
{
set<int> s(arr + 1, arr + n + 1);
vi tmp(s.begin(), s.end());
sz = tmp.size();
lg = 32 - __builtin_clz(sz) - 1;
int v;
REP1(i, n) {
v = sz - (LB(tmp.begin(), tmp.end(), arr[i]) - tmp.begin());
val[v] = arr[i];
arr[i] = v;
}
}
void update(int pos)
{
for(int i = pos; i <= sz; i += i&-i) {
fen[i].X += val[pos];
++fen[i].Y;
}
}
void rollback(int pos)
{
for(int i = pos; i <= sz; i += i&-i) {
fen[i].X -= val[pos];
--fen[i].Y;
}
}
li binsearch(ll value)
{
int p = 0, v = 0, jump;
REPB0(i, lg + 1) {
jump = p + (1 << i);
if(jump <= sz && v + fen[jump].Y < value) {
p = jump;
v += fen[p].Y;
}
}
if(p == sz) return {0, p};
return {(value - v) * val[p + 1], p};
}
ll getSum(int pos)
{
ll sum = 0;
for(int i = pos; i; i &= i - 1) {
//bug(i); bugp(fen[i]);
sum += fen[i].X;
}
return sum;
}
void solveR(ll l, ll r, int from, int to)
{
if(l > r) return;
int pos = from, last = to + 1;
li p;
ll res = -1, cur, mid = l + r >> 1;
bug(l); bug(r); bug(mid);
cerr << "updating from " << from << " to " << to << endl;
FOR(i, from, to) {
bug(i); bug(arr[i]);
if(i - s >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - i + s);
bugp(p);
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
if(res != -1) R[mid] = res;
bug(pos); bug(res);
cerr << "rolling back from " << pos << " to " << to << endl;
FOR(i, pos, min(to, last - 1)) rollback(arr[i]);
solveR(mid + 1, r, pos, to);
cerr << "rolling back from " << from << " to " << pos - 1 << endl;
FOR(i, from, pos - 1) rollback(arr[i]);
solveR(l, mid - 1, from, pos);
}
void solveRR(ll l, ll r, int from, int to)
{
if(l > r) return;
int pos = from, last = to + 1;
li p;
ll res = -1, cur, mid = l + r >> 1;
cerr << "updating from " << from << " to " << to << endl;
bug(l); bug(r); bug(mid); bug(from); bug(to);
FOR(i, from, to) {
if(2LL * (i - s) >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - 2LL * (i - s));
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
bug(pos); bug(res);
if(res != -1) RR[mid] = res;
cerr << "rolling back from " << pos << " to " << to << endl;
FOR(i, pos, min(last - 1, to)) rollback(arr[i]);
solveRR(mid + 1, r, pos, to);
cerr << "rolling back from " << from << " to " << pos - 1 << endl;
FOR(i, from, pos - 1) rollback(arr[i]);
solveRR(l, mid - 1, from, pos);
}
void solveL(ll l, ll r, int from, int to)
{
if(l > r) return;
int pos = to, last = from - 1;
li p;
ll res = -1, cur, mid = l + r >> 1;
bug(l); bug(r); bug(mid); bug(from); bug(to);
FORB(i, to, from) {
bug(i); bug(arr[i]);
if(s - i >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - s + i);
bugp(p);
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
if(res != -1) L[mid] = res;
bug(L[mid]);
FOR(i, max(last + 1, from), pos) rollback(arr[i]);
solveL(mid + 1, r, from, pos);
FOR(i, pos + 1, to) rollback(arr[i]);
solveL(l, mid - 1, pos, to);
}
void solveLL(ll l, ll r, int from, int to)
{
if(l > r) return;
int pos = to, last = from - 1;
li p;
ll res = -1, cur, mid = l + r >> 1;
FORB(i, to, from) {
if(2LL * (s - i) >= mid) {
last = i;
break;
}
update(arr[i]);
p = binsearch(mid - 2LL * (s - i));
cur = p.X + getSum(p.Y);
if(cur > res) {
res = cur;
pos = i;
}
}
bug(pos); bug(res);
if(res != -1) LL[mid] = res;
FOR(i, max(last + 1, from), pos) rollback(arr[i]);
solveLL(mid + 1, r, from, pos);
FOR(i, pos + 1, to) rollback(arr[i]);
solveLL(l, mid - 1, pos, to);
}
int main()
{
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> s >> d;
++s;
REP1(i, n) cin >> arr[i];
compress();
solveR(1, d, s, n);
cerr << "________________________ SOLVE RR _____________________________" << endl;
solveRR(1, d, s, n);
if(s > 1) {
cerr << "________________________ CHECKING _____________________________" << endl;
REP1(i, n) {
if(fen[i].X || fen[i].Y) {
bugp(fen[i]);
}
}
cerr << "________________________ SOLVE L _____________________________" << endl;
solveL(2, d, 1, s - 1);
cerr << "________________________ SOLVE LL _____________________________" << endl;
solveLL(2, d, 1, s - 1);
}
ll ans = 0;
REP0(t, d + 1) {
bug(t);
bug(L[t]); bug(LL[t]); bug(R[t]); bug(RR[t]);
}
REP0(t, d + 1) {
ans = max(ans, L[t] + RR[d - t]);
ans = max(ans, LL[t] + R[d - t]);
}
cout << ans;
return 0;
}