Submission #1056715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056715		Piokemon	The short shank; Redemption (BOI21_prison)	C++17	25 / 100	33 ms	16844 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 500;
constexpr int N2 = 2e6;
int koszt[N+9][N+9];
int dp[N+9][N+9];
int a[N2+9];
int pref[N2+9];
int suf[N2+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,t;
    cin >> n >> d >> t;
    for (int x=1;x<=n;x++){
        cin >> a[x];
    }
    if (n<=500){
        for (int x=1;x<=n;x++){
            int val=0;
            int pop=1e9;
            for (int y=x;y<=n;y++){
                pop = min(a[y],pop+1);
                if (pop<=t)val++;
                koszt[x][y]=val;
            }
        }
        for (int x=0;x<=n+1;x++){
            for (int y=0;y<=d+1;y++)dp[x][y]=1e9;
        }
        dp[1][0]=0;
        for (int x=1;x<=n;x++){
            for (int k=0;k<=d;k++){
                for (int y=x+1;y<=n+1;y++){
                    dp[y][k+1]=min(dp[y][k+1],dp[x][k]+koszt[x][y-1]);
                }
            }
        }
        cout << dp[n+1][d+1] << '\n';
    }
    else{
        int pop=1e9;
        pref[0]=0;
        for (int x=1;x<=n;x++){
            pop=min(a[x],pop+1);
            pref[x]=pref[x-1];
            if (pop<=t)pref[x]++;
        }
        vector<int> wez; wez.push_back(2e9);
        suf[n+1]=0;
        for (int x=n;x>=1;x--){
            wez.push_back(x);
            int rang=x-1;
            suf[x]=suf[x+1];
            if (a[x]<=t)rang=x+(t-a[x]);
            while(wez.back()<=rang){
                suf[x]++;
                wez.pop_back();
            }
        }
        int odp=1e9;
        for (int x=1;x<n;x++){
            odp=min(odp,pref[x]+suf[x+1]);
        }
        cout << odp << '\n';
    }
    return 0;
}

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