Submission #501125

#	Time	Username	Problem	Language	Result	Execution time	Memory
501125		Mazaalai	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	204 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], 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;
	ll ans = 1;
	int l = 1, r = n;
	// while(l <= r) {
		// int mid = (l+r)>>1;
	for (int mid = n; mid > 0; mid--) {
		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';
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:21:6: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   21 |  int l = 1, r = n;
      |      ^
segments.cpp:21:13: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   21 |  int l = 1, r = n;
      |             ^

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