Submission #1123928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123928		fryingduc	Holding (COCI20_holding)	C++20	110 / 110	26 ms	25416 KiB

holding

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 105;
const int K = 2555;

int n, l, r, k;
int a[maxn];

int f[maxn][maxn][K];
int g[maxn][maxn][K];

void solve() {
  cin >> n >> l >> r >> k;
  int mx_prof = n * (n + 1) / 4;
  debug(mx_prof);
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 1; i < l; ++i) {
    for(int j = l; j <= r; ++j) {
      for(int prof = 0; prof <= min(k, mx_prof); ++prof) {
        f[i][j][prof] = max(f[i - 1][j][prof], f[i][j - 1][prof]);
        if(prof >= j - i) {
          f[i][j][prof] = max(f[i][j][prof], f[i - 1][j - 1][prof - j + i] + a[j] - a[i]);
        }
      }
    }
  }
  for(int i = n; i > r; --i) {
    for(int j = r; j >= l; --j) {
      for(int prof = 0; prof <= min(k, mx_prof); ++prof) {
        g[i][j][prof] = max(g[i + 1][j][prof], g[i][j + 1][prof]);
        if(prof >= i - j) {
          g[i][j][prof] = max(g[i][j][prof], g[i + 1][j + 1][prof - i + j] + a[j] - a[i]);
        }
      }
    }
  }
  int res = 0;
  for(int i = l - 1; i <= r; ++i) {
    for(int prof = 0; prof <= k; ++prof) {
      if(res < f[l - 1][i][min(prof, mx_prof)] + g[r + 1][i + 1][min(k - prof, mx_prof)]) {
        res = max(res, f[l - 1][i][min(prof, mx_prof)] + g[r + 1][i + 1][min(k - prof, mx_prof)]);
      }
    }
  }
  int sum = 0;
  for(int i = l; i <= r; ++i) {
    sum += a[i];
  }
  cout << sum - res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22