Submission #1153137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153137		shezitt	Holiday (IOI14_holiday)	C++20	0 / 100	9 ms	3004 KiB

holiday

#include <vector>
#include <algorithm>
using namespace std;

struct SegmentTree {
    vector<int> sortedAttractions;
    vector<long long> prefixSum;

    SegmentTree(vector<int> attractions) {
        sort(attractions.begin(), attractions.end(), greater<int>());
        sortedAttractions = attractions;
        prefixSum.resize(sortedAttractions.size() + 1, 0);
        for (int i = 0; i < sortedAttractions.size(); ++i) {
            prefixSum[i + 1] = prefixSum[i] + sortedAttractions[i];
        }
    }

    long long query(int k) {
        if (k >= prefixSum.size()) return prefixSum.back();
        return prefixSum[k];
    }
};

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (d == 0) return 0;

    vector<int> left, right;
    for (int i = start - 1; i >= 0; --i) left.push_back(attraction[i]);
    for (int i = start + 1; i < n; ++i) right.push_back(attraction[i]);

    SegmentTree leftTree(left), rightTree(right);

    long long maxAtt = attraction[start];
    for (int a = 0; a <= left.size(); ++a) {
        for (int dir = 0; dir < 2; ++dir) {
            int cost = 2 * a + (dir ? 2 : 3) * 0;
            if (cost + 1 > d) continue;
            int remDays = d - cost - 1;
            int maxB = remDays / (dir ? 2 : 3);
            maxB = min(maxB, (int)right.size());
            maxAtt = max(maxAtt, attraction[start] + leftTree.query(a) + rightTree.query(maxB));
        }
    }

    for (int b = 0; b <= right.size(); ++b) {
        for (int dir = 0; dir < 2; ++dir) {
            int cost = 2 * b + (dir ? 2 : 3) * 0;
            if (cost + 1 > d) continue;
            int remDays = d - cost - 1;
            int maxA = remDays / (dir ? 2 : 3);
            maxA = min(maxA, (int)left.size());
            maxAtt = max(maxAtt, attraction[start] + rightTree.query(b) + leftTree.query(maxA));
        }
    }

    return maxAtt;
}

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