oj.uz

답안 #395956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395956 2021-04-29T09:14:48 Z fadi57 Holding (COCI20_holding) C++14
22 / 110
 2000 ms 280 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=0;
//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];}
}
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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 624 ms 280 KB Output is correct

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 624 ms 280 KB Output is correct
8 Execution timed out 2089 ms 204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 624 ms 280 KB Output is correct
8 Execution timed out 2089 ms 204 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 624 ms 280 KB Output is correct
8 Execution timed out 2089 ms 204 KB Time limit exceeded
9 Halted 0 ms 0 KB -