제출 #501112

#제출 시각아이디문제언어결과실행 시간메모리
501112MazaalaiBigger segments (IZhO19_segments)C++17
0 / 100
1 ms324 KiB
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 5e5 + 5;
int nums[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];
	int ans = 1, cur = 0, pre = nums[1];
	for (int i = 2, l = 2; i <= n; i++) {
		cur += nums[i];
		if (cur >= pre) {
			ans++;
			// cout << pre << ' ' << cur << " -> ";
			while(cur - nums[l] >= pre + nums[l]) {
				pre += nums[l];
				cur -= nums[l++];
			}
			// cout << pre << ' ' << cur << "\n";
			pre = cur;
			cur = 0;
			l = i+1;
		}
		// cout << cur << ' ' << pre << '\n';
	}
	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...