Submission #844521

#	Time	Username	Problem	Language	Result	Execution time	Memory
844521		vjudge1	Holding (COCI20_holding)	C++17	110 / 110	129 ms	200016 KiB

holding

#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
	int n, l, r, k;
	cin>>n>>l>>r>>k;
	l--,r--;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>arr[i];
	}
	vector<vector<vector<int>>> dp(r-l+1,vector<vector<int>>(n-(r-l+1),vector<int>(k+1,-1)));
	auto f = [&](int node, int node2, int kalan, auto f)->int{
		if (node>=r-l+1) return 0ll;
		if (node2>=n-(r-l+1)) return 0ll;
		if (dp[node][node2][kalan]!=-1) return dp[node][node2][kalan];
		dp[node][node2][kalan]=f(node,node2+1,kalan,f);
		dp[node][node2][kalan]=max(dp[node][node2][kalan],f(node+1,node2,kalan,f));
		int val = node2+1+node;
		int pos = l-(node2+1);
		if (node2>=l){
			val=node2-l+1+(r-l-node);
			pos=r+node2-l+1;
		}
		if (kalan>=val && arr[pos]<=arr[node+l]){
			dp[node][node2][kalan]=max(dp[node][node2][kalan],f(node+1,node2+1,kalan-val,f)+arr[node+l]-arr[pos]);
		}
		return dp[node][node2][kalan];
	};
	int somma = 0;
	for (int i = l; i <= r; i++){
		somma+=arr[i];
	}
	int ans = f(0,0,k,f);
	cout<<somma-ans<<endl;
}

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