1. 区間の限定と二分木構造の形成

まず、高橋君の魔法の使用順序は体力変化や魔力の使用量に影響しないため、各区間を何度選んだかのみが重要となります。さらに、魔法を使用するとき、消費する魔力を変化させない限り、なるべく広い範囲を選んで損になることはありません。すなわち、\(1\leq r\leq N\) をみたす \((l,r)\) のうち、

• \(l\leq j\leq r\) をみたす任意の \(j\) に対して \(B_{l-1}>B_j\) または \(l=1\)
• \(l\leq j\leq r\) をみたす任意の \(j\) に対して \(B_{r+1}>B_j\) または \(r=N\)

の \(2\) 条件をともにみたすもののみを使用するとして良いです。 そのような区間は、その区間において、 \(B_i\) が最大となる \(i\) (複数ある場合はそのうち最大の \(i\), 以下このような \(i\) をとる時も同様 )と対応させることで、次のように \(l_i,r_i\) を定義したときの \((l_i,r_i)\) として書くことができます。

• \(j<i\)かつ\(B_j>B_i\)をみたす最大の \(j\) に対して, \(l_i=j+1\), そのような \(j\) が存在しないならば \(l_i=1\)
• \(j>i\)かつ\(B_j\geq B_i\)をみたす最小の \(j\) に対して, \(r_i=j-1\), そのような \(j\) が存在しないならば \(r_i=N\)

よって、これらの区間に対してのみ操作を行う場合を考えて良いです。(余計な区間が含まれている場合がありますが、使用しなければ問題ありません。)

ここで、これらの区間について、 \(B_1,\ldots,B_N\) の中で \(B_i\) が最大であるような頂点 \(i\) を根とした、次のような二分木構造を考える事ができます。(根 \(R\) について \((l_R,r_R)=(1,N)\) であることに注意)

• 頂点 \(i\) は、\(l_i< i\)ならば、\(l_i\leq j\leq i-1\) をみたす \(j\) のうち、\(B_j\) が最大のものを(直接の)左の子として持つ。そうでないならば左の子を持たない。
• 頂点 \(i\) は、\(i<r_i\)ならば、\(i+1\leq j\leq r_i\) をみたす \(j\) のうち、\(B_j\) が最大のものを(直接の)右の子として持つ。そうでないならば右の子を持たない。

このとき、頂点 \(i\) について、

• 頂点 \(i\) が左の子 \(x\) を持つならば \((l_x,r_x)=(l_i,i-1)\)
• 頂点 \(i\) が右の子 \(y\) を持つならば \((l_y,r_y)=(i+1,r_i)\)

が成り立ちます。

2. DPの設定と更新

