oj.uz

Submission #395958

# Submission time Handle Problem Language Result Execution time Memory
395958 2021-04-29T09:17:46 Z fadi57 Holding (COCI20_holding) C++14
55 / 110
 2000 ms 204496 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;}
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=0;
//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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 2 ms 1996 KB Output is correct
3 Correct 1 ms 1996 KB Output is correct
4 Correct 1 ms 1996 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 16 ms 13644 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 2 ms 1996 KB Output is correct
3 Correct 1 ms 1996 KB Output is correct
4 Correct 1 ms 1996 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 16 ms 13644 KB Output is correct
8 Correct 10 ms 22512 KB Output is correct
9 Correct 10 ms 23116 KB Output is correct
10 Correct 11 ms 23216 KB Output is correct
11 Correct 14 ms 25304 KB Output is correct
12 Correct 11 ms 23344 KB Output is correct
13 Correct 265 ms 204496 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 2 ms 1996 KB Output is correct
3 Correct 1 ms 1996 KB Output is correct
4 Correct 1 ms 1996 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 16 ms 13644 KB Output is correct
8 Correct 10 ms 22512 KB Output is correct
9 Correct 10 ms 23116 KB Output is correct
10 Correct 11 ms 23216 KB Output is correct
11 Correct 14 ms 25304 KB Output is correct
12 Correct 11 ms 23344 KB Output is correct
13 Correct 265 ms 204496 KB Output is correct
14 Correct 9 ms 21528 KB Output is correct
15 Correct 10 ms 23116 KB Output is correct
16 Execution timed out 2066 ms 22440 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 2 ms 1996 KB Output is correct
3 Correct 1 ms 1996 KB Output is correct
4 Correct 1 ms 1996 KB Output is correct
5 Correct 2 ms 1996 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 16 ms 13644 KB Output is correct
8 Correct 10 ms 22512 KB Output is correct
9 Correct 10 ms 23116 KB Output is correct
10 Correct 11 ms 23216 KB Output is correct
11 Correct 14 ms 25304 KB Output is correct
12 Correct 11 ms 23344 KB Output is correct
13 Correct 265 ms 204496 KB Output is correct
14 Correct 9 ms 21528 KB Output is correct
15 Correct 10 ms 23116 KB Output is correct
16 Execution timed out 2066 ms 22440 KB Time limit exceeded
17 Halted 0 ms 0 KB -