Pagini recente » Cod sursa (job #981652) | Cod sursa (job #731815) | Cod sursa (job #799832) | Cod sursa (job #2109291) | Cod sursa (job #1794825)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
deque<int>maxim;
deque<int>minim;
int a[50005],sum[50005],n,k;
void Citire()
{
int i;
fin>>n>>k;
for(i=1;i<=n;i++)
fin>>a[i];
fin.close();
}
void Rezolvare()
{
int i,smaxim=-10000000,ind,ind1,x;
sum[1]=a[1];
for(i=2;i<=n;i++)
sum[i]=sum[i-1]+a[i];
for(i=1;i<=n;i++)
{
x=sum[i];
while(!maxim.empty() and sum[maxim.back()]<x)
maxim.pop_back();
while(!minim.empty() and sum[minim.back()]>x)
minim.pop_back();
maxim.push_back(i);
minim.push_back(i);
if(abs(maxim.front()-minim.front())<k)
maxim.pop_front();
if(!maxim.empty() and !minim.empty() and sum[maxim.front()]-sum[minim.front()]>smaxim)
{
smaxim=sum[maxim.front()]-sum[minim.front()];
ind=minim.front()+1;
ind1=maxim.front();
}
}
fout<<ind<<" "<<ind1<<" "<<smaxim<<"\n";
}
int main()
{
Citire();
Rezolvare();
return 0;
}