Submission #1017344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017344		vjudge1	Holding (COCI20_holding)	C++17	110 / 110	41 ms	4444 KiB

holding

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=105;
int const K=10005;
int const mod=1e9+7;

int dp_pre[2][N][K],dp_suf[N][2][K];
int arr[N];

int main(){
	int n,L,R,k;
	cin>>n>>L>>R>>k;
	for (int i = 1; i <=n; ++i)
		cin>>arr[i];
	int debt=0;
	for (int i = L; i <=R; ++i)
		debt+=arr[i];
	//compute dp_pre;
	for(int l=L-1;l>=1;l--)
		for(int r=L;r<=R;r++)
			for(int c=0;c<=k;c++){
				dp_pre[l%2][r][c]=max(dp_pre[(l+1)%2][r][c],dp_pre[l%2][r-1][c]);
				if(c>=r-l)
					dp_pre[l%2][r][c]=max(dp_pre[l%2][r][c],dp_pre[(l+1)%2][r-1][c-(r-l)]+max(0,(arr[r]-arr[l])));
			}
	//compute suf_dp;
	for(int r=R+1;r<=n;r++)
		for(int l=R;l>=L;l--)
			for(int c=0;c<=k;c++){
				dp_suf[l][r%2][c]=max(dp_suf[l+1][r%2][c],dp_suf[l][(r-1)%2][c]);
				if(c>=r-l)
					dp_suf[l][r%2][c]=max(dp_suf[l][r%2][c],dp_suf[(l+1)][(r-1)%2][c-(r-l)]+max(0,(arr[l]-arr[r])));
			}
	int mx=0;
	for(int i=L-1;i<=R;i++)
		for(int c=0;c<=k;c++)
			mx=max(dp_pre[1][i][c]+dp_suf[i+1][n%2][k-c],mx);
	cout<<debt-mx<<endl;
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22