CF704D Captain America

Steve Rogers is fascinated with new vibranium shields S.H.I.E.L.D gave him. They're all uncolored. There are $ n $ shields in total, the $ i $ -th shield is located at point $ (x_{i},y_{i}) $ of the coordinate plane. It's possible that two or more shields share the same location. Steve wants to paint all these shields. He paints each shield in either red or blue. Painting a shield in red costs $ r $ dollars while painting it in blue costs $ b $ dollars. Additionally, there are $ m $ constraints Steve wants to be satisfied. The $ i $ -th constraint is provided by three integers $ t_{i} $ , $ l_{i} $ and $ d_{i} $ : - If $ t_{i}=1 $ , then the absolute difference between the number of red and blue shields on line $ x=l_{i} $ should not exceed $ d_{i} $ . - If $ t_{i}=2 $ , then the absolute difference between the number of red and blue shields on line $ y=l_{i} $ should not exceed $ d_{i} $ . Steve gave you the task of finding the painting that satisfies all the condition and the total cost is minimum.

N/A

N/A