Cerința

Se dă un şir format din n numere naturale. Un termen din şir se numeşte minim relativ dacă este mai mic sau egal decât toţi termenii din şir situaţi înaintea lui. Să se determine numărul elementelor din şir care sunt minime relative, precum şi suma maximă a elementelor dintr-o secvenţă cuprinsă între două minime relative consecutive, inclusiv acestea.

Date de intrare

Fișierul de intrare relativ.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire relativ.out va conține pe prima linie numărul k, reprezentând numărul termenilor din şir care sunt minime relative, iar pe a doua linie maximul sumei elementelor dintr-o secvenţă cuprinsă între două minime relative consecutive din şir, inclusiv acestea.

Restricții și precizări

1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
o secvenţă cuprinsă între doi termeni din şir conţine toţi termenii din şir situaţi între aceştia, inclusiv cei doi termeni daţi.
primul termen din şir este considerat minim relativ
şirul conţine cel puţin doi termeni care sunt minime relative
două minime relative sunt consecutive în şir dacă între ele nu mai este alt minim relativ
prima cerinţă valorează 40% din punctaj, iar a doua 60% ( în fişierul relativ.out trebuie afişate două numere pentru a primi punctaje parţiale)

Exemplu

relativ.in

9
3 5 9 2 7 11 3 4 2

relativ.out

3
29

Explicație

În şirul dat sunt trei minime relative, 3, 2 şi 2 situate pe poziţiile 1, 4, respectiv 9 în şir. Secvenţele din şir situate între două minime relative consecutive sunt 3, 5, 9, 2, respectiv 2, 7, 11, 3, 4, 2, suma elementelor acestora fiind 19, respectiv 29. Suma maximă este 29.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema relativ:

#include <fstream>

using namespace std;
ifstream f("relativ.in");
ofstream g("relativ.out");
long long n , x , minim , maxim , sumpart , suma , i , nrrel ;

int main()
{
    f >> n ;
    f >> x ;
    minim = x ;
    maxim = 0 ;
    sumpart = x ;
    suma = x ;
    nrrel = 1 ;
    for ( i=1 ; i<=n-1 ; i++ )
    {
        f >> x ;
        sumpart += x ;
        if ( x <= minim )
          {
              nrrel++ ;
              if ( sumpart-suma+minim > maxim ) maxim = sumpart-suma+minim ;
              minim = x ;
              suma = sumpart ;
          }
    }
    g << nrrel << "\n" << maxim ;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1468 relativ

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1468 relativ de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1468 relativ