bzoj3549.cc

#include #include #include

using namespace std;

const int maxn = 100009;

int n, a[maxn], sm[maxn], ans; int f[maxn], g[maxn], q[maxn], hd, tl;

int main() { #ifndef ONLINE_JUDGE //freopen(".in", “r”, stdin); #endif

scanf("%d", &n);
sm[0] = 0;
for (int i = 0; i < n; ++ i) {
	scanf("%d", a + i);
	sm[i + 1] = sm[i] + a[i];
}
hd = 0, tl = 1, q[hd] = n;
f[n] = 0, g[n] = 0;
for (int i = n - 1; i >= 0; -- i) {
	while (hd + 1 < tl && sm[q[hd + 1]] - f[q[hd + 1]] >= sm[i])
		++ hd;
	f[i] = sm[q[hd]] - sm[i];
	g[i] = g[q[hd]] + 1;
	while (hd < tl && sm[i] - f[i] >= sm[q[tl - 1]] - f[q[tl - 1]])
		-- tl;
	q[tl ++] = i;
}
printf("%d\n", g[0]);

}