Submission #1101307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101307		Muhammet	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	348 KiB

segments

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

int main(){
	int n;
	cin >> n;
	vector <long long> 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((sm + x) >= 0){
				s.erase(--s.end());
				if(dp[y] >= mx){
					ind = y;
				}
				mx = max(mx,dp[y]);
			}
			else break;
		}
		dp[i] = mx+1;
		ll k = (p[i]-p[ind]);
		k *= (-1);
		s.insert({k-sm,i});
	}
	cout << dp[n];
}

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