Submission #1089676

#TimeUsernameProblemLanguageResultExecution timeMemory
1089676xnqsK blocks (IZhO14_blocks)C++17
53 / 100
896 ms46672 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 = 24; 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<=50'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::vector<std::pair<uint32_t,int>> min(BULAN,std::pair<uint32_t,int>(0x3f3f3f3f,0)); for (int i = 0; i < k; i++) { dp[k][i] = 0x3f3f3f3f; int pos = -1; for (int j = 0; j < BULAN; j++) { if (min[j].first>dp[k-1][i]||(min[j].first==dp[k-1][i]&&min[j].second<i+1)) { pos = j; break; } } if (pos!=-1) { for (int j = BULAN-1; j > pos; j--){ min[j] = min[j-1]; } min[pos].first = dp[k-1][i]; min[pos].second = i+1; } } for (int i = k; i <= x; i++) { dp[k][i] = 0x3f3f3f3f; for (int j = 0; j < BULAN; j++) { dp[k][i] = std::min(dp[k][i], min[j].first + max_query(min[j].second,i)); } int pos = -1; for (int j = 0; j < BULAN; j++) { if (min[j].first>dp[k-1][i]||(min[j].first==dp[k-1][i]&&min[j].second<i+1)) { pos = j; break; } } if (pos!=-1) { for (int j = BULAN-1; j > pos; j--){ min[j] = min[j-1]; } min[pos].first = dp[k-1][i]; min[pos].second = i+1; } } } } 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...