Cod sursa(job #931216)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 28 martie 2013 08:37:07
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
# include <fstream>
# define maxn 5000010
using namespace std;

int N,K;
int A[maxn],Deque[maxn];
int prim,ultim;
long long S;

int main()
{
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    fin >> N >> K;
    prim = 1 , ultim = 0;
    for( int i = 1 ; i <= N ; ++i )
    {
        fin >> A[i];
        while ( prim <= ultim && A[i] <= A[ Deque[ultim] ]) ultim--;
        Deque[++ultim] = i;
        if (Deque[prim] == i-K) prim++;
        if (i >= K) S += A[ Deque[prim]];
    }
    fout << S;
    fin.close();
    fout.close();
}