Submission #770772

#	Time	Username	Problem	Language	Result	Execution time	Memory
770772		That_Salamander	Holiday (IOI14_holiday)	C++14	23 / 100	35 ms	5480 KiB

holiday

#include <bits/stdc++.h>

#ifndef LOCAL_TEST
#include "holiday.h"
#endif

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    multiset<int> included;
    multiset<int> excluded;
    long long sum = 0;
    long long res = 0;

    for (int i = 0; i < min(d + 1, n); i++) {
        excluded.insert(attraction[i]);

        int canTake = d - i;

        while (included.size() > canTake) {
            auto it = included.begin();
            excluded.insert(*it);
            sum -= *it;
            included.erase(it);
        }

        while (included.size() < canTake && excluded.size()) {
            auto it = (--excluded.end());
            included.insert(*it);
            sum += *it;
            excluded.erase(*it);
        }

        while (included.size() && excluded.size() && *included.begin() < *(--excluded.end())) {
            int fromIncluded = *included.begin();
            int fromExcluded = *(--excluded.end());

            included.erase(included.begin());
            excluded.erase(--excluded.end());

            included.insert(fromExcluded);
            excluded.insert(fromIncluded);

            sum -= fromIncluded;
            sum += fromExcluded;
        }

        res = max(sum, res);
    }

    return res;
}

#ifdef LOCAL_TEST
namespace hidden {
    int attraction[1000000];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, start, d;

    cin >> n >> start >> d;

    FOR(i, n) {
        cin >> hidden::attraction[i];
    }

    cout << findMaxAttraction(n, start, d, hidden::attraction) << endl;
}
#endif

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:29:32: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         while (included.size() > canTake) {
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~
holiday.cpp:36:32: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while (included.size() < canTake && excluded.size()) {
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~

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