# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
742167 | viwlesxq | Split the sequence (APIO14_sequence) | C++17 | 1624 ms | 82128 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>
using namespace std;
typedef int64_t ll;
typedef string str;
const int N = 1e5 + 1, K = 201;
int n, k;
ll a[N], pref[N];
vector <ll> dp_old(N), dp_new(N);
int p[N][K], v;
ll get(int l, int r) {
return (pref[r] - pref[l - 1]) * (pref[n] - pref[r]);
}
void solve(int l, int r, int opt_l, int opt_r) {
if (l > r) {
return;
}
int mid = (l + r) >> 1;
pair <ll, int> best = {-1, -1};
for (int i = opt_l; i <= min(mid - 1, opt_r); ++i) {
best = max(best, {dp_old[i] + get(i + 1, mid), i});
}
dp_new[mid] = best.first;
int opt = best.second;
p[mid][v] = opt;
# | 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... |