Submission #1025801

#TimeUsernameProblemLanguageResultExecution timeMemory
1025801ach00Feast (NOI19_feast)C++14
100 / 100
854 ms24188 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define MP make_pair #define EPS 0.00001 int n,k; vector<ll> W; pair<ll,ll> solve(ll pen) { vector<vector<pair<ll,ll>>> dp(300005, vector<pair<ll,ll>>(2)); dp[0][0] = {0, 0}; dp[0][1] = {W[0] - pen, 1}; for(int i = 1; i < n; i++) { dp[i][0] = max(dp[i-1][0], dp[i-1][1]); dp[i][1] = max(MP(dp[i-1][1].first + W[i], dp[i-1][1].second), MP(dp[i-1][0].first + W[i] - pen, dp[i-1][0].second + 1)); } return max(dp[n-1][0], dp[n-1][1]); } int main() { cin >> n >> k; ll lower = 0; ll upper = 1000000000000000; W.resize(n); for(auto &a : W) cin >> a; while(lower < upper) { ll m = (lower+upper+1)/2; auto K = solve(m); if(K.second >= k) { lower = m; } else { upper = m-1; } } auto K = solve(lower); cout << K.first + k*lower; }
#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...