제출 #391660

#제출 시각아이디문제언어결과실행 시간메모리
391660saarang123K개의 묶음 (IZhO14_blocks)C++17
53 / 100
1099 ms1484 KiB
#include <bits/stdc++.h> using namespace std; const int mxn = 100 * 1000 + 3, mxk = 103; int dp[mxk][mxn], a[mxn]; int n, k; template<class T> struct SparseTable { // comb(ID,b) = b T ID = T(); function<T(const T&,const T&)> comb; int n, k; vector<vector<T>> seg; void init(int _n, T base, function<T(const T&,const T&)> join) { n = _n; k = lg(n); comb = join; ID = base; seg.assign(_n + 1, vector<T> (k + 1, ID)); } int lg(int x) { return 31 - __builtin_clz(x); } //CHECK THIS void build() { for(int i = 1; i <= n; i++) seg[i][0] = a[i]; for(int j = 1; j <= k; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++) seg[i][j] = comb(seg[i][j - 1], seg[i + (1 << (j - 1))][j - 1]); } T query(int L, int R) { int j = lg(R - L + 1); return comb(seg[L][j], seg[R - (1 << j) + 1][j]); } }; SparseTable<int> st; // void f(int i, int l, int r, int optl, int optr) { // if(l > r) // return; // int mid = (l + r) >> 1, opt = -1; // dp[i][mid] = 1e9; // for(int m = optl; m < min(optr, mid); m++) { // int cost = st.query(m + 1, mid); // if(dp[i][mid] > dp[i - 1][m] + cost) { // dp[i][mid] = dp[i - 1][m] + cost; // opt = m; // } // } // cout << opt << '\n'; // f(i, l, mid - 1, optl, opt); // f(i, mid + 1, r, opt, optr); // } signed main() { std::ios::sync_with_stdio(0); std::cout.tie(0); std::cin.tie(0); #ifdef saarang freopen("/home/saarang/Documents/cp/input.txt", "r", stdin); freopen("/home/saarang/Documents/cp/output.txt", "w", stdout); #endif cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[0][i] = 1e9; } st.init(n, 0, [&] (int x, int y) { return max(x, y); }); st.build(); // for(int i = 1; i <= k; i++) // f(i, 1, n, 0, n); for(int i = 1; i <= k; i++) { dp[i][0] = 1e9; for(int j = 1; j <= n; j++) { int opt = -1; dp[i][j] = 1e9; for(int l = 0; l < j; l++) { if(dp[i][j] > dp[i - 1][l] + st.query(l + 1, j)) { opt = l + 1; dp[i][j] = dp[i - 1][l] + st.query(l + 1, j); } } //cout << opt << ' '; } //cout << '\n'; } // for(int i = 1; i <= k; i++) { // for(int j = 1; j <= n; j++) // cout << dp[i][j] << ' '; // cout << '\n'; // } cout << dp[k][n] << '\n'; return 0; }

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

blocks.cpp: In function 'int main()':
blocks.cpp:67:11: warning: variable 'opt' set but not used [-Wunused-but-set-variable]
   67 |       int opt = -1;
      |           ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...