Pagini recente » Cod sursa (job #3363229) | Cod sursa (job #3363241) | Cod sursa (job #3362249) | Cod sursa (job #3363223) | Cod sursa (job #3363240)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
deque<int>dq;
struct maxime {
int m, ind;
};
int n, k, sp[500008],a,sum_max=0, st=0, dr=0;
maxime max1[50008];
int main()
{
fin>>n>>k;
for (int i=1;i<=n;i++)
{
fin>>a;
sp[i]=sp[i-1]+a;
}
max1[n+1].m=-1e9;
for (int i=n;i>=1;i--)
{
if (max1[i+1].m<sp[i])
{
max1[i].m=sp[i];
max1[i].ind=i;
}
else
{
max1[i].m=max1[i+1].m;
max1[i].ind=max1[i+1].ind;
}
}
for (int i=0;i<=n-k;i++)
{
while (!dq.empty() && sp[dq.back()]>sp[i])
{
dq.pop_back();
}
dq.push_back(i);
if (sum_max<max1[dq.front()+k].m-sp[dq.front()])
{
sum_max=max1[dq.front()+k].m-sp[dq.front()];
st=dq.front()+1;
dr=max1[dq.front()+k].ind;
}
}
fout<<st<<' '<<dr<<' '<<sum_max;
}