Submission #1172039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172039		coolboy19521	Bigger segments (IZhO19_segments)	C++20	100 / 100	134 ms	14236 KiB

segments

#include "bits/stdc++.h"

#define mxN 500005

using namespace std;

long long pr[mxN];
int a[mxN];

int main(){
	int N;
	cin >> N;
	
	for (int i = 1; i <= N; i ++)
		cin >> a[i];

	priority_queue<tuple<long long,int,int>> pq;
	
	long long aux = 0;
	int ans = 0;
    pair<int,int> bs = {0, 0};
	
	for (int i = 1; i <= N; i ++){
		pr[i] = aux += a[i];

		for(;;){
			if (pq.empty()) break;
			auto [sm, cn, ix] = pq.top();
			
			sm = -sm;
			
			if (sm - aux <= 0){
                bs = max(bs, {cn, ix});
				pq.pop();
			}
			
			else break;
		}
		
		auto [cn, ix] = bs;
        ans = cn + 1;
		
		pq.emplace(pr[ix] - pr[i] - aux, cn + 1, i);
	}
	
	cout << ans << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27