Hello, can any one please tell how to solve This question

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

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

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

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 174 |

5 | tourist | 166 |

6 | McDic | 164 |

6 | Um_nik | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

Hello, can any one please tell how to solve This question

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/26/2020 03:57:00 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Firstly, sort the indices in chronological order. Secondly, we can define dp[i] as the maximum amount of money we can obtain at time a[i]. We can then say that this amount can be represented as the best out of these 2 values:

We don't use interval i: the maximum amount of money we can obtain from a[i+1]...N

We do use interval i: Define j as the first interval such that s[j] > e[i] (in other words, the first disjoint interval after i). Then, the value would be (the maximum possible money obtained from j..N) + p[i].

In terms of reccurence relation, this would be: dp[i] = max(dp[i+1], dp[j]+p[i])

This gives us an O(N^2) solution, which will definetly TLE. However, we notice that for all intervals i+1..N, there is always an interval j such that intervals i and j are disjoint, and that for all k from i+1..j-1, k and i are not disjoint. Therefore, we can binary search to find the value j. The total complexity therefore becomes O(NlgN)

My code

Hope this helped!

Thanks man, that is really helpful.

CodePlease feel free to ask if anything is ambiguous.

Got it, Thank you