Submission #997138

#TimeUsernameProblemLanguageResultExecution timeMemory
997138anonymous321Feast (NOI19_feast)C++17
0 / 100
174 ms11648 KiB
// https://oj.uz/problem/view/NOI19_feast #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n, k; cin >> n >> k; vector<ll> a (n); for (int i = 0; i < n; i++) { cin >> a[i]; } ll ans = 0; ll lo = -1e9; ll hi = 1e9; while (lo < hi) { ll mid = lo + (hi - lo)/2; vector<ll> dp (n+1, 0); vector<ll> p (n+1, 0); ll best = 0; int id = 0; vector<int> cnt (n+1, 0); for (int i = 0; i < n; i++) { p[i+1] = p[i] + a[i]; dp[i+1] = max(dp[i+1], dp[i]); cnt[i+1] = cnt[i]; if (dp[i+1] < best + p[i+1] - lo) { dp[i+1] = best + p[i+1] - lo; cnt[i+1] = cnt[id] + 1; } if (best < dp[i+1] - p[i+1]) { best = dp[i+1] - p[i+1]; id = i+1; } } if (cnt[n] <= k) { hi = mid; ans = dp[n]; } else { lo = mid+1; } } cout << ans + k*lo << "\n"; 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...