#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz(x) (ll)(x.size())
#define all(v) v.begin(), v.end()
#define sz(x) (ll)(x.size())
#define se second
#define fi first
using namespace std;
const ll N = 1e5 + 9;
const ll M = 109;
ll n, i, j, k, bit[M][N], dp[N][M], a[N];
void up( ll x, ll y, ll val )
{
while(y <= n)
{
bit[x][y] = min(bit[x][y], val);
y += (y & (-y));
}
}
ll get( ll x, ll y )
{
if(x == 0) return 0;
ll maxn = 1e18;
while(y > 0)
{
maxn = min(maxn, bit[x][y]);
y -= (y & (-y));
}
return maxn;
}
int main()
{
#define TN "blocks"
if(fopen(TN ".in", "r"))
{
freopen(TN ".inp", "r", stdin);
freopen(TN ".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for( i = 1; i <= n; i ++ )
cin >> a[i];
stack<ll>f;
for( i = 1; i <= n; i ++ )
for( int j = 1; j <= k; j ++ ) bit[j][i] = 1e18;
for( i = 1; i <= n; i ++ )
{
ll vt = 0;
while(sz(f) && a[f.top()] <= a[i])
f.pop();
if(sz(f)) vt = f.top();
if(vt == 0)
{
for( int w = 1; w <= min(i, k); w ++)
dp[i][w] = a[i] + get(w - 1, n);
}
else
{
for( int w = 1; w <= min(i, k); w ++ )
dp[i][w] = min(dp[vt][w], a[i] + get(w - 1, n - vt));
}
f.push(i);
for( int w = 1; w <= min(i, k); w ++ ) up(w, n - i + 1, dp[i][w]);
}
cout << dp[n][k];
return 0;
}
/*
*/
Compilation message (stderr)
blocks.cpp: In function 'int main()':
blocks.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen(TN ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen(TN ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |