Cod sursa(job #1174570)
Utilizator | Hasmasan Dragos hasmasandragos | Data | 23 aprilie 2014 13:03:10 |
---|---|---|---|
Problema | Deque | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int vec[500005],i,n,k;
long long minim;
int main()
{deque<int>deck;
f>>n>>k;
for (i=1;i<=n;i++)
{f>>vec[i];
while (!deck.empty() && vec[deck.back()]>vec[i])
deck.pop_back();
deck.push_back(i);
if(deck.front()<=i-k)
deck.pop_front();
if (i>=k)
minim+=vec[deck.front()];
}
g<<minim<<'\n';
f.close();
g.close();
return 0;
}