平均評価が星 \(3\) 以上であるとはどのようなことでしょうか。立式してみましょう。
もともと \(q\) 件のレビューがついており、星の合計が \(p\) 個であったとしましょう。
更に、星 \(i\) のレビューを \(B_i\) 件追加したとしましょう。
このとき、平均評価が星 \(3\) 以上であるということを以下のように立式できます。
\(\displaystyle \frac{p+B_1+2B_2+3B_3+4B_4+5B_5}{q+B_1+B_2+B_3+B_4+B_5} \ge 3\)
ここから式変形を進めて、 \(p+B_1+2B_2+3B_3+4B_4+5B_5 \ge 3 \times (q+B_1+B_2+B_3+B_4+B_5)\)
\(p-3q-2B_1-B_2+B_4+2B_5 \ge 0\)
を得ます。この式より、星 \(3\) 以下のレビューを追加することは無意味または有害であることがわかります。
以降、 \(B_1=B_2=B_3=0\) として更に変形すると \(B_4+2B_5 \ge 3q-p\) を得ます。
以降、最小の賄賂でこの式を満たすことを考えましょう。

上の式について、「星 \(4\) のレビューを \(2\) 件追加する」ことと「星 \(5\) のレビューを \(1\) 件追加する」ことは同じ効果を持つことがわかります。
これを換言すると、この \(2\) つの操作を交換してもよいと言い換えられます。

ここから、最適なケースは以下の \(3\) つのうちどれかであることが分かります。

• 星 \(4\) のレビューを全く追加しない。星 \(5\) のレビューのみを追加して平均を星 \(3\) 以上にする。
• 星 \(4\) のレビューを \(1\) 件だけ追加し、星 \(5\) を追加することで平均を星 \(3\) 以上にする。
• 星 \(4\) のレビューのみを追加して平均を星 \(3\) 以上にする。

上記 \(3\) ケースを全て試して賄賂の最小値を出力することで、この問題をテストケースあたり時間計算量 \(O(1)\) で正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}

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

  int t;
  cin >> t;
  while(t>0){
    t--;

    vector<long long> a(8),p(8);
    for(long long i=1;i<=5;i++){cin >> a[i];}
    for(long long i=1;i<=5;i++){cin >> p[i];}

    long long star=0,rev=0;
    for(long long i=1;i<=5;i++){
      star+=a[i]*i;
      rev+=a[i];
    }

    long long res=8e18;
    long long gain=3*rev-star;
    if(gain<=0){res=0;}
    else{
      // all 4*
      res=min(res,gain*p[4]);

      // one 4* + many 5*
      res=min(res,p[4]+llceil(gain-1,2)*p[5]);

      // all 5*
      res=min(res,llceil(gain,2)*p[5]);
    }
    cout << res << "\n";
  }
  return 0;
}