Submission #1278925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278925		stanwaibbange	Holiday (IOI14_holiday)	C++20	23 / 100	10 ms	1216 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = numeric_limits<int>::max() / 2;

void dodp(int n, int d, int attraction[], int step, int cost, vector<int>& out) {
    vector<int> dp(d+1,0);
    int *pos = attraction;
    for (int i{0};i<n;++i) {
        vector<int> ndp(d+1,0);
        ndp[0] = -INF;
        if (cost == 1) {
            if (d>=1) {
            ndp[1] = dp[0];
            if (d>=2) {
            ndp[2] = max(dp[2-cost-1]+*pos,dp[2-cost]);
            out[2] = max(ndp[2],out[2]);
            }
            }
        }
        if (cost == 2) {
            if (d>=1) {
            ndp[1] = -INF;
            if (d>=2) {
            ndp[2] = dp[0];
            }}

        }
        for (int j{3};j<d+1;++j) {
            ndp[j] = max(dp[j-cost-1]+*pos,dp[j-cost]);
            out[j] = max(ndp[j],out[j]);
        }
        ndp.swap(dp);
        pos += step;
    }
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    if (start == 0)
    {
        ll out = 0;
        ll cur = 0;
        ll get = d + 1;
        ll size = 0;
        ll i = 0;
        priority_queue<int, std::vector<int>, std::greater<int>> pq{};
        while (get > size + 1 && i < n)
        {
            pq.push(attraction[i]);
            cur += attraction[i];
            --get;
            ++size;
            ++i;
        }
        if (get > size && i < n)
        {
            pq.push(attraction[i]);
            cur += attraction[i];
            cur -= pq.top();
            pq.pop();
            --get;
            ++i;
        }
        out = cur;
        while (i < n)
        {
            pq.push(attraction[i]);
            cur += attraction[i];
            cur -= pq.top();
            pq.pop();
            if (pq.empty())
            {
                break;
            }
            cur -= pq.top();
            pq.pop();
            out = max(out, cur);
            --get;
            --size;
            ++i;
        }
        return out;
    }
    int l1 = start;
    int l2 = n-start-1;
    int *seg1 = attraction;
    int *seg2 = attraction+start+1;
    vector<int> dpl1(d+1,0);
    dodp(l1,d,seg1,-1,1,dpl1);
    vector<int> dpl2(d+1,0);
    dodp(l1,d,seg1,-1,2,dpl2);
    vector<int> dpr1(d+1,0);
    dodp(l2,d,seg2,1,1,dpr1);
    vector<int> dpr2(d+1,0);
    dodp(l2,d,seg2,1,2,dpr2);
    int out = 0;
    out = max(out,dpl1[0]+dpr2[d]);
    out = max(out,dpl2[0]+dpr1[d]);
    for (int i{1};i<d+1;++i){
        out = max(out,dpl1[i]+dpr2[d-i]);
        out = max(out,dpl2[i]+dpr1[d-i]);
        out = max(out,dpl1[i-1]+dpr2[d-i]+attraction[start]);
        out = max(out,dpl2[i-1]+dpr1[d-i]+attraction[start]);
    }
    return out;
}

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