Submission #1209950

#TimeUsernameProblemLanguageResultExecution timeMemory
1209950raphaeltfaFeast (NOI19_feast)C++20
100 / 100
914 ms23916 KiB
#include <bits/stdc++.h> using namespace std; #define int long long pair<int, int> lambda_func(int lmb, const vector<int> &base){ vector<vector<pair<int, int>>> dp(base.size(), vector<pair<int, int>> (2, {0, 0})); dp[0][0] = {0, 0}, dp[0][1] = {base[0] - lmb, 1}; for(int i = 1; i < base.size(); i++){ dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = max( make_pair(dp[i - 1][0].first + base[i] - lmb, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + base[i], dp[i - 1][1].second)); } return max(dp.back()[0], dp.back()[1]); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; vector<int> base(n); for(int & i : base) cin >> i; int left = 0, right = 1e18; while(left < right){ int mid = (left + right + 1) / 2; pair<int, int> res = lambda_func(mid, base); if(res.second >= m) left = mid; else right = mid - 1; } int res = lambda_func(left, base).first + left * m; cout << res << endl; }
#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...