#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define md ((l + r) >> 1)
#pragma GCC optimize("Ofast,O3")
const int BUF_SZ = 1 << 20;
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
if (pos == len) {
pos = 0;
len = (int)fread(buf, 1, BUF_SZ, stdin);
if (!len) {
return EOF;
}
}
return buf[pos++];
}
int read_int() {
int x;
char ch;
int sgn = 1;
while (!isdigit(ch = next_char())) {
if (ch == '-') {
sgn *= -1;
}
}
x = ch - '0';
while (isdigit(ch = next_char())) {
x = x * 10 + (ch - '0');
}
return x * sgn;
}
long long read_ll() {
long long x;
char ch;
int sgn = 1;
while (!isdigit(ch = next_char())) {
if (ch == '-') {
sgn *= -1;
}
}
x = ch - '0';
while (isdigit(ch = next_char())) {
x = x * 10 + (ch - '0');
}
return x * sgn;
}
} // namespace Input
inline namespace Output {
char buf[BUF_SZ];
int pos;
void flush_out() {
fwrite(buf, 1, pos, stdout);
pos = 0;
}
void write_char(char c) {
if (pos == BUF_SZ) {
flush_out();
}
buf[pos++] = c;
}
void write_int(long long x) {
static char num_buf[100];
if (x < 0) {
write_char('-');
x *= -1;
}
int len = 0;
for (; x >= 10; x /= 10) {
num_buf[len++] = (char)('0' + (x % 10));
}
write_char((char)('0' + x));
while (len) {
write_char(num_buf[--len]);
}
write_char('\n');
}
// auto-flush output when program exits
void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output
ll dp[2][100'005];
int a[100'005], sparse[17][100'005], lg[100'005];
void build(int n)
{
for (int i = 1; i <= n; i++) sparse[0][i] = a[i];
for (int j = 1; j < 17; j++) for (int i = 1; i + (1 << (j - 1)) <= n; i++) sparse[j][i] = max(sparse[j-1][i], sparse[j-1][i + (1 << (j - 1))]);
}
int query(int l, int r)
{
int sz = lg[r-l+1];
return max(sparse[sz][l], sparse[sz][r-(1 << sz) + 1]);
}
int n, m;
int mstanyeh(int lvl, int j, int k)
{
if (dp[lvl & 1][j] - dp[lvl & 1][k] > query(k + 1, n) - query(j + 1, n)) return n + 1;
int l = max(j + 1, k + 1), r = n;
while (l <= r)
{
dp[lvl & 1][j] - dp[lvl & 1][k] <= query(k + 1, md) - query(j + 1, md)? r = md - 1 : l = md + 1;
}
return l;
}
int v[100'005], mstany[100'005], vsz, mstanysz, val;
signed main()
{
init_output();
lg[1] = 0;
for (int i = 2; i < 100'005; i++) lg[i] = lg[i >> 1] + 1;
int t = read_int(), st = read_int();
while (t--)
{
n = read_int(), m = read_int();
for (int i = 1; i <= n; i++) a[i] = read_int();
build(n);
for (int i = 1; i <= n; i++) dp[0][i] = query(1, i);
dp[0][0] = dp[1][0] = 1e18;
for (int i = 1; i < m; i++)
{
vsz = mstanysz = 0;
for (int j = 1; j <= n; j++)
{
while (vsz > 1 && mstany[mstanysz-1] <= (val = mstanyeh(i - 1, v[vsz-1], j - 1))) vsz--, mstanysz--;
if (vsz == 1) val = mstanyeh(i - 1, v[vsz-1], j - 1);
v[vsz++] = j - 1;
if (vsz > 1) mstany[mstanysz++] = val;
while (vsz > 1 && mstany[mstanysz-1] <= j) vsz--, mstanysz--;
dp[i&1][j] = dp[(i - 1)&1][v[vsz-1]] + query(v[vsz-1] + 1, j);
}
}
write_int(dp[(m - 1) & 1][n]);
}
return 0;
}
Compilation message
blocks.cpp: In function 'int main()':
blocks.cpp:123:25: warning: unused variable 'st' [-Wunused-variable]
123 | int t = read_int(), st = read_int();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1033 ms |
2396 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1038 ms |
2396 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1033 ms |
2396 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1033 ms |
2396 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
