Submission #1101016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101016		epicci23	The short shank; Redemption (BOI21_prison)	C++17	35 / 100	48 ms	62564 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 N = 4e3 + 5;
const int INF = 1e9;

int n,d,t;
int ar[N],dp[N],ndp[N];
int cost[N][N];

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 _(){
  cin >> n >> d >> t;
  for(int i=1;i<=n;i++) cin >> ar[i];
  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: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20