Cod sursa(job #2569132)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 4 martie 2020 11:13:56
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>

#define N 400001

using namespace std;

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

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

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