Pagini recente » Cod sursa (job #2729656) | Cod sursa (job #1747683) | Cod sursa (job #1928920) | Cod sursa (job #2848671) | Cod sursa (job #2887524)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("grader_test7.in");
ofstream out("deque.out");
long long n, k, i, suma, x, dFront, dBack, dSize;
pair<long long, long long> deq[500010];
int main()
{
in >> n >> k;
dFront = n - 2;
dBack = n - 1;
dSize = 0;
for(i = 1; i <= k; i++)
{
in>>x;
while(dSize > 0 && deq[dBack].first >= x)
{
dBack++;
dSize--;
}
dBack--;
dSize++;
deq[dBack] = make_pair(x, i);
}
suma = deq[dFront].first;
for(i = k + 1; i <= n; i++)
{
in>>x;
while(dSize > 0 && i - deq[dFront].second >= k)
{
dFront--;
dSize--;
}
while(dSize > 0 && deq[dBack].first >= x)
{
dBack++;
dSize--;
}
dBack--;
dSize++;
deq[dBack] = make_pair(x, i);
suma += deq[dFront].first;
}
out<<suma;
return 0;
}