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>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const int inf = 1e9;
const ll inf64 = 1e18;
struct output {
ll res;
void print() {
cout << res << "\n";
}
bool operator == (const output& o) const {
return res == o.res;
}
};
struct input {
int n, k;
vector<int> a;
vector<ll> pref;
input() = default;
void read() {
cin >> n >> k;
a.resize(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
}
void print() {
}
void gen() {
// use static
}
void gen_max_test() {
}
pair<ll, int> check(ll lambda) {
vector<pair<ll, int>> dp(n + 1, make_pair(-inf64, -inf));
dp[0] = {0, 0};
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
for (int j = 0; j < i; j++) {
pair<ll, int> tmp = {
dp[j].first + (pref[i] - pref[j]) + lambda,
dp[j].second - 1
};
dp[i] = max(dp[i], tmp);
}
}
return dp[n];
}
output fast() {
pref.assign(n + 1, 0);
for (int i = 1; i <= n; i++)
pref[i] = pref[i - 1] + a[i];
ll bl = -inf64, br = inf64, bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
if (-check(bm).second <= k) bl = bm;
else br = bm;
}
ll res = -inf64;
for (int di = -1; di <= 1; di++) {
auto tmp = check(bl + di);
if (-tmp.second <= k)
res = max(res, tmp.first + 1ll * (bl + di) * tmp.second);
}
return output{res};
}
output slow() {
#ifndef DEBUG
throw;
#endif
return output();
}
};
void test_case() {
input in;
in.read();
output res = in.fast();
res.print();
}
void work() {
int t = 1;
while (t--)
test_case();
}
void test() {
for (int t = 1;;t++) {
input in;
in.gen();
input in_fs = in;
input in_sl = in;
output fs = in_fs.fast();
output sl = in_sl.slow();
if (fs == sl) {
cout << "OK" << endl;
fs.print();
cout << "\n=========" << endl;
} else {
cout << "WA " << t << "\n";
cout << "exp\n";
sl.print();
cout << "\n=========\n";
cout << "fnd\n";
fs.print();
cout << "\n=========\n";
in.print();
break;
}
}
}
void max_test() {
input in;
in.gen_max_test();
input in_fs = in;
output fs = in_fs.fast();
fs.print();
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
work();
// test();
// max_test();
return 0;
}
Compilation message (stderr)
feast.cpp: In function 'void max_test()':
feast.cpp:27:8: warning: 'in.input::n' is used uninitialized in this function [-Wuninitialized]
27 | struct input {
| ^~~~~
feast.cpp:27:8: warning: 'in' is used uninitialized in this function [-Wuninitialized]
# | 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... |