Cod sursa(job #1246179)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 20 octombrie 2014 18:42:16
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#include<deque>

using namespace std;

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

const int inf = 1 << 30;
const int nmax = 50000;
int n, k, x, y, ans, s[ nmax + 1 ];
deque <int> d;

void read() {
    int x;
    fin >> n >> k;
    for( int i = 1; i <= n; ++ i ) {
        fin >> x;
        s[ i ] = x + s[ i - 1 ];
    }
}
void solve() {
    ans = -inf;
    for( int i = 0; i <= n - k; ++ i ) {
        while( !d.empty() && s[ i ] < s[ d.back() ] ) {
            d.pop_back();
        }
        d.push_back( i );

        if ( ans < s[ i + k ] - s[ d.front() ] ) {
            ans = s[ i + k ] - s[ d.front() ];
            y = i + k;
            x = d.front() + 1;
        }
    }
}

int main() {
    read();

    solve();

    fout << x << ' ' << y << ' ' << ans << "\n";

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