この解説はユーザー解説です。

この問題に、物理的な解釈を与えてみましょう。

まず、数列 \(B\) は数列 \(A\) の隣接項の差を表します(\(B_i=A_{i+1}-A_i\))。このことは、 \(A\) を「座標」を表す列であるとすると、 \(B\) は「速度」を表す列であると言い換えられます。
同様に、数列 \(C\) は数列 \(B\) の隣接項の差を表します(\(C_i=B_{i+1}-B_i\))。このことから、 \(B\) が「速度」を表す列であるので、 \(C\) は「加速度」を表す列であると言い換えられます。

では、解法に入ります。
求めるべきは「座標」が最大となる点です。「座標」が最大となる点の候補として、以下を検討すれば十分です。

• 全ての整数 \(i (1 \le i \le N)\) に対し、 \(A_{y_1+y_2+\dots+y_{i-1}+1}\)
• 全ての整数 \(i (1 \le i \le N)\) に対し、 \(A_{y_1+y_2+\dots+y_i}\)
• 区間 \((A_{y_1+y_2+\dots+y_{i-1}+1},A_{y_1+y_2+\dots+y_{i-1}+2},\dots,A_{y_1+y_2+\dots+y_i})\) の内部で、「速度」が \(0\) 以上から \(0\) 以下に切り替わる点。

このうち上 \(2\) つは順次計算を進めることにより \(O(N)\) で計算できます。
では、一番下のものはどのように求めればよいでしょうか?
全ての整数 \(i (1 \le i \le N)\) に対し、数列 \(A\) の区間 \((A_{y_1+y_2+\dots+y_{i-1}+1},A_{y_1+y_2+\dots+y_{i-1}+2},\dots,A_{y_1+y_2+\dots+y_i})\) は「加速度が一定」となります。なので、「その区間の先頭での速度」を「その区間における加速度」を割って \(-1\) を掛けることによって、速度が \(0\) 以上から \(0\) 以下に切り替わる点がどこになるかを求めることができます。
この解法の計算量は \(O(N)\) です。文章では雰囲気だけを説明したので、詳しくは実装例を参照してください。

実装例(C++):

#include<bits/stdc++.h>
 
using namespace std;
 
long long sum(long long l,long long r,long long cnt){
  long long res=(l+r);
  res*=cnt;
  return res/2;
}
 
int main(){
  int t;
  cin >> t;
  for(int cs=0;cs<t;cs++){
    long long n,m;;
    cin >> n >> m;
    vector<long long> a(n),y(n);
    for(int i=0;i<n;i++){cin >> a[i] >> y[i];}

    long long cv=0,cx=0,res=-8e18;
    for(int i=0;i<n;i++){
      long long vl=cv+a[i];
      long long vr=cv+a[i]*y[i];
      if(a[i]!=0){
        if(vl>=0 && vr<=0){
          long long pt=(-cv)/a[i];
          res=max(res,cx+sum(vl,cv+a[i]*pt,pt));
        }
      }
      cv=vr;
      res=max(res,cx+vl);
      cx+=sum(vl,vr,y[i]);
      res=max(res,cx);
    }
    cout << res << '\n';
  }
}