Submission #873801

#	Time	Username	Problem	Language	Result	Execution time	Memory
873801		qthang2k11	Bigger segments (IZhO19_segments)	C++17	100 / 100	73 ms	13080 KiB

segments

// [+]
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 5e5 + 5;

ll a[N];
int n;

int dp[N], ans[N];

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], a[i] += a[i - 1];
	
	for (int i = 1; i <= n; i++) {
		dp[i] = max(dp[i - 1], dp[i]);
		ans[i] = ans[dp[i]] + 1;
		
		int pos = lower_bound(a + 1, a + n + 1, 2 * a[i] - a[dp[i]]) - a;
		dp[pos] = max(dp[pos], i);
	}
	
	cout << ans[n];
	
	return 0;
}

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