This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;
int n, k;
int dp[2][N];
int a[N];
struct sparse {
int table[19][N];
int numlog[N];
void build() {
for (int i = 2; i < N; i++) {
numlog[i] = numlog[i / 2] + 1;
}
for (int i = 0; i <= 17; i++) {
for (int j = 1; j <= n; j++) {
if (!i) {
table[i][j] = a[j];
} else {
table[i][j] = max(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
}
}
int getmax(int l, int r) {
int lg = numlog[r - l + 1];
return max(table[lg][l], table[lg][r - (1 << lg) + 1]);
}
};
sparse table;
void div(int id, int l, int r, int optl, int optr) {
if (l > r) return ;
int mid = (l + r) >> 1;
int &res = dp[id][mid];
res = inf;
int opt = optl;
for (int i = optl; i <= mid; i++) {
int cost = table.getmax(i, mid);
if (dp[id ^ 1][i - 1] + cost <= res) {
res = dp[id ^ 1][i - 1] + cost;
opt = i;
}
}
div(id, l, mid - 1, optl, opt);
div(id, mid + 1, r, opt, optr);
}
main() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
table.build();
for (int i = 1; i <= n; i++) {
dp[1][i] = max(dp[1][i - 1], a[i]);
}
for (int i = 2; i <= k; i++) {
div(i & 1, 1, n, i, n);
}
cout << dp[k & 1][n];
}
Compilation message (stderr)
blocks.cpp:53:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
blocks.cpp: In function 'int main()':
blocks.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~
blocks.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |