Submission #1026013

#TimeUsernameProblemLanguageResultExecution timeMemory
1026013ach00Feast (NOI19_feast)C++14
100 / 100
93 ms5460 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) { pair<ll,ll> zero = {0,0}; pair<ll,ll> one = {W[0] - pen, 1}; for(int i = 1; i < n; i++) { pair<ll,ll> _zero, _one; _zero = max(zero, one); _one = max(MP(one.first + W[i], one.second), MP(zero.first + W[i] - pen, zero.second + 1)); zero = _zero; one = _one; } return max(zero, one); } int main() { ios_base::sync_with_stdio(0); cin >> n >> k; ll lower = 0; ll upper = 10000000000000; 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...