Cod sursa(job #2202552)

Utilizator MikeStrikeAgache Mihai MikeStrike Data 9 mai 2018 08:04:55
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <iostream>
#include <fstream>
#include <deque>
#define NMAX 5000001
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
deque <int> deck;
int v[NMAX],n,lg,lgcurent;
long long  S;
int main()
{
  in>>n>>lg;
  for(int i=1;i<=n;i++)
    in>>v[i];
deck.push_back(1);
for(int i=2;i<=n;i++)
{
    while(!deck.empty() && v[i]<=v[deck.back()])
        deck.pop_back();
    deck.push_back(i);
    lgcurent=i-deck.front();
    if(lgcurent>=lg) deck.pop_front();
    if(i>=lg)
        S=S+v[deck.front()];
}
out<<S;

    return 0;
}