Submission #1276202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276202		KindaGoodGames	Holiday (IOI14_holiday)	C++20	7 / 100	68 ms	131072 KiB

holiday

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

using namespace std;
#define int long long

int solve(int n, int s, int d, vector<int> 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 += right[l][min(steps,l)];
            c += bleft[r];
            if(c > ans){
                ans = c;
            }
        }
    }
    return ans;
}

long long findMaxAttraction(int32_t n, int32_t s, int32_t d, int32_t A[]) { 
    vector<int> arr(n);
    for(int i = 0; i < n; i++){
        arr[i] = A[i];
    }

    int v1 = 0;
    v1 = solve(n,s,d,arr);
    reverse(arr.begin(),arr.end());
    s = (n-1)-s;
    int v2 = 0;
    v2 = solve(n,s,d,arr);
    return max(v1,v2);
}

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