Submission #696231

#	Time	Username	Problem	Language	Result	Execution time	Memory
696231		aSSSd	Holding (COCI20_holding)	C++14	110 / 110	158 ms	119288 KiB

holding

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],pref[N],dp[N][N][N*N/4];
int main()
{
    //freopen("ngu.inp","r",stdin);
    int n,l,r,k;
    cin >> n >> l >> r >> k;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i];
        pref[i]=pref[i-1]+a[i];
    }
    k=min(k,n*n/4);
    memset(dp,50,sizeof dp);
    if(l!=1) dp[1][l][k]=pref[r]-pref[l-1];
    else dp[r+1][l][k]=pref[r]-pref[l-1];
    int ans=dp[0][0][0];
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            for(int p=0;p<=k;++p)
            {
                ans=min(ans,dp[i][j][p]);

                if(i>=l&&i<=r) continue;
                int nxti=i+1;
                if(nxti>=l&&nxti<=r) nxti=r+1;

                dp[nxti][j][p]=min(dp[nxti][j][p],dp[i][j][p]);
                dp[i][j+1][p]=min(dp[i][j+1][p],dp[i][j][p]);

                if(j<=r&&j>=l) if(i<l||i>r) if(p>=abs(j-i))
                    dp[nxti][j+1][p-abs(j-i)]=min(dp[nxti][j+1][p-abs(j-i)],dp[i][j][p]+a[i]-a[j]);

            }
        }
    }

    for(int i=1;i<=n+1;++i)
        for(int j=1;j<=n+1;++j)
            for(int p=0;p<=k;++p)
                ans=min(ans,dp[i][j][p]);
    cout << ans;
}

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