Submission #212090

#TimeUsernameProblemLanguageResultExecution timeMemory
212090NONAMEHolding (COCI20_holding)C++17
0 / 110
5 ms1280 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[N][K], answ[N][K], res = oo; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("in.txt","r",stdin); cin >> n >> l >> r >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) for (int j = 0; j <= n + 1; j++) for (int kl = 0; kl <= k; kl++) f[i][j][kl] = oo; for (int i = 0; i < n + 2; i++) fill(ans[i], ans[i] + k + 1, 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 <= r; j++) for (int ost = 0; ost <= k; ost++){ if (f[i][j][ost] == oo) continue; ans[j][ost] = min(ans[j][ost], f[i][j][ost]); if (i > 0) f[i - 1][j][ost] = min(f[i - 1][j][ost], f[i][j][ost]); if (j < r) f[i][j + 1][ost] = min(f[i][j + 1][ost], f[i][j][ost]); if (i > 0 && j < r) { int n1 = i - 1, n2 = j + 1; f[n1][n2][ost - (n2 - n1)] = min(f[n1][n2][ost - (n2 - n1)], f[i][j][ost] + a[n1] - a[n2]); } } for (int i = l - 1; i <= r; i++) for (int ost = 0; ost <= k; ost++) { if (i >= l) ans[i][ost] = min(ans[i][ost], ans[i - 1][ost]); ans[i + 1][ost] = min(ans[i + 1][ost], ans[i][ost]); } // right side for (int i = 0; i < n + 2; i++) fill(answ[i], answ[i] + k + 1, oo); for (int i = 1; i <= n; i++) for (int j = 0; j <= n + 1; j++) for (int kl = 0; kl <= k; kl++) f[i][j][kl] = oo; f[r][r + 1][k] = 0; for (int i = l; i <= r; i++) f[r][r + 1][k] += a[i]; for (int i = r; i <= n; i++) for (int j = r + 1; j >= l; j--) for (int ost = 0; ost <= k; ost++){ if (f[i][j][ost] == oo) continue; answ[j][ost] = min(answ[j][ost], f[i][j][ost]); if (i < n) f[i + 1][j][ost] = min(f[i + 1][j][ost], f[i][j][ost]); if (j > l) f[i][j - 1][ost] = min(f[i][j - 1][ost], f[i][j][ost]); if (i < n && j > l) { int n1 = i + 1, n2 = j - 1; f[n1][n2][ost - (n1 - n2)] = min(f[n1][n2][ost - (n1 - n2)], f[i][j][ost] + a[n1] - a[n2]); } } for (int i = r + 1; i >= l; i--) for (int ost = 0; ost <= k; ost++) { if (i <= r) answ[i][ost] = min(answ[i][ost], answ[i + 1][ost]); int opp = k - ost; if (ans[i - 1][opp] < oo && answ[i][ost] < oo) res = min(res, ans[i - 1][opp] + answ[i][ost]); } cout << res - f[r][r + 1][k]; 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...