Pagini recente » Cod sursa (job #1377015) | Cod sursa (job #3281398) | Cod sursa (job #1245221) | Cod sursa (job #1560057) | Cod sursa (job #2359746)
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int n, Deque1[50100], Deque2[50100], dr1, dr2, k, p1, p2;
long long sol = -1000000000, S[50100];
int main()
{
f >> n >> k;
for(int i=1; i<=n; i++)
{
int x;
f >> x;
S[i] = S[i-1] + x;
}
dr1 = dr2 = 0;
for(int i=1; i<=n; i++)
{
while(dr1 >= 1 && S[i] <= S[Deque1[dr1]]) dr1--;
while(dr2 >= 1 && S[i] >= S[Deque2[dr2]]) dr2--;
Deque1[++dr1] = i;
Deque2[++dr2] = i;
if(abs(Deque1[1] - Deque2[1]) >= k)
{
long long val = S[Deque2[1]] - S[Deque1[1]];
if(val > sol)
{
p1 = Deque1[1] + 1;
p2 = Deque2[1];
sol = val;
}
}
}
g << p1 << ' ' << p2 << ' ' << sol << '\n';
return 0;
}