Cod sursa(job #852892)

Utilizator informatician28Andrei Dinu informatician28 Data 11 ianuarie 2013 21:27:47
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <deque>
#define INF 0x3f3f3f3f
#define DIM 50001

using namespace std;

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

int N, K, A[DIM], _left, _right;
long long Sol;
deque <int> D;

int main()
{
    int i;
    in >> N >> K;
    for (i = 1; i <= N; i++)
    {
        in >> A[i];
        A[i] += A[i-1];
    }
    Sol = -INF;
    //D.push_back(1);
    for (i = 1; i <= N; i++)
    {
        while (!D.empty() and A[i] <= A[ D.back() ]) D.pop_back ();
        D.push_back (i);
        //if (A[ D.back() ] <= A[ D.front()]) D.pop_front();
        if (i >= K)
        {
            if (A[i] - A[ D.front() ] > Sol) Sol = A[i] - A[ D.front() ], _left = D.front()+1, _right = i;
        }
    }
    out << _left << " " << _right << " " << Sol;
    return 0;
}