Submission #970744

#	Time	Username	Problem	Language	Result	Execution time	Memory
970744		Gangsta	Split the sequence (APIO14_sequence)	C++17	0 / 100	5 ms	2652 KiB

sequence

#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()

const int N = 2e5 + 1;

using namespace std;

ll a[N], p[N], ans, n, k;

set <pii> s;

vector <int> v;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
    	cin >> a[i];
    	p[i] = p[i-1] + a[i];
    }
    s.insert({1,n});
    while(k--){
    	ll mx = 0;
    	int bol, poz, poz1;
    	for(auto i: s){
    		for(int j = i.ff; j < i.ss; j++){
    			ll san = p[j] - p[i.ff-1], san1 = p[i.ss] - p[j];
    			if(san * san1 >= mx){
    				mx = san * san1;
    				bol = j;
    				poz = i.ff;
    				poz1 = i.ss;
    			}
    		}
    	}
    	ans += mx;
    	s.erase({poz,poz1});
    	s.insert({poz,bol});
    	s.insert({bol+1,poz1});
    	v.pb(bol);
    }
    cout << ans << '\n';
    for(auto i : v) cout << i << ' ';
}

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