oj.uz

Submission #582071

# Submission time Handle Problem Language Result Execution time Memory
582071 2022-06-23T10:57:56 Z l_reho Split the sequence (APIO14_sequence) C++14
0 / 100
 11 ms 2396 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB contestant found the optimal answer: 108 == 108
2 Incorrect 0 ms 212 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB contestant didn't find the optimal answer: 1093726 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 212 KB contestant found the optimal answer: 311760000 == 311760000
3 Incorrect 1 ms 340 KB position 3 occurs twice in split scheme
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB contestant didn't find the optimal answer: 21419072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB contestant didn't find the optimal answer: 1794250000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2076 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 7 ms 2000 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Incorrect 11 ms 2396 KB declared answer doesn't correspond to the split scheme: declared = 497021612070336120, real = 497009580651102108
4 Halted 0 ms 0 KB -