Submission #1153163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153163		shezitt	Holiday (IOI14_holiday)	C++20	0 / 100	10 ms	2752 KiB

holiday

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

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

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

    long long query(int k) {
        if (k <= 0) return 0;
        k = min(k, (int)prefixSum.size() - 1);
        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 = 0;

    // Case 1: Visit start first
    if (d >= 1) {
        maxAtt = attraction[start];
    }

    // Explore left then right
    for (int a = 0; a <= left.size(); ++a) {
        // Days used: a (move left) + 1 (visit start) + 2*b (move and visit right)
        int daysUsed = a + 1;
        if (daysUsed > d) continue;
        int remaining = d - daysUsed;
        int maxB = min(remaining / 2, (int)right.size());
        long long current = attraction[start] + leftTree.query(a) + rightTree.query(maxB);
        maxAtt = max(maxAtt, current);
    }

    // Explore right then left
    for (int b = 0; b <= right.size(); ++b) {
        int daysUsed = b + 1;
        if (daysUsed > d) continue;
        int remaining = d - daysUsed;
        int maxA = min(remaining / 2, (int)left.size());
        long long current = attraction[start] + rightTree.query(b) + leftTree.query(maxA);
        maxAtt = max(maxAtt, current);
    }

    // Consider visiting only left or only right
    for (int a = 0; a <= left.size(); ++a) {
        int daysNeeded = a + (a > 0 ? 1 : 0); // Move a steps + visit start if a > 0
        if (daysNeeded > d) continue;
        int remaining = d - daysNeeded;
        long long current = (a > 0 ? attraction[start] : 0) + leftTree.query(a);
        maxAtt = max(maxAtt, current);
    }

    for (int b = 0; b <= right.size(); ++b) {
        int daysNeeded = b + (b > 0 ? 1 : 0);
        if (daysNeeded > d) continue;
        int remaining = d - daysNeeded;
        long long current = (b > 0 ? attraction[start] : 0) + rightTree.query(b);
        maxAtt = max(maxAtt, current);
    }

    return maxAtt;
}

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