只要心地善，$n^2$ 过十万。

但凡出一个油价正好完全下降的数据都能卡掉我这个暴力分治，但是 CCF 不肯。（你可能会说我这个不是 $n^2$，的确，我这个是 $\mathcal O(\sum\limits_{i=1}^n i)$）

ll solve(ll l, ll r) {
  if (l >= r) {
    return 0;
  }
  ll m = l;
  for (ll i = l; i < r; i++) {
    if (a[i] < a[m]) {
      m = i;
    }
  }
  ll t = s[r] - s[m];
  ll ans = solve(l, m);
  double len = t - res;
  ll buy = ceil(len / d);
  ans += a[m] * buy;
  res = (res + buy * d) - t;
  return ans;
}