Submission #395960

#	Time	Username	Problem	Language	Result	Execution time	Memory
395960		fadi57	Holding (COCI20_holding)	C++14	88 / 110	268 ms	204516 KiB

holding

#include<bits/stdc++.h>
using namespace std;

const int mx=60;
int n,l,r,k;
typedef long long ll;
ll a[mx];
int dp[mx][mx][10010];
int dp2[mx][mx][10010];
int solveL(int i,int j,int left){
    if(j<l){return 0;}
if(i<0){return 0;}
if(left<0){return 0;}
int &ret=dp[i][j][left];
if(ret!=-1){return ret;}

if(abs(j-i)<=left){

    ret=solveL(i-1,j-1,left-abs(j-i))+(a[j]-a[i]);
}
ret=max(ret,solveL(i-1,j,left));
ret=max(ret,solveL(i,j-1,left));

return ret;
}
int solveR(int i,int j,int left){
    if(j>r){return 0;}
if(i>=n){return 0;}
if(left<0){return 0;}
int &ret=dp[i][j][left];
if(ret!=-1){return ret;}

if(abs(j-i)<=left){

    ret=solveR(i+1,j+1,left-abs(j-i))+(a[j]-a[i]);
}
ret=max(ret,solveR(i+1,j,left));
ret=max(ret,solveR(i,j+1,left));
return ret;
}
int main(){
cin>>n>>l>>r>>k;
l--;
r--;
ll sum=0;
ll ans;
/*
memset(dp,-1,sizeof(dp));
memset(dp2,-1,sizeof(dp2
                     */
for(int i=0;i<n;i++){

    cin>>a[i];
    if(i>=l&&i<=r){sum+=a[i];}
}
for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
        for(int l=0;l<=k;l++){
            dp[i][j][l]=-1;
            dp2[i][j][l]=-1;
        }
    }
}
ans=sum;

for(int i=l-1;i<=r;i++){
    for(int j=0;j<=k;j++){


   ll z=solveL(l-1,i,j)+solveR(r+1,i+1,k-j);
    ans=min(sum-z,ans);

     //cout<<z;

      }
 }
 cout<<ans;





}

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