#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
template <typename A, typename B>
bool chmin(A &a, const B &b) {
if(a > b) {
return a = b, true;
}
return false;
}
template <typename A, typename B>
bool chmax(A &a, const B &b) {
if(a < b) {
return a = b, true;
}
return false;
}
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for(auto &x : a) cin >> x;
vector<int> pref(n + 1);
for(int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + a[i];
}
auto sum = [&](int l, int r) {
return pref[r + 1] - pref[l];
};
vector<int> choose(n - 1);
for(int i = 0; i < k; i++) {
choose[i] = 1;
}
reverse(all(choose));
vector<int> v;
int ans = 0;
do {
vector<int> p;
for(int i = 0; i < n - 1; i++) {
if(choose[i]) {
p.pb(i);
}
}
do {
set<pair<int, int>> st;
st.emplace(0, n - 1);
int cur = 0;
for(auto i : p) {
auto [l, r] = *(--st.upper_bound({i, n}));
cur += sum(l, i) * sum(i + 1, r);
// cout << l << ' ' << r << nl;
st.erase({l, r});
st.emplace(l, i);
st.emplace(i + 1, r);
}
// for(auto i : p) cout << i + 1 << ' ';
// cout << ": " << cur << nl;
if(ans < cur) {
ans = cur;
v = p;
}
} while(next_permutation(all(p)));
} while(next_permutation(all(choose)));
cout << ans << nl;
for(auto i : v) {
cout << i + 1 << ' ';
}
cout << nl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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... |