#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("fma")
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// the real solution is quite hard to implement (two pointers on convex hull), even if I knew how to solve this problem.
// (problem 1 is solved by using the observation that there's only n distinct
// palindromic substrings in a string of length n, and then use a map of hashes.)
// still, the heuristic worked surprisingly well, so I'll see if I can optimize to make it work.
// I'll comment my code to make it understandable.
ll dp[100005][2]; // dp[i][j]: the best way to partition prefix of length i into j parts.
int trace[100005][205]; // trace[i][j]: just a trace to calculate dp.
ll a[100005], prefix[100005]; // ...
ll patrol[30], seg[30], seg_size; // patrol[i]: current index of "patrol" pointer i, seg[i]: bound for patrol i, seg_size: size of the segment that they'll be patrolling.
int main(){
fastio;
ll n, k; cin >> n >> k; k++;
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
for (ll i = 1; i <= n; i++) dp[i][1] = (prefix[i] * prefix[i]);
if (n <= 1000){
// the brute force solution. this works is something like (n ^ 2 * k) / 6,
// and even with a bad constant it should be fast enough.
for (ll l = 2; l <= k; l++){
ll now = l % 2, prv = now ^ 1;
for (ll i = l; i <= n; i++){
dp[i][now] = 1e18;
for (ll j = l - 1; j < i; j++){
ll calc = dp[j][prv] + (prefix[i] - prefix[j]) * (prefix[i] - prefix[j]);
if (dp[i][now] > calc){
dp[i][now] = calc; trace[i][l] = j;
}
}
}
}
}
if (n > 10000){
// first heuristic (made by my wrong observation that the function will be convex): two pointers to find the minima.
// still, this managed to pass the last subtask, which is certainly saying something about it's efficiency.
for (ll l = 2; l <= k; l++){
ll ptr = l - 1;
ll now = l % 2, prv = now ^ 1;
for (ll i = l; i <= n; i++){
while ((ptr < i - 1) && (dp[ptr][prv] + (prefix[i] - prefix[ptr]) * (prefix[i] - prefix[ptr])
>= dp[ptr + 1][prv] + (prefix[i] - prefix[ptr + 1]) * (prefix[i] - prefix[ptr + 1]))) ptr++;
dp[i][now] = dp[ptr][prv] + (prefix[i] - prefix[ptr]) * (prefix[i] - prefix[ptr]); trace[i][l] = ptr;
}
}
}
else{
// second heuristic (a small improvement over the previous heuristic):
// we create "patrol" pointers: pointers that are supposed to find the minima of a segment.
// it functions in basically the same way as the pointer in the first heuristic, except that it should be able
// to find some more "deep" positions while runs a lot slower. (25x)
seg_size = n / 25 + (n % 25 != 0);
for (ll i = 0; i < 25; i++) seg[i] = (i + 1) * seg_size - 1;
for (ll l = 2; l <= k; l++){
for (ll i = 0; i < 25; i++){
if (i * seg_size <= l - 1) patrol[i] = l - 1;
else patrol[i] = i * seg_size;
}
ll now = l % 2, prv = now ^ 1;
for (ll i = l; i <= n; i++){
dp[i][now] = 1e18;
for (ll p = 0; p < 25; p++){
while ((patrol[p] < min(seg[p], i - 1)) &&
(dp[patrol[p]][prv] + (prefix[i] - prefix[patrol[p]]) * (prefix[i] - prefix[patrol[p]])
>= dp[patrol[p] + 1][prv] + (prefix[i] - prefix[patrol[p] + 1]) * (prefix[i] - prefix[patrol[p] + 1]))) patrol[p]++;
ll calc = dp[patrol[p]][prv] + (prefix[i] - prefix[patrol[p]]) * (prefix[i] - prefix[patrol[p]]);
if (dp[i][now] > calc){
dp[i][now] = calc; trace[i][l] = patrol[p];
}
}
}
}
}
cout << (prefix[n] * prefix[n] - dp[n][k % 2]) / 2 << "\n";
ll cur = n;
for (ll l = k; l > 1; l--){
cout << trace[cur][l] << " "; cur = trace[cur][l];
}
}
Compilation message
sequence.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops, no-stack-protector")
|
sequence.cpp:34: warning: ignoring #pragma 03 [-Wunknown-pragmas]
34 | #pragma 03
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
declared answer doesn't correspond to the split scheme: declared = 117, real = 98 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
416 KB |
declared answer doesn't correspond to the split scheme: declared = 1094750, real = 1093343 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
declared answer doesn't correspond to the split scheme: declared = 614151152, real = 610590000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
1152 KB |
declared answer doesn't correspond to the split scheme: declared = 21774088, real = 21286056 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
8704 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
| 2 |
Correct |
10 ms |
8704 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
| 3 |
Correct |
354 ms |
8704 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
| 4 |
Correct |
11 ms |
8752 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
| 5 |
Correct |
225 ms |
8740 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
| 6 |
Incorrect |
255 ms |
8744 KB |
contestant didn't find the optimal answer: 514787559390 < 514790755404 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
55 ms |
83704 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
| 2 |
Correct |
54 ms |
83704 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
| 3 |
Correct |
354 ms |
83672 KB |
contestant found the optimal answer: 497313449256899208 == 497313449256899208 |
| 4 |
Correct |
56 ms |
83704 KB |
contestant found the optimal answer: 374850090734572421 == 374850090734572421 |
| 5 |
Correct |
409 ms |
83832 KB |
contestant found the optimal answer: 36183271951 == 36183271951 |
| 6 |
Correct |
293 ms |
83704 KB |
contestant found the optimal answer: 51629847150471 == 51629847150471 |
| 7 |
Correct |
311 ms |
83704 KB |
contestant found the optimal answer: 124074747024496432 == 124074747024496432 |
| 8 |
Correct |
250 ms |
83704 KB |
contestant found the optimal answer: 309959349080800 == 309959349080800 |
| 9 |
Correct |
266 ms |
83832 KB |
contestant found the optimal answer: 124113525649823701 == 124113525649823701 |
| 10 |
Correct |
329 ms |
83704 KB |
contestant found the optimal answer: 124309619349406845 == 124309619349406845 |
