Submission #1089658

#TimeUsernameProblemLanguageResultExecution timeMemory
1089658xnqsK blocks (IZhO14_blocks)C++17
53 / 100
1076 ms33620 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #include <iostream> #include <fstream> #include <vector> #include <queue> #include <utility> #include <algorithm> #include <cstdint> const int BULAN = 15; int x, p; int arr[100005]; int sp_tb[17][100005]; uint32_t dp[105][100005]; void build_sparse_table() { for (int l = 1; l < 17; l++) { for (int i = 1; i+(1<<l)-1 <= x; i++) { sp_tb[l][i] = std::max(sp_tb[l-1][i], sp_tb[l-1][i+(1<<(l-1))]); } } } inline int max_query(int l, int r) { int lvl = 31-__builtin_clz(r-l+1); return std::max(sp_tb[lvl][l], sp_tb[lvl][r-(1<<lvl)+1]); } void calculate_dp() { if (1LL*x*x*p<=10'000'000) { dp[1][0] = 0x3f3f3f3f; for (int i = 1; i <= x; i++) { dp[1][i] = max_query(1,i); } for (int k = 2; k <= p; k++) { for (int i = 0; i < k; i++) { dp[k][i] = 0x3f3f3f3f; } for (int i = k; i <= x; i++) { dp[k][i] = 0x3f3f3f3f; for (int j = k; j <= i; j++) { dp[k][i] = std::min(dp[k][i], dp[k-1][j-1] + max_query(j,i)); } } } return; } dp[1][0] = 0x3f3f3f3f; for (int i = 1; i <= x; i++) { dp[1][i] = max_query(1,i); } for (int k = 2; k <= p; k++) { std::priority_queue<std::pair<uint32_t,int>> pq; for (int i = 0; i < BULAN; i++) { pq.emplace(0x3f3f3f3f,0); } for (int i = 0; i < k; i++) { dp[k][i] = 0x3f3f3f3f; pq.emplace(dp[k-1][i],i+1); pq.pop(); } for (int i = k; i <= x; i++) { dp[k][i] = 0x3f3f3f3f; auto tmp = pq; while (!tmp.empty()) { auto [opt_dp, idx] = tmp.top(); tmp.pop(); dp[k][i] = std::min(dp[k][i], opt_dp + max_query(idx,i)); } pq.emplace(dp[k-1][i],i+1); pq.pop(); } } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); std::cin >> x >> p; for (int i = 1; i <= x; i++) { std::cin >> arr[i]; sp_tb[0][i] = arr[i]; } build_sparse_table(); calculate_dp(); std::cout << dp[p][x] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...