oj.uz

Submission #582081

# Submission time Handle Problem Language Result Execution time Memory
582081 2022-06-23T11:05:47 Z l_reho Split the sequence (APIO14_sequence) C++14
0 / 100
 9 ms 1880 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;
		
		if(I.mid - I.start != 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;
		if(I.end - (I.mid+1) != 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+1;
					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 0 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 0 ms 212 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 212 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 0 ms 212 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 0 ms 212 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Incorrect 1 ms 212 KB contestant didn't find the optimal answer: 1019625813 < 1019625819
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 1 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 9 ms 1880 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 6 ms 1876 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Incorrect 8 ms 1876 KB contestant didn't find the optimal answer: 497009314607795353 < 497313449256899208
4 Halted 0 ms 0 KB -