Pagini recente » Cod sursa (job #2109113) | Cod sursa (job #856837) | Cod sursa (job #2455143) | Cod sursa (job #121359) | Cod sursa (job #967155)
Cod sursa(job #967155)
#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
struct Nod {
int val, poz;
};
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int a[50001], n, k, i, sume[50001], start, end, startaux;
long long rez;
deque<Nod> d;
void citire()
{
fin >> n >> k;
for(i = 1; i <= n; i++)
{
fin >> a[i];
}
}
void calcul_sume_partiale()
{
sume[0] = 0;
sume[1] = a[1];
for(i = 2; i <= n; i++)
{
sume[i] = sume[i-1] + a[i];
}
}
Nod make_nod(int val, int poz)
{
Nod p;
p.val = val;
p.poz = poz;
return p;
}
int main()
{
citire();
calcul_sume_partiale();
start = 0;
end = k;
rez = sume[k];
d.push_back(make_nod(0, 0));
for(i = k + 1; i <= n; i++)
{
while(!d.empty() && sume[i-k] < d.back().val)
{
d.pop_back();
}
d.push_back(make_nod(sume[i-k], i-k));
if(sume[i] - sume[d.front().poz] > rez)
{
rez = sume[i] - sume[d.front().poz];
start = d.front().poz + 1;
end = i;
}
}
fout << start << " " << end << " " << rez;
return 0;
}