oj.uz

답안 #395961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395961 2021-04-29T09:26:03 Z fadi57 Holding (COCI20_holding) C++14
88 / 110
 318 ms 226680 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<=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

# 결과 실행 시간 메모리 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 2 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 7 ms 4528 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 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 2 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 7 ms 4528 KB Output is correct
8 Correct 10 ms 22220 KB Output is correct
9 Correct 11 ms 22860 KB Output is correct
10 Correct 11 ms 22976 KB Output is correct
11 Correct 16 ms 25008 KB Output is correct
12 Correct 11 ms 23116 KB Output is correct
13 Correct 93 ms 54668 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 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 2 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 7 ms 4528 KB Output is correct
8 Correct 10 ms 22220 KB Output is correct
9 Correct 11 ms 22860 KB Output is correct
10 Correct 11 ms 22976 KB Output is correct
11 Correct 16 ms 25008 KB Output is correct
12 Correct 11 ms 23116 KB Output is correct
13 Correct 93 ms 54668 KB Output is correct
14 Correct 8 ms 21196 KB Output is correct
15 Correct 9 ms 22732 KB Output is correct
16 Correct 9 ms 22104 KB Output is correct
17 Correct 12 ms 24356 KB Output is correct
18 Correct 14 ms 26156 KB Output is correct
19 Correct 96 ms 54684 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 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 2 ms 1868 KB Output is correct
6 Correct 1 ms 1996 KB Output is correct
7 Correct 7 ms 4528 KB Output is correct
8 Correct 10 ms 22220 KB Output is correct
9 Correct 11 ms 22860 KB Output is correct
10 Correct 11 ms 22976 KB Output is correct
11 Correct 16 ms 25008 KB Output is correct
12 Correct 11 ms 23116 KB Output is correct
13 Correct 93 ms 54668 KB Output is correct
14 Correct 8 ms 21196 KB Output is correct
15 Correct 9 ms 22732 KB Output is correct
16 Correct 9 ms 22104 KB Output is correct
17 Correct 12 ms 24356 KB Output is correct
18 Correct 14 ms 26156 KB Output is correct
19 Correct 96 ms 54684 KB Output is correct
20 Runtime error 318 ms 226680 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -