Submission #1137278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137278		aykhn	Holding (COCI20_holding)	C++20	55 / 110	117 ms	17664 KiB

holding

#include <bits/stdc++.h>

using namespace std;

const int MXN = 5e1 + 5;
const int MXK = 1e4 + 5;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

int dp[2][MXN][MXK], ndp[2][MXN][MXK];

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, l, r, k;
  cin >> n >> l >> r >> k;
  int a[n + 1], s = 0;
  for (int i = 1; i <= n; i++) cin >> a[i], s += (l <= i && i <= r) * a[i];
  for (int i = 0; i < 2; i++) for (int j = 0; j < MXN; j++) for (int k = 0; k < MXK; k++) dp[i][j][k] = ndp[i][j][k] = inf;
  dp[0][0][0] = dp[1][0][0] = 0;
  for (int i = n; i >= 1; i--)
  {
    int val = a[i];
    for (int i = 0; i < 2; i++) for (int j = 0; j < MXN; j++) for (int k = 0; k < MXK; k++) ndp[i][j][k] = inf;
    for (int j = 0; j < MXN; j++) for (int k = 0; k < MXK; k++)
    {
      ndp[0][j][k] = min(ndp[0][j][k], dp[0][j][k]);
      ndp[1][j][k] = min(ndp[1][j][k], dp[1][j][k]);
      if (r < i && j + 1 < MXN && k + i < MXK) ndp[0][j + 1][k + i] = min(ndp[0][j + 1][k + i], dp[0][j][k] + val);
      if (l <= i && i <= r && j - 1 >= 0 && k - i >= 0) ndp[0][j - 1][k - i] = min(ndp[0][j - 1][k - i], dp[0][j][k] - val);
      if (l <= i && i <= r && j + 1 < MXN && k + i < MXK) ndp[1][j + 1][k + i] = min(ndp[1][j + 1][k + i], dp[1][j][k] - val);
      if (i < l && j - 1 >= 0 && k - i >= 0) ndp[1][j - 1][k - i] = min(ndp[1][j - 1][k - i], dp[1][j][k] + val);
    }
    for (int k = 0; k < MXK; k++) ndp[1][0][k] = min(ndp[1][0][k], dp[0][0][k]);
    for (int i = 0; i < 2; i++) for (int j = 0; j < MXN; j++) for (int k = 0; k < MXK; k++) dp[i][j][k] = ndp[i][j][k];
  }
  int res = s + *min_element(dp[1][0], dp[1][0] + k + 1);
  cout << res << '\n';
}

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