Submission #638264

#TimeUsernameProblemLanguageResultExecution timeMemory
638264ieeHolding (COCI20_holding)C++17
110 / 110
54 ms113172 KiB
// iee #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <set> #include <map> #define rep(i, a, b) for (auto i = (a); i <= (b); ++i) #define per(i, a, b) for (auto i = (a); i >= (b); --i) #define fi first #define se second using ll = long long; using ull = unsigned long long; using namespace std; void work(int); template <class T> void read(T &x) { x = 0; int f = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar(); x *= f; } int main() { int TT = 1; // cin >> TT; rep(CAS, 1, TT) work(CAS); return 0; } const int N = 105, K = 2605; int n, l, r, qian, a[N]; int S, mx, f[N][N][K], L[N][K]; void work(int CASE) { cin >> n >> l >> r >> qian; qian = min(qian, 2600); rep(i, 1, n) cin >> a[i], (i >= l && i <= r) && (S += a[i]); rep(i, l, r) per(j, l - 1, 1) rep(k, 0, qian) { f[i][j][k] = max(f[i - 1][j][k], f[i][j + 1][k]); if (k - (i - j) >= 0) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - (i - j)] + a[i] - a[j]); } rep(i, l - 1, r) rep(j, 0, qian) L[i][j] = f[i][1][j]; memset(f, 0, sizeof f); per(i, r, l) rep(j, r + 1, n) rep(k, 0, qian) { f[i][j][k] = max(f[i + 1][j][k], f[i][j - 1][k]); if (k - (j - i) >= 0) f[i][j][k] = max(f[i][j][k], f[i + 1][j - 1][k - (j - i)] + a[i] - a[j]); } rep(i, l - 1, r) rep(j, 0, qian) mx = max(mx, L[i][j] + f[i + 1][n][qian - j]); cout << S - mx; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...