Submission #212065

#TimeUsernameProblemLanguageResultExecution timeMemory
212065NONAMEHolding (COCI20_holding)C++17
55 / 110
71 ms100472 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...