Submission #1209940

#TimeUsernameProblemLanguageResultExecution timeMemory
1209940azaylibelzFeast (NOI19_feast)C++20
100 / 100
925 ms23892 KiB
#include <iostream> #include <string> #include <stdio.h> #include <vector> #include <map> #include <algorithm> #include <numeric> #include <cmath> #include <iterator> #include <stack> #include <queue> #include <set> #include <climits> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 1e9 + 7; const ll infmax = ~(1LL << 64 - 1); const ll infmin = (1LL << 64 - 1); pair<ll, ll> dp(vector<ll>& a, ll pen) { ll n = a.size(); vector<vector<pair<ll, ll>>> dp(n, vector<pair<ll, ll>>(2)); dp[0][0] = {0, 0}; dp[0][1] = {a[0] - pen, 1}; for(ll i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - pen, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second)); } return max(dp[n - 1][0], dp[n - 1][1]); } signed main() { ll n, k; cin >> n >> k; vector<ll> nums(n); for(ll i = 0; i < n; i++) cin >> nums[i]; ll lo = 0, hi = 1e18; while(lo < hi) { ll mid = (lo + hi) / 2; if(dp(nums, mid).second >= k) lo = mid + 1; else hi = mid; } cout << dp(nums, max(lo - 1, 0LL)).first + max(lo - 1, 0LL) * k; 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...