Submission #198508

#	Time	Username	Problem	Language	Result	Execution time	Memory
198508		quocnguyen1012	Holding (COCI20_holding)	C++14	22 / 110	8 ms	4216 KiB

holding

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

template<class T> inline bool chkmin(T & a, const T & val) {return val < a ? a = val, 1 : 0;}
template<class T> inline bool chkmax(T & a, const T & val) {return a < val ? a = val, 1 : 0;}

const int maxn = 105;

int fl[maxn][maxn][2505], fr[maxn][maxn][2505];
int N, L, R, K, a[maxn];
int sum[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> L >> R >> K;
  K = min(K, N * N / 4);
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    sum[i] = sum[i - 1] + a[i];
  }
  for (int i = 1; i < L; ++i){
    for (int j = L; j <= R; ++j){
      for (int cost = 0; cost <= K; ++cost){
        chkmin(fl[i][j][cost], fl[i - 1][j][cost]);
        chkmin(fr[i][j][cost], fl[i][j - 1][cost]);
        if (j - i <= cost) chkmin(fl[i][j][cost], fl[i - 1][j - 1][cost - (j - i)] - a[j] + a[i]);
      }
    }
  }
  for (int i = R + 1; i <= N; ++i){
    for (int j = L; j <= R; ++j){
      for (int cost = 0; cost <= K; ++cost){
        chkmin(fr[i][j][cost], fr[i + 1][j][cost]);
        chkmin(fr[i][j][cost], fr[i][j + 1][cost]);
        if (i - j <= cost) chkmin(fr[i][j][cost], fr[i + 1][j + 1][cost - (i - j)] - a[j] + a[i]);
      }
    }
  }
  int ret = 1e9;
  for (int i = L - 1; i <= R + 1; ++i){
    for (int cost = 0; cost <= K; ++cost){
      chkmin(ret, fl[L - 1][i][cost] + fr[N][i + 1][K - cost]);
    }
  }
  cout << ret + sum[R] - sum[L - 1] << '\n';
}

Compilation message (stderr)

holding.cpp: In function 'int main()':
holding.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
holding.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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