#include <iostream> #include <vector> #include <map> #include <string> #include <algorithm> #include <cassert> #include <cstring> #include <stack> #include <set> #include <cmath> #include <queue> #include <iomanip> using namespace std; const int N = 300005; // f[i][j][m] là tổng lớn nhất khi ta xét vị trí i đang ở group j và group j đó nếu = 0 group đang đóng và ngược lại; pair<long long , long long > f[N][2]; int n , m; int a[N]; pair<long long, long long> better(pair<long long, long long> x, pair<long long, long long> y){ if(x.first != y.first) return (x.first > y.first) ? x : y; return (x.second > y.second) ? x : y; } auto solve(long long lmb){ const long long NEG = -(1LL << 60); f[0][0] = make_pair(0 , 0); f[0][1] = make_pair(NEG , 0); for(int i = 1; i <= n ; i++){ f[i][0] = better(f[i - 1][0] , f[i - 1][1]); pair<long long, long long> start = make_pair(f[i - 1][0].first + a[i] - lmb , f[i - 1][0].second + 1); pair<long long, long long> extend = make_pair(f[i - 1][1].first + a[i] , f[i - 1][1].second); f[i][1] = better(start, extend); } return better(f[n][0] , f[n][1]); } int main(){ cin >> n >> m; for(int i = 1; i <= n ;i++){ cin >> a[i]; } long long lo = 0; long long hi = 1e18; long long p = lo; while(lo <= hi){ long long mid = (lo + hi) / 2; if(solve(mid).second >= m ){ p = mid; lo = mid + 1; }else{ hi = mid - 1; } // cout << solve(mid).second << endl; } cout << solve(p).first + p * m; return 0; }