이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int dp[105][10005],dp2[105][10005];
int dplast[105][10005],dp2last[105][10005];
int dps[105][10005], dps2[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]=dp2[l][j]=sum;
dplast[l][j]=dp2last[l][j]=sum;
dps[l][j]=dps2[l][j]=sum;
}
}
int ans=sum;
for(int i=1; i<=right; i++){
if(i<left){
for(int l=left; l<=right; l++){
for(int j=l-i; j<=k; j++){
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 i=n; i>right; i--){
for(int l=right; l>=left; l--){
for(int j=i-l; j<=k; j++){
dp2[l][j] = min(dp2[l][j], dp2last[l+1][j-(i-l)]-a[l]+a[i]);
dp2[l][j] = min(dp2[l][j], dp2[l+1][j]);
ans=min(ans, dp2[l][j]);
dps2[l][j]=min(dps2[l][j], dp2[l][j]);
}
}
swap(dp2last, dp2);
}
for(int i=0; i<n; i++){
for(int j=1; j<=k; j++) dps[i][j]=min(dps[i][j], dps[i][j-1]);
for(int j=1; j<=k; j++) dps2[i][j]=min(dps2[i][j], dps2[i][j-1]);
}
for(int i=left; i<right; i++){
for(int j=1; j<k; j++)
ans=min(ans, dps[i][j]+dps2[i+1][k-j]);
}
*/
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |