Submission #542626

#	Time	Username	Problem	Language	Result	Execution time	Memory
542626		alextodoran	Holiday (IOI14_holiday)	C++17	0 / 100	5087 ms	6712 KiB

holiday

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = (int) 1e5;

int n;
int start, days;
int attr[N_MAX];

struct Segment {
    int l, r;
    multiset <int> take, skip;
    int cntTake;
    ll sumTake;
    Segment () {
        l = 1, r = 0;
        sumTake = 0;
    }
    void fix () {
        cntTake = max(0, days - abs(start - l) - abs(r - l));
        while (take.empty() == false && skip.empty() == false) {
            int minTake = *take.begin();
            int maxSkip = *prev(skip.end());
            if (minTake < maxSkip) {
                sumTake -= minTake;
                take.erase(take.begin());
                skip.erase(prev(skip.end()));
                sumTake += maxSkip;
                take.insert(maxSkip);
                skip.insert(minTake);
            } else {
                break;
            }
        }
        while ((int) take.size() > cntTake) {
            sumTake -= *take.begin();
            skip.insert(*take.begin());
            take.erase(take.begin());
        }
        while ((int) take.size() < cntTake && skip.empty() == false) {
            sumTake += *prev(skip.end());
            take.insert(*prev(skip.end()));
            skip.erase(prev(skip.end()));
        }
    }
    void addL () {
        skip.insert(attr[--l]);
        fix();
    }
    void addR () {
        skip.insert(attr[++r]);
        fix();
    }
    void cutL () {
        if (skip.count(attr[l]) > 0) {
            skip.erase(skip.find(attr[l]));
        } else {
            sumTake -= attr[l];
            take.erase(take.find(attr[l]));
        }
        l++;
        fix();
    }
    void cutR () {
        if (skip.count(attr[r]) > 0) {
            skip.erase(skip.find(attr[r]));
        } else {
            sumTake -= attr[r];
            take.erase(take.find(attr[r]));
        }
        r--;
        fix();
    }
    void moveTo (int L, int R) {
        while (L < l) {
            addL();
        }
        while (r < R) {
            addR();
        }
        while (l < L) {
            cutL();
        }
        while (R < r) {
            cutR();
        }
    }
};

Segment seg;

ll solve (int l1, int l2, int r1, int r2) {
    int l = (l1 + l2) / 2;
    int r; ll maxSum = LLONG_MIN;
    for (int i = max(l, r1); i <= r2; i++) {
        seg.moveTo(l, i);
        if (seg.sumTake > maxSum) {
            maxSum = seg.sumTake;
            r = i;
        }
    }
    if (l1 <= l - 1) {
        maxSum = max(maxSum, solve(l1, l - 1, r1, r));
    }
    if (l + 1 <= l2) {
        maxSum = max(maxSum, solve(l + 1, r2, r, r2));
    }
    return maxSum;
}

ll findMaxAttraction (int _n, int _start, int _days, int _attr[]) {
    n = _n;
    start = _start;
    days = _days;
    for (int i = 0; i < n; i++) {
        attr[i] = _attr[i];
    }
    ll answer = solve(0, n - 1, 0, n - 1);
    reverse(attr, attr + n);
    seg = Segment();
    answer = max(answer, solve(0, n - 1, 0, n - 1));
    return answer;
}

Compilation message (stderr)

holiday.cpp: In function 'll solve(int, int, int, int)':
holiday.cpp:117:35: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |         maxSum = max(maxSum, solve(l + 1, r2, r, r2));
      |                              ~~~~~^~~~~~~~~~~~~~~~~~

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