← 返回 walmartlabs 的题目列表Minimum Cost to Build k-Capable ML Model Sets
类型：online_judge
Problem Statement
You are given n machine learning models. Each model has:
cost[i]: the cost of selecting the i-th model;
featureAvailability[i]: a binary string of length 2 describing the supported features:
"00": supports neither Feature A nor Feature B;
"01": supports only Feature B;
"10": supports only Feature A;
"11": supports both Feature A and Feature B.
For an integer k, a selected set of models is called k-capable if:
at least k selected models support Feature A;
at least k selected models support Feature B.
Note that a model with featureAvailability[i] == "11" counts toward both Feature A and Feature B.
For every k = 1, 2, ..., n, compute the minimum total cost needed to form a k-capable set. If it is impossible, return -1 for that k.
Input Format
n
cost[0] cost[1] ... cost[n-1]
featureAvailability[0] featureAvailability[1] ... featureAvailability[n-1]
Output Format
Print n integers. The i-th integer is the minimum cost for k = i + 1; print -1 if impossible.
Constraints
1 <= n <= 2 * 10^5
1 <= cost[i] <= 10^9
featureAvailability[i] is one of "00", "01", "10", "11"
Example
Example 1
Input:
5
3 2 5 4 10
10 01 11 11 00
Output:
4 9 14 -1 -1
Explanation:
k = 1: choose the "11" model with cost 4;
k = 2: choose the "11" model with cost 4, plus the "10" model with cost 3 and the "01" model with cost 2, total cost 9;
k = 3: choose two "11" models, one "10" model, and one "01" model, total cost 14;
k >= 4: impossible.
Example
Input
5
3 2 5 4 10
10 01 11 11 00
Output
4 9 14 -1 -1