#include //#define gc getchar_unlocked #define gc getchar int liczbaNaWejsciu; /* użycie 'inline' >daje szanse< na szybsze wykonanie programu ( https://pl.wikibooks.org/wiki/C%2B%2B/Funkcje_inline ) wywołanie funkcji to operacje na stosie [chyba], lepiej ich oszczędzić i wkleić kod funkcji w miejsce wywołania, ale dla czytelności lepiej trzymać fragmenty kodu w funkcjach 'daje szanse' dlatego, że kompilatory same zazwyczaj decydują które funkcje skopiować i wkleić [inline], a które zostawić oddzielnie i odwoływać się do ich przez adres w pamięci */ inline void pobierzNastepnaLiczbeZWejscia() { /* 'register' daje do zrozumienia kompilatorowi, że potrzebujemy szybkiego dostępu do tej zmiennej, ale nie będziemy potrzebowali jej adresu [w RAM], dlatego zamiast trzymać zmienną w RAMie wystarczy nam dostęp do niej w 'rejestrze procesora' (setki tysięcy razy szybszy od RAM) */ register int znakZWejscia = gc(); liczbaNaWejsciu = 0; for( ; ((znakZWejscia < 48 || znakZWejscia > 57)); znakZWejscia = gc() ); for( ;znakZWejscia > 47 && znakZWejscia < 58; znakZWejscia = gc() ) { // mnozymy aktualna liczba przez 10 (dzięki 2 operacją bitowym) i // dodajemy cyfrę z wejścia (znaki ASCII 0-9 zaczynają się od 48 znaku) liczbaNaWejsciu = (liczbaNaWejsciu << 1) + (liczbaNaWejsciu << 3) + znakZWejscia - 48; } } // użycie 'inline' daje szanse na szybsze wykonanie programu ( https://pl.wikibooks.org/wiki/C%2B%2B/Funkcje_inline ) inline bool czyJestNastepnaLiczbaNaWejsciu() { return !feof(stdin); } /* "elementy rozważanego ciągu zawarte w przedziale wartości [0,10^9]" - wystarczą nam INT dla elementów, ale do przechowywania sumy elementow potrzeba LONG [0,10^18] (w C 'long long int') */ int main() { // "Długość ciągu C dodatnia i ograniczona przez 10^7" - na pewno bedzie 1 liczba do wczytania // wczytujemy pierwszą liczbę z wejścia pobierzNastepnaLiczbeZWejscia(); /* ciągi monotoniczne dzielimy na ( https://pl.wikipedia.org/wiki/Funkcja_monotoniczna ): rosnące malejące stałe nierosnące - zawiera w sobie ciągi malejące i stałe niemalejące - zawiera w sobie ciągi rosnące i stałe ze względu na to, że chcemy znaleźć najdłuższe ciągi, możemy podzielić ciąg który otrzymamy na wejściu na 2 rodzaje: nierosnące niemalejące pamiętając jednak o tym, że ciąg 'stały' może być końcem ciągu nierosnącego i za razem początekim ciągu niemalejącego i na odwrót */ // czy aktualnie ciąg rośnie czy maleje, wartość początkowa bez znaczenia bool czyNiemalejacy = true; // ostatnio wczytana liczba, potrzebna do sprawdzenia czy ciąg rośnie/maleje/jest stały long long int poprzedniaLiczbaNaWejsciu = liczbaNaWejsciu; // długość ciągu 'stałęgo', po wczytaniu pierwszej liczby mamy ciąg stały od długości 1 int dlugoscCiaguStalego = 1; // aktualna długość podciągu, po wczytaniu pierwszej liczby mamy ciąg stały od długości 1 int dlugoscAktualnegoCiagu = 1; // suma elementów aktualnego podciągu, po wczytaniu pierwszej liczby jest równa jej wartości long long int sumaElementowAktualnegoCiagu = poprzedniaLiczbaNaWejsciu; // maksymalne wartości znalezionego podciągu int maksymalnaDlugoscPodciaguMonotonicznego = 1; long long int sumaElementowCiaguMaksymalnejDlugosci = poprzedniaLiczbaNaWejsciu; while(czyJestNastepnaLiczbaNaWejsciu()) { pobierzNastepnaLiczbeZWejscia(); // jeśli ciąg rośnie if(liczbaNaWejsciu > poprzedniaLiczbaNaWejsciu) { // jeśli wcześniej też rósł if(czyNiemalejacy) { // dodajmy aktualną liczbę do sumy aktualnego ciągu sumaElementowAktualnegoCiagu += liczbaNaWejsciu; // zwiększmy długość aktualnego ciągu o 1 dlugoscAktualnegoCiagu++; } // jeśli wcześniej malał else { // jeśli wcześniej malał, a teraz rośnie to trzeba sprawdzić czy ostatni podciąg nie jest najdłuższy if(dlugoscAktualnegoCiagu > maksymalnaDlugoscPodciaguMonotonicznego) { maksymalnaDlugoscPodciaguMonotonicznego = dlugoscAktualnegoCiagu; sumaElementowCiaguMaksymalnejDlugosci = sumaElementowAktualnegoCiagu; } // zapamiętujemy, że teraz rośnie czyNiemalejacy = !czyNiemalejacy; // dodajemy sumę elementów poprzedzającego ciągu stałego i aktualną wartość sumaElementowAktualnegoCiagu = dlugoscCiaguStalego * poprzedniaLiczbaNaWejsciu + liczbaNaWejsciu; // aktualna długość ciągu to długość poprzedzającego ciągu stałego plus 1 dlugoscAktualnegoCiagu = dlugoscCiaguStalego + 1; } dlugoscCiaguStalego = 1; } // jeśli ciąg maleje else if(liczbaNaWejsciu < poprzedniaLiczbaNaWejsciu) { // jeśli wcześniej rósł if(czyNiemalejacy) { // jeśli wcześniej rósł, a teraz maleje to trzeba sprawdzić czy ostatni podciąg nie jest najdłuższy if(dlugoscAktualnegoCiagu > maksymalnaDlugoscPodciaguMonotonicznego) { maksymalnaDlugoscPodciaguMonotonicznego = dlugoscAktualnegoCiagu; sumaElementowCiaguMaksymalnejDlugosci = sumaElementowAktualnegoCiagu; } // zapamiętujemy, że teraz maleje czyNiemalejacy = !czyNiemalejacy; // dodajemy sumę elementów poprzedzającego ciągu stałego i aktualną wartość sumaElementowAktualnegoCiagu = dlugoscCiaguStalego * poprzedniaLiczbaNaWejsciu + liczbaNaWejsciu; // aktualna długość ciągu to długość poprzedzającego ciągu stałego plus 1 dlugoscAktualnegoCiagu = dlugoscCiaguStalego + 1; } // jeśli wcześniej malał else { // dodajmy aktualną liczbę do sumy aktualnego ciągu sumaElementowAktualnegoCiagu += liczbaNaWejsciu; // zwiększmy długość aktualnego ciągu o 1 dlugoscAktualnegoCiagu++; } dlugoscCiaguStalego = 1; } // jeśli ciąg jest stały else { /* zwiększamy długość ciągu stałego (potrzebna do obliczenia ilości i sumy elementów poprzedzających, w przypadku zmiany z rosnącego na malejący lub odwrotnie) */ dlugoscCiaguStalego++; /* podciąg 'stały' może być elementem ciągu nierosnącego/niemalejącego 'dlugoscCiaguStalego' trzymamy na wypadek gdyby ciąg zmienił kierunek 'dlugoscAktualnegoCiagu' i 'sumaElementowAktualnegoCiagu' zwiększamy, żeby nie musieć tego dodatkowo obliczać w warunkach '>' i '<' oraz sprawdzać po 'while' */ // zwiększamy długość aktualnego ciągu dlugoscAktualnegoCiagu++; // zwiększamy sumę elementów aktualnego ciągu sumaElementowAktualnegoCiagu += liczbaNaWejsciu; } poprzedniaLiczbaNaWejsciu = liczbaNaWejsciu; } // sprawdzamy czy ciąg na którym zakończyły się dane nie jest najdłuższy if(dlugoscAktualnegoCiagu > maksymalnaDlugoscPodciaguMonotonicznego) { maksymalnaDlugoscPodciaguMonotonicznego = dlugoscAktualnegoCiagu; sumaElementowCiaguMaksymalnejDlugosci = sumaElementowAktualnegoCiagu; } // wyświetlamy wynik, %d = int, %lld = long long int // użycie '%d' dla 'long long int' wyświetliło by dziwną lub zmniejszoną wartość nie pokazując żadnego błedu printf("%d %lld", maksymalnaDlugoscPodciaguMonotonicznego, sumaElementowCiaguMaksymalnejDlugosci); return 0; }