Submission #891705

#TimeUsernameProblemLanguageResultExecution timeMemory
891705ind1vHolding (COCI20_holding)C++11
110 / 110
24 ms25180 KiB
#include <bits/stdc++.h> using namespace std; const int N = 105; const int K = 2505; int n, l, r, k; int a[N]; int fl[N][N][K], fr[N][N][K]; template<typename T> bool minimize(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> l >> r >> k; k = min(k, K - 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } int cost = 0; for (int i = l; i <= r; i++) { cost += a[i]; } for (int i = 1; i <= l - 1; i++) { for (int j = l; j <= r; j++) { for (int c = 0; c <= k; c++) { minimize(fl[i][j][c], fl[i - 1][j][c]); minimize(fl[i][j][c], fl[i][j - 1][c]); if (c >= 1) { minimize(fl[i][j][c], fl[i][j][c - 1]); } if (c >= j - i) { minimize(fl[i][j][c], fl[i - 1][j - 1][c - j + i] - a[j] + a[i]); } } } } for (int i = n; i >= r + 1; i--) { for (int j = r; j >= l; j--) { for (int c = 0; c <= k; c++) { minimize(fr[i][j][c], fr[i + 1][j][c]); minimize(fr[i][j][c], fr[i][j + 1][c]); if (c >= 1) { minimize(fr[i][j][c], fr[i][j][c - 1]); } if (c >= i - j) { minimize(fr[i][j][c], fr[i + 1][j + 1][c - i + j] - a[j] + a[i]); } } } } long long ans = cost; ans = min(ans, (long long) cost + fl[l - 1][r][k]); ans = min(ans, (long long) cost + fr[r + 1][l][k]); for (int i = l; i <= r - 1; i++) { for (int tk = 0; tk <= k; tk++) { ans = min(ans, (long long) cost + fl[l - 1][i][tk] + fr[r + 1][i + 1][k - tk]); } } cout << ans << '\n'; 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...