Submission #720775

#	Time	Username	Problem	Language	Result	Execution time	Memory
720775		Johann	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	79 ms	7016 KiB

prison

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

#define ll long long
#define pii pair<int, int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvpii vector<vpii>
#define sz(x) (int)(x).size()

int N, D, T;
vi F, NF;
vector<priority_queue<pii, vpii, greater<pii>>> Q;
vi P;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> D >> T;
    D = min(D, N);
    P.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> P[i];

    F.assign(D + 1, 0), NF.assign(D + 1, 0);
    Q.resize(D + 1);

    for (int i = 0; i < N; ++i)
    {
        for (int d = 0; d <= D; ++d)
        {
            NF[d] = min(F[d], NF[d]);
            if (d < D)
                F[d + 1] = min(F[d + 1], NF[d]);
            ++NF[d];

            if (P[i] <= T)
            {
                F[d] = INT_MAX;
                int nextBorder = min(N - 1, i + T - P[i]);
                while (!Q[d].empty() && Q[d].top().first <= nextBorder)
                    Q[d].pop();
                Q[d].push({nextBorder, NF[d] + nextBorder - i});
            }
            while (!Q[d].empty() && Q[d].top().first == i)
            {
                F[d] = min(F[d], Q[d].top().second);
                Q[d].pop();
            }
            NF[d] = min(NF[d], F[d]);
        }
    }
    cout << NF[D] << endl;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20