#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
pair<ll,ll> calc(vector<pair<ll,ll>> a){
ll sum = 0;
int n = sz(a);
for(int i = 0;i < n; ++i){
sum += a[i].first;
}
ll cur = 0;
ll mx = -1;
ll idx = -1;
for(int i = 0;i < n; ++i){
sum -= a[i].first;
cur += a[i].first;
if(mx <= cur * sum){
mx = cur * sum;
idx = i;
}
}
return {mx, idx};
}
void solve()
{
priority_queue<pair<pair<ll,ll>,vector<pair<ll,ll>>>> q;
int n, k;
cin >> n >> k;
vector<pair<ll,ll>> a(n);
ll sum = 0;
for(int i = 0;i < n; ++i){
cin >> a[i].first;
a[i].second = i;
sum += a[i].first;
}
ll count = 0;
q.push({calc(a), a});
ll ans = 0;
vector<int> why_print_counstruction;
while(count < k){
auto x = q.top();
q.pop();
if(sz(x.second) < 2){
continue;
}
++count;
auto f = calc(x.second);
ans += f.first;
vector<pair<ll,ll>> A, B;
for(int i = 0;i <= f.second; ++i){
A.pb(x.second[i]);
}
for(int i = f.second + 1; i < sz(x.second); ++ i){
B.pb(x.second[i]);
}
why_print_counstruction.pb(x.second[f.second].second);
q.push({calc(A), A});
q.push({calc(B), B});
}
cout << ans << "\n";
for(auto x: why_print_counstruction){
cout << x + 1 << " ";
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Incorrect |
0 ms |
204 KB |
contestant didn't find the optimal answer: 951 < 999 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
contestant didn't find the optimal answer: 1093726 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
0 ms |
332 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
1 ms |
332 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
0 ms |
204 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
0 ms |
332 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Incorrect |
0 ms |
332 KB |
position 9 occurs twice in split scheme |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
contestant didn't find the optimal answer: 21419072 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1132 KB |
contestant didn't find the optimal answer: 1794250000 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
7912 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
2 |
Incorrect |
12 ms |
8208 KB |
contestant didn't find the optimal answer: 19874432171 < 19874432173 |
3 |
Halted |
0 ms |
0 KB |
- |