1 / 4
May 2023

http://www.spoj.pl/problems/PRATA/9

I am getting TLE. please help.
my code:

‘’’
#include

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--){
        int p,l;
        cin>>p>>l;
        pair<int,int> c[l];
        for(int i=0;i<l;i++){
            int ci;
           cin>>ci;
           c[i]={ci,0};
        }
        int b=0,e=0;
        for(int a=0;a>=0;a++){
            for(int i=0;i<l;i++){
               if((c[i].first)*((c[i].second)+1)*((c[i].second)+2)/2==a){
                   c[i].second++;
                   b++;
                   if(b==p){
                       cout<<a<<endl;
                       e=1;
                       break;

                   }
               }
           }
           if(e==1){
                break;
           }
       }

    }
     return 0;
}

‘’’

  • created

    May '23
  • last reply

    May '23
  • 3

    replies

  • 445

    views

  • 2

    users

  • 1

    like

  • 2

    links

Some details of the code have been lost by the “smart” editor. You can fix this - please edit your post to put three back ticks ``` on a line by themselves both before and after the code. Alternatively, indent the entire code by four spaces.

consider this test case:

1000
1 1

At the end of the calculation, c[0].second is 1000 of course, which means the “a” loop executes 999 times only to do nothing. Is there a way to skip all those loops that do nothing? Perhaps a data structure of some kind?

Minor optimisations that are unlikely to make much difference:

  1. “for(int a=0; a>=0; a++)” the while “a>=0” part is redundant, as it always equates to true. Just use “for(int a=0; ; a++)”

  2. Division is relatively slow. Can the “if(c[i].first * (c[i].second+1) * (c[i].second+2)/2 == a)” comparison be restated to remove it? (Although the compiler may replace the division by 2 with a bit shift, so possibly a moot point.)

PRATA1