Submission #462474

#	Time	Username	Problem	Language	Result	Execution time	Memory
462474		Jasiekstrz	Holding (COCI20_holding)	C++17	110 / 110	106 ms	14032 KiB

holding

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e2;
const int K=1e4;
int tab[N+10];
int dp[2][N+10][K+10];
int bck[2][N+10][K+10];
void solve(int n,int x,int k,int t) // x - first inside 
{
	for(int j=1;j<=n;j++)
	{
		for(int c=0;c<=k;c++)
			dp[0][j][c]=dp[1][j][c]=0;
	}

	for(int i=x-1;i>=1;i--)
	{
		for(int j=1;j<=n;j++)
		{
			for(int c=0;c<=k;c++)
				dp[i%2][j][c]=0;
		}
		for(int j=x;j<=n;j++)
		{
			for(int c=0;c<=k;c++)
				dp[i%2][j][c]=min(dp[(i+1)%2][j][c],dp[i%2][j-1][c]);
			for(int c=j-i;c<=k;c++)
				dp[i%2][j][c]=min(dp[i%2][j][c],
						dp[(i+1)%2][j-1][c-j+i]+tab[i]-tab[j]);
		}
	}

	for(int i=x;i<=n;i++)
	{
		for(int c=0;c<=k;c++)
		{
			bck[t][i-x+1][c]=dp[1][i][c];
			//cerr<<"type="<<t<<" d="<<i-x+1<<" c="<<c<<" : "<<bck[t][i-x+1][c]<<"\n";
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,l,r,k;
	cin>>n>>l>>r>>k;
	for(int i=1;i<=n;i++)
		cin>>tab[i];

	solve(n,l,k,0);
	reverse(tab+1,tab+n+1);
	solve(n,n-r+1,k,1);
	reverse(tab+1,tab+n+1);

	int ans=0;
	for(int i=0;i<=r-l+1;i++)
	{
		for(int c=0;c<=k;c++)
		{
			ans=min(ans,bck[0][i][c]+bck[1][r-l+1-i][k-c]);
			//cerr<<i<<" "<<c<<" "<<ans<<"\n";
		}
	}
	for(int i=l;i<=r;i++)
		ans+=tab[i];
	cout<<ans<<"\n";
	return 0;
}

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