Submission #881905

#	Time	Username	Problem	Language	Result	Execution time	Memory
881905		Pannda	Holiday (IOI14_holiday)	C++14	100 / 100	57 ms	7404 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

long long work(int n, int s, int d, vector<int> &a) {
    priority_queue<int, vector<int>, greater<>> pq;
    long long sum = 0;
    long long ans0 = -1;
    int key0;
    for (int i = s; i < n && i - s <= d; i++) {
        pq.push(a[i]);
        sum += a[i];
        while (i - s + pq.size() > d) {
            sum -= pq.top();
            pq.pop();
        }
        if (sum > ans0) {
            ans0 = sum;
            key0 = i;
        }
    }

    set<array<int, 2>> st;
    for (int i = s; i <= key0; i++) {
        st.insert({a[i], i});
        while (i - s + st.size() > d) {
            st.erase(st.begin());
        }
    }

    long long ans = ans0;
    for (int i = s - 1; i >= 0 && s - i <= d; i--) {
        st.insert({a[i], i});
        ans0 += a[i];
        while (key0 > s && !st.count({a[key0], key0})) {
            key0--;
        }
        int cost = st.size() + key0 - s + key0 - i;
        while (cost > d) {
            if (cost == d + 1) {
                ans0 -= (*st.begin())[0];
                st.erase(st.begin());
                break;
            }
            int worst = (*st.begin())[0];
            int second_worst = (*next(st.begin()))[0];
            int rightmost = a[key0];
            if (key0 > s && st.count({a[key0], key0}) && rightmost <= worst + second_worst) {
                ans0 -= rightmost;
                st.erase({a[key0], key0});
            } else {
                ans0 -= worst + second_worst;
                st.erase(st.begin());
                st.erase(st.begin());
            }
            while (key0 > s && !st.count({a[key0], key0})) {
                key0--;
            }
            cost = st.size() + min(s - i, key0 - s) + key0 - i;
        }
        ans = max(ans, ans0);
    }

    return ans;
}

long long findMaxAttraction(int n, int s, int d, int attraction[]) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = attraction[i];
    }

    long long ans1 = work(n, s, d, a);
    reverse(a.begin(), a.end());
    s = n - 1 - s;
    long long ans2 = work(n, s, d, a);
    return max(ans1, ans2);
}

//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//
//}

Compilation message (stderr)

holiday.cpp: In function 'long long int work(int, int, int, std::vector<int>&)':
holiday.cpp:12:34: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<void> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |         while (i - s + pq.size() > d) {
      |                ~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:25:34: warning: comparison of integer expressions of different signedness: 'std::set<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |         while (i - s + st.size() > d) {
      |                ~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:23:23: warning: 'key0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     for (int i = s; i <= key0; i++) {
      |                     ~~^~~~~~~

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