SteelMill
SRM 765 · 2019-08-22 · by misof
Problem Statement
You run a steel mill. Your goal for this month is to produce goal kg of steel.
In order to do that, you first need to order some shipments of iron ore. Multiple mines are selling their output. For each mine x, you know three values:
- If you order the output of this mine, you need to pay shipmentCost[x] dollars to have it delivered.
- The output of mine x contains enough iron to produce shipmentSize[x] kg of steel.
- As different mines have outputs of different purity, the cost to produce 1 kg of steel varies. For mine x, you'll need to spend costPerKg[x] dollars per each kg of steel you'll actually produce from this mine's output.
Calculate and return the minimum total cost of producing goal kg of steel.
Constraints
- goal will be between 1 and 10^6, inclusive.
- shipmentCost will contain between 1 and 100 elements, inclusive.
- shipmentSize will contain the same number of elements as shipmentCost.
- costPerKg will contain the same number of elements as shipmentCost.
- Each element of shipmentCost will be between 1 and 10^9, inclusive.
- Each element of shipmentSize will be between 1 and 10^6, inclusive.
- The sum of shipmentSize will be at least goal.
- Each element of costPerKg will be between 1 and 10^9, inclusive.
30
{100, 200, 300}
{10, 10, 10}
{1, 2, 3}
Returns: 660
We need to purchase everything on the market in order to reach the goal. We will pay 100 + 200 + 300 = 600 for shipping and then 10*1 + 10*2 + 10*3 = 60 for producing the steel from the iron ores.
20
{1234567, 50, 50}
{20, 11, 13}
{1, 12345, 23456}
Returns: 346999
The iron ore from mine 0 is really cheap to process, but this mine is very far from us and paying the shipping costs is too expensive. The optimal solution is to pay for the ore from mines 1 and 2, and to produce 11 kg of steel from the ore of mine 1 and 9 kg of steel from the ore of mine 2.
20
{1234567, 50, 50}
{20, 11, 13}
{1, 123456789, 234567890}
Returns: 1234587
Here the processing costs for mines 1 and 2 are too high and we are better off just paying for the shipment from mine 0.
1000000
{1000000000}
{1000000}
{1000000000}
Returns: 1000001000000000
A single very expensive mine. Watch out for integer overflow.
178161
{122650, 72284, 86999, 45034, 21485, 103347, 65527, 92958, 37687, 42371, 73749, 32079, 24531, 1423, 24134, 42751, 68828, 30275, 103574, 16674, 79204, 83732, 99078, 91406, 64282, 104138, 115351, 26161, 13725, 54489, 80708, 43671, 13533, 112607, 6655, 28270, 47621, 74869, 58694, 63543, 76525, 115816, 90723, 112532, 49258, 91019, 31629, 1927, 120136, 105702, 29977, 120072, 44099, 88211, 85800, 39551, 34572, 122227, 122922, 19976, 85427, 111255, 17759, 107931, 85737, 26093, 43577, 55563, 126794, 114283, 114482, 121707, 97171, 130000, 29302, 72152, 50688, 56946, 77286, 106645, 6089, 105702, 19366, 55974, 69842, 50615, 25054, 119219, 43197, 117710, 14148, 9565, 34034, 122200}
{646, 1858, 196, 2436, 2788, 2463, 1669, 673, 2972, 1372, 968, 2493, 3580, 261, 1806, 2871, 1533, 2380, 415, 755, 3686, 2470, 1870, 1206, 2233, 873, 2765, 4037, 1586, 275, 1986, 1182, 705, 3177, 1070, 236, 2919, 3128, 1366, 2112, 2938, 133, 2143, 3013, 3738, 63, 2033, 3132, 1558, 2232, 1786, 3447, 3747, 2195, 3155, 1693, 1626, 618, 1577, 599, 2176, 2624, 606, 1933, 118, 486, 1503, 3741, 3762, 3265, 2923, 3684, 3270, 2505, 2076, 352, 987, 3167, 1848, 3878, 807, 1635, 2995, 2343, 2384, 1883, 3465, 3904, 908, 921, 1468, 393, 251, 2385}
{1158, 1052, 1197, 1753, 1604, 1375, 1440, 1801, 329, 853, 1706, 153, 1866, 745, 1849, 865, 1988, 768, 388, 1526, 394, 892, 116, 1638, 1449, 461, 1969, 1208, 832, 1572, 1717, 1212, 468, 1622, 1277, 1516, 1314, 846, 1522, 1388, 943, 926, 778, 1555, 1146, 624, 1609, 1187, 1784, 1095, 1147, 223, 1375, 1321, 756, 457, 1618, 1879, 1099, 1643, 1443, 729, 1498, 1890, 949, 778, 240, 203, 791, 663, 1520, 268, 478, 1966, 1594, 1995, 1763, 1157, 1520, 53, 490, 1317, 558, 1791, 1483, 1384, 853, 866, 506, 1075, 1025, 930, 1450, 1739}
Returns: 194857831
Submissions are judged against all 160 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SteelMill with a public method long long cheapest(int goal, vector<int> shipmentCost, vector<int> shipmentSize, vector<int> costPerKg) · 160 test cases · 2 s / 256 MB per case