Cod sursa(job #526104)
Utilizator | Giulia Stef giuliastef | Data | 27 ianuarie 2011 13:40:04 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
//Deque
#include <fstream>
#define MAXN 5000050
using namespace std;
int n,k,a[MAXN],deque[MAXN];
long long suma;
int main()
{
int i,front,back;
ifstream f("deque.in");
ofstream g("deque.out");
f>>n>>k;
for(i=1;i<=n;i++)
f>>a[i];
front=1,back=0; //deque vid initial
for(i=1;i<=n;i++)
{
while(front<=back && a[i]<a[deque[back]]) back--;
deque[++back]=i;
if(deque[front]==i-k) front++;
if(i>=k) suma+=a[deque[front]];
}
g<<suma<<"\n";
f.close();
g.close();
return 0;
}