Cod sursa(job #1894304)

Utilizator danyvsDan Castan danyvs Data 26 februarie 2017 18:52:07
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int NMAX = 50005;

int V[NMAX], n, k;
int S[NMAX];
int l, r, sum_max;
deque < int > dq;

int main()
{
    fin >> n >> k;
    for (int i = 1; i <= n; ++ i)
        fin >> V[i];
    fin.close();
    for (int i = 1; i <= n; ++ i)
        S[i] = S[i - 1] + V[i];
    sum_max = -0x3f3f3f3f;
    for (int i = k; i <= n; ++ i)
        {
         while (!dq.empty() && S[dq.back()] > S[i - k])
            dq.pop_back();
         dq.push_back(i - k);
         if (S[i] - S[dq.front()] > sum_max)
            {
             sum_max = S[i] - S[dq.front()];
             l = dq.front() + 1;
             r = i;
            }
        }
    fout << l << " " << r << " " << sum_max << "\n";
    fout.close();
    return 0;
}