Submission #261446

#	Time	Username	Problem	Language	Result	Execution time	Memory
261446		A02	Holiday (IOI14_holiday)	C++14	24 / 100	5055 ms	2132 KiB

holiday

#include"holiday.h"
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <queue>

using namespace std;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {

    if (d == 0){
        return 0;
    }

//    if (start == 0){
//
//        long long best = attraction[0];
//
//        multiset<pair<long long, long long> > best_cities;
//        best_cities.insert(attraction[0], 0);
//        long long current_sum = attraction[0];
//        pair<long long, long long> last_in_sum = make_pair(attraction[0], 0);
//
//        for (int r = 1; r < d; r++){
//
//            long long can_visit = d - r;
//
//            best_cities.insert(make_pair(attraction[r], -r));
//
//            if (can_visit >= best_cities.size()){
//                current_sum += attraction[r];
//                last_in_sum = *(best_cities.begin());
//            } else{
//                if (can_visit == best_cities.size() - 1){
//                    current_sum += attraction[r];
//                    current_sum -= (best_cities.begin()) -> first;
//                    last_in_sum = *(++best_cities.begin());
//                } else {
//
//                    if (attraction[r] <= last_in_sum.first){
//
//                        current_sum -= last_in_sum.first;
//                        last_in_sum = *(++best_cities.lower_bound(last_in_sum));
//
//                    } else{
//
//                        current_sum += attraction[r];
//                        current_sum -= last_in_sum.first;
//                        last_in_sum = *(++best_cities.lower_bound(last_in_sum));
//                        current_sum -= last_in_sum.first;
//                        last_in_sum = *(++best_cities.lower_bound(last_in_sum));
//                    }
//
//                }
//            }
//
//            best = max(best, current_sum);
//        }
//
//
//        return best;
//    }

    long long total = 0;

    for (int left = start; left >= 0 && start - left < d; left--){

        int can_visit = d - (start - left);

        priority_queue<long long> best;

        long long best_sum = 0;

        for (int i = left; i <= start; i++){
            best.push(-attraction[i]);
            best_sum += attraction[i];
        }

        while (best.size() > can_visit){
            best_sum -= -best.top();
            best.pop();
        }

        int right = start;

        total = max(total, best_sum);

        while (can_visit > 2 && right < n - 1){
            can_visit -= 2;

            right++;
            best.push(-attraction[right]);
            best_sum += attraction[right];

            while (best.size() > can_visit){
                best_sum -= -best.top();
                best.pop();
            }

            total = max(total, best_sum);
        }

    }

    for (int right = start; right < n && right - start < d; right++){

        int can_visit = d - (right - start);

        priority_queue<long long> best;

        long long best_sum = 0;

        for (int i = start; i <= right; i++){
            best.push(-attraction[i]);
            best_sum += attraction[i];
        }

        while (best.size() > can_visit){
            best_sum -= -best.top();
            best.pop();
        }

        int left = start;

        total = max(total, best_sum);

        while (can_visit > 2 && left > 0){
            can_visit -= 2;

            left--;
            best.push(-attraction[left]);
            best_sum += attraction[left];

            while (best.size() > can_visit){
                best_sum -= -best.top();
                best.pop();
            }

            total = max(total, best_sum);
        }

    }

    return total;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:82:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (best.size() > can_visit){
                ~~~~~~~~~~~~^~~~~~~~~~~
holiday.cpp:98:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (best.size() > can_visit){
                    ~~~~~~~~~~~~^~~~~~~~~~~
holiday.cpp:121:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (best.size() > can_visit){
                ~~~~~~~~~~~~^~~~~~~~~~~
holiday.cpp:137:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (best.size() > can_visit){
                    ~~~~~~~~~~~~^~~~~~~~~~~

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