Pan Stefan z polskiego spoja

[Tramwaj z Bombaju 2]

http://pl.spoj.com/problems/FZI_STEF/

 

Sprawdziłem przykładowe zestawy danych: program działa. Działa także dla zestawów, które ktoś podsunął w komentarzu. Mimo to, system sprawdzający wyrzuca informację o błędnej odpowiedzi.

 

Tak, Jeżu, wiem Miałem czytać o kontenerach, ale trafiłem na pana Stefana i mnie wciągnął

 

#include <iostream>

using namespace std;

int m, liczba_miast, zysk, zyskm, mi, maks_suma_lewa, maks_suma_prawa, suma_czastkowa_prawa, suma_czastkowa_lewa;

int main()
{
   cin>>liczba_miast;

   int *zysk_strata;
   zysk_strata = new int [liczba_miast];

   for (int i=0; i<liczba_miast; i++)
   {
       cin>>zysk_strata[i];
   }

   m=zysk_strata[0];
   for (int i=0; i<liczba_miast; i++)
   {
       if (zysk_strata[i]>m)
       {
           m=zysk_strata[i];
       }
   }

   for (int i=0; i<liczba_miast; i++)
   {
       if (m==zysk_strata[i])
       {
           mi=i;
           maks_suma_lewa=m;
           suma_czastkowa_lewa=m;

           for (int i=mi; i>0; i--)
           {
               suma_czastkowa_lewa=suma_czastkowa_lewa+zysk_strata[i-1];
               if (suma_czastkowa_lewa>=maks_suma_lewa)
               {
                   maks_suma_lewa=suma_czastkowa_lewa;
               }
           }

           maks_suma_prawa=m;
           suma_czastkowa_prawa=m;
           for (int i=mi; i<liczba_miast-1; i++)
           {
               suma_czastkowa_prawa=suma_czastkowa_prawa+zysk_strata[i+1];
               if (suma_czastkowa_prawa>=maks_suma_prawa)
               {
                   maks_suma_prawa=suma_czastkowa_prawa;
               }
           }

       zysk=maks_suma_lewa+maks_suma_prawa-m;
       zyskm=zysk;
       if (zysk>zyskm)
       {
           zyskm=zysk;
       }
       }
   }
   if (zyskm<=0)
   {
       zyskm=0;
   }
   cout<<zyskm;

   return 0;
}

[MitycznyJeż 476]

Zastanów się ile maksymalnie może zarobić Stefan. Czy program jest przygotowany na taką okoliczność?

[Tramwaj z Bombaju 2]

Hm, racja. Nie był. Zmieniłem int na long long, by pomieścił wyniki do 10^10:

int m, liczba_miast, mi;
long long zysk, zyskm, maks_suma_lewa, maks_suma_prawa, suma_czastkowa_prawa, suma_czastkowa_lewa;

Co jeszcze robię źle?

 

dobra, już widzę błąd. później wrzucę poprawiony kod