Submission #847301

#	Time	Username	Problem	Language	Result	Execution time	Memory
847301		Ahmed57	The short shank; Redemption (BOI21_prison)	C++17	35 / 100	127 ms	604 KiB

prison

#include <bits/stdc++.h>
using namespace std;
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];
}
int main(){
    cin>>n>>k>>T;
    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: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20