Cod sursa(job #2229677)
| Utilizator | Data | 7 august 2018 20:48:58 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.75 kb |
#include <fstream>
#include <deque>
using namespace std;
deque <int>D;
int v[5000005];
int main()
{ ifstream cin("deque.in");
ofstream cout("deque.out");
int n,k,s=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
D.push_back(1);
for(int i=2;i<=n;i++)
{
while(!D.empty())
{
if(v[D.back()]>v[i])
D.pop_back();
else
break;
}
D.push_back(i);
if(i-D.front()<k&&k<=i)
{
s+=v[D.front()];
}
else
if(k<=i)
{
D.pop_front();
s+=v[D.front()];
}
}
cout<<s;
return 0;
}
