이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define mp make_pair
#define random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
template <typename T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename Container>
void Print(Container& container, int starting) {
auto Start = container.begin() + starting, End = container.end();
while (Start != End) cout << *(Start++) << " ";
cout << '\n';
}
template <typename T>
void print(T&& t) {cout << t << '\n';}
template <typename T, typename... Args>
void print(T&& t, Args&&... args) {
cout << t << " ";
print(forward<Args>(args)...);
}
const int MAXN = 1e5 + 5, MAXK = 205;
int a[MAXN], dp[2][MAXN], par[MAXK][MAXN], n;
void compute(int32_t l, int32_t r, int32_t optl, int32_t optr, int32_t k)
{
if (l > r) return;
int32_t mid = (l + r) >> 1, row = k & 1;
pair <int32_t, int32_t> best = make_pair(-1, -1);
for (int32_t i = optl; i <= min(mid, optr); ++i) best = max(best, make_pair(dp[row ^ 1][i] + (a[n] - a[mid]) * (a[mid] - a[i]), i));
dp[row][mid] = best.first;
par[k][mid] = best.second;
int32_t opt = best.second;
compute(l, mid - 1, optl, opt, k);
compute(mid + 1, r, opt, optr, k);
}
inline void solve() {
int k;
cin >> n >> k;
memset(a, 0, sizeof a);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] += a[i - 1];
}
for (int i = 0; i <= k; ++i) {
for (int j = 0; j <= n; ++j) {
par[i][j] = -1;
}
}
for (int i = 0; i <= n; ++i) {
dp[0][i] = dp[1][i] = -1;
}
dp[0][0] = 0;
for (int i = 1; i <= k; ++i) {
compute(0, n, 0, n, i);
}
pair <int32_t, int32_t> ans = mp(-1, -1);
for (int i = 1; i <= n; ++i) {
ans = max(ans, mp(dp[k & 1][i], i));
}
print(ans.F);
vector <int32_t> seq(k);
int cur = k - 1;
while (k) {
seq[cur--] = ans.S;
ans.S = par[k--][ans.S];
}
Print(seq, 0);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
for (int test = 1; test <= T; ++test) {
// cout << "Case #" << test << ": ";
solve();
}
}
# | 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... |