Submission #209613

#	Time	Username	Problem	Language	Result	Execution time	Memory
209613		papa	Holding (COCI20_holding)	C++14	110 / 110	83 ms	108920 KiB

holding

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 100+5;
const int maxk = 10000/4+5;
int n,k;
int l,r;
int a[maxn];
int s;
int sol;
int dp[maxn][maxn][maxk];
int sl[maxn][maxk];

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);
    
    cin >> n >> l >> r >> k;
    
    k = min(k,n*n/4+2);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=l;i<=r;i++) s+=a[i];
    for(int i=l;i<=r;i++)
    {
        for(int j=l-1;j>0;j--)
        {
            for(int kk=0;kk<=k;kk++)
            {
                dp[i][j][kk] = max(dp[i][j][kk],dp[i-1][j][kk]);
                dp[i][j][kk] = max(dp[i][j][kk],dp[i][j+1][kk]);
                int cena = i-j;
                if(kk>=cena) dp[i][j][kk] = max(dp[i][j][kk],dp[i-1][j+1][kk-cena] + a[i]-a[j]);
            }
        }
    }
    
    for(int i=l-1;i<=r;i++)
       for(int j=0;j<=k;j++)
         sl[i][j] = dp[i][1][j];
         
    
    memset(dp,0,sizeof dp);
    
    for(int i=r;i>=l;i--)
    {
        for(int j=r+1;j<=n;j++)
        {
            for(int kk=0;kk<=k;kk++)
            {
                dp[i][j][kk] = max(dp[i][j][kk],dp[i+1][j][kk]);
                dp[i][j][kk] = max(dp[i][j][kk],dp[i][j-1][kk]);
                int cena = j-i;
                if(kk >= cena) dp[i][j][kk] = max(dp[i][j][kk],dp[i+1][j-1][kk-cena] + a[i] - a[j]);
            }
        }
    }
    
    for(int i=l-1;i<=r;i++)
       for(int j=0;j<=k;j++)
         sol = max(sol,sl[i][j] + dp[i+1][n][k-j]);
    
    cout << s-sol;
    
    return 0;
}

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