oj.uz

Submission #881905

# Submission time Handle Problem Language Result Execution time Memory
881905 2023-12-02T08:38:32 Z Pannda Holiday (IOI14_holiday) C++14
100 / 100
 57 ms 7404 KB 
#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

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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6356 KB Output is correct
2 Correct 22 ms 5960 KB Output is correct
3 Correct 38 ms 6400 KB Output is correct
4 Correct 23 ms 5952 KB Output is correct
5 Correct 56 ms 4568 KB Output is correct
6 Correct 14 ms 2396 KB Output is correct
7 Correct 27 ms 3540 KB Output is correct
8 Correct 30 ms 3540 KB Output is correct
9 Correct 9 ms 1912 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1012 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 824 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7404 KB Output is correct
2 Correct 39 ms 7108 KB Output is correct
3 Correct 13 ms 1628 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 57 ms 3320 KB Output is correct
9 Correct 57 ms 3512 KB Output is correct