比赛 20160415 评测结果 AAAAATTTTT
题目名称 烤鸡翅 最终得分 50
用户昵称 KZNS 运行时间 5.015 s
代码语言 C++ 内存使用 2.46 MiB
提交时间 2016-04-15 09:25:10
显示代码纯文本
//KZNS
#include <fstream>
#include <map>
using namespace std;
//
ifstream fin ("wing.in");
ofstream fout ("wing.out");
const int Nmax = 250003;
//
int X[Nmax], Y[Nmax];
int N;
map<int, long long> mp;
map<int, long long>::iterator mpi;
bool ex[Nmax] = {0};
//
int main() {
	fin >> N;
	ex[0] = true;
	for (int i = 0; i < N; i++)
		fin >> X[i];
	for (int i = 0; i < N; i++)
		fin >> Y[i];
	mp[0] = 0;
	for (int i = 0; i < N; i++) {
		for (mpi = mp.begin(); mpi!=mp.end(); mpi++) {
			mpi->second += X[i];
		}
		for (mpi--; mpi!=mp.begin(); mpi--) {
			if (ex[mpi->first+1]) {
				mp[mpi->first+1] = max(mp[mpi->first + 1], mpi->second - Y[i]);
			}
			else {
				if (mpi->second - Y[i] >=0) {
					mp[mpi->first+1] = mpi->second - Y[i];
					ex[mpi->first+1] = true;
				}
			}
		}
		if (ex[mpi->first+1]) {
			mp[mpi->first+1] = max(mp[mpi->first + 1], mpi->second - Y[i]);
		}
		else {
			if (mpi->second - Y[i] >=0) {
				mp[mpi->first+1] = mpi->second - Y[i];
				ex[mpi->first+1] = true;
			}
		}
	}
	mpi = mp.end();
	mpi--;
	fout << mpi->first << endl;
	return 0;
}
//UBWH