Submission #238840

#	Time	Username	Problem	Language	Result	Execution time	Memory
238840		Exile_2k4	Holding (COCI20_holding)	C++17	0 / 110	54 ms	102136 KiB

holding

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

const int N = 101;

int a[N],dp[N][N][N*N/4], L[N][N*N/4] ,n,l,r,k,sum=0;

signed main(){
	cin >> n >> l >> r >> k;
	for(int i=1;i<=n;++i) cin >> a[i];
	sum = accumulate(a+l,a+r+1,sum);
	
	for(int i=l-1;i>0;--i){
		for(int j=l;j<=r;++j){
			for(int k=0;k<N*N/4;++k){
				dp[i][j][k] = max({dp[i][j][k],dp[i+1][j][k],dp[i][j-1][k]});
				int spend = j-i;
				if(k>=spend) dp[i][j][k] = max(dp[i][j][k],dp[i+1][j-1][k-spend]+a[j]-a[i]);
			}
		}
	}
	for(int i=l;i<=r;++i){
		for(int j=0;j<N*N/4;++j){
			L[i][j] = dp[1][i][j];
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=r;i>=l;--i){
		for(int j=r+1;j<=n;++j){
			for(int k=0;k<N*N/4;++k){
				dp[i][j][k] = max({dp[i][j][k],dp[i-1][j][k],dp[i][j+1][k]});
				int spend = j-i;
				if(k>=spend) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j+1][k-spend]+a[i]-a[j]);
			}
		}
	}
	int ans = 1e9;
	for(int i=l;i<=r+1;++i){
		for(int j=0;j<N*N/4;++j){
			ans = min(ans,sum-L[i-1][j]-dp[i][n][k-j]);
		}
	}
	cout << ans;
}

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