제출 #1035943

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

blocks

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1 , K = 1e2 + 1 , LOG = 18;
int n , k , a[N] , mx[N][LOG] , dp[N] , ndp[N];
int GET(int L , int R){
   int sz = __lg(R - L + 1);
   return max(mx[L][sz] , mx[R - (1 << sz) + 1][sz]);
}
void solve(int l , int r , int L , int R){
   if(l > r){
      return;
   }
   int m = (l + r) / 2 , id;
   dp[m] = -1;
   for(int x = L;x <= min(m , R);x ++){
      if(dp[m] == -1 || dp[m] > ndp[x - 1] + GET(x , m)){
         dp[m] = ndp[x - 1] + GET(x , m);
         id = x;
      }
   }
   solve(l , m - 1 , L , id);
   solve(m + 1 , r , id , R);
}
int main(){
   cin >> n >> k;
   int _mx = 0;
   dp[0] = 1e9;
   for(int i = 1;i <= n;i ++){
      cin >> a[i];
      _mx = max(_mx , a[i]);
      dp[i] =_mx;
      mx[i][0] = a[i];
   }
   for(int bit = 1;bit < LOG;bit ++){
      for(int i = 1;i + (1 << bit) - 1 <= n;i ++){
         mx[i][bit] = max(mx[i][bit - 1] , mx[i + (1 << (bit - 1))][bit - 1]);
      }
   }
   for(int x = 1;x < k;x ++){
      for(int x = 0;x <= n;x ++){
         ndp[x] = dp[x];
      }
      solve(1 , n , 1 , n);
   }
   cout << dp[n] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

blocks.cpp: In function 'void solve(int, int, int, int)':
blocks.cpp:21:9: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |    solve(l , m - 1 , L , id);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

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