oj.uz

Submission #870356

# Submission time Handle Problem Language Result Execution time Memory
870356 2023-11-07T13:29:55 Z truongdoan2012 K blocks (IZhO14_blocks) C++17
0 / 100
 20 ms 87900 KB 
#include <bits/stdc++.h>

using namespace std;

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

using i64 = long long;

struct Tree {
  typedef i64 T;
  static constexpr T unit = 1e16;
  T f(T a, T b) { return min(a, b); } // (any associative fn)
  vector<T> s;
  int n;
  Tree(int n = 0, T def = unit) : s(2 * n, def), n(n) {}
  void update(int pos, T val) {
    for (s[pos += n] = val; pos /= 2;)
      s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
  }
  T query(int b, int e) { // query [b, e)
    T ra = unit, rb = unit;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2)
        ra = f(ra, s[b++]);
      if (e % 2)
        rb = f(s[--e], rb);
    }
    return f(ra, rb);
  }
};

const int N = 1e5 + 10;
i64 dp[N][110]; // min val khi chia i phan tu vao j nhom
i64 a[N], pm[N];

void solve() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pm[i] = max(pm[i - 1], a[i]);
  }
  memset(dp, 127, sizeof dp);
  for (int i = 1; i <= n; i++) {
    dp[i][1] = pm[i];
  }
  vector<int> l(n + 10);
  {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
      while (!st.empty() && a[st.top()] <= a[i]) {
        st.pop();
      }
      if (st.empty())
        l[i] = 0;
      else
        l[i] = st.top();
      st.push(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    debug(i, l[i]);
  }
  for (int j = 2; j <= k; j++) {
    Tree st(n + 10);
    for (int i = 1; i <= n; i++) {
      st.update(i, dp[i][j - 1]);
    }
    for (int i = 1; i <= n; i++) {
      dp[i][j] = min(dp[i][j], st.query(l[i], i) + a[i]);
    }
  }
  cout << dp[n][k];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int TC = 1;
  // cin >> TC;
  while (TC--) {
    solve();
  }
}

Compilation message

blocks.cpp: In function 'void solve()':
blocks.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
blocks.cpp:66:5: note: in expansion of macro 'debug'
   66 |     debug(i, l[i]);
      |     ^~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 87900 KB Output is correct
2 Correct 10 ms 87900 KB Output is correct
3 Correct 10 ms 87900 KB Output is correct
4 Correct 11 ms 87900 KB Output is correct
5 Correct 12 ms 87780 KB Output is correct
6 Correct 11 ms 87896 KB Output is correct
7 Correct 11 ms 87896 KB Output is correct
8 Correct 11 ms 87900 KB Output is correct
9 Correct 12 ms 87900 KB Output is correct
10 Correct 11 ms 87900 KB Output is correct
11 Correct 11 ms 87896 KB Output is correct
12 Correct 11 ms 87900 KB Output is correct
13 Incorrect 12 ms 87900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 87836 KB Output is correct
2 Correct 11 ms 87900 KB Output is correct
3 Correct 11 ms 87900 KB Output is correct
4 Correct 10 ms 87900 KB Output is correct
5 Correct 11 ms 87900 KB Output is correct
6 Correct 11 ms 87884 KB Output is correct
7 Correct 11 ms 87896 KB Output is correct
8 Correct 10 ms 87900 KB Output is correct
9 Correct 11 ms 87900 KB Output is correct
10 Correct 11 ms 87900 KB Output is correct
11 Correct 10 ms 87900 KB Output is correct
12 Correct 11 ms 87900 KB Output is correct
13 Correct 11 ms 87900 KB Output is correct
14 Incorrect 11 ms 87900 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 87900 KB Output is correct
2 Correct 10 ms 87900 KB Output is correct
3 Correct 10 ms 87900 KB Output is correct
4 Correct 11 ms 87900 KB Output is correct
5 Correct 12 ms 87780 KB Output is correct
6 Correct 11 ms 87896 KB Output is correct
7 Correct 11 ms 87896 KB Output is correct
8 Correct 11 ms 87900 KB Output is correct
9 Correct 12 ms 87900 KB Output is correct
10 Correct 11 ms 87900 KB Output is correct
11 Correct 11 ms 87896 KB Output is correct
12 Correct 11 ms 87900 KB Output is correct
13 Incorrect 12 ms 87900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 87900 KB Output is correct
2 Correct 10 ms 87900 KB Output is correct
3 Correct 10 ms 87900 KB Output is correct
4 Correct 11 ms 87900 KB Output is correct
5 Correct 12 ms 87780 KB Output is correct
6 Correct 11 ms 87896 KB Output is correct
7 Correct 11 ms 87896 KB Output is correct
8 Correct 11 ms 87900 KB Output is correct
9 Correct 12 ms 87900 KB Output is correct
10 Correct 11 ms 87900 KB Output is correct
11 Correct 11 ms 87896 KB Output is correct
12 Correct 11 ms 87900 KB Output is correct
13 Incorrect 12 ms 87900 KB Output isn't correct
14 Halted 0 ms 0 KB -