Cod sursa(job #2569243)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 4 martie 2020 11:37:04
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <deque>
#include <climits>

#define N 50001

using namespace std;

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

deque < int > dq;
int v[N];

int main()
{   int n, i, Max = INT_MIN, k, start, finish;
    f >> n >> k;
    dq.push_back ( 0 );
    v[0] = 0;
    for ( i = 1 ; i <= n; i++ ){
        f >> v[i];
        v[i] += v[i - 1];
        if ( i >= k && Max < v[i] - v[dq.front ( )] ){
            Max = v[i] - v[dq.front( )];
            start = dq.front ( ) + 1;
            finish = i;
        }
        if ( i > k ){
            while ( !dq.empty ( ) && v[dq.back ( )] > v[i - k] )
                dq.pop_back ( );
            dq.push_back ( i - k );
        }
    }
    g << start << ' ' << finish << ' ' << Max;
}