3017.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3017  User Id:fzk 
Memory:4500K  Time:978MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <string.h>
#include <memory.h>
#include <queue>
using namespace std;

typedef pair<__int64, int> type;

priority_queue< type, vector<type> > q;
deque< pair<int,int> > dq;

__int64 sum[100010], ans[100000], res[100010];
int a[100010], b[100010], pos[100010];

int main( ) {
	int i, n, h, k;
	type t;
	__int64 m;
	scanf( "%d%I64d", &n, &m );
	
	for( i=1; i<=n; i++ )
		scanf( "%d", a+i );
	for( i=1; i<=n; i++ )
		sum[i] = sum[i-1] + a[i];
	
	h = 1;
	b[0] = 1000001; pos[0] = 0;
	k = 1;

	for( i=1; i<=n; i++ ) {
		if( a[i] < b[h-1] ) {
			b[h] = a[i];
			pos[h] = i;
		}
		else {
			while( a[i] >= b[h-1] ) {
				h--;
				res[ pos[h] ] = 1;
			}
			b[h] = a[i];
			pos[h] = pos[h];
		}
		h++;
		
		res[pos[h-1]] = -a[i]-ans[pos[h-1]-1];
		q.push( make_pair( -a[i]-ans[pos[h-1]-1], pos[h-1] ) );
		while( sum[i] - sum[pos[k]-1] > m && pos[k] <= i ) {
			//printf( "df\n" );
			pos[k]++;
			res[pos[k]-1] = 1;
			if( k < h-1 && pos[k] == pos[k+1] ) {
				b[k] = 1000001;
				k++;
			}
		}
		if( pos[k] > i )
			break;
		
		res[pos[k]] = -b[k]-ans[pos[k]-1];
		q.push( make_pair( -b[k]-ans[pos[k]-1], pos[k] ) );
		
		while( sum[ (t=q.top()).second-1 ] < sum[i]-m || t.first != res[t.second] )
			q.pop( );
		ans[i] = -q.top().first;
	}
	
	if( i <= n )
		printf( "-1\n" );
	else
		printf( "%I64d\n", ans[n] );
	return 0;
}