Cod sursa(job #778903)
Utilizator | Tudor Costin Razvan costyrazvy | Data | 16 august 2012 09:51:07 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
using namespace std;
deque <int> v;
long long sum;
int a[5000001],i,n,k;
int main()
{
ifstream f("deque.in");
ofstream g("deque.out");
f>>n>>k;
for (i=1; i<=n; i++)
{ f>>a[i];
while (!v.empty() && a[v.back()]>=a[i]) v.pop_back();
v.push_back(i);
if (v.front()<=i-k) v.pop_front();
if (i>=k) sum=sum+a[v.front()];
}
g<<sum;
f.close();
g.close();
return 0;
}