# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1113202 | HiepVu217 | Feast (NOI19_feast) | C++17 | 116 ms | 7260 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")
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 (int 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];
}
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;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |