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