Submission #601581

#	Time	Username	Problem	Language	Result	Execution time	Memory
601581		alexander707070	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	2073 ms	17384 KiB

prison

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 200007
using namespace std;

const long long inf=1e16;

int n,d;
long long t,a[MAXN],b[MAXN],poss[MAXN];

long long dp[MAXN][2],cost;

void solve(int l,int r,int optl,int optr,int k){
    if(l>r)return;

    int mid=(l+r)/2,opt=0;
    dp[mid][k%2]=inf; cost=0;

    for(int i=mid;i<=optr;i++){
        if(poss[i]>=mid)cost++;
        if(dp[i+1][(k-1)%2]+cost<dp[mid][k%2]){
            dp[mid][k%2]=dp[i+1][(k-1)%2]+cost;
            opt=i;
        }
    }

    solve(l,mid-1,optl,opt,k);
    solve(mid+1,r,opt,optr,k);
}

int power[20],lg[MAXN];
long long mind[MAXN][20];
bool li[MAXN][20];

void calc(){
    power[0]=1; lg[1]=0;
    for(int i=1;i<20;i++)power[i]=power[i-1]*2;
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
}

long long rmq(int i,int j){
    if(j==0)return b[i];

    if(li[i][j])return mind[i][j];
    li[i][j]=true;

    mind[i][j]=min(rmq(i,j-1),rmq(i+power[j-1],j-1));
    return mind[i][j];
}

long long getmin(int l,int r){
    return min( rmq(l,lg[r-l+1]) , rmq(r-power[lg[r-l+1]]+1,lg[r-l+1]) );
}

int main(){

    cin>>n>>d>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-i;
    }
    calc();

    for(int i=1;i<=n;i++){
        int l=0,r=i+1,mid;
        while(l+1<r){
            mid=(l+r)/2;
            if(min(getmin(mid,i)+i,a[i])<=t){
                l=mid;
            }else{
                r=mid;
            }
        }
        poss[i]=l;
    }

    dp[n+1][0]=0;
    for(int i=1;i<=n;i++){
        dp[i][0]=inf;
    }

    for(int i=1;i<=d+1;i++){
        dp[n+1][i%2]=inf;
        solve(1,n,1,n,i);
    }

    cout<<dp[1][(d+1)%2]<<"\n";

    return 0;
}

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