Submission #760855

#TimeUsernameProblemLanguageResultExecution timeMemory
760855NK_Bigger segments (IZhO19_segments)C++17
0 / 100
1576 ms212 KiB
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair

template<class T> using V = vector<T>;
using ll = long long;
using pl = pair<ll, int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	V<int> A(N); for(auto& x : A) cin >> x;

	V<ll> P(N); for(int i = 0; i < N; i++) {
		P[i] = A[i];
		if (i) P[i] += P[i-1];
	}

	set<pl> S; for(int i = 1; i < N; i++) {
		S.insert(mp(P[i], i));
	}

	int l = 1; ll prv = A[0]; int ans = 1;
	while(l < N) {
		auto it = S.lower_bound(mp(prv + P[l - 1], -1));
		if (it == end(S)) break;
		int r = (*it).s;
		// cout << l << " " << r << nl;
		ans++; ll nxt = P[r] - P[l - 1];

		while(l < r && (nxt - 2 * A[l]) >= prv) {
			l++;
			nxt -= 2 * A[l];
			prv += 2 * A[l];
		}
		prv = nxt; l = r + 1;
	}

	cout << ans << nl;

    return 0;
}


#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...