Submission #1229380

#TimeUsernameProblemLanguageResultExecution timeMemory
1229380unnickFeast (NOI19_feast)C++20
100 / 100
156 ms5104 KiB
#include <iostream> #include <vector> typedef long long int real_ll; typedef __int128_t ll; using namespace std; #define dbg(v) cout << #v << " = " << v << "\n"; int main() { int n, k; cin >> n >> k; vector<ll> arr(n); for (auto &v: arr) {int t; cin >> t; v = t;} // vector<ll> b(k*2+1); // for (int i = 0; i < n; i++) { // ll a; // cin >> a; // for (int j = k*2-1; j >= 1; j -= 2) { // b[j+1] = max(b[j], b[j+1]); // b[j] = max(b[j], b[j-1]) + a; // } // } // ll r = 0; // for (ll v: b) r = max(v,r); ll ah = (((ll) 1)<<64); ll al = 0; ll r; while (ah >= al) { ll am = (ah + al) / 2; ll pn = 0; ll pi = -(((ll) 1)<<120); ll scn = 0; ll sci = 0; for (auto v: arr) { if (pi > pn) scn = sci; pn = max(pi, pn); if (pn-am > pi) sci = scn+1; pi = max(pi, pn-am) + v; } r = max(pn, pi) + (pn > pi ? scn : sci) * am; // dbg(am); // dbg(pn); // dbg(pi); // dbg(scn); // dbg(sci); if (al == ah) break; if ((pn > pi ? scn : sci) > k) { al = am; if (al == am) al++; } else { ah = am; } } cout << (real_ll) r << "\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...