Pagini recente » Cod sursa (job #1709635) | Cod sursa (job #1145619) | Cod sursa (job #1602911) | Cod sursa (job #728564) | Cod sursa (job #516387)
Cod sursa(job #516387)
#include<iostream>
#include<fstream>
#define max_N 5000005
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int V[max_N], Deque[max_N], Front, Back, i, K, N, U, L, S[max_N], x1, x2, minim = -2199921;
long long Sum;
int main()
{
fin >> N >> K;
for(i = 1; i <= N; i ++)
{
fin >> V[i];
S[i] = S[i - 1] + V[i];
}
Front = 1, Back = 0;
for(i = 1; i <= N; i ++)
{
if(i - K >= 1)
while(S[i - K] <= S[Deque[Back]] && Back >= Front) Back --;
if(i - K >= 1)
Deque[++Back] = i - K;
while(S[Deque[Front]] > S[Deque[Front + 1]] && Deque[Front] >= 1)
Front ++;
if(i >= K && Deque[Front] > 0)
if(minim < S[i] - S[Deque[Front]])
{
minim = S[i] - S[Deque[Front]];
x1 = Deque[Front];
x2 = i;
}
}
fout << x1 + 1<< " " << x2 << " " << minim;
return 0;
}