OTS.ME - Paste

#include <stdio.h>

//#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;
}