\(dp[i][j]\)で, \(N'=r_i-l_i+1\), \(A'=(A_{l_i}-j,A_{l_i+1}-j,\ldots,A_{r_i}-j)\), \(B'=(B_{l_i},B_{l_i+1}, \ldots,B_{r_i})\) とした時の問題に対する答え（使用する魔力の総和の最小値）を表すとします。
求めたいものは、\(dp[R][0]\) となります。

これを\(i\) について、 \(B_i\) の値が小さい順に求めていくことを考えます。
また、同時に、この時、\(dp[i][j]\) が \(j\) について単調減少であり、 \((dp[i][j]-dp[i][j+1]\)) も単調減少である事を帰納法で示します。

まず、\(l_i=r_i=i\) であるとき、

\[ dp[i][j]= \begin{cases} (A_i-j)B_i & (0\leq j\leq A_i) \\ 0 & (A_i\leq j) \end{cases} \]

となります。この時、仮定もみたしています。

そうでない時、頂点 \(i\) が左右の子 \(x,y\) を持つとします。 ここで、二分木や区間の定義から、 \(B_x\leq B_i\), \(B_y<B_i\) であるため、\(dp[x][j],dp[y][j]\) がすでに求まっていることに注意します。 また、いずれかの子が存在しない場合は以下の方針で \(dp[x][j](またはdp[y][j])\equiv 0\) とすれば良いです。

高橋君は座標 \(i\) のモンスターの体力を削る必要がある事から, このとき,

\[ dp[i][j]=\displaystyle\min_{\max(A_i-j,0)\leq k} \{kB_i+ dp[x][j+k]+dp[y][j+k]\} \]

となります。\(k\) を \(1\) 増加させた時の、 \(kB_i+ dp[x][j+k]+dp[y][j+k]\) の変位は、 \(B_i-(dp[x][j+k]-dp[x][j+k+1])-(dp[y][j+k]-dp[y][j+k+1])\) であり、これは帰納法の仮定より、単調増加です。 よって、ある \(j_0\geq A_i\) において、

• \(j_0=A_i\) または \(B_i-(dp[x][j_0-1]-dp[x][j_0])-(dp[y][j_0-1]-dp[y][j_0])\leq 0\)
• \(B_i-(dp[x][j_0]-dp[x][j_0+1])-(dp[y][j_0]-dp[y][j_0+1])> 0\)

の\(2\)つをみたします。まず、この時、\(j\leq j_0\) ならば、

\[ dp[i][j]=(j_0-j)B_i+ dp[x][j_0]+dp[y][j_0] \]

となります。そうでない時、すなわち \(j\geq j_0\) の時、\(k\)を\(0\) から増加させる利点がないため、

\[ dp[i][j]=dp[x][j]+dp[y][j] \]

となります。帰納法の仮定から、\(dp[i][j]\)は単調減少であり、 \(B_i>(dp[x][j_0]+dp[y][j_0])-(dp[x][j_0+1]+dp[y][j_0+1])\) から \(dp[i][j]-dp[i][j+1]\)も単調減少となります。

よって、帰納的に \(dp[i][j]\) の値を求める方法が分かりました。

3.折れ線である事を利用した高速化

さて、この\(dp[i][j]\) ですが、\(j\) の添字の範囲を考えたとき、\(j\geq \max(A_{l_i},\ldots,A_{r_i})\) ならば \(dp[i][j]=0\) となりますが、逆に言えば その付近、つまり最大で \(j\simeq 10^9\) あたりまで計算しなくてはならず、間に合いません。そこで、先ほどのものを見るとほとんどの点で\(dp[i][j]\)が等間隔に減少している事がわかり、\(dp[i][j]-dp[i][j+1]\) が変化している点はその頂点を根とする部分木の頂点数程度しかありません。よって、\(dp[i][j]\) の値を陽に持つ代わりに、 \(dp[i][0]\), \(dp[i][0]-dp[i][1]\) の値および

\[ S_i=\{(j,(dp[i][j-1]-dp[i][j])-(dp[i][j]-dp[i][j+1]))| (dp[i][j-1]-dp[i][j])\neq (dp[i][j]-dp[i][j+1]) なる j\} \]

を持つ事を考えます。この時、更新は \(2\) つの段階からなります。

1. \(dp[x][j]\)と \(dp[y][j]\) の併合(\(dp'\),\(S'_i\) はこれらの値や集合が計算途中であり、最終的なものとは異なることを表す)

   • \(dp'[i][0]=dp[x][0]+dp[y][0]\)
   • \(dp'[i][0]-dp'[i][1]=(dp[x][0]-dp[x][1])+(dp[y][0]-dp[y][1])\)
   • \(S'_i=S_x\bigcup S_y\)

2. \((A_i,B_i)\)の情報の追加

   • 1. の情報を用いて, \(dp'[i][j]\) を前から順に計算していき、 \(j\geq A_i\) かつ \(B_i>dp'[i][j]-dp'[i][j+1](=(dp[x][j]+dp[y][j])-(dp[x][j+1]+dp[y][j+1]))\)なる最小の \(j=j_0\) を見つける。
   • \(dp[i][0]=dp'[i][j_0]+j_0B_i\)
   • \(dp[i][0]-dp[i][1]=B_i\)
   • \(j\leq j_0\)なる \((j,x)\in S'_i\) は集合から取り除く
   • \((j_0,B_i-(dp'[i][j_0]-dp'[i][j_0+1]))\) を \(S'\) に加える。

このようにして更新していくことができます。

最後に、計算量についてです。 \(S_x\) と \(S_y\) の併合は、\(S_x\), \(S_y\) のうち大きい方に併合してそれを新たに \(S_i\) とすることによって、各 \(S_i\) への挿入が合計で \(O(N\log N)\) 回となります。また、2.で\(dp'[i][j]\)を \(j=j_0\) まで計算する部分についても、一度参照された \(S_i\) の要素は高々\(1\) つを除いて削除される事から、こちらも全体で \(O(N\log N)\) 回程度の計算で終わります。\(S_i\) を 順序付き多重集合や優先度付きキューなどで管理する事によって、挿入・参照・削除が \(O(\log N)\) で行えるため、dpの更新にかかる計算量は全体で \(O(N\log^2 N)\)となります。なお、他の \(l_i\) や \(r_i\) を求めるパートは順序集合等で \(O(N\log N)\)で行えるため、問題全体で \(O(N\log^2 N)\) であり、十分高速にこの問題を解く事ができました。

c++ による実装例 :

#include <bits/stdc++.h>
using namespace std;

#define N 100010
#define INF (long long)4e+18

int main() {
  int n;
  long long a[N];
  long long b[N];
  int c[N][2];
  int x,y;
  set<int>st;
  set<int>::iterator itr;
	vector<pair<long long,int> >ord;
 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
    cin>>b[i];
    ord.push_back({b[i],i});
  }
  b[0]=INF;
  b[n+1]=INF;

  sort(ord.begin(),ord.end());
  for(int i=1;i<=n;i++)for(int j=0;j<2;j++)c[i][j]=-1;
  st.insert(0);
  st.insert(n+1);
  for(int i=n-1;i>=0;i--){
    itr=st.upper_bound(ord[i].second);
    y=(*itr);
    itr--;
    x=(*itr);
    if(b[x]<=b[y])c[x][1]=ord[i].second;
    else c[y][0]=ord[i].second;
    st.insert(ord[i].second);
  }

  int k;
  int p[N];
  long long dp0[N];
  long long d[N];
  long long cur;
  multiset<pair<long long,long long> >mst[N];
  multiset<pair<long long,long long> >::iterator mstitr;
  pair<long long,long long> z;
  
	for(int i=1;i<=n;i++)p[i]=i;
 
	for(int i=0;i<n;i++){
		k=ord[i].second;
		if((c[k][0]==-1)&&(c[k][1]==-1)){
			dp0[k]=a[k]*b[k];
			d[k]=b[k];
			mst[k].insert({a[k],b[k]});
			continue;
		}
		if(c[k][0]==-1)p[k]=p[c[k][1]];
		else if(c[k][1]==-1)p[k]=p[c[k][0]];
    else if(mst[p[c[k][0]]].size()<mst[p[c[k][1]]].size()){
      p[k]=p[c[k][1]];
      dp0[p[k]]+=dp0[p[c[k][0]]];
      d[p[k]]+=d[p[c[k][0]]];      
      mst[p[k]].merge( mst[p[c[k][0]]]);
    }
    else{
      p[k]=p[c[k][0]];
      dp0[p[k]]+=dp0[p[c[k][1]]];
      d[p[k]]+=d[p[c[k][1]]];   
      mst[p[k]].merge( mst[p[c[k][1]]]);
    }

		cur=0;
		while(!mst[p[k]].empty()){
      mstitr=mst[p[k]].begin();
			z=(*mstitr);
			if((z.first<=a[k])||(d[p[k]]>=b[k])){
				dp0[p[k]]-=(z.first-cur)*d[p[k]];
				d[p[k]]-=z.second;
				cur=z.first;
				mst[p[k]].erase(mstitr);
			}
			else break;
		}
		if(cur<a[k]){
			dp0[p[k]]-=(a[k]-cur)*d[p[k]];
			cur=a[k];
		}
      	mst[p[k]].insert({cur,b[k]-d[p[k]]});
		dp0[p[k]]+=(cur*b[k]);
		d[p[k]]=b[k];
	}
	cout<<dp0[p[ord[n-1].second]]<<endl;
 
	return 0;
}

(追記 : なお、この問題には\(O(N\log N)\)解法も存在します。)