betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング お題箱より。 Problem - D - Codeforces 問題概要 ※解説の都合上、0-indexedと半開区間での記述に書き換えます。 非負とは限らない整数列 と、正整数 が与えられる。 この数列の連続部分列 について、そのスコアを と定める。ただし長さ0の連続部分列のスコアは0とする。 スコアの最大値を求めよ。 制約 解法 連続部分列の和（区間和）は、累積和を取ってその差を考えるのが鉄則です。以下のように要素の「区切り位置」と累積和を対応させ、区間を半開区間として捉えると、累積和の差と区間和がキレイに対応します。 もしスコア計算に の項がなければ、この問題は以下のように解けます。 累… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F11%2F23%2F142302" title="Educational Codeforces Round 69 D. Yet Another Subarray Problem - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20a_%7B0%7D%2C%20...%2C%20a_%7Bn-1%7D Hatena Blog https://hatena.blog 2019-11-23 14:23:02 rich https://betrue12.hateblo.jp/entry/2019/11/23/142302 1.0 100%