Submission #1166981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166981		HappyCapybara	Holiday (IOI14_holiday)	C++20	47 / 100	5094 ms	5856 KiB

holiday

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

#define ll long long

int n;
vector<int> a;

ll solve(int s, int d, bool l){
    ll res = 0;
    int k = d+1;
    multiset<int> best;
    ll cur = 0;
    int x = 1;
    if (l) x = -1;
    for (int i=0; abs(i)<d; i+=x){
        if (s+i >= n || s+i < 0) break;
        k--;
        if (best.size() < k || a[s+i] > *best.begin()){
            best.insert(a[s+i]);
            cur += a[s+i];
        }
        while (best.size() > k){
            cur -= *best.begin();
            best.erase(best.begin());
        }
        res = max(res, cur);
    }
    return res;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]){
    ::n = n;
    a.resize(n);
    for (int i=0; i<n; i++) a[i] = attraction[i];
    if (start == 0) return solve(0, d, false);
    ll res = 0;
    for (int i=0; i<d; i++){
        if (start+i < n) res = max(res, solve(start+i, d-i, true));
        if (start-i >= 0) res = max(res, solve(start-i, d-i, false));
    }
    return res;
}

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