#include #include using namespace std; using ll = long long; using S = pair; S op(S lhs, S rhs){return max(lhs, rhs);} constexpr S e(){return make_pair(-(1ll << 62), -1);} int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n, k; cin >> n >> k; vector a(n); for(auto &&v : a) cin >> v; ll sv = 0, mx = -(1ll << 62); int p = 0; for(int i = 0; i < n; i++){ sv += a[i]; if(i >= k - 1 && sv > mx){ mx = sv; p = i + 1; } } vector> sv2(n + 1); sv2[n] = make_pair(0, n); for(int i = n - 1; i >= 0; i--){ sv2[i] = make_pair(sv2[i + 1].first + a[i], i); } atcoder::segtree seg(sv2); ll ans = mx; int l = 1; for(int i = k - 2; i >= 0; i--){ int r = p - i; auto pa = seg.prod(l, r); ans += pa.first - sv2[p].first; l = pa.second + 1; } cout << ans << '\n'; }