Submission #501124

#TimeUsernameProblemLanguageResultExecution timeMemory
501124MazaalaiBigger segments (IZhO19_segments)C++17
0 / 100
0 ms332 KiB
#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;
		bool 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) {
			// cout << mid << ": " << cur << '\n';
			ans = max(ans, cur);
			l = mid+1;
		} else {
			r = mid-1;
		}
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...