D. Extreme Subtraction 単調増加と単調減少に分離

• Quiz
  • https://codeforces.com/contest/1443/problem/D
• AC
  • https://codeforces.com/contest/1443/submission/97668720
• 解説
  • 配列Vを単調減少なA, 単調増加なBに分離できるかという問題になる
  • editorialのように式変形すれば貪欲に前から決めていける
• その他
  • この分離は別の問題の1ステップとして出てきそうなのでメモ

string solve(){
  ll N;
  cin>>N;
  VI V(N);
  rep(i, N){
    cin >> V[i];
  }
  VI A(N); // decreasing
  VI B(N); // increasing
  A[0]=V[0];
  FOR(i,1,N){
    A[i] = min(A[i-1], V[i]-B[i-1]);
    B[i] = V[i]-A[i];
    if(B[i]<B[i-1]) return "NO";
    if(A[i]<0 or B[i]<0) return "NO";
  }
  return "YES";
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    while(N--){
      auto ans = solve();
      p(ans);
    }
    
    return 0;
}

memo image