Cod sursa(job #862498)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 22 ianuarie 2013 18:56:56
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 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;
    for (i = K; i <= N; i++)
    {
        while (!D.empty() and A[i - K] <= A[ D.back() ]) D.pop_back ();
        D.push_back (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;
}