Submission #809086

#	Time	Username	Problem	Language	Result	Execution time	Memory
809086		htphong0909	Holiday (IOI14_holiday)	C++17	100 / 100	1106 ms	6640 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
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;
long long curSum = 0;
int lt = 1;
int rt = 0;
int n, d, start;
int du;
int arr[100001];
long long 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 (!chosen.empty() && 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));
}
 
long long 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;
    long long 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);
}
 
long long findMaxAttraction(int _n, int _start, int _d, int *attraction)
{
    n = _n;
    d = _d;
    start = _start + 1;
    for (int i = 1; i <= n; i++) arr[i] = attraction[i - 1];
    du = d;
    divide(1, n, 1, n);
    return ans;
}
 
/*
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    File();
    cin >> n >> start >> d;
    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 << findMaxAttraction(n, start, d, arr);
    return 0;
}*/
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿
 
 ___  ___  _________        ________  ___  ___  ________  ________   ________          ________  ________  ________  ________
|\  \|\  \|\___   ___\     |\   __  \|\  \|\  \|\   __  \|\   ___  \|\   ____\        |\   __  \|\   ____\|\   __  \|\   __  \
\ \  \\\  \|___ \  \_|     \ \  \|\  \ \  \\\  \ \  \|\  \ \  \\ \  \ \  \___|        \ \  \|\  \ \  \___|\ \  \|\ /\ \  \|\  \
 \ \   __  \   \ \  \       \ \   ____\ \   __  \ \  \\\  \ \  \\ \  \ \  \  ___       \ \  \\\  \ \  \    \ \   __  \ \  \\\  \
  \ \  \ \  \   \ \  \       \ \  \___|\ \  \ \  \ \  \\\  \ \  \\ \  \ \  \|\  \       \ \  \\\  \ \  \____\ \  \|\  \ \  \\\  \
   \ \__\ \__\   \ \__\       \ \__\    \ \__\ \__\ \_______\ \__\\ \__\ \_______\       \ \_______\ \_______\ \_______\ \_______\
    \|__|\|__|    \|__|        \|__|     \|__|\|__|\|_______|\|__| \|__|\|_______|        \|_______|\|_______|\|_______|\|_______|
*/

Compilation message (stderr)

holiday.cpp: In function 'void File()':
holiday.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53