Pagini recente » Cod sursa (job #1471824) | Cod sursa (job #2143524) | Cod sursa (job #1907977) | Cod sursa (job #846076) | Cod sursa (job #1721149)
#include <bits/stdc++.h>
using namespace std;
deque<int>q;
deque<int>d;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int a[500005],n,k,p=0,b[1006];
void Citire()
{
int i;
fin>>n>>k;
for(i=1;i<=n;i++)
fin>>a[i];
}
void Formare()
{
int i;
for(i=1;i<=n;i++)
a[i]=a[i-1]+a[i];
}
int main()
{
int i,inceput,sfarsit,x;
long long summax=-1250000001;
Citire();
Formare();
if(k==n)
{
fout<<"1"<<" "<<n<<" "<<a[n]<<"\n";
return 0;
}
for(i=1;i<=n;i++)
{
x=a[i];
while(!q.empty() and a[q.back()]>=x)
q.pop_back();
q.push_back(i);
while(!d.empty() and a[d.empty()]<=x)
d.pop_back();
d.push_back(i);
if(d.front()>=q.front())
{
if(summax<=a[d.front()]-a[q.front()] and d.front()-q.front()>=k)
{
summax=a[d.front()]-a[q.front()];
inceput=q.front()+1;
sfarsit=d.front();
}
}
else if(d.front()<q.front())
{
if(summax<=a[d.front()]-a[q.front()] and q.front()-d.front()>=k)
{
summax=a[d.front()]-a[q.front()];
inceput=d.front()+1;
sfarsit=q.front();
}
}
}
fout<<inceput<<" "<<sfarsit<<" "<<summax<<"\n";
fin.close();
fout.close();
}