Educational Codeforces Round 108 (Rated for Div. 2) C. Berland Regional

Question:Problem - C - Codeforces
My sol:Submission #114622583 - Codeforces
I am getting TLE on this problem. I am curious to know how can I reduce my code time complexity
Thank you in advance

There are many optimizations

  1. Instead of unordered map of ll, multiset , and ll,vector , you should have use vector of array in both the cases , as unordered map and multiset both includes a good constant time factor ,
  2. You should notice that if for k=x you don’t need an sums[i] , then for k=x+1 also you don’t need sums[i] , so you can just reduce the range of checking one by one .
    Link to my submission
    Submission #114585096 - Codeforces

The biggest optimization in this problem is finding pattern according to the size of each university value .

try to understand this u will surely get it.

1 Like