Submission #469187

#	Time	Username	Problem	Language	Result	Execution time	Memory
469187		amirmohammad_nezami	Split the sequence (APIO14_sequence)	C++14	0 / 100	9 ms	1308 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define PB push_back
#define _sz(e) e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0);

const int maxn = 2e5 + 4 , N = 1e6 + 4 , mod = 1e9 + 7 , INF = 1e9;

int n , k , a[maxn] , ps[maxn];
set <pair <pii , pii> > se;
vector <int> vec;

pii get(int l , int r) {
    int mx = 0 , id = -1;
    for (int i = l; i < r - 1; ++i) {
        int val = (ps[i + 1] - ps[l]) * (ps[r] - ps[i + 1]);
        if(val > mx) {
            mx = val , id = i;
        }
    }
    return {mx , id};
}

int main() {
    FAST;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ps[i + 1] = ps[i] + a[i];
    }
    pii c = get(0 , n);
    se.insert({c , {0 , n}});

    int cnt = k , res = 0;
    while(_sz(se) && cnt > 0) {
        auto c = *se.rbegin();
        se.erase(c);
        
        res += c.F.F;
        int l = c.S.F , r = c.S.S , p = c.F.S + 1;
        if(p - l > 1) se.insert({get(l , p) , {l , p}});
        if(r - p > 1) se.insert({get(p , r) , {p , r}});
        vec.PB(p);
        cnt--;
    }
    cout << res << '\n';
    for (auto u : vec) cout << u << ' ';
    cout << '\n';
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29