Cod sursa(job #2221324)
Utilizator | Andrei Feodorov Nashik | Data | 13 iulie 2018 18:59:50 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
//#include <iostream>
#include <fstream>
using namespace std;
long long v[5000001],k,n,i,s=0;
int p,u,d[5000001];
void deque()
{
p=1;
u=0;
for(i=1; i<=n; i++){
while(p<=u && v[i]<=v[d[u]])u--;
d[++u]=i;
if(d[p]+k<=i)p++;
if(i>=k)s+=v[d[p]];
}
}
int main()
{
ifstream cin("deque.in");
ofstream cout("deque.out");
cin>>n>>k;
for(i=1; i<=n; i++)
cin>>v[i];
deque();
cout<<s;
return 0;
}