Cod sursa(job #1370463)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 3 martie 2015 14:51:51
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <limits>


int main()
{
    std::ifstream fin("secv2.in");
    std::ofstream fout("secv2.out");

    int N, K;
    fin >> N >> K;

    std::vector<int> v(N);
    for (auto &i : v)
        fin >> i;

    std::vector<int> sums(N);
    for (auto i = 0; i < N; ++i)
        sums[i] = i ? sums[i - 1] + v[i] : v[i];

    int start = 0;
    int finalStart, finalEnd;
    int max_sum = std::numeric_limits<int>::min();
    for (int end = K; end < N; ++end) {
        if (sums[end - K] - (start ? sums[start - 1] : 0) < 0)
            start = end - K + 1;

        int crt_sum = sums[end] - (start ? sums[start - 1] : 0);
        if (crt_sum > max_sum) {
            max_sum = crt_sum;
            finalStart = start;
            finalEnd = end;
        }
    }

    fout << finalStart + 1 << " " << finalEnd + 1 << " " << max_sum << std::endl;
    return 0;
}