Cod sursa(job #2239742)
Utilizator | Sabau Florin Vlad Haesteinn | Data | 11 septembrie 2018 19:16:09 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
deque< pair<int,int> > dq;
int n,k;
long long smin;
fin>>n>>k;
int tmp;
for(int i=0;i<n;i++)
{
fin>>tmp;
while(dq.size()>0&&dq.back().first>=tmp)
dq.pop_back();
dq.push_back(make_pair(tmp,i));
if(dq.front().second == i - k)
dq.pop_front();
if(i >= k-1)
smin+=dq.front().first;
}
fout<<smin;
return 0;
}