Cod sursa(job #758429)
Utilizator | Data | 15 iunie 2012 17:10:18 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <iostream>
#include <fstream>
using namespace std;
const int MAX=5000001;
int v[MAX], dq[MAX], st=1, dr=1, K;
void stanga (int i)
{
if(dq[st]==i-K)
st++;
}
void dreapta (int i)
{
while(st<=dr&&v[i]<=v[dq[dr]])
dr--;
}
int main()
{
ifstream in("deque.in");
ofstream out("deque.out");
int N,i;
long long s=0;
in>>N>>K;
for(i=1; i<=N; i++)
in>>v[i];
for(i=1; i<=N; i++)
{
stanga(i);
dreapta(i);
dq[++dr]=i;
if(i>=K) s+=v[dq[st]];
}
out<<s;
return 0;
}