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;
const int N = 105;
int n, L, R, k, s;
int a[102];
int dp[N][2505][N], Left[N][2505], Right[N][2505];
void MAX(int &A, int B)
{
if(A < B) A = B;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> L >> R >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = L; i <= R; i++) s += a[i];
k = min(k, n * n / 4 + 2);
int ans = 0;
for(int i = L; i <= R; i++)
for(int j = L - 1; j > 0; j--)
for(int c = 0; c <= k; c++)
{
MAX(dp[i][c][j], dp[i - 1][c][j]);
MAX(dp[i][c][j], dp[i][c][j + 1]);
if(c - i + j >= 0)
MAX(dp[i][c][j], dp[i - 1][c - i + j][j + 1] + a[i] - a[j]);
}
for(int i = L; i <= R; i++)
for(int j = 0; j <= k; j++)
Left[i][j] = dp[i][j][1];
memset(dp, 0, sizeof dp);
for(int i = R; i >= L; i--)
for(int j = R + 1; j <= n; j++)
{
for(int c = 0; c <= k; c++)
{
MAX(dp[i][c][j], dp[i + 1][c][j]);
MAX(dp[i][c][j], dp[i][c][j - 1]);
if(c + i - j >= 0)
MAX(dp[i][c][j], dp[i + 1][c - j + i][j - 1] + a[i] - a[j]);
}
}
for(int i = R; i >= L; i--)
for(int j = 1; j <= k; j++)
Right[i][j] = dp[i][j][n];
for(int i = L - 1; i <= R; i++)
for(int j = 0; j <= k; j++)
MAX(ans, Left[i][j] + Right[i + 1][k - j]);
cout << s - 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... |