oj.uz

Submission #770772

# Submission time Handle Problem Language Result Execution time Memory
770772 2023-07-01T22:42:15 Z That_Salamander Holiday (IOI14_holiday) C++14
23 / 100
 35 ms 5480 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Incorrect 0 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5360 KB Output is correct
2 Correct 25 ms 5344 KB Output is correct
3 Correct 25 ms 5356 KB Output is correct
4 Correct 25 ms 5312 KB Output is correct
5 Correct 35 ms 4932 KB Output is correct
6 Correct 9 ms 2004 KB Output is correct
7 Correct 16 ms 3172 KB Output is correct
8 Correct 21 ms 3744 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 828 KB Output is correct
4 Incorrect 1 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5360 KB Output is correct
2 Correct 30 ms 5480 KB Output is correct
3 Incorrect 6 ms 1132 KB Output isn't correct
4 Halted 0 ms 0 KB -