| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 884707 | thienhx | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;
///--------------------------------
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(f, x) memset(f, x, sizeof(f))
#define uniqueV(x) sort(all(x)), (x).resize(unique(all(x)) - x.begin())
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
///--------------------------------
#define PROBLEM "test"
const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL
///--------------------------------
void precalc();
void solve();
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(PROBLEM".inp", "r")) {
freopen(PROBLEM".inp", "r", stdin);
freopen(PROBLEM".out", "w", stdout);
}
constexpr bool MULTI_TEST = 0;
// cout << 100000 << " " << 50000 << " " << 250000 << '\n';
// for (int i = 0; i < 100000; i++)
// cout << i + 1 << " ";
// cout << '\n';
int t = 1;
if (MULTI_TEST) cin >> t;
while (t--)
solve();
cerr << setprecision(3) << fixed;
cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s] ";
}
///--------------------[PROBLEM SOLUTION]--------------------///
const int maxn = 1e5 + 35;
int fL[maxn * 2], fR[maxn * 2], cnt[maxn * 4];
ll dpL[maxn * 2], dpR[maxn * 2], seg[maxn * 4];
int val[maxn], ind[maxn];
int n, s, d, source, cInd;
vector<int> b;
void Update(int v, int tl, int tr, int l, int r, int x) {
if (l > r) return;
if (tl == l && tr == r) {
seg[v] += b[tl] * x;
cnt[v] += x;
return;
}
int mid = (tl + tr) >> 1;
if (r <= mid)
Update(v << 1, tl, mid, l, r, x);
else if (l > mid)
Update(v << 1 | 1, mid + 1, tr, l, r, x);
seg[v] = seg[v << 1] + seg[v << 1 | 1];
cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
}
ll Query(int v, int tl, int tr, int k) {
if (tl == tr)
return 1LL * b[tl] * min(cnt[v], k);
int mid = (tl + tr) >> 1;
if (cnt[v << 1 | 1] >= k) return Query(v << 1 | 1, mid + 1, tr, k);
else return seg[v << 1 | 1] + Query(v << 1, tl, mid, k - cnt[v << 1 | 1]);
}
void fixRangeL(int p) {
while (cInd < p)
Update(1, 0, n, ind[cInd], ind[cInd], -1), cInd++;
while (cInd > p)
cInd--, Update(1, 0, n, ind[cInd], ind[cInd], 1);
}
void fixRangeR(int p) {
while (cInd > p)
Update(1, 0, n, ind[cInd], ind[cInd], -1), cInd--;
while (cInd < p)
cInd++, Update(1, 0, n, ind[cInd], ind[cInd], 1);
}
//solve for dp[tl, tr]
void dncR(int tl, int tr, int opl, int opr) {
if (tl > tr) return;
int mid = (tl + tr) >> 1;
for (int i = opl; i <= opr; i++) {
if (mid >= (i - source)) {
fixRangeR(i);
if (maximize(dpR[mid], Query(1, 0, n, mid - (i - source))))
fR[mid] = i;
}
}
dncR(tl, mid - 1, opl, fR[mid]);
dncR(mid + 1, tr, fR[mid], opr);
}
void dncL(int tl, int tr, int opl, int opr) {
if (tl > tr) return;
int mid = (tl + tr) >> 1;
for (int i = opr; i >= opl; i--) {
if (mid >= (source - i)) {
fixRangeL(i);
if (maximize(dpL[mid], Query(1, 0, n, mid - (source - i))))
fL[mid] = i;
}
}
dncL(tl, mid - 1, fL[mid], opr);
dncL(mid + 1, tr, opl, fL[mid]);
}
void solve() {
cin >> n >> s >> d;
s++;
for (int i = 1; i <= n; i++)
cin >> val[i], b.pb(val[i]);
uniqueV(b);
for (int i = 1; i <= n; i++)
ind[i] = lb(all(b), val[i]) - b.begin();
while (b.size() < n + 1)
b.pb(0);
source = s; cInd = s - 1;
dncR(1, min(2 * (n - s + 1), d), s, n);
fixRangeR(s - 1);
source = s - 1; cInd = s;
dncL(1, min(2 * s, d), 1, s - 1);
ll res = dpR[d];
if (d) maximize(res, dpL[d - 1]);
for (int i = 1; i <= min(2 * (n - s + 1), d); i++) {
int need = i + (fR[i] - (s - 1));
if (d >= need)
maximize(res, dpR[i] + dpL[min(2 * n, d - need)]);
}
for (int i = 1; i <= min(2 * s, d); i++) {
int need = i + ((s - 1) - fL[i] + 2);
if (d >= need)
maximize(res, dpL[i] + dpR[min(2 * n, d - need)]);
}
cout << res << '\n';
}