# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
877997 | noiaint | Holding (COCI20_holding) | C++17 | 67 ms | 16908 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 int long long
using namespace std;
const int N = 105;
const long long ooo = 1e18;
int mini(int &x, int y) {
if (x > y) {
x = y;
return true;
}
return false;
}
int n, l, r, k;
int a[N];
int f[2][N][10005];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> l >> r >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
memset(f, 0x3f, sizeof f);
f[0][0][0] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= r - l + 1; ++j) {
int pos = l + j - 1;
for(int cost = 0; cost <= k; ++cost) {
f[i & 1][j][cost] = f[i & 1 ^ 1][j][cost];
if(abs(pos - i) > cost || j == 0) continue;
mini(f[i & 1][j][cost], f[i & 1 ^ 1][j - 1][cost - abs(pos - i)] + a[i]);
}
}
}
int res = ooo;
for(int i = 0; i <= k; ++i) mini(res, f[n & 1][r - l + 1][i]);
cout << res;
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... |