Submission #1101312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101312		Muhammet	Bigger segments (IZhO19_segments)	C++17	100 / 100	176 ms	45388 KiB

segments

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long

int main(){
	int n;
	cin >> n;
	vector <ll> a(n+1), p(n+1, 0), dp(n+1,0);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i-1] + a[i];
	}
	multiset <pair<ll,int>> s;
	ll mx = 0, ind = 0, sm = 0;
	dp[1] = 1;
	s.insert({-a[1],1});
	for(int i = 2; i <= n; i++){
		sm += a[i];
		while(!s.empty()){
			auto [x,y] = *s.rbegin();
			if((x + sm) >= 0){
				s.erase(--s.end());
				if((dp[y] > mx) or (dp[y] >= mx and ind < y)) ind = y;
				mx = max(mx,dp[y]);
			}
			else break;
		}
		dp[i] = mx+1;
		ll k = (p[i]-p[ind]);
		k += sm;
		k *= (-1);
		s.insert({k,i});
	}
	cout << dp[n];
}

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