Submission #1062849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062849		phoenix	Holiday (IOI14_holiday)	C++17	47 / 100	5071 ms	2488 KiB

holiday

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

using namespace std;

const int N = 100100;

int n, d;
int a[N];

long long solve(int s, int d) {
    if (d <= 0) return 0ll;
    priority_queue<int, vector<int>, greater<int>> pq;
    long long sum = 0;
    long long res = 0;

    
    for (int i = s; i < n; i++) {
        sum += a[i];
        pq.push(a[i]);
        while (!pq.empty() && (int)pq.size() > d - i + s) {
            sum -= pq.top();
            pq.pop();
        }
        res = max(res, sum);
    }
    return res;
}

long long findMaxAttraction(int _n, int start, int _d, int _attraction[]) {
    n = _n;
    for (int i = 0; i < n; i++)
        a[i] = _attraction[i];
    d = _d;
    if (start == 0)
        return solve(0, d);
    
    long long res = 0;
    for (int it = 0; it < 2; it++) {
        for (int i = start; i >= 0; i--) {
            res = max(res, solve(i, d - start + i));
        }
        reverse(a, a + n);
        start = n - 1 - start;
    }
    
    return res;
}

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