## Submission #489362

# Submission time Handle Problem Language Result Execution time Memory
489362 2021-11-22T17:34:12 Z SlavicG Split the sequence (APIO14_sequence) C++17
0 / 100
16 ms 8208 KB
```#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();
}
}
```

#### Subtask #1 0 / 11.0

# 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 -

#### Subtask #2 0 / 11.0

# 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 -

#### Subtask #3 0 / 11.0

# 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 -

#### Subtask #4 0 / 17.0

# 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 -

#### Subtask #5 0 / 21.0

# 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 -

#### Subtask #6 0 / 29.0

# 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 -