 # Getting TLE!

I have attempted this problem on codeforces educational round 108 , problem c, Berland Regionals. I am still getting TLE after many attempts of code optimization. Here is the problem. @suman_18733097 @cubefreak777 @uwi

I am storing the strength of different students in a list and storing these such list in an array ,where array index denotes the university number. Then i sort these list in descending order. After sorting , i am maintaining a prefix sum of each university . for each query 1 to n i am returning prefix sum of the list[i] . Here is my solution.

Please do respond , i post queries in the forum but got no reply from past few queries. If i am not able to explain my problem well please do tell me , i will improve or edit the text to a better and more understandable text. ,but please do not ignore such doubts.

Isn’t this O(N^2)?

``````for(int i=0;i<n;i++)
{
sum=0;
for(int j=0;j<list[i].size();j++)
{
sum+=list[i].get(j);
}
}
for(int i=1;i<=n;i++)
{
if(i>max)
{
System.out.print(0+" ");
continue;
}
long s=0;
for(int j=0;j<n;j++)
{
if(list[j]!=null && list[j].size()>=i){
int x=i*(presum[j].size()/i);
s+=(presum[j].get(x-1));
}
}
``````

The desired time complexity is O(N \log{N})

1 Like

This might help.

1 Like