Submission #1078640

#TimeUsernameProblemLanguageResultExecution timeMemory
1078640YudoTLEFeast (NOI19_feast)C++17
100 / 100
102 ms12832 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; const ll INF = LLONG_MAX / 2; const int iINF = INT_MAX / 2; const int MAXN = 3e5 + 5; int n, k; ll arr[MAXN], dp[MAXN][2]; int cnt[MAXN][2]; pll eval(ll c) { dp[0][1] = -INF; for (int i = 1; i <= n; i++) { if (dp[i - 1][0] >= dp[i - 1][1]) { dp[i][0] = dp[i - 1][0]; cnt[i][0] = cnt[i - 1][0]; } else { dp[i][0] = dp[i - 1][1]; cnt[i][0] = cnt[i - 1][1]; } if (dp[i - 1][0] - c >= dp[i - 1][1]) { dp[i][1] = arr[i] + dp[i - 1][0] - c; cnt[i][1] = cnt[i - 1][0] + 1; } else { dp[i][1] = arr[i] + dp[i - 1][1]; cnt[i][1] = cnt[i - 1][1]; } } return max(pll(dp[n][0], cnt[n][0]), pll(dp[n][1], cnt[n][1])); } void solve() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> arr[i]; ll answer = 0; ll lo = 0, hi = INF; while (lo <= hi) { ll mi = lo + (hi - lo) / 2; auto [optv, optc] = eval(mi); if (optc <= k) hi = mi - 1, answer = max(answer, optv + optc * mi); else lo = mi + 1; } cout << answer << '\n'; } int main() { ios_base::sync_with_stdio(false), cin.tie(0); int t = 1; // cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...