oj.uz

Submission #542635

# Submission time Handle Problem Language Result Execution time Memory
542635 2022-03-27T09:55:44 Z alextodoran Holiday (IOI14_holiday) C++17
100 / 100
 1816 ms 5956 KB 
/**
 ____ ____ ____ ____ ____
||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];

int chng = 0;

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) - (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.find(attr[l]) != skip.end()) {
            skip.erase(skip.find(attr[l]));
        } else {
            sumTake -= attr[l];
            take.erase(take.find(attr[l]));
        }
        l++;
        fix();
    }
    void cutR () {
        if (skip.find(attr[r]) != skip.end()) {
            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;
    seg.moveTo(l, max(l, r1));
    int r = r1; ll maxSum = 0;
    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, l2, 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, start, start, n - 1);
    reverse(attr, attr + n);
    seg = Segment();
    start = (n - 1) - start;
    answer = max(answer, solve(0, start, start, n - 1));
    return answer;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 5756 KB Output is correct
2 Correct 274 ms 5952 KB Output is correct
3 Correct 289 ms 5952 KB Output is correct
4 Correct 290 ms 5956 KB Output is correct
5 Correct 482 ms 5544 KB Output is correct
6 Correct 97 ms 2200 KB Output is correct
7 Correct 246 ms 3416 KB Output is correct
8 Correct 258 ms 3996 KB Output is correct
9 Correct 67 ms 1748 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 852 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 8 ms 844 KB Output is correct
4 Correct 25 ms 828 KB Output is correct
5 Correct 20 ms 808 KB Output is correct
6 Correct 4 ms 744 KB Output is correct
7 Correct 6 ms 724 KB Output is correct
8 Correct 7 ms 744 KB Output is correct
9 Correct 7 ms 740 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 5756 KB Output is correct
2 Correct 294 ms 5760 KB Output is correct
3 Correct 470 ms 2808 KB Output is correct
4 Correct 22 ms 828 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 7 ms 740 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 1816 ms 5176 KB Output is correct
9 Correct 1711 ms 5168 KB Output is correct