# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
844505 | vjudge1 | Holding (COCI20_holding) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int dp[105][10005], dplast[105][10005];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, left, right, k; cin >> n >> left >> right >> k;
vector<int> a(n+1);
for (int i = 1; i <= n; i++) cin >> a[i];
int sum = 0;
for (int i = left; i <= right; i++) sum+=a[i];
for(int l=0; l<100+5; l++){
for(int j=0; j<=k; j++){
dp[l][j]=dplast[l][j]=dptmp[l][j]=sum;
}
}
int ans=sum;
for(int i=1; i<=right; i++){
if(i<left){
for(int l=left; l<=n; l++){
for(int j=l-i; j<=k; j++){
if(l<=right){
dp[l][j] = min(dp[l][j], dplast[l-1][j-(l-i)]-a[l]+a[i]);
}
dp[l][j] = min(dp[l][j], dp[l-1][j]);
ans=min(ans, dp[l][j]);
}
}
}
else{
for(int l = right+1; l <=n; l++){
for(int j=l-i; j<=k; j++){
dp[l][j] = min(dp[l][j], dplast[l-1][j-(l-i)]-a[i]+a[l]);
dp[l][j] = min(dp[l][j], dp[l-1][j]);
ans=min(ans, dp[l][j]);
}
}
}
swap(dplast, dp);
for(int l=0; l<100+5; l++){
for(int j=0; j<=k; j++){
dp[l][j]=sum;
}
}
}
cout << ans;
}