Submission #582289

#	Time	Username	Problem	Language	Result	Execution time	Memory
582289		Josia	Holiday (IOI14_holiday)	C++14	47 / 100	4869 ms	1236 KiB

holiday

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

using namespace std;


long long int findFromZero(int n, int start, int d, int attraction[], int walkingFactor) {
    assert(start == 0);
    map<int, int> bestAttractions;
    long long int res = 0;
    long long int sum = 0;
    int inUse = 0;
    for (int i = 0; i<min(d, n); i++) {
        sum += attraction[i]; bestAttractions[attraction[i]]++; inUse++;

        while (i*walkingFactor + inUse > d) {
            if (bestAttractions.empty()) return res;
            sum -= (*bestAttractions.begin()).first; bestAttractions[(*bestAttractions.begin()).first]--; inUse--;
            if (bestAttractions[(*bestAttractions.begin()).first] == 0) bestAttractions.erase((*bestAttractions.begin()).first);
        }
        // cerr << i << " " << inUse << "\n";

        res = max(sum, res);
    }

    return res;
}


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (n > 3000) {
        return findFromZero(n, start, d, attraction, 1);
    }



    vector<int> left;
    vector<int> right;

    for (int i = 0; i<n; i++) {
        if (i<=start) left.push_back(attraction[i]);
        if (i>start) right.push_back(attraction[i]);
    }

    reverse(left.begin(), left.end());

    int attL[left.size()];
    int attR[right.size()];

    for (int i = 0; i<left.size(); i++) attL[i] = left[i];
    for (int i = 0; i<right.size(); i++) attR[i] = right[i];

    long long int res = 0;
    for (int i = 0; i<=d; i++) {
        long long int tmp = 0;
        tmp += findFromZero(left.size(), 0, i, attL, 1);
        tmp += findFromZero(right.size(), 0, d-i-2, attR, 2);
        res = max(res, tmp);

        tmp = 0;
        tmp += findFromZero(left.size(), 0, i, attL, 2);
        tmp += findFromZero(right.size(), 0, d-i-1, attR, 1);
        res = max(res, tmp);
    }


    return res;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i<left.size(); i++) attL[i] = left[i];
      |                     ~^~~~~~~~~~~~
holiday.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i<right.size(); i++) attR[i] = right[i];
      |                     ~^~~~~~~~~~~~~

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