# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
334036 | ronnith | Holding (COCI20_holding) | C++14 | 289 ms | 262148 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>
typedef long long ll;
#define v vector
#define vl vector<ll>
#define mk make_pair
#define f first
#define s second
using namespace std;
int main(){
ll n, l, r, K;
scanf("%lld%lld%lld%lld", &n, &l, &r, &K);
ll a[n];
for(int i = 0;i < n;i ++){
scanf("%lld", &a[i]);
}
// int ans = INT_MAX;
// for(int bit = 0;bit < (1<<n);bit ++){
// if(__builtin_popcount(bit) == n - l + 1){
// int sm = 0;
// int cost = 0;
// int h = l;
// for(int i = 0;i < n;i ++){
// if(!((1<<i)&bit))continue;
// cost += h - (i + 1);
// h ++;
// sm += a[i];
// }
// if(cost <= k){
// ans = min(ans, sm);
// }
// }
// }
// printf("%d\n", ans);
ll ans = INT_MAX;
v<v<vl>> dp1(n, v<vl>(r - l + 2, vl(K + 1, INT_MAX)));
v<v<vl>> dp2(n, v<vl>(r - l + 2, vl(K + 1, INT_MAX)));
for(int i = 0;i < n;i ++){
for(int j = 0;j < r - l + 2;j ++){
for(int k = 0;k <= K;k ++){
if(j == 0){
dp2[i][j][k] = 0;
} else if(i == 0){
if(j == 1){
if(abs(l - i - 1) == k)
dp1[i][j][k] = a[i];
} else {
dp1[i][j][k] = INT_MAX;
}
} else {
if(abs(j - 1 + l - i - 1) <= k){
dp1[i][j][k] = a[i] + min(dp1[i - 1][j - 1][k - abs(j - 1 + l - i - 1)], dp2[i - 1][j - 1][k - abs(j - 1 + l - i - 1)]);// abs(j - 1 + l - i)
}
dp2[i][j][k] = min(dp1[i - 1][j][k], dp2[i - 1][j][k]);
}
if(i == n - 1 and j == r - l + 1)
ans = min(ans, min(dp1[i][j][k], dp2[i][j][k]));
// cerr << dp1[i][j][k] << ' ' << dp2[i][j][k] << ' ';
}
// cerr << '\n';
}
// cerr << '\n';
}
printf("%lld\n", ans);
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... |