Submission #582071

#	Time	Username	Problem	Language	Result	Execution time	Memory
582071		l_reho	Split the sequence (APIO14_sequence)	C++14	0 / 100	11 ms	2396 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define ll long long

int N, K;
vector<ll> V;

struct info{
	
	ll start, end, mid;
	ll split;
	
	bool operator< (const info& rhs) const {
        return split < rhs.split;
    }
	
};

void solve(){
	
	cin>>N>>K;
	
	V.assign(N, 0);
	
	for(ll &v:V) cin>>v;
	
	priority_queue<info> pq;
	
	vector<ll> pref(N+1);
	for(int i = 0; i < N; i++) pref[i+1] = pref[i] + V[i];
	
	ll start, end, mid, split = 0, s = 0;
	
	for(int i = 0; i < N; i++){
		ll s = pref[i+1] * (pref[N]-pref[i+1]);
		
		if(s > split){
			start = 0;
			end = N-1;
			mid = i;
			split = s;
		}
		
	}
	
	pq.push({start, end, mid, split});
	
	ll ans = 0;
	
	vector<int> res;
	
	
	while(!pq.empty() && K){
		info I = pq.top();
		pq.pop();
		
		// cout<<I.split<<endl;
		res.push_back(I.mid+1);
		ans += I.split;
		
		// adesso registro gli split
		split = 0;
		for(int i = I.start; i < I.mid; i++){
			s = (pref[i+1] - pref[I.start]) * (pref[I.mid+1] - pref[i+1]);
			if(s > split){
				start = I.start;
				end = I.mid;
				mid = i;
				split = s;
			}		
		}	
		
		pq.push({start, end, mid, split});
		split = 0;
		for(int i = I.mid+1; i < I.end; i++){
			s = (pref[i+1] - pref[I.mid+1]) * (pref[I.end+1] - pref[i+1]);
			if(s > split){
				start = I.mid;
				end = I.end;
				mid = i;
				split = s;
			}		
		}	
		pq.push({start, end, mid, split});
		K--;
	}
	
	cout<<ans<<endl;
	for(int i : res) cout<<i<<" ";
	cout<<endl;
	/*
	 * 
	 *  7 3
		4 1 3 4 0 2 3 
	 * 
	 * */
}

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:50:9: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |  pq.push({start, end, mid, split});
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:50:9: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]

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