| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1113199 | HiepVu217 | Feast (NOI19_feast) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define int long long;
using namespace std;
const int N = 3e5 + 17;
int n, k;
long long a[N];
pair <long long, int> f[N], m;
inline pair <long long, int> calc (long long c)
{
f[0] = m = {0, 0};
for (int i = 1; i <= n; ++i)
{
f[i] = f[i - 1];
if (m.first + a[i] - c > f[i].first || (m.first + a[i] - c == f[i].first && m.second + 1 < f[i].second))
{
f[i].first = m.first + a[i] - c;
f[i].second = m.second + 1;
}
if (f[i].first - a[i] > m.first || (f[i].first - a[i] == m.first && f[i].second < m.second))
{
m.first = f[i].first - a[i];
m.second = f[i].second;
}
}
return f[n];
}
int32_t 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;
m = calc (mid);
if (m.second == k)
{
cout << mid * k + m.first;
return 0;
}
if (m.second > k)
{
l = mid + 1;
continue;
}
r = mid - 1;
}
long long ans = l * k + calc(l).first;
cout << ans;
}