Pagini recente » Cod sursa (job #2893018) | Cod sursa (job #337686) | Cod sursa (job #2852079) | Cod sursa (job #2077569) | Cod sursa (job #2032033)
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int s[50001], Deque[50001];
int n, k, i, Max, Front, Back, x, st, dr, j;
int main()
{
fin>>n>>k;
for(i=1; i<=n; ++i)
{
fin>>x;
s[i]=s[i-1]+x;
}
/*for(i=1; i<=n; ++i) fout<<s[i]<<" ";
fout<<"\n";*/
Max=INT_MIN;
Front=1; Back=0;
for(i=1; i<=n; ++i)
{
/*fout<<"FRONT: "<<Front<<" BACK: "<<Back<<"\n";
for(j=Front; j<=Back; ++j) fout<<s[Deque[j]]<<" ";
fout<<"\n\n";*/
while(Front<=Back && s[i]<=s[Deque[Back]]) --Back;
Deque[++Back]=i;
if(Deque[Front]==i-k) ++Front;
if(s[i+k]-s[Deque[Front]]>Max)
{
Max=s[i+k]-s[Deque[Front]];
st=Deque[Front]+1; dr=i+k;
}
}
fout<<st<<" "<<dr<<" "<<Max<<"\n";
return 0;
}