#include <bits/stdc++.h>
typedef long long ll;
template <typename T> class Vector : public std::vector<T> {
public:
using std::vector<T>::vector;
std::vector<ll> psum;
void calculate_prefix_sum() {
psum.resize(this->size());
std::partial_sum(this->begin(), this->end(), psum.begin());
}
T sum(ll a, ll b) {
if (a > b) {
return 0;
}
T ans = psum[b];
if (a - 1 >= 0) {
ans -= psum[a - 1];
}
return ans;
}
};
const ll N = 1e5 + 1, K = 201;
const ll inf = 1e15;
class Ans {
public:
ll tot;
ll cur;
ll idx;
};
bool operator<(const Ans &a, const Ans &b) {
return a.tot < b.tot;
}
Ans dp[N][K];
int main() {
ll n, k;
std::cin >> n >> k;
Vector<ll> a(n);
for (auto &i : a) {
std::cin >> i;
}
a.calculate_prefix_sum();
for (ll i = n - 1; i >= 0; -- i) {
for (ll j = 0; j <= k; ++ j) {
if (i == n - 1) {
if (j != 0) {
dp[i][j].tot = -inf;
} else {
dp[i][j].tot = 0;
}
continue;
}
if (j == 0) {
dp[i][j].tot = 0;
continue;
}
dp[i][j].tot = 0;
for (ll c = i; c < n - 1; c++) {
ll cur = a.sum(i, c) * a.sum(c + 1, n - 1);
dp[i][j] = std::max(dp[i][j], {cur + dp[c + 1][j - 1].tot, cur, c + 1});
}
}
}
std::cout << dp[0][k].tot << "\n";
ll cur = 0;
ll ops = k;
while (dp[cur][ops].tot > 0) {
std::cout << dp[cur][ops].idx << " ";
cur = dp[cur][ops].idx;
ops--;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
440 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - int32 expected |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
1 ms |
2396 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
1 ms |
2396 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
1 ms |
2904 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
1 ms |
2648 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
20 ms |
2496 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
1 ms |
2648 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
14 ms |
2652 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
19 ms |
2652 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
20 ms |
2648 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Correct |
6 ms |
2652 KB |
contestant found the optimal answer: 193556962 == 193556962 |
9 |
Correct |
4 ms |
2652 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
10 |
Correct |
7 ms |
2656 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
6748 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
10 ms |
6748 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
492 ms |
6596 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
11 ms |
6748 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
491 ms |
6588 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
421 ms |
6740 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
500 ms |
6592 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
492 ms |
6584 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
103 ms |
6588 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
202 ms |
6588 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1301 ms |
47772 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Correct |
1221 ms |
47744 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
3 |
Execution timed out |
2033 ms |
11092 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2056 ms |
61352 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |