Cod sursa(job #1418502)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 13 aprilie 2015 12:51:41
Problema Secventa 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <limits>

using namespace std;

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

int main()
{
    int N, K;
    in >> N >> K;

    vector<int> sums(N + 1, 0);
    int nb;
    for (int i = 1; i <= N; i++) {
        in >> nb;
        sums[i] = sums[i - 1] + nb;
    }

    deque<int> dq;
    for (int i = 1; i <= K; i++) dq.push_back(i);

    int finalStart, finalEnd, maxSum = numeric_limits<int>::min();
    for (int i = K + 1; i <= N; i++) {
        
        while (sums[dq.back() - K] - sums[dq.front() - 1] < 0) 
            dq.pop_front();
        
        if (sums[dq.back()] - sums[dq.front() - 1] > maxSum) {
            maxSum = sums[dq.back()] - sums[dq.front() - 1];
            finalStart = dq.front();
            finalEnd = dq.back();
        }

        dq.push_back(i);
    }

    out << finalStart << " " << finalEnd << " " << maxSum << '\n';

    return 0;
}