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;
typedef long long ll;
const int N = 55;
const int K = 10010;
const int oo = 2e9;
int a[N], f[N][N][K], n, l, r, k, ans = oo;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n >> l >> r >> k;
assert(r == n);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int kl = 0; kl <= k; kl++)
f[i][j][kl] = oo;
f[l][l - 1][k] = 0;
for (int i = l; i <= r; i++)
f[l][l - 1][k] += a[i];
for (int i = l; i > 0; i--)
for (int j = l - 1; j <= n; j++)
for (int ost = 0; ost <= k; ost++){
if (f[i][j][ost] == oo) continue;
ans = min(ans, f[i][j][ost]);
for (int nw = i - 1; nw > 0; nw--)
for (int n2 = j + 1; n2 <= n; n2++)
if (ost - (n2 - nw) >= 0)
f[nw][n2][ost - (n2 - nw)] = min(f[nw][n2][ost - (n2 - nw)], f[i][j][ost] + a[nw] - a[n2]);
}
cout << ans;
return 0;
}
# | 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... |