| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 591264 | Drew_ | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
using ll = long long;
bool flag = false;
struct Segtree
{
int n;
pair<ll, int> st[1 << 18];
Segtree() {}
Segtree(int n_) : n(n_) { fill(st, st + (1 << 18), mp(0, 0)); }
inline void modify(int p, ll val)
{
const auto _modify = [&](const auto &self, int node, int l, int r) -> void
{
if (l > p || r < p)
return;
if (l == r)
{
st[node] = { val, val > 0 };
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node].f1 = st[node << 1].f1 + st[node << 1 | 1].f1;
st[node].s2 = st[node << 1].s2 + st[node << 1 | 1].s2;
};
_modify(_modify, 1, 0, n-1);
}
inline ll query(int x)
{
const auto _query = [&](const auto &self, int node, int l, int r) -> ll
{
if (flag) cerr << x << " " << node << " " << l << " " << r << " " << st[node].f1 << " " << st[node].s2 << '\n';
if (x <= 0)
return 0;
if (l == r)
return st[node].f1;
int mid = (l + r) >> 1;
if (x <= st[node << 1].s2)
return self(self, node << 1, l, mid);
x -= st[node << 1].s2;
return st[node << 1].f1 + self(self, node << 1 | 1, mid+1, r);
};
return _query(_query, 1, 0, n-1);
}
};
vector<ll> solve(vector<int> item, int D, int C)
{
if (item.empty())
return vector<ll>(D+1, 0);
int N = (int)item.size();
Segtree st(N);
vector<ll> res(D+1);
vector<int> id(N);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](const int &x, const int &y){
return item[x] > item[y];
});
{
vector<int> tmp(N);
for (int i = 0; i < N; ++i)
tmp[id[i]] = i;
id = tmp;
}
const auto dnc = [&](const auto &self, int l, int r, int optL, int optR) -> void
{
if (l > r)
return;
int mid = (l + r) >> 1;
ll optVal = -1;
int optIdx = -1;
// costs `C * i` stamina to get to that spot
for (int i = optL; i <= optR && C*i <= mid; ++i)
{
st.modify(id[i], item[i]);
ll val = st.query(mid - C*i);
if (val > optVal)
{
optVal = val;
optIdx = i;
}
}
res[mid] = optVal;
for (int i = optL; i <= min(mid, optR); ++i)
st.modify(id[i], 0);
self(self, l, mid-1, optL, optIdx);
for (int i = optL; i < optIdx; ++i)
st.modify(id[i], item[i]);
self(self, mid+1, r, optIdx, optR);
};
dnc(dnc, 0, D, 0, N-1);
return res;
}
ll findMaxAttraction(int n, int start, int d, int attraction[])
{
vector<int> vl = { 0 }, vr;
for (int i = start-1; i >= 0; --i)
vl.pb(attraction[i]);
for (int i = start; i < n; ++i)
vr.pb(attraction[i]);
ll res = 0;
for (int rep = 0; rep < 2; ++rep)
{
vector<ll> L = solve(vl, d, 1);
vector<ll> R = solve(vr, d, 2);
for (int i = 0; i <= d; ++i)
res = max(res, L[i] + R[d - i]);
vl.swap(vr);
}
return res;
}
int main() {
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}