Cod sursa(job #2345401)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 16 februarie 2019 12:23:11
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
/*
    ** Code by
    ** Arhire Andrei
*/
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
int n , k , a , i , sp [ 50005 ] , best = - ( 1 << 30 ) , X , Y ;
deque < int > dq , st ;
int main(){

  in >> n >> k ;
    for ( i = 1 ; i <= n ; ++ i )
    {
        in >> a , sp [ i ] = a + sp [ i - 1 ] ;
        dq.push_back ( i ) ;
        if ( sp [ dq.back() ] - sp [ dq.front() - 1 ] < 0 ) st.push_back ( i ) ;
        if ( !st.empty() && i - st.front() + 1 > k )
        {
        while ( i - st.front() + 1 > k && sp [ st.front() ] - sp [ dq.front() - 1 ] < 0 )
        dq.pop_front()  ;
        st.pop_front() ;
        }
        if ( dq.back() - dq.front() + 1 >= k && sp [ dq.back() ] - sp [ dq.front() - 1 ] > best )
        {
             best = sp [ dq.back() ] - sp [ dq.front() - 1 ] ;
             X = dq.front() ;
             Y = dq.back() ;
        }
    }
    out << X << ' ' << Y << ' ' << best << '\n' ;
}