Submission #1101036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101036		epicci23	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	1356 ms	524288 KiB

prison

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e9;
const int LOG = 20;
int n,d,t;
vector<int> ar,dp,ndp,A;
vector<vector<int>> lift,cost;

inline int get_cost(int l,int r,int res=0LL){
  for(int i=LOG-1;i>=0;i--){
    if(lift[l][i]>r) continue;
    res+=cost[l][i];
    l=lift[l][i];
  }
  int patla=min(r+1,l+max(0,t+1-ar[l]));
  res+=patla-l;
  return res;
}

void f(int l,int r,int optl,int optr){
  if(l>r) return;
  int mid=(l+r)/2;
  int opt=-1;
  for(int i=optl;i<=min(mid-1,optr);i++){
  	if(ndp[mid]>dp[i]+cost[i+1][mid]) opt=i;
    ndp[mid]=min(ndp[mid],dp[i]+cost[i+1][mid]);
  }
  f(l,mid-1,optl,opt),f(mid+1,r,opt,optr);
}

void f2(int l,int r,int optl,int optr){
  if(l>r) return;
  int mid=(l+r)/2;
  int opt=-1;
  for(int i=optl;i<=min(mid-1,optr);i++){
  	if(ndp[mid]>dp[i]+get_cost(i+1,mid)) opt=i;
    ndp[mid]=min(ndp[mid],dp[i]+get_cost(i+1,mid));
  }
  f2(l,mid-1,optl,opt),f2(mid+1,r,opt,optr);
}

void _(){
  cin >> n >> d >> t;
  ar.resize(n+5),A.resize(n+5),dp.resize(n+5),ndp.resize(n+5);
  for(int i=1;i<=n;i++) cin >> ar[i];

  if(d<=20){
   lift.assign(n+5,vector<int>(LOG,0));
   cost.assign(n+5,vector<int>(LOG,0));
   for(int i=1;i<=n;i++) A[i]=ar[i]-i;
   stack<int> s;
   for(int i=1;i<=n;i++){
    while(!s.empty() && A[s.top()]>A[i]){
     lift[s.top()][0]=i;
     s.pop();
    }
    s.push(i);
   }

   while(!s.empty()){
   	 lift[s.top()][0]=n+1;
   	 s.pop();
   }
   
   for(int i=0;i<LOG;i++){
   	lift[n+1][i]=n+1;
   	cost[n+1][i]=0;
   }

   for(int i=1;i<=n;i++){
     int r=lift[i][0]-1;
     int patla=min(r+1,i+max(0,t+1-ar[i]));
     cost[i][0]=patla-i;
   }

   for(int j=1;j<LOG;j++){
   	for(int i=1;i<=n;i++){
   	  cost[i][j]=cost[i][j-1]+cost[lift[i][j-1]][j-1];
   	  lift[i][j]=lift[lift[i][j-1]][j-1];
   	}
   }

   for(int i=1;i<=n;i++) dp[i]=get_cost(1,i);
  
   for(int u=2;u<=d;u++){
    for(int i=1;i<=n;i++) ndp[i]=INF;
    f2(1,n,1,n);
  	for(int i=1;i<=n;i++) dp[i]=ndp[i];
   }

    int ans=INF;
    for(int i=1;i<=n;i++){
     if(dp[i]==INF) continue;
     ans=min(ans,dp[i]+get_cost(i+1,n));
    }

   cout << ans << '\n';
   return;
  }

  cost.assign(n+5,vector<int>(n+5,0));
  for(int i=1;i<=n;i++){
  	int res=0,xd=ar[i];
  	for(int j=i;j<=n;j++){
     xd=min(xd,ar[j]);
     if(xd<=t) res++;
     xd++;
     cost[i][j]=res;
  	}
  }

  for(int i=1;i<=n;i++) dp[i]=cost[1][i];
  
  for(int u=2;u<=d;u++){
    for(int i=1;i<=n;i++) ndp[i]=INF;
    f(1,n,1,n);
  	for(int i=1;i<=n;i++) dp[i]=ndp[i];
  }

  int ans=INF;
  for(int i=1;i<=n;i++){
    if(dp[i]==INF) continue;
    ans=min(ans,dp[i]+cost[i+1][n]);
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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