Problem

You will be given two arrays A and B, each of length N. For some value K, let's call an array C good if it satisfies the following conditions:

  • 0\le C_i \le B_i for (1 \le i \le N)
  • At least K elements in the array must be equal to 0.
  • \sum_{i=1}^N A_i = \sum_{i=1}^N C_i

Among all the good arrays C, let result(K) denote the minimum value of \sum_{i=1}^N |A_i-C_i|. If no good array is possible, result(K) = -1.

Find the value result(K) for all (0\le K \lt N).

Input Format

  • The first line of input contains an integer T denoting the number of test cases. T test cases follow.
  • The first line of each test case contains a single integer N.
  • The second line contains N integers A_1, A_2, \ldots, A_N, the array A.
  • The third line contains N integers B_1, B_2, \ldots, B_N, the array B.

Output Format

For each test case, output N space-separated integers, result(K) for (0 \le K \lt N).

Constraints

  • 1 \le T \le 100
  • 1 \le N \le 100
  • 1 \le A_i, B_i \le 100
  • The sum of N over all test cases won't exceed 100.

Sample 1:

Input
Output
2
5
6 5 2 1 7
10 1 5 1 5
3
7 7 9
8 9 9

12 14 -1 -1 -1 
0 -1 -1

Explanation:

Test case 1:

  • [10, 1, 4, 1, 5] is a good array with at least 0 zeroes and gives the minimum value for result(0).
  • [10, 0, 5, 1, 5] is a good array with at least 1 zeroes and gives the minimum value for result(1).
  • No good array is possible for the given constraints when K = 2, 3, or 4.

Test case 2:

  • [7, 7, 9] is a good array with at least 0 zeroes and gives the minimum value of result(0).
  • No good array is possible when K = 1 or 2.

 #include "bits/stdc++.h"

// #pragma GCC optimize("O3,unroll-loops")

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

using ll = long long int;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());


int main()

{

ios::sync_with_stdio(false); cin.tie(0);


int t; cin >> t;

while (t--) {

int n; cin >> n;

vector<int> a(n), b(n);

for (int &x : a) cin >> x;

for (int &x : b) cin >> x;


int sumA = accumulate(begin(a), end(a), 0);

int sumB = accumulate(begin(b), end(b), 0);

const int inf = 1e9 + 7;

vector dp(n+1, vector(sumB + 1, inf));

vector<int> ans(n, inf);

dp[0][0] = 0;

for (int i = 0; i < n; ++i) {

for (int ch = i+1; ch >= 1; --ch) {

for (int j = b[i]; j <= sumB; ++j) {

dp[ch][j] = min(dp[ch][j], dp[ch-1][j-b[i]] + max(0, a[i] - b[i]) - a[i]);

if (j >= sumA) ans[n-ch] = min(ans[n-ch], 2*dp[ch][j]);

}

}

}

for (int i = 0; i < n; ++i) {

if (ans[i] < 1e8) cout << ans[i] + 2*sumA << ' ';

else cout << -1 << ' ';

}

cout << '\n';

}

}