Cod sursa(job #1847455)
| Utilizator | Data | 14 ianuarie 2017 17:22:16 | |
|---|---|---|---|
| Problema | Deque | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.51 kb |
#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> ii;
deque <ii> q;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k,i,x,s=0;
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
{
scanf("%d",&x);
while(!q.empty() && q.back().first>=x)
{
q.pop_back();
}
q.push_back(ii(x,i));
if(i>=k)
{
while(!q.empty() && i-q.front().second+1>k)
q.pop_front();
s=s+q.front().first;
}
}
printf("%d\n",s);
return 0;
}
