Submission #819950

#	Time	Username	Problem	Language	Result	Execution time	Memory
819950		MohamedAhmed04	The short shank; Redemption (BOI21_prison)	C++14	35 / 100	1376 ms	19984 KiB

prison

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 4000 + 10 ;

int arr[MAX] ;
int n , m , t ; 

vector< pair<int , int> >vp ;
int st[MAX] ;

int cost[MAX][MAX] ;

int dp[MAX][MAX] ;

int solve()
{
	int sz = (int)(vp.size()) - 1 ;
	for(int i = 1 ; i <= sz ; ++i)
	{
		int curtim = 2e9 , sum = 0 ;
		for(int j = i ; j <= sz ; ++j)
		{
			curtim = min(curtim , arr[vp[j].second-1]+1) ;
			sum += min(t - curtim + 1 , vp[j].first) ;
			cost[i][j] = sum ;
			if(j+1 <= sz)
				curtim += vp[j+1].second - vp[j].second ;
		} 
	}
	for(int i = 1 ; i <= sz ; ++i)
		dp[i][0] = cost[1][i] ;
	for(int j = 1 ; j <= m ; ++j)
	{
		for(int i = 1 ; i <= sz ; ++i)
		{
			dp[i][j] = 1e9 ;
			for(int k = i ; k >= 1 ; --k) //put mattress at k
				dp[i][j] = min(dp[i][j] , dp[k-1][j-1] + cost[k+1][i]) ;
		}
	}
	return dp[sz][m] ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>t ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	arr[0] = 1e9 + 10 ;
	vp.emplace_back(0 , 1e9+10) ;
	int ans = 0 , last = -1 , cnt = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(arr[i] <= t)
		{
			arr[i] = min(arr[i] , arr[i-1] + 1) ;
			if(cnt && last != -1)
				vp.emplace_back(cnt , last+1) ;
			ans++ , last = i , cnt = 0 ;
		}
		else
			cnt++ ;
	}
	if(cnt && last != -1)
		vp.emplace_back(cnt , last+1) , cnt = 0 ;
	ans += solve() ;
	return cout<<ans<<"\n" , 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