#pragma GCC optimize("Ofast") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; #define f0r(i, n) for (auto i = 0; i < (n); ++i) #define fnr(i, n, k) for (auto i = (n); i < (k); ++i) #define all(v) (v).begin(), (v).end() #define pb push_back #define F first #define S second #define ctn(x) cout << x << '\n' #define forl(a, l) for (auto a : l) #define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl; #define lb(v, x) (lower_bound(all(v), x) - begin(v)) #define ub(v, x) (upper_bound(all(v), x) - begin(v)) #define pq priority_queue template <class T> using V = vector<T>; using ll = long long; using vi = V<int>; using vl = V<ll>; using pi = pair<int, int>; using ti = tuple<int, int, int>; using Adj = V<vi>; using vvi = V<vi>; using db = long double; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int K, N; cin >> N >> K; vi A(N); vl pf(N+1); f0r(i, N) { cin >> A[i]; pf[i+1] = pf[i] + A[i]; } db lo = 0, hi = 1e9; V<pair<db, int>> dp(N+1); db ans = 0; f0r(_, 100) { db m = (lo+hi)/2; // lambda dp.assign(N+1, {0, 0}); pair<db, int> mx{0, 0}; fnr(i, 1, N+1) { dp[i] = max(dp[i-1], { mx.F+pf[i] - m, mx.S+1 }); mx = max(mx, {dp[i].F - pf[i], dp[i].S}); } if (dp[N].S <= K) { // reduce lambda hi = m; ans = max(ans, (dp[N].F + dp[N].S * m)); } else lo = m; } ctn((ll)ans); }