Submission #500776

#	Time	Username	Problem	Language	Result	Execution time	Memory
500776		InternetPerson10	Holiday (IOI14_holiday)	C++17	47 / 100	457 ms	5364 KiB

holiday

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

using namespace std;
typedef long long ll;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    ll best = 0;
    // Try left
    ll ans = 0;
    multiset<int> s;
    int g = d;
    for(int i = start; i < n; i++) {
        ans += attraction[i];
        s.insert(attraction[i]);
        while(g < s.size()) {
            auto it = s.begin();
            ans -= *(it);
            s.erase(it); 
        }
        g--;
        best = max(ans, best);
        if(g == 0) break;
    }
    multiset<int>().swap(s);
    // Try right
    g = d;
    ans = 0;
    for(int i = start; i >= 0; i--) {
        ans += attraction[i];
        s.insert(attraction[i]);
        while(g < s.size()) {
            auto it = s.begin();
            ans -= *(it);
            s.erase(it);
        }
        g--;
        best = max(ans, best);
        if(g == 0) break;
    }
    multiset<int>().swap(s);
    if(n <= 20) { // Subtask 1
        for(int le = 0; le < start; le++) {
            ll ans = 0;
            int l = start - le;
            for(int i = le; i <= start; i++) {
                s.insert(attraction[i]);
                ans += attraction[i];
            }
            for(int rr = start+1; rr < n; rr++) {
                int r = rr - start;
                s.insert(attraction[rr]);
                ans += attraction[rr];
                int g = d - (l + r + min(l, r));
                if(g <= 0) break;
                while(g < s.size()) {
                    auto it = s.begin();
                    ans -= *(it);
                    s.erase(it);
                }
                best = max(ans, best);
            }
            multiset<int>().swap(s);
        }
        return best;
    }
    else if(start == 0) { // Subtask 2
        return best;
    }
    else if(n <= 3000) { // Subtask 3
        for(int le = 0; le < start; le++) {
            ll ans = 0;
            int l = start - le;
            for(int i = le; i <= start; i++) {
                s.insert(attraction[i]);
                ans += attraction[i];
            }
            for(int rr = start+1; rr < n; rr++) {
                int r = rr - start;
                s.insert(attraction[rr]);
                ans += attraction[rr];
                int g = d - (l + r + min(l, r));
                if(g <= 0) break;
                while(g < s.size()) {
                    auto it = s.begin();
                    ans -= *(it);
                    s.erase(it);
                }
                best = max(ans, best);
            }
            multiset<int>().swap(s);
        }
        return best;
    }
    // Subtask 4
    return 0;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(g < s.size()) {
      |               ~~^~~~~~~~~~
holiday.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while(g < s.size()) {
      |               ~~^~~~~~~~~~
holiday.cpp:57:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 while(g < s.size()) {
      |                       ~~^~~~~~~~~~
holiday.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 while(g < s.size()) {
      |                       ~~^~~~~~~~~~

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