Submission #308324

#	Time	Username	Problem	Language	Result	Execution time	Memory
308324		ErdosSzekeres	Holding (COCI20_holding)	C++14	110 / 110	121 ms	26488 KiB

holding

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 103;
const int MAXK = (MAXN*MAXN)/4 + 3;
int dpL[MAXN][MAXN][MAXK], dpR[MAXN][MAXN][MAXK], n,l,r,k, a[MAXN];
int main(){
    scanf("%d %d %d %d", &n, &l, &r, &k);
    k = min(k, MAXK - 1);
    for(int i=1; i<=n; i++)scanf("%d", &a[i]);
    int orig = 0; for(int i=l; i<=r; i++)orig+=a[i];
    //compute dpL (base case dpL[][][0])
    for(int j=1; j<=k; j++){
        for(int i=1; i<=l-1; i++){
            for(int g=l; g<=r; g++){
                if(j >= g-i)dpL[i][g][j] = max(dpL[i][g][j], dpL[i-1][g-1][j-(g-i)] + a[g] - a[i]);//swap them
                dpL[i][g][j] = max(dpL[i][g][j], dpL[i-1][g][j]);
                dpL[i][g][j] = max(dpL[i][g][j], dpL[i][g-1][j]);
            }
        }
    }
    //compute dpR
    for(int j=1; j<=k; j++){
        for(int i=n; i>=r+1; i--){
            for(int g=r; g>=l; g--){
                if(j >= i-g)dpR[i][g][j] = max(dpR[i][g][j], dpR[i+1][g+1][j-(i-g)] + a[g] - a[i]);//swap them
                dpR[i][g][j] = max(dpR[i][g][j], dpR[i+1][g][j]);
                dpR[i][g][j] = max(dpR[i][g][j], dpR[i][g+1][j]);
            }
        }
    }
    int ans = 0;
    for(int i=l-1; i<=r+1; i++){//position of line
        for(int j=0; j<=k; j++){//money
            //cout<<i<<" "<<j<<" "<<dpL[l-1][i][j] + dpR[r+1][i+1][k-j]<<endl;
            ans = max(ans, dpL[l-1][i][j] + dpR[r+1][i+1][k-j]);
        }
    }
    cout << orig - ans << endl;
}

Compilation message (stderr)

holding.cpp: In function 'int main()':
holding.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     scanf("%d %d %d %d", &n, &l, &r, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:9:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     for(int i=1; i<=n; i++)scanf("%d", &a[i]);
      |                            ~~~~~^~~~~~~~~~~~~

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