| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 808761 | htphong0909 | 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>
#define int long long
using namespace std;
void File() {
#define file "test"
freopen(file".in", "r", stdin);
freopen(file".out", "w", stdout);
}
set<pair<int, int>> chosen;
set<pair<int, int>, greater<>> have;
int curSum = 0;
int lt = 1;
int rt = 0;
int n, d, start;
int du;
int arr[100001];
int ans = -1e18;
void giveToHave()
{
du++;
have.insert(*chosen.begin());
curSum -= chosen.begin()->first;
chosen.erase(chosen.begin());
}
void giveToChosen()
{
du--;
chosen.insert(*have.begin());
curSum += have.begin()->first;
have.erase(have.begin());
}
void trade()
{
pair<int, int> temp1 = *have.begin();
pair<int, int> temp2 = *(--chosen.end());
curSum = curSum - temp2.first + temp1.first;
have.erase(have.begin());
chosen.erase(--chosen.end());
have.insert(temp2);
chosen.insert(temp1);
}
void Add(int x)
{
if (du > 0)
{
du--;
curSum += arr[x];
chosen.insert(make_pair(arr[x], x));
}
else if (arr[x] > chosen.begin()->first)
{
curSum -= chosen.begin()->first;
have.insert(*chosen.begin());
chosen.erase(chosen.begin());
chosen.insert(make_pair(arr[x], x));
curSum += arr[x];
}
else have.insert(make_pair(arr[x], x));
}
/*void Add(int x)
{
have.insert(make_pair(arr[x], x));
}*/
void Del(int x)
{
if (chosen.find(make_pair(arr[x], x)) != chosen.end())
{
chosen.erase(make_pair(arr[x], x));
curSum -= arr[x];
du++;
if (!have.empty() && du > 0) giveToChosen();
}
else have.erase(make_pair(arr[x], x));
}
int calcDis(int l, int r)
{
if (l > r) return 0;
if (start <= l) return(l - start + (r - l));
if (start >= r) return(start - r + (r - l));
return (min(start - l, r - start) + (r - l));
}
int cost(int l, int r)
{
while (lt != l || rt != r)
{
while (rt < r)
{
du += calcDis(lt, rt) - calcDis(lt, rt + 1);
rt++;
Add(rt);
//while (!have.empty() && !chosen.empty() && have.begin()->first > (--chosen.end())->first) trade();
while (du < 0 && !chosen.empty()) giveToHave();
while (du > 0 && !have.empty()) giveToChosen();
}
while (rt > lt && rt > r)
{
du += calcDis(lt, rt) - calcDis(lt, rt - 1);
Del(rt);
rt--;
//while (!have.empty() && !chosen.empty() && have.begin()->first > (--chosen.end())->first) trade();
while (du < 0 && !chosen.empty()) giveToHave();
while (du > 0 && !have.empty()) giveToChosen();
}
while (lt < rt && lt < l)
{
du += calcDis(lt, rt) - calcDis(lt + 1, rt);
Del(lt);
lt++;
//while (!have.empty() && !chosen.empty() && have.begin()->first > (--chosen.end())->first) trade();
while (du < 0 && !chosen.empty()) giveToHave();
while (du > 0 && !have.empty()) giveToChosen();
}
while (lt > l)
{
du += calcDis(lt, rt) - calcDis(lt - 1, rt);
lt--;
Add(lt);
//while (!have.empty() && !chosen.empty() && have.begin()->first > (--chosen.end())->first) trade();
while (du < 0 && !chosen.empty()) giveToHave();
while (du > 0 && !have.empty()) giveToChosen();
}
}
return curSum;
}
void divide(int l, int r, int gL, int gR)
{
if (l > r) return;
int mid = (l + r) / 2;
int bestCost = -1e18;
int bestPos = gL;
for (int i = gL; i <= min(mid, gR); i++)
{
if (cost(i, mid) > bestCost)
{
bestCost = cost(i, mid);
bestPos = i;
}
}
ans = max(ans, bestCost);
divide(l, mid - 1, gL, bestPos);
divide(mid + 1, r, bestPos, gR);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//File();
cin >> n >> start >> d;
start++;
for (int i = 1; i <= n; i++) cin >> arr[i];
du = d;
/*for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
if (cost(i, j) >= 4400) cerr << i << " " << j << " " << cost(i, j) << " " << du << " " << chosen.size() << endl;
ans = max(ans, cost(i, j));
}
}*/
divide(1, n, 1, n);
cout << ans;
return 0;
}
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿
___ ___ _________ ________ ___ ___ ________ ________ ________ ________ ________ ________ ________
|\ \|\ \|\___ ___\ |\ __ \|\ \|\ \|\ __ \|\ ___ \|\ ____\ |\ __ \|\ ____\|\ __ \|\ __ \
\ \ \\\ \|___ \ \_| \ \ \|\ \ \ \\\ \ \ \|\ \ \ \\ \ \ \ \___| \ \ \|\ \ \ \___|\ \ \|\ /\ \ \|\ \
\ \ __ \ \ \ \ \ \ ____\ \ __ \ \ \\\ \ \ \\ \ \ \ \ ___ \ \ \\\ \ \ \ \ \ __ \ \ \\\ \
\ \ \ \ \ \ \ \ \ \ \___|\ \ \ \ \ \ \\\ \ \ \\ \ \ \ \|\ \ \ \ \\\ \ \ \____\ \ \|\ \ \ \\\ \
\ \__\ \__\ \ \__\ \ \__\ \ \__\ \__\ \_______\ \__\\ \__\ \_______\ \ \_______\ \_______\ \_______\ \_______\
\|__|\|__| \|__| \|__| \|__|\|__|\|_______|\|__| \|__|\|_______| \|_______|\|_______|\|_______|\|_______|
*/