Submission #1035864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035864		d4xn	Holiday (IOI14_holiday)	C++17	47 / 100	5029 ms	5044 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()

const int N = 1e5;

int n, s, d, a[N];

int findMaxAttraction(signed N, signed S, signed D, signed attraction[]) {
    n = N;
    s = S;
    d = D;
    for (int i = 0; i < n; i++) {
        a[i] = attraction[i];
    }

    int ans = 0;
    for (int i = 0; i <= s; i++) {
        priority_queue<int, vector<int>, greater<int>> pq;
    
        int sum = 0;
        int rem = d - (s-i);
        if (rem <= 0) continue;

        vector<int> vt(s-i+1);
        for (int j = i; j <= s; j++) {
            vt[j-i] = a[j];
        }
        sort(all(vt));

        for (int j = s-i; j >= max(0ll, s-i-rem+1); j--) {
            sum += vt[j];
            pq.push(vt[j]);
        }
        rem -= min(rem, s-i+1);

        ans = max(ans, sum);
        for (int j = s+1; j < n; j++) {
            rem = d - pq.size() - (j-i) - min(s-i, j-s);

            while (rem < 0) {
                if (pq.empty()) break;

                sum -= pq.top();
                pq.pop();
            
                rem++;
            }
            if (rem < 0) break;

            if (rem) {
                sum += a[j];
                pq.push(a[j]);
            
                rem--;
            }
            else if (!pq.empty() && pq.top() < a[j]) {
                sum -= pq.top();
                pq.pop();

                sum += a[j];
                pq.push(a[j]);
            }

            ans = max(ans, sum);
        }
    }

    return ans;
}

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