/* https://oj.uz/problem/view/NOI19_feast */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef vector<vpll> vvpll; typedef vector<bool> vb; #define fi first #define se second const ll INSUB = 1ll, NOTSUB = 0ll; /* Find the maximal value of sum of all subarrays minus y * number subarrays */ pll solve_lambda(const vll& a, ll n, ll y) { vvpll dp(n, vpll(2ll, {0ll, 0ll})); dp[0ll][INSUB] = {a[0ll] - y, 1ll}; for(ll i = 1ll; i < n; i++) { dp[i][INSUB] = {dp[i - 1ll][INSUB].fi + a[i], dp[i - 1ll][INSUB].se}; pll insub_cand = {dp[i - 1ll][NOTSUB].fi + a[i] - y, dp[i - 1ll][NOTSUB].se + 1ll}; if(insub_cand > dp[i][INSUB]) dp[i][INSUB] = insub_cand; insub_cand = {dp[i - 1ll][NOTSUB].fi + a[i] - (y << 1ll), dp[i - 1ll][NOTSUB].se + 2ll}; // This line is here to ensure that we can create subarrays of size zero if(insub_cand > dp[i][INSUB]) dp[i][INSUB] = insub_cand; insub_cand = {dp[i - 1ll][INSUB].fi + a[i] - y, dp[i - 1ll][INSUB].se + 1ll}; // This one too if(insub_cand > dp[i][INSUB]) dp[i][INSUB] = insub_cand; dp[i][NOTSUB] = {dp[i - 1ll][NOTSUB].fi, dp[i - 1ll][NOTSUB].se}; pll notsub_cand = {dp[i - 1ll][INSUB].fi, dp[i - 1ll][INSUB].se}; if(notsub_cand > dp[i][NOTSUB]) dp[i][NOTSUB] = notsub_cand; notsub_cand = {dp[i - 1ll][NOTSUB].fi - y, dp[i - 1ll][NOTSUB].se + 1ll}; // This one too if(notsub_cand > dp[i][NOTSUB]) dp[i][NOTSUB] = notsub_cand; notsub_cand = {dp[i - 1ll][INSUB].fi - y, dp[i - 1ll][INSUB].se + 1ll}; // This one too if(notsub_cand > dp[i][NOTSUB]) dp[i][NOTSUB] = notsub_cand; } if(dp[n - 1ll][INSUB] > dp[n - 1ll][NOTSUB]) return dp[n - 1ll][INSUB]; return dp[n - 1ll][NOTSUB]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll n, k; cin >> n >> k; vll a(n, 0ll); for(ll& v : a) cin >> v; ll low = -1ll, hi = 1e13; ll low_val = 0ll; while(hi - low > 1ll) { ll mid = (hi + low) >> 1ll; auto [opt_val, opt_k] = solve_lambda(a, n, mid); if(opt_k >= k) { low = mid; low_val = opt_val; } else { hi = mid; } } cout << low_val + k * low << endl; return 0; }