ABC017 C ハイスコア

C

Submission #2418387 - AtCoder Beginner Contest 017

問題概要

N(<100000)個の区間とスコアが与えられる。区間を選ぶとその区間に対応するスコアを得ることができる。選んだ区間の和集合が全体を覆ってはいけない時の最大スコアを求めよ。

取った方針

少なくとも一つの整数を含まない->含まない整数を一つ選び、その整数を含まないことによるスコア減少を最小にすればよい。
たくさんの区間と重みが与えられて、区間内の要素における重みの和を求めたいときはimos法が使えることが知られている。imos さえいればいい。
今回なら、 長さMの配列arrayを用意して、すべての区間についてarray[l_i]+=s_i,array[r_i+1]-=s_iとしておき、arrayの累積和をとれば各値を捨てることで減るスコアが求められるので、arrayの最小値をスコアの総和から引けばよい。

正しい方針

同上(imos法)

得られた知見

・imos法

解くのに必要な要素

・要素を全部使ってはいけない(今回の場合選んだ区間が全体をカバーしてはいけない)->少なくとも一つ捨てればよい
・この言いかえはよく見る。
・imos法

周辺調査によって得られた知見

特になし