// #pragma GCC optimize ("O3") // #pragma GCC optimize ("unroll-loops") // #pragma comment(linker, "/STACK:2000000") #include<bits/stdc++.h> using namespace std; #define ll long long #define int ll #define ld double #define ui unsigned int #define endl "\n" #define FOCUS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void Go() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } const int N = 3e5 + 5; pair<ld,ll> dp[N][2]; vector<int> vals(N); ld C = 0; int n, k; pair<ld,ll> merge(pair<ld,ll> &a, pair<ld,ll>& b) { if (a.first>b.first)return a; if (b.first>a.first)return b; if (a.second<b.second)return a; return b; } pair<ld,ll> solve(int idx,int open) { if (idx == n) { return {0, 0}; } auto &ret = dp[idx][open]; if (ret.first != -1)return ret; ret = {0, 0}; if (!open) { auto res = solve(idx + 1, open); ret = merge(ret, res); } if (!open) { auto res = solve(idx + 1, 1); res.first += -C + vals[idx]; res.second++; ret = merge(res, ret); } if (open) { // close auto res = solve(idx, 0); ret = merge(res, ret); // contine } if (open) { auto res = solve(idx + 1, 1); res.first += vals[idx]; ret = merge(res, ret); } return ret; } signed main() { // Go(); FOCUS cin >> n >> k; for (int i = 0; i < n; i++)cin >> vals[i]; ld lo = 0, hi = 3e14; ld best = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = {-1, -1}; } } C = 0; while (hi - lo > 1e-6) { auto mid = (lo + hi) / 2; for (int i = 0; i < N; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = {-1, -1}; } } C = mid; auto res = solve(0, 0); if (res.second > k) { lo = mid; } else { hi = mid; } } C = hi; for (int i = 0; i < N; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = {-1, -1}; } } auto res = solve(0, 0); cout << res.first + C * res.second; // open close // skip // binary search on extra cost to add person }

feast.cpp: In function 'void Go()':
feast.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~