Submission #1282582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282582		reginox	K blocks (IZhO14_blocks)	C++20	53 / 100	1093 ms	12312 KiB

blocks

#include <bits/stdc++.h>
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e5+3;
int n, k, a[N];
int dp[N], dp2[N];

struct Lazy{
  //todo: write apply function, clear lazy function
  vector<int> tree, lazy;
  void resize(int n){
    tree.assign(n<<2+3, 0);
    lazy.assign(n<<2+3, 0);
  }

  void apply(int id, int len, int add){
    //do something (both tree and lazy)
    tree[id] += add; lazy[id] += add;
  }
  
  void push(int id, int l, int r){
    int mid = (l+r)/2;
    apply(id << 1, mid - l + 1, lazy[id]);
    apply(id << 1 | 1, r - mid, lazy[id]);
    //clear lazy
    lazy[id] = 0;
  }

  void update(int id, int l, int r, int u, int v, int tmp){
    if(v < l || r < u) return ;
    if(u <= l && r <= v){
      apply(id, r-l+1, tmp);
      return ;
    }
    push(id, l, r);
    int mid = (l+r)/2;
    update(id<<1, l, mid, u, v, tmp);
    update(id<<1|1, mid+1, r, u, v, tmp);
    tree[id] = min(tree[id<<1], tree[id<<1|1]);
  }
  
  int get(int id, int l, int r, int u, int v){
    if(v < l || r < u) return 1e9;
    if(u <= l && r <= v) return tree[id];
    push(id, l, r);
    int mid = (l+r)/2;
    int lf = get(id<<1, l, mid, u, v);
    int rg = get(id<<1|1, mid+1, r, u, v);
    return min(lf, rg);
  }
} t;
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];
  memset(dp2, 0x3f, sizeof(dp2));
  dp2[0] = 0;
  for(int j = 1; j <= k; j++){
    t.resize(n);
    for(int i = 1; i <= n; i++) t.update(1, 1, n, i, i, dp2[i-1]);
    stack<pair<int, int>> st;
    for(int i = 0; i <= n; i++) dp[i] = 1e9;
    for(int i = 1; i <= n; i++){
      int pos = i;
      while(!st.empty() && st.top().first <= a[i]){
        int val = st.top().first;
        int l = st.top().second;
        st.pop();
        if(l < pos){
          t.update(1, 1, n, l, pos-1, a[i]-val);
        }
        pos = l;
      }
      st.push(make_pair(a[i], pos));
      t.update(1, 1, n, i, i, a[i]);
      dp[i] = t.get(1, 1, n, 1, i);
    }
    // for(int i = 0; i <= n; i++) cout << (dp[i]>=1e9?-1:dp[i]) << " ";
    // cout << "\n";
    for(int i = 0; i <= n; i++) dp2[i] = dp[i];
  }
  cout << dp[n];
  return 0;
}

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