Submission #1077837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077837		duyhoanho	K blocks (IZhO14_blocks)	C++14	100 / 100	200 ms	84388 KiB

blocks

#include <bits/stdc++.h>
#define task ""

using namespace std;
const int N = 1e5 + 5,
          M = 105;
long long n, a[N], dp[N][M], k;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  if (fopen ("task.inp", "r")) {
    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);
  }

  if (fopen (task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> k;
  long long mx = -1e9;
  memset(dp, 126, sizeof(dp));
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    mx = max (mx, a[i]);
    dp[i][1] = mx;
  }

  for (int j = 2; j <= k; j++) {
    stack <long long> st;
    for (int i = 1; i <= n; i++) {
      while (!st.empty() and a[st.top()] <= a[i]) {
        dp[i][j] = min (dp[i][j], dp[st.top()][j - 1] + a[i]);
        dp[i][j] = min (dp[i][j], dp[st.top()][j] - a[st.top()] + a[i]);
        st.pop();
      }

      if (!st.empty()) {
        dp[i][j] = min(dp[i][j], dp[st.top()][j - 1] + a[i]);
        dp[i][j] = min(dp[i][j], dp[st.top()][j]);
        dp[i][j] = min(dp[i][j], dp[st.top() - 1][j - 1] + a[st.top()]);
      }

      st.push(i);
    }
  }
  cout << dp[n][k];
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:14:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen ("task.inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:15:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen ("task.out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:19:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:20:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47