Submission #1092075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092075		juicy	K blocks (IZhO14_blocks)	C++17	100 / 100	178 ms	4732 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  const long long inf = 1e18;

  int n, k; cin >> n >> k;
  vector dp(2, vector<long long>(n + 1, inf));
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    dp[1][i + 1] = max(i ? dp[1][i] : 0, (long long) a[i]);
  }
  for (int i = 1; i < k; ++i) {
    vector<pair<int, long long>> st;
    dp[i & 1 ^ 1][0] = inf;
    for (int j = 0; j < n; ++j) {
      long long x = dp[i & 1][j];
      while (st.size() && st.back().first <= a[j]) {
        x = min(x, st.back().second);
        st.pop_back();
      }
      if (!st.size() || st.back().first + st.back().second > x + a[j]) {
        st.push_back({a[j], x});
      }
      dp[i & 1 ^ 1][j + 1] = st.back().first + st.back().second;
    }
  }
  cout << dp[k & 1][n];
  return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:25:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   25 |     dp[i & 1 ^ 1][0] = inf;
      |        ~~^~~
blocks.cpp:35:12: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   35 |       dp[i & 1 ^ 1][j + 1] = st.back().first + st.back().second;
      |          ~~^~~

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