Cod sursa(job #1471231)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 13 august 2015 14:58:18
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

const int NM = 50005;

int N,K,Sol,F,L;
int Sum[NM];
deque< int > D;

int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);

     scanf("%d %d",&N,&K);

     for (int i = 1;i <= N;i++)
         scanf("%d",&Sum[i]),Sum[i] += Sum[i - 1];

     for (int i = 1;i <= N;i++)
     {
         while (!D.empty() && Sum[D.back()] > Sum[i])
               D.pop_back();

         D.push_back(i);

         if (Sol < Sum[i + K] - Sum[D.front()])
            Sol = Sum[i + K] - Sum[D.front()],F = D.front() + 1,L = i + K;
     }

     printf("%d %d %d\n",F,L,Sol);

   return 0;
}