Submission #1190792

#TimeUsernameProblemLanguageResultExecution timeMemory
1190792pemguimnFeast (NOI19_feast)C++20
0 / 100
256 ms16676 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int INF = 1e18 + 5; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n); for(int &x : a) cin >> x; int lo = -1e9, hi = 1e9, ans = -1; while(lo <= hi){ int mid = (lo + hi) / 2; auto check = [&](int lb){ vector dp(2, vector<pii> (n, {INF, INF})); dp[0][0] = {0, 0}; dp[1][0] = {-lb, 1}; for(int i = 1; i < n; i++){ dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]); dp[1][i] = max(pii {dp[0][i - 1].first - lb + a[i], dp[0][i - 1].second + 1}, {dp[1][i - 1].first + a[i], dp[0][i - 1].second}); } return max(dp[0][n - 1], dp[1][n - 1]); }; pii cur = check(mid); if(cur.second >= k){ ans = cur.first + mid * k, lo = mid + 1; } else{ hi = mid - 1; } } cout << ans << '\n'; }
#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...