Cod sursa(job #943915)
Utilizator | Data | 26 aprilie 2013 19:26:00 | |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <fstream>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int d[500000], k, i, a[5000001],dr,st,n;
long long s;
inline void stanga()
{
if(d[st]<=i-k) st++;
}
inline void dreapta()
{
while(st<=dr&&a[i]<a[d[dr]])
dr--;
}
int main()
{
in>>n>>k;
st=1; dr=0;
s=0;
for(i=1;i<=n;i++)
{
in>>a[i];
}
for(i=1;i<=n;i++)
{
if(i>k) stanga();
dreapta();
dr++;
d[dr]=i;
if(i>=k) s=s+a[d[st]];
}
out<<s;
return 0;
}