Submission #1276198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276198		KindaGoodGames	Holiday (IOI14_holiday)	C++20	0 / 100	67 ms	131072 KiB

holiday

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

using namespace std;
#define int long long


long long findMaxAttraction(int32_t n, int32_t s, int32_t d, int32_t arr[]) { 
    vector<vector<int>> left(d+1, vector<int>(d+1));
    vector<vector<int>> right(d+1, vector<int>(d+1)); 

    vector<int> bleft(d+1);
    vector<int> bright(d+1);

    int best = 0;
    for(int k = 0; k <= d; k++){
        int sum = 0;
        int ma = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = s; i < n; i++){
            sum += arr[i];
            int len = i-s;
            pq.push(arr[i]);

            if(len > k) break;
            while(len+pq.size() > k){
                sum -= pq.top();    
                pq.pop();
            }
            right[k][len] = sum;
            ma = max(ma,sum);
        } 
        bright[k] = ma;
    }
    
    if(s == 0){
        return bright[d];
    }
    s--;
    for(int k = 0; k <= d; k++){
        int sum = 0;
        int ma = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = s; i >= 0; i--){
            sum += arr[i];
            int len = s-i;
            pq.push(arr[i]);

            if(len > k) break;
            while(len+pq.size() > k){
                sum -= pq.top();    
                pq.pop();
            }
            left[k][len] = sum;
            ma = max(ma,sum);
        } 
        bleft[k] = ma;
    }
     
    int ans = 0;

    for(int l = 0; l <= d; l++){
        for(int steps = 0; steps <= l; steps++){
            int r = d-l-steps-1;
            if(r < 0) break;
            int c = 0;
            c += left[l-steps][min(steps,l-steps)];
            c += bright[r];
            if(c > ans){
                ans = c;
            }
        }
    }
    return ans;
}

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