https://codeforces.com/contest/448/submission/96518240 I think the complexity is O(n^2) and so, I can't figure out as to why does it TLE? I have been trying to debug it and optimize it for hours. Any help would be appreciated.

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

1 | tourist | 3687 |

2 | ecnerwala | 3668 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | ainta | 3318 |

9 | Itst | 3239 |

10 | apiadu | 3238 |

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

1 | Errichto | 204 |

2 | SecondThread | 200 |

3 | Monogon | 199 |

4 | vovuh | 189 |

5 | Um_nik | 188 |

6 | pikmike | 186 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 178 |

9 | pashka | 169 |

10 | -is-this-fft- | 165 |

https://codeforces.com/contest/448/submission/96518240 I think the complexity is O(n^2) and so, I can't figure out as to why does it TLE? I have been trying to debug it and optimize it for hours. Any help would be appreciated.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/04/2020 02:33:31 (i3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

After seeing the title I thought, you are gonna help me with this problem..

In case of increasingly sorted input data your solution has O(2^n) time complexity.

thanks a lot! I think I need to study complexity analysis for recursion.