# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
200942 | ZwariowanyMarcin | Holding (COCI20_holding) | C++14 | 59 ms | 50680 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>
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define cat(x) cerr << #x << " = " << x << endl
#define ss(x) (int) x.size()
using namespace std;
const int nax = 101;
int n, L, R, k;
int a[nax];
int dp[nax][nax][10001];
bool ok(int x, int y) {
int r = 0;
r += (L <= x && x <= R);
r += (L <= y && y <= R);
return (r == 1);
}
int main() {
scanf ("%d%d%d%d", &n, &L, &R, &k);
int sum = 0;
for (int i = 1; i <= n; ++i) {
scanf ("%d", a + i);
if (L <= i && i <= R) sum += a[i];
}
for (int dl = 1; dl <= n; ++dl) {
for (int l = 1; l + dl - 1 <= n; ++l) {
int r = l + dl - 1;
for (int cost = 0; cost <= k; ++cost) {
dp[l][r][cost] = min(dp[l + 1][r][cost], dp[l][r - 1][cost]);
if (abs(l - r) <= cost && ok(l, r)) {
int x = 0;
if (L <= l && l <= R) {
x -= a[l];
x += a[r];
}
else {
x += a[l];
x -= a[r];
}
dp[l][r][cost] = min(dp[l][r][cost], dp[l + 1][r - 1][cost - abs(l - r)] + x);
}
}
}
}
printf ("%d\n", sum + dp[1][n][k]);
return 0;
}
Compilation message (stderr)
# | 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... |