Cerința

Se dă un șir de n numere naturale și un număr natural val. Determinați lungimea maximă a unei secvențe cu proprietatea că suma numerelor din aceasta este mai mică sau egală cu val.

Date de intrare

Fișierul de intrare secvmaxval.in conține pe prima linie numerele n și val, iar pe a două linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire secvmaxval.out va conține pe prima linie lungimea maximă a unei secvențe care satisface proprietatea dată.

Restricții și precizări

1 ≤ n ≤ 200.000
numerele de pe a două linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
1 ≤ val ≤ 2⁶³

Exemplu

secvmaxval.in

5 11
4 5 2 3 9

secvmaxval.out

Explicație

O secvență de lungime maximă cu suma elementelor mai mică sau egală cu 11 este 5 2 3.

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 SecvMaxVal:

/// Solutie - Moca Andrei - O(n^2)
#include <bits/stdc++.h>
#define ENTER ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define EXIT  fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("secvmaxval.in");
ofstream fout("secvmaxval.out");
int n, lmax, v[200002], minim = 1e9;
int64_t s, sum, val;
int main()
{
    ENTER
    fin >> n >> val;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        s += v[i];
        minim = min(minim, v[i]);
    }
    if (val < minim) {
        fout << 0; EXIT
    }
    if (val >= s) {
        fout << n; EXIT
    }
    for (int i = 1; i <= n; ++i)
    {
        sum = 0;
        for (int j = i; j <= n; ++j)
        {
            sum += v[j];
            if (sum > val) {
                lmax = max(lmax, j - i);
                break;
            }
        }
    }
    fout << lmax;
    EXIT
}

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 #3163 SecvMaxVal

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3163 SecvMaxVal 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 #3163 SecvMaxVal