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();
    }
}
# 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 -