#include <bits/stdc++.h> #define ll long long #define task "FEAST" using namespace std; const int N = 3e5 + 16; const ll INF = 1e18; int n, K; ll a[N]; namespace sub7 { pair <ll, ll> dp[N][2]; pair <ll, ll> dpCalc(ll k) { for (int i = 0; i <= n; i++) { dp[i][0] = dp[i][1] = {-INF, 0}; } dp[0][0] = {0, 0}; for (int i = 1; i <= n; i++) { dp[i][0] = max(dp[i][0], dp[i - 1][0]); dp[i][0] = max(dp[i][0], dp[i - 1][1]); dp[i][1] = max(dp[i][1], make_pair(dp[i - 1][0].first + a[i] - k, dp[i - 1][0].second + 1)); dp[i][1] = max(dp[i][1], make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second)); } return max(dp[n][0], dp[n][1]); } void solve() { ll l = 0, r = INF, mid, result; while (l <= r) { mid = l + r + 1 >> 1; if (dpCalc(mid).second >= K) { l = mid + 1; result = mid; } else { r = mid - 1; } } cout << dpCalc(result).first + result * K; } } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n >> K; for (int i = 1; i <= n; i++) { cin >> a[i]; } sub7 :: solve(); return 0; }

feast.cpp: In function 'int main()':
feast.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~