제출 #1282606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282606		reginox	K개의 묶음 (IZhO14_blocks)	C++20	0 / 100	1 ms	576 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#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, sp[N][17];
int a[N];
vector<int> dp, dp2;

int get(int l, int r){
  int lg = __lg(r-l+1);
  return max(sp[l][lg], sp[r - (1 << lg) + 1][lg]);
}

void compute(int l, int r, int L, int R){
  if(l > r) return ;
  int mid = (l+r)>>1;
  pi best = {1e9, -1};
  for(int k = L; k <= min(mid, R); k++){
    best = min(best, make_pair(dp2[k-1] + get(k, mid), k));
  }
  dp[mid] = best.first;
  compute(l, mid-1, L, best.second);
  compute(mid+1, r, best.second, R);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    sp[i][0] = a[i];
  }
  for(int j = 1; (1 << j) <= n; j++){
    for(int i = 1; i + (1 << j) - 1 <= n; i++) 
      sp[i][j] = max(sp[i][j-1], sp[i + (1 << (j-1))][j-1]);
  }
  dp2.assign(n + 1, 0); dp.assign(n + 1, 0);
  for(int i = 1; i <= n; i++){
    dp2[i] = get(1, i);
  }
  dp2[0] = 1e9;
  for(int i = 2; i <= k; i++){
    compute(1, n, 1, n);
    // for(int i = 1; i <= n; i++) cout << dp[i] << " ";
    // cout << "\n";
    dp[0] = 1e9;
    swap(dp2, dp);  
  }
  cout << dp2[n];
  return 0;
}

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