Submission #1056567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056567		aymanrs	Holiday (IOI14_holiday)	C++17	7 / 100	5072 ms	9120 KiB

holiday

#include"holiday.h"
#include <set>
using namespace std;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(!d) return 0;
    int et = 4*n+10;
    long long le[et], l[et];
    l[0]=le[0]=0;l[1]=le[1]=attraction[start];
    fill(l+2, l+et, -1);
    fill(le+2, le+et, -1);
    multiset<int> s;
    s.insert(attraction[start]);
    for(int i = start+1;i < n;i++){
        int e = 1;
        long long t = 0;
        s.insert(attraction[i]);
        for(auto it = s.rbegin();it != s.rend();it++,e++){
            t += *it;
            l[e+i-start] = max(l[e+i-start], t);
            le[e+2*(i-start)] = max(l[e+2*(i-start)], t);
        }
    }
    for(int i = 1;i < et;i++){
        l[i]=max(l[i], l[i-1]);
        le[i]=max(le[i], le[i-1]);
    }
    long long ans = l[d];
    s.clear();
    for(int i = start-1;i >= 0;i--){
        s.insert(attraction[i]);
        int e = 1;long long t = 0;
        for(auto it = s.rbegin();it != s.rend();it++,e++){
            t += *it;
            if(e+2*(start-i) <= d) ans = max(ans, t+l[d-(e+2*(start-i))]);
            if(e+start-i <= d) ans = max(ans, t+le[d-(e+start-i)]);
        }
    }
    return ans;
}

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