Submission #601566

#	Time	Username	Problem	Language	Result	Execution time	Memory
601566		alexander707070	The short shank; Redemption (BOI21_prison)	C++14	15 / 100	2078 ms	17044 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];

int fenwick[MAXN],us[MAXN],tim;

inline void check(int x){
    if(us[x]!=tim)fenwick[x]=0;
    us[x]=tim;
}

void update(int x){
    if(x==0)return;
    while(x<=n){
        check(x);
        fenwick[x]++;
        x+=(x & (-x));
    }
}

int getsum(int x){
    if(x==0)return 0;
    int res=0;
    while(x>=1){
        check(x);
        res+=fenwick[x];
        x-=(x & (-x));
    }
    return res;
}

int cost(int from){
    return getsum(n)-getsum(from-1);
}

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; tim++;

    for(int i=mid;i>=optl;i--){
        update(poss[i]);
        if(dp[i-1][(k-1)%2]+cost(i)<=dp[mid][k%2]){
            dp[mid][k%2]=dp[i-1][(k-1)%2]+cost(i);
            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[0][0]=0;
    for(int i=1;i<=n;i++){
        dp[i][0]=inf;
    }

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

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

    return 0;
}

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