Cod sursa(job #2228165)

Utilizator LIR16LazarIonutRadu LIR16 Data 2 august 2018 20:30:12
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <climits>

using namespace std;

int main()
{
    // sums[i] = suma elementelor v[0], v[1], v[2], ... v[i]
    // suma elementelor v[i], v[i+1], v[i+2], ... v[j] = sums[j] - sums[i-1]
    // min_sums[i] = pozitia minimul elementelor sums[0], sums[1], sums[2], ... sums[i]
    // sums[min_sums[i]] = minimul elementelor sums[0], sums[1], sums[2], ... sums[i]
    // Folosind min_sums vom puteam gasi secventa de suma maxima care se termina pe pozitia i
    // de orice lungime. Suma secventei este sums[i] - sums[min_sums[i-lungime-1]],
    // incepe la min_sums[i-lungime-1]+1 si se termina la i.

    ifstream fin("secv2.in");
    ofstream fout("secv2.out");

    long long vector_length, length_min, number, sums[50001], min_sums[50001];

    fin >> vector_length >> length_min;

    sums[0] = 0;
    min_sums[0] = 0;
    for( int i=1 ; i<=vector_length ; i++ )
    {
        fin >> number;
        sums[i] = sums[i-1] + number;
        if( sums[i] > sums[min_sums[i-1]] )
            min_sums[i] = min_sums[i-1];
        else
            min_sums[i] = i;
    }

    long long left, right, value = -999999999;
    for( int i=length_min ; i<=vector_length ; i++ )
    {
        if( value < sums[i] - sums[min_sums[i-length_min-1]] )
        {
            value = sums[i] - sums[min_sums[i-length_min-1]];
            left = min_sums[i-length_min-1]+1;
            right = i;
        }
    }

    fout << left << " " << right << " " << value;

    fin.close();
    fout.close();
    return 0;
}