Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя priyanka_1998

Автор priyanka_1998, история, 6 лет назад, По-английски

Problem link : https://www.codechef.com/LTIME58B/problems/ARRP Solution link : https://www.codechef.com/viewsolution/18034419

int main(){

ll t;
cin>>t;

while(t--){

    ll n;
    cin>>n;

    ll a[n];

    for(ll i=1;i<=n;i++)
       cin>>a[i];

    ll prefix[n];


    prefix[1]=a[1];

    for(ll i=2;i<=n;i++)
       prefix[i]=prefix[i-1]+a[i];

    ll sum=prefix[n];



    cout<<"1";

    for(ll i=2;i<=n;i++){

       ll flag=0;

       if(sum%i==0){

         flag=1;

         ll k=sum/i;
         ll p=k;

         for(ll j=1;j<=n;j++){

          if(prefix[j]==p)
              p=p+k;
          else if(prefix[j]>p){
              flag=0;
              break;
          }

         }          
       }

       if(flag)
         cout<<"1";
       else
         cout<<"0";

    }

    cout<<"\n";



}


return 0;

}

can anyone help me to compute the time complexity of my code . It got accepted How??

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Auto comment: topic has been updated by priyanka_1998 (previous revision, new revision, compare).

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Author of this problem has analyzed about time complexity in depth about this problem here.

Also, you don't need to post the code, you can link it up to Ideone for clarity!