Submission #847308

#	Time	Username	Problem	Language	Result	Execution time	Memory
847308		Ahmed57	The short shank; Redemption (BOI21_prison)	C++17	45 / 100	281 ms	14572 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define int long long
pair<long long,long long> dp[5001];
long long n,k,T,arr[5001];
pair<long long,long long> solve(int mid){
    dp[0] = {0,0};
    for(int i = 1;i<=n;i++){
        dp[i] = {1e9,-1e9};
    }
    for(int i = 0;i<n;i++){
        long long c1 = 0 , la = 0;
        for(int j = i;j<n;j++){
            if(j==i){
                c1+=(arr[j]<=T);
                la = arr[j];
            }else{
                if(la+1<=arr[j]){
                    c1+=((la+1)<=T);
                    la++;
                }else{
                    c1+=(arr[j]<=T);
                    la = arr[j];
                }
            }
            if(dp[j+1].first>(dp[i].first+c1+mid)){
                dp[j+1].first = dp[i].first+c1+mid;
                dp[j+1].second = dp[i].second+1;
            }else if(dp[j+1].first==(dp[i].first+c1+mid)&&dp[j+1].second<dp[i].second+1){
                dp[j+1].second = dp[i].second+1;
            }
        }
    }
    dp[n].second--;
    dp[n].first -= mid;
    return dp[n];
}
signed main(){
    cin>>n>>k>>T;
    if(k==1){
        int arr[n];
    for(int i = 0;i<n;i++)cin>>arr[i];
    int la = 0;
    int pref[n] = {0};
    for(int i = 0;i<n;i++){
        if(i==0){
            la = arr[i];
            pref[i] = (arr[i]<=T);
        }else{
            if(la+1<=arr[i]){
                la++;
                pref[i] = (la<=T);
            }else{
                la = arr[i];
                pref[i] = (arr[i]<=T);
            }
            pref[i] += pref[i-1];
        }
    }
    stack<pair<pair<int,int>,int>> suf;int suff[n+1] = {0};
    long long an = 0;
    for(int i = n-1;i>=0;i--){
        long long val = arr[i]-i;
        an+=(arr[i]<=T);
        int st  = i+1;
        while(!suf.empty()&&suf.top().first.first>=val){
            int xd = suf.top().first.second;
            int len1 = 0;
            if(xd<=T){
                len1 = min(suf.top().second,(T-xd+1));
            }
            int len2 = 0;
            xd = arr[i];
            if(xd+(st-i)<=T){
                len2 = min(suf.top().second,(T-(xd+(st-i))+1));
            }
            an+=max(0ll,len2-len1);
            st+=suf.top().second;
            suf.pop();
        }
        suf.push({{val,arr[i]},st-i});
        suff[i] = an;
    }
    int all = 1e18;
    for(int i = 0;i<n;i++){
        all = min(all,pref[i]+suff[i+1]);
    }
    cout<<all<<endl;
    return 0;
    }
    for(int i = 0;i<n;i++)cin>>arr[i];
    long long l = 0 , r = n , ans = 0;
    while(l<=r){
        long long mid = (l+r)/2;
        pair<int,int> p = solve(mid);
        if(p.second>=k){
            ans = p.first-k*mid;
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    cout<<ans<<endl;
}

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