oj.uz

Submission #395942

# Submission time Handle Problem Language Result Execution time Memory
395942 2021-04-29T08:51:11 Z fadi57 Holding (COCI20_holding) C++14
0 / 110
 136 ms 262148 KB 
#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;}
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){
int &ret=dp2[i][j][left];
if(ret!=-1){return ret;}
if(j>r){return 0;}
if(i==n){return 0;}
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];}
}
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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -