Codeforces Round #117 (Div. 2) C : Optimal Sum

問題概要

長さN(<10^5)の数列Xがある。数列Xのうち高々k(

解法

全部符号をひっくり返して2回考えるようにすれば絶対値最大化は単なる最大化で解けるので以下それで考える。
幅Lの窓をスライドさせて考える。窓の中にある負の数字を覚えておいて、絶対値の大きい方からk個の和をとって素の部分和に2倍して加えると現在の窓に対応する最大値がとれる。絶対値の大きい方からk個の和は、平衡二分探索木を使えば求められる。
平衡二分探索木を使わなくてもsetにサイズがk個以下になるように突っ込んで、k個を越えたときは溢れたのをバッファ代わりのheapに避難させることで代用できる。

acceptされたコード

#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = (int)(1e5);
const int64 INF = 1LL<<60;

int N, L, K;
int64 as[MAX_N];

void init(){
	scanf("%d%d", &N, &L);
	for(int i=0; i<N; ++i){
		scanf("%lld\n", as+i);
		//scanf("%I64d\n", as+i);
	}
	scanf("%d", &K);
}

int64 solve(){
	set< pair<int64, int> > negas;
	//priority_queue< pair<int64, int>, vector< pair<int64, int> >, greater< pair<int64, int> > > que;
	priority_queue< pair<int64, int> > que;

	int64 ans = -INF, cur = 0, ns = 0;
	for(int i=0; i<L; ++i){
		cur += as[i];
		if(as[i] < 0){
			negas.insert(make_pair(-as[i], i));
			ns += -as[i];
			if((int)negas.size() > K){
				que.push( *negas.begin() );
				ns -= negas.begin()->first;
				negas.erase(negas.begin());
			}
		}
	}

	ans = max(ans, cur + 2 * ns);

	for(int i=L; i < N; ++i){
		cur -= as[i-L];
		if(as[i-L] < 0){
			if(negas.find(make_pair(-as[i-L], i-L))!=negas.end()){
				negas.erase(make_pair(-as[i-L], i-L));
				ns -= -as[i-L];
			}
			for(;!que.empty() && (int)negas.size() < K;){
				if(que.top().second <= i - L){
					que.pop();
					continue;
				}
				else{
					ns += que.top().first;
					negas.insert( que.top() );
					que.pop();
				}
			}
		}

		cur += as[i];
		if(as[i] < 0){
			negas.insert(make_pair(-as[i], i));
			ns += -as[i];
			if((int)negas.size() > K){
				que.push( *negas.begin() );
				ns -= negas.begin()->first;
				negas.erase(negas.begin());
			}
		}
		ans = max(ans, cur + 2 * ns);
	}

	return ans;
}

int main(){
	init();
	int64 ans = solve();
	for(int i=0; i<N; ++i){
		as[i] = -as[i];
	}
	ans = max(ans, solve());
	cout << ans << endl;

	return 0;
}