Submission #501466

#	Time	Username	Problem	Language	Result	Execution time	Memory
501466		Mazaalai	Bigger segments (IZhO19_segments)	C++17	100 / 100	82 ms	10128 KiB

segments

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
const int N = 5e5 + 5;
long long pre[N], ans;
int n, m, nums[N], dp[N], par[N], id;
signed main () {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	m = n+1;
	for (int i = 1; i < m; i++) cin >> nums[i];
	for (int i = 1; i < m; i++) pre[i] += pre[i-1] + nums[i];
	for (int i = 1; i < m; i++) {
		int&p = par[i]; p = max(p, par[i-1]);
		dp[i] = dp[p]+1;
		id = lower_bound(pre, pre+m, pre[i]*2-pre[p])-pre;
		par[id] = max(par[id], i);
	}
	ans = dp[n];
	cout << ans << '\n';
}

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