| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 331006 | Kujoh | 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.
/** Kujoh **/
#include <bits/stdc++.h>
#define fi first
#define se second
#define bug(x) cerr << #x << " = " << x << '\n';
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FFOR(i,a,b) for(int i = a; i < b; i++)
#define DFOR(i,b,a) for(int i = b; i >= a; i--)
#define getbit(x,i) ((x>>i)&1)
#define onbit(x,i) (x(1<<i))
#define cntone(x) __builtin_popcount(x)
#define mask(i) (1<<i)
#define pb push_back
#define mp make_pair
#define taskname "holiday"
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
template <typename T> inline void read(T & x)
{
char c; bool nega=0;
while((!isdigit(c=getchar()))&&c!='-');
if(c=='-')
{
c=getchar();
nega=1;
}
x=c-48;
while(isdigit(c=getchar()))
{
x=x*10+c-48;
}
if(nega) x=-x;
}
template <typename T> void Write(T x) {
if (x > 9) Write(x/10);
putchar(x%10+48);
}
template <typename T> void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
Write(x);
putchar(' ');
}
template <typename T> void writeln(T x) {
write(x);
putchar('\n');
}
/** END OF TEMPLATE **/
const int N = 1e5 + 7;
struct Data{
int l, r, from, to;
};
int n, start, d;
ll a[N];
ll b[N];
int pos[N];
ll fL[3 * N], fR[3 * N];
pii gL[3 * N], gR[3 * N];
pair<ll, int> st[4 * N];
void update(int id, int l, int r, int i, ll val){
if(l == r){
st[id] = {val, 1};
}
else{
int mid = (l + r) / 2;
if(i <= mid) update(id * 2, l, mid, i, val);
else update(id * 2 + 1, mid + 1, r, i, val);
st[id].fi = st[id * 2].fi + st[id * 2 + 1].fi;
st[id].se = st[id * 2].se + st[id * 2 + 1].se;
}
}
ll get(int id, int l, int r, int re){
if(re == st[id].se) return st[id].fi;
if(re == 0) return 0;
int mid = (l + r) / 2;
if(st[id * 2].se >= re) return get(id * 2, l, mid, re);
else{
return st[id * 2].fi + get(id * 2 + 1, mid + 1, r, re - st[id * 2].se);
}
}
void Prepare(int id){
vector<Data> curLevels, nextLevels;
curLevels.pb({1, d, start, n});
while(!curLevels.empty()){
FFOR(i, 1, 4 * N) st[i] = {0, 0};
int st = start;
int cur = 0;
for(auto p : curLevels){
ll val = 0;
int cnt = n;
int mid = (p.l + p.r) / 2;
int best = p.to;
for(; st <= p.to; st++){
if(st > cur) update(1, 1, n, pos[st], a[st]);
cur = max(cur, st);
int remain = mid - (st - start);
if(remain < 0) break;
remain = min(remain, st - start + 1);
ll tmp = get(1, 1, n, remain);
if(tmp > val){
val = tmp;
best = st;
cnt = remain;
}
}
st--;
if(id)fR[mid] = val;
else fL[mid] = val;
if(id)gR[mid] = {best - start, cnt};
else gL[mid] = {best - start, cnt};
if(mid > p.l) nextLevels.pb({p.l, mid - 1, p.from, best});
if(mid < p.r) nextLevels.pb({mid + 1, p.r, best, p.to});
}
curLevels = nextLevels;
nextLevels.clear();
}
}
int main()
{
fastio;
//freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
cin >> n >> start >> d;
start++;
FOR(i, 1, n){
cin >> a[i];
b[i] = i;
}
sort(b + 1, b + n + 1, [](int i, int j){
return a[i] > a[j];
});
//FOR(i, 1, n) bug(b[i]);
FOR(i, 1, n) pos[b[i]] = i;
//FOR(i, 1, n) bug(pos[i]);
Prepare(1);
if(start == 1){
cout << fR[d];
return 0;
}
else{
start = n - start + 1;
reverse(a + 1, a + n + 1);
FOR(i, 1, n) b[i] = i;
sort(b + 1, b + n + 1, [](int i, int j){
return a[i] > a[j];
});
FOR(i, 1, n) pos[b[i]] = i;
start++;
Prepare(0);
}
ll res = max(fL[d - 1], fR[d]);
FOR(i, 1, d){
int pos = gR[i].fi;
int re = d - 2 * pos - 1 - gR[i].se;
if(re > 0)res = max(res, fR[i] + fL[re]);
if(i > 1){
pos = gL[i - 1].fi;
re = d - 2 * pos - 2 - gL[i - 1].se;
if(re > 0) res = max(res, fL[i - 1] + fR[re]);
}
}
cout << res;
return 0;
}