#1197109 (C++23(gcc16)) No.3646 Decrement.

• 問題: No.3646 Decrement.
• ユーザー: C
• 提出日時: 2026-11-05 21:43:20
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 15 ms / 2,000 ms
• コード長: 5,811 bytes
• コンパイル時間: 5,535 ms
• コンパイル使用メモリ: 389,812 KB
• 実行使用メモリ: 9,864 KB
• 最終ジャッジ日時: 2026-11-05 21:43:31
• 合計ジャッジ時間: 9,936 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

サブタスク	配点	結果
サンプル	0 %	AC * 1
小課題1	5 %	AC * 5
小課題2	5 %	AC * 3
小課題3	20 %	AC * 10
小課題4	30 %	AC * 19
小課題5	10 %	AC * 34
小課題6	30 %	AC * 45
合計	100 点

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
// using vvm=vector<vm>;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	/**
	 * O(N)
	 * 
	 * 1. 目的関数の言い換え
	 * A_0=A_{N+1}=0 とし、V(A)=\sum_{i=0}^N |A_i-A_{i+1}| とおく。
	 *
	 * 各高さ h>=1 について、S_h = {i : A_i>=h} を考え
	 * S_h の極大な連続区間を「高さ h の成分」と呼ぶ 、例えば
	 * A = (1,6,9,2,3,1) の時　h = 3 の成分は [2,3]　と　[5,5]　です
	 * 成分の幅とは、その区間に含まれる添字の個数である。
	 *
	 * 非負整数 x,y に対して
	 *
	 * |x-y| = \sum_{h>=1} |[x>=h]-[y>=h]|
	 *
	 * が成り立つ
	 * 
	 * よって
	 * 
	 * V(A) = \sum_{h>=1} \sum_{i=0}^N |[A_i>=h]-[A_{i+1}>=h]|
	 * 
	 * 各高さ h で隣接する列の境界を数えると、
	 * どの成分も左右にちょうど 2 つの境界を持つため、
	 *
	 * V(A)=2 * (全ての高さにわたる成分の総数)
	 *
	 * となる。したがって、成分の個数を最小化すれば良い。
	 *
	 * 2. 元の成分をコスト付きアイテムとして扱う
	 *
	 * 元の配列 A の成分の総数を M とし、その幅を重複込みで
	 *
	 * w_1<=w_2<=...<=w_M
	 *
	 * と並べる。
	 *
	 * 補題：
	 * 
	 * 		V(A) を少なくとも 2q 減らすために必要な操作回数の最小値は
	 *
	 * 		w_1+w_2+...+w_q
	 *
	 * である。
	 *
	 * > 下界
	 *
	 * 最終的な配列 B は 0<=B_i<=A_i としてよい。
	 * （負の値は 0 に置き換えても操作回数・目的関数は増えない）
	 *
	 * 元の各成分は、操作後に完全に消滅するか、
	 * 少なくとも 1 つの成分として残る。
	 * 減算だけでは異なる元の成分が結合することはない。
	 *
	 * よって、成分数を q 個以上減らすには、
	 * 元の成分を少なくとも q 個完全に消す必要がある。
	 *
	 * 幅 w の成分を完全に消すには、その w 個のマスを全て削る必要がある
	 * また、異なる成分のマスは重複しない
	 * したがって、必要な操作回数は少なくとも \sum_{j=1}^q w_j である。
	 *
	 * > 上界（達成可能）
	 *
	 * 元の成分を「幅の昇順、同じ幅なら高さの降順」に並べ、
	 * 先頭 q 個の成分を全て削ることを考える
	 *
	 * ある成分のマスの上にあるマスは、必ずその成分に包含されるより高い位置の成分に属する。
	 * その成分の幅は元の成分以下なので、上の順序では必ず先に選ばれる。
	 *
	 * つまり、選んだマスは各列の上から連続しており、実際に減算で削れる。
	 * さらに、成分を丸ごと削るので、残った成分が分裂することもない。
	 *
	 * よって、ちょうど \sum_{j=1}^q w_j 回の操作で q 個の成分を消せる。
	 *
	 * 以上より、
	 *
	 * 		q=max{t : \sum_{j=1}^t w_j <= K}
	 *   	答え=2(M-q)
	 *
	 * 3. 成分の幅ごとの個数を求める
	 *
	 * cnt[w] を「元の配列における幅 w の成分数」と定義する
	 * 幅は 1<=w<=N なので、cnt が求まれば w=1,2,...,N の順に
	 * 予算 K で購入できる成分を貪欲に選べば良い。
	 *
	 * なお、A_i が大きくても cnt が O(N) で求める。
	 *
	 * > 成分と最左最小位置 j が対応する
	 *
	 * 高さ h の成分 [L,R] に対して、区間 [L,R] 内で
	 * A_j が最小となる添字のうち、最も左のものを j とする。
	 * この成分を j に対応させる。
	 *
	 * 各 j (A_j>0) について
	 *
	 *	p_j = max{i<j : A_i<=A_j}
	 *	r_j = min{i>j : A_i<A_j}
	 *
	 * と定義する。両端の 0 により、これらは必ず存在する。
	 *
	 * このとき、j に対応する成分はちょうど
	 *
	 *	max(A_{p_j},A_{r_j}) < h <= A_j
	 *
	 * を満たす各整数 h に対する
	 *
	 *	[p_j+1,r_j-1]
	 *
	 * である。
	 *
	 * 実際、この高さでは区間内の全ての列が存在し
	 * 両端の列は存在しない。また j が区間内の最左の最小値となる。
	 * 逆に、任意の成分 [L,R] の最左最小位置を j とすると
	 * 必ず p_j=L-1, r_j=R+1 となる。
	 *
	 * したがって、全成分と上記の (j,h) は一対一に対応する。
	 *
	 * 固定した j に対して、これらの成分は全て幅
	 *
	 *	w = r_j - p_j-1
	 *
	 * を持ち、その個数は
	 *
	 *	d = A_j - max(A_{p_j},A_{r_j})
	 *
	 * である。よって、各 j について
	 *
	 *   cnt[r_j-p_j-1] += A_j-max(A_{p_j},A_{r_j})
	 *
	 * とすれば良い
	 * 
	 * p,r などは単調スタックを使えばO(N)で計算できます。
	 */
	int N;
	ll K;
	cin>>N>>K;
	vll A(N+2),cnt(N+1);
	rep(i,1,N+1)cin>>A[i];
	vi stk={0};
	rep(i,1,N+2){
		while(A[stk.back()]>A[i]){
			int j=stk.back();
			stk.pop_back();
			int l=stk.back();
			cnt[i-l-1]+=A[j]-max(A[l],A[i]);
		}
		stk.push_back(i);
	}
	ll ans=0;
	rep(w,1,N+1){
		ll t=min(cnt[w],K/w);
		K-=t*w;
		ans+=2*(cnt[w]-t);
	}
	cout<<ans<<'\n';
}