Cod sursa(job #2229675)
| Utilizator | Data | 7 august 2018 20:40:40 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.05 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++)
{
if(v[i]<=v[D.front()])
{
D.pop_front();
D.push_front(i);
}
else
{ while(1)
{
if(v[D.back()]>v[i])
{D.pop_back();}
else
{
D.push_back(i);
break;
}
}
}
if(i-D.front()<k&&k<=i)
{
s+=v[D.front()];
}
else
if(k<=i)
{ while(1)
{
if(i-D.front()>=k)
D.pop_front();
else
break;
}
s+=v[D.front()];
}
}
cout<<s;
return 0;
}
