Cod sursa(job #1326112)

Utilizator felixiPuscasu Felix felixi Data 24 ianuarie 2015 18:29:07
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 50000;

deque <int> d;
int v[NMAX+2],s[NMAX+2], st,dr,sum = -(1<<30);
int N,K;

int main() {
    in >> N >> K;
    for( int i = 1;  i <= N;  ++i ) {
        in >> v[i];
        s[i] = v[i]+s[i-1];
    }
    d.push_back(0);
    for( int i = K;  i <= N;  ++i ) {
        if( s[i]-s[d.front()] > sum ) {
            sum = s[i]-s[d.front()];
            st = d.front()+1;
            dr = i;
        }
        while( !d.empty() && s[i-K+1] < s[d.back()] ) {
            d.pop_back();
        }
        d.push_back(i-K+1);
    }
    out << st << ' ' << dr << ' ' << sum << '\n';
    return 0;
}