比赛 20160412 评测结果 WWAWWAAAWAWWAWAAWAAA
题目名称 非负的部分和 最终得分 55
用户昵称 KZNS 运行时间 0.549 s
代码语言 C++ 内存使用 11.75 MiB
提交时间 2016-04-12 11:18:08
显示代码纯文本
//KZNS
#include <fstream>
using namespace std;
//
ifstream fin ("sumc.in");
ofstream fout ("sumc.out");
const int Nmax = 1000003;
//
int N;
int ls[Nmax] = {0};
int la[Nmax], nt[Nmax];
int fs = 0;
int n;
//
int main() {
	fin >> N;
	n = N;
	for (int i = 0; i < N; i++) {
		fin >> ls[i];
		nt[i] = (i-1+N)%N;
		la[i] = (i+1)%N;
		if (ls[i] < 0)
			fs++;
	}
	int i = 0;
	while (!(n==1||fs==0)) {
		if (ls[la[i]] < 0) {
			if (ls[i] < 0) {
				fs--;
				n--;
				ls[i] += ls[la[i]];
				nt[la[i]] = nt[i];
				la[i] = la[la[i]];
				i = nt[i];
			}
			else {
				n--;
				ls[i] += ls[la[i]];
				if (ls[i] >= 0)
					fs--;
				la[i] = la[la[i]];
				nt[la[i]] = i;
				i = nt[i];
			}
		}
		else {
			i = nt[i];
		}
	}
	fout << n;
	return 0;
}
//UBWH