Submission #1114327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114327		peacebringer1667	Split the sequence (APIO14_sequence)	C++17	0 / 100	9 ms	2128 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;

int a[maxn];
ll pre[maxn];

inline ll sum(int l,int r){
	return pre[r] - pre[l - 1];
}

set <pair<ll,pair<pir,int>>> s;

void gen_cost(int l,int r){
	if (l > r) return;
	ll tmp = 0;
	int pivot = l;
	
	for (int i = l ; i <= r ; i++)
	  if (sum(l,i) * sum(i + 1,r) > tmp){
	  	tmp = sum(l,i) * sum(i + 1,r);
	  	pivot = i;
	  }
	
	s.insert({tmp,{{l,r},pivot}});
}

void solve(int n,int k,ll &cost,vector <int> &res){
	gen_cost(1,n);
	
	while (k--){
		pair <ll,pair<pir,int>> t = *s.rbegin();
		s.erase(t);
		
		int l = t.se.fi.fi,r = t.se.fi.se,pivot = t.se.se;
		
		cost += t.fi;
		res.push_back(pivot);
		
		gen_cost(l,pivot);
		gen_cost(pivot + 1,r);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,k;
	cin >> n >> k;
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	
	vector <int> res;
	ll cost = 0;
	solve(n,k,cost,res);
	
	cout << cost << "\n";
    for (int x : res) cout << x << " ";
	return 0;
}

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