Submission #1343682

#TimeUsernameProblemLanguageResultExecution timeMemory
1343682ppmn_6Bigger segments (IZhO19_segments)C++20
0 / 100
0 ms344 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	int en = 1, cnt = 1;
	ll val = a[1];
	while (true) {
		if (a[n] < a[en] + val) {
			break;
		}
		int new_en = en + 1;
		while (a[new_en] < a[en] + val) {
			new_en++;
		}
		ll new_val = a[new_en] - a[en];
		while (new_val - a[en + 1] + a[en] >= val + a[en + 1] - a[en]) {
			new_val -= a[en + 1] - a[en];
			val += a[en + 1] - a[en];
			en++;
		}
		en = new_en;
		val = new_val;
		cnt++;
	}
	cout << cnt;
	
	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...