Pagini recente » Cod sursa (job #1415101) | Cod sursa (job #1997455) | Cod sursa (job #1546240) | Cod sursa (job #2949208) | Cod sursa (job #516390)
Cod sursa(job #516390)
#include<iostream>
#include<fstream>
#define max_N 50005
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 >= 0)
while(S[i - K] <= S[Deque[Back]] && Back >= Front) Back --;
if(i - K >= 0)
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;
}