| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 395961 |
2021-04-29T09:26:03 Z |
fadi57 |
Holding (COCI20_holding) |
C++14 |
|
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;
}
| # |
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 |
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 |
| # |
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 |
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 |
| # |
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 |
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 |
| # |
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 |
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 |
- |
