Polynomial-Time Exact MAP Inference on Discrete Models With Global Dependencies