Submission #501123

#	Time	Username	Problem	Language	Result	Execution time	Memory
501123		Mazaalai	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	332 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector <int>;
using VLL = vector <ll>;
int n, m;
const int N = 5e5 + 5;
const ll INF = 1e17;
ll nums[N], pre[N], dp[N];
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	for (int i = 1; i <= n; i++) dp[i] = INF;
	nums[n+1] = INF;
	for (int i = 1; i <= n+1; i++) pre[i] = pre[i-1] + nums[i];
	ll ans = 1;
	int l = 1, r = n;
	while(l <= r) {
		int mid = (l+r)>>1;
		ll suf = 0, cur = 1, curSum = 0, done = 1;
		for (int i = n; i >= mid; i--) suf += nums[i];
		for (int i = mid-1; i > 0; i--) {
			if (nums[i] > suf) done = 0;
			if (curSum + nums[i] > suf) {
				cur++;
				suf = curSum;
				curSum = 0;
			}
			curSum += nums[i];
		}
		cur++;
		if (done) {
			ans = max(ans, cur);
			l = mid+1;
		} else {
			r = mid-1;
		}
	}
	cout << ans << '\n';
}

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