Submission #501467

#	Time	Username	Problem	Language	Result	Execution time	Memory
501467		Mazaalai	Bigger segments (IZhO19_segments)	C++17	100 / 100	87 ms	10072 KiB

segments

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops, O3")
#pragma GCC target("avx2")
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';
}

Compilation message (stderr)

segments.cpp:2:40: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("unroll-loops, O3")
      |                                        ^
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
    3 | #pragma GCC target("avx2")
      |                          ^
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
segments.cpp:3:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
/v

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