Submission #1282587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282587		reginox	K blocks (IZhO14_blocks)	C++20	0 / 100	1 ms	840 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 build(int id, int l, int r){
    if(l == r){tree[id] = dp2[l-1], lazy[id] = 0; return ;}
    int mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    tree[id] = min(tree[id*2], tree[id*2+1]);
    return ;
  }

  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;
  t.resize(n);
  for(int j = 1; j <= k; j++){
    t.build(1, 1, n);
    stack<pair<int, int>> st;
    dp[0] = 1e9;
    for(int i = 1; i <= n; i++){
      dp[i] = 1e9;
      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: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47