CODE FESTIVAL 2018 Final : E - Tough Journey

わかるとすんなり。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_e

問題

0～Nの名前が付いた(N+1)個の町が並んでいる。
0番からN番に順に移動するが、1つ移動するごとにペットボトルの水を1本分消費する。
同時に持てるペットボトルの最大値はK本分で、初期状態値はいずれも空である。
町iでは料金A[i]で1本分水を補充できる(何本分も補充することもできる)

適切な補充をした場合、かかる料金の最小値はいくらか。

解法

必要な時に適宜水を買い足すことを考える。
町i→(i+1)に移動する場合、町(i-K+1)～町(i)のいずれかで水を1本分補充したことにすると考えると、スライド最小値でO(N)、multisetやpriority_queueを使ってもO(NlogN)で解ける。

町(i-K)以前の町で水を買うことは考えられない。
なぜならそこから町iまでにK本水を消費するため、結局もっと後に買うタイミングを設けなければならないためである。

int N,K;
int A[101010];
set<pair<int,int>> S;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll ret=0;
	int ma=-1;
	FOR(i,N) {
		cin>>A[i];
		S.insert({A[i],i});
		if(i>=K) S.erase({A[i-K],i-K});
		x=S.begin()->second;
		ret+=A[x];
	}
	cout<<ret<<endl;
}

まとめ

これは実装軽いし500ptでもよさそう。