Submission #1249215

#TimeUsernameProblemLanguageResultExecution timeMemory
1249215HiepVu217Feast (NOI19_feast)C++17
0 / 100
98 ms35276 KiB
#include <bits/stdc++.h> #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") using namespace std; const int N = 3e5 + 17; int n, k; long long a[N]; pair <long long, int> f[N][7], m; inline pair <long long, int> calc (long long c) { f[1][0] = {0, 0}, f[1][1] = {a[1] - c, 1}; for (int i = 2; i <= n; ++i) { f[i][0] = max (f[i - 1][0], f[i - 1][1]); f[i][1] = max (make_pair (f[i - 1][1].first + a[i], f[i - 1][1].second), make_pair (f[i - 1][0].first + a[i] - c, f[i - 1][0].second + 1)); } return max (f[n][0], f[n][1]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] += a[i - 1]; } long long l = 1, r = 3e14; while (l < r) { long long mid = l + r + 1 >> 1; m = calc (mid); if (m.second >= k) { l = mid; continue; } r = mid - 1; } m = calc(l); long long ans = l * m.second + m.first; cout << ans; }
#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...