Submission #597764

#	Time	Username	Problem	Language	Result	Execution time	Memory
597764		AlperenT	Holiday (IOI14_holiday)	C++17	100 / 100	1208 ms	7792 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;

const long long INF = 2e18;

struct Item{
    int l, r, optl, optr;
};

long long findMaxAttraction(int n, int s, int d, int attraction[]){
    long long ans = 0;

    vector<Item> cur, nxt;

    cur.push_back({0, n - 1, 0, n - 1});

    while(!cur.empty()){
        int lptr = 0, rptr = -1;
        long long sum = 0;

        multiset<int> taken, nottaken;

        for(auto itm : cur){
            int m = itm.l + (itm.r - itm.l) / 2;

            pair<long long, int> bst = {-INF, -1};

            for(int i = max({s, m, itm.optl}); i <= itm.optr; i++){
                while(rptr < i){
                    rptr++;

                    nottaken.insert(attraction[rptr]);
                }

                while(lptr < m){
                    if(nottaken.find(attraction[lptr]) != nottaken.end()){
                        nottaken.erase(nottaken.find(attraction[lptr]));
                    }
                    else{
                        sum -= attraction[lptr];
                        taken.erase(taken.find(attraction[lptr]));
                    }

                    lptr++;
                }

                int cnt = min(d - (i - m + min(s - m, i - s)), i - m + 1);

                if(cnt >= 0 && m <= s){
                    while(!nottaken.empty() && !taken.empty() && *prev(nottaken.end()) > *taken.begin()){
                        int x = *prev(nottaken.end()), y = *taken.begin();

                        sum -= y;
                        sum += x;

                        nottaken.erase(nottaken.find(x));
                        nottaken.insert(y);

                        taken.erase(taken.find(y));
                        taken.insert(x);
                    }

                    while(taken.size() < cnt){
                        sum += *prev(nottaken.end());

                        taken.insert(*prev(nottaken.end()));
                        nottaken.erase(prev(nottaken.end()));
                    }

                    while(taken.size() > cnt){
                        sum -= *taken.begin();

                        nottaken.insert(*taken.begin());
                        taken.erase(taken.begin());
                    }
                }

                bst = max(bst, {sum, i});
            }

            ans = max(ans, bst.first);

            if(itm.l <= m - 1) nxt.push_back({itm.l, m - 1, itm.optl, bst.second});
            if(m + 1 <= itm.r) nxt.push_back({m + 1, itm.r, bst.second, itm.optr});
        }

        swap(cur, nxt);
        nxt.clear();
    }

    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:65:40: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |                     while(taken.size() < cnt){
      |                           ~~~~~~~~~~~~~^~~~~
holiday.cpp:72:40: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |                     while(taken.size() > cnt){
      |                           ~~~~~~~~~~~~~^~~~~

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