Cod sursa(job #2221409)
Utilizator | Aliciuc Alexandru AlexandruGabriel | Data | 14 iulie 2018 02:11:20 |
---|---|---|---|
Problema | Deque | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.75 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
deque <long long> dq,pos;
long long suma=0;
long long x,n,k;
int main()
{
fin>>n>>k;
for (int i=1;i<=n;i++)
{
fin>>x;
while (x<dq.front() && !dq.empty())
{
dq.pop_front();
pos.pop_front();
}
if (dq.empty() || x>dq.front())
{
dq.push_front(x);
pos.push_front(i);
}
if (i>=k)
{
suma+=dq.back();
if (i-k+1>=pos.back())
{
dq.pop_back();
pos.pop_back();
}
}
}
fout<<suma;
return 0;
}