Cod sursa(job #1099765)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 6 februarie 2014 11:56:06
Problema Secventa 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>
#include <vector>

using namespace std;

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

const int Nmax = 50100;
const int oo = 0x3f3f3f3f;

long long N, K, S[Nmax], sol, st, dr;
deque <int> D;

int main()
{
    fin >> N >> K;
    for(int i = 1; i <= N; i++)
    {
        int x; fin >> x;
        S[i] = S[i - 1] + x;
    }

    sol = S[K];
    D.push_back(0); st = 1; dr = K;
    for(int i = K + 1; i <= N; i++)
    {
        int V = S[i - K + 1];
        if(sol < S[i] - S[D.front()])
            {
                sol = S[i] - S[D.front()];
                st = D.front(); dr = i;
            }

        while(!D.empty() && S[D.back()] >= V)
            D.pop_back();
        D.push_back(i - K + 1);
    }

    if(!st) st = 1;
    fout << st << ' ' << dr << ' ' << sol;
    return 0;
}