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);
presum[i].add(j,sum);
    }
}
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