Submission #1114007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114007		stdfloat	Bigger segments (IZhO19_segments)	C++17	100 / 100	219 ms	34632 KiB

segments

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

using ll = long long;

vector<ll> st;

int fnd(int nd, int l, int r, int x, int y, ll vl) {
	if (r < x || y < l || vl < st[nd]) return -1;

	if (l == r) return l;

	int ch = nd << 1, md = (l + r) >> 1, res = fnd(ch + 1, md + 1, r, x, y, vl);
	return (~res ? res : fnd(ch, l, md, x, y, vl));	
}

ll upd(int nd, int l, int r, int x, ll vl) {
	if (r < x || x < l) return st[nd];

	if (l == r) return st[nd] = vl;

	int ch = nd << 1, md = (l + r) >> 1;
	return st[nd] = min(upd(ch, l, md, x, vl), upd(ch + 1, md + 1, r, x, vl)); 
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;

	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	vector<ll> p(n + 1);
	for (int i = 1; i <= n; i++)
		p[i] = p[i - 1] + a[i];

	st.assign(n << 2, 0);
	vector<ll> dp(n + 1), v(n + 1);
	for (int i = 1; i <= n; i++) {
		int x = fnd(1, 0, n, 0, i - 1, p[i]);

		dp[i] = dp[x] + 1;
		upd(1, 0, n, i, (p[i] << 1) - p[x]);
	}

	cout << dp[n];
}

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