Can any one help?

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3772 |

3 | tourist | 3706 |

4 | maroonrk | 3609 |

5 | Um_nik | 3591 |

6 | fantasy | 3526 |

7 | ko_osaga | 3500 |

8 | inaFSTream | 3477 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 183 |

2 | awoo | 181 |

3 | nor | 172 |

4 | -is-this-fft- | 170 |

4 | adamant | 170 |

6 | maroonrk | 165 |

7 | antontrygubO_o | 160 |

8 | SecondThread | 159 |

9 | dario2994 | 152 |

9 | kostka | 152 |

Can any one help?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/23/2023 08:06:06 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

_{i}-B_{i}, that is how much it would take to replace this close bracket with an open one. Now, if at any time the balance becomes negative, find the close bracket with the cheapest cost and replace it with open bracket (don't forget to increase the total price by cost transformation) and increase the balance by 2.The sequence is impossible to construct, if for a negative balance we do not have any close brackets earlier that can be replaced by open, or if the final balance is not equal to 0 (that means the number of open brackets is greater than the number of close brackets).

The formal proof here can be found by using the standard greedy approaches.