Submission #489362

#	Time	Username	Problem	Language	Result	Execution time	Memory
489362		SlavicG	Split the sequence (APIO14_sequence)	C++17	0 / 100	16 ms	8208 KiB

sequence

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29