#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (int i = a; i <= b; i++)
#define fo(i, a, b) for (int i = a; i >= b; i--)
#define minimize(a, b) a = (a < b ? a : b)
#define maximize(a, b) a = (a > b ? a : b)
#define fi first
#define se second
#define ll long long
#define pii pair <int, int>
#define pb push_back
#define pi acos(-1)
#define sz(a) (int)a.size()
#define getbit(a, b) (((a) >> (b)) & 1)
#define INOUT "main"
#define INFT 0x3f3f3f3f
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
cout << *it << " = [" << a << "]" << '\n';
err(++it, args...);
}
#define debug1(a, st, en) { cout << #a << " = ["; int kt = false; f(i, st, en) {if (kt) cout << ", "; kt = true; cout << a[i];} cout << "]\n"; }
void ctime()
{
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
void file()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
if (fopen(INOUT".INP", "r"))
{
freopen(INOUT".INP", "r", stdin);
freopen(INOUT".OUT", "w", stdout);
}
}
const int MX_N = 1e5 + 5;
int n, k;
int a[MX_N];
int dp[MX_N][105];
int rmq[25][MX_N];
void build()
{
f(i, 1, n) rmq[0][i] = a[i];
f(u, 1, 20)
f(i, 1, n - (1 << u) + 1)
rmq[u][i] = max(rmq[u - 1][i], rmq[u - 1][i + (1 << (u - 1))]);
}
int get(int l, int r)
{
int k = __lg(r - l + 1);
return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
int main()
{
file();
memset(dp, INFT, sizeof dp);
cin >> n >> k;
f(i, 1, n) cin >> a[i];
build();
dp[0][0] = 0;
f(i, 1, n)
f(j, 1, min(i, k))
f(u, 0, i - 1)
minimize(dp[i][j], dp[u][j - 1] + get(u + 1, i));
cout << dp[n][k];
ctime();
return 0;
}
Compilation message
blocks.cpp: In function 'void file()':
blocks.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen(INOUT".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen(INOUT".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
41564 KB |
Output is correct |
2 |
Correct |
15 ms |
41564 KB |
Output is correct |
3 |
Correct |
16 ms |
41528 KB |
Output is correct |
4 |
Correct |
15 ms |
41564 KB |
Output is correct |
5 |
Correct |
15 ms |
41564 KB |
Output is correct |
6 |
Correct |
15 ms |
41448 KB |
Output is correct |
7 |
Correct |
15 ms |
41556 KB |
Output is correct |
8 |
Correct |
15 ms |
41564 KB |
Output is correct |
9 |
Correct |
15 ms |
41564 KB |
Output is correct |
10 |
Correct |
16 ms |
41568 KB |
Output is correct |
11 |
Correct |
15 ms |
41560 KB |
Output is correct |
12 |
Correct |
16 ms |
41436 KB |
Output is correct |
13 |
Correct |
15 ms |
41576 KB |
Output is correct |
14 |
Correct |
15 ms |
41560 KB |
Output is correct |
15 |
Correct |
14 ms |
41564 KB |
Output is correct |
16 |
Correct |
17 ms |
41564 KB |
Output is correct |
17 |
Correct |
15 ms |
41560 KB |
Output is correct |
18 |
Correct |
15 ms |
41396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
41572 KB |
Output is correct |
2 |
Correct |
15 ms |
41568 KB |
Output is correct |
3 |
Correct |
14 ms |
41436 KB |
Output is correct |
4 |
Correct |
15 ms |
41528 KB |
Output is correct |
5 |
Correct |
14 ms |
41564 KB |
Output is correct |
6 |
Correct |
16 ms |
41580 KB |
Output is correct |
7 |
Correct |
17 ms |
41572 KB |
Output is correct |
8 |
Correct |
15 ms |
41572 KB |
Output is correct |
9 |
Correct |
14 ms |
41560 KB |
Output is correct |
10 |
Correct |
16 ms |
41364 KB |
Output is correct |
11 |
Correct |
15 ms |
41572 KB |
Output is correct |
12 |
Correct |
15 ms |
41376 KB |
Output is correct |
13 |
Correct |
20 ms |
41600 KB |
Output is correct |
14 |
Correct |
17 ms |
41572 KB |
Output is correct |
15 |
Correct |
17 ms |
41572 KB |
Output is correct |
16 |
Correct |
15 ms |
41572 KB |
Output is correct |
17 |
Correct |
15 ms |
41572 KB |
Output is correct |
18 |
Correct |
17 ms |
41572 KB |
Output is correct |
19 |
Correct |
18 ms |
41572 KB |
Output is correct |
20 |
Correct |
16 ms |
41492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
41564 KB |
Output is correct |
2 |
Correct |
15 ms |
41564 KB |
Output is correct |
3 |
Correct |
16 ms |
41528 KB |
Output is correct |
4 |
Correct |
15 ms |
41564 KB |
Output is correct |
5 |
Correct |
15 ms |
41564 KB |
Output is correct |
6 |
Correct |
15 ms |
41448 KB |
Output is correct |
7 |
Correct |
15 ms |
41556 KB |
Output is correct |
8 |
Correct |
15 ms |
41564 KB |
Output is correct |
9 |
Correct |
15 ms |
41564 KB |
Output is correct |
10 |
Correct |
16 ms |
41568 KB |
Output is correct |
11 |
Correct |
15 ms |
41560 KB |
Output is correct |
12 |
Correct |
16 ms |
41436 KB |
Output is correct |
13 |
Correct |
15 ms |
41576 KB |
Output is correct |
14 |
Correct |
15 ms |
41560 KB |
Output is correct |
15 |
Correct |
14 ms |
41564 KB |
Output is correct |
16 |
Correct |
17 ms |
41564 KB |
Output is correct |
17 |
Correct |
15 ms |
41560 KB |
Output is correct |
18 |
Correct |
15 ms |
41396 KB |
Output is correct |
19 |
Correct |
15 ms |
41572 KB |
Output is correct |
20 |
Correct |
15 ms |
41568 KB |
Output is correct |
21 |
Correct |
14 ms |
41436 KB |
Output is correct |
22 |
Correct |
15 ms |
41528 KB |
Output is correct |
23 |
Correct |
14 ms |
41564 KB |
Output is correct |
24 |
Correct |
16 ms |
41580 KB |
Output is correct |
25 |
Correct |
17 ms |
41572 KB |
Output is correct |
26 |
Correct |
15 ms |
41572 KB |
Output is correct |
27 |
Correct |
14 ms |
41560 KB |
Output is correct |
28 |
Correct |
16 ms |
41364 KB |
Output is correct |
29 |
Correct |
15 ms |
41572 KB |
Output is correct |
30 |
Correct |
15 ms |
41376 KB |
Output is correct |
31 |
Correct |
20 ms |
41600 KB |
Output is correct |
32 |
Correct |
17 ms |
41572 KB |
Output is correct |
33 |
Correct |
17 ms |
41572 KB |
Output is correct |
34 |
Correct |
15 ms |
41572 KB |
Output is correct |
35 |
Correct |
15 ms |
41572 KB |
Output is correct |
36 |
Correct |
17 ms |
41572 KB |
Output is correct |
37 |
Correct |
18 ms |
41572 KB |
Output is correct |
38 |
Correct |
16 ms |
41492 KB |
Output is correct |
39 |
Correct |
16 ms |
41620 KB |
Output is correct |
40 |
Correct |
15 ms |
41588 KB |
Output is correct |
41 |
Correct |
15 ms |
42856 KB |
Output is correct |
42 |
Correct |
15 ms |
42808 KB |
Output is correct |
43 |
Correct |
15 ms |
42804 KB |
Output is correct |
44 |
Correct |
14 ms |
42852 KB |
Output is correct |
45 |
Correct |
15 ms |
42844 KB |
Output is correct |
46 |
Correct |
15 ms |
42840 KB |
Output is correct |
47 |
Correct |
14 ms |
42844 KB |
Output is correct |
48 |
Correct |
14 ms |
42844 KB |
Output is correct |
49 |
Correct |
16 ms |
42840 KB |
Output is correct |
50 |
Correct |
15 ms |
42840 KB |
Output is correct |
51 |
Correct |
17 ms |
42844 KB |
Output is correct |
52 |
Correct |
15 ms |
42784 KB |
Output is correct |
53 |
Correct |
16 ms |
41564 KB |
Output is correct |
54 |
Correct |
16 ms |
41576 KB |
Output is correct |
55 |
Correct |
16 ms |
41572 KB |
Output is correct |
56 |
Correct |
15 ms |
41564 KB |
Output is correct |
57 |
Correct |
16 ms |
41560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
41564 KB |
Output is correct |
2 |
Correct |
15 ms |
41564 KB |
Output is correct |
3 |
Correct |
16 ms |
41528 KB |
Output is correct |
4 |
Correct |
15 ms |
41564 KB |
Output is correct |
5 |
Correct |
15 ms |
41564 KB |
Output is correct |
6 |
Correct |
15 ms |
41448 KB |
Output is correct |
7 |
Correct |
15 ms |
41556 KB |
Output is correct |
8 |
Correct |
15 ms |
41564 KB |
Output is correct |
9 |
Correct |
15 ms |
41564 KB |
Output is correct |
10 |
Correct |
16 ms |
41568 KB |
Output is correct |
11 |
Correct |
15 ms |
41560 KB |
Output is correct |
12 |
Correct |
16 ms |
41436 KB |
Output is correct |
13 |
Correct |
15 ms |
41576 KB |
Output is correct |
14 |
Correct |
15 ms |
41560 KB |
Output is correct |
15 |
Correct |
14 ms |
41564 KB |
Output is correct |
16 |
Correct |
17 ms |
41564 KB |
Output is correct |
17 |
Correct |
15 ms |
41560 KB |
Output is correct |
18 |
Correct |
15 ms |
41396 KB |
Output is correct |
19 |
Correct |
15 ms |
41572 KB |
Output is correct |
20 |
Correct |
15 ms |
41568 KB |
Output is correct |
21 |
Correct |
14 ms |
41436 KB |
Output is correct |
22 |
Correct |
15 ms |
41528 KB |
Output is correct |
23 |
Correct |
14 ms |
41564 KB |
Output is correct |
24 |
Correct |
16 ms |
41580 KB |
Output is correct |
25 |
Correct |
17 ms |
41572 KB |
Output is correct |
26 |
Correct |
15 ms |
41572 KB |
Output is correct |
27 |
Correct |
14 ms |
41560 KB |
Output is correct |
28 |
Correct |
16 ms |
41364 KB |
Output is correct |
29 |
Correct |
15 ms |
41572 KB |
Output is correct |
30 |
Correct |
15 ms |
41376 KB |
Output is correct |
31 |
Correct |
20 ms |
41600 KB |
Output is correct |
32 |
Correct |
17 ms |
41572 KB |
Output is correct |
33 |
Correct |
17 ms |
41572 KB |
Output is correct |
34 |
Correct |
15 ms |
41572 KB |
Output is correct |
35 |
Correct |
15 ms |
41572 KB |
Output is correct |
36 |
Correct |
17 ms |
41572 KB |
Output is correct |
37 |
Correct |
18 ms |
41572 KB |
Output is correct |
38 |
Correct |
16 ms |
41492 KB |
Output is correct |
39 |
Correct |
16 ms |
41620 KB |
Output is correct |
40 |
Correct |
15 ms |
41588 KB |
Output is correct |
41 |
Correct |
15 ms |
42856 KB |
Output is correct |
42 |
Correct |
15 ms |
42808 KB |
Output is correct |
43 |
Correct |
15 ms |
42804 KB |
Output is correct |
44 |
Correct |
14 ms |
42852 KB |
Output is correct |
45 |
Correct |
15 ms |
42844 KB |
Output is correct |
46 |
Correct |
15 ms |
42840 KB |
Output is correct |
47 |
Correct |
14 ms |
42844 KB |
Output is correct |
48 |
Correct |
14 ms |
42844 KB |
Output is correct |
49 |
Correct |
16 ms |
42840 KB |
Output is correct |
50 |
Correct |
15 ms |
42840 KB |
Output is correct |
51 |
Correct |
17 ms |
42844 KB |
Output is correct |
52 |
Correct |
15 ms |
42784 KB |
Output is correct |
53 |
Correct |
16 ms |
41564 KB |
Output is correct |
54 |
Correct |
16 ms |
41576 KB |
Output is correct |
55 |
Correct |
16 ms |
41572 KB |
Output is correct |
56 |
Correct |
15 ms |
41564 KB |
Output is correct |
57 |
Correct |
16 ms |
41560 KB |
Output is correct |
58 |
Execution timed out |
1066 ms |
42076 KB |
Time limit exceeded |
59 |
Halted |
0 ms |
0 KB |
- |