oj.uz

Submission #395962

# Submission time Handle Problem Language Result Execution time Memory
395962 2021-04-29T09:27:10 Z fadi57 Holding (COCI20_holding) C++14
88 / 110
 356 ms 226616 KB 
#include<bits/stdc++.h>
using namespace std;

const int mx=100;
int n,l,r,k;
typedef long long ll;
ll a[mx];
int dp[mx][mx][2500];
int dp2[mx][mx][2500];
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<=min(k,2500);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 588 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 6 ms 4428 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 6 ms 4428 KB Output is correct
8 Correct 9 ms 22220 KB Output is correct
9 Correct 11 ms 22872 KB Output is correct
10 Correct 11 ms 22988 KB Output is correct
11 Correct 13 ms 25020 KB Output is correct
12 Correct 10 ms 23116 KB Output is correct
13 Correct 82 ms 54616 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 6 ms 4428 KB Output is correct
8 Correct 9 ms 22220 KB Output is correct
9 Correct 11 ms 22872 KB Output is correct
10 Correct 11 ms 22988 KB Output is correct
11 Correct 13 ms 25020 KB Output is correct
12 Correct 10 ms 23116 KB Output is correct
13 Correct 82 ms 54616 KB Output is correct
14 Correct 9 ms 21196 KB Output is correct
15 Correct 11 ms 22860 KB Output is correct
16 Correct 9 ms 22092 KB Output is correct
17 Correct 12 ms 24396 KB Output is correct
18 Correct 16 ms 26060 KB Output is correct
19 Correct 82 ms 54668 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 6 ms 4428 KB Output is correct
8 Correct 9 ms 22220 KB Output is correct
9 Correct 11 ms 22872 KB Output is correct
10 Correct 11 ms 22988 KB Output is correct
11 Correct 13 ms 25020 KB Output is correct
12 Correct 10 ms 23116 KB Output is correct
13 Correct 82 ms 54616 KB Output is correct
14 Correct 9 ms 21196 KB Output is correct
15 Correct 11 ms 22860 KB Output is correct
16 Correct 9 ms 22092 KB Output is correct
17 Correct 12 ms 24396 KB Output is correct
18 Correct 16 ms 26060 KB Output is correct
19 Correct 82 ms 54668 KB Output is correct
20 Runtime error 356 ms 226616 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -