Submission #760854

#	Time	Username	Problem	Language	Result	Execution time	Memory
760854		NK_	Bigger segments (IZhO19_segments)	C++17	0 / 100	1575 ms	320 KiB

segments

// 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((nxt - 2 * A[l]) > prv) {
			l++;
			nxt -= 2 * A[l];
			prv += 2 * A[l];
		}
		prv = nxt; l = r + 1;
	}

	cout << ans << nl;

    return 0;
}

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