Cod sursa(job #2228132)

Utilizator LIR16LazarIonutRadu LIR16 Data 2 august 2018 19:17:21
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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 minimului 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.

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

    cin >> vector_length >> length_min;

    sums[0] = 0;
    min_sums[0] = 0;
    for( int i=1 ; i<=vector_length ; i++ )
    {
        cin >> v[i];
        sums[i] = sums[i-1] + v[i];
        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 = LONG_LONG_MIN;
    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;
        }
    }

    cout << left << " " << right << " " << value;

    return 0;
}