Cod sursa(job #662227)
| Utilizator | Data | 16 ianuarie 2012 09:53:22 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.49 kb |
#include<fstream>
#define nmax 5000001
using namespace std;
int n,k,V[nmax],coada[nmax];
long long suma=0;
int main(){
int head,tail;
ifstream f("deque.in");
ofstream g("deque.out");
f>>n>>k;
for(int i=1;i<=n;i++)
f>>V[i];
head=1;
tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&V[i]<=V[coada[tail]])
tail--;
tail++;
coada[tail]=i;
if(coada[head]==i-k)
head++;
if(i>=k)
suma=suma+V[coada[head]];
}
g<<suma;
f.close();
g.close();
return 0;
}