Submission #742167

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
7421672023-05-15 17:31:40viwlesxqSplit the sequence (APIO14_sequence)C++17
89 / 100
1624 ms82128 KiB
#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;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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